Boris Adamczewski

Jason P Bell

ON VANISHING COEFFICIENTS OF ALGEBRAIC POWER SERIES OVER FIELDS OF POSITIVE CHARACTERISTIC by

Let K be a field of characteristic p > 0 and let f (t1, . . . , t d ) be a power series in d variables with coefficients in K that is algebraic over the field of multivariate rational functions K(t1, . . . , t d ). We prove a generalization of both Derksen's recent analogue of the Skolem-Mahler-Lech theorem in positive characteristic and a classical theorem of Christol, by showing that the set of indices (n1, . . . , n d ) ∈ N d for which the coefficient of

Applying this result to multivariate rational functions leads to interesting effective results concerning some Diophantine equations related to S-unit equations and more generally to the Mordell-Lang Theorem over fields of positive characteristic.

Introduction

The Skolem-Mahler-Lech theorem is a celebrated result which describes the set of solutions in n to the equation a(n) = 0, where a(n) is a sequence satisfying a linear recurrence over a field of characteristic 0. We recall that if K is a field and a is a K-valued sequence, then a satisfies a linear recurrence over K if there exists a natural number m and values c 1 , . . . , c m ∈ K such that

a(n) = m i=1 c i a(n -i)
for all sufficiently large values of n. The zero set of the linear recurrence a is defined by Z(a) := {n ∈ N | f (n) = 0} . The Skolem-Mahler-Lech theorem can then be stated as follows.

Theorem 1.1 (Skolem-Mahler-Lech). -Let a be a linear recurrence over a field of characteristic 0. Then the set Z(a) is a union of a finite set and a finite number of infinite arithmetic progressions.

This result was first proved for linear recurrences over the rational numbers by Skolem [START_REF] Skolem | Ein Verfahren zur Behandlung gewisser exponentialer Gleichungen und dio-phantischer Gleichungen[END_REF]. It was next extended to linear recurrences over the algebraic numbers by Mahler [START_REF] Mahler | Eine arithmetische Eigenschaft der Taylor-Koeffizienten rationaler Funktionen[END_REF]. The version above was proven first by Lech [START_REF] Lech | A note on recurring series[END_REF] and later by Mahler [START_REF] Mahler | On the Taylor coefficients of rational functions[END_REF][START_REF] Mahler | Addendum to the paper "On the Taylor coefficients of rational functions[END_REF]. More details about the history of this theorem can be found in the book by Everest et al. [START_REF] Everest | Recurrence Sequences[END_REF].

Though the conclusion of the Skolem-Mahler-Lech theorem obviously holds for linear recurrences defined over finite fields, this is not the case for infinite fields K of positive characteristic. The simplest counter-example was given by Lech [START_REF] Lech | A note on recurring series[END_REF]. Throughout this paper, p will denote a prime number. Let K = F p (t) be the field of rational functions in one variable over F p . Let a(n) := (1 + t) nt n -1 .

We can observe that the sequence a satisfies the recurrence a(n) = (2 + 2t)a(n -1) -(1 + 3t + t 2 )a(n -2) + (t + t 2 )a(n -3) for n > 3, while Z(a) = {1, p, p 2 , p 3 , . . .} .

More recently, Derksen [START_REF] Derksen | A Skolem-Mahler-Lech theorem in positive characteristic and finite automata[END_REF] gave more pathological examples, which show that the correct analogue of the Skolem-Mahler-Lech theorem in positive characteristic is much more subtle. For example, one has

Z(a) = {p n | n ∈ N} ∪ {p n + p m | n, m ∈ N} ,
for the linear recurrence a defined over the field F p (x, y, z) by a(n) := (x + y + z) n -(x + y) n -(x + z) n -(y + z) n + x n + y n + z n .

Derksen noted that while pathological examples of zero sets of linear recurrences do exist in characteristic p, the base-p expansions of the natural numbers in the zero set are still well behaved. In fact, he proved the remarkable result that the zero set of a linear recurrence can always be described in terms of finite automata [START_REF] Derksen | A Skolem-Mahler-Lech theorem in positive characteristic and finite automata[END_REF].

Theorem 1.2 (Derksen). -Let a be a linear recurrence over a field K of characteristic p. Then the set Z(a) is p-automatic.

We recall that an infinite sequence a with values in a finite set is said to be p-automatic if a(n) is a finite-state function of the base-p representation of n. Roughly, this means that there exists a finite automaton taking the base-p expansion of n as input and producing the term a(n) as output. A set E ⊂ N is said to be p-automatic if there exists a finite automaton that reads as input the base-p expansion of n and accepts this integer (producing as output the symbol 1) if n belongs to E, otherwise this automaton rejects the integer n, producing as output the symbol 0.

Let us give a formal definition of both notions. Let k ≥ 2 be a natural number. We let Σ k denote the alphabet {0, 1, . . . , k -1}. A k-automaton is a 6-tuple A = (Q, Σ k , δ, q 0 , ∆, τ ) , where Q is a finite set of states, δ : Q × Σ k → Q is the transition function, q 0 is the initial state, ∆ is the output alphabet and τ : Q → ∆ is the output function. For a state q in Q and for a finite word w = w 1 w 2 • • • w n on the alphabet Σ k , we define δ(q, w) recursively by δ(q, w) = δ(δ(q, w 1 w 2 • • • w n-1 ), w n ). Let n ≥ 0 be an integer and let w r w r-1 • • • w 1 w 0 in (Σ k ) r+1 be the base-k expansion of n. Thus n = r i=0 w i k i := [w r w r-1 • • • w 0 ] k . We denote by w(n) the word w 0 w 1 • • • w r . Definition 1.1. -A sequence (a n ) n≥0 is said to be k-automatic if there exists a k-automaton A such that a n = τ (δ(q 0 , w(n))) for all n ≥ 0. Definition 1.2. -A set E ⊂ N is said to be recognizable by a finite kautomaton, or for short k-automatic, if the characteristic sequence of E, defined by a n = 1 if n ∈ E and a n = 0 otherwise, is a k-automatic sequence.

More generally, feeding a finite automaton with d-tuples of nonnegative integers leads to the notion of p-automatic subsets of N d . Some background on automata theory, including examples, formal definitions of multidimensional automatic sequences and sets, and their extension to arbitrary finitely generated abelian groups, are given in Section 5.

Remark 1.1. -Let us make few important remarks.

• In the previous definitions, we chose the convention that the base-k expansion of n is scanned from left to right. Our automata thus read the input starting with the most significant digit. We recall that it is wellknown that the class of k-automatic sets or sequences remains unchanged when choosing to read the input starting from the least significant digit (see for instance Chapter V of [START_REF] Eilenberg | Automata, Languages, and Machines[END_REF] or Chapter 5 of [START_REF] Allouche | Automatic sequences. Theory, applications, generalizations[END_REF]).

• One could also ask whether the base k plays an important role here.

As proved in a fundamental paper of Cobham [START_REF] Cobham | On the base-dependence of sets of numbers recognizable by finite automata[END_REF], this is actually the case. Periodic sets, that are sets obtained as a union of a finite set and a finite number of infinite arithmetic progressions, are exactly those that are k-automatic for every integer k ≥ 2. In addition, an infinite aperiodic k-automatic set is also k n -automatic for every positive integer n, while it cannot be ℓ-automatic if k and ℓ are two multiplicatively independent integers.

• The class of k-automatic sets is closed under various natural operations such as intersection, union and complement (see for instance Chapter V of [START_REF] Eilenberg | Automata, Languages, and Machines[END_REF] or Chapter 5 of [START_REF] Allouche | Automatic sequences. Theory, applications, generalizations[END_REF]).

On the other hand, it is well known that if K is a field and a is a K-valued sequence, then a satisfies a linear recurrence over K if and only if the power series

f (t) = ∞ n=0 a(n)t n
is the power series expansion of a rational function. For instance, Mahler [START_REF] Mahler | Eine arithmetische Eigenschaft der Taylor-Koeffizienten rationaler Funktionen[END_REF][START_REF] Mahler | On the Taylor coefficients of rational functions[END_REF][START_REF] Mahler | Addendum to the paper "On the Taylor coefficients of rational functions[END_REF] worked with rational power series rather than linear recurrences when proving what we now call the Skolem-Mahler-Lech theorem. Let Z(f ) := {n | a(n) = 0} . Then Derksen's theorem can be restated as follows: let K be a field of characteristic p and let f (t) ∈ K[[t]] be a rational function, then the set Z(f ) is p-automatic.

This formulation of Derksen's theorem is in the same spirit as another famous result involving automata theory and known as Christol's theorem [START_REF] Christol | Suites algébriques, automates et substitutions[END_REF].

Theorem 1.3 (Christol). -Let q be a positive integer power of p. Then

f (t) = ∞ n=0 a(n)t n ∈ F q [[t]
] is algebraic over F q (t) if and only if the sequence a is p-automatic.

The main aim of this paper is to produce a simultaneous multivariate generalization of both the theorem of Derksen and the theorem of Christol.

Given a multivariate power series

f (t 1 , . . . , t d ) = (n 1 ,...,n d )∈N d a(n 1 , . . . , n d )t n 1 1 • • • t n d d ∈ K[[t 1 , . . . , t d ]] ,
we define the set of vanishing coefficients of f by

Z(f ) = {(n 1 , . . . , n d ) ∈ N d | a(n 1 , . . . , n d ) = 0} .
Our main result reads as follows.

Theorem Let us make few comments on this result.

• In the case that d = 1 and f (t) is chosen to be the power series expansion of a rational function in Theorem 1.4, we immediately obtain Derksen's theorem (Theorem 1.2). We do not obtain his finer characterization, but, as explained in Section 9, it is not possible to obtain a significantly improved characterization of zero sets even for multivariate rational power series.

• In the case that d = 1 and K is chosen to be a finite field in Theorem 1.4, we cover the more difficult direction of Christol's theorem (Theorem

1.3). Indeed, if f (t) = ∞ n=0 a(n)t n ∈ K[[t]
] is an algebraic power series, then for each x ∈ K the function f (t)x/(1t) is algebraic. Theorem 1.4 thus implies that the set {n ∈ N | a(n) = x} is p-automatic for all x ∈ K. This immediately implies that the sequence a is p-automatic.

• Theorem 1.4 can actually take a stronger form. Let E ⊂ N d . The following conditions are equivalent. (i) The set E is p-automatic.

(ii) E = Z(f ) for some algebraic power series with coefficients over a field of characteristic p. Indeed, it is known [START_REF] Salon | Suites automatiques à multi-indices et algébricité[END_REF] that given a p-automatic set E ⊂ N d , the formal power series

f (t 1 , . . . , t d ) = (n 1 ,...,n d )∈E t n 1 1 • • • t n d d is algebraic over F p (t 1 , . . . , t d ).
From the latter property and Theorem 1.4, we also deduce the following result. Let K be a field of characteristic p and let

f (t 1 , . . . , t d ) = (n 1 ,...,n d )∈N d a(n 1 , . . . , n d )t n 1 1 • • • t n d d ∈ K[[t 1 , . . . , t d ]]
be a power series that is algebraic over the field of multivariate rational functions K(t 1 , . . . , t d ). For x ∈ K, let

a -1 (x) := (n 1 , . . . , n d ) ∈ N d | a(n 1 , . . . , n d ) = x .
Then for every x ∈ K the formal power series

