Notes on the Conant Gasket, the Conant Lattice, and Associated Sequences N. J. A. Sloane Preliminary version, August 23 2020 Summary: The Conant structure can be described either as a finer and finer dissection of a square (the "Conant Gasket") or as a grid drawn on the first quadrant of the integer lattice Z X Z (the "Conant Lattice"). The two descriptions are equivalent. The Gasket version is described in A328078, where there are a series of pictures showing successive generations G_0, G_1, G_2, ... of the dissection of the square. But the Lattice version is easier to analyze. The following description of the dissection used in the Gasket Version is based on an email message from Robert Fathauer from October 2019 Start with a unit square. 1. Draw a vertical line from bottom to top, dividing the square in half. 2. Go to the left edge, and halfway up draw a line from left to right. Stop when you reach the vertical line. 3. Return to the bottom edge and draw vertical lines at the midpoints of the remaining intervals (at the 1/4 and 3/4 points for the second pass), from bottom to top. If you reach a line, stop, skip to the next line and start again, stopping the next time you reach a line. 4. Return to the left edge and draw horizontal lines at the midpoints of the remaining intervals, from left to right. If you reach a line, stop, skip to the next line and start again, stopping the next time you reach a line. Repeat steps 3 and 4. A328078 is the sequence of the number of cells in the n-th generation G_n of the dissection. A328080 is the subsequence giving the number of cells in even-numbered generations G_{2n}. The Conant Lattice is easier to describe mathematically. It is drawn in the first quadrant of the integer lattice Z X Z, that is, the points {(m,n): m >=0, n >= 0}. In the bottom left corner of the grid (that is, starting at the origin (0,0)), there are successive even generations of the dissection, enlarged and nested: G_0 inside G_2 inside G_4 inside G_6 ... This is offically the Even Conant Lattice, and it is shown as a link in A328078, see N. J. A. Sloane, The Even Conant Lattice The odd-numbered generations G_1, G_3, G_5, ..., are similarly nested, and this produces the Odd Conant Lattice, also shown in A328078. At the grid points (m,n) in the Even Conant Lattice there may be vertical or horizontal lines joining that point to its North and/or East neighbors. The following definitions and recurrences are essentially due to Doug McIlroy (email, Feb 6, 2020). Define v(m,n) to be 1 if there is a vertical line joining (m,n) to (m,n+1), or 0 if there is no such line, and define h(m,n) to be 1 if there is a horizontal line joining (m,n) to (m+1,n), or 0 if there is no such line. Then v and h are given by the following recurrences: if m=0 or n=0 then v(m,n) = h(m,n) = 1; if m=1 and n=1 then v(m,n) = 1, h(m,n) = 0; otherwise, if m is even, v(m,n) = v(m/2, floor(n/2)), if m is odd, v(m,n) = Sum_{k=0..floor(n/2)} h((m-1)/2,k) mod 2; if n is even, h(m,n) = h(floor(m/2), n/2), if n is odd, h(m,n) = Sum_{k=0..m} v(k,n) mod 2. It is not difficult to see that these equations exactly describe the process that constructs the dissection. The lack of symmetry between the equations for v and h is because the vertical lines are drawn before the horizontal lines. We can associate each cell in the Conant Lattice with the point (m,n) at its bottom left corner, where of course we have v(m,n) = h(m,n) = 1. It follows that the number of cells in G_{2k} = Sum Sum_{ 0 <= m,n <= 2^k-1 } v(m,n)*h(m,n). Here is Maple code: # v(i,j) = 1 iff there is a vertical line upwards at (i,j) in even generations # h(i,j) = 1 iff there is a horizontal line to the right at (i,j) in even generations v:=proc(i,j) local k; global h; option remember; if (i=0 or j=0) then 1; elif (i=1 and j=1) then 1; elif type(i,even) then v(i/2, floor(j/2)); else ( add( h((i-1)/2,k),k=0..floor(j/2) ) ) mod 2; fi; end; h:=proc(i,j) local k; global v; option remember; if (i=0 or j=0) then 1; elif (i=1 and j=1) then 0; elif type(j,even) then h(floor(i/2), j/2); else ( add( v(k,j),k=0..i ) ) mod 2; fi; end; # To get the (v,h) label for grid-point (i,j) in the Even Conant Lattice: s:=(i,j) -> [v(i,j),h(i,j)]; # To get the first 2^k labels for row m: rho:=(m,k)->[seq([v(i,m),h(i,m)],i=0..2^k-1)]; # To get the first 2^k labels for column m: col:=(m,k)->[seq([v(m,i),h(m,i)],i=0..2^k-1)]; These labels are shown in the drawing in A328078: N. J. A. Sloane, The Even Conant Lattice # To get the number of cells in G_{2k}. This is Sum Sum_{ 0 <= i,j <= 2^k-1 } v(i,j)*h(i,j): C1 := n -> add( add( v(i,j)*h(i,j), j=0..2^n-1), i=0..2^n-1); # A328080 [seq(C1(n),n=0..8)]; # giving (the start of) A328080: [1, 3, 9, 27, 91, 325, 1201, 4527, 17227] There are similar recurrences for the Odd Conant Lattice We just give the Maple code: # V(i,j) = 1 iff there is a vertical line upwards at (i,j) in odd generations # H(i,j) = 1 iff there is a horizontal line to the right at (i,j) in odd generations V:=proc(i,j) local k; global v,h; option remember; if (i=0 or j=0) then 1; elif (i=1 and j=1) then 1; elif type(i,even) then v(i/2, floor(j/2)); else (0 + add( h((i-1)/2,k),k=0..floor(j/2) ) ) mod 2; fi; end; H:=proc(i,j) local k; global v,h; option remember; if (i=0) then (1+(-1)^j)/2; elif (j=0) then 1; elif (i=1 and j=1) then 0; elif type(j,odd) then 0; else h(floor(i/2), floor(j/2)); fi; end; # To get the (v,h) label for grid-point (i,j) in the Odd Conant Lattice: sO:=(i,j) -> [V(i,j),H(i,j)]; # To get the first 2^k labels for row m: rhoO:=(m,k)->[seq([V(i,m),H(i,m)],i=0..2^k-1)]; # To get the first 2^k labels for column m: colO:=(m,k)->[seq([V(m,i),H(m,i)],i=0..2^k-1)]; These labels are shown in the drawing in A328078: %H N. J. A. Sloane, The Odd Conant Lattice # To get the number of cells in G_{2k+1}. This is Sum Sum_{ 0 <= i,j <= 2^k-1 } V(i,j)*H(i,j): C5 := n -> add( add( V(i,j)*H(i,j), j=0..2^n-1), i=0..2^n-1); # A337262 [seq(C5(n),n=1..8)]; # giving (the start of) A337262: [2, 5, 15, 48, 169, 618, 2319, 8804] # Number of paths to origin (A337266): 1, 1,1, 1,2,1, 1,3,1,1, 1,1,4,2,1, 1,1,5,2,1,1, 1,2,6,2,1,2,1, 1,3,0,8,3,3,1,1, 1,1,3,0,11,0,4,2,1, 1,1,1,3,11,0,4,2,1,1, 1,2,1,4,14,11,4,6,1,2,1,