Ignacio García-Marco

Pascal Koiran

Timothée Pecatte Lip

Reconstruction Algorithms for Sums of Affine Powers

α i (x -a i ) ei .
Although quite simple, this model is a generalization of two well-studied models: Waring decomposition and Sparsest Shift. For these three models there are natural extensions to several variables, but this paper is mostly focused on univariate polynomials. We present structural results which compare the expressive power of the three models; and we propose algorithms that find the smallest decomposition of f in the first model (sums of affine powers) for an input polynomial f given in dense representation. We also begin a study of the multivariate case.

This work could be extended in several directions. In particular, just as for Sparsest Shift and Waring decomposition, one could consider extensions to "supersparse" polynomials and attempt a fuller study of the multivariate case. We also point out that the basic univariate problem studied in the present paper is far from completely solved: our algorithms all rely on some assumptions for the exponents e i in a decomposition of f , and some algorithms also rely on a distinctness assumption for the shifts a i . It would be very interesting to weaken these assumptions, or even to remove them entirely. Another related and poorly understood issue is that of the bit size of the constants a i , α i in an optimal decomposition: is it always polynomially related to the bit size of the input polynomial f given in dense representation?

Introduction

Let F be any characteristic zero field and let f ∈ F[x] be a univariate polynomial. This work concerns the study of expressions of f as a linear combination of powers of affine forms.

Model 1.1. We consider expressions of f of the form:

f = s i=1 α i (x -a i ) e i
with α i , a i ∈ F, e i ∈ N. We denote by AffPow F (f ) the minimum value s such that there exists a representation of the previous form with s terms.

This model was already studied in [START_REF] García-Marco | Lower bounds by Birkhoff interpolation[END_REF], where we gave explicit examples of polynomials of degree d requiring AffPow R (f ) = Ω(d) terms for the field F = R.

The main goal of this work is to design algorithms that reconstruct the optimal representation of polynomials in this model, i.e., algorithms that receive as input f ∈ F[x] and compute the exact value s = AffPow F (f ) and a set of triplets of coefficients, nodes and exponents {(α i , a i , e

i ) | 1 ≤ i ≤ s} ⊆ F × F × N such that f = s i=1 α i (x -a i ) e i .
We assume that f is given in dense representation, i.e., as a tuple of deg(f ) + 1 elements of F. Model 1.1 extends two already well-studied models. The first one is the Waring model, where all the exponents are equal to the degree of the polynomial, i.e., e i = deg(f ) for all i.

Model 1.2. For a polynomial f of degree d, we consider expressions of f of the form:

f = s i=1 α i (x -a i ) d
with α i , a i ∈ F. We denote by Waring F (f ) the Waring rank of f , which is the minimum value s such that there exists a representation of the previous form with s terms.

Waring rank has been studied by algebraists and geometers since the 19th century. The algorithmic study of Model 1.2 is usually attributed to Sylvester. We refer to [START_REF] Iarrobino | Power sums, Gorenstein algebras, and determinantal loci. Appendix C by Iarrobino and[END_REF] for the historical background and to section 1.3 of that book for a description of the algorithm (see also Kleppe [17] and Proposition 46 of Kayal [START_REF]Affine projections of polynomials[END_REF]). Most of the subsequent work was devoted to the multivariate generalization 1 of Model 1.2, with much of the 20th century work focused on the determination of the Waring rank of generic polynomials [START_REF] Alexander | Polynomial interpolation in several variables[END_REF][START_REF] Chiara | On the Alexander -Hirschowitz theorem[END_REF][START_REF] Iarrobino | Power sums, Gorenstein algebras, and determinantal loci. Appendix C by Iarrobino and[END_REF]. A few recent papers [START_REF] Joseph | On the ranks and border ranks of symmetric tensors[END_REF][START_REF] Boij | Monomials as sums of powers: the real binary case[END_REF] have begun to investigate the Waring rank of specific polynomials such as monomials, sums of coprime monomials, the permanent and the determinant.

The second model that we generalize is the Sparsest Shift model, where all the shifts a i are required to be equal.

Model 1.3. For a polynomial f , we consider expressions of f of the form:

f = s i=1 α i (x -a) e i
with α i , a ∈ F, e i ∈ N. We denote by Sparsest F (f ) the minimum value s such that there exists a representation of the previous form with s terms. This model and its variations have been studied in the computer science literature at least since Borodin and Tiwari [START_REF] Borodin | On the decidability of sparse univariate polynomial interpolation[END_REF]. Some of these papers deal with multivariate generalizations [START_REF] Grigoriev | A zero-test and an interpolation algorithm for the shifted sparse polynomials[END_REF][START_REF] Giesbrecht | Algorithms for computing sparsest shifts of polynomials in power, Chebyshev and Pochhammer bases[END_REF], with "supersparse" polynomials2 [START_REF] Giesbrecht | Interpolation of shifted-lacunary polynomials[END_REF] or establish condition for the uniqueness of the sparsest shift [START_REF] Lakshman | Sparse shifts for univariate polynomials[END_REF]. It is suggested at the end of [START_REF] Giesbrecht | Algorithms for computing sparsest shifts of polynomials in power, Chebyshev and Pochhammer bases[END_REF] to allow "multiple shifts" instead of a single shift, and this is just what we do in this paper. More precisely, as is apparent from Model 1.1, we do not place any constraint on the number of distinct shifts: it can be as high as the number s of affine powers. It would also make sense to place an upper bound k on the number of distinct shifts. This would provide a smooth interpolation between the sparsest shift model (where k = 1) and Model 1.1, where k = s.

Our results

We provide both structural and algorithmic results. Our structural results are presented in Section 3. We compare the expressive power of our 3 models: sums of affine powers, sparsest shift and the Waring decomposition. Namely, we show that some polynomials have a much smaller expression as a sum of affine powers than in the sparsest shift or Waring models. Moreover, we show that the Waring and sparsest shift models are "orthogonal" in the sense that (except in one trivial case) no polynomial can have a small representation in both models at the same time. We also show that some real polynomials have a short expression as a sum of affine powers over the field of complex numbers, but not over the field of real numbers. Finally, we study the uniqueness of the optimal representation as a sum of affine powers. It turns out that our reconstruction algorithms only work in a regime where the uniqueness of optimal representations is guaranteed.

As already explained, we present algorithms that find the optimal representation of an input polynomial f . We achieve this goal in several cases, but we do not solve the problem in its full generality. One typical result is as follows (see Theorem 4.5 in Section 4 for a more detailed statement which includes a description of the algorithm).

Theorem 1.4. Let f ∈ F[x] be a polynomial that can be written as

f = s i=1 α i (x -a i ) e i ,
where the constants a i ∈ F are all distinct, α i ∈ F \ {0}, and e i ∈ N. Assume moreover that n i ≤ (3i/4) 1/3 -1 for all i ≥ 2, where n i denotes the number of indices j such that e j ≤ i.

Then, AffPow F (f ) = s. Moreover, there is a polynomial time algorithm that receives f = d i=0 f i x i ∈ F[x] as input and computes the s-tuples of coefficients C(f ) = (α 1 , . . . , α s ), of nodes N (f ) = (a 1 , . . . , a s ) and exponents E(f ) = (e 1 , . . . , e s ).

From the point of view of the optimality of representations, it is quite natural to assume an upper bound on the numbers n i . Indeed, if there is an index j such that n j > j + 1 then the powers (xa i ) e i are linearly dependent, and there would be a smaller expression of f as a linear combination of these polynomials. 3 We would therefore have AffPow F (f ) < s instead of AffPow F (f ) = s. It would nonetheless be interesting to relax the assumption n i ≤ (3i/4) 1/3 -1 in this theorem. Another restriction is the assumption that the shifts a i are all distinct. We relax that assumption in Section 5 but we still need to assume that all the exponents e i corresponding to a given shift a i = a belong to a "small" interval (see Theorem 5.3 for a precise statement). Alternatively, we can assume instead that there is a large gap between the exponents in two consecutive occurences of the same shift as in Theorem 5. [START_REF] Cox | Galois theory[END_REF].

In Section 6 we extend the sum of affine powers model to several variables. We consider expressions of the form

f (x 1 , . . . , x n ) = s i=1 α i ℓ i (x 1 , . . . , x n ) e i , (1)
where e i ∈ N, α i ∈ F and ℓ i is a (non constant) linear form for all i. This is clearly a generalization of the univariate model 1.1 and of multivariate Waring decomposition. Work on multivariate sparsest shift has developed in a different direction: one idea [START_REF] Giesbrecht | Algorithms for computing sparsest shifts of polynomials in power, Chebyshev and Pochhammer bases[END_REF] has been to transform the input polynomial into a sparse polynomial by applying a (possibly) different shift to each variable. The model from [START_REF] Grigoriev | A zero-test and an interpolation algorithm for the shifted sparse polynomials[END_REF] is more general than [START_REF] Giesbrecht | Algorithms for computing sparsest shifts of polynomials in power, Chebyshev and Pochhammer bases[END_REF], and we do not generalize any of these two models. Our algorithmic strategy for reconstructing expressions of the form ( 1) is to transform the multivariate problem into univariate problems by projection, and to "lift" the solution of n different projections to the solution of the multivariate problem. This can be viewed as an analogue of "case 1" of Kayal's algorithm for Waring decomposition [START_REF]Affine projections of polynomials[END_REF]Theorem 5].

Main tools

Most of our results 4 hinge on the study of certain differential equations satisfied by the input polynomial f . We consider differential equations of the form

k i=0 P i (x)f (i) = 0 (2)
where the P i 's are polynomials. If the degree of P i is bounded by i + l for every i, we say that (2) is a Shifted Differential Equation (SDE) of order k and shift l. Section 2 recalls some (mostly standard) background on differential equations and the Wronskian determinant. When f is a polynomial with an expression of size s in Model 1.1 we prove in Proposition 2.6 that f satisfies a "small" SDE, of order 2s -1 and shift zero. The basic idea behind our algorithms is to look for one of these "small" SDEs satisfied by f , and hope that the powers (xa i ) e i in an optimal decomposition of f satisfy the same SDE. This isn't just wishful thinking because the SDE from Proposition 2.6 is satisfied not only by f but also by the powers (xa i ) e i .

Unfortunately, this basic idea by itself does not yield efficient algorithms. The main difficulty is that f could satisfy several SDE of order 2s -1 and shift 0. By Remark 2.7 we can efficiently find such a SDE, but what if we don't find the "right" SDE, i.e., the SDE which (by Proposition 2.6) is guaranteed to be satisfied by f and by the powers (xa i ) e i ? One way around this difficulty is to assume that the exponents e i are all sufficiently large compared to s. In this case we can show that every SDE of order 2s -1 and shift 0 which is satisfied by f is also satisfied by (xa i ) e i . This fact is established in Corollary 4.2, and yields the following result (see Theorem 4.3 in Section 4 for a more detailed statement which includes a description of the algorithm).

Theorem 1.5 (Big exponents). Let f ∈ F[x] be a polynomial that can be written as

f = s i=1 α i (x -a i ) e i ,
where the constants a i ∈ F are all distinct, α i ∈ F \ {0} and e i > 5s 2 /2. Then, AffPow F (f ) = s. Moreover, there is a polynomial time algorithm that receives

f = d i=0 f i x i ∈ F[x]
as input and computes the s-tuples of coefficients C(f ) = (α 1 , . . . , α s ), of nodes N (f ) = (a 1 , . . . , a s ) and exponents E(f ) = (e 1 , . . . , e s ).

The algorithm of Theorem 1.4 is more involved: contrary to Theorem 1.5, we cannot determine all the terms (xa i ) e i in a single pass. Solving the SDE only allows the determination of some (high degree) terms. We must then subtract these terms from f , and iterate.

In the first version of this paper, 5 instead of a SDE(2s -1, 0) we used a SDE of order s and shift s 2 originating from the Wronskian determinant (compare the two versions of Proposition 2.6). Switching to the new SDE led to significant improvements in most of our algorithmic results. For instance, in the first version of Theorem 1.5 the exponents e i had to satisfy the condition e i > s 2 (s + 1)/2 instead of the current (less stringent) condition e i > 5s 2 /2.

Models of computation

Our algorithms take as inputs polynomials with coefficients in an arbitrary field K of characteristic 0. At this level of generality, we need to be able to perform arithmetic operations (additions, multiplications) and equality tests between elements of K. When we write that an algorithm runs in polynomial time, we mean that the number of such steps is polynomial in the input size. This is a fairly standard setup for algebraic algorithms (it is also interesting to analyze the bit complexity of our algorithms for some specific fields such as the field of rational numbers; more on this at the end of this subsection and in Section 1.4). An input polynomial of degree d is represented simply by the list of coefficients of its d + 1 monomials, and its size thus equals d + 1. In addtion to arithmetic operations and equality tests, we need to to be able to compute roots of polynomials with coefficients in K. This is in general unavoidable: for an an optimal decomposition of f ∈ K[X] in Model 1.1, the coefficients α i , a i may lie in an extension field F of K (see Section 3 and more precisely Example 3.3 in Section 3.1 for the case K = R, F = C). If the optimal decomposition has size s, we need to compute roots of polynomials of degree at most 2s -1. 6 As a rule, root finding is used only to output the nodes a i of the optimal decomposition, 7 but the "internal working" of our algorithms remains purely rational (i.e., requires only arithmetic operations and comparisons). This is similar to the symbolic algorithm for univariate sparsest shifts of Giesbrecht, Kaltofen and Lee ( [START_REF] Giesbrecht | Algorithms for computing sparsest shifts of polynomials in power, Chebyshev and Pochhammer bases[END_REF], p. 408 of the journal paper), which also needs access to a polynomial root finder.

The one exception to this rule is the algorithm of Theorem 1.4. As mentioned at the end of Section 1.2, this is an iterative algorithm. At each step of the iteration we have to compute roots of polynomials (which may lie outside K), and we keep computing with these roots in the subsequent iterations. For more details see Theorem 4.5 and the discussion after that theorem. We make a first step toward removing root finding from the internal working of this algorithm in Proposition 4.6.