f x (t 1 , . . . , t d ) := (n 1 ,...,n d )∈a -1 (x) t n 1 1 • • • t n d d
is also algebraic. In the particular case where K is a finite field, this result was first proved by Furstenberg [START_REF] Furstenberg | Algebraic functions over finite fields[END_REF] (see also the more recent result of Kedlaya [START_REF] Kedlaya | Finite automata and algebraic extensions of function fields[END_REF] for a generalization to Hahn's power series with coefficients in a finite field).

• No such multivariate generalization of the Skolem-Mahler-Lech theorem exists in characteristic 0. For example, if one takes the rational bivariate power series

f (x, y) = n,m (n 3 -2 m )x n y m ∈ Q[[x, y]] , then Z(f ) = {(n, m) | m ≡ 0 (mod 3), n = 2 m/3
}. This shows that there is no natural way to express the set of vanishing coefficients of f in terms of more general arithmetic progressions or in terms of automatic sets. In fact, finding zero sets of coefficients of multivariate rational power series with integer coefficients is often equivalent to very difficult classes of Diophantine problems which cannot be solved at this moment, such as for instance finding an effective procedure to solve all S-unit equations (see Section 3 for more details). In Section 2, we also give a Diophantine problem related to linear recurrences which is conjectured in [START_REF] Cerlienco | Suites récurrentes linéaires : propriétés algébriques et arithmétiques[END_REF] to be undecidable and, as shown in the proof of Theorem 2.1, which is equivalent to describe the zero sets of coefficients of a class of simple mutivatiate rational power series with integer coefficients.

Our proof of Theorem 1.4 involves using methods of Derksen as well as more advanced techniques from automata theory reminiscent of works of Christol [START_REF] Christol | Suites algébriques, automates et substitutions[END_REF], Denef and Lipshitz [START_REF] Denef | Algebraic power series and diagonals[END_REF], Harase [START_REF] Harase | Algebraic elements in formal power series rings[END_REF], Shariff and Woodcock [START_REF] Sharif | Algebraic functions over a field of positive characteristic and Hadamard products[END_REF] among others. We first consider the action of a certain infinite semigroup on the ring of power series over a field of characteristic p. We use the fact that algebraic power series have a finite orbit under the action of this semigroup to apply Derksen's "Frobenius splitting" technique which allows us to show that the set of vanishing coefficients is necessarily p-automatic. An especially important aspect of the proof of Theorem 1.2 is that each step can be made effective. We prove that this is also the case with Theorem 1.4.

Theorem 1.5. -Let K be a field of positive characteristic and let f (t 1 , . . . , t d ) ∈ K[[t 1 , . . . , t d ]] be a power series that is algebraic over the field of multivariate rational functions K(t 1 , . . . , t d ). Then the set Z(f ) can be effectively determined. Furthermore, the following properties are decidable.

(i) the set Z(f ) is empty. (ii) the set Z(f ) is finite.
(iii) the set Z(f ) is periodic, that is, formed by the union of a finite set and of a finite number of (d-dimensional) arithmetic progressions.

In particular, when Z(f ) is finite, one can determine (in a finite amount of time) all its elements.

Remark 1.2. -When we say that the set Z(f ) can be effectively determined, this means that there is an algorithm that produces a p-automaton that generates Z(f ) in a finite amount of time. Furthermore, there exists an algorithm that allows one to determine in a finite amount of time whether or not Z(f ) is empty, finite, or periodic.

As we will illustrate in Sections 2, 3 and 4, applying Theorem 1.5 to multivariate rational functions actually leads to interesting effective results concerning some Diophantine equations related to S-unit equations and more generally to the Mordell-Lang Theorem over fields of positive characteristic.

The outline of this paper is as follows. Our Diophantine applications are discussed in Sections 2, 3 and 4. In Section 5, we recall some basic background on automata theory. We define in particular the notion of automatic sets of N d and more generally of automatic subsets of finitely generated abelian groups. The latter notion does not appear to have been introduced earlier and may be of independent interest. In Section 6, we prove Theorem 1.4. In Sections 7 and 8, we make the proof of Theorem 1.4 effective, proving Theorem 1.5. Finally, we conclude our paper with some comments in Section 9.

Linear recurrences and decidability

There are many different proofs and extensions of the Skolem-Mahler-Lech theorem in the literature (see for instance [START_REF] Bézivin | Une généralisation du théorème de Skolem-Mahler-Lech[END_REF][START_REF] Hansel | Une démonstration simple du théorème de Skolem-Mahler-Lech, Theoret[END_REF][START_REF] Van Der Poorten | Some facts that should be better known, especially about rational functions[END_REF][START_REF] Everest | Recurrence Sequences[END_REF]). These proofs all use p-adic methods in some way, although the result is valid in any field of characteristic 0. This seems to be responsible for a well-known deficiency of the Skolem-Mahler-Lech theorem: all known proofs are ineffective. This means that we do not know any algorithm that allows us to determine the set Z(a) for a given linear recurrence a(n) defined over a field of characteristic 0. We refer the reader to [START_REF] Everest | Recurrence Sequences[END_REF] and to the recent discussion in [START_REF] Tao | Structure and randomness, Pages from year one of a mathematical blog[END_REF] for more details. It is actually still unknown whether the fact that Z(a) is empty or not is decidable. In fact, it seems unclear that one should even expect it to be decidable. In this direction, let us recall the following conjecture from [START_REF] Cerlienco | Suites récurrentes linéaires : propriétés algébriques et arithmétiques[END_REF]. Given linear recurrences a 1 (n), . . . , a d (n) over a field K, we let

Z(a 1 , . . . , a d ) := (n 1 , . . . , n d ) ∈ N d | a 1 (n 1 ) + • • • + a d (n d ) = 0 . It was conjectured in [4] that, if K = Q, the property Z(a 1 , . . . , a d ) = ∅
is undecidable for every positive integer d large enough.

As mentioned in the introduction, the situation is drastically different for fields of positive characteristic. Indeed, Derksen [START_REF] Derksen | A Skolem-Mahler-Lech theorem in positive characteristic and finite automata[END_REF] proved that each step of the proof of Theorem 1.2 can be made effective. In particular, there exists an algorithm that allows one to decide whether the set Z(a) is empty or not in a finite amount of time. We give below a generalization of Derksen's theorem to an arbitrary number of linear recurrences. It well illustrates the relevance of Theorem 1.5.

Theorem 2.1. -Let K be a field of characteristic p, d a positive integer, and let a 1 (n), . . . , a d (n) be linear recurrences over K. Then Z(a 1 , . . . , a d ) is a p-automatic set that can be effectively determined. In particular, the property

Z(a 1 , . . . , a d ) = ∅ is decidable.
Note that, in addition, we can decide whether such a set Z(a 1 , . . . , a d ) is finite or periodic.

Proof. -In view of Theorem 1.5, it suffices to prove that there exists an explicit multivariate rational function f (t 1 , . . . , t d ) ∈ K(t 1 , . . . , t d ) such that Z(f ) = Z(a 1 , . . . , a d ).

Let i ∈ {1, . . . , d}. Since a i is a linear recurrence over K, we have that f i (t) := n≥0 a i (n)t n is a rational function. Thus,

f (t 1 , . . . , t d ) := d i=1   f i (t i ) • j =i 1 1 -t j   is a multivariate rational function in K(t 1 , . . . , t d ). Furthermore, this definition implies that f (t 1 , . . . , t d ) = (n 1 ,...,n d )∈N d (a 1 (n 1 ) + • • • + a d (n d ))t n 1 1 • • • t n d d .
We thus deduce that Z(f ) = Z(a 1 , . . . , a d ). This ends the proof.

Linear equations over multiplicative groups

In this section, we discuss some Diophantine equations that generalize the famous S-unit equations (see for instance the survey [START_REF] Evertse | S-unit equations and their applications[END_REF]). More precisely, given a field K and a finitely generated subgroup Γ of K * , we consider linear equations of the form

(3.1) c 1 X 1 + • • • + c d X d = 1 ,
where c 1 , . . . , c d belong to K and where we look for solutions in Γ d . These equations have a long history. Let S be a finite number of prime numbers and Γ ⊆ Q * the multiplicative group generated by the elements of S. In 1933, Mahler [START_REF] Mahler | Zur Approximation algebraischer Zahlen, I. ( Über den grössten Primteiler binärer Formen)[END_REF] proved that for all nonzero rational numbers a and b the equation

(3.2) aX + bY = 1
has only a finite number of solutions in Γ 2 . Lang [START_REF] Lang | Integral points on curves[END_REF] later generalized this result by proving that for all a and b belonging to C * and all subgroups of finite rank Γ of C * , Equation (3.2) has only a finite number of solutions in Γ 2 . Furthermore, in the case where Γ is a subgroup of Q * , there exists an effective method based on the theory of linear forms of logarithms to determine all solutions of Equation (3.2). When the number of variables d is larger than 2, one can no longer expect that Equation (3.1) necessarily has only a finite number of solutions. However, the subspace theorem can be used to prove that such an equation has only a finite number of nondegenerate solutions; that is, solutions with the property that no proper subsum vanishes [START_REF] Evertse | On sums of S-units and linear recurrences[END_REF][START_REF] Van Der Poorten | Additive relations in fields[END_REF]. Furthermore, it is possible to use some quantitative version of the subspace theorem to bound the number of nondegenerate solutions. In this direction, the following general and very strong result was obtained by Evertse, Schlickewei and W. Ṁ. Schmidt [START_REF] Evertse | Linear equations in variables which lie in a multiplicative group[END_REF]: given K a field of characteristic 0 and Γ a multiplicative subgroup of rank r of K * , Equation (3.1) has at most exp((6d) 3d (r + 1)) nondegenerate solutions. However, all general known results concerning more than two variables are ineffective.

The situation in characteristic p is similar to the one encountered with the Skolem-Mahler-Lech theorem. The Frobenius endomorphism may be responsible for the existence of "pathological solutions". Indeed, it is easy to check that, for every positive integer q that is a power of p, the pair (t q , (1t) q ) is a solution of the equation

X + Y = 1 in Γ 2
, where Γ is the multiplicative subgroup of F p (t) * generated by t and 1t. In fact, if we take K = F p (t) and Γ = t, (1t) , we can find more sophisticated examples. As observed in [START_REF] Masser | Mixing and linear equations over groups in positive characteristic[END_REF], the equation

X + Y -Z = 1
has for every pair of positive integer (n, m) the nondegenerated solution

X = t (p n -1)p m , Y = (1 -t) p n+m , Z = t (p n -1)p m (1 -t) p m .
Thus, there is no hope to obtain in this framework results similar to those mentioned previously. Concerning Equation (3.2), Voloch [START_REF] Voloch | The equation ax + by = 1 in characteristic p[END_REF] gave interesting results. He obtained, in particular, conditions that ensure the finiteness of the number of solutions (with explicit bounds for the number of solutions). Masser [START_REF] Masser | Mixing and linear equations over groups in positive characteristic[END_REF] obtained a result concerning the structure of the solutions of the general Equation (3.1). His aim was actually to prove a conjecture of K. Schmidt concerning mixing properties of algebraic Z d -actions (see [START_REF] Masser | Mixing and linear equations over groups in positive characteristic[END_REF][START_REF] Schmidt | The dynamics of algebraic Z d -actions[END_REF][START_REF] Schmidt | Mixing automorphisms of compact groups and a theorem of Schlickewei[END_REF] for more details on this problem).

As a consequence of Theorem 1.5, we are able to give a satisfactory effective solution to the general equation (3.1) over fields of positive characteristic, proving that the set of solutions is p-automatic in a natural sense. We note that the notion of an automatic subset of a finitely generated abelian group is given in Section 5 (see Definition 5.9 and Proposition 5.4).

Theorem 3.1. -Let K be a field of characteristic p, let c 1 , . . . , c d ∈ K * , and let Γ be a finitely generated multiplicative subgroup K * . Then the set of solutions in Γ d of the equation

c 1 X 1 + • • • + c d X d = 1
is a p-automatic subset of Γ d that can be effectively determined.

Proof. -Let

S := (x 1 , . . . , x d ) ∈ Γ d | c 1 x 1 + • • • + c d x d = 1 .
Our aim is to prove that S is p-automatic and can be effectively determined.

We first fix some notation. Let g 1 , . . . , g m be a set of generators of Γ and let us consider a surjective group homomorphism Φ : Z m → Γ. This allows us to define a surjective group homomorphism Φ :

(Z m ) d → Γ d by Φ(x 1 , . . . , x d ) = (Φ(x 1 ), . . . , Φ(x d )). By Proposition 5.3, it is enough to show that Φ-1 (S) is a p-automatic subset of (Z m ) d ≃ Z m×d . Let E := {±1} m . Given n := (n 1 , . . . , n m ) ∈ N m
a := (n 1 , . . . , n d ) ∈ N m×d | c 1 Φ(a 1 • n 1 ) + • • • + c d Φ(a d • n d ) = 1 . Thus (3.3) Φ-1 (S) = a∈E d a • S a .
Note that by Proposition 5.1, S is p-automatic subset of Γ d if and only if S a is a p-automatic subset of N d for every a ∈ E d .

We let t i,j be indeterminates for 1 ≤ i ≤ d and 1 ≤ j ≤ m. We define t i = (t i,1 , . . . , t i,m ) for 1 ≤ i ≤ d. Given n ∈ N m and i ∈ {1, 2, . . . , d}, we define t n i to be the product

t n 1 i,1 • • • t nm i,m . Given a := (a 1 , . . . , a d ) ∈ E d , we define the function f a (t 1 , . . . , t d ) := n 1 ,...,n d ∈N m -1 + d i=1 c i Φ(a i • n i ) t n 1 1 • • • t n d d .
This definition ensures that

(3.4) S a = Z(f a ) .
For every i ∈ {1, 2, . . . , d}, we also set n i = (n i,1 , . . . , n i,m ) and a i := (a i,1 , . . . , a i,m ). Let e j = (0, 0, . . . , 0, 1, 0 . . . , 0) ∈ Z m denote the element whose jth coordinate is 1 and whose other coordinates are 0. Then for every i ∈ {1, . . . , d}, we have

n i ∈N m c i Φ(a i • n i )t n i i = ∞ n i,1 =0 • • • ∞ n i,m =0 m j=1
Φ(e j ) a i,j n i,j t

n i,j i,j = m j=1 (1 -Φ(e j ) a i,j t i,j ) -1
is a rational function. Hence

f a (t 1 , . . . , t d ) = d i=1 m j=1 (1 -t i,j ) -1   -1 + d i=1 c i m j=1 (1 -t i,j ) (1 -Φ(e j ) a i,j t i,j )  
is a rational function for each a ∈ E d . Since we get an explicit expression for the function f a (assuming that we explicitly know a set of generators g 1 , . . . , g m of Γ), we infer from Theorem 1.5 that the set Z(f a ) is a p-automatic subset of N d which can be effectively determined. By (3.3) and (3.4), this ends the proof.

An effective result related to the Mordell-Lang theorem

The expression "Mordell-Lang theorem" or "Mordell-Lang conjecture" serves as a generic appellation which denotes results describing the structure of intersections of the form

X ∩ Γ ,
where X is a subvariety (Zariski closed subset) of a (affine, abelian, or semiabelian) variety A and Γ is a finitely generated subgroup (or even a subgroup of finite rank) of A. The case where the variety A is defined over a field of characteristic 0 has many interesting Diophantine consequences, including the famous Faltings' theorem [START_REF] Faltings | Diophantine approximation on abelian varieties[END_REF].

On the other hand, simple examples constructed using the Frobenius endomorphism (as in Section 3) show that such intersections may behave differently when the variety A is defined over a field of positive characteristic. Hrushovski [START_REF] Hrushovski | The Mordell-Lang conjecture for function fields[END_REF] proved a relative version of the Mordell-Lang conjecture for semi-abelian varieties defined over a field K of positive characteristic. His approach, which makes use of model theory, has then been pursued by several authors (see for instance [START_REF] Moosa | F -structures and integral points on semiabelian varieties over finite fields[END_REF] and [START_REF] Ghioca | The isotrivial case in the Mordell-Lang Theorem[END_REF]).

All general results known up to now in this direction seem to be ineffective. The aim of this section is to prove the two following effective statements. We recall that the notion of an automatic subset of a finitely generated abelian group is given in Section 5 (see Definition 5.9 and Proposition 5.4).

Theorem 4.1. -Let K be a field of characterisitc p and let d be a positive integer. Let X be a Zariski closed subset of GL d (K) and Γ a finitely generated abelian subgroup of GL d (K). Then the set X ∩ Γ is a p-automatic subset of Γ that can be effectively determined.

Note more generally that, given positive integers d 1 , . . . , d n , the same result holds for Zariski closed subsets of n i=1 GL d i (K). Indeed, we have a natural embedding ß of n i=1 GL d i (K) as a Zariski closed subset of GL d 1 +•••+dn (K), where ß sends an n-tuple of invertible matrices in which the ith matrix has size d i × d i to the block diagonal matrix with n blocks whose ith block is the ith coordinate of our n-tuple. Indeed, under this identification, n i=1 GL d i (K) is the zero set of the linear polynomials x i,j for which i and j have the property that there does not exist a positive integer k, k ≤ n, such that

d 0 + • • • + d k-1 < i, j ≤ d 1 + • • • + d k ,
where we take d 0 to be zero. Given a Zariski closed subset X of n i=1 GL d i (K), we thus may regard X as a Zariski closed subset of GL d 1 +•••+dn (K). We note that the additive torus embeds in GL 2 (K) by identifying the torus with unipotent upper-triangular matrices. Moreover, this is easily seen to be a Zariski closed subset of GL 2 (K). Applying these remarks with d 1 , . . . , d n ∈ {1, 2}, we deduce the following corollary.

Corollary 4.1. -Let K be a field of characterisitc p and let s and t be nonnegative integers. Let X be a subvariety of G s a (K)×G t m (K) and Γ a finitely generated subgroup of G s a (K) × G t m (K). Then the set X ∩ Γ is a p-automatic subset of Γ that can be effectively determined.

We note that one can actually obtain an ineffective version of Theorem 4.1 from Corollary 4.1. In fact, one only needs to consider multiplicative tori.

To see this, we observe that if Γ is a finitely generated abelian subgroup of GL d (K), then by considering Jordan forms, there is some natural number n such that g p n is diagonalizable for every g ∈ Γ. As commuting diagonalizable operators are simultaneously diagonalizable, we may replace K by a finite extension K ′ that contains the eigenvalues of g p n as g ranges over a generating set, and assume that Γ p n is a subgroup of

T ∼ = G d m (K ′ ), the invertible diagonal matrices in GL d (K ′ ). As X ∩ T is Zariski closed in T and X ∩ Γ p n = (X ∩ T ) ∩ Γ p n , Corollary 4.
1 applies and so Γ p n ∩ X is p-automatic. By applying a suitable translate, it follows that the intersection of X with each coset of Γ/Γ p n is p-automatic. As there are only finitely many cosets, using basic properties of automaticity, we deduce that Γ ∩ X is p-automatic.

It is however less clear whether an effective version of Theorem 4.1 can be obtained from Corollary 4.1. Indeed, to determine the intersection using the method described above in practice, one must be able to explicitly find eigenvectors in order to diagonalize elements of Γ p n . A necessary step in doing this is to find roots of characteristic polynomials in the algebraic closure of K, which seems uneasy to be done explicitly in general.

It is also natural to ask whether a similar version of Theorem 4.1 might hold for abelian varieties. We believe this to be the case, but it is not clear whether the result follows from our approach: if P is a point on an abelian variety X over a field of positive characteristic then the points n • P do not appear, in general, to be sufficiently well-behaved to allow one to associate an algebraic generating function, which is necessary to apply our methods.

Proof of Theorem 4.1. -We first make a few reductions. We let Φ : GL d (K) → A d 2 (K) be the injective morphism whose image, Y , consists of all points at which the determinant does not vanish. Note that the affine variety GL d (K) is a Zariski open subset of A d 2 (K) and that the Zariski closed subsets of GL d (K) are precisely those obtained by intersecting Zariski closed subsets of A d 2 (K) with GL d (K). By the Hilbert Basis Theorem, a Zariski closed subset of A d 2 (K) is given by the vanishing set of a finite set of polynomials. Thus there are polynomials P 1 , . . . , P r

∈ K[x 1,1 , . . . , x d,d ] such that for M ∈ GL d (K), M ∈ X ⇐⇒ P 1 (Φ(M )) = • • • = P r (Φ(M )) = 0 .
It is then enough to consider the case that Φ(X) = Z(P ) ∩ Y , where P is a single polynomial in the indeterminates x i,j with 1 ≤ i, j ≤ d and Z(P ) denotes the set of zeros of P .

Let Γ be a finitely generated abelian subgroup of GL d (K) and let X be a Zariski closed subset of GL d (K) such that Φ(X) = Z(P ) ∩ Y , where

P ∈ K[x 1,1 , . . . , x d,d ]. Our aim is to prove that X ∩ Γ is a p-automatic subset of Γ. Let C 1 , . . . , C m ∈ GL d (K) be generators of Γ and suppose that Ψ : Z m → Γ is the surjective group homomorphism defined by Ψ(e i ) = C i for 1 ≤ i ≤ m
, where e i stands for the vector whose ith coordinate is 1 and all other coordinates are 0. We let n denote an m-tuple

(n 1 , . . . , n m ) ∈ N m . By Proposition 5.3, X ∩ Γ is p-automatic if S := {n ∈ Z m | P (Φ • Ψ(n)) = 0} is a p-automatic subset of Z m . Let E := {±1} m . Given n := (n 1 , . . . , n m ) ∈ N m and a := (a 1 , . . . , a m ) ∈ E, we denote by a • n := (a 1 n 1 , . . . , a m n m ) the ordinary coordinate-wise multiplication. Given A ⊆ N m , we also set a • A := {a • n | n ∈ A}. For every a ∈ E, we set S a := {n ∈ N m | P (Φ • Ψ(a • n)) = 0} .
Note that by Proposition 5.1, S is a p-automatic subset of Z m if and only if S a is a p-automatic subset of N m for every a ∈ E.

To see this, let t j be indeterminates for 1 ≤ j ≤ m. Given n ∈ N m , we define t n to be the product

t n 1 1 • • • t nm m . Let a = (a 1 , . . . , a m ) ∈ E. We set f a (t) := n∈N m Ψ(a • n)t n ∈ GL d (K)[[t]] .
We claim that for 1 ≤ i, j ≤ d, the (i, j) entry of Ψ(a • n)t n is a rational function in t. To see this, first note that since C 1 , . . . , C m commute, we have

f a (t) = (n 1 ,...,nm)∈N m Ψ(C a 1 n 1 1 , . . . , C amnm m )t n 1 1 • • • t nm m = m i=1 n i ∈N C a i n i i t n i i .
On the other hand, for every i ∈ {1, . . . , m}, the sum

n i ∈N C a i n i i t n i i
is a d × d matrix whose entries are rational functions that belong to K(t i ). This follows for instance from Proposition 1.1 in [START_REF] Hansel | Une démonstration simple du théorème de Skolem-Mahler-Lech, Theoret[END_REF]. Since rational functions are closed under Hadamard product and taking linear combinations, we obtain that f a (t) is a d×d matrix whose entries are all multivariate rational functions in t. For all 1 ≤ i, j ≤ d, let us denote by f i,j,a (t) the (i, j) entry of f a (t). Note that the power series fa (t) :=

n∈N m P (Φ • Ψ(a • n))t n
can be obtained by taking Hadamard product and linear combinations of the rational functions f i,j,a (t). We thus deduce that fa (t) belongs to the field of multivariate rational functions K(t). On the other hand, the definition of fa implies that S a = Z( fa ) . By Theorem 1.5, we have that the set S a is a p-automatic set that can be effectively determined. Since this holds true for evey a ∈ E, this ends the proof.

Background from automata theory

We start this section with few examples of automatic sequences and automatic subsets of the natural numbers, as well as a useful chatacterization of them (Theorem 5.1). Then we describe Salon's [START_REF] Salon | Suites automatiques à multi-indices et algébricité[END_REF] extension of the notion of automatic sets to subsets of N d and show how to genralize it to subsests of Z d . Finally, we introduce a natural notion of automaticity for subsets of arbitrary finitely generated abelian groups. It seems that the latter notion has not been considered before and that it could be of independent interest. Let k ≥ 2 be a natural number. We let Σ k denote the alphabet {0, 1, . . . , k -1}.

5.1. Automatic sequences and one-dimensional automatic sets. -For reader's convenience we choose to recall here the definitions of a kautomatic sequence and a k-automatic subset of the natural numbers.

A k-automaton is a 6-tuple

A = (Q, Σ k , δ, q 0 , ∆, τ ) ,
where Q is a finite set of states, δ : Q × Σ k → Q is the transition function, q 0 is the initial state, ∆ is the output alphabet and τ : Q → ∆ is the output function. For a state q in Q and for a finite word w = w 1 w 2 • • • w n on the alphabet Σ k , we define δ(q, w) recursively by δ(q, w) = δ(δ(q, w 1 w 2 • • • w n-1 ), w n ). Let n ≥ 0 be an integer and let w r w r-1

• • • w 1 w 0 in (Σ k ) r+1 be the base-k expan- sion of n. Thus n = r i=0 w i k i := [w r w r-1 • • • w 0 ] k . We denote by w(n) the word w 0 w 1 • • • w r . A sequence (a n ) n≥0 is said to be k-automatic if there exists a k-automaton A such that a n = τ (δ(q 0 , w(n))) for all n ≥ 0. A set E ⊂ N
is said to be recognizable by a finite k-automaton, or for short k-automatic, if the characteristic sequence of E, defined by a n = 1 if n ∈ E and a n = 0 otherwise, is a k-automatic sequence.

Example 5.1. -The Thue-Morse sequence t := (t n ) n≥0 is probably the famous example of automatic sequences. It is defined as follows: t n = 0 if the sum of the binary digits of n is even, and t n = 1 otherwise. The Thue-Morse sequence can be generated by the following finite 2-automaton: Example 5.4. -In the same spirit, the set formed by taking all integers that can be expressed as the sum of at most two powers of 3 is 3-automatic. There are also much stranger automatic sets. The fact that the class of k-automatic sets is closed under various natural operations such as intersection, union and complement, can actually be used to easily construct rather sophisticated automatic sets. For instance, the set of integers whose binary expansion has an odd number of digits, does not contain three consecutive 1's, and contains an even number of two consecutive 0's is a 2-automatic set.

A = ({A, B}, {0, 1}, δ, A, {0, 1}, τ ), where δ(A, 0) = δ(B, 1) = A, δ(A, 1) = δ(B, 0) = B, τ (A) = 0 and τ (B) = 1. A/0 B/1 0 0 1 1 Figure 1.
A/0 B/1 C/1 D/0 1 1 2 0 0 0 0, 1, 2 2 1, 2
An important notion in the study of k-automatic sequences is the notion of k-kernel. Definition 5.1. -The k-kernel of a sequence a = (a n ) n≥0 is defined as the set (a

k i n+j ) n≥0 | i ≥ 0, 0 ≤ j < k i .
Example 5.5. -The 2-kernel of the Thue-Morse sequence t has only two elements t and the sequence t obtained by exchanging the symbols 0 and 1 in t.

This notion gives rise to a useful characterization of k-automatic sequences which was first proved by Eilenberg in [START_REF] Eilenberg | Automata, Languages, and Machines[END_REF].

Theorem 5.1 (Eilenberg). -A sequence is k-automatic if and only if its k-kernel is finite.
5.2. Automatic subsets of N d and multidimensional automatic sequences. -Salon [START_REF] Salon | Suites automatiques à multi-indices et algébricité[END_REF] extended the notion of automatic sets to include subsets of N d , where d ≥ 1. To do this, we consider an automaton

A = Q, Σ d k , δ, q 0 , ∆, τ ,
where Q is a finite set of states, δ : Q × Σ d k → Q is the transition function, q 0 is the initial state, ∆ is the output alphabet and τ : Q → ∆ is the output function. Just as in the one-dimensional case, for a state q in Q and for a finite word w = w 1 w 2 • • • w n on the alphabet Σ d k , we recursively define δ(q, w) by δ(q, w) = δ(δ(q, w 1 w 2 • • • w n-1 ), w n ). We call such an automaton a d-dimensional k-automaton.

We identify Σ d k * with the subset of (Σ * k ) d consisting of all d-tuples (u 1 , . . . , u d ) such that u 1 , . . . , u d all have the same length. Each nonnegative integer n can be written uniquely as

n = ∞ j=0 e j (n)k j ,
in which e j (n) ∈ {0, . . . , k -1} and e j (n) = 0 for all sufficiently large j. Given a nonzero d-tuple of nonnegative integers (n 1 , . . . , n d ), we set

h := max{j ≥ 0 | there exists some i , 1 ≤ i ≤ d, such that e j (n i ) = 0} . Furthermore, if (n 1 , . . . , n d ) = (0, . . . , 0), we set : h = 0.
We can then produce an element

w k (n 1 , . . . , n d ) := (w 1 , . . . , w d ) ∈ Σ d k *
corresponding to (n 1 , . . . , n d ) by defining

w i := e h (n i )e h-1 (n i ) • • • e 0 (n i ) .
In other words, we are taking the base-k expansions of n 1 , . . . , n r and then "padding" the expansions of each n i at the beginning with 0's if necessary to ensure that each expansion has the same length.

Example 5.6. -If d = 3 and k = 2, then we have w 2 (3, 5, 0) = (011, 101, 000). A/0 B/1 (0, 0), (1, 1) (0, 0), (1, 1) (0, 1), (1, 0) (0, 1), (1, 0)

Definition 5.2. -A map f : N d → ∆ is k-automatic if there is a d- dimensional k-automaton A = Q, Σ d k , δ, q 0 , ∆, τ such that f (n 1 , . . . , n d ) = τ (δ(q 0 , w d (n 1 , . . . , n d ))) . Similarly, a subset S of N d is k-automatic if its characteristic function, f : N d → {0, 1}, defined by f (n 1 , . . . , n d ) = 1 if (n 1 , . . . , n d ) ∈ S; and f (n 1 , . . . , n d ) = 0, otherwise, is k-automatic.
:= f (m, n), f 2 (m, n) = f (2m + 1, 2n).
Just as Eilenberg [START_REF] Eilenberg | Automata, Languages, and Machines[END_REF] showed that being k-automatic is equivalent to having a finite k-kernel for k-automatic sequences, Salon [START_REF] Salon | Suites automatiques à multi-indices et algébricité[END_REF]Theorem 1] observed that a similar characterization of multidimensional k-automatic maps holds. Given a natural number n, we let [n] k denote the base-k expansion of n. We set Σ ′ k = {0, 1, . . . , k -1, -, +} and we let L k denote the language over the alphabet Σ ′ k consisting of the empty word and all words over Σ ′ k whose length is at least 2 such that the initial letter is either + or -, the remaining letters are all in Σ k , and the last letter is not equal to zero. This is easily seen to be a regular language.

