Emmanuel Hallouin

Marc Perret

A Graph Aided Strategy to Produce Good Recursive Towers over Finite Fields

We propose a systematic method to produce potentially good recursive towers over finite fields. The graph point of view, so as some magma and sage computations are used in this process. We also establish some theoretical functional criterion ensuring the existence of many rational points on a recursive tower. Both points are illustrated on an example, from the production process, to the theoretical study, using this functional criterion, of the parameters of the obtained potentially good tower.

Introduction

The search of explicit examples of sequences of algebraic curves over a given finite field, of genus growing to infinity and having as much as possible rational points with regard to their genera became more and more important not only for its own, but also for several uses such as coding theory and cryptography (Garcia and Stichtenoth [START_REF]Explicit towers of function fields over finite fields, Topics in geometry, coding theory and cryptography[END_REF]) or for multiplication algorithms over finite fields (Ballet [Bal03]). For quite a long time, only modular examples were known for square size of the finite field (Tsfasmann-Vladut-Zink [START_REF] Tsfasman | Modular curves, shimura curves, and goppa codes, better than the varshamov-gilbert bound[END_REF] and Ihara [Iha81, "The general case", p. 723]), and only examples coming from class field theory were known for non square size. Unfortunately, these examples were not explicit.

In 1995 appeared the important Garcia-Stichtenoth's paper [START_REF] Garcia | A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladut bound[END_REF] in which the very first explicit example was given. The explicitness comes from the recursive definition of each floor of the tower; such towers are now called recursive towers. Since then, several authors gave many examples of recursive towers (see Garcia and Stichtenoth's survey [START_REF]Explicit towers of function fields over finite fields, Topics in geometry, coding theory and cryptography[END_REF] or Li's one [START_REF] Wen- | Modular curves and coding theory: a survey, Finite fields: theory and applications[END_REF]). Two features appear at a look at the literature. First, the authors never explain how they where able to guess their examples. Second, once the explicit tower is given, there is always some difficulty in its study. Either the genus sequence is hard to compute (usually in the wildly ramified case), either the existence of many rational points is hard to prove (usually in the moderately ramified case). For instance, in the particularly interesting example of Garcia-Sitchtenoth moderately ramified tower recursively defined by the equation

y 2 = x 2 +1
2x , the proof of the splitting behavior is quite mysteriously related to some functional equation satisfied by the well known Deuring polynomial1 .

Apart from our previous article [START_REF] Hallouin | Recursive towers of curves over finite fields using graph theory[END_REF], the present work joins in the continuation of Lenstra's and Beelen's one [START_REF] Jr | On a problem of Garcia, Stichtenoth, and Thomas[END_REF][START_REF] Beelen | Graphs and recursively defined towers of function fields[END_REF]. A kind of non-existence result is proved by Lenstra [START_REF] Jr | On a problem of Garcia, Stichtenoth, and Thomas[END_REF] over prime finite fields for a very particular type of recursive towers. The proof is technical and quite intricate, at least for the authors of the present paper. A somehow understandable point is that it relies upon some functional equation labeled as (5) therein and whose meaning is explained in a concluding remark. Beelen proved soon after that the characteristic function of a totally splitting set has to fulfill some functional equation in case of separable variable correspondances on the projective line [Bee04, Theorem 3.2]. Beelen also proves, in a second part of his paper, that such a functional equation can have at most one solution for a special type of recursive tower, he called of type A. This second part has already been generalized by the authors [START_REF] Hallouin | Recursive towers of curves over finite fields using graph theory[END_REF].

In Section 1, we recall some backgrounds about recursive towers. Geometrically, the definition only requires a base curve X and a correspondence Γ ⊂ X × X. In this article we focus on the special case of recursive towers with separable variables2 , where the correspondence is given by two morphisms f, g : X → X 0 . One of the main tool for the study of a recursive tower is an associated graph G ∞ (X, Γ). This graph has already been introduced by Beelen [START_REF] Beelen | Graphs and recursively defined towers of function fields[END_REF] with a slightly different definition, and has been extensively used by the authors [START_REF] Hallouin | Recursive towers of curves over finite fields using graph theory[END_REF]. Many features of the tower can be directly read on the graph. In particular, the existence of some kind of finite component, the d-regular ones, is related to the existence of sets of points of the base curve splitting totally in the tower. Following Beelen (loc. cit.), this leads to introduce the weaker notion of completeness for subset of X(F q ). The importance of completeness comes from Proposition 6, that the search for a splitting set in a tower is carried out if one knows the ramification loci of f and g, an easy task, and if one can find complete sets, an harder task.

In section 2, we push further the understanding of the functional equation and its connection with the existence of many rational points in the tower. Theorem 9 asserts essentially that a finite set of points of the base curve splits totally in the tower if and only if the characteristic function of its support satisfies some functional equation. Beyond the fact that we do not need to assume the base curve to be the projective line, the contribution of Section 2 compared to Beelen's one is at first that while he proved that the functional equation is a necessary condition for completeness, we prove here that it is in fact a necessary and sufficient conditions for regularness. Next, that the precise form of the functional equation can be easily read from the singular graph of the tower. The sufficiency is of great importance for the applications given in the following of the present article.

We think that Theorem 9 is interesting in both theoretical and algorithmic study of recursive towers. In section 3, we give several applications that may convince the reader.

On the theoretical side, we deduce Theorem 10 from Theorem 9, extending one of the two main results in [START_REF] Hallouin | Recursive towers of curves over finite fields using graph theory[END_REF].

On the explicit side, we give two applications of the functional equation. Both use also the graph theoretic approach of recursive towers. In Section 3.2, we explain how the mysterious functional equation needed in [START_REF] Garcia | On tame towers over finite fields[END_REF] to prove the splitting behavior of some base points can in fact been deduced from the initial data y 2 = x 2 +1 2x . Then, in Section 3.3, we describe our main application of the functional equation. It consists in a systematic method to produce some potentially good recursive towers (Section 3.3.1) and in original methods to compute the asymptotic parameters of the tower. These methods use jointly the graph approach, some magma and sage computations, and Theorem 9 (Sections 3.3.2 & 3.3.3). All these ideas are illustrated on a concrete example. An interesting feature of this example is the following. The reader will be convinced that no modular tool is used in its production. However, the tower turns to be modular (Proposition 18). This can be seen as another experimental evidence toward Elkies' modularity conjecture 3 that any tame good recursive tower over a square finite field should be modular!

Preliminary notations and background

We recall the definition of a recursive tower and of its principal parameters, and we associate a graph to a recursive tower, as in our previous work [START_REF] Hallouin | Recursive towers of curves over finite fields using graph theory[END_REF]. Some of the results of this article are also included.

Recursive towers

Let X be a smooth projective absolutely irreducible curve defined over the finite field F q and let Γ ⊂ X × X be an irreducible correspondence, without no vertical nor horizontal component. The singular recursive tower T (X, Γ) = (X n ) n≥1 is defined, for n ≥ 1, by