We also take some steps toward the analysis of our algorithms in the bit model of computation. We focus on the algorithm of Theorem 1.4 since it is the most difficult to analyze due to its iterative nature. We show in Proposition 4.7 that for polynomials with integer coefficients, this algorithm can be implemented in the bit model to run in time polynomial in the bit size of the output. We do not have a polynomial running time bound as a function of the input size (more on this in Section 1.4). We also compute explicitly a polynomial bound on the running time of the simpler algorithm of Theorem 4.3, which deals with the case of "big exponents". Our bound is of fairly large degree and is probably not optimal.

Future work

One could try to extend the results of this paper in several directions. For instance, one could try to handle "supersparse" polynomials like in the Sparsest Shift algorithm of [START_REF] Giesbrecht | Interpolation of shifted-lacunary polynomials[END_REF]. The multivariate case would also deserve further study. As explained above we proceed by reduction to the univariate case, but one could try to design more "genuinely multivariate" algorithms. For Waring decomposition, such an algorithm is proposed in "case 2" of [START_REF]Affine projections of polynomials[END_REF]Theorem 5]. Its analysis relies on a randomness assumption for the input f (our multivariate algorithm is randomized, but in this paper we never assume that the input polynomial is randomized).

One should also keep in mind, however, that the basic univariate problem studied in the present paper is far from completely solved: our algorithms all rely on some assumptions for the exponents e i in a decomposition of f , and some 6 Except in the algorithm of Theorem 5.3, where we need to compute roots of polynomials at most 2s -1 + δ. Here δ is a parameter of the algorithm, see Theorem 5.3 for details. 7 Once the ai's have been determined, we also need to do some linear algebra computations with these nodes to determine the coefficients αi.

algorithms also rely on a distinctness assumption for the shifts a i . It would be very interesting to weaken these assumptions, or even to remove them entirely. With a view toward this question, one could first try to improve the lower bounds from [START_REF] Kayal | Lower bounds for sums of powers of low degree univariates[END_REF]. Indeed, the same tools (Wronskians, shifted differential equations) turn out to be useful for the two problems (lower bounds and reconstruction algorithms) but the lower bound problem appears to be easier. For real polynomials we have already obtained optimal Ω(d) lower bounds in [START_REF] García-Marco | Lower bounds by Birkhoff interpolation[END_REF] using Birkhoff interpolation, but it remains to give an algorithmic application of this lower bound method.

Another issue that we have only begun to address is the analysis of the bit complexity of our algorithms. We give an explicit polynomial bound on the bit complexity of the algorithm of Theorem 4.3, but this issue seems to be more subtle for Theorem 1.4 due to the iterative nature of our algorithm. It is in fact not clear that there exists a solution of size polynomially bounded in the input size (i.e., in the bit size of f given as a sum of monomials). More precisely, we ask the following question.

Question 1.6. We define the dense size of a polynomial f

= d i=0 f i x i ∈ Z[X] as d i=0 [1 + log 2 (1 + |f i |)].
Assume that f can be written as

f = s i=1 α i (x -a i ) e i
with a i ∈ Z, α i ∈ Z \ {0}, and that this decomposition satisfies the conditions of Theorem 1.4: the constants a i are all distinct, and n i ≤ (3i/4) 1/3 -1 for all i ≥ 2, where n i denotes the number of indices j such that e j ≤ i. Is it possible to bound the bit size of the constants α i , a i by a polynomial function of the dense size of f ? As explained at the end of Section 1.3, under the same conditions we have a decomposition algorithm that runs in time polynomial in the bit size of the output. It follows that the above question has a positive answer if and only if there is a decomposition algorithm that runs in time polynomial in the bit size of the input (i.e., in time polynomial in the dense size of f ).

One could also ask similar questions in the case where the conditions of Theorem 1.4 do not hold. For instance, assuming that f has an optimal decomposition with integer coefficients, is there such a decomposition where the coefficients α i , a i are of size polynomial in the size of f ?

Preliminaries

In this section we present some tools that are useful for their algorithmic applications in Sections 4 and 5. Section 3 can be read independently, except for the proof of Proposition 3.11 and Theorem 5.3 which use the Wronskian.

The Wronskian

In mathematics the Wronskian is a tool mainly used in the study of differential equations, where it can be used to show that a set of solutions is linearly independent.

Definition 2.1 (Wronskian). For n univariate functions f 1 , . . . , f n , which are n-1 times differentiable, the Wronskian Wr(f 1 , . . . , f n ) is defined as

Wr(f 1 , . . . , f n )(x) = f 1 (x) f 2 (x) . . . f n (x) f ′ 1 (x) f ′ 2 (x) . . . f ′ n (x) . . . . . . . . . . . . f (n-1) 1 f (n-1) 2 . . . f (n-1) n
It is a classical result, going back at least to [START_REF] Bocher | The theory of linear dependence[END_REF], that the Wronskian captures the linear dependence of polynomials in F[x].

Proposition 2.2. For f 1 , . . . , f n ∈ F[X], the polynomials are linearly dependent if and only if the Wronskian Wr(f 1 , . . . , f n ) vanishes everywhere.

For every f ∈ F[x] and every a ∈ F we denote by M a (f ) the multiplicity of a as a root of f , i.e., M a (f ) is the maximum t ∈ N such that (xa) t divides f . The following result from [START_REF] Voorhoeve | Wronskian determinants and the zeros of certain functions[END_REF] gives a Wronskian-based bound on the multiplicity of a root in a sum of polynomials.

Lemma 2.3. Let f 1 , . . . , f n be some linearly independent polynomials and a ∈ F, and let f (x) = n j=1 f j (x). Then:

M a (f ) ≤ n -1 + M a (Wr(f 1 , . . . , f n )) ,
where M a (f ) is finite since Wr(f 1 , . . . , f n ) ≡ 0.

In [START_REF] Pólya | Problems and theorems in analysis[END_REF] one can find several properties concerning the Wronskian (and which have been known since the 19 th century). In this work we will use the following properties, which can be easily derived from those of [START_REF] Pólya | Problems and theorems in analysis[END_REF]. For the sake of completeness we include a short proof. Proposition 2.4. Let f 1 , . . . , f n ∈ F[x] be linearly independent polynomials and let a ∈ F.

If f j = Q d j j g j with Q j ∈ F[x] and d j ≥ n for all j, then Q := n j=1 Q d j -n+1 j divides Wr(f 1 , . . . , f n ). Moreover, if Q(a) = 0, then M a (Wr(f 1 , . . . , f n )) ≤ n j=1 deg(g j ) + (n -1)deg(Q j ) - n 2 .
Hence, if we set f := n j=1 f j , then

M a (f ) ≤ n -1 + n j=1 deg(g j ) + (n -1)deg(Q j ) - n 2 .
Proof. Consider the n×n Wronskian matrix W whose (i+1, j)-th entry is f

(i) j (x) with 0 ≤ i ≤ n -1, 1 ≤ j ≤ n. Since Q d j j divides f j , then f (i) j = Q d j -i j g i,j = Q d j -n+1 j Q n-1-i j g i,j , for some g i,j ∈ F[x] of degree deg(g j ) + i deg(Q j ) -i. Since Q d j -n+1 j
divides every element in the j-th column of W , we can factor it out from the Wronskian. This proves that Q divides Wr(f 1 , . . . , f n ). Once we have factored out Q d j -n+1 j for all j, we observe that Wr(f 1 , . . . , f n ) = Q(x) h(x), where h(x) is the determinant of a matrix whose (i + 1, j)-th entry has degree deg(g j ) + (n -1)deg(Q j )i for all 0 ≤ i ≤ n -1 and 1 ≤ j ≤ n. Hence, deg(h)

≤ n j=1 [deg(g j ) + (n -1)deg(Q j )] -n 2 .
Finally, we observe that if

Q(a) = 0: M a (Wr(f 1 , . . . , f n )) = M a (Q) + M a (h) = M a (h) ≤ deg(h).
For f = n j=1 f j , the upper bound for M a (f ) follows directly from Lemma 2.3.

✷

We observe that the result holds when some of the Q i (x) = 1.

Shifted Differential Equations

Definition 2.5. A Shifted Differential Equation (SDE) is a differential equation of the form

k i=0 P i (x)f (i) (x) = 0
where f is the unknown function and the P i are polynomials in

F[x] with deg(P i ) ≤ i + l.
The quantity k is called the order of the equation, and the quantity l is called the shift. We will usually denote such a differential equation by SDE(k, l).

One of the key ingredients for our results is that if AffPow(f ) is small, then f satisfies a "small" SDE. More precisely: Proposition 2.6. Let δ ∈ Z + and let f ∈ F[x] be written as

f = t i=1 Q i (x)(x -a i ) e i .
where a i ∈ F, e i ∈ N and deg(Q i (x)) ≤ δ for all i.

Then, f satisfies a SDE(2t -1, δ) which is also satisfied by the t terms

f i (x) = Q i (x)(x-a i ) e i . In particular, if AffPow F (f ) = s, then f satisfies a SDE(2s-1, 0).
Proof. If we can find a SDE(2t -1, δ) which is satisfied by all the f i , by linearity the same SDE will be satisfied by f and the theorem will be proved. The existence of this common SDE is equivalent to the existence of a nonzero solution for the following linear system in the unknowns a j,k :

j,k a j,k x j f (k) i (x) = 0, where 1 ≤ i ≤ t, 0 ≤ k ≤ 2t -1 and 0 ≤ j ≤ k + δ. There are (δ + 1) + (δ + 2) + • • • + (δ + 2t) = (2δ + 2t + 1)
t unknowns, so we need to show that the matrix of this linear system has rank smaller than (2δ + 2t + 1)t. It suffices to show that for each fixed value of i ∈ {1, . . . , t}, the subsystem:

j,k a j,k x j f (k) i (x) = 0 (0 ≤ k ≤ 2t -1, 0 ≤ j ≤ k + δ)
has a matrix of rank < 2δ + 2t + 1. In other words, we have to show that the subspace V i spanned by the polynomials x j f (k) i (x) has dimension less than 2δ + 2t + 1. But V i is included in the subspace spanned by the polynomials

{(x -a i ) e i +j ; -(2t -1) ≤ j ≤ δ, e i + j ≥ 0}.
This is due to the fact that the polynomials x j and Q i (x) belong respectively to the spans of the polynomials {(x -

a i ) ℓ | 0 ≤ ℓ ≤ j}, and {(x -a i ) ℓ | 0 ≤ ℓ ≤ δ}. We conclude that dim V i ≤ 2t + δ < 2δ + 2t + 1. ✷ Remark 2.7.
A polynomial f satisfies a SDE(k, l) if and only if the polynomials (x j f (i) (x)) 0≤i≤k,0≤j≤i+l are linearly dependent over F. The existence of such a SDE can therefore be decided efficiently by linear algebra, and when a SDE(k, l) exists it can be found explicitly by solving the corresponding linear system (see, e.g., [START_REF] Schrijver | Theory of linear and integer programming[END_REF]Corollary 3.3a] for an analysis of linear system solving in the bit model of computation). We use this fact repeatedly in the algorithms of Sections 4 and 5.

In this paper we will use some results concerning the set of solutions of a SDE. They are particular cases of properties that apply to linear homogeneous differential equations.

Lemma 2.8. The set of polynomial solutions of a SDE of order k is a vector space of dimension at most k.

Given two SDE of order k:

k i=0 p i (x)g (i) (x) = 0 and k i=0 q i (x)g (i) (x) = 0,
we say that they are equivalent if p k q i = q k p i for all i ∈ {0, . . . , k -1}. The following result can be found in [23, Property 61] and will only be used in the appendix. We include a short proof. Lemma 2.9. For any set of F-linearly independent polynomials f

1 , . . . , f k ∈ F[x],
there exists a unique SDE (up to equivalence) of order k satisfied simultaneously by all the f i 's.

Proof. Suppose there exist two different SDE satisfied by f 1 , . . . , f k , namely:

k i=0 p i (x)g (i) (x) = 0 and k i=0 q i (x)g (i) (x) = 0.
Then, we set r i := p k q iq k p i for all i ∈ {0, . . . , k}. By definition we have that r k = 0 and we aim at proving that r i = 0 for all i. Assume that there exists j ∈ {0, . . . , k -1} such that r j = 0. Then, the following SDE

k-1 i=0 r i (x) g (i) (x) = 0 has order ≤ k -1 and is satisfied by f 1 , . . . , f k , a contradiction to Lemma 2.8. ✷

Structural results

In this section we compare the expressive power of our 3 models: sums of affine powers, sparsest shift and the Waring decomposition. We will see in Section 3.2 that some polynomials have a much smaller expression as a sum of affine powers than in the sparsest shift or Waring models. Moreover, we show that the Waring and sparsest shift models are "orthogonal" in the sense that (except in one trivial case) no polynomial can have a small representation in both models at the same time.

We begin this investigation of structural properties with the field of real numbers, where an especially strong version of orthogonality holds true. We also show that some real polynomials have a short expression as a sum of affine powers over the field of complex numbers, but not over the field of real numbers. This observation has algorithmic implications: given a polynomial f ∈ F[X], we may have to work in a field extension of F to find the optimal representation for f . These "real" results can be derived fairly quickly from results in our previous paper [START_REF] García-Marco | Lower bounds by Birkhoff interpolation[END_REF]. We then move to arbitrary fields of characteristic zero in Section 3.2. Finally, we study the uniqueness of optimal representations in Section 3.3. It turns out that the algorithms of Sections 4 and 5 only work in a regime where the uniqueness of optimal representations is guaranteed.

The real case

In [START_REF] García-Marco | Lower bounds by Birkhoff interpolation[END_REF] the authors considered polynomials with real coefficients and proved the following result.

Theorem 3.1. [9, Theorem 13] Consider a polynomial identity of the form:

k i=1 α i (x -a i ) d = l i=1 β i (x -b i ) e i
where the a i ∈ R are distinct constants, the constants α i ∈ R are not all zero, the β i ∈ R and b i ∈ R are arbitrary constants, and e i < d for every i. Then, we must have k + l ≥ ⌈(d + 3)/2⌉. Theorem 3.1 will be our main tool in Section 3.1. As a consequence of this result, we first give a sufficient condition for a polynomial to have a unique optimal expression in the model AffPow R .

Corollary 3.2. Let f ∈ R[x] be a polynomial of the form: f = s i=1 α i (x -a i ) e i ( 3
)
with α i = 0.
For every e ∈ N we denote by n e the number of exponents smaller than e, i.e., n e = #{i : e i ≤ e}.

If 2n e ≤ ⌈(e + 3)/2⌉ for all e ∈ N, then AffPow R (f ) = s. Moreover, if 2n e < ⌈(e + 3)/2⌉ for all e then (3) is the unique optimal expression for f .

Proof. Suppose that f can be written in another way

f = p j=1 β j (x -b j ) f j (4) with p ≤ s. Set d = max ((e i ) 1≤i≤s ∪ (f j ) 1≤j≤p ) and denote by s ′ (respectively, p ′ ) the index such that d = e 1 = • • • = e s ′ > e s ′ +1 ≥ • • • ≥ e s (respectively, d = f 1 = • • • = f p ′ > f p ′ +1 ≥ • • • ≥ f p ).
Note that one of the two indices s ′ , p ′ will be equal to 0 if the exponent d appears only in one of the two expressions ( 3) and ( 4).

Combining equations ( 3) and ( 4), we obtain the following equality:

s ′ i=1 α i (x -a i ) d - p ′ j=1 β j (x -b j ) d = - s i=s ′ +1 α i (x -a i ) e i + p j=p ′ +1 β j (x -b j ) f j
We can rewrite this as

k i=1 α ′ i (x -a ′ i ) d = l i=1 β ′ i (x -b ′ i ) e ′ i with α ′ i = 0, k ≤ s ′ + p ′ and l ≤ (s -s ′ ) + (p -p ′ ).
To prove the first assertion, let us assume that 2n e ≤ ⌈(e + 3)/2⌉ for all e. Assume also for contradiction that p < s and k > 0. By Theorem 3.1, we must have k + l ≥ ⌈(d + 3)/2⌉. The upper bounds on k and l imply 2s > s + p ≥ k + l ≥ ⌈(d+3)/2⌉. However we have from our assumption that 2s = 2n d ≤ 2⌈(d+3)/2⌉, which contradicts the previous inequality. This shows that p < s ⇒ k = 0, i.e., if p < s then the highest degree terms are the same. Continuing by induction, we find that all the terms in the two expressions are equal. In particular we would have p = s, a contradiction. This shows that p ≥ s, i.e., that AffPow R (f ) = s.

To prove the second assertion, let us now assume further that 2n e < ⌈(e + 3)/2⌉ for all e. Assume also that p = s. By Theorem 3.1, either k = 0 or k + l ≥ ⌈(d + 3)/2⌉. In the second case, the upper bounds on k and l imply that 2s = s+p ≥ k +l ≥ ⌈(d+3)/2⌉. This is in contradiction with the assumption that 2n d < ⌈(d + 3)/2⌉. We conclude that that k must be equal to 0, i.e., the highest degree terms are the same. Continuing by induction, we obtain that all the terms of the two decompositions are equal, thus showing that (3) is the unique optimal expression for f in this model. ✷ Let K be a field extension of F. Theorem 1 in [START_REF] Lakshman | Sparse shifts for univariate polynomials[END_REF] shows that whenever the value Sparsest K (f ) is "small", then it is equal to Sparsest F (f ); more precisely, if Sparsest K (f ) ≤ (d + 1)/2 then Sparsest K (f ) = Sparsest F (f ). This is no longer the case for the Affine Power model as the following example shows.

Example 3.3. For every d ∈ N, we consider the polynomial

f d := j≡3 (mod 4) 0≤j≤d 4 d j x d-j ∈ R[x]. (5)
We can express f d as

f d = (x+ 1) d -(x-1) d + i(x+ i) d -i(x-i) d , which proves that AffPow C (f d ) ≤ 4.
Moreover, in expression [START_REF] Boij | Monomials as sums of powers: the real binary case[END_REF] we have n e ≤ ⌈(e + 1)/4⌉ for all e ∈ N. Since 2⌈(e + 1)/4⌉ ≤ ⌈(e + 3)/2⌉, it follows from Corollary 3.2 that this expression for f d is optimal over the reals, i.e., AffPow

R (f d ) = ⌊(d + 1)/4⌋.
As a consequence of Theorem 3.1 we can easily derive the following result.

Corollary 3.4. Let f ∈ R[x] be a polynomial of degree d. Either f = α(x -a) d for some α, a ∈ R (and Waring R (f ) = Sparsest R (f ) = 1)
, or the following holds:

Waring R (f ) + Sparsest R (f ) ≥ d + 3 2
Proof. We set k = Waring R (f ) and l = Sparsest R (f ) and assume that l ≥ 2. We write f in two different ways:

f = k i=1 α i (x -a i ) d = l j=1 β i (x -a) e i ,
where the a j ∈ R are all distinct, and e 1 < • • • < e l = d. Let us move the term β l (x-a) d to the left hand side of the equation. We then have two cases to consider:

• if a = a i for all i, we have k + 1 terms on the left hand side of the equation and l -1 terms on the right hand side. Theorem 3.1 shows that (k + 1) + (l -1) ≥ (d + 3)/2.

• If a = a i for some i, we have k or k -1 terms on the left hand side of the equation and l-1 terms on the right hand side. By Theorem 3.1, k+(l-1) ≥

(d + 3)/2. ✷ Remark 3.5. Consider the degree d ≥ 2 polynomial f := (x + 1) d + (x -1) d = i even 0≤i≤d 2 d i x d-i .
We observe that Waring R (f ) = 2 and Sparsest R (f ) ≤ ⌈(d + 1)/2⌉. Hence, the inequality in Corollary 3.4 is optimal up to one unit.

A similar proofs to that of Corollary 3.4 yield the following result:

Corollary 3.6. Let f ∈ R[x] be a polynomial of degree d. Either AffPow R (f ) = Waring R (f )
or the following inequality holds:

Waring R (f ) + AffPow R (f ) ≥ d + 3 2

Fields of characteristic zero

We now switch from the real field to an arbitrary field F of characteristic zero. By definition we have AffPow

F (f ) ≤ Waring F (f ) and AffPow F (f ) ≤ Sparsest F (f ) for any polynomial f ∈ F[X].
We show in Example 3.7 that there are polynomials f such that AffPow F (f ) is much smaller than both Waring F (f ) and Sparsest F (f ).

We first make some basic observations about Sparsest Shift. For any a ∈ F, the polynomials {(xa) i | i ∈ N} are linearly independent, hence f can be uniquely expressed as f = d i=0 α i (xa) i where α i = f (i) (a)/i!. Consider such a decomposition for f , and let s be the number of nonzero terms. It follows that the d + 1s derivatives f (i) with α i = 0 admit a as a common root.

Example 3.7. For every d ∈ N, we consider the polynomial

f d := (x + 1) d - dx d-1 ∈ C[x]. It is easy to check that AffPow(f d ) = 2 for all d ≥ 2. By [5, Proposition 3.1] we have that if x d-1 = s i=1 α i (x -a i ) d with α i , a i ∈ C, then s ≥ d; and thus we get that Waring C (f d ) ≥ d -1.
One can easily check that for every i ∈ {0, . . . , d -1}, the polynomials f

(i) d = d! (d-i)! f d-i and f (i+1) d = d! (d-i-1)! f d-i-1
do not share a common root. Consider a decomposition of f in the sparsest shift model. By the above observations, for any pair of consecutive coefficients in this decomposition at least one of the 2 coefficients is nonzero. This implies that Sparsest C (f ) ≥ ⌈(d + 1)/2⌉.

In the remainder of Section 3.2 we give (in Proposition 3.9) a weaker version of Corollary 3.4 that works for any field of characteristic zero. Moreover, for F = C we provide a family of polynomials showing that the bound from Proposition 3.9 is sharp.

We will use Jordan's lemma [START_REF] Grace | The algebra of invariants[END_REF] (see [START_REF] Iarrobino | Power sums, Gorenstein algebras, and determinantal loci. Appendix C by Iarrobino and[END_REF]Lemma 1.35] for a recent reference), which can be restated as follows.

Lemma 3.8. Let d ∈ Z + , e 1 , . . . , e t ∈ {1, . . . , d}, and let a 1 , . . . , a t ∈ F be distinct constants.

If t i=1 (d + 1 -e i ) ≤ d + 1, then the set of polynomials {(x -a i ) e | 1 ≤ i ≤ t, e i ≤ e ≤ d} is linearly independent. Proposition 3.9. Let f ∈ F[x] be a polynomial of degree d. Either f = α(x -a) d
for some α, a ∈ F (and Waring F (f ) = Sparsest F (f ) = 1), or the following holds:

Waring F (f ) • Sparsest F (f ) ≥ d + 1
Proof. We set k = Waring F (f ) and l = Sparsest F (f ) and assume that k, l ≥ 2.

We express f in two different ways:

f = k i=1 α i (x -a i ) d = l j=1 β j (x -a) e j ,
with a j ∈ F all distinct and e 0 := -1 < e 1 < • • • < e l = d. First, we are going to prove that e i+1e i ≤ k for all i ∈ {0, . . . , l -1}. Indeed, if there exists t ∈ {0, . . . , l -1} such that e t+1e t ≥ k + 1, then we set r := e t + 1 and differentiate the previous equality r times to obtain

f (r) = k i=1 α i d! (d -r)! (x -a i ) d-r = l j=t+1 β j e j ! (e j -r)! (x -a) e j -r
, where e jr = e je t -1 ≥ e t+1e t -1 ≥ k for all j ∈ {t + 1, . . . , l}. From this equality, we deduce that the set

B := {(x -a i ) d-r | 1 ≤ i ≤ k} ∪ {(x -a) e i -r | t + 1 ≤ i ≤ l} is linearly dependent. However, B ⊆ {(x -a i ) d-r | 1 ≤ i ≤ k} ∪ {(x -a) i | k ≤ i ≤ d -r}.
The dr + 1 polynomials on the right-hand side are of degree at most dr, and they are linearly independent by Jordan's lemma. This is a contradiction since B is linearly dependent. We have proved that e i+1e i ≤ k for all i ∈ {0, . . . , l -1}, and we conclude that

d + 1 = e l -e 0 = l i=1 (e i -e i-1 ) ≤ kl.
✷ Remark 3.10. One can slightly modify [START_REF] García-Marco | Lower bounds by Birkhoff interpolation[END_REF]Proposition 19] to obtain the following equality of complex polynomials of degree d:

k j=1 (x + ξ j ) d = 0≤i≤d i≡0 (mod k) k d i x d-i
where k ∈ N and ξ ∈ C is a k-th primitive root of unity. This equality shows that there are polynomials of degree d such that Waring C (g) ≤ k and Sparsest C (g) ≤ ⌈(d + 1)/k⌉ and, thus the bound from Proposition 3.9 is tight.

Uniqueness results for sums of affine powers

The following result is an analogue of Theorem 3.1 for polynomials with coefficients over F, where F is any field of characteristic zero.

Proposition 3.11. Consider a polynomial identity of the form:

k i=1 α i (x -a i ) d = l i=1 β i (x -b i ) e i
where the a i ∈ F are distinct, the α i ∈ F are not all zero, β i , b i ∈ F are arbitrary, and e i < d for every i. Then we must have k + l > 2(d + 1).

Proof. We assume α 1 = 0 and we have the following equality:

α 1 (x -a 1 ) d = - k i=2 α i (x -a i ) d + l i=1 β i (x -b i ) e i
Consider an independent subfamily on the right hand side of this equality. We obtain a new identity of the form:

g = p i=1 λ i ℓ r i i with g(x) = α 1 (x -a 1 ) d , and p ≤ k + l -1.
Since deg(g) = d and e i < d for all i; then there exists i such that r i = d. We assume without loss of generality that

ℓ 1 = x -a 2 and r 1 = d.
We take the derivatives of this equality to obtain the following system:

g = p i=1 λ i ℓ r i i g ′ = p i=1 λ i [ℓ r i i ] ′ . . . g (p-1) = p i=1 λ i [ℓ r i i ] (p-1)
Using Cramer's rule, we obtain:

λ 1 = Wr(g, ℓ r 2 2 , . . . , ℓ rp p ) Wr(ℓ r 1 1 , ℓ r 2 2 , . . . , ℓ rp p )
We define ∆ = {i : 2 ≤ i ≤ p, r i ≥ p} and, following Proposition 2.4, we factorise the Wronskians:

λ 1 = (x -a 1 ) d-(p-1) i∈∆ ℓ r i -(p-1) i • W 1 (x -a 2 ) d-(p-1) i∈∆ ℓ r i -(p-1) i • W 2
where W 1 , W 2 are the remaining determinants.

After some simplifications, we obtain the following identity:

λ 1 (x -a 2 ) d-(p-1) W 2 = (x -a 1 ) d-(p-1) W 1
Notice now that since we have factorised the large r i 's, the i th row of W 1 and W 2 contains polynomials with degree bounded by pi,

thus deg W 1 , deg W 2 ≤ p(p -1)/2.
Moreover, since a 1 = a 2 , we compute the multiplicity of a 1 on both sides of the identity and obtain that

M a 1 (x -a 1 ) d-(p-1) W 1 = M a 1 λ 1 (x -a 2 ) d-(p-1) W 2 = M a 1 (W 2 ) .
The previous remark on the degree of W 2 therefore implies that

d -(p -1) ≤ p(p -1) 2
Finally, we set s = l + k and we use the fact that p ≤ s -1 to obtain the desired lower bound:

d ≤ (p + 2)(p -1) 2 d ≤ (s + 1)(s -2) 2 2d ≤ s 2 -s -2
and finally, 2(d + 1) < s 2 . ✷ Remark 3.12. The same equality as in Remark 3.10 shows that the order of this bound is tight when F = C, the field of complex numbers. Indeed, choosing k = √ d + 1 leads to the equality