There is a bijection [ • ] k : L(k) → Z in which the empty word is sent to zero,

+s 0 • • • s n ∈ L(k) → n j=0 s j k j and -s 0 • • • s n ∈ L(k) → - n j=0 s j k j ,
where s 0 , . . . , s n ∈ {0, 1, . . . , k -1}.

Definition 5.4. -We say that a subset S of Z is k-automatic if there is a finite-state automaton that takes words over Σ ′ k as input, and has the property that a word W ∈ L k is accepted by the automaton if and only if

[W ] k ∈ S.
More generally, we can define automatic subsets of Z d , mimicking the construction of Salon [START_REF] Salon | Suites automatiques à multi-indices et algébricité[END_REF]. For a natural number d ≥ 1, we create the alphabet Σ ′ k (d) to be the alphabet (Σ ′ k ) d consisting of all d-tuples of elements of Σ ′ k . With this in mind, we construct a regular language L k (d) ⊆ (Σ ′ k (d)) * as follows. Given a nonzero integer n, we can write it uniquely as

n = ǫ ∞ j=0 e j (n)k j ,
in which ǫ ∈ {±1}, e j (n) ∈ {0, . . . , k -1} and there is some natural number N , depending on n, such that e j (n) = 0 whenever j > N . We also set 0 = + ∞ j=0 e j (0)k j , where e j (0) = 0 for all j ≥ 0. Given a nonzero d-tuple of integers (n 1 , . . . , n d ), we set h := max{j | there exists some i such that e j (n i ) = 0} .

