Wouter Castryck
email: wouter.castryck@wis.kuleuven.be

Robert Laterveer
email: robert.laterveer@math.unistra.fr

Myriam Ounaïes
email: myriam.ounaies@unistra.fr

Constraints on counterexamples to the Casas-Alvero conjecture, and a verification in degree 12

In a first (theoretical) part of this paper, we prove a number of constraints on hypothetical counterexamples to the Casas-Alvero conjecture, building on ideas of Graf von Bothmer, Labs, Schicho and van de Woestijne that were recently reinterpreted by Draisma and de Jong in terms of p-adic valuations. In a second (computational) part, we present ideas improving upon Diaz-Toca and Gonzalez-Vega's Gröbner basis approach to the Casas-Alvero conjecture. One application is an extension of the proof of Graf von Bothmer et al. to the cases 5p k , 6p k and 7p k (that is, for each of these cases, we elaborate the finite list of primes p to which their proof is not applicable). Finally, by combining both parts, we settle the Casas-Alvero conjecture in degree 12 (the smallest open case).

1 Introduction and overview (1.1) The subject of this article is the following intriguing conjecture [START_REF] Casas-Alvero | Higher order polar germs[END_REF]:

Conjecture 1 (The Casas-Alvero conjecture, 2001). Let f (x) ∈ C[x] be of degree d > 0 and suppose that for each j = 1, . . . , d -1 there exists an a ∈ C such that f (a) = f (j) (a) = 0, where f (j) (x) denotes the jth derivative. Then f (x) is the dth power of a linear polynomial.

For each given degree d, proving Conjecture 1 (if true) boils down to a finite Gröbner basis computation. In 2006, this was used by Diaz-Toca and Gonzalez-Vega to verify the conjecture for d ≤ 7 [START_REF] Gema | On analyzing a conjecture about univariate polynomials and their roots by using maple[END_REF]. Shortly after, Graf von Bothmer, Labs, Schicho and van de Woestijne [START_REF] Graf Von Bothmer | The Casas-Alvero conjecture for infinitely many degrees[END_REF] proved a theoretical result settling the cases d = p k and d = 2p k (where p is prime and k ≥ 0 is an integer). The proof uses reduction-mod-p arguments in algebraic geometry. It was recently rewritten in the more elementary (and slightly more powerful) language of padic valuations, in a nice overview due to Draisma and de Jong [START_REF] Draisma | On the Casas-Alvero conjecture[END_REF].

(1.2) By lack of a general strategy, beyond the degree, we subdivide the set of hypothetical counterexamples f (x) to the Casas-Alvero conjecture by

• their number of distinct roots #roots(f ),

• their type type(f ), which is the minimal number of recycled roots minus one min #S S ⊂ C and ∀j : ∃ a ∈ S : f (a) = f (j) (a) = 0 -1 where j ranges over {1, . . . , d -1},

• their scenario scen(f ), which is min (s 1 , . . . , s d-1 ) ∈ Z d-1

≥0

∃ a i 's ∈ C : ∀j : f (a sj ) = f (j) (a sj ) = 0

(1) where the minimum is taken lexicographically and j ranges over {1, . . . , d-1}. Note that type(f ) is the maximal entry of scen(f ).

Example. Since it is conjecturally impossible to give examples over C, consider f (x) = x(x -1) 4 (x -8)(x -18) ∈ F 23 [x]. One checks that the common roots of f with f (1) , . . . , f (6) are {1}, {1, 18}, {1}, {0}, {18}, {1}, respectively. So type(f ) = 2 and scen(f ) = (0, 0, 0, 1, 2, 0) (take a 0 = 1, a 1 = 0, a 2 = 18).

(1.3) The scenario (s 1 , . . . , s d-1 ) ∈ Z d-1 ≥0 of a degree d counterexample f ∈ C[x] to the Casas-Alvero conjecture always satisfies s 1 = 0 and s j ≤ max{ s i | i < j } + 1 for all j = 2, . . . , d -1. A sequence of this form will therefore be called a scenario for degree d. In view of the above, the type of a scenario is defined to be its maximal entry -we denote it by type(s). The number of scenarios for a given degree d grows quickly with d. E.g., in our main case of interest d = 12, we have [START_REF] Shi Bai | CADO-NFS 1.1[END_REF]1023,28501,145750,246730,179487,63987,11880,1155, 55, 1 scenarios of type 0, . . . , 10, respectively, amounting to a total of 678570.

(1.4) Let s = (s 1 , . . . , s d-1 ) be a scenario for degree d, and let t = type(s). Let f (x) ∈ C[x] be a degree d counterexample to the Casas-Alvero conjecture. Then we say that f (x) matches with s if there exist a 0 , . . . , a t ∈ C such that

• f (x) = g(x) • (x -a 0 )(x -a 1 ) • • • (x -a t ) for a degree d -1 -t polynomial g(x) ∈ C[x],
• f (a sj ) = f (j) (a sj ) = 0 for all j = 1, . . . , d -1.

Clearly f (x) matches with its own scenario scen(f ), but it may also match with various other scenarios.

Example (continued). The polynomial f (x) = x(x -1) 4 (x -8)(x -18) ∈ F 23 [x] also matches with (0, 1, 0, 2, 1, 0) (and many more).

(1.5) In Section 2, we prove a number of general constraints on these attributes. E.g., we find that

• #roots(f ) ≥ 5,
• 2 ≤ type(f ) ≤ d-3 (the first inequality being due to Draisma and Knopper [START_REF] Draisma | On the Casas-Alvero conjecture[END_REF]Proposition 6]),

• if type(f ) = d -3, then no consecutive entries of scen(f ) are equal.

The methods used here are classically flavoured (Gauss-Lucas, Newton, Rolle).

(1.6) In Section 3, using the p-adic valuation approach, we prove additional constraints for certain special degrees. Our main results are on degrees of the form p + 1:

Theorem 2. Let p be prime and let f (x) be a degree d = p + 1 counterexample to the Casas-Alvero conjecture. Let c be the root of f (d-1) (x). Then f (1) (c) = 0, and there exist at least two indices

2 ≤ j 1 < j 2 ≤ d -2 such that f (j1) (c) = f (j2) (c) = 0. In particular, type(f ) ≤ d -4. Moreover, if j 1 < • • • < j m are the indices between 2 and d -2 for which f (d-j1) (c) = • • • = f (d-jm) (c) = 0, then the determinant of ∆ f =        -1 j 1 0 0 • • • 0 -1 j2-2 j1-2 j 2 j 2 0 • • • 0 . . . . . . . . . . . . . . . . . . -1 jm-2 j1-2 j m jm-2 j2-2 j m jm-2 j3-2 j m • • • j m -1 (-1) j1 (-1) j2 (-1) j3 • • • (-1) jm        (2)
is a multiple of p.

Theorem 2 implies that every degree d = p + 1 counterexample to the Casas-Alvero conjecture matches with an element of the strongly reduced list of scenarios s = (s 1 , . . . , s d-1 ) for which

• s d-1 = 0,
• the set of indices 2 ≤ j ≤ d -2 for which s d-j = s d-1 satisfies the above determinant condition.