k i=1 (x + ξ i ) d = k-1 j=0 k d jk x d-jk which has 2k = 2 √ d + 1 terms.
As a consequence of Proposition 3.11 we obtain that whenever AffPow F (f ) is sufficiently small, the terms of highest degree in an optimal expression of f as f = s i=1 α i (xa i ) e i are uniquely determined.

Corollary 3.13. Let f ∈ F[x] be a polynomial of the form :

f = k i=1 α i (x -a i ) d + l j=1 β j (x -b j ) e j with e j < d. If k + l ≤ d+1
2 , then the highest degree terms are unique. In other words, for every expression of f as

f = k ′ i=1 α ′ i (x -a ′ i ) d + l ′ j=1 β ′ j (x -b ′ j ) e ′ j with e ′ j < d and k ′ + l ′ ≤ d+1 2
, then k = k ′ and there exists a permutation π : {1, . . . , k} → {1, . . . , k} such that α i = α ′ π(i) and a i = a ′ π(i) for all i ∈ {1, . . . , k}.

Proof. Let us assume that we have another different decomposition for f :

f = k ′ i=1 α ′ i (x -a ′ i ) d + l ′ j=1 β ′ j (x -b ′ j ) e ′ j with k ′ + l ′ ≤ (d + 1)/2
. Hence, we have the following equality:

k i=1 α i (x -a i ) d - k ′ i=1 α ′ i (x -a ′ i ) d = l j=1 β j (x -b j ) e j - l ′ j=1 β ′ j (x -b ′ j ) e ′ j Since k + k ′ + l + l ′ ≤ 2(d + 1
), the result follows from Proposition 3.11. ✷

Finally, as a direct consequence of Corollary 3.13, we obtain a a sufficient condition for a polynomial to have a unique optimal expression in the AffPow model:

Corollary 3.14. Let f ∈ F[x] be a polynomial of the form: f = s i=1 α i (x -a i ) e i
For every e ∈ N we denote by n e the number of exponents smaller than e, i.e., n e = #{i : e i ≤ e}. If n e ≤ e+1

2 for all e ∈ N, then AffPow F (f ) = s and the optimal representation of f is unique. Remark 3.15. Whenever f ∈ R[x] satisfies the hypotheses of Corollary 3.14 and one term in the expression of f is of the form α i (xa i ) e i with a i ∈ C -R, then there exists j = i such that α j = α i , a j = a i and e j = e i . Indeed, if we have a decomposition for f , taking the conjugate of α i and a i for all i gives another decomposition of f , but by Corollary 3.14 these two decompositions must be identical. In Proposition 4.6 we will prove a more general version of this fact.

Another consequence of Proposition 3.11 is the following upper bound on the degree of the terms involved in an optimal expression of f in the model AffPow F . Corollary 3.16. Let f ∈ F[x] be a polynomial of degree d written as

f = s i=1 α i (x -a i ) e i with α i , a i ∈ F, e i ∈ N and s = AffPow F (f ). We set e := max{e i : 1 ≤ i ≤ s}, then e < d + s 2 2 and, if F = R, then e ≤ d + 2s -2.
In particular, we have that e < d + (d+2) 2 8 and, if F = R, then e ≤ 2d.

Proof. If e = d, then the result is trivial. Assume therefore that e > d. Now, we differentiate d + 1 times the expression for f to obtain the identity:

0 = f (d+1) = e i >d α i e i ! (e i -d -1)! (x -a i ) e i -d
k j=1 (x + ξ j ) d - 0≤i≤d i≡0 (mod k) k d i x d-i = 0
If we integrate this expression 7(d + 1) times we get a polynomial Also, as a byproduct of Corollary 3.16, we obtain the exact value of AffPow F (f ) for a generic polynomial f of degree d. It turns out to be equal to the worst case value of AffPow F (f ), obtained in [9, Proposition 18].

f := k j=1 (x + ξ j ) 8d+7 - 0≤i≤d i≡0 (mod k) k d i x 8d+7-i ,
Corollary 3.19. For a generic polynomial f ∈ F[x] of degree d, AffPow F (f ) = ⌈ d+1 2 ⌉.
Proof. The set of polynomials of degree ≤ d can be seen as a variety W of dimension d + 1. Given f ∈ F[x] a polynomial of degree d, by [9, Proposition 18] we have AffPow F (f ) ≤ ⌈ d+1 2 ⌉. For k < ⌈ d+1 2 ⌉, let us show that the set of polynomials g of degree d such that AffPow F (g) ≤ k is contained in a variety of dimension 2k < d + 1. For every e 1 , . . . , e k ∈ N the set of polynomials that can be written as

k i=1 α i (x -a i ) e i with a i , α i ∈ F is contained in a variety V e 1 ,...,e k of dimension 2k. If we set M := d + (d+2) 2 8
, Corollary 3.16 proves that in every optimal expression of a polynomial of degree d, the exponents e i are ≤ M ; thus the set of polynomials with AffPow F (f ) ≤ k and degree d is contained in e i ≤M V e 1 ,...,e k , which is a variety of dimesion ≤ 2k (it is a finite union of varieties of dimension ≤ 2k). ✷

Algorithms for distinct nodes

The goal of this and the following section is to provide algorithms that receive as input a polynomial f and computes s = AffPow F (f ) and the triplets (α i , a i , e i ) for i ∈ {1, . . . , s} such that f = s i=1 α i (xa i ) e i . We will not able to solve the problem in all its generality but under certain hypotheses. This section concerns the case where the a i in the optimal expression of f are all distinct. In this setting, our main result is Theorem 4.5 where we solve the problem when the number n e of exponents in the optimal expression that are ≤ e is 'small'. A key point to obtain the algorithms is given by the following Proposition. Roughly speaking, this result says that if f satisfies a SDE, then every term in the optimal expression of f with exponent e i big enough also satisfies the same SDE.

Proposition 4.1. Let f ∈ F[x] be written as f = s i=1 α i (x -a i ) e i ,
with α i ∈ F nonzero, the a i ∈ F are all distinct, and e i ∈ N. Whenever f satisfies a SDE(k, l), then for all e i ≥ k + (k + l)(s -1) + s 2 we have that (xa i ) e i satisfies the same SDE.

Proof. We assume that e 1 ≥ k + (k + l)(s -1) + s 2 and that f satisfies the following SDE(k, l):

k i=0 P i (x) g (i) (x) = 0,
with deg(P i ) ≤ i + l. By contradiction, we assume that (xa 1 ) e 1 does not satisfy this equation. For every j ∈ {1, . . . , s}, we denote by f j and R j the polynomials such that

f j = k i=0 P i (x) ((x -a j ) e j ) (i) = R j (x) (x -a j ) d j ,
where d j := max{e j -k, 0}. We observe that deg(f j ) ≤ e j +l, so deg(R j ) ≤ k+l, and that -f 1 = s j=2 f j = 0. We consider a linearly independent subfamily of f 2 , . . . , f s , namely {f j | j ∈ J} with J = {j 1 , . . . , j p } ⊆ {2, . . . , s}. Then by Proposition 2.4 we have that

e 1 -k = d 1 ≤ M a 1 (f 1 ) ≤ p -1 + j∈J deg(R j ) + (p -1)p -p 2 ≤ p -1 + (k + l)p + p 2 . Since p ≤ s -1, we get that e 1 ≤ k + s -2 + (k + l)(s -1) + s-1 2 < k + (k + l)(s -1) + s 2 , a contradiction. ✷
As a consequence of Proposition 4.1, we get Corollary 4.2 and Theorem 4.3. They provide an effective method to obtain the optimal expression of a polynomial f in the Affine Power model whenever all the terms involved have big exponents and all the nodes are different.

Corollary 4.2. Let f ∈ F[x] be written as f = s i=1 α i (x -a i ) e i , with α i ∈ F \ {0}, a i ∈ F all distinct
, and e i ≥ 5s 2 /2 for all i. Then,

a) {(x -a i ) e i | 1 ≤ i ≤ s} are linearly independent, b) If f = t i=1 β i (x -b i ) d i with t ≤ s, then t = s and we have the equal- ity {(α i , a i , e i ) | 1 ≤ i ≤ s} = {(β i , b i , d i ) | 1 ≤ i ≤ s}; in particular, AffPow F (f ) = s, c) f satisfies a SDE(2s -1, 0), d) if f satisfies a SDE(k, 0) with k ≤ 2s -1 then (x -a i ) e i also
f = s i=1 α i (x -a i ) e i ,
where the constants a i ∈ F are all distinct, α i ∈ F \ {0} and e i > 5s 2 /2. Then, AffPow F (f ) = s. Moreover, there is a polynomial time algorithm Build(f

) that receives f = d i=0 f i x i ∈ F[x]
as input and computes the s-tuples of coefficients C(f ) = (α 1 , . . . , α s ), of nodes N (f ) = (a 1 , . . . , a s ) and exponents E(f ) = (e 1 , . . . , e s ). The algorithm Build(f ) works as follows:

Step 1. Take r the minimum value such that f satisfies a SDE(r, 0) and compute explicitly one of these SDE.

Step 2. Compute B = {(xb i ) d i | 1 ≤ i ≤ l}, the set of all the solutions of the SDE of the form (xb) e with (r + 1) 2 /2 ≤ e ≤ deg(f ) + (r 2 /2).

Step

3. Determine β 1 , . . . , β l such that f = l i=1 β i (x -b i ) d i
Step 4. Set I := {i | β i = 0} and output the sets

C(f ) = (β i | i ∈ I), N (f ) = (b i | i ∈ I) and E(f ) = (d i | i ∈ I).
Proof. Corollary 4.2 proves the correctness of this algorithm. Indeed, by Corollary 4.2.(c) and (e), the value r computed in Step 1 satisfies that s ≤ r ≤ 2s -1. We claim that the set B computed in Step 2 satisfies that:

(1) it contains the set {(x -

a i ) e i | 1 ≤ i ≤ s)}, (2
) it has at most r elements, and

(3) all its elements are F-linearly independent. 3), the expression of f as a combination of the elements of B is unique and is the desired one.

Finally, the four steps can be perfomed in polynomial time. Only the first two steps require a justification. See Remark 2.7 in Section 2 regarding Step 1. In

Step 2 we substitute for each value of e the polynomial (xb) e in the SDE. This yields a polynomial g(x) whose coefficients are polynomials in b of degree at most r ≤ 2s -1. We are looking for the values of b which make g identically 0, so we find b as a root of the gcd of the coefficients of g. ✷

In the following result we are going to analyze the bitsize complexity of the algorithm proposed; for this purpose we assume that the output (and, hence, the input) have integer coefficients. With this analysis we intend to show a rough overestimate on the number of bitsize operations showing the polynomial time nature of the algorithm.

We recall that by the dense size of a polynomial f

= d i=0 f i x i ∈ Z[X] we mean size(f ) := d i=0 [1 + log 2 (1 + |f i |)].
Also for an n × m matrix M with rational entries p ij /q ij where p ij ∈ Z, q ij ∈ Z + , the bit size of M is size(M ) :=

n i=1 m j=1 [1 + log 2 (1 + |p ij |) + log 2 (1 + q ij )]. The notation f (n) = O(g(n)) means that there exists a k ∈ N such that f (n) = O(g(n) log k (max(|g(n)|, 2))).
Proposition 4.4. Let f be a polynomial of degree d that can be written as

f = s i=1 α i (x -a i ) e i ,
where the constants a i ∈ Z are all distinct, α i ∈ Z \ {0} and e i > 5s 2 /2. The algorithm Build(f ) in Theorem 4.3 outputs the optimal expression of f in the AffPow model in O(d 6.5 Let us study now the number of bitsize operations needed to obtain a SDE(r, 0) satisfied by f assuming that we know in advance the value of r in Step 1 of the algorithm. We propose to follow the idea of Remark 2.7 and find the SDE by computing a vector in the kernel of the matrix M whose entries are the coefficients of the polynomials x j f (i) with 0 ≤ j ≤ i ≤ r. We have that M has

1 + • • • + r = (r + 1)r/2 rows and d + 1 columns. Since size(x j f (i) ) = O(size(f ) + id log(d)), we have that size(M ) = O( r i=0 (i + 1)(size(f ) + id log(d))) = O(r 2 (size(f ) + rd log(d))), which is O(d size(f ) + d 2.5
). Now, we can obtain the required SDE by means of the Gauss pivoting method on M . Let E be the matrix in echelon form obtained by the Gauss method. By [START_REF] Schrijver | Theory of linear and integer programming[END_REF]Theorem 3.3], to compute E one needs O(r 4 d) arithmetic operations, which is O(d 3 ), and the biggest size of a coefficient appearing during the process of elimination by pivoting is O(size(M )). Thus, the number of bitsize operations needed to obtain the SDE(r, 0) is O(d 3 size(M )). Also, the biggest size of a coefficient appearing in the SDE(r, 0) found is O(size(M )). After multiplying by an appropriate integer, we can assume that each of these coefficients are integers of size O(size(M )).

We now lift the assumption that r is known in advance. To perform Step 1 we follow Remark 2.7 and we check whether f satisfies a SDE(ℓ, 0) starting from ℓ = 0 and increasing ℓ. We observe that at each step, we can check if f satisfies a SDE(ℓ, 0) by checking if the matrix M ℓ whose rows are the coefficients of the polynomials x i f (j) with 0 ≤ i ≤ j ≤ ℓ has full row rank. This can be easily checked from the matrix E ℓ in echelon form obtained by applying the Gauss method to M ℓ . Since M ℓ and E ℓ are respectively submatrices of M ℓ+1 and E ℓ+1 , the procedure of computing the SDE of smallest order satisfied by f can be done incrementally. Moreover, all the matrices M ℓ and E ℓ are submatrices of the matrices M and E described above. So, it is interesting to notice that knowing the exact value of r in advance does not give any advantage and Step 1 can be performed in O(d ,3 size(M )) bitsize operations.

