Notation and conventions
We write N = { 0 , 1 , 2 , … } \mathbb{N}=\{0,1,2,\ldots\} N = { 0 , 1 , 2 , … } and Z \mathbb{Z} Z for the integers, and use log 2 \log_2 log 2 for the binary logarithm and log \log log for the natural logarithm. An integer is dyadic if it is a power of two. For m ≥ 1 m \ge1 m ≥ 1 , lb ( m ) \operatorname{lb}(m) lb ( m ) is the largest power of two dividing m m m . For m ≥ 0 m \ge0 m ≥ 0 , s 2 ( m ) s_2(m) s 2 ( m ) counts the ones in its binary expansion. For nonnegative integers, x & y x \mathbin{\&} y x & y has binary digits equal to the products of the corresponding digits of x x x and y y y . Thus x & y = 0 x \mathbin{\&} y=0 x & y = 0 when they have no common digit equal to one.
Generating-function identities are understood as identities of formal power series. We write [ z j ] Q [z^j]Q [ z j ] Q for the coefficient of z j z^j z j in Q Q Q , with value zero for j < 0 j<0 j < 0 . For a polynomial Q Q Q , supp ( Q ) \operatorname{supp}(Q) supp ( Q ) is the set of its nonzero coefficient indices, # supp ( Q ) \#\operatorname{supp}(Q) # supp ( Q ) its size, and ∥ Q ∥ \lVert Q\rVert ∥ Q ∥ the sum of the absolute values of its coefficients. The indicator 1 E \mathbf{1}_{\mathcal{E}} 1 E is 1 when the condition E \mathcal{E} E holds and 0 otherwise. For n ≥ 0 n \ge0 n ≥ 0 , we set ( n j ) = 0 \binom{n}{j}=0 ( j n ) = 0 unless 0 ≤ j ≤ n 0 \le j \le n 0 ≤ j ≤ n .
Introduction
From toothpicks to the honeycomb
Omar E. Pol introduced the toothpick sequence, OEIS A139250, in 2008 [7 ] . Starting with one segment on the square lattice, the construction adds a perpendicular segment whose midpoint meets each exposed end. Applegate, Pol, and Sloane [2 ] studied this sequence in 2010, giving recurrences based on powers of two, generating functions, and asymptotic results. They also related the growth to the Ulam-Warburton cellular automaton and examined other local rules.
Pol introduced the V-toothpick variant in 2009 as A161206 [7 ] . Its pieces lie on the honeycomb lattice, and the counting mechanism of the square-lattice construction does not directly apply. The OEIS entry describes the growth but gives no general formula for its terms. We obtain an expression for its generating function, an algorithm for an arbitrary term, and its leading asymptotic form. The algorithm computes a term without computing all preceding terms. To our knowledge, this is the first such representation and algorithm with polynomial cost in the binary input length for this variant.
Consider the honeycomb lattice, that is, the tiling of the plane by regular hexagons with sides of length one. A V-toothpick is a piece made of two sides of the lattice that meet at a vertex at an angle of 120 degrees. This vertex is the apex of the piece and the two other endpoints are its ends.
The game starts with an empty plane. At round 1 one piece is placed. At each later round a new piece is placed at every free end of the structure. A free end is an end of a piece that touches no other piece. The new piece has its apex at the free end and covers the two other sides of the lattice that leave this vertex. All pieces of a round are placed simultaneously. When two new pieces reach the same vertex in the same round, this vertex is not a free end and nothing grows from it later. Figure 1 shows the first rounds and Figure 2 shows the structure after 32 rounds.
Figure 1. The structure after rounds 1, 2, 3, 4, and 6. The pieces of the last round are in red and the dots are the free ends.
Figure 2. The V-toothpick structure after 32 rounds. It contains a ( 32 ) = 1005 a(32)=1005 a ( 32 ) = 1005 pieces.
Let a ( n ) a(n) a ( n ) be the number of pieces after n n n rounds, with a ( 0 ) = 0 a(0)=0 a ( 0 ) = 0 , and let t ( n ) = a ( n ) − a ( n − 1 ) t(n)=a(n)-a(n-1) t ( n ) = a ( n ) − a ( n − 1 ) be the number of pieces placed at round n n n . The first values are
a ( n ) = 0 , 1 , 3 , 7 , 13 , 21 , 31 , 43 , 57 , 69 , 81 , 99 , 123 , … a(n)=0,\ 1,\ 3,\ 7,\ 13,\ 21,\ 31,\ 43,\ 57,\ 69,\ 81,\ 99,\ 123,\ldots a ( n ) = 0 , 1 , 3 , 7 , 13 , 21 , 31 , 43 , 57 , 69 , 81 , 99 , 123 , …
The increments form entry A161207 of the OEIS [7 ] .
The question
The definition gives a ( n ) a(n) a ( n ) by playing the game through all the preceding rounds. Finite propagation places every affected vertex in a region with O ( n 2 ) O(n^2) O ( n 2 ) sites. A direct simulation visits successive fronts in this region, whereas the question here is whether one can recover the count from the binary expansion of n n n . Even the number of simulated rounds is exponential in the length of that input.
The irregular increments in Figure 3 suggest that the dyadic repetition is more complicated than for the original toothpick sequence. We seek a description that accounts for all vertices that appear inside each region, including those reached when growing parts of the structure meet.
Figure 3. The number t ( n ) t(n) t ( n ) of pieces placed at round n n n , for n ≤ 256 n \le256 n ≤ 256 . The dotted lines mark the powers of two.
Results
We use polynomials to count the vertices that appear at successive times under the local growth rule of § 3 . Each appearance is called a birth . The polynomials P 2 , P 4 , P 8 , … P_2,P_4,P_8,\ldots P 2 , P 4 , P 8 , … are indexed by the powers of two. The polynomial P q P_q P q counts, round by round, the births in a finite region of the structure that we call a diamond of size q q q . Its definition is given in § 3 . The first two are P 2 = 1 + z P_2=1+z P 2 = 1 + z and P 4 = 1 + 2 z + 2 z 2 + z 3 + 2 z 4 + 2 z 5 P_4=1+2z+2z^2+z^3+2z^4+2z^5 P 4 = 1 + 2 z + 2 z 2 + z 3 + 2 z 4 + 2 z 5 . The cone polynomial C r C_r C r counts births in a triangular region of size r r r , also defined there. Set
G ( w ) = ∏ i ≥ 0 ( 1 + 2 w 2 i ) = ∑ j ≥ 0 2 s 2 ( j ) w j . G(w)=\prod_{i\ge0}(1+2w^{2^i})=\sum_{j\ge0}2^{s_2(j)}w^j. G ( w ) = i ≥ 0 ∏ ( 1 + 2 w 2 i ) = j ≥ 0 ∑ 2 s 2 ( j ) w j .
Theorem 1. Let A ( z ) = ∑ n ≥ 0 a ( n ) z n A(z)=\sum_{n\ge0}a(n)z^n A ( z ) = ∑ n ≥ 0 a ( n ) z n . In the ring of formal power series,
A ( z ) = ( 1 + z ) ( 1 + 2 z 2 ) 1 − z ( z 1 − z + 2 ∑ q = 2 , 4 , 8 , … z 2 q + 1 P q ( z ) 1 − z 4 q ) . (1) A(z)=\frac{(1+z)(1+2z^2)}{1-z}\left(\frac{z}{1-z}+2\sum_{q=2,4,8,\ldots}\frac{z^{2q+1}P_q(z)}{1-z^{4q}}\right). \tag*{(1)} A ( z ) = 1 − z ( 1 + z ) ( 1 + 2 z 2 ) ( 1 − z z + 2 q = 2 , 4 , 8 , … ∑ 1 − z 4 q z 2 q + 1 P q ( z ) ) . (1) The equivalent expression in terms of cones is
A ( z ) = ( 1 + z ) ( 1 + 2 z 2 ) 1 − z ( z 1 − z + 2 ∑ q = 2 , 4 , 8 , … z 2 q ( C q ( z ) − 1 ) G ( z 4 q ) ) . A(z)=\frac{(1+z)(1+2z^2)}{1-z}\left(\frac{z}{1-z}+2\sum_{q=2,4,8,\ldots}z^{2q}(C_q(z)-1)G(z^{4q})\right). A ( z ) = 1 − z ( 1 + z ) ( 1 + 2 z 2 ) ( 1 − z z + 2 q = 2 , 4 , 8 , … ∑ z 2 q ( C q ( z ) − 1 ) G ( z 4 q ) ) . Each term of the first sum says that a diamond of size q q q appears for the first time at a fixed round and then again every 4 q 4q 4 q rounds. Only the terms with 2 q + 1 ≤ n 2q+1\le n 2 q + 1 ≤ n contribute to the coefficient of z n z^n z n , so the sum is well defined.
For example, the contribution of q = 2 q=2 q = 2 to the increment series ( 1 − z ) A ( z ) (1-z)A(z) ( 1 − z ) A ( z ) begins with
2 z 5 ( 1 + z ) 2 ( 1 + 2 z 2 ) = 2 z 5 + 4 z 6 + 6 z 7 + 8 z 8 + 4 z 9 . 2z^5(1+z)^2(1+2z^2)=2z^5+4z^6+6z^7+8z^8+4z^9. 2 z 5 ( 1 + z ) 2 ( 1 + 2 z 2 ) = 2 z 5 + 4 z 6 + 6 z 7 + 8 z 8 + 4 z 9 .
The rational term contributes 6 at each round n ≥ 4 n\ge4 n ≥ 4 . Hence t ( 5 ) = 8 t(5)=8 t ( 5 ) = 8 , t ( 6 ) = 10 t(6)=10 t ( 6 ) = 10 , and t ( 7 ) = 12 t(7)=12 t ( 7 ) = 12 , which give a ( 5 ) = 21 a(5)=21 a ( 5 ) = 21 , a ( 6 ) = 31 a(6)=31 a ( 6 ) = 31 , and a ( 7 ) = 43 a(7)=43 a ( 7 ) = 43 .
The geometric construction in § 4 shows that P q P_q P q has at least 2 q − 2 2q-2 2 q − 2 nonzero coefficients. Expanding a polynomial of size comparable to n n n would therefore require at least as many operations. The following algorithm avoids this expansion. The class FP consists of functions computable in time polynomial in the length of the input [3 ] .
Theorem 2. There is an algorithm that takes as input the binary expansion of an integer n ≥ 0 n\ge0 n ≥ 0 and returns a ( n ) a(n) a ( n ) and t ( n ) t(n) t ( n ) . With ℓ = ⌊ log 2 ( n + 3 ) ⌋ + 1 \ell=\lfloor\log_2(n+3)\rfloor+1 ℓ = ⌊ log 2 ( n + 3 )⌋ + 1 , it performs O ( ℓ 8 ) O(\ell^8) O ( ℓ 8 ) arithmetic operations on integers of O ( ℓ ) O(\ell) O ( ℓ ) bits. In particular the maps n ↦ a ( n ) n\mapsto a(n) n ↦ a ( n ) and n ↦ t ( n ) n\mapsto t(n) n ↦ t ( n ) belong to the class FP.
Here the input has length of order log n \log n log n , so the running time is polynomial in log n \log n log n . The same program works for every n n n and needs no precomputed table. We do not claim that the exponent 8 is optimal. The computations in Section 6 include indices up to 10 100 10^{100} 1 0 100 , with the outputs checked by two separately written implementations.
The number of births in a diamond of size q q q is asymptotic to κ q 2 \kappa q^2 κ q 2 for a computable constant κ = 0.6879156855 … \kappa= 0.6879156855\ldots κ = 0.6879156855 … . Theorem 32 shows that
a ( n ) = n 2 Ψ ( n 2 k ) + O ( n log 2 3 ( log n ) 2 ) , k = ⌊ log 2 n ⌋ , a(n)=n^2\Psi\left(\frac{n}{2^k}\right)+O\left(n^{\log_2 3}(\log n)^2\right), \qquad k=\lfloor\log_2 n\rfloor, a ( n ) = n 2 Ψ ( 2 k n ) + O ( n l o g 2 3 ( log n ) 2 ) , k = ⌊ log 2 n ⌋ ,
for a continuous function Ψ \Psi Ψ on [ 1 , 2 ] [1,2] [ 1 , 2 ] determined by two functional equations. The ratio a ( n ) / n 2 a(n)/n^2 a ( n ) / n 2 has no limit. Its lower and upper limits are 9 κ / 8 9\kappa/8 9 κ /8 and 3 κ / 2 3\kappa/2 3 κ /2 . Theorem 25 gives a series for κ \kappa κ whose first N N N terms have error at most 4 / 3 N 4/3^N 4/ 3 N and require cones of size at most 4 N 4N 4 N .
Theorem 34 also shows that the differences X k = C 2 k − C 2 k − 1 X_k=C_{2^k}-C_{2^k-1} X k = C 2 k − C 2 k − 1 have only O ( k 3 ) O(k^3) O ( k 3 ) nonzero coefficients. It computes these coefficients using cones and triangles of size O ( k ) O(k) O ( k ) .
The recursive construction computes its initial data by applying the growth rule to triangles of side O ( log n ) O(\log n) O ( log n ) . Whether a fixed finite family of numerical recurrences suffices remains open.
Geometric reduction and coefficient extraction
Earliest births follow Pascal’s triangle modulo 2. Along certain lines of constant coordinate sum, this pattern prevents further growth and separates the structure into finite diamonds. The repeated occurrence of a diamond of size q q q , every 4 q 4q 4 q rounds, gives the denominator in (1) .
Each diamond reduces to smaller diamonds and cones. A translation identity for truncated triangles then reduces the cones, except for domains of size O ( log n ) O(\log n) O ( log n ) . The algorithm stores these identities as a graph of polynomial expressions. A coefficient or a partial sum is evaluated by following this graph. The queried indices lie in a polynomial number of residue classes modulo the dyadic sizes, which bounds the number of evaluations.
Related work
The square-lattice analysis of Applegate, Pol, and Sloane [2 ] provides the closest enumerative comparison. Here the relevant finite regions also occur at dyadic scales, but their evolution requires additional cone polynomials. Their reduction gives a uniform algorithm as the queried index grows.
The complexity of prediction for cellular automata depends on the rule and the input model. Neary and Woods [5 ] show that predicting Rule 110 can encode any decision problem solvable in polynomial time, through a transformation using logarithmic space. Such results concern families of initial configurations and a prediction task. Our input consists only of a time index, with a fixed initial seed, and our output is a global count. We make no claim about prediction from arbitrary initial data.
The representation used below is related to random access in compressed objects. Bille et al. [4 ] retrieve characters from a string specified by a grammar that generates that string alone, without expanding it. Our nodes instead describe signed sums of shifted, potentially overlapping polynomials. The residue lemma is needed to bound how many coefficient queries these sums generate.
The model and the birth polynomials
The lattice and the growth rule
All time indices start at 0, unless global round numbers are specified. We describe the honeycomb lattice as a bipartite graph. Its vertices are the points A ( x , y ) A(x,y) A ( x , y ) and B ( x , y ) B(x,y) B ( x , y ) with ( x , y ) ∈ Z 2 (x,y)\in\mathbb{Z}^2 ( x , y ) ∈ Z 2 . We also write A ( x , y ) = ( 0 , x , y ) A(x,y)=(0,x,y) A ( x , y ) = ( 0 , x , y ) and B ( x , y ) = ( 1 , x , y ) B(x,y)=(1,x,y) B ( x , y ) = ( 1 , x , y ) , so that a vertex is a triple ( p , x , y ) (p,x,y) ( p , x , y ) with p ∈ { 0 , 1 } p \in\{0,1\} p ∈ { 0 , 1 } . The neighbors of A ( x , y ) A(x,y) A ( x , y ) are B ( x , y ) B(x,y) B ( x , y ) , B ( x − 1 , y ) B(x-1,y) B ( x − 1 , y ) , and B ( x , y − 1 ) B(x,y-1) B ( x , y − 1 ) . Consequently the neighbors of B ( x , y ) B(x,y) B ( x , y ) are A ( x , y ) A(x,y) A ( x , y ) , A ( x + 1 , y ) A(x+1,y) A ( x + 1 , y ) , and A ( x , y + 1 ) A(x,y+1) A ( x , y + 1 ) .
Definition 3. Let D D D be a set of vertices and let s ∈ D s \in D s ∈ D be a vertex called the seed. Time is discrete. Every vertex of D D D other than the seed is initially intact . The seed is born at time 0. At each time t ≥ 0 t \ge0 t ≥ 0 every vertex born at time t t t sends a proposal to each of its neighbors in D D D . An intact vertex that receives exactly one proposal at time t + 1 t+1 t + 1 is born at time t + 1 t+1 t + 1 . An intact vertex that receives two or three proposals at time t + 1 t+1 t + 1 is blocked . A vertex that is born or blocked is never modified again and ignores later proposals. The birth polynomial of ( D , s ) (D,s) ( D , s ) is the sum of z t z^t z t over the vertices born at time t t t . When D D D is infinite it is a formal power series.
A born vertex emits once, at the time that follows its birth. A blocked vertex never emits.
Remark 4. In a finite domain with N N N vertices, a birth at time t ≥ 1 t \ge1 t ≥ 1 requires a birth at time t − 1 t-1 t − 1 . Thus the birth polynomial has degree at most N − 1 N-1 N − 1 .
Lemma 5. Run the growth of Definition 3 on the whole lattice with seed A ( 0 , 0 ) A(0,0) A ( 0 , 0 ) , with the single change that the seed sends proposals to two of its three neighbors only. Then for every n ≥ 1 n \ge1 n ≥ 1 the number t ( n ) t(n) t ( n ) of pieces placed at round n n n is the number of vertices born at time n − 1 n-1 n − 1 .
Proof. Place the first piece with its apex at A ( 0 , 0 ) A(0,0) A ( 0 , 0 ) and its two ends at the two chosen neighbors. We prove by induction on n ≥ 1 n \ge1 n ≥ 1 that after round n n n the vertices touched by the structure are the vertices that are not intact at time n n n , and that the free ends are the vertices born at time n n n . After round 1 the two ends of the first piece have each received one proposal and are born at time 1, and they are the free ends. Assume the claim after round n n n . At round n + 1 n+1 n + 1 a piece is placed at each free end u u u . It covers the two sides at u u u that are not yet covered, which lead to the two neighbors of u u u other than the vertex that sent its proposal to u u u . In the growth, u u u sends a proposal to its three neighbors and the third one is ignored because its target is not intact. An end w w w of a new piece is a free end after round n + 1 n+1 n + 1 exactly when w w w was not touched before and is reached by a single new piece. This means that w w w is intact at time n n n and receives exactly one proposal at time n + 1 n+1 n + 1 , that is, w w w is born at time n + 1 n+1 n + 1 . The vertices touched for the first time at round n + 1 n+1 n + 1 are those that receive their first proposals at time n + 1 n+1 n + 1 . This proves the claim. The pieces placed at round n + 1 n+1 n + 1 are in bijection with the free ends after round n n n , and the piece of round 1 corresponds to the seed. □ \square □
Cones and derived polynomials
For r ≥ 1 r \ge1 r ≥ 1 the cone of size r r r is
K r = { ( p , x , y ) ∣ x ≥ 0 , y ≥ 0 , 2 x + y + p < r } . K_r=\{(p,x,y)\mid x\ge0,\ y\ge0,\ 2x+y+p<r\}. K r = {( p , x , y ) ∣ x ≥ 0 , y ≥ 0 , 2 x + y + p < r } .
It has r ( r + 1 ) / 2 r(r+1)/2 r ( r + 1 ) /2 vertices. We denote by C r ( z ) C_r(z) C r ( z ) the birth polynomial of the growth on K r K_r K r with seed A ( 0 , 0 ) A(0,0) A ( 0 , 0 ) , and we set C 0 = 0 C_0=0 C 0 = 0 . For instance
C 1 = 1 , C 2 = 1 + z + z 2 , C 3 = 1 + z + 2 z 2 + z 3 + z 4 , C 4 = 1 + z + 2 z 2 + 2 z 3 + z 4 + z 5 + z 6 . C_1=1,\qquad C_2=1+z+z^2,\qquad C_3=1+z+2z^2+z^3+z^4,\qquad C_4=1+z+2z^2+2z^3+z^4+z^5+z^6. C 1 = 1 , C 2 = 1 + z + z 2 , C 3 = 1 + z + 2 z 2 + z 3 + z 4 , C 4 = 1 + z + 2 z 2 + 2 z 3 + z 4 + z 5 + z 6 .
For integers u ≤ v u\le v u ≤ v we write J u , v = z u + z u + 1 + ⋯ + z v J_{u,v}=z^u+z^{u+1}+\cdots+z^v J u , v = z u + z u + 1 + ⋯ + z v , and J u , v = 0 J_{u,v}=0 J u , v = 0 when u > v u>v u > v . We set
H r = C r + z C r − 1 − J 1 , r − 1 , H_r=C_r+zC_{r-1}-J_{1,r-1}, H r = C r + z C r − 1 − J 1 , r − 1 ,
with H 0 = 0 H_0=0 H 0 = 0 .
Definition 6. For every dyadic q ≥ 2 q\ge2 q ≥ 2 , define P q P_q P q recursively by
P q = S q , 0 + C q − 1 z , (2) P_q=S_{q,0}+\frac{C_q-1}{z}, \tag*{(2)} P q = S q , 0 + z C q − 1 , (2) where, for dyadic B ≥ 1 B\ge1 B ≥ 1 and an integer d ≥ 0 d\ge0 d ≥ 0 ,
S B , d = ∑ 2 ≤ m < B m e v e n z 2 m + d P ⌊ m / 2 ⌋ . (3) S_{B,d}=\sum_{\substack{2\le m<B\\ m\ \mathrm{even}}}z^{2m+d}P_{\lfloor m/2\rfloor}. \tag*{(3)} S B , d = 2 ≤ m < B m even ∑ z 2 m + d P ⌊ m /2 ⌋ . (3)
The quotient is a polynomial because C q ( 0 ) = 1 C_q(0)=1 C q ( 0 ) = 1 . The definition is well founded, since the sum contains only P p P_p P p with p < q p<q p < q . In particular P 2 = ( C 2 − 1 ) / z = 1 + z P_2=(C_2-1)/z=1+z P 2 = ( C 2 − 1 ) / z = 1 + z . Proposition 11 identifies P q P_q P q with the births in a finite diamond. Lemma 21 bounds its degree by 2 q + O ( ( log q ) 2 ) 2q+O((\log q)^2) 2 q + O (( log q ) 2 ) . The equality deg P q = 2 q − 3 \deg P_q=2q-3 deg P q = 2 q − 3 is proved over a finite range in Appendix § 11 and remains open in general.
Generating functions and computation model
Theorem 1 can now be read with Definition 6 . We also record the form for the increments. Let B ( z ) = ∑ n ≥ 1 t ( n ) z n = ( 1 − z ) A ( z ) B(z)=\sum_{n\ge1}t(n)z^n=(1-z)A(z) B ( z ) = ∑ n ≥ 1 t ( n ) z n = ( 1 − z ) A ( z ) and
G ( z ) = ∑ q = 2 , 4 , 8 , … z 2 q + 1 P q ( z ) 1 − z 4 q . (4) G(z)=\sum_{q=2,4,8,\ldots}\frac{z^{2q+1}P_q(z)}{1-z^{4q}}. \tag*{(4)} G ( z ) = q = 2 , 4 , 8 , … ∑ 1 − z 4 q z 2 q + 1 P q ( z ) . (4)
Then (1) is equivalent to
B ( z ) = ( 1 + z ) ( 1 + 2 z 2 ) ( z 1 − z + 2 G ( z ) ) . (5) B(z)=(1+z)(1+2z^2)\left(\frac{z}{1-z}+2G(z)\right). \tag*{(5)} B ( z ) = ( 1 + z ) ( 1 + 2 z 2 ) ( 1 − z z + 2 G ( z ) ) . (5)
Theorem 2 refers to the following model of computation. The input is the binary expansion of n n n . An arithmetic operation is an addition, a subtraction, a multiplication, a comparison, or a division with remainder on integers of O ( ℓ ) O(\ell) O ( ℓ ) bits. The algorithm is uniform, which means that a single program handles every n n n , builds its own data, and reads no table.
From geometric barriers to the generating function
Earliest times and Pascal’s triangle
For a vertex ( p , x , y ) (p,x,y) ( p , x , y ) with x , y ≥ 0 x,y\ge0 x , y ≥ 0 let t min ( p , x , y ) = 2 ( x + y ) + p t_{\min}(p,x,y)=2(x+y)+p t m i n ( p , x , y ) = 2 ( x + y ) + p . Along every edge of the lattice the value of t min t_{\min} t m i n changes by exactly one, and t min t_{\min} t m i n vanishes at A ( 0 , 0 ) A(0,0) A ( 0 , 0 ) . In a growth seeded at A ( 0 , 0 ) A(0,0) A ( 0 , 0 ) inside the quadrant x , y ≥ 0 x,y\ge0 x , y ≥ 0 , no vertex can therefore receive a proposal before time t min t_{\min} t m i n . We call t min t_{\min} t m i n the earliest time of the vertex.
We say that a domain D D D inside the quadrant is closed under predecessors when, for every vertex of D D D , the neighbors with nonnegative coordinates and with a smaller value of t min t_{\min} t m i n also belong to D D D . The cones K r K_r K r and the truncated triangles of § 5 have this property, because a step that decreases t min t_{\min} t m i n increases neither x + y x+y x + y nor 2 x + y + p 2x+y+p 2 x + y + p .
Lemma 7. Let D D D be a domain inside the quadrant that contains A ( 0 , 0 ) A(0,0) A ( 0 , 0 ) and is closed under predecessors . In the growth on D D D seeded at A ( 0 , 0 ) A(0,0) A ( 0 , 0 ) , a vertex A ( x , y ) A(x,y) A ( x , y ) or B ( x , y ) B(x,y) B ( x , y ) of D D D is born at its earliest time if and only if x & y = 0 x\mathbin{\&}y=0 x & y = 0 .
Proof. A vertex can be born at its earliest time only through a proposal sent by a neighbor that was itself born at its own earliest time, one time step earlier. For B ( x , y ) B(x,y) B ( x , y ) the only neighbor with a smaller value of t min t_{\min} t m i n is A ( x , y ) A(x,y) A ( x , y ) , so B ( x , y ) B(x,y) B ( x , y ) is born at its earliest time exactly when A ( x , y ) A(x,y) A ( x , y ) is. For A ( x , y ) A(x,y) A ( x , y ) the neighbors with a smaller value of t min t_{\min} t m i n are B ( x − 1 , y ) B(x-1,y) B ( x − 1 , y ) and B ( x , y − 1 ) B(x,y-1) B ( x , y − 1 ) , when their coordinates are nonnegative, and they belong to D D D by assumption. Let α ( x , y ) \alpha(x,y) α ( x , y ) be 1 when A ( x , y ) A(x,y) A ( x , y ) is born at time 2 ( x + y ) 2(x+y) 2 ( x + y ) and 0 otherwise, with α = 0 \alpha=0 α = 0 outside the quadrant. The rule of a single first arrival gives α ( x , y ) = α ( x − 1 , y ) + α ( x , y − 1 ) \alpha(x,y)=\alpha(x-1,y)+\alpha(x,y-1) α ( x , y ) = α ( x − 1 , y ) + α ( x , y − 1 ) modulo 2 for ( x , y ) ≠ ( 0 , 0 ) (x,y)\ne(0,0) ( x , y ) = ( 0 , 0 ) , since two simultaneous arrivals block the vertex and no arrival leaves it intact at that time. With α ( 0 , 0 ) = 1 \alpha(0,0)=1 α ( 0 , 0 ) = 1 this is the recurrence of the binomial coefficients, so α ( x , y ) \alpha(x,y) α ( x , y ) is the parity of ( x + y x ) \binom{x+y}{x} ( x x + y ) . By the theorem of Lucas this binomial coefficient is odd exactly when the addition of x x x and y y y in base two has no carry, which is the condition x & y = 0. □ x\mathbin{\&}y=0. \square x & y = 0. □
:::
Spines and a global counting identity
We use round numbers for the global growth, so that the seed A ( 0 , 0 ) A(0,0) A ( 0 , 0 ) is born at round 1 and its two chosen neighbors B ( 0 , 0 ) B(0,0) B ( 0 , 0 ) and B ( − 1 , 0 ) B(-1,0) B ( − 1 , 0 ) at round 2. Birth times in a finite cone are still measured from its seed at time 0. Put
g = 2 x + y + p , h = y − x , Q 1 = { x ≥ 0 , y ≥ 0 } , H + = { x ≥ 1 , y > x } . g = 2x + y + p,\qquad h = y - x,\qquad Q_1 = \{x \ge0, y \ge0\},\qquad H^+ = \{x \ge1, y > x\}. g = 2 x + y + p , h = y − x , Q 1 = { x ≥ 0 , y ≥ 0 } , H + = { x ≥ 1 , y > x } .
The vertical spine consists of A ( 0 , m ) A(0,m) A ( 0 , m ) and B ( 0 , m ) B(0,m) B ( 0 , m ) for m ≥ 1 m \ge1 m ≥ 1 . Let Z ( n ) Z(n) Z ( n ) count the births at round n n n in { x ≥ 0 , y > x } \{x \ge0, y > x\} { x ≥ 0 , y > x } and let F ( n ) F(n) F ( n ) count those in H + H^+ H + . We put F ( n ) = 0 F(n) = 0 F ( n ) = 0 for negative indices. We have Z ( n ) = 1 + F ( n ) Z(n) = 1 + F(n) Z ( n ) = 1 + F ( n ) for n ≥ 3 n \ge3 n ≥ 3 .
Lemma 8. The quadrant Q 1 Q_1 Q 1 evolves as the growth on the induced quadrant with seed A ( 0 , 0 ) A(0,0) A ( 0 , 0 ) at round 1. Its vertical and horizontal spines have birth times
A ( 0 , m ) , A ( m , 0 ) : 2 m + 1 , B ( 0 , m ) , B ( m , 0 ) : 2 m + 2. A(0,m), A(m,0): 2m + 1,\qquad B(0,m), B(m,0): 2m + 2. A ( 0 , m ) , A ( m , 0 ) : 2 m + 1 , B ( 0 , m ) , B ( m , 0 ) : 2 m + 2. The ray x = y > 0 x = y > 0 x = y > 0 is inactive at every round, as is the rest of its diagonal inside Q 1 Q_1 Q 1 after round 2. The global axis g = 0 g = 0 g = 0 is inactive after the seed. There is also a spine
B ( m , − m ) : 2 m + 2 , A ( m + 1 , − m ) : 2 m + 3 ( m ≥ 0 ) . B(m,-m): 2m + 2,\qquad A(m+1,-m): 2m + 3\qquad(m \ge0). B ( m , − m ) : 2 m + 2 , A ( m + 1 , − m ) : 2 m + 3 ( m ≥ 0 ) . Proof. The functions 2 x + p 2x + p 2 x + p , 2 y + p 2y + p 2 y + p , and 2 ( x + y ) + p 2(x + y) + p 2 ( x + y ) + p change by one along each edge. Their values at the two births of round 2 give the lower bounds
n ≥ 2 x + p + 1 , n ≥ 2 y + p + 1 , n ≥ 2 ( x + y ) + p + 1 n \ge2x + p + 1,\qquad n \ge2y + p + 1,\qquad n \ge2(x + y) + p + 1 n ≥ 2 x + p + 1 , n ≥ 2 y + p + 1 , n ≥ 2 ( x + y ) + p + 1 for any later first arrival. Except at the already resolved initial seed, the same argument with − 2 y − p -2y - p − 2 y − p gives n ≥ − 2 y − p + 3 n \ge-2y - p + 3 n ≥ − 2 y − p + 3 . On the vertical spine, each indicated birth has exactly one predecessor at the required round. The other two neighbors have a lower bound two rounds later than that predecessor. Induction proves the displayed times, starting with B ( 0 , 0 ) B(0,0) B ( 0 , 0 ) , and the argument with x x x and y y y interchanged proves the horizontal times. The only external edges of Q 1 Q_1 Q 1 away from the seed join B ( − 1 , m ) B(-1,m) B ( − 1 , m ) to A ( 0 , m ) A(0,m) A ( 0 , m ) or B ( m , − 1 ) B(m,-1) B ( m , − 1 ) to A ( m , 0 ) A(m,0) A ( m , 0 ) . Their external endpoints cannot be born before round 2 m + 2 2m + 2 2 m + 2 , so every return arrives after the spine has been resolved. This proves autonomy.
The quadrant and its initial state are invariant under μ ( p , x , y ) = ( p , y , x ) \mu(p,x,y) = (p,y,x) μ ( p , x , y ) = ( p , y , x ) . After B ( 0 , 0 ) B(0,0) B ( 0 , 0 ) , a diagonal vertex receives its off-diagonal proposals in pairs. Its possible diagonal neighbor is inactive by induction. Thus no further diagonal birth occurs. Likewise, the global reflection
R ( p , x , y ) = ( p , − x − y − p , y ) R(p,x,y) = (p,-x-y-p,y) R ( p , x , y ) = ( p , − x − y − p , y ) preserves the initial V, exchanges its two ends, and sends g g g to − g -g − g . On its fixed axis the off-axis proposals arrive in pairs. The only edge from the seed along that axis is the edge not used by the initial V. Induction therefore proves inactivity of the axis after the seed.
The vertex B ( m , − m ) B(m,-m) B ( m , − m ) reaches A ( m + 1 , − m ) A(m+1,-m) A ( m + 1 , − m ) at round 2 m + 3 2m + 3 2 m + 3 . The other possible parents have lower bound 2 m + 4 2m + 4 2 m + 4 . That A vertex then reaches B ( m + 1 , − m − 1 ) B(m+1,-m-1) B ( m + 1 , − m − 1 ) at round 2 m + 4 2m + 4 2 m + 4 , whereas its other possible parents have lower bound 2 m + 5 2m + 5 2 m + 5 . These bounds also exclude any earlier first touch. Induction from B ( 0 , 0 ) B(0,0) B ( 0 , 0 ) proves the last spine.
In particular, Q 1 Q_1 Q 1 has 2 Z ( n ) 2Z(n) 2 Z ( n ) births at round n ≥ 3 n \ge3 n ≥ 3 , and Z ( n ) = 1 + F ( n ) Z(n) = 1 + F(n) Z ( n ) = 1 + F ( n ) . Its earliest births are given by Lemma 7, with the additional shift of one round. Along the boundary of H + H^+ H + , A ( 1 , m ) A(1,m) A ( 1 , m ) is born at round 2 m + 3 2m + 3 2 m + 3 for even m ≥ 2 m \ge2 m ≥ 2 . For odd m m m it is blocked at that round by B ( 0 , m ) B(0,m) B ( 0 , m ) and B ( 1 , m − 1 ) B(1,m-1) B ( 1 , m − 1 ) . We keep these literal boundary proposals when using symmetry arguments.
Proposition 9. For every n ≥ 4 n \ge4 n ≥ 4 ,
t ( n ) = 6 + 2 F ( n + 2 ) + 2 F ( n + 1 ) + 4 F ( n ) + 4 F ( n − 1 ) . (6) t(n) = 6 + 2F(n+2) + 2F(n+1) + 4F(n) + 4F(n-1). \tag*{(6)} t ( n ) = 6 + 2 F ( n + 2 ) + 2 F ( n + 1 ) + 4 F ( n ) + 4 F ( n − 1 ) . (6)
Proof. By the reflection R R R , it suffices to count the births in g > 0 g > 0 g > 0 . Besides Q 1 Q_1 Q 1 , introduce
S − = { g > 0 , h > 0 , x ≤ − 1 } S^{-} = \{g > 0, h > 0, x \leq-1\} S − = { g > 0 , h > 0 , x ≤ − 1 } , Q 2 = { y ≤ 0 , x + y + p ≥ 1 } Q_2 = \{y \leq0, x + y + p \geq1\} Q 2 = { y ≤ 0 , x + y + p ≥ 1 } , D = { g > 0 , x + y + p ≤ 0 } D = \{g > 0, x + y + p \leq0\} D = { g > 0 , x + y + p ≤ 0 } .
These regions give a partition into Q 1 Q_1 Q 1 , S − S^{-} S − , Q 2 ∖ Q 1 Q_2 \setminus Q_1 Q 2 ∖ Q 1 , and D D D of the births in g > 0 g > 0 g > 0 after round 3. The graph automorphism
Φ ( p , x , y ) = ( 1 − p , − x , x + y + p ) \Phi(p, x, y) = (1 - p, -x, x + y + p) Φ ( p , x , y ) = ( 1 − p , − x , x + y + p )
maps S − S^{-} S − onto H + H^{+} H + and sends ( g , h ) (g,h) ( g , h ) to ( h + 1 , g ) (h+1,g) ( h + 1 , g ) . The proposals entering S − S^{-} S − are those from A ( 0 , m ) A(0,m) A ( 0 , m ) to B ( − 1 , m ) B(-1,m) B ( − 1 , m ) . Their images are the proposals from B ( 0 , m ) B(0,m) B ( 0 , m ) to A ( 1 , m ) A(1,m) A ( 1 , m ) entering H + H^{+} H + , one round later. In both cases m ≥ 2 m \geq2 m ≥ 2 for an interior target. The other boundary is an inactive ray, and returns to the spine arrive after its resolution by Lemma 8 . The two regions are empty off their boundaries at corresponding rounds 3 and 4. Induction on first arrivals, including simultaneous arrivals, proves that S − S^{-} S − has F ( n + 1 ) = Z ( n + 1 ) − 1 F(n+1) = Z(n+1) - 1 F ( n + 1 ) = Z ( n + 1 ) − 1 births at round n n n .
The region Q 2 Q_2 Q 2 is autonomous. Its external edges join B ( x , 0 ) B(x,0) B ( x , 0 ) to A ( x , 1 ) A(x,1) A ( x , 1 ) , or B ( m , − m ) B(m,-m) B ( m , − m ) to A ( m , − m ) A(m,-m) A ( m , − m ) . On the first boundary the spine vertex is born at 2 x + 2 2x+2 2 x + 2 and the external A cannot be born before 2 x + 3 2x+3 2 x + 3 . On the second boundary the corresponding bounds are 2 m + 2 2m+2 2 m + 2 and 2 m + 3 2m+3 2 m + 3 , with the initial seed already resolved when m = 0 m=0 m = 0 . Every return is therefore too late. The automorphism
K ( p , x , y ) = ( 1 − p , x + y + p , − x ) K(p, x, y) = (1 - p, x + y + p, -x) K ( p , x , y ) = ( 1 − p , x + y + p , − x )
maps Q 1 Q_1 Q 1 onto Q 2 Q_2 Q 2 . It maps the state of Q 1 Q_1 Q 1 at round 2 to that of Q 2 Q_2 Q 2 at round 3, so that Q 2 Q_2 Q 2 has 2 Z ( n − 1 ) 2Z(n-1) 2 Z ( n − 1 ) births. Its intersection with Q 1 Q_1 Q 1 is the horizontal spine and has one birth per round. Thus Q 2 ∖ Q 1 Q_2 \setminus Q_1 Q 2 ∖ Q 1 contributes 2 Z ( n − 1 ) − 1 2Z(n-1)-1 2 Z ( n − 1 ) − 1 .
The remaining automorphism
J ( p , x , y ) = ( p , 1 − x − y − p , x + 1 ) J(p, x, y) = (p, 1 - x - y - p, x + 1) J ( p , x , y ) = ( p , 1 − x − y − p , x + 1 )
maps D D D onto H + H^{+} H + . Its new coordinates satisfy x ′ = 1 − ( x + y + p ) x' = 1 - (x + y + p) x ′ = 1 − ( x + y + p ) and h ′ = g h' = g h ′ = g . It takes the inactive boundary g = 0 g = 0 g = 0 to h ′ = 0 h' = 0 h ′ = 0 and maps the entering edge B ( m , − m ) A ( m , − m ) B(m,-m)A(m,-m) B ( m , − m ) A ( m , − m ) to B ( 0 , m + 1 ) A ( 1 , m + 1 ) B(0,m+1)A(1,m+1) B ( 0 , m + 1 ) A ( 1 , m + 1 ) . The source of the first edge is born at 2 m + 2 2m+2 2 m + 2 and the source of the image edge at 2 m + 4 2m+4 2 m + 4 . These are all the entering edges for m ≥ 1 m \geq1 m ≥ 1 . The otherwise missing edge at m = 0 m=0 m = 0 has its image target on the inactive diagonal. The regions are empty at corresponding rounds 3 and 5. Their states therefore agree after this translation of time, and D D D has F ( n + 2 ) = Z ( n + 2 ) − 1 F(n+2) = Z(n+2)-1 F ( n + 2 ) = Z ( n + 2 ) − 1 births at round n n n .
Adding the four counts gives
t ( n ) 2 = Z ( n + 2 ) + Z ( n + 1 ) + 2 Z ( n ) + 2 Z ( n − 1 ) − 3. \frac{t(n)}{2} = Z(n+2) + Z(n+1) + 2Z(n) + 2Z(n-1) - 3. 2 t ( n ) = Z ( n + 2 ) + Z ( n + 1 ) + 2 Z ( n ) + 2 Z ( n − 1 ) − 3.
Substitution of Z = 1 + F Z = 1 + F Z = 1 + F proves the formula.
Isolation and coverage of the diamonds
For an even integer m ≥ 2 m \geq2 m ≥ 2 , put q = lb ( m ) q = \operatorname{lb}(m) q = lb ( m ) and use the coordinates ℓ = y − x \ell= y - x ℓ = y − x and r = x + y r = x + y r = x + y . Define the finite region D m D_m D m by
m − q < ℓ < m ≤ r < m + q , (7) m - q < \ell< m \leq r < m + q, \tag*{(7)} m − q < ℓ < m ≤ r < m + q , (7)
with A vertices on r = m r = m r = m omitted.
Its seed is A ( 1 , m ) A(1,m) A ( 1 , m ) . After writing w = y − m w = y - m w = y − m , the region depends only on q q q and becomes
x ≥ 1 , − x ≤ w ≤ x − 1 , x + ∣ w ∣ ≤ q − 1 , A ( x , − x ) omitted . (8) x \geq1,\qquad-x \leq w \leq x - 1,\qquad x + |w| \leq q - 1,\qquad A(x,-x)\text{ omitted}. \tag*{(8)} x ≥ 1 , − x ≤ w ≤ x − 1 , x + ∣ w ∣ ≤ q − 1 , A ( x , − x ) omitted . (8)
Write P ^ q \widehat{P}_q P q for its birth polynomial when the seed is born at age 0.
Lemma 10. The growth in D m D_m D m is its isolated growth, with seed born at round 2 m + 3 2m+3 2 m + 3 . Every birth in H + H^+ H + belongs to exactly one such region.
Proof. Two families of blocked vertices separate the diamonds. If M M M is even and Q = lb ( M ) Q=\operatorname{lb}(M) Q = lb ( M ) , then for 0 < x < Q 0<x<Q 0 < x < Q the vertex A ( x , M − x ) A(x,M-x) A ( x , M − x ) has two earliest parents B ( x − 1 , M − x ) B(x-1,M-x) B ( x − 1 , M − x ) and B ( x , M − x − 1 ) B(x,M-x-1) B ( x , M − x − 1 ) at round 2 M 2M 2 M . Their coordinates have disjoint binary digits. Lemma 7 and the lower bound on first arrivals therefore block the A vertex at round 2 M + 1 2M+1 2 M + 1 , permanently.
For the second barrier fix even m m m , put q = lb ( m ) q=\operatorname{lb}(m) q = lb ( m ) , and translate y = m + w y=m+w y = m + w . The triangle x , w ≥ 0 x,w\ge0 x , w ≥ 0 , x + w < q x+w<q x + w < q is empty immediately before round 2 m + 1 2m+1 2 m + 1 , when only A ( 0 , m ) A(0,m) A ( 0 , m ) is born. This follows from the lower bound 2 m + 2 ( x + w ) + p + 1 2m+2(x+w)+p+1 2 m + 2 ( x + w ) + p + 1 . On its horizontal axis the vertices are born at their earliest times, since x & m = 0 x\mathbin{\&}m=0 x & m = 0 for x < q x<q x < q . A possible return from below comes from B ( x , m − 1 ) B(x,m-1) B ( x , m − 1 ) . For 0 < x < q 0<x<q 0 < x < q one has x & ( m − 1 ) = x ≠ 0 x\mathbin{\&}(m-1)=x\ne0 x & ( m − 1 ) = x = 0 . That B misses its earliest time and, by bipartite parity, any later birth sends its proposal after A ( x , m ) A(x,m) A ( x , m ) has been resolved. The vertical axis is the one-way spine already proved.
The far side x + w = q x+w=q x + w = q is closed by the first barrier because lb ( m + q ) ≥ 2 q \operatorname{lb}(m+q)\ge2q lb ( m + q ) ≥ 2 q . At its endpoints the only interior neighbors are B ( 0 , m + q − 1 ) B(0,m+q-1) B ( 0 , m + q − 1 ) and B ( q − 1 , m ) B(q-1,m) B ( q − 1 , m ) , both born at round 2 ( m + q ) 2(m+q) 2 ( m + q ) . The endpoint A vertices cannot be born before round 2 ( m + q ) + 1 2(m+q)+1 2 ( m + q ) + 1 , so their returns are also ineffective. The induced triangle thus has a single seed, symmetric initial state, and no effective external input. Reflection in x = w x=w x = w preserves its evolution. A positive diagonal vertex receives its off-diagonal proposals in pairs, and its diagonal neighbor is inactive by induction. This proves that
y − x = m , m < x + y < m + q y-x=m,\qquad m<x+y<m+q y − x = m , m < x + y < m + q is an inactive segment at every round. This argument uses the actual initially intact sites, including those later blocked by spine proposals.
These barriers determine the four faces of (7) . The faces r = m r=m r = m and r = m + q r=m+q r = m + q are closed by the A barriers just proved. The face ℓ = m \ell=m ℓ = m is closed by the mirror segment. If m = q m=q m = q , the face ℓ = m − q \ell=m-q ℓ = m − q is the original inactive diagonal. Otherwise put m 0 = m − q m_0=m-q m 0 = m − q . Then lb ( m 0 ) ≥ 2 q \operatorname{lb}(m_0)\ge2q lb ( m 0 ) ≥ 2 q , and the relevant fourth face lies on the mirror segment already proved for m 0 m_0 m 0 . This uses no previous diamond decomposition. At the corners, the remaining incident A vertices lie on these barriers. The B vertices on r = m r=m r = m have their same-level A neighbor blocked and their other neighbors on r = m + 1 r=m+1 r = m + 1 . On the far face no extra B vertex has an interior neighbor. The only effective entering edge is therefore B ( 0 , m ) A ( 1 , m ) B(0,m)A(1,m) B ( 0 , m ) A ( 1 , m ) , which creates the seed at round 2 m + 3 2m+3 2 m + 3 . No other birth or first touch can occur inside before this input, so the entire subsequent evolution is the isolated one.
For coverage, let a vertex of H + H^+ H + have coordinates 0 < ℓ < r 0<\ell<r 0 < ℓ < r . The integers ℓ \ell ℓ and r r r have the same parity. Let
q = 2 ⌊ log 2 ( ℓ xor r ) ⌋ , m = q ⌊ r / q ⌋ . q=2^{\lfloor\log_2(\ell\mathbin{\operatorname{xor}}r)\rfloor},\qquad m=q\lfloor r/q\rfloor. q = 2 ⌊ l o g 2 ( ℓ xor r )⌋ , m = q ⌊ r / q ⌋ . where xor denotes digitwise exclusive or. The highest differing binary digit is 0 in ℓ \ell ℓ and 1 in r r r . Thus q ≥ 2 q\ge2 q ≥ 2 , lb ( m ) = q \operatorname{lb}(m)=q lb ( m ) = q and m − q ≤ ℓ < m ≤ r < m + q m-q\le\ell<m\le r<m+q m − q ≤ ℓ < m ≤ r < m + q . Equality at ℓ = m − q \ell=m-q ℓ = m − q , or an A vertex at r = m r=m r = m , places the site on one of the inactive barriers. Otherwise it belongs to D m D_m D m . The highest differing digit also makes this choice unique. Hence the isolated diamonds contain all births and are disjoint.
The polynomial of a diamond
Proposition 11. The geometric polynomial P ^ q \widehat{P}_q P q is P q P_q P q of Definition 6 . Consequently
F ( z ) = ∑ q = 2 , 4 , 8 , … z 2 q + 3 P q ( z ) 1 − z 4 q . (9) F(z)=\sum_{q=2,4,8,\ldots}\frac{z^{2q+3}P_q(z)}{1-z^{4q}}. \tag*{(9)} F ( z ) = q = 2 , 4 , 8 , … ∑ 1 − z 4 q z 2 q + 3 P q ( z ) . (9)
Proof. Let q ≥ 2 q\ge2 q ≥ 2 be dyadic. In the domain (8) the two spines have schedules
A ( x , 0 ) : 2 x − 2 , B ( x , 0 ) : 2 x − 1 ( 1 ≤ x < q ) , A(x,0): 2x-2,\qquad B(x,0): 2x-1\quad(1\le x<q), A ( x , 0 ) : 2 x − 2 , B ( x , 0 ) : 2 x − 1 ( 1 ≤ x < q ) ,
B ( x , − x ) : 2 x − 1 , A ( x + 1 , − x ) : 2 x ( 1 ≤ x < q / 2 ) . B(x,-x): 2x-1,\qquad A(x+1,-x): 2x\quad(1\le x<q/2). B ( x , − x ) : 2 x − 1 , A ( x + 1 , − x ) : 2 x ( 1 ≤ x < q /2 ) .
Their births follow by induction from the potentials 2 x + p 2x+p 2 x + p , − 2 w − p -2w-p − 2 w − p and 2 ( x + w ) + p 2(x+w)+p 2 ( x + w ) + p , which exclude earlier arrivals and competing parents. The second list does not repeat the seed.
The upper part w > 0 w>0 w > 0 maps by ( p , x , w ) ↦ ( p , w , x ) (p,x,w)\mapsto(p,w,x) ( p , x , w ) ↦ ( p , w , x ) onto H + H^+ H + truncated by x ′ + y ′ < q x'+y'<q x ′ + y ′ < q . Its spine schedule is the global schedule shifted by − 3 -3 − 3 rounds. Its other boundaries are the mirror and A barriers of Lemma 10 , and returns to its spine are too late. For every even m < q m<q m < q , the inequality m + lb ( m ) ≤ q m+\operatorname{lb}(m)\le q m + lb ( m ) ≤ q shows that the corresponding diamond is retained in full. Coverage gives exactly
∑ 2 ≤ m < q m e v e n z 2 m P ^ lb ( m ) \sum_{\substack{2\le m<q\\m\ \mathrm{even}}} z^{2m}\widehat{P}_{\operatorname{lb}(m)} 2 ≤ m < q m even ∑ z 2 m P lb ( m )
For the lower part apply the inverse cone map
( p , x , w ) ⟼ ( P , u , v ) = ( 1 − p , − w , x + w + p − 1 ) . (p,x,w)\longmapsto(P,u,v)=(1-p,-w,x+w+p-1). ( p , x , w ) ⟼ ( P , u , v ) = ( 1 − p , − w , x + w + p − 1 ) .
The inequalities become u , v ≥ 0 u,v\ge0 u , v ≥ 0 and 2 u + v + P < q 2u+v+P<q 2 u + v + P < q . The seed A ( 0 , 0 ) A(0,0) A ( 0 , 0 ) of this cone corresponds to the external vertex B ( 0 , 0 ) B(0,0) B ( 0 , 0 ) , which precedes the diamond seed by one round. Its next vertex B ( 0 , 0 ) B(0,0) B ( 0 , 0 ) corresponds to the diamond seed A ( 1 , 0 ) A(1,0) A ( 1 , 0 ) . Thus the cone age equals the diamond age plus one. The common horizontal spine is counted only once, and the two parts are autonomous by the same spine bounds.
The lower part therefore contributes ( C q − 1 ) / z (C_q-1)/z ( C q − 1 ) / z , including the horizontal spine. The upper part and this cone exhaust the diamond, with disjoint counted vertices. Hence
P ^ q = ∑ 2 ≤ m < q m e v e n z 2 m P ^ lb ( m ) + C q − 1 z . \widehat{P}_q=\sum_{\substack{2\le m<q\\m\ \mathrm{even}}}z^{2m}\widehat{P}_{\operatorname{lb}(m)}+\frac{C_q-1}{z}. P q = 2 ≤ m < q m even ∑ z 2 m P lb ( m ) + z C q − 1 .
Induction on q q q and Definition 6 give P ^ q = P q \widehat{P}_q=P_q P q = P q . The centers with lb ( m ) = q \operatorname{lb}(m)=q lb ( m ) = q are m = q ( 2 j + 1 ) m=q(2j+1) m = q ( 2 j + 1 ) for j ≥ 0 j\ge0 j ≥ 0 , and their seeds occur at 2 q + 3 + 4 q j 2q+3+4qj 2 q + 3 + 4 q j . Summing the isolated polynomials proves (9) .
Proof of the generating function identity
By (9) and (4) we have F = z 2 G F=z^2G F = z 2 G , and every P q P_q P q has constant term 1 1 1 , so the first nonzero coefficient of F F F is F ( 7 ) F(7) F ( 7 ) . Multiply (6) by z n z^n z n and sum over n ≥ 4 n\ge4 n ≥ 4 . Since F ( j ) = 0 F(j)=0 F ( j ) = 0 for j ≤ 6 j\le6 j ≤ 6 , the four sums over n ≥ 4 n\ge4 n ≥ 4 can be extended to all n n n , and
∑ n ≥ 4 ( 2 F ( n + 2 ) + 2 F ( n + 1 ) + 4 F ( n ) + 4 F ( n − 1 ) ) z n = ( 2 z − 2 + 2 z − 1 + 4 + 4 z ) F = 2 ( 1 + z + 2 z 2 + 2 z 3 ) G . \sum_{n\ge4}\left(2F(n+2)+2F(n+1)+4F(n)+4F(n-1)\right)z^n=(2z^{-2}+2z^{-1}+4+4z)F=2(1+z+2z^2+2z^3)G. n ≥ 4 ∑ ( 2 F ( n + 2 ) + 2 F ( n + 1 ) + 4 F ( n ) + 4 F ( n − 1 ) ) z n = ( 2 z − 2 + 2 z − 1 + 4 + 4 z ) F = 2 ( 1 + z + 2 z 2 + 2 z 3 ) G .
The values t ( 1 ) = 1 t(1)=1 t ( 1 ) = 1 , t ( 2 ) = 2 t(2)=2 t ( 2 ) = 2 , and t ( 3 ) = 4 t(3)=4 t ( 3 ) = 4 follow from the first three rounds. Therefore
B ( z ) = z + 2 z 2 + 4 z 3 + 6 z 4 1 − z + 2 ( 1 + z + 2 z 2 + 2 z 3 ) G ( z ) . B(z)=z+2z^2+4z^3+\frac{6z^4}{1-z}+2(1+z+2z^2+2z^3)G(z). B ( z ) = z + 2 z 2 + 4 z 3 + 1 − z 6 z 4 + 2 ( 1 + z + 2 z 2 + 2 z 3 ) G ( z ) .
The rational part equals z ( 1 + z + 2 z 2 + 2 z 3 ) / ( 1 − z ) z(1+z+2z^2+2z^3)/(1-z) z ( 1 + z + 2 z 2 + 2 z 3 ) / ( 1 − z ) , and 1 + z + 2 z 2 + 2 z 3 = ( 1 + z ) ( 1 + 2 z 2 ) 1+z+2z^2+2z^3=(1+z)(1+2z^2) 1 + z + 2 z 2 + 2 z 3 = ( 1 + z ) ( 1 + 2 z 2 ) . This gives (5) , and (1) follows from A ( z ) = B ( z ) / ( 1 − z ) A(z)=B(z)/(1-z) A ( z ) = B ( z ) / ( 1 − z ) .
Reduction of the cones
By Definition 6 the polynomials P q P_q P q are determined by the cones. Most cones can in turn be reduced to smaller cones.
Truncated triangles and the dyadic copy theorem
For integers M ≥ 1 M \ge1 M ≥ 1 and 0 ≤ c ≤ M 0 \le c \le M 0 ≤ c ≤ M let
Ω M , c = { ( p , x , y ) ∣ x ≥ 0 , y ≥ 0 , x + y < M , 2 x + y + p < 2 M − c } , \Omega_{M,c} = \{(p,x,y) \mid x \ge0,\ y \ge0,\ x+y < M,\ 2x+y+p < 2M-c\}, Ω M , c = {( p , x , y ) ∣ x ≥ 0 , y ≥ 0 , x + y < M , 2 x + y + p < 2 M − c } ,
and let L M , c L_{M,c} L M , c be the birth polynomial of the growth on Ω M , c \Omega_{M,c} Ω M , c seeded at A ( 0 , 0 ) A(0,0) A ( 0 , 0 ) . We write L M = L M , 0 L_M = L_{M,0} L M = L M , 0 . The domain Ω M , 0 \Omega_{M,0} Ω M , 0 is a triangle, and Ω M , c \Omega_{M,c} Ω M , c is obtained by cutting its corner near the point x = M x=M x = M , y = 0 y=0 y = 0 . These domains are closed under predecessors.
Theorem 12. Let m m m be dyadic, let M M M be a positive multiple of m m m , let 0 ≤ c ≤ m 0 \le c \le m 0 ≤ c ≤ m and put k = M − m k=M-m k = M − m . In the growth on Ω M , c \Omega_{M,c} Ω M , c , the vertices with x ≥ k x \ge k x ≥ k evolve as in the growth on Ω m , c \Omega_{m,c} Ω m , c , after the translation x ↦ x − k x \mapsto x-k x ↦ x − k and with all times increased by 2 k 2k 2 k . The vertices with x < k x < k x < k evolve as in the growth on Ω M , 0 \Omega_{M,0} Ω M , 0 . In particular
L M , c − L M = z 2 ( M − m ) ( L m , c − L m ) . (10) L_{M,c}-L_M=z^{2(M-m)}(L_{m,c}-L_m). \tag*{(10)} L M , c − L M = z 2 ( M − m ) ( L m , c − L m ) . (10)
Proof. The case k = 0 k=0 k = 0 is immediate, so let k > 0 k>0 k > 0 . Since k k k is a multiple of the dyadic integer m m m , every y y y with 0 ≤ y < m 0 \le y < m 0 ≤ y < m satisfies k & y = 0 k \mathbin{\&} y=0 k & y = 0 and ( k − 1 ) & y = y (k-1) \mathbin{\&} y=y ( k − 1 ) & y = y . The vertices of Ω M , c \Omega_{M,c} Ω M , c with x ≥ k x \ge k x ≥ k have y < m y<m y < m , and the translation x ↦ x − k x \mapsto x-k x ↦ x − k maps them onto Ω m , c \Omega_{m,c} Ω m , c , because the two constraints become x + y < m x+y<m x + y < m and 2 x + y + p < 2 m − c 2x+y+p<2m-c 2 x + y + p < 2 m − c . Every vertex A ( k , y ) A(k,y) A ( k , y ) with 0 ≤ y < m 0 \le y<m 0 ≤ y < m belongs to Ω M , c \Omega_{M,c} Ω M , c , since 2 k + y ≤ 2 M − m − 1 < 2 M − c 2k+y \le2M-m-1<2M-c 2 k + y ≤ 2 M − m − 1 < 2 M − c . By Lemma 7 it is born at time 2 ( k + y ) 2(k+y) 2 ( k + y ) , whatever the value of c c c . The only edges between the region x < k x<k x < k and the region x ≥ k x \ge k x ≥ k join B ( k − 1 , y ) B(k-1,y) B ( k − 1 , y ) to A ( k , y ) A(k,y) A ( k , y ) . These B B B vertices are retained, since k − 1 + y < M k-1+y<M k − 1 + y < M and 2 ( k − 1 ) + y + 1 < 2 k + y < 2 M − c 2(k-1)+y+1<2k+y<2M-c 2 ( k − 1 ) + y + 1 < 2 k + y < 2 M − c . For y ≥ 1 y \ge1 y ≥ 1 the vertex B ( k − 1 , y ) B(k-1,y) B ( k − 1 , y ) is not born at its earliest time 2 ( k + y ) − 1 2(k+y)-1 2 ( k + y ) − 1 , again by Lemma 7 . Births of a given type occur at times of a fixed parity, so if B ( k − 1 , y ) B(k-1,y) B ( k − 1 , y ) is born later, its proposal reaches A ( k , y ) A(k,y) A ( k , y ) at time 2 ( k + y ) + 2 2(k+y)+2 2 ( k + y ) + 2 or later, when A ( k , y ) A(k,y) A ( k , y ) is already born. For y = 0 y=0 y = 0 the proposal of B ( k − 1 , 0 ) B(k-1,0) B ( k − 1 , 0 ) creates A ( k , 0 ) A(k,0) A ( k , 0 ) at time 2 k 2k 2 k . Hence the region x ≥ k x \ge k x ≥ k receives from outside a single effective proposal, which makes A ( k , 0 ) A(k,0) A ( k , 0 ) a seed born at time 2 k 2k 2 k . No vertex of this region can be touched before time 2 k 2k 2 k . Its growth is therefore the growth on Ω m , c \Omega_{m,c} Ω m , c , translated and delayed by 2 k 2k 2 k . In the other direction, every vertex of Ω M , 0 \Omega_{M,0} Ω M , 0 with x < k x<k x < k belongs to Ω M , c \Omega_{M,c} Ω M , c , because 2 x + y + p ≤ M + x ≤ 2 M − m − 1 2x+y+p \le M+x \le2M-m-1 2 x + y + p ≤ M + x ≤ 2 M − m − 1 . The region x < k x<k x < k receives proposals from the region x ≥ k x \ge k x ≥ k only through the vertices A ( k , y ) A(k,y) A ( k , y ) , whose birth times do not depend on c c c . By induction on time its growth does not depend on c c c either. Applying the first statement to c c c and to 0 0 0 and subtracting gives (10).
Adjacent cones and the Pascal wall
For r ≥ 1 r \ge1 r ≥ 1 consider the finite wedge
W r = { ( p , x , y ) ∣ x ≥ 0 , x + y ≥ 0 , 2 x + y + p < r } . W_r=\{(p,x,y) \mid x \ge0,\ x+y \ge0,\ 2x+y+p<r\}. W r = {( p , x , y ) ∣ x ≥ 0 , x + y ≥ 0 , 2 x + y + p < r } .
Its seed is A ( 0 , 0 ) A(0,0) A ( 0 , 0 ) and its other A vertices on x + y = 0 x+y=0 x + y = 0 are blocked initially. All remaining vertices are intact.
Lemma 13. The birth polynomial of this wedge is H r = C r + z C r − 1 − J 1 , r − 1 H_r=C_r+zC_{r-1}-J_{1,r-1} H r = C r + z C r − 1 − J 1 , r − 1 .
Proof. The potentials 2 x + p 2x+p 2 x + p and 2 ( x + y ) + p 2(x+y)+p 2 ( x + y ) + p give the lower bound max ( 2 x + p , 2 ( x + y ) + p ) \max(2x+p,2(x+y)+p) max ( 2 x + p , 2 ( x + y ) + p ) for every first touch. Along y = 0 y=0 y = 0 , induction therefore gives births A ( x , 0 ) A(x,0) A ( x , 0 ) at 2 x 2x 2 x and B ( x , 0 ) B(x,0) B ( x , 0 ) at 2 x + 1 2x+1 2 x + 1 whenever the sites are retained. A return from B ( x , − 1 ) B(x,-1) B ( x , − 1 ) cannot reach A ( x , 0 ) A(x,0) A ( x , 0 ) before 2 x + 2 2x+2 2 x + 2 . A return from A ( x , 1 ) A(x,1) A ( x , 1 ) cannot reach B ( x , 0 ) B(x,0) B ( x , 0 ) before 2 x + 3 2x+3 2 x + 3 . The regions y ≥ 0 y \ge0 y ≥ 0 and y ≤ 0 y \le0 y ≤ 0 , x + y + p ≥ 1 x+y+p \ge1 x + y + p ≥ 1 are consequently autonomous inside the wedge, the remaining A boundary being blocked.
The first region is the cone K r K_r K r . The automorphism
Λ ( p , x , y ) = ( 1 − p , x + y + p , − y ) \Lambda(p,x,y)=(1-p,x+y+p,-y) Λ ( p , x , y ) = ( 1 − p , x + y + p , − y )
maps K r − 1 K_{r-1} K r − 1 onto the second region, because it increases 2 x + y + p 2x+y+p 2 x + y + p by one. It sends the seed to B ( 0 , 0 ) B(0,0) B ( 0 , 0 ) , born at age 1. All other sites of that region are then intact, giving its polynomial z C r − 1 zC_{r-1} z C r − 1 . Their intersection is the horizontal spine without the seed, with one birth at each age 1 , … , r − 1 1,\ldots,r-1 1 , … , r − 1 . All wedge vertices outside the union are the initially blocked A vertices. Subtracting the intersection proves the formula.
Proposition 14. Let M M M be dyadic and 0 ≤ c ≤ M 0 \le c \le M 0 ≤ c ≤ M . Then
C 2 M − c = L M , c + z 2 M H M − c . (11) C_{2M-c}=L_{M,c}+z^{2M}H_{M-c}. \tag*{(11)} C 2 M − c = L M , c + z 2 M H M − c . (11) The complete triangle satisfies
L M = 1 + z + 2 J 2 , 2 M − 1 + 2 S M , 2 . (12) L_M=1+z+2J_{2,2M-1}+2S_{M,2}. \tag*{(12)} L M = 1 + z + 2 J 2 , 2 M − 1 + 2 S M , 2 . (12) Proof. In K 2 M − c K_{2M-c} K 2 M − c the vertices with x + y < M x+y<M x + y < M form Ω M , c \Omega_{M,c} Ω M , c . Every retained A ( x , M − x ) A(x,M-x) A ( x , M − x ) with x > 0 x>0 x > 0 has x < M − c x<M-c x < M − c and receives two earliest proposals at age 2 M 2M 2 M , since M M M is dyadic. Both parents belong to the truncated triangle. The vertex is thus permanently blocked. At the only retained endpoint A ( 0 , M ) A(0,M) A ( 0 , M ) , a possible return reaches B ( 0 , M − 1 ) B(0,M-1) B ( 0 , M − 1 ) after that B B B has been born at 2 M − 1 2M-1 2 M − 1 . The other endpoint A ( M , 0 ) A(M,0) A ( M , 0 ) is outside K 2 M − c K_{2M-c} K 2 M − c . These observations prove autonomy of the truncated triangle.
If c < M c<M c < M , the region x + y ≥ M x+y \ge M x + y ≥ M receives its unique seed A ( 0 , M ) A(0,M) A ( 0 , M ) at age 2 M 2M 2 M . At this time its retained A vertices on the wall have just been blocked and all its other vertices are intact, by the earliest-time bound. Translation y ↦ y − M y \mapsto y-M y ↦ y − M gives exactly W M − c \mathcal{W}_{M-c} W M − c . The condition y ≥ 0 y \ge0 y ≥ 0 in the original coordinates is automatic after this translation, since x < M − c ≤ M x<M-c \le M x < M − c ≤ M and the new y y y is at least − x -x − x . Lemma 13 gives its polynomial H M − c H_{M-c} H M − c and proves (11) . For c = M c=M c = M there is no residual region and H 0 = 0 H_0=0 H 0 = 0 , giving the same identity.
For c = 0 c=0 c = 0 , the two axes of the triangle meet at A ( 0 , 0 ) A(0,0) A ( 0 , 0 ) and B ( 0 , 0 ) B(0,0) B ( 0 , 0 ) . They contribute 1 + z + 2 J 2 , 2 M − 1 1+z+2J_{2,2M-1} 1 + z + 2 J 2 , 2 M − 1 . The diagonal reflection separates the remaining births into two equal halves. Each half contains all the diamonds with even centers 2 ≤ m < M 2 \le m<M 2 ≤ m < M and no others. They fit because m + lb ( m ) ≤ M m+\operatorname{lb}(m) \le M m + lb ( m ) ≤ M . Their seeds have cone age 2 m + 2 2m+2 2 m + 2 . Isolation and coverage therefore give 2 S M , 2 2S_{M,2} 2 S M , 2 , proving (12) .
Figure 4 shows the decomposition when M = 8 M=8 M = 8 and c = 3 c=3 c = 3 .
Figure 4. The cone K 13 K_{13} K 13 . The blue vertices form Ω 8 , 3 \Omega_{8,3} Ω 8 , 3 . On the line x + y = 8 x+y=8 x + y = 8 , the crosses are vertices blocked by two arrivals at time 16. The red vertex A ( 0 , 8 ) A(0,8) A ( 0 , 8 ) is the only seed of the orange region, whose birth polynomial is z 16 H 5 z^{16}H_5 z 16 H 5 .
The reduction
Proposition 15. Let r ≥ 2 r \ge2 r ≥ 2 , let q q q be the smallest dyadic integer with q ≥ r q \ge r q ≥ r , and put c = q − r c=q-r c = q − r and M = q / 2 M=q/2 M = q /2 . If c = 0 c=0 c = 0 then
C q = L M + z q H M . (13) C_q=L_M+z^qH_M. \tag*{(13)} C q = L M + z q H M . (13) If c > 0 c>0 c > 0 , let m m m be the smallest dyadic integer with m ≥ c m \ge c m ≥ c . Then
C r = L M + z q H M − c + z q − 2 m ( C 2 m − c − L m ) − z q H m − c . (14) C_r=L_M+z^qH_{M-c}+z^{q-2m}(C_{2m-c}-L_m)-z^qH_{m-c}. \tag*{(14)} C r = L M + z q H M − c + z q − 2 m ( C 2 m − c − L m ) − z q H m − c . (14) When c ≤ q / 4 c \le q/4 c ≤ q /4 every cone on the right-hand side of (14) has an index smaller than r r r . When c > q / 4 c>q/4 c > q /4 one has m = M m=M m = M and (14) is the trivial identity C r = C r C_r=C_r C r = C r .
Proof. Since r > q / 2 r>q/2 r > q /2 we have 0 ≤ c < M 0 \le c<M 0 ≤ c < M . Identity (13) is (11) with c = 0 c=0 c = 0 . Let c > 0 c>0 c > 0 . Then m ≤ M m \le M m ≤ M and both are dyadic, so M M M is a multiple of m m m and (10) gives L M , c = L M + z q − 2 m ( L m , c − L m ) L_{M,c}=L_M+z^{q-2m}(L_{m,c}-L_m) L M , c = L M + z q − 2 m ( L m , c − L m ) . Identity (11) at size m m m gives L m , c = C 2 m − c − z 2 m H m − c L_{m,c}=C_{2m-c}-z^{2m}H_{m-c} L m , c = C 2 m − c − z 2 m H m − c . Substituting both into (11) at size M M M yields (14) . The polynomial H M − c H_{M-c} H M − c involves the cones of index M − c M-c M − c and M − c − 1 M-c-1 M − c − 1 , and H m − c H_{m-c} H m − c those of index m − c m-c m − c and m − c − 1 m-c-1 m − c − 1 , all smaller than M < r M<r M < r . Since m < 2 c m<2c m < 2 c we have 2 m − c < 3 c 2m-c<3c 2 m − c < 3 c . If c ≤ q / 4 c \le q/4 c ≤ q /4 then 3 c ≤ 3 q / 4 ≤ q − c = r 3c \le3q/4 \le q-c=r 3 c ≤ 3 q /4 ≤ q − c = r , so 2 m − c < r 2m-c<r 2 m − c < r . If c > q / 4 c>q/4 c > q /4 then M / 2 < c < M M/2<c<M M /2 < c < M , hence m = M m=M m = M and 2 m − c = r 2m-c=r 2 m − c = r , and the terms of (14) cancel in pairs.
With (12) the polynomials L M L_M L M and L m L_m L m are expressed through diamonds of size smaller than M M M . A cone is called direct when r ≤ 3 r \le3 r ≤ 3 or when c > q / 4 c>q/4 c > q /4 . Direct cones are computed by running the growth of Definition 3 on K r K_r K r .
Eliminating the diamonds
Definition 6 also gives a generating function involving the dyadic cones alone.
The product G G G was defined in the introduction. Its coefficient 2 s 2 ( j ) 2^{s_2(j)} 2 s 2 ( j ) counts the odd entries in row j j j of Pascal’s triangle (OEIS A001316 [7 ] ). Choosing a subset of the nonzero binary digits of j j j gives exactly 2 s 2 ( j ) 2^{s_2(j)} 2 s 2 ( j ) odd binomial coefficients.
Proposition 16. In the ring of formal power series,
F ( z ) = ∑ q = 2 , 4 , 8 , … z 2 q + 2 ( C q ( z ) − 1 ) G ( z 4 q ) = ∑ m ≥ 2 m e v e n 2 s 2 ( m ) − 1 z 2 m + 2 ( C lb ( m ) ( z ) − 1 ) . (15) F(z)=\sum_{q=2,4,8,\ldots}z^{2q+2}(C_q(z)-1)G(z^{4q})=\sum_{\substack{m\ge2\\m\ \mathrm{even}}}2^{s_2(m)-1}z^{2m+2}(C_{\operatorname{lb}(m)}(z)-1). \tag*{(15)} F ( z ) = q = 2 , 4 , 8 , … ∑ z 2 q + 2 ( C q ( z ) − 1 ) G ( z 4 q ) = m ≥ 2 m even ∑ 2 s 2 ( m ) − 1 z 2 m + 2 ( C lb ( m ) ( z ) − 1 ) . (15) Moreover, for every dyadic M ≥ 1 M\ge1 M ≥ 1 ,
C 2 M = 1 + z + 2 J 2 , 2 M − 1 + 2 ∑ 2 ≤ m < M m e v e n 2 s 2 ( m ) z 2 m + 1 ( C lb ( m ) − 1 ) + z 2 M H M . (16) C_{2M}=1+z+2J_{2,2M-1}+2\sum_{\substack{2\le m<M\\m\ \mathrm{even}}}2^{s_2(m)}z^{2m+1}(C_{\operatorname{lb}(m)}-1)+z^{2M}H_M. \tag*{(16)} C 2 M = 1 + z + 2 J 2 , 2 M − 1 + 2 2 ≤ m < M m even ∑ 2 s 2 ( m ) z 2 m + 1 ( C lb ( m ) − 1 ) + z 2 M H M . (16)
Proof. For a dyadic q q q let U q U_q U q be the sum of z 2 p + 3 P p / ( 1 − z 4 p ) z^{2p+3}P_p/(1-z^{4p}) z 2 p + 3 P p / ( 1 − z 4 p ) over the dyadic p p p with 2 ≤ p ≤ q 2\le p\le q 2 ≤ p ≤ q , so that U 1 = 0 U_1=0 U 1 = 0 . The centers m < q m<q m < q with lb ( m ) = p \operatorname{lb}(m)=p lb ( m ) = p are the odd multiples of p p p below q q q . Summing the corresponding geometric progression in (3) gives S q , 0 = z − 3 ( 1 − z 2 q ) U q / 2 S_{q,0}=z^{-3}(1-z^{2q})U_{q/2} S q , 0 = z − 3 ( 1 − z 2 q ) U q /2 . With Definition 6 we obtain
U q = 1 + 2 z 2 q 1 + z 2 q U q / 2 + z 2 q + 2 ( C q − 1 ) 1 − z 4 q . U_q=\frac{1+2z^{2q}}{1+z^{2q}}U_{q/2}+\frac{z^{2q+2}(C_q-1)}{1-z^{4q}}. U q = 1 + z 2 q 1 + 2 z 2 q U q /2 + 1 − z 4 q z 2 q + 2 ( C q − 1 ) .
By induction, U Q U_Q U Q is the sum over the dyadic q ≤ Q q\le Q q ≤ Q of z 2 q + 2 ( C q − 1 ) / ( 1 − z 4 q ) z^{2q+2}(C_q-1)/(1-z^{4q}) z 2 q + 2 ( C q − 1 ) / ( 1 − z 4 q ) multiplied by the product of the factors ( 1 + 2 z 2 p ) / ( 1 + z 2 p ) (1+2z^{2p})/(1+z^{2p}) ( 1 + 2 z 2 p ) / ( 1 + z 2 p ) over the dyadic p p p with q < p ≤ Q q<p\le Q q < p ≤ Q . Put w = z 4 q w=z^{4q} w = z 4 q . These factors are ( 1 + 2 w 2 i ) / ( 1 + w 2 i ) (1+2w^{2^i})/(1+w^{2^i}) ( 1 + 2 w 2 i ) / ( 1 + w 2 i ) for 0 ≤ i < I 0\le i<I 0 ≤ i < I , where 2 I = Q / q 2^I=Q/q 2 I = Q / q , and the product of the denominators is ( 1 − w 2 I ) / ( 1 − w ) (1-w^{2^I})/(1-w) ( 1 − w 2 I ) / ( 1 − w ) . Letting Q Q Q tend to infinity gives the first expression in (15), since F = lim U Q F=\lim U_Q F = lim U Q by (9). The second expression follows by writing m = q ( 2 j + 1 ) m=q(2j+1) m = q ( 2 j + 1 ) , for which s 2 ( m ) = s 2 ( j ) + 1 s_2(m)=s_2(j)+1 s 2 ( m ) = s 2 ( j ) + 1 . For a finite Q = M / 2 Q=M/2 Q = M /2 the same computation gives
( 1 − z 2 M ) U M / 2 = ∑ 2 ≤ m < M m e v e n 2 s 2 ( m ) − 1 z 2 m + 2 ( C l b ( m ) − 1 ) . (1-z^{2M})U_{M/2}=\sum_{\substack{2\le m<M\\m\ \mathrm{even}}}2^{s_2(m)-1}z^{2m+2}(C_{\mathrm{lb}}(m)-1). ( 1 − z 2 M ) U M /2 = 2 ≤ m < M m even ∑ 2 s 2 ( m ) − 1 z 2 m + 2 ( C lb ( m ) − 1 ) .
and the left-hand side is z S M , 2 zS_{M,2} z S M , 2 . Identity (16) is then (13) with (12) .
Combining (15) with (5) proves the second form of Theorem 1 . In (16) the polynomial H M = C M + z C M − 1 − J 1 , M − 1 H_M=C_M+zC_{M-1}-J_{1,M-1} H M = C M + z C M − 1 − J 1 , M − 1 involves the cone of size M − 1 M-1 M − 1 , which is not dyadic. Writing X k = C 2 k − C 2 k − 1 X_k=C_{2^k}-C_{2^k-1} X k = C 2 k − C 2 k − 1 isolates the missing term in this recursion. Lemma 19 bounds its coefficient norm.
Layer polynomials
For a vertex v = ( p , x , y ) v=(p,x,y) v = ( p , x , y ) put g ( v ) = 2 x + y + p g(v)=2x+y+p g ( v ) = 2 x + y + p . The cone K r K_r K r is the set of vertices with x ≥ 0 x\ge0 x ≥ 0 , y ≥ 0 y\ge0 y ≥ 0 and g < r g<r g < r , and Ω M , c \Omega_{M,c} Ω M , c is the set of vertices of Ω M , 0 \Omega_{M,0} Ω M , 0 with g < 2 M − c g<2M-c g < 2 M − c . The cone K r − 1 K_{r-1} K r − 1 is thus obtained from K r K_r K r by removing the vertices with g = r − 1 g=r-1 g = r − 1 , and Ω M , c + 1 \Omega_{M,c+1} Ω M , c + 1 is obtained from Ω M , c \Omega_{M,c} Ω M , c by removing the vertices with g = 2 M − c − 1 g=2M-c-1 g = 2 M − c − 1 . In both cases we call the removed set the last layer . The earliest time of a vertex is g ( v ) + y g(v)+y g ( v ) + y , so the last layer cannot be reached before time r − 1 r-1 r − 1 in the first case and before time 2 M − c − 1 2M-c-1 2 M − c − 1 in the second. We put
∂ C r ( z ) = z − ( r − 1 ) ( C r ( z ) − C r − 1 ( z ) ) ( r ≥ 1 ) , ∂ C 0 = 1 , \partial C_r(z)=z^{-(r-1)}\bigl(C_r(z)-C_{r-1}(z)\bigr)\quad(r\ge1),\qquad\partial C_0=1, ∂ C r ( z ) = z − ( r − 1 ) ( C r ( z ) − C r − 1 ( z ) ) ( r ≥ 1 ) , ∂ C 0 = 1 ,
and, for a dyadic integer M M M and 0 ≤ c < M 0\le c<M 0 ≤ c < M ,
E c ( z ) = z − ( 2 M − c − 1 ) ( L M , c ( z ) − L M , c + 1 ( z ) ) , e j ( c ) = [ z j ] E c ( z ) . (17) E_c(z)=z^{-(2M-c-1)}\bigl(L_{M,c}(z)-L_{M,c+1}(z)\bigr),\qquad e_j(c)=[z^j]E_c(z). \tag*{(17)} E c ( z ) = z − ( 2 M − c − 1 ) ( L M , c ( z ) − L M , c + 1 ( z ) ) , e j ( c ) = [ z j ] E c ( z ) . (17)
We call E c E_c E c the kernel of index c c c . Its coefficients are signed differences of birth counts. The exponent of z z z is a delay, counted from the time at which the last layer is reached. By definition
C r ( z ) = ∑ s = 1 r z s − 1 ∂ C s ( z ) , X k ( z ) = z 2 k − 1 ∂ C 2 k ( z ) . C_r(z)=\sum_{s=1}^{r}z^{s-1}\partial C_s(z),\qquad X_k(z)=z^{2^k-1}\partial C_{2^k}(z). C r ( z ) = s = 1 ∑ r z s − 1 ∂ C s ( z ) , X k ( z ) = z 2 k − 1 ∂ C 2 k ( z ) .
Lemma 17. The functions ∂ C r \partial C_r ∂ C r and E c E_c E c are polynomials in z z z with constant term 1. The kernel E c E_c E c does not depend on the dyadic integer M > c M>c M > c . Moreover deg ∂ C r ≤ r ( r − 1 ) / 2 \deg\partial C_r\le r(r-1)/2 deg ∂ C r ≤ r ( r − 1 ) /2 , and deg E c ≤ 4 c 2 \deg E_c\le4c^2 deg E c ≤ 4 c 2 for c ≥ 1 c\ge1 c ≥ 1 , while $E_0=1.
Proof. Let D D D be one of the domains K r K_r K r and Ω M , c \Omega_{M,c} Ω M , c , let t 0 t_0 t 0 be r − 1 r-1 r − 1 or 2 M − c − 1 2M-c-1 2 M − c − 1 accordingly, and let D ′ D' D ′ be D D D without its last layer. A vertex of the last layer has earliest time t 0 + y t_0+y t 0 + y . Hence no vertex of the last layer is born before time t 0 t_0 t 0 , and none sends a proposal before time t 0 + 1 t_0+1 t 0 + 1 . The growths on D D D and on D ′ D' D ′ therefore agree on D ′ D' D ′ up to time t 0 t_0 t 0 . The only vertex of the last layer that can be born at time t 0 t_0 t 0 is the vertex of the axis y = 0 y=0 y = 0 with 2 x + p = t 0 2x+p=t_0 2 x + p = t 0 . It belongs to D D D , and it is born at time t 0 t_0 t 0 by Lemma 7 . The difference of the two birth polynomials is therefore z t 0 z^{t_0} z t 0 plus terms of higher degree.
Let m m m be the least dyadic integer with m > c m>c m > c and let M M M be a dyadic multiple of m m m . Theorem 12 , applied to the cuts c c c and c + 1 c+1 c + 1 , gives L M , c − L M , c + 1 = z 2 ( M − m ) ( L m , c − L m , c + 1 ) L_{M,c}-L_{M,c+1}=z^{2(M-m)}(L_{m,c}-L_{m,c+1}) L M , c − L M , c + 1 = z 2 ( M − m ) ( L m , c − L m , c + 1 ) . Thus (17) gives the same polynomial for M M M and for m m m .
By Remark 4, the r ( r + 1 ) / 2 r(r+1)/2 r ( r + 1 ) /2 vertices of K r K_r K r give the bound on deg ∂ C r \deg\partial C_r deg ∂ C r . The triangle Ω m , 0 \Omega_{m,0} Ω m , 0 has m ( m + 1 ) m(m+1) m ( m + 1 ) vertices, so deg E c ≤ m 2 − m + c \deg E_c\le m^2-m+c deg E c ≤ m 2 − m + c . For c ≥ 1 c\ge1 c ≥ 1 we have m ≤ 2 c m\le2c m ≤ 2 c . For c = 0 c=0 c = 0 we have m = 1 m=1 m = 1 , L 1 , 0 = 1 + z L_{1,0}=1+z L 1 , 0 = 1 + z and L 1 , 1 = 1 L_{1,1}=1 L 1 , 1 = 1 .
For example
E 0 = 1 , E 1 = E 2 = 1 + z , E 3 = 1 + z 2 + 2 z 3 , E 4 = 1 + z 2 + z 3 − z 5 . E_0=1,\qquad E_1=E_2=1+z,\qquad E_3=1+z^2+2z^3,\qquad E_4=1+z^2+z^3-z^5. E 0 = 1 , E 1 = E 2 = 1 + z , E 3 = 1 + z 2 + 2 z 3 , E 4 = 1 + z 2 + z 3 − z 5 .
and ∂ C 1 = 1 \partial C_1=1 ∂ C 1 = 1 , ∂ C 2 = 1 + z \partial C_2=1+z ∂ C 2 = 1 + z , ∂ C 3 = 1 + z + z 2 \partial C_3=1+z+z^2 ∂ C 3 = 1 + z + z 2 , ∂ C 4 = 1 + z 2 + z 3 \partial C_4=1+z^2+z^3 ∂ C 4 = 1 + z 2 + z 3 . For n ≥ 0 n\ge0 n ≥ 0 let J n J_n J n be the largest degree of the kernels E 0 , … , E n E_0,\ldots,E_n E 0 , … , E n . By the lemma, J 0 = 0 J_0=0 J 0 = 0 and J n ≤ 4 n 2 J_n\le4n^2 J n ≤ 4 n 2 .
Differences of consecutive cones
Proposition 18. Let M M M be dyadic and let M < r ≤ 2 M M < r \le2M M < r ≤ 2 M . Then
∂ C r = E 2 M − r + z M ( ∂ C r − M + ∂ C r − M − 1 − 1 ) . (18) \partial C_r = E_{2M-r} + z^M\left(\partial C_{r-M} + \partial C_{r-M-1} - 1\right). \tag*{(18)} ∂ C r = E 2 M − r + z M ( ∂ C r − M + ∂ C r − M − 1 − 1 ) . (18)
Proof. Put c = 2 M − r c = 2M-r c = 2 M − r , so that 0 ≤ c < M 0 \le c < M 0 ≤ c < M . Identity (11) for the cuts c c c and c + 1 c+1 c + 1 gives
C r − C r − 1 = L M , c − L M , c + 1 + z 2 M ( H M − c − H M − c − 1 ) . C_r - C_{r-1} = L_{M,c} - L_{M,c+1} + z^{2M}\left(H_{M-c} - H_{M-c-1}\right). C r − C r − 1 = L M , c − L M , c + 1 + z 2 M ( H M − c − H M − c − 1 ) .
Let ρ = M − c = r − M \rho= M-c = r-M ρ = M − c = r − M . For ρ ≥ 2 \rho\ge2 ρ ≥ 2 the definition of H ρ H_\rho H ρ gives H ρ − H ρ − 1 = ( C ρ − C ρ − 1 ) + z ( C ρ − 1 − C ρ − 2 ) − z ρ − 1 H_\rho-H_{\rho-1}=(C_\rho-C_{\rho-1})+z(C_{\rho-1}-C_{\rho-2})-z^{\rho-1} H ρ − H ρ − 1 = ( C ρ − C ρ − 1 ) + z ( C ρ − 1 − C ρ − 2 ) − z ρ − 1 , which is z ρ − 1 ( ∂ C ρ + ∂ C ρ − 1 − 1 ) z^{\rho-1}(\partial C_\rho+\partial C_{\rho-1}-1) z ρ − 1 ( ∂ C ρ + ∂ C ρ − 1 − 1 ) . For ρ = 1 \rho=1 ρ = 1 we have H 1 − H 0 = 1 H_1-H_0=1 H 1 − H 0 = 1 , which is the same expression because ∂ C 1 = ∂ C 0 = 1 \partial C_1=\partial C_0=1 ∂ C 1 = ∂ C 0 = 1 . The first difference is z r − 1 E c z^{r-1}E_c z r − 1 E c by (17) . Dividing by z r − 1 z^{r-1} z r − 1 gives (18) , since 2 M + ρ − 1 − ( r − 1 ) = M 2M+\rho-1-(r-1)=M 2 M + ρ − 1 − ( r − 1 ) = M .
For instance ∂ C 8 = E 0 + z 4 ( ∂ C 4 + ∂ C 3 − 1 ) = 1 + z 4 + z 5 + 2 z 6 + z 7 \partial C_8=E_0+z^4(\partial C_4+\partial C_3-1)=1+z^4+z^5+2z^6+z^7 ∂ C 8 = E 0 + z 4 ( ∂ C 4 + ∂ C 3 − 1 ) = 1 + z 4 + z 5 + 2 z 6 + z 7 . At z = 1 z=1 z = 1 , this identity relates the total numbers of births. Its coefficient norm controls the error made by replacing a cone by its neighbor. Its successive substitutions give the decomposition of Section 8.
Lemma 19. For every integer k ≥ 1 k \ge1 k ≥ 1 ,
∥ C 2 k − C 2 k − 1 ∥ = O ( k 2 2 k ) , \lVert C_{2^k} - C_{2^k-1}\rVert= O(k^2 2^k), ∥ C 2 k − C 2 k − 1 ∥ = O ( k 2 2 k ) , with an absolute implied constant. The same bound holds for the absolute value of any partial sum of these coefficients.
Proof. The kernel E c E_c E c is computed in a triangle of size at most 2 max ( c , 1 ) 2\max(c,1) 2 max ( c , 1 ) , so ∥ E c ∥ = O ( ( c + 1 ) 2 ) \lVert E_c\rVert=O((c+1)^2) ∥ E c ∥ = O (( c + 1 ) 2 ) . Apply (18) repeatedly to ∂ C 2 k \partial C_{2^k} ∂ C 2 k . At a node with cone index 2 a − c 2^a-c 2 a − c , continue only while c + 1 ≤ 2 a − 2 c+1\le2^{a-2} c + 1 ≤ 2 a − 2 . The depth is at most k k k , and every cut index is at most k k k . Each internal node contributes O ( ( k + 1 ) 2 ) O((k+1)^2) O (( k + 1 ) 2 ) to the norm. At a leaf, the cone index is smaller than 4 ( k + 1 ) 4(k+1) 4 ( k + 1 ) , so the finite-domain bound gives the same estimate. There are at most 2 k 2^k 2 k leaves and fewer than 2 k 2^k 2 k internal nodes. Multiplication by a monomial preserves the norm, which proves the result. Explicit constants are given in Appendix A.
Coefficient extraction and complexity
Throughout this section n ≥ 4 n \ge4 n ≥ 4 is the queried index and ℓ = ⌊ log 2 ( n + 3 ) ⌋ + 1 \ell=\lfloor\log_2(n+3)\rfloor+1 ℓ = ⌊ log 2 ( n + 3 )⌋ + 1 . By (6) and by summation, with Σ F ( j ) = ∑ i ≤ j F ( i ) \Sigma F(j)=\sum_{i\le j}F(i) Σ F ( j ) = ∑ i ≤ j F ( i ) ,
a ( n ) = 6 n − 11 + 2 Σ F ( n + 2 ) + 2 Σ F ( n + 1 ) + 4 Σ F ( n ) + 4 Σ F ( n − 1 ) . (19) a(n)=6n-11+2\Sigma F(n+2)+2\Sigma F(n+1)+4\Sigma F(n)+4\Sigma F(n-1). \tag*{(19)} a ( n ) = 6 n − 11 + 2Σ F ( n + 2 ) + 2Σ F ( n + 1 ) + 4Σ F ( n ) + 4Σ F ( n − 1 ) . (19)
It is therefore enough to compute a coefficient F ( t ) F(t) F ( t ) or a partial sum Σ F ( t ) \Sigma F(t) Σ F ( t ) for t ≤ n + 2 t\le n+2 t ≤ n + 2 . The value t ( n ) t(n) t ( n ) is obtained from (6) with four coefficients. Only the diamonds P q P_q P q with 2 q + 3 ≤ n + 2 2q+3\le n+2 2 q + 3 ≤ n + 2 are involved, and their sizes are q = 2 i q=2^i q = 2 i with i < ℓ i<\ell i < ℓ .
A graph of expressions
The algorithm builds a finite directed acyclic graph. Its nodes are the polynomials P q P_q P q and L M L_M L M for dyadic indices, and the polynomials C r C_r C r and H r H_r H r that are reached from them. Each node is written as a signed sum of blocks
R ( z ) = ∑ j = 0 N − 1 z α + δ j Q ( z ) . (20) R(z)=\sum_{j=0}^{N-1}z^{\alpha+\delta j}Q(z). \tag*{(20)} R ( z ) = j = 0 ∑ N − 1 z α + δ j Q ( z ) . (20)
where Q Q Q is another node, an interval J u , v J_{u,v} J u , v or the constant 1, and where α \alpha α , δ \delta δ , and N N N are nonnegative integers. For q ≥ 2 q \ge2 q ≥ 2 dyadic, (2) , (13) , and (12) give the rule
P q = 1 + 2 J 1 , q − 2 + S q , 0 + 2 S q / 2 , 1 + z q − 1 H q / 2 . (21) P_q = 1 + 2J_{1,q-2} + S_{q,0} + 2S_{q/2,1} + z^{q-1}H_{q/2}. \tag*{(21)} P q = 1 + 2 J 1 , q − 2 + S q , 0 + 2 S q /2 , 1 + z q − 1 H q /2 . (21)
All its shifts are nonnegative, including when q = 2 q = 2 q = 2 . The other rules are the definition of H r H_r H r , (12) for L M L_M L M , and (13) and (14) for cones that are not direct. The direct cones are leaves. Their coefficients are computed by running the growth and are stored as lists. Every node is created once and shared by all the expressions that refer to it.
The sums S B , d S_{B,d} S B , d have about B / 2 B/2 B /2 terms. To group them into blocks, partition the even integers m m m according to p = lb ( m ) p = \operatorname{lb}(m) p = lb ( m ) . The integers m < B m < B m < B with lb ( m ) = p \operatorname{lb}(m) = p lb ( m ) = p are the numbers p ( 2 j + 1 ) p(2j + 1) p ( 2 j + 1 ) with 0 ≤ j < N B , p 0 \le j < N_{B,p} 0 ≤ j < N B , p , where N B , p = 1 + ⌊ ( B − 1 − p ) / ( 2 p ) ⌋ N_{B,p} = 1 + \left\lfloor(B - 1 - p)/(2p) \right\rfloor N B , p = 1 + ⌊ ( B − 1 − p ) / ( 2 p ) ⌋ . Hence
S B , d = ∑ p = 2 , 4 , 8 , … p < B ∑ j = 0 N B , p − 1 z 2 p + d + 4 p j P p . (22) S_{B,d} = \sum_{\substack{p=2,4,8,\ldots\\p<B}} \sum_{j=0}^{N_{B,p}-1} z^{2p+d+4pj}P_p. \tag*{(22)} S B , d = p = 2 , 4 , 8 , … p < B ∑ j = 0 ∑ N B , p − 1 z 2 p + d + 4 p j P p . (22)
which is a sum of fewer than log 2 B \log_2 B log 2 B blocks. The series F F F is treated in the same way. For a query at index t t t only the first 1 + ⌊ ( t − 2 q − 3 ) / ( 4 q ) ⌋ 1 + \left\lfloor(t - 2q - 3)/(4q) \right\rfloor 1 + ⌊ ( t − 2 q − 3 ) / ( 4 q ) ⌋ copies of P q P_q P q in (9) can contribute.
To each node X X X we attach its total mass μ ( X ) = X ( 1 ) \mu(X) = X(1) μ ( X ) = X ( 1 ) and an integer b ( X ) b(X) b ( X ) that bounds its degree. Both are computed from the rules. The bound b b b of a sum is the largest of the bounds of its shifted terms, without regard to cancellations. Zero terms are omitted, and a direct cone is assigned its degree.
The cones that occur
For r ≥ 1 r \ge1 r ≥ 1 let λ ( r ) \lambda(r) λ ( r ) be the least integer with 2 λ ( r ) ≥ r 2^{\lambda(r)} \ge r 2 λ ( r ) ≥ r , let c ( r ) = 2 λ ( r ) − r c(r) = 2^{\lambda(r)} - r c ( r ) = 2 λ ( r ) − r , and call ρ ( r ) = λ ( r ) + c ( r ) \rho(r) = \lambda(r) + c(r) ρ ( r ) = λ ( r ) + c ( r ) the rank of r r r . If r = 2 b − e ≥ 1 r = 2^b - e \ge1 r = 2 b − e ≥ 1 with integers b ≥ 0 b \ge0 b ≥ 0 and e ≥ 0 e \ge0 e ≥ 0 , then ρ ( r ) ≤ b + e \rho(r) \le b + e ρ ( r ) ≤ b + e . Indeed, either e < 2 b − 1 e < 2^{b-1} e < 2 b − 1 and b = λ ( r ) b = \lambda(r) b = λ ( r ) , or r ≤ 2 b − 1 r \le2^{b-1} r ≤ 2 b − 1 and r = 2 b − 1 − ( e − 2 b − 1 ) r = 2^{b-1} - (e - 2^{b-1}) r = 2 b − 1 − ( e − 2 b − 1 ) with a smaller exponent and a smaller deficit, and one repeats the argument.
Lemma 20. Every cone C r C_r C r of the graph built for the diamonds P 2 i P_{2^i} P 2 i with i ≤ s i \le s i ≤ s satisfies ρ ( r ) ≤ s \rho(r) \le s ρ ( r ) ≤ s . Consequently the graph contains O ( s 2 ) O(s^2) O ( s 2 ) cones, and every direct cone has an index r < 3 s r < 3s r < 3 s or r ≤ 3 r \le3 r ≤ 3 .
Proof. The diamond P q P_q P q with q = 2 i q = 2^i q = 2 i refers to H q / 2 H_{q/2} H q /2 , hence to the cones of index 2 i − 1 2^{i-1} 2 i − 1 and 2 i − 1 − 1 2^{i-1} - 1 2 i − 1 − 1 , whose ranks are at most i i i . It also refers to diamonds of smaller size. The triangle L M L_M L M refers only to diamonds of size smaller than M M M . Consider now a cone C r C_r C r that is not direct, with a = λ ( r ) a = \lambda(r) a = λ ( r ) , c = c ( r ) c = c(r) c = c ( r ) , q = 2 a q = 2^a q = 2 a and M = q / 2 M = q/2 M = q /2 , so that c ≤ q / 4 c \le q/4 c ≤ q /4 . Through H M − c H_{M-c} H M − c it refers to the cones of index 2 a − 1 − c 2^{a-1} - c 2 a − 1 − c and 2 a − 1 − ( c + 1 ) 2^{a-1} - (c+1) 2 a − 1 − ( c + 1 ) , whose ranks are at most a + c a + c a + c . When c > 0 c > 0 c > 0 , let m = 2 b m = 2^b m = 2 b be the smallest dyadic integer with m ≥ c m \ge c m ≥ c . Then b ≤ a − 2 b \le a - 2 b ≤ a − 2 . The cone C r C_r C r refers to the cones of index 2 b + 1 − c 2^{b+1} - c 2 b + 1 − c , 2 b − c 2^b - c 2 b − c and 2 b − ( c + 1 ) 2^b - (c+1) 2 b − ( c + 1 ) , whose ranks are at most b + 1 + c ≤ a + c b + 1 + c \le a + c b + 1 + c ≤ a + c . It also refers to L M L_M L M and L m L_m L m , hence to diamonds of size at most 2 a − 2 2^{a-2} 2 a − 2 . Along the references between cones the rank never increases, and the cones referred to by a diamond of size 2 i 2^i 2 i have rank at most i i i . This proves the first claim. A cone of rank at most s s s is determined by a pair ( a , c ) (a,c) ( a , c ) with a + c ≤ s a + c \le s a + c ≤ s , and there are O ( s 2 ) O(s^2) O ( s 2 ) such pairs. If a cone with r ≥ 4 r \ge4 r ≥ 4 is direct then c > 2 a / 4 c > 2^a/4 c > 2 a /4 , so r = 2 a − c < 3 c ≤ 3 ( s − a ) < 3 s r = 2^a - c < 3c \le3(s-a) < 3s r = 2 a − c < 3 c ≤ 3 ( s − a ) < 3 s .
Extraction of a coefficient and of a partial sum
For a node Q Q Q write Q t Q_t Q t for the coefficient of z t z^t z t and Q ≤ t = ∑ i ≤ t Q i Q_{\le t} = \sum_{i \le t} Q_i Q ≤ t = ∑ i ≤ t Q i . These numbers vanish for t < 0 t < 0 t < 0 , and for t ≥ b ( Q ) t \ge b(Q) t ≥ b ( Q ) one has Q ≤ t = μ ( Q ) Q_{\le t} = \mu(Q) Q ≤ t = μ ( Q ) . Consider a block R R R as in (20) , with δ ≥ 1 \delta\ge1 δ ≥ 1 , and let b = b ( Q ) b = b(Q) b = b ( Q ) . For a block with a single copy we take δ = 1 \delta= 1 δ = 1 . For t ≥ α t \ge\alpha t ≥ α put
j 0 = max ( 0 , ⌈ t − α − b δ ⌉ ) , j 1 = min ( N − 1 , ⌊ t − α δ ⌋ ) , j_0 = \max\left(0,\left\lceil\frac{t-\alpha-b}{\delta}\right\rceil\right), \qquad
j_1 = \min\left(N-1,\left\lfloor\frac{t-\alpha}{\delta}\right\rfloor\right), j 0 = max ( 0 , ⌈ δ t − α − b ⌉ ) , j 1 = min ( N − 1 , ⌊ δ t − α ⌋ ) ,
f = max ( 0 , min ( j 1 + 1 , 1 + ⌊ t − α − b δ ⌋ ) ) . f = \max\left(0,\min\left(j_1+1,1+\left\lfloor\frac{t-\alpha-b}{\delta}\right\rfloor\right)\right). f = max ( 0 , min ( j 1 + 1 , 1 + ⌊ δ t − α − b ⌋ ) ) .
The copies with j < j 0 j<j_0 j < j 0 end before t t t and the copies with j > j 1 j>j_1 j > j 1 start after t t t . Therefore
R t = ∑ j = j 0 j 1 Q t − α − δ j , R ≤ t = f μ ( Q ) + ∑ j = f j 1 Q ≤ t − α − δ j . (23) R_t=\sum_{j=j_0}^{j_1} Q_{t-\alpha-\delta j},\qquad R_{\leq t}=f\,\mu(Q)+\sum_{j=f}^{j_1} Q_{\leq t-\alpha-\delta j}. \tag*{(23)} R t = j = j 0 ∑ j 1 Q t − α − δ j , R ≤ t = f μ ( Q ) + j = f ∑ j 1 Q ≤ t − α − δ j . (23)
In the second formula the copies with j < f j<f j < f lie entirely below t t t and are replaced by their mass. For t < α t<\alpha t < α both quantities vanish. A query at a node is answered by applying (23) to each of its blocks, with the appropriate signs. The answers are stored in a table indexed by the node, the index, and the type of query, so that no query is evaluated twice. The number of terms in each sum of (23) is at most 1 + b / δ 1+b/\delta 1 + b / δ .
Supports and residues
The scale σ ( X ) \sigma(X) σ ( X ) of a node is q q q for P q P_q P q and L q L_q L q , and it is the smallest dyadic integer q ≥ r q\geq r q ≥ r for C r C_r C r and H r H_r H r . In every rule, the nodes that appear on the right-hand side have a scale at most equal to the scale of the node that is defined.
For k ≥ 1 k\geq1 k ≥ 1 , let τ k \tau_k τ k be the maximum of deg C r − 2 r + 2 \deg C_r-2r+2 deg C r − 2 r + 2 over direct cones of rank at most k k k . The axis vertex A ( 0 , r − 1 ) A(0,r-1) A ( 0 , r − 1 ) is born at time 2 r − 2 2r-2 2 r − 2 , so τ k ≥ 0 \tau_k\geq0 τ k ≥ 0 . Remark 4 and Lemma 20 give τ k ≤ 5 k 2 \tau_k\leq5k^2 τ k ≤ 5 k 2 .
Lemma 21. Let k ≥ 1 k\geq1 k ≥ 1 . For every cone index r r r with ρ ( r ) ≤ k \rho(r)\leq k ρ ( r ) ≤ k , and every dyadic q = 2 j q=2^j q = 2 j with 1 ≤ j ≤ k 1\leq j\leq k 1 ≤ j ≤ k ,
b ( C r ) ≤ 2 r − 2 + τ k , b ( P q ) ≤ 2 q − 3 + τ k , b ( L q ) ≤ 2 q − 1 + τ k . b(C_r)\leq2r-2+\tau_k,\qquad b(P_q)\leq2q-3+\tau_k,\qquad b(L_q)\leq2q-1+\tau_k. b ( C r ) ≤ 2 r − 2 + τ k , b ( P q ) ≤ 2 q − 3 + τ k , b ( L q ) ≤ 2 q − 1 + τ k . Consequently every node X X X in the graph for the queried index n n n satisfies deg X ≤ b ( X ) ≤ 2 σ ( X ) + 5 ℓ 2 \deg X\leq b(X)\leq2\sigma(X)+5\ell^2 deg X ≤ b ( X ) ≤ 2 σ ( X ) + 5 ℓ 2 .
Proof. Put τ = τ k \tau=\tau_k τ = τ k and use induction along the rules, starting from the direct cones, whose bounds are their degrees. If the bounds hold for the cones in H r H_r H r , its defining terms give b ( H r ) ≤ 2 r − 2 + τ b(H_r)\leq2r-2+\tau b ( H r ) ≤ 2 r − 2 + τ . A term z 2 m + 2 P p z^{2m+2}P_p z 2 m + 2 P p of L M L_M L M has p = lb ( m ) p=\operatorname{lb}(m) p = lb ( m ) and m + p ≤ M m+p\leq M m + p ≤ M . Together with the axes, this gives b ( L M ) ≤ 2 M − 1 + τ b(L_M)\leq2M-1+\tau b ( L M ) ≤ 2 M − 1 + τ .
For a cone that is not direct, use the notation of Proposition 15 . All the smaller cones have rank at most k k k , and the diamonds in L M L_M L M and L m L_m L m have size at most q / 4 q/4 q /4 . The five terms of (14) therefore have bounds at most
max ( 4 M − 2 c − 2 , 2 M + 2 m − 2 c − 2 , 2 M − 1 ) + τ ≤ 2 r − 2 + τ , \max(4M-2c-2,\ 2M+2m-2c-2,\ 2M-1)+\tau\leq2r-2+\tau, max ( 4 M − 2 c − 2 , 2 M + 2 m − 2 c − 2 , 2 M − 1 ) + τ ≤ 2 r − 2 + τ ,
because m ≤ M m\leq M m ≤ M and 2 c + 1 ≤ 2 M 2c+1\leq2M 2 c + 1 ≤ 2 M . The case (13) follows from the same bounds with c = 0 c=0 c = 0 . In (21) , a term of S q , 0 S_{q,0} S q , 0 has bound at most 2 ( m + p ) − 3 + τ ≤ 2 q − 3 + τ 2(m+p)-3+\tau\leq2q-3+\tau 2 ( m + p ) − 3 + τ ≤ 2 q − 3 + τ . The terms of S q / 2 , 1 S_{q/2,1} S q /2 , 1 have bound at most q − 2 + τ q-2+\tau q − 2 + τ , and the last term has bound q − 1 + q − 2 + τ q-1+q-2+\tau q − 1 + q − 2 + τ . The constant and the interval satisfy the same bound. This proves the asserted inequalities without using cancellation. Lemma 20 and τ ℓ ≤ 5 ℓ 2 \tau_\ell\leq5\ell^2 τ ℓ ≤ 5 ℓ 2 give the conclusion. □
The horizontal spine in the diamond also gives deg P q ≥ 2 q − 3 \deg P_q\geq2q-3 deg P q ≥ 2 q − 3 .
Lemma 22. Fix the queried index n n n . There is a constant K 0 K_0 K 0 such that every index t t t queried at a node of scale σ \sigma σ during the evaluation of (19) satisfies t ≡ n + ε ( m o d σ ) t\equiv n+\varepsilon\pmod{\sigma} t ≡ n + ε ( mod σ ) for some integer ε \varepsilon ε with ∣ ε ∣ ≤ K 0 ℓ |\varepsilon|\leq K_0\ell ∣ ε ∣ ≤ K 0 ℓ .
Proof. A query at a node is generated by a chain of blocks that starts at the root F F F . Passing through a block (20) replaces the index t t t by t − α − δ j t-\alpha-\delta j t − α − δ j . We inspect the shifts α + δ j \alpha+\delta j α + δ j of the rules. In (22) the shift is 2 p + d + 4 p j 2p+d+4pj 2 p + d + 4 p j with d ∈ { 0 , 1 , 2 } d\in\{0,1,2\} d ∈ { 0 , 1 , 2 } , and the child P p P_p P p has scale p p p . In (21) the last term has shift q − 1 q-1 q − 1 and its child H q / 2 H_{q/2} H q /2 has scale q / 2 q/2 q /2 . In (13) and (14) the shifts are 0 0 0 , q q q , and q − 2 m q-2m q − 2 m , the children with shift q q q have a scale that divides q q q , and the children with shift q − 2 m q-2m q − 2 m have a scale that divides 2 m 2m 2 m , which divides q − 2 m q-2m q − 2 m . In the definition of H r H_r H r the shifts are 0 0 0 and 1 1 1 . In (9) the shift is 2 q + 3 + 4 q j 2q+3+4qj 2 q + 3 + 4 q j and the child has scale q q q . In each case the shift is a multiple of the scale of the child plus an integer of absolute value at most 3. Scales are powers of two and do not increase along a chain, so the scale of the current node divides the scale of every earlier child. Modulo the scale of the current node, the index t t t therefore differs from the root index by a sum of at most three units per block of the chain. The root indices are n + 2 n+2 n + 2 , n + 1 n+1 n + 1 , n n n , and n − 1 n-1 n − 1 . The length of a chain is also bounded. Along a chain the scale is at least halved at each block, except on a passage from H r H_r H r to a cone. Two such passages cannot be consecutive. Since there are at most ℓ \ell ℓ scales, a chain has O ( ℓ ) O(\ell) O ( ℓ ) blocks.
Proof of the direct access theorem
The terms a ( 0 ) , … , a ( 3 ) a(0),\ldots,a(3) a ( 0 ) , … , a ( 3 ) are returned directly, so let n ≥ 4 n\ge4 n ≥ 4 . By Lemma 20 the graph has O ( ℓ 2 ) O(\ell^2) O ( ℓ 2 ) cones, hence O ( ℓ 2 ) O(\ell^2) O ( ℓ 2 ) nodes, since only a bounded number of nodes H r H_r H r occur for each cone and there are O ( ℓ ) O(\ell) O ( ℓ ) diamonds and triangles. By (22) each node is a sum of O ( ℓ ) O(\ell) O ( ℓ ) blocks. The direct cones have O ( ℓ ) O(\ell) O ( ℓ ) distinct indices smaller than 3 ℓ 3\ell 3 ℓ and O ( ℓ 2 ) O(\ell^2) O ( ℓ 2 ) vertices each. Every vertex receives at most three proposals and emits at most once, so all the direct cones are computed with O ( ℓ 3 ) O(\ell^3) O ( ℓ 3 ) elementary operations on vertices.
We count the entries of the table of answers. At a node of scale σ \sigma σ the queried indices lie in the interval from 0 to b b b , with b ≤ 2 σ + 5 ℓ 2 b\le2\sigma+5\ell^2 b ≤ 2 σ + 5 ℓ 2 by Lemma 21, because the other indices are answered by 0 or by the mass. If σ ≤ ℓ \sigma\le\ell σ ≤ ℓ this interval contains O ( ℓ 2 ) O(\ell^2) O ( ℓ 2 ) integers. If σ > ℓ \sigma>\ell σ > ℓ , Lemma 22 leaves O ( ℓ ) O(\ell) O ( ℓ ) residues modulo σ \sigma σ , and each residue has O ( 1 + ℓ 2 / σ ) O(1+\ell^2/\sigma) O ( 1 + ℓ 2 / σ ) representatives in the interval, which gives O ( ℓ 2 ) O(\ell^2) O ( ℓ 2 ) indices again. With two types of queries the table has O ( ℓ 4 ) O(\ell^4) O ( ℓ 4 ) entries.
An entry is computed by applying (23) to O ( ℓ ) O(\ell) O ( ℓ ) blocks. For a block with child P p P_p P p the step is δ = 4 p \delta=4p δ = 4 p and the number of terms is at most 1 + b ( P p ) / ( 4 p ) = O ( ℓ 2 ) 1+b(P_p)/(4p)=O(\ell^2) 1 + b ( P p ) / ( 4 p ) = O ( ℓ 2 ) by Lemma 21. The other blocks have a single copy. An entry therefore costs O ( ℓ 3 ) O(\ell^3) O ( ℓ 3 ) arithmetic operations and look-ups, and the whole evaluation costs O ( ℓ 7 ) O(\ell^7) O ( ℓ 7 ) of them. With a balanced dictionary each look-up costs O ( log ℓ ) O(\log\ell) O ( log ℓ ) comparisons, giving O ( ℓ 8 ) O(\ell^8) O ( ℓ 8 ) operations in total.
All the integers that occur are indices, numbers of copies, or signed sums of numbers of births in domains with O ( n 2 ) O(n^2) O ( n 2 ) vertices. They have O ( ℓ ) O(\ell) O ( ℓ ) bits. The algorithm is therefore polynomial in ℓ \ell ℓ in bit complexity as well. With elementary integer arithmetic, O ( ℓ 10 ) O(\ell^{10}) O ( ℓ 10 ) is a sufficient bound in a model with addressed memory. Simulation on a Turing machine preserves polynomial time, without asserting the same exponent. Consequently the maps n ↦ a ( n ) n\mapsto a(n) n ↦ a ( n ) and n ↦ t ( n ) n\mapsto t(n) n ↦ t ( n ) belong to FP.
Remark 23. The proof uses neither the identity deg P q = 2 q − 3 \deg P_q=2q-3 deg P q = 2 q − 3 nor any bound on the time at which a cone becomes extinct other than its number of vertices.
Computations
The supplementary code contains two separately written implementations, both using integer arithmetic and neither reading a table of birth polynomials. The first builds the expanded cone identities. The second uses the shorter triangle reduction in (14) , an event queue for the direct cones, and the factorized generating function (5) for the global count. They share the mathematical identities, but not their implementation.
Both programs agree with direct simulation through n = 1024 n=1024 n = 1024 , including the OEIS values [7 ] . They also pass coefficient and partial-sum checks against the reference diamonds through P 65536 P_{65536} P 65536 . The generating function agrees with the global filter through n = 262144 n=262144 n = 262144 . The README and recorded outputs give the query counts and the reproduction commands.
The two programs agree on a ( n ) a(n) a ( n ) and t ( n ) t(n) t ( n ) at each of the six large indices in Table 1 . For example,
Table 1. Observed wall-clock times for single-process Python implementations. These are individual runs, not estimates of the optimal complexity exponent.
a ( 131072 ) = 17 727 196 305 , a ( 262144 ) = 70 909 299 829 , a(131072)=17\,727\,196\,305,\qquad a(262144)=70\,909\,299\,829, a ( 131072 ) = 17 727 196 305 , a ( 262144 ) = 70 909 299 829 ,
and a ( 10 12 ) = 897 974 080 671 417 343 896 245 a(10^{12}) = 897\,974\,080\,671\,417\,343\,896\,245 a ( 1 0 12 ) = 897 974 080 671 417 343 896 245 , t ( 10 12 ) = 148 595 720 694 t(10^{12}) = 148\,595\,720\,694 t ( 1 0 12 ) = 148 595 720 694 .
The value of a ( 10 100 ) a(10^{100}) a ( 1 0 100 ) has 200 decimal digits. The supplementary JSON files contain the full integer outputs and the check results.
The large-index comparisons check the implementations against each other. They do not constitute independent simulations of the full geometric structure at those indices, nor are they used in the proofs.
Asymptotic structure
The normalized masses of the diamonds converge to a constant κ \kappa κ . The cumulative birth counts, rescaled on dyadic intervals, converge to a continuous profile. Two functional equations determine this profile and its extreme values.
A computable density for the diamonds
Write μ q = P q ( 1 ) \mu_q=P_q(1) μ q = P q ( 1 ) for dyadic q ≥ 2 q\ge2 q ≥ 2 .
Theorem 24. There is a positive real number κ \kappa κ such that, as k → ∞ k\to\infty k → ∞ ,
μ 2 k = κ 4 k + O ( k 2 2 k ) . \mu_{2^k}=\kappa4^k+O(k^2 2^k). μ 2 k = κ 4 k + O ( k 2 2 k ) . The constant is computable, with decimal expansion
κ = 0.687915685568298445216698239913 … \kappa=0.687915685568298445216698239913\ldots κ = 0.687915685568298445216698239913 …
Proof. Write c r = C r ( 1 ) c_r=C_r(1) c r = C r ( 1 ) and d k = ∂ C 2 k ( 1 ) = c 2 k − c 2 k − 1 d_k=\partial C_{2^k}(1)=c_{2^k}-c_{2^{k-1}} d k = ∂ C 2 k ( 1 ) = c 2 k − c 2 k − 1 . Lemma 19 gives d k = O ( k 2 2 k ) d_k=O(k2^{2k}) d k = O ( k 2 2 k ) . For dyadic q ≥ 2 q\ge2 q ≥ 2 , put w q = ∑ p = 2 , 4 , … , q / 2 μ p / p w_q=\sum_{p=2,4,\ldots,q/2}\mu_p/p w q = ∑ p = 2 , 4 , … , q /2 μ p / p . Evaluating (2) , (12) , and (13) at z = 1 z=1 z = 1 gives
q w q = 2 μ q − 2 c q + 2 , c 2 q = 3 q + 1 + 2 μ q − ( c q − c q − 1 ) . qw_q=2\mu_q-2c_q+2,\qquad c_{2q}=3q+1+2\mu_q-(c_q-c_{q-1}). q w q = 2 μ q − 2 c q + 2 , c 2 q = 3 q + 1 + 2 μ q − ( c q − c q − 1 ) .
The initial case q = 2 q=2 q = 2 follows from P 2 = 1 + z P_2=1+z P 2 = 1 + z and C 2 = 1 + z + z 2 C_2=1+z+z^2 C 2 = 1 + z + z 2 . With δ k = μ 2 k + 1 − 4 μ 2 k \delta_k=\mu_{2^{k+1}}-4\mu_{2^k} δ k = μ 2 k + 1 − 4 μ 2 k , these identities imply
δ 1 = 2 , δ k = δ k − 1 + 2 d k − 1 − d k ( k ≥ 2 ) . (24) \delta_1=2,\qquad\delta_k=\delta_{k-1}+2d_{k-1}-d_k\qquad(k\ge2). \tag*{(24)} δ 1 = 2 , δ k = δ k − 1 + 2 d k − 1 − d k ( k ≥ 2 ) . (24)
Telescoping gives δ k = O ( k 2 2 k ) \delta_k=O(k2^{2k}) δ k = O ( k 2 2 k ) . Therefore
κ = 1 2 + ∑ k ≥ 1 δ k 4 k + 1 \kappa=\frac{1}{2}+\sum_{k\ge1}\frac{\delta_k}{4^{k+1}} κ = 2 1 + k ≥ 1 ∑ 4 k + 1 δ k
converges absolutely, and its tail gives the stated estimate. Appendix § 11 gives an explicit error bound, proves positivity from a computed value, and certifies the displayed decimal digits. ∎
A rapidly convergent series for the density
The transfer identity also gives a series whose first N N N terms use cones of size O ( N ) O(N) O ( N ) . For j ≥ 0 j \ge0 j ≥ 0 , put
Q j = 2 ⌈ log 2 ( j + 2 ) ⌉ , ϵ j = 1 j = Q j / 2 − 1 , α j = 3 ∂ C Q j − j ( 1 ) − 1 + E j ( 1 ) + 9 ϵ j Q j 2 . Q_j = 2^{\lceil\log_2(j+2)\rceil}, \qquad\epsilon_j = 1_{j=Q_j/2-1}, \qquad\alpha_j = \frac{3\partial C_{Q_j-j}(1)-1+E_j(1)+9\epsilon_j}{Q_j^2}. Q j = 2 ⌈ l o g 2 ( j + 2 )⌉ , ϵ j = 1 j = Q j /2 − 1 , α j = Q j 2 3 ∂ C Q j − j ( 1 ) − 1 + E j ( 1 ) + 9 ϵ j .
Thus the row sums E j ( 1 ) E_j(1) E j ( 1 ) of the kernels determine the density, while their columns determine the windows in § 9 .
Theorem 25. The density has the absolutely convergent representation
κ = 1 − 2 27 ∑ j ≥ 0 α j 3 j , ∣ κ − 1 + 2 27 ∑ j = 0 N − 1 α j 3 j ∣ ≤ 4 3 N ( N ≥ 1 ) . \kappa= 1-\frac{2}{27}\sum_{j\ge0}\frac{\alpha_j}{3^j}, \qquad\left|\kappa-1+\frac{2}{27}\sum_{j=0}^{N-1}\frac{\alpha_j}{3^j}\right|\le\frac{4}{3^N}\quad(N\ge1). κ = 1 − 27 2 j ≥ 0 ∑ 3 j α j , κ − 1 + 27 2 j = 0 ∑ N − 1 3 j α j ≤ 3 N 4 ( N ≥ 1 ) . The first N N N terms use only cones of index at most 4 N 4N 4 N .
Proof. Let d k = c 2 k − c 2 k − 1 d_k=c_{2^k}-c_{2^{k-1}} d k = c 2 k − c 2 k − 1 and δ k = μ 2 k + 1 − 4 μ 2 k \delta_k=\mu_{2^{k+1}}-4\mu_{2^k} δ k = μ 2 k + 1 − 4 μ 2 k . The recurrence (24) , with d 1 = δ 1 = 2 d_1=\delta_1=2 d 1 = δ 1 = 2 , gives
( 1 − t ) Δ ( t ) = 4 t + ( 2 t − 1 ) D ( t ) , D ( t ) = ∑ k ≥ 1 d k t k , Δ ( t ) = ∑ k ≥ 1 δ k t k . (1-t)\Delta(t)=4t+(2t-1)D(t), \qquad D(t)=\sum_{k\ge1}d_kt^k,\qquad\Delta(t)=\sum_{k\ge1}\delta_kt^k. ( 1 − t ) Δ ( t ) = 4 t + ( 2 t − 1 ) D ( t ) , D ( t ) = k ≥ 1 ∑ d k t k , Δ ( t ) = k ≥ 1 ∑ δ k t k .
The estimates already proved justify evaluation at t = 1 / 4 t=1/4 t = 1/4 . Since κ = 1 / 2 + Δ ( 1 / 4 ) / 4 \kappa=1/2+\Delta(1/4)/4 κ = 1/2 + Δ ( 1/4 ) /4 , we obtain
κ = 5 − D ( 1 / 4 ) 6 = 5 6 − 1 6 ∑ k ≥ 1 c 2 k − c 2 k − 1 4 k . (25) \kappa=\frac{5-D(1/4)}{6}=\frac{5}{6}-\frac{1}{6}\sum_{k\ge1}\frac{c_{2^k}-c_{2^{k-1}}}{4^k}. \tag*{(25)} κ = 6 5 − D ( 1/4 ) = 6 5 − 6 1 k ≥ 1 ∑ 4 k c 2 k − c 2 k − 1 . (25)
For a , j ≥ 0 a,j\ge0 a , j ≥ 0 let Y ( a , j ) = c 2 a − j − c 2 a − j − 1 Y(a,j)=c_{2^a-j}-c_{2^a-j-1} Y ( a , j ) = c 2 a − j − c 2 a − j − 1 if j < 2 a j<2^a j < 2 a , and let Y ( a , j ) = 0 Y(a,j)=0 Y ( a , j ) = 0 otherwise. Evaluating (18) at z = 1 z=1 z = 1 gives
Y ( a , j ) = Y ( a − 1 , j ) + Y ( a − 1 , j + 1 ) + g j , g j = E j ( 1 ) − 1 , (26) Y(a,j)=Y(a-1,j)+Y(a-1,j+1)+g_j,\qquad g_j=E_j(1)-1, \tag*{(26)} Y ( a , j ) = Y ( a − 1 , j ) + Y ( a − 1 , j + 1 ) + g j , g j = E j ( 1 ) − 1 , (26)
whenever 2 a − 1 ≥ j + 2 2^{a-1}\ge j+2 2 a − 1 ≥ j + 2 .
For convergence, expand only while j + 1 ≤ 2 a − 2 j+1\le2^{a-2} j + 1 ≤ 2 a − 2 . In the tree starting at ( a , j ) (a,j) ( a , j ) every corner index is at most j + a j+a j + a . The estimates in Appendix § 11 give
∣ Y ( a , j ) ∣ ≤ 40 ( a + j + 1 ) 2 2 a , U j : = ∑ a ≥ 0 Y ( a , j ) 4 − a , ∣ U j ∣ ≤ 80 ( j 2 + 4 j + 6 ) . |Y(a,j)|\le40(a+j+1)2^{2a},\qquad U_j:=\sum_{a\ge0}Y(a,j)4^{-a},\qquad|U_j|\le80(j^2+4j+6). ∣ Y ( a , j ) ∣ ≤ 40 ( a + j + 1 ) 2 2 a , U j := a ≥ 0 ∑ Y ( a , j ) 4 − a , ∣ U j ∣ ≤ 80 ( j 2 + 4 j + 6 ) .
Thus these series converge absolutely.
Write Q j = 2 h Q_j=2^h Q j = 2 h and w j = c Q j − j − c Q j − j − 1 w_j=c_{Q_j-j}-c_{Q_j-j-1} w j = c Q j − j − c Q j − j − 1 . Below level h h h the only possible nonzero value is Y ( h − 1 , j ) = 1 Y(h-1,j)=1 Y ( h − 1 , j ) = 1 , and it occurs exactly when ϵ j = 1 \epsilon_j=1 ϵ j = 1 . At level h h h the value is w j w_j w j , and at every level a ≥ h + 1 a\ge h+1 a ≥ h + 1 recurrence (26) applies. Therefore, with Y j ( t ) = ∑ a ≥ 0 Y ( a , j ) t a Y_j(t)=\sum_{a\ge0}Y(a,j)t^a Y j ( t ) = ∑ a ≥ 0 Y ( a , j ) t a ,
( 1 − t ) Y j ( t ) − t Y j + 1 ( t ) = w j t h + ϵ j ( 1 − t ) t h − 1 + g j t h + 1 1 − t . (1-t)Y_j(t)-tY_{j+1}(t)=w_jt^h+\epsilon_j(1-t)t^{h-1}+\frac{g_jt^{h+1}}{1-t}. ( 1 − t ) Y j ( t ) − t Y j + 1 ( t ) = w j t h + ϵ j ( 1 − t ) t h − 1 + 1 − t g j t h + 1 .
At t = 1 / 4 t=1/4 t = 1/4 this gives
U j = 1 3 U j + 1 + 4 9 α j . U_j=\frac{1}{3}U_{j+1}+\frac{4}{9}\alpha_j. U j = 3 1 U j + 1 + 9 4 α j .
Since U j = O ( j 2 ) U_j=O(j^2) U j = O ( j 2 ) , iteration yields U 0 = ( 4 / 9 ) ∑ j ≥ 0 α j 3 − j U_0=(4/9)\sum_{j\ge0}\alpha_j3^{-j} U 0 = ( 4/9 ) ∑ j ≥ 0 α j 3 − j . Since Y ( 0 , 0 ) = 1 Y(0,0)=1 Y ( 0 , 0 ) = 1 , we have D ( 1 / 4 ) = U 0 − 1 D(1/4)=U_0-1 D ( 1/4 ) = U 0 − 1 . Substitution in (25) proves the formula.
The bounds on E j E_j E j in Appendix § 11 and 0 ≤ c r ≤ r ( r + 1 ) / 2 0\le c_r\le r(r+1)/2 0 ≤ c r ≤ r ( r + 1 ) /2 imply
∣ g j ∣ ≤ 29 ( j + 1 ) 2 ≤ 29 Q j 2 , ∣ w j ∣ Q j 2 ≤ 3 4 , ∣ α j ∣ ≤ 29 + 9 4 + 9 4 < 36. |g_j|\le29(j+1)^2\le29Q_j^2,\qquad\frac{|w_j|}{Q_j^2}\le\frac{3}{4},\qquad|\alpha_j|\le29+\frac{9}{4}+\frac{9}{4}<36. ∣ g j ∣ ≤ 29 ( j + 1 ) 2 ≤ 29 Q j 2 , Q j 2 ∣ w j ∣ ≤ 4 3 , ∣ α j ∣ ≤ 29 + 4 9 + 4 9 < 36.
The tail is at most ( 2 / 27 ) ⋅ 36 ∑ j ≥ N 3 − j = 4 / 3 N (2/27)\cdot36\sum_{j\ge N}3^{-j}=4/3^N ( 2/27 ) ⋅ 36 ∑ j ≥ N 3 − j = 4/ 3 N . For j < N j<N j < N , the kernel E j E_j E j is computed with a dyadic size m ≤ 2 max ( j , 1 ) m\le2\max(j,1) m ≤ 2 max ( j , 1 ) . Identity (11) expresses its two triangle masses through cones of index at most 2 m 2m 2 m . Also Q j < 2 ( j + 2 ) ≤ 4 N Q_j<2(j+2)\le4N Q j < 2 ( j + 2 ) ≤ 4 N , so every required cone index is at most 4 N 4N 4 N . □ \square □
The supplied program certifies 105 decimal digits from 224 terms, using cones of index at most 384, with every cone mass checked by two implementations.
Block identities
Identity (2) relates the global count to a dyadic cone.
For r ≥ 0 r \ge0 r ≥ 0 and an integer t t t , let c r ( t ) c_r(t) c r ( t ) be the coefficient of z t z^t z t in C r C_r C r and let Γ r ( t ) = ∑ i ≤ t c r ( i ) \Gamma_r(t) = \sum_{i \le t} c_r(i) Γ r ( t ) = ∑ i ≤ t c r ( i ) . Let H ( n ) = ∑ i ≤ n F ( i ) \mathcal{H}(n) = \sum_{i \le n} F(i) H ( n ) = ∑ i ≤ n F ( i ) . These quantities vanish for negative arguments. By (9) , the coefficient F ( n ) F(n) F ( n ) is the sum of the coefficients of z n − 2 m − 3 z^{n-2m-3} z n − 2 m − 3 in P l b ( m ) P_{\mathrm{lb}(m)} P lb ( m ) over the even integers m ≥ 2 m \ge2 m ≥ 2 . The integer m m m is the center of a diamond whose seed appears at round 2 m + 3 2m+3 2 m + 3 . For a dyadic integer B B B let F < B ( n ) F^{<B}(n) F < B ( n ) be the same sum restricted to m < B m < B m < B , and let H < B ( n ) = ∑ i ≤ n F < B ( i ) \mathcal{H}^{<B}(n) = \sum_{i \le n} F^{<B}(i) H < B ( n ) = ∑ i ≤ n F < B ( i ) . Then F < B ( n ) = F ( n ) F^{<B}(n) = F(n) F < B ( n ) = F ( n ) for n ≤ 2 B + 2 n \le2B+2 n ≤ 2 B + 2 . The function H < B \mathcal{H}^{<B} H < B is nondecreasing and its limit is
M B = ∑ 2 ≤ m < B m e v e n μ l b ( m ) = ∑ p = 2 , 4 , … , B / 2 B 2 p μ p . M_B = \sum_{\substack{2 \le m < B \\ m\ \mathrm{even}}} \mu_{\mathrm{lb}(m)} = \sum_{p=2,4,\ldots,B/2} \frac{B}{2p}\mu_p. M B = 2 ≤ m < B m even ∑ μ lb ( m ) = p = 2 , 4 , … , B /2 ∑ 2 p B μ p .
Lemma 26. Let N = 2 q N = 2q N = 2 q with q ≥ 2 q \ge2 q ≥ 2 dyadic. For 3 ≤ j ≤ N 3 \le j \le N 3 ≤ j ≤ N ,
F ( N + j ) = 2 F ( j ) + c q ( j − 2 ) + F < q ( N + j ) , (27) F(N+j) = 2F(j) + c_q(j-2) + F^{<q}(N+j), \tag*{(27)} F ( N + j ) = 2 F ( j ) + c q ( j − 2 ) + F < q ( N + j ) , (27)
and F ( N + j ) = F < q ( N + j ) F(N+j) = F^{<q}(N+j) F ( N + j ) = F < q ( N + j ) for j = 1 j=1 j = 1 and j = 2 j=2 j = 2 . Consequently, for 0 ≤ J ≤ N 0 \le J \le N 0 ≤ J ≤ N ,
H ( N + J ) = H < q ( N + J ) + 2 H ( J ) + max ( Γ q ( J − 2 ) − 1 , 0 ) . (28) \mathcal{H}(N+J) = \mathcal{H}^{<q}(N+J) + 2\mathcal{H}(J) + \max(\Gamma_q(J-2)-1,0). \tag*{(28)} H ( N + J ) = H < q ( N + J ) + 2 H ( J ) + max ( Γ q ( J − 2 ) − 1 , 0 ) . (28)
Proof. Let 1 ≤ j ≤ N 1 \le j \le N 1 ≤ j ≤ N . In the sum that defines F ( N + j ) F(N+j) F ( N + j ) , a center m ≥ 2 q m \ge2q m ≥ 2 q has 2 m + 3 > N + j 2m+3 > N+j 2 m + 3 > N + j and does not contribute. The centers m < q m < q m < q contribute F < q ( N + j ) F^{<q}(N+j) F < q ( N + j ) . A center with q < m < 2 q q < m < 2q q < m < 2 q is m = q + m ′ m=q+m' m = q + m ′ with 0 < m ′ < q 0 < m' < q 0 < m ′ < q . Then lb ( m ) = lb ( m ′ ) \operatorname{lb}(m) = \operatorname{lb}(m') lb ( m ) = lb ( m ′ ) and the exponent is j − 2 m ′ − 3 j-2m'-3 j − 2 m ′ − 3 . These centers therefore contribute F < q ( j ) F^{<q}(j) F < q ( j ) , which equals F ( j ) F(j) F ( j ) because j ≤ 2 q + 2 j \le2q+2 j ≤ 2 q + 2 . The center m = q m=q m = q contributes the coefficient of z j − 3 z^{j-3} z j − 3 in P q P_q P q . By Definition 6 this coefficient is zero for j ≤ 2 j \le2 j ≤ 2 . For j ≥ 3 j \ge3 j ≥ 3 it is the sum of c q ( j − 2 ) c_q(j-2) c q ( j − 2 ) and of the coefficient of z j − 3 z^{j-3} z j − 3 in S q , 0 S_{q,0} S q , 0 . By (3) the latter is F < q ( j ) = F ( j ) F^{<q}(j) = F(j) F < q ( j ) = F ( j ) . This proves (27) . Since F ( 1 ) = F ( 2 ) = 0 F(1)=F(2)=0 F ( 1 ) = F ( 2 ) = 0 and H ( N ) = H < q ( N ) \mathcal{H}(N)=\mathcal{H}^{<q}(N) H ( N ) = H < q ( N ) , summation over 1 ≤ j ≤ J 1 \le j \le J 1 ≤ j ≤ J gives (28) . Its last term is ∑ j = 3 J c q ( j − 2 ) = Γ q ( J − 2 ) − c q ( 0 ) \sum_{j=3}^{J} c_q(j-2) = \Gamma_q(J-2)-c_q(0) ∑ j = 3 J c q ( j − 2 ) = Γ q ( J − 2 ) − c q ( 0 ) when J ≥ 2 J \ge2 J ≥ 2 .
Lemma 27. Let M ≥ 1 M \ge1 M ≥ 1 be dyadic and N = 2 M N=2M N = 2 M . For every t ≥ 0 t \ge0 t ≥ 0 ,
c N ( t ) = ε N ( t ) + 2 F < M ( t + 1 ) + c M ( t − N ) + c M − 1 ( t − N − 1 ) − 1 1 ≤ t − N ≤ M − 1 , (29) c_N(t) = \varepsilon_N(t) + 2F^{<M}(t+1) + c_M(t-N) + c_{M-1}(t-N-1) - \mathbf{1}_{1 \le t-N \le M-1}, \tag*{(29)} c N ( t ) = ε N ( t ) + 2 F < M ( t + 1 ) + c M ( t − N ) + c M − 1 ( t − N − 1 ) − 1 1 ≤ t − N ≤ M − 1 , (29)
where ε N ( t ) \varepsilon_N(t) ε N ( t ) equals 1 1 1 for t ≤ 1 t \le1 t ≤ 1 , equals 2 2 2 for 2 ≤ t ≤ N − 1 2 \le t \le N-1 2 ≤ t ≤ N − 1 and equals 0 0 0 for t ≥ N t \ge N t ≥ N .
Proof. This is (13) with (12) and the definition of H M H_M H M . By (3) the coefficient of z t z^t z t in S M , 2 S_{M,2} S M , 2 is F < M ( t + 1 ) F^{<M}(t+1) F < M ( t + 1 ) .
The limit profile
The block identity and the reduction of a dyadic cone have continuous counterparts. Let X \mathcal{X} X be the set of pairs ( f , g ) (f,g) ( f , g ) of continuous functions on [ 1 , 2 ] [1,2] [ 1 , 2 ] with
f ( 1 ) = 1 8 , f ( 2 ) = 1 2 , g ( 1 ) = 1 4 , g ( 2 ) = 1 2 . f(1)=\frac{1}{8}, \qquad f(2)=\frac{1}{2}, \qquad g(1)=\frac{1}{4}, \qquad g(2)=\frac{1}{2}. f ( 1 ) = 8 1 , f ( 2 ) = 2 1 , g ( 1 ) = 4 1 , g ( 2 ) = 2 1 .
For such a pair, extend f f f to [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) by f ( 2 u ) = 4 f ( u ) f(2u)=4f(u) f ( 2 u ) = 4 f ( u ) and f ( 0 ) = 0 f(0)=0 f ( 0 ) = 0 , and extend g g g to [ 0 , 1 ] [0,1] [ 0 , 1 ] by g ( y ) = 2 f ( y ) g(y)=2f(y) g ( y ) = 2 f ( y ) . Both extensions are continuous. Define T ( f , g ) = ( f ∗ , g ∗ ) T(f,g)=(f^*,g^*) T ( f , g ) = ( f ∗ , g ∗ ) by
f ∗ ( 1 + x ) = 1 8 + 2 f ( x ) + 1 4 g ( 2 x ) , g ∗ ( 1 + x ) = 1 4 + 1 2 g ( 2 x ) ( 0 ≤ x ≤ 1 ) . (30) f^*(1+x)=\frac{1}{8}+2f(x)+\frac{1}{4}g(2x), \qquad g^*(1+x)=\frac{1}{4}+\frac{1}{2}g(2x) \qquad(0 \le x \le1). \tag*{(30)} f ∗ ( 1 + x ) = 8 1 + 2 f ( x ) + 4 1 g ( 2 x ) , g ∗ ( 1 + x ) = 4 1 + 2 1 g ( 2 x ) ( 0 ≤ x ≤ 1 ) . (30)
The four endpoint values are preserved, so T T T maps X \mathcal{X} X to itself.
Lemma 28. The operator T T T has a unique fixed point ( S , C ) (S,C) ( S , C ) in X \mathcal{X} X . The functions S S S and C C C are nondecreasing. With S ( u ) = C ( u ) = 0 S(u)=C(u)=0 S ( u ) = C ( u ) = 0 for u ≤ 0 u \le0 u ≤ 0 , they satisfy
C ( y ) = S ( 2 + y ) − 2 S ( y ) − 1 2 ( 0 ≤ y ≤ 2 ) , S ( u ) = 1 8 + S ( 2 u − 2 ) − S ( 2 u − 3 ) ( 1 ≤ u ≤ 2 ) . (31) C(y)=S(2+y)-2S(y)-\frac{1}{2} \qquad(0 \le y \le2), \qquad S(u)=\frac{1}{8}+S(2u-2)-S(2u-3) \qquad(1 \le u \le2). \tag*{(31)} C ( y ) = S ( 2 + y ) − 2 S ( y ) − 2 1 ( 0 ≤ y ≤ 2 ) , S ( u ) = 8 1 + S ( 2 u − 2 ) − S ( 2 u − 3 ) ( 1 ≤ u ≤ 2 ) . (31)
Proof. Let ( f 1 , g 1 ) (f_1,g_1) ( f 1 , g 1 ) and ( f 2 , g 2 ) (f_2,g_2) ( f 2 , g 2 ) be in X \mathcal{X} X and let δ \delta δ be the larger of the uniform distances between f 1 f_1 f 1 and f 2 f_2 f 2 and between g 1 g_1 g 1 and g 2 g_2 g 2 on [ 1 , 2 ] [1,2] [ 1 , 2 ] . By scaling, the extensions of f 1 f_1 f 1 and f 2 f_2 f 2 differ by at most δ / 4 \delta/4 δ /4 on [ 0 , 1 ] [0,1] [ 0 , 1 ] , and the extensions of g 1 g_1 g 1 and g 2 g_2 g 2 differ by at most δ \delta δ on [ 0 , 2 ] [0,2] [ 0 , 2 ] . By (30) the images differ by at most 3 δ / 4 3\delta/4 3 δ /4 . Thus T \mathcal{T} T is a contraction for the uniform distance, and it has a unique fixed point ( S , C ) (S,C) ( S , C ) . The pairs of nondecreasing functions form a closed subset of X \mathcal{X} X which is preserved by T \mathcal{T} T , because the extensions of nondecreasing functions are nondecreasing. This subset contains the pair of affine functions with the prescribed endpoint values, so it contains the fixed point.
The first equation of (30) at x = y / 2 x=y/2 x = y /2 , multiplied by 4 4 4 , is the first identity of (31) . Let 0 ≤ w ≤ 1 0\leq w\leq1 0 ≤ w ≤ 1 . Substituting this identity at 1 + w 1+w 1 + w and at 2 w 2w 2 w in C ( 1 + w ) = 1 4 + 1 2 C ( 2 w ) C(1+w)=\frac{1}{4}+\frac{1}{2}C(2w) C ( 1 + w ) = 4 1 + 2 1 C ( 2 w ) and using the scaling of S S S gives S ( 3 + w ) = 4 S ( 1 + w ) − 4 S ( w ) + 1 2 S(3+w)=4S(1+w)-4S(w)+\frac{1}{2} S ( 3 + w ) = 4 S ( 1 + w ) − 4 S ( w ) + 2 1 . With u = ( 3 + w ) / 2 u=(3+w)/2 u = ( 3 + w ) /2 this is the second identity of (31) for 3 / 2 ≤ u ≤ 2 3/2\leq u\leq2 3/2 ≤ u ≤ 2 . For 1 ≤ u ≤ 3 / 2 1\leq u\leq3/2 1 ≤ u ≤ 3/2 the second identity reads S ( u ) = 1 8 + 4 S ( u − 1 ) S(u)=\frac{1}{8}+4S(u-1) S ( u ) = 8 1 + 4 S ( u − 1 ) , which is the first equation of (30) with g ( 2 x ) = 2 S ( 2 x ) = 8 S ( x ) g(2x)=2S(2x)=8S(x) g ( 2 x ) = 2 S ( 2 x ) = 8 S ( x ) .
The second identity of (31) determines the profile on each dyadic piece. Put u = 1 + x u=1+x u = 1 + x . For 0 ≤ x ≤ 1 / 2 0\leq x\leq1/2 0 ≤ x ≤ 1/2 it gives S ( 1 + x ) = 1 8 + 4 S ( x ) S(1+x)=\frac{1}{8}+4S(x) S ( 1 + x ) = 8 1 + 4 S ( x ) . At x = 1 / 3 x=1/3 x = 1/3 the scaling relation turns this into S ( 4 / 3 ) = 1 8 + 1 4 S ( 4 / 3 ) S(4/3)=\frac{1}{8}+\frac{1}{4}S(4/3) S ( 4/3 ) = 8 1 + 4 1 S ( 4/3 ) , hence
S ( 4 / 3 ) = 1 6 . (32) S(4/3)=\frac{1}{6}. \tag*{(32)} S ( 4/3 ) = 6 1 . (32)
A function h h h is Hölder continuous of exponent 0 < β ≤ 1 0<\beta\leq1 0 < β ≤ 1 on an interval if ∣ h ( u ) − h ( v ) ∣ ≤ K ∣ u − v ∣ β |h(u)-h(v)|\leq K|u-v|^\beta ∣ h ( u ) − h ( v ) ∣ ≤ K ∣ u − v ∣ β for all u , v u,v u , v in that interval and some constant K K K .
Lemma 29. Let β = log 2 ( 4 / 3 ) = 2 − log 2 3 \beta=\log_2(4/3)=2-\log_2 3 β = log 2 ( 4/3 ) = 2 − log 2 3 . The functions S S S and C C C are Hölder continuous of exponent β \beta β on [ 0 , 2 ] [0,2] [ 0 , 2 ] .
Proof. Let ( f 0 , g 0 ) (f_0,g_0) ( f 0 , g 0 ) be the pair of affine functions of X \mathcal{X} X and let ( f n , g n ) = T n ( f 0 , g 0 ) (f_n,g_n)=\mathcal{T}^n(f_0,g_0) ( f n , g n ) = T n ( f 0 , g 0 ) . On [ 1 , 2 ] [1,2] [ 1 , 2 ] the functions f 0 f_0 f 0 and S S S take their values in [ 1 / 8 , 1 / 2 ] [1/8,1/2] [ 1/8 , 1/2 ] , and g 0 g_0 g 0 and C C C in [ 1 / 4 , 1 / 2 ] [1/4,1/2] [ 1/4 , 1/2 ] . The contraction therefore gives ∣ f n − S ∣ ≤ 3 8 ( 3 4 ) n |f_n-S|\leq\frac{3}{8}\left(\frac{3}{4}\right)^n ∣ f n − S ∣ ≤ 8 3 ( 4 3 ) n and ∣ g n − C ∣ ≤ 3 8 ( 3 4 ) n |g_n-C|\leq\frac{3}{8}\left(\frac{3}{4}\right)^n ∣ g n − C ∣ ≤ 8 3 ( 4 3 ) n on [ 1 , 2 ] [1,2] [ 1 , 2 ] . Let Λ n \Lambda_n Λ n be the larger of the Lipschitz constants of f n f_n f n and g n g_n g n on [ 1 , 2 ] [1,2] [ 1 , 2 ] . The extension of f n f_n f n to [ 0 , 1 ] [0,1] [ 0 , 1 ] has Lipschitz constant at most Λ n / 2 \Lambda_n/2 Λ n /2 , and the extension of g n g_n g n to [ 0 , 2 ] [0,2] [ 0 , 2 ] has Lipschitz constant at most Λ n \Lambda_n Λ n . By (30) , Λ n + 1 ≤ 3 2 Λ n \Lambda_{n+1}\leq\frac{3}{2}\Lambda_n Λ n + 1 ≤ 2 3 Λ n , and Λ 0 = 3 8 \Lambda_0=\frac{3}{8} Λ 0 = 8 3 . Let u u u and v v v be in [ 1 , 2 ] [1,2] [ 1 , 2 ] with u ≠ v u\ne v u = v , and choose n ≥ 0 n\geq0 n ≥ 0 with 2 − n − 1 < ∣ u − v ∣ ≤ 2 − n 2^{-n-1}<|u-v|\leq2^{-n} 2 − n − 1 < ∣ u − v ∣ ≤ 2 − n . Then
∣ S ( u ) − S ( v ) ∣ ≤ 3 4 ( 3 4 ) n + 3 4 ( 3 2 ) n 2 − n = 9 8 ( 3 4 ) n ≤ 3 2 ∣ u − v ∣ β , |S(u)-S(v)|\leq\frac{3}{4}\left(\frac{3}{4}\right)^n+\frac{3}{4}\left(\frac{3}{2}\right)^n2^{-n}=\frac{9}{8}\left(\frac{3}{4}\right)^n\leq\frac{3}{2}|u-v|^\beta, ∣ S ( u ) − S ( v ) ∣ ≤ 4 3 ( 4 3 ) n + 4 3 ( 2 3 ) n 2 − n = 8 9 ( 4 3 ) n ≤ 2 3 ∣ u − v ∣ β ,
because ( 3 4 ) n = 2 − n β < ( 2 ∣ u − v ∣ ) β \left(\frac{3}{4}\right)^n=2^{-n\beta}<(2|u-v|)^\beta ( 4 3 ) n = 2 − n β < ( 2∣ u − v ∣ ) β . The same bound holds for C C C on [ 1 , 2 ] [1,2] [ 1 , 2 ] . By scaling it holds for S S S on each interval [ 2 − i , 2 1 − i ] [2^{-i},2^{1-i}] [ 2 − i , 2 1 − i ] with i ≥ 0 i\geq0 i ≥ 0 . Two points x < y x<y x < y of [ 0 , 2 ] [0,2] [ 0 , 2 ] with y ≤ 2 x y\leq2x y ≤ 2 x lie in the same interval of this family or in two consecutive ones, which gives S ( y ) − S ( x ) ≤ 3 ( y − x ) β S(y)-S(x)\leq3(y-x)^\beta S ( y ) − S ( x ) ≤ 3 ( y − x ) β . If y > 2 x y>2x y > 2 x then S ( y ) − S ( x ) ≤ S ( y ) = O ( y 2 ) = O ( ( y − x ) 2 ) S(y)-S(x)\leq S(y)=O(y^2)=O((y-x)^2) S ( y ) − S ( x ) ≤ S ( y ) = O ( y 2 ) = O (( y − x ) 2 ) . Hence S S S is Hölder continuous of exponent β \beta β on [ 0 , 2 ] [0,2] [ 0 , 2 ] , and so is C C C , which equals 2 S 2S 2 S on [ 0 , 1 ] [0,1] [ 0 , 1 ] .
Convergence to the profile
Theorem 30. There is a constant K K K such that, for every k ≥ 1 k\geq1 k ≥ 1 ,
max 0 ≤ n ≤ 2 k + 1 ∣ H ( n ) 4 k − k S ( n 2 k ) ∣ ≤ K k 2 ( 3 4 ) k , \max_{0\leq n\leq2^{k+1}}\left|\frac{\mathcal{H}(n)}{4^k}-kS\left(\frac{n}{2^k}\right)\right|\leq Kk^2\left(\frac{3}{4}\right)^k, 0 ≤ n ≤ 2 k + 1 max 4 k H ( n ) − k S ( 2 k n ) ≤ K k 2 ( 4 3 ) k , max 0 ≤ t ≤ 2 k + 1 ∣ Γ 2 k ( t ) 4 k − k C ( t 2 k ) ∣ ≤ K k 2 ( 3 4 ) k . (33) \max_{0\leq t\leq2^{k+1}}\left|\frac{\Gamma_{2^k}(t)}{4^k}-kC\left(\frac{t}{2^k}\right)\right|\leq Kk^2\left(\frac{3}{4}\right)^k. \tag*{(33)} 0 ≤ t ≤ 2 k + 1 max 4 k Γ 2 k ( t ) − k C ( 2 k t ) ≤ K k 2 ( 4 3 ) k . (33)
Equivalently, the two cumulative counts differ from k 4 k S ( n / 2 k ) k4^kS(n/2^k) k 4 k S ( n / 2 k ) and k 4 k C ( t / 2 k ) k4^kC(t/2^k) k 4 k C ( t / 2 k ) by at most K k 2 3 k Kk^2 3^k K k 2 3 k .
Proof. Let e k e_k e k and f k f_k f k be the two maxima in (33) . Let ω \omega ω be a common modulus of continuity of k S kS k S and k C kC k C on [ 0 , 2 ] [0,2] [ 0 , 2 ] . Fix k k k , put N = 2 k N=2^k N = 2 k , q = N / 2 q=N/2 q = N /2 and τ = τ k \tau=\tau_k τ = τ k , and assume τ + 3 ≤ q \tau+3\leq q τ + 3 ≤ q . Put θ k = ∣ M q / N 2 − k / 8 ∣ \theta_k=|\mathcal{M}_q/N^2-k/8| θ k = ∣ M q / N 2 − k /8∣ . By Theorem 24 and the definition of M q \mathcal{M}_q M q we have θ k = O ( k 3 / 2 k ) \theta_k=O(k^3/2^k) θ k = O ( k 3 / 2 k ) . We write η k \eta_k η k for quantities that are bounded by a fixed multiple of θ k + ω ( ( τ + 4 ) / N ) + ( τ + 2 ) 2 / N 2 + k 2 / 2 k \theta_k+\omega((\tau+4)/N)+(\tau+2)^2/N^2+k^2/2^k θ k + ω (( τ + 4 ) / N ) + ( τ + 2 ) 2 / N 2 + k 2 / 2 k . By Lemma 29 we have ω ( h ) = O ( h β ) \omega(h)=O(h^\beta) ω ( h ) = O ( h β ) , and 2 − β k = ( 3 / 4 ) k 2^{-\beta k}=(3/4)^k 2 − β k = ( 3/4 ) k . Since τ = O ( k 2 ) \tau=O(k^2) τ = O ( k 2 ) , this gives η k = O ( k 2 β ( 3 / 4 ) k ) \eta_k=O(k^{2\beta}(3/4)^k) η k = O ( k 2 β ( 3/4 ) k ) . By Lemma 21 , a diamond with center m < q m < q m < q and size p = lb ( m ) p = \operatorname{lb}(m) p = lb ( m ) is complete at round 2 m + 2 p + τ ≤ N + τ 2m + 2p + \tau\le N + \tau 2 m + 2 p + τ ≤ N + τ . Hence H < q ( n ) = M q \mathcal{H}^{<q}(n) = \mathcal{M}_q H < q ( n ) = M q for n ≥ N + τ n \ge N + \tau n ≥ N + τ . For n ≤ N + 2 n \le N + 2 n ≤ N + 2 we have H < q ( n ) = H ( n ) \mathcal{H}^{<q}(n) = \mathcal{H}(n) H < q ( n ) = H ( n ) , and H < q ≤ M q \mathcal{H}^{<q} \le\mathcal{M}_q H < q ≤ M q everywhere. We also use the uniform crude bounds H ( n ) = O ( ( n + 2 ) 2 ) \mathcal{H}(n) = O((n + 2)^2) H ( n ) = O (( n + 2 ) 2 ) and Γ r ( t ) = O ( ( t + 2 ) 2 ) \Gamma_r(t) = O((t + 2)^2) Γ r ( t ) = O (( t + 2 ) 2 ) . Every vertex born by time t t t lies in a graph ball with O ( ( t + 2 ) 2 ) O((t + 2)^2) O (( t + 2 ) 2 ) vertices, independently of the cone size. The same bound holds for a ( n ) a(n) a ( n ) , and (19) gives 12 H ( n − 1 ) ≤ a ( n ) 12\mathcal{H}(n - 1) \le a(n) 12 H ( n − 1 ) ≤ a ( n ) for n ≥ 4 n \ge4 n ≥ 4 . The remaining indices are checked directly.
For n ≤ N n \le N n ≤ N the scaling of S \mathcal{S} S shows that the difference in (33) is one quarter of the corresponding difference at level k − 1 k - 1 k − 1 . It is at most e k − 1 / 4 e_{k-1}/4 e k − 1 /4 . Let n = N + J n = N + J n = N + J with τ ≤ J ≤ N \tau\le J \le N τ ≤ J ≤ N . By (28) , H ( n ) = M q + 2 H ( J ) + Γ q ( J − 2 ) − ϵ \mathcal{H}(n) = \mathcal{M}_q + 2\mathcal{H}(J) + \Gamma_q(J - 2) - \epsilon H ( n ) = M q + 2 H ( J ) + Γ q ( J − 2 ) − ϵ with ϵ ∈ { 0 , 1 } \epsilon\in\{0,1\} ϵ ∈ { 0 , 1 } . By (30) at the fixed point, κ S ( 1 + J / N ) = κ / 8 + 2 κ S ( J / N ) + 1 4 κ C ( J / q ) \kappa\mathcal{S}(1 + J/N) = \kappa/8 + 2\kappa\mathcal{S}(J/N) + \frac{1}{4}\kappa\mathcal{C}(J/q) κ S ( 1 + J / N ) = κ /8 + 2 κ S ( J / N ) + 4 1 κ C ( J / q ) . Subtracting and dividing by N 2 N^2 N 2 , the term with H ( J ) \mathcal{H}(J) H ( J ) contributes at most 2 e k − 1 / 4 2e_{k-1}/4 2 e k − 1 /4 , the term with Γ q \Gamma_q Γ q contributes at most 1 4 ( f k − 1 + ω ( 2 / q ) ) \frac{1}{4}(f_{k-1} + \omega(2/q)) 4 1 ( f k − 1 + ω ( 2/ q )) , and the constants contribute at most θ k + 1 / N 2 \theta_k + 1/N^2 θ k + 1/ N 2 . The difference is therefore at most 1 2 e k − 1 + 1 4 f k − 1 + η k \frac{1}{2}e_{k-1} + \frac{1}{4}f_{k-1} + \eta_k 2 1 e k − 1 + 4 1 f k − 1 + η k . Let n = N + J n = N + J n = N + J with 0 ≤ J < τ 0 \le J < \tau 0 ≤ J < τ . Then H ( N ) ≤ H ( n ) ≤ M q + O ( ( τ + 2 ) 2 ) \mathcal{H}(N) \le\mathcal{H}(n) \le\mathcal{M}_q + O((\tau+ 2)^2) H ( N ) ≤ H ( n ) ≤ M q + O (( τ + 2 ) 2 ) by (28) and the crude bounds, while κ / 8 ≤ κ S ( n / N ) ≤ κ / 8 + ω ( τ / N ) \kappa/8 \le\kappa\mathcal{S}(n/N) \le\kappa/8 + \omega(\tau/N) κ /8 ≤ κ S ( n / N ) ≤ κ /8 + ω ( τ / N ) . Since H ( N ) / N 2 ≥ κ / 8 − e k − 1 / 4 \mathcal{H}(N)/N^2 \ge\kappa/8 - e_{k-1}/4 H ( N ) / N 2 ≥ κ /8 − e k − 1 /4 , the difference is at most 1 4 e k − 1 + η k \frac{1}{4}e_{k-1} + \eta_k 4 1 e k − 1 + η k . Altogether
e k ≤ 1 2 e k − 1 + 1 4 f k − 1 + η k . e_k \le\frac{1}{2}e_{k-1} + \frac{1}{4}f_{k-1} + \eta_k. e k ≤ 2 1 e k − 1 + 4 1 f k − 1 + η k .
For the second error, put M = q M = q M = q , so that N = 2 M N = 2M N = 2 M . Summing (29) gives, for t ≥ 0 t \ge0 t ≥ 0 ,
Γ N ( t ) = E ( t ) + 2 H < M ( t + 1 ) + Γ M ( t − N ) + Γ M − 1 ( t − N − 1 ) , \Gamma_N(t) = E(t) + 2\mathcal{H}^{<M}(t + 1) + \Gamma_M(t - N) + \Gamma_{M-1}(t - N - 1), Γ N ( t ) = E ( t ) + 2 H < M ( t + 1 ) + Γ M ( t − N ) + Γ M − 1 ( t − N − 1 ) ,
with ∣ E ( t ) ∣ ≤ 3 N |E(t)| \le3N ∣ E ( t ) ∣ ≤ 3 N . For t ≤ N − 1 t \le N - 1 t ≤ N − 1 the last two terms vanish and H < M ( t + 1 ) = H ( t + 1 ) \mathcal{H}^{<M}(t + 1) = \mathcal{H}(t + 1) H < M ( t + 1 ) = H ( t + 1 ) with t + 1 ≤ N t + 1 \le N t + 1 ≤ N . Since C ( y ) = 2 S ( y ) \mathcal{C}(y) = 2\mathcal{S}(y) C ( y ) = 2 S ( y ) on [ 0 , 1 ] [0,1] [ 0 , 1 ] , the difference in (33) is at most 2 e k − 1 / 4 + 2 ω ( 1 / N ) + 3 / N 2e_{k-1}/4 + 2\omega(1/N) + 3/N 2 e k − 1 /4 + 2 ω ( 1/ N ) + 3/ N . For N + τ ≤ t ≤ 2 N N + \tau\le t \le2N N + τ ≤ t ≤ 2 N we have H < M ( t + 1 ) = M M \mathcal{H}^{<M}(t + 1) = \mathcal{M}_M H < M ( t + 1 ) = M M , and Lemma 19 replaces Γ M − 1 ( t − N − 1 ) \Gamma_{M-1}(t - N - 1) Γ M − 1 ( t − N − 1 ) by Γ M ( t − N − 1 ) \Gamma_M(t - N - 1) Γ M ( t − N − 1 ) with an error O ( k 2 2 k ) O(k2^{2k}) O ( k 2 2 k ) . Since κ C ( t / N ) = κ / 4 + 1 2 κ C ( ( t − N ) / M ) \kappa\mathcal{C}(t/N) = \kappa/4 + \frac{1}{2}\kappa\mathcal{C}((t - N)/M) κ C ( t / N ) = κ /4 + 2 1 κ C (( t − N ) / M ) and 2 M M / N 2 2\mathcal{M}_M/N^2 2 M M / N 2 differs from κ / 4 \kappa/4 κ /4 by 2 θ k 2\theta_k 2 θ k , the difference is at most 1 4 ( 2 f k − 1 + ω ( 1 / M ) ) + η k \frac{1}{4}(2f_{k-1} + \omega(1/M)) + \eta_k 4 1 ( 2 f k − 1 + ω ( 1/ M )) + η k . For N ≤ t < N + τ N \le t < N + \tau N ≤ t < N + τ , monotonicity gives Γ N ( N − 1 ) ≤ Γ N ( t ) ≤ 3 N + 2 M M + O ( ( τ + 2 ) 2 ) \Gamma_N(N - 1) \le\Gamma_N(t) \le3N + 2\mathcal{M}_M + O((\tau+ 2)^2) Γ N ( N − 1 ) ≤ Γ N ( t ) ≤ 3 N + 2 M M + O (( τ + 2 ) 2 ) , while κ C ( t / N ) \kappa\mathcal{C}(t/N) κ C ( t / N ) lies between κ / 4 \kappa/4 κ /4 and κ / 4 + ω ( τ / N ) \kappa/4 + \omega(\tau/N) κ /4 + ω ( τ / N ) . The difference is at most 1 2 e k − 1 + η k \frac{1}{2}e_{k-1} + \eta_k 2 1 e k − 1 + η k . Altogether
f k ≤ max ( 1 2 e k − 1 , 1 2 f k − 1 ) + η k . f_k \le\max\left(\frac{1}{2}e_{k-1},\frac{1}{2}f_{k-1}\right) + \eta_k. f k ≤ max ( 2 1 e k − 1 , 2 1 f k − 1 ) + η k .
Let v k = max ( e k , f k ) v_k = \max(e_k,f_k) v k = max ( e k , f k ) . The two inequalities give v k ≤ 3 4 v k − 1 + η k v_k \le\frac{3}{4}v_{k-1} + \eta_k v k ≤ 4 3 v k − 1 + η k for all large k k k . Multiplying by ( 4 3 ) k (\frac{4}{3})^k ( 3 4 ) k and summing, we obtain v k = O ( k 1 + 2 β ( 3 4 ) k ) v_k = O(k^{1+2\beta}(\frac{3}{4})^k) v k = O ( k 1 + 2 β ( 4 3 ) k ) , and 1 + 2 β < 2 1 + 2\beta< 2 1 + 2 β < 2 .
The envelope and the optimal constants
Theorem 31. For 1 ≤ u ≤ 2 1 \le u \le2 1 ≤ u ≤ 2 ,
3 u 2 32 ≤ S ( u ) ≤ u 2 8 . (34) \frac{3u^2}{32} \le\mathcal{S}(u) \le\frac{u^2}{8}. \tag*{(34)} 32 3 u 2 ≤ S ( u ) ≤ 8 u 2 . (34) Equality holds on the left only at u = 4 / 3 u = 4/3 u = 4/3 , and on the right only at u = 1 u = 1 u = 1 and u = 2 u = 2 u = 2 .
Proof. Let K \mathcal{K} K be the set of pairs ( f , g ) (f,g) ( f , g ) in X \mathcal{X} X such that, on [ 1 , 2 ] [1,2] [ 1 , 2 ] ,
3 u 2 32 ≤ f ( u ) ≤ u 2 8 , 1 4 ≤ g ( y ) ≤ 1 2 − ( 2 − y ) 2 8 . \frac{3u^2}{32} \le f(u) \le\frac{u^2}{8}, \qquad\frac{1}{4} \le g(y) \le\frac{1}{2} - \frac{(2-y)^2}{8}. 32 3 u 2 ≤ f ( u ) ≤ 8 u 2 , 4 1 ≤ g ( y ) ≤ 2 1 − 8 ( 2 − y ) 2 .
It is closed and it contains the pair f ( u ) = u 2 / 8 f(u) = u^2/8 f ( u ) = u 2 /8 , g ( y ) = y / 4 g(y) = y/4 g ( y ) = y /4 . We show that T \mathcal{T} T preserves K \mathcal{K} K . Let ( f , g ) ∈ K (f,g) \in\mathcal{K} ( f , g ) ∈ K and ( f ∗ , g ∗ ) = T ( f , g ) (f^*,g^*) = \mathcal{T}(f,g) ( f ∗ , g ∗ ) = T ( f , g ) . By scaling, the extension of f f f satisfies the same two bounds on [ 0 , 1 ] [0,1] [ 0 , 1 ] , and the extension of g g g satisfies 0 ≤ g ( y ) ≤ y 2 / 4 0 \le g(y) \le y^2/4 0 ≤ g ( y ) ≤ y 2 /4 on [ 0 , 1 ] [0,1] [ 0 , 1 ] . For 0 ≤ x ≤ 1 / 2 0 \le x \le1/2 0 ≤ x ≤ 1/2 we have g ( 2 x ) = 8 f ( x ) g(2x) = 8f(x) g ( 2 x ) = 8 f ( x ) , and (30) gives
f ∗ ( 1 + x ) − 3 ( 1 + x ) 2 32 = 4 ( f ( x ) − 3 x 2 32 ) + ( 3 x − 1 ) 2 32 , f^*(1+x) - \frac{3(1+x)^2}{32} = 4\left(f(x) - \frac{3x^2}{32}\right) + \frac{(3x-1)^2}{32}, f ∗ ( 1 + x ) − 32 3 ( 1 + x ) 2 = 4 ( f ( x ) − 32 3 x 2 ) + 32 ( 3 x − 1 ) 2 ,
( 1 + x ) 2 8 − f ∗ ( 1 + x ) = 4 ( x 2 8 − f ( x ) ) + x ( 2 − 3 x ) 8 . (35) \frac{(1+x)^2}{8} - f^*(1+x) = 4\left(\frac{x^2}{8} - f(x)\right) + \frac{x(2-3x)}{8}. \tag*{(35)} 8 ( 1 + x ) 2 − f ∗ ( 1 + x ) = 4 ( 8 x 2 − f ( x ) ) + 8 x ( 2 − 3 x ) . (35)
@page 23/33 starts_mid=1 ends_mid=1 By Lemma 21 , a diamond with center m < q m < q m < q and size p = lb ( m ) p = \operatorname{lb}(m) p = lb ( m ) is complete at round 2 m + 2 p + τ ≤ N + τ 2m + 2p + \tau\le N + \tau 2 m + 2 p + τ ≤ N + τ . Hence H < q ( n ) = M q \mathcal{H}^{<q}(n) = \mathcal{M}_q H < q ( n ) = M q for n ≥ N + τ n \ge N + \tau n ≥ N + τ . For n ≤ N + 2 n \le N + 2 n ≤ N + 2 we have H < q ( n ) = H ( n ) \mathcal{H}^{<q}(n) = \mathcal{H}(n) H < q ( n ) = H ( n ) , and H < q ≤ M q \mathcal{H}^{<q} \le\mathcal{M}_q H < q ≤ M q everywhere. We also use the uniform crude bounds H ( n ) = O ( ( n + 2 ) 2 ) \mathcal{H}(n) = O((n + 2)^2) H ( n ) = O (( n + 2 ) 2 ) and Γ r ( t ) = O ( ( t + 2 ) 2 ) \Gamma_r(t) = O((t + 2)^2) Γ r ( t ) = O (( t + 2 ) 2 ) . Every vertex born by time t t t lies in a graph ball with O ( ( t + 2 ) 2 ) O((t + 2)^2) O (( t + 2 ) 2 ) vertices, independently of the cone size. The same bound holds for a ( n ) a(n) a ( n ) , and (19) gives 12 H ( n − 1 ) ≤ a ( n ) 12\mathcal{H}(n - 1) \le a(n) 12 H ( n − 1 ) ≤ a ( n ) for n ≥ 4 n \ge4 n ≥ 4 . The remaining indices are checked directly.
For n ≤ N n \le N n ≤ N the scaling of S \mathcal{S} S shows that the difference in (33) is one quarter of the corresponding difference at level k − 1 k - 1 k − 1 . It is at most e k − 1 / 4 e_{k-1}/4 e k − 1 /4 . Let n = N + J n = N + J n = N + J with τ ≤ J ≤ N \tau\le J \le N τ ≤ J ≤ N . By (28) , H ( n ) = M q + 2 H ( J ) + Γ q ( J − 2 ) − ϵ \mathcal{H}(n) = \mathcal{M}_q + 2\mathcal{H}(J) + \Gamma_q(J - 2) - \epsilon H ( n ) = M q + 2 H ( J ) + Γ q ( J − 2 ) − ϵ with ϵ ∈ { 0 , 1 } \epsilon\in\{0,1\} ϵ ∈ { 0 , 1 } . By (30) at the fixed point, κ S ( 1 + J / N ) = κ / 8 + 2 κ S ( J / N ) + 1 4 κ C ( J / q ) \kappa\mathcal{S}(1 + J/N) = \kappa/8 + 2\kappa\mathcal{S}(J/N) + \frac{1}{4}\kappa\mathcal{C}(J/q) κ S ( 1 + J / N ) = κ /8 + 2 κ S ( J / N ) + 4 1 κ C ( J / q ) . Subtracting and dividing by N 2 N^2 N 2 , the term with H ( J ) \mathcal{H}(J) H ( J ) contributes at most 2 e k − 1 / 4 2e_{k-1}/4 2 e k − 1 /4 , the term with Γ q \Gamma_q Γ q contributes at most 1 4 ( f k − 1 + ω ( 2 / q ) ) \frac{1}{4}(f_{k-1} + \omega(2/q)) 4 1 ( f k − 1 + ω ( 2/ q )) , and the constants contribute at most θ k + 1 / N 2 \theta_k + 1/N^2 θ k + 1/ N 2 . The difference is therefore at most 1 2 e k − 1 + 1 4 f k − 1 + η k \frac{1}{2}e_{k-1} + \frac{1}{4}f_{k-1} + \eta_k 2 1 e k − 1 + 4 1 f k − 1 + η k . Let n = N + J n = N + J n = N + J with 0 ≤ J < τ 0 \le J < \tau 0 ≤ J < τ . Then H ( N ) ≤ H ( n ) ≤ M q + O ( ( τ + 2 ) 2 ) \mathcal{H}(N) \le\mathcal{H}(n) \le\mathcal{M}_q + O((\tau+ 2)^2) H ( N ) ≤ H ( n ) ≤ M q + O (( τ + 2 ) 2 ) by (28) and the crude bounds, while κ / 8 ≤ κ S ( n / N ) ≤ κ / 8 + ω ( τ / N ) \kappa/8 \le\kappa\mathcal{S}(n/N) \le\kappa/8 + \omega(\tau/N) κ /8 ≤ κ S ( n / N ) ≤ κ /8 + ω ( τ / N ) . Since H ( N ) / N 2 ≥ κ / 8 − e k − 1 / 4 \mathcal{H}(N)/N^2 \ge\kappa/8 - e_{k-1}/4 H ( N ) / N 2 ≥ κ /8 − e k − 1 /4 , the difference is at most 1 4 e k − 1 + η k \frac{1}{4}e_{k-1} + \eta_k 4 1 e k − 1 + η k . Altogether
e k ≤ 1 2 e k − 1 + 1 4 f k − 1 + η k . e_k \le\frac{1}{2}e_{k-1} + \frac{1}{4}f_{k-1} + \eta_k. e k ≤ 2 1 e k − 1 + 4 1 f k − 1 + η k .
For the second error, put M = q M = q M = q , so that N = 2 M N = 2M N = 2 M . Summing (29) gives, for t ≥ 0 t \ge0 t ≥ 0 ,
Γ N ( t ) = E ( t ) + 2 H < M ( t + 1 ) + Γ M ( t − N ) + Γ M − 1 ( t − N − 1 ) , \Gamma_N(t) = E(t) + 2\mathcal{H}^{<M}(t + 1) + \Gamma_M(t - N) + \Gamma_{M-1}(t - N - 1), Γ N ( t ) = E ( t ) + 2 H < M ( t + 1 ) + Γ M ( t − N ) + Γ M − 1 ( t − N − 1 ) ,
with ∣ E ( t ) ∣ ≤ 3 N |E(t)| \le3N ∣ E ( t ) ∣ ≤ 3 N . For t ≤ N − 1 t \le N - 1 t ≤ N − 1 the last two terms vanish and H < M ( t + 1 ) = H ( t + 1 ) \mathcal{H}^{<M}(t + 1) = \mathcal{H}(t + 1) H < M ( t + 1 ) = H ( t + 1 ) with t + 1 ≤ N t + 1 \le N t + 1 ≤ N . Since C ( y ) = 2 S ( y ) \mathcal{C}(y) = 2\mathcal{S}(y) C ( y ) = 2 S ( y ) on [ 0 , 1 ] [0,1] [ 0 , 1 ] , the difference in (33) is at most 2 e k − 1 / 4 + 2 ω ( 1 / N ) + 3 / N 2e_{k-1}/4 + 2\omega(1/N) + 3/N 2 e k − 1 /4 + 2 ω ( 1/ N ) + 3/ N . For N + τ ≤ t ≤ 2 N N + \tau\le t \le2N N + τ ≤ t ≤ 2 N we have H < M ( t + 1 ) = M M \mathcal{H}^{<M}(t + 1) = \mathcal{M}_M H < M ( t + 1 ) = M M , and Lemma 19 replaces Γ M − 1 ( t − N − 1 ) \Gamma_{M-1}(t - N - 1) Γ M − 1 ( t − N − 1 ) by Γ M ( t − N − 1 ) \Gamma_M(t - N - 1) Γ M ( t − N − 1 ) with an error O ( k 2 2 k ) O(k2^{2k}) O ( k 2 2 k ) . Since κ C ( t / N ) = κ / 4 + 1 2 κ C ( ( t − N ) / M ) \kappa\mathcal{C}(t/N) = \kappa/4 + \frac{1}{2}\kappa\mathcal{C}((t - N)/M) κ C ( t / N ) = κ /4 + 2 1 κ C (( t − N ) / M ) and 2 M M / N 2 2\mathcal{M}_M/N^2 2 M M / N 2 differs from κ / 4 \kappa/4 κ /4 by 2 θ k 2\theta_k 2 θ k , the difference is at most 1 4 ( 2 f k − 1 + ω ( 1 / M ) ) + η k \frac{1}{4}(2f_{k-1} + \omega(1/M)) + \eta_k 4 1 ( 2 f k − 1 + ω ( 1/ M )) + η k . For N ≤ t < N + τ N \le t < N + \tau N ≤ t < N + τ , monotonicity gives Γ N ( N − 1 ) ≤ Γ N ( t ) ≤ 3 N + 2 M M + O ( ( τ + 2 ) 2 ) \Gamma_N(N - 1) \le\Gamma_N(t) \le3N + 2\mathcal{M}_M + O((\tau+ 2)^2) Γ N ( N − 1 ) ≤ Γ N ( t ) ≤ 3 N + 2 M M + O (( τ + 2 ) 2 ) , while κ C ( t / N ) \kappa\mathcal{C}(t/N) κ C ( t / N ) lies between κ / 4 \kappa/4 κ /4 and κ / 4 + ω ( τ / N ) \kappa/4 + \omega(\tau/N) κ /4 + ω ( τ / N ) . The difference is at most 1 2 e k − 1 + η k \frac{1}{2}e_{k-1} + \eta_k 2 1 e k − 1 + η k . Altogether
f k ≤ max ( 1 2 e k − 1 , 1 2 f k − 1 ) + η k . f_k \le\max\left(\frac{1}{2}e_{k-1},\frac{1}{2}f_{k-1}\right) + \eta_k. f k ≤ max ( 2 1 e k − 1 , 2 1 f k − 1 ) + η k .
Let v k = max ( e k , f k ) v_k = \max(e_k,f_k) v k = max ( e k , f k ) . The two inequalities give v k ≤ 3 4 v k − 1 + η k v_k \le\frac{3}{4}v_{k-1} + \eta_k v k ≤ 4 3 v k − 1 + η k for all large k k k . Multiplying by ( 4 3 ) k (\frac{4}{3})^k ( 3 4 ) k and summing, we obtain v k = O ( k 1 + 2 β ( 3 4 ) k ) v_k = O(k^{1+2\beta}(\frac{3}{4})^k) v k = O ( k 1 + 2 β ( 4 3 ) k ) , and 1 + 2 β < 2 1 + 2\beta< 2 1 + 2 β < 2 .
The envelope and the optimal constants
Theorem 31. For 1 ≤ u ≤ 2 1 \le u \le2 1 ≤ u ≤ 2 ,
3 u 2 32 ≤ S ( u ) ≤ u 2 8 (36) \frac{3u^2}{32} \le\mathcal{S}(u) \le\frac{u^2}{8} \tag*{(36)} 32 3 u 2 ≤ S ( u ) ≤ 8 u 2 (36) Equality holds on the left only at u = 4 / 3 u = 4/3 u = 4/3 , and on the right only at u = 1 u = 1 u = 1 and u = 2 u = 2 u = 2 .
Proof. Let K \mathcal{K} K be the set of pairs ( f , g ) (f,g) ( f , g ) in X \mathcal{X} X such that, on [ 1 , 2 ] [1,2] [ 1 , 2 ] ,
3 u 2 32 ≤ f ( u ) ≤ u 2 8 , 1 4 ≤ g ( y ) ≤ 1 2 − ( 2 − y ) 2 8 . \frac{3u^2}{32} \le f(u) \le\frac{u^2}{8}, \qquad\frac{1}{4} \le g(y) \le\frac{1}{2} - \frac{(2-y)^2}{8}. 32 3 u 2 ≤ f ( u ) ≤ 8 u 2 , 4 1 ≤ g ( y ) ≤ 2 1 − 8 ( 2 − y ) 2 .
It is closed and it contains the pair f ( u ) = u 2 / 8 f(u) = u^2/8 f ( u ) = u 2 /8 , g ( y ) = y / 4 g(y) = y/4 g ( y ) = y /4 . We show that T \mathcal{T} T preserves K \mathcal{K} K . Let ( f , g ) ∈ K (f,g) \in\mathcal{K} ( f , g ) ∈ K and ( f ∗ , g ∗ ) = T ( f , g ) (f^*,g^*) = \mathcal{T}(f,g) ( f ∗ , g ∗ ) = T ( f , g ) . By scaling, the extension of f f f satisfies the same two bounds on [ 0 , 1 ] [0,1] [ 0 , 1 ] , and the extension of g g g satisfies 0 ≤ g ( y ) ≤ y 2 / 4 0 \le g(y) \le y^2/4 0 ≤ g ( y ) ≤ y 2 /4 on [ 0 , 1 ] [0,1] [ 0 , 1 ] . For 0 ≤ x ≤ 1 / 2 0 \le x \le1/2 0 ≤ x ≤ 1/2 we have g ( 2 x ) = 8 f ( x ) g(2x) = 8f(x) g ( 2 x ) = 8 f ( x ) , and (30) gives
f ∗ ( 1 + x ) − 3 ( 1 + x ) 2 32 = 4 ( f ( x ) − 3 x 2 32 ) + ( 3 x − 1 ) 2 32 , f^*(1+x) - \frac{3(1+x)^2}{32} = 4\left(f(x) - \frac{3x^2}{32}\right) + \frac{(3x - 1)^2}{32}, f ∗ ( 1 + x ) − 32 3 ( 1 + x ) 2 = 4 ( f ( x ) − 32 3 x 2 ) + 32 ( 3 x − 1 ) 2 ,
( 1 + x ) 2 8 − f ∗ ( 1 + x ) = 4 ( x 2 8 − f ( x ) ) + x ( 2 − 3 x ) 8 . (37) \frac{(1+x)^2}{8} - f^*(1+x) = 4\left(\frac{x^2}{8} - f(x)\right) + \frac{x(2 - 3x)}{8}. \tag*{(37)} 8 ( 1 + x ) 2 − f ∗ ( 1 + x ) = 4 ( 8 x 2 − f ( x ) ) + 8 x ( 2 − 3 x ) . (37)
For 1 / 2 ≤ x ≤ 1 1/2 \le x \le1 1/2 ≤ x ≤ 1 it gives
f ∗ ( 1 + x ) − 3 ( 1 + x ) 2 32 = 2 ( f ( x ) − 3 x 2 32 ) + 1 4 ( g ( 2 x ) − 1 4 ) + 3 ( 1 − x ) 2 32 , ( 1 + x ) 2 8 − f ∗ ( 1 + x ) = 2 ( x 2 8 − f ( x ) ) + 1 4 ( 1 2 − ( 1 − x ) 2 2 − g ( 2 x ) ) . (38) \begin{aligned}
f^*(1+x)-\frac{3(1+x)^2}{32} &= 2\left(f(x)-\frac{3x^2}{32}\right)+\frac{1}{4}\left(g(2x)-\frac{1}{4}\right)+\frac{3(1-x)^2}{32},\\
\frac{(1+x)^2}{8}-f^*(1+x) &= 2\left(\frac{x^2}{8}-f(x)\right)+\frac{1}{4}\left(\frac{1}{2}-\frac{(1-x)^2}{2}-g(2x)\right). \tag*{(38)}
\end{aligned} f ∗ ( 1 + x ) − 32 3 ( 1 + x ) 2 8 ( 1 + x ) 2 − f ∗ ( 1 + x ) = 2 ( f ( x ) − 32 3 x 2 ) + 4 1 ( g ( 2 x ) − 4 1 ) + 32 3 ( 1 − x ) 2 , = 2 ( 8 x 2 − f ( x ) ) + 4 1 ( 2 1 − 2 ( 1 − x ) 2 − g ( 2 x ) ) . (38)
All the terms on the right-hand sides are nonnegative, so f ∗ f^* f ∗ satisfies the two bounds. For 0 ≤ x ≤ 1 / 2 0 \le x \le1/2 0 ≤ x ≤ 1/2 we have 0 ≤ g ( 2 x ) ≤ x 2 0 \le g(2x) \le x^2 0 ≤ g ( 2 x ) ≤ x 2 , hence
1 4 ≤ g ∗ ( 1 + x ) ≤ 1 4 + x 2 2 ≤ 1 2 − ( 1 − x ) 2 8 . \frac{1}{4} \le g^*(1+x) \le\frac{1}{4}+\frac{x^2}{2} \le\frac{1}{2}-\frac{(1-x)^2}{8}. 4 1 ≤ g ∗ ( 1 + x ) ≤ 4 1 + 2 x 2 ≤ 2 1 − 8 ( 1 − x ) 2 .
the last inequality being 5 x 2 − 2 x − 1 ≤ 0 5x^2-2x-1 \le0 5 x 2 − 2 x − 1 ≤ 0 . For 1 / 2 ≤ x ≤ 1 1/2 \le x \le1 1/2 ≤ x ≤ 1 the bounds on g ( 2 x ) g(2x) g ( 2 x ) give
3 8 ≤ g ∗ ( 1 + x ) ≤ 1 2 − ( 1 − x ) 2 4 . \frac{3}{8} \le g^*(1+x) \le\frac{1}{2}-\frac{(1-x)^2}{4}. 8 3 ≤ g ∗ ( 1 + x ) ≤ 2 1 − 4 ( 1 − x ) 2 .
Thus T T T preserves K \mathcal{K} K . The iterates of a point of K \mathcal{K} K converge to the fixed point, so ( S , C ) ∈ K (S,C) \in\mathcal{K} ( S , C ) ∈ K , which is (34).
Take f = f ∗ = S f=f^*=S f = f ∗ = S and g = g ∗ = C g=g^*=C g = g ∗ = C in these identities. The lower bound gives S > 0 S>0 S > 0 on ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) , hence C > 0 C>0 C > 0 on ( 0 , 2 ] (0,2] ( 0 , 2 ] and C ( y ) > 1 / 4 C(y)>1/4 C ( y ) > 1/4 for 1 < y ≤ 2 1<y\le2 1 < y ≤ 2 . In the first line of (38) the middle term is then positive for x > 1 / 2 x>1/2 x > 1/2 , and the first line of (35) vanishes only for x = 1 / 3 x=1/3 x = 1/3 . Together with (32) this proves the assertion on the left. For 0 < x ≤ 1 / 2 0<x\le1/2 0 < x ≤ 1/2 the last term of the second line of (35) is positive. For 1 / 2 ≤ x < 1 1/2\le x<1 1/2 ≤ x < 1 the two displayed bounds on g ∗ g^* g ∗ give C ( 2 x ) < 1 2 − 1 2 ( 1 − x ) 2 C(2x)<\frac{1}{2}-\frac{1}{2}(1-x)^2 C ( 2 x ) < 2 1 − 2 1 ( 1 − x ) 2 , so the second line of (38) is positive. The values u = 1 u=1 u = 1 and u = 2 u=2 u = 2 remain, where S ( u ) = u 2 / 8 S(u)=u^2/8 S ( u ) = u 2 /8 .
Theorem 32. For 1 ≤ u ≤ 2 1\le u\le2 1 ≤ u ≤ 2 let Ψ ( u ) = 12 κ S ( u ) / u 2 \Psi(u)=12\kappa S(u)/u^2 Ψ ( u ) = 12 κ S ( u ) / u 2 . Then, with k = ⌊ log 2 n ⌋ k=\lfloor\log_2 n\rfloor k = ⌊ log 2 n ⌋ ,
a ( n ) = n 2 Ψ ( n 2 k ) + O ( n log 2 3 ( log n ) 2 ) . (39) a(n)=n^2\Psi\left(\frac{n}{2^k}\right)+O\left(n^{\log_2 3}(\log n)^2\right). \tag*{(39)} a ( n ) = n 2 Ψ ( 2 k n ) + O ( n l o g 2 3 ( log n ) 2 ) . (39) The function Ψ \Psi Ψ is continuous, Ψ ( 1 ) = Ψ ( 2 ) = 3 κ / 2 \Psi(1)=\Psi(2)=3\kappa/2 Ψ ( 1 ) = Ψ ( 2 ) = 3 κ /2 , and
lim inf n → ∞ a ( n ) n 2 = 9 κ 8 = 0.773905146264335750 … , \liminf_{n\to\infty}\frac{a(n)}{n^2}=\frac{9\kappa}{8}=0.773905146264335750\ldots, n → ∞ lim inf n 2 a ( n ) = 8 9 κ = 0.773905146264335750 … , lim sup n → ∞ a ( n ) n 2 = 3 κ 2 = 1.031873528352447667 … . \limsup_{n\to\infty}\frac{a(n)}{n^2}=\frac{3\kappa}{2}=1.031873528352447667\ldots. n → ∞ lim sup n 2 a ( n ) = 2 3 κ = 1.031873528352447667 … . The lower limit is approached along n = ⌊ 2 k + 2 / 3 ⌋ n=\lfloor2^{k+2/3}\rfloor n = ⌊ 2 k + 2/3 ⌋ and the upper limit along n = 2 k n=2^k n = 2 k . In particular a ( n ) / n 2 a(n)/n^2 a ( n ) / n 2 has no limit, and the quotient of the two constants is 3 / 4 3/4 3/4 .
Proof. Let N = 2 k ≤ n < 2 N N=2^k\le n<2N N = 2 k ≤ n < 2 N and u = n / N u=n/N u = n / N . By Theorem 30 at the levels k k k and k + 1 k+1 k + 1 , each of H ( n − 1 ) \mathcal{H}(n-1) H ( n − 1 ) , H ( n ) \mathcal{H}(n) H ( n ) , H ( n + 1 ) \mathcal{H}(n+1) H ( n + 1 ) , and H ( n + 2 ) \mathcal{H}(n+2) H ( n + 2 ) differs from the corresponding value of κ N 2 S \kappa N^2S κ N 2 S by O ( k 2 3 k ) O(k2^{3k}) O ( k 2 3 k ) . By Lemma 29 these four values of κ N 2 S \kappa N^2S κ N 2 S differ from κ N 2 S ( u ) \kappa N^2S(u) κ N 2 S ( u ) by O ( N 2 − β ) O(N^{2-\beta}) O ( N 2 − β ) , and N 2 − β = 3 k N^{2-\beta}=3^k N 2 − β = 3 k . Formula (19) then gives a ( n ) = 12 κ N 2 S ( u ) + O ( k 2 3 k ) a(n)=12\kappa N^2S(u)+O(k2^{3k}) a ( n ) = 12 κ N 2 S ( u ) + O ( k 2 3 k ) , which is (39) because 3 k ≤ n log 2 3 3^k\le n^{\log_2 3} 3 k ≤ n l o g 2 3 . By Theorem 31, 9 κ / 8 ≤ Ψ ( u ) ≤ 3 κ / 2 9\kappa/8\le\Psi(u)\le3\kappa/2 9 κ /8 ≤ Ψ ( u ) ≤ 3 κ /2 on [ 1 , 2 ] [1,2] [ 1 , 2 ] , with equality on the left at u = 4 / 3 u=4/3 u = 4/3 and on the right at u = 1 u=1 u = 1 . The two limits follow, the continuity of Ψ \Psi Ψ being used for the sequence n = ⌊ 2 k + 2 / 3 ⌋ n=\lfloor2^{k+2/3}\rfloor n = ⌊ 2 k + 2/3 ⌋ .
In logarithmic scale the main term is n 2 Φ ( log 2 n ) n^2\Phi(\log_2 n) n 2 Φ ( log 2 n ) , where Φ ( v ) = Ψ ( 2 v − ⌊ v ⌋ ) \Phi(v)=\Psi(2^{v-\lfloor v\rfloor}) Φ ( v ) = Ψ ( 2 v − ⌊ v ⌋ ) is continuous and has period 1. Figure 5 compares the profile with the counts at scale 2 16 2^{16} 2 16 .
Figure 5. The function Ψ ( u ) = 12 κ S ( u ) / u 2 \Psi(u) = 12\kappa S(u)/u^2 Ψ ( u ) = 12 κ S ( u ) / u 2 on [ 1 , 2 ] [1,2] [ 1 , 2 ] , with values of a ( n ) / n 2 a(n)/n^2 a ( n ) / n 2 at n = 2 16 u n = 2^{16}u n = 2 16 u . The dashed lines are the lower and upper limits of a ( n ) / n 2 a(n)/n^2 a ( n ) / n 2 .
Theorem 32 is asymptotic. The next bound holds for every index.
Proposition 33. For every n ≥ 0 n\ge0 n ≥ 0 we have a ( n ) ≤ ( 9 n 2 + 3 ) / 8 a(n)\le(9n^2+3)/8 a ( n ) ≤ ( 9 n 2 + 3 ) /8 .
Proof. Each piece covers two edges of the lattice. By the proof of Lemma 5 , a piece placed at a free end covers the two sides that are not yet covered. Two free ends created at the same round have the same color in the bipartite lattice and are not adjacent. Hence no edge is covered twice. The edges covered during the first n n n rounds join vertices at distance at most n n n from the first apex. The sphere of radius d ≥ 1 d \ge1 d ≥ 1 around a vertex of the honeycomb lattice has 3 d 3d 3 d vertices, and every edge joins two consecutive spheres. The number e d e_d e d of edges between the spheres of radius d d d and d + 1 d+1 d + 1 therefore satisfies e 0 = 3 e_0 = 3 e 0 = 3 and e d + e d − 1 = 9 d e_d + e_{d-1} = 9d e d + e d − 1 = 9 d . The sum of e d e_d e d over d < n d < n d < n is 9 n 2 / 4 9n^2/4 9 n 2 /4 for even n n n and ( 9 n 2 + 3 ) / 4 (9n^2 + 3)/4 ( 9 n 2 + 3 ) /4 for odd n n n , and it is at least 2 a ( n ) 2a(n) 2 a ( n ) .
Binomial windows
The difference X k = C 2 k − C 2 k − 1 X_k = C_{2^k} - C_{2^k-1} X k = C 2 k − C 2 k − 1 records the effect of adding the last layer of a dyadic cone. The polynomials ∂ C r \partial C_r ∂ C r and E c E_c E c of § 5 measure that effect from the first possible birth in the added layer. Iterating (18) decomposes the polynomial into shifted groups of coefficients, which we call windows , and a remainder computed on domains of size O ( k ) O(k) O ( k ) .
The finite decomposition
The window polynomial of depth n ≥ 0 n \ge0 n ≥ 0 is
V n ( z ) = ∑ c = 0 n ( n c ) E c ( z ) − ⌊ 2 n − 1 ⌋ . (40) V_n(z) = \sum_{c=0}^{n} \binom{n}{c} E_c(z) - \left\lfloor2^{n-1} \right\rfloor. \tag*{(40)} V n ( z ) = c = 0 ∑ n ( c n ) E c ( z ) − ⌊ 2 n − 1 ⌋ . (40)
It has degree at most J n J_n J n . The first five are
V 0 = 1 , V 1 = 1 + z , V 2 = 2 + 3 z , V_0 = 1,\qquad V_1 = 1+z,\qquad V_2 = 2+3z, V 0 = 1 , V 1 = 1 + z , V 2 = 2 + 3 z ,
V 3 = 4 + 6 z + z 2 + 2 z 3 , V 4 = 8 + 10 z + 5 z 2 + 9 z 3 − z 5 . V_3 = 4+6z+z^2+2z^3,\qquad V_4 = 8+10z+5z^2+9z^3-z^5. V 3 = 4 + 6 z + z 2 + 2 z 3 , V 4 = 8 + 10 z + 5 z 2 + 9 z 3 − z 5 .
Theorem 34. Let 0 ≤ D ≤ k 0 \le D \le k 0 ≤ D ≤ k and q = 2 k − D q = 2^{k-D} q = 2 k − D , with q ≥ D q \ge D q ≥ D . Then
∂ C 2 k ( z ) = ∑ n = 0 D − 1 z 2 k − 2 k − n V n ( z ) + z 2 k − q R k , D ( z ) , \partial C_{2^k}(z) = \sum_{n=0}^{D-1} z^{2^k-2^{k-n}} V_n(z) + z^{2^k-q}R_{k,D}(z), ∂ C 2 k ( z ) = n = 0 ∑ D − 1 z 2 k − 2 k − n V n ( z ) + z 2 k − q R k , D ( z ) , R k , D = ∑ c = 0 D ( D c ) ∂ C q − c − ⌊ 2 D − 1 ⌋ . (41) R_{k,D} = \sum_{c=0}^{D} \binom{D}{c}\partial C_{q-c} - \left\lfloor2^{D-1} \right\rfloor. \tag*{(41)} R k , D = c = 0 ∑ D ( c D ) ∂ C q − c − ⌊ 2 D − 1 ⌋ . (41)
For k ≥ 1 k \ge1 k ≥ 1 , choose q = 2 ⌈ log 2 ( k + 1 ) ⌉ q = 2^{\lceil\log_2(k+1)\rceil} q = 2 ⌈ l o g 2 ( k + 1 )⌉ and D = k − log 2 q D = k - \log_2 q D = k − log 2 q . Then every kernel and every remainder term is computed on cones and triangles of size at most 2 k + 1 2k+1 2 k + 1 . Moreover
# supp ( X k ) = O ( k 3 ) . (42) \#\operatorname{supp}(X_k) = O(k^3). \tag*{(42)} # supp ( X k ) = O ( k 3 ) . (42)
Proof. We prove by induction on N N N , for 0 ≤ N ≤ D 0 \le N \le D 0 ≤ N ≤ D , that
∂ C 2 k = ∑ n = 0 N − 1 z 2 k − 2 k − n ( ∑ c = 0 n ( n c ) E c − 2 n z 2 k − 2 k − n − 1 ) + z 2 k − 2 k − N ∑ c = 0 N ( N c ) ∂ C 2 k − N − c . \partial C_{2^k} = \sum_{n=0}^{N-1} z^{2^k-2^{k-n}}\left(\sum_{c=0}^{n} \binom{n}{c} E_c - 2^n z^{2^k-2^{k-n-1}}\right) + z^{2^k-2^{k-N}}\sum_{c=0}^{N}\binom{N}{c}\partial C_{2^{k-N}-c}. ∂ C 2 k = n = 0 ∑ N − 1 z 2 k − 2 k − n ( c = 0 ∑ n ( c n ) E c − 2 n z 2 k − 2 k − n − 1 ) + z 2 k − 2 k − N c = 0 ∑ N ( c N ) ∂ C 2 k − N − c .
For N = 0 N=0 N = 0 the identity is immediate. Let N < D N<D N < D and put M = 2 k − N − 1 M=2^{k-N-1} M = 2 k − N − 1 . Every index c c c of the last sum satisfies c ≤ N ≤ D − 1 < q ≤ M c\le N\le D-1<q\le M c ≤ N ≤ D − 1 < q ≤ M . Proposition 18 therefore applies to ∂ C 2 M − c \partial C_{2M-c} ∂ C 2 M − c . The terms ∂ C M − c \partial C_{M-c} ∂ C M − c and ∂ C M − c − 1 \partial C_{M-c-1} ∂ C M − c − 1 are collected with Pascal’s rule and carry the factor z 2 k − 2 M + M = z 2 k − 2 k − N − 1 z^{2^k-2M+M}=z^{2^k-2^{k-N-1}} z 2 k − 2 M + M = z 2 k − 2 k − N − 1 . The constants add up to − 2 N -2^N − 2 N with the same factor. This is the statement for N + 1 N+1 N + 1 . In the statement for N = D N=D N = D , the monomial − 2 N z 2 k − 2 k − N − 1 -2^N z^{2^k-2^{k-N-1}} − 2 N z 2 k − 2 k − N − 1 is the constant term − 2 n -2^n − 2 n of the window of depth n + 1 n+1 n + 1 when n + 1 ≤ D − 1 n+1\le D-1 n + 1 ≤ D − 1 , and it joins the last sum when n = D − 1 n=D-1 n = D − 1 . This gives (41) .
For the stated choice we have k + 1 ≤ q < 2 ( k + 1 ) k+1\le q<2(k+1) k + 1 ≤ q < 2 ( k + 1 ) and D = k − ⌈ log 2 ( k + 1 ) ⌉ < q D=k-\lceil\log_2(k+1)\rceil<q D = k − ⌈ log 2 ( k + 1 )⌉ < q . The remainder uses the cones of size at most q q q . The windows use the kernels E c E_c E c with c < D c<D c < D , which are computed in triangles of size at most 2 k 2k 2 k . By Lemma 17 the remainder has O ( q 2 ) O(q^2) O ( q 2 ) possible exponents and the window of depth n n n has at most J n + 1 J_n+1 J n + 1 . Summing over n < D n<D n < D gives (42) .
The window of depth n n n starts at the delay 2 k − 2 k − n 2^k-2^{k-n} 2 k − 2 k − n . The windows therefore accumulate toward the delay 2 k 2^k 2 k , and the distance between two consecutive windows is halved at each step. Figure 6 shows the case k = 12 k=12 k = 12 .
Figure 6. (a) The 51 nonzero coefficients of ∂ C 4096 \partial C_{4096} ∂ C 4096 . The abscissa is − log 2 ( 1 − t / 4096 ) -\log_2(1-t/4096) − log 2 ( 1 − t /4096 ) for the delay t t t , so that the window of depth n n n starts at n n n . The shaded part is the remainder of (39) for q = 16 q=16 q = 16 . (b) The window of depth 5, which is V 5 V_5 V 5 .
Corollary 35. Let k = a + n k=a+n k = a + n with a ≥ 1 a\ge1 a ≥ 1 and n ≥ 0 n\ge0 n ≥ 0 . If 2 a − 1 > max ( n , J n ) 2^{a-1}>\max(n,J_n) 2 a − 1 > max ( n , J n ) , then for 0 ≤ j < 2 a − 1 0\le j<2^{a-1} 0 ≤ j < 2 a − 1
[ z 2 k − 2 a + j ] ∂ C 2 k ( z ) = [ z j ] V n ( z ) . [z^{2^k-2^a+j}]\partial C_{2^k}(z)=[z^j]V_n(z). [ z 2 k − 2 a + j ] ∂ C 2 k ( z ) = [ z j ] V n ( z ) . In particular this coefficient depends only on n n n and j j j .
Proof. Use Theorem 34 with D = n + 1 D=n+1 D = n + 1 , for which q = 2 a − 1 q=2^{a-1} q = 2 a − 1 . The remainder starts at the delay 2 k − 2 a − 1 2^k-2^{a-1} 2 k − 2 a − 1 . A window of depth n ′ < n n'<n n ′ < n ends before the delay 2 k − 2 k − n ′ + 2 a − 1 2^k-2^{k-n'}+2^{a-1} 2 k − 2 k − n ′ + 2 a − 1 , which is at most 2 k − 2 a 2^k-2^a 2 k − 2 a . The window of depth n n n starts at 2 k − 2 a 2^k-2^a 2 k − 2 a . Hence it is the only term that contributes to the delays from 2 k − 2 a 2^k-2^a 2 k − 2 a to 2 k − 2 a − 1 − 1 2^k-2^{a-1}-1 2 k − 2 a − 1 − 1 .
The first rounds after a cut
In a growth, the first-touch data of a vertex other than the seed are the time at which it first receives a proposal and the number of proposals that it receives at that time. We assign the seed the initial data ( 0 , 1 ) (0,1) ( 0 , 1 ) . A non-seed vertex that never receives a proposal has no data. With this convention, a vertex is born at time t t t exactly when its data are ( t , 1 ) (t,1) ( t , 1 ) . Along an edge of the lattice either g g g changes by one and y y y is unchanged, or y y y changes by one and g g g is unchanged.
Lemma 36. Let 0 ≤ c < M 0 \le c < M 0 ≤ c < M and t 0 = 2 M − c − 1 t_0 = 2M-c-1 t 0 = 2 M − c − 1 . Consider the growths on Ω M , c \Omega_{M,c} Ω M , c and on Ω M , c + 1 \Omega_{M,c+1} Ω M , c + 1 . Let v v v be a vertex of Ω M , c + 1 \Omega_{M,c+1} Ω M , c + 1 and write g ( v ) = t 0 − ι g(v)=t_0-\iota g ( v ) = t 0 − ι , with ι ≥ 1 \iota\ge1 ι ≥ 1 . If the first-touch data of v v v in the two growths differ, then v v v receives no proposal before time t 0 + ι + y t_0+\iota+y t 0 + ι + y in either growth, where y y y is the height of v v v .
Consequently, let j ≥ 0 j \ge0 j ≥ 0 and let v v v be a vertex of Ω M , c \Omega_{M,c} Ω M , c that is born at time t 0 + j t_0+j t 0 + j in exactly one of the two growths. If g ( v ) < t 0 g(v)<t_0 g ( v ) < t 0 then ι + y ≤ j \iota+y \le j ι + y ≤ j . If g ( v ) = t 0 g(v)=t_0 g ( v ) = t 0 then y ≤ j y \le j y ≤ j .
Proof. Let T T T be the least time at which v v v receives a proposal in one of the two growths. We prove T ≥ t 0 + ι + y T \ge t_0+\iota+y T ≥ t 0 + ι + y by induction on T T T . The seed has the same data in both growths, so T ≥ 1 T \ge1 T ≥ 1 . Before time T T T the vertex v v v is intact in both growths, and the numbers of proposals that it receives at time T T T differ. These proposals are sent by the neighbors of v v v born at time T − 1 T-1 T − 1 . Hence some neighbor w w w of v v v is born at time T − 1 T-1 T − 1 in exactly one of the two growths. Suppose first that w ∉ Ω M , c + 1 w \notin\Omega_{M,c+1} w ∈ / Ω M , c + 1 . Then g ( w ) = t 0 g(w)=t_0 g ( w ) = t 0 and g ( v ) ≤ t 0 − 1 g(v) \le t_0-1 g ( v ) ≤ t 0 − 1 , so g g g changes along the edge. Therefore ι = 1 \iota=1 ι = 1 and w w w has height y y y . The vertex w w w is born at time T − 1 T-1 T − 1 in the growth on Ω M , c \Omega_{M,c} Ω M , c , which is at least its earliest time t 0 + y t_0+y t 0 + y . Thus T ≥ t 0 + 1 + y T \ge t_0+1+y T ≥ t 0 + 1 + y . Suppose now that w ∈ Ω M , c + 1 w \in\Omega_{M,c+1} w ∈ Ω M , c + 1 , and write g ( w ) = t 0 − ι ′ g(w)=t_0-\iota' g ( w ) = t 0 − ι ′ and y ′ y' y ′ for its height. The data of w w w in the two growths differ, and w w w receives a proposal at time T − 1 T-1 T − 1 in one of them. By the induction hypothesis T − 1 ≥ t 0 + ι ′ + y ′ T-1 \ge t_0+\iota'+y' T − 1 ≥ t 0 + ι ′ + y ′ . Along the edge the sum ι + y \iota+y ι + y changes by one, so ι ′ + y ′ ≥ ι + y − 1 \iota'+y' \ge\iota+y-1 ι ′ + y ′ ≥ ι + y − 1 and T ≥ t 0 + ι + y T \ge t_0+\iota+y T ≥ t 0 + ι + y .
For the second assertion, suppose that g ( v ) < t 0 g(v)<t_0 g ( v ) < t 0 . The data of v v v differ and v v v receives a proposal at time t 0 + j t_0+j t 0 + j in one of the growths, so t 0 + j ≥ t 0 + ι + y t_0+j \ge t_0+\iota+y t 0 + j ≥ t 0 + ι + y . Suppose that g ( v ) = t 0 g(v)=t_0 g ( v ) = t 0 . Then v v v is born at time t 0 + j t_0+j t 0 + j in the growth on Ω M , c \Omega_{M,c} Ω M , c , and this time is at least its earliest time t 0 + y t_0+y t 0 + y .
By (17) , the coefficient e j ( c ) e_j(c) e j ( c ) is the number of vertices born at time t 0 + j t_0+j t 0 + j in the growth on Ω M , c \Omega_{M,c} Ω M , c minus the same number for Ω M , c + 1 \Omega_{M,c+1} Ω M , c + 1 . The lemma confines the vertices that contribute to this difference to a triangle of side j j j next to the last layer. For j ≤ 1 j \le1 j ≤ 1 , this determines the coefficients.
Proposition 37. For every c ≥ 0 c \ge0 c ≥ 0 ,
e 0 ( c ) = 1 , e 1 ( c ) = 1 c ≡ 1 , 2 ( m o d 4 ) . e_0(c)=1,\qquad e_1(c)=\mathbf{1}_{c\equiv1,2\pmod{4}}. e 0 ( c ) = 1 , e 1 ( c ) = 1 c ≡ 1 , 2 ( mod 4 ) .
Consequently
[ z 0 ] V n = { 1 , n = 0 , 2 n − 1 , n ≥ 1 , [ z ] V n = ∑ 0 ≤ c ≤ n c ≡ 1 , 2 ( m o d 4 ) ( n c ) = 2 n − Re ( 1 + i ) n + 1 2 . (43) \begin{aligned}
[z^0]V_n&=
\begin{cases}
1, & n=0,\\
2^{n-1}, & n\ge1,
\end{cases}
&
[z]V_n&=\sum_{\substack{0\le c\le n\\c\equiv1,2\pmod{4}}}\binom{n}{c}
=\frac{2^n-\operatorname{Re}(1+i)^{n+1}}{2}. \tag*{(43)}
\end{aligned} [ z 0 ] V n = { 1 , 2 n − 1 , n = 0 , n ≥ 1 , [ z ] V n = 0 ≤ c ≤ n c ≡ 1 , 2 ( mod 4 ) ∑ ( c n ) = 2 2 n − Re ( 1 + i ) n + 1 . (43)
Proof. The first formula is the constant term of E c E_c E c in Lemma 17. Let M M M be dyadic with M > c M>c M > c and let v v v be a vertex born at time t 0 + 1 t_0+1 t 0 + 1 in exactly one of the two growths of Lemma 36. If g ( v ) < t 0 g(v)<t_0 g ( v ) < t 0 then ι = 1 \iota=1 ι = 1 and y = 0 y=0 y = 0 . By Lemma 7 such a vertex of the axis is born at its earliest time t 0 − 1 t_0-1 t 0 − 1 in both growths, which is a contradiction. Hence g ( v ) = t 0 g(v)=t_0 g ( v ) = t 0 and y ≤ 1 y\le1 y ≤ 1 . The vertex of the axis with g = t 0 g=t_0 g = t 0 is born at time t 0 t_0 t 0 . Therefore v v v is the vertex with g = t 0 g=t_0 g = t 0 and y = 1 y=1 y = 1 , and e 1 ( c ) e_1(c) e 1 ( c ) equals 1 if this vertex belongs to Ω M , c \Omega_{M,c} Ω M , c and is born at its earliest time t 0 + 1 t_0+1 t 0 + 1 , and 0 otherwise. This vertex has 2 x + p = 2 M − c − 2 2x+p=2M-c-2 2 x + p = 2 M − c − 2 . By Lemma 7 it is born at its earliest time exactly when x x x is even. For c = 0 c=0 c = 0 it is A ( M − 1 , 1 ) A(M-1,1) A ( M − 1 , 1 ) , which is outside the triangle. Let c ≥ 1 c\ge1 c ≥ 1 , so that M M M is even. If c c c is even the vertex is A ( M − 1 − c / 2 , 1 ) A(M-1-c/2,1) A ( M − 1 − c /2 , 1 ) and x x x is even exactly when c ≡ 2 ( m o d 4 ) c\equiv2\pmod{4} c ≡ 2 ( mod 4 ) . If c c c is odd the vertex is B ( M − ( c + 3 ) / 2 , 1 ) B(M-(c+3)/2,1) B ( M − ( c + 3 ) /2 , 1 ) and x x x is even exactly when c ≡ 1 ( m o d 4 ) c\equiv1\pmod{4} c ≡ 1 ( mod 4 ) . In both cases x + 1 < M x+1<M x + 1 < M , so the vertex belongs to Ω M , c \Omega_{M,c} Ω M , c . This proves the second formula. Identity (40) gives the binomial sums, and the fourth roots of unity give the displayed expression for the second one.
Periodic kernels
The next lemma compares two truncated triangles from two columns whose abscissas are multiples of a power of two.
Lemma 38. Let P P P be a power of two. Let Ω = Ω M , c \Omega= \Omega_{M,c} Ω = Ω M , c and Ω ′ = Ω M ′ , c ′ \Omega' = \Omega_{M',c'} Ω ′ = Ω M ′ , c ′ , and let k k k and k ′ k' k ′ be multiples of P P P with 0 ≤ k < M 0 \le k < M 0 ≤ k < M and 0 ≤ k ′ < M ′ 0 \le k' < M' 0 ≤ k ′ < M ′ . Assume that 2 M − c − 2 k = 2 M ′ − c ′ − 2 k ′ 2M-c-2k = 2M'-c'-2k' 2 M − c − 2 k = 2 M ′ − c ′ − 2 k ′ . Put
m = min ( M − k , M ′ − k ′ ) , m = \min(M-k,M'-k'), m = min ( M − k , M ′ − k ′ ) , and let R R R be the set of triples ( p , x , y ) (p,x,y) ( p , x , y ) with x ≥ 0 x \ge0 x ≥ 0 , y ≥ 0 y \ge0 y ≥ 0 , x + y < m x+y < m x + y < m and ( p , k + x , y ) ∈ Ω (p,k+x,y) \in\Omega ( p , k + x , y ) ∈ Ω . A triple ( p , x , y ) (p,x,y) ( p , x , y ) with x ≥ 0 x \ge0 x ≥ 0 , y ≥ 0 y \ge0 y ≥ 0 and x + y < m x+y < m x + y < m belongs to R R R if and only if ( p , k ′ + x , y ) ∈ Ω ′ (p,k'+x,y) \in\Omega' ( p , k ′ + x , y ) ∈ Ω ′ . Moreover, for every ( p , x , y ) ∈ R (p,x,y) \in R ( p , x , y ) ∈ R , every integer s s s with
s < 2 x + p + 2 P and s ≤ 2 m , s < 2x+p+2P \qquad\text{and}\qquad s \le2m, s < 2 x + p + 2 P and s ≤ 2 m , and every μ ≥ 1 \mu\ge1 μ ≥ 1 , the vertex ( p , k + x , y ) (p,k+x,y) ( p , k + x , y ) has first-touch data ( 2 k + s , μ ) (2k+s,\mu) ( 2 k + s , μ ) in the growth on Ω \Omega Ω if and only if the vertex ( p , k ′ + x , y ) (p,k'+x,y) ( p , k ′ + x , y ) has first-touch data ( 2 k ′ + s , μ ) (2k'+s,\mu) ( 2 k ′ + s , μ ) in the growth on Ω ′ \Omega' Ω ′ .
Proof. For x + y < m x+y < m x + y < m the vertex ( p , k + x , y ) (p,k+x,y) ( p , k + x , y ) satisfies the first constraint of Ω \Omega Ω , and it satisfies the second one exactly when 2 x + y + p < 2 M − c − 2 k 2x+y+p < 2M-c-2k 2 x + y + p < 2 M − c − 2 k . The same holds for Ω ′ \Omega' Ω ′ , which proves the first assertion. We call s s s the relative time, and we say that a triple v = ( p , x , y ) \mathbf{v}=(p,x,y) v = ( p , x , y ) of R R R has the event ( s , μ ) (s,\mu) ( s , μ ) in Ω \Omega Ω when ( p , k + x , y ) (p,k+x,y) ( p , k + x , y ) has first-touch data ( 2 k + s , μ ) (2k+s,\mu) ( 2 k + s , μ ) , and similarly in Ω ′ \Omega' Ω ′ . Put h ( v ) = 2 x + p + 2 P h(\mathbf{v}) = 2x+p+2P h ( v ) = 2 x + p + 2 P . Along an edge h h h changes by one. The earliest time of ( p , k + x , y ) (p,k+x,y) ( p , k + x , y ) is 2 k + 2 ( x + y ) + p 2k+2(x+y)+p 2 k + 2 ( x + y ) + p , so no triple of R R R has an event at a negative relative time. We prove the statement by induction on s s s . Let v ∈ R \mathbf{v} \in R v ∈ R and let s s s satisfy s < h ( v ) s < h(\mathbf{v}) s < h ( v ) and s ≤ 2 m s \le2m s ≤ 2 m , and assume the statement for the smaller relative times.
Both truncated triangles are closed under predecessors for the earliest-time potential 2 ( x + y ) + p 2(x+y)+p 2 ( x + y ) + p , so Lemma 7 applies to them. Suppose first that v = ( 0 , 0 , y ) \mathbf{v}=(0,0,y) v = ( 0 , 0 , y ) . If y < P y<P y < P then k & y = 0 k \mathbin{\&} y=0 k & y = 0 and k ′ & y = 0 k' \mathbin{\&} y=0 k ′ & y = 0 , since k k k and k ′ k' k ′ are multiples of P P P . By Lemma 7 the vertices A ( k , y ) A(k,y) A ( k , y ) and A ( k ′ , y ) A(k',y) A ( k ′ , y ) are born at their earliest times, so v \mathbf{v} v has the event ( 2 y , 1 ) (2y,1) ( 2 y , 1 ) in both domains and no other event. If y ≥ P y \ge P y ≥ P the earliest relative time of v \mathbf{v} v is 2 y ≥ 2 P = h ( v ) > s 2y \ge2P = h(\mathbf{v}) > s 2 y ≥ 2 P = h ( v ) > s , and v \mathbf{v} v has no event at the relative time s s s in either domain.
Suppose now that v \mathbf{v} v is not of this form. Then every neighbor of ( p , k + x , y ) (p,k+x,y) ( p , k + x , y ) has an x x x -coordinate at least k k k , and the same holds with k ′ k' k ′ . By the induction hypothesis, applied to v \mathbf{v} v and to the relative times smaller than s s s , the triple v \mathbf{v} v is intact before the relative time s s s in Ω \Omega Ω exactly when it is so in Ω ′ \Omega' Ω ′ . The proposals that reach it at the relative time s s s are sent by its neighbors born at the relative time s − 1 s-1 s − 1 . A neighbor w ∈ R \mathbf{w} \in R w ∈ R satisfies h ( w ) ≥ h ( v ) − 1 > s − 1 h(\mathbf{w}) \ge h(\mathbf{v})-1 > s-1 h ( w ) ≥ h ( v ) − 1 > s − 1 and s − 1 ≤ 2 m s-1 \le2m s − 1 ≤ 2 m , so by the induction hypothesis it is born at the relative time s − 1 s-1 s − 1 in Ω \Omega Ω exactly when it is so in Ω ′ \Omega' Ω ′ . A neighbor ( p ′ , x ′ , y ′ ) (p',x',y') ( p ′ , x ′ , y ′ ) with x ′ ≥ 0 x' \ge0 x ′ ≥ 0 , y ′ ≥ 0 y' \ge0 y ′ ≥ 0 and x ′ + y ′ ≥ m x'+y' \ge m x ′ + y ′ ≥ m has an earliest relative time at least 2 m > s − 1 2m > s-1 2 m > s − 1 , so it is not born at the relative time s − 1 s-1 s − 1 in either domain. The remaining neighbors have a negative coordinate or lie outside both domains, by the first assertion. Hence v \mathbf{v} v receives the same number of proposals at the relative time s s s in both domains, which completes the induction.
Theorem 39. Let j ≥ 1 j \ge1 j ≥ 1 and let P P P be a power of two with P > j P > j P > j . Then
e j ( c + 2 P ) = e j ( c ) for every c ≥ j − 1. e_j(c+2P)=e_j(c) \qquad\text{for every } c \ge j-1. e j ( c + 2 P ) = e j ( c ) for every c ≥ j − 1. Proof. Let c ≥ j − 1 c \ge j-1 c ≥ j − 1 and c ^ = c + 2 P \hat{c}=c+2P c ^ = c + 2 P . Let M M M be a dyadic integer with M > c ^ M>\hat{c} M > c ^ . Then P P P divides M M M . Put
t 0 = 2 M − c − 1 , t ^ 0 = t 0 − 2 P , m = M − P , s = t ^ 0 + j = 2 m − ( c + 1 − j ) . t_0=2M-c-1,\qquad\hat{t}_0=t_0-2P,\qquad m=M-P,\qquad s=\hat{t}_0+j=2m-(c+1-j). t 0 = 2 M − c − 1 , t ^ 0 = t 0 − 2 P , m = M − P , s = t ^ 0 + j = 2 m − ( c + 1 − j ) . Thus s ≤ 2 m s \le2m s ≤ 2 m , with equality exactly when c = j − 1 c=j-1 c = j − 1 . For a vertex v v v of Ω M , c \Omega_{M,c} Ω M , c put
σ ( v ) = 1 [ v is born at time t 0 + j in Ω M , c ] − 1 [ v is born at time t 0 + j in Ω M , c + 1 ] , \sigma(v)=\mathbf{1}[v\text{ is born at time }t_0+j\text{ in }\Omega_{M,c}]-\mathbf{1}[v\text{ is born at time }t_0+j\text{ in }\Omega_{M,c+1}], σ ( v ) = 1 [ v is born at time t 0 + j in Ω M , c ] − 1 [ v is born at time t 0 + j in Ω M , c + 1 ] ,
where the second term is zero when v ∉ Ω M , c + 1 v \notin\Omega_{M,c+1} v ∈ / Ω M , c + 1 . Define σ ^ ( v ) \hat{\sigma}(v) σ ^ ( v ) in the same way for a vertex v v v of Ω M , c ^ \Omega_{M,\hat{c}} Ω M , c ^ , with the cuts c ^ \hat{c} c ^ and c ^ + 1 \hat{c}+1 c ^ + 1 and the time t ^ 0 + j = s \hat{t}_0+j=s t ^ 0 + j = s . By (17) ,
e j ( c ) = ∑ v ∈ Ω M , c σ ( v ) , e j ( c ^ ) = ∑ v ∈ Ω M , c ^ σ ^ ( v ) . (44) e_j(c)=\sum_{v\in\Omega_{M,c}}\sigma(v),\qquad e_j(\hat{c})=\sum_{v\in\Omega_{M,\hat{c}}}\hat{\sigma}(v). \tag*{(44)} e j ( c ) = v ∈ Ω M , c ∑ σ ( v ) , e j ( c ^ ) = v ∈ Ω M , c ^ ∑ σ ^ ( v ) . (44)
We say that a triple ( p , x , y ) (p,x,y) ( p , x , y ) with x ≥ 0 x\geq0 x ≥ 0 and y ≥ 0 y\geq0 y ≥ 0 is sensitive when, with γ = 2 x + y + p \gamma=2x+y+p γ = 2 x + y + p , either γ = t ^ 0 − ι \gamma=\hat{t}_0-\iota γ = t ^ 0 − ι with ι ≥ 1 \iota\geq1 ι ≥ 1 and ι + y ≤ j \iota+y\leq j ι + y ≤ j , or γ = t ^ 0 \gamma=\hat{t}_0 γ = t ^ 0 and y ≤ j y\leq j y ≤ j . A sensitive triple satisfies y ≤ j y\leq j y ≤ j and
2 x + p ≥ s − 2 j , 2 ( x + y ) + p ≤ s . (45) 2x+p\geq s-2j,\qquad2(x+y)+p\leq s. \tag*{(45)} 2 x + p ≥ s − 2 j , 2 ( x + y ) + p ≤ s . (45)
In the second inequality, equality requires γ = t ^ 0 \gamma=\hat{t}_0 γ = t ^ 0 and y = j y=j y = j .
By Lemma 36 , applied with the cut c ^ \hat{c} c ^ , every vertex with σ ^ ≠ 0 \hat{\sigma}\ne0 σ ^ = 0 is a sensitive triple. By (45) it satisfies x + y ≤ m x+y\leq m x + y ≤ m , and x + y = m x+y=m x + y = m is possible only if c = j − 1 c=j-1 c = j − 1 , p = 0 p=0 p = 0 and y = j y=j y = j . Let v = ( p , x , y ) v=(p,x,y) v = ( p , x , y ) be a vertex with σ ( v ) ≠ 0 \sigma(v)\ne0 σ ( v ) = 0 . By Lemma 36 , applied with the cut c c c , we have y ≤ j y\leq j y ≤ j and g ( v ) ≥ t 0 − j g(v)\geq t_0-j g ( v ) ≥ t 0 − j , hence 2 x ≥ t 0 − 2 j − 1 2x\geq t_0-2j-1 2 x ≥ t 0 − 2 j − 1 . Since t 0 ≥ 2 c ^ + 1 − c ≥ 4 P + j t_0\geq2\hat{c}+1-c\geq4P+j t 0 ≥ 2 c ^ + 1 − c ≥ 4 P + j , this gives x ≥ P x\geq P x ≥ P . Moreover ( p , x − P , y ) (p,x-P,y) ( p , x − P , y ) is a sensitive triple, because g ( v ) − t 0 = ( g ( v ) − 2 P ) − t ^ 0 g(v)-t_0=(g(v)-2P)-\hat{t}_0 g ( v ) − t 0 = ( g ( v ) − 2 P ) − t ^ 0 , and ( x − P ) + y < m (x-P)+y<m ( x − P ) + y < m because v ∈ Ω M , 0 v\in\Omega_{M,0} v ∈ Ω M , 0 .
Let R R R be the set of sensitive triples with x + y < m x+y<m x + y < m , and let ( p , x , y ) ∈ R (p,x,y)\in R ( p , x , y ) ∈ R . The vertex ( p , P + x , y ) (p,P+x,y) ( p , P + x , y ) belongs to Ω M , c \Omega_{M,c} Ω M , c and the vertex ( p , x , y ) (p,x,y) ( p , x , y ) belongs to Ω M , c ^ \Omega_{M,\hat{c}} Ω M , c ^ . The first belongs to Ω M , c + 1 \Omega_{M,c+1} Ω M , c + 1 exactly when the second belongs to Ω M , c ^ + 1 \Omega_{M,\hat{c}+1} Ω M , c ^ + 1 , that is when γ < t ^ 0 \gamma<\hat{t}_0 γ < t ^ 0 . By (45) , 2 x + p + 2 P ≥ s − 2 j + 2 P > s 2x+p+2P\geq s-2j+2P>s 2 x + p + 2 P ≥ s − 2 j + 2 P > s , and s ≤ 2 m s\leq2m s ≤ 2 m . We apply Lemma 38 with k = P k=P k = P and k ′ = 0 k'=0 k ′ = 0 , for which min ( M − k , M − k ′ ) = m \min(M-k,M-k')=m min ( M − k , M − k ′ ) = m . With the domains Ω M , c \Omega_{M,c} Ω M , c and Ω M , c ^ \Omega_{M,\hat{c}} Ω M , c ^ , whose relative cuts are both t ^ 0 + 1 \hat{t}_0+1 t ^ 0 + 1 , it shows that ( p , P + x , y ) (p,P+x,y) ( p , P + x , y ) is born at time 2 P + s = t 0 + j 2P+s=t_0+j 2 P + s = t 0 + j in the growth on Ω M , c \Omega_{M,c} Ω M , c if and only if ( p , x , y ) (p,x,y) ( p , x , y ) is born at time s s s in the growth on Ω M , c ^ \Omega_{M,\hat{c}} Ω M , c ^ . With the domains Ω M , c + 1 \Omega_{M,c+1} Ω M , c + 1 and Ω M , c ^ + 1 \Omega_{M,\hat{c}+1} Ω M , c ^ + 1 , whose relative cuts are both t ^ 0 \hat{t}_0 t ^ 0 , it shows the same equivalence for these two growths when γ < t ^ 0 \gamma<\hat{t}_0 γ < t ^ 0 . Therefore σ ( p , P + x , y ) = σ ^ ( p , x , y ) \sigma(p,P+x,y)=\hat{\sigma}(p,x,y) σ ( p , P + x , y ) = σ ^ ( p , x , y ) .
By the two preceding paragraphs, the first sum of (44) is the sum of σ ^ \hat{\sigma} σ ^ over R R R , and the second sum is the sum of σ ^ \hat{\sigma} σ ^ over R R R and over the sensitive triples with x + y = m x+y=m x + y = m . If c > j − 1 c>j-1 c > j − 1 there is no such triple, so e j ( c ^ ) = e j ( c ) e_j(\hat{c})=e_j(c) e j ( c ^ ) = e j ( c ) . Let c = j − 1 c=j-1 c = j − 1 . Then s = 2 m s=2m s = 2 m and t ^ 0 = 2 m − j \hat{t}_0=2m-j t ^ 0 = 2 m − j , and the only sensitive triple with x + y = m x+y=m x + y = m is the vertex A ( m − j , j ) A(m-j,j) A ( m − j , j ) . It belongs to Ω M , c ^ \Omega_{M,\hat{c}} Ω M , c ^ and not to Ω M , c ^ + 1 \Omega_{M,\hat{c}+1} Ω M , c ^ + 1 , and 2 m 2m 2 m is its earliest time. By Lemma 7 it is born at time 2 m 2m 2 m in the growth on Ω M , c ^ \Omega_{M,\hat{c}} Ω M , c ^ exactly when ( m − j ) & j = 0 (m-j)\mathbin{\&}j=0 ( m − j ) & j = 0 . This fails. Indeed 1 ≤ j < P 1\leq j<P 1 ≤ j < P and P P P divides m m m , so if 2 ℓ 2^\ell 2 ℓ is the largest power of two that divides j j j , then j j j and m − j m-j m − j are both odd multiples of 2 ℓ 2^\ell 2 ℓ . Hence σ ^ \hat{\sigma} σ ^ vanishes at this vertex and e j ( c ^ ) = e j ( c ) e_j(\hat{c})=e_j(c) e j ( c ^ ) = e j ( c ) .
The proof uses no bound on the time of the last birth in a triangle. For c = j − 1 c=j-1 c = j − 1 the coefficient e j ( c ) e_j(c) e j ( c ) is read at time 2 M 2M 2 M , and Lemma 38 is used at its last admissible relative time s = 2 m s=2m s = 2 m . The rows c ≤ j − 2 c\leq j-2 c ≤ j − 2 are not covered. They concern births after time 2 M 2M 2 M .
The columns of the windows
For j ≥ 1 j\geq1 j ≥ 1 let p j = 2 ⌊ log 2 j ⌋ + 2 p_j=2^{\lfloor\log_2j\rfloor+2} p j = 2 ⌊ l o g 2 j ⌋ + 2 . It is twice the least power of two larger than j j j , so Theorem 39 gives e j ( c + p j ) = e j ( c ) e_j(c+p_j)=e_j(c) e j ( c + p j ) = e j ( c ) for c ≥ j − 1 c\geq j-1 c ≥ j − 1 . Define
π j ( r ) = e j ( j − 1 + ( ( r − j + 1 ) m o d p j ) ) ( 0 ≤ r < p j ) , \pi_j(r)=e_j\left(j-1+((r-j+1)\bmod p_j)\right)\qquad(0\leq r<p_j), π j ( r ) = e j ( j − 1 + (( r − j + 1 ) mod p j ) ) ( 0 ≤ r < p j ) ,
η j ( c ) = e j ( c ) − π j ( c m o d p j ) ( 0 ≤ c ≤ j − 2 ) . (46) \eta_j(c)=e_j(c)-\pi_j(c\bmod p_j)\qquad(0\leq c\leq j-2). \tag*{(46)} η j ( c ) = e j ( c ) − π j ( c mod p j ) ( 0 ≤ c ≤ j − 2 ) . (46)
The list π j \pi_j π j is one period of the column j j j , and η j \eta_j η j measures the defect of periodicity on the first rows. The list η j \eta_j η j is empty for j = 1 j=1 j = 1 . For n ≥ 0 n\geq0 n ≥ 0 let ν j ( n ) = ⌊ z j ⌋ ν 2 ( z ) \nu_j(n)=\lfloor z^j\rfloor\nu_2(z) ν j ( n ) = ⌊ z j ⌋ ν 2 ( z ) .
Proposition 40. Let j ≥ 1 j\geq1 j ≥ 1 . For every $n\geq 0,
ν j ( n ) = ∑ r = 0 p j − 1 π j ( r ) ∑ 0 ≤ c ≤ n c ≡ r ( m o d p j ) ( n c ) + ν j ( n ) , ν j ( n ) = ∑ c = 0 j − 2 η j ( c ) ( n c ) . (47) \nu_j(n)=\sum_{r=0}^{p_j-1}\pi_j(r)\sum_{\substack{0\leq c\leq n\\ c\equiv r\pmod{p_j}}}\binom{n}{c}+\nu_j(n),
\qquad
\nu_j(n)=\sum_{c=0}^{j-2}\eta_j(c)\binom{n}{c}. \tag*{(47)} ν j ( n ) = r = 0 ∑ p j − 1 π j ( r ) 0 ≤ c ≤ n c ≡ r ( mod p j ) ∑ ( c n ) + ν j ( n ) , ν j ( n ) = c = 0 ∑ j − 2 η j ( c ) ( c n ) . (47)
The function ν j \nu_j ν j is a polynomial in n n n of degree at most j − 2 j-2 j − 2 , and $\nu_1=0.
Proof. By (40) , v j ( n ) = ∑ c = 0 n ( n c ) e j ( c ) v_j(n)=\sum_{c=0}^{n}\binom{n}{c}e_j(c) v j ( n ) = ∑ c = 0 n ( c n ) e j ( c ) . We have e j ( c ) = π j ( c m o d p j ) e_j(c)=\pi_j(c\bmod p_j) e j ( c ) = π j ( c mod p j ) for c ≥ j − 1 c\ge j-1 c ≥ j − 1 by Theorem 39 , and e j ( c ) = π j ( c m o d p j ) + η j ( c ) e_j(c)=\pi_j(c\bmod p_j)+\eta_j(c) e j ( c ) = π j ( c mod p j ) + η j ( c ) for c ≤ j − 2 c\le j-2 c ≤ j − 2 by (46) .
Corollary 41. Let ∇ \nabla ∇ be the difference operator, ( ∇ f ) ( n ) = f ( n + 1 ) − f ( n ) (\nabla f)(n)=f(n+1)-f(n) ( ∇ f ) ( n ) = f ( n + 1 ) − f ( n ) . For every j ≥ 1 j\ge1 j ≥ 1 ,
∇ j − 1 ( ∇ p j − 1 ) v j = 0. \nabla^{j-1}(\nabla^{p_j}-1)v_j=0. ∇ j − 1 ( ∇ p j − 1 ) v j = 0.
Proof. For a residue r r r modulo p j p_j p j let f r ( n ) f_r(n) f r ( n ) be the inner sum of (47) . Pascal’s rule gives ∇ f r = f r − 1 \nabla f_r=f_{r-1} ∇ f r = f r − 1 , hence ∇ p j f r = f r \nabla^{p_j}f_r=f_r ∇ p j f r = f r . It also gives ∇ ( n c ) = ( n c − 1 ) \nabla\binom{n}{c}=\binom{n}{c-1} ∇ ( c n ) = ( c − 1 n ) , so ∇ j − 1 \nabla^{j-1} ∇ j − 1 annihilates ϑ j \vartheta_j ϑ j . The two operators commute.
These are recurrences for each fixed column, and their order grows with j j j . The number of sequences needed as j j j varies is not bounded here.
For 1 ≤ j ≤ 63 1\le j\le63 1 ≤ j ≤ 63 , a finite calculation gives η j = 0 \eta_j=0 η j = 0 and proves that p j p_j p j is the least period. Appendix B gives the procedure, the first seven lists, and the certificate. The general theorem requires only eventual periodicity and allows a nonzero polynomial correction.
Open questions
The optimal error term in (39) and the best Hölder exponent of the profile are unknown. It is also open whether 9 κ / 8 < a ( n ) / n 2 < 3 κ / 2 9\kappa/8<a(n)/n^2<3\kappa/2 9 κ /8 < a ( n ) / n 2 < 3 κ /2 holds for every n ≥ 3 n\ge3 n ≥ 3 .
The identity deg P q = 2 q − 3 \deg P_q=2q-3 deg P q = 2 q − 3 remains open beyond the range certified in Appendix A. By Lemma 21 , it would follow from deg C r = 2 r − 2 \deg C_r=2r-2 deg C r = 2 r − 2 for every direct cone. A bound J n = O ( n ) J_n=O(n) J n = O ( n ) for the kernel degrees would improve (42) to # supp ( X k ) = O ( k 2 ) \#\operatorname{supp}(X_k)=O(k^2) # supp ( X k ) = O ( k 2 ) .
Theorem 39 gives eventual periodicity for every kernel column. It is unknown whether all prefix corrections η j \eta_j η j vanish, or equivalently whether, for every dyadic P P P , the coefficients of E c E_c E c of degree less than P P P are determined by c c c modulo 2 P 2P 2 P . A rule for the period lists π j \pi_j π j is also unknown.
The series of Theorem 25 computes κ \kappa κ with a geometric error bound. Its rationality, algebraicity, or transcendence is unknown. A Mellin analysis of the periodic function Φ \Phi Φ , along the lines of Flajolet, Gourdon, and Dumas [6 ] , may describe its Fourier coefficients. The analytic continuation of the generating function is another question. The denominators 1 − z 4 q 1-z^{4q} 1 − z 4 q alone do not exclude cancellation in the infinite sum.
It is not known whether finitely many auxiliary numerical sequences give a ( n ) a(n) a ( n ) by recurrences of a fixed form, or whether the direct cones can be eliminated. Another question is whether all subsequences ( a ( 2 e n + r ) ) n ≥ 0 (a(2^e n+r))_{n\ge0} ( a ( 2 e n + r ) ) n ≥ 0 , with e ≥ 0 e\ge0 e ≥ 0 and 0 ≤ r < 2 e 0\le r<2^e 0 ≤ r < 2 e , are integer linear combinations of finitely many fixed integer sequences, as in Allouche and Shallit [1 ] . No equivalence between these questions is asserted. It is also unknown whether a nontrivial linear equation with polynomial coefficients relates A ( z ) A(z) A ( z ) to finitely many of the series A ( z 2 ) , A ( z 4 ) , … A(z^2),A(z^4),\ldots A ( z 2 ) , A ( z 4 ) , … , or whether the complexity bound can be improved.
The geometric method may apply to other toothpick constructions. It requires separating boundaries and a bound on the unreduced regions, in addition to the earliest-time Pascal pattern.
Explicit bounds and finite degree checks
The estimates used in the text can be made effective without an assumption about the last birth time. The sizes of the cone and triangle give
0 ≤ C r ( 1 ) ≤ r ( r + 1 ) 2 , 0 ≤ L m , c ( 1 ) ≤ m ( m + 1 ) . 0\le C_r(1)\le\frac{r(r+1)}{2},\qquad0\le L_{m,c}(1)\le m(m+1). 0 ≤ C r ( 1 ) ≤ 2 r ( r + 1 ) , 0 ≤ L m , c ( 1 ) ≤ m ( m + 1 ) .
For c ≥ 1 c\ge1 c ≥ 1 , the least dyadic integer m > c m>c m > c satisfies m ≤ 2 c m\le2c m ≤ 2 c . Consequently
∥ E c ∥ ≤ 2 m ( m + 1 ) ≤ 12 c 2 , \lVert E_c\rVert\le2m(m+1)\le12c^2, ∥ E c ∥ ≤ 2 m ( m + 1 ) ≤ 12 c 2 ,
while E 0 = 1 E_0 = 1 E 0 = 1 . These inequalities justify the following constants in the proof of Lemma 19 . An internal node has forcing norm at most 29 ( k + 1 ) 2 29(k+1)^2 29 ( k + 1 ) 2 . At a leaf, the two cones have index smaller than 4 ( k + 1 ) 4(k+1) 4 ( k + 1 ) , so their difference has norm less than 16 ( k + 1 ) 2 16(k+1)^2 16 ( k + 1 ) 2 . Its value at 1 1 1 has absolute value at most 10 ( k + 1 ) 2 10(k+1)^2 10 ( k + 1 ) 2 , since both masses are nonnegative. Counting the leaves and internal nodes gives
∥ C 2 k − C 2 k − 1 ∥ ≤ 45 ( k + 1 ) 2 2 k , ∣ d k ∣ ≤ 40 ( k + 1 ) 2 2 k . \left\lVert C_{2k}-C_{2k-1}\right\rVert\le45(k+1)^2 2^k,\qquad|d_k|\le40(k+1)^2 2^k. ∥ C 2 k − C 2 k − 1 ∥ ≤ 45 ( k + 1 ) 2 2 k , ∣ d k ∣ ≤ 40 ( k + 1 ) 2 2 k .
For a tree starting from Y ( a , j ) Y(a,j) Y ( a , j ) , the same argument gives ∣ Y ( a , j ) ∣ ≤ 40 ( a + j + 1 ) 2 2 a |Y(a,j)|\le40(a+j+1)^2 2^a ∣ Y ( a , j ) ∣ ≤ 40 ( a + j + 1 ) 2 2 a . Since d 1 = 2 d_1=2 d 1 = 2 , identity (24) yields ∣ δ k ∣ ≤ 81 ( k + 1 ) 2 2 k |\delta_k|\le81(k+1)^2 2^k ∣ δ k ∣ ≤ 81 ( k + 1 ) 2 2 k . Therefore
∣ k − μ 2 k 4 k ∣ ≤ 81 4 ∑ s ≥ k ( s + 1 ) 2 2 s = 81 ( k 2 + 4 k + 6 ) 2 k + 1 ≤ 42 ( k 2 + 4 k + 6 ) 2 k . (48) \left|k-\frac{\mu_{2^k}}{4^k}\right|
\le\frac{81}{4}\sum_{s\ge k}\frac{(s+1)^2}{2^s}
= \frac{81(k^2+4k+6)}{2^{k+1}}
\le\frac{42(k^2+4k+6)}{2^k}. \tag*{(48)} k − 4 k μ 2 k ≤ 4 81 s ≥ k ∑ 2 s ( s + 1 ) 2 = 2 k + 1 81 ( k 2 + 4 k + 6 ) ≤ 2 k 42 ( k 2 + 4 k + 6 ) . (48)
The value μ 232 = 12 689 804 595 979 239 659 \mu_{232}=12\,689\,804\,595\,979\,239\,659 μ 232 = 12 689 804 595 979 239 659 and this bound imply κ > 0 \kappa>0 κ > 0 . At k = 128 k=128 k = 128 , the bound is less than 2.087 ⋅ 10 − 33 2.087\cdot10^{-33} 2.087 ⋅ 1 0 − 33 . This mass, computed by both programs, and rational interval arithmetic certify the thirty decimal digits in Theorem 24 . The integer and the interval endpoints are included with the code.
For the degree excess of Lemma 21 , the domain bound gives τ k ≤ 5 k 2 \tau_k\le5k^2 τ k ≤ 5 k 2 . A direct cone of index r ≥ 4 r\ge4 r ≥ 4 has r = 2 a − c r=2^a-c r = 2 a − c , c > 2 a − 2 c>2^{a-2} c > 2 a − 2 , and rank a + c a+c a + c . If this rank is at most 266 266 266 , then a ≤ 9 a\le9 a ≤ 9 and r ≤ 383 r\le383 r ≤ 383 . The computation of the cones through index 383 383 383 gives deg C r = 2 r − 2 \deg C_r=2r-2 deg C r = 2 r − 2 , so τ k = 0 \tau_k=0 τ k = 0 for k ≤ 266 k\le266 k ≤ 266 . Lemma 21 then gives deg P q = 2 q − 3 \deg P_q=2q-3 deg P q = 2 q − 3 for dyadic q ≤ 2 266 q\le2^{266} q ≤ 2 266 . Let N = 2 q N=2^q N = 2 q with q ≥ 2 q\ge2 q ≥ 2 dyadic. The term F < q ( N + j ) F^{<q}(N+j) F < q ( N + j ) in (27) counts births of diamonds with center below q q q at an age larger than their size allows when deg P p = 2 p − 3 \deg P_p=2p-3 deg P p = 2 p − 3 . When this degree condition holds for every p < q p<q p < q , the term vanishes and Lemmas 26 and 27 read
F ( N + j ) = 2 F ( j ) + c N / 2 ( j − 2 ) ( 3 ≤ j ≤ N ) , c N ( t ) = 2 + 2 F ( t + 1 ) ( 2 ≤ t ≤ N − 1 ) , c N ( N + u ) = c N / 2 ( u ) + c N / 2 − 1 ( u − 1 ) − 1 1 ≤ u ≤ N / 2 − 1 ( u ≥ 0 ) . (49) \begin{aligned}
F(N+j)&=2F(j)+c_{N/2}(j-2) &&(3\le j\le N),\\
c_N(t)&=2+2F(t+1) &&(2\le t\le N-1),\\
c_N(N+u)&=c_{N/2}(u)+c_{N/2-1}(u-1)-\mathbf{1}_{1\le u\le N/2-1}(u\ge0). \tag*{(49)}
\end{aligned} F ( N + j ) c N ( t ) c N ( N + u ) = 2 F ( j ) + c N /2 ( j − 2 ) = 2 + 2 F ( t + 1 ) = c N /2 ( u ) + c N /2 − 1 ( u − 1 ) − 1 1 ≤ u ≤ N /2 − 1 ( u ≥ 0 ) . ( 3 ≤ j ≤ N ) , ( 2 ≤ t ≤ N − 1 ) , (49)
This gives the following formula at dyadic times.
Proposition 43. For 1 ≤ j ≤ 63 1\le j\le63 1 ≤ j ≤ 63 the list η j \eta_j η j vanishes. Hence e j ( c ) = π j ( c m o d p j ) e_j(c)=\pi_j(c\bmod p_j) e j ( c ) = π j ( c mod p j ) for every
c ≥ 0 c \ge0 c ≥ 0 , ϑ j = 0 \vartheta_j = 0 ϑ j = 0 , and ( ∇ p j − 1 ) v j = 0 (\nabla^{p_j}-1)v_j = 0 ( ∇ p j − 1 ) v j = 0 . The lists π j \pi_j π j for j ≤ 7 j \le7 j ≤ 7 are
j = 1 p 1 = 4 0 , 1 , 1 , 0 j = 2 p 2 = 8 0 , 0 , 0 , 1 , 1 , 1 , 0 j = 3 p 3 = 8 0 , 0 , 0 , 2 , 1 , − 1 , 1 , 0 j = 4 p 4 = 16 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , − 1 , 2 , 0 j = 5 p 5 = 16 0 , 0 , 0 , 0 , − 1 , 2 , 1 , 0 , 1 , 2 , 1 , − 1 , 0 , 1 , 2 , 0 j = 6 p 6 = 16 0 , 0 , 0 , 0 , 0 , 1 , − 1 , 2 , 2 , 1 , 1 , − 1 , − 1 , 2 , 1 , 0 j = 7 p 7 = 16 0 , 0 , 0 , 0 , 0 , 0 , 3 , 1 , − 1 , 2 , − 1 , 0 , 1 , 1 , 0. \begin{aligned}
j &= 1 \quad p_1 = 4 \quad0,\,1,\,1,\,0 \\
j &= 2 \quad p_2 = 8 \quad0,\,0,\,0,\,1,\,1,\,1,\,0 \\
j &= 3 \quad p_3 = 8 \quad0,\,0,\,0,\,2,\,1,\,-1,\,1,\,0 \\
j &= 4 \quad p_4 = 16 \quad0,\,0,\,0,\,0,\,0,\,0,\,1,\,1,\,1,\,1,\,1,\,1,\,-1,\,2,\,0 \\
j &= 5 \quad p_5 = 16 \quad0,\,0,\,0,\,0,\,-1,\,2,\,1,\,0,\,1,\,2,\,1,\,-1,\,0,\,1,\,2,\,0 \\
j &= 6 \quad p_6 = 16 \quad0,\,0,\,0,\,0,\,0,\,1,\,-1,\,2,\,2,\,1,\,1,\,-1,\,-1,\,2,\,1,\,0 \\
j &= 7 \quad p_7 = 16 \quad0,\,0,\,0,\,0,\,0,\,0,\,3,\,1,\,-1,\,2,\,-1,\,0,\,1,\,1,\,0.
\end{aligned} j j j j j j j = 1 p 1 = 4 0 , 1 , 1 , 0 = 2 p 2 = 8 0 , 0 , 0 , 1 , 1 , 1 , 0 = 3 p 3 = 8 0 , 0 , 0 , 2 , 1 , − 1 , 1 , 0 = 4 p 4 = 16 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , − 1 , 2 , 0 = 5 p 5 = 16 0 , 0 , 0 , 0 , − 1 , 2 , 1 , 0 , 1 , 2 , 1 , − 1 , 0 , 1 , 2 , 0 = 6 p 6 = 16 0 , 0 , 0 , 0 , 0 , 1 , − 1 , 2 , 2 , 1 , 1 , − 1 , − 1 , 2 , 1 , 0 = 7 p 7 = 16 0 , 0 , 0 , 0 , 0 , 0 , 3 , 1 , − 1 , 2 , − 1 , 0 , 1 , 1 , 0.
Proof. For $1 \le j \le J, f o r m u l a x r e f ‘ ( 43 ) ‘ u s e s , formula {xref}`(43)` uses , f or m u l a x r e f ‘ ( 43 ) ‘ u ses e_j(c)o n l y f o r $ 0 ≤ c ≤ j − 2 + p j ≤ J − 2 + p J only for \$0 \le c \le j - 2 + p_j \le J - 2 + p_J o n l y f or $0 ≤ c ≤ j − 2 + p j ≤ J − 2 + p J . For each such c c c , choose the least dyadic m > c m > c m > c and simulate the two finite domains Ω m , c \Omega_{m,c} Ω m , c and Ω m , c + 1 \Omega_{m,c+1} Ω m , c + 1 . Form E c E_c E c from their complete birth polynomials, read the required coefficients, and apply (46) . Each simulation stops by Remark 4. For J = 63 J = 63 J = 63 , the computation uses c ≤ 189 c \le189 c ≤ 189 and m ≤ 256 m \le256 m ≤ 256 . It gives η j = 0 \eta_j = 0 η j = 0 for every j ≤ 63 j \le63 j ≤ 63 . The other assertions follow from Theorem 39 , Proposition 40, and Corollary 41 .
The list π 1 \pi_1 π 1 agrees with Proposition 37. The computation was repeated with a second program, written separately. In the computed range c < 260 c < 260 c < 260 every kernel satisfies deg E c ≤ c + 1 \deg E_c \le c + 1 deg E c ≤ c + 1 , which means that the triangles Ω m , c \Omega_{m,c} Ω m , c and Ω m , c + 1 \Omega_{m,c+1} Ω m , c + 1 have the same numbers of births at every time after 2 m 2m 2 m . This is a finite observation and not a general statement.
In this section a period is any integer T T T for which the stated periodicity holds. For 1 ≤ j ≤ 63 1 \le j \le63 1 ≤ j ≤ 63 the computed lists also show that π j \pi_j π j does not have the period p j / 2 p_j/2 p j /2 . Since the least period of a sequence divides each of its periods, p j p_j p j is the least period of e j e_j e j for these columns. We make no claim of minimality for j ≥ 64 j \ge64 j ≥ 64 .
Use of AI
The author used OpenAI’s ChatGPT 6 Astra to explore the V-toothpick sequence. The first prompt, posed partly in jest, was: “Find a formula or an asymptotic formula for a ( n ) a(n) a ( n ) .“ The AI supplied neither a usable answer nor a reference with directly applicable results. It drew on the OEIS entry and simpler toothpick models without finding a solution for this variant.
The investigation proceeded by trial and error through sustained dialogue. The author directed the search toward direct recurrences, relations for a ( 2 k + i ) a(2^k+i) a ( 2 k + i ) , coupled recurrences involving auxiliary sequences, and comparisons with other OEIS sequences. When these attempts yielded no general formula, he proposed working with generating functions. Several dozen exchanges led to the representation given in this paper, followed by the asymptotic analysis. Progress required repeated attempts and changes of direction, for which the author’s mathematical guidance was essential. With AI assistance, the author developed the proofs of the generating-function and asymptotic results.
The AI also assisted with numerical simulations, \LaTeX formatting, and English expression. The author reviewed the arguments and computations and takes full responsibility for the mathematical content and the final text.