X n = {(P 1 , P 2 , • • • , P n ) ∈ X n | (P i , P i+1 ) ∈ Γ for each i = 1, 2, . . . , n -1} .
In this article, we restrict ourselves to correspondences with separable variables, that is of the form

Γ = Γ f,g = {(P, Q) ∈ X × X; f (P ) = g(Q)}, (1)
where f, g : X → X 0 are two degree d maps from X to a given smooth base curve X 0 . The curves X n may be singular and by desingularization process, we obtain the smooth recursive tower T (X, Γ) = ( X n ) n≥1 . The interesting parameters of the towers are:

• the arithmetic genus of X n , γ n = γ(X n );

• the geometric genus of X n , i.e. the genus of X n , g n = g(X n ) = g( X n );

• the number of rational points over F q r for r ≥ 1, N r ( X n ) = X n (F q r );

3 Or Elkies' fantasia, as Elkies himself stated it in [START_REF] Elkies | Explicit towers of Drinfeld modular curves[END_REF].

• last, the limit

λ r (T ) = lim n→+∞ N r ( X n ) g n .
For a recursive tower, this limit always exists and is thus a non negative number. The tower is said to be asymptotically good if it is non-zero for some r ≥ 1. This happens (see Lemma 1 in [START_REF] Hallouin | Recursive towers of curves over finite fields using graph theory[END_REF] for instance) if and only if there exist some c, c > 0 such that

g n = c × d n + o(d n ) and N r ( X n ) = c × d n + o(d n ).
(2)

Graphs and Recursive towers

To each recursive tower, one can associate a directed graph.

Definition 1. Let T (X, Γ) be a recursive tower, where Γ is associated, via (1), to the functions f, g : X → X 0 .

(i) The geometric graph G ∞ (X, Γ) is the graph whose vertices are the geometric points of X, and for which there is an oriented edge from

P ∈ X(F q ) to Q ∈ X(F q ) if (P, Q) ∈ Γ(F q ), that is if f (P ) = g(Q).
(ii) For S ⊂ X(F q ), the S-graph G S (X, Γ) is the subgraph of G ∞ (X, Γ) whose vertices are the points of S.

(iii) The r-th arithmetic graph G r (X, Γ) is the X(F q r )-graph.

(iv) The singular graph is the union of the weakly connected components containing a (directed) path joining a ramified point of f to a ramified point of g.

The adjectives geometric, arithmetic, or singular, qualifying the different graphs come from the following correspondence between the points of tower and the paths in the graphs (see [HP14, Section 3.2]).

Proposition 2. Let T (X, Γ) be a recursive tower, where Γ is associated, via (1), to the functions f, g : X → X 0 . There is a one-to-one correspondence between

{paths of G ∞ (X, Γ) of length n -1} ←→ X n (F q ).

This correspondence:

(i) restricts to a one-to-one correspondence between X n (F q r ) and the set of paths of length (n -1) of the r-th arithmetic graph G r (X, Γ);

(ii) is such that a path corresponds to a singular point of X n if and only if it joins a ramified point of f to a ramified point of g.

At any point outside the ramification loci of f and g, the in and out degrees in the geometric graph are equal to the common degree d of both morphisms f, g, and only points that are ramified by f or g have in or out degrees less than d. The following definition is of importance in this article because of the following alternative which follows from (2) and [HP14, Proposition 21]. Definition 3. A finite subset S ⊂ X(F q ) is said to be d-regular if the S-graph G S (X, Γ) is a d-regular graph that is if any vertex has in and out degrees equal to d.

Proposition 4. Let T (X, Γ) be a recursive tower, where Γ is associated, via (1), to the functions f, g : X → X 0 of degree d. Then the tower T (X, Γ) is asymptotically good over F q r if and only if there exists some c > 0, such that g n = c × d n + o(d n ), and (i) either the number of points of X n , defined over F q r , coming from the desingularization of the singular component of G r (X, Γ) has asymptotic behaviour of the form to c × d n + o(d n ) for some c > 0;

(ii) or there exists a finite d-regular set inside the r-th arithmetic graph G r (X, Γ).

See loc. cit. for details, but notice that if there exists a d-regular finite subset S ⊂ X(F q r ) for some r ≥ 1, then the number of paths of length (n -1) of this component is clearly S × d n . By Proposition 2, these paths are in one-to-one correspondence with smooth points of X n defined over F q r . Therefore the number of points of X n satisfies the last condition in Proposition 4 and the tower is asymptotically good, provided that the genus sequence do not grows too fast as required also as a first condition in Proposition 4. Note that geometrically, the vertices/points of S are nothing else than the totally split points in the tower.

One of the main result of our previous work [START_REF] Hallouin | Recursive towers of curves over finite fields using graph theory[END_REF] says that there exists at most one finite d-regular set. But there may exist other interesting finite subsets satisfying a weaker property than regularness which turns to be useful to give characterizations of d-regular set.

Definition 5. Let X and X 0 be two smooth, projective, absolutely irreducible curves over F q and let f : X → X 0 , g : X → X 0 be two morphisms of degree d. A subset S of X(F q ) is said to be:

(i) forward complete if g -1 (f (S)) ⊂ S; (ii) backward complete if f -1 (g(S)) ⊂ S;
(iii) complete if it is both backward and forward complete.

For S ⊂ X(F q ) a finite subset, if the graph G S (X, Γ) is d-regular, then S is complete. The converse is false, but one easily see that the following Proposition holds. Proposition 6. Let T (X, Γ) be a recursive tower, where Γ is associated, via (1), to the morphisms f, g : X → X 0 and let S be a subset of X(F q ). Then S is d-regular if and only if S is complete and outside the ramification loci of f and g. If this is the case, then any point of S splits totally in the tower.

Completeness and regularness criteria

We build successively in this section three characterizations of complete and of regular sets. The first one is a basic set theoretic criterion for completeness, the second one is a divisorial criterion for completeness, and the last one is a functional equation characterizing, once a first complete finite set is known, if another given finite set is d-regular.

A divisorial criterion for completeness

Lemma 7 (Set theoretical completeness criterion). A subset S ⊂ X(F q ) is complete if and only if there exists S 0 ⊂ X 0 (F q ) such that S = f -1 (S 0 ) = g -1 (S 0 ).

Proof -Suppose that S is complete. First we prove that f (S) = g(S). Let P ∈ S. There exists some Q ∈ X(F q ) such that f (P ) = g(Q). By forward completeness, one has Q ∈ S. This leads to f (S) ⊂ g(S), and the reverse inclusion is proved the same way using backward completeness. Put S 0 = f (S) = g(S) and let us prove that

