betaFeedback

WorksMathematics

Automatic nn-dimensional recurrences over finite pp-groups with negative predecessor coordinates

Abstract

We study nn-dimensional recurrences on Nn\mathbb{N}^n over finite pp-groups. The rules are ordered products of group endomorphisms, with a pp-automatic additional sequence and compatible pp-automatic boundary data. For finite, nonempty, lexicographically positive predecessor sets, we prove automaticity whenever at most one coordinate contains entries of both signs. This covers all such systems for n=1n=1 and n=2n=2. For n≥3n\ge3, lexicographic positivity alone is insufficient: a fixed three-dimensional recurrence with a single nonzero boundary value is nonautomatic in base pp for every prime pp. For nonnegative predecessors, we give a direct automaton construction and explicit state bounds in the abelian case. Negative coordinates are treated using algebraic power-series division, lifting modulo prime powers, central subgroups and boundary-preserving coordinate changes. A two-parameter family with a specified rule and a single boundary seed admits an exact automaticity criterion modulo prime powers. We also give nonabelian examples and finite computational certificates, including a proof of a previously proposed formula counting nonzero Delannoy residues modulo 2727.

Introduction and statements

An nn-dimensional recurrence determines an array indexed by Nn\mathbb{N}^n from prescribed boundary values and values at predecessor points. We ask when the resulting array is pp-automatic, meaning that a deterministic automaton with finitely many states computes an entry by reading the base-pp digits of its nn 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 Fp\mathbb{F}_p-affine recurrences over finite fields Fq\mathbb{F}_q of characteristic pp 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 pp-groups, and for both together. We allow finite pp-groups, meaning finite groups of order a power of pp, 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 pp-automatic additional sequence and compatible pp-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≥3n \ge3, already for Fp\mathbb{F}_p-linear rules over Fp\mathbb{F}_p.

Theorem 7.2 treats another sufficient family with negative entries in several coordinates. Its boundary consists of the dd coordinate slices {x1=j}\{x_1=j\} for 0≤j<d0 \le j < d. Each slice is a copy of Nn−1\mathbb{N}^{n-1} and is infinite when n≥2n \ge2. 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 11. 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 pp 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 2727 in squares of side 3r3^r, for every r≥4r \ge4.

The scalar algebraic principle for one possible negative direction appears in [15 Theorem 13], stated over C\mathbb{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 pp and put N={0,1,…}\mathbb{N} = \{0,1,\ldots\}. Coordinatewise inequalities are used unless lexicographic order is specified. A vector is lexicographically positive if its first nonzero coordinate is positive. Let

P={v1,…,vm}⊂Zn,vj>lex0,di=max⁡(0,max⁡j(vj)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),

where PP is finite and nonempty. A predecessor of xx is a point x−vjx-v_j. The interior and prescribed boundary are

I=d+Nn,C=Nn∖I=⋃i=1n⋃0≤j<di{xi=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\}.

At an interior point all required predecessors belong to Nn\mathbb{N}^n. At a boundary point at least one required predecessor leaves Nn\mathbb{N}^n. An empty range 0≤j<di0\leq j<d_i contributes no face. There are ∑idi\sum_i d_i faces. Each face has infinitely many points when n≥2n\geq2, while for n=1n=1 the boundary consists of d1d_1 points.

Definition 1.1. A function on Nn\mathbb{N}^n with a finite output alphabet is pp-automatic if a finite deterministic automaton with output computes its value by reading the base-pp digits of all coordinates together, padded to a common length. The output must be invariant under additional zero padding. A boundary function c:C→Ac:C\to A is automatic on its faces if its restriction to each face xi=jx_i=j, 0≤j<di0\leq j<d_i, is an (n−1)(n-1)-dimensional pp-automatic function. The values on intersecting faces must agree. A face in dimension one is a single point.

The additional sequence bb is a prescribed array on Nn\mathbb{N}^n. In additive notation, 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 (vj)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)}

The coordinate kk is common to the whole predecessor set. For example, {(1,−2),(0,1)}\{(1,-2),(0,1)\} satisfies the condition with k=2k=2. The set {(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 HH be a finite abelian pp-group, h:Hm→Hh:H^m\to H a homomorphism, and b:Nn→Hb:\mathbb{N}^n\to H a pp-automatic function. Suppose PP satisfies (1) and c:C→Hc:C\to 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−v1),…,a(x−vm))+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}