If (n 1 , . . . , n d ) = (0, . . . , 0), we set : h = 0.

We can then produce an element

w k (n 1 , . . . , n d ) := (w 1 , . . . , w d ) ∈ Σ ′ k (d) *
corresponding to (n 1 , . . . , n d ) by defining

w i := ǫ i e h (n i )e h-1 (n i ) • • • e 0 (n i )
,

where ǫ i is + if n i is nonnegative and is -if n i < 0.
In other words, we are taking the base k-expansions of n 1 , . . . , n d and then "padding" the expansions of each n i at the beginning to ensure that each expansion has the same length.

Example 5.9.

-If d = 3 and k = 2, then we have w 3 (14, -3, 0) = (+1110, -0011, +0000).

We then take L k (d) to be the collection of words of the form

w k (n 1 , . . . , n d )
where (n 1 , . . . , n d ) ∈ Z d . Then there is an obvious way to extend the map

[•] k to a bijection [ • ] k : L k (d) → Z d ; namely, [w k (n 1 , . . . , n d )] k := (n 1 , . . . , n d ) .
We also denote by [ • ] -1 k the reciprocal map. We can now define the notion of a k-automatic function from Z d to a finite set as follows.

Definition 5.5. -Let ∆ be a finite set. A function f : Z d → ∆ is kautomatic if there is a finite automaton that takes words over L k (d) as input and has the property that reading a word W ∈ L k (d), the automaton outputs

f ([W ] k ). Similarly, a subset S of Z d is k-automatic if its characteristic function, f : Z d → {0, 1}, defined by f (n 1 , . . . , n d ) = 1 if (n 1 , . . . , n d ) ∈ S; and f (n 1 , . . . , n d ) = 0, otherwise, is k-automatic.
In fact, much as in the classical situation, automaticity of subsets of Z d can be characterized using the kernel. (i) The map f is k-automatic.

(ii) The k-kernel of f is finite. (iii) For each ǫ = (ǫ 1 , . . . , ǫ d ) ∈ {±1} d , the function f ǫ : N d → ∆ defined by (n 1 , . . . , n d ) → f (ǫ 1 n 1 , . . . , ǫ d n d ) is k-automatic in the usual sense.
Proof. -We note that by definition of automatic maps on Z d , each of the f ǫ is k-automatic in the usual sense and hence (i) implies (iii). Similarly, (iii) implies (i). Next assume that (iii) holds. Let h(n 1 , . . . ,

n d ) = f (k a n 1 + b 1 , . . . , k a n d + b d ) be a map in the kernel of f . Then for ǫ = (ǫ 1 , . . . , ǫ d ) ∈ {±1} d , the map h ǫ : N d → ∆ defined by (n 1 , . . . , n d ) → h(ǫ 1 n 1 , . . . ǫ d n d ) is of the form f (ǫ 1 k a n 1 + b 1 , . . . , ǫ d k a n d + b d ),
which is in the k-kernel of f ǫ . Since there are only finitely many ǫ = (ǫ 1 , . . . , ǫ d ) ∈ {±1} d and only finitely many elements in the kernel of f ǫ , we see that the kernel of f is finite and hence (iii) implies (ii). Similarly, (ii) implies (iii).

5.4. Automatic subsets of finitely generated abelian groups. -We introduce here a relevant notion of automaticity for subsets of arbitrary finitely generated abelian groups. In this area, we quote [START_REF] Allouche | Automatic maps in exotic numeration systems[END_REF] where the authors provide a general framework for the automaticity of maps from some semirings to finite sets. In particular, a similar notion of automaticity for subsets of Z 2 was considered in that paper.

In this more general framework, it seems more natural to define first kautomatic maps in terms of some generalized k-kernels and then to prove that such maps can be characterized in terms of finite automata.

In the rest of this section, all finitely generated abelian groups are written additively. We thus first define the k-kernel of a map from a finitely generated abelian group to a finite set. Definition 5.7. -Let Γ be a finitely generated abelian group and T = {γ 1 , . . . , γ d } a set of generators of Γ. Let ∆ be a finite set. Given a map f : Γ → ∆, we define the k-kernel of f with respect to the generating set T to be the collection of all maps from Γ to ∆ of the form

g(x) := f (k a x + b 1 γ 1 + • • • + b d γ d ) such that a ≥ 0 and 0 ≤ b 1 , . . . , b d < k a .
We can now define k-automatic maps as follows.

Definition 5.8. -Let Γ be a finitely generated abelian group and ∆ a finite set. A map f : Γ → ∆ is k-automatic if its k-kernel with respect to every finite generating set of Γ is finite.

As usual, we can use the previous definition to introduce the notion of a k-automatic subset of a finitely generated abelian group. Definition 5.9. -Let Γ be a finitely generated abelian group. A subset S of Γ is k-automatic if the map χ S : Γ → {0, 1}, defined by χ S (x) = 1 if and only if x ∈ S, is k-automatic.

We note that our definition of k-automaticity appears to be somewhat difficult to verify, as we must check that the k-kernel is finite with respect to every finite generating set. As shown below, it actually suffices to check that the k-kernel is finite with respect to just anyone generating set. Proposition 5.2. -Let Γ be a finitely generated abelian group and ∆ a finite set. Let us assume that the map f : Γ → ∆ has a finite k-kernel with respect to some generating set of Γ. Then the map f is k-automatic.

Proof. -Suppose that the k-kernel of f is finite with respect to the generating set T := {γ 1 , . . . , γ d } of Γ and let f 1 , . . . , f m denote the distinct maps in the k-kernel of f .

Given another generating set of Γ, say T ′ := {δ 1 , . . . , δ e }, we have to show that the k-kernel of f with respect to T ′ is also finite.

There exist integers c i,j with 1 ≤ i ≤ d and 1 ≤ j ≤ e such that

δ j = d i=1 c i,j γ i
for j ∈ {1, . . . , e}. Set N := i,j |c i,j |. Given an integer i, 1 ≤ i ≤ m, and a d-tuple of integers j = (j 1 , . . . , j d ), we define the map g i,j from Γ to ∆ by

g i,j (x) := f i (x + j 1 γ 1 + • • • + j d γ d )
for all x ∈ Γ. We claim that the k-kernel of f with respect to T ′ is contained in the finite set S defined by

S := g i,j : Γ → ∆ | j = (j 1 , . . . , j d ) ∈ {-N, -N + 1, . . . , N } d , i ∈ {1, . . . , m} .
To see this, note that if a ≥ 0 and 0 ≤ b 1 , . . . , b d < k a , then

b 1 δ 1 + • • • + b e δ e = b ′ 1 γ 1 + • • • + b ′ d γ d , where b ′ i = e j=1
b j c i,j . It follows that

|b ′ i | ≤ N (k a -1) for every i, 1 ≤ i ≤ d. We can thus write b ′ i = k a m i + r i with |m i | < N and 0 ≤ r i < k a . This implies that f (k a x + b 1 δ 1 + • • • + b e δ e ) = f (k a x + b ′ 1 γ 1 + • • • + b ′ d γ d ) = f (k a (x + m 1 γ 1 + • • • + m d γ d ) +r 1 γ 1 + • • • + r d γ d ) = f ℓ (x + m 1 γ 1 + • • • + m d γ d ) for some ℓ, 1 ≤ ℓ ≤ m. Thus we see that f (k a x + b 1 δ 1 + • • • + b e δ e ) = g ℓ,m (x)
where m := (m 1 , . . . , m d ), which proves that the k-kernel of f with respect to the generating set T ′ is included in the finite set S, as claimed.

Proposition 5.3. -Let Γ 1 and Γ 2 be two finitely generated abelian groups, and Φ :

Γ 1 → Γ 2 a surjective group homomorphism. If S is a k-automatic subset of Γ 2 then Φ -1 (S) is a k-automatic subset of Γ 1 .
Proof. -Let f and g denote respectively the characteristic function of Φ -1 (S) and S. Let {γ 1 , . . . , γ d } be a set of generators of Γ 1 . Then if a ≥ 0 and 0 ≤ b 1 , . . . , b d < k a , we infer from the definition of f that