indeed, the only pairs (j 1 , j 2 ) for which det ∆ f ≡ 0 mod 11 are [START_REF] Casas-Alvero | Higher order polar germs[END_REF][START_REF] Graf Von Bothmer | The Casas-Alvero conjecture for infinitely many degrees[END_REF], [START_REF] De | [END_REF][START_REF] Gema | On analyzing a conjecture about univariate polynomials and their roots by using maple[END_REF], [START_REF] Gema | On analyzing a conjecture about univariate polynomials and their roots by using maple[END_REF][START_REF] Graf Von Bothmer | The Casas-Alvero conjecture for infinitely many degrees[END_REF], [START_REF] Gema | On analyzing a conjecture about univariate polynomials and their roots by using maple[END_REF][START_REF] Kollár | Sharp effective Nullstellensatz[END_REF], [START_REF] Draisma | On the Casas-Alvero conjecture[END_REF][START_REF] Kollár | Sharp effective Nullstellensatz[END_REF].

(1.7) For the computational part of our paper, we turn back to the original reduction-mod-p setting used by Graf von Bothmer et al. Because of the interplay between characteristic 0 and characteristic p > 0, the following general definition is convenient.

Definition 1. Let k be an algebraically closed field. We say that a degree d

polynomial f ∈ k[x] (d > 0) is a Casas-Alvero polynomial or CA-polynomial (over k) if f is not a power of a linear polynomial and if for each j = 1, . . . , d -1 there exists an a ∈ k such that f (a) = f (j) H (a) = 0.
Here, f

H denotes the jth Hasse derivative (using Hasse derivatives turns the Casas-Alvero condition somewhat more restrictive -it makes no difference in characteristic 0 or p > d -1, where f

(j) H = 1 j! f (j)
). Then the main theorem of [START_REF] Graf Von Bothmer | The Casas-Alvero conjecture for infinitely many degrees[END_REF] reads: Theorem 3 (Graf von Bothmer, Labs, Schicho, van de Woestijne). Let d > 0 be an integer and let p be a prime number. If no CA-polynomials of degree d exist over F p , then the Casas-Alvero conjecture is true in degree dp k for all integers k ≥ 0.

Since it is trivial that no CA-polynomials of degree 1 or 2 can exist (in any characteristic), the cases p k and 2p k follow. More generally, we call a prime p a bad prime for degree d if there exist CA-polynomials of degree d in characteristic p. Then it is easily verified that p = 2 is the sole bad prime for degree d = 3. De Jong and Draisma [START_REF] Draisma | On the Casas-Alvero conjecture[END_REF] proved that the bad primes for degree d = 4 are p = 3, 5, 7.

(1.8) In Section 5 we present a Gröbner basis algorithm, the basic version of which takes as input an integer d > 0 and a prime number p (or p = 0), and outputs whether or not CA-polynomials of degree d exist in characteristic p. The basic idea is to classify all CA-polynomials by their scenario (the definitions in (1.2) straightforwardly generalize to arbitrary k -this was already used in the example there under). We will see that scenarios of moderately low type t can be ruled out easily (if the Casas-Alvero conjecture is true). In characteristic 0, the computation seems feasible up to d • t ≈ 50, say. In small characteristic p, this can be pushed to about twice that value.

(1.9) By running the algorithm in characteristic 0 and analyzing the prime factors appearing in certain resulting Nullstellensatz expansions, we can find the bad primes for d up to 7. (a 135-digit number).

It should be noted that the possibility of enumerating bad primes using Gröbner bases is already reported upon by Graf von Bothmer et al. [START_REF] Graf Von Bothmer | The Casas-Alvero conjecture for infinitely many degrees[END_REF], and that the bad primes for d = 5 resp. d ∈ {5, 6} have been independently computed by Chellali and Salinier [START_REF] Chellali | La conjecture de Casas-Alvero pour les degrés 5p e[END_REF] and de Frutos [START_REF] De | [END_REF], respectively.

(1.10) Finally in Section 6, we combine our theoretical and computational approaches. A naive run of our algorithm in degree 12 lies completely out of reach. But in view of Theorem 2 and certain reduction-mod-p considerations, it suffices to restrict to a limited list of scenarios and to run the algorithm in characteristic p. In doing so, the computation becomes feasible:

Theorem 5. Conjecture 1 is true for d = 12.
The margin is tight: each of the five scenarios of (4) took approximately three weeks of computation and required about 90 GB of RAM. Pushing the analogous computation to d = 20, the next open case, is utopic.

(1.11) The main computations have been carried out using Magma [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF] version 2.18-2 on a computer called matrix, running Ubuntu 11.10 on a 6-core Intel Xeon 2.53 GHz processor with 96 GB RAM. Some additional calculations were executed using Magma version 2.15-12 on kasparov, running Debian GNU/Linux 6.0.4 on an 8-core x86-64 2.93 GHz processor with 64 GB RAM.

(1.12) We would like to thank Filip Cools, Jan Schepers, Fréderik Vercauteren and an anonymous referee for some helpful discussions and/or comments. We are also grateful to the Department of Electrical Engineering (KU Leuven), for allowing us to use kasparov.

2 General constraints on counterexamples

(2.1)
The following easy fact will be used throughout:

Lemma 6. Let f be a CA-polynomial over k of degree d > 0, α 1 , α 2 ∈ k * and β ∈ k. Then the polynomial g(x) = α 1 f (α 2 x + β) is also CA.
The polynomials f and g will be called equivalent. Note that the number of distinct roots, the type, the scenario, the matching or not with a given scenario, . . . are all preserved by equivalence.

Another frequently used fact is:

Proposition 7. Let f ∈ C[x]
be a polynomial of degree d all of whose roots are on a line (when plotted in the complex plane). Then for all j = 0, • • • , d -2:

f (j) (c) = 0, f (j+1) (c) = 0 =⇒ f (j+2) (c) = 0.
Proof: Using a transformation of the above kind we may assume that f and its derivatives are real polynomials having real roots only. For c ∈ R and j ∈ {0, . . . , d -2}, denote by m j (c) the multiplicity of c as a zero of f (j) , and by N j the number of distinct roots of f (j) . We have the relations:

c:f (j) (c)=0 m j+1 (c) = c:f (j) (c)=0 (m j (c) -1) = d -j -N j c:f (j) (c) =0 m j+1 (c) = d -j -1 - c:f (j) (c)=0 m j+1 (c) = N j -1. (5)
By Rolle's theorem, there is a zero of f (j+1) strictly between any pair of zeros of f (j) , thus:

#{ c ∈ R | f (j) (c) = 0, f (j+1) (c) = 0 } ≥ N j -1.
From [START_REF] De | [END_REF] we conclude that m j+1 (c) = 1 whenever f

(j) (c) = 0, f (j+1) (c) = 0.
Finally, thanks to the results of Graf von Bothmer et al. [START_REF] Graf Von Bothmer | The Casas-Alvero conjecture for infinitely many degrees[END_REF], we may assume that the degree of a counterexample to the Casas-Alvero conjecture is at least 12. This will also be used in some of the proofs below.

