Hardin 'nuff for you? ********************* As a result of a serendipitous misunderstanding, I have recently derived much enjoyment from investigating this topic. In an effort to bring its puzzle aspects to a wider audience, convince everybody what a brilliant mathematician I am, and delay the looming necessity to write the results up properly, I have prepared the following sketch. Solutions to (some of) the numbered problems may be forthcoming should suspicion subsequently arise that anybody else gives a stuff. A `Hardin array' is defined to be a binary assignment to the nodes of a rectangular m x n grid, such that every 2 x 2 square has some diagonal given equal values; that is, no square is permitted to belong to the set C C C D D C D D D D C D D C C C [Circumventing proportional spacing propels the aliases C = 0 , D = 1 .] I am interested in evaluating T(m, n) = half the number of distinct m x n Hardin arrays, and in estimating its asymptotic behaviour for large m, n . It is not difficult to establish that there is a constant c such that as m, n -> oo , in a rough sense T(m, n) approximates c^(m n) -- rather more precisely, log T(m, n) ~ m n log c . Extrapolation via Aiken delta^2, Wynn rho, suggests (optimistically) that maybe c = 1.5396... . Easy combinatorial constructions establish the rigorous elementary bounds sqrt2 = 1.414213... < c < 1.618034... = tau . ((1)) For more refined bounds which approach the actual value, develop linear recurrences for small fixed m via classical Markov process analysis, then apply Fekete subadditivity (and stop dropping names). For example at m = 5 , we find that f(n) = T(m, n) satisfies f(n) - 16 f(n-1) + 65 f(n-2) - 92 f(n-3) + 48 f(n-4) - 8 f(n-5) = 0 , whence numerically f(n) = (1.39119...) (10.6829...)^n + (smaller terms ...) . Since any m x n Hardin array can be decomposed into roughly m/5 of these arrays, we deduce the upper bound c < 1.6060 = (10.6829)^(1/5) , improving on the earlier elementary bound. Applying similar methods at m = 20 yields tighter bounds 1.504113 < c < 1.555473 . ((2)) The polynomials associated with the recurrences apparently have unexpected properties, the least bizarre being irreducibility; all roots real; all roots positive (upper). ((3)) I'm not going to show you more of these polynomials here. At m = 17 say, they have degree 2123 , with some components over 1300 decimal digits! Establishing lower bounds involves instead a subset of Hardin arrays: those `bordered' with C along all four edges, and counted by S(m, n) . The border acts as cement, allowing m x n bordered arrays to be tiled together (borders overlapping), so building larger arrays of size (k m - k + 1) x (l n - l + 1) . A key stage in the recurrence construction involves characterising those distinct binary columns requiring consideration, leading to the following `accessibility' problem: Develop an algorithm to decide, in time and space linear in m , whether a given m-vector can occur as a column in a bordered m x n Hardin array (for sufficiently large n ). ((4)) For example with m = 15 columns CDDDDDDDDDDDDDC and CDDCCDDCDDCCDDC are accessible (via columns bordered by C...C) from an initial CCCCCCCCCCCCCCC ; however CDDCCCCCCCCCCCC is not. This puzzle has a wonderfully compact and elegant solution. Once you get it right, after the fourth or fifth fumble, that is. But having finally cracked it, count the number a(m) of accessible vectors, compared to the total number b(m) = 2^(m-2) of bordered vectors: m 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ... a(m) 1, 1, 2, 3, 6, 10, 20, 35, 70, 126, 252, 462, ... b(m) 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ... [I blush to confess that I went searching for a(m) in OEIS ; even then, I couldn't at first get my head around what it kept trying to tell me.] But amazingly, these seem to be simply the central binomial coefficients (Conjecture) a(m) = (m-1)_C_[(m-1)/2] ?! ((5)) though I have at present no idea why. Anyway on this assumption, Stirling's approximation yields a welcome reduction factor a(m)/b(m) ~ 1.595770 / sqrt(m) in the number of columns required -- a saving which squares up in space, a(m) representing the order of a rather hefty matrix. I mentioned previously the (presumed) conjecture -- mentioned [??] cryptically under OEIS A078099 -- to the effect that Hardin arrays correspond to grid-colourings of the same-size using three colours: here P, Q, R . Note that nodes sharing an edge are assigned distinct colours; and the top-left node of both grids remains constant, C and P resp. Specify a bijective mapping between m x n Hardin arrays and grid three- colourings. ((6)) While this is trickier than might be expected, there awaits again a solution both short and sweet. Appendix:: sample 9 x 9 Hardin array, together with corresponding grid 3-colouring: C D C C D C C C C P R P Q R Q P Q P D C C C C C D C D R P Q P Q P R P R C C D C C C C D D P Q R Q P Q P R Q C D D D C D C C D Q R P R Q R Q P R D D C D D C D C C R P Q P R Q R Q P ; D D D C D D D D C P R P Q P R P R Q C D D D D D D C C Q P R P R P R Q P D D D D C D C C C P R P R Q R Q P Q D D D D D C C D C R P R P R Q P R P and a bordered 8 x 8 Hardin array, illustrating some of 35 distinct accessible columns (or rows): C C C C C C C C C C D C D C C C C C C D C C C C C C D D D C D C C D D D C C C C C C D D D C C C C C C D C C C C C C C C C C C C Short tables -- best viewed sans pesky proportional spacing -- of T(m, n) , counting m x n Hardin arrays with C at top-left: m\n 1 2 3 4 5 6 7 1 1 2 4 8 16 32 64 2 2 6 18 54 162 486 1458 3 4 18 82 374 1706 7782 35498 4 8 54 374 2604 18150 126534 882180 5 16 162 1706 18150 193662 2068146 22091514 6 32 486 7782 126534 2068146 33865632 554916090 7 64 1458 35498 882180 22091514 554916090 13956665236 and S(m, n) , counting m x n Hardin arrays with C around border: m\n 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 3 1 1 2 3 5 8 13 21 34 4 1 1 3 7 17 41 99 239 577 5 1 1 5 17 64 235 870 3211 11867 6 1 1 8 41 235 1322 7479 42267 238958 7 1 1 13 99 870 7479 64914 562213 4876632 8 1 1 21 239 3211 42267 562213 7474305 99480399 9 1 1 34 577 11867 238958 4876632 99480399 2033739170 Fred Lunnon Maynooth 22/02/14