f (k a x + b 1 γ 1 + • • • + b d γ d ) = 1 ⇐⇒ Φ(k a x + b 1 γ 1 + • • • + b d γ d ) ∈ S ,
which occurs if and only if

g k a Φ(x) + d i=1 b i Φ(γ i ) = 1 .

Note that

T := {Φ(γ i ) : 1 ≤ i ≤ d}
is a set of generators of Γ 2 since Φ is surjective. Since, by assumption, g is k-automatic, the k-kernel of g is finite with respect to T . Thus the k-kernel of f is finite with respect to T ′ := {γ 1 , . . . , γ d }. The result now follows from Proposition 5.2.

We can now prove, as we may expect, that a k-automatic subset of a finitely generated abelian group can be described by a finite automaton.

n 1 γ 1 + • • • + n d γ d belongs to S.
Proof. -For every integer i, 1 ≤ i ≤ d, we denote by e i := (0, 0, ..., 0, 1, 0..., 0) the element of Z d whose jth coordinate is 1 and whose other coordinates are 0. Let Φ be the surjective group homomorphism from Z d to Γ defined by Φ(e i ) = γ i for every integer i,

1 ≤ i ≤ d.
If S is k-automatic then, by Proposition 5.3, Φ -1 (S) is a k-automatic subset of Z d . By Definition 5.5, there is a finite automaton that takes words over L k (d) as input and has the property that the word W ∈ L k (d) is accepted by the automaton if and only if [W ] k belongs to Φ -1 (S). Thus for every d-tuple of integers (n 1 , . . . , n d ) the word [(n 1 , . . . , n

d )] -1 k ∈ L k (d)

is accepted by this automaton if and only if n

1 γ 1 + • • • + n d γ d belongs to S.
On the other hand, if there exists a finite automaton such that for every d-tuple of integers (n 1 , . . . , n d ) the word [(n 1 , . . . , n

d )] -1 k ∈ L k (d) is accepted by this automaton if and only if n 1 γ 1 + • • • + n d γ d belongs to S.
The same automaton can also be used to recognize Φ -1 (S). Thus Φ -1 (S) is a k-automatic subset of Z d . By Proposition 5.1, the set Φ -1 (S) has a finite k-kernel and it follows that S has a finite k-kernel with respect to {γ 1 , . . . , γ d }. By Proposition 5.2, S is thus a k-automatic subset of Γ.

Proof of our main result

Our aim is to prove Theorem 1.4. Throughout this section, we take d to be a natural number. We let n and j denote respectively the d-tuple of natural numbers (n 1 , . . . , n d ) and (j 1 , . . . , j d ). We will also let t n denote the monomial

t n 1 1 • • • t n d d in
(t) ∈ K[[t]] is algebraic if it is algebraic over the field of rational functions K(t), that is, if there exist polynomials A 0 , . . . , A m ∈ K[t], not all zero, such that m i=0 A i (t)f (t) i = 0 .
In order to prove Theorem 1.4 we need to introduce some notation. For each j = (j 1 , . . . , j d ) ∈ {0, 1, . . . , p -1} d , we define e j : N d → N d by (6.5) e j (n 1 , . . . , n d ) := (pn 1 + j 1 , . . . , pn d + j d ) .

We let Σ denote the semigroup generated by the collection of all e j under composition. In view of Definition 5.3, this semigroup is intimately related to the definition of the p-kernel of d-dimensional maps. As a direct consequence of Theorem 5.2, we make the following remark which underlines the important role that will be played by the semigroup Σ in the proof of Theorem 1.4. We recall that a field K of characteristic p > 0 is perfect if the map x → x p is surjective on K. Let p be a prime number and let K be a perfect field of characteristic p. For every j ∈ Σ d p = {0, 1, . . . , p -1} d , we define the so-called Cartier operator

E j from K[[t]] into itself by (6.6) E j (f (t)) := n∈N d (a • e j (n)) 1/p t n where f (t) := n∈N d a(n)t n ∈ K[[t]
]. Then we have the following useful decomposition:

(6.7) f = j∈Σ d p t j E j (f ) p .
We now recall the following simple classical result, usually known as Ore's lemma.

Lemma 6.1. -Let f (t) ∈ K[[t]
] be a nonzero algebraic power series. Then there exists a positive integer r and polynomials P 0 , . . . , P r in K[t] such that r i=0

P i f p i = 0 and P 0 = 0. Proof. -Since f is algebraic, f, f p , f p 2 , . . .

is linearly dependent over K(t).

There thus exists a natural number r and polynomials P 0 , . . . , P r in K[t] such that r i=0

P i f p i = 0 .
It remains to prove that one can choose P 0 = 0. Let k be the smallest nonnegative integer such that f satisfies a relation of this type with P k = 0. We shall prove that k = 0 which will end the proof. We assume that k > 0 and we argue by contradiction. Since P k = 0, we infer from Equality (6.7) that there exists a d-tuple j ∈ Σ d p such that E j (P k ) = 0. Since r i=k P i f p i = 0, we have

E j r i=k P i f p i = r i=k E j P i f p i = r i=k E j (P i ) f p i-1 = 0 .
We thus obtain a new relation of the same type but for which the coefficient of f p k-1 is nonzero. This provides a contradiction with the definition of k.

We now let Ω denote the semigroup generated by the collection of the Cartier operators E j and the identity operator under composition. We let Ω(f ) denote the orbit of f under the action of Ω, that is,

Ω(f ) := {E(f ) | E ∈ Ω} .
As in the work of Harase [START_REF] Harase | Algebraic elements in formal power series rings[END_REF] and of Sharif and Woodcock [START_REF] Sharif | Algebraic functions over a field of positive characteristic and Hadamard products[END_REF], the K-vector space spanned by Ω(f ) will play an important role. We will in particular need the following auxiliary result based on Ore's lemma. Lemma 6.2. -Let K be a perfect field of characteristic p, and let

f (t) := n∈N d a(n)x n ∈ K[[t]]
be a nonzero algebraic function over K(t). Then there exists a natural number m and there exist maps a 1 , . . . , a m : N d → K with the following properties.

(i) The formal power series

f i (t) := n∈N d a i (n)t n , 1 ≤ i ≤ m, form a basis of the K-vector space spanned by Ω(f ). (ii) One has f 1 = f . (iii) Let g(t) := n∈N d b(n)t n be a power series that belongs to Ω(f ). Then b • e j ∈ K a p 1 + • • • + K a p m for every j ∈ {0, . . . , p -1} d . Proof. -Let f (t) ∈ K[[t]
] be a nonzero algebraic power series. By Lemma 6.1, there exist a positive integer r and polynomials P 0 , . . . , P r in K[t] such that r i=0 P i f p i = 0 and P 0 = 0. Set f := P -1 0 f . Then

(6.8) f = r i=1 Q i f p i ,
where

Q i = -P i P p i -2 0
. Set M := max{deg P 0 , deg Q i | 1 ≤ i ≤ r} and (6.9)

H := h ∈ K((t)) | h = r i=0 R i f p i such that R i ∈ K[t] and deg R i ≤ M .
We first note that f belongs to H since f = P 0 f and deg P 0 ≤ M . We also observe that H is closed under the action of Ω. Indeed, if h := r i=0 R i f p i ∈ H and j ∈ {0, . . . , p -1} d , then

E j (h) = E j R 0 f + r i=1 R i f p i = E j r i=1 (R 0 Q i + R i ) f p i = r i=1 E j (R 0 f + R i ) f p i-1 ,
and since deg(R

0 Q i + R i ) ≤ 2M , we have deg E j (R 0 Q i + R i ) ≤ 2M/p ≤ M .
It follows that the K-vector space spanned by Ω(f ) is contained in H and thus has finite dimension, say m. We can thus pick maps a 1 , . . . , a m : N d → K such that the m power series f i (t) := n∈N d a i (n)t n form a basis of Ω(f ). Furthermore, since by assumption f is a nonzero power series, we can chose f 1 = f . Let b : N d → K be such that g(t) := n∈N d b(n)t n belongs to Ω(f ). Observe that the power series g can be decomposed as (6.10)

g(t) = j∈{0,...,p-1} d t j E j (g(t)) p .
By assumption, E j (g(t)

) ∈ K f 1 (t) + • • • + K f m (t) and hence E j (g(t)) p ∈ K f 1 (t) p +• • •+K f m (t) p . Let j ∈ {0, 1, . . . , p-1} d .
Considering the coefficient of t pn+j in Equation (6.10), we see that b • e j (n) is equal to the coefficient of

t pn in E j (g(t)) p , which belongs to K a 1 (n) p + • • • + K a m (n) p .
This concludes the proof.

We will also need the following lemma that says we will only have to work with finitely generated extensions of the prime field instead of general fields of characteristic p. Lemma 6.3. -Let f 1 , . . . , f m be power series as in Lemma 6.2. Then there is a finitely generated field extension K 0 of F p such that all coefficients of the power series f 1 , . . . , f m belong to K 0 .

Proof. -Let f := n∈N d ã(n)t n be defined as in Equation (6.8), that is,

(6.11) f = r i=1 Q i f p i ,
Let also H be the K-vector space defined as in Equation (6.9), that is, (6.12)

H = h ∈ K((t)) | h = r i=0 R i f p i such that R i ∈ K[t] and deg R i ≤ M .
Since H contains the K-vector space spanned by Ω(f ), the power series f 1 , . . . , f m belong to H. There thus exist a finite number of polynomials R i,k such that

f k = r i=0 R i,k f p i .
It thus remains to prove that there exists a finitely generated field extension K 0 of F p such that all coefficients of f belong to K 0 . Indeed, by adding to K 0 all the coefficients of the polynomials R i,k , we would obtain a finitely generated field extension K 1 of F p such that all coefficients of the power series f 1 , . . . , f m belong to K 1 . Given a d-tuple n = (n 1 , . . . , n d ), we set n := max(n 1 , . . . , n d ). Let N be a positive integer. We let K 0 be the finitely generated extension of F p generated by the coefficients of Q 1 , . . . , Q r and the collection of coefficients of t n in f (t) with n ≤ N . We claim that the coefficients of f all lie in K 0 .

We prove by induction on n that all coefficients ã(n) belongs to K 0 . By construction, this holds whenever n ≤ N .

Suppose that the claim holds whenever n < M for some M > N and let us assume that n = M . Then if we consider the coefficient of t n 1 1 • • • t n d d in both sides of Equation 6.11, we get that

ã(n 1 , . . . , n d ) ∈ r i=1 (m 1 ,...,m d )∈S K 0 ã(m 1 , . . . , m d ) p i ,
where S is the (possibly empty) set of all d-tuples m := (m 1 , . . . , m d ) ∈ N d such that either m i = 0 or m i < n i for each i ∈ {1, . . . , d}. Since M > 0, we get that m < M and the inductive hypothesis implies that

r i=1 (m 1 ,...,m d )∈S K 0 ã(m 1 , . . . , m d ) p i ⊆ K 0 ,
and so ã(n 1 , . . . , n d ) ∈ K 0 . This completes the induction and shows that all coefficients of f lie in K 0 .

Before proving Theorem 1.4, we first fix a few notions. Given a finitely generated field extension K 0 of F p , we let K p 0 denote the subfield consisting of all elements of the form x p with x ∈ K 0 . Given F p -vector subspaces U and V of K 0 we let V U denote the F p -subspace of K 0 spanned by all products of the form vu with v ∈ V, u ∈ U . We let V p denote the F p -vector subspace consisting of all elements of the form v p with v ∈ V . We note that since K 0 is a finitely generated field extension of F p , K 0 is a finite-dimensional K p 0 -vector space. If we fix a basis

K 0 = r i=1 K p 0 h i then we have projections π 1 , . . . , π r : K 0 → K 0 defined by (6.13) x = r i=1 π i (x) p h i . Remark 6.2.
-For 1 ≤ i ≤ r and x, y, z ∈ K 0 we have

π i (x p y + z) = xπ i (y) + π i (z) .
The last ingredient we have to state before proving Theorem 1.4 is a rather technical result, but very useful, due to Derksen, which we state here without proof. It corresponds to Proposition 5.2 in [START_REF] Derksen | A Skolem-Mahler-Lech theorem in positive characteristic and finite automata[END_REF]. Basically, we will prove an effective version of this result later in Section 8 (step 2 in the proof of Theorem 1.5). Proposition 6.1 (Derksen). -Let K 0 be a finitely generated field extension of F p and let π 1 , . . . , π r : K 0 → K 0 be as in Equation (6.13). If U is a finite-dimensional F p -vector subspace of K 0 . Then there exists a finitedimensional F p -vector subspace V of K 0 containing U such that

π i (V U ) ⊆ V for all i such that 1 ≤ i ≤ r.
We are now ready to prove Theorem 1.4.

Proof of Theorem 1.4. -By enlarging K if necessary, we may assume that K is perfect. By Lemma 6.2 we can find maps a 1 , . . . , a m : N d → K with the following properties.