S = f -1 (S 0 ) = g -1 (S 0 ). Of course S ⊂ f -1 (S 0 ) = f -1 (f (S)). Conversely, if P ∈ f -1 (S 0 ) then f (P ) ∈ S 0 = g(S), that is f (P ) = g(Q) for some Q ∈ S.
By backward completeness, we deduce that P ∈ S and that f -1 (S 0 ) ⊂ S. The proof of the converse works also in the same way.

For the remaining characterizations, we need to introduce the following notations.

• For S ⊂ X(F q ), we put div(S) = P ∈S P and for ϕ ∈ F q (X), we denote by div(ϕ) the associated divisor.

• For P ∈ X(F q ) we denote by e f (P ) the ramification index of P by f .

• For S 0 ⊂ X 0 (F q ), let D f (S 0 ) = P ∈f -1 (S 0 )
(e f (P ) -1) P be the restricted different divisor of f . Under these notations, if S 0 is a subset of X 0 (F q ), one can point out the useful divisorial equalities

f * div(S 0 ) = D f (S 0 ) + div f -1 (S 0 ) and g * div(S 0 ) = D g (S 0 ) + div g -1 (S 0 ) . (3)
We can then state the following, a generalization of Lenstra's identity.

Proposition 8 (Divisorial completeness criterion). Let S 0 be a finite subset of X 0 (F q ). The following assertions are equivalent.

(i) The set f -1 (S 0 ) is complete. (ii) The set g -1 (S 0 ) is complete. (iii) f * div(S 0 ) -g * div(S 0 ) = D f (S 0 ) -D g (S 0 ).
Proof -This is a direct consequence of (3) together with the set theoretical completeness criterion (Lemma 7).

A functional criterion for regularness

From this section, and for the rest of this article, given a curve X defined over F q and f, g

∈ F q (X), we write f ∼ g if div(f ) = div(g) in div(X), that is if there exists a constant c ∈ F * q such that f = cg.
The characterizations of completeness given in Lemma 7 and Proposition 8 are not always sufficiently effective in practice. The most fruitful characterization is the following functional regularness characterization.

Theorem 9 (functional regularness criterion). Let Γ be a correspondence induced by f, g : X → X 0 as in (1). Let S = f -1 (S 0 ) = g -1 (S 0 ) be a complete subset of X(F q ). Let b be the order of the degree zero divisor D f (S 0 ) -D g (S 0 ) in the jacobian Jac(X), and let ρ ∈ F q (X) be a function such that div(ρ) = b(D f (S 0 ) -D g (S 0 )). Let T 0 be a finite subset of X 0 (F q ), disjoint from the ramification locus of g. Let s, t ∈ N * be such that t S 0 = s T 0 , let a be the order of the degree zero divisor s div(T 0 ) -t div(S 0 ) in Jac(X 0 ), and let ϕ ∈ F q (X 0 ) be a function such that div(ϕ) = a (s div(T 0 ) -t div(S 0 )).

Then the functional equation

ρ ta × (ϕ • f ) b ∼ (ϕ • g) b (4) holds in F q (X 0 ) if and only if f -1 (T 0 ) is d-regular.
Remark -In most instances4 , the singular graph turns to be finite and complete.

It is then fruitful to choose S to be this singular graph, see Sections 3.2 and 3.3.3.

Proof -The divisors of the functions ϕ

• f and ϕ • g on X are div(ϕ • f ) = a (sf * div(T 0 ) -tf * div(S 0 )) and div(ϕ • g) = a (sg * div(T 0 ) -tg * div(S 0 )) , so that by difference div(ϕ • f ) -div(ϕ • g) = as (f * div(T 0 ) -g * div(T 0 )) -at (f * div(S 0 ) -g * div(S 0 )) . ( 5
)
Since S is complete, it follows by the divisorial completeness criterion (Proposition 8) that

f * div(S 0 ) -g * div(S 0 ) = D f (S 0 ) -D g (S 0
). Since none of the points of T 0 are ramified by g, we have

D g (T 0 ) = 0, hence (3) reduces to f * div(T 0 ) -g * div(T 0 ) = div (f -1 (T 0 )) + D f (T 0 ) - div (g -1 (T 0 )).
Multiplying by b and taking div(ρ ta ) into account, equation (5

) becomes b [div(ϕ • f ) -div(ϕ • g)] + ta div(ρ) = abs div f -1 (T 0 ) + D f (T 0 ) -div g -1 (T 0 ) .
It follows that the functional equation (4) holds if and only if

div f -1 (T 0 ) + D f (T 0 ) = div g -1 (T 0 ) . (6)
Suppose that the functional equation (4), or equivalently that (6) do holds. Since the effective divisor div (g -1 (T 0 )) is reduced, the effective divisor div (f -1 (T 0 )) + D f (T 0 ) is also reduced. Moreover, the support of the divisor D f (T 0 ) is contained in the support of div (f -1 (T 0 )), hence we can deduce that D f (T 0 ) = 0, that is T 0 is outside the ramification locus of f . Furthermore, (6) becomes div f -1 (T 0 ) = div g -1 (T 0 ) , meaning that f -1 (T 0 ) is complete by the set theoretical completeness criterion Lemma 7. It follows that f -1 (T 0 ) is d-regular by Proposition 6. Conversely, suppose that that f -1 (T 0 ) is d-regular, so that T 0 is disjoint from the ramification locus of f and f -1 (T 0 ) is complete by Proposition 6. Then D f (T 0 ) = 0, and by the set theoretical completeness criterion, we have div (f -1 (T 0 )) = div (g -1 (T 0 )), so that (6), hence the functional equation (4), holds true.

Applications

Non existence of totally splitting sets for some recursive towers

We deduce from the functional regularness criterion the following Theorem, extending the main result of [START_REF] Hallouin | Recursive towers of curves over finite fields using graph theory[END_REF].

Theorem 10. Let T (X, Γ) be a recursive tower, where Γ is associated, via (1), to the morphisms f, g : X → X 0 of degree d. Suppose that the tower is irreducible, and that there exists a complete set S such that D f (S 0 ) = D g (S 0 ) for S 0 = f (S) = g(S). Then the graph do not contains any non-empty finite d-regular component T disjoint to S.