(2.2) We begin with some considerations on the type:

Proposition 8. Let f ∈ C[x]
be a CA-polynomial of degree d and let Γ be the convex hull of the roots of f (when plotted in the complex plane). Let m ≥ 2 be the maximum of the multiplicities of these roots, and let δ = 1 if this maximum is attained by a non-vertex of Γ (let δ = 0 otherwise). Let γ ≥ 2 be the number of vertices of Γ.

Then 2 ≤ type(f ) ≤ d + 1 -γ -m -δ ≤ d -3.
Proof: For each vertex v of Γ we have: Remark. Proposition 8 remains valid when we replace γ by the number of roots on the boundary of Γ (given that we adapt δ accordingly).

• f (j) (v) = 0 for all j = 1, . . . , d -1, or • v
Refining to the level of scenarios, we find: Proof: The first part is an immediate corollary to Proposition 8. As for the second statement, suppose to the contrary that f is a CA-polynomial for which scen(f ) = s, with t = type(s) ≤ d -3 and the first d -2 -t entries of s equal to zero. Let a 0 , . . . , a t ∈ C be as in [START_REF] Shi Bai | CADO-NFS 1.1[END_REF]. Then a 0 is a root with multiplicity at least d -1 -t. Let Γ be the convex hull of the roots of f and let γ be its number of vertices. Using Proposition 8, we conclude that γ = 2 and that a 0 is a vertex. Then if another 0 would appear in s = scen(f ), by Gauss-Lucas we would conclude that the multiplicity of a 0 is strictly bigger than d -1 -t, which would contradict Proposition 8. On the other hand, if two consecutive entries would be equal, some high-order derivative of f (x) would have a double root. But since γ = 2, f (x) is equivalent to a real-root polynomial, so Rolle's theorem (cfr. Proposition 7) would imply that this double root is actually a root of f (x) with multiplicity strictly bigger than d -t, again contradicting Proposition 8.

Remark.

Let s be as in the énoncé of Proposition 9. Then one cannot merely conclude (without using new arguments, that is) the stronger statement that there are no CA-polynomials f ∈ C[x] that match with s.

(2.3) As immediate corollaries to the lower bound 2 ≤ type(f ), we get the following three easy facts: if f is a CA-polynomial (over C) of degree d, then 1. f (2) (x) cannot be the (d -2)th power of a linear polynomial, 2. f cannot have a root of multiplicity at least d -1,

3. f has at least three distinct roots (note that these statements can be proved in various other ways, see e.g. [13, Proposition 2.2]). In the next two propositions, we will go a step further in directions 1 and 2. Later on (Proposition 13 and Theorem 14), we will go two steps further in direction 3.

Proposition 10. If f ∈ C[x] is a CA-polynomial of degree d, then f (3) (x)
cannot be the (d -3)th power of a linear polynomial.

Proof: Suppose to the contrary that f (3) (x) is the (d -3)th power of a linear polynomial. Thanks to Lemma 6, we may assume

f (3) (x) = d! (d-3)! x d-3
. Assume that f (1) (0) = 0, then f has a root of multiplicity at least 2 which is different from 0 and again by Lemma 6, we may assume f (1) = f (1) (1) = 0. Thus

f (x) = x d -(d -1)x 2 + (d -2)x; f (2) (x) = (d -1) dx d-2 -2 . Solving f (x) = f (2) (x) = 0, we get x = d
d+1 : a contradiction because rational roots of monic integer polynomials are necessarily integral. We conclude that f (1) (0) = 0. Then, for some constant c, f (2) Proof: Suppose that 0 is such a root. If f (d-1) (0) = 0, then we may assume that f (1) = f (d-1) (1) = 0 and

(x) = d(d -1)x d-2 + 2c and f (x) = x d + cx 2 . Solving f (x) = f (2) (x) = 0,
f (x) = x d-2 (x 2 -dx + d -1), f (d-2) (x) = (d -1)! 2 (dx 2 -2dx + 2).
Solving f (x) = f (d-2) (x) = 0, we get x = d+1 d : again a contradiction. We conclude that we necessarily have f (d-1) (0) = 0. Then, for some constant c,

f (x) = x d + cx d-2 and f (d-2) (x) = d! 2 x 2 + c. Solving f (x) = f (d-2) (x) = 0, we get c = 0.
We have chosen to present an elementary proof of Proposition 11, though we also can see it as a direct consequence of the forthcoming Proposition 13.

(2.4) Let us recall some basic properties of the elementary symmetric polynomials. Let a polynomial f and its derivatives be of the form

f (j) (x) = d! (d -j)! x d-j + d -j 1 a 1 x d-j-1 + d -j 2 a 2 x d-j-2 + • • • + a d-j
(here by convention f = f (0) ). Let σ m (j) be the sum of the mth powers of the roots of f (j) , for j = 0, • • • , d -1. Then Newton's formulas applied to each f (j) give the following relations (see for example [START_REF] Victor | Polynomials, Algorithms and Computation in Mathematics 11[END_REF] for more details on Newton formulas):

Lemma 12. r k=1 σ k (j) d -j r -k a r-k = -r d -j r a r for 0 ≤ j ≤ d -1, 1 ≤ r ≤ d -j. (It is understood that a 0 = 1.)
In particular, for r = 1, we have that

σ 1 (j) d -j = σ 1 (0) d
for j = 0, . . . , d -1, which means that the center of mass of the roots of the derivatives is fixed. As obviously

σ 1 (d -1) = σ 1 (0) d = -a 1
is the only root of f (d-1) , we see that whenever f is a CA-polynomial over C, the center of mass of its roots σ 1 (0) d is itself a root of f . As a direct consequence, the number of distinct roots of a CA-polynomial cannot be two. Actually, we can say more: if f has more than two distinct roots, then at least one of them (the center of mass) has to be in the interior of the convex hull of the roots. This fact also follows immediately from the Gauss-Lucas theorem, and can be pushed further:

Proposition 13. Let f ∈ C[x]
be a CA-polynomial. Then f has at least two distinct roots in the interior of the convex hull of the roots, when plotted in the complex plane. In particular, f has at least four distinct roots.

Proof: Assume that f has exactly one root, say 0, in the interior. Let ζ be among the roots of f located on the boundary with maximal multiplicity m. Then by Gauss-Lucas,

f (m) (0) = f (m+1) (0) = • • • = f (d-1
) (0) = 0 which means that for j = m, . . . , d -1:

f (j) (x) = d! (d -j)! x d-j .
Taylor expansion at x = ζ gives

f (0) = d j=m f (j) (ζ) j! (-ζ) j = ζ d d j=m (-1) j d j = ζ d (-1) m d -1 m -1 .
As f (0) = 0, we get ζ = 0, which is a contradiction.

Note that Proposition 13 can also be deduced directly from 2 ≤ type(f ).

(2.5) We now prove the main result of this section:

Theorem 14. Let f be a CA-polynomial over C, then f has at least five distinct roots.