(i) The power series

f i (t) := n∈N d a i (n)t n , 1 ≤ i ≤ m, form a basis of the K-vector space spanned by Ω(f ). (ii) One has f 1 = f . (iii) Let g(t) := n∈N d b(n)t n be a power series that belongs to Ω(f ). Then b • e j ∈ K a p 1 + • • • + K a p m for every j ∈ {0, . . . , p -1} d . In particular, given 1 ≤ i ≤ m and j ∈ {0, 1, . . . , p -1} d , there are elements λ(i, j, k), 1 ≤ k ≤ m, such that (6.14) a i • e j = m k=1 λ(i, j, k)a p k .
Furthermore, by Lemma 6.3, there exists a finitely generated field extension of F p such that all coefficients of f 1 , . . . , f m are contained in this field extension. It follows that the subfield K 0 of K generated by the coefficients of f 1 (t), . . . , f m (t) and all the elements λ(i, j, k) is a finitely generated field extension of F p . Since K 0 is a finite-dimensional K p 0 -vector space, we can fix a basis {h 1 , . . . , h r } of K 0 , that is,

K 0 = r i=1 K p 0 h i .
As already mentioned, we have projections π 1 , . . . , π r : K 0 → K 0 defined by (6.15)

x = r i=1 π i (x) p h i .
We let U denote the finite-dimensional F p -vector subspace of K 0 spanned by the elements λ(i, j, k), 1 ≤ i, k ≤ m and j ∈ {0, 1, . . . , p -1} d , and by 1. By Equation (6.14), we have (6.16)

a i • e j ∈ U a p 1 + • • • + U a p m ,
for 1 ≤ i ≤ m and j ∈ {0, 1, . . . , p-1} d . By Proposition 6.1 there exists a finitedimensional

F p -vector subspace V of K 0 containing U such that π i (V U ) ⊆ V for 1 ≤ i ≤ r.
We now set

W := V a 1 + • • • + V a m ⊆ {b | b : N d → K 0 } .
We note that since V is a finite-dimensional F p -vector space, it is a finite set.

It follows that W is also a finite set since Card W ≤ ( Card V ) d < ∞. Note also that if ℓ ∈ {1, . . . , r}, i ∈ {1, . . . , m}, and j ∈ {0, 1, . . . , p -1} d then by Equation (6.16) and Remark 6.2 we have

π ℓ (V a i • e j ) ⊆ π ℓ (V U a p 1 + • • • + V U a p m ) ⊆ π ℓ (V U )a 1 + • • • + π ℓ (V U )a m ⊆ V a 1 + • • • + V a m .
By Remark 6.2, we obtain that (6.17)

b ℓ := π ℓ (b • e j ) ∈ W
for all b ∈ W , j ∈ {0, 1, . . . , p -1} d , and 1 ≤ ℓ ≤ r. Since {h 1 , . . . , h r } form a basis of K 0 as a K p 0 -vector space, given x in K 0 , we have x = 0 ⇐⇒ (π ℓ (x) = 0 for all 1 ≤ ℓ ≤ r) .

In particular, (6.18) b(pn

+ j) = 0 ⇐⇒ b 1 (n) = b 2 (n) = • • • = b r (n) = 0 .
Given a map b : N d → K 0 , we define the map χ b :

N d → {0, 1} by (6.19) χ b (n) = 0 if b(n) = 0 1 if b(n) = 0 .
Then we set

X := {χ b 1 • • • χ bt | t ≥ 0, b 1 , . . . , b t ∈ W } . We first get from Equation (6.18) that (χ b • e j )(n) = r ℓ=1 χ b ℓ (n) .
Furthermore, we infer from Equation 6.17 that b ℓ ∈ W for all b ∈ W , j ∈ {0, 1, . . . , p -1} d , and 1 ≤ ℓ ≤ r. The definition of X then implies that χ b • e j belongs to X. More generally, it follows that

(6.20) ∀χ ∈ X, ∀e ∈ Σ, χ • e ∈ X .
We note that by (6.19) we have χ 2 b = χ b for all b ∈ W . Since W is a finite set, it follows that the set X is also finite. It thus follows from (6.20) and Remark 6.1 that all maps χ in X are p-automatic. In particular, since by assumption a(n) = a 1 (n) ∈ W , we deduce that the map χ a is p-automatic. It follows that the set

Z(f ) = n ∈ N d | a(n) = 0
is a p-automatic set, which ends the proof.

Finite automata and effectivity

In this section, we define a classical measure of complexity for p-automatic sets and we show how it can be used to prove effective results concerning such sets. We follow the presentation of [START_REF] Derksen | A Skolem-Mahler-Lech theorem in positive characteristic and finite automata[END_REF]. The aim of this section is to state and prove the following result. Suppose also that for every positive integer n one can compute (in a finite amount of time) all the elements s ∈ S such that s ≤ n. Then the set S can be effectively determined. Furthermore, the following properties are decidable.

(i) the set S is empty.

(ii) the set S is finite.

(iii) the set S is periodic, that is, formed by the union of a finite set and of a finite number of (p-dimensional) arithmetic progressions.

In particular, when S is finite, one can find (in a finite amount of time) all its elements.

Remark 7.1. -When we say that the set S can be effectively determined, this means that there is an algorithm that produces in a finite amount of time a p-automaton that generates S. The format of the output is thus a 6-tuple Q, Σ d p , δ, q 0 , {0, 1}, τ , where Q the set of states, δ : Q × Σ d k → Q is the transition function, q 0 is the initial state, and τ : Q → {0, 1} is the output function. Furthermore, there exists an algorithm that allows one to determine in a finite amount of time whether S is empty, finite or whether S is formed by the union of a finite set and of a finite number of (p-dimensional) arithmetic progressions. This shows, using (i), that one can check whether Equality (7.21) is satisfied in a finite amount of time.

(iii). We have already shown that we can explitly determine a p-automaton that recognized S, since the p-complexity of S is at most N (S). Then a classical result of Honkala [START_REF] Honkala | A decision method for the recognizability of sets defined by number systems[END_REF] shows that one can check whether such set is periodic, that is, whether S is the union of a finite set and a finite number of (p-dimensional) arithmetic progressions.

Finally, to obtain all the elements of S when S is finite one can proceed as follows. First, one can check that S is finite as in (ii). Once this has been done, one knows that S is finite and thus Lemma 7.4 implies that

S = S ∩ n ∈ N d | n ≤ p N (S) 2 -2
since S has complexity at most N (S). By assumption, all the elements of S can thus be determined in a finite amount of time. This ends the proof.

Proof of Theorem 1.5

The aim of this section is to show how each step of the proof of Theorem 1.4 can be made effective.

We first recall some notation. Given a polynomial P (X) ∈ K[t][X], we define the height of P as the maximum of the degrees of the coefficient of P . The (naive) height of an algebraic power series

f (t) = n∈N a(n)t n ∈ K[[t]]
is then defined as the height of the minimal polynomial of f , or equivalently, as the minimum of the heights of the nonzero polynomials P (X) ∈ K[t][X] that vanishes at f . We first prove the following effective version of Ore's lemma. Lemma 8.1. -Let s and H be two positive integers and let f (t) ∈ K[[t]] be an algebraic power series of degree at most s and height at most H. Then there exist polynomials Q 0 , . . . , Q s ∈ K[t] with degree at most Hsp s such that

s i=0 Q i (t)f (t) p i = 0 and Q 0 = 0.
In order to prove Lemma 8.1, we will need the following auxiliary result. Lemma 8.2. -Let s be a natural number and let V 0 , . . . , V s be s + 1 vectors in K[t] s such that each coordinate has degree at most r. Then there exist Q 0 (t), . . . , Q s (t) in K[t] of degree at most rs, not all of which are zero, such that

s i=0 Q i V i = 0 .
Proof. -Let e denote the size of a maximally linearly independent subset of V 0 , . . . , V s . By relabelling if necessary, we may assume that V 0 , . . . , V e-1 are linearly independent. Let A denote the s × e matrix whose (j + 1)th column is V j . Then by reordering the coordinates of our vectors if necessary, we may assume that the e × e submatrix B of A obtained by deleting the bottom de rows of A is invertible. Let V ′ s denote the vector in K[t] e obtained by deleting the bottom de coordinates of V s . Then there is a unique vector X that is solution to the matrix equation

BX = V ′
s . Moreover, by Cramer's rule, the ith coordinate of X is the polynomial X i defined by

X i (t) := det(B i )/ det(B) ,
where B i is the e × e matrix obtained by replacing the ith column of B by V ′ s . For 0 ≤ i ≤ e -1, we set

Q i (t) := -det(B i ) .
We also set Q s (t) := det(B) .

Since the entries of B i and B are all polynomials of degree at most r, we obtain that these polynomials have degree at most re ≤ rs. Furthermore, by construction e-1 i=0

X i V i = V s .
Letting Q i (t) = 0 for e ≤ i < s, we obtain that

s i=0 Q i V i = 0
and each Q i has degree at most rs, as required.

We are now ready to prove Lemma 8.1.

Proof of Lemma 8.1. -By assumption, there exist polynomials P 0 (t), . . . , P s (t) ∈ K[t] of degree at most H such that s i=0 P i (t)f (t) i = 0 and P s (t) = 0. Let V denote the K(t)-vector space spanned by 1, f, . . . , f s-1 . For 1 ≤ i ≤ s, let e i denote the standard unit d × 1 vector in K(t) s whose jth coordinate is equal to the Kronecker delta δ ij . Then we have a surjective linear map T : K(t) s → V in which we send the vector e i to f i-1 . Let V = s i=1 T (e i )e i ∈ K(t) s and let

M :=          0 0 0 • • • 0 -X 0 (t) 1 0 0 • • • 0 -X 1 (t) 0 1 0 • • • 0 -X 2 (t) . . . . . . . . . . . . • • • . . . 0 • • • 0 1 0 -X s-2 (t) 0 0 • • • 0 1 -X s-1 (t)          ∈ M s (K(t)) ,
where X i (t) := P i (t)/P s (t) for i = 0, 1, . . . , s -1. Then

T (M n e 1 ) = f (t) n .
Notice that M n = P s (t) -n C n where C n is a matrix in M s (K[t]) whose entries have degree at most nH. Then to find a relation of the form

s i=0 Q i (t)f (t) p i = 0 ,
it is enough to find a vector

[Q 0 (t), . . . , Q s (t)] ∈ K[t] 1×d such that (8.22) P s (t) p s Q 0 (t)e 1 + P s (t) p s -p Q 1 (t)C p e 1 + • • • + Q s (t)C p s e 1 = 0 .
For 0 ≤ j ≤ s, we set (8.23)

V j := P s (t) p s -p j C p j e 1 .
We note that V j is a vector in K[t] s such that each coordinate has degree at most Hp s . Then Lemma 8.2 ensures the existence of polynomials Q 0 (t), . . . , Q s (t) in K[t] of degree at most sHp s , not all of which are 0, and such that s j=0

Q j V j = 0 .
We deduce from Equations (8.22) and (8.23) that (8.24)

s j=0 Q j (t)f p j (t) = 0 .
It thus remains to show that we can choose our polynomials Q 0 , . . . , Q s such that Q 0 is nonzero. To see this, we let k denote the smallest index such that we have a relation of the form given in Equation (8.24) with the degrees of Q 0 , . . . , Q s all bounded above by sHp s and such that Q k is nonzero. If k is equal to zero, we are done.

We now assume that k > 0 and we argue by contradiction. Since Q k = 0, we infer from Equality (6.7) that there exists a d-tuple j ∈ Σ d p such that

E j (Q k ) = 0. Since s i=k Q i f p i = 0, we have E j s i=k Q i f p i = s i=k E j Q i f p i = s i=k E j (Q i ) f p i-1 = 0 .
Furthermore, one can observe that, for k ≤ i ≤ s, the polynomial E j (Q i ) has degree at most sHp s . We thus obtain a new relation of the same type but for which the coefficient of f p k-1 is nonzero, which contradicts the minimality of k. This ends the proof.

We are now ready to prove Theorem 1.5.

Proof of Theorem 1.5. -We first explain our strategy. We assume that

f (t) ∈ K[[t]
] is an algebraic function and that we know an explicit polynomial P (X) ∈ K[t][X] that vanishes at f . Note that from the equation P (f ) = 0, one can obviously derive explicit effective bounds of the degree and of the height of f . Then we will show how the proof of Theorem 1.4 allows us to derive an effective upper bound for comp p (Z(f )). It will thus follows from the results of Section 7 that one can effectively determined the set Z(f ) only by looking at the first coefficients of f (which can be computed in a finite amount of time by using the equation P (f ) = 0).

Let us assume that the degree of f is bounded by s and that the height of f is bounded by H. In order to get an effective upper bound for comp p (Z(f )), we have to give effective upper bounds for the cardinality of the sets U, V, W and X introduced all along the proof of Theorem 1.4.

Step 1. In this first step we show how to obtain an effective upper bound for the dimension m of the K-vector space spanned by Ω(f ). We then deduce an effective upper bound for the cardinality of the F p -vector space U .