To perform Step 2 we propose the following strategy. Assume that the SDE obtained in Step 1 is r i=0 P i (x)f (i) (x) = 0. For each value e : (r + 1) 2 /2 ≤ e ≤ d + (r 2 /2), we input in the SDE the polynomial (x -Y ) e , where Y is a new variable; we obtain an equation of the form g(x, Y ) = 0. We first observe that [START_REF] Bostan | Algorithmes efficaces en calcul formel[END_REF]Proposition 21.22], the cost of computing the integer roots of each h i is O(d 2 size(M )). Since we have to solve r + 1 equations and take the common roots, this makes O(d 2.5 size(M )) bitsize operations and since we have to do it for at most d values of e, this gives O(d 3.5 size(M )) bit operations overall. Moreover, the b j 's computed divide the independent term of all the h i and, hence, the bit size of each b i is O(d size(M )).

g(x, Y ) = (x -Y ) e-r h(x, Y ), where h(x, Y ) ∈ Z[x, Y ] has degree ≤ r. We write h = r i=0 h i x i , where h i ∈ Z[Y ] is of degree ≤ r -i. The bit size of any coefficient of h i is O(r 2 size(M )), which is O(d size(M )). Moreover, since every h i ∈ Z[Y ] has degree ≤ r, by
In Step 3, the corresponding matrix has at most d + 1 + (r 2 /2) rows, at most r columns (see the proof of Theorem 4.3), and its size is O(d 3.5 size(M )). Since the rank of this matrix is ≤ r (indeed, as we proved in Theorem 4.3, this matrix has full column rank), when we are performing Gaussian elimination and treating a new row we have at most r already treated nonzero rows. As a consequence of this, we have to perform O(r 2 d) arithmetic operations to solve the system of equations by Gaussian elimination through pivoting. Hence the cost of this step is O(d 5.5 size(M )), giving a total cost of O(d 6.5 size(f ) + d 8 ) bitsize operations. Now, we can proceed with the main result of this section: Theorem 4.5 (Different nodes). Let f ∈ F[x] be a polynomial that can be written as

f = s i=1 α i (x -a i ) e i ,
where the constants a i ∈ F are all distinct, α i ∈ F \ {0}, and e i ∈ N. Assume moreover that n i ≤ (3i/4) 1/3 -1 for all i ≥ 2, where n i denotes the number of indices j such that e j ≤ i.

Then, AffPow F (f ) = s. Moreover, there is a polynomial time algorithm Build(f )

that receives f = d i=0 f i x i ∈ F[x]
as input and computes the s-tuples of coefficients C(f ) = (α 1 , . . . , α s ), of nodes N (f ) = (a 1 , . . . , a s ) and exponents E(f ) = (e 1 , . . . , e s ). The algorithm Build(f ) works as follows:

Step 1. We take t the minimum value such that f satisfies a SDE(t, 0) and compute explicitly one of these SDE.

Step 2. and assume that

Consider B := {(x -b i ) d i | 1 ≤ i ≤ l},
d 1 ≥ d 2 ≥ • • • ≥ d l ≥ d l+1 := (t + 1) 2 /2.
Step 3. We take r ∈ {1, . . . , l} such that d rd r+1 > r 2 /2 and d r+1 < deg(f ).

Step 4. We set j := d r -(r 2 /2) and express f (j) as f

(j) = r i=1 β i d i ! (d i -j)! (x - b i ) d i -j with β 1 , . . . , β r ∈ F. We set I := {i | β i = 0}. Step 5. We set f := r i=1 β i (x -b i ) d i and h := f -f . If h = 0, then C(f ) = (β i | i ∈ I), N (f ) = (b i | i ∈ I) and E(f ) = (d i | i ∈ I).
Otherwise, we set h := ff and we have that

C(f ) = (β i | i ∈ I) ∪ C(h), N (f ) = (b i | i ∈ I) ∪ N (h) and E(f ) = (d i | i ∈ I) ∪ E(h),
where the triplet (C(h), N (h), E(h)) is the output of Build(h).

Proof. By Corollary 3.14 we have that AffPow F (f ) = s. Concerning the algorithm, first we observe that the value t computed in Step 1 is ≤ 2s -1 by Proposition 2.6. Moreover, we claim that the set B computed in Step 2 has l ≤ t elements. Otherwise, by Lemma 2.8, there exists a set I ⊆ {1, . . . , l} of size ≤ t + 1 and there exist

{γ i | i ∈ I} ⊆ F \ {0} such that i∈I γ i (x -b i ) d i = 0. Setting m := max{d i | i ∈ I} ≥ (t + 1) 2 /2, Proposition 3.11 yields that t + 1 ≥ |I| > 2(m + 1) > t + 1, a contradiction.
Now we set L := 5s 2 /2 and consider the set C := {(xa i ) e i | e i ≥ L} where the a i 's are the nodes in the optimal expression of f . We have that C = ∅; indeed, if we set e max := max{e i | 1 ≤ i ≤ s}, then s = n emax ≤ (3e max /4) for all i ∈ {1, . . . , s}. Hence C ⊆ B. In particular, there exists a τ ∈ {1, . . . , l} such that

d 1 ≥ d τ = e max ≥ 4 3 (s + 1) 3 . Now we take k := max{i | d i > L} (we have that 1 ≤ k ≤ l ≤ t ≤ 2s -1)
and we are going to prove that • there exists r ∈ {τ, . . . , k -1} such that d rd r+1 > r 2 /2, or

• d k -L > k 2 /2.
Indeed, if this is not the case, then we get the following contradiction:

4s 3 3 ≤ 4(s+1) 3 3 -L ≤ e max -L = d τ -L = k-1 i=τ (d i -d i+1 ) + d k -L ≤ ≤ 1 2 k i=τ i 2 ≤ 1 2 k i=1 i 2 = k(k+1)(2k+1) 12 ≤ (2s-1)2s(4s-1) 12 < 4s 3 3 .
We take r ∈ {1, . . . , k -1} such that d rd r+1 > r 2 /2, or r = k if such a value does not exist (and d k -L > k 2 /2). We claim that e max ≥ d r if and only if d r+1 < deg(f ) and, thus, the r described in Conversely, assume now that e max ≥ d r and let us prove that d r+1 < deg(f ). To prove this we first observe that setting j := d r -(r 2 /2), then f (j) can be uniquely expressed as a linear combination of

B ′ := {(x -b i ) d i -j | 1 ≤ j ≤ r} . Indeed, f (j) = e i ≥j α i e i !
(e i -j)! (xa i ) e i -j with α i = 0 and (xa i ) e i -j ∈ B ′ for all e i ≥ j, and if there is another way of expressing f (j) as a linear combination of B ′ , then by Proposition 3.11 we get that r > 2

(min{d i | 1 ≤ i ≤ r} -j + 1) ≥ √ r 2 + 2 > r, a contradiction. So, if d r+1 ≥ deg(f )
, then f (j) = 0 and the only expression of f (j) as a linear combination of B ′ would be the one in which every coefficient is 0, a contradiction. Hence, the value r computed in Step 3 exists.

We have seen that f (j) can be uniquely expressed as a linear combination of B ′ as f (j) = e i ≥j α i e i ! (e i -j)! (xa i ) e i -j . Hence, in Step 4, one finds all the (α i , a i , e i ) such that e i ≥ j. In Step 5, either the polynomial h is 0 and we have finished or h = e i <j α i (xa i ) e i is written as a linear combination of strictly less than s terms and satisfies the hypotheses of the Theorem, so by induction we are done. ✷ Note that in Step 2 of this algorithm we need to compute polynomial roots, just as in the corresponding step of Theorem 4.3 (see the proof of Theorem 4.3 for details). One difference, however, is that we do not use the roots b i only to output the coefficients of the optimal decomposition: we also use the b i in the subsequent iterations of the algorithm since the polynomials f and h of Step 5 are defined in terms of the b i , and we call the algorithm recursively on input h. From this discussion one might be lead to think that if f has its coefficients in a subfield K of F, the coefficients of f and h may lie outside K. We show in Proposition 4.6 that this is not the case: f and h = f -f always lie in K[X]. We do not know if f can be computed from f with a polynomial number of arithmetic operations and comparisons (in the words of Section 1.3, this would be a way to eliminate root finding from the "internal working" of the algorithm). Proposition 4.6. Let K be a subfield of F. Let f ∈ K[x] be a polynomial that can be expressed in the AffPow F model as

f = s i=1 α i (x -a i ) e i with α i , a i ∈ F,
and n e = #{i : e i ≤ e} ≤ e+1 2 for all e ∈ N. Then, for all m, M ∈ N, the truncated expression f = Proof. By Corollary 3.14, we know that AffPow F (f ) = s and, hence, α i , a i are algebraic over K. We denote by T the splitting field of the minimal polynomials of all the α i , a i over K (i.e., the smallest field T such that K(α i , a i ) ⊂ T and K ⊂ T is normal). Since K is of characteristic 0 (and, thus, the extension K ⊂ T is separable), then K ⊂ T is a Galois extension. Take now σ any element of the Galois group of the extension

m≤e i ≤M α i (x -a i ) e i
K ⊂ T. Since f ∈ K[x], if we apply σ to f we obtain that f = σ(f ) = s i=1 σ(α i )(x - σ(a i
)) e i . Moreover, by Corollary 3.14, we know that AffPow T (f ) = s and f has a unique optimal expression in the AffPow T model, then

{(α i , a i , e i ) | 1 ≤ i ≤ s} = {(σ(α i ), σ(a i ), e i ) | 1 ≤ i ≤ s}.
In particular, for every e ∈ N, we have that

{(α i , a i , e i ) | e i = e} = {(σ(α i ), σ(a i ), e i ) | e i = e}. (6)
Now, we consider f = m≤e i ≤M α i (xa i ) e i , by [START_REF] Bostan | Algorithmes efficaces en calcul formel[END_REF] we get that

σ( f ) = m≤e i ≤M σ(α i )(x -σ(a i )) e i = m≤e i ≤M α i (x -a i ) e i = f . Summarizing, if we denote f = M i=m f i x i ∈ T[x],
we have proved that σ(f i ) = f i for every i ∈ {0, . . . , M } and every σ in the Galois group of the extension K ⊂ T. This proves (see, e.g., [START_REF] Cox | Galois theory[END_REF]Theorem 7

.1.1]) that f i ∈ K for all i ∈ {0, . . . , M } and f ∈ K[x]. ✷ We define the size of the set of triplets {(α i , a i , e i ) | 1 ≤ i ≤ s} ⊂ Z×Z×N as s i=1 [1 + log 2 (1 + |a i |) + log 2 (1 + |α i |) + e i ].
As mentioned in the introduction, it is not clear that the size of the output of the algorithm proposed in Theorem 4.5 is polynomially bounded in the input size (i.e., in the bit size of f given as a sum of monomials). However, it is straightforward to check that the input size is polynomially bounded by the output size. Indeed, the degree of f is upper bounded by the maximum value of the e i and every coefficient of f can be seen as the evaluation of a small polynomial in the α i , a i 's. In the following result we prove that the algorithm works in polynomial time in the size of the output. Hence, a positive answer to Question 1.6 together with Corollary 3.16 would directly yield that the algorithm works in polynomial time (in the size of the input).

Proposition 4.7. Let f ∈ Z[x] be written as f = s i=1 α i (x -a i ) e i
with a i ∈ Z, α i ∈ Z \ {0}, e i ∈ N and assume that this decomposition satisfies the conditions of Theorem 4.5: the constants a i are all distinct, and n i ≤ (3i/4) 1/3 -1 for all i ≥ 2, where n i denotes the number of indices j such that e j ≤ i.

Then, the algorithm in Theorem 4.5 works in polynomial time in the size of the output.

Proof. We write f = d j=0 f j x j with f j ∈ Z and d = deg(f ) ≤ max{e 1 , . . . , e s }. We have that f j = e i ≥j α i e i j a e i -j i for all j ∈ {0, . . . , d}. Thus, the size of f is polynomially bounded by the size of the output. To perform Step 1 we follow Remark 2.7. We note that the coefficients of the polynomials appearing in the SDE are polynomially bounded by the size of f . In Step 2 we have to compute the integral roots of polynomials of degree t ≤ s with integral coefficients, which can also be done in polynomial time (see, e.g., [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF]).

Step 4 can also be performed in polynomial time by solving a linear system of equations (see, e.g., [START_REF] Schrijver | Theory of linear and integer programming[END_REF]Corollary 3.3a]) . The result follows from the fact that the polynomial h defined in Step 5 can be written as h = j∈J α j (xa j ) e j for some set J ⊂ {1, . . . , s} of at most s -1 elements. After the first iteration, the algorithm is therefore called recursively on polynomials h with an output size bounded by the output size of the original f . ✷

Algorithms for repeated nodes

This section is a continuation of the previous one and concerns the case where the nodes a i in the optimal expression of f in the Affine Power model are not necessarily different. The section is divided in two. In the first subsection we provide algorithms when all the exponents corresponding to a repeated node appear in a small interval. The second one handles the case where the difference between two consecutive exponents corresponding to the same node is always large.

Small intervals

We begin with the following result generalizing Proposition 4.1, which corresponds to δ = 0. Proposition 5.1. Let δ ∈ N + and let f ∈ F[x] be written as

f = t i=1 Q i (x) (x -a i ) e i , with distinct a i ∈ F, Q i ∈ F[X] with deg(Q i ) ≤
δ and e i ∈ N for all i. Assume that f satisfies the following SDE of parameters k, l:

k i=0 P i (x)f (i) (x) = 0. If e i ≥ k + (t -1)(k + l + δ) + t 2 , then Q i (x) (x -a i ) e i satisfies the same SDE; as a consequence P k (a i ) = 0.
Proof. We take i = 1. We assume that e 1 ≥ k + (t -1)(k + l + δ) + t 2 and that f satisfies a SDE(k, l)

k i=0 P i (x)f (i) (x) = 0
By contradiction, suppose that Q 1 (x)(xa 1 ) e 1 does not satisfy this equation. For every j ∈ {1, . . . , t}, we denote by g j and R j the polynomials such that