is pp-automatic. For coordinatewise nonnegative predecessors, the proof gives an explicit terminating automaton construction from the rule and automata for the data. The term bb may in particular be constant.

Theorem 1.3 (Finite pp-groups). Let GG be a finite pp-group and let α1,…,αm\alpha_1,\ldots,\alpha_m be endomorphisms of GG. Suppose PP satisfies (1), b:Nn→Gb:\mathbb{N}^n \to G is pp-automatic, and c:C→Gc:C \to 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−v1))⋯αm(a(x−vm))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)

is pp-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−v1),…,a(x−vm))b(x)a(x)=h(a(x-v_1),\ldots,a(x-v_m))b(x) when h:Gm→Gh:G^m\to G is a group homomorphism.

Proof. Define αj(g)=h(1,…,g,…,1)\alpha_j(g)=h(1,\ldots,g,\ldots,1) using the jjth input. Each αj\alpha_j is an endomorphism, and the product decomposition of a tuple in GmG^m gives

h(g1,…,gm)=α1(g1)⋯αm(gm).h(g_1,\ldots,g_m)=\alpha_1(g_1)\cdots\alpha_m(g_m).

Theorem 1.3 applies to these endomorphisms.

For a direct-product homomorphism, images of different αj\alpha_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⊂Z2P\subset\mathbb{Z}^2 be a finite nonempty set of lexicographically positive predecessor vectors, and define II and CC as above. Let GG be a finite pp-group, let α1,…,αm\alpha_1,\ldots,\alpha_m be endomorphisms of GG, and suppose the boundary faces and the additional sequence are pp-automatic, with compatible boundary values. Then the unique array defined by the ordered-product recurrence in Theorem 1.3 is pp-automatic. The conclusion includes homomorphisms from GmG^m to GG and the additive abelian rules of Theorem 1.2, without a further sign restriction on PP.

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 di=0d_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⊂ZnP\subset\mathbb{Z}^n be finite, nonempty and lexicographically positive. Suppose at most one coordinate ii satisfies

min⁡j(vj)i<0<max⁡j(vj)i.\min_j (v_j)_i<0<\max_j (v_j)_i.

For any finite pp-group GG, ordered endomorphisms α1,…,αm\alpha_1,\ldots,\alpha_m, compatible automatic boundary faces, and an automatic additional sequence, the unique solution of the recurrence in Theorem 1.3 is pp-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 pp-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 Dn={0,…,p−1}n\mathcal{D}_n=\{0,\ldots,p-1\}^n for the alphabet of digit vectors. For u:Nn→Au:\mathbb{N}^n\to A, where AA is finite, define

ue,r(x)=u(pex+r),Kp(u)={ue,r:e≥0, 0≤ri<pe}.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\}.

The array ue,ru_{e,r} is called a section of uu. Its indices have their ee low digits fixed by rr. For e=0e=0, the only choice is r=0r=0, so u0,0=uu_{0,0}=u.

We write an automaton with output as A=(Q,q0,δ,τ)\mathcal{A}=(Q,q_0,\delta,\tau). Here QQ is its finite state set, q0q_0 is its initial state, δ:Q×Dn→Q\delta:Q\times\mathcal{D}_n\to Q is its transition map, and τ:Q→A\tau:Q\to A gives the output of a state. For a word ww of digit vectors, the extended transition δ∗\delta^* means that the letters of ww are read in their written order. Formally,

δ∗(q,ε)=q,δ∗(q,wr)=δ(δ∗(q,w),r),\delta^*(q,\varepsilon)=q,\qquad\delta^*(q,wr)=\delta(\delta^*(q,w),r),

where ε\varepsilon denotes the empty word.

The output on a word ww is A(w)=τ(δ∗(q0,w))\mathcal{A}(w)=\tau(\delta^*(q_0,w)). For w=r0⋯rℓ−1w=r_0\cdots r_{\ell-1}, the represented index is

∑j=0ℓ−1pℓ−1−jrj\sum_{j=0}^{\ell-1}p^{\ell-1-j}r_j

when most significant digits are read first,