This can be deduced from our effective version of Ore's lemma. Indeed, by Lemma 6.1, one can find polynomials Q 0 , . . . , Q s ∈ K[t] with degree at most

Hsp s such that s i=0 Q i (t)f (t) p i = 0 and Q 0 = 0. We set f := Q -1 0 f . Then (8.25) f = s i=1 R i f p i ,
where

R i = -Q i Q p i -2 0
. Then each R i has degree at most Hsp s (p i -1). Set M := Hsp s (p s -1) and (8.26)

H := h ∈ K((t)) | h = s i=0 S i f p i such that S i ∈ K[t] and deg S i ≤ M .
Furthermore, H is a K-vector space of dimension at most

(s + 1) M + d M .
Just as in the proof of Lemma 6.2, one can check that f belongs to H and that H is closed under the action of Ω. It follows that the K-vector space spanned by Ω(f ) is contained in H. There thus exists an effective constant N 0 := (s + 1) M +d M such that the K-vector space spanned by Ω(f ) has dimension (8.27) m ≤ N 0 .

We recall that K 0 denotes the subfield of K generated by the coefficients of f 1 . . . , f m and all the elements λ(i, j, k) 1 ≤ i, k ≤ m and j ∈ {0, 1, . . . , p -1} d , and that U is defined as the finite-dimensional F p -vector subspace of K 0 spanned by the elements λ(i, j, k), 1 ≤ i, k ≤ m and j ∈ {0, 1, . . . , p -1} d , and by 1. We thus deduce from (8.27) that there exist an effective upper bound

N 1 := p 1+p d N 2 0 such that (8.28) Card(U ) ≤ N 1 .
Step 2. From Derksen's proposition (Proposition 6.1), we know that there exists a finite-dimensional

F p -vector subspace V of K 0 containing U such that π i (V U ) ⊆ V for 1 ≤ i ≤ r.
In this second step, we show how to obtain an effective upper bound for the cardinality of such a vector space V .

In the proof of Lemma 6.3, we have shown that K 0 is a finitely generated field extension of F p that can be generated by the λ(i, j, k) and the coefficients of a finite number of some explicit polynomials. We write

K 0 = F p (X 1 , . . . , X r )(a 1 , . . . , a s ) ,
where X 1 , . . . , X r are algebraically independent over F p and a 1 , . . . , a s form a basis for K 0 as an F p (X 1 , . . . , X r )-vector space; moreover, we may assume that for each i and j, we have a i a j is an F p (X 1 , . . . , X r )-linear combination of a 1 , . . . , a s in which the numerators and denominators of the coefficients are polynomials in F p [X 1 , . . . , X r ] whose degrees are uniformly bounded by some explicit constant N 2 .

Let T 1 , . . . , T n denote such a set of generators of K 0 with the following properties.

(i) T i = X i for i ≤ r.

(ii) T r+j = a j for j ≤ s.

(iii) T n = 1.

(iv) {T 1 , . . . , T n } contains all the λ(i, j, k). Note that from Step 1 and the proof of Lemma 6.3 we can obtain an explicit upper bound for the integer n.

An easy induction shows that for 1 ≤ j ≤ s, a p j is an F p (X 1 , . . . , X r )-linear combination of a 1 , . . . , a s in which the coefficients are rational functions whose numerators and denominators have degrees uniformly bounded by (8.29)

N 3 := N 2 2s p-2 + s p-2 -s s -1 .
We now regard K 0 as an s-dimensional F p (X 1 , . . . , X r )-vector space. Then we may regard the F p (X 1 , . . . , X r )-span of a p 1 , . . . , a p s as a subspace of F p (X 1 , . . . , X r ) s spanned by s vectors whose coordinates are rational functions whose numerators and denominators have degrees uniformly bounded by N 3 . We can effectively compute the dimension of this space and a basis. We let t denote the dimension of this vector space and by relabelling if necessary, we may assume that a p 1 , . . . , a p t form a basis. Then there exist ℓ 1 , . . . , ℓ s-t such that {a p 1 , . . . , a p t , a ℓ 1 , . . . , a ℓ s-t } forms a basis for K 0 as a F p (X 1 , . . . , X r )vector space. Moreover, using Cramer's rule, we can express each a j as a F p (X 1 , . . . , X r )-linear combination of a p 1 , . . . , a p t , a ℓ 1 , . . . , a ℓ s-t in which the numerators and denominators have degrees uniformly bounded by (8.30) N 4 := 2N 3 st .

To see this, let φ : K 0 → F p (X 1 , . . . , X r ) s be the F p (X 1 , . . . , X r )-linear isomorphism which sends a i to the vector with a 1 in the ith coordinate and zeros in all other coordinates. Let A denote the s × s matrix whose ith row is equal to φ(a p i ) for i ≤ t and is equal to φ(a ℓ t-i ) for i > t. Then the entries of A are rational functions whose numerators and denominators have degrees that are uniformly bounded by N 3 . Note that expressing a j as a F p (X 1 , . . . , X r )linear combination of a p 1 , . . . , a p t , a ℓ 1 , . . . , a ℓ t-s is the same as solving the matrix equation

Ax = e j ,
where e j is the vector whose jth coordinate is 1 and whose other coordinates are 0. By Cramer's rule, the ith coordinate of x is a ratio of two s × s determinants, each of which have entries which are rational functions in F p (X 1 , . . . , X r ) whose numerators and denominators have degrees that are uniformly bounded by N 3 , and such that the bottom st rows consist of constants. Note that the determinant of an s × s matrix whose entries are rational functions is a rational function; moreover, we can take the denominator to be the product of the denominators of the entries. Since our matrices have a total of st entries which are not constant, we obtain a bound of N 3 st for the degrees of the denominators of our determinants. It is easy to check that this bound applies to the degrees of the numerators as well. When we take a ratio of these determinants, this can at most double this bound on the degrees of the numerators and denominators. Thus we can express each a j as a F p (X 1 , . . . , X r )-linear combination of a p 1 , . . . , a p t , a ℓ 1 , . . . , a ℓ t-s in which the degrees of the numerators and denominators are uniformly bounded by 2N 3 st, as claimed.

Notice that

S := T i 1 1 • • • T in n | 0 ≤ i 1 , . . . , i n < p
spans K 0 as a K p 0 -vector space. Observe also that every polynomial Q ∈ F p [T 1 , . . . , T n ] can be decomposed as

(8.31) Q = f ∈S Q p f f ,
where the Q f are polynomials in F p [T 1 , . . . , T n ] of degree at most ⌊deg Q/p⌋. Let us choose S 0 to be the subset of S corresponding to the monomials from the set formed by the union of

X i 1 1 • • • X ir r | 0 ≤ i 1 , . . . , i r < p and X i 1 1 • • • X ir r a ℓ j | 0 ≤ i 1 , . . . , i r < p, 1 ≤ j ≤ s -t .
Then S 0 is a basis for K 0 as a K p 0 -vector space. Thus for T

i 1 1 • • • T in n ∈ S, we have T i 1 1 • • • T in n = h∈S 0 α p h,i 1 ,...,in h
for some coefficients α h,i 1 ,...,in ∈ K 0 . We may pick some nonzero polynomial H(T 1 , . . . , T n ) such that (8.32)

H(T 1 , . . . , T n ) p T i 1 1 • • • T in n = h∈S 0 A p h,i 1 ,...,in h , where A h,i 1 ,...,in ∈ F p [T 1 , . . . , T n ] for all (h, i 1 , . . . , i n ) ∈ S 0 × {0, 1, . . . , p -1} n .
We let (8.33)

M ′ := max {deg H, deg A h,i 1 ,...,in }
where the maximum is taken over all

(h, i 1 , . . . , i n ) ∈ S 0 × {0, 1, . . . , p -1} n .
We claim that it is possible to obtain an effective upper bound for M ′ , once the set of generators and the basis are known. To see this, note that we write T i = s j=1 φ i,j (X 1 , . . . , X r )a s , where each φ i,j is a rational function in X 1 , . . . , X r , where we assume that the degrees of the numerators and denominators of the φ i,j are uniformly bounded by some explicit constant N 5 .

Note that by construction, a monomial T i 1 1 • • • T in n with 0 ≤ i 1 , . . . , i n < p is an F p (X 1 , . . . , X r )-linear combination of a 1 , . . . , a s in which the coefficients are rational functions whose numerators and denominators have degrees uniformly bounded by (8.34) N 6 := (N 2 + N 5 )(p -1)ns 2(p-1)n .

To see this, we claim more generally that a monomial T j 1 1 • • • T jn n can be expressed as a F p (X 1 , . . . , X r )-linear combination of a 1 , . . . , a s in which the coefficients are rational functions whose numerators and denominators have degrees uniformly bounded by

(N 2 + N 5 )(j 1 + • • • + j n )s 2(j 1 +•••+jn) .
We prove this by induction on j 1 + • • • + j n . When j 1 + • • • + j n = 1, the claim is trivially true. So we assume that the claim holds whenever j 1 + • • • + j n < k and we consider the case that j 1 + • • • + j n = k. Then j i ≥ 1 for some i. Thus we may write

T j 1 1 • • • T jn n = T i • T j 1 1 • • • T j i -1 i • • • T jn n .
By the inductive hypothesis,

T j 1 1 • • • T j i -1 i • • • T jn n = s ℓ=1 ψ ℓ a ℓ ,
where each ψ ℓ is a rational function whose numerator and denominator have degrees bounded by (N 2 + N 5 )(k -1)s 2k-2 . Thus (φ i,j ψ ℓ )a j a ℓ .

T i • T j 1 1 • • • T j i -1
Recall that by assumption each a j a ℓ is a F p (X 1 , . . . , X r )-linear combination of a 1 , . . . , a s in which the degrees of the numerators and denominators are uniformly bounded by N 2 . Thus the coefficient of each a j is a linear combination consisting of s 2 terms whose numerators and denominators have degrees bounded by N 5 + (N 2 + N 5 )(k -1)s 2k-2 + N 2 and hence can be expressed as a rational function whose numerator and denominator have degrees bounded by (N 2 + N 5 )(1 + (k -1)s 2k-2 )s 2 ≤ (N 2 + N 5 )ks 2k . This gives the bound (8.34), as claimed. Then we may write

T i 1 1 • • • T in n = s j=1
C j (X 1 , . . . , X r ) D(X 1 , . . . , X r ) p a j , where C 1 , . . . , C s , D are polynomials of degree at most N 6 sp. Furthermore, we showed in (8.30) that each a j can be written as a F p (X 1 , . . . , X s )-linear combination of {a p 1 , . . . , a p t , a ℓ 1 , . . . , a ℓ s-t } in which the coefficients have numerators and denominators uniformly bounded by N 4 . Thus we may write Let k be a positive integer. We infer from (8.36) that U k 0 is contained in the F p -vector space spanned by the set

T i 1 1 • • • T in n = t j=1 C j (
K := H -j 0 T j 1 1 • • • T jn n | n i=0 j i ≤ k .
Then, every element L of K can be written as (8.38) L = H -pi 0 (H ℓ T j 1 1 • • • T jn n ) =: H -p(i 0 +1) H p Q where Q := H ℓ T j 1 1 • • • T jn n , 0 ≤ ℓ < p, 0 ≤ i 0 ≤ ⌊k/p⌋ and n i=1 j i ≤ kpi 0 . Thus Q is a polynomial in F p [T 1 , . . . , T n ] of degree at most (p deg H + kpi 0 ). By (8.31), Q can be decomposed as

Q = f ∈S Q p f f ,
where Q f are polynomials in F p [T 1 , . . . , T n ] of degree at most deg H +⌊k/p⌋-i 0 .

We deduce that H -(i 0 +1) Q f ∈ U M ′ +⌊k/p⌋+1 0 .

Thus we have (8.39) . This choice of k 0 implies that π i (V U ) ⊆ V . Furthermore, U ⊆ V and the cardinality of V is bounded by Card U k 0 -1 0 ≤ ( Card U 0 ) k 0 -1 ≤ p (n+1)(k 0 -1) . Since one could find an effective upper bound for n and since Inequality (8.35) provides an

H p Q = f ∈S Q p f (H p f ) .

Concluding remarks

We end our paper with a few comments. We note that Derksen [START_REF] Derksen | A Skolem-Mahler-Lech theorem in positive characteristic and finite automata[END_REF] also proved a refinement of his Theorem 1.2. Let us state his result. Let p be a prime number and let q be a power of p. Given c 0 , . . . , c d ∈ Q * with (q -1)c i ∈ Z for i ∈ {1, . . . , d} and c 0 + • • • + c d ∈ Z, we define Sq (c 0 , . . . , c d ) := c 0 + c 1 q i 1 + • • • + c d q i d | i 1 , . . . , i d ≥ 0 and we take S q (c 0 , . . . , c d ) := N ∩ Sq (c 0 , . . . , c d ) . If c i > 0 for some i ∈ {1, . . . , d}, we say that S q (c 0 , . . . , c d ) is an elementary pnested set of order d. We say that a subset of the natural numbers is p-nested of order d if it is a finite union of elementary p-nested sets of order at most d with at least one set having order exactly d. We then say that a subset of the natural numbers is p-normal of order d if it is, up to a finite set, the union of a finite number of arithmetic progressions along with a p-nested set of order d. Derksen [START_REF] Derksen | A Skolem-Mahler-Lech theorem in positive characteristic and finite automata[END_REF]Theorem 1.8] proved that the zero set of a linear recurrence of order d is a p-normal set of order at most equal to d -2. Of course, this refines the fact that such a set is p-automatic.