g j = k i=0 P i (x) (Q j (x)(x -a j ) e j ) (i) = R j (x)(x -a j ) d j
where d j := max{0, e j -k} for all j, and with deg R j ≤ δ+e j +l-d j ≤ k+l+δ. We have the equality

-g 1 = t i=2 g i = 0. (7)
We consider a linearly independent subfamily of g 2 , . . . , g t , namely {g j | j ∈ J} with J = {j 1 , . . . , j p } ⊆ {2, . . . , t}. Then by Proposition 2.4 we have that

e 1 -k = d 1 ≤ M a 1 (g 1 ) ≤ p -1 + j∈J deg(R j ) + p(p -1) -p 2 ≤ p -1 + (k + l + δ)p + p 2 .
Taking into account that p ≤ t -1, we finally obtain the inequality

e 1 -k ≤ t -2 + (t -1)(k + l + δ) + t-1 2 ,
which yields a contradiction. Now, we take

l 1 ≥ e 1 and R 1 ∈ F[x] such that (x -a 1 ) l i R 1 (x) = (x - a 1 ) e 1 Q 1 (x) and R 1 (a 1 ) = 0. Since (x -a 1 ) e 1 Q 1 (x)
is a solution of the SDE, we have that:

k i=0 P i (x) ((x -a 1 ) l 1 R 1 (x)) (i) = 0, we deduce that there exists q ∈ F[x] such that P k (x)(x -a 1 ) l 1 -k h(x) = (x - a 1 ) l 1 -k+1 q(x)
, from where we deduce that P k (a 1 ) = 0. ✷ From Proposition 5.1 we shall now derive Corollary 5.2 and Theorem 5.3. They provide an effective method to obtain the optimal expression of a polynomial f in the Affine Power model whenever all the exponents corresponding to a repeated node are required to lie in a small interval.

Corollary 5.2. Let δ ∈ Z + and let f ∈ F[x] be a polynomial written as

f = t i=1 Q i (x) (x -a i ) e i ,
where:

• Q i (x) = s i j=1 γ i,j (x -a i ) ǫ i,j ∈ F[x] with γ i,j = 0 and 0 = ǫ i,0 < ǫ i,1 < • • • < ǫ i,s i ≤ δ,
• the a i 's are elements of F and are all distinct, and

• e i ≥ 5t 2 (δ + 1) 2 /2 for all i. Then, a) the set of polynomials {Q i (x) (x -a i ) e i | 1 ≤ i ≤ t} is linearly independent, b) AffPow F (f ) = t i=1 s i and the optimal representation of f is unique, c) f satisfies a SDE(2t -1, δ), d) if f satisfies the SDE(k, δ) k i=0 P i (x)f (i) (x) = 0
and k ≤ 2t -1; then Q i (x)(xa i ) e i also satisfies it and P r (a i ) = 0 for all i ∈ {1, . . . , s}, and e) f does not satisfy any SDE(k, δ) with k < t.

Proof. Notice that (b) implies (a). To prove (b), we observe that f is written as

f = t i=1 s i j=1 γ i,j (x -a i ) e i +ǫ i,j , so AffPow F (f ) ≤ t i=1 s i . Now assume that f can also be expressed as f = r i=1 β i (x -b i ) d i with β i ∈ F and r ≤ t i=1 s i ≤ t(δ + 1)
. By Proposition 3.11 we get that either both expressions are the same, or

2t(δ + 1) ≥ r + t i=1 s i ≥ 2(min{e 1 , . . . , e t } + 1) > 5t 2 (δ + 1) 2 ,
which is not possible. Thus AffPow F (f ) = t i=1 s i and the optimal representation of f is unique.

From Proposition 2.6 we get (c). If f satisfies a SDE(k, d) with k ≤ 2t -1, then for all i ∈ {1, . . . , t} we have that

e i ≥ 5 2 t 2 (δ + 1) 2 > 5 2 t 2 -3 2 t + 2tδ -2δ = 2t -1 + (t -1) (2t -1 + 2δ) + t 2 ≥ k + (t -1) (k + 2δ) + t 2 . (8)
Hence, Proposition 5.1 yields that Q i (x)(x-a i ) e i is also a solution of this equation for all i, proving (d). Finally, f cannot satisfy a SDE(k, δ) with k < t; otherwise by (a) and (d), the vector space of solutions to this equation has dimension ≥ t, which contradicts Lemma 2.8. ✷ Theorem 5.3 (repeated nodes in small intervals). Let δ ∈ Z + and let f ∈ F[x] be a polynomial of degree d that can be written as

f = t i=1 Q i (x) (x -a i ) e i , with
• Q i (x) = s i j=1 γ i,j (x -a i ) ǫ i,j ∈ F[x] with γ i,j = 0 and 0 = ǫ i,0 < ǫ i,1 < • • • < ǫ i,s i ≤ δ,
• the a i 's are elements of F and are all distinct, and

• e i ≥ 5
2 t 2 (δ + 1) 2 for all i.

Then AffPow F (f ) = t i=1 s i . Moreover, there is a polynomial time algorithm Build(f, δ) that receives f = d i=0 f i x i ∈ F[x]
and δ as input and computes the t-tuples of nodes N (f ) = (a 1 , . . . , a t ), the values s 1 , . . . , s t and the tuple of coefficients

C(f ) = (γ i,j : 1 ≤ i ≤ t, 1 ≤ j ≤ s i ), and exponents E(f ) = (e i + ǫ i,j : 1 ≤ i ≤ t, 1 ≤ j ≤ s i ).
The algorithm Build(f, δ) works as follows:

Step 1. Take r the minimum value such that f satisfies a SDE(r, δ). Compute explicitly one of these SDE, i.e., compute P 0 , . . . , P r ∈ F[x] such that

r i=0 P i (x)f (i) (x) = 0 and deg(P i ) ≤ i + δ.
Step 2. Compute R = {c 1 , . . . , c p } ⊆ F the set of roots of P r .

For each i ∈ {1, . . . , p}, consider the F-vector space V i spanned by the solutions of the SDE of the form R(x)(xc i ) e , with (r+1) 2 (δ+1)

2 2 < e < d + r 2 (δ+1) 2 2
and R(x) a polynomial of degree ≤ δ.

We take B i = {g i,1 , . . . , g i,l i } a base of V i , where

g i,j = R(x)(x -c i ) e with (r+1) 2 (δ+1) 2 2 < e < d + r 2 (δ+1) 2 2
and deg(R(x)) ≤ δ. We set B := ∪ p i=1 B i .

Step 3. Express f as a linear combination of the elements of B, namely, f = p i=1 l i j=1 λ i,j g i,j with λ i,j ∈ F.

Step 4. Denote f i = l i j=1 λ i,j g i,j , for all i ∈ {1, . . . , p}. Write f i in the shift c i , i.e., f i = r i j=1 β i,j (xc i ) µ i,j with β i,j ∈ F \ {0}.

Step 5. Output N (f ) = (c 1 , . . . , c p ), r 1 , . . . , r p ∈ N,

C(f ) = (β i,j | 1 ≤ i ≤ p, 1 ≤ j ≤ r i ) and E(f ) = (µ i,j | 1 ≤ i ≤ p, 1 ≤ j ≤ r i ).
Proof. We observe that f satisfies the hypotheses of Corollary 5.2; then, by Corollary 5.2.(b), we have that AffPow F (f ) = t i=1 s i and that there is a unique optimal expression of f in the AffPow model.

Let us prove the correctness of the algorithm Build(f, δ). By Corollary 5.2.(c), (d) and (e), the value r computed in Step 1 satisfies that t ≤ r ≤ 2t -1. For all i ∈ {1, . . . , t} we have that • a i ∈ R, and

• Q i (x) (x -a i ) e i is a solution of the SDE computed in Step 1
Moreover, the input polynomial f can be expressed as a linear combination of the elements of B, because:

• f can be written as a combination of Q i (x) (xa i ) e i .

• Since AffPow F (f ) = t i=1 s i and s i ≤ δ, we have AffPow F (f ) ≤ t(δ + 1) ≤ r(δ + 1) and thus using Corollary 3.16 we have max{e i } < d + r 2 (δ+1) 2 2

. On the other hand, we have

e i ≥ 5 2 t 2 (δ + 1) 2 > 2t 2 (δ + 1) 2 ≥ (r+1) 2 (δ+1) 2 2
. This implies that Q i (x) (xa i ) e i belongs to V i and thus can be written as a linear combination of the elements of B i .

So, let us assume (we will prove it later) that all the elements of B are linearly independent. Then, in Step 3 there is a unique way of writing of f as a linear combination of the elements of B. Finally, it suffices to write

f i = R i (x)(x - deg(W 2 ) ≤ zδ + z(z-1)

2

, and τ ≤ (z -1) + zδ + z(z-1)

2 ≤ r -1 + rδ + r(r-1) 2 ≤ (r+1) 2 2 + rδ ≤ (r+1) 2 (δ+1) 2 2
, a contradiction.

✷

Remark 5.4. The algorithm Build(f, δ) described above can be slightly modified to not receive δ as input as long as f satisfies the hypotheses of Theorem 5.3 for some t, δ ∈ Z + . That is, we only need to assume that there exists δ ∈ Z + such that

f = t i=1 Q i (x) (x -a i ) e i ,
where

Q i (x) ∈ F[x]
has degree ≤ δ, the a i 's are distinct elements of F, and e i ≥ 5 2 t 2 (δ + 1) 2 for all i. Indeed, it suffices to start with δ = 0 and execute Build(f, δ) with increasing values of δ until the reconstruction of f succeeds. The correctness of this algorithm is justified by Corollary 5.2.(b). In fact, once we find δ such that the reconstruction is possible, we obtain the optimal expression of f in the Affine Power model.

Big gaps

This subsection deals with polynomials f such that whenever the terms (xa) e and (xa) d appear in the optimal expression of f in the Affine Power model, then the difference between d and e is "large". Similarly to Section 5.1, we begin with some results ensuring that whenever f satisfies a SDE, then so do some of its terms in the optimal expression of f in the Affine Power model. The desired algorithm then follows as a consequence of these results. Proposition 5.5. Let f ∈ F[x] be written as

f = (x -a) m g(x) + s i=1 α i (x -a) e i + p i=1 β i (x -a i ) d i , with g ∈ F[x]
, a, a i , α i , β i ∈ F, m, e i , d i ∈ N and a i = a for all i. We set e := max{e 1 , . . . , e s } if s ≥ 1 or e := -1 if s = 0. Whenever f satisfies a SDE(k, l) with me > p + (k + l)(p + 1) + p 2 , then (xa) m g satisfies the same SDE.

Proof. Assume that f satisfies a SDE(k, l)

k i=1 P i (x)f (i) (x) = 0
By contradiction, we assume that (xa) m g(x) does not satisfy this equation. Thus, there exists T (x) ∈ F[x] nonzero such that k i=0 P i (x) ((xa) m g) (i) = T (x)(xa) m-k . For every j ∈ {1, . . . , s} and every j ∈ {1, . . . , p}, we denote by h j and g j the polynomials such that

h j = k i=0 P i (x) ((x -a) e j ) (i) and g j = k i=0 P i (x) ((x -a j ) d j ) (i) .
We observe that deg(h j ) ≤ e j + l ≤ e + l and deg(g j ) ≤ d j + l. Since f satisfies the already mentioned SDE, we get that

T (x)(x -a) m-k = s i=1 α i h i + p i=1 β i g i .
If we differentiate (e + l + 1) times on both sides of the previous equation, we obtain an equality of the following form

U (x)(x -a) m-k-e-l-1 = p i=1 β i g (e+l+1) i = p i=1 U i (x)(x -a i ) r i with r i := max{0, d i -k -e -l -1} and deg(U i (x)) ≤ k + l.
f = s i=1 α i (x -a) e i + p i=1 β i (x -a i ) d i ,
with a, a i , α i , β i ∈ F, m, e i , d i ∈ N, a i = a for all i and e s > • • • > e 1 > e 0 := -1. Assume that f satisfies a SDE(k, l) and that e i+1 -e i > p+(k+l)(p+1)+ p 2 for all i, then (xa) e i satisfies the same SDE for all i ∈ {1, . . . , s}.

Proof. Assume that there exists an e i such that (xa) e i does not satisfy the SDE(k, l) and we take e the maximum of such e i . Then, we can write f (x) = g(x)(xa) e + e i <e α i (xa) e i + p i=1 β i (xa i ) d i . By means of Proposition 5.5 we have that g(x)(xa) e is a solution of the same SDE. Moreover, for all e i > e, then (xa) e i is also a solution of the SDE. But this is not possible since the set of solutions is a vector space, and, hence, (xa) e would also be a solution to the same SDE.

✷ The proof of the following Corollary is similar to that of Corollary 4.2 but makes use of Corollary 5.6 instead of Proposition 4.1.

Corollary 5.7. Let f ∈ F[x] be a polynomial that can be written as

f = s i=1 α i (x -a i ) e i
with a i , α i ∈ F, e i > 5s 2 /2 and, whenever a i = a j for some

1 ≤ i < j ≤ s, then |e i -e j | > 5s 2 /2. a) {(x -a i ) e i | 1 ≤ i ≤ s} are linearly independent, b) If f = t i=1 β i (x -b i ) d i with t ≤ s, then t = s and we have the equal- ity {(α i , a i , e i ) | 1 ≤ i ≤ s} = {(β i , b i , d i ) | 1 ≤ i ≤ s}; in particular, AffPow F (f ) = s, c) f satisfies a SDE(2s -1, 0), d) if f satisfies a SDE(k, 0) with k ≤ 2s -1, then (x -a i ) e i
also satisfies it for all i ∈ {1, . . . , s}, and e) f does not satisfy any SDE(k, 0) with k < s.

From this corollary we get the following result whose proof is similar to that of Theorem 4.3.

Theorem 5.8 (Big gaps). Let f ∈ F[x] be a polynomial that can be written as