References

  1. [1]K. Sutner, S. Tetruashvili, Inferring Automatic Sequences, author preprint, 6 November 2012. https://www.cs.cmu.edu/~sutner/papers/auto-seq.pdf.
  2. [2]R. P. Laurberg, Fractal Structures in Multidimensional Integer Arrays Generated by Multivariate Homogeneous Linear Recurrence Relations, MA thesis, American University, 2021. Section 10.2.2, Eq. (10.47), p. 164. University repository record.DOI
  3. [3]O. Salon, Suites automatiques à multi-indices et algébricité, Comptes Rendus de l’Académie des Sciences de Paris, Série I 305 (1987), 501–504.
  4. [4]G. Rond, Local zero estimates and effective division in rings of algebraic power series, Journal für die reine und angewandte Mathematik 737 (2018), 111–160. https://doi.org/10.1515/crelle-2015-0041. Preprint arXiv:1406.4634v4, 27 April 2015.
  5. [5]J.-P. Allouche, J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003. https://doi.org/10.1017/CBO9780511546563.
  6. [6]G. Christol, T. Kamae, M. Mendès France, G. Rauzy, Suites algébriques, automates et substitutions, Bulletin de la Société Mathématique de France 108 (1980), 401–419. https://doi.org/10.24033/bsmf.1926.
  7. [7]P. Cartier, Une nouvelle opération sur les formes différentielles, Comptes Rendus de l’Académie des Sciences de Paris 244 (1957), 426–428. https://www.ihes.fr/wp-content/uploads/2024/09/CartierCRAS57.pdf.
  8. [8]M. Prunescu, Fₚ-affine recurrent n-dimensional sequences over F_q are p-automatic, European Journal of Combinatorics 34 (2) (2013), 260–284. https://home.mathematik.uni-freiburg.de/prunescu/fpaffine.pdf.
  9. [9]M. Prunescu, Self-similar carpets over finite fields, European Journal of Combinatorics 30 (4) (2009), 866–878. https://doi.org/10.1016/j.ejc.2008.08.002.
  10. [10]J. Denef, L. Lipshitz, Algebraic power series and diagonals, Journal of Number Theory 26 (1987), 46–67. https://doi.org/10.1016/0022-314X(87)90095-3.
  11. [11]E. Rowland, R. Yassawi, Automatic congruences for diagonals of rational functions, Journal de Théorie des Nombres de Bordeaux 27 (2015), 245–288. https://arxiv.org/abs/1310.8635.
  12. [12]E. Rowland, R. Yassawi, Algebraic power series and their automatic complexity modulo prime powers, Mathematics of Computation, published electronically 25 June 2026. https://doi.org/10.1090/mcom/4227. Preprint arXiv:2408.00750v4.
  13. [13]M. E. Alonso, F. J. Castro-Jiménez, H. Hauser, Encoding algebraic power series, Foundations of Computational Mathematics 18 (2018), 789–833. https://arxiv.org/abs/1403.4104.
  14. [14]H. Hauser, C. Koutschan, Multivariate linear recurrences and power series division, Discrete Mathematics 312 (2012), 3553–3560. https://doi.org/10.1016/j.disc.2012.08.009.
  15. [15]M. Bousquet-Mélou, M. Petkovšek, Linear recurrences with constant coefficients: the multivariate case, Discrete Mathematics 225 (2000), 51–75. https://doi.org/10.1016/S0012-365X(00)00147-3.
  16. [16]J. Gütschow, V. Nesme, R. F. Werner, The fractal structure of cellular automata on abelian groups, DMTCS Proceedings AL (2010), 51–70. A correction to its Proposition 4 appears in [18, Section 1]. https://dmtcs.episciences.org/2759.arxiv.org/abs/1011.0313
  17. [17]E. Rowland, R. Yassawi, Automaticity and invariant measures of linear cellular automata, Canadian Journal of Mathematics 72 (2020), 1691–1726. https://arxiv.org/abs/1811.01256.
  18. [18]V. Nesme, Automaticity of spacetime diagrams generated by cellular automata on commutative monoids, Discrete Mathematics and Theoretical Computer Science 28:3 (2026), #8. Preprint arXiv:2207.13062v5, 26 August 2026. https://arxiv.org/abs/2207.13062v5.
  19. [19]M. Pivato, Multiplicative cellular automata on nilpotent groups: structure, entropy, and asymptotics, Journal of Statistical Physics 110 (2003), 247–267. https://arxiv.org/abs/math/0108084v3.

Paper details

vlnc:W_r97puzdh
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

AI assistants

View statement
Looking for related papers…
Contents