Remark -A d-regular set S satisfies D f (S 0 ) = P ∈S P = D g (S 0 ), so that this statement contains Theorem 19 of [START_REF] Hallouin | Recursive towers of curves over finite fields using graph theory[END_REF] in case of correspondences with separable variables. This Theorem also contains the case of a complete loop at a point P (for instance for type A towers in Bellen's [START_REF] Beelen | Graphs and recursively defined towers of function fields[END_REF] and in [START_REF] Jr | On a problem of Garcia, Stichtenoth, and Thomas[END_REF]), in which case we have S = {P }, S 0 = {f (P 0 )} and D f (S 0 ) = (d -1)P = D g (S 0 ).

Proof -Suppose by contradiction that there do exist a finite d-regular component T and let

T 0 = f (T ) = g(T ). Since G T (X, Γ
) is assumed to be d-regular, each vertex of T is unramified by f and g. One can apply the functional regularness criterion (Theorem 9) to S 0 and T 0 .

Since by assumption D f (S 0 ) -D g (S 0 ) = 0, we have b = 1 and one can choose ρ = 1. We denote by a the order, in Jac(X 0 ), of the zero degree divisor S 0 div(T 0 ) -T 0 div(S 0 ), and we consider ϕ ∈ F q (X 0 ) such that div(ϕ) = a( S 0 div(T 0 ) -T 0 div(S 0 )). By the functional regularness criterion (Theorem 9), there exists some c ∈ F q * such that 3.2 Understanding the splitting set of the optimal tower

ϕ • g = c × ϕ • f. For any Q, R ∈ X(F q ) such that f (Q) = g(R), we deduce that ϕ • f (Q) = ϕ • g(R) = c × ϕ • f (R). Therefore, if Q is any vertex of G ∞ (X, Γ), then ϕ • f takes values in c Z × ϕ • f (Q) on
y 2 = x 2 +1 2x
For some known Garcia-Stichtenoth recursive towers, especially for the tame one, it is quite difficult to prove that some set of places splits totally in the tower. Suppose that the base curve is P 1 (which is the case for all known explicit examples) whose Jacobian is trivial. Once the characteristic function of the involved points on P 1 is guessed (we explain in Subsection 3.3 how it can be guessed on an example), the functional regularness criterion Theorem 9 is the good tool to prove that they do split in the tower. Let us illustrate this on the example of the moderate tower T P 1 , y 2 = x 2 +1 2x , studied for instance in [START_REF] Garcia | On tame towers over finite fields[END_REF] and well known to be optimal. The genus computation being not difficult in this case, the hard point is the existence of some totally splitting locus. Let H be the Deuring polynomial over F p , whose simple roots are supersingular j-invariants in characteristic p. The splitting behaviour of some set closely related to the zero set of H is easily deduced by Garcia and Stichtenoth from the functional equation

H(x 4 ) = x p-1 H x 2 + 1 2x 2 , (7) 1 -1 ı -ı 0 ∞ ı 2 = -1
Figure 1: The singular component of T P 1 , x 2 +1 2x = y 2 over F p 2 which seems to be pulled out of the hat! We explain in this subsection that taking into account the singular part of the graph, this is nothing but the functional equation (4) requested in the functional regularness criterion (Theorem 9) for the characteristic function of some splitting set! Let h(x) = P ∈T 0 (x -x(P )) ∈ F q [x] be the characteristic polynomial of any finite set T 0 ⊂ P 1 \ {∞} outside the ramification locus {0, ∞} of g(y) = y 2 .

The singular graph is drawn in figure 1. For general p ≥ 3, the involved points of

X = P 1 are S = {1, -1, ı, -ı, 0, ∞} where ı is a square root of -1 in F p . Applying f (x) = 1+x 2 2x (or g(y) = y 2 ), we have S 0 = {1, -1, 0, ∞}. Moreover, D f (S 0 ) = (2-1)[1]+(2-1)[-1] and D g (S 0 ) = (2 -1)[0] + (2 -1)[∞], hence the condition div(ρ) = D f (S 0 ) -D g (S 0 ) = [1] + [-1] -[0] -[∞] is fulfilled by the function ρ(x) = (x -1)(x + 1) x ∈ F p (P 1 ).
Some magma experiments, for few small values of p, show that there do exist such a set with T 0 = p -1. Since S 0 = 4 and p is odd, one can try t = p-1 2 and s = 2. The functional regularness criterion also requires a function ϕ ∈ F p (X 0 ) such that div(ϕ) = 2 div(T 0 ) -p-1 2 div(S 0 ). Up to a constant,

ϕ(x) = h(x) 2 [(x -1)(x + 1)x]
p-1 2 works. Hence, Theorem 9 asserts that the set f -1 (T 0 ) is complete if and only if h(0) = 0 and

ρ(x) p-1 2 ϕ x 2 + 1 2x ∼ ϕ(x 2 ).
This functional equation can be written

(x -1)(x + 1) x p-1 2 × h x 2 +1 2x 2 x 2 +1 2x -1 x 2 +1 2x + 1 x 2 +1 2x p-1 2 ∼ h(x 2 ) 2 [(x 2 -1)(x 2 + 1)x 2 ] p-1 2 .
After simplification by powers of x, x -1 and x + 1, this is equivalent to

x p-1 h x 2 + 1 2x 2 ∼ h(x 2 ) 2 ,
that is to

x p-1 h x 2 + 1 2x ∼ h(x 2 ),
which is neither than (7) with h(x) = H(x 2 ).

Of course, proving that this functional equation do have a solution H is another task. On this example, the solution H have been already guessed by Garcia and Stichtenoth. To ovoid cheating, we explain in the following section how this task can be achieved on another example, chosen in such a way that the solution is a priori unknown.

Graph based strategy to produce and to study asymptotically good recursive towers

The goal of this section is to show how a good recursive tower can be studied, from its production process in Section 3.3.1, to the computation of its parameters in Sections 3.3.2 and 3.3.3.

Producing a potentially good recursive tower using graphs and computer help

The strategy to produce such a candidate is the following. For algorithmic purpose, we fix a base curve X and a "kind" of correspondence Γ ⊂ X × X, that is a set of correspondences parametrized by some quasi-projective variety V . In order to obtain recursive towers having potentially low genus sequence as required by Proposition 4, we also fix a specific finite singular graph. Now, any edge of the graph G ∞ (X, Γ) corresponds to a relation on the parameters of the correspondence Γ viewed as a points of V . Hence, correspondences Γ on X of the given kind such that G ∞ (X, Γ) contains the fixed finite graph as a subgraph are parametrized by a subvariety W of V . Then, a magma program returns, for a given prime p, all F p -rational points of W .

After very few trials of specific singular graphs5 , we obtain for few values of p some explicit equations. The associated graph having, as checked using a sage program, some d-regular component, these equations define potentially good recursive towers. Indeed, they experimentally possess some d-regular set ensuring that the number of points is large enough, and their singular graph have a certain imposed shape, making it possible that the genus sequence is low enough as required in Proposition 4.

Here is how all this works on an example. We choose:

• the base curve X to be P 1 ;

• correspondences Γ of bi-degree (2, 2) and with separable variables, that is of type Γ f,g where f and g are two functions from P 1 to P 1 of degree 2;

• a singular graph of the form

R 1 P 1 S 1 R 2 P 2 S 2 ,
where R 1 , R 2 are the ramified points of f and S 1 , S 2 those of g. In particular, in view of the specific shape of the singular graph, these four ramification points should be distinct.

Remark -This kind of singular graph is not chosen at random. In order to minimize the genus sequence, the curves X n must be singular as pointed out in [START_REF] Hallouin | Recursive towers of curves over finite fields using graph theory[END_REF]. This means by Proposition 2 that there must exist some paths from ramification points of f to ramification points of g. We also have noted that in most known examples of good recursive tower, there are loops at some of these ramification points. The chosen graph is one of the most simple that takes into account these constraints.

Note that there are 6 parameters in such a singular graph, namely the 6 points P i , R i , S i , for i = 1, 2. We use the automorphisms group Aut(P 1 ) to fix some of them as follows. For any σ, τ ∈ Aut(P 1 ), the map (P 1 , . . . , P n ) → (τ -1 (P 1 ), . . . , τ -1 (P n )) defines an isomorphism from the tower T (P 1 , Γ f,g ) to the tower T (P 1 , Γ σ•f •τ,σ•g•τ ). Therefore, using the simply 3-transitivity of Aut(P 1 ) on P 1 , one can suppose that R 1 = 1, S 1 = 0 and S 2 = ∞. In the same way, one can suppose that g(S 1 ) = 0, g(S 2 ) = ∞ and g(1) = 1. These normalizations lead to g(y) = y 2 , so that we are reduced to look for a rational function

f (x) = a 2 x 2 + a 1 x + a 0 b 2 x 2 + b 1 x + b 0
where the parameter (a 2 : a 1 : a 0 : b 2 : b 1 : b 0 ) lives in P 5 . Since f have to be of degree deg f = deg g = 2, this point in P 5 must lie in the complementary V of the sets of constant functions and of degree one functions. The constant functions is the zero set of the 2-by-2 minors of (

a 2 a 1 a 0 b 2 b 1 b 0 )
, and the degree one functions is the zero set of the resultant of a 2 x 2 + a 1 x + a 0 and b 2 x 2 + b 1 x + b 0 .

For such a f ∈ V , the equation of the correspondence Γ f,g in

P 1 × P 1 = Proj(F q [X 1 , Y 1 ]) × Proj(F q [X 2 , Y 2 ]) is E(X 1 , Y 1 , X 2 , Y 2 ) = Y 2 2 (a 2 X 2 1 + a 1 X 1 Y 1 + a 0 Y 2 1 ) -X 2 2 (b 2 X 2 1 + b 1 X 1 Y 1 + b 0 Y 2 1 ) = 0.
Let us now traduce as equations on the parameter (a 2 : a 1 : a 0 : b 2 : b 1 : b 0 ) the requested shape for the singular graph. The fact that the point (1 : 1) is ramified by f gives as a first constraint the vanishing at x = 1 of the derivative of f (x), a quadratic equation in the parameters. Note for later use that the second ramified point by f is (a 1 b 0 -a 0 b 1 : a 2 b 1 -a 1 b 2 ). Each loop, so as each horizontal path of length 2, gives rise to linear algebraic constraints on the parameters as follows. The four loops lead to the equations

E(1, 1, 1, 1) = E(0, 1, 0, 1) = E(1, 0, 1, 0) = E(a 1 b 0 -a 0 b 1 , a 2 b 1 -a 1 b 2 , a 1 b 0 -a 0 b 1 , a 2 b 1 -a 1 b 2 ) = 0.
The existence of a path of length 2 from R i to S i is equivalent to the vanishing of a resultant, since this is the request of the existence of some common zero P i of f (R i ) -g(P ) and of f (P ) -g(S i ). Finally these 1 + 4 + 2 = 7 equations define a quasi-projective curve W in P 5 .

For the small values of the prime p ∈ {5, 7, 11, 13, 17}, we find using magma the unique solution whose equation f (x) = x 2 +x 3x-1 doesn't depend on p. To conclude, this graph aided strategy suggests to study the recursive tower defined by X = P 1 for p ≥ 5, and

Γ f,g = ((x 1 : y 1 ), (x 2 : y 2 )) ∈ P 1 × P 1 | x 2 1 + x 1 y 1 3x 1 y 1 -y 2 1 = x 2 2 y 2 2 .
The ramification points of the function f (x) = x 2 +x 3x-1 are 1 and -1 3 ∈ F p , those of the function g(y) = y 2 are 0 and ∞, and the singular complete subgraph is the following

1 -1 0 -1 3 1 3 ∞ .
The remaining of this section is devoted to the proof of the following result stating that this potentially good tower is actually asymptotically good.

Theorem 11. The recursive tower T P 1 , y 2 = x 2 +x 3x-1 is asymptotically good.

Proof -The proof is divided in two steps. In Propositions 12, the genus sequence is computed and we observe that it has the good shape requested in Proposition 4. Then, we prove Proposition 14 that the number of points sequence also have the good shape.

Genus sequence computation

In this section we establish a closed formula for the genus sequence of the tower. One can distinguish at least two strategies to compute the genus sequence of such a recursive tower. The first one, used by Garcia and Stichtenoth in their articles in this area, consists in applying the Riemann-Hurwitz genus formula to the function field extensions F p (X n )/F p (X 1 ) after having computed the different divisor of these extensions. The second one, used in our previous work on recursive towers [START_REF] Hallouin | Recursive towers of curves over finite fields using graph theory[END_REF], consists in computing the geometric genus of the curves X n from their arithmetic one by subtracting the sum of the measures of singularity of the points. This last point of view takes better into account the geometry of the data. Furthermore, as will be seen by the reader in the proof of Lemma 12 below, this method is a guide for the choice of a fixed singular graph as was done in Subsection 3.3.1. This is the first time that we illustrate our method on a simple, though non-trivial, example of recursive tower.

Proposition 12. The genus sequence (g n ) n≥1 of the tower T P 1 , y 2 = x 2 +x 3x-1 is given by

g n = 2 n -(2 + n mod 2) × 2 n 2 + 1, ∀n ≥ 1.
Proof -Let n ≥ 1. We denote by ν n the desingularization morphism ν n : X n → X n and by X n the pullback of the embedding

X n → X n-1 × X along ν n-1 × Id : X n-1 × X → X n-1 × X. We have the cartesian diagram X n X n-1 × X X n X n-1 × X ν n-1 × Id
The curves X n , X n and X n are birational and the two first one are singular for n ≥ 3. We thus introduce the measure of singularity of the curve X n defined, as usual, by

∆ n = P ∈X n (Fp) dim Fp O P /O P ,
where O P and O P denote the local ring at P of X n and of its integral closure. Then, using Proposition 4 in [START_REF] Hallouin | Recursive towers of curves over finite fields using graph theory[END_REF] specialized to the case where d = 2, g 1 = 0 and γ 2 = 1, we obtain:

g n = 1 + (n -2)2 n-1 - n i=2 2 n-i ∆ i .
From the following Lemma 13, we have ∆ i = 2 i-1 -2 i 2 . Proposition 12 follows from an easy summation exercise. Lemma 13. Let n ≥ 1. The singular points of the curve X n are above the points (1 r , -1, 0 s ) and -1 3 r , 1 3 , ∞ s of X n , for r + s + 1 = n and r ≥ s ≥ 1. For such r, s, there are exactly 2 s-1 points on X n , all of them giving rise to two points on X n , and having a measure of singularity equal to 2 r-s . The global measure of singularity of the curve

X n is ∆ n = 2 n-1 -2 n 2 .
Remark -The curves X 1 and X 2 are smooth and thus so are X 1 and X 2 .

Proof -The singular points of X n correspond by Proposition 2 to the paths of the graph G ∞ joining a ramified point of f to a ramified point of g. In view of the chosen singular graph, they are the points (1 r , -1, 0 s ) and -1 3 r , 1 3 , ∞ s for r, s ≥ 1 and r + s + 1 = n. The second one going the same way, let us concentrate on the first type of points. For each edge of the corresponding singular component of the singular graph

1

-1 0 , one can associate an appropriate recursive algebraic relation and the corresponding Newton polygon in the following way:

(x n -1) 2 -2(x n -1) -(x n-1 -1) 2 3x n-1 -1 (x n + 1) 2 -2(x n + 1) -(x n-1 -1) 2 3x n-1 -1 1 -2v(x n-1 -1) • 2v(x n-1 -1) • 1 • 2 O 1 -1 -2v(x n-1 -1) • 2v(x n-1 -1) • 1 • 2 O x 2 n -x n-1 (x n-1 +1) 3x n-1 -1 x 2 n -x n-1 (x n-1 +1) 3x n-1 -1 -1 0 -1 2 v(x n-1 + 1) • v(x n-1 + 1) • 2 O 0 -1 2 v(x n-1 ) • v(x n-1 ) • 2 O
In this tabular, v respectively denotes a valuation of the field F p (X n-1 ) satisfying v(x n-1 -1) > 0, v(x n-1 -1) > 0, v(x n-1 + 1) > 0 and v(x n-1 ) > 0. In the remaining of this section, for r, s ≥ 1, we denote by v (1 r ,-1,0 s ) any valuation of the field F p (X r+s+1 ) satisfying v (1 r ,-1,0 s ) (x i -1) > 0 for 1 ≤ i ≤ r, v (1 r ,-1,0 s ) (x r+1 + 1) > 0, v (1 r ,-1,0 s ) (x j ) > 0 for 1 ≤ j ≤ s and v (1 r ,-1,0 s ) (x 1 -1) = 1 (we normalize this way in order to have formulas (8)). We do the same for v (1 r ) and v (1 r ,-1) . With these notations, the Newton polygons of the preceding tabular permit to prove that every loop at 1 and the path form 1 to -1 multiply the valuations by 2, while the path from -1 to 0 and the loop at 0 divides the valuations by 2. More precisely, we have

v (1 r ) (x r -1) = 2 r-1 , v (1 r ,-1) (x r+1 + 1) = 2 r , v (1 r ,-1,0 s ) (x r+s+1 ) = 2 r-s . (8)
Let us start with the point Q = (1 n-2 , -1, 0), that is with r = n -2 and s = 1. The point P = (1 n-2 , -1) ∈ X n-1 is smooth and thus corresponds to a unique point of X n-1 , and the function x 1 is an uniformizing parameter at P . Let O P be the local ring at P . There is a unique singular point Q ∈ X n above P ∈ X n-1 , and above Q ∈

X n . The local ring at Q is O Q = O P [x n ]. Since v P (x n-1 + 1) = 2 n-2 , one has x n x 2 n-3 1 2 - x n-1 3x n-1 -1 × x n-1 + 1 x 2 n-2 1 non zero at P = 0.
The non-vanishing of the constant function shows that this equation is smooth. This proves that O

P [x n ] = O P xn x 2 n-3 1 . Thus there are two points in X n above Q ∈ X n , or above (1 n-2 , -1, 0) ∈ X n and moreover δ P = 2 n-3 .
We proceed by induction on s for the study of the singularity above the general singular point P = (1 r , -1, 0 s ) ∈ X n for r + s + 1 = n. We need to distinguish two cases.

If r ≥ s ≥ 1, then by induction, there are exactly 2 s-1 points of X n-1 above (1 r , -1, 0 s-1 ). Let P one of them and let O P be the local ring at P . The function x 1 is still an uniformizing parameter at P and above P there is only one point Q ∈ X n , whose local ring is

O Q = O P [x n ].
Then v P (x n-1 ) = 2 r-s+1 , and the equation

x n x 2 r-s 1 2 - x n-1 3x n-1 -1 × x n-1 + 1 x 2 r-s+1
1 non zero at P = 0 is smooth. This proves that there are two points of X n above Q ∈ X n , that is above (1 r , -1, 0 s ) ∈ X n , and that δ P = 2 r-s . In the other case, that is if s > r ≥ 1, then x n-1 turns to be an uniformizing element for all the points of X n-1 above P = (1 r , -1, 0 s-1 ), and the corresponding points P on X n are smooth (and ramified over X n-1 ).

In conclusion, we get by summation

∆ n = 2 × n-1 2 s=1 2 s-1 × 2 r-s = n-1 2 s=1 2 n-s-1 ,
where the first factor 2 comes from the other component of the singular graph. The remaining of the computation is left to the reader.

Lower bound for the number of points sequence

The last step is to prove that the tower has a large enough number of rational points sequence over some F p r , that is of size X n (F p r ) = c × 2 n + o(2 n ) for some non-zero constant c as requested in Proposition 4. To this end, we prove the following result.

Proposition 14. Let p ≥ 5 be a prime. There exists r ≥ 1, and a finite set T ⊂ P 1 (F p r ) with 2(p -1) elements, such that the graph G T (X, Γ) is 2-regular and the number of points sequence of the tower

T P 1 Fp , y 2 = x 2 +x 3x-1 satisfies X n (F r q ) ≥ (p -1) × 2 n .
By the correspondence recalled in Proposition 2, if such a finite set T exists, then the curve X n contains at least 2 n (p -1) points over F p 2 . The rest of this section is devoted to the proof of the existence of this finite set T , stated in Lemma 15. It is divided in few steps.

First, we experimentally compute this finite set and its characteristic polynomial for few small primes p. Second, we observe that these polynomials for these small values of p do lift to Z, that is are reduction modulo p of some truncation of some integer coefficients series. We enter this experimental integer sequence of first coefficients in the database OEIS, which luckily returns a whole infinite integer sequence. Finally, we prove that the reduction modulo p of some truncation of the generating series of this infinite integer sequence do fulfill the functional equation required in Theorem 9. This implies the regularness of the reciprocal image by f of the zeroes of the truncations. The fact that the power series is closely related to a Gaussian hypergeometric function, hence satisfies some second order linear differential equation, turns to be a crucial point here. Experimental observation for few small primes p. -It is an experimental observation, using magma and sage, that for small values of the prime p, the geometric graph G ∞ (P 1 Fp , y 2 =

x 2 +x 3x-1 ) contains a finite 2-regular component with 2(p -1) vertices. In figure 2, we represent this component for p = 5.

Looking for a potentially splitting set for any prime p. -Suppose that there exists, for any prime p ≥ 5, some non-empty finite 2-regular set T = T p in the geometric graph G ∞ (P 1 Fp , y 2 =

x 2 +x 3x-1 ). Note that in this case, this set is unique thanks to It is an easy task using magma to compute χ p (x) for small primes p. Here is the table for p ∈ {5, 7, 11, 13, 17, 23}:

p χ p (x) 5 -1 + 2x + 2x 3 + x 4 7 1 + 3x + x 2 + 2x 3 + 2x 4 -2x 5 + x 6 11 -1 -3x -4x 2 -5x 3 -x 4 -2x 6 -2x 7 + x 8 + 4x 9 + x 10 13 1 + 3x + 2x 2 + 2x 3 + 2x 4 -x 5 + 4x 6 + 4x 7 + 6x 8 + 2x 9 + 5x 10 -4x 11 + x 12 17 -1 -3x + 2x 2 -8x 3 + 7x 4 + 5x 5 + 4x 6 -2x 7 + x 9 -x 10 -7x 11 + 7x 12 -4x 13 -8x 14 + 6x 15 + x 16 19 1 + 3x -4x 2 -2x 3 -7x 4 -2x 5 -5x 7 + 5x 8 + 7x 9 + 7x 10 -6x 11 + 7x 13 + 2x 14 -3x 15 + 3x 16 -6x 17 + x 18 23 -1 -3x + 8x 2 -x 3 + 5x 4 -7x 5 -2x 6 -9x 7 + 9x 8 -9x 9 + 4x 10 + 10x 12 -7x 13 -6x 14 + 8x 15 -7x 16 -2x 17 + 3x 18 -10x 19 + 7x 20 + 8x 21 + x 22
We observe that the constant term is nothing but the Legendre symbol -3 p . So all the polynomials -3 p χ p (x) have unitary constant coefficient. These polynomials can be seen as the analogue for this tower, of the Deuring polynomials for the tame optimal tower already touched on in Subsection 3.2. However, in contrast with this Subsection, we a priori do not know here any theoretical polynomial which could play the part of the Deuring polynomials therein. Fortunately, the Deuring polynomials turn to be the modulo p truncations at degree (p -1) of a power series in Z[[x]]. One can expect that the same holds in our example. More precisely, we want to prove that there exists a power series H(x) = n≥0 a n x n ∈ Z[[x]], such that for all primes p ≥ 5, one has

-3 p χ p (x) = p-1 n=0 a n x n mod p.
In other terms, we want to lift to Z

[[x]] the polynomials -3 p χ p (x) ∈ F p [x]
. Thanks to the Chinese Remainder Theorem and using more and more primes, one can lift the experimentally known polynomials -3 p χ p (x) for small p modulo increasing integers. For example using primes of the preceding tabular, one obtains

H(x) = 1 + 3x + 15x 2 + 93x 3 + 639x 4 + 4653x 5 +
a n = n k=0 n k 2 2k
k .

The associated generating power series H(x) is moreover related to a Gaussian hypergeometric function by

H(x) = ∞ k=0 n k=0 n k 2 2k k an x n = 1 1 -3x F 1/3, 2/3 1 27x 2 (1 -x) (1 -3x) 3 , (9)
where the Gaussian hypergeometric part (see for instance [GKP89, Chap. 5] for hypergeometric series) is

F 1/3, 2/3 1 z = ∞ n=0 1 3 n 2 3 n (1) n n! z n , so that F 1/3, 2/3 1 27z = ∞ n=0 (3n)! (n!) 3 z n .
Here, we denote as usual (a) n def = a(a+1) • • • (a+n-1). We denote by H p (x) ∈ F p [x] the modulo p truncation in degree (p -1) of H:

H p (x) = p-1 n=0 a n x n mod p. ( 10
)
Proof of the splitting behavior. -We have now reached the point where we do have, for any prime p ≥ 5, a candidate for a 2-regular set, namely the set of roots of the explicit polynomial H p (x) defined in (10). The encouraging point is that it is easily checked using magma and sage that for any tested value of p, this set do corresponds to a 2-regular component of the geometric graph.

Lemma 15. Let p ≥ 5 be a prime and let T 0 (depending on p) be the set of roots of the polynomial H p (x) ∈ F p [x] defined in (10). Then f -1 (T 0 ) is 2-regular.

Proof -In order to apply the functional regularness criterion Theorem 9 of which we keep notations, we choose as finite complete set S the support of the singular graph S = 0, ±1, ± 1 3 , ∞ , so that S 0 = 0, 1, 1 9 , ∞ .

The different divisors are

D f (S 0 ) = -1 3 + [1] and D g (S 0 ) = [0] + [∞] ,
hence one can choose the function ρ to be ρ(x) = (x -1) x + 1 3 x ∈ F q (P 1 ).

Since H p (0) ≡ H p (0) ≡ 1 = 0 (mod p), the set T 0 of roots of H p (x) in F p is disjoint from the ramification locus {0, ∞} of g. Since T 0 = deg(H p ) = (p -1), we can try t = 2 and s = p-1 2 . We put ϕ(x) = H p (x) x(x -1) x -1 9 .

After some easy computation similar to those in Subsection 3.2, we see that the functional regularness criterion specializes as follows in this example. For the set f -1 (T 0 ) to be 2-regular, it suffices that the functional equation 1 (3x -1) which proves (i). Now, Gaussian hypergeometric functions are known to be solution of some second order linear differential equation. As for the hypergeometric geometric function F (x) = F 1/3, 2/3 1 x , it satisfies the equation

x(1 -x)F (x) + (1 -2x)F (x) -2 9 F (x) = 0 (see [GKP89, Ex. 5.108 p. 221]). We then deduce (the details of the computations are left to the reader) two second order linear differential equations respectively satisfied by the functions x → 1 1-3x H x 2 +x 3x-1 and x → H(x 2 ). These two equations turn to be proportional. Since the two preceding functions have same value and derivative at zero, they must be equal. This complete the proof of the first functional equation. To prove the second one, it suffices to raise the first one to the power (p -1) and to use point (i). This completes the proofs of (ii).

The last question

We have not yet answered the important question of the value of r, such that λ r T P 1 , y 2 = x 2 +x 3x-1 > 0. The magma experiments for small values of p ≥ 5 show that, at least for these values of p, one has r = 2. Unfortunately, we were not able to prove this. But a close look at Elkies article [START_REF] Elkies | Explicit towers of Drinfeld modular curves[END_REF] leads to the following Proposition, showing that this tower is actually not new.

Proposition 18. The recursive tower T P 1 , y 2 = x 2 +x 3x-1 is isomorphic to the modular tower (X 0 (3 • 2 n )) n≥2 described by Elkies [Elk01]. This tower is asymptotically good, and even optimal, over F p 2 for every prime p outside {2, 3}.

Proof -The model of the tower (X 0 (3 • 2 n )) n≥2 given by Elkies [START_REF] Elkies | Explicit towers of Drinfeld modular curves[END_REF]formula (45)] is the recursive tower with base curve X = P 1 and correspondence Γ f E ,g E defined by the two functions f E (x) = x 2 and g E (y) = y 2 +3y y-1 . One easily verifies that f = σ • f E • τ and g = σ • g E • τ for τ (x) = 3x+1