We already observed in the introduction that Theorem 1.4 is in some sense best possible since any p-automatic subset of N d can be obtained as the set of vanishing coefficients of an algebraic power series in F p [[t 1 , . . . , t d ]]. However, one might hope that a refinement, involving a reasonable version of multidimensional p-normal set, could hold if we restrict our attention to multivariate rational functions. This is actually not the case. Even for bivariate rational functions over finite fields, the set of vanishing coefficients can be rather pathological. Indeed, Furstenberg [START_REF] Furstenberg | Algebraic functions over finite fields[END_REF] showed that the diagonal of a multivariate rational power series with coefficients in a field of positive characteristic is an algebraic power series in one variable ( * ) . Moreover, the converse holds for any field: any one variable algebraic power series can be obtained as the diagonal of a bivariate rational power series ( * ) . In light of Christol's theorem, this implies in particular that any p-automatic subset of N can be realized as the diagonal of the set of vanishing coefficients of a bivariate rational power series with coefficients in F p .

Nevertheless, we may imagine that a similar refinement of Theorem 1.4 does exist for the special rational functions that appear in the Diophantine applications given in Sections 2, 3 and 4. Finally, since these applications only ( * ) Deligne [START_REF] Deligne | Intégration sur un cycle évanescent[END_REF] generalized this result to diagonals of algebraic power series with coefficients in a field of positive characteristic.

( * ) This result is essentially proved in [START_REF] Furstenberg | Algebraic functions over finite fields[END_REF]. Denef and Lipshitz [START_REF] Denef | Algebraic power series and diagonals[END_REF] actually obtained the following stronger result: any algebraic power series in n variables with coefficients in an arbitrary field can be obtained as the diagonal of a rational power series in 2n variables.

involve multivariate rational functions, it would be interesting to find natural Diophantine problems that would involve some sets of vanishing coefficients of algebraic irrational multivariate power series.

Addendum. -During the last stage of the writing of this paper, the authors learned about a related work (though not written in terms of automata) of Derksen and Masser [START_REF] Derksen | Linear equations over multiplicative groups, recurrences, and mixing I[END_REF]. These authors obtain in particular strong effective results for the general S-unit equations over fields of positive characteristic and more generally for the Mordell-Lang theorem, in the special case of linear subvarieties of G n m (K) for fields K of positive characteristic.

  and a := (a 1 , . . . , a m ) ∈ E, we let a • n := (a 1 n 1 , . . . , a m n m ) denote the ordinary coordinate-wise multiplication. Given A ⊆ N m , we also set a • A := {a • n | n ∈ A}. For every a := (a 1 , . . . , a d ) ∈ E d , we set

S

Figure 2 .Figure 3 .

 23 Figure 1. A 2-automaton generating Thue-Morse sequence.

Figure 4 .

 4 Figure 4. A 3-automaton recognizing those integers that are the sum of at most two powers of 3.

Example 5 . 7 .

 57 -Let f : N 2 → {0, 1} be defined by f (n, m) = 1 if the sum of the binary digits of n added to the sum of the binary digits of m is even, and f (n, m) = 0 otherwise. Then f (m, n) is a 2-automatic map. One can check that f can be generated by the following 2-dimensional 2-automaton: A = {A, B}, {0, 1} 2 , δ, A, {0, 1}, τ , where δ(A, (0, 0)) = δ(A, (1, 1)) = δ(B, (1, 0)) = δ(B, (0, 1)) = A, δ(A, (1, 0)) = δ(A, (0, 1)) = δ(B, (0, 0)) = δ(B, (1, 1)) = B, τ (A) = 0 and τ (B) = 1.

Figure 5 .

 5 Figure 5. A 2-dimensional 2-automaton generating the map f defined in Example 5.7. Just as k-automatic sequences can be characterized by the finiteness of the k-kernel, multidimensional k-automatic sequences have a similar characterization. Definition 5.3. -Let d be a positive integer and let ∆ be a finite set. We define the k-kernel of a map f : N d → ∆ to be the collection of all maps of the form g(n 1 , . . . , n d ) := f (k a n 1 + b 1 , . . . , k a n d + b d ) where a ≥ 0 and 0 ≤ b 1 , . . . , b d < k a . Example 5.8. -The 2-kernel of the map f : N 2 → {0, 1} defined in Example 5.7 consists of the 2 maps f 1 (m, n) := f (m, n), f 2 (m, n) = f (2m + 1, 2n).

Theorem 5 . 2 (

 52 Salon). -Let d be a positive integer and let ∆ be a finite set. A map f : N d → ∆ is k-automatic if and only if its k-kernel is finite. 5.3. Automatic subsets of Z d . -We show now how to naturally extend Salon's construction to k-automatic subsets of Z d by simply adding sympols + andto our alphabet Σ k .

Definition 5 . 6 .

 56 -Let d ≥ 1 be an integer and ∆ a finite set. Given a map f : Z d → ∆, we define the k-kernel of f to be the collection of all maps of the form g(n 1 , . . . , n d ) := f (k a n 1 + b 1 , . . . , k a n d + b d ) where a ≥ 0 and 0 ≤ b 1 , . . . , b d < k a . Proposition 5.1. -Let d ≥ 1 be an integer and ∆ a finite set. Given a map f : Z d → ∆, the following are equivalent.

Proposition 5 . 4 .

 54 -Let Γ be a finitely generated group, {γ 1 , . . . , γ d } a set of generators of Γ, and S a subset of Γ. Then S is k-automatic if and only if there exists a finite automaton that takes words over L k (d) as input and has the property that for every d-tuple of integers (n 1 , . . . , n d ) the word [(n 1 , . . . , n d )] -1 k ∈ L k (d) is accepted by the automaton if and only if

Remark 6 . 1 .

 61 -Let ∆ be a finite set. Then a map a : N d → ∆ is p-automatic if and only the set of functions {a • e | e ∈ Σ} is a finite set.

Definition 7 . 1 .

 71 -Let S ⊂ N d be a p-automatic set and let denote by K the p-kernel of S. We define the p-complexity of S by comp p (S) := Card K .

Proposition 7 . 1 .

 71 -Let S ⊂ N d be a p-automatic set and suppose that there exists an explicit integer N (S) such that comp p (S) ≤ N (S) .

Furthermore, by

  assumption, for f ∈ S (8.40)H p f ∈ h∈S 0 (U M ′ 0 ) p h .We infer from (8.38), (8.39) and (8.40) that Let k 0 := ⌊2(M ′ + 1)p/(p -1)⌋ + 1 and set V := U k 0 -1 0

  1.4. -Let K be a field of characteristic p and let f (t 1 , . . . , t d ) ∈ K[[t 1 , . . . , t d ]] be a power series that is algebraic over the field of multivariate rational functions K(t 1 , . . . , t

d ). Then the set Z(f ) is p-automatic.

  indeterminates t 1 , . . . , t d . The degree of such a monomial is the nonnegative integer n 1 + • • • + n d . Given a polynomial P in K[t], we denote by deg P the maximum of the degrees of the monomials in P with nonzero coefficient.

Definition 6.1. -We say that a power series f

  X 1 , . . . , X r ) D(X 1 , . . . , X r ) p D(X 1 , . . . , X r ) p a ℓ j ,where C 1 , . . . , C s , D have degrees bounded by(N 4 + N 6 )sp . M ′ ≤ (N 4 + N 6 )sp + p . Since {1} ∪ λ i,j,k | 1 ≤ i, k ≤ m, j ∈ {0,1, . . . , p -1} d ⊆ {T 1 , . . . , T n }, we have (8.37) U ⊆ U 0 .

	a p j + C Since S 0 forms a basis for K s-t j=1 p 0 , this ensures that
	(8.35)
	Now, we set
		n
	(8.36)	U 0 := F p H -1 +	F p T j .
		j=1

j (X 1 , . . . , X r )

Acknowledgement. -The authors would like to thank Jean-Paul Allouche, David Masser and the anonymous referees for their useful remarks. They are also indebted to Gaël Rémond for his interesting comments concerning the relation between Theorem 4.1 and Corrolary 4.1. The first author is also most grateful to Aurélie and Vadim for their constant patience and support during the preparation of this paper.

The First author was supported by ANR grants Hamot and SubTile. The second author was supported by NSERC grant 31-611456.

We first make the important observation that for every positive integer N there are only a finite number of p-automatic subsets of N d whose p-complexity is at most N . Lemma 7.1. -Let N be a positive integer. Then there at most N 2 N N pN distinct p-automatic subsets of N d whose p-complexity is at most N .

Proof. -In the definition of p-automatic sets in Section 5, we used pautomata that read the input (d-tuples of integers) starting from the most significant digits (the input is scanned from the left to the right). It is well known that using p-automata that read the input starting from the least significant digits (the input is scanned from the right to the left) leads to the same notion of p-automatic sets. Furthermore, it is known that for every pautomatic set S, there exists such a p-automaton for which the number of states is equal to the cardinality of the p-kernel of S. Such an automaton has actually the minimal number of states among all automata recognizing S and reading the input from the right to the left (see for instance [START_REF] Allouche | Automatic sequences. Theory, applications, generalizations[END_REF] or [START_REF] Derksen | A Skolem-Mahler-Lech theorem in positive characteristic and finite automata[END_REF]).

Thus a p-automatic set S ⊆ N d with p-complexity at most N can be recognized by a p-automaton A (reading from the right to the left) with at most N states. Let Q := {Q 1 , . . . , Q N } denote the set of states of A. To define A, we must choose the initial state, the transition function from Q × Σ p to Q, and the output function from Q to {0, 1}. We have at most N choices for the initial state, at most N pN choices for the transition function, and at most 2 N choices for the output function. The result immediately follows.

Lemma 7.2. -Let S 1 , S 2 ⊆ N d be p-automatic sets. Then the following hold.

Proof. -Given a set S let us denote by I S its indicator function. The proof follows from the fact that

, and

We will also use the following two results that can be easily proved as in [START_REF] Derksen | A Skolem-Mahler-Lech theorem in positive characteristic and finite automata[END_REF]. We are now ready to prove Proposition 7.1.

Proof of Proposition 7.1. -Let S ⊆ N d be a p-automatic set. Let us assume that one knows an effective bound N (S) for the p-complexity of S and that one can compute the initial terms of S. Let us also assume that for every positive integer n one can compute (in a finite amount of time) all the elements s ∈ S such that s ≤ n.

We first note that by Lemma 7.1 there are only a finite number, say r, of p-automatic subsets of N d with p-complexity at most N (S). Going through the proof of Lemma 7.1, we can explicitly enumerate all these sets to get a collection S 1 , S 2 , . . . , S r . Now for each S i , we can check whether S = S i as follows. Since both S and S i have p-complexity at most N (S), we infer from Lemma 7.2 that

Thus, by Lemma 7.3, the set (S \ S i ) ∪ (S i \ S) is empty if and only if it has no element up to p N (S) 2 -2 . This implies that S = S i if and only if

By assumption, this can be verified in a finite amount of time.

(i). Since the p-complexity of S is at most N (S), Lemma 7.3 implies that S is empty if and only if

By assumption, this can be verified in a finite amount of time.

(ii). Since the p-complexity of S is at most N (S), Lemma 7.4 implies that S is finite if and only if

On the other hand, it is easy to see that S ′ is a p-automatic set with complexity at most (p N (S) 2 -2 + 1) d . By Lemma 7.2, we deduce that

effective upper bound for M ′ (and thus for k 0 ), we obtain that there exists an effective constant N 7 such that Card V ≤ N 7 .

Step 3. In this last step, we show how to derive from Step 2 effective upper bounds for the cardinality of the sets W and X, from which we will finally deduce an effective upper bound for Comp p Z(f ).

We just show that it is possible to get an effective upper bound N 7 for the cardinality of the F p -vector space V . We now recall that the set W is defined by

We thus have Card W ≤ ( Card V ) m , and we infer from (8.27) that there exists an effective constant N 8 := N N 0 7 such that (8.41) Card W ≤ N 8 .

We recall that given a map b :

We recall that the set X is defined by

Since χ 2 b = χ b for all b ∈ W and since the product of maps χ b is commutative, we get that Card X ≤ 2 Card W .

Thus we infer from (8.41) the existence of an effective constant N 9 := 2 N 8 such that Card X ≤ N 9 .

On the other hand, the proof of Theorem 1.4 shows that the p-kernel of Z(f ) is contained in X, which implies that comp p (Z(f )) ≤ N 9 .

This ends the proof.