Introduction and statements
An n n n -dimensional recurrence determines an array indexed by N n \mathbb{N}^n N n from prescribed boundary values and values at predecessor points. We ask when the resulting array is p p p -automatic, meaning that a deterministic automaton with finitely many states computes an entry by reading the base-p p p digits of its n n n coordinates together. The existence of a recurrence with finitely many predecessor offsets and automatic boundary data does not by itself imply automaticity of the solution. Both the algebraic rule and the geometry of the predecessor offsets matter.
Prunescu [8 Theorem 5.2] proves automaticity for F p \mathbb{F}_p F p -affine recurrences over finite fields F q \mathbb{F}_q F q of characteristic p p p when predecessor vectors are coordinatewise nonnegative and boundary faces are automatic. He asks [8 Section 7, Open problems 3–5] whether this remains true for predecessor sets with negative entries, for homomorphisms of arbitrary finite abelian p p p -groups, and for both together. We allow finite p p p -groups, meaning finite groups of order a power of p p p , and predecessor vectors with negative entries in one common coordinate. Theorem 1.6 then permits negative entries in further coordinates, provided those coordinates have no positive entries. The rule can be an ordered product of endomorphisms, where an endomorphism is a homomorphism from the group to itself. Theorems 1.2 and 1.3 state the resulting automaticity conclusions.
For these group rules, with a p p p -automatic additional sequence and compatible p p p -automatic boundary data, the dimensions separate as follows. In dimension one, lexicographic positivity requires positive integer offsets. The boundary is a finite initial segment, and the nonnegative construction gives automaticity. § 2.6 states this case and explains the stronger conclusion of eventual periodicity when the additional sequence is constant. In dimension two, the first coordinate of every lexicographically positive vector is nonnegative. Negative entries can therefore occur only in the second coordinate, so Corollary 1.5 covers every such predecessor set. In dimensions at least three, negative entries can occur in several coordinates that also contain positive entries. The counterexample in § 8 shows that lexicographic positivity then ceases to be a sufficient condition. Theorem 1.6 still gives automaticity when at most one coordinate contains both signs. In this sense, three is the first possible dimension of failure under the stated algebraic and data assumptions.
For Prunescu’s questions, Theorem 1.2 gives a positive answer to Open problem 4, retaining the nonnegative predecessor hypothesis of his theorem. Corollary 1.5 answers Open problems 3 and 5 affirmatively in dimension two, and Theorem 1.6 does so in every dimension under its sign condition. § 8 gives counterexamples to the unrestricted assertions in Open problems 3 and 5 in every dimension n ≥ 3 n \ge3 n ≥ 3 , already for F p \mathbb{F}_p F p -linear rules over F p \mathbb{F}_p F p .
Theorem 7.2 treats another sufficient family with negative entries in several coordinates. Its boundary consists of the d d d coordinate slices { x 1 = j } \{x_1=j\} { x 1 = j } for 0 ≤ j < d 0 \le j < d 0 ≤ j < d . Each slice is a copy of N n − 1 \mathbb{N}^{n-1} N n − 1 and is infinite when n ≥ 2 n \ge2 n ≥ 2 . An integer change of coordinates reduces this recurrence to the nonnegative case.
The proof treats the boundary differently according to the predecessor geometry. For nonnegative vectors, the boundary contribution is known and the solution is an automatic series divided by a polynomial with constant coefficient 1 1 1 . We give its automaton by extending the coefficient selection method of Rowland–Yassawi [11 ] from polynomial to automatic numerators. With negative entries, the generating-function equation also contains unknown boundary series. When the negative entries are confined to one coordinate, algebraic Weierstrass division determines those series over a finite field. Reduction modulo successive powers of p p p gives the abelian group case. A central subgroup then reduces a nonabelian group recurrence to a smaller group and an abelian recurrence with an automatic affine term.
Theorem 9.2 gives a second route to an explicit automaton. It samples arrays obtained by fixing the low digits of the indices, called kernel arrays, to construct a candidate. It then checks the recurrence and boundary values at all reachable states. Automaticity guarantees eventual termination, while each accepted candidate has a certificate valid at all indices. A matrix that counts automaton transitions also proves Lauberger’s proposed formula [2 Eq. (10.47)] for the number of nonzero Delannoy residues modulo 27 27 27 in squares of side 3 r 3^r 3 r , for every r ≥ 4 r \ge4 r ≥ 4 .
The scalar algebraic principle for one possible negative direction appears in [15 Theorem 13] , stated over C \mathbb{C} C , and is interpreted through division in [14 ] . Both papers work in characteristic zero. We use division valid in arbitrary characteristic [4 ] and supply the matrix reduction needed for coupled recurrences. The group induction uses the decomposition method of [19 Theorem 4 and Proposition 8(3)] . Related cellular-automaton results appear in [16 , 17 , 18 ] . Nesme [18 Lemma 4] also proves automaticity of convolutions taking values in a finite commutative monoid when each coefficient receives only finitely many nonzero contributions. We need only multiplication by polynomials, which reduces to finite sums of translations by Lemma 2.2. The obstruction adapts the recurrence in [15 Section 4.5, Example 6] .
Fix a prime p p p and put N = { 0 , 1 , … } \mathbb{N} = \{0,1,\ldots\} N = { 0 , 1 , … } . Coordinatewise inequalities are used unless lexicographic order is specified. A vector is lexicographically positive if its first nonzero coordinate is positive. Let
P = { v 1 , … , v m } ⊂ Z n , v j > l e x 0 , d i = max ( 0 , max j ( v j ) i ) , P = \{v_1,\ldots,v_m\} \subset\mathbb{Z}^n,\qquad v_j >_{\mathrm{lex}} 0,\qquad d_i = \max\left(0,\max_j(v_j)_i\right), P = { v 1 , … , v m } ⊂ Z n , v j > lex 0 , d i = max ( 0 , j max ( v j ) i ) ,
where P P P is finite and nonempty. A predecessor of x x x is a point x − v j x-v_j x − v j . The interior and prescribed boundary are
I = d + N n , C = N n ∖ I = ⋃ i = 1 n ⋃ 0 ≤ j < d i { x i = j } . I = \boldsymbol{d}+\mathbb{N}^n,\qquad C = \mathbb{N}^n\setminus I = \bigcup_{i=1}^{n}\bigcup_{0\leq j<d_i}\{x_i=j\}. I = d + N n , C = N n ∖ I = i = 1 ⋃ n 0 ≤ j < d i ⋃ { x i = j } .
At an interior point all required predecessors belong to N n \mathbb{N}^n N n . At a boundary point at least one required predecessor leaves N n \mathbb{N}^n N n . An empty range 0 ≤ j < d i 0\leq j<d_i 0 ≤ j < d i contributes no face. There are ∑ i d i \sum_i d_i ∑ i d i faces. Each face has infinitely many points when n ≥ 2 n\geq2 n ≥ 2 , while for n = 1 n=1 n = 1 the boundary consists of d 1 d_1 d 1 points.
Definition 1.1. A function on N n \mathbb{N}^n N n with a finite output alphabet is p p p -automatic if a finite deterministic automaton with output computes its value by reading the base-p p p digits of all coordinates together, padded to a common length. The output must be invariant under additional zero padding. A boundary function c : C → A c:C\to A c : C → A is automatic on its faces if its restriction to each face x i = j x_i=j x i = j , 0 ≤ j < d i 0\leq j<d_i 0 ≤ j < d i , is an ( n − 1 ) (n-1) ( n − 1 ) -dimensional p p p -automatic function. The values on intersecting faces must agree. A face in dimension one is a single point.
The additional sequence b b b is a prescribed array on N n \mathbb{N}^n N n . In additive notation, b ( x ) b(x) b ( x ) is the affine term of the recurrence. In a rule written multiplicatively, it is the prescribed factor on the right of the ordered product.
Our sufficient geometric condition is
there exists k such that ( v j ) i ≥ 0 for all j and all i ≠ k . (1) \text{there exists }k\text{ such that }(v_j)_i\geq0\text{ for all }j\text{ and all }i\ne k. \tag*{(1)} there exists k such that ( v j ) i ≥ 0 for all j and all i = k . (1)
The coordinate k k k is common to the whole predecessor set. For example, { ( 1 , − 2 ) , ( 0 , 1 ) } \{(1,-2),(0,1)\} {( 1 , − 2 ) , ( 0 , 1 )} satisfies the condition with k = 2 k=2 k = 2 . The set { ( 1 , 2 , − 1 ) , ( 1 , − 1 , 2 ) , ( 2 , 1 , 1 ) } \{(1,2,-1),(1,-1,2),(2,1,1)\} {( 1 , 2 , − 1 ) , ( 1 , − 1 , 2 ) , ( 2 , 1 , 1 )} has negative entries in two different coordinates and does not satisfy the condition. Throughout the statements below, the predecessor set is also assumed to be finite, nonempty and lexicographically positive as specified above.
Theorem 1.2 (Abelian case). Let H H H be a finite abelian p p p -group, h : H m → H h:H^m\to H h : H m → H a homomorphism, and b : N n → H b:\mathbb{N}^n\to H b : N n → H a p p p -automatic function. Suppose P P P satisfies (1) and c : C → H c:C\to H c : C → H is automatic on its faces with compatible values on intersections. Then the unique solution of
a ( x ) = c ( x ) ( x ∈ C ) , a ( x ) = h ( a ( x − v 1 ) , … , a ( x − v m ) ) + b ( x ) ( x ∈ I ) \begin{aligned}
a(x)&=c(x) &&(x\in C),\\
a(x)&=h(a(x-v_1),\ldots,a(x-v_m))+b(x) &&(x\in I)
\end{aligned} a ( x ) a ( x ) = c ( x ) = h ( a ( x − v 1 ) , … , a ( x − v m )) + b ( x ) ( x ∈ C ) , ( x ∈ I ) is p p p -automatic. For coordinatewise nonnegative predecessors, the proof gives an explicit terminating automaton construction from the rule and automata for the data. The term b b b may in particular be constant.
Theorem 1.3 (Finite p p p -groups). Let G G G be a finite p p p -group and let α 1 , … , α m \alpha_1,\ldots,\alpha_m α 1 , … , α m be endomorphisms of G G G . Suppose P P P satisfies (1), b : N n → G b:\mathbb{N}^n \to G b : N n → G is p p p -automatic, and c : C → G c:C \to G c : C → G is automatic on its faces with compatible values on intersections. Then the unique solution of
a ( x ) = c ( x ) ( x ∈ C ) , a ( x ) = α 1 ( a ( x − v 1 ) ) ⋯ α m ( a ( x − v m ) ) b ( x ) ( x ∈ I ) a(x)=c(x)\quad(x\in C),\qquad a(x)=\alpha_1(a(x-v_1))\cdots\alpha_m(a(x-v_m))b(x)\quad(x\in I) a ( x ) = c ( x ) ( x ∈ C ) , a ( x ) = α 1 ( a ( x − v 1 )) ⋯ α m ( a ( x − v m )) b ( x ) ( x ∈ I ) is p p p -automatic. The order of the factors is fixed as displayed.
Corollary 1.4 (Direct-product homomorphism rules). Under the same geometric and data assumptions, the conclusion holds for the rule a ( x ) = h ( a ( x − v 1 ) , … , a ( x − v m ) ) b ( x ) a(x)=h(a(x-v_1),\ldots,a(x-v_m))b(x) a ( x ) = h ( a ( x − v 1 ) , … , a ( x − v m )) b ( x ) when h : G m → G h:G^m\to G h : G m → G is a group homomorphism.
Proof. Define α j ( g ) = h ( 1 , … , g , … , 1 ) \alpha_j(g)=h(1,\ldots,g,\ldots,1) α j ( g ) = h ( 1 , … , g , … , 1 ) using the j j j th input. Each α j \alpha_j α j is an endomorphism, and the product decomposition of a tuple in G m G^m G m gives
h ( g 1 , … , g m ) = α 1 ( g 1 ) ⋯ α m ( g m ) . h(g_1,\ldots,g_m)=\alpha_1(g_1)\cdots\alpha_m(g_m). h ( g 1 , … , g m ) = α 1 ( g 1 ) ⋯ α m ( g m ) .
Theorem 1.3 applies to these endomorphisms.
For a direct-product homomorphism, images of different α j \alpha_j α j commute. Theorem 1.3 allows endomorphisms without that property, including an ordered product of the unmodified inputs.
Corollary 1.5 (Two-dimensional recurrences). Let P ⊂ Z 2 P\subset\mathbb{Z}^2 P ⊂ Z 2 be a finite nonempty set of lexicographically positive predecessor vectors, and define I I I and C C C as above. Let G G G be a finite p p p -group, let α 1 , … , α m \alpha_1,\ldots,\alpha_m α 1 , … , α m be endomorphisms of G G G , and suppose the boundary faces and the additional sequence are p p p -automatic, with compatible boundary values. Then the unique array defined by the ordered-product recurrence in Theorem 1.3 is p p p -automatic. The conclusion includes homomorphisms from G m G^m G m to G G G and the additive abelian rules of Theorem 1.2, without a further sign restriction on P P P .
The proof in Section 6.1 checks the geometric and boundary hypotheses and explains why all planar predecessor systems in this statement are covered.
The number of coordinates containing a negative entry is not itself the boundary difficulty. A coordinate with only nonpositive predecessor entries has width d i = 0 d_i=0 d i = 0 , hence no prescribed boundary face. The following theorem allows such coordinates without restriction.
Theorem 1.6 (At most one coordinate with both signs). Let P ⊂ Z n P\subset\mathbb{Z}^n P ⊂ Z n be finite, nonempty and lexicographically positive. Suppose at most one coordinate i i i satisfies
min j ( v j ) i < 0 < max j ( v j ) i . \min_j (v_j)_i<0<\max_j (v_j)_i. j min ( v j ) i < 0 < j max ( v j ) i . For any finite p p p -group G G G , ordered endomorphisms α 1 , … , α m \alpha_1,\ldots,\alpha_m α 1 , … , α m , compatible automatic boundary faces, and an automatic additional sequence, the unique solution of the recurrence in Theorem 1.3 is p p p -automatic.
Section 7.1 proves the theorem by removing negative entries in coordinates without prescribed boundary faces. The fixed obstruction in Corollary 8.7 has two coordinates with both signs and fails for every prime. Thus the threshold in the theorem cannot be increased using their number alone.
Finite kernels and elementary constructions
Fixing the low digits of the indices leaves another array to compute. The p p p -kernel collects these remaining arrays. A finite kernel will give the states of an automaton, and products of automata will let us combine the prescribed data and test the boundary conditions. The kernel characterization is treated in [5 Section 6.6] , with the multidimensional formulation in [5 Section 14.2] .
Digit words and finite kernels
Write D n = { 0 , … , p − 1 } n \mathcal{D}_n=\{0,\ldots,p-1\}^n D n = { 0 , … , p − 1 } n for the alphabet of digit vectors. For u : N n → A u:\mathbb{N}^n\to A u : N n → A , where A A A is finite, define
u e , r ( x ) = u ( p e x + r ) , K p ( u ) = { u e , r : e ≥ 0 , 0 ≤ r i < p e } . u_{e,r}(x)=u(p^e x+r),\qquad\mathcal{K}_p(u)=\{u_{e,r}:e\geq0,\ 0\leq r_i<p^e\}. u e , r ( x ) = u ( p e x + r ) , K p ( u ) = { u e , r : e ≥ 0 , 0 ≤ r i < p e } .
The array u e , r u_{e,r} u e , r is called a section of u u u . Its indices have their e e e low digits fixed by r r r . For e = 0 e=0 e = 0 , the only choice is r = 0 r=0 r = 0 , so u 0 , 0 = u u_{0,0}=u u 0 , 0 = u .
We write an automaton with output as A = ( Q , q 0 , δ , τ ) \mathcal{A}=(Q,q_0,\delta,\tau) A = ( Q , q 0 , δ , τ ) . Here Q Q Q is its finite state set, q 0 q_0 q 0 is its initial state, δ : Q × D n → Q \delta:Q\times\mathcal{D}_n\to Q δ : Q × D n → Q is its transition map, and τ : Q → A \tau:Q\to A τ : Q → A gives the output of a state. For a word w w w of digit vectors, the extended transition δ ∗ \delta^* δ ∗ means that the letters of w w w are read in their written order. Formally,
δ ∗ ( q , ε ) = q , δ ∗ ( q , w r ) = δ ( δ ∗ ( q , w ) , r ) , \delta^*(q,\varepsilon)=q,\qquad\delta^*(q,wr)=\delta(\delta^*(q,w),r), δ ∗ ( q , ε ) = q , δ ∗ ( q , w r ) = δ ( δ ∗ ( q , w ) , r ) ,
where ε \varepsilon ε denotes the empty word.
The output on a word w w w is A ( w ) = τ ( δ ∗ ( q 0 , w ) ) \mathcal{A}(w)=\tau(\delta^*(q_0,w)) A ( w ) = τ ( δ ∗ ( q 0 , w )) . For w = r 0 ⋯ r ℓ − 1 w=r_0\cdots r_{\ell-1} w = r 0 ⋯ r ℓ − 1 , the represented index is
∑ j = 0 ℓ − 1 p ℓ − 1 − j r j \sum_{j=0}^{\ell-1}p^{\ell-1-j}r_j j = 0 ∑ ℓ − 1 p ℓ − 1 − j r j
when most significant digits are read first,
∑ j = 0 ℓ − 1 p j r j \sum_{j=0}^{\ell-1}p^jr_j j = 0 ∑ ℓ − 1 p j r j
when least significant digits are read first.
Each coordinate has the same word length. Adding a zero digit vector at the most significant end leaves the index unchanged. Thus padding invariance means A ( 0 w ) = A ( w ) \mathcal{A}(0w)=\mathcal{A}(w) A ( 0 w ) = A ( w ) in the first convention and A ( w 0 ) = A ( w ) \mathcal{A}(w0)=\mathcal{A}(w) A ( w 0 ) = A ( w ) in the second. The convention will be specified for each construction.
The empty word represents the zero tuple and has output u ( 0 ) u(0) u ( 0 ) . For a machine already correct on all nonempty padded words, this empty-word convention can be obtained by adding a new initial state with output u ( 0 ) u(0) u ( 0 ) and the same outgoing transitions as the old initial state. Every nonempty word then has its previous output. When the output alphabet is { 0 , 1 } \{0,1\} { 0 , 1 } , we also call the machine a recognizer . It accepts a word if its final output is 1 1 1 .
Lemma 2.1 (Finite-kernel characterization). A finite-valued array u u u is p p p -automatic if and only if K p ( u ) \mathcal{K}_p(u) K p ( u ) is finite. When the kernel is finite, an automaton for u u u has
Q = K p ( u ) , q 0 = u , δ ( v , s ) ( x ) = v ( p x + s ) , τ ( v ) = v ( 0 ) . Q=\mathcal{K}_p(u),\qquad q_0=u,\qquad\delta(v,s)(x)=v(px+s),\qquad\tau(v)=v(0). Q = K p ( u ) , q 0 = u , δ ( v , s ) ( x ) = v ( p x + s ) , τ ( v ) = v ( 0 ) . It reads digits from least to most significant. The two digit-reading conventions define the same class of arrays.
Proof. From a finite kernel to an automaton. First check that a transition remains in Q Q Q . If v = u e , r v=u_{e,r} v = u e , r , then
δ ( v , s ) ( x ) = u ( p e + 1 x + r + p e s ) = u e + 1 , r + p e s ( x ) . \delta(v,\mathbf{s})(x)=u(p^{e+1}x+r+p^e\mathbf{s})=u_{e+1,r+p^e\mathbf{s}}(x). δ ( v , s ) ( x ) = u ( p e + 1 x + r + p e s ) = u e + 1 , r + p e s ( x ) .
Since 0 ≤ r i + p e s i < p e + 1 0\le r_i+p^e s_i<p^{e+1} 0 ≤ r i + p e s i < p e + 1 , this is a member of K p ( u ) K_p(u) K p ( u ) .
Let r 0 , … , r ℓ − 1 \mathbf{r}_0,\ldots,\mathbf{r}_{\ell-1} r 0 , … , r ℓ − 1 be the digit vectors read so far, starting with the least significant ones, and put b ℓ = ∑ j < ℓ p j r j b_\ell=\sum_{j<\ell}p^j\mathbf{r}_j b ℓ = ∑ j < ℓ p j r j . Induction on ℓ \ell ℓ gives the state identity
δ ∗ ( u , r 0 ⋯ r ℓ − 1 ) ( x ) = u ( p ℓ x + b ℓ ) . \delta^*(u,\mathbf{r}_0\cdots\mathbf{r}_{\ell-1})(x)=u(p^\ell x+b_\ell). δ ∗ ( u , r 0 ⋯ r ℓ − 1 ) ( x ) = u ( p ℓ x + b ℓ ) .
The initial case is u ( x ) u(x) u ( x ) , and the transition just computed proves the induction step. At the end of the input, setting x = 0 x=0 x = 0 gives output u ( b ℓ ) u(b_\ell) u ( b ℓ ) , the requested entry. Extra zero digit vectors at the end do not change the output, because δ ( v , 0 ) ( 0 ) = v ( 0 ) \delta(v,\mathbf{0})(0)=v(0) δ ( v , 0 ) ( 0 ) = v ( 0 ) .
From an automaton to a finite kernel. Suppose first that A = ( Q , q 0 , δ , τ ) \mathcal{A}=(Q,q_0,\delta,\tau) A = ( Q , q 0 , δ , τ ) reads most significant digits first. Let w ( x ) w(x) w ( x ) be a padded digit word for x x x , and put q ( x ) = δ ∗ ( q 0 , w ( x ) ) q(x)=\delta^*(q_0,w(x)) q ( x ) = δ ∗ ( q 0 , w ( x )) . For 0 ≤ r i < p e 0\le r_i<p^e 0 ≤ r i < p e , let ρ e ( r ) \rho_e(\mathbf{r}) ρ e ( r ) be the word of exactly e e e digit vectors representing r \mathbf{r} r in that same order, including initial zero vectors where necessary. Appending that word to w ( x ) w(x) w ( x ) represents p e x + r p^e x+\mathbf{r} p e x + r . Define an output map on the existing states by
τ e , r ( q ) = τ ( δ ∗ ( q , ρ e ( r ) ) ) . \tau_{e,\mathbf{r}}(q)=\tau\bigl(\delta^*(q,\rho_e(\mathbf{r}))\bigr). τ e , r ( q ) = τ ( δ ∗ ( q , ρ e ( r )) ) .
Then
u e , r ( x ) = τ e , r ( q ( x ) ) . u_{e,\mathbf{r}}(x)=\tau_{e,\mathbf{r}}(q(x)). u e , r ( x ) = τ e , r ( q ( x )) .
The map x ↦ q ( x ) x\mapsto q(x) x ↦ q ( x ) is fixed. Only the function τ e , r : Q → A \tau_{e,\mathbf{r}}:Q\to A τ e , r : Q → A varies, and there are at most ∣ A ∣ ∣ Q ∣ |A|^{|Q|} ∣ A ∣ ∣ Q ∣ such functions. Thus there are at most that many kernel arrays.
Changing the digit-reading direction. For this equivalence, see also [5 Sections 4.3 and 5.2] . To reverse the reading direction, for a digit vector r \mathbf{r} r write δ r ( q ) = δ ( q , r ) \delta_{\mathbf{r}}(q)=\delta(q,\mathbf{r}) δ r ( q ) = δ ( q , r ) . Use functions η : Q → A \eta:Q\to A η : Q → A as new states, start with η = τ \eta=\tau η = τ , and define
δ ^ ( η , r ) = η ∘ δ r , τ ^ ( η ) = η ( q 0 ) . \widehat{\delta}(\eta,\mathbf{r})=\eta\circ\delta_{\mathbf{r}},\qquad\widehat{\tau}(\eta)=\eta(q_0). δ ( η , r ) = η ∘ δ r , τ ( η ) = η ( q 0 ) .
After the word s 1 ⋯ s ℓ \mathbf{s}_1\cdots\mathbf{s}_\ell s 1 ⋯ s ℓ , the new state is τ ∘ δ s 1 ∘ ⋯ ∘ δ s ℓ \tau\circ\delta_{\mathbf{s}_1}\circ\cdots\circ\delta_{\mathbf{s}_\ell} τ ∘ δ s 1 ∘ ⋯ ∘ δ s ℓ . Its output is the old automaton’s output on the reversed word s ℓ ⋯ s 1 \mathbf{s}_\ell\cdots\mathbf{s}_1 s ℓ ⋯ s 1 . There are at most ∣ A ∣ ∣ Q ∣ |A|^{|Q|} ∣ A ∣ ∣ Q ∣ new states, and they can be enumerated by closing the initial map under the displayed transitions. Reversal exchanges initial zero padding with final zero padding, so the old padding invariance gives the required invariance in the new direction. □
Products and output codings
To compute several arrays at the same index, we run their automata on the same input word. The construction below specifies how the component states and outputs are combined. It is the usual product construction, together with an output map [5 Sections 4.3 and 5.4] .
Definition (Product automaton). Let t ≥ 1 t\ge1 t ≥ 1 , and let A j = ( Q j , q j , δ j , τ j ) \mathcal{A}_j=(Q_j,q_j,\delta_j,\tau_j) A j = ( Q j , q j , δ j , τ j ) , for 1 ≤ j ≤ t 1\le j\le t 1 ≤ j ≤ t , be automata over the same input alphabet D n D_n D n , using the same digit-reading convention. Write A j A_j A j for their output alphabets. Their product automaton is A = ( Q , q 0 , δ , τ ) \mathcal{A}=(Q,q_0,\delta,\tau) A = ( Q , q 0 , δ , τ ) , with
Q = ∏ j = 1 t Q j , q 0 = ( q 1 , … , q t ) , τ : Q → ∏ j = 1 t A j , Q=\prod_{j=1}^{t}Q_j,\qquad q_0=(q_1,\ldots,q_t),\qquad\tau:Q\to\prod_{j=1}^{t}A_j, Q = j = 1 ∏ t Q j , q 0 = ( q 1 , … , q t ) , τ : Q → j = 1 ∏ t A j , and, for r ∈ D n \mathbf{r}\in D_n r ∈ D n ,
δ ( ( s 1 , … , s t ) , r ) = ( δ 1 ( s 1 , r ) , … , δ t ( s t , r ) ) , \delta((s_1,\ldots,s_t),\mathbf{r})=(\delta_1(s_1,\mathbf{r}),\ldots,\delta_t(s_t,\mathbf{r})), δ (( s 1 , … , s t ) , r ) = ( δ 1 ( s 1 , r ) , … , δ t ( s t , r )) , τ ( s 1 , … , s t ) = ( τ 1 ( s 1 ) , … , τ t ( s t ) ) . \tau(s_1,\ldots,s_t)=(\tau_1(s_1),\ldots,\tau_t(s_t)). τ ( s 1 , … , s t ) = ( τ 1 ( s 1 ) , … , τ t ( s t )) .
A product state records one state from each component machine. Induction on the length of w w w gives
δ ∗ ( q 0 , w ) = ( δ 1 ∗ ( q 1 , w ) , … , δ t ∗ ( q t , w ) ) . (2) \delta^*(q_0,w) = \left(\delta_1^*(q_1,w),\ldots,\delta_t^*(q_t,w)\right). \tag*{(2)} δ ∗ ( q 0 , w ) = ( δ 1 ∗ ( q 1 , w ) , … , δ t ∗ ( q t , w ) ) . (2)
Consequently, if A j A_j A j computes u j u_j u j , the product computes x ↦ ( u 1 ( x ) , … , u t ( x ) ) x \mapsto(u_1(x),\ldots,u_t(x)) x ↦ ( u 1 ( x ) , … , u t ( x )) . Its state set has ∏ j ∣ Q j ∣ \prod_j |Q_j| ∏ j ∣ Q j ∣ elements. Padding preserves its output because it preserves every component output. The states themselves may change under padding. If the machines initially use different reading directions, Lemma 2.1 first converts them to a common one.
A coding is a map between finite output alphabets, applied at each index. For any finite set B B B and map h : ∏ j A j → B h:\prod_j A_j \to B h : ∏ j A j → B , replacing the product’s output map τ \tau τ by h ∘ τ h\circ\tau h ∘ τ computes
x ↦ h ( u 1 ( x ) , … , u t ( x ) ) . x \mapsto h(u_1(x),\ldots,u_t(x)). x ↦ h ( u 1 ( x ) , … , u t ( x )) .
The states, initial state and transitions are unchanged. For example, if the A j A_j A j are a common group G G G , the coding h ( a 1 , … , a t ) = a 1 ⋯ a t h(a_1,\ldots,a_t)=a_1\cdots a_t h ( a 1 , … , a t ) = a 1 ⋯ a t computes their ordered product at each index. This applies to a nonabelian group because the order of the factors is fixed. Boolean codings give equality tests and unions, intersections and complements of recognized sets.
A two-dimensional example. In base 2, consider u ( m , n ) = m m o d 2 u(m,n)=m\bmod2 u ( m , n ) = m mod 2 and v ( m , n ) = n m o d 3 v(m,n)=n\bmod3 v ( m , n ) = n mod 3 . Use most significant digits first, with input ( r , s ) ∈ { 0 , 1 } 2 (r,s)\in\{0,1\}^2 ( r , s ) ∈ { 0 , 1 } 2 . The first machine has states { 0 , 1 } \{0,1\} { 0 , 1 } , initial state 0, output equal to its state, and transition a ↦ r a\mapsto r a ↦ r . The second has states { 0 , 1 , 2 } \{0,1,2\} { 0 , 1 , 2 } , initial state 0, output equal to its state, and transition b ↦ 2 b + s ( m o d 3 ) b\mapsto2b+s\pmod3 b ↦ 2 b + s ( mod 3 ) . These transitions follow from appending a binary digit to the corresponding coordinate. The product therefore has six states and transition
( a , b ) → ( r , s ) ( r , 2 b + s m o d 3 ) . (a,b)\xrightarrow{(r,s)}(r,2b+s\bmod3). ( a , b ) ( r , s ) ( r , 2 b + s mod 3 ) .
For ( m , n ) = ( 5 , 2 ) (m,n)=(5,2) ( m , n ) = ( 5 , 2 ) , the padded binary representations are 101 and 010, so the path is
( 0 , 0 ) → ( 1 , 0 ) ( 1 , 0 ) → ( 0 , 1 ) ( 0 , 1 ) → ( 1 , 0 ) ( 1 , 2 ) . (0,0)\xrightarrow{(1,0)}(1,0)\xrightarrow{(0,1)}(0,1)\xrightarrow{(1,0)}(1,2). ( 0 , 0 ) ( 1 , 0 ) ( 1 , 0 ) ( 0 , 1 ) ( 0 , 1 ) ( 1 , 0 ) ( 1 , 2 ) .
The output ( 1 , 2 ) (1,2) ( 1 , 2 ) is ( 5 m o d 2 , 2 m o d 3 ) (5\bmod2,2\bmod3) ( 5 mod 2 , 2 mod 3 ) . Changing the output to h ( a , b ) = 1 h(a,b)=1 h ( a , b ) = 1 if ( a , b ) = ( 0 , 0 ) (a,b)=(0,0) ( a , b ) = ( 0 , 0 ) and 0 otherwise makes the same product a recognizer for the indices where m m m is even and n n n is divisible by 3.
Reachable states and comparison of outputs. A state is reachable if it equals δ ∗ ( q 0 , w ) \delta^*(q_0,w) δ ∗ ( q 0 , w ) for some finite input word w w w , including the empty word. Starting with R 0 = { q 0 } R_0=\{q_0\} R 0 = { q 0 } , form
R h + 1 = R h ∪ { δ ( q , r ) : q ∈ R h , r ∈ D n } . R_{h+1}=R_h\cup\{\delta(q,r):q\in R_h,\ r\in D_n\}. R h + 1 = R h ∪ { δ ( q , r ) : q ∈ R h , r ∈ D n } .
This increasing sequence of subsets of the finite set Q Q Q stabilizes. Induction shows that R h R_h R h contains exactly the states reached by words of length at most h h h , so the stabilized set contains all reachable states. It is closed under transitions. Restricting the machine to this set preserves every output and may reduce the state count below ∏ j ∣ Q j ∣ \prod_j |Q_j| ∏ j ∣ Q j ∣ .
To test whether two machines with the same output alphabet compute the same array, give their product the Boolean output h ( a , b ) = 1 { a = b } h(a,b)=1_{\{a=b\}} h ( a , b ) = 1 { a = b } . The arrays agree at all indices if and only if every reachable product state outputs 1. A reachable state with output 0 supplies a counterexample: retain a word reaching it and decode that word by the chosen digit convention. The same procedure checks any specified relation among finitely many array values. Section 9 applies it to a recurrence and its boundary conditions.
Merging equivalent states. For a fixed reading convention, two states are equivalent if they give the same output after every continuation word. This can also be checked by a finite computation. On the reachable state set, put
q ∼ 0 s ⟺ τ ( q ) = τ ( s ) , q \sim_0 s \Longleftrightarrow\tau(q)=\tau(s), q ∼ 0 s ⟺ τ ( q ) = τ ( s ) ,
and define q ∼ h + 1 s q \sim_{h+1} s q ∼ h + 1 s to mean that q ∼ h s q \sim_h s q ∼ h s and δ ( q , r ) ∼ h δ ( s , r ) \delta(q,r) \sim_h \delta(s,r) δ ( q , r ) ∼ h δ ( s , r ) for every input r r r . Induction on h h h shows that q ∼ h s q \sim_h s q ∼ h s if and only if the outputs agree after all words of length at most h h h . The partitions into equivalence classes successively refine a finite state set, so they stabilize. At stabilization, equivalent states have equal outputs and equivalent successors. They can therefore be replaced by one state per class, with the induced transitions and output.
This operation is called minimization . Distinct classes are separated by some continuation word. Choose a word reaching each class from the initial state. Any machine with the same output on all input words must reach different states on these chosen words, since otherwise it could not distinguish their separating continuations. Thus the quotient has the least possible number of states in the chosen reading convention. This is the minimization used for the counts in § 9.1 .
Face tests, translations and boundary data
Lemma 2.2 (Closure operations). For any positive integer t t t , the tuple of t t t p p p -automatic arrays and any coding of that tuple are p p p -automatic. Fixed-coordinate equality tests, finite unions of boundary faces, and their complements are automatic. If u u u takes values in a finite set with distinguished value 0 0 0 , then, for fixed v ∈ Z n v \in\mathbb{Z}^n v ∈ Z n , its translated zero extension
( T v u ) ( x ) = { u ( x − v ) , x − v ∈ N n , 0 , otherwise (T_vu)(x)=
\begin{cases}
u(x-v), & x-v \in\mathbb{N}^n,\\
0, & \text{otherwise}
\end{cases} ( T v u ) ( x ) = { u ( x − v ) , 0 , x − v ∈ N n , otherwise is automatic. All these constructions are effective.
Proof. Products and output codings. The product construction and the coding argument in § 2.2 prove the first assertion. Their transition tables are obtained directly from those of the input machines.
Face tests. Fix a coordinate i i i and an integer c ≥ 0 c \ge0 c ≥ 0 . To recognize x i = c x_i=c x i = c from least significant digits first, start in state c c c and use the state set { 0 , … , c } ∪ { ⊥ } \{0,\ldots,c\}\cup\{\perp\} { 0 , … , c } ∪ { ⊥ } , where ⊥ \perp ⊥ records a mismatch. On a digit vector r r r , a state a ≠ ⊥ a \ne\perp a = ⊥ moves to ⌊ a / p ⌋ \lfloor a/p\rfloor ⌊ a / p ⌋ if r i r_i r i is the remainder of a a a modulo p p p , and otherwise moves to ⊥ \perp ⊥ . The state ⊥ \perp ⊥ is absorbing. Output 1 in state 0 and 0 in all other states. After ℓ \ell ℓ matching digits, the state is ⌊ c / p ℓ ⌋ \lfloor c/p^\ell\rfloor ⌊ c / p ℓ ⌋ , the part of c c c still to be checked. Thus the output is 1 precisely when the whole input equals c c c in coordinate i i i . The other coordinates are ignored. Products of these machines and Boolean output functions give finite unions, intersections and complements of the face tests.
Translations, including negative coordinates. Take a least-significant-digit automaton A = ( Q , q 0 , δ , τ ) \mathcal{A}=(Q,q_0,\delta,\tau) A = ( Q , q 0 , δ , τ ) for u u u , retaining its reachable states. For q ∈ Q q \in Q q ∈ Q , let u q ( x ) u_q(x) u q ( x ) be the output obtained by starting in state q q q and reading x x x . Its zero extension to Z n \mathbb{Z}^n Z n is denoted by u ~ q \widetilde{u}_q u q . These arrays inherit padding invariance because q q q is reachable from the initial state. We will use states ( q , z ) (q,z) ( q , z ) to represent
q q , z ( x ) = u ~ q ( x + z ) . q_{q,z}(x)=\widetilde{u}_q(x+z). q q , z ( x ) = u q ( x + z ) .
The initial state is ( q 0 , − v ) (q_0,-v) ( q 0 , − v ) , which represents T v u T_vu T v u . For an input digit r ∈ D n r \in D_n r ∈ D n , divide componentwise
r + z = p z ′ + s , 0 ≤ s i < p . (3) r+z=pz'+s,\qquad0\le s_i<p. \tag*{(3)} r + z = p z ′ + s , 0 ≤ s i < p . (3)
The transition is ( q , z ) ↦ ( δ ( q , s ) , z ′ ) (q,z) \mapsto(\delta(q,s),z') ( q , z ) ↦ ( δ ( q , s ) , z ′ ) . Indeed,
g q , z ( p x + r ) = u ~ q ( p ( x + z ′ ) + s ) = u ~ δ ( q , s ) ( x + z ′ ) . g_{q,z}(px+r)=\widetilde{u}_q\bigl(p(x+z')+s\bigr)=\widetilde{u}_{\delta(q,s)}(x+z'). g q , z ( p x + r ) = u q ( p ( x + z ′ ) + s ) = u δ ( q , s ) ( x + z ′ ) .
If a coordinate of x + z ′ x+z' x + z ′ is negative, the same coordinate of p ( x + z ′ ) + s p(x+z')+s p ( x + z ′ ) + s is negative, because s i < p s_i<p s i < p . Both sides are then zero, so the identity covers that case too.
The integer vectors z z z range over a finite set. Put L i = min ( − v i , 0 ) L_i=\min(-v_i,0) L i = min ( − v i , 0 ) and U i = max ( − v i , 0 ) U_i=\max(-v_i,0) U i = max ( − v i , 0 ) . The initial vector belongs to ∏ i [ L i , U i ] \prod_i[L_i,U_i] ∏ i [ L i , U i ] , and
L i ≤ ⌊ z i + r i p ⌋ ≤ U i when L i ≤ z i ≤ U i . L_i\le\left\lfloor\frac{z_i+r_i}{p}\right\rfloor\le U_i\qquad\text{when }L_i\le z_i\le U_i. L i ≤ ⌊ p z i + r i ⌋ ≤ U i when L i ≤ z i ≤ U i .
For the lower bound, use z i + r i ≥ L i z_i+r_i\ge L_i z i + r i ≥ L i and L i ≤ 0 L_i\le0 L i ≤ 0 . For the upper bound, use z i + r i ≤ U i + p − 1 z_i+r_i\le U_i+p-1 z i + r i ≤ U i + p − 1 and the fact that U i U_i U i is a nonnegative integer. Thus the displayed product of integer intervals is invariant under transitions. The output of ( q , z ) (q,z) ( q , z ) is u ~ q ( z ) \widetilde{u}_q(z) u q ( z ) , evaluated by the given automaton when z ∈ N n z\in\mathbb{N}^n z ∈ N n , and set to zero otherwise. The state set has at most ∣ Q ∣ ∏ i ( U i − L i + 1 ) |Q|\prod_i(U_i-L_i+1) ∣ Q ∣ ∏ i ( U i − L i + 1 ) elements. The state identities prove that the machine computes the translated array. Its transition table and outputs are obtained by integer arithmetic and evaluations of the given automaton at those states.
Lemma 2.3 (Boundary assembly). If c : C → H c:C\to H c : C → H is automatic on its faces and the face values agree, its extension c 0 c_0 c 0 by the neutral element to N n ∖ C \mathbb{N}^n\setminus C N n ∖ C is p p p -automatic and can be constructed effectively.
Proof. Write e H e_H e H for the neutral element of H H H , using 0 0 0 in additive notation. Enumerate the faces as
F ℓ = { x : x i ℓ = j ℓ } , 1 ≤ ℓ ≤ s , s = ∑ i = 1 n d i . F_\ell=\{x:x_{i_\ell}=j_\ell\},\qquad1\le\ell\le s,\qquad s=\sum_{i=1}^{n}d_i. F ℓ = { x : x i ℓ = j ℓ } , 1 ≤ ℓ ≤ s , s = i = 1 ∑ n d i .
Since P P P is nonempty and its vectors are lexicographically positive, some d i d_i d i is positive, so s ≥ 1 s\ge1 s ≥ 1 . Let π i : N n → N n − 1 \pi_i:\mathbb{N}^n\to\mathbb{N}^{n-1} π i : N n → N n − 1 delete coordinate i i i , and let c ℓ : N n − 1 → H c_\ell:\mathbb{N}^{n-1}\to H c ℓ : N n − 1 → H be the prescribed array on F ℓ F_\ell F ℓ . Define arrays on the whole orthant by
b ℓ ( x ) = c ℓ ( π i ℓ x ) , χ ℓ ( x ) = 1 F ℓ ( x ) . b_\ell(x)=c_\ell(\pi_{i_\ell}x),\qquad\chi_\ell(x)=\mathbf{1}_{F_\ell}(x). b ℓ ( x ) = c ℓ ( π i ℓ x ) , χ ℓ ( x ) = 1 F ℓ ( x ) .
An automaton for b ℓ b_\ell b ℓ ignores coordinate i ℓ i_\ell i ℓ in each digit vector and runs the automaton for c ℓ c_\ell c ℓ on the remaining coordinates. In dimension one, it simply outputs the prescribed value at the face’s single point. The indicator χ ℓ \chi_\ell χ ℓ is automatic by Lemma 2.2.
To select a value when several faces meet, assign each point to the first face containing it. The corresponding Boolean masks are
μ ℓ ( x ) = χ ℓ ( x ) ∏ h < ℓ ( 1 − χ h ( x ) ) . \mu_\ell(x)=\chi_\ell(x)\prod_{h<\ell}(1-\chi_h(x)). μ ℓ ( x ) = χ ℓ ( x ) h < ℓ ∏ ( 1 − χ h ( x )) .
The masks use ordinary products of Boolean values, so they are automatic { 0 , 1 } \{0,1\} { 0 , 1 } -valued arrays. At a point of C C C , one mask equals 1, namely the mask for the first containing face. Outside C C C , all masks vanish.
Define a coding on the full output alphabet by
Φ ( ( ϵ 1 , … , ϵ s ) , ( g 1 , … , g s ) ) = { g min { ℓ : ϵ ℓ = 1 } , if some ϵ ℓ = 1 , e H , if all ϵ ℓ = 0. \Phi((\epsilon_1,\ldots,\epsilon_s),(g_1,\ldots,g_s))=
\begin{cases}
g_{\min\{\ell:\epsilon_\ell=1\}}, & \text{if some }\epsilon_\ell=1,\\
e_H, & \text{if all }\epsilon_\ell=0.
\end{cases} Φ (( ϵ 1 , … , ϵ s ) , ( g 1 , … , g s )) = { g m i n { ℓ : ϵ ℓ = 1 } , e H , if some ϵ ℓ = 1 , if all ϵ ℓ = 0.
Here each ε ℓ \varepsilon_\ell ε ℓ belongs to { 0 , 1 } \{0,1\} { 0 , 1 } and each g ℓ g_\ell g ℓ belongs to H H H . Choosing the least index also defines Φ \Phi Φ on tuples that never occur as simultaneous machine outputs. For the computed masks,
c 0 ( x ) = Φ ( ( μ ℓ ( x ) ) ℓ = 1 s , ( b ℓ ( x ) ) ℓ = 1 s ) . c_0(x)=\Phi\left((\mu_\ell(x))_{\ell=1}^{s},(b_\ell(x))_{\ell=1}^{s}\right). c 0 ( x ) = Φ ( ( μ ℓ ( x ) ) ℓ = 1 s , ( b ℓ ( x ) ) ℓ = 1 s ) .
The product automaton for all the masks and face arrays, with its output composed with Φ \Phi Φ , therefore computes c 0 c_0 c 0 .
If x x x lies on several faces, compatibility says that the values b ℓ ( x ) b_\ell(x) b ℓ ( x ) on those faces coincide. Hence the selected value agrees with every prescribed restriction. □ \square □
For example, suppose n = 2 n=2 n = 2 and d 1 = d 2 = 1 d_1=d_2=1 d 1 = d 2 = 1 . Write c 1 ( y ) c_1(y) c 1 ( y ) for the data on x = 0 x=0 x = 0 and c 2 ( x ) c_2(x) c 2 ( x ) for the data on y = 0 y=0 y = 0 . Compatibility means c 1 ( 0 ) = c 2 ( 0 ) c_1(0)=c_2(0) c 1 ( 0 ) = c 2 ( 0 ) . Choosing x = 0 x=0 x = 0 first gives
c 0 ( x , y ) = { c 1 ( y ) , x = 0 , c 2 ( x ) , x > 0 , y = 0 , e H , x > 0 , y > 0. c_0(x,y)=
\begin{cases}
c_1(y), & x=0,\\
c_2(x), & x>0,\ y=0,\\
e_H, & x>0,\ y>0.
\end{cases} c 0 ( x , y ) = ⎩ ⎨ ⎧ c 1 ( y ) , c 2 ( x ) , e H , x = 0 , x > 0 , y = 0 , x > 0 , y > 0.
The choice of face order has no effect at the corner because the prescribed values there agree.
Existence and uniqueness
Lemma 2.4 (Existence and uniqueness). Let P = { v 1 , … , v m } P=\{\mathbf{v}_1,\ldots,\mathbf{v}_m\} P = { v 1 , … , v m } be a finite nonempty set of lexicographically positive vectors, with interior I I I and boundary C C C as defined in Section 1. Let A A A be a nonempty set. Any boundary function c : C → A c:C\to A c : C → A and maps h x : A m → A h_x:A^m\to A h x : A m → A for x ∈ I x\in I x ∈ I determine a unique array a : N n → A a:\mathbb{N}^n\to A a : N n → A satisfying
a ( x ) = c ( x ) ( x ∈ C ) , a ( x ) = h x ( a ( x − v 1 ) , … , a ( x − v m ) ) ( x ∈ I ) . a(x)=c(x)\quad(x\in C),\qquad a(x)=h_x\left(a(x-\mathbf{v}_1),\ldots,a(x-\mathbf{v}_m)\right)\quad(x\in I). a ( x ) = c ( x ) ( x ∈ C ) , a ( x ) = h x ( a ( x − v 1 ) , … , a ( x − v m ) ) ( x ∈ I ) .
Proof. We assign an integer weight to each point so that every predecessor has smaller weight. For vectors w , x ∈ Z n w,x\in\mathbb{Z}^n w , x ∈ Z n , the scalar product is w ⋅ x = ∑ i = 1 n w i x i w\cdot x=\sum_{i=1}^{n}w_i x_i w ⋅ x = ∑ i = 1 n w i x i . Choose the positive integer weights backwards by
w n = 1 , w i = 1 + max 1 ≤ j ≤ m ∑ k = i + 1 n w k ∣ ( v j ) k ∣ ( i = n − 1 , … , 1 ) , w_n=1,\qquad w_i=1+\max_{1\leq j\leq m}\sum_{k=i+1}^{n}w_k\lvert(v_j)_k\rvert\quad(i=n-1,\ldots,1), w n = 1 , w i = 1 + 1 ≤ j ≤ m max k = i + 1 ∑ n w k ∣( v j ) k ∣ ( i = n − 1 , … , 1 ) ,
and put w = ( w 1 , … , w n ) w=(w_1,\ldots,w_n) w = ( w 1 , … , w n ) and ρ ( x ) = w ⋅ x \rho(x)=w\cdot x ρ ( x ) = w ⋅ x . The maximum is over the m m m predecessor vectors. If the first nonzero entry of v j v_j v j is in coordinate i i i , that entry is at least 1. Therefore
ρ ( v j ) = w i ( v j ) i + ∑ k > i w k ( v j ) k ≥ w i − ∑ k > i w k ∣ ( v j ) k ∣ ≥ 1. \rho(v_j)=w_i(v_j)_i+\sum_{k>i}w_k(v_j)_k\geq w_i-\sum_{k>i}w_k\lvert(v_j)_k\rvert\geq1. ρ ( v j ) = w i ( v j ) i + k > i ∑ w k ( v j ) k ≥ w i − k > i ∑ w k ∣( v j ) k ∣ ≥ 1.
For i = n i=n i = n , the last inequality follows from w n = 1 w_n=1 w n = 1 .
For each integer N ≥ 0 N\geq0 N ≥ 0 , define
S N = { x ∈ N n : ρ ( x ) ≤ N } , S − 1 = ∅ . S_N=\{x\in\mathbb{N}^n:\rho(x)\leq N\},\qquad S_{-1}=\varnothing. S N = { x ∈ N n : ρ ( x ) ≤ N } , S − 1 = ∅ .
The set S N S_N S N contains finitely many points, because its coordinates satisfy 0 ≤ x i ≤ ⌊ N / w i ⌋ 0\leq x_i\leq\lfloor N/w_i\rfloor 0 ≤ x i ≤ ⌊ N / w i ⌋ . Induct on N N N to assign the values on S N S_N S N , starting with the empty assignment on S − 1 S_{-1} S − 1 . Suppose the values on S N − 1 S_{N-1} S N − 1 are already assigned. For each x ∈ S N ∖ S N − 1 x\in S_N\setminus S_{N-1} x ∈ S N ∖ S N − 1 , prescribe c ( x ) c(x) c ( x ) if x ∈ C x\in C x ∈ C . Otherwise x ∈ I x\in I x ∈ I , so every x − v j x-v_j x − v j belongs to N n \mathbb{N}^n N n and
ρ ( x − v j ) = N − ρ ( v j ) ≤ N − 1. \rho(x-v_j)=N-\rho(v_j)\leq N-1. ρ ( x − v j ) = N − ρ ( v j ) ≤ N − 1.
All inputs to h x h_x h x have thus been assigned, and the rule gives a ( x ) a(x) a ( x ) . Points of weight N N N do not depend on one another. If no point has that weight, then S N = S N − 1 S_N=S_{N-1} S N = S N − 1 and the step adds no values. The induction does not require every integer to occur as a weight.
Every point of N n \mathbb{N}^n N n belongs to some S N S_N S N , so these assignments define a solution on the whole domain. If two solutions agree on S N − 1 S_{N-1} S N − 1 , their prescribed boundary values and their identical inputs to each h x h_x h x make them agree on S N S_N S N . Induction proves uniqueness.
Adjugates and division by a determinant
The generating functions below satisfy matrix equations over commutative rings. To solve those equations, we need a determinant identity that remains valid when the coefficient ring has zero divisors.
Definition 2.5. For an s × s s \times s s × s matrix D D D over a commutative ring, let D ( i , j ) D^{(i,j)} D ( i , j ) be the matrix obtained by deleting row i i i and column j j j . The adjugate of D D D is the transpose of its cofactor matrix, so
( adj D ) i j = ( − 1 ) i + j det D ( j , i ) . (\operatorname{adj} D)_{ij}=(-1)^{i+j}\det D^{(j,i)}. ( adj D ) ij = ( − 1 ) i + j det D ( j , i ) . The determinant of the empty matrix is 1 1 1 . In particular, the adjugate of a 1 × 1 1 \times1 1 × 1 matrix is the 1 × 1 1 \times1 1 × 1 identity matrix.
Lemma 2.6 (Adjugate identity). For a square matrix D D D over a commutative ring A A A ,
D adj D = ( det D ) I s = ( adj D ) D . D\operatorname{adj}D=(\det D)I_s=(\operatorname{adj}D)D. D adj D = ( det D ) I s = ( adj D ) D . If det D \det D det D is invertible in A A A , then D − 1 = ( det D ) − 1 adj D D^{-1}=(\det D)^{-1}\operatorname{adj}D D − 1 = ( det D ) − 1 adj D . If A A A is an integral domain and det D ≠ 0 \det D\ne0 det D = 0 , the same inverse formula holds over its fraction field.
Proof. The ( i , j ) (i,j) ( i , j ) entry of D adj D D\operatorname{adj}D D adj D is ∑ k d i k ( − 1 ) j + k det D ( j , k ) \sum_k d_{ik}(-1)^{j+k}\det D^{(j,k)} ∑ k d ik ( − 1 ) j + k det D ( j , k ) . For i = j i=j i = j , this is the expansion of det D \det D det D along row j j j . For i ≠ j i\ne j i = j , it is the determinant of the matrix obtained by replacing row j j j by row i i i , so it vanishes because two rows coincide. Expansion by columns proves the other identity. These determinant identities use only sums and products in a commutative ring. Multiplication by ( det D ) − 1 (\det D)^{-1} ( det D ) − 1 proves the inverse statements.
For variables X = ( X 1 , … , X n ) \mathbf{X}=(X_1,\ldots,X_n) X = ( X 1 , … , X n ) , the notation A [ [ X ] ] A[[\mathbf{X}]] A [[ X ]] denotes the ring of formal power series with coefficients in A A A . Its sums and products are defined coefficient by coefficient, without a convergence requirement.
Lemma 2.7 (Units in a power-series ring). A series Q ∈ A [ [ X ] ] Q\in A[[\mathbf{X}]] Q ∈ A [[ X ]] over a commutative ring A A A is invertible if and only if Q ( 0 ) Q(0) Q ( 0 ) is invertible in A A A . Consequently, if a polynomial matrix D D D satisfies D ( 0 ) = I s D(0)=I_s D ( 0 ) = I s , then det D \det D det D and D D D are invertible over A [ [ X ] ] A[[\mathbf{X}]] A [[ X ]] .
Proof. The constant coefficient of Q V = 1 QV=1 Q V = 1 gives Q ( 0 ) V ( 0 ) = 1 Q(0)V(0)=1 Q ( 0 ) V ( 0 ) = 1 , proving necessity. Conversely, if c = Q ( 0 ) c=Q(0) c = Q ( 0 ) is invertible, write Q = c ( 1 − W ) Q=c(1-W) Q = c ( 1 − W ) with W ( 0 ) = 0 W(0)=0 W ( 0 ) = 0 . The series c − 1 ∑ r ≥ 0 W r c^{-1}\sum_{r\ge0}W^r c − 1 ∑ r ≥ 0 W r is well-defined because a coefficient of total degree d d d receives terms only from r ≤ d r\le d r ≤ d . Multiplication by Q Q Q gives 1 1 1 . If D ( 0 ) = I s D(0)=I_s D ( 0 ) = I s , then ( det D ) ( 0 ) = 1 (\det D)(0)=1 ( det D ) ( 0 ) = 1 , and the adjugate identity gives the matrix inverse.
In Section 4, the determinant has constant coefficient 1 1 1 , so the inverse is a matrix of formal series even over Z / p e Z \mathbb{Z}/p^e\mathbb{Z} Z / p e Z . In Section 5, a determinant with zero constant coefficient is divided out in a fraction field. The argument there separately establishes that the resulting vector is a formal power series.
The one-dimensional case
When n = 1 n = 1 n = 1 , a lexicographically positive predecessor vector is a positive integer. Write the predecessor offsets as r 1 , … , r m r_1,\ldots,r_m r 1 , … , r m and put d = max j r j d = \max_j r_j d = max j r j . Then the prescribed boundary is the initial segment C = { 0 , … , d − 1 } C = \{0,\ldots,d-1\} C = { 0 , … , d − 1 } . Each boundary face is a single point, so any assignment of these d d d values meets the boundary hypothesis.
Corollary 2.8 (One-dimensional recurrences). Let G G G be a finite p p p -group, let r 1 , … , r m r_1,\ldots,r_m r 1 , … , r m be positive integers, and let α 1 , … , α m \alpha_1,\ldots,\alpha_m α 1 , … , α m be endomorphisms of G G G . For any prescribed a ( 0 ) , … , a ( d − 1 ) ∈ G a(0),\ldots,a(d-1) \in G a ( 0 ) , … , a ( d − 1 ) ∈ G and any p p p -automatic additional sequence b : N → G b:\mathbb{N}\to G b : N → G , the recurrence
a ( k ) = α 1 ( a ( k − r 1 ) ) ⋯ α m ( a ( k − r m ) ) b ( k ) ( k ≥ d ) a(k) = \alpha_1(a(k-r_1))\cdots\alpha_m(a(k-r_m))b(k) \qquad(k \ge d) a ( k ) = α 1 ( a ( k − r 1 )) ⋯ α m ( a ( k − r m )) b ( k ) ( k ≥ d ) has a unique solution, and this solution is p p p -automatic.
Proof. Lemma 2.4 applies with the single weight w 1 = 1 w_1 = 1 w 1 = 1 . All offsets are positive, so the geometric hypothesis of Theorem 1.3 holds. The boundary has d d d points and is automatic on its faces. That theorem therefore gives automaticity. Its proof uses the nonnegative construction in this case, with no algebraic division argument for negative predecessor entries. Section 3.3 writes out a scalar instance of the construction.
If b ( k ) = β b(k) = \beta b ( k ) = β is constant, eventual periodicity follows directly from the finite number of consecutive blocks. For k ≥ d − 1 k \ge d-1 k ≥ d − 1 , put
s k = ( a ( k − d + 1 ) , … , a ( k ) ) ∈ G d . s_k = (a(k-d+1),\ldots,a(k)) \in G^d. s k = ( a ( k − d + 1 ) , … , a ( k )) ∈ G d .
For s = ( g 0 , … , g d − 1 ) s = (g_0,\ldots,g_{d-1}) s = ( g 0 , … , g d − 1 ) , the next entry is
h ( s ) = α 1 ( g d − r 1 ) ⋯ α m ( g d − r m ) β , h(s) = \alpha_1(g_{d-r_1})\cdots\alpha_m(g_{d-r_m})\beta, h ( s ) = α 1 ( g d − r 1 ) ⋯ α m ( g d − r m ) β ,
and the next block is ( g 1 , … , g d − 1 , h ( s ) ) (g_1,\ldots,g_{d-1},h(s)) ( g 1 , … , g d − 1 , h ( s )) . For d = 1 d = 1 d = 1 , this block consists just of h ( s ) h(s) h ( s ) . Thus a fixed map G d → G d G^d \to G^d G d → G d updates the blocks. There are ∣ G ∣ d |G|^d ∣ G ∣ d possible blocks, so two blocks in the first ∣ G ∣ d + 1 |G|^d + 1 ∣ G ∣ d + 1 positions coincide. All subsequent blocks repeat with the same period because the update map is fixed. Reading their last coordinates proves eventual periodicity of a a a . An eventually periodic sequence is automatic in every integer base at least 2. An automaton can test its finite initial segment and compute the index modulo its period for the remaining entries.
For a general automatic b b b , the next block also depends on b ( k + 1 ) b(k+1) b ( k + 1 ) . Repeated blocks alone then give no periodicity conclusion. The automaticity assertion in Corollary 2.8 uses the group rule and the automaticity of b b b .
Automatic series divided by a polynomial
An n n n -dimensional array and its generating series in n n n variables contain the same coefficients. Section operators select coefficients according to the low digits of their indices. In one variable over F p \mathbb{F}_p F p , these are the operators used by Christol, Kamae, Mendès France and Rauzy [6 Section 6, p. 407] , who work more generally over F q \mathbb{F}_q F q in base q q q . We use the name Cartier operators , as in [11 Definition 1.7] , and explain its relation to Cartier’s operator on differential forms after the definition. The product identity will let us compute sections while keeping a fixed denominator.
Fix R = Z / p e Z R = \mathbb{Z}/p^{e}\mathbb{Z} R = Z / p e Z with e ≥ 1 e \ge1 e ≥ 1 , and retain the digit alphabet D n = { 0 , … , p − 1 } n D_n = \{0,\ldots,p-1\}^{n} D n = { 0 , … , p − 1 } n . For X = ( X 1 , … , X n ) \mathbf{X} = (X_1,\ldots,X_n) X = ( X 1 , … , X n ) and a ∈ N n \mathbf{a} \in\mathbb{N}^{n} a ∈ N n , write X a = ∏ i X i a i \mathbf{X}^{\mathbf{a}} = \prod_i X_i^{a_i} X a = ∏ i X i a i . A formal series has the form
F ( X ) = ∑ a ∈ N n f a X a , f a ∈ R . F(\mathbf{X}) = \sum_{\mathbf{a}\in\mathbb{N}^{n}} f_{\mathbf{a}}\mathbf{X}^{\mathbf{a}}, \qquad f_{\mathbf{a}}\in R. F ( X ) = a ∈ N n ∑ f a X a , f a ∈ R .
We write [ X a ] F = f a [\mathbf{X}^{\mathbf{a}}]F = f_{\mathbf{a}} [ X a ] F = f a for coefficient extraction. No analytic convergence is involved. In a product of formal series, each coefficient is a finite sum.
Definition 3.1 (Cartier operator). For r ∈ D n \mathbf{r} \in D_n r ∈ D n , the Cartier operator Λ r \Lambda_{\mathbf{r}} Λ r is the R R R -linear map given by
Λ r F = ∑ x ∈ N n f p x + r X x . \Lambda_{\mathbf{r}}F = \sum_{\mathbf{x}\in\mathbb{N}^{n}} f_{p\mathbf{x}+\mathbf{r}}\mathbf{X}^{\mathbf{x}}. Λ r F = x ∈ N n ∑ f p x + r X x . It selects the coefficients whose index vector has low digit r \mathbf{r} r and divides the remaining indices by p p p after removing that digit. Its coefficient array is the section x ↦ f p x + r \mathbf{x}\mapsto f_{p\mathbf{x}+\mathbf{r}} x ↦ f p x + r . On a monomial the rule is
Λ r ( X a ) = { X ( a − r ) / p , a ≡ r ( m o d p ) , 0 , otherwise , \Lambda_{\mathbf{r} }(\mathbf{X}^{\mathbf{a}}) =
\begin{cases}
\mathbf{X}^{(\mathbf{a}-\mathbf{r})/p}, & \mathbf{a}\equiv\mathbf{r}\pmod p,\\
0, & \text{otherwise},
\end{cases} Λ r ( X a ) = { X ( a − r ) / p , 0 , a ≡ r ( mod p ) , otherwise , with the congruence interpreted coordinatewise.
Relation to Cartier’s operator. Cartier [7 p. 427, formulas (5)] introduces an operator on differential forms in characteristic p p p . In the field F p ( ( X ) ) \mathbb{F}_p((X)) F p (( X )) of formal Laurent series, write a differential form as ω = F ( X ) d X \omega= F(X)\,\mathrm{d}X ω = F ( X ) d X and set d H = H ′ ( X ) d X \mathrm{d}H = H'(X)\,\mathrm{d}X d H = H ′ ( X ) d X for F , H ∈ F p ( ( X ) ) F,H\in\mathbb{F}_p((X)) F , H ∈ F p (( X )) . His additive operator C C C satisfies
C ( H p ω ) = H C ( ω ) , C ( d H ) = 0 , C ( X p − 1 d X ) = d X . C(H^{p}\omega)=HC(\omega), \qquad C(\mathrm{d}H)=0, \qquad C(X^{p-1}\mathrm{d}X)=\mathrm{d}X. C ( H p ω ) = H C ( ω ) , C ( d H ) = 0 , C ( X p − 1 d X ) = d X .
For 0 ≤ r < p − 1 0\le r<p-1 0 ≤ r < p − 1 , the form X r d X X^{r}\mathrm{d}X X r d X is the differential of X r + 1 / ( r + 1 ) X^{r+1}/(r+1) X r + 1 / ( r + 1 ) , so its image is zero. Decomposing a series over F p \mathbb{F}_p F p as F = ∑ r = 0 p − 1 X r ( Λ r F ) p F=\sum_{r=0}^{p-1}X^{r}(\Lambda_rF)^{p} F = ∑ r = 0 p − 1 X r ( Λ r F ) p gives the first identity below. Applying it to X p − 1 − r F X^{p-1-r}F X p − 1 − r F gives the second for 0 ≤ r < p 0\le r<p 0 ≤ r < p :
C ( F d X ) = ( Λ p − 1 F ) d X , C ( X p − 1 − r F d X ) = ( Λ r F ) d X . C(F\,\mathrm{d}X)=(\Lambda_{p-1}F)\,\mathrm{d}X, \qquad C(X^{p-1-r}F\,\mathrm{d}X)=(\Lambda_rF)\,\mathrm{d}X. C ( F d X ) = ( Λ p − 1 F ) d X , C ( X p − 1 − r F d X ) = ( Λ r F ) d X .
These identities explain the association with Cartier. Our definition selects coefficients directly, which also makes sense in several variables and over Z / p e Z \mathbb{Z}/p^{e}\mathbb{Z} Z / p e Z . The arguments below use this coefficient definition and the identities proved next.
For example, in one variable and base 2 2 2 , the two operators are
Λ 0 ( f 0 + f 1 X + f 2 X 2 + ⋯ ) = f 0 + f 2 X + f 4 X 2 + ⋯ , \Lambda_0(f_0+f_1X+f_2X^2+\cdots)=f_0+f_2X+f_4X^2+\cdots, Λ 0 ( f 0 + f 1 X + f 2 X 2 + ⋯ ) = f 0 + f 2 X + f 4 X 2 + ⋯ ,
Λ 1 ( f 0 + f 1 X + f 2 X 2 + ⋯ ) = f 1 + f 3 X + f 5 X 2 + ⋯ . \Lambda_1(f_0+f_1X+f_2X^2+\cdots)=f_1+f_3X+f_5X^2+\cdots. Λ 1 ( f 0 + f 1 X + f 2 X 2 + ⋯ ) = f 1 + f 3 X + f 5 X 2 + ⋯ .
Thus an even-index coefficient and an odd-index coefficient move into different series. The next identity reconstructs F F F from those series. The second identity explains how to select coefficients of a product when one factor uses only powers divisible by p p p .
Lemma 3.2 (Coefficient selection identities). The Cartier operators are R R R -linear. For formal series F , V , W F,V,W F , V , W ,
F ( X ) = ∑ r ∈ D n X r ( Λ r F ) ( X p ) . (4) F(\mathbf{X})=\sum_{\mathbf{r}\in D_n}\mathbf{X}^{\mathbf{r}}(\Lambda_{\mathbf{r}}F)(\mathbf{X}^{p}). \tag*{(4)} F ( X ) = r ∈ D n ∑ X r ( Λ r F ) ( X p ) . (4) Λ r ( V ( X ) W ( X p ) ) = ( Λ r V ) ( X ) W ( X ) . (5) \Lambda_{\mathbf{r}}\bigl(V(\mathbf{X})W(\mathbf{X}^{p})\bigr)=(\Lambda_{\mathbf{r}}V)(\mathbf{X})W(\mathbf{X}). \tag*{(5)} Λ r ( V ( X ) W ( X p ) ) = ( Λ r V ) ( X ) W ( X ) . (5) Here X p = ( X 1 p , … , X n p ) \mathbf{X}^{p}=(X_1^{p},\ldots,X_n^{p}) X p = ( X 1 p , … , X n p ) . If V V V is a polynomial with deg X i V ≤ d i \deg_{X_i}V\le d_i deg X i V ≤ d i , then deg X i Λ r V ≤ ⌊ d i / p ⌋ \deg_{X_i}\Lambda_{\mathbf{r}}V\le\lfloor d_i/p\rfloor deg X i Λ r V ≤ ⌊ d i / p ⌋ whenever the selected polynomial is nonzero.
Proof. For a , b ∈ R a,b \in\mathbb{R} a , b ∈ R and formal series V , W V,W V , W , coefficient selection gives
[ X x ] Λ r ( a V + b W ) = a [ X p x + r ] V + b [ X p x + r ] W . [X^{\mathbf{x}}]\Lambda_r(aV+bW)=a[X^{p\mathbf{x}+\mathbf{r}}]V+b[X^{p\mathbf{x}+\mathbf{r}}]W. [ X x ] Λ r ( aV + bW ) = a [ X p x + r ] V + b [ X p x + r ] W .
This proves linearity. For reconstruction, divide each coordinate of an exponent vector by p p p . There is a unique expression a = p x + r \mathbf{a}=p\mathbf{x}+\mathbf{r} a = p x + r with x ∈ N n \mathbf{x}\in\mathbb{N}^n x ∈ N n and r ∈ D n \mathbf{r}\in D_n r ∈ D n . Grouping the terms of F F F by this remainder gives
F ( X ) = ∑ r ∈ D n ∑ x ∈ N n f p x + r X p x + r = ∑ r ∈ D n X r ( Λ r F ) ( X p ) . F(\mathbf{X})=\sum_{\mathbf{r}\in D_n}\sum_{\mathbf{x}\in\mathbb{N}^n}f_{p\mathbf{x}+\mathbf{r}}\mathbf{X}^{p\mathbf{x}+\mathbf{r}}=\sum_{\mathbf{r}\in D_n}\mathbf{X}^{\mathbf{r}}(\Lambda_rF)(\mathbf{X}^p). F ( X ) = r ∈ D n ∑ x ∈ N n ∑ f p x + r X p x + r = r ∈ D n ∑ X r ( Λ r F ) ( X p ) .
Each monomial appears in one summand, which justifies the identity coefficient by coefficient.
For the product identity, write V = ∑ a v a X a V=\sum_{\mathbf{a}}v_{\mathbf{a}}\mathbf{X}^{\mathbf{a}} V = ∑ a v a X a and W = ∑ b w b X b W=\sum_{\mathbf{b}}w_{\mathbf{b}}\mathbf{X}^{\mathbf{b}} W = ∑ b w b X b . For a fixed x ∈ N n \mathbf{x}\in\mathbb{N}^n x ∈ N n ,
[ X x ] Λ r ( V ( X ) W ( X p ) ) = [ X p x + r ] ( V ( X ) W ( X p ) ) = ∑ a + p b = p x + r v a w b = ∑ 0 ≤ b ≤ x v p ( x − b ) + r w b . \begin{aligned}
[\mathbf{X}^{\mathbf{x}}]\Lambda_r\bigl(V(\mathbf{X})W(\mathbf{X}^p)\bigr)
&=[\mathbf{X}^{p\mathbf{x}+\mathbf{r}}]\bigl(V(\mathbf{X})W(\mathbf{X}^p)\bigr)\\
&=\sum_{\mathbf{a}+p\mathbf{b}=p\mathbf{x}+\mathbf{r}}v_{\mathbf{a}}w_{\mathbf{b}}\\
&=\sum_{0\leq\mathbf{b}\leq\mathbf{x}}v_{p(\mathbf{x}-\mathbf{b})+\mathbf{r}}w_{\mathbf{b}}.
\end{aligned} [ X x ] Λ r ( V ( X ) W ( X p ) ) = [ X p x + r ] ( V ( X ) W ( X p ) ) = a + p b = p x + r ∑ v a w b = 0 ≤ b ≤ x ∑ v p ( x − b ) + r w b .
In the middle sum both exponent vectors are nonnegative. Since 0 ≤ r i < p 0\leq r_i<p 0 ≤ r i < p , its index equation forces b i ≤ x i b_i\leq x_i b i ≤ x i and then a i = p ( x i − b i ) + r i a_i=p(x_i-b_i)+r_i a i = p ( x i − b i ) + r i . The last sum is the coefficient of X x \mathbf{X}^{\mathbf{x}} X x in ( Λ r V ) W (\Lambda_rV)W ( Λ r V ) W , which proves (4).
Finally, if a monomial of V V V survives selection, its exponent in coordinate i i i has the form p x i + r i ≤ d i px_i+r_i\leq d_i p x i + r i ≤ d i . Its new exponent therefore satisfies x i ≤ ⌊ ( d i − r i ) / p ⌋ ≤ ⌊ d i / p ⌋ x_i\leq\lfloor(d_i-r_i)/p\rfloor\leq\lfloor d_i/p\rfloor x i ≤ ⌊( d i − r i ) / p ⌋ ≤ ⌊ d i / p ⌋ . This proves the degree bound.
To obtain an automaton, we need a finite family of series that remains inside the family after each digit selection. The series themselves will be the states. The output of a state will be its constant coefficient, because reading the remaining digits eventually reduces the requested index to zero.
Proposition 3.3 (Cartier construction of an automaton). Suppose a finite set S ⊂ R [ [ X ] ] S\subset R[[\mathbf{X}]] S ⊂ R [[ X ]] contains F F F and satisfies Λ r V ∈ S \Lambda_rV\in S Λ r V ∈ S for all V ∈ S V\in S V ∈ S and r ∈ D n \mathbf{r}\in D_n r ∈ D n . Define
A F = ( S , F , δ , τ ) , δ ( V , r ) = Λ r V , τ ( V ) = [ X 0 ] V . A_F=(S,F,\delta,\tau),\qquad\delta(V,\mathbf{r})=\Lambda_rV,\qquad\tau(V)=[\mathbf{X}^{\mathbf{0}}]V. A F = ( S , F , δ , τ ) , δ ( V , r ) = Λ r V , τ ( V ) = [ X 0 ] V . Then A F A_F A F computes the coefficient array of F F F by reading coordinate digits together from least to most significant.
Proof. Write F = ∑ x f x X x F=\sum_{\mathbf{x}}f_{\mathbf{x}}\mathbf{X}^{\mathbf{x}} F = ∑ x f x X x . After reading the first ℓ \ell ℓ digit vectors r 0 , … , r ℓ − 1 \mathbf{r}_0,\ldots,\mathbf{r}_{\ell-1} r 0 , … , r ℓ − 1 , put
V 0 = F , V ℓ + 1 = Λ r ℓ V ℓ , b ℓ = ∑ j < ℓ p j r j . V_0=F,\qquad V_{\ell+1}=\Lambda_{\mathbf{r}_\ell}V_\ell,\qquad\mathbf{b}_\ell=\sum_{j<\ell}p^j\mathbf{r}_j. V 0 = F , V ℓ + 1 = Λ r ℓ V ℓ , b ℓ = j < ℓ ∑ p j r j .
The state remains in S S S by the closure assumption. We prove the coefficient identity
[ X x ] V ℓ = f p ℓ x + b ℓ ( x ∈ N n ) . (6) [\mathbf{X}^{\mathbf{x}}]V_\ell=f_{p^\ell\mathbf{x}+\mathbf{b}_\ell}\qquad(\mathbf{x}\in\mathbb{N}^n). \tag*{(6)} [ X x ] V ℓ = f p ℓ x + b ℓ ( x ∈ N n ) . (6)
For ℓ = 0 \ell=0 ℓ = 0 , it is the definition of F F F . If it holds for ℓ \ell ℓ , then
[ X x ] V ℓ + 1 = [ X p x + r ℓ ] V ℓ = f p ℓ ( p x + r ℓ ) + b ℓ = f p ℓ + 1 x + b ℓ + 1 , \begin{aligned}
[\mathbf{X}^{\mathbf{x}}]V_{\ell+1}
&=[\mathbf{X}^{p\mathbf{x}+\mathbf{r}_\ell}]V_\ell\\
&=f_{p^\ell(p\mathbf{x}+\mathbf{r}_\ell)+\mathbf{b}_\ell}\\
&=f_{p^{\ell+1}\mathbf{x}+\mathbf{b}_{\ell+1}},
\end{aligned} [ X x ] V ℓ + 1 = [ X p x + r ℓ ] V ℓ = f p ℓ ( p x + r ℓ ) + b ℓ = f p ℓ + 1 x + b ℓ + 1 ,
which proves the induction step. If the full input has length L L L and represents m m m , then b L = m \mathbf{b}_L=m b L = m . (6) at x = 0 \mathbf{x}=\mathbf{0} x = 0 gives τ ( V L ) = f m \tau(V_L)=f_m τ ( V L ) = f m . Appending a zero digit vector preserves the output because [ X 0 ] Λ 0 V = [ X 0 ] V [\mathbf{X}^{\mathbf{0}}]\Lambda_{\mathbf{0}}V=[\mathbf{X}^{\mathbf{0}}]V [ X 0 ] Λ 0 V = [ X 0 ] V .
This is the machine of Lemma 2.1 expressed in terms of generating series. To implement it, one needs a finite list of state representatives, their constant coefficients, and an exact identity for each transition Λ r V \Lambda_r V Λ r V . Those identities give the complete transition table. Starting from F F F , one may discard states that are never reached. The next example computes the list and all transitions directly. Theorem 3.5 represents states by polynomial tuples and bounds the number of such tuples.
A complete example: Pascal’s triangle modulo 2
We construct the automaton for the array
b ( n , k ) = ( n k ) m o d 2 , n , k ∈ N , b(n,k) = \binom{n}{k} \bmod2,\qquad n,k \in\mathbb{N}, b ( n , k ) = ( k n ) mod 2 , n , k ∈ N ,
where ( n k ) = 0 \binom{n}{k} = 0 ( k n ) = 0 for k > n k > n k > n . The first coordinate n n n is the row number and the second coordinate k k k is the column number. The boundary values are b ( n , 0 ) = 1 b(n,0) = 1 b ( n , 0 ) = 1 for all n n n and b ( 0 , k ) = 0 b(0,k) = 0 b ( 0 , k ) = 0 for k > 0 k > 0 k > 0 . Pascal’s identity gives
b ( n , k ) = b ( n − 1 , k ) + b ( n − 1 , k − 1 ) ( n , k ≥ 1 ) b(n,k) = b(n-1,k) + b(n-1,k-1)\qquad(n,k \ge1) b ( n , k ) = b ( n − 1 , k ) + b ( n − 1 , k − 1 ) ( n , k ≥ 1 )
in F 2 \mathbb{F}_2 F 2 . Table 1 displays the first eight rows, including the zeros beyond the end of each row.
Table 1. The values b ( n , k ) = ( n k ) m o d 2 b(n,k) = \binom{n}{k} \bmod2 b ( n , k ) = ( k n ) mod 2 for 0 ≤ n , k < 8 0 \le n,k < 8 0 ≤ n , k < 8 . Rows are indexed by n n n and columns by k k k . Entries with k > n k > n k > n are zero. The automaton in Table 2 computes the whole infinite array.
The generating function. Work in F 2 [ [ X , Y ] ] \mathbb{F}_2[[X,Y]] F 2 [[ X , Y ]] . By the binomial theorem, the polynomial for row n n n is ∑ k ≥ 0 b ( n , k ) Y k = ( 1 + Y ) n \sum_{k\ge0} b(n,k)Y^k = (1+Y)^n ∑ k ≥ 0 b ( n , k ) Y k = ( 1 + Y ) n . Thus the generating series is
F ( X , Y ) = ∑ n , k ≥ 0 b ( n , k ) X n Y k = ∑ n ≥ 0 ( X ( 1 + Y ) ) n = 1 1 + X + X Y . F(X,Y) = \sum_{n,k\ge0} b(n,k)X^nY^k = \sum_{n\ge0}\bigl(X(1+Y)\bigr)^n = \frac{1}{1+X+XY}. F ( X , Y ) = n , k ≥ 0 ∑ b ( n , k ) X n Y k = n ≥ 0 ∑ ( X ( 1 + Y ) ) n = 1 + X + X Y 1 .
The geometric sum is valid formally because X ( 1 + Y ) X(1+Y) X ( 1 + Y ) has zero constant coefficient. Write Q ( X , Y ) = 1 + X + X Y Q(X,Y) = 1+X+XY Q ( X , Y ) = 1 + X + X Y , so F = 1 / Q F = 1/Q F = 1/ Q . The constant coefficient of Q Q Q is 1 1 1 , which makes this division valid by Lemma 2.7 .
All four Cartier images. There are four input digits, ( r , s ) ∈ { 0 , 1 } 2 (r,s) \in\{0,1\}^2 ( r , s ) ∈ { 0 , 1 } 2 , where r r r is a digit of n n n and s s s is a digit of k k k . In characteristic 2 2 2 , squaring gives
Q ( X , Y ) 2 = 1 + X 2 + X 2 Y 2 = Q ( X 2 , Y 2 ) . Q(X,Y)^2 = 1+X^2+X^2Y^2 = Q(X^2,Y^2). Q ( X , Y ) 2 = 1 + X 2 + X 2 Y 2 = Q ( X 2 , Y 2 ) .
It follows that
F ( X , Y ) = Q ( X , Y ) Q ( X 2 , Y 2 ) = Q ( X , Y ) F ( X 2 , Y 2 ) . F(X,Y)=\frac{Q(X,Y)}{Q(X^{2},Y^{2})}=Q(X,Y)F(X^{2},Y^{2}). F ( X , Y ) = Q ( X 2 , Y 2 ) Q ( X , Y ) = Q ( X , Y ) F ( X 2 , Y 2 ) .
Apply (5) with V = Q V=Q V = Q and W = F W=F W = F to obtain
Λ r , s F = ( Λ r , s Q ) F . \Lambda_{r,s}F=(\Lambda_{r,s}Q)F. Λ r , s F = ( Λ r , s Q ) F .
The monomials 1 1 1 , X X X and X Y XY X Y of Q Q Q have remainder vectors ( 0 , 0 ) (0,0) ( 0 , 0 ) , ( 1 , 0 ) (1,0) ( 1 , 0 ) and ( 1 , 1 ) (1,1) ( 1 , 1 ) , respectively. Their exponents become ( 0 , 0 ) (0,0) ( 0 , 0 ) after selection. There is no monomial with remainder ( 0 , 1 ) (0,1) ( 0 , 1 ) . Consequently,
Λ 0 , 0 Q = 1 , Λ 0 , 1 Q = 0 , Λ 1 , 0 Q = 1 , Λ 1 , 1 Q = 1. \Lambda_{0,0}Q=1,\qquad\Lambda_{0,1}Q=0,\qquad\Lambda_{1,0}Q=1,\qquad\Lambda_{1,1}Q=1. Λ 0 , 0 Q = 1 , Λ 0 , 1 Q = 0 , Λ 1 , 0 Q = 1 , Λ 1 , 1 Q = 1.
Therefore the four images of F F F are F , 0 , F , F F,0,F,F F , 0 , F , F , in that order. All four images of the zero series are zero. The family S = { F , 0 } \mathcal{S}=\{F,0\} S = { F , 0 } is closed under the Cartier operators, so Proposition 3.3 applies.
The complete automaton. Label the state representing F F F by q F q_F q F and the state representing the zero series by q Z q_Z q Z . The initial state is q F q_F q F , and the outputs are τ ( q F ) = F ( 0 , 0 ) = 1 \tau(q_F)=F(0,0)=1 τ ( q F ) = F ( 0 , 0 ) = 1 and τ ( q Z ) = 0 \tau(q_Z)=0 τ ( q Z ) = 0 . Table 2 lists every transition. In particular, once the digit pair ( 0 , 1 ) (0,1) ( 0 , 1 ) is read in state q F q_F q F , the machine enters q Z q_Z q Z and remains there.
Table 2. The two-state Cartier automaton for ( n k ) \binom{n}{k} ( k n ) mod 2. The initial state is q F q_F q F . The first and second components of each input pair are binary digits of n n n and k k k , respectively. Pairs are read from least to most significant. The four middle columns give successor states. The last column gives the output when the input ends.
For example, 5 = ( 101 ) 2 5=(101)_2 5 = ( 101 ) 2 and 1 = ( 001 ) 2 1=(001)_2 1 = ( 001 ) 2 . Reading from the low digits gives the pairs ( 1 , 1 ) , ( 0 , 0 ) , ( 1 , 0 ) (1,1),(0,0),(1,0) ( 1 , 1 ) , ( 0 , 0 ) , ( 1 , 0 ) and the path
q F → ( 1 , 1 ) q F → ( 0 , 0 ) q F → ( 1 , 0 ) q F . q_F \xrightarrow{(1,1)} q_F \xrightarrow{(0,0)} q_F \xrightarrow{(1,0)} q_F. q F ( 1 , 1 ) q F ( 0 , 0 ) q F ( 1 , 0 ) q F .
The output is 1, in agreement with ( 5 1 ) = 5 \binom{5}{1}=5 ( 1 5 ) = 5 modulo 2. For 5 = ( 101 ) 2 5=(101)_2 5 = ( 101 ) 2 and 2 = ( 010 ) 2 2=(010)_2 2 = ( 010 ) 2 , the path is
q F → ( 1 , 0 ) q F → ( 0 , 1 ) q Z → ( 1 , 0 ) q Z . q_F \xrightarrow{(1,0)} q_F \xrightarrow{(0,1)} q_Z \xrightarrow{(1,0)} q_Z. q F ( 1 , 0 ) q F ( 0 , 1 ) q Z ( 1 , 0 ) q Z .
Its output is 0, in agreement with ( 5 2 ) = 10 \binom{5}{2}=10 ( 2 5 ) = 10 modulo 2. Additional digit pairs ( 0 , 0 ) (0,0) ( 0 , 0 ) preserve the output in both states.
What the states mean for the whole array. Equating coefficients in the four Cartier identities gives
b ( 2 n , 2 k ) = b ( n , k ) , b ( 2 n , 2 k + 1 ) = 0 , b ( 2 n + 1 , 2 k ) = b ( n , k ) , b ( 2 n + 1 , 2 k + 1 ) = b ( n , k ) . \begin{aligned}
b(2n,2k)&=b(n,k), & b(2n,2k+1)&=0,\\
b(2n+1,2k)&=b(n,k), & b(2n+1,2k+1)&=b(n,k).
\end{aligned} b ( 2 n , 2 k ) b ( 2 n + 1 , 2 k ) = b ( n , k ) , = b ( n , k ) , b ( 2 n , 2 k + 1 ) b ( 2 n + 1 , 2 k + 1 ) = 0 , = b ( n , k ) .
These identities hold for all n , k ≥ 0 n,k\geq0 n , k ≥ 0 , including positions above the triangle. If n = ∑ j 2 j n j n=\sum_j 2^j n_j n = ∑ j 2 j n j and k = ∑ j 2 j k j k=\sum_j 2^j k_j k = ∑ j 2 j k j , the transition table therefore says
b ( n , k ) = 1 ⟺ k j ≤ n j for every j . b(n,k)=1\Longleftrightarrow k_j\leq n_j\text{ for every }j. b ( n , k ) = 1 ⟺ k j ≤ n j for every j .
This follows from the proved identities for formal series and applies to all indices. The two states are both reachable and have different outputs, so a one-state automaton cannot compute this array.
Finite polynomial states for division
The denominator argument below is the Cartier construction in [11 Proposition 1.9 and the proof of Theorem 2.1] , in the form of [11 Theorem 5.1] that keeps all variables, adapted to a tuple of automatic numerator series. We will use the reconstruction identity to separate their low digits and the product identity to preserve a common denominator. Lemma 2.7 justifies division by any polynomial with constant coefficient 1 over R [ [ X ] ] R[[X]] R [[ X ]] .
Lemma 3.4. For any Q ∈ R [ X ] Q \in R[X] Q ∈ R [ X ] and E = p e − 1 E = p^{e-1} E = p e − 1 ,
Q ( X ) p E = Q ( X p ) E in R [ X ] . Q(X)^{p^E} = Q(X^p)^E \quad\text{in } R[X]. Q ( X ) p E = Q ( X p ) E in R [ X ] . Proof. Lift coefficients to integers. Modulo p p p , the binomial theorem and Fermat’s congruence give Q ( X ) p ≡ Q ( X p ) Q(X)^p \equiv Q(X^p) Q ( X ) p ≡ Q ( X p ) . If A ≡ B A \equiv B A ≡ B modulo p j p^j p j , j ≥ 1 j \ge1 j ≥ 1 , the binomial expansion of ( B + p j C ) p (B + p^jC)^p ( B + p j C ) p gives A p ≡ B p A^p \equiv B^p A p ≡ B p modulo p j + 1 p^{j+1} p j + 1 . Iterating this e − 1 e-1 e − 1 times gives the displayed equality modulo p e p^e p e .
Theorem 3.5 (Explicit division construction). Let U ∈ R [ [ X ] ] U \in R[[X]] U ∈ R [[ X ]] have M M M distinct arrays in its p p p -kernel, and let Q ∈ R [ X ] Q \in R[X] Q ∈ R [ X ] have Q ( 0 ) = 1 Q(0)=1 Q ( 0 ) = 1 . Put
E = p e − 1 , d i = deg X i Q , V = ∏ i = 1 n ( E d i + 1 ) . E=p^{e-1},\qquad d_i=\deg_{X_i}Q,\qquad V=\prod_{i=1}^{n}(Ed_i+1). E = p e − 1 , d i = deg X i Q , V = i = 1 ∏ n ( E d i + 1 ) . Then U / Q U/Q U / Q is p p p -automatic and has a least-significant-digit automaton with at most
∣ R ∣ M V = p e M V (7) \lvert R\rvert^{MV}=p^{eMV} \tag*{(7)} ∣ R ∣ M V = p e M V (7) states. The transitions and outputs can be constructed from the kernel transitions of U U U and the coefficients of Q Q Q .
Proof. State representatives and the initial state. List the kernel series as U 1 , … , U M U_1,\ldots,U_M U 1 , … , U M , with U 1 = U U_1=U U 1 = U . Record their transitions by the index map σ \sigma σ , defined by
Λ s U j = U σ ( j , s ) ( 1 ≤ j ≤ M , s ∈ D n ) . \Lambda_sU_j=U_{\sigma(j,s)}\qquad(1\le j\le M,\ s\in\mathcal{D}_n). Λ s U j = U σ ( j , s ) ( 1 ≤ j ≤ M , s ∈ D n ) .
Let P \mathcal{P} P be the finite set of polynomial tuples P = ( P 1 , … , P M ) \mathbf{P}=(P_1,\ldots,P_M) P = ( P 1 , … , P M ) such that deg X i P j ≤ E d i \deg_{X_i}P_j\le Ed_i deg X i P j ≤ E d i for all i , j i,j i , j . A tuple represents the formal series
F P = ∑ j = 1 M P j U j Q E . (8) F_{\mathbf{P}}=\frac{\sum_{j=1}^{M}P_jU_j}{Q^E}. \tag*{(8)} F P = Q E ∑ j = 1 M P j U j . (8)
The initial tuple is P i n i t = ( Q E − 1 , 0 , … , 0 ) \mathbf{P}^{\mathrm{init}}=(Q^{E-1},0,\ldots,0) P init = ( Q E − 1 , 0 , … , 0 ) . It satisfies the degree bounds and represents U / Q U/Q U / Q .
Computing a transition. Fix an input digit r ∈ D n r\in\mathcal{D}_n r ∈ D n . We seek a tuple P ′ \mathbf{P}' P ′ representing Λ r F P \Lambda_rF_{\mathbf{P}} Λ r F P . Put B = Q ( p − 1 ) E B=Q^{(p-1)E} B = Q ( p − 1 ) E . Lemma 3.4 gives Q E B = Q ( X p ) E Q^EB=Q(X^p)^E Q E B = Q ( X p ) E , while (3) gives
U j ( X ) = ∑ s ∈ D n X s U σ ( j , s ) ( X p ) . U_j(X)=\sum_{s\in\mathcal{D}_n}X^sU_{\sigma(j,s)}(X^p). U j ( X ) = s ∈ D n ∑ X s U σ ( j , s ) ( X p ) .
Multiply numerator and denominator of (7) by B B B , and substitute these expressions for the U j U_j U j . Then
F P = ∑ j , s X s P j B U σ ( j , s ) ( X p ) Q ( X p ) E = ∑ j , s X s P j B ( U σ ( j , s ) Q E ) ( X p ) . \begin{aligned}
F_{\mathbf{P}}=\frac{\sum_{j,s}X^sP_jB\,U_{\sigma(j,s)}(X^p)}{Q(X^p)^E} \\
&=\sum_{j,s}X^sP_jB\left(\frac{U_{\sigma(j,s)}}{Q^E}\right)(X^p).
\end{aligned} F P = Q ( X p ) E ∑ j , s X s P j B U σ ( j , s ) ( X p ) = j , s ∑ X s P j B ( Q E U σ ( j , s ) ) ( X p ) .
Here and below, j j j ranges over 1 , … , M 1,\ldots,M 1 , … , M and s s s over D n \mathcal{D}_n D n . The formal quotients exist because Q ( 0 ) = 1 Q(0)=1 Q ( 0 ) = 1 . Applying (4) to each summand yields
Λ r F P = ∑ j , s Λ r ( X s P j B ) U σ ( j , s ) Q E . \Lambda_rF_{\mathbf{P}}=\frac{\sum_{j,s}\Lambda_r(X^sP_jB)U_{\sigma(j,s)}}{Q^E}. Λ r F P = Q E ∑ j , s Λ r ( X s P j B ) U σ ( j , s ) .
Group the terms multiplying the same series U ℓ U_\ell U ℓ . The resulting transition is δ ( P , r ) = P ′ \delta(\mathbf{P},r)=\mathbf{P}' δ ( P , r ) = P ′ , where
P ℓ ′ = ∑ j , s σ ( j , s ) = ℓ Λ r ( X s P j B ) . (9) P'_\ell=\sum_{\substack{j,s\\\sigma(j,s)=\ell}}\Lambda_r(X^sP_jB). \tag*{(9)} P ℓ ′ = j , s σ ( j , s ) = ℓ ∑ Λ r ( X s P j B ) . (9)
Thus F P ′ = Λ r F P F_{\mathbf{P}'}=\Lambda_rF_{\mathbf{P}} F P ′ = Λ r F P . Why the state set is finite and closed. The degree of X s P j B X^{s}P_jB X s P j B in X i X_i X i is at most
( p − 1 ) + E d i + ( p − 1 ) E d i = p E d i + p − 1. (p-1)+Ed_i+(p-1)Ed_i=pEd_i+p-1. ( p − 1 ) + E d i + ( p − 1 ) E d i = pE d i + p − 1.
Lemma 3.2 bounds the degree after selection by ⌊ ( p E d i + p − 1 ) / p ⌋ = E d i \lfloor(pEd_i+p-1)/p\rfloor=Ed_i ⌊( pE d i + p − 1 ) / p ⌋ = E d i . Summing the selected polynomials does not increase this bound, so P ′ \mathbf{P}' P ′ belongs to P \mathcal{P} P . There are V = ∏ i ( E d i + 1 ) V=\prod_i(Ed_i+1) V = ∏ i ( E d i + 1 ) possible monomials in each component P j P_j P j , each with a coefficient in R R R . Therefore ∣ P ∣ = ∣ R ∣ M V |\mathcal{P}|=|R|^{MV} ∣ P ∣ = ∣ R ∣ M V .
Outputs and termination of the construction. Assign the output
τ ( P ) = [ X 0 ] F P = ∑ j = 1 M P j ( 0 ) U j ( 0 ) . \tau(\mathbf{P})=[X^0]F_{\mathbf{P}}=\sum_{j=1}^{M}P_j(0)U_j(0). τ ( P ) = [ X 0 ] F P = j = 1 ∑ M P j ( 0 ) U j ( 0 ) .
The last equality uses Q ( 0 ) = 1 Q(0)=1 Q ( 0 ) = 1 . Starting with P i n i t \mathbf{P}^{\mathrm{init}} P init , compute its successors for all p n p^n p n input digits using (9) . Repeat for new tuples, identifying tuples by their polynomial coefficient lists. The process adds at most ∣ R ∣ M V |R|^{MV} ∣ R ∣ M V tuples and therefore terminates.
Different tuples may represent the same series. The transition identity still gives the coefficient invariant (6) for the represented series, so the proof of Proposition 3.3 gives the required outputs at all indices. The bound counts the polynomial tuples before any further minimization.
Remark 3.6 (Obtaining the numerator’s kernel). Given a most-significant-digit automaton for U U U , enumerate the output maps produced by all finite suffixes as in Lemma 2.1 . At most ∣ R ∣ ∣ Q ∣ |R|^{|Q|} ∣ R ∣ ∣ Q ∣ distinct output maps can occur, where Q Q Q is the given state set. Each such map represents a section of U U U , and composition with a digit transition gives its successor. Redundant states may be merged by ordinary finite-automaton minimization. The construction uses the given transition table and output map to enumerate all reachable maps. Bound (7) also holds with the number of states in any such section presentation in place of the exact kernel size M M M .
A one-dimensional affine recurrence
To apply the construction in one dimension, take R = Z / p e Z R=\mathbb{Z}/p^e\mathbb{Z} R = Z / p e Z , a p p p -automatic sequence b : N → R b:\mathbb{N}\to R b : N → R , and the recurrence
a ( 0 ) = c , a ( k ) = a ( k − 1 ) + b ( k ) ( k ≥ 1 ) . a(0)=c,\qquad a(k)=a(k-1)+b(k)\qquad(k\geq1). a ( 0 ) = c , a ( k ) = a ( k − 1 ) + b ( k ) ( k ≥ 1 ) .
Let A ( X ) = ∑ k ≥ 0 a ( k ) X k A(X)=\sum_{k\geq0}a(k)X^k A ( X ) = ∑ k ≥ 0 a ( k ) X k and B ( X ) = ∑ k ≥ 0 b ( k ) X k B(X)=\sum_{k\geq0}b(k)X^k B ( X ) = ∑ k ≥ 0 b ( k ) X k . Summing the recurrence for k ≥ 1 k\geq1 k ≥ 1 gives A − c = X A + B − b ( 0 ) A-c=XA+B-b(0) A − c = X A + B − b ( 0 ) , hence
A ( X ) = c + B ( X ) − b ( 0 ) 1 − X . A(X)=\frac{c+B(X)-b(0)}{1-X}. A ( X ) = 1 − X c + B ( X ) − b ( 0 ) .
The numerator has automatic coefficients. It is obtained from b b b by replacing its value at 0 with c c c , an operation covered by Lemma 2.2 . The denominator has constant coefficient 1, so Theorem 3.5 constructs an automaton for a a a . If the numerator has M M M kernel sequences, its polynomial states are tuples ( P 1 , … , P M ) (P_1,\ldots,P_M) ( P 1 , … , P M ) with deg P j ≤ p e − 1 \deg P_j\leq p^e-1 deg P j ≤ p e − 1 . There are at most p e M ( p e − 1 + 1 ) p^{eM(p^e-1+1)} p e M ( p e − 1 + 1 ) such tuples. Their transitions are given by (9) with a single digit r ∈ { 0 , … , p − 1 } r\in\{0,\ldots,p-1\} r ∈ { 0 , … , p − 1 } .
For constant b ( k ) = β b(k)=\beta b ( k ) = β , the solution is a ( k ) = c + k β a(k)=c+k\beta a ( k ) = c + k β in R R R , which has period dividing p e p^e p e . With a general automatic b b b , the same construction computes its partial sums modulo p e p^e p e .
The constructive proof for nonnegative predecessors
Throughout this section assume P ⊂ N n ∖ { 0 } P \subset\mathbb{N}^{n} \setminus\{0\} P ⊂ N n ∖ { 0 } . Section 5 will supply the additional argument for the full hypothesis (1).
A product of equal-order cyclic groups
First take H = R s H = R^{s} H = R s , R = Z / p e Z R = \mathbb{Z}/p^{e}\mathbb{Z} R = Z / p e Z . A homomorphism h : H m → H h : H^{m} \to H h : H m → H has the form
h ( z 1 , … , z m ) = ∑ j = 1 m A j z j , A j ∈ M s ( R ) , h(z_{1}, \ldots, z_{m}) = \sum_{j=1}^{m} A_{j}z_{j}, \qquad A_{j} \in M_{s}(R), h ( z 1 , … , z m ) = j = 1 ∑ m A j z j , A j ∈ M s ( R ) ,
with column-vector conventions. Let c 0 c_{0} c 0 be the automatic zero extension of the boundary, as in Lemma 2.3. Define the boundary correction γ \gamma γ and the source array r r r by
γ ( x ) = 1 C ( x ) ( c 0 ( x ) − ∑ j A j ( T v j c 0 ) ( x ) ) , r ( x ) = γ ( x ) + 1 I ( x ) b ( x ) . (10) \gamma(x) = 1_{C}(x)\left(c_{0}(x) - \sum_{j} A_{j}(T_{v_{j}}c_{0})(x)\right), \qquad r(x) = \gamma(x) + 1_{I}(x)b(x). \tag*{(10)} γ ( x ) = 1 C ( x ) ( c 0 ( x ) − j ∑ A j ( T v j c 0 ) ( x ) ) , r ( x ) = γ ( x ) + 1 I ( x ) b ( x ) . (10)
On C C C , the correction records the difference between the prescribed value and the sum of its predecessor contributions, with values outside N n \mathbb{N}^{n} N n set to zero. On I I I , it vanishes. Its support can be infinite, since a boundary face is infinite when n ≥ 2 n \ge2 n ≥ 2 . Every coordinate of γ \gamma γ and r r r is automatic by the closure lemmas.
If x ∈ C x \in C x ∈ C and x − v j ∈ N n x - v_{j} \in\mathbb{N}^{n} x − v j ∈ N n , then x − v j ∈ C x - v_{j} \in C x − v j ∈ C . Indeed, some x i < d i x_{i} < d_{i} x i < d i , and x i − ( v j ) i ≤ x i < d i x_{i} - (v_{j})_{i} \le x_{i} < d_{i} x i − ( v j ) i ≤ x i < d i . This is precisely where the nonnegative predecessor hypothesis enters the proof.
Extend a a a by zero outside N n \mathbb{N}^{n} N n . The recurrence at interior points and the preceding boundary observation give, at every point of N n \mathbb{N}^{n} N n ,
a ( x ) − ∑ j A j a ( x − v j ) = r ( x ) . a(x) - \sum_{j} A_{j}a(x - v_{j}) = r(x). a ( x ) − j ∑ A j a ( x − v j ) = r ( x ) .
Let S = ∑ x a ( x ) X x S = \sum_{x} a(x)X^{x} S = ∑ x a ( x ) X x and R 0 = ∑ x r ( x ) X x R_{0} = \sum_{x} r(x)X^{x} R 0 = ∑ x r ( x ) X x , as column vectors of formal series. With
D ( X ) = I s − ∑ j A j X v j , Q ( X ) = det D ( X ) , D(X) = I_{s} - \sum_{j} A_{j}X^{v_{j}}, \qquad Q(X) = \det D(X), D ( X ) = I s − j ∑ A j X v j , Q ( X ) = det D ( X ) ,
we have D S = R 0 DS = R_{0} D S = R 0 . Since every v j v_{j} v j is nonnegative and nonzero, D ( 0 ) = I s D(0) = I_{s} D ( 0 ) = I s and Q ( 0 ) = 1 Q(0) = 1 Q ( 0 ) = 1 . By Lemmas 2.6 and 2.7, the adjugate identity applies over R [ [ X ] ] R[[X]] R [[ X ]] and Q Q Q is invertible. Thus
S = adj ( D ) R 0 Q . (11) S = \frac{\operatorname{adj}(D)R_{0}}{Q}. \tag*{(11)} S = Q adj ( D ) R 0 . (11)
Each coordinate U i U_{i} U i of adj ( D ) R 0 \operatorname{adj}(D)R_{0} adj ( D ) R 0 has automatic coefficients: multiplication by a polynomial is a finite sum of translated zero extensions with scalar coefficients. Apply Theorem 3.5 to every U i / Q U_{i}/Q U i / Q . Taking the tuple of the coordinate outputs proves automaticity of a a a and gives a terminating construction.
Corollary 4.1 (A computable bound). In this equal-exponent case , let M i M_{i} M i count the states of an automaton representing the sections of U i U_{i} U i , with transition Λ r \Lambda_{r} Λ r on input r r r . Let q j = deg X j det D q_{j} = \deg_{X_{j}}\det D q j = deg X j det D , and put V = ∏ j ( p e − 1 q j + 1 ) V = \prod_{j}(p^{e-1}q_{j} + 1) V = ∏ j ( p e − 1 q j + 1 ) . The vector solution has a least-significant-digit automaton with at most
p e V ∑ i = 1 s M i p^{eV}\sum_{i=1}^{s} M_{i} p e V i = 1 ∑ s M i states. The quantities M i M_{i} M i are computable from automata for the boundary data and the additional sequence by the constructions above. The bound applies before removing unreachable states or merging equivalent states.
Proof. For coordinate i i i , Theorem 3.5 gives a machine with at most p e V M i p^{eV M_i} p e V M i states. All these machines read the same digit vectors from least to most significant. Their product, as defined in § 2.2 , has at most
∏ i = 1 s p e V M i = p e V ∑ i = 1 s M i \prod_{i=1}^{s} p^{eV M_i}=p^{eV\sum_{i=1}^{s}M_i} i = 1 ∏ s p e V M i = p e V ∑ i = 1 s M i
states and outputs the vector of solution coordinates.
Different cyclic exponents
Write H = ∏ i = 1 s Z / p e i Z H=\prod_{i=1}^{s}\mathbb{Z}/p^{e_i}\mathbb{Z} H = ∏ i = 1 s Z / p e i Z and set e = max i e i e=\max_i e_i e = max i e i . There is a coordinatewise quotient π : ( Z / p e Z ) s → H \pi:(\mathbb{Z}/p^e\mathbb{Z})^s\to H π : ( Z / p e Z ) s → H . Decompose h h h into the sum of the endomorphisms on its individual input factors. For each such endomorphism use an integer matrix A = ( a i j ) A=(a_{ij}) A = ( a ij ) with
p e i ∣ p e j a i j . (12) p^{e_i}\mid p^{e_j}a_{ij}. \tag*{(12)} p e i ∣ p e j a ij . (12)
This condition is necessary and sufficient for multiplication by the matrix to be well-defined on H H H . The same integer matrix modulo p e p^e p e defines an endomorphism of ( Z / p e Z ) s (\mathbb{Z}/p^e\mathbb{Z})^s ( Z / p e Z ) s commuting with π \pi π . To see this, changing a representative in coordinate j j j by p e j p^{e_j} p e j changes coordinate i i i of its image by a multiple of p e i p^{e_i} p e i , by (12) .
Choose one lift in ( Z / p e Z ) s (\mathbb{Z}/p^e\mathbb{Z})^s ( Z / p e Z ) s of every element of H H H . Lift c c c and b b b by this coding, which preserves automaticity and compatibility on face intersections. The equal-exponent result gives an automatic lifted solution a ′ a' a ′ . Applying π \pi π to its recurrence gives the original recurrence and boundary values. Uniqueness in Lemma 2.4 gives π a ′ = a \pi a'=a π a ′ = a . A final output coding proves Theorem 1.2 in the nonnegative case.
Allowing negative entries in one coordinate
With a negative predecessor coordinate, extending the prescribed boundary by zero does not determine the whole boundary term in the generating function equation. Some of that term depends on the unknown solution. Condition (1) confines these unknown coefficients to bounded degree in one variable. Algebraic division can then determine them together with the solution.
For a field K K K , a formal series is algebraic if it satisfies a nonzero polynomial equation over the rational-function field in its variables. We use the scalar algebraic division principle underlying [15 Theorem 13] and its treatment in [14 ] , both in characteristic zero. The Christol–Salon theorem converts automaticity into algebraicity. Algebraic Weierstrass division then determines the unknown boundary series in the matrix argument.
Theorem 5.1 (Christol–Salon). Let K K K be a finite field of characteristic p p p . A formal series F ∈ K [ [ X ] ] F\in K[[X]] F ∈ K [[ X ]] is algebraic over K ( X ) K(X) K ( X ) if and only if its coefficient array is p p p -automatic.
For one variable, this is the theorem of Christol, Kamae, Mendès France and Rauzy [6 Theorem 1] . Salon [3 ] gives the multivariate extension. See also [10 ] and the two-dimensional statement in [5 Theorem 14.4.1] . Automaticity in base p f p^f p f is equivalent to automaticity in base p p p , because a finite automaton can group or ungroup blocks of f f f digits, allowing leading zero padding.
Theorem 5.2 (Algebraic Weierstrass division). Let K K K be a field, write Y = ( Y 1 , … , Y n − 1 ) Y=(Y_1,\ldots,Y_{n-1}) Y = ( Y 1 , … , Y n − 1 ) , and suppose D ( Y , Z ) D(Y,Z) D ( Y , Z ) is algebraic with D ( 0 , Z ) = Z L u ( Z ) D(0,Z)=Z^L u(Z) D ( 0 , Z ) = Z L u ( Z ) , where u ( 0 ) ≠ 0 u(0)\ne0 u ( 0 ) = 0 . For every algebraic series V ( Y , Z ) V(Y,Z) V ( Y , Z ) there are unique formal series Q Q Q and R R R with
V = D Q + R , R ∈ K [ [ Y ] ] [ Z ] , deg Z R < L . V=DQ+R,\qquad R\in K[[Y]][Z],\quad\deg_Z R<L. V = D Q + R , R ∈ K [[ Y ]] [ Z ] , deg Z R < L . The quotient and all coefficients of R R R are algebraic over the corresponding rational-function fields. For L = 0 L=0 L = 0 the remainder is zero.
Formal Weierstrass division gives existence and uniqueness of Q Q Q and R R R among formal series. Algebraicity follows from [4 Theorem 4.5] , which holds over any field. In positive characteristic, the case of a Weierstrass polynomial with inseparable factors is treated in [4 Lemma 4.3] . We write rem D V \operatorname{rem}_D V rem D V for the remainder. Formal uniqueness makes this operation K [ [ Y ] ] K[[Y]] K [[ Y ]] -linear: multiplying a division identity by a series in Y Y Y preserves the degree restriction on the remainder, and adding division identities does the same.
Lemma 5.3 (A matrix division step). Let M ( Y , Z ) M(Y,Z) M ( Y , Z ) be an s × s s\times s s × s polynomial matrix over K K K satisfying
M ( 0 , Z ) = Z ℓ U ( Z ) , U ( 0 ) = I s . M(0,Z)=Z^\ell U(Z),\qquad U(0)=I_s. M ( 0 , Z ) = Z ℓ U ( Z ) , U ( 0 ) = I s . Suppose a vector of formal series F F F and a vector R ∈ K [ [ Y ] ] [ Z ] s R\in K[[Y]][Z]^s R ∈ K [[ Y ]] [ Z ] s of degree less than ℓ \ell ℓ satisfy
M F + R = V , (13) MF+R=V, \tag*{(13)} M F + R = V , (13) where the entries of V V V are algebraic. Then the entries of F F F and the coefficients of R R R are algebraic.
Proof. For ℓ = 0 \ell=0 ℓ = 0 , M ( 0 , 0 ) = I s M(0,0)=I_s M ( 0 , 0 ) = I s and F = M − 1 V F=M^{-1}V F = M − 1 V is algebraic. Assume ℓ > 0 \ell>0 ℓ > 0 . Put D = det M D=\det M D = det M and L = s ℓ L=s\ell L = s ℓ . Then D ( 0 , Z ) = Z L det U ( Z ) D(0,Z)=Z^L\det U(Z) D ( 0 , Z ) = Z L det U ( Z ) , so Theorem 5.2 applies. Write
R = ∑ a = 1 s ∑ j = 0 ℓ − 1 r a , j ( Y ) e a Z j , R=\sum_{a=1}^{s}\sum_{j=0}^{\ell-1}r_{a,j}(Y)e_aZ^j, R = a = 1 ∑ s j = 0 ∑ ℓ − 1 r a , j ( Y ) e a Z j ,
where e a e_a e a are the standard coordinate vectors. By Lemma 2.6, multiplication by the adjugate replaces the matrix coefficient M M M by the scalar D D D . Multiply (12) by adj M \operatorname{adj}M adj M and take the scalar remainder of each entry. This gives the finite linear system
∑ a , j r a , j ( Y ) rem D ( ( adj M ) e a Z j ) = rem D ( ( adj M ) V ) . (14) \sum_{a,j}r_{a,j}(Y)\operatorname{rem}_D\bigl((\operatorname{adj}M)e_aZ^j\bigr)=\operatorname{rem}_D\bigl((\operatorname{adj}M)V\bigr). \tag*{(14)} a , j ∑ r a , j ( Y ) rem D ( ( adj M ) e a Z j ) = rem D ( ( adj M ) V ) . (14)
Equating coefficients of Z 0 , … , Z L − 1 Z^0,\ldots,Z^{L-1} Z 0 , … , Z L − 1 in each component gives s L sL s L equations for s ℓ s\ell s ℓ unknown series over K [ [ Y ] ] K[[Y]] K [[ Y ]] . The K [ [ Y ] ] K[[Y]] K [[ Y ]] -linearity of the remainder justifies this step while the unknown coefficients r a , j r_{a,j} r a , j are still only formal series. Every matrix entry and right-hand entry is an algebraic series in Y Y Y , by Theorem 5.2.
This system has a square minor that is a unit at Y = 0 Y=0 Y = 0 . To prove this, specialization of a formal division identity at Y = 0 Y=0 Y = 0 shows that its remainder is truncation modulo Z L Z^L Z L . Also
( adj M ) ( 0 , Z ) = Z ℓ ( s − 1 ) adj U ( Z ) . (\operatorname{adj}M)(0,Z)=Z^{\ell(s-1)}\operatorname{adj}U(Z). ( adj M ) ( 0 , Z ) = Z ℓ ( s − 1 ) adj U ( Z ) .
If a vector polynomial T ( Z ) T(Z) T ( Z ) of degree less than ℓ \ell ℓ belongs to the kernel of the specialized coefficient matrix, then Z L Z^L Z L divides Z ℓ ( s − 1 ) adj U ( Z ) T ( Z ) Z^{\ell(s-1)}\operatorname{adj}U(Z)T(Z) Z ℓ ( s − 1 ) adj U ( Z ) T ( Z ) . Since adj U ( 0 ) = I s \operatorname{adj}U(0)=I_s adj U ( 0 ) = I s , Lemmas 2.6 and 2.7 give an inverse over K [ [ Z ] ] K[[Z]] K [[ Z ]] . Multiplication by that inverse shows that Z ℓ Z^\ell Z ℓ divides T ( Z ) T(Z) T ( Z ) . This forces T = 0 T=0 T = 0 . The specialized columns are therefore linearly independent over K K K , giving the asserted minor.
Solve the equations in this minor by Cramer’s rule. Each r a , j r_{a,j} r a , j is a fraction of algebraic series with a unit denominator, and is therefore an algebraic power series. The assumed formal solution of the full system agrees with this unique solution of the chosen equations. Finally
F = ( adj M ) ( V − R ) D F=\frac{(\operatorname{adj} M)(V-R)}{D} F = D ( adj M ) ( V − R )
is algebraic componentwise. These fractions are power series because they equal the original formal vector F F F . No regularity of the other minors is needed.
The finite-field case
Let H = F p s H=\mathbb{F}_p^s H = F p s , and write the rule as h = ∑ j A j h=\sum_j A_j h = ∑ j A j on its separate inputs. Let c 0 c_0 c 0 be the prescribed boundary extended by zero, and put f ( u ) = a ( d + u ) f(u)=a(d+u) f ( u ) = a ( d + u ) for u ∈ N n u\in\mathbb{N}^n u ∈ N n , with f = 0 f=0 f = 0 outside N n \mathbb{N}^n N n . Extend a a a and c 0 c_0 c 0 similarly. Then everywhere on Z n \mathbb{Z}^n Z n ,
a ( x ) = c 0 ( x ) + f ( x − d ) . a(x)=c_0(x)+f(x-d). a ( x ) = c 0 ( x ) + f ( x − d ) .
In particular, at every interior point the original recurrence is equivalent to
f ( u ) − ∑ j A j f ( u − v j ) = g ( u ) ( u ∈ N n ) , g ( u ) = b ( d + u ) + ∑ j A j c 0 ( d + u − v j ) . (15) f(u)-\sum_j A_jf(u-v_j)=g(u)\quad(u\in\mathbb{N}^n),\qquad g(u)=b(d+u)+\sum_j A_jc_0(d+u-v_j). \tag*{(15)} f ( u ) − j ∑ A j f ( u − v j ) = g ( u ) ( u ∈ N n ) , g ( u ) = b ( d + u ) + j ∑ A j c 0 ( d + u − v j ) . (15)
All terms defining g g g are known and automatic, by the closure lemmas.
To see why the translation is needed, consider the boundary correction that the original solution would require in a generating-function equation on the whole orthant:
γ a ( x ) = 1 C ( x ) ( a ( x ) − ∑ j A j a ( x − v j ) ) . \gamma_a(x)=\mathbf{1}_C(x)\left(a(x)-\sum_j A_ja(x-v_j)\right). γ a ( x ) = 1 C ( x ) ( a ( x ) − j ∑ A j a ( x − v j ) ) .
No recurrence is imposed on C C C , so this difference need not vanish. For nonnegative predecessors, the observation in § 4.1 expresses it using c 0 c_0 c 0 alone. With negative entries, a predecessor of a boundary point may lie in I I I , where its value is still unknown. For example, take P = { ( 1 , − 1 ) , ( 0 , 1 ) } P=\{(1,-1),(0,1)\} P = {( 1 , − 1 ) , ( 0 , 1 )} and scalar coefficients A 1 = A 2 = 1 A_1=A_2=1 A 1 = A 2 = 1 . Here d = ( 1 , 1 ) d=(1,1) d = ( 1 , 1 ) , and at the boundary point ( 2 , 0 ) (2,0) ( 2 , 0 ) ,
γ a ( 2 , 0 ) = c ( 2 , 0 ) − a ( 1 , 1 ) , \gamma_a(2,0)=c(2,0)-a(1,1), γ a ( 2 , 0 ) = c ( 2 , 0 ) − a ( 1 , 1 ) ,
because the other predecessor ( 2 , − 1 ) (2,-1) ( 2 , − 1 ) lies outside the orthant. The value a ( 1 , 1 ) a(1,1) a ( 1 , 1 ) is an interior value. Formula (14) avoids putting such unknown values into the prescribed sequence g g g . They remain part of the unknown series F F F and the remainder R R R in the equation below.
Name the exceptional coordinate Z Z Z , and the remaining coordinates Y Y Y . This renaming does not change the causal order used to define the array. In these variable names, write v j = ( w j , t j ) v_j=(w_j,t_j) v j = ( w j , t j ) with w j ∈ N n − 1 w_j\in\mathbb{N}^{n-1} w j ∈ N n − 1 and t j ∈ Z t_j\in\mathbb{Z} t j ∈ Z . Set
ℓ = max ( 0 , − t 1 , … , − t m ) , M ( Y , Z ) = Z ℓ I s − ∑ j A j Y w j Z ℓ + t j . \ell=\max(0,-t_1,\ldots,-t_m),\qquad M(Y,Z)=Z^\ell I_s-\sum_j A_jY^{w_j}Z^{\ell+t_j}. ℓ = max ( 0 , − t 1 , … , − t m ) , M ( Y , Z ) = Z ℓ I s − j ∑ A j Y w j Z ℓ + t j .
Let F , G F,G F , G be the generating vectors of f , g f,g f , g . Comparing coefficients of Y u Z ℓ + v Y^uZ^{\ell+v} Y u Z ℓ + v , for u ∈ N n − 1 u\in\mathbb{N}^{n-1} u ∈ N n − 1 and v ≥ 0 v\ge0 v ≥ 0 , in (14) gives
M F + R = Z ℓ G , R ∈ F p [ [ Y ] ] [ Z ] s , deg Z R < ℓ . (16) MF+R=Z^\ell G,\qquad R\in\mathbb{F}_p[[Y]][Z]^s,\qquad\deg_Z R<\ell. \tag*{(16)} M F + R = Z ℓ G , R ∈ F p [[ Y ]] [ Z ] s , deg Z R < ℓ . (16)
There are no remainders in the Y Y Y directions because every w j w_j w j is coordinatewise nonnegative. If w j = 0 w_j = 0 w j = 0 , lexicographic positivity of v j v_j v j forces t j > 0 t_j > 0 t j > 0 . Consequently
M ( 0 , Z ) = Z ℓ ( I s − ∑ w j = 0 A j Z t j ) , M(0,\mathbb{Z})=\mathbb{Z}^{\ell}\left(I_s-\sum_{w_j=0} A_j Z^{t_j}\right), M ( 0 , Z ) = Z ℓ I s − w j = 0 ∑ A j Z t j ,
and the matrix in parentheses has value I s I_s I s at zero.
The entries of G G G are algebraic by Theorem 5.1. Lemma 5.3 applied to (15) makes the entries of F F F algebraic. Theorem 5.1 now makes f f f automatic. Boundary assembly and translation make a a a automatic. This proves the elementary abelian case with the full geometric hypothesis.
Lifting to prime powers
We next treat H = ( Z / p e Z ) s H=(\mathbb{Z}/p^e\mathbb{Z})^s H = ( Z / p e Z ) s by induction on e e e . Reduce the solution modulo p p p . Its boundary data, affine term and matrices satisfy the finite-field result, so a ˉ \bar a a ˉ is automatic. Choose the coordinate representatives 0 , … , p − 1 0,\ldots,p-1 0 , … , p − 1 as a coding and let u u u be the resulting automatic lift to ( Z / p e Z ) s (\mathbb{Z}/p^e\mathbb{Z})^s ( Z / p e Z ) s . There is a unique array z z z over ( Z / p e − 1 Z ) s (\mathbb{Z}/p^{e-1}\mathbb{Z})^s ( Z / p e − 1 Z ) s with a = u + p z a=u+pz a = u + p z . On the interior it satisfies
z ( x ) = ∑ j ( A j m o d p e − 1 ) z ( x − v j ) + β ( x ) , β ( x ) = ∑ j A j u ( x − v j ) + b ( x ) − u ( x ) p . z(x)=\sum_j (A_j\bmod p^{e-1})z(x-v_j)+\beta(x),\qquad
\beta(x)=\frac{\sum_j A_j u(x-v_j)+b(x)-u(x)}{p}. z ( x ) = j ∑ ( A j mod p e − 1 ) z ( x − v j ) + β ( x ) , β ( x ) = p ∑ j A j u ( x − v j ) + b ( x ) − u ( x ) .
The numerator lies in p ( Z / p e Z ) s p(\mathbb{Z}/p^e\mathbb{Z})^s p ( Z / p e Z ) s because a ˉ \bar a a ˉ satisfies the reduced recurrence. Division by p p p here means the inverse of the bijection from ( Z / p e − 1 Z ) s (\mathbb{Z}/p^{e-1}\mathbb{Z})^s ( Z / p e − 1 Z ) s to that ideal, which is a well-defined coding. Extend β \beta β by zero on the boundary. It is automatic, as are the face values z = ( c − u ) / p z=(c-u)/p z = ( c − u ) / p . The induction hypothesis therefore makes z z z automatic, and then a = u + p z a=u+pz a = u + p z is automatic. The case e = 1 e=1 e = 1 was proved above.
For unequal cyclic exponents, apply exactly the matrix lift and output coding in the preceding section. That argument uses the equal-exponent conclusion and uniqueness, and requires no further geometric assumption. This completes the proof of Theorem 1.2 under (1).
The explicit state bound in Corollary 4.1 concerns the nonnegative construction. The algebraic division proof above establishes automaticity without a corresponding state bound.
Proof for arbitrary finite p p p -groups
We reduce a group recurrence to a quotient and a recurrence in a central subgroup, following the approach of [19 Theorem 4 and Proposition 8(3)] . A subgroup is central if its elements commute with the whole group, and it is fully invariant if every endomorphism maps it into itself. We need both properties: invariance gives a quotient rule, while centrality lets us collect the subgroup contributions in the product without changing their order relative to the other factors. An elementary abelian p p p -group is a finite vector space over F p \mathbb{F}_p F p under addition, so its recurrence is covered by the abelian theorem.
Lemma 6.1. Every nontrivial finite p p p -group G G G has a nontrivial central elementary abelian subgroup N N N that is preserved by every endomorphism of G G G .
Proof. A finite p p p -group has nontrivial center by its class equation. Induction on its order, applied to the quotient by the center, shows it is nilpotent. Writing [ g , h ] = g h g − 1 h − 1 [g,h]=ghg^{-1}h^{-1} [ g , h ] = g h g − 1 h − 1 , define γ 1 ( G ) = G \gamma_1(G)=G γ 1 ( G ) = G and let γ i + 1 ( G ) \gamma_{i+1}(G) γ i + 1 ( G ) be the subgroup generated by the commutators [ u , g ] [u,g] [ u , g ] with u ∈ γ i ( G ) u \in\gamma_i(G) u ∈ γ i ( G ) and g ∈ G g \in G g ∈ G . Nilpotence means that this series reaches the identity subgroup. Let γ c ( G ) \gamma_c(G) γ c ( G ) be the last nontrivial term of its lower central series. This subgroup is central and is preserved by every endomorphism, since each term of the lower central series is generated by iterated commutators. The elements of γ c ( G ) \gamma_c(G) γ c ( G ) killed by the p p p th-power map form a nontrivial subgroup N N N . It is elementary abelian because γ c ( G ) \gamma_c(G) γ c ( G ) is abelian. Both defining conditions are preserved by endomorphisms, so N N N has the required invariance.
Proof of Theorem 1.3. Induct on ∣ G ∣ |G| ∣ G ∣ , the trivial group being immediate. Take N N N as in Lemma 6.1. If N = G N=G N = G , the group is elementary abelian and Theorem 1.2 applies. Otherwise put G ‾ = G / N \overline{G}=G/N G = G / N . Every α j \alpha_j α j preserves N N N , so the ordered-product rule descends to the same kind of rule on G ‾ \overline{G} G . Projecting the initial data and b b b gives automatic data in G ‾ \overline{G} G . By induction, the projected solution q ( x ) = a ( x ) N q(x)=a(x)N q ( x ) = a ( x ) N is automatic.
Choose a set-theoretic section σ : G ‾ → G \sigma:\overline{G}\to G σ : G → G with σ ( 1 ) = 1 \sigma(1)=1 σ ( 1 ) = 1 . Write uniquely a ( x ) = σ ( q ( x ) ) z ( x ) a(x)=\sigma(q(x))z(x) a ( x ) = σ ( q ( x )) z ( x ) with z ( x ) ∈ N z(x)\in N z ( x ) ∈ N . At interior points set
β ( x ) = σ ( q ( x ) ) − 1 α 1 ( σ ( q ( x − v 1 ) ) ) ⋯ α m ( σ ( q ( x − v m ) ) ) b ( x ) . \beta(x)=\sigma(q(x))^{-1}\alpha_1\bigl(\sigma(q(x-v_1))\bigr)\cdots\alpha_m\bigl(\sigma(q(x-v_m))\bigr)b(x). β ( x ) = σ ( q ( x ) ) − 1 α 1 ( σ ( q ( x − v 1 )) ) ⋯ α m ( σ ( q ( x − v m )) ) b ( x ) .
The quotient recurrence shows that β ( x ) ∈ N \beta(x)\in N β ( x ) ∈ N . Extend β \beta β by 1 1 1 on C C C . It is automatic: the translated quotient arrays are automatic by Lemma 2.2, and the expression uses only functions between finite sets followed by the automatic interior mask.
Since N N N is central and each α j ( N ) ⊆ N \alpha_j(N)\subseteq N α j ( N ) ⊆ N , substitution into the recurrence gives
z ( x ) = ∏ j = 1 m α j ∣ N ( z ( x − v j ) ) β ( x ) ( x ∈ I ) . z(x)=\prod_{j=1}^{m}\alpha_j|_N\bigl(z(x-v_j)\bigr)\beta(x)\qquad(x\in I). z ( x ) = j = 1 ∏ m α j ∣ N ( z ( x − v j ) ) β ( x ) ( x ∈ I ) .
On C C C , z = σ ( q ) − 1 c z=\sigma(q)^{-1}c z = σ ( q ) − 1 c has automatic face restrictions. The last display is an abelian recurrence on the elementary abelian group N N N with an automatic affine term. Theorem 1.2 makes z z z automatic. The coding ( q , z ) ↦ σ ( q ) z (q,z)\mapsto\sigma(q)z ( q , z ) ↦ σ ( q ) z now makes a a a automatic.
Remark 6.2 (Effectiveness and scope). For a finite group specified by its multiplication table, the subgroups, quotients, sections, and induced maps in this induction can be found by enumerating subsets of G G G and maps between the resulting finite sets. For nonnegative predecessors, combining this with the abelian construction gives an explicit effective proof. Its cost is not analyzed here. For the larger geometry, the proof uses the algebraic division step of Section 5. Cross-commutation of the images of different endomorphisms is unnecessary: only the centrality of N N N is used when collecting its factors. The unrestricted extension fails already in its abelian special case.
Proof of the two-dimensional corollary
Proof of Corollary 1.5. Write the predecessors as v j = ( u j , v j ) v_j=(u_j,v_j) v j = ( u j , v j ) . Lexicographic positivity means that either u j > 0 u_j>0 u j > 0 , or u j = 0 u_j=0 u j = 0 and v j > 0 v_j>0 v j > 0 . Thus u j ≥ 0 u_j\geq0 u j ≥ 0 for all j j j , and a negative entry can occur only in the second coordinate. This verifies (1) with the same exceptional coordinate k = 2 k=2 k = 2 for the entire predecessor set. There is no restriction on the magnitudes or number of its negative second coordinates.
The recurrence is well-founded even when a predecessor has a larger second coordinate than the point being computed. Choose a positive integer L L L so large that L u j + v j > 0 Lu_j+v_j>0 L u j + v j > 0 for each j j j with u j > 0 u_j>0 u j > 0 . There are finitely many such inequalities. If u j = 0 u_j=0 u j = 0 , the same inequality holds because v j > 0 v_j>0 v j > 0 . Each predecessor of ( m , n ) (m,n) ( m , n ) therefore has smaller weight L m + n Lm+n L m + n . The weights are nonnegative integers on N 2 \mathbb{N}^2 N 2 . For each integer N ≥ 0 N \ge0 N ≥ 0 , the set { ( m , n ) ∈ N 2 : L m + n ≤ N } \{(m,n) \in\mathbb{N}^2 : Lm+n \le N\} {( m , n ) ∈ N 2 : L m + n ≤ N } contains finitely many points, because m ≤ N / L m \le N/L m ≤ N / L and n ≤ N n \le N n ≤ N .
Put d 1 = max ( 0 , max j u j ) d_1=\max(0,\max_j u_j) d 1 = max ( 0 , max j u j ) and d 2 = max ( 0 , max j v j ) d_2=\max(0,\max_j v_j) d 2 = max ( 0 , max j v j ) . For m ≥ d 1 m \ge d_1 m ≥ d 1 and n ≥ d 2 n \ge d_2 n ≥ d 2 , all predecessors lie in N 2 \mathbb{N}^2 N 2 . The remaining points form the boundary C = { m < d 1 } ∪ { n < d 2 } C=\{m<d_1\}\cup\{n<d_2\} C = { m < d 1 } ∪ { n < d 2 } . Its face restrictions are the automatic sequences assumed in the corollary, and their compatibility makes the prescribed function well-defined. The induction on these sublevel sets in Lemma 2.4 determines a unique array with the specified data.
The sign condition and the automatic data now satisfy all hypotheses of Theorem 1.3, which makes the ordered-product solution p p p -automatic. In the abelian case, the same conclusion also follows directly from Theorem 1.2. If the rule is a homomorphism G m → G G^m \to G G m → G , the factor decomposition in Corollary 1.4 puts it in the ordered-product form.
For example, the predecessor ( 1 , − 2 ) (1,-2) ( 1 , − 2 ) requests the value at ( m − 1 , n + 2 ) (m-1,n+2) ( m − 1 , n + 2 ) . With the additional predecessor ( 0 , 1 ) (0,1) ( 0 , 1 ) , the weight 3 m + n 3m+n 3 m + n decreases by 1 under either step. The automaticity conclusion applies to this system for any of the group rules and data in the corollary.
Removing coordinates without prescribed boundary faces
The restriction to one possible negative coordinate does not cover all automatic predecessor systems. Another sufficient family allows negative entries in several coordinates when the boundary is the union of the slices { t = j } \{t=j\} { t = j } for 0 ≤ j < d 0 \le j<d 0 ≤ j < d . Here t t t denotes the first coordinate, and the other n − 1 n-1 n − 1 coordinates range over N n − 1 \mathbb{N}^{n-1} N n − 1 . There are d d d slices, each infinite when n ≥ 2 n \ge2 n ≥ 2 . We first prove the closure property used to change coordinates. The distinguished value 0 in the lemma can be replaced by the identity when the output alphabet is a group.
Lemma 7.1 (Integer affine substitution). Let u : N k → A u:\mathbb{N}^k \to A u : N k → A be p p p -automatic, where A A A is finite with a distinguished element 0. Extend u u u by zero to Z k \mathbb{Z}^k Z k . For any integer matrix B ∈ M k , d ( Z ) B \in M_{k,d}(\mathbb{Z}) B ∈ M k , d ( Z ) and c ∈ Z k c \in\mathbb{Z}^k c ∈ Z k , the array v ( x ) = u ( B x + c ) v(x)=u(Bx+c) v ( x ) = u ( B x + c ) on N d \mathbb{N}^d N d is p p p -automatic.
Proof. For e ≥ 0 e \ge0 e ≥ 0 and 0 ≤ r i < p e 0 \le r_i<p^e 0 ≤ r i < p e , write B r + c = p e q + s Br+c=p^e q+s B r + c = p e q + s coordinatewise, with 0 ≤ s i < p e 0 \le s_i<p^e 0 ≤ s i < p e . The coordinates of q q q range over a finite set depending on B , c B,c B , c , since r i / p e r_i/p^e r i / p e belongs to [ 0 , 1 ) [0,1) [ 0 , 1 ) and ∣ c i ∣ / p e ≤ ∣ c i ∣ |c_i|/p^e \le|c_i| ∣ c i ∣/ p e ≤ ∣ c i ∣ . Let u e , s ( y ) = u ( p e y + s ) u_{e,s}(y)=u(p^e y+s) u e , s ( y ) = u ( p e y + s ) for y ∈ N k y \in\mathbb{N}^k y ∈ N k , again extended by zero outside N k \mathbb{N}^k N k . Then
v ( p e x + r ) = u e , s ( B x + q ) . v(p^e x+r)=u_{e,s}(Bx+q). v ( p e x + r ) = u e , s ( B x + q ) .
The equality remains valid if a coordinate of B x + q Bx+q B x + q is negative, because 0 ≤ s i < p e 0 \le s_i<p^e 0 ≤ s i < p e makes the corresponding coordinate of p e ( B x + q ) + s p^e(Bx+q)+s p e ( B x + q ) + s negative as well. There are finitely many choices of u e , s u_{e,s} u e , s by automaticity, and finitely many choices of q q q . Thus v v v has a finite p p p -kernel.
Theorem 7.2 (Boundary on prescribed coordinate slices). Let P P P be a finite nonempty set of vectors
v j = ( r j , − s j ) ∈ Z × Z n − 1 , r j > 0 , s j ∈ N n − 1 . v_j=(r_j,-s_j)\in\mathbb{Z}\times\mathbb{Z}^{n-1},\qquad r_j>0,\quad s_j\in\mathbb{N}^{n-1}. v j = ( r j , − s j ) ∈ Z × Z n − 1 , r j > 0 , s j ∈ N n − 1 . Put d = max j r j d=\max_j r_j d = max j r j . Let $G be a finite p p p -group, let α 1 , … , α m \alpha_1,\ldots,\alpha_m α 1 , … , α m be endomorphisms of G G G , and let b : N × N n − 1 → G b:\mathbb{N}\times\mathbb{N}^{n-1}\to G b : N × N n − 1 → G be p p p -automatic. Prescribe p p p -automatic data on each slice t = j t=j t = j , $0\le j<d$, as functions of the other coordinates. Then the unique solution of
a ( t , x ) = α 1 ( a ( t − r 1 , x + s 1 ) ) ⋯ α m ( a ( t − r m , x + s m ) ) b ( t , x ) ( t ≥ d ) a(t,x)=\alpha_1(a(t-r_1,x+s_1))\cdots\alpha_m(a(t-r_m,x+s_m))b(t,x)\qquad(t\ge d) a ( t , x ) = α 1 ( a ( t − r 1 , x + s 1 )) ⋯ α m ( a ( t − r m , x + s m )) b ( t , x ) ( t ≥ d ) on N × N n − 1 \mathbb{N}\times\mathbb{N}^{n-1} N × N n − 1 is p p p -automatic.
Proof. Choose integers c i ≥ 0 c_i \ge0 c i ≥ 0 such that c i r j ≥ ( s j ) i c_i r_j \ge(s_j)_i c i r j ≥ ( s j ) i for all i , j i,j i , j . Define the invertible integer linear map
T ( t , x ) = ( t , y ) , y i = x i + c i t . T(t,x)=(t,y), \qquad y_i=x_i+c_i t. T ( t , x ) = ( t , y ) , y i = x i + c i t .
It sends each predecessor to v j ′ = ( r j , c r j − s j ) v'_j=(r_j,c r_j-s_j) v j ′ = ( r j , c r j − s j ) , a nonnegative nonzero vector. It sends the original domain to
W = { ( t , y ) ∈ N n : y i ≥ c i t for all i } . W=\{(t,y)\in\mathbb{N}^n:y_i\ge c_i t\text{ for all }i\}. W = {( t , y ) ∈ N n : y i ≥ c i t for all i } .
The boundary widths of the transformed nonnegative recurrence are d 0 ′ = d d'_0=d d 0 ′ = d and
d i ′ = max j ( c i r j − ( s j ) i ) ≤ c i d . d'_i=\max_j\bigl(c_i r_j-(s_j)_i\bigr)\le c_i d. d i ′ = j max ( c i r j − ( s j ) i ) ≤ c i d .
If t ≥ d t\ge d t ≥ d , every point of W W W lies in the transformed interior, since y i ≥ c i t ≥ d i ′ y_i\ge c_i t\ge d'_i y i ≥ c i t ≥ d i ′ .
Let c 0 c_0 c 0 be the original boundary data extended by the identity to all of N n \mathbb{N}^n N n . It is automatic by Lemma 2.3. Extend it and the original additional sequence b b b by the identity outside N n \mathbb{N}^n N n . On the transformed boundary prescribe c ′ = c 0 ∘ T − 1 c'=c_0\circ T^{-1} c ′ = c 0 ∘ T − 1 , and on the whole transformed orthant use the additional sequence b ′ = b ∘ T − 1 b'=b\circ T^{-1} b ′ = b ∘ T − 1 . Both arrays are automatic by Lemma 7.1 , and the boundary values are compatible because they are restrictions of one array. The nonnegative case of Theorem 1.3 gives an automatic solution F F F for these transformed data.
Set a ~ ( t , x ) = F ( T ( t , x ) ) \tilde a(t,x)=F(T(t,x)) a ~ ( t , x ) = F ( T ( t , x )) . This array is automatic by Lemma 7.1 . If t < d t<d t < d , its value is the prescribed original boundary value, because T ( t , x ) T(t,x) T ( t , x ) lies in the transformed boundary and T − 1 T ( t , x ) = ( t , x ) T^{-1}T(t,x)=(t,x) T − 1 T ( t , x ) = ( t , x ) . If t ≥ d t\ge d t ≥ d , the recurrence for F F F applies at T ( t , x ) T(t,x) T ( t , x ) and
T ( t , x ) − v j ′ = T ( t − r j , x + s j ) . T(t,x)-v'_j=T(t-r_j,x+s_j). T ( t , x ) − v j ′ = T ( t − r j , x + s j ) .
These predecessors belong to W W W , since t − r j ≥ 0 t-r_j\ge0 t − r j ≥ 0 and x + s j ∈ N n − 1 x+s_j\in\mathbb{N}^{n-1} x + s j ∈ N n − 1 . Substituting them into the transformed rule gives the original ordered-product rule for a ~ \tilde a a ~ , with additional sequence b ( t , x ) b(t,x) b ( t , x ) . Uniqueness gives a ~ = a \tilde a=a a ~ = a .
For example,
P = { ( 1 , − 1 , 0 ) , ( 1 , 0 , − 1 ) } P=\{(1,-1,0),(1,0,-1)\} P = {( 1 , − 1 , 0 ) , ( 1 , 0 , − 1 )}
has negative entries in two coordinates. The map T ( t , x , y ) = ( t , x + t , y + t ) T(t,x,y)=(t,x+t,y+t) T ( t , x , y ) = ( t , x + t , y + t ) gives transformed predecessors { ( 1 , 0 , 1 ) , ( 1 , 1 , 0 ) } \{(1,0,1),(1,1,0)\} {( 1 , 0 , 1 ) , ( 1 , 1 , 0 )} . Theorem 7.2 applies to any of the stated group rules and automatic data on t = 0 t=0 t = 0 . The argument uses the prescribed boundary slices as well as the transformed predecessors. A coordinate change for a more general system would also have to control its other boundary faces.
Related automaticity results for cellular automata appear in [16 , 17 , 18 ] .
Coordinates without prescribed boundary faces
A negative predecessor entry causes a boundary difficulty only when the same coordinate also has a positive predecessor entry. If all its entries are nonpositive, its boundary width is zero. We can then add a positive weighted sum of the other coordinates without losing a prescribed boundary face. This extends the argument for prescribed coordinate slices.
Proof of Theorem 1.6 . Put
A = { i : d i > 0 } , U = { 1 , … , n } ∖ A . A=\{i:d_i>0\},\qquad U=\{1,\ldots,n\}\setminus A. A = { i : d i > 0 } , U = { 1 , … , n } ∖ A .
Thus ( v j ) i ≤ 0 (v_j)_i\le0 ( v j ) i ≤ 0 for i ∈ U i\in U i ∈ U . Project the predecessors onto the coordinates in A A A , retaining their original order. The projected vectors are nonzero and lexicographically positive: the first nonzero coordinate of an original predecessor is positive and therefore belongs to A A A . Lemma 2.4 supplies positive integer weights w i w_i w i , i ∈ A i \in A i ∈ A , such that
h ( x ) = ∑ i ∈ A w i x i , ρ j = h ( v j ) > 0. h(x) = \sum_{i \in A} w_i x_i,\qquad\rho_j = h(v_j) > 0. h ( x ) = i ∈ A ∑ w i x i , ρ j = h ( v j ) > 0.
For each i ∈ U i \in U i ∈ U , choose an integer c i ≥ 0 c_i \ge0 c i ≥ 0 with c i ρ j + ( v j ) i ≥ 0 c_i\rho_j + (v_j)_i \ge0 c i ρ j + ( v j ) i ≥ 0 for all j j j . Define the invertible integer linear map T T T by
( T x ) i = x i ( i ∈ A ) , ( T x ) i = x i + c i h ( x ) ( i ∈ U ) . (Tx)_i = x_i \quad(i \in A),\qquad(Tx)_i = x_i + c_i h(x) \quad(i \in U). ( T x ) i = x i ( i ∈ A ) , ( T x ) i = x i + c i h ( x ) ( i ∈ U ) .
The function h h h depends only on the unchanged coordinates. Thus the inverse subtracts c i h ( x ) c_i h(x) c i h ( x ) in the coordinates in U U U . The transformed predecessors v j ′ = T v j v'_j = Tv_j v j ′ = T v j are nonnegative in U U U and retain their entries in A A A . They remain lexicographically positive, since their first original positive coordinate is unchanged and earlier coordinates can only increase. In A A A , a negative entry can occur only in the one coordinate permitted by the hypothesis. Consequently P ′ = { v j ′ } P' = \{v'_j\} P ′ = { v j ′ } satisfies (1).
We next check the transformed boundary. The image of the original domain is
W = T ( N n ) = { y ∈ N n : y i ≥ c i h ( y ) for i ∈ U } . W = T(\mathbb{N}^n) = \{y \in\mathbb{N}^n : y_i \ge c_i h(y)\text{ for }i \in U\}. W = T ( N n ) = { y ∈ N n : y i ≥ c i h ( y ) for i ∈ U } .
Its boundary widths satisfy d i ′ = d i d'_i = d_i d i ′ = d i for i ∈ A i \in A i ∈ A and
d i ′ = max j ( ( v j ) i + c i ρ j ) ≤ c i ∑ a ∈ A w a d a ( i ∈ U ) . d'_i = \max_j\bigl((v_j)_i + c_i\rho_j\bigr) \le c_i\sum_{a \in A} w_a d_a \quad(i \in U). d i ′ = j max ( ( v j ) i + c i ρ j ) ≤ c i a ∈ A ∑ w a d a ( i ∈ U ) .
Indeed, ( v j ) i ≤ 0 (v_j)_i \le0 ( v j ) i ≤ 0 for i ∈ U i \in U i ∈ U and ( v j ) a ≤ d a (v_j)_a \le d_a ( v j ) a ≤ d a for a ∈ A a \in A a ∈ A . If x ∈ I x \in I x ∈ I , then h ( x ) ≥ ∑ a ∈ A w a d a h(x) \ge\sum_{a \in A} w_a d_a h ( x ) ≥ ∑ a ∈ A w a d a , so ( T x ) i ≥ d i ′ (Tx)_i \ge d'_i ( T x ) i ≥ d i ′ also in U U U . If x ∈ C x \in C x ∈ C , one of the unchanged coordinates in A A A is below its boundary width. Therefore
T x ∈ I ′ ⟺ x ∈ I , x ∈ N n . Tx \in I' \quad\Longleftrightarrow\quad x \in I,\qquad x \in\mathbb{N}^n. T x ∈ I ′ ⟺ x ∈ I , x ∈ N n .
Let c 0 c_0 c 0 be the original boundary function extended by the identity of C C C , and extend both c 0 c_0 c 0 and b b b by the identity outside N n \mathbb{N}^n N n . Prescribe c 0 ∘ T − 1 c_0 \circ T^{-1} c 0 ∘ T − 1 on the transformed boundary and use the additional sequence b ∘ T − 1 b \circ T^{-1} b ∘ T − 1 . These data are automatic by Lemmas 2.3 and 7.1 . Their face restrictions are compatible because they come from one array. Theorem 1.3 gives an automatic transformed solution F F F .
The pullback a ~ = F ∘ T \widetilde a = F \circ T a = F ∘ T is automatic by Lemma 7.1 . On C C C it has the prescribed values. For x ∈ I x \in I x ∈ I , the transformed recurrence applies at T x Tx T x , and
T x − v j ′ = T ( x − v j ) ∈ W . Tx - v'_j = T(x-v_j) \in W. T x − v j ′ = T ( x − v j ) ∈ W .
Hence that recurrence becomes the original ordered-product recurrence for a ~ \widetilde a a , with additional sequence b ( x ) b(x) b ( x ) . Uniqueness gives a ~ = a \widetilde a = a a = a .
For a three-dimensional example with two prescribed boundary directions, take
P = { ( 1 , − 1 , − 1 ) , ( 0 , 1 , − 1 ) } , d = ( 1 , 1 , 0 ) . P = \{(1,-1,-1),(0,1,-1)\},\qquad d = (1,1,0). P = {( 1 , − 1 , − 1 ) , ( 0 , 1 , − 1 )} , d = ( 1 , 1 , 0 ) .
Both the second and third coordinates contain negative entries, but only the second contains entries of both signs. The choice h ( x , y , z ) = 2 x + y h(x,y,z) = 2x+y h ( x , y , z ) = 2 x + y and
T ( x , y , z ) = ( x , y , z + 2 x + y ) T(x,y,z) = (x,y,z+2x+y) T ( x , y , z ) = ( x , y , z + 2 x + y )
gives transformed predecessors { ( 1 , − 1 , 0 ) , ( 0 , 1 , 0 ) } \{(1,-1,0),(0,1,0)\} {( 1 , − 1 , 0 ) , ( 0 , 1 , 0 )} . Theorem 1.6 allows arbitrary compatible automatic data on x = 0 x=0 x = 0 and y = 0 y=0 y = 0 , together with an automatic additional sequence. The earlier family with boundary on prescribed slices has no coordinate with both signs and is a special case of this theorem.
If no coordinate contains both signs, all transformed predecessors are nonnegative. In that case the reduction combines with the direct construction in § 4 , without algebraic division. The integer affine substitution itself also admits an explicit machine, as follows.
Proposition 7.3 (A bound for integer affine substitution). Suppose u : N k → A u:\mathbb{N}^{k}\to A u : N k → A is given by a least-significant-digit automaton with M M M states, and extend it by a distinguished value outside N k \mathbb{N}^{k} N k . For v ( x ) = u ( B x + c ) v(x)=u(Bx+c) v ( x ) = u ( B x + c ) as in Lemma 7.1 , put
L i = min ( c i , ∑ j : B i j < 0 B i j ) , U i = max ( c i , ∑ j : B i j > 0 B i j ) . L_i=\min\left(c_i,\sum_{j:B_{ij}<0}B_{ij}\right),\qquad U_i=\max\left(c_i,\sum_{j:B_{ij}>0}B_{ij}\right). L i = min c i , j : B ij < 0 ∑ B ij , U i = max c i , j : B ij > 0 ∑ B ij . There is an effectively constructed automaton for v v v with at most M ∏ i = 1 k ( U i − L i + 1 ) M\prod_{i=1}^{k}(U_i-L_i+1) M ∏ i = 1 k ( U i − L i + 1 ) states.
Proof. First discard unreachable input states, leaving at most M M M states. For each remaining state q q q , let u q u_q u q be the array computed by starting the input automaton in q q q . These arrays inherit padding invariance, as in the translation construction in Lemma 2.2 . A state is a pair ( q , z ) (q,z) ( q , z ) , where q q q is an input automaton state and L i ≤ z i ≤ U i L_i\le z_i\le U_i L i ≤ z i ≤ U i . It represents the function x ↦ u q ( B x + z ) x\mapsto u_q(Bx+z) x ↦ u q ( B x + z ) , with the same extension outside N k \mathbb{N}^{k} N k . The initial pair is ( q 0 , c ) (q_0,c) ( q 0 , c ) . On an input digit vector r r r , divide componentwise
B r + z = p z ′ + s , 0 ≤ s i < p . Br+z=pz'+s,\qquad0\le s_i<p. B r + z = p z ′ + s , 0 ≤ s i < p .
The successor is ( δ ( q , s ) , z ′ ) (\delta(q,s),z') ( δ ( q , s ) , z ′ ) . The represented function is the required section, including at negative arguments, by the calculation in Lemma 7.1 . The interval for z i ′ z'_i z i ′ is invariant because
p L i ≤ ( B r + z ) i ≤ p U i , pL_i\le(Br+z)_i\le pU_i, p L i ≤ ( B r + z ) i ≤ p U i ,
using 0 ≤ r j < p 0\le r_j<p 0 ≤ r j < p , L i ≤ ∑ B i j < 0 B i j L_i\le\sum_{B_{ij}<0}B_{ij} L i ≤ ∑ B ij < 0 B ij and U i ≥ ∑ B i j > 0 B i j U_i\ge\sum_{B_{ij}>0}B_{ij} U i ≥ ∑ B ij > 0 B ij . Taking the integer quotient gives L i ≤ z i ′ ≤ U i L_i\le z'_i\le U_i L i ≤ z i ′ ≤ U i . The output is u q ( z ) u_q(z) u q ( z ) if z ∈ N k z\in\mathbb{N}^{k} z ∈ N k , and the distinguished value otherwise. Evaluating u q u_q u q at the fixed tuple z z z uses its given automaton. There are at most M M M choices of q q q and ∏ i = 1 k ( U i − L i + 1 ) \prod_{i=1}^{k}(U_i-L_i+1) ∏ i = 1 k ( U i − L i + 1 ) choices of z z z , giving at most M ∏ i = 1 k ( U i − L i + 1 ) M\prod_{i=1}^{k}(U_i-L_i+1) M ∏ i = 1 k ( U i − L i + 1 ) states.
A three-dimensional obstruction
With negative entries in two coordinate directions, automatic boundary data need not give an automatic solution. The construction uses the recurrence of [15 Section 4.5, Example 6] . Its generating-function identity is the Gabber–Kashiwara division of X Y XY X Y by ( X − Y 2 ) ( Y − X 2 ) (X-Y^2)(Y-X^2) ( X − Y 2 ) ( Y − X 2 ) in [13 Example 5.2] . An additional first coordinate makes its predecessor vectors lexicographically positive and allows prescribed boundary data with a single nonzero value.
Theorem 8.1. For every prime p p p , there is a recurrence over the additive group F p \mathbb{F}_p F p , with lexicographically positive predecessors, a homomorphism rule and a single nonzero boundary value, whose solution on N 3 \mathbb{N}^{3} N 3 is not p p p -automatic.
The recurrence and its initial conditions
Use coordinates ( t , i , j ) (t,i,j) ( t , i , j ) , in that order, and set
P = { ( 1 , 2 , − 1 ) , ( 1 , − 1 , 2 ) , ( 2 , 1 , 1 ) } . P=\{(1,2,-1),(1,-1,2),(2,1,1)\}. P = {( 1 , 2 , − 1 ) , ( 1 , − 1 , 2 ) , ( 2 , 1 , 1 )} .
Every vector has positive first coordinate. The prescribed boundary is
C = { ( t , i , j ) ∈ N 3 : t < 2 or i < 2 or j < 2 } . C=\{(t,i,j)\in\mathbb{N}^{3}:t<2\text{ or }i<2\text{ or }j<2\}. C = {( t , i , j ) ∈ N 3 : t < 2 or i < 2 or j < 2 } .
Prescribe
c ( t , i , j ) = { 1 , ( t , i , j ) = ( 0 , 2 , 2 ) , 0 , otherwise , ( t , i , j ) ∈ C . c(t,i,j)=
\begin{cases}
1,&(t,i,j)=(0,2,2),\\
0,&\text{otherwise},
\end{cases}
\qquad(t,i,j)\in C. c ( t , i , j ) = { 1 , 0 , ( t , i , j ) = ( 0 , 2 , 2 ) , otherwise , ( t , i , j ) ∈ C .
For t , i , j ≥ 2 t,i,j\ge2 t , i , j ≥ 2 define, in F 3 \mathbb{F}_{3} F 3 ,
a ( t , i , j ) = a ( t − 1 , i − 2 , j + 1 ) + a ( t − 1 , i + 1 , j − 2 ) − a ( t − 2 , i − 1 , j − 1 ) . (17) a(t,i,j)=a(t-1,i-2,j+1)+a(t-1,i+1,j-2)-a(t-2,i-1,j-1). \tag*{(17)} a ( t , i , j ) = a ( t − 1 , i − 2 , j + 1 ) + a ( t − 1 , i + 1 , j − 2 ) − a ( t − 2 , i − 1 , j − 1 ) . (17)
The rule ( u , v , w ) ↦ u + v − w (u,v,w)\mapsto u+v-w ( u , v , w ) ↦ u + v − w is a group homomorphism ( F 3 ) 3 → F 3 (\mathbb{F}_{3})^{3}\to\mathbb{F}_{3} ( F 3 ) 3 → F 3 . Every specified boundary slice is zero except the slice t = 0 t=0 t = 0 , which has a single nonzero point. Such slices are automatic in every base: a finite automaton can check equality with a fixed coordinate tuple. The values agree on all intersections. The recurrence has a unique solution by induction on t t t , since each right hand side uses points with a smaller first coordinate.
The formula for the section
Proposition 8.2. The solution of (16) satisfies
a ( n , n + 2 , 2 ) = { ( − 1 ) k m o d 3 , n = 3 ⋅ 2 k − 3 , k ≥ 0 , 0 , otherwise . (18) a(n,n+2,2)=
\begin{cases}
(-1)^{k}\bmod3,&n=3\cdot2^{k}-3,\ k\ge0,\\
0,&\text{otherwise}.
\end{cases} \tag*{(18)} a ( n , n + 2 , 2 ) = { ( − 1 ) k mod 3 , 0 , n = 3 ⋅ 2 k − 3 , k ≥ 0 , otherwise . (18)
Proof. First work over the integers. Define q i j = 0 q_{ij}=0 q ij = 0 when either index is negative, and for i , j ≥ 0 i,j\ge0 i , j ≥ 0 set
q i j = 1 ( i , j ) = ( 0 , 0 ) + q i − 2 , j + 1 + q i + 1 , j − 2 − q i − 1 , j − 1 . (19) q_{ij}=\mathbf{1}_{(i,j)=(0,0)}+q_{i-2,j+1}+q_{i+1,j-2}-q_{i-1,j-1}. \tag*{(19)} q ij = 1 ( i , j ) = ( 0 , 0 ) + q i − 2 , j + 1 + q i + 1 , j − 2 − q i − 1 , j − 1 . (19)
Every term with nonnegative indices on the right has smaller total degree. This defines q q q uniquely. In particular q 00 = 1 q_{00}=1 q 00 = 1 and q 10 = q 01 = 0 q_{10}=q_{01}=0 q 10 = q 01 = 0 . Let
Q ( X , Y ) = ∑ i , j ≥ 0 q i j X i Y j , g ( X , Y ) = ( X − Y 2 ) ( Y − X 2 ) . Q(X,Y)=\sum_{i,j\ge0}q_{ij}X^{i}Y^{j},\qquad g(X,Y)=(X-Y^{2})(Y-X^{2}). Q ( X , Y ) = i , j ≥ 0 ∑ q ij X i Y j , g ( X , Y ) = ( X − Y 2 ) ( Y − X 2 ) .
The recurrence and initial value are symmetric in i , j i,j i , j , so Q ( X , Y ) = Q ( Y , X ) Q(X,Y)=Q(Y,X) Q ( X , Y ) = Q ( Y , X ) . For u , v ≥ 1 u,v\ge1 u , v ≥ 1 , coefficient extraction gives
[ X u Y v ] g Q = q u − 1 , v − 1 − q u − 3 , v − q u , v − 3 + q u − 2 , v − 2 = 1 u = v = 1 . [X^{u}Y^{v}]gQ=q_{u-1,v-1}-q_{u-3,v}-q_{u,v-3}+q_{u-2,v-2}=\mathbf{1}_{u=v=1}. [ X u Y v ] g Q = q u − 1 , v − 1 − q u − 3 , v − q u , v − 3 + q u − 2 , v − 2 = 1 u = v = 1 .
On the axes, g ( X , 0 ) Q ( X , 0 ) = − X 3 Q ( X , 0 ) g(X,0)Q(X,0)=-X^{3}Q(X,0) g ( X , 0 ) Q ( X , 0 ) = − X 3 Q ( X , 0 ) , and likewise for X = 0 X=0 X = 0 . Consequently, writing r ( X ) = X 3 Q ( X , 0 ) r(X)=X^{3}Q(X,0) r ( X ) = X 3 Q ( X , 0 ) , we obtain the exact formal identity
g ( X , Y ) Q ( X , Y ) = X Y − r ( X ) − r ( Y ) . (20) g(X,Y)Q(X,Y)=XY-r(X)-r(Y). \tag*{(20)} g ( X , Y ) Q ( X , Y ) = X Y − r ( X ) − r ( Y ) . (20)
Substituting Y = X 2 Y=X^{2} Y = X 2 is valid in formal power series, since a coefficient of X n X^{n} X n receives contributions from only finitely many pairs ( i , j ) (i,j) ( i , j ) . It yields
r ( X ) + r ( X 2 ) = X 3 . r(X)+r(X^{2})=X^{3}. r ( X ) + r ( X 2 ) = X 3 .
For any positive integer N N N , repeated substitution gives
r ( X ) = ∑ k = 0 N − 1 ( − 1 ) k X 3 ⋅ 2 k + ( − 1 ) N r ( X 2 N ) . r(X)=\sum_{k=0}^{N-1}(-1)^{k}X^{3\cdot2^{k}}+(-1)^{N}r(X^{2^{N}}). r ( X ) = k = 0 ∑ N − 1 ( − 1 ) k X 3 ⋅ 2 k + ( − 1 ) N r ( X 2 N ) .
The last summand has order at least 3 ⋅ 2 N 3\cdot2^N 3 ⋅ 2 N because r ( X ) = X 3 Q ( X , 0 ) r(X)=X^3Q(X,0) r ( X ) = X 3 Q ( X , 0 ) . Thus a fixed coefficient is unaffected by that summand when N N N is sufficiently large, proving
r ( X ) = ∑ k ≥ 0 ( − 1 ) k X 3 ⋅ 2 k , Q ( X , 0 ) = ∑ k ≥ 0 ( − 1 ) k X 3 ⋅ 2 k − 3 . (21) r(X)=\sum_{k\ge0}(-1)^kX^{3\cdot2^k},\qquad Q(X,0)=\sum_{k\ge0}(-1)^kX^{3\cdot2^k-3}. \tag*{(21)} r ( X ) = k ≥ 0 ∑ ( − 1 ) k X 3 ⋅ 2 k , Q ( X , 0 ) = k ≥ 0 ∑ ( − 1 ) k X 3 ⋅ 2 k − 3 . (21)
The solution of (17) is
a ( t , i , j ) = { q i − 2 , j − 2 mod 3 , i , j ≥ 2 and t = i + j − 4 , 0 , otherwise. (22) a(t,i,j)=
\begin{cases}
q_{i-2,j-2\mathbin{\operatorname{mod}}3}, & i,j\ge2\text{ and }t=i+j-4,\\
0, & \text{otherwise.}
\end{cases} \tag*{(22)} a ( t , i , j ) = { q i − 2 , j − 2 mod 3 , 0 , i , j ≥ 2 and t = i + j − 4 , otherwise. (22)
We verify both the recurrence and its prescribed values. Put Δ ( t , i , j ) = t − i − j + 4 \Delta(t,i,j)=t-i-j+4 Δ ( t , i , j ) = t − i − j + 4 . For the three predecessor vectors,
1 − 2 − ( − 1 ) = 0 , 1 − ( − 1 ) − 2 = 0 , 2 − 1 − 1 = 0. 1-2-(-1)=0,\qquad1-(-1)-2=0,\qquad2-1-1=0. 1 − 2 − ( − 1 ) = 0 , 1 − ( − 1 ) − 2 = 0 , 2 − 1 − 1 = 0.
Hence Δ \Delta Δ is preserved by each predecessor step. At an interior point with Δ ≠ 0 \Delta\ne0 Δ = 0 , all terms in (17) vanish under the proposed formula. At an interior point with Δ = 0 \Delta=0 Δ = 0 , put u = i − 2 u=i-2 u = i − 2 and v = j − 2 v=j-2 v = j − 2 . The three predecessor values become q u − 2 , v + 1 q_{u-2,v+1} q u − 2 , v + 1 , q u + 1 , v − 2 q_{u+1,v-2} q u + 1 , v − 2 and q u − 1 , v − 1 q_{u-1,v-1} q u − 1 , v − 1 , reduced modulo 3. A negative index gives a boundary value zero. Since t = u + v ≥ 2 t=u+v\ge2 t = u + v ≥ 2 , the seed term of (19) is zero, and that equation proves (17) at the point.
The boundary cases also agree. If i < 2 i<2 i < 2 or j < 2 j<2 j < 2 , the formula is zero. If t = 0 t=0 t = 0 , the conditions i , j ≥ 2 i,j\ge2 i , j ≥ 2 and i + j = 4 i+j=4 i + j = 4 force i = j = 2 i=j=2 i = j = 2 , where the value is q 00 = 1 q_{00}=1 q 00 = 1 . If t = 1 t=1 t = 1 , the possible nonzero entries would be q 10 q_{10} q 10 and q 01 q_{01} q 01 , both zero. Thus the formula has the prescribed values on all boundary faces. Uniqueness of the recurrence proves (22) .
At ( t , i , j ) = ( n , n + 2 , 2 ) (t,i,j)=(n,n+2,2) ( t , i , j ) = ( n , n + 2 , 2 ) , the equality t = i + j − 4 t=i+j-4 t = i + j − 4 holds and the embedded coefficient is q n , 0 q_{n,0} q n , 0 . Extracting that coefficient from (21) gives (18) .
The nonzero positions of this section begin with 0, 3, 9, 21, 45, 93, 189, 381.
Why this section cannot be automatic in base three
A subset of N \mathbb{N} N is recognizable in base k k k if a finite automaton accepts its canonical base-k k k representations. We show that the support in (18) is not recognizable in base 3, using a repeated cycle in an accepting path.
Lemma 8.3. Let b , k ≥ 2 b,k\ge2 b , k ≥ 2 be multiplicatively independent , meaning that b u ≠ k v b^u\ne k^v b u = k v for positive integers u , v u,v u , v . For any positive integer C C C , the set { C ( b j − 1 ) : j ≥ 0 } \{C(b^j-1):j\ge0\} { C ( b j − 1 ) : j ≥ 0 } is not recognizable in base k k k .
Proof. Suppose a finite automaton accepts the canonical base-k k k representations. There are infinitely many such words, so an accepting path for a sufficiently long word contains a cycle after its first digit. There are fixed words u , v , w u,v,w u , v , w , with u u u starting in a nonzero digit and d = ∣ v ∣ > 0 d=|v|>0 d = ∣ v ∣ > 0 , such that every u v ℓ w uv^\ell w u v ℓ w , ℓ ≥ 0 \ell\ge0 ℓ ≥ 0 , is accepted. Let N ℓ N_\ell N ℓ be its numerical value. Summing the geometric progression for the repeated block gives
N ℓ = A k d ℓ + B N_\ell=Ak^{d\ell}+B N ℓ = A k d ℓ + B
for fixed rational A > 0 A>0 A > 0 , B B B . Hence
N ℓ + 1 + C N ℓ + C ⟶ k d . \frac{N_{\ell+1}+C}{N_\ell+C}\longrightarrow k^d. N ℓ + C N ℓ + 1 + C ⟶ k d .
Since each N ℓ + C = C b j ℓ N_\ell+C=Cb^{j_\ell} N ℓ + C = C b j ℓ , each ratio is an integral power of b b b . In a compact subinterval of ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) there are only finitely many integral powers of b b b . Convergence therefore forces the ratios eventually to equal their limit. Thus k d = b h k^d=b^h k d = b h for a positive integer h h h , a contradiction. ∎
If a a a were 3-automatic, Lemma 7.1 applied to the integer affine map n ↦ ( n , n + 2 , 2 ) n \mapsto(n,n+2,2) n ↦ ( n , n + 2 , 2 ) would make the section s ( n ) = a ( n , n + 2 , 2 ) s(n)=a(n,n+2,2) s ( n ) = a ( n , n + 2 , 2 ) 3-automatic. Coding its nonzero values as 1 gives a base-three recognizer for its support. Formula (17) and Lemma 8.3 , with b = 2 b=2 b = 2 , k = 3 k=3 k = 3 , C = 3 C=3 C = 3 , give a contradiction. This proves the assertion of Theorem 8.1 for p = 3 p=3 p = 3 .
The obstruction occurs for every prime
For completeness, replace the integer 2 controlling the dilation by an integer b ≥ 2 b \ge2 b ≥ 2 , and take
P b = { ( b − 1 , b , − 1 ) , ( b − 1 , − 1 , b ) , ( 2 b − 2 , b − 1 , b − 1 ) } . P_b=\{(b-1,b,-1),(b-1,-1,b),(2b-2,b-1,b-1)\}. P b = {( b − 1 , b , − 1 ) , ( b − 1 , − 1 , b ) , ( 2 b − 2 , b − 1 , b − 1 )} .
The initial domain is t < 2 b − 2 t<2b-2 t < 2 b − 2 or i < b i<b i < b or j < b j<b j < b . Set the single initial value at ( 0 , b , b ) (0,b,b) ( 0 , b , b ) to 1 and all other initial values to 0. The rule remains ( u , v , w ) ↦ u + v − w (u,v,w)\mapsto u+v-w ( u , v , w ) ↦ u + v − w . Define the integer array
q i , j = 1 ( i , j ) = ( 0 , 0 ) + q i − b , j + 1 + q i + 1 , j − b − q i − b + 1 , j − b + 1 . q_{i,j}=\mathbf{1}_{(i,j)=(0,0)}+q_{i-b,j+1}+q_{i+1,j-b}-q_{i-b+1,j-b+1}. q i , j = 1 ( i , j ) = ( 0 , 0 ) + q i − b , j + 1 + q i + 1 , j − b − q i − b + 1 , j − b + 1 .
with negative indices zero. Its terms are determined by smaller total degree. For 0 < i + j < 2 b − 2 0<i+j<2b-2 0 < i + j < 2 b − 2 , all values vanish: an induction leaves only possible predecessors ( 0 , 0 ) (0,0) ( 0 , 0 ) , and reaching that point with either of the first two shifts would require a negative coordinate, while the third shift requires total degree 2 b − 2 2b-2 2 b − 2 .
The preceding coefficient calculation, now with g b = ( X − Y b ) ( Y − X b ) g_b=(X-Y^b)(Y-X^b) g b = ( X − Y b ) ( Y − X b ) , gives
g b Q = X Y − r b ( X ) − r b ( Y ) , r b ( X ) = X b + 1 Q ( X , 0 ) , r b ( X ) + r b ( X b ) = X b + 1 . g_bQ=XY-r_b(X)-r_b(Y),\qquad r_b(X)=X^{b+1}Q(X,0),\qquad r_b(X)+r_b(X^b)=X^{b+1}. g b Q = X Y − r b ( X ) − r b ( Y ) , r b ( X ) = X b + 1 Q ( X , 0 ) , r b ( X ) + r b ( X b ) = X b + 1 .
It follows that
q n , 0 = { ( − 1 ) j , n = ( b + 1 ) ( b j − 1 ) , 0 , otherwise . q_{n,0}=
\begin{cases}
(-1)^j, & n=(b+1)(b^j-1),\\
0, & \text{otherwise}.
\end{cases} q n , 0 = { ( − 1 ) j , 0 , n = ( b + 1 ) ( b j − 1 ) , otherwise .
The embedding is a ( t , i , j ) = q i − b , j − b a(t,i,j)=q_{i-b,j-b} a ( t , i , j ) = q i − b , j − b on t = i + j − 2 b t=i+j-2b t = i + j − 2 b , zero elsewhere, reduced modulo p p p . Its initial layers agree by the vanishing just proved. Its section a ( n , n + b , b ) a(n,n+b,b) a ( n , n + b , b ) has support { ( b + 1 ) ( b j − 1 ) : j ≥ 0 } \{(b+1)(b^j-1):j\ge0\} {( b + 1 ) ( b j − 1 ) : j ≥ 0 } . If a a a were p p p -automatic, Lemma 7.1 applied to n ↦ ( n , n + b , b ) n\mapsto(n,n+b,b) n ↦ ( n , n + b , b ) would make this section p p p -automatic. Lemma 8.3 applies whenever b b b and p p p are multiplicatively independent. Choosing b = 2 b=2 b = 2 for odd p p p , and b = 3 b=3 b = 3 for p = 2 p=2 p = 2 , proves failure of the unrestricted assertion for every prime, already with the cyclic group F p \mathbb{F}_p F p .
The example also gives failure in every dimension n > 3 n>3 n > 3 . Append n − 3 n-3 n − 3 zero coordinates to each predecessor and prescribe the same boundary values independently of the added indices. Uniqueness makes the new solution independent of those indices as well. If it were p p p -automatic, feeding zero digits in the added coordinates would give an automaton for the original three-dimensional array, which is impossible.
Two different jumps and a fixed obstruction for every prime
The preceding symmetric example changes its jump size when the prime changes. Allowing two different jump sizes gives a single recurrence that fails in every prime characteristic. It also identifies when the same factorized construction becomes automatic. The factorization is an adaptation of [15 Section 4.5, Example 6] , not a separate source of the sparse-series method.
We first record the support test used in the nonautomatic case. Here the support of an array is the set of indices where its value is nonzero.
Lemma 8.4 (A finite union of geometric progressions). Let L , k ≥ 2 L,k \ge2 L , k ≥ 2 be multiplicatively independent , let A 1 , … , A s A_1,\ldots,A_s A 1 , … , A s be positive integers, and let C ∈ Z C \in\mathbb{Z} C ∈ Z . No infinite subset of
{ A i L j − C : 1 ≤ i ≤ s , j ≥ 0 } ∩ N \left\{A_iL^j-C:1\le i\le s,\ j\ge0\right\}\cap\mathbb{N} { A i L j − C : 1 ≤ i ≤ s , j ≥ 0 } ∩ N is recognizable in base k k k .
Proof. If such a subset were recognizable, the accepting-cycle argument in Lemma 8.3 would give accepted numbers N ℓ = a k d ℓ + b N_\ell=ak^{d\ell}+b N ℓ = a k d ℓ + b , where a > 0 a>0 a > 0 , d > 0 d>0 d > 0 and a , b a,b a , b are fixed rationals. Thus
N ℓ + 1 + C N ℓ + C ⟶ k d . \frac{N_{\ell+1}+C}{N_\ell+C}\longrightarrow k^d. N ℓ + C N ℓ + 1 + C ⟶ k d .
For sufficiently large ℓ \ell ℓ , each ratio belongs to { ( A i / A j ) L h : 1 ≤ i , j ≤ s , h ∈ Z } \{(A_i/A_j)L^h:1\le i,j\le s,\ h\in\mathbb{Z}\} {( A i / A j ) L h : 1 ≤ i , j ≤ s , h ∈ Z } . This set has finite intersection with any compact subinterval of ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) . Convergence forces the ratios to equal k d k^d k d eventually. Among the finitely many possible multipliers A i A_i A i , one occurs at two later indices ℓ \ell ℓ and ℓ + r \ell+r ℓ + r , where r > 0 r>0 r > 0 . Dividing those two terms gives k d r = L h k^{dr}=L^h k d r = L h for an integer h > 0 h>0 h > 0 , contrary to multiplicative independence.
For the positive case over prime powers, we need division by a polynomial whose constant coefficient may vanish. The existence of the formal quotient is an assumption in this lemma.
Lemma 8.5 (Exact polynomial division). Let R = Z / p e Z R=\mathbb{Z}/p^e\mathbb{Z} R = Z / p e Z , and let D ∈ R [ X ] D\in R[X] D ∈ R [ X ] have nonzero reduction modulo p p p . If F ∈ R [ [ X ] ] F\in R[[X]] F ∈ R [[ X ]] and the coefficients of D F DF D F are p p p -automatic, then the coefficients of F F F are p p p -automatic.
Proof. For e = 1 e=1 e = 1 , Theorem 5.1 makes D F DF D F algebraic, so F = ( D F ) / D F=(DF)/D F = ( D F ) / D is algebraic over F p ( X ) \mathbb{F}_p(X) F p ( X ) . It is already a formal series by assumption, and Theorem 5.1 applies again. For e > 1 e>1 e > 1 , reduction modulo p p p therefore gives an automatic series F ‾ \overline{F} F . Lift its coefficients to { 0 , … , p − 1 } \{0,\ldots,p-1\} { 0 , … , p − 1 } to obtain an automatic series U U U over R R R . Write F = U + p Z F=U+pZ F = U + pZ , with Z Z Z over Z / p e − 1 Z \mathbb{Z}/p^{e-1}\mathbb{Z} Z / p e − 1 Z . The coefficients of
D Z = D F − D U p DZ=\frac{DF-DU}{p} D Z = p D F − D U
are automatic. Multiplication by D D D uses a sum of translated coefficient arrays, one for each monomial of D D D . Subtraction and division by p p p on the ideal p R pR pR are codings between finite alphabets. Lemma 2.2 therefore preserves automaticity in these operations. The reduced polynomial still has nonzero reduction modulo p p p , so induction makes Z Z Z automatic. The coding F = U + p Z F=U+pZ F = U + pZ finishes the proof.
Theorem 8.6 (The two-parameter family). Let b , c ≥ 2 b,c\ge2 b , c ≥ 2 , let p p p be prime, and let e ≥ 1 e\ge1 e ≥ 1 . Use predecessors
P b , c = { ( b − 1 , b , − 1 ) , ( c − 1 , − 1 , c ) , ( b + c − 2 , b − 1 , c − 1 ) } P_{b,c}=\{(b-1,b,-1),(c-1,-1,c),(b+c-2,b-1,c-1)\} P b , c = {( b − 1 , b , − 1 ) , ( c − 1 , − 1 , c ) , ( b + c − 2 , b − 1 , c − 1 )} and the additive rule ( u , v , w ) ↦ u + v − w (u,v,w)\mapsto u+v-w ( u , v , w ) ↦ u + v − w over Z / p e Z \mathbb{Z}/p^e\mathbb{Z} Z / p e Z . On the boundary { t < b + c − 2 } ∪ { i < b } ∪ { j < c } \{t<b+c-2\}\cup\{i<b\}\cup\{j<c\} { t < b + c − 2 } ∪ { i < b } ∪ { j < c } , prescribe 1 1 1 at ( 0 , b , c ) (0,b,c) ( 0 , b , c ) and 0 0 0 elsewhere. The unique solution is p p p -automatic if and only if b c bc b c is a power of p p p .
Proof. Work first over the integers. Put q i j = 0 q_{ij}=0 q ij = 0 at negative indices and define
q i j = 1 i = j = 0 + q i − b , j + 1 + q i + 1 , j − c − q i − b + 1 , j − c + 1 . q_{ij}=1_{i=j=0}+q_{i-b,j+1}+q_{i+1,j-c}-q_{i-b+1,j-c+1}. q ij = 1 i = j = 0 + q i − b , j + 1 + q i + 1 , j − c − q i − b + 1 , j − c + 1 .
All right-hand indices in the nonnegative quadrant have smaller total degree. For 0 < i + j < b + c − 2 0<i+j<b+c-2 0 < i + j < b + c − 2 , induction gives q i j = 0 q_{ij}=0 q ij = 0 . Indeed, reaching the seed through either of the first two shifts would require a negative coordinate, and reaching it through the third requires ( i , j ) = ( b − 1 , c − 1 ) (i,j)=(b-1,c-1) ( i , j ) = ( b − 1 , c − 1 ) .
Set Q ( X , Y ) = ∑ q i j X i Y j Q(X,Y)=\sum q_{ij}X^iY^j Q ( X , Y ) = ∑ q ij X i Y j and
g = ( X − Y c ) ( Y − X b ) , R ( X ) = X b + 1 Q ( X , 0 ) , S ( Y ) = Y c + 1 Q ( 0 , Y ) . g=(X-Y^c)(Y-X^b),\qquad R(X)=X^{b+1}Q(X,0),\qquad S(Y)=Y^{c+1}Q(0,Y). g = ( X − Y c ) ( Y − X b ) , R ( X ) = X b + 1 Q ( X , 0 ) , S ( Y ) = Y c + 1 Q ( 0 , Y ) .
Coefficient extraction as in (20) gives
g Q = X Y − R ( X ) − S ( Y ) . gQ=XY-R(X)-S(Y). g Q = X Y − R ( X ) − S ( Y ) .
Substitute Y = X b Y=X^b Y = X b and X = Y c X=Y^c X = Y c in this identity. Both substitutions are valid formally. They give
R ( X ) + S ( X b ) = X b + 1 , R ( Y c ) + S ( Y ) = Y c + 1 . R(X)+S(X^b)=X^{b+1},\qquad R(Y^c)+S(Y)=Y^{c+1}. R ( X ) + S ( X b ) = X b + 1 , R ( Y c ) + S ( Y ) = Y c + 1 .
Eliminating S S S yields, with L = b c L=bc L = b c ,
R ( X ) − R ( X L ) = X b + 1 − X b ( c + 1 ) . R(X)-R(X^L)=X^{b+1}-X^{b(c+1)}. R ( X ) − R ( X L ) = X b + 1 − X b ( c + 1 ) .
Iteration is justified coefficient by coefficient because the order of the remaining term tends to infinity. Therefore
R ( X ) = ∑ r ≥ 0 ( X ( b + 1 ) L r − X b ( c + 1 ) L r ) . (23) R(X)=\sum_{r\geq0}\left(X^{(b+1)L^r}-X^{b(c+1)L^r}\right). \tag*{(23)} R ( X ) = r ≥ 0 ∑ ( X ( b + 1 ) L r − X b ( c + 1 ) L r ) . (23)
The corresponding formula for S S S exchanges b b b and c c c . The two exponent sets in (23) are disjoint:
1 < b ( c + 1 ) b + 1 < b c = L . 1<\frac{b(c+1)}{b+1}<bc=L. 1 < b + 1 b ( c + 1 ) < b c = L .
Thus their coefficients remain nonzero modulo every p e p^e p e .
The three-dimensional solution is
a ( t , i , j ) = { q i − b , j − c m o d p e , i ≥ b , j ≥ c , t = i + j − b − c , 0 , otherwise . a(t,i,j)=
\begin{cases}
q_{i-b,j-c}\bmod p^e, & i\geq b,\ j\geq c,\ t=i+j-b-c,\\
0, & \text{otherwise}.
\end{cases} a ( t , i , j ) = { q i − b , j − c mod p e , 0 , i ≥ b , j ≥ c , t = i + j − b − c , otherwise .
For each predecessor, its first coordinate is the sum of its other two coordinates. The equation t = i + j − b − c t=i+j-b-c t = i + j − b − c is consequently preserved under predecessor steps, and the recurrence on that plane becomes the displayed recurrence for q q q . The proved vanishing for 0 < i + j < b + c − 2 0<i+j<b+c-2 0 < i + j < b + c − 2 supplies the prescribed slices 0 ≤ t < b + c − 2 0\leq t<b+c-2 0 ≤ t < b + c − 2 . The other boundary faces are zero. Uniqueness therefore proves this embedding.
If L L L is not a power of p p p , it is multiplicatively independent of p p p . The section a ( n , n + b , c ) a(n,n+b,c) a ( n , n + b , c ) has support
{ ( b + 1 ) L r − ( b + 1 ) : r ≥ 0 } ∪ { b ( c + 1 ) L r − ( b + 1 ) : r ≥ 0 } . (24) \{(b+1)L^r-(b+1):r\geq0\}\cup\{b(c+1)L^r-(b+1):r\geq0\}. \tag*{(24)} {( b + 1 ) L r − ( b + 1 ) : r ≥ 0 } ∪ { b ( c + 1 ) L r − ( b + 1 ) : r ≥ 0 } . (24)
Lemma 8.4 says that this support is not recognizable in base p p p . If the full array were automatic, affine substitution and a nonzero-value coding would make the support recognizable. This contradiction proves nonautomaticity.
Suppose instead that L = p h L=p^h L = p h . The base-p p p representations of A p h r Ap^{hr} A p h r , for fixed A > 0 A>0 A > 0 , are the representation of A A A followed by h r hr h r zeros. A finite automaton recognizes them by checking the fixed prefix and counting the appended zeros modulo h h h . Formula (23) therefore gives automatic coefficient arrays for R R R and S S S modulo p e p^e p e . So X Y − R − S XY-R-S X Y − R − S is automatic. The coefficient of X Y XY X Y in g g g is 1 1 1 , hence g g g has nonzero reduction modulo p p p . Lemma 8.5 makes the coefficients of Q Q Q automatic. Finally, integer affine substitution and the automatic test t − i − j + b + c = 0 t-i-j+b+c=0 t − i − j + b + c = 0 make the embedded array automatic. The equality test is obtained by applying Lemma 7.1 to the indicator of { 0 } \{0\} { 0 } , extended by zero to the integers.
Corollary 8.7 (One fixed predecessor set for all primes). The fixed set
P = { ( 1 , 2 , − 1 ) , ( 2 , − 1 , 3 ) , ( 3 , 1 , 2 ) } P = \{(1,2,-1),(2,-1,3),(3,1,2)\} P = {( 1 , 2 , − 1 ) , ( 2 , − 1 , 3 ) , ( 3 , 1 , 2 )} with the rule ( u , v , w ) ↦ u + v − w (u,v,w) \mapsto u+v-w ( u , v , w ) ↦ u + v − w and the single boundary seed at ( 0 , 2 , 3 ) (0,2,3) ( 0 , 2 , 3 ) produces a non-p p p -automatic array over Z / p e Z \mathbb{Z}/p^{e}\mathbb{Z} Z / p e Z for every prime p p p and every e ≥ 1 e \ge1 e ≥ 1 .
Proof. Take b = 2 b=2 b = 2 , c = 3 c=3 c = 3 in Theorem 8.6 . The integer 6 is not a power of any prime.
For this set, the section a ( n , n + 2 , 3 ) a(n,n+2,3) a ( n , n + 2 , 3 ) is 1 at n = 3 ⋅ 6 r − 3 n=3\cdot6^{r}-3 n = 3 ⋅ 6 r − 3 , is − 1 -1 − 1 at n = 8 ⋅ 6 r − 3 n=8\cdot6^{r}-3 n = 8 ⋅ 6 r − 3 , and is zero elsewhere, with values reduced modulo p e p^{e} p e . Both the second and third predecessor coordinates contain entries of both signs. Together with Theorem 1.6 , this shows that the threshold of at most one such coordinate is sharp as a sufficient condition depending only on their number. It does not classify individual systems with two or more coordinates of both signs.
Verifying and constructing automata
For systems treated by algebraic power-series division, the proof establishes automaticity without directly giving a transition table. We can instead compute candidate kernel states from finite samples and verify the recurrence for every index. For one-dimensional sequences, kernel inference from finite prefixes is established, including the possibility of false identifications and tight bounds on the prefix length [1 Section 2.3 and Theorem 2.3] . The verification below uses the specified recurrence to decide whether a candidate computes its unique solution.
Proposition 9.1 (Finite verification of a candidate). Given automata for the boundary data, the additional sequence, and a candidate array u u u , one can decide whether u u u satisfies the prescribed recurrence at all indices. The procedure either certifies u = a u=a u = a or returns an index where the boundary condition or recurrence fails.
Proof. Construct automata for the interior mask and the assembled boundary function using Lemmas 2.2 and 2.3. For each predecessor, Proposition 7.3, with B = I B=I B = I and c = − v j c=-v_j c = − v j , constructs the shifted array u ( x − v j ) u(x-v_j) u ( x − v j ) , extended by the neutral element at negative indices. Use Lemma 2.1 to put all the machines in the least-significant-digit convention, and form their product as in § 2.2 . At a product state, let z z z be the candidate output, z j z_j z j the output for predecessor j j j , β \beta β the additional-sequence output, γ \gamma γ the assembled boundary output, and ι ∈ { 0 , 1 } \iota\in\{0,1\} ι ∈ { 0 , 1 } the interior mask. For the ordered group rule, give this state the Boolean output
κ ( z , z 1 , … , z m , β , γ , ι ) = { 1 , ι = 0 and z = γ , 1 , ι = 1 and z = α 1 ( z 1 ) ⋯ α m ( z m ) β , 0 , otherwise. \kappa(z,z_1,\ldots,z_m,\beta,\gamma,\iota)=
\begin{cases}
1, & \iota=0\ \text{and}\ z=\gamma,\\
1, & \iota=1\ \text{and}\ z=\alpha_1(z_1)\cdots\alpha_m(z_m)\beta,\\
0, & \text{otherwise.}
\end{cases} κ ( z , z 1 , … , z m , β , γ , ι ) = ⎩ ⎨ ⎧ 1 , 1 , 0 , ι = 0 and z = γ , ι = 1 and z = α 1 ( z 1 ) ⋯ α m ( z m ) β , otherwise.
This is a coding on a finite output alphabet. An arbitrary specified local rule on a finite alphabet can be checked by substituting that rule in the second comparison.
Enumerate the reachable product states by the construction in § 2.2 , recording a word reaching each new state. If a state outputs 0, its word r 0 ⋯ r ℓ − 1 r_0\cdots r_{\ell-1} r 0 ⋯ r ℓ − 1 gives the failing index
x = ∑ j < ℓ p j r j . x=\sum_{j<\ell}p^j r_j. x = j < ℓ ∑ p j r j .
The empty word checks x = 0 x=0 x = 0 . If every reachable state outputs 1, every index satisfies its boundary condition or its interior recurrence, as appropriate. Lemma 2.4 then gives u = a u=a u = a . ∎
Theorem 9.2 (A terminating search when the solution is automatic). Given a recurrence with a finite nonempty set of lexicographically positive predecessor offsets, a local rule on a finite output alphabet, and automatic compatible data, there is an algorithm that constructs and verifies an automaton whenever the unique solution is p p p -automatic. In particular, it terminates under the hypotheses of Theorem 1.6 .
Proof. For a positive integer B B B , compare sections of the solution on the finite set { 0 , … , B − 1 } n \{0,\ldots,B-1\}^{n} { 0 , … , B − 1 } n . A section is represented by a pair ( e , r ) (e,r) ( e , r ) and means the function x ↦ a ( p e x + r ) x\mapsto a(p^{e}x+r) x ↦ a ( p e x + r ) . Each requested value can be computed from the recurrence and data by induction on the positive weight in Lemma 2.4 .
Starting from a a a , process all digit sections of each retained representative. Retain a new representative only if its vector of sample values differs from those already retained. Otherwise use the existing representative with that vector. There are at most ∣ G ∣ B n |G|^{B^{n}} ∣ G ∣ B n sample vectors when the output alphabet is G G G , so this process terminates for each B B B . It defines a finite candidate machine, with a state’s output its representative’s value at zero. The sample contains zero, so the output is unchanged by zero padding.
Apply Proposition 9.1 . Return the candidate if it passes. Otherwise increase B B B and repeat. If a a a is automatic, its kernel is finite. For each pair of distinct kernel arrays, choose one index where they differ. All these finitely many indices lie in some cube { 0 , … , B 0 − 1 } n \{0,\ldots,B_{0}-1\}^{n} { 0 , … , B 0 − 1 } n . For B ≥ B 0 B\ge B_{0} B ≥ B 0 , comparison on that cube identifies kernel arrays correctly. The closure procedure then constructs the actual kernel machine, which passes verification. An earlier candidate that passes is also correct by uniqueness.
The theorem does not give a stopping criterion for a nonautomatic solution. It also gives no bound on the number of computational steps in terms of the recurrence’s input size. The coefficient samples propose a machine, and checking all reachable product states supplies its certificate.
Two certified binary examples
The first example has predecessors { ( 1 , 0 ) , ( 1 , 2 ) , ( 2 , − 2 ) } \{(1,0),(1,2),(2,-2)\} {( 1 , 0 ) , ( 1 , 2 ) , ( 2 , − 2 )} and satisfies
a ( m , n ) = a ( m − 1 , n ) + a ( m − 1 , n − 2 ) + a ( m − 2 , n + 2 ) + 1 ( m o d 2 ) ( m , n ≥ 2 ) , (25) a(m,n)=a(m-1,n)+a(m-1,n-2)+a(m-2,n+2)+1\pmod2\qquad(m,n\ge2), \tag*{(25)} a ( m , n ) = a ( m − 1 , n ) + a ( m − 1 , n − 2 ) + a ( m − 2 , n + 2 ) + 1 ( mod 2 ) ( m , n ≥ 2 ) , (25)
with a ( m , n ) = 1 a(m,n)=1 a ( m , n ) = 1 when m < 2 m<2 m < 2 or n < 2 n<2 n < 2 . The constant term matters: if it is omitted, the same boundary data give the constant array 1 1 1 , because 1 + 1 + 1 = 1 1+1+1=1 1 + 1 + 1 = 1 in F 2 \mathbb{F}_{2} F 2 . For (25) , sample cubes of side 1 , 2 , 3 1,2,3 1 , 2 , 3 give incorrect candidates. Verification returns failing indices ( 2 , 2 ) (2,2) ( 2 , 2 ) , ( 4 , 4 ) (4,4) ( 4 , 4 ) and ( 52 , 16 ) (52,16) ( 52 , 16 ) , respectively. Side 4 4 4 gives a candidate with 53 53 53 states, which passes the verification. The second example has
P = { ( 0 , 4 ) , ( 1 , 3 ) , ( 3 , 1 ) , ( 4 , 0 ) , ( 4 , 4 ) } P=\{(0,4),(1,3),(3,1),(4,0),(4,4)\} P = {( 0 , 4 ) , ( 1 , 3 ) , ( 3 , 1 ) , ( 4 , 0 ) , ( 4 , 4 )}
and rule a ( x ) = ∑ v ∈ P a ( x − v ) + 1 a(x)=\sum_{v\in P}a(x-v)+1 a ( x ) = ∑ v ∈ P a ( x − v ) + 1 over F 2 \mathbb{F}_{2} F 2 , with unit boundary data on m < 4 m<4 m < 4 or n < 4 n<4 n < 4 . For this example, side 6 6 6 gives a verified candidate with 254 254 254 states.
Table 3 gives state counts and block-rule counts for these two specified infinite arrays. The digit automata read the coordinate digits together, with zero padding allowed. A numerical block is a 16 × 16 16\times16 16 × 16 array at an origin ( 16 m , 16 n ) (16m,16n) ( 16 m , 16 n ) . The numerical substitution replaces each block by the corresponding 32 × 32 32\times32 32 × 32 array. A colored substitution may use different labels for the same numerical block, and distinct labels may share a display color.
Table 3. Counts for the two binary recurrences in § 9.1 . The first two numerical columns give minimal automaton state counts for the indicated reading directions, using binary digit pairs and allowing zero padding. The Blocks column counts distinct 16 × 16 16 \times16 16 × 16 numerical blocks at origins ( 16 m , 16 n ) (16m, 16n) ( 16 m , 16 n ) . The Labels column counts states of the reconstructed colored substitution. Both substitutions have scale factor 2.
The verification programs, input data and computational certificates are available in the accompanying repository.4 All file paths in this paper are relative to the repository root. The commands in README.txt reproduce the reported computations.
The script research/certify_original_examples.py produces the full transition tables and certificates. The recurrence checks explore 686 reachable product states for the first example and 552 493 for the second. At each reachable state, the boundary or recurrence comparison holds. The minimization procedure in § 2.2 , which refines states by their outputs and successor classes, certifies the minimal state counts in the table.
The block certificate examines every reachable state of each most-significant-digit machine. At such a state, four further digit pairs give its 16 × 16 16 \times16 16 × 16 block, and five give its 32 × 32 32 \times32 32 × 32 expansion. The certificate checks that equal smaller blocks always have equal expansions, that all four child blocks belong to the same collection of numerical blocks, and that the initial block is its own upper left child. These identities make substitution iteration agree with the array on squares of side 16 ⋅ 2 r 16 \cdot2^r 16 ⋅ 2 r for every r ≥ 0 r \ge0 r ≥ 0 . The colored-state transitions decode to these numerical rules.
For reproduction, the two numerical images and the two colored images distributed with the examples each have 512 2 = 262 144 512^2 = 262\,144 51 2 2 = 262 144 pixels. The numerical images match the respective recurrences at all displayed positions. Every reachable most-significant-digit state occurs among the displayed positions in each colored image, and its assigned color is consistent across all occurrences. The resulting colored machines decode to the numerical block rules at all indices by the preceding finite checks. The 44 and 212 labels use 39 and 151 distinct RGB colors, respectively, because the palettes repeat some colors.
Nonabelian examples
The Heisenberg group
The Heisenberg group H = U T 3 ( F 3 ) H = \mathrm{UT}_3(\mathbb{F}_3) H = UT 3 ( F 3 ) consists of the 27 matrices
( x , y , z ) ⟷ ( 1 x z 0 1 y 0 0 1 ) , x , y , z ∈ F 3 . (x,y,z) \longleftrightarrow\begin{pmatrix} 1 & x & z \\ 0 & 1 & y \\ 0 & 0 & 1 \end{pmatrix}, \qquad x,y,z \in\mathbb{F}_3. ( x , y , z ) ⟷ 1 0 0 x 1 0 z y 1 , x , y , z ∈ F 3 .
All arithmetic below is modulo 3. Matrix multiplication gives
( x , y , z ) ( u , v , w ) = ( x + u , y + v , z + w + x v ) . (26) (x,y,z)(u,v,w) = (x+u,y+v,z+w+xv). \tag*{(26)} ( x , y , z ) ( u , v , w ) = ( x + u , y + v , z + w + xv ) . (26)
The identity is ( 0 , 0 , 0 ) (0,0,0) ( 0 , 0 , 0 ) and the inverse of ( x , y , z ) (x,y,z) ( x , y , z ) is ( − x , − y , x y − z ) (-x,-y,xy-z) ( − x , − y , x y − z ) . With X = ( 1 , 0 , 0 ) X=(1,0,0) X = ( 1 , 0 , 0 ) and Y = ( 0 , 1 , 0 ) Y=(0,1,0) Y = ( 0 , 1 , 0 ) ,
X Y = ( 1 , 1 , 1 ) , Y X = ( 1 , 1 , 0 ) . XY=(1,1,1),\qquad YX=(1,1,0). X Y = ( 1 , 1 , 1 ) , Y X = ( 1 , 1 , 0 ) .
Thus the multiplication is noncommutative. Its center, the set of elements commuting with the whole group, consists of ( 0 , 0 , z ) (0,0,z) ( 0 , 0 , z ) , and the central coordinate is where the multiplication order is recorded. A commutator measures the failure of two elements to commute. With the convention [ g , h ] = g h g − 1 h − 1 [g,h]=ghg^{-1}h^{-1} [ g , h ] = g h g − 1 h − 1 ,
[ ( x , y , z ) , ( u , v , w ) ] = ( 0 , 0 , x v − u y ) . [(x,y,z),(u,v,w)]=(0,0,xv-uy). [( x , y , z ) , ( u , v , w )] = ( 0 , 0 , xv − u y ) .
A homomorphism rule on a group of order 81
Take G = H × ( F 3 , + ) G=H\times(\mathbb{F}_3,+) G = H × ( F 3 , + ) and write elements as ( x , y , z , t ) (x,y,z,t) ( x , y , z , t ) . Define
α ( x , y , z , t ) = ( y , x , x y − z , t ) , β ( x , y , z , t ) = ( 0 , 0 , t , t ) . \alpha(x,y,z,t)=(y,x,xy-z,t),\qquad\beta(x,y,z,t)=(0,0,t,t). α ( x , y , z , t ) = ( y , x , x y − z , t ) , β ( x , y , z , t ) = ( 0 , 0 , t , t ) .
For g = ( x , y , z , t ) g=(x,y,z,t) g = ( x , y , z , t ) and h = ( u , v , w , s ) h=(u,v,w,s) h = ( u , v , w , s ) , the central coordinate of α ( g h ) \alpha(gh) α ( g h ) is
( x + u ) ( y + v ) − ( z + w + x v ) = x y + u v + u y − z − w . (x+u)(y+v)-(z+w+xv)=xy+uv+uy-z-w. ( x + u ) ( y + v ) − ( z + w + xv ) = x y + uv + u y − z − w .
It equals the central coordinate of α ( g ) α ( h ) \alpha(g)\alpha(h) α ( g ) α ( h ) , and the other coordinates also agree by the displayed formulas. Thus α \alpha α is an endomorphism. Applying it twice gives g g g , so it is an involutive automorphism. The map β \beta β is an endomorphism because its two nonzero coordinates depend additively on t t t . Its image is central because ( 0 , 0 , t ) (0,0,t) ( 0 , 0 , t ) commutes with every element of H H H . Consequently
h ( g 1 , g 2 , g 3 ) = α ( g 1 ) β ( g 2 ) β ( g 3 ) (27) h(g_1,g_2,g_3)=\alpha(g_1)\beta(g_2)\beta(g_3) \tag*{(27)} h ( g 1 , g 2 , g 3 ) = α ( g 1 ) β ( g 2 ) β ( g 3 ) (27)
is a group homomorphism G 3 → G G^3\to G G 3 → G : factors from different input images commute. All three inputs matter, since α \alpha α is bijective and β \beta β is nonconstant.
Prescribe the compatible periodic boundaries
a ( 0 , n ) = ( n m o d 3 , 1 , 0 , 1 ) , a ( m , 0 ) = α m ( 0 , 1 , 0 , 1 ) , a(0,n)=(n\bmod3,1,0,1),\qquad a(m,0)=\alpha^m(0,1,0,1), a ( 0 , n ) = ( n mod 3 , 1 , 0 , 1 ) , a ( m , 0 ) = α m ( 0 , 1 , 0 , 1 ) ,
and for m , n ≥ 1 m,n\ge1 m , n ≥ 1 put
a ( m , n ) = α ( a ( m − 1 , n ) ) β ( a ( m , n − 1 ) ) β ( a ( m − 1 , n − 1 ) ) . (28) a(m,n)=\alpha(a(m-1,n))\beta(a(m,n-1))\beta(a(m-1,n-1)). \tag*{(28)} a ( m , n ) = α ( a ( m − 1 , n )) β ( a ( m , n − 1 )) β ( a ( m − 1 , n − 1 )) . (28)
The predecessors are ( 1 , 0 ) (1,0) ( 1 , 0 ) , ( 0 , 1 ) (0,1) ( 0 , 1 ) , ( 1 , 1 ) (1,1) ( 1 , 1 ) . Corollary 1.4 proves 3-automaticity.
Writing a = ( x , y , z , t ) a=(x,y,z,t) a = ( x , y , z , t ) makes the mechanism explicit:
x ( m , n ) = y ( m − 1 , n ) , y ( m , n ) = x ( m − 1 , n ) , t ( m , n ) = t ( m − 1 , n ) + t ( m , n − 1 ) + t ( m − 1 , n − 1 ) , z ( m , n ) = x ( m − 1 , n ) y ( m − 1 , n ) − z ( m − 1 , n ) + t ( m , n − 1 ) + t ( m − 1 , n − 1 ) . \begin{aligned}
x(m,n)&=y(m-1,n), & y(m,n)&=x(m-1,n),\\
t(m,n)&=t(m-1,n)+t(m,n-1)+t(m-1,n-1),\\
z(m,n)&=x(m-1,n)y(m-1,n)-z(m-1,n)\\
&\quad{}+t(m,n-1)+t(m-1,n-1).
\end{aligned} x ( m , n ) t ( m , n ) z ( m , n ) = y ( m − 1 , n ) , = t ( m − 1 , n ) + t ( m , n − 1 ) + t ( m − 1 , n − 1 ) , = x ( m − 1 , n ) y ( m − 1 , n ) − z ( m − 1 , n ) + t ( m , n − 1 ) + t ( m − 1 , n − 1 ) . y ( m , n ) = x ( m − 1 , n ) ,
The boundary and the first two coordinate equations give ( x , y ) = ( n m o d 3 , 1 ) (x,y)=(n\bmod3,1) ( x , y ) = ( n mod 3 , 1 ) for even m m m and ( 1 , n m o d 3 ) (1,n\bmod3) ( 1 , n mod 3 ) for odd m m m . In particular, x y = n m o d 3 xy=n\bmod3 x y = n mod 3 throughout the array.
The Delannoy coordinate
The Delannoy number D m , n D_{m,n} D m , n counts paths in N 2 \mathbb{N}^2 N 2 from ( 0 , 0 ) (0,0) ( 0 , 0 ) to ( m , n ) (m,n) ( m , n ) whose steps are ( 1 , 0 ) (1,0) ( 1 , 0 ) , ( 0 , 1 ) (0,1) ( 0 , 1 ) or ( 1 , 1 ) (1,1) ( 1 , 1 ) . There is one path along either coordinate axis, so D m , 0 = D 0 , n = 1 D_{m,0}=D_{0,n}=1 D m , 0 = D 0 , n = 1 . For m , n ≥ 1 m,n\geq1 m , n ≥ 1 , partitioning paths according to their last step gives
D m , n = D m − 1 , n + D m , n − 1 + D m − 1 , n − 1 . (29) D_{m,n}=D_{m-1,n}+D_{m,n-1}+D_{m-1,n-1}. \tag*{(29)} D m , n = D m − 1 , n + D m , n − 1 + D m − 1 , n − 1 . (29)
For example, the three paths to ( 1 , 1 ) (1,1) ( 1 , 1 ) are the two possible orders of the horizontal and vertical steps, and the single diagonal step. Hence D 1 , 1 = 3 D_{1,1}=3 D 1 , 1 = 3 .
Prunescu [9 Definition 1.2 and Theorem 4.4] studies this recurrence over finite fields with a coefficient on the diagonal term and proves identities for its residue blocks. Taking that coefficient to be 1 gives the Delannoy residues used here.
Proposition 10.1. The fourth coordinate of the group recurrence (28) is t ( m , n ) = D m , n m o d 3 t(m,n)=D_{m,n}\bmod3 t ( m , n ) = D m , n mod 3 .
Proof. Both prescribed boundaries have fourth coordinate 1. The maps α \alpha α and β \beta β each preserve the input’s fourth coordinate, and multiplication in the last factor of G G G adds those coordinates. Thus t t t satisfies (28) modulo 3 with the same boundary values. Induction on m + n m+n m + n identifies it with $D_{m,n}\bmod 3.
We call t t t the Delannoy coordinate because of this identity. It enters the equation for z z z at ( m , n − 1 ) (m,n-1) ( m , n − 1 ) and ( m − 1 , n − 1 ) (m-1,n-1) ( m − 1 , n − 1 ) . The equation for z z z also contains x ( m − 1 , n ) y ( m − 1 , n ) − z ( m − 1 , n ) x(m-1,n)y(m-1,n)-z(m-1,n) x ( m − 1 , n ) y ( m − 1 , n ) − z ( m − 1 , n ) from the automorphism α \alpha α . Figure 1 shows these two coordinates over the square { 0 , … , 242 } 2 \{0,\ldots,242\}^2 { 0 , … , 242 } 2 .
Figure 1. The homomorphism example on G = U T 3 ( F 3 ) × ( F 3 , + ) G = \mathrm{UT}_3(\mathbb{F}_3) \times(\mathbb{F}_3,+) G = UT 3 ( F 3 ) × ( F 3 , + ) , of order 81, for $0 \leq m,n < 243. The coordinate n n n increases to the right and m m m downwards from the upper left corner. Each pixel block shows a residue modulo 3. The left panel displays the central coordinate z z z and the right panel displays the Delannoy coordinate t t t . Each full group value is a tuple ( x , y , z , t ) (x,y,z,t) ( x , y , z , t ) .
Two interior values witness noncommutativity:
a ( 1 , 1 ) = ( 1 , 1 , 0 , 0 ) , a ( 1 , 2 ) = ( 1 , 2 , 0 , 2 ) , [ a ( 1 , 1 ) , a ( 1 , 2 ) ] = ( 0 , 0 , 1 , 0 ) ≠ 1. a(1,1)=(1,1,0,0),\qquad a(1,2)=(1,2,0,2),\qquad[a(1,1),a(1,2)]=(0,0,1,0)\ne1. a ( 1 , 1 ) = ( 1 , 1 , 0 , 0 ) , a ( 1 , 2 ) = ( 1 , 2 , 0 , 2 ) , [ a ( 1 , 1 ) , a ( 1 , 2 )] = ( 0 , 0 , 1 , 0 ) = 1.
Thus the solution is not contained in an abelian subgroup. Among the 59 049 values at 0 ≤ m , n < 243 0\leq m,n<243 0 ≤ m , n < 243 , direct evaluation of the recurrence gives 39 distinct elements of G G G . The computation and its checks are described in § 11 .
Ordered multiplication with a negative predecessor
We next combine ordered multiplication in H H H with a negative predecessor coordinate. Put a ( 0 , 0 ) = 1 a(0,0)=1 a ( 0 , 0 ) = 1 and prescribe
a ( 0 , n ) = Y ( n ≥ 1 ) , a ( m , 0 ) = X ( m ≥ 1 ) . a(0,n)=Y \quad(n\ge1), \qquad a(m,0)=X \quad(m\ge1). a ( 0 , n ) = Y ( n ≥ 1 ) , a ( m , 0 ) = X ( m ≥ 1 ) .
For m , n ≥ 1 m,n\ge1 m , n ≥ 1 define
a ( m , n ) = a ( m − 1 , n + 1 ) a ( m , n − 1 ) . (30) a(m,n)=a(m-1,n+1)a(m,n-1). \tag*{(30)} a ( m , n ) = a ( m − 1 , n + 1 ) a ( m , n − 1 ) . (30)
Its predecessor vectors are ( 1 , − 1 ) (1,-1) ( 1 , − 1 ) and ( 0 , 1 ) (0,1) ( 0 , 1 ) , both lexicographically positive. The negative entry is confined to the second coordinate. The weight 2 m + n 2m+n 2 m + n decreases by 1 for either predecessor, which gives a direct well-founded construction.
Proposition 10.2. The array in (29) is 3-automatic, takes values outside every abelian subgroup of H H H , and depends on the order of multiplication.
Proof. Apply Theorem 1.3 with both endomorphisms equal to the identity. The boundary data are automatic, and the sign condition holds. Direct computation gives
a ( 1 , 1 ) = ( 1 , 1 , 0 ) , a ( 1 , 2 ) = ( 1 , 2 , 0 ) , [ a ( 1 , 1 ) , a ( 1 , 2 ) ] = ( 0 , 0 , 1 ) . a(1,1)=(1,1,0), \qquad a(1,2)=(1,2,0), \qquad[a(1,1),a(1,2)]=(0,0,1). a ( 1 , 1 ) = ( 1 , 1 , 0 ) , a ( 1 , 2 ) = ( 1 , 2 , 0 ) , [ a ( 1 , 1 ) , a ( 1 , 2 )] = ( 0 , 0 , 1 ) .
These two interior values cannot lie in a common abelian subgroup. Already at ( 1 , 1 ) (1,1) ( 1 , 1 ) the stated order gives Y X YX Y X , while the reversed order gives X Y XY X Y , which are different.
Multiplication H 2 → H H^2\to H H 2 → H is not a group homomorphism when H H H is noncommutative. This example uses the stronger ordered-product theorem. The order-81 example satisfies Corollary 1.4.
For an elementary view of the proof, write L = ( m − 1 , n + 1 ) L=(m-1,n+1) L = ( m − 1 , n + 1 ) and D = ( m , n − 1 ) D=(m,n-1) D = ( m , n − 1 ) . Its coordinates obey
x = x L + x D , y = y L + y D , z = z L + z D + x L y D . x=x_L+x_D,\qquad y=y_L+y_D,\qquad z=z_L+z_D+x_Ly_D. x = x L + x D , y = y L + y D , z = z L + z D + x L y D .
The quotient coordinates x , y x,y x , y are automatic by the abelian theorem with the allowed negative direction. Their product x L y D x_Ly_D x L y D is an automatic affine term. Apply that theorem once more to get automatic z z z . This application of the abelian theorem supplies the central coordinate in the group induction. All boundary central coordinates are zero, but a ( 2 , 2 ) = ( 0 , 2 , 2 ) a(2,2)=(0,2,2) a ( 2 , 2 ) = ( 0 , 2 , 2 ) . Consequently the nonzero central pattern is produced by the group multiplication itself. Replacing it by coordinatewise addition would make the central coordinate identically zero.
The effect of reversing multiplication
Let a r e v a^{\mathrm{rev}} a rev have the same boundary and reversed product in (29). Define
τ ( x , y , z ) = ( x , y , x y − z ) . \tau(x,y,z)=(x,y,xy-z). τ ( x , y , z ) = ( x , y , x y − z ) .
Calculation gives τ ( g h ) = τ ( h ) τ ( g ) \tau(gh)=\tau(h)\tau(g) τ ( g h ) = τ ( h ) τ ( g ) and τ ( X ) = X \tau(X)=X τ ( X ) = X , τ ( Y ) = Y \tau(Y)=Y τ ( Y ) = Y . Induction on 2 m + n 2m+n 2 m + n proves the exact identity
a r e v ( m , n ) = τ ( a ( m , n ) ) , z r e v ( m , n ) = x ( m , n ) y ( m , n ) − z ( m , n ) . a^{\mathrm{rev}}(m,n)=\tau(a(m,n)),\qquad z^{\mathrm{rev}}(m,n)=x(m,n)y(m,n)-z(m,n). a rev ( m , n ) = τ ( a ( m , n )) , z rev ( m , n ) = x ( m , n ) y ( m , n ) − z ( m , n ) .
The two arrays have the same coordinates x , y x,y x , y . Among the 59 049 positions in 0 ≤ m , n < 243 0\le m,n<243 0 ≤ m , n < 243 , direct evaluation finds 17 737 positions where their central coordinates differ. All 27 elements of H H H occur in this square. Figure 2 compares the two central coordinates.
Figure 2. Ordered multiplication in H = U T 3 ( F 3 ) H = \mathrm{UT}_3(\mathbb{F}_3) H = UT 3 ( F 3 ) , of order 27, using the negative predecessor ( 1 , − 1 ) (1,-1) ( 1 , − 1 ) . Coordinates run from 0 to 242, with n n n to the right and m m m down. The two panels differ only in the order of multiplication. Each pixel block shows the residue modulo 3 of the central coordinate, with z z z on the left and x y − z xy-z x y − z on the right. The other two coordinates agree between the arrays.
Exact computations on the displayed squares
The figures and counts concern the square S = { ( m , n ) : 0 ≤ m , n < 243 } S = \{(m,n): 0 \le m,n < 243\} S = {( m , n ) : 0 ≤ m , n < 243 } , which contains 59 049 positions. The computation evaluates the specified recurrences at all positions in this square and records group elements as residue tuples. Distinct values are counted as distinct tuples, without identifying values by an automorphism or any other equivalence relation. Table 4 records the counts.
Table 4. Exact counts on S = { 0 , … , 242 } 2 S = \{0,\ldots,242\}^2 S = { 0 , … , 242 } 2 , containing 59 049 positions. Distinct values are counted as group elements. The final row compares the two multiplication orders at each position.
The last count compares the full group values. Since reversing the product preserves x x x and y y y , it is also the count of positions where the central coordinate changes.
For the order-81 example, evaluation proceeds by increasing m m m and, within a row, increasing n n n . The three predecessors in (27) have already been evaluated. For the negative predecessor in (29), a rectangular truncation would omit required values at n + 1 n+1 n + 1 . Instead, for a square of side N N N , row m m m is evaluated through n = 2 N − 2 − m n = 2N - 2 - m n = 2 N − 2 − m , for 0 ≤ m < N 0 \le m < N 0 ≤ m < N . The preceding row is one entry longer, so its value at n + 1 n+1 n + 1 is available. The current row’s value at n − 1 n-1 n − 1 is also available. Because 2 N − 2 − m ≥ N − 1 2N - 2 - m \ge N - 1 2 N − 2 − m ≥ N − 1 , the computation covers the entire requested square before cropping. This proves that the computed entries agree with the infinite recurrence at all N 2 N^2 N 2 positions used for each count.
The repository cited in footnote 1 includes the script examples/nonabelian_examples.py, which performs these evaluations using exact arithmetic modulo 3. It writes the images, small arrays and counts under examples/generated/nonabelian/, including verification.json. It also checks the two endomorphism identities and centrality of the image of β \beta β on all 81 2 = 6 561 81^2 = 6\,561 8 1 2 = 6 561 ordered pairs in each case. Associativity in H H H is checked on all 27 3 = 19 683 27^3 = 19\,683 2 7 3 = 19 683 ordered triples. An independent computation ordered by the weight 2 m + n 2m+n 2 m + n checks the negative recurrence on 0 ≤ m , n < 35 0 \le m,n < 35 0 ≤ m , n < 35 . The identity with τ \tau τ is checked at all 59 049 displayed positions.
We also check the Delannoy coordinate independently. Define
F ( X , Y ) = ∑ m , n ≥ 0 D m , n X m Y n , Q = 1 − X − Y − X Y . F(X,Y) = \sum_{m,n \ge0} D_{m,n}X^mY^n,\qquad Q = 1-X-Y-XY. F ( X , Y ) = m , n ≥ 0 ∑ D m , n X m Y n , Q = 1 − X − Y − X Y .
The recurrence cancels the coefficients of Q F QF QF off the axes. On a positive axis, the unit boundary gives 1 − 1 = 0 1-1=0 1 − 1 = 0 , and the constant coefficient is 1. Therefore F = 1 / Q F=1/Q F = 1/ Q . Over F 3 \mathbb{F}_3 F 3 , Q 3 = Q ( X 3 , Y 3 ) Q^3=Q(X^3,Y^3) Q 3 = Q ( X 3 , Y 3 ) , so
F ( X , Y ) = Q ( X , Y ) 2 F ( X 3 , Y 3 ) , Q 2 = ∑ 0 ≤ i , j < 3 B i j X i Y j , B = ( 1 1 1 1 0 2 1 2 1 ) . F(X,Y) = Q(X,Y)^2F(X^3,Y^3),\qquad Q^2 = \sum_{0 \le i,j < 3}B_{ij}X^iY^j,\qquad B=\begin{pmatrix}1&1&1\\1&0&2\\1&2&1\end{pmatrix}. F ( X , Y ) = Q ( X , Y ) 2 F ( X 3 , Y 3 ) , Q 2 = 0 ≤ i , j < 3 ∑ B ij X i Y j , B = 1 1 1 1 0 2 1 2 1 .
Coefficient extraction gives D 3 m + i , 3 n + j ≡ B i j D m , n ( m o d 3 ) D_{3m+i,3n+j} \equiv B_{ij}D_{m,n}\pmod3 D 3 m + i , 3 n + j ≡ B ij D m , n ( mod 3 ) . Iteration computes a residue as the product of entries B i j B_{ij} B ij selected by successive ternary digit pairs. The script compares this formula with the coordinate at every displayed position.
These computations establish the counts on S S S and check the implementation of the examples. Automaticity of the infinite arrays follows from the theorems and proofs in Sections 5–10.
An exact Delannoy count modulo 27
The Delannoy numbers defined in § 10.2.1 also permit exact counts of nonzero residues. For r ≥ 0 r \ge0 r ≥ 0 , put
N 27 ( r ) = ∣ { ( m , n ) : 0 ≤ m , n < 3 r , D m , n ≠ 0 ( m o d 27 ) } ∣ . N_{27}(r)=\left|\left\{(m,n):0\le m,n<3^r,\ D_{m,n}\ne0\pmod{27}\right\}\right|. N 27 ( r ) = ∣ { ( m , n ) : 0 ≤ m , n < 3 r , D m , n = 0 ( mod 27 ) } ∣ .
Laurberg [2 Eq. (10.47), p. 164] proposes the following formula from computed values. We give a certificate consisting of a transition table and identities between polynomial and integer vectors. These identities prove the formula for all r ≥ 4 r \ge4 r ≥ 4 .
Theorem 12.1. For every r ≥ 4 r \ge4 r ≥ 4 ,
N 27 ( r ) = 8 r − 4 ( 18 r 2 + 471 r + 3993 ) . N_{27}(r)=8^{r-4}(18r^2+471r+3993). N 27 ( r ) = 8 r − 4 ( 18 r 2 + 471 r + 3993 ) . Consequently, the number of zero entries in that square is 9 r − N 27 ( r ) 9^r-N_{27}(r) 9 r − N 27 ( r ) .
Proof. Work over R = Z / 27 Z R=\mathbb{Z}/27\mathbb{Z} R = Z /27 Z . The generating function of the Delannoy array is 1 / Q 1/Q 1/ Q , where Q = 1 − X − Y − X Y Q=1-X-Y-XY Q = 1 − X − Y − X Y , as proved in § 11 . The construction in Theorem 3.5 uses states P / Q 9 P/Q^9 P / Q 9 , starts with P = Q 8 P=Q^8 P = Q 8 , and has transitions
P ⟼ Λ i , j ( P Q 18 ) , 0 ≤ i , j < 3. P\longmapsto\Lambda_{i,j}(P Q^{18}),\qquad0\le i,j<3. P ⟼ Λ i , j ( P Q 18 ) , 0 ≤ i , j < 3.
Enumerating the reachable polynomials gives 1362 states. The file research/generated/mod27_rational_machine.json in the repository cited in footnote 1 records their coefficient arrays. The script research/verify_mod27.py verifies the initial polynomial, reachability, constant-coefficient outputs, and all 9 ⋅ 1362 = 12258 9\cdot1362=12258 9 ⋅ 1362 = 12258 transition identities over R [ X , Y ] R[X,Y] R [ X , Y ] . Each polynomial has degree at most 9 in each variable, so the state bound of Theorem 3.5 proves termination of this enumeration.
Index the states starting from q 0 = 0 q_0=0 q 0 = 0 , and define the integer matrix
M q , q ′ = ∣ { ( i , j ) : δ ( q , ( i , j ) ) = q ′ } ∣ . M_{q,q'}=\left|\left\{(i,j):\delta(q,(i,j))=q'\right\}\right|. M q , q ′ = ∣ { ( i , j ) : δ ( q , ( i , j )) = q ′ } ∣ .
Let e 0 e_0 e 0 be the column vector indexed by the 1362 states, with entry 1 at state 0 and 0 elsewhere. Let v v v be the column vector with v q = 1 v_q=1 v q = 1 when state q q q outputs a nonzero residue modulo 27, and v q = 0 v_q=0 v q = 0 otherwise. Each coordinate pair below 3 r 3^r 3 r has one padded digit representation of length r r r , so
N 27 ( r ) = e 0 T M r v . N_{27}(r)=e_0^{\mathsf{T}}M^r v. N 27 ( r ) = e 0 T M r v .
The certificate stores the eight integer vectors v , M v , … , M 7 v v,Mv,\ldots,M^7v v , M v , … , M 7 v and checks, in all 1362 coordinates, the identity
M 7 v − 24 M 6 v + 192 M 5 v − 512 M 4 v = 0. (31) M^7v-24M^6v+192M^5v-512M^4v=0. \tag*{(31)} M 7 v − 24 M 6 v + 192 M 5 v − 512 M 4 v = 0. (31)
Multiplying by e 0 T M r − 4 e_0^{\mathsf{T}}M^{r-4} e 0 T M r − 4 gives, for r ≥ 4 r\ge4 r ≥ 4 ,
N 27 ( r + 3 ) − 24 N 27 ( r + 2 ) + 192 N 27 ( r + 1 ) − 512 N 27 ( r ) = 0. N_{27}(r+3)-24N_{27}(r+2)+192N_{27}(r+1)-512N_{27}(r)=0. N 27 ( r + 3 ) − 24 N 27 ( r + 2 ) + 192 N 27 ( r + 1 ) − 512 N 27 ( r ) = 0.
The same certificate gives
N 27 ( 4 ) = 6165 , N 27 ( 5 ) = 54384 , N 27 ( 6 ) = 477888. N_{27}(4)=6165,\qquad N_{27}(5)=54384,\qquad N_{27}(6)=477888. N 27 ( 4 ) = 6165 , N 27 ( 5 ) = 54384 , N 27 ( 6 ) = 477888.
The proposed formula has these three values. It satisfies the displayed recurrence because applying the operator f ( r ) ↦ f ( r + 1 ) − 8 f ( r ) f(r)\mapsto f(r+1)-8f(r) f ( r ) ↦ f ( r + 1 ) − 8 f ( r ) three times to 8 r 8^r 8 r times a quadratic polynomial gives zero. The recurrence and initial values therefore prove the formula.
As an independent check, the script also evaluates the Delannoy recurrence directly on a 243 × 243 243 \times243 243 × 243 square and compares all 59 049 residues with the automaton.
Corollary 12.2. The proportion of entries divisible by 27 in { 0 , … , N − 1 } 2 \{0,\ldots,N-1\}^{2} { 0 , … , N − 1 } 2 tends to 1 as N → ∞ N \to\infty N → ∞ .
Proof. For N = 3 r N=3^r N = 3 r , the nonzero proportion is 8 − 4 ( 18 r 2 + 471 r + 3993 ) ( 8 / 9 ) r 8^{-4}(18r^2+471r+3993)(8/9)^r 8 − 4 ( 18 r 2 + 471 r + 3993 ) ( 8/9 ) r , which tends to zero. For 3 r ≤ N < 3 r + 1 3^r \le N < 3^{r+1} 3 r ≤ N < 3 r + 1 , the number of nonzero entries is at most N 27 ( r + 1 ) N_{27}(r+1) N 27 ( r + 1 ) and the square has at least 9 r 9^r 9 r entries. Thus its nonzero proportion is at most N 27 ( r + 1 ) / 9 r N_{27}(r+1)/9^r N 27 ( r + 1 ) / 9 r , which also tends to zero.
State counts for the first three powers of 3
For the numerical Delannoy arrays, Table 5 compares certified minimal state counts with a bound from the rational case of Theorem 3.5 . All machines in this comparison read least significant ternary digits first and output the full residue. To count polynomial states, put E = 3 e − 1 E=3^{e-1} E = 3 e − 1 . The numerator series 1 has kernel { 1 , 0 } \{1,0\} { 1 , 0 } . In the construction of Theorem 3.5 , the polynomial multiplying the zero series can be discarded. The remaining state is a single polynomial of degree at most E E E in each variable, with ( E + 1 ) 2 (E+1)^2 ( E + 1 ) 2 coefficients in Z / 3 e Z \mathbb{Z}/3^e\mathbb{Z} Z / 3 e Z . This gives the bound 3 e ( E + 1 ) 2 3^{e(E+1)^2} 3 e ( E + 1 ) 2 .
Table 5. Exact minimal state counts for the two-dimensional numerical Delannoy array modulo 3 e 3^e 3 e , for e = 1 , 2 , 3 e=1,2,3 e = 1 , 2 , 3 , using least-significant-digit automata with ternary digit pairs and zero padding. The last column is a bound on the polynomial states before reachability and minimization.
Reachability and refinement of states by their outputs and successor classes certify the minimal counts. These three cases do not determine the minimal state count as a function of e e e .
Further questions
Theorem 1.6 guarantees automaticity when at most one coordinate contains predecessor entries of both signs. The fixed obstruction shows that two such coordinates can already produce a nonautomatic array. It remains to determine which predecessor sets with two or more such coordinates guarantee automaticity for every permitted rule and every compatible automatic datum.
Theorem 8.6 gives an exact criterion for one specified rule and seed. Its positive cases do not establish automaticity for all rules on the same predecessor set. Understanding which features of a boundary equation produce a multiplicative substitution such as X ↦ X b c X \mapsto X^{bc} X ↦ X b c could give further obstruction criteria.
The verified search of Theorem 9.2 gives a terminating construction under the geometric theorems. The proof gives no bound on its number of computational steps in terms of the input rule and automata. A direct construction from the matrix division proof could give bounds in terms of the group, predecessors and input automata. Such bounds could be compared, where their hypotheses apply, with the explicit bounds of [12 Theorems 1–3] for algebraic series and diagonals of rational functions modulo prime powers.
Theorem 12.1 gives an exact count of nonzero Delannoy residues modulo 27. For the family modulo 3 e 3^e 3 e , with e ≥ 4 e \ge4 e ≥ 4 , the results here do not determine how the counting recurrences and their polynomial factors depend on e e e , or whether the corresponding minimal automata admit a uniform description. The three state counts in Table 5 alone do not determine that dependence. Laurberg [2 Section 10.3, Eq. (10.49)] conjectures that, for every prime p p p and every e ≥ 1 e \ge1 e ≥ 1 , the number of nonzero residues modulo p e p^e p e in the square of side p r p^r p r is eventually the corresponding count modulo p p p times a polynomial in r r r of degree e − 1 e - 1 e − 1 . The exact-degree assertion requires an exception at p = 2 p = 2 p = 2 when e > 1 e > 1 e > 1 . Indeed, the unit boundary and the Delannoy recurrence show by induction that every D m , n D_{m,n} D m , n is odd. The count modulo 2 e 2^e 2 e is therefore 4 r 4^r 4 r for every e ≥ 1 e \ge1 e ≥ 1 , so the multiplier relative to the count modulo 2 is the constant polynomial 1. For p = 3 p = 3 p = 3 and e = 3 e = 3 e = 3 , Theorem 12.1 establishes the eventual formula predicted by Laurberg, with count 8 r 8^r 8 r modulo 3 and a quadratic multiplier for r ≥ 4 r \ge4 r ≥ 4 .
Acknowledgments
This paper was produced in an AI-assisted workflow. AI assistants helped explore candidate constructions, draft proofs, and write software for numerical experiments.