x-1 and σ(x) = x-1 x-9 .

  the vertices in the connected component of Q. But this set of values is finite since c ∈ F q * . Hence, the function ϕ • f takes only finitely many values on each given connected component. Since ϕ • f is a finite morphism, every connected components is thus finite. Now, the graph G ∞ (X, Γ) being infinite and since since there are only finitely many ramified points by f or g, it must have infinitely many finite d-regular components by Proposition 6, a contradiction with Theorem 19 in[START_REF] Hallouin | Recursive towers of curves over finite fields using graph theory[END_REF] that under the irreducibility assumption, the graph contains at most one d-regular component.

FFigure 2 :

 2 Figure 2: The 2 regular complete component of G ∞ for p = 5

  [HP14, Theorem 19]. Let χ p (x) ∈ F p [x] be the characteristic polynomial of the set of values of f (or g) at the vertices of T p χ p (x) = P ∈Tp (x -x (f (P ))) .

  35169x 6 + 272835x 7 + 33065x 8 + 322285x 9 + 438261x 10 + 43884x 11 + 40470x 12 + 1755x 13 -2202x 14 + 130x 15 -1327x 16 -44x 17 + 20x 18 + 10x 19 -7x 20 -8x 21 -x 22 + • • • ,

	each coefficient being respectively known modulo
	37182145, 37182145, 37182145, 37182145, 37182145, 7436429, 7436429, 1062347, 1062347,
	1062347, 1062347, 96577, 96577, 7429, 7429,
	7429, 7429, 437, 437, 23, 23, 23, 23.