f = s i=1 α i (x -a i ) e i
with a i , α i ∈ F, e i > 5s 2 /2 and whenever a i = a j for some 1 ≤ i < j ≤ s, then |e ie j | > 5s 2 /2. Then, AffPow F (f ) = s. Moreover, there is a polynomial time algorithm Build(f

) that receives f = d i=0 f i x i ∈ F[x]
as input and computes the s-tuples of nodes N (f ) = (a 1 , . . . , a s ), coefficients C(f ) = (α 1 , . . . , α s ) and exponents E(f ) = (e 1 , . . . , e s ). The algorithm Build(f ) works as follows:

Step 1. Take r the minimum value such that f satisfies a SDE(r, 0) and compute explicitly one of these SDE.

Step 2.

Compute B = {(x -b i ) d i | 1 ≤ i ≤ t},
f = s i=1 α i ℓ e i i , (10)
where e i ∈ N, α i ∈ F and ℓ i is a (non constant) linear form for all i. We denote by AffPow F (f ) the minimum value s such that there exists a representation of the previous form with s terms. We will study the uniqueness of optimal representations and propose an algorithm for finding such representations. In this section only, we work in the black box model: we assume that our algorithm has access to f only through a "black box" that outputs f (x 1 , . . . , x n ) when queried on an input (x 1 , . . . , x n ) ∈ F n . This very general model is standard for the study of many problems about multivariate polynomials such as, e.g., factorization [START_REF] Kaltofen | Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators[END_REF], sparse interpolation [START_REF] Ben-Or | A deterministic algorithm for sparse multivariate polynomial interpolation[END_REF][START_REF] Giesbrecht | Symbolic-numeric sparse interpolation of multivariate polynomials[END_REF], sparsest shift [START_REF] Giesbrecht | Algorithms for computing sparsest shifts of polynomials in power, Chebyshev and Pochhammer bases[END_REF] or Waring decomposition [START_REF]Affine projections of polynomials[END_REF]. We also assume that our algorithm has access to d = deg(f ); the knowledge of an upper bound on deg(f ) would in fact suffice. As explained in the introduction, our algorithm proceeds by reduction to the univariate case: we solve n univariate projections of the multivariate problem, and then "lift" them to a solution of the multivariate problem. One (very) minor difficulty is that our univariate algorithms are presented for polynomials given in dense representation rather than in black box representation. But it is easy to convert from black box to dense representation:

Remark 6.1. Suppose that we have black-box access to a polynomial f (x 1 , . . . , x n ) of degree d. We can obtain the dense representation of the univariate polynomial f 1 (x 1 ) = f (x 1 , 0, 0, . . . , 0) by querying f on d + 1 distinct inputs of the form (a i , 0, . . . , 0) and interpolating f 1 from its values at a 0 , . . . , a d .

In our algorithm we perform a random change of coordinates before projecting to a univariate problem. Converting to dense representation in this case is hardly more difficult: Remark 6.2. Suppose that we have black-box access to a polynomial f (x 1 , . . . , x n ) of degree d. Let g(x) = f (Λ.x + λ), where λ = (λ 1 , . . . , λ n ) ∈ F n and Λ = (λ ij ) is an n × n matrix.

We can obtain the dense representation of the univariate polynomial g 1 (x 1 ) = g(x 1 , 0, 0, . . . , 0) = f (λ 11 x 1 + λ 1 , λ 21 x 1 + λ 2 , . . . , λ n1 x 1 + λ n ) by evaluating g 1 at d + 1 points and interpolating from those values. Equivalently, we can observe that a black-box for g can be constructed from the black box for f , and we can therefore apply Remark 6.1 to g.

Having recalled these well-known facts, we proceed with uniqueness considerations. Strictly speaking the optimal expressions in model ( 10) are never unique since for all λ ∈ F \ {0} we have α i ℓ e i i = β i t e i i with β i := α i λ e i and t i := ℓ i /λ. To deal with this ambiguity, we use the notion of essentially equal expressions. Given f we say that two expressions of f = s i=1 α i ℓ e i i = r i=1 β i t d i i are essentially equal if r = s and there exists a permutation σ of {1, . . . , s} such that

α i ℓ e i i = β σ(i) t d σ(i)
σ(i) for all i ∈ {1, . . . , s}. Likewise, we say that f has an essentially unique optimal decomposition in the multivariate Affine Powers model if two optimal decompositions of f are always essentially equal.

If the representation of f = s i=1 α i ℓ e i i is optimal, ℓ i and ℓ j cannot be proportional whenever e i = e j . Otherwise if ℓ i = λℓ j with λ ∈ F, we can rewrite α i ℓ e i i + α j ℓ e j j = (λ e i α i + α j )ℓ e j j

The following result provides a sufficient condition for f to have an essentially unique optimal decomposition in the multivariate Affine Powers model. Indeed, it is an extension to the multivariate setting of Corollary 3.14. Proposition 6.3. Let f ∈ F[x 1 , . . . , x n ] be a polynomial of the form:

f = s i=1 α i ℓ e i i
where α i ∈ F \ {0}, the ℓ i are non constant linear forms, and ℓ i is not proportional to ℓ j whenever e i = e j . For every e ∈ N we denote by n e the number of exponents smaller than e, i.e., n e = #{i : e i ≤ e}. If n e ≤ e+1 2 for all e ∈ N, then AffPow F (f ) = s and the optimal representation of f is essentially unique.

Proof. Let r := AffPow F (f ) ≤ s and let f = s+r i=s+1 α i ℓ e i i be an optimal representation of f . We write ℓ i = n j=1 a ij x j + a i0 for all i ∈ {1, . . . , s + r}.

Consider the ring homomorphism ϕ :

F[x 1 , . . . , x n ] → F[x] induced by x i → ω i x + λ i where ω = (ω 1 , . . . , ω n ), λ = (λ 1 , . . . , λ n ) ∈ F n . If we write ϕ(ℓ i ) = b i x + c i ,
≤ i < j ≤ s+r, ϕ(ℓ i ) = µϕ(ℓ j ) with µ ∈ F if and only if ℓ i = µℓ j .
It is important to observe that a generic choice of ω, λ ∈ F n fulfils these two conditions. Then

ϕ(f ) = s i=1 α i ϕ(ℓ i ) e i = s i=1 α i b e i i (x + c i /b i ) e i = s+r i=s+1 α i ϕ(ℓ i ) e i = s+r i=s+1 α i b e i i (x + c i /b i ) e i . We consider the expression ϕ(f ) = s i=1 α i b e i i (x + c i /b i ) e i in
α i ℓ e i i = α i µ e i ℓ e i i+s = α i+s ℓ e i+s i+s ,
proving that the optimal representation of f is essentially unique. ✷ Our next goal is to provide algorithms that, given black-box access to a polynomial f ∈ F[x 1 , . . . , x n ], compute s = AffPow F (f ) and the terms α i ℓ e i i for i ∈ {1, . . . , s} such that f = s i=1 α i ℓ e i i . We are going to prove a multivariate analogue of Theorem 4.5 where the condition of "distinct nodes" is replaced by "the ℓ i 's in the decomposition are not proportional". The same strategy that we are going to exhibit in the proof also applies to obtain similar results for the other algorithms of sections 4 and 5. Theorem 6.4. Let f ∈ F[x 1 , . . . , x n ] be a polynomial that can be written as

f = s i=1 α i ℓ e i i ,
where ℓ i are nonconstant linear forms such that ℓ i = λℓ j for all λ ∈ F, 1 ≤ i < j ≤ s, α i ∈ F \ {0}, and e i ∈ N. Assume that n i ≤ (3i/4) 1/3 -1 for all i ≥ 2, where n i denotes the number of indices j such that e j ≤ i. Then, AffPow F (f ) = s. Moreover, there is a randomized algorithm MultiBuild(f ) that, given access to a black box for f and to d = deg(f ), computes the set of terms T

(f ) = {α i ℓ e i i | 1 ≤ i ≤ s}.
The algorithm MultiBuild(f ) runs in time polynomial in n and d, and works as follows:

Step 1. We define g := φ(f ) where φ is a random affine change of coordinates (x i → n j=1 λ ij x j + λ i for all i).

Step 2. For each j ∈ {1, . . . , n}, we set g j := π j (g) where π j :

F[x 1 , . . . , x n ] -→ F[x] is induced by x k → 0 if k = j and x j → x.
We apply the algorithm Build(g j ) from Theorem 4.5 to obtain s j := AffPow F (g j ) and the triplets

(β ij , b ij , e ij ) ∈ F × F × N such that g j = s j i=1 β ij (x + b ij ) e ij .
If there exist i, j such that b ij = 0, then output 'It is not possible to reconstruct f '. Otherwise, for all j we define the set of triplets

P j := {(c ij , p ij , e i,j ) | c ij := β ij b e ij ij , p ij := 1/b ij , 1 ≤ i ≤ s i }.
Step 3. If one of these conditions holds: (a) there exist j 1 = j 2 such that s j 1 = s j 2 , (b) there exist i 1 = i 2 and j such that c i 1 j = c i 2 j , or (c) there exist i, j such that for all i ′ , c i1 = c i ′ j or e i1 = e i ′ j ; then output: 'It is not possible to reconstruct f '. Otherwise we set s := s 1 = s 2 = • • • = s r and reorder the elements of P 2 , . . . , P n so that c i := c i1 = c i2 = • • • = c in and e i := e i1 = e i2 = • • • = e in for all i ∈ {1, . . . , s}.

Step 4. g = s i=1 c i (1 + n j=1 p ij x j ) e i , so we output f = s i=1 c i (φ -1 (1

+ n j=1 p ij x j )) e i
If the λ i 's and the λ ij 's needed to define φ are chosen uniformly at random from a finite set S, then the probability of success of the algorithm is at least

1 - d 2/3 (2n + d) |S| .
Proof. The input polynomial f satisfies the hypotheses of Proposition 6.3, so AffPow F (f ) = s and the optimal representation of f is essentially unique.

After applying a random φ as described in Step 1, with high probability 8 we have that φ is invertible and g = s i=1 α i t e i i with t i = n j=1 a ij x j + a i0 satisfies the following properties:

(i) a ij = 0 for all i, j.

(ii) for all j = 0, then a ij /a i0 = a i ′ j /a i ′ 0 for all i, i ′ , and (iii) α i a e i i0 = α i ′ a e i ′ i ′ 0 for all i = i ′ . It is important to observe that for a generic choice of the λ i 's and λ ij 's involved in the definition of φ, these conditions will be fulfilled. The goal of the algorithm is to recover f via the following expression of g: Since π j (g) satisfies the hypotheses of Theorem 4.5 Build(π j (g)) outputs the values

(α i a e i ij , a i0 a ij , e i ) | 1 ≤ i ≤ s .
From these values we obtain in the sets

P j = (α i a e i i0 , a ij a i0 , e i ) | 1 ≤ i ≤ s .
Before calling Build(π j (g)), we compute the dense representation of π j (g) using Remarks 6.1 and 6.2. Thanks to the unique expression of g j for all j and to (iii) we have that none of the conditions of Step 3 is satisfied and we obtain g in Step 4.

If we see the values of λ i , λ ij used to define φ as variables, the invertibility of φ is equivalent to the nonvanishing of a degree n polynomial. Moreover, the a ij are degree one polynomials in these variables. Thus, the conditions a ij = 0 consist in the nonvanishing of s(n + 1) polynomials of degree 1. The conditions a ij /a i0 = a i ′ j /a i ′ 0 for all i, i ′ , j with j = 0 can be seen as the nonvanishing of s(s -1)n/2 polynomials of degree 2. The conditions α i a e i i0 = α i ′ a e i ′ i ′ 0 can be seen as the nonvanishing of s(s -1)/2 polynomials of degree at most max(e i ), which, by Corollary 3.16, is upper bounded by d + (s 2 /2). Hence, all the conditions to be satisfied can be codified in a nonzero polynomial ψ of degree n + s(n + 1) + s(s -1)n + (s(s -1)(2d + s 2 )/4) ≤ 8s 2 n + 2s 2 d + s 4 4 .

Moreover, if we set e := max(e i ), then

• e ≤ d + (s 2 /2), and

• s = n e ≤ (3e/4) 1/3 , form where we deduce that s ≤ d 1/3 and the degree of ψ is upper bounded by d 2/3 (2n + d). Hence, by the Schwartz-Zippel lemma, if we assume the λ i , λ ij are taken uniformly at random from a finite set S, the probability of satisfying all these constraints is at least

1 - d 2/3 (2n + d) |S| .
and the result follows. ✷

A.1 Waring decompositions

In Proposition 2.6 we saw that if f has an expression in the AffPow model with s terms, then f satisfies a SDE(2s -1, 0). We begin this section by proving that an expression of f with s terms in the Waring model yields a SDE satisfied by f of order s and shift 0.

Proposition A.1. Let f ∈ F[x] be written as

f = s i=1 α i (x -a i ) d ,
Then f satisfies a SDE(s, 0) that is also satisfied by the (xa i ) d 's.

Proof. We consider the SDE in the unknown g given by the Wronskian:

Wr(g, (xa 1 ) d , . . . , (xa s ) d )(x) = 0

After factoring out (xa i ) d-s for all i, we get the reduced SDE: We factor (xa i ) on each row and use the known formula for the determinant of a Vandermonde matrix to obtain:

R s = s i=1 d i • s i=1 (x -a i ) • i<j (a i -a j )
We have deg(R s ) = s, and hence deg(R i ) = i, which shows that the reduced SDE has in fact a zero shift. ✷ Moreover, when Waring F (f ) is small enough we have that the SDE provided in Proposition A.1 is the only SDE(s, 0) satisfied by f . Corollary A.2. Let f be a polynomial such that s = Waring F (f ) ≤ 2d/3. Then f satisfies a unique SDE(s, 0).

Proof. Consider a SDE(s, 0) satisfied by f :

s i=0 P i (x)f (i) (x) = 0
Since Waring F (f ) = s, f can be expressed as f = s i=1 α i (xa i ) d and {(xa i ) d : 1 ≤ i ≤ d} are linearly independent. By Proposition 4.1 we get that any term (xa i ) d satisfies this SDE because d ≥ 3 2 s 2 ≥ s + s(s -1) + s 2 .

