Recursive p-adics

Straight-line programs

Straight-line programs are a model of computation that consist in ordered lists of instructions without branching. We give a short presentation of this notion and refer to [BCS97] for more details. We will use this model of computation to describe and analyze the forthcoming recursive operators and shifted algorithms. Let R be a ring and A an R-algebra. A straight-line program (s.l.p.) is an ordered sequence of operations between elements of A. An operation of arity r is a map from a subset D of Ar to A. We usually work with the binary arithmetic operators +, −, ·: D = A2→A. We also define for r ∈ R the 0-ary operations r c whose output is the constant r and the unary scalar multiplication r × _ by r. We denote the set of all these operations by Rc and R. Let us fix a set of operations Ω, usually Ω = {+, −, ·} ∪ R ∪ Rc . An s.l.p. starts with a number ℓ of input parameters indexed from −(ℓ − 1) to 0. It has L instructions Γ1, , ΓL with Γi = (ωi ; ui,1, , ui,ri ) where −ℓ < ui,1, , ui,ri < i and ri is the arity of the operation ωi ∈ Ω. The s.l.p. Γ is executable on a= (a0, , aℓ−1) with result sequence b= (b−ℓ+1, , bL)∈Aℓ+L , if bi=aℓ−1+i whenever −(ℓ −1)6i60 and bi=ωi(bu,1, , bu,ri ) with (bu,1, , bu,ri )∈ Dωi whenever 16i6L. We say that the s.l.p. Γ computes b∈ A on the entries a1, , aℓ if Γ is executable on a1, , aℓ over A and b is a member of the result sequence. The multiplicative complexity L ∗ (Γ) of an s.l.p. Γ is the number of operations ωi that are multiplications · between elements of A. Example 2.1. Let R=Z, A=Z[X, Y ] and Γ be the s.l.p. with two input parameters indexed −1, 0 and Γ1 = (·; −1, −1), Γ2 = (·; 1, 0), Γ3 = (1c ), Γ4 = (−; 2, 3), Γ5 = (3 × _; 1). First, its multiplicative complexity is L ∗ (Γ) = 2. Then, Γ is executable on (X, Y )∈ A2 , and for this input its result sequence is (X, Y , X2 , X2 Y , 1, X2 Y −1, 3 X2 ). Remark 2.2. For the sake of simplicity, we will associate a “canonical” arithmetic expression with an s.l.p. It is the same operation as when one writes an arithmetic expression in a programming language, e.g. C, and a compiler turns it into an s.l.p. In our case, we fix an arbitrary compiler that starts by the left-hand side of an arithmetic expression. We use the binary powering algorithm to compute powers of an expression. For example, the arithmetic expression ϕ:Z  Z 4 + 1 can be represented by the s.l.p. with one argument and instructions Γ1 = (·; 0, 0), Γ2 = (·; 1, 1), Γ3 = (1c ), Γ4 = (+; 2, 3).

Recursive p-adics

The study of on-line algorithms is motivated by its efficient implementation of recursive p-adics. To the best of our knowledge, the paper [Wat89] was the first to mention the lazy computation of power series which are solutions of a fixed point equation y = Φ(y). The paper [Hoe02], in addition to rediscovering the fast on-line multiplication algorithm of [FS74], connected for the first time this fast multiplication algorithm to the on-line computation of recursive power series. Van der Hoeven named these on-line algorithms, that use the fast on-line multiplication, relaxed algorithms. Article [BHL11] generalizes relaxed algorithms for p-adics. We contribute by clarifying the setting in which recursive p-adics can be computed from their fixed point equations y = Φ(y) by an on-line algorithm. For this matter, we introduce the notion of shifted algorithm. We will work with recursive p-adics in a simple case and do not need the general context of recursive p-adics [Kap01, Definition 7]. We denote by νp(a) the valuation in p of the p-adic a. For vectors or matrices A ∈ Mr×s(Rp), we define νp(A) 7 mini,j (νp(Ai,j)). We start by giving a definition of recursive p-adics and their recursive equation that suits our needs. Definition 2.3. Let ℓ∈ N, Φ ∈(Rp[Y1, , Yℓ])ℓ , y ∈(Rp) ℓ be a fixed point of Φ, i.e. y = Φ(y). We write y = P i∈N yi p i the p-adic decomposition of y. Let us denote Φ0 = Id and, for all n ∈ N ∗ , Φn = Φ ◦ ◦ Φ (n times). Then, we say that the coordinates (y1, , yℓ) of y are recursive p-adics and that the recursive operator Φ allows the computation of y if, for all n ∈ N, we have νp(y − Φn (y0)) > n + 1. The general case with more initial conditions y0, y1, , ys is not considered here but we believe it would to be an interesting extension of these results. Proposition 2.4. Let Φ ∈ (Rp[Y1, , Yℓ])ℓ with a fixed point y ∈ Rp ℓ and let y0 = y rem p. Suppose νp(JacΦ(y0)) > 0. Then Φ allows the computation of y. Moreover, for all n 6 m ∈ N ∗ , the p-adic coefficient (Φ(y))n does not depend on the coefficient ym, i.e. (Φ(y))n = (Φ(y + a))n for any a ∈ (p n Rp) ℓ . 

Shifted algorithms

Because of the issue raised in Warning 2.6, we need to make explicit the fact that yN is not read at step N of the computation of Φ(y). This issue was never mentioned in the literature before. In this section, we define the notion of shifted algorithms and prove that these algorithms compute correctly recursive p-adics by the on-line method of previous section. We introduce for all s in N ∗ two new operators: p s × _: Rp → Rp _/p s : p s Rp → Rp a  p s a, a  a/p s . The implementation of these operators just moves (or shifts) the coefficients of the input. It does not call any multiplication algorithm.