Addenda to Casas-Alvero Conjecture: Polynomial Derivatives and Common Roots.

In this research work, the Casas-Alvero conjecture is explored, focusing on polynomials and their derivatives, and the common roots they share. The study delves into the normalization of roots under various transformations, using p-adic methods and Gröbner bases. Noteworthy findings include implications for low-degree polynomials, applications of the Gauss-Lucas theorem, and an alternative proof in degree 4. This comprehensive examination provides insights into the intersection of algebra and arithmetic in addressing this intriguing conjecture.

• Casas-Alvero Conjecture
• Polynomials
• Derivatives
• Common Roots
• Algebra-Arithmetic Intersection.

lker Follow

Uploaded on Nov 13, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Some addenda to the Casas-Alvero conjecture Wouter Castryck (KU Leuven) joint work with Robert Laterveer and Myriam Ouna es (Univ. Strasbourg) Arithm tique en Plat Pays (Univ. Lille-1) December 10, 2012

2. Statement Consider a polynomial = + + + + 1 d d C ( ) ... ( ) f x a x a x a x a a 0 1 1 d d i along with its derivatives = + ) 1 + + ) 1 ( 1 2 d d ( ) ( ... f x da x d a x a 0 1 1 d = ) 1 + ( d ( ) ! ( 1 )! . f x d a x d a 0 1 (x ) f Suppose that each derivative has a root in common with , i.e. } 1 = = ( ) i C 1 { ,..., : ( ) ( ) . 0 i d c f c f c Conjecture (E. Casas-Alvero, 2001): These common roots are all the same, and hence = d ( ) ( ) f x a x c 0 C c for some .

3. Part I: Introduction Part II: p-Adic methods Part III: Gr bner bases

4. INTRO p-ADIC METHODS GR BNER BASES Normalization The relative position of the roots of a polynomial and those of its derivatives does not change under transformations of the form + bx af x f ( ) ( ), , . 0 c a b Geometrically: rotations, translations, stretchings of the complex plane. Example: i i i ) + ( ( ( ( ) ) ) ) ( ( ( ( f f f f x x x x af af af af x e re re ) x x ) ) x c = ) 1 + 3 2 ( ) ( 1 )( f x x x x ) 1 ( ) 2 ( ) 3 ( ( ) ( ) ( ) f x f x f x ) 4 ( ) 5 ( ( ) ( ) f x f x Corollary: If there exists a counterexample to the Casas-Alvero conjecture, then there exists a counterexample of the form )( 1 ( ) ( = x x x x f + + + 2 3 4 d d ... ). a x a 1 3 d

5. INTRO p-ADIC METHODS GR BNER BASES Example: CA conjecture in low degree Degree 3. ( f = ) 1 2 ) ( x x = x x ) 2 ( ( ) 6 2 f x Degree 4. ( f = 2 C a ) ( 1 )( + ) ( ) x x = x x a a + ) 2 ( 2 ( ) 12 ( 6 ) 6 2 f x x a x a 2 , 0 { 3 , 3 / / 2 } a / 1 , 1 { = ) 3 ( 3 , 3 } ( ) 24 6 6 f x x a Degree 5. ( f = + + 2 C ) ( 1 )( )( + ) + ( , ) x x = x x a x b a + b , 1 , 0 a , b Plugging in yields 4 systems of non-linear equations Their insolvability can be checked using Gr bner bases (see later). in the variables ) 2 ( 3 2 ( ) 20 12 ( ) 1 ( 6 ) 2 f x x a b x ab a b x ab = = + + ) 1 + + + + + ) 3 ( 2 ( ) 60 24 ( ( 6 ) f x x a b x ab a b ,b . a ) 4 ( ( ) 120 24 ( ) 1 f x x a b Feasible up to degree 8. (Diaz-Toca, Gonzalez-Vega, 2006)

6. INTRO p-ADIC METHODS GR BNER BASES The Gauss-Lucas theorem ) (x ) 1 ( ( ) f x f Rolle: If all roots of are contained in a line, then the roots of are contained in the intervals separated by the roots of . (x ) f (x ) f ) 1 ( ( ) f x A weak generalization is: ) 1 ( (x ) Gauss-Lucas: The roots of are inside the convex hull of the roots of . ) ( x f f (x ) f ia a ,..., 1 ) 1 ( f d a ) x Explicit formula: if are the roots of and is a root of different from all s, then = = d a ( a d 1 a i 2 a a 1 i i . 1 = i 2 a a 1 i

7. INTRO p-ADIC METHODS GR BNER BASES Alternative proof in degree 4 A Casas-Alvero counterexample has a root of multiplicity at least 2. Thus we have the following possible configurations of the roots: A similar proof can be given in degree 5.

8. INTRO p-ADIC METHODS GR BNER BASES Refining Gauss-Lucas? Difficult problem. Jensen, 1913: Suppose that the roots of are distributed symmetrically about a line. Then the roots of are contained in the union of the symmetry axis and the Jensen disks. (x ) f ) 1 ( ( ) f x (x ) f Conjecture (Sendov, 1958): Suppose that all roots of can be caught in a closed disk of radius . Then if one centers a closed disk of radius around a root of , it will always contain a root of . ) (x f R R ) 1 ( ( ) f x Open for degree > 8. Extremal case: . d 1 x

9. INTRO p-ADIC METHODS GR BNER BASES Casas-Alvero: current state of the art Known constraints: { , } 1a a Number of recycled roots > 2. If is a pair of distinct roots of a polynomial , then there is at least one such that neither nor (Draisma, de Jong, Knopper). 2 (x ) f = = ( ) i i ( ) i (1 a ) 0 f ( ) 0 f a 2 Number of distinct roots > 4. Degree > 19. The Casas-Alvero conjecture is true in degrees = = = k k , 2 p d p d p (Graf von Bothmer, Labs, Schicho, van de Woestijne) 2 k 3 d p if (same idea) = k 4 d p 7 , 5 , 3 p ( ) if = k 7 d p with 366 exceptional primes, the largest one being 249847120216983926479165256672374830117371749836786068968700949838499096141806825287856933123954724798488422551659890912229726792102063 = 12 d ( , Laterveer, Ouna es)

10. INTRO p-ADIC METHODS GR BNER BASES Number of recycled roots > 2 { , } 1a a Draisma, de Jong, Knopper, 2010: If is a pair of distinct roots of a polynomial , then there is at least one such that neither nor . 0 ) ( 2 = a f 2 = ( ) i (1 a ) 0 f (x ) f i ( ) i Proof: By contradiction. Normalize: , leading coefficient Write ) ( 1 + = x a x x f = = f 0 ) 0 ( = f Now is a linear function, so with graph either ) ( x f x But then is strictly increasing or decreasing on And so on... = = . 1 , 0 1 a a 1 2 + + 1 d d C ... x ( ). a a 1 d i ! d ) 1 ) 2 + d ( ( d d = ( + (x )! 1 + 2 ( ( ) ) ! 1 f f and so on... so is a real polynomial. ) f x x d ! 2 x d a )! ( ( 2 )! x a x d a R 1a2 1 1 . 1 , 0 R 2 a ) 1 ) 2 ) 1 d ) 1 ) 2 = = ( ( ( ( d d d d ) 0 ( ( d 0 ) ) 1 ( ) 1 ( 0 0 f f ( or or ) 3 ( x f x . 1 , 0 d ( ) 2 But then is strictly increasing or decreasing on ) ( x f x x or (x 1 , 0 ) f One eventually finds that is strictly in- or decreasing on : impossible. d ( ) 1 ( ) f x So is either strictly positive or strictly negative on the interval . 1 , 0 So again strictly positive or strictly negative...

11. INTRO p-ADIC METHODS GR BNER BASES Number of distinct roots > 4 Corollary (to the previous result): The Gauss-Lucas hull of a counterexample to the Casas-Alvero conjecture contains at least 2 roots in its interior. (x ) f Proof: Let be a counterexample to the Casas-Alvero conjecture. Let be a root of that is located on the boundary of the Gauss- Lucas hull with maximal multiplicity. (x ) a f a a Only roots that need to be recycled: and (some of) the interior roots. So by Draisma et al.: at least 2 interior roots. Thus: at least 4 roots in total. If exactly 4, then these are contained in a line. Using Rolle, one can exclude the latter case (omitted here, nothing deep).

12. Part I: Introduction Part II: p-Adic methods Part III: Gr bner bases

13. INTRO p-ADIC METHODS GR BNER BASES p-adic valuations Biggest breakthrough thus far: Graf von Bothmer, Labs, Schicho and van de Woestijne, 2007. Their proof was rewritten in more elementary language by Draisma and de Jong in 2010, using p-adic valuations. = = pe | x . (x ) 0 ( ) e vp p v Over the integers. largest exponent such that =N Z) ( = + ( ) ( ) ( ) v ab v a v b and p v p p p ( ( Note: + ( ) min( ), ( )) b v a b v a ) v b ( p p p ) (equality if ) v p a v = ( / ) ( = Z ) ( ) v x y v x v y Over the rationals. p p p p Q) ( p v Note: C p v Q C Over the complex numbers. Possible to extend to (via ). Far from unique! p = Q C) ( p v Here:

14. INTRO p-ADIC METHODS GR BNER BASES Valuations of binomial coefficients p ! p = ( ! r )! r p r p , 0 p , r = 0 vp if r p 2 , 1 . = ,..., 1 r p 1 vp if r + ( ) ( ) ( ) n s n r s r s n Special case of: Legendre: p p p = , v p 1 r p where is the sum of the p-adic digits of . ) (x sp x n = n p vp r r So: the number of carries when adding to in base . r

15. INTRO p-ADIC METHODS GR BNER BASES Proof of the Casas-Alvero conjecture in degree p By contradiction. Let p p p = + + + + 1 2 p p p C ( ) ... x ( ) f x x a x a x a a 1 2 1 p i 1 2 1 p be a counterexample. ep e Using a normalization of the form , we may assume: ( f min vp : 1 = p j For z ( vp ) ( ) x p f p 0 0 = x = ( ) ( ) z f z Derivative of a term: ! 1 p 1 = ) 0 z Now: evaluate in a root with : ) 1 (1 a = + ( p ) 0 evaluate in a common root : z vp ( ) f x x a ( ) j ! 1 p p ( )! 1 p 1 p k a ( ( )! )! p ! ! p + p k p j p p ) : ( j 0 1 2 = z p k p k j = = 2 p p k k j j a x 2 a p 2 x a a a kx kx k = k ( )! p k = p ! 2 p k + p k j ( ( ... )! )! 1 ( ! ( ! p )! )! p p k k j j k k a p p z 1 k j For = + + p p f z z z 1 2 2 p j ! p ) 2 z z = + a + p 2 ( 2 p So: ( ) f x x p 1 a x a p 2 ( ) 0 vp p a similarly: a p x = k j a kx p 1 2 1 p 2 2 ! ( p )! a k 2 z p 2 j j ) = 1 2 p 1 ... z a 1 p j p j ( )! p j p 1 1 = ) i + + + + ( 1 j p j p j j p ( pa v ) ... f x ( x a x a and so on: all s non-negative 1 2 p j ! p j p

16. INTRO p-ADIC METHODS GR BNER BASES Degrees pk, 2pk, 3pk, ... r p k p 2 2 ... 2 k p : still true that as soon as . k p r 0 v k 0 p p k k k p 1 p still gives the desired contradiction. k k = 1 p p z a z a z a z 1 k 1 k p 1 p k 2 p : still true that as soon as , unless when . 0 r Counterexample: ( f k r = 2 If , the Casas-Alvero conjecture is true over any field. 2 = p n k v k p 0 2 r p p k 2 k k k p 2 2 2 p 1 p p z = x k k k k p 3 If , the Casas-Alvero conjecture is true over any field of characteristic not 2. n = 2 2 1 2 2 p p p ... ... a z a z a z a z 1 2 k k 2 1 2 k p k p 2 1 p ) 1 p = 2 ( ) ( f x x ( ) . 0 v pa would still give the desired contradiction if we would know that Following the same line of thinking: = = ) 1 ( 2 2 k ) 3 2 x x x x p (x f ) p 2 Idea: reduce mod to f p n = = But this we know! Graf von Bothmer et al.: Let be a prime number. If the Casas-Alvero conjecture holds in degree over , then it holds in degree over , for each non-negative integer . k integer factorization. Feasible up to . 7 = n ) 2 ( ( ) 0 x x k 2 p k k p + 2 p ( ) p F mod . k x b x b a p with C np 1 1 k k p The list of bad s can be computed using a Gr bner basis computation and p p 1 F 2+ 0 mod b p Then satisfies CA conditions over x b x 1 p

17. INTRO p-ADIC METHODS GR BNER BASES Constraints in degree p + 1 Same normalization: let + + + + + + p pb v 1 1 1 1 1 1 1 p p p p p px + + x 1 2 x = + + + + + + = ) + 1 1 1 2 2 1 p p p p p p C C ) ( ... ... ( ( ) ) ( x f x x x a a x x a a x x a a f a 2 2 1 1 p p i i ) i 2 2 1 1 1 p p ( 0 0 = 0 be a counterexample, where we may assume . 0 ) 1 ( = f ... )( 1 ( ) ( 2 x b x x x f + + = + 1 p p p = ) b min ( ) ( ) vp z f z p This implies that all other roots have valuation > 0. In particular, 1 is a simple root. Summarizing: ( ( ) ) 0 v v pa pa + + + As before, we obtain that all s are non-negative. In addition: Now 1 ) 1 ( 0 so for at least one . 0 ) ( = i v Pushing the argument further, one can show that this root must be recycled at least twice more. 1 1 1 p p p i i + p x 2 + ( + + 1 1 2 p p p ... x x f a x a x 1 1 x x 2 1 p + 1 1 1 2 1 1 p p ( ) p The root of must be recycled at least once more (not by the first ) + + + + + = + 2 + 1 1 + p 1 1 1 p p 2 p p 2 1 a 1 = 1 p p p p ( + ) 0 ) 2 b ( p b derivative). x x + 1 1 + p p p p x x px px 1 z z p = p + a + p + + + + a a + f = + 1 + p + 1 1 = ( 1 p ... ... a a p a a ... + p 1 + b + + 2 p 2 p x ( ( ) a z z v z v 2 1 p 2 ... 1 p 1 2 1 p 1 2 x 1 2 x p p ) 0 x b + + + p 1 p p px a 2 2 p (1= px i 2 1 p pa ) 0 implies . vp 2 1 p ( ) ) 0 p b b v 1 p p px p p Note that But as before Moreover: severe constraints on the indices for which has a common root with the last derivative. + 1 1 p i ( ) ji r ( ) 2 ... f x i i + p f = ( + ( + x = 2 + x ( i + ) coefficients with 1 p ( )! ) f ( + 1 x )! ) ! ( p 1 i )! 2 ( + ) i f x p x = p p v a + p a x ... a i 1 i ! 1 1 0 x ) 1 1 + 1 ) p i i i , a 2 i ( p so is a root of . so for such an , the common root of and should be 1. i This will prove useful in the next part. We may assume (via ). 1 a 0 1= ) 1 + ( p (x ) f 1a ( ) ( ) ( ) f x a f a x 1 1 + ( 1 ) i (x ( ) f x

18. Part I: Introduction Part II: p-Adic methods Part III: Gr bner bases

19. INTRO p-ADIC METHODS GR BNER BASES Proving the unsolvability of a linear system Given a linear system of equations: + + + + = : ... + , 0 = V a x a x a x a x b 1 11 1 12 a 2 13 a 3 x 1 a 1 b n n x + + + : ... , 0 V a x x 2 21 1 22 2 23 3 2 2 n n V + x x + + + = : ... . 0 a a a x a x b 1 1 2 2 3 3 m m m m mn n m How do we verify that it has no solutions? Method: Gaussian elimination. C + 2x 0 ( ) V eliminate coefficient of , then of , ... cV c i i 1x operations are invertible, so solution set does not change 0 C ( , 0 = ) V V cV c i j i i j throw away equations 1= . 0 ... until one finds the equation

20. INTRO p-ADIC METHODS GR BNER BASES Proving the unsolvability of a non-linear system Given a system of polynomial equations: = : ( , ,..., ) 0 V f x x x 1 1 1 2 n = : ( , ,..., ) , 0 V f x x x 2 2 1 2 n V x = : ( , ,..., ) . 0 f x x 1 2 m m n How do we verify that it has no solutions? Method: Buchberger s algorithm. eliminate coefficients of monomials in V 1 x x 0 = C + 3 1 x x 0 ( ) V lexicographical order (for instance). 2 3 : 1 2 1 + x V throw away equations reduce these modulo the former system cV c i i V ij V ij operations are invertible, so solution set does not change + 5 2 ( ( ) ) V add m m m m V ji V ji i i j + . 0 j + may create new solutions... 2 2 V x 3 x x x x i i i j j 2 3 2 2 3 x V 1 2 4 2 2 2 : 2 1 2 1 1= . 0 ... until one finds the equation Works by Hilbert s Basis Theorem and Hilbert s Nullstellensatz. Worst-case complexity: horrendous.

21. INTRO p-ADIC METHODS GR BNER BASES Back to Casas-Alvero We will stick to , the smallest case not covered by the p-adic method. 12 = d Hypothetical counterexample: = 2 ( ) ( 1 )( )( ) ( ). f x x x x a x a x a 5 5 2 3 10 1= a 0= 1 We set and . 0 a We call (1,2,3,1,3,4,7,0,2,7) a scenario for this counterexample. One reason for to be a counterexample could be: ) (x f If there are no counterexamples corresponding to (1,2,3,1,3,4,7,0,2,7), then there are no counterexamples corresponding to (1,2,3,1,3,4,5,0,2,5), and vice versa. = = = = = ) 2 ( ) 3 ( ) 4 ( ) 5 ( ) 6 ( ( ) , 0 = ( ) , 0 = ( ) , 0 = ( ) , 0 = ( ) , 0 = f a f a f a f a f a 1 2 3 1 a 3 7 ( ) ) 8 ( ) 9 ( 10 ( ) 11 ( ) ( ) , 0 ( ) , 0 ( ) , 0 ( ) , 0 ( ) . 0 f a f a f a f f a 4 7 0 2 7 system of 10 equations in 9 variables, that can be verified using Buchberger. It suffices to consider the scenarios for which . , ( 1 s s 1 + max ,..., s s i s ,..., ) s 1 1 i 2 10 Problems: Each system would take a lifetime on a computer with an astronomical amount of memory. 29 392 systems (applying the stuff to ). 1110 systems 678 570 systems = + 11 1 p p There are 1110 such systems.

22. INTRO p-ADIC METHODS GR BNER BASES Hybrid representation Suppose we wish to exclude counterexamples + 1 p By the stuff: the number of unused variables is at least 2. = 2 + b 4 b ) + x + + )( b + 5 4 3 2 ( ) ( 1 )( )( )( ) f x x x x a x a x a ( ( )( 1 x b )( x )( ) x x a x a b a 3 x a x x 5 a x 2 3 5 6 7 8 9 10 2 In fact, the lower the number of unused variables, the more restrictive the condition becomes. p that match with the scenario (1,2,0,3,1,4,5,0,2,2). + 1 System: # unused time per case memory # scenarios # scenarios (with p+1 stuff) 0 = = = = = ) 2 ( ) 3 ( ) 4 ( ) 5 ( ) 6 ( ( ) , 0 = ( ) , 0 ( ) , 0 ( ) , 0 = ( ) , 0 = 0 5 146 1469 6298 11586 8172 1668 48 0 f a f a f a f a 1 f a 1 2 0 3 1 a 0 1 2 impossible = = 7 ( ) ) 8 ( ) 9 ( 10 ( ) 11 ( ) ( ) , 0 impossible 3 weeks 20 hours 15 minutes 10 seconds 0.01 seconds negligible negligible negligible negligible ( ) , 0 ( ) , 0 ( ) , 0 ( ) . 0 f a f a f a f a 55 1155 11880 63987 179487 246730 145750 28501 1023 1 f 4 5 0 2 2 90 GB Note that the variables are never being plugged in. 8 7 6 , , , a a a a 3 4 5 6 7 8 9 10 , a 9 10 GB 1.4 GB 0.2 GB 0.1 GB negligible negligible negligible negligible 10 We use an according hybrid representation for . ) (x f So: the more unused variables, the easier the system becomes! , , , , b b b b b Advantage: the variables appear linearly in all equations of the system. 1 2 3 4 5 They can be get rid of using Gaussian elimination.

23. INTRO p-ADIC METHODS GR BNER BASES Some details that were suppressed Computations are done modulo a small prime p to avoid coefficient inflation (some theoretical justification needed). Instead of Buchberger s algorithm, we used Faug res F4 method. Instead of the lexicographical order, we used grevlex.

24. and now...? It seems unlikely that the p-adic method will ever lead to a complete proof. Without new insights, pushing the Gr bner basis method to the next open case ( ) is utopic. And in any case, Gr bner bases can only check one at a time, so they will never lead to a complete proof. d = 20 d A larger unexploited area seems to lie at the analytic side of the story (so far, only algebrists have attacked this problem). WARNING: This is an addictive problem.