Thus, we apply Lemma 2.9 to conclude the equation given by the Proposition A.1 is the unique SDE(s, 0) satisfied by f . ✷ As a direct consequence of this result, we have the following algorithm.

Algorithm A.3. Let f be a polynomial of degree d. There is a polynomial time algorithm WaringDec(f ) that receives f = d i=0 f i x i ∈ F[x] as input decides if Waring(f ) ≤ 2d/3. Moreover, whenever Waring F (f ) ≤ 2d/3, with the optimal decomposition being f = s i=1 α i (xa i ) d , the algorithm computes the s-tuples of shifts S(f ) = (a 1 , . . . , a s ) and coefficients C(f ) = (α 1 , . . . , α s ). The algorithm works as follows:

Step 1. Find the minimum k such that there exists an SDE(k, 0) satisfied by f and compute explicitly one of these SDE.

Step 2. If k > 2d/3, then Waring F (f ) > 2d/3.

Step 3. Compute the set B = {(xb i ) d | 1 ≤ i ≤ t} of solutions of the form (xa) d of this SDE.

Step 4. If t < k, then Waring F (f ) > 2d/3.

Step 5. Write f = Note that if we reach Step 5 of the algorithm, we have t = k = s ≤ 2d/3.

A.2 Sparsest Shift decompositions

We saw in Section A.1 that a polynomial with a Waring decomposition of size s satisfies a SDE of order s and shift 0. The same is true for the Sparsest Shift model:

Proposition A.4. Let f ∈ F[x] be written as f = s i=1 α i (x -a) e i ,
Then f satisfies a SDE(s, 0) that is also satisfied by the (xa) e i 's.

Proof. We will prove something stronger, namely that f satisfies an SDE(s, 0) of the following form s i=0 γ i (xa) i g (i) (x) = 0, where γ 0 , . . . , γ s ∈ F. We take the original SDE given by the Wronskian of an unknown polynomial g and (xa) e i for all i ∈ {1, . . . , s}: s i=0 (-1) i P i (x) g (i) (x) = 0.

Because of the stepped sequence of degrees in the determinant defining P i , there exists an integer ∆ i such that every permutation σ corresponds to a term c σ (xa) ∆ i . More precisely, we have

∆ i =   s j=1 e j   - s 2 + i

  the set of all the solutions of the SDE of the form (xb) e with (t + 1) 2 /2 ≤ e ≤ deg(f ) + (deg(f )+2) 2 8

  Step 3 always exists. If d r+1 < deg(f ), since deg(f ) ≤ e and C ⊆ B, then d r ≤ e max (since e max = d τ , it cannot be sandwiched between two consecutive elements d r , d r+1 of this sequence).

  belongs to K[x]. In particular, whenever f ∈ F[x] satisfies the hypotheses of Theorem 4.5 and f ∈ K[x], then the polynomial f computed in Step 5 of the algorithm also belongs to K[x].

2 , 2 ,Corollary 5 . 6 .

 2256 If we take a linearly independent family {g (e+l+1) i : i ∈ I} ⊆ {g (e+l+1) i : i ∈ {1, . . . , p}} and compute the multiplicity of a on both sides of the previous equality using Proposition 2.4, we obtain that mkel -1 ≤ p -1 + (k + l)p + (p -1)p -p which yields that me ≤ p + (k + l)(p + 1) + p a contradiction. ✷ The following result is a generalization of Proposition 4.1 where we allow repeated nodes provided their corresponding exponents are far enough. Let f ∈ F[x] be written as

Step 3 .Step 4 .

 34 the set of all the solutions of the SDE of the form(xb) d with (r + 1) 2 /2 ≤ e ≤ deg(f ) + (r 2 /2). Determine α 1 , . . . , α r such that f = r i=1 α i (xb i ) d i Output the sets C(f ) = (α 1 , . . . , α r ), N (f ) = (b 1 , . . . , b r) and E(f ) = (d 1 , . . . , d r ).

  we choose ω and λ such that (1.a) b i = 0 and c i = 0 for all i ∈ {1, . . . , r + s}, and (1.b) for all 1

  the univariate Affine Power model. By (1.b), whenever e i = e j then c i /b i = c j /b j . Moreover it satisfies that {i ∈ {1, . . . , s} : e i ≤ e} = n e ≤ e+1 2 for all e ∈ N. Hence we apply Corollary 3.14 to get that r ≥ AffPow F (ϕ(f )) = s ≥ r and that both expressions for ϕ(f ) are the same. After reindexing if necessary we get that (2.a) α i b e i i = α i+s b e i+s i+s , (2.b) c i /b i = c i+s /b i+s , (2.c) and e i = e i+s for all i ∈ {1, . . . , s}. By (2.b) we have that b i x + c i = µ(b i+s x + c i+s ) with µ := b i /b i+s . By (1.b) we have that ℓ i = µℓ i+s . Finally, by (2.a) and (2.c), we conclude that

;α i a e i i0 1

 1 so we are interested in computing the values• α i a e ii0 for all i• a ij /a i0 for all i, j• e i for all iIn Step 2, for all j ∈ {1, . . . , n} we consider π j (g) = s i=1

R

  i (x)g (i) (x) = 0,whereR i = (xa 1 ) s . . . (xa s ) s d 1 (xa 1 ) s-1 . . . d 1 (xa s ) s-1 . . . . . . . . . d i-1 (xa 1 ) s-i+1 . . . d i-1 (xa s ) s-i+1 d i+1 (xa 1 ) s-i-1 . . . d i+1 (xa s ) s-i-1and d k := k j=1 (dj + 1). Because of the nice structure induced by all the exponents being equal to d, we have that R ′ i+1 = R i , and hence deg(R i ) = deg(R s ) -(si).If we factor out the constants on each row in R s we get thatR s = s i=1 d i • (xa 1 ) s . . . (xa s ) s (xa 1 ) s-1 . . . (xa s ) s-1 . . . . . . . . . (xa 1 ) . . . (xa s )

t

  i=1 β i (xb i ) d , and output S(f ) = (b 1 , . . . , b t ) and C(f ) = (β 1 , . . . , β t ).

  -1 . By Proposition 3.11 we have s > 2(ed) and we conclude that e < d + s 2 2 . When F = R, by Theorem 3.1 we have s ≥ (ed + 2)/2 and we conclude that e ≤ d + 2s -2. To finish the proof it suffices to recall that s = AffPow F (f ) ≤ ⌈(d + 1)/2⌉ ≤ (d + 2)/2; see [9, Proposition 18].

✷ Remark 3.17. On can find examples that are close to the bound of Corollary 3.16. Indeed, if we take k = √ d + 1 in Remark 3.10, we get an expression of the 0 polynomial with 2k terms, namely:

  Notice first that (b) implies (a). Assume now that (b) does not hold, then there is another expression of f asf = t i=1 β i (xb i ) d i witht ≤ s. Hence, by Proposition 3.11, we get that 2s ≥ t + s > 2(min({e 1 , . . . , e s }) + 1) ≥ √ 5s 2 , a contradiction. From Proposition 2.6 we get (c). If f satisfies a SDE(k, 0) with k ≤ 2s -1, then for all i ∈ {1, . . . , s} we have that Hence, Proposition 4.1 yields that (xa i ) e i is also a solution of this equation for all i, proving (d). Finally, f cannot satisfy a SDE(k, 0) with k < s; otherwise by (a) and (d), the vector space of solutions to this equation has dimension ≥ s, which contradicts Lemma 2.8.

	e i ≥ 5s 2 /2 ≥ (2s -1)s +	s 2	≥ ks +	s 2	.

satisfies it for all i ∈ {1, . . . , s}, and e) f does not satisfy any SDE(k, 0) with k < s.

Proof. ✷ Theorem 4.3 (Big exponents). Let f ∈ F[x] be a polynomial that can be written as

  The first claim follows from Corollary 4.2.(d), the fact that (r+1) 2 /2 ≤ (2s) 2 /2 < 5s 2 /2, and from Corollary 3.16, since e i ≤ deg(f )+(s 2 /2) ≤ deg(f )+(r 2 /2) for all i. To prove the second claim assume that B has more than r elements, then we take t 1 , . . . , t r+1 ∈ B. To reach a contradiction, by Lemma 2.8 it suffices to prove that t 1 , . . . , t r+1 are linearly independent. If this were not the case, by Proposition 3.11, we would have that r + 1 > (r + 1) 2 + 2, which is not possible. A similar argument and the fact that B has at most r elements proves the third claim. By[START_REF] Alexander | Polynomial interpolation in several variables[END_REF] and (

  size(f ) + d 8 ) bitsize operations. Proof. A first observation is that the value r computed in Step 1 of the algorithm is upper bounded in terms of d. Indeed, by hypothesis 5s 2 /2 ≤ max(e i ) and, by Corollary 3.16, max(e i ) ≤ d + (s 2 /2), which implies that d ≥ 2s 2 . Moreover, in Corollary 4.2 we show that r ≤ 2s -1; this gives r = O( √ d). Also by Corollary 4.2, we have that s ≤ r and then max(e

i ) = O(d).

  1/3 -1 and L ≤ 4(s + 1) 3 /3 ≤ e max . Proposition 4.1 yields that all the elements of C are solution of the SDE and, by Corollary 3.16 we know that e

	Since	ts +	s 2	≤ (2s -1)s +	s 2	≤ 5s 2 /2,

i ≤ deg(f ) + (deg(f )+2) 2 8

6

  The multivariate caseThis section concerns the study of the multivariate version of the Affine Power model, i.e., we study expressions of a polynomial f ∈ F[x 1 , . . . , x n ] as

In the literature, Waring rank is usually defined for homogeneous polynomials. After homogenization, the univariate model 1.2 becomes bivariate and the "multivariate generalization" therefore deals with homogeneous polynomials in 3 variables or more.

In that model, the size of the monomial x d is defined to be log d instead of d as in the usual dense encoding.

It is hardly more difficult to show that one must have nj ≤ ⌈ j+1 2 ⌉ for any optimal expression, see[START_REF] García-Marco | Lower bounds by Birkhoff interpolation[END_REF] Proposition 18].

The structural results about real polynomials from Section 3.1 rely instead on Birkhoff interpolation[START_REF] García-Marco | Lower bounds by Birkhoff interpolation[END_REF].

arxiv.org/abs/1607.05420v1

A detailed probabilistic analysis is performed at the end of this proof.

Acknowledgments

The reconstruction problem for sums of affine powers was suggested to one of us (P.K.) by Erich Kaltofen at a Dagstuhl workshop where P.K. gave a talk on lower bounds for this model.

c i ) d i and consider the Taylor expansion of R i (x) with respect to c i for every i ∈ {1, . . . , p} as in Step 4 to get the desired sets of nodes, coefficients and exponents.

To prove the correctness of the algorithm, it only remains to prove that the elements of B are linearly independent. To prove this we will follow a similar argument to that of Propposition 3.11. Assume that the elements of B are not linearly independent. We take

∈ Z} is F-linearly independent. We assume that Z = {b 2 , . . . , b z+1 } with z ≤ w -1 ≤ r. For all j ∈ {0, . . . , z -1}, if we differentiate the above expression j times we have that

where P i,j (x) ∈ F[x] are polynomials of degree ≤ δ. We set g i := P i (x)(xb i ) d i for all i ∈ {2, . . . , z + 1} and apply Cramer's rule to the system of equations ( 9) to get that

. . , g z+1 ) Wr(g 2 , . . . , g z+1 ) .

We observe that

where W 2 is a polynomial of degree ≤ zδ + z(z-1)

2

. Thus,

and, the multiplicity of b 1 in both sides of this expression has to be the same. Therefore, τ -

A Appendix: Algorithms for Sparsest Shift and Waring decomposition

In this appendix we apply the techniques from the previous sections to study optimal decompositions of polynomials in the Waring and Sparsest Shift models. As explained in the introduction, these two models have been extensively studied in the literature. We do not claim that the algorithms proposed in this appendix improve on the existing methods. Rather, we present them for the sole purpose of illustrating on these two classical models the techniques developed for the more general model of sums of affine powers.

Thus, the determinant is either 0, or some constant times (xa) ∆ i . Moreover, we have ∆ i+1 = ∆ i + 1 and hence we can rewrite the SDE as

with c i ∈ F. We factorize this equation by (xa) ∆ 0 to obtain the wanted SDE(s, 0). Notice that the factorization again doesn't change the space of solutions, hence f and (xa) e i are still solutions of this SDE. ✷ Corollary A.5. Let f be a polynomial of degree d such that s = Sparsest F (f ) < √ d, and let a ∈ F be the corresponding sparsest shift. Let k i=1 P i (x)f (i) (x) = 0 be any SDE(k, 0) satisfied by f . If k ≤ s we must have P k (a) = 0.

Proof. Assume that f satisfies an SDE(k, 0) :

Assume that e 1 > e 2 > • • • > e s > e s+1 := -1. We take t ∈ {1, . . . , s} the maximum value such that e te t+1 -1 ≥ s. Such a value t exists, otherwise d ≤ e 1 < s i=1 (e ie i+1 ) < s 2 , a contradiction. We rewrite f as

Now we apply Proposition 5.5 with p = 0 to get that (xa) et g satisfies the same SDE because e te t+1 > s ≥ k. By the same argument as in Proposition 5.1, we conclude that P k (a) = 0. ✷ Algorithm A.6. Let f be a polynomial of degree d. There is a polynomial time algorithm SparsestShift(f

the algorithm computes the shift a ∈ F, and the s-tuples of coefficients C(f ) = (α 1 , . . . , α s ) and exponents E(f ) = (e 1 , . . . , e s ). The algorithm works as follows:

Step 1. Find the minimum k such that there exists an SDE(k, 0) satisfied by f and compute explicitly one of these SDE. Namely,

Step 2. Factorize the last coefficient of this SDE, i.e., write:

(xa i ).

Step 3. For each a i , decompose f in the shifted basis ((xa i ) j ) 0≤j≤d .

Step