Requesting for the integer sequence 1, 3, 15, 93, 639, 4 653, 35 169 on the Online Encyclopedia of Integer Sequences

[OEI]

, we fortunately learn that these are the first terms of the sequence

  1-p H p Lemma 16. Let n = r i=0 n i p i be the decomposition of n in basis p. Then we have Proof -We recall Lucas formula [Dic66, p. 271] for binomial coefficients modulo a prime p.If n = n 0 + n 1 p + • • • + n r p r and k = k 0 + k 1 p + • • • + k r p r with p i ∈ {0, . . . , p -1}, then(ii)The series H and its truncation H p satisfy the functional equations -3x) 1-p H px 2 + x 3x -1 = H p (x 2 ).Proof -Point (i). We have the following congruences modulo p:H p (x) × H p (x) p × H p (x) p 2 × . . . ≡ H p (x) × H p (x p ) × H p (x p 2 ) × . . .where the first product converges to an invertible function in Z p[[x]]. It follows that

	1 1 -3x	H	x 2 + x 3x -1	= H(x 2 )	and ∞ (1 ≡ p-1	1 a n i x n i p i
									i=0	n i =0
									r
									≡	a n i x n 0 +pn 1 +•••+nrp r
									r∈N;0≤n 0 ,...,nr≤p-1	i=1
									≡	a n x n	(by Lemma 16)
									n∈N
									≡ H(x),
					H(x) 1-p =	H(x) H(x)
									x 2 + x 3x -1	∼ H p x 2	(11)
	holds, which follows from Lemma 17 below.
							a n ≡
							n k	≡	r i=0	n i k i	(mod p).
	From both computations
	a n =	n= r i=0 n i p i k= r i=0 k i p i =0		r i=0 n i p i r i=0 k i p i	2 2k k
	≡	r i=0	p-1 k i =0	r i=0	n i k i	2 2k k	(mod p)	(by Lucas formula)

r i=1 a n i (mod p). p ≡ H p (x) (mod p),

This is the characteristic polynomial of supersingular invariants in characteristic p.

In a forthcoming paper, we intend to prove that one can always reduce the study of a general recursive tower to the study of a recursive tower with separable variables.

We will prove in a forthcoming paper that the singular graph is not finite for the recursive tower X 0 (P n 2 ) over Q( √ 3), whose explicit recursive equation is given in [Elk01, equations (47) and (48)].

Trying with the singular graph in figure1gives as an unique solution (up to Aut(P 1 )) the Garcia-Stichtenoth tower y 2 = x 2 +1 2x !

which takes into account that nr kr = 0 if k r > n r , we have only to prove that for any k = r i=0 k i p i with 0

holds. Suppose first that for any i = 0, . . . , r, we have 0 ≤ k i ≤ p-1 2 . Then 2k = r i=0 2k i p i is the decomposition of 2k in basis p, and (12) follows from Lucas formula. Suppose now that for at least one i ∈ {0, 1, . . . , r}, we have p-1 2 < k i ≤ p -1. Then k i ≤ p -1 < p ≤ 2k i , hence as is well known 2k i k i ≡ 0 (mod p). We now prove that in this case, 2k k ≡ 0 (mod p), so that both sides in (12) vanish. We use Legendre Theorem [Dic66, p. 263] that the p-adic valuation of the factorial n! of an integer n, written in basis p as n = r i=0 n i p i , is given by

where 13), is equivalent to S p (2k) < 2S p (k). We observe that :

• for i ∈ {0, 1, . . . , r} such that k i = p-1 2 + i , with 1 ≤ i ≤ p-1 2 , then 2k i = (2 i -1) + p, with 0 ≤ 2 i -1 ≤ p -1.

Denote by [N ]

i the i-th digit of a composite integer N in basis p, so that

We deduce the following tabular, where contrib. means "contribution to":

from which it follows that v p ( 2k k ) = 0 if, and only if, there exists some 0 ≤ i ≤ r such that p-1 2 < k i . The proof of Lemma 16 is complete.

We are now able to prove that the functional equation (11) holds. We use a Li's trick [Li10, §7.2], which relies this truncated series modulo p to the initial series, and on the fact that hypergeometric functions are solutions of some second order linear differential equations.

Lemma 17. Let H(x) ∈ Z[[x]] be the series defined in (9) and for every prime p, let H p (x) ∈ F p [x] be the degree (p -1) -th truncation of H(x) modulo p defined in (10).

(i) The series H and its truncation H p modulo p are related by the relation H(x) 1-p ≡ H p (x) (mod p).