Critère d'Hermite

Olympiades mathématiques, énigmes et défis
Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

Critère d'Hermite

par Ben314 » 06 Déc 2016, 20:33

Salut à tous.
Pour ne pas poluer ni son thread, ni de façon plus générale la section "supérieure", je reprend un post d'Archytas concernant le "critère d'Hermite" que je ne conaissait pas :
Archytas a écrit:Soit avec premier et et .
La fonction polynôme associée à : est une permutation de si et seulement si :
(*) admet exactement une racine dans .
(**) t.q. , si est le reste de la division de par , on a .

J'ai cherché à démontrer le bidule, sauf que je trouve pas exactement ça comme C.N.S (mais quelque chose de très proche dans la formulation).
D'où deux questions :
- Est-ce vrai ou pas ?
- Quelles est la C.N.S. que j'ai trouvé ?
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius



Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

Re: Critère d'Hermite

par Doraki » 07 Déc 2016, 01:19

P^k c'est P multiplié avec lui-même k fois ou P composé avec lui-même k fois ?

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

Re: Critère d'Hermite

par Ben314 » 07 Déc 2016, 01:33

P^k, c'est P multiplié par lui même k fois.
J'aurais du préciser car le contexte (des permutations) prête fortement à confusion...

Sinon, s'il y en a qui veulent chercher et qui voudraient une petite indication (que j'avais), il y en a une... petite dans le thread de départ :
superieur/correction-incomprise-t180353.html

Et sinon, j'ai pas bien vu quel pouvait-être l'intérêt de ce critère (dans un sens comme dans l'autre) donc s'il y en a qui ont une idée de ce à quoi ça peut éventuellement servir...
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

Re: Critère d'Hermite

par Doraki » 07 Déc 2016, 12:05

Ben pour l'instant, la condition que p ne divise pas k m'a l'air de servir à rien
(parceque P^(np) = (P^n)^p, et donc R(np) va être Frob(R(n)) si je me gourre pas, donc le coeff de l'un est nul si et seulement si le coeff de l'autre est nul)
Enfin ça sert à faire remarquer qu'ils sont redondants quoi.

Ensuite, R(n) est le polynôme interpolateur de P^n, donc on devrait pouvoir traduire la condition en termes des valeurs prises par P sur Fq. Si je me gourre toujours pas, que le coefficient en question soit nul revient à dire que la somme pour x dans Fq des f(x)^n est nulle (pas exactement trivial à montrer)

Donc le problème revient à montrer que si on a un multi-ensemble {x1...xq} d'éléments de Fq,
alors ce multi-ensemble est Fq <=> il y a un seul zéro et x1+...+xq = x1^2+...+xq^2 = ... = x1^(q-2)+...+xq^(q-2) = 0 (perso moi le critère je le préfère LARGEMENT sous cette forme)

Il me semble qu'avec les identités de Newton et en appliquant l'automorphisme de Frobenius comme il faut, on devrait pouvoir s'en sortir en montrant que (T-x1)...(T-xq) = T^q - T. (faut que je vérifie...)

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

Re: Critère d'Hermite

par Ben314 » 07 Déc 2016, 13:19

J'ai tenu exactement le même raisonnement mais j'avais pas cherché à utiliser le Frobenius pour voir qu'il y avait "redondance" dans les conditions.
Donc la C.N.S. que j'avais l'impression de trouver, via les identités de Newton, c'était que les x1^k+x2^k+...xq^k étaient tous nuls pour k dans {1..q-2} sans restriction particulière sur k (mais sans avoir besoin de supposer qu'il y a un seul zéro).

Mais en fait, en réfléchissant un peu, j'ai du me planter car si le "multi ensemble" {x1,...,xq} est réduit à un seul élément x alors x1^k+x2^k+...xq^k=q.x^k=0 pour absolument tout les k donc il doit falloir mettre une "petite hypothèse" quelque part pour éviter ce cas de figure.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

Re: Critère d'Hermite

par Doraki » 07 Déc 2016, 15:14

Si toutes les somme des xi^n pour n=1 à q-2 sont nulles, d'après les identités de Newton, ça implique que
Q(T) = (T-x1)...(T-xq) est de la forme f(T^p) + aT + b, c'est-à-dire que Q'(T) est un polynôme constant.

Maintenant, si Q' est constant alors ou bien il est non nul et toutes les racines sont simples ou bien il est nul et elles sont toutes multiples (parceque les règles de dérivation d'un produit marchent toujours)

Si on suppose donc que 0 est une racine simple de Q, alors comme Q est scindé sur Fq, la seule possibilité est que {xi} = Fq, et donc que le polynôme initial était une permutation.

Par contre si 0 est racine multiple (ou pas racine du tout) alors Q' = 0 et je ne sais pas du tout à quoi peut ressembler Q.
Y'a le cas où les seuls coefficients non nuls sont ceux de T^(p^k), alors Q est un "polynôme affine" (il vérifie Q(x+y) + Q(0) = Q(x) + Q(y)), et dans ce cas là les racines de Q sont un sous-espace affine de Fq (vu comme espace affine sur Fp) toutes avec la même multiplicité.

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

Re: Critère d'Hermite

par Ben314 » 07 Déc 2016, 16:25

En fait, je sais où je me suis planté : j'ai pas regardé suffisamment dans le détail comment, on remontait des sommes de Newton aux polynômes symétriques élémentaires et j'ai "raté" le fait qu'il y avait des divisions à faire qui, dans le cas d'un corps de caractéristique p, ne sont licites que si l'on divise par un entier non divisible par p.
Ca explique que javais loupé ton f(T^p) et que j'avais pas l'impression qu'il y avait besoin d'hypothèses supplémentaires.
Bref, maintenant, ça me semble O.K. est assez clair (modulo les question intéressante que tu pose, mais dont les réponses ne sont pas utiles à la preuve du bidule)
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

Re: Critère d'Hermite

par Ben314 » 08 Déc 2016, 15:31

Doraki a écrit:Par contre si 0 est racine multiple (ou pas racine du tout) alors Q' = 0 et je ne sais pas du tout à quoi peut ressembler Q.
Toujours en supposant que Q est scindé, je pense avoir montré que toutes les racines de Q sont d'ordre >=p et je conjecturerais bien qu'elles sont d'ordre un multiple de p, c'est à dire que
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

Re: Critère d'Hermite

par Doraki » 08 Déc 2016, 16:32

Ben en fait (toujours en ayant comme hypothèse que les sommes de xi^k sont nulles pour k=0... q-2)
si Q' = 0 ça veut dire que a=0 (et que somme de xi^(q-1) = 0) et donc que Q est de la forme f(T^p), et comme Frob est surjectif sur Fq, Q(T) = g(T)^p pour un certain polynôme g scindé sur Fq de degré q/p.

En y repensant, si {x1...xq} sont regroupés en groupes de p, toutes les sommes vont évidemment être nulles lol.

Donc on a fait le tour des possibilités je crois.

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

Re: Critère d'Hermite

par Ben314 » 08 Déc 2016, 19:01

Effectivement : ça marche directement comme ça et c'est plus simple que ce que j'avais fini par trouver qui consistait à dire que, si on décompose f tel que f(T^p)=Q(T) en facteur irréductible f=f1xf2... alors, fk(T^p) est scindé vu que c'est "un morceau" de Q(T) qui est scindé et cela prouve que fk admet au moins une racine.
Et comme fk est supposé irréductible, ça prouve qu'il est de degré 1 donc f est scindé et Q(T) est un produit de (T^p-y_k), c'est à dire de (T-x_k)^p.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Archytas
Habitué(e)
Messages: 1223
Enregistré le: 19 Fév 2012, 15:29

Re: Critère d'Hermite

par Archytas » 11 Déc 2016, 03:42

Salut,
Je viens finir la correction du bouquin ici, au cas où quelqu'un retombe sur le même problème (c'est issu d'un exercice du livre "algèbre concrète" de Maurice Mignotte). Je suis désolé si je répète ce qui a été dit, j'ai pas le courage de tout relire :/. On commence par poser comme lemme (comme l'a constaté Doraki) que pour q éléments de on a les équivalences suivantes:
(i)
(ii) tel que p ne divise pas t et pour t=q-1
(iii) et pour t =q-1
Pour le montrer on pose justement (la deuxième inégalité est justifiée par le premier post). Mais c'est aussi et surtout l'indicatrice de . Ainsi avec on a :
(*) les sont distincts si et seulement si g est constance égale à 1. L’intérêt de l'écriture sous forme de somme est qu'on peut écrire g comme un polynôme en X.

en supposant (i) c'est un polynôme à coefficients dans un corps et qui coïncide en q points avec 1. C'est donc g=1 et on en déduit le point (iii) la réciproque se fait de la même façon sachant que (*) est une équivalence.
On a en plus trivialement (iii) implique (ii) et sachant (ii) en écrivant tel que s ne divise pas p, on obtient (iii).


On peut ensuite s'attaquer au critère d'Hermite ; On prend une permutation
La première condition du critère est facile. Pour la deuxième condition j'ai pas compris ce que l'auteur a fait donc j'ai essayé de faire à ma sauce... Mea culpa si c'est pas correct ou inutilement compliqué :lol: .
On remarque déjà que puisque , f et [f] (f modulo ont la même image quand on leur fait manger un élément de . Donc avec t<q-1 et
on a donc on on a bien la deuxième condition.
Avec des arguments du même genre, la réciproque est pas compliquée.

Pour ce qui est des implications du critère, y en a une que l'auteur donne que je trouve méga super cool :
Corollaire:
Soit de degré d qui divise q-1 alors f n'est pas une permutation.
La démonstration tient en une ligne : est de degré q-1 donc la deuxième condition d'Hermite n'a pas lieu.
ça redémontre que par exemple le carré n'est jamais surjectif dans les corps finis mais par exemple on sait qu'un polynôme de degré 5 ne sera jamais une permutation dans entre autre.
Voilà voilà, j'espère avoir pu éclairé quelqu'un!

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

Re: Critère d'Hermite

par Ben314 » 11 Déc 2016, 13:46

Juste une question concernant le fait que (*) est une équivalence :
Comment l'auteur procède t'il pour montrer que g=1 => les ai sont distincts ?
(Avec Doraki, on a utilisé les formules donnant le lien entre les sommes de Newton et les polynômes symétriques mais il y a peut-être plus élémentaire.)
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Archytas
Habitué(e)
Messages: 1223
Enregistré le: 19 Fév 2012, 15:29

Re: Critère d'Hermite

par Archytas » 13 Déc 2016, 01:51

Et bien c'est tout simplement une somme d'indicatrice, pour peu que deux ai soient égaux g prendrait une valeur plus grande que 2.

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

Re: Critère d'Hermite

par Doraki » 13 Déc 2016, 01:54

c'est magique

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

Re: Critère d'Hermite

par Ben314 » 13 Déc 2016, 13:33

oui....
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Archytas
Habitué(e)
Messages: 1223
Enregistré le: 19 Fév 2012, 15:29

Re: Critère d'Hermite

par Archytas » 13 Déc 2016, 14:39

C'est pas ça? L'auteur dit juste que c'est équivalent et que c'est évident, et donne pas plus de détail

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

Re: Critère d'Hermite

par Ben314 » 13 Déc 2016, 14:53

Si, c'est tout à fait ça.
Avec Doraki, on était parti sur le premier truc qui nous était venu à l'esprit vu la forme de la question, c'est à dire d'utiliser les liens bien connus entre les polynômes symétriques élémentaires et les sommes de Newton.
Et, comme souvent, lorsque tu as trouvé UNE façon d'aborder le problème, tu as du mal à en trouver une autre donc ni lui, ni moi n'avons vu qu'il y avait un argument extraordinairement (*) plus élémentaire que celui qu'on a employé...

(*) D'où le commentaire "magique" de Doraki....
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Archytas
Habitué(e)
Messages: 1223
Enregistré le: 19 Fév 2012, 15:29

Re: Critère d'Hermite

par Archytas » 14 Déc 2016, 00:22

Ah d'accord ^^!
En tout cas ce critère et sa démonstration je les trouve très élégants (:

Milany
Messages: 7
Enregistré le: 31 Mai 2023, 14:46

Re: Critère d'Hermite

par Milany » 31 Mai 2023, 15:23

Bonjour

je suis entraine d'essayer de comprendre la démonstration de ce critère
Dans l'ouvrage "finite fields by Lidl and Niederreiter," , ils ont vérifié que cette somme est nulle

https://imgur.com/cb8mNnx
Image


je n'ai pas compris pourquoi ils ont vérifié ceci

et à la fin d'après ce que j'ai compris comme la somme est nul donc les f(c) sont distincts pour tout c dans Fq donc f est une permutation sur Fq

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

Re: Critère d'Hermite

par Ben314 » 31 Mai 2023, 16:29

Salut,
koomath a écrit:
C'est plutôt des que des dans les exposants (je vois pas ce que représenterais vu le contexte).

Mais bon, d'un autre coté, j'ai pas vraiment compris la question de Milany . . .
Modifié en dernier par Ben314 le 31 Mai 2023, 16:35, modifié 1 fois.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 4 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite