Abstract 1 Introduction 2 Preliminaries 3 Main results and consequences 4 From Submonoid Membership to S-unit equation 5 S-unit equation over modules References

Submonoid Membership in n-Dimensional Lamplighter Groups and S-Unit Equations

Ruiwen Dong ORCID Department of Mathematics, Saarland University, Saarbrücken, Germany
Magdalen College, University of Oxford, UK
Abstract

We show that Submonoid Membership is decidable in n-dimensional lamplighter groups (/p)n for any prime p and integer n. More generally, we show decidability of Submonoid Membership in semidirect products of the form 𝒴n, where 𝒴 is any finitely presented module over the Laurent polynomial ring 𝔽p[X1±,,Xn±]. Combined with a result of Shafrir (2024), this gives the first example of a group G and a finite index subgroup G~G, such that Submonoid Membership is decidable in G~ but undecidable in G.

To obtain our decidability result, we reduce Submonoid Membership in 𝒴n to solving S-unit equations over 𝔽p[X1±,,Xn±]-modules. We show that the solution set of such equations is effectively p-automatic, extending a result of Adamczewski and Bell (2012). As an intermediate result, we also obtain that the solution set of the Knapsack Problem in 𝒴n is effectively p-automatic.

Keywords and phrases:
Submonoid Membership, lamplighter groups, S-unit equations, p-automatic sets, Knapsack in groups
Category:
Track B: Automata, Logic, Semantics, and Theory of Programming
Copyright and License:
[Uncaptioned image] © Ruiwen Dong; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Computing methodologies Symbolic and algebraic manipulation
Related Version:
Full Version: https://arxiv.org/abs/2409.07077
Acknowledgements:
The author would like to thank Doron Shafrir for pointing out the open problem on Submonoid Membership in finite extension of groups, as well as for discussion of his work [37]. The author would like to thank the anonymous reviewers for their helpful comments.
Funding:
This work was funded by the European Union (ERC, AdG grant 101097307). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.
Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

1 Introduction

Algorithmic problems in infinite groups

Algorithmic problems concerning groups are a classical topic in algebra and theoretical computer science. Dating back to the work of Max Dehn from the 1910s, this area has traditionally served as a bridge between geometry, algebra and logic, and has now found numerous applications in automata theory, program analysis and complexity theory [7, 9, 14, 22]. One of the central decision problems on groups is the Submonoid Membership problem: given a finite number of elements g1,g2,,gk in a group G and an element gG, does g belong to the submonoid generated by g1,g2,,gk? In the seminal work of Markov from the 1950s [30], it was shown that Submonoid Membership is undecidable for a matrix group of dimension six. The undecidability result was later strengthened to the group 𝖲𝖫(4,) of 4×4 integer matrices of determinant one [31]. Subsequently, a number of positive decidability results were obtained, such as for commutative matrix groups [2], low-dimensional matrix groups [12, 33], and certain graph groups [26]. See [15, 25] for recent surveys.

A generalization of Submonoid Membership is the Rational Subset Membership problem: given a rational subset S of a group G and an element gG, does g belong to S? Here, a subset S of a group G is called a rational subset if there is a finite alphabet Σ, a monoid homomorphism φ:ΣG, and a regular language LΣ, such that φ(L)=S. In particular, if L=Σ, then we recover the definition of Submonoid Membership. In fact, many decidability results for Submonoid Membership are also proven for the more general Rational Subset Membership, such as in free groups [8], abelian groups [20], and certain wreath products [28]. Nevertheless, Bodart [10] and Shafrir111An example appeared in the Bachelor’s thesis of Potthast [34], based on an unpublished draft of Shafrir. recently provided examples of groups with undecidable Rational Subset Membership but decidable Submonoid Membership.

A longstanding open problem in computational group theory is whether decidability of Submonoid Membership is preserved under finite extension of groups. Grunschlag [20] showed that for any group G and a finite index subgroup G~G, Rational Subset Membership is decidable in G~ if and only if it is decidable in G. The same statement is also true for the Subgroup Membership problem [20] (given g1,g2,,gk,g, does g belong to the subgroup generated by g1,g2,,gk?). Whether the same holds for Submonoid Membership remained open. One of the goals of this paper is to construct a counterexample to this open problem: we construct a group G and a finite index subgroup G~G, such that Submonoid Membership is decidable in G~ but undecidable in G.

n-dimensional lamplighter groups

In this paper, we study Submonoid Membership in n-dimensional lamplighter groups as well as their generalizations. The lamplighter groups are well-studied objects in the context of geometric group theory [19, 38]. Given an integer p2 and n, the n-dimensional lamplighter group, denoted (/p)n, can be most easily defined as the (multiplicative) 2×2 upper-triangular matrix group

{(X1a1X2a2Xnanf01)|a1,a2,,an,f(/p)[X1,X11,,Xn,Xn1]}, (1)

where (/p)[X1,X11,,Xn,Xn1] is the Laurent polynomial ring over n variables, with coefficients in the finite ring /p={0,1,,p1}. When p is prime, /p is actually the finite field 𝔽p. Intuitively, an element in (/p)n can be understood as the following configuration: at each position in the lattice n there is a lamp, each lamp has a state among /p={0,1,,p1}, and there is a pointer at some position in n. In particular, for the element (X1a1Xnanf01) , the pointer is at position (a1,,an)n, the lamp at position (z1,,zn)n has state s if the monomial X1z1Xnzn appearing in f has coefficient s. In particular, all but finitely many lamps have state 0. Multiplication in the group (/p)n, like matrix multiplication, corresponds to first moving the pointer by a vector (a1,,an), then additively changing the states of the lamps around the new location.

Owing to this geometric interpretation, the study of lamplighter groups has close connections to automata theory, tiling problems, random walks, and graph theory [3, 4, 23, 27, 29]. Lamplighter groups are also important examples of metabelian groups, which are some of the most tractable generalization of abelian groups. Recall that a group G is called metabelian if it admits a normal subgroup A such that both A and G/A are abelian. An important amount of research in computational group theory concentrates on metabelian groups, since decision problems in abelian groups are already well-understood. For example, Cadilhac, Chistikov and Zetzsche [11] showed decidability of Rational Subset Membership in the Baumslag-Solitar groups 𝖡𝖲(1,p); Lohrey, Steinberg and Zetzsche [27] showed decidability of Rational Subset Membership in 1-dimensional lamplighter groups. On the other hand, the 2-dimensional lamplighter groups occupy an interesting position as they have undecidable Rational Subset Membership [27] but decidable Submonoid Membership [34]. The decision algorithm in [34] cannot be generalized to dimensions larger than 2 as it relies on a reduction to Rational Subset Membership in dimension 1. It is thus left as an open problem whether Submonoid Membership is decidable in lamplighter groups of dimension n3.

Contributions of this paper

In this paper, we show that Submonoid Membership is decidable in lamplighter groups (/p)n of every dimension n and prime p. In fact, we prove a much more general result (Theorem 3.1): Submonoid Membership is decidable for semidirect products 𝒴n, where 𝒴 is a finitely presented module over the Laurent polynomial ring 𝔽p[X1±,,Xn±].

An important consequence of the more general Theorem 3.1 is the resolution of a longstanding open problem (Corollary 3.2). Combined with a recent result of Shafrir [37], we show that there exist a group G and a finite index subgroup G~G, such that Submonoid Membership decidable in G~ but undecidable in G.

Our main strategy to decide Submonoid Membership in 𝒴n is to reduce it to solving S-unit equations over modules: these are equations of the form x1c1+x2c2++xmcm=c0, where the variables xi take value in a multiplicative subgroup of a commutative ring. We show that the solutions of such S-unit equations over an 𝔽p[X1±,,Xn±]-module forms an effectively p-automatic set (Theorem 3.3), generalizing a result of Adamczewski and Bell [1]. As an intermediate result, we also obtain effective p-automaticity for the solution set of the Knapsack Problem in 𝒴n: given g1,g2,,gk,g𝒴n, find (z1,,zk)k such that g1z1g2z2gkzk=g. We give an example (Example 4.9) where the solution set is p-automatic but not semilinear. This shows that the situation in semidirect products is much more complicated than in the wreath product of two abelian groups, as seen in the work of Ganardi, König, Lohrey, and Zetzsche [18].

Note that our decidability results heavily rely on working over the finite ring /p instead of the infinite ring . Indeed, Submonoid Membership is known to be undecidable [28] in n for n1, and solving S-unit equations over [X1±]-modules is also known to be undecidable [16]. Nevertheless, it is not clear whether the decidability for (/p)n can be generalized to non-prime numbers p, for example when p=p1p2 for two primes p1p2. This is closely related to deciding emptiness of the intersection of a p1-automatic set and a p2-automatic set, which to the best of our knowledge remains an open problem (however, see [21, 24] for recent progress). Progress towards a solution for non-prime p will also be the first step towards a classification of metabelian groups with decidable Submonoid Membership, namely by tackling those with torsion commutators.

2 Preliminaries

Laurent polynomial ring and modules

Let p be a prime number, denote by 𝔽p the finite field of size p. Denote by 𝔽p[X1±,,Xn±] the Laurent polynomial ring over 𝔽p with n variables: this is the set of polynomials over the variables X1,X11,,Xn,Xn1, with coefficients in 𝔽p, such that XiXi1=1 for all i. When n is fixed, we denote by X¯ the tuple of variables (X1,,Xn), and 𝔽p[X1±,,Xn±] is written in short as 𝔽p[X¯±].

For a vector 𝒂=(a1,,an)n, denote by X¯𝒂 the monomial X1a1X2a2Xnan. When Λ is a subgroup of n, we denote by 𝔽p[X¯Λ]𝔽p[X¯±] the subring of polynomials of the form 𝒂Λc𝒂X¯𝒂.

Since we work in polynomial rings over a finite field 𝔽p, it is worth pointing out a useful equation, folklorishly dubbed “the freshman’s dream”. For any f𝔽p[X¯±], we have (f+1)p=fp+1, and more generally (f+1)pk=fpk+1 for all k.

When R is a commutative ring (such as 𝔽p[X¯±]), an R-module is defined as an abelian group (M,+) along with an operation :R×MM satisfying f(m+m)=fm+fm, (f+g)m=fm+gm, fgm=f(gm) and 1m=m. For example, for any d, 𝔽p[X¯±]d is an 𝔽p[X¯±]-module by f(h1,,hd)=(fh1,,fhd). We often use a bold symbol 𝒉 to denote a vector (h1,,hd)𝔽p[X¯±]d.

Given elements 𝒉1,,𝒉k in an R-module M, we say that they generate the R-module

i=1kR𝒉i{i=1kri𝒉i|r1,,rkR}M.

Given submodules M,M of 𝔽p[X¯±]d such that MM, we define the quotient M/M{m¯mM} where m¯1=m¯2 if and only if m1m2M. This quotient is also an 𝔽p[X¯±]-module. We say that an 𝔽p[X¯±]-module 𝒴 is finitely presented if it can be written as a quotient 𝔽p[X¯±]d/M for a finitely generated submodule M of 𝔽p[X¯±]d for some d. We call a finite presentation of 𝒴 the generators of such M. Every finitely generated 𝔽p[X¯±]-module admits a finite presentation.

Given a finitely presented 𝔽p[X1±,,Xn±]-module 𝒴, we can define the following group using semidirect product:

𝒴n{(y,𝒂)y𝒴,𝒂n}; (2)

multiplication and inversion in this group are defined by

(y,𝒂)(y,𝒂)=(y+X¯𝒂y,𝒂+𝒂),(y,𝒂)1=(X¯𝒂y,𝒂). (3)

The neutral element of 𝒴n is (0,𝟎), where 𝟎 denotes the zero vector in n. Intuitively, the element (y,𝒂) can be seen as a 2×2 matrix (X¯𝒂y01), where group multiplication is represented by matrix multiplication. We have the formula (f,𝒂)(y,𝟎)(f,𝒂)1=(X¯𝒂y,𝟎). Note that 𝒴n naturally contains the subgroup 𝒴{(y,𝟎)y𝒴}, and there is a projection map π:𝒴nn,(y,𝒂)𝒂, such that ker(π)=𝒴.

In particular, if we take 𝒴=𝔽p[X¯±] considered as a 𝔽p[X¯±]-module, then we recover the definition (1) of the n-dimensional lamplighter group (/p)n.

Effective computation in modules

In order to effectively compute in groups of the form 𝒴n, we need to be able to effectively compute in the 𝔽p[X¯±]-module 𝒴. The following are some classic problems with effective algorithms that we will make use of. We state the following result over 𝔽p[X¯±], although they hold over polynomial rings over any field.

Lemma 2.1 ([5, Lemma 2.1, 2.2]).

Let 𝒴 be an 𝔽p[X¯±]-module with a given finite presentation. The following problems are effectively solvable:

  1. (i)

    (Submodule Membership) Given elements y1,,yk,y𝒴, decide whether y is in the submodule generated by y1,,yk.

  2. (ii)

    (Submodule Presentation) Given elements y1,,yk𝒴, compute a finite presentation for the submodule generated by y1,,yk.

  3. (iii)

    (Computing intersection and sum) Given the generators of a submodule A𝒴 and the generators of a submodule B𝒴, compute the generators for the submodule AB and for the submodule A+B={a+baA,bB}.

  4. (iv)

    (Computing quotient) Given the generators of a submodule 𝒴𝒴, compute a finite presentation of the quotient 𝒴/𝒴.

Let Λ be a subgroup of n, then any 𝔽p[X¯±]-module can be considered as a (possibly infinitely generated) 𝔽p[X¯Λ]-module. For example, the 𝔽p[X1±,X2±]-module 𝔽p[X1±,X2±] can be considered as an 𝔽p[X1±]-module, but it is not finitely generated (it is generated by the infinite set {,X22,X21,1,X2,X22,}). However, finitely generated 𝔽p[X¯Λ]-submodules of an 𝔽p[X¯±]-module are still effectively computable:

Lemma 2.2 ([5, Theorem 2.14] or [6, Theorem 2.6]).

Let Λ be a subgroup of n, and 𝒴 be a finitely presented 𝔽p[X¯±]-module. Given a finite subset S of 𝒴, one can effectively compute the finite presentation of the 𝔽p[X¯Λ]-module sS𝔽p[X¯Λ]s.

p-automatic sets

We recall the standard notion of p-automatic subsets of , and more generally, p-automatic subsets of d.

Let Σ be a finite alphabet. An automaton over Σ is a tuple 𝒜=(Q,Σ,δ,qI,F), where Q is a finite set of states, δ:Q×ΣQ is the transition function, qI is the initial state, and FQ is the set of final states. For a state q in Q and for a finite word w=w1w2wn over the alphabet Σ, we define δ(q,w) recursively by δ(q,w)=δ(δ(q,w1w2wn1),wn). The word w is accepted by 𝒜 if δ(qI,w)F.

Let p2 be an integer, define the alphabet Σp{+,,0,1,2,,p1}. Let n0 be a non-negative integer and let wrwr1w1w0(Σp)r+1 be the base-p expansion of n. That is, n=i=0rwipi with the smallest possible r. We denote by w(n) the word +w0w1wr. For example, if p=2, then w(4)=+001. Similarly, for a negative integer n, let w(n) denote the word w0w1wr. A subset S of is called p-automatic if there is an automaton over Σp that accepts exactly the set w(S){w(s)sS}. For example, the set S={2kk} is 2-automatic, because w(S)={+1,+01,+001,+0001,} is accepted by an automaton over Σ2={+,,0,1}.

Let d. The definition of p-automatic subsets of can be naturally generalized to p-automatic subsets of d. For (z1,,zd)d, consider the tuple of words (w(z1),,w(zd)) over the alphabet Σp. We naturally identify a d-tuple of words (w(z1),,w(zd)) over the alphabet Σp as a single word w(z1,,zd) over the alphabet Σpd: if the words w(z1),,w(zd) have different lengths, we add a minimal number of zeros at the end so they all have equal lengths. Naturally, a subset S of d is called p-automatic if there is an automaton over Σpd that accepts exactly the set w(S){w(s)sS}. For example, the set S={(a,2a)a<1} 2 is 2-automatic, because

w(S)={(,)(a1,0)(a2,a1)(a3,a2)(ak,ak1)(1,ak)(0,1)k,a1,,ak{0,1}}

is accepted by an automaton over Σ22. We say a subset Sd is effectively p-automatic if its accepting automaton is explicitly given. p-automatic sets enjoy various closure properties. In this paper, we will use the following:

Lemma 2.3 ([39]).

Let p2 be an integer.

  1. (1)

    If S and T are effectively p-automatic subsets of d, then ST and ST are also effectively p-automatic.

  2. (2)

    If Sd is effectively p-automatic, and φ:dn is a linear transformation, then φ(S)n is also effectively p-automatic.

  3. (3)

    If Sd is effectively p-automatic, and ϕ:Nd is a linear transformation, then ϕ1(S){vNϕ(v)S} is also effectively p-automatic.

  4. (4)

    It is decidable whether a given effectively p-automatic set S is empty.

3 Main results and consequences

The main result of this paper is the following.

Theorem 3.1.

Let p be a prime number, X¯=(X1,,Xn) be a tuple of variables and 𝒴 be a finitely presented 𝔽p[X¯±]-module. Then, Submonoid Membership is decidable in the group 𝒴n.

In particular, taking 𝒴=𝔽p[X¯±], we immediately obtain decidability of Submonoid Membership in the n-dimensional lamplighter groups (/p)n for prime p.

We say a group is virtually abelian if it has a finite index subgroup that is abelian. A recent result of Shafrir [37, Theorem 8.1] shows that membership problem in a fixed rational subset S of a group L can be reduced to the membership problem in a fixed submonoid M of the group L×H, where H is an explicitly constructed finitely generated virtually abelian group. Combined with Theorem 3.1, this allows us to construct an example where decidability of Submonoid Membership is not preserved under finite extension of groups:

Corollary 3.2.

There exist a group G and a finite index subgroup G~G, such that Submonoid Membership is decidable in G~ but undecidable in G.

Proof.

By [27, Theorem 10], there is a rational subset S of the two-dimensional lamplighter group L(/2)2, whose membership problem (given gL, whether gS?) is undecidable. By Shafrir’s result [37, Theorem 8.1], the membership problem in S reduces to the membership problem in a finitely generated submonoid of the group GL×H, where H is finitely generated virtually abelian. Therefore, Submonoid Membership is undecidable in G=L×H.

Since H is finitely generated virtually abelian, it has a finite index subgroup dH for some d. Let G~L×d, so the index [G:G~]=[H:d] is finite. We now show that Submonoid Membership is decidable in G~.

Note that G~=L×d=((/2)2)×d can be written as a semidirect product 𝒴d+2, where 𝒴𝔽2[X1±,X2±] is considered as an 𝔽2[X1±,X2±,X3±,Xd+2±]-module where the elements X3,,Xd+2 act trivially. That is, 𝒴=𝔽2[X1±,,Xd+2±]/i=3d+2𝔽2[X1±,,Xd+2±](Xi1). So by Theorem 3.1, Submonoid Membership is decidable in G~.

Our proof of Theorem 3.1 is divided into two parts. First, in Section 4, we reduce Submonoid Membership to solving S-unit equations over modules. Then, in Section 5, we prove the following result for S-unit equations over modules.

Theorem 3.3.

Let p be a prime number, X¯=(X1,,Xn) be a tuple of variables, M be a finitely presented 𝔽p[X¯±]-module, and let c0,c1,,cmM. Then, the set of solutions (𝐳1,,𝐳m)(n)m for the equation

X¯𝒛1c1++X¯𝒛mcm=c0 (4)

is an effectively p-automatic subset of (n)mnm.

During the reduction in Section 4, we go through an intermediate step involving the Knapsack Problem in groups. In particular, we obtain the following intermediate result that is of independent interest:

Theorem 3.4.

Let p be a prime number, 𝒴 be a finitely presented 𝔽p[X¯±]-module and G=𝒴n. Let h1,,hm,g be elements of G, then the solution set (n1,,nm)m of

h1n1h2n2hmnm=g (5)

is an effectively p-automatic subset of m.

4 From Submonoid Membership to S-unit equation

In this section we reduce the problem of Submonoid Membership in 𝒴n to solving S-unit equations over 𝔽p[X¯±]-modules. The reduction is done in three steps. In Step 1, we reduce Submonoid Membership in 𝒴n to deciding membership in a product of conjugate groups (Proposition 4.1). In Step 2, we reduce membership in a product of conjugate groups to solving the Knapsack Problem in another semidirect product 𝒴n (Proposition 4.4). In Step 3, we show that the solution set of the Knapsack Problem is effectively p-automatic (Theorem 3.4), assuming a theorem on S-unit equations (Theorem 3.3).

Recall that the rank of an abelian group A is defined as smallest cardinality of a generating set for A. If An, then A is a lattice in n, the rank of A is the dimension of this lattice.

Step 1: from Submonoid Membership to Group Product Membership

Given qG and a subgroup HG, define the conjugate subgroup qH{qhq1hH}. For q1,q2,,qkG, denote the set

q1Hq2HqkH{h1h2hkh1q1H,,hkqkH}. (6)

Note that qH is always a group, but the product q1Hq2HqkH is in general not a group. Our first step is the following reduction from Submonoid Membership to the membership problem in sets of the form (6), originally due to Shafrir. We give a proof here for the sake of completeness. Recall that the projection π:G=𝒴nn is surjective and its kernel is 𝒴. A group A is called torsion if for all aA, there exists t1 such that at is the neutral element. In particular, an 𝔽p[X¯±]-module 𝒴 considered as an abelian group is torsion, because py=0 for all y𝒴.

Proposition 4.1 ([34, Theorem 4.3.3]).

Let G be a finitely generated group and π:Gn be a surjective homomorphism with ker(π) being a torsion group. Submonoid Membership in G can be reduced to the following membership problem:

Input: elements g,q1,,qkG and finitely many generators of a subgroup HG.

Question: whether gq1Hq2HqkH?

Proof.

For a subset TG, denote by T the submonoid generated by T: this is the set of elements of the form g1g2gs where s0 and giT for 1is.

Let g1,g2,,gm,gG, and suppose we want to decide whether gg1,g2,,gm. Consider the elements π(g1),,π(gm),π(g)nn, let 𝒞n be the 0-cone generated by π(g1),π(g2),,π(gm), and let 𝒞0 be the maximal -subspace of 𝒞. In particular, there exists vn, such that vw=0 for all w𝒞0, and vw>0 for all w𝒞𝒞0 (if 𝒞0=𝒞 then we can take v=𝟎). Without loss of generality suppose π(g1),,π(g)𝒞0 and π(g+1),,π(gm)𝒞𝒞0, for some 1m.

If gg1,g2,,gm, then we can write g as a word gi1gi2gis over {g1,,gm}. In this case, π(g)=π(gi1)+π(gi2)++π(gis), so we must have vπ(g)0, and the elements g+1,,gm can only be used a bounded number of times (in fact, bounded by Bvπ(g)/min{vπ(g+1),,vπ(gm)}). Therefore, it suffices to check, for each possible choice of gj1,,gjb{g+1,,gm},bB, whether g can be written as h1gj1h2gj2h3gjbhb+1 for h1,,hb+1g1,g2,,g.

Let Hg1,g2,,g, we claim that the monoid H is actually a group. It is easy to see that the 0-cone generated by π(g1),,π(g) is the linear space 𝒞0. Therefore we can find positive integers n1,,n>0 such that n1π(g1)++nπ(g)=𝟎. Thus, π(g1n1g2n2gn)=𝟎, so g1n1g2n2gnker(π). But ker(π) is torsion, so (g1n1g2n2gn)t is the neutral element for some t1. This yields g11=g1n11g2n2gn(g1n1g2n2gn)t1H. Similarly, g21,,g1H, so the monoid H is actually a group.

By the discussion above, it suffices to check for finitely many instances of gj1,,gjb, whether gHgj1Hgj2HgjbH. But Hgj1Hgj2HgjbH is equal to

H(gj1Hgj11)(gj1gj2Hgj21gj11)(gj1gj2gjbHgjb1gj21gj11)gj1gj2gjb.

So gHgj1Hgj2HgjbH is equivalent to

ggjb1gj21gj11Hgj1Hgj1gj2Hgj1gj2gjbH,

which is a product of conjugate groups. This finishes the reduction from Submonoid Membership to membership in products of conjugate groups.

In particular, for the case of G=𝒴n, Proposition 4.1 is effective, meaning one can explicitly compute the elements q1,,qkG and the generators of H.

Example 4.2 (label=exa:cont).

Let 𝒴=𝔽2[X1±,X2±] considered as an 𝔽2[X1±,X2±]-module, so 𝒴2 is the 2-dimensional lamplighter group (/2)2. Let g1=(1+X2,(2,0)),g2=(1,(2,0)),g3=(1+X1,(0,1)) be the generators of a submonoid, and let g=(X22,(4,2)).

We have π(g1)=(2,0),π(g2)=(2,0),π(g3)=(0,1), so the 0-cone they generate is 𝒞={(x,y)2y0}. Its maximal subspace is 𝒞0={(x,0)x}. We have π(g1),π(g2)𝒞0 and π(g3)𝒞𝒞0.

Suppose g=gi1gi2gis with i1,i2,,is{1,2,3}. Let v=(0,1). Since vπ(g)=v(4,2)=2, and vπ(g1)=vπ(g2)=0,vπ(g3)=1, the element g3 must appear exactly twice in the product gi1gi2gis. Therefore, g must be of the form w1g3w2g3w3, where w1,w2,w3 are words over {g1,g2}. Let H be the monoid generated by g1,g2: this is actually a group because (g1g2)2=(0,𝟎). The above discussion shows gg1,g2,g3 if and only if gHg3Hg3H: this is equivalent to gg32Hg3Hg32H.  

Remark 4.3.

If G=(/2)2 and π(H) is of rank one (i.e. π(H)) as in Example 4.2, then membership problem in the product q1Hq2HqkH can be reduced to Rational Subset Membership in the 1-dimensional lamplighter group (/2), which is known to be decidable [28]. In fact, this is the key idea in Shafrir’s solution [34] for Submonoid Membership in 2-dimensional lamplighter groups. However, when the dimension n is greater or equal to three, the rank of π(H) may be greater or equal to two: in this case, the membership problem in q1Hq2HqkH has been open and will be solved in the rest of this paper. Notably, we do not want to reduce it to Rational Subset Membership in lamplighter groups of dimension 2, as it is undecidable [27].

Step 2: from Group Product Membership to Knapsack Problem

The goal of this step is to reduce membership problem in the product q1Hq2HqkH to a version of the Knapsack Problem in groups. Namely, we will prove:

Proposition 4.4.

Let G=𝒴n where 𝒴 is a finitely presented 𝔽p[X1±,,Xn±]-module. Let g,q1,,qkG and let HG be a finitely generated subgroup. Then, one can effectively find a group G=𝒴n, where 𝒴 is a finitely presented 𝔽p[X1±,,Xn±]-module, as well as elements g,h1,,hmG, such that

gq1Hq2HqkH

if and only if there exist z1,,zm satisfying

h1z1h2z2hmzm=g. (7)

We now proceed to prove Proposition 4.4. Recall that 𝒴 can be identified with the subgroup 𝒴×{𝟎}=ker(π) of G=𝒴n. First, we give the following classic result on the structure of subgroups HG. Note that π(H)π(G)=n, let dn be the rank of π(H).

Lemma 4.5 ([6, Theorem 3.3] or [35, Lemma 2]).

Let G=𝒴n and HG be a finitely generated subgroup. Let 𝐚1,,𝐚dn be a -basis of π(H), and choose elements h1,,hdH so that π(hi)=𝐚i,i=1,,d. Then, the subgroup 𝒴H is a finitely generated 𝔽p[X¯π(H)]-module, whose finite presentation can be effectively computed. Furthermore, H is generated by h1,,hd and the set 𝒴H.

Example 4.6 (continues=exa:cont).

As in Example 4.2, let 𝒴=𝔽2[X1±,X2±]. Consider the subgroup H𝒴2 generated by g1=(1+X2,(2,0)) and g2=(1,(2,0)). Then π(H) is the subgroup of 2 generated by 𝐚1(2,0), it has rank d=1. We can choose h1g1 in Lemma 4.5.

The subgroup 𝒴H is an 𝔽p[X¯π(H)]=𝔽p[X12,X12]-module. We have g1g2=(1+X2+X12,𝟎). We claim that 1+X2+X12 is the generator of the 𝔽p[X12,X12]-module 𝒴H: that is, 𝒴H={F(1+X2+X12)F𝔽p[X12,X12]}. Indeed, recall the formula (f,𝐚)(y,𝟎)(f,𝐚)1=(X¯𝐚y,𝟎). For each m, we have g1m(g1g2)g1m=g1m(1+X2+X12,𝟎)g1m=(X12m(1+X2+X12),𝟎). So X12m(1+X2+X12)𝒴H for all m. Consequently, F(1+X2+X12)𝒴H for all F𝔽p[X12,X12]. It is not difficult to show that {F(1+X2+X12)F𝔽p[X12,X12]} is indeed all the elements in 𝒴H, but we will omit the details. Note that 𝒴H is finitely generated as an 𝔽p[X12,X12]-module but not finitely generated as an abelian group.

Finally, for any element h=(f,2z)H, we have π(h1zh)=𝟎, so (y,𝟎)h1zh𝒴H. Consequently, h can actually be written in a “canonical form” h1z(y,𝟎), where z and y𝒴H. Such canonical forms will be extensively used below.  

Define

𝒴i𝒴(qiH),i=1,,k.

Note that for any qG, we have π(qH)=π(H) because n is abelian. Therefore π(q1H)==π(qkH)=π(H). So by Lemma 4.5, all the 𝒴i’s are finitely generated 𝔽p[X¯π(H)]-modules. Let 𝒂1,,𝒂dn be a -basis of π(H). For each 1ik, choose elements hi,1,,hi,dqiH so that π(hi,1)=𝒂1,,π(hi,d)=𝒂d. Then, qiH is generated by hi,1,,hi,d and 𝒴i.

Fix any i. Since 𝒂1,,𝒂dn form a -basis for π(qiH), for each element hqiH we can find integers z1,,zd such that

π(h)=z1𝒂1+z2𝒂2++zd𝒂d=z1π(hi,1)+z2π(hi,2)++zdπ(hi,d).

This shows π(hi,dzi,dhi,2zi,2hi,1zi,1h)=𝟎, so hi,dzi,dhi,2zi,2hi,1zi,1hker(π)qiH=𝒴i. Consequently, h is equal to hi,1zi,1hi,2zi,2hi,dzi,d(yi,𝟎) for some yi𝒴i.

The form of this product of powers gives us the motivation to reduce membership in group products to the Knapsack Problem. Denote

𝒴~𝒴1++𝒴k.

Again we identify 𝒴~ with the subgroup 𝒴~×{𝟎} of 𝒴n. We show the following:

Lemma 4.7.

We have gq1Hq2HqkH, if and only if there exist integers z1,1,,z1,d, , zk,1,,zk,d, such that

(h1,1z1,1h1,2z1,2h1,dz1,d)(hk,1zk,1hk,2zk,2hk,dzk,d)g1𝒴~. (8)

Proof.

For the “only if” part, suppose gq1Hq2HqkH, and write g=h1h2hk with hiqiH for each 1ik. As shown above, we can write

hi=hi,1zi,1hi,2zi,2hi,dzi,d(yi,𝟎)

for some yi𝒴i,i=1,,k. Denote yiX¯j=1dz1,j𝒂j+j=1dz2,j𝒂j++j=1dzi,j𝒂jyi, then yi𝒴i. Recall the formula (f,𝒂)(y,𝟎)(f,𝒂)1=(X¯𝒂y,𝟎), that is (f,𝒂)(yi,𝟎)=(X¯𝒂yi,𝟎)(f,𝒂). Therefore,

g =h1h2hk=(h1,1z1,1h1,2z1,2h1,dz1,d)(y1,𝟎)(hk,1zk,1hk,2zk,2hk,dzk,d)(yk,𝟎)
=(yk,𝟎)(y2,𝟎)(y1,𝟎)(h1,1z1,1h1,2z1,2h1,dz1,d)(hk,1zk,1hk,2zk,2hk,dzk,d)

Therefore

(h1,1z1,1h1,2z1,2h1,dz1,d)(hk,1zk,1hk,2zk,2hk,dzk,d)g1=(yky2y1,𝟎)𝒴1++𝒴k=𝒴~.

For the “if” part, let z1,1,,z1,d, , zk,1,,zk,d be integers that satisfy Equation (8). Since 𝒴~𝒴1++𝒴k, there exist y1𝒴1,,yk𝒴k, such that

(h1,1z1,1h1,2z1,2h1,dz1,d)(hk,1zk,1hk,2zk,2hk,dzk,d)g1=(y1+y2++yk,𝟎).

Denote yiX¯j=1dz1,j𝒂jj=1dz2,j𝒂jj=1dzi,j𝒂jyi, then yi𝒴i. We have

g =(y1y2yk,𝟎)(h1,1z1,1h1,2z1,2h1,dz1,d)(hk,1zk,1hk,2zk,2hk,dzk,d)
=(yk,𝟎)(y2,𝟎)(y1,𝟎)(h1,1z1,1h1,2z1,2h1,dz1,d)(hk,1zk,1hk,2zk,2hk,dzk,d)
=(h1,1z1,1h1,2z1,2h1,dz1,d)(y1,𝟎)(hk,1zk,1hk,2zk,2hk,dzk,d)(yk,𝟎).

For each i, we have (yi,𝟎)𝒴iqiH, so (hi,1zi,1hi,2zi,2hi,dzi,d)(yi,𝟎)qiH. Therefore gq1Hq2HqkH.

Proposition 4.4 then follows from Lemma 4.7:

Proof of Proposition 4.4.

By Lemma 4.7, we have gq1Hq2HqkH if and only if Equation (8) has integer solutions. Write hi,j as (fi,j,𝒂j) for i=1,,k;j=1,,d, and write g as (f0,𝒂0). Let denote the 𝔽p[X¯π(H)]-submodule of 𝒴 generated by f0 and fi,j,i=1,,k;j=1,,d. Notably, contains 𝒴i,i=1,,k. A finite presentation of can be computed (see Lemma 2.2). The group generated by g and all the hi,j’s is contained in the subgroup π(H) of 𝒴n. Hence, Equation (8) is equivalent to the following equation in (/𝒴~)π(H):

(h1,1z1,1h1,2z1,2h1,dz1,d)(hk,1zk,1hk,2zk,2hk,dzk,d)=g. (9)

Choose the new variables X1X¯𝒂1,,XdX¯𝒂d. Then the ring 𝔽p[X¯π(H)] can be written as the polynomial ring 𝔽p[X1±,,Xd±], and 𝒴/𝒴~ is now a finitely presented 𝔽p[X1±,,Xd±]-module. We conclude by letting G𝒴d=(/𝒴~)π(H), and observing that Equation (9) is a Knapsack equation of the form (7).

Remark 4.8.

Note that even if we only considered the lamplighter group G=(/p)n by supposing 𝒴=𝔽p[X¯], we would inevitably introduce the quotient by 𝒴~ during our reduction from Submonoid Membership to the Knapsack Problem. Therefore, it is reasonable to directly consider Submonoid Membership in the more general case of semidirect product 𝒴n with finitely presented 𝒴, instead of only the special case of lamplighter groups (/p)n. In other words, it does not appear that the special case of lamplighter groups admits a more direct solution.

Step 3: from Knapsack Problem to S-unit equation

The goal of this step is to solve the Knapsack Problem in groups of the form 𝒴n. Namely, assuming a theorem on S-unit equations (Theorem 3.3), we will prove the following result:

See 3.4

Before we proceed to the formal proof, let us show another example to illustrate the ideas.

Example 4.9.

Let p=2, n=2. Let 𝒴=𝔽2[X1±,X2±]/(X1+X2+1), that is, the quotient of 𝔽2[X1±,X2±] by the submodule 𝔽2[X1±,X2±](X1+X2+1). Let h1=(0,(1,0)),h2=(1X2,(0,1)),h3=(0,(1,0)),h4=(0,(0,1)),g=(1,(0,0)) be elements of 𝒴2. We will to show that the solution set of the equation

h1n1h2n2h3n3h4n4=g (10)

is 2-automatic.

By direct computation, we have (f,𝐚)z=((1+X¯𝐚++X¯(z1)𝐚)f,z𝐚) for z>0 and (f,𝐚)z=((X¯z𝐚X¯(z+1)𝐚X¯𝐚)f,z𝐚) for z<0. In either case (and for z=0), we have

(f,𝒂)z=(1X¯z𝒂1X¯𝒂f,z𝒂).

Hence,

h1n1h2n2h3n3h4n4 =(0,(1,0))n1(1X2,(0,1))n2(0,(1,0))n3(0,(0,1))n4
=(0,(n1,0))(1X2n21X2(1X2),(0,n2))(0,(n3,0))(0,(0,n4))
=(X1n1(1X2n2),(n1+n3,n2+n4))

Since g=(1,(0,0)), we have h1n1h2n2h3n3h4n4=g if and only if

X1n1(1X2n2)=1,n1+n3=0,n2+n4=0.

We now show that the solution set (n1,n2,n3,n4)4 is 2-automatic. Since n3=n1 and n4=n2, it suffices to show that the solution set (n1,n2)2 of X1n1(1X2n2)=1 is 2-automatic.

The equation X1n1(1X2n2)=1 can be rewritten as

X1n1+X2n2=1 (11)

Therefore, we have reduced the Knapsack equation (10) to the S-unit equation (11) over the module 𝔽2[X1±,X2±]/(X1+X2+1). The 2-automaticity of its solution set can already be deduced from Theorem 3.3 (see below). However, we now prove “by hand” that the solution set of the S-unit Equation (11) is 2-automatic, in order to give an idea of how 2-automaticity can arise from such equations.

Since we work in the module 𝔽2[X1±,X2±]/(X1+X2+1), we have X2=(X1+1)=X1+1 (we are in characteristic 2). Therefore, Equation (11) is equivalent to (X1+1)n2=X1n1+1. We claim that its solution set is (n1,n2){(2k,2k)k}.

Indeed, since X1n1+1𝔽2[X1±], we must have n20 so that (X1+1)n2 is also in 𝔽2[X1±]. Considering the degree of both sides we have n1=n2. Now, in order for (X1+1)n2=X1n2+1 to hold, n2 must be a power of 2. Indeed, n2=0 is not a solution, so suppose n21 and write n2=2k+a with 0a<2k. By “freshman’s dream”, we have

(X1+1)n2=(X1+1)2k(X1+1)a=(X12k+1)(X1+1)a=X12k(X1+1)a+(X1+1)a.

Every monomial appearing in X12k(X1+1)a has degree larger than every monomial appearing (X1+1)a. But (X1+1)n2=X1n2+1 has only two monomials. So both X12k(X1+1)a and (X1+1)a must be monomials, meaning a=0. Therefore n2=2k, and n1=n2=2k.

In conclusion, the solution set of Equation (10) is (n1,n2,n3,n4){(2k,2k,2k,2k)k}, which is 2-automatic. Note that this set is not semilinear, so the situation in semidirect products is more complicated than in the wreath product of two abelian groups [18].  

Example 4.9 shows that there will be two parts in the proof of Theorem 3.4: a (fairly elementary) first part reducing Knapsack Equations to S-unit equations, then a (rather non-trivial) second part showing that S-unit equations have p-automatic solution sets. The second part is summarized as Theorem 3.3 below, which we will prove in Section 5. In the rest of this section, we will focus on the first part of the proof, assuming Theorem 3.3 as a blackbox.

See 3.3

Proof of Theorem 3.4 (assuming Theorem 3.3).

Write hi=(fi,𝒂i),i=1,,m, and g=(f,𝒃).

Case 1: none of the 𝒂𝒊 is 𝟎

(in fact this case already suffices to solve the Equation (5) arising from the previous step). We have

hini=(fi,𝒂i)ni=(1X¯ni𝒂i1X¯𝒂ifi,ni𝒂i).

Computing their product gives

h1n1h2n2hmnm=(i=1mX¯n1𝒂1++ni1𝒂i11X¯ni𝒂i1X¯𝒂ifi,n1𝒂1++nm𝒂m).

Therefore, writing 𝒛in1𝒂1++ni𝒂i for i=1,,m, and 𝒛0𝟎, we have h1n1h2n2hmnm=g if and only if

i=1mX¯𝒛i11X¯𝒛i𝒛i11X¯𝒂ifi =f, (12)
and𝒛m =𝒃. (13)

Write 𝒴=𝔽p[X¯±]d/N for some N𝔽p[X¯±]d. Considering f1,,fm,f, as elements in 𝔽p[X¯±]d, Equation (12) is equivalent to

i=1m(X¯𝒛i1X¯𝒛i)ji(1X¯𝒂j)fii=1m(1X¯𝒂i)fi=1m(1X¯𝒂i)N.

Letting c0j1(1X¯𝒂j)f1+i=1m(1X¯𝒂i)f, cij(i+1)(1X¯𝒂j)fi+1ji(1X¯𝒂j)fi,i=1,,m1 and cmjm(1X¯𝒂j)fm, the equation above is equivalent to the following equation in M𝔽p[X¯±]d/i=1m(1X¯𝒂i)N:

X¯𝒛1c1++X¯𝒛mcm=c0. (14)

Therefore, we have h1n1h2n2hmnm=g if and only if 𝒛in1𝒂1++ni𝒂i,i=1,,m satisfy Equations (13) and (14). By Theorem 3.3, the set 𝒵 of (𝒛1,,𝒛m)mn satisfying (13) and (14) is p-automatic. Define the map φ:mmn,(n1,,nm)(n1𝒂1,n1𝒂1+n2𝒂2,,n1𝒂1++nm𝒂m). Then the solution set of h1n1h2n2hmnm=g is φ1(𝒵). Since 𝒵 is p-automatic and φ is linear, φ1(𝒵) is also p-automatic (see Lemma 2.3).

Case 2: some of the 𝒂𝒊’s are 𝟎.

This case can easily be reduced to the previous case. The full proof is given in the appendix of the full version of this paper.

Combining the three steps in this section, we have proven Theorem 3.1:

Proof of Theorem 3.1.

By Proposition 4.1, Proposition 4.4 and Theorem 3.4, Submonoid Membership in 𝒴n reduces to checking whether the solution set of the Knapsack Equation (5) is empty. Since the solution set is effectively p-automatic, its emptiness is decidable (Lemma 2.3).

5 S-unit equation over modules

The purpose of this section is to prove Theorem 3.3 on S-unit equations over modules.

See 3.3

As a comparison, S-unit equations over fields are an intensively studied area in number theory. In the positive characteristic case, Adamczewski and Bell gave the following result.

Theorem 5.1 ([1, Theorem 3.1]).

Let K be a field of characteristic p>0, let c1,,cmK, and let x¯=(x1,,xn)(K)n. Then the set of solutions (𝐳1,,𝐳m)(n)m for the equation

x¯𝒛1c1++x¯𝒛mcm=1

is an effectively p-automatic subset of (n)mnm.

Our objective is to generalize Theorem 5.1 from fields to modules. Notably, we need to replace the field K by the polynomial ring 𝔽p[X¯±], and replace the elements c1,,cm in K by elements in the finitely presented 𝔽p[X¯±]-module M. To give a general idea of our approach, consider the following example.

Example 5.2 (label=exa:Sunit).

For simplicity, we present this example using regular polynomial rings instead of Laurent polynomial rings. Consider the equation

Xa+Yb=1 (15)

in the 𝔽2[X,Y]-module 𝔽2[X,Y]/Y2(X+Y+1). Here, the variables are a,b. (Technically, in order to match the form of the equation in Theorem 3.3, one needs to consider the equation XaYc+XdYb=1 instead of (15). However, to keep this example simple, we only consider the solutions with c=d=0.)

Equation (15) in 𝔽2[X,Y]/Y2(X+Y+1) is equivalent to Y2(X+Y+1)Xa+Yb+1 in 𝔽2[X,Y], which in turn is equivalent to “Y2Xa+Yb+1 and X+Y+1Xa+Yb+1”. In other words, Equation (15) holds in 𝔽2[X,Y]/Y2(X+Y+1) if and only if it holds in both 𝔽2[X,Y]/Y2 and in 𝔽2[X,Y]/(X+Y+1).

The 𝔽2[X,Y]-module 𝔽2[X,Y]/Y2 can be considered as a finitely generated 𝔽2[X]-module 𝔽2[X,Y]/Y2=𝔽2[X]+Y𝔽2[X]𝔽2[X]2 by 1(1,0),Y(0,1). Considered as an equation in 𝔽2[X]2, the equation Xa+Yb=1 becomes

(Xa,0)=(1,0) if b2,(Xa,1)=(1,0) if b=1,(Xa+1,0)=(1,0) if b=0.

So the solution set of Xa+Yb=1 in 𝔽2[X,Y]/Y2 is 𝒵1{(a,b)a=0,b2}.

The 𝔽2[X,Y]-module 𝔽2[X,Y]/(X+Y+1) can be considered as the 𝔽2[X]-module 𝔽2[X] through the variable substitution Y=X+1. Under this variable substitution, the equation Xa+Yb=1 becomes Xa+(X+1)b=1, so its solution set is 𝒵2{(a,b)a=b2}. This can be shown similar to Example 4.9, or by directly applying Theorem 5.1 on the quotient field K=𝔽2(X).

Thus, the solution set of Equation (15) in 𝔽2[X,Y]/Y2(X+Y+1) is 𝒵1𝒵2=.  

Example 5.2 illustrates the idea that, to solve an equation in a module M, we first “decompose” it into several equations in coprimary modules M1,,Ml (such as 𝔽2[X,Y]/Y2 and 𝔽2[X,Y]/(X+Y+1)). This will be formalized in Lemma 5.6. Then, for the equation in each coprimary module, we “eliminate” variables to simplify the quotients (for example 𝔽2[X,Y]/Y2𝔽2[X]2 and 𝔽2[X,Y]/(X+Y+1)𝔽2[X] both eliminate the variable Y). In general, variable elimination might not be directly possible, and we need to perform a “change of variables” using Noether Normalization. This will be formalized in Lemma 5.8 and Lemma 5.9. Finally, we show that each such equation “without quotient” (more precisely, in torsion-free modules) has a p-automatic solution set, by reducing to the case of fields (for example, considering equations over 𝔽2[X] as equations over the quotient field 𝔽2(X)). This will be formalized in Lemma 5.10. Thus, the solution set of the original equation over M is an intersection of effectively p-automatic sets, and is therefore also effectively p-automatic. This approach is inspired by Derkson’s proof of the Skolem-Mahler-Lech theorem in modules over positive characteristic [13, Chapter 9].

The starting point of our proof is the following deep theorem by Adamczewski and Bell, generalizing Theorem 5.1.

Theorem 5.3 ([1, Theorem 4.1]).

Let K be a field of characteristic p>0 and let D be a positive integer. Let V be a Zariski closed subset of 𝖦𝖫D(K) and let A1,,AN be commuting matrices in 𝖦𝖫D(K). Then the set {(z1,,zN)NA1z1A2z2AnzNV} is effectively p-automatic.

For effectiveness reasons, we need to suppose K to be an effectively computable field (field where all arithmetic operations are effective): this will be the case in all our applications. We will not give the formal definition of a Zariski closed subset because in our application of Theorem 5.3, the set V will be of the form

V={A𝖦𝖫D(K)BAv=0d} (16)

for some d,BKd×D,vKD×1. This is a linear subset of 𝖦𝖫D(K) and hence Zariski closed. For a tuple of commutative matrices A¯=(A1,,An)(𝖦𝖫d(K))n and a vector 𝒛=(z1,,zn)n, denote

A¯𝒛A1z1A2z2Anzn,

similar to our notation for monomials. In the case where V has the form (16), Theorem 5.3 gives the following corollary, which can be considered as a version of Theorem 3.3 where the module M is replaced by a vector space over a field K.

Corollary 5.4.

Let K be a field of characteristic p>0 and let A¯=(A1,,An)(𝖦𝖫d(K))n be a tuple of commuting matrices. Let c0,c1,,cm be elements in the d-dimensional vector space Kd. Then, the set of solutions (𝐳1,,𝐳m)(n)m for the equation

A¯𝒛1c1++A¯𝒛mcm=c0 (17)

is an effectively p-automatic subset of (n)mnm.

Proof.

For any B1,,Bm+1𝖦𝖫d(K), we denote by diag(B1,,Bm+1) the block diagonal matrix in 𝖦𝖫(m+1)d(K) whose block diagonal entries are B1,,Bm+1. Let I denote the identity matrix of dimension d and denote D=(m+1)d. Consider the following elements in 𝖦𝖫D(K). For j=1,,n, let A1jdiag(Aj,I,,I),A2j=diag(I,Aj,,I),,Amj=diag(I,,Aj,I).

Furthermore, let v(c1,c2,,cm,c0)KD×1, and B(I,I,,I,I)Kd×D. Then, Equation (17) is equivalent to

B(i=1mj=1nAijzij)v=0d. (18)

We then apply Theorem 5.3 to the set

V={A𝖦𝖫D(K)BAv=0d}

and the commuting matrices Aij,i=1,,m;j=1,,n. This shows that the set of solutions (zij)1im,1jn for Equation (18) is an effectively p-automatic subset of nm.

To pass from vector spaces to modules, we now introduce the primary decomposition of a module. First, we recall some standard definitions and tools from commutative algebra [17].

Definition 5.5.

Let R be a commutative Noetherian ring (for example, R=𝕂[X¯±] for some field 𝕂).

  1. (1)

    An ideal of R is an R-submodule of R. An ideal IR is called prime if IR, and for every a,bR, abI implies aI or bI. Prime ideals are usually denoted by the Gothic letter 𝔭.

  2. (2)

    Let M be a finitely generated R-module. The annihilator of an element mM, denoted by AnnR(m), is the set {rRrm=0}.

  3. (3)

    An R-module M is called torsion-free if for every rR,mM, rm=0 implies r=0 or m=0. That is, M is torsion-free if and only if AnnR(m)={0} for all mM{0}.

  4. (4)

    A prime ideal 𝔭R is called associated to M if there exists a non-zero mM such that 𝔭=AnnR(m).

  5. (5)

    Let N be a finitely generated R-module. A submodule N of N is called primary if N/N has only one associated prime ideal. If we denote this prime ideal by 𝔭, then NN is called 𝔭-primary.

  6. (6)

    Let N be a submodule of a finitely generated R-module N. The primary decomposition of N is the writing of N as a finite intersection i=1lNi, where Ni is a 𝔭i-primary submodule of N for some prime ideal 𝔭iR. A primary decomposition always exists [17, Theorem 3.10]. If R=𝔽p[X¯±] and N,N are finitely generated submodules of Rd for some d, then a primary decomposition of NN can be effectively computed [36].

  7. (7)

    A finitely generated R-module M is called coprimary if the submodule {0} is primary, that is, if M has only one associated prime ideal. If we denote this prime ideal by 𝔭, then M is called 𝔭-coprimary. If M is 𝔭-coprimary, and m is a non-zero element in M, then AnnR(m)𝔭.

Let M=𝔽p[X¯±]d/N,N𝔽p[X¯±]d be the finite presentation of M in Theorem 3.3. Let N=i=1lNi be the primary decomposition of N as a submodule of 𝔽p[X¯±]d, where Ni is 𝔭i-primary for a prime ideal 𝔭i𝔽p[X¯±], i=1,,l. Then Mi𝔽p[X¯±]d/Ni is 𝔭i-coprimary. The finite presentation of Ni, and hence Mi, can be effectively computed (Definition 5.5(6)). Since NNi, there is a canonical map ρi:M=𝔽p[X¯±]d/NMi=𝔽p[X¯±]d/Ni. Since N=i=1lNi, the intersection of kernels i=1lker(ρi) is {0}.

Lemma 5.6.

For i=1,,l, let 𝒵i denote the set of solutions (𝐳1,,𝐳m)(n)m of the following equation in Mi:

X¯𝒛1ρi(c1)++X¯𝒛mρi(cm)=ρi(c0). (19)

Then the solution set of Equation (4) is exactly the intersection i=1l𝒵i.

Proof.

Since i=1lker(ρi)={0}, an element yM is zero if and only if ρi(y)=0 for all i=1,,l. Equation (4) is equivalent to X¯𝒛1c1++X¯𝒛mcmc0=0. This holds if and only if ρi(X¯𝒛1c1++X¯𝒛mcmc0)=0 for all i=1,,l. Therefore, Equation (4) holds if and only if Equation (19) holds for all i. Hence, the solution set of Equation (4) is exactly i=1l𝒵i.

Example 5.7 (continues=exa:Sunit).

In Example 5.2, we took R to be the ring 𝔽2[X,Y], and M to be the finitely presented R-module 𝔽2[X,Y]/Y2(X+Y+1). In this case, we have M=𝔽2[X,Y]/N with N=𝔽2[X,Y]Y2(X+Y+1), whose primary decomposition is N=N1N2,N1=𝔽2[X,Y]Y2,N2=𝔽2[X,Y](X+Y+1). The modules M1=𝔽2[X,Y]/N1=𝔽2[X,Y]/Y2 and M2=𝔽2[X,Y]/N2=𝔽2[X,Y]/(X+Y+1) are respectively 𝔭1 and 𝔭2-coprimary, where 𝔭1 is the ideal of R generated by Y, and 𝔭2 is the ideal of R generated by X+Y+1. The sets 𝒵1,𝒵2 are respectively solutions of the equation Xa+Yb=1 in M1 and M2.  

Our next step is to show that each 𝒵i is effectively p-automatic. If so, then their intersection i=1l𝒵i will also be p-automatic (see Lemma 2.3). Fix i{1,,l}. Note that Equation (19) is now an equation over the 𝔭i-coprimary 𝔽p[X¯±]-module Mi. This motivates us to consider the quotient ring 𝔽p[X¯±]/𝔭i. We start with the following staple result in commutative algebra, which can be intuitively understood as performing a “change of variable” to simplify 𝔽p[X¯±]/𝔭i.

Lemma 5.8 (Noether Normalization Lemma [32, p.2]).

Let 𝕂 be an infinite field and A be a finitely generated 𝕂-algebra. Then there exist algebraically independent elements X~1,,X~sA such that A is a finitely generated 𝕂[X~1,,X~s]-module.

Ideally we would want to apply the Noether Normalization Lemma to A=𝔽p[X¯±]/𝔭i. Even though 𝔽p is not an infinite field, we can without loss of generality replace it with its algebraic closure 𝕂 (which is infinite). Formally, we replace 𝔭i with 𝔭i𝔽p𝕂 and Mi with Mi𝔽p𝕂. Now 𝔭i and Mi are respectively an ideal and a module over the ring 𝕂[X¯±]=𝔽p[X¯±]𝔽p𝕂. Note that this does not change the solution set 𝒵i.

The classical proof of Noether Normalization Lemma is constructive [32, p.2]. In our context, this means that given A=𝕂[X¯±]/𝔭i, the lemma explicitly gives the expressions for X~1,,X~sA as elements in 𝕂[X¯±]/𝔭i.

Choose Y1,,Ys𝕂[X¯±] such that Yi+𝔭i=X~i for all i. Since X~1,,X~s are algebraically independent in A=𝕂[X¯±]/𝔭i, we have 𝔭i𝕂[Y1,,Ys]={0}. Any finitely generated 𝕂[X¯±]-module M is also a 𝕂[Y1,,Ys]-module. However, M might not be finitely generated as a 𝕂[Y1,,Ys]-module. However, in case M is also finitely generated as a 𝕂[Y1,,Ys]-module, then a finite presentation can be effectively computed. This is summarized in the following rather standard result in effective commutative algebra.

Lemma 5.9 ([5, Section 2]).

Let Y1,,Ys𝕂[X¯±]. Suppose we are given the finite presentation of an 𝕂[X¯±]-module M, as well as a finite number of generators m1,,mt of M as a 𝕂[Y1,,Ys]-module. Then one can effectively compute the finite presentation of M as a 𝕂[Y1,,Ys]-module.

Lemma 5.10.

The set 𝒵i is effectively p-automatic.

Proof.

The main line of our proof follows [13, Lemma 9.7-9.8], with additional remarks given on effectiveness. As above, we can replace the base field 𝔽p by its algebraic closure 𝕂.

Since Mi is 𝔭i-coprimary, we can compute t such that 𝔭itMi=0 (such t exists by the ascending chain condition [17, Chapter 1.4]). We have Mi𝔭iMi𝔭i2Mi𝔭itMi=0. Because 𝔭i(𝔭ijMi/𝔭ij+1Mi)=0, each quotient 𝔭ijMi/𝔭ij+1Mi is a finitely generated 𝕂[X¯±]/𝔭i-module with effectively computable generators, and therefore a finitely generated 𝕂[Y1,,Ys]-module with effectively computable generators. It follows that the 𝕂[X¯±]-module Mi is also finitely generated as a 𝕂[Y1,,Ys]-module, with effectively computable generators. Since the finite presentation of Mi as a 𝕂[X¯±]-module is given, we can compute the finite presentation of Mi as a 𝕂[Y1,,Ys]-module by Lemma 5.9.

Since Mi is 𝔭i-coprimary, the annihilator of any non-zero element in Mi as a 𝕂[Y1,,Ys]-module is contained in 𝔭i𝕂[Y1,,Ys]={0} (see Definition 5.5(7)). Therefore, Mi is a finitely generated torsion-free 𝕂[Y1,,Ys]-module (see Definition 5.5(3)).

Consider the quotient field K𝕂(Y1,,Ys) of 𝕂[Y1,,Ys]. The localization Mi~Mi𝕂[Y1,,Ys]K is a finite dimensional K-linear space, so Mi~Kd for some integer d. Because Mi is torsion-free, the canonical map φ:MiMi𝕂[Y1,,Ys]K is injective. The linear transformations Aj:Mi~Mi~,yXjy, commute for j=1,,n, and they are respectively inverses of the transformations Aj1:Mi~Mi~,yXj1y. Hence, Aj is in 𝖦𝖫d(K) for j=1,,n, for a fixed basis of Mi~Kd, and these matrices commute.

Since φ is injective, Equation (19) holds if and only if

A¯𝒛1φ(ρi(c1))++A¯𝒛mφ(ρi(cm))=φ(ρi(c0)), (20)

where A¯=(A1,,An). So 𝒵i is the solution set for Equation (20). Note that K=𝕂(Y1,,Ys) is an effective field. We now apply Corollary 5.4, and conclude that the solution set for Equation (20) is an effectively p-automatic subset of (n)mnm.

Example 5.11 (continues=exa:Sunit).

As above, the 𝕂[X,Y]-module M1=𝕂[X,Y]/Y2 is isomorphic to the 𝕂[X]-module 𝕂[X]2 by 𝕂[X,Y]/Y2𝕂[X]2,f0+Yf1+Y2f2+(f0,f1), for f0,f1,f2,𝕂[X].

We would like to solve the equation Xa+Yb=1 in M1. Let 𝕂(X) denote the quotient field of 𝕂[X]: this is the set of univariate rational functions over the field 𝕂. Note that φ:M1𝕂[X]2𝕂(X)2 is injective. Consider 𝕂(X)2 as a 2-dimensional vector space over 𝕂(X), then the map φ(m)φ(Xm),mM1, extends to a linear transformation associated to the matrix AX=(X00X), and the map φ(m)φ(Ym),mM1 extends to a linear transformation associated to the matrix AY=(0100). (Here, AY is not invertible because the variable Y is not invertible in 𝕂[X,Y]. However in the proof of Lemma 5.10, we are considering Laurent polynomial rings, so all the associated matrices would be invertible.)

As a result, the equation Xa+Yb=1 in M1 is equivalent to the equation AXa(1,0)+AYb(1,0)=(1,0) in the 2-dimensional vector space 𝕂(X)2. Subject to the invertibility of AY, we can then use Corollary 5.4 to conclude that the equation admits an effectively 2-automatic solution set.  

Combining Lemma 5.6 and Lemma 5.10, we obtain a proof of Theorem 3.3:

Proof of Theorem 3.3.

By Lemma 5.6, the solution set of Equation (4) is the intersection i=1l𝒵i. Lemma 5.10 shows that each 𝒵i is effectively p-automatic, so their intersection is also effectively p-automatic (Lemma 2.3).

References

  • [1] Boris Adamczewski and Jason P. Bell. On vanishing coefficients of algebraic power series over fields of positive characteristic. Inventiones mathematicae, 187(2):343–393, 2012.
  • [2] László Babai, Robert Beals, Jin-yi Cai, Gábor Ivanyos, and Eugene M. Luks. Multiplicative equations over commuting matrices. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 498–507, 1996. URL: http://dl.acm.org/citation.cfm?id=313852.314109.
  • [3] Sebastián Barbieri, Jarkko Kari, and Ville Salo. The group of reversible Turing machines. In Cellular Automata and Discrete Complex Systems: 22nd IFIP WG 1.5 International Workshop, AUTOMATA 2016, Zurich, Switzerland, June 15-17, 2016, Proceedings 22, pages 49–62. Springer, 2016. doi:10.1007/978-3-319-39300-1_5.
  • [4] Laurent Bartholdi and Ville Salo. Simulations and the lamplighter group. Groups, Geometry, and Dynamics, 16(4):1461–1514, 2022.
  • [5] Gilbert Baumslag, Frank B. Cannonito, and Charles F. Miller III. Computable algebra and group embeddings. Journal of Algebra, 69(1):186–212, 1981.
  • [6] Gilbert Baumslag, Frank B. Cannonito, and Derek J.S. Robinson. The algorithmic theory of finitely generated metabelian groups. Transactions of the American Mathematical Society, 344(2):629–648, 1994.
  • [7] Robert Beals and László Babai. Las Vegas algorithms for matrix groups. In Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, pages 427–436. IEEE, 1993. doi:10.1109/SFCS.1993.366844.
  • [8] Michèle Benois. Parties rationnelles du groupe libre. C. R. Acad. Sci. Paris, Sér. A,, 269:1188–1190, 1969.
  • [9] Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, and Natacha Portier. Decidable and undecidable problems about quantum automata. SIAM Journal on Computing, 34(6):1464–1473, 2005. doi:10.1137/S0097539703425861.
  • [10] Corentin Bodart. Membership problems in nilpotent groups. arXiv preprint arXiv:2401.15504, 2024. doi:10.48550/arXiv.2401.15504.
  • [11] Michaël Cadilhac, Dmitry Chistikov, and Georg Zetzsche. Rational subsets of Baumslag-Solitar groups. In 47th International Colloquium on Automata, Languages, and Programming, ICALP, volume 168 of LIPIcs, pages 116:1–116:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPICS.ICALP.2020.116.
  • [12] Thomas Colcombet, Joël Ouaknine, Pavel Semukhin, and James Worrell. On reachability problems for low-dimensional matrix semigroups. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 44:1–44:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPICS.ICALP.2019.44.
  • [13] Harm Derksen. A Skolem–Mahler–Lech theorem in positive characteristic and finite automata. Inventiones mathematicae, 168(1):175–224, 2007.
  • [14] Harm Derksen, Emmanuel Jeandel, and Pascal Koiran. Quantum automata and algebraic groups. Journal of Symbolic Computation, 39(3-4):357–371, 2005. doi:10.1016/j.jsc.2004.11.008.
  • [15] Ruiwen Dong. Recent advances in algorithmic problems for semigroups. ACM SIGLOG News, 10(4):3–23, 2023. doi:10.1145/3636362.3636365.
  • [16] Ruiwen Dong. Linear equations with monomial constraints and decision problems in abelian-by-cyclic groups. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1892–1908. SIAM, 2025. doi:10.1137/1.9781611978322.59.
  • [17] David Eisenbud. Commutative algebra: with a view toward algebraic geometry, volume 150. Springer Science & Business Media, 2013.
  • [18] Moses Ganardi, Daniel König, Markus Lohrey, and Georg Zetzsche. Knapsack problems for wreath products. In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, volume 96 of LIPIcs, pages 32:1–32:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPICS.STACS.2018.32.
  • [19] Rostislav Grigorchuk and Andrzej Żuk. The lamplighter group as a group generated by a 2-state automaton, and its spectrum. Geometriae Dedicata, 87(1):209–244, 2001.
  • [20] Zeph Grunschlag. Algorithms in geometric group theory. University of California, Berkeley, 1999.
  • [21] Philipp Hieronymi and Christian Schulz. A strong version of Cobham’s theorem. SIAM Journal on Computing, 51(6):1400–1421, 2022. doi:10.1137/22M1538065.
  • [22] Ehud Hrushovski, Joël Ouaknine, Amaury Pouly, and James Worrell. Polynomial invariants for affine programs. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, pages 530–539, 2018. doi:10.1145/3209108.3209142.
  • [23] Mark Kambites, Pedro V. Silva, and Benjamin Steinberg. The spectra of lamplighter groups and Cayley machines. Geometriae Dedicata, 120(1):193–227, 2006.
  • [24] Toghrul Karimov, Florian Luca, Joris Nieuwveld, Joël Ouaknine, and James Worrell. On the decidability of Presburger arithmetic expanded with powers. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2755–2778. SIAM, 2025. doi:10.1137/1.9781611978322.89.
  • [25] Markus Lohrey. Membership problems in infinite groups. In Conference on Computability in Europe, pages 44–59. Springer, 2024. doi:10.1007/978-3-031-64309-5_5.
  • [26] Markus Lohrey and Benjamin Steinberg. The submonoid and rational subset membership problems for graph groups. Journal of Algebra, 320(2):728–755, 2008.
  • [27] Markus Lohrey and Benjamin Steinberg. Tilings and submonoids of metabelian groups. Theory of Computing Systems, 48(2):411–427, 2011. doi:10.1007/S00224-010-9264-9.
  • [28] Markus Lohrey, Benjamin Steinberg, and Georg Zetzsche. Rational subsets and submonoids of wreath products. Information and Computation, 243:191–204, 2015. doi:10.1016/J.IC.2014.12.014.
  • [29] Russell Lyons, Robin Pemantle, and Yuval Peres. Random walks on the lamplighter group. The annals of probability, pages 1993–2006, 1996.
  • [30] A. Markov. On an unsolvable problem concerning matrices. Doklady Akad. Nauk SSSR, 78(6):1089–1092, 1951.
  • [31] K. A. Mikhailova. The entrance problem for direct unions of groups. Doklady Akad. Nauk SSSR, 119(6):1103–1105, 1958.
  • [32] David Mumford. The Red Book of Varieties and Schemes, volume 1358 of Lecture Notes in Mathematics. Springer, 1999.
  • [33] Igor Potapov and Pavel Semukhin. Decidability of the membership problem for 2 × 2 integer matrices. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 170–186. SIAM, 2017.
  • [34] Felix Potthast. Submonoid Membership for Wreath Products. Bachelor’s thesis, Universität Siegen, 2020. Based on the unpublished draft of Doron Shafrir: The Submonoid Problem in Torsion-by-d Groups, private communication with Markus Lohrey and Benjamin Steinberg. May 2018.
  • [35] N.S. Romanovskii. Some algorithmic problems for solvable groups. Algebra and Logic, 13(1):13–16, 1974.
  • [36] Elizabeth W. Rutman. Gröbner bases and primary decomposition of modules. Journal of symbolic computation, 14(5):483–503, 1992. doi:10.1016/0747-7171(92)90019-Z.
  • [37] Doron Shafrir. Is decidability of the Submonoid Membership Problem closed under finite extensions? arXiv preprint arXiv:2405.12921, 2024. doi:10.48550/arXiv.2405.12921.
  • [38] Pedro V. Silva and Benjamin Steinberg. On a class of automata groups generalizing lamplighter groups. International journal of algebra and computation, 15(05n06):1213–1234, 2005. doi:10.1142/S0218196705002761.
  • [39] Pierre Wolper and Bernard Boigelot. On the construction of automata from linear arithmetic constraints. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 1–19. Springer, 2000. doi:10.1007/3-540-46419-0_1.