Récemment, j’ai produit une preuve fausse du théorème de Schwarz-Zippel. Ce théorème, du plus grand intérêt, sert à donner une borne au nombre de zéros dans à un polynôme en n variables sur un corps fini
. Plus précisément, soit
, non-nul, de degré d. Alors le nombre de zéros est inférieur à
.
J’aurais eu envie de dire : pour chaque n-1 uplet , soit
, ce qui définit un polynôme à une indéterminée, de degré au plus d. Il a donc au plus d racines. On obtient ainsi
tels polynômes. Or,
est un zéro de P si et seulement si x_n est un zéro de
. D’où la borne sur le nombre de zéros.
Avez-vous vu l’erreur ?
Une vraie preuve a besoin d’une vraie récurrence. Ici on part du résultat bien connu pour les polynômes en une variable, et on l’étend. Une vraie preuve suppose le résultat vrai pour n-1 variables, et en déduit le résultat pour n variables.
2 commentaires
Comments feed for this article
25/01/2014 à 12:18
2pac
C’est en effet sournois !
Mais rien ne nous dit que le polynôme à une indéterminée ainsi construit n’est pas nul : il pourrait ainsi avoir q racines, et le raisonnement tombe à l’eau.
Imaginons par exemple que la nième variable soit muette. Rien ne m’empêche de définir P(X,Y)=Q(X). Si X est racine de Q, alors le polynôme à une variable qu’utilise ta démonstration est nul, et il possède q racines. En revanche, si X n’est pas racine de Q, il n’y aura aucune racine; ce qui fait que l’on trouve, in fine, une borne cohérente…
Une vraie récurrence est donc la seule manière de conclure proprement !
25/01/2014 à 12:33
pybienvenu
Exactement !! Bravo 2pac !