Proof: Assume that f has four distinct roots. Then by the previous proposition, it has at least two distinct roots in the interior of its Gauss-Lucas hull. This implies that the four roots are on a line. By Lemma 6, we may assume that this is the real line. We denote by m the maximal multiplicity of the roots of f . By Proposition 11, we know that 2 ≤ m ≤ d -3.

• First case: m ≤ d -5. Again using Lemma 6, we may assume without loss of generality that the roots of f are as follows: a < 0 < 1 < b and f (d-1) (0) = 0. Then a and b cannot be zeros of f (j) for d -5 ≤ j ≤ d -1. Moreover, by Rolle's theorem (cfr. Proposition 7), each zero of f (j) is simple. Then we necessarily have

f (d-2) (1) = 0, f (d-3) (0) = 0, f (d-4) (1) = 0, f (d-5) (0) = 0. Integrating five times the expression f (d-1) (x) = d!x
and taking into account these constraints, we get

f (d-5) (x) = d! 5!
x(x 2 -5) 2 . But this contradicts the fact that the roots are simple.

• Second case: m = d -4. In view of Lemma 6, we arrange the roots as follows: a < 0 < b < 1 and we assume that f (d-1) (0) = 0. Denote by m a , m 0 , m b , m 1 their respective multiplicities. Then again we must have

f (d-2) (b) = 0, f (d-3) (0) = 0, f (d-4) (b) = 0.
Like in the first case, computing the last derivatives, we get

f (d-1) (x) = d!x, 2!f (d-2) (x) = d!(x 2 -b 2 ), 3!f (d-3) (x) = d!x(x 2 -3b 2 ), 4!f (d-4) (x) = d!(x 2 -5b 2 )(x 2 -b 2 ).
Obviously, as f (d-4) (b) = 0, we have m b ≤ d -5. From the Gauss-Lucas theorem, we deduce that a < -√ 5b. Now we apply Lemma 12 with j = 0, r = 1 and with j = 0, r = 3 to obtain

m a a + m b b + m 1 = m a a 3 + m b b 3 + m 1 = 0. (6)
We deduce that m a a(a

d -4 = m b b -a + m 1 1 -a < m b √ 5 + m 1 √ 3 < 4.
Since the Casas-Alvero conjecture is true for d ≤ 7, this is a contradiction.

• Third case: m = d -3. We proceed as in the previous case. We have

f (d-1) (x) = d!x, 2!f (d-2) (x) = d!(x 2 -b 2 ), 3!f (d-3) (x) = d!x(x 2 -3b 2 ).
From Gauss-Lucas we deduce that a < -√ 3b. Again, we obtain that m a ≥ 2. Thus we necessarily have:

m a = m, m 0 = m 1 = m b = 1. The linear equation in (6) gives d -3 = b -a + 1 -a < 1 √ 3 + √ 3 < 3,
again a contradiction.

3 Additional constraints for special degrees (3.

2) The p-adic valuations of binomial coefficients are well-understood. A formula due to Legendre [START_REF] Legendre | Théorie des nombres[END_REF] states that for any n ∈ Z >0 and any j ∈ {0, . . . , n} one has

v p n j = s p (j) + s p (n -j) -s p (n) p -1 ,
where s p (•) denotes the sum of the p-adic digits. Note that s p (j) + s p (n -j)s p (n) is a measure for the number of carries when adding n -j to j in base p.

In particular, v p n j = 0 iff there are no carries.

It follows that:

Lemma 15. Let n ∈ Z >0 and k ∈ Z ≥0 . If j ∈ {0, 1, 2, . . . , np k } is not a multiple of p k , then v p np k j > 0.
If moreover n = p r + 1 for some r ∈ Z ≥0 , it is sufficient to assume that j ∈ {0, p k , (n -1)p k , np k }.

Proof: According to Legendre's formula

v p np k j = s p (j) + s p (np k -j) -s p (np k ) p -1 .
Let q and ρ = 0 be the quotient and remainder of j when divided by p k . Then s p (np k ) = s p (n), s p (j) = s p (q) + s p (ρ), and

s p (np k -j) = s p ((n -q -1)p k + (p k -ρ)) ≥ s p (n -q) -1 + 1, from which v p np k j ≥ v p n q + s p (ρ) p -1 > 0.
A similar argument proves the second statement.

f, f (p k ) , f (2p k ) , . . . , f (d-p k )
do not share a common root. If n = p r + 1 for some integer r ≥ 0, one even has that f, f

(p k ) , f (d-p k )
do not share a common root. As a consequence, if s = (s 1 , . . . , s d-1 ) is a scenario for degree d and

s p k = s 2p k = • • • = s d-p k (resp. s p k = s d-p k )
, then there are no CA-polynomials that match with s.

Proof: We only prove the first statement (the second assertion can be proved in a similar way). Suppose to the contrary that f is a CA-polynomial such that f, f (p k ) , . . . , f (d-p k ) do have a common root. We may assume without loss of generality, using Lemma 6, that f is of the form

f (x) = x d + d 1 a 1 x d-1 + d 2 a 2 x d-2 + • • • + d d -1 a d-1 x, (7)
that the assumed common root of f, f (p k ) , . . . , f (d-p k ) is 0, and that min{v p (x i ) | i = 1, . . . , d} = 0, where we have denoted by x 1 , x 2 , . . . , x d the zeros of f . For j = 1, . . . , d -1, we have:

j! d! f (d-j) (x) = x j + j 1 a 1 x j-1 + j 2 a 2 x j-2 + • • • + j j -1 a j-1 x + a j . (8)
Using equality (8) with j = 1, • • • , d -1, each time plugging in a common root of f (d-j) and f (taking 0 if j is a multiple of p k ), one proves by induction on j that v p (a j ) ≥ 0 for all j = 1, . . . , d -1, a j = 0 as soon as p k | j.

Let x j be such that v p (x j ) = 0. Then taking valuations of both sides of the equality

x d j = - d 1 a 1 x d-1 j - d 2 a 2 x d-2 j -• • • - d d -2 a d-2 x 2 j - d d -1 a d-1 x j
yields a contradiction with (9) and Lemma 15.

Note that if n = 1 or n = 2 the conclusion that f resp. f and f (p k ) do not share a common root is trivially impossible. Hence the cases p k and 2p k tautologically follow from Proposition 16. If d = p r + 1, the proposition implies that the root of f (d-1) (x) must be a simple root of f (x). If p ≥ 3, this in turn can be seen as a limit case of the following statement:

Proposition 17. If d = p r + 1, then the root of f (d-1) (x) cannot be the mean of two distinct roots of f (x).

Proof: Using Lemma 6 we can assume that f (x) is of the form ( 7) with a 1 = 0 (i.e. the root of f (d-1) (x) is 0), and that again all roots x 1 , . . . , x d have nonnegative valuation, with minimum 0. Let x j be such that v p (x j ) = 0. Then the equality

da d-1 x j = -x d j - d 2 a 2 x d-2 j -• • • - d d -2 a d-2 x 2 j implies that v p (a d-1 ) = 0. Let w ∈ C * be such that f (w) = f (-w) = 0. Then 0 = f (w) -f (-w) gives da d-1 w = - d 3 a 3 w d-3 - d 5 a 5 w d-5 -• • • - d d -3 a d-3 w 3 .
Taking valuations yields a contradiction.

The same argument can be used to show that the root of f (d-1) (x) cannot be the mean of two distinct roots of f (1) (x).

(3.4) From now on, we focus on the special case d = p + 1. Using once again Lemma 6, we may assume that

   f (x) = x d + da 1 x d-1 + d 2 a 2 x d-2 + • • • + d d-2 a d-2 x 2 , min{v p (x j ) | j = 1, . . . , d} = 0, ( 10
)
where we have denoted by x 1 , . . . , x d-3 , x d-2 = x d-1 = 0, x d = -a 1 the roots of f . For j = 1, . . . , d -2, we then again have that expression (8) holds. Observe that v p (a 1 ) ≥ 0 because -a 1 is one of the roots of f . As before, using equality (8) with j = 2, . . . , d -2, each time plugging in a common root of f (d-j) and f , we prove by induction on j that v p (a j ) ≥ 0 for all j = 1, . . . , d -2. ( 11) Let x j be such that v p (x j ) = 0. The equality

-da 1 x d-1 j = x d j + d 2 a 2 x d-2 j + • • • + d d -2 a d-2 x 2 j
shows that v p (a 1 ) = 0. Therefore, we may assume without loss of generality that a 1 = -1. Then we can write f (x) = (x -1)g(x) where

g(x) = x d-1 -(d -1)x d-2 + d 2 a 2 -(d -1) x d-3 + d 3 a 3 + d 2 a 2 -(d -1) x d-4 + • • • + d d -3 a d-3 + • • • + d 2 a 2 -(d -1) x 2 .
In view of [START_REF] Victor | Polynomials, Algorithms and Computation in Mathematics 11[END_REF] and Lemma 15, all roots of g have strictly positive valuations (actually greater than 1/(d -3)). As a consequence, we see that 1 is a simple root of f (a fact already implied by Proposition 16) and that v p (x j ) > 0 for j = 1, . . . , d-3. Now whenever f (d-j) (1) = 0, the Casas-Alvero property implies that f (d-j) (x j ) = 0 with v p (x j ) > 0 and from equality (8) we get v p (a j ) > 0. But as

f (1) = 1 -d + d 2 a 2 + • • • + d d -2 a d-2 = 0,
there is at least one index 2 ≤ j ≤ d -2 such that v p (a j ) = 0. In other words, at least one of the derivatives f (d-j) (1) = 0. If we put this together with Proposition 11 and the observations following Lemma 12, we get:

Lemma 18. Let f be a CA-polynomial over C of degree d = p + 1, where p is prime. Let c be the center of mass of the roots of f . Then the following conditions are satisfied:

• f (1) (c) = 0, f (d-1) (c) = 0,
• f (j) (c) = 0 for at least one j ∈ {2, . . . , d -2},

• f (j) (c) = 0 for at least one j ∈ {2, . . . , d -2}.

(3.5) Let us now go further into the investigation of the orders of the derivatives having the center of mass as a root, thereby proving Theorem 2. We may again assume that f is of the form [START_REF] Legendre | Théorie des nombres[END_REF] and that a 1 = -1. We will use the notation x ≡ y if v p (x -y) > 0. In view of Lemma 18, let j 1 < j 2 < • • • < j m be the indices between 2 and d -2 such that f (d-ji) (1) = 0 for i = 1, . . . , m.

As observed previously, for all j ∈ {2, • • • , d -2}, we have v p (a j ) ≥ 0. If moreover j / ∈ {j 1 , • • • , j m }, then a j ≡ 0. From equality (8) with x = 1 and j = j 1 , j 2 , . . . , j m , we get

         1 -j 1 + a j1 ≡ 0 1 -j 2 + j2 j1 a j1 + a j2 ≡ 0 . . . 1 -j m + jm j1 a j1 + jm j2 a j2 + • • • + a jm ≡ 0 (12)
Using the equation f (1) p = 0 and the inequalities v p d j ≥ 1 for j = 2, . . . , d -2, we obtain

-1 + d j1 p a j1 + • • • + d jm p a jm ≡ 0. ( 13
)
Observe that for all 2 ≤ j ≤ d -2 we have:

d j p = d(d -2)(d -3) • • • (d -(j -1)) j! = (p + 1)(p -1)(p -2) • • • (p -(j -2)) j! = 1 j! (p j-1 + α j-2 p j-2 + • • • + α 1 p) + (-1) j-2 (j -2)! j!
where α 1 , . . . , α j-2 are integers. Therefore:

d j p ≡ (-1) j j(j -1)
.

Putting equations ( 12) and ( 13) together and putting ãji = aj i ji(ji-1) , we obtain:

             -1 + j 1 ãj1 ≡ 0 -1 + j2-2 j1-2 j 2 ãj1 + j 2 ãj2 ≡ 0 . . . -1 + jm-2 j1-2 j m ãj1 + jm-2 j2-2 j m ãj2 + • • • + j m ãjm ≡ 0 -1 + (-1) j1 ãj1 + (-1) j2 ãj2 + • • • + (-1) jm ãm ≡ 0. ( 14
)
With ∆ f as in the énoncé of Theorem 2, we see that necessarily det ∆ f ≡ 0: otherwise inverting ( 14) we would get that 1 ≡ 0. To conclude the proof of Theorem 2 we show:

Lemma 19. Let f ∈ C[x]
be a CA-polynomial of degree d = p+1 and let c be the center of mass of its roots. Then there are at least two indices

2 ≤ j 1 < j 2 ≤ d-2 such that f (j1) (c) = f (j2) (c) = 0.
Proof: If not, in virtue of Lemma 18, there exists a unique index 2 ≤ j ≤ d -2 such that f (d-j) (c) = 0. We can assume without loss of generality that f is of the form (10) with a 1 = -1 and apply the above. Then m = 1 and

det ∆ f = -1 j -1 (-1) j = j -(-1) j . (15)
Observe that 1 ≤ j -(-1) j ≤ j + 1 ≤ d -2 for j ∈ 2, . . . , d -3. Besides, d -2 -(-1) d-2 = d -3 because d is even (indeed, p = 2 since the Casas-Alvero conjecture is true for degree 3). Thus there is no way for p to divide det ∆ f .

(3.6) Theorem 2 implies that every CA-polynomial of degree d = p + 1 matches with a scenario s = (s 1 , . . . , s d-1 ) for which s d-1 = 0 and the index set

ind(s) = { j | 2 ≤ j ≤ d -2 and s d-j = s d-1 }
satisfies the according determinant condition. We remark however that this does not necessarily imply that the scenario of a CA-polynomial satisfies these conditions. Indeed, imagine a CA-polynomial f ∈ C[x] of degree 12 for which

scen(f ) = s = (0, 1 , 2, 3, 4, 2, 5, 6, 4, 7, 4),
i.e. there exist a 1 , . . . , a 7 ∈ C such that f (a sj ) = f (j) (a sj ) = 0 for j = 1, . . . , d -1. Then ind(s) = {3, 7} does not satisfy the determinant condition. However, it might a priori be that f (6) (x) has both a 2 and a 4 as a root. Then f (x) also matches with the scenario (0, 1, 2, 3, 4, 4, 5, 6, 4, 7, 4) = scen(f ). In this example, the index set {3, 6, 7} satisfies the determinant condition.

(3.7) We end our study of the degree p + 1 case with the following observation.

Proposition 20. Let p be a prime number. Then there is no CA-polynomial of degree d = p + 1 all of whose roots are rational.

Proof: Using the notations and the results found in the proof of Lemma 18, we may assume that f is of the form

f (x) =x d -dx d-1 + d 2 x d-2 + • • • + (-1) k-1 d k -1 x d-k+1 + d k a k x d-k + • • • + d d -2 a d-2 x 2 ,
with v p (x j ) ≥ 1 for j = 1, . . . , d -3. Here, we have denoted by k the smallest index between 2 and d -2 such that f (d-k) (1) = 0 (we know from Lemma 18 that such a k exists). We introduce the notation

S m = d-3 j=1
x m j .

Then we have: v p (S 1 ) = v p (d -1) = 1, and v p (S j ) ≥ 2 for j = 2, . . . , d -2. Using Newton's formulas (see Lemma 12 applied to j = 0), we obtain

-k d k a k = k-1 j=0 (-1) j (1 + S k-j ) d j = k-1 j=0 (-1) j d j + k-1 j=0 (-1) j S k-j d j = (-1) k-1 d -1 k -1 + k-1 j=0 (-1) j S k-j d j .
Note that v p d k a k > 1 which will lead to a contradiction:

• If k = 2, then the last equality becomes -2 d 2 a 2 = -(d-1)+S 2 -dS 1 = -(d-1)+S 2 -d(d-1) = -(d+1)(d-1)+S 2 .
The valuation of the right-hand term is 1.

• If 3 ≤ k ≤ d -2, then the right-hand term is (-1) k-1 d -1 k -1 + k-2 j=0 (-1) j S k-j d j + (-1) k-1 S 1 d k -1 . But v p (S k-j ) ≥ 2 for j = 0, . . . , k -2, and v p (S 1 d k-1 ) = 2, so the valuation of the right-hand term is v p d-1 k-1 = 1.
We remark that the proof of Proposition 20 in fact implies that there are no CA-polynomials of degree p + 1 all of whose roots are contained in a number field in which p does not ramify. Indeed, this ensures that the valuations of the x j are integers, hence we can still conclude that v p (x j ) ≥ 1.

Algebraic varieties of counterexamples

Φ k (d, d -2) : V k (d, d -2) → CA k (d) : (p 1 , . . . , p d-2 ) → x 2 (x -p 1 ) • • • (x -p d-2 ), where V k (d, d -2) ⊂ P d-3 k
is the projective variety defined by the ideal

I k (d, d -2) = Res x (F, F (j) H ) j = 2, . . . , d -1 with F = x 2 (x -P 1 ) . . . (x -P d-2 ) ∈ k[P 1 , . . . , P d-2 ][x]
. Therefore, in order to prove that no CA-polynomials exist in degree d, it suffices to show that

V k (d, d -2) = ∅. Note that V k (d, d -2
) is invariant under coordinate permutations, so it is sufficient to show that V k (d, d -2) does not contain any points of the form (p 1 , . . . , p d-3 , 1). Setting P d-2 = 1 in I k (d, d -2), we obtain an ideal of k[P 1 , . . . , P d-3 ] that is equal to the unit ideal if and only if V k (d, d -2) = ∅. This can be checked using a finite Gröbner basis computation, which is exactly the approach of [START_REF] Gema | On analyzing a conjecture about univariate polynomials and their roots by using maple[END_REF].

(4.3) We also have a surjective map Φ k (d, 0) : V k (d, 0) → CA k (d) : (a 1 , . . . , a d-2 ) → x 2 (x d-2 + a 1 x d-3 + • • • + a d-2 ),
where now V k (d, 0) ⊂ P k (d -2; d -1; . . . ; 2; 1) is the weighted projective variety defined by the ideal

I k (d, 0) = Res x (F, F (j) H ) j = 2, . . . , d -1 with F = x 2 (x d-2 + A 1 x d-3 + • • • + A d-2 ) ∈ k[A 1 , . . . , A d-2 ][x]
. Again, in order to show that no Casas-Alvero polynomials can exist in degree d, it is sufficient to prove that V k (d, 0) = ∅. This was used in the theoretical approach of [START_REF] Graf Von Bothmer | The Casas-Alvero conjecture for infinitely many degrees[END_REF].

(4.4) We will make use of a hybrid version of the above maps. Namely, for each t ∈ {0, . . . , d -2} we have a surjective map

Φ k (d, t) : V k (d, t) → CA k (d) : (p 1 , . . . , p t , a 1 , . . . , a d-2-t ) → x 2 (x-p 1 ) • • • (x-p t )(x d-2-t +a 1 x d-3-t +• • •+a d-2-t ),
where V k (d, t) ⊂ P k (1; . . . ; 1; d-2-t; d-3-t; . . . ; 2; 1) is the weighted projective variety defined by the ideal

I k (d, t) = Res x (F, F (j) H ) j = 2, . . . , d -1 with F = x 2 (x -P 1 ) • • • (x -P t )(x d-2-t + A 1 x d-3-t + • • • + A d-2-t ) in k[P 1 , . . . , P t , A 1 , . . . , A d-2-t ][x]
. Once more it is sufficient to show that V k (d, t) = ∅ (for any value of t) in order to prove that no Casas-Alvero polynomials of degree d exist over k.

(4.5) To each scenario s for degree d of type t, we associate the variety

V k (s) ⊂ V k (d, t)
defined by the ideal

I k (s) = F (j) H (P sj ) j = 2, . . . , d -1 ⊂ k[P 1 , . . . , P t , A 1 , . . . , A d-2-t ]
where

F = x 2 (x -P 1 ) • • • (x -P t )(x d-2-t + A 1 x d-3-t + • • • + A d-2-t )
and P 0 = 0. Then it is clear that V k (s) parameterizes the CA-polynomials that match with s. Recall that every CA-polynomial matches with at least one scenario (e.g., its own scenario scen(f )). Thus, if one wants to show that no CApolynomials of degree d exist over k, it suffices to show that V k (s) = ∅ for each scenario s for degree d. This is essentially the 'more primary decomposition' that was mentioned in [8, Section 4], but in Section 5 below we will see that there is a significant amount of computational gain to be expected when viewing the set of CA-polynomials that match with s as a subvariety of V k (d, t) rather than V k (d, d -2). Moreover, if k = C, in view of the theoretical results obtained in Sections 2 and 3, it is actually sufficient to check whether V C (s) = ∅ for a restricted set of scenarios. We will elaborate the details of this for d = 12 in Section 6.

5 Revisiting the computational approach (5.1) We now describe the basic version of our algorithm, discarding the theoretical results of Sections 2 and 3. The input is a field characteristic p (either 0 or a prime number) along with an integer d > 2. The output is yes or no, depending on whether Casas-Alvero polynomials exist in degree d and characteristic p or not.

Step 1. Create a list L (of length d -1) of lists, such that L[t] contains all scenarios for type t (for t = 0, . . . , d -2). This can be done easily using d -2 nested for-loops. Let k be the field of rational numbers if p = 0, and let k be the field with p elements otherwise. Set answer := no.

Step 2. For t going from 1 to d -2 do:

-Initiate the following variables/structures: Step 3. Output answer.

* R = k[P 1 , . . . , P t-1 , A 1 , . . . , A d-2-t ] * S = R[x] * P 0 = 0 and P t = 1 * F (x) = x 2 (x -P 1 ) • • • (x -P t )(x d-2-t + A 1 x d-3-t + • • • + A d-2-t ) * ≺ = a
(5.2) Modulo a base change to the algebraic closure of k, I aff k (s) is obtained from I k (s) (as described in (4.5)) by setting P t = 1, so it only describes an affine part of V k (s). However, it suffices to verify that this affine part is empty. Indeed, the type of a CA-polynomial corresponding to a point (p 1 , . . . , p t , a 1 , . . . , a d-2-t ) ∈ V k (s) with p t = 0 is strictly smaller than t, so we would have encountered it already.

(5.3) The variables A 1 , . . . , A d-2-t appear linearly in the defining polynomials F (j) H (P sj ). Therefore, they can be eliminated easily. (In fact, the corresponding linear system is in echelon form, so the A i 's could also be eliminated bottom-up by hand.) The lower the type, the more variables can be eliminated and the easier the Gröbner basis computation becomes (in the extreme case t = 1 one obtains a linear system in d -3 variables). This is the main reason for our usage of the hybrid varieties V k (d, t).

(5.4) It is theoretically possible to avoid Gröbner basis computations and use linear algebra instead. Indeed, I aff k (s) = R is equivalent to the solvability of 1 = g 1 • F

(2)

H (P s2 ) + . . . + g d-2 • F (d-1) H (P s d-1 ) (16)
in terms of polynomials g i ∈ R. If such polynomials exist, by the effective Nullstellensatz they can be chosen such that their degree is bounded by d d (e.g., see [START_REF] Kollár | Sharp effective Nullstellensatz[END_REF]). So in principle, one could use indetermined coefficients to translate the solvability of ( 16) to the solvability of some linear system of equations. But this system is so huge that no gain is to be expected (although maybe this deserves a deeper analysis).

(5.5) One can speed up the algorithm slightly by noting the following. If s 2 = 0, then the first defining polynomial is

F (2) H (0) = (-1) t • P 1 • • • P t-1 • A d-2-t But Casas-Alvero polynomials corresponding to P 1 • • • P t-1 =
0 are of strictly lower type than t, so they would have been encountered already. Therefore, our defining polynomial can be replaced by A d-2-t . If in addition s 3 = 0, then similarly the second defining polynomial can be replaced by A d-3-t , and so on. Suppose that the first nonzero entry of s appears at position j. Then after substituting (5.6) The above algorithm can be used straightforwardly to find all bad primes for a given degree d (given that we know that the Casas-Alvero conjecture is true in degree d):

A d-2-t = • • • = A d-j+1-t = 0 (no substitutions if j = 2),
1. Initialize a set of candidate bad primes C = { }.

2. First run the basic algorithm with p = 0, but instead of just checking whether the reduced Gröbner basis of I aff Q (s) equals {1}, compute polynomials g 1 , . . . , g d-2 ∈ R for which (16) holds. Then add every prime factor appearing in the denominators of the g j to C.

3. If a prime p is not in C, it cannot be a bad prime because each of the expansions (16) can be reduced mod p. To find which candidate bad primes are actually bad primes, we run the basic algorithm for each p ∈ C.

An implementation of this method can be found in CAbadprimes.m.

(5.7) The hardest part is step 2, because of the computing in characteristic 0. Note that it is possible to give an upper bound for the elements of C purely in terms of d, so that step 2 could in principle be avoided. Indeed, see the discussion following (16) -the denominators of the solutions of the linear system can be bounded using Cramer's rule. But the bound one obtains is too large to be of any practical use.

(5.8) We have executed the algorithm for d = 5, d = 6 and d = 7. In case of d = 5, the total time needed was less than 0.03 seconds. For d = 6, the computer needed less than 3 seconds. A naive run of the algorithm for d = 7 is not expected to end in a reasonable amount of time, because the denominators become very hard to factor. But by using several monomial orders and computing greatest common divisors, one can make the case d = 7 feasible in Magma (apart from the factorization of one composite 119-digit number, for which we used the CADO-NFS package [START_REF] Shi Bai | CADO-NFS 1.1[END_REF]). The file CAbadprimes7test.m contains Magma code proving the correctness of our output. The case d = 8 lies out of reach. Of course, exhaustive lists of bad primes for increasing degrees become less and less interesting. But it would be good to have an idea on the growth of the largest bad prime, or on the number of bad primes. Such lists can also be helpful in detecting patterns (we could not observe any). By just repeating our basic algorithm for increasing values of p, it is feasible to find the smallest non-bad prime (that does not divide d), for d up to 10. We have put the outcomes in Table 2.

6 The Casas-Alvero conjecture in degree 12 (6.1) A direct application of the basic algorithm for degree d = 12 and characteristic p = 0 does not seem to be realistic. Two observations lead to a crucial speed-up:

• as remarked in (4.5), in view of the theoretical results obtained in Sections 2 and 3, it suffices to show that V C (s) = ∅ for a restricted set of scenarios s,

• for each such s, it actually suffices to show that V Fp (s) = ∅ for a single prime p, because the varieties are projective and take equations over Z.

(6.2) As for the first speed-up, by Theorem 2 and Proposition 16 it suffices to prove that V C (s) = ∅ for all scenarios s = (s 1 , . . . , s 11 ) for which

• s 1 = 0 = s 11 ,

• s 3 = s 9 ,

• s 4 = s 8 ,

• ind(s) satisfies the determinant condition mentioned in the énoncé of Theorem 2

(we omit the contribution of Proposition 9 to this discussion, because the arguments involved are rather subtle, whereas the computational gain is limited). Let L res be obtained from L (as introduced in (5.1)) by restricting to these scenarios. Then L res contains 0, 6, 718, 5210, 8918, 5404, 1352, 141, 5, 0, 0 scenarios of type 0, . . . , 10, respectively (this is less than was mentioned in [START_REF] Casas-Alvero | Higher order polar germs[END_REF], where only the determinant condition was taken into account). However, for the algorithm to work rigorously, the list L res should be slightly enlarged again, so that it becomes closed under taking descendants, in the following sense.

Definition 2. Let d > 0 be an integer and let s = (s 1 , . . . , s d-1 ) be a scenario for degree d. Let t = type(s). Then we say that s = (s 1 , . . . , s d-1 ) is a descendant of s if there exists a 1 ≤ j ≤ t such that for all i = 1, . . . , d -1

• s i = s i if s i < j,
• s i = 0 if s i = j,

• s i = s i -1 if s i > j.
This ensures that working in the affine subvariety P t = 1 (see (5.2)) and speeding up the algorithm (as in (5.5)) are still justified. Note that if s is a descendant of s, then type(s ) = type(s)-

2

 2

has multiplicity at least 2 (

 2 by the Gauss-Lucas theorem). This means that among the d roots of f , counting multiplicities, at least γ of them are not needed to find a common root for each derivative. If δ = 1, some non-vertex has multiplicity m, so another m -1 roots are superfluous. Therefore, at most d -γ -(m -1) roots are needed. If δ = 0, then the bound reads d -(γ -1) -(m -1). In both cases, the upper bound for type(f ) follows. The lower bound follows from an observation by Draisma and Knopper [7, Proposition 6].

Proposition 9 .

 9 Let d > 2 be an integer and let s = (s 1 , s 2 , . . . , s d-1 ) be a scenario for degree d. If 1. type(s) ∈ {0, 1, d -2}, or 2. type(s) ≤ d -3, the first d -2 -type(s) entries of s are zero, and among s d-1-type(s) , . . . , s d-1 there is a zero or two consecutive entries that are equal, then there are no CA-polynomials f ∈ C[x] for which scen(f ) = s.

  we get that c = 0. Proposition 11. Let f ∈ C[x] be a CA-polynomial of degree d, then f cannot have a root of multiplicity at least d -2.

2 - 1 ) 3 .

 213 = -m b b(b 2 -1) and looking at the sign, we see that -a < 1. Then m a > -am a = m b b + m 1 > m 1 which implies that m a ≥ 2 and m 1 ≤ d -5. In the case where m a = 2, m 1 = m b = 1, equations (6) give a(a + 1) 2 = 0. Thus this case cannot occur. We can readily deduce that m 0 ≤ d-5. The only possibility left is m a = m = d-4. From the relation -(d-4)a(1-a 2 ) = m b b(1-b 2 ), we deduce that φ(-a) ≤ φ(b) where we put φ(t) = t(1 -t 2 ). But φ is increasing on [0, 1/ √ 3] and we know that -a > b > 0. Thus we have -a > 1/ √ Now we get back to the linear equation in (6):

( 3 . 1 )

 31 We now turn our attention to certain special instances of d, in each case involving a prime number p. Inspired by Draisma and de Jong's take[START_REF] Draisma | On the Casas-Alvero conjecture[END_REF], we use p-adic valuations. Most of the proofs below have straightforward analogs in the original reduction-mod-p setting of Graf von Bothmer et al. But at some points, the valuation language does seem slightly more powerful. Our starting point is the existence of a mapv p : C → Q ∪ {+∞} satisfying • v p (a) = +∞ if and only if a = 0, • v p (ab) = v p (a) + v p (b) for all a, b ∈ C, • v p (a + b) ≥ min{v p (a), v p (b)} for all a, b ∈ C, and extending the usual p-adic valuation on Z (i.e. if n = p r • n with n prime to p, then v p (n) = r). See e.g. [12, Chapter 4, Theorem 1]. Note that the last property implies v p (a + b) = min{v p (a), v p (b)} if v p (a) = v p (b): we will make a frequent use of this fact.

( 3 . 3 )

 33 We use this to prove: Proposition 16. Let n ∈ Z >0 and k ∈ Z ≥0 be integers, and let f ∈ C[x] be a CA-polynomial of degree d = np k . Then

( 4 . 1 )

 41 Let k be an algebraically closed field and let d > 0 be an integer. The set of equivalence classes (in the sense of Lemma 6) of CA-polynomials of degree d will be denoted by CA k (d).

( 4 . 2 )

 42 We have a surjective map

Table 1 :

 1 Bad primes for degree 6 (53 primes)

		5	7	11
	13	19	23	29
	37	47	61	67
	73	97	257	811
	983	1069	1087	1187
	1487	1499	1901	2287
	3209	3877	3881	4019
	4943	5471	6983	8699
	9337	15131	15823	20771
	21379	23993	150203	266587
	547061	685177	885061	1030951
	7783207	17250187	40362599	9348983563
	70016757407	2610767527031 225833117528659 7390044713023799
	51313000813080529
	Theorem 4. There are
	• 9 bad primes for degree d = 5, namely,
		p = 2, 3, 7, 11, 131, 193, 599, 3541, and 8009,
	• 53 bad primes for degree d = 6, namely, the primes listed in Table 1,
	• 366 bad primes for degree d = 7, namely, the primes listed in the file
	badprimes7.txt that accompanies this paper -the smallest non-bad prime
	(apart from p = 7) is 127 -the largest bad prime is
	24984712021698392647916525667237483011737174983678606896870094983849
	9096141806825287856933123954724798488422551659890912229726792102063

  monomial ordering that first eliminates A 1 , . . . , A d-2-t and that behaves like grevlex on the remaining variables P 1 , . . . , P t-1

	-For s in L[t] do:
	* Let I aff k (s) ⊂ R be the ideal generated by F H (P sj ) for j = 2, . . . , d -(j) 1. Check whether or not I aff k (s) = R by checking if the reduced Gröbner basis (w.r.t. ≺) of I aff k (s) equals {1}. If it does not, set
	answer := yes and quit the loops.

Table 2 :

 2 The smallest non-bad prime p that does not divide d is a multiple of P 1 . For the same reason, this factor can be removed.

	one finds

H (P sj ) = F

  1. By closing L res under taking descendants, one obtains a list L cl res containing 1, 279, 3892, 12073, 13661, 6685, 1491, 146, 5, 0, 0

Available at https://perswww.kuleuven.be/˜u0040935/.

scenarios of type 0, . . . , 10, respectively. This might appear as a significant increase in the number of scenarios. However, note that scenarios of low type can be eliminated very easily.

(6.3) As for the second speed-up, based on the experimentally observed distribution of bad primes in degrees d ≤ 7, any prime p which is 'not too small' is most likely to work. If nevertheless the computation breaks down and a yes is printed, one can redo the computation using a different value of p. (In principle, it is possible to give a lower bound on p so that it is guaranteed to work, but this bound is much too large to be of any practical use -recall from Theorem 4 that the largest bad prime for d = 7 had already 135 decimal digits). Our first try was p = 10 7 + 17 and it immediately worked. It is convenient to use the same p for all scenarios listed in L cl res . At least, if a scenario s is treated modulo some p, then all of its subsequent descendants should be treated modulo the same p. Indeed, this enables us to conclude that the projective variety V Fp (s) is empty, and hence that V C (s) = ∅. (6.4) Magma code implementing the above method can be found in the file CAdeg12.m. We have executed the algorithm and the outcome was affirmative (i.e. the Casas-Alvero conjecture is true in degree 12, thereby proving Theorem 5). Approximate time and memory requirements can be found in Table 3. Our algorithm can in principle be generalized to higher degrees (note in particular that the two next open cases d = 20 and d = 24 are also of the form p + 1). But without new theoretical ingredients, an implementation of this is expected to demand astronomical amounts of time and memory.