Théorème de Schur
![Page d’aide sur l’homonymie](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Logo_disambig.svg/20px-Logo_disambig.svg.png)
Pour d'autres théorèmes de Schur[1], voir Issai Schur.
En mathématiques, il existe plusieurs théorèmes de Schur.
Un théorème de Schur garantit qu'il n'existe pas de partition finie de l'ensemble des entiers strictement positifs par des sous-ensembles sans somme. Il est généralisé par le théorème de Folkman.
Concrètement[2],[3], si l'on attribue une couleur à chaque entier d'un même sous-ensemble de la partition, il existe trois entiers x, y, z de même couleur (avec x et y non nécessairement distincts) tels que x + y = z.
Plus précisément[4], si c est le nombre de couleurs utilisées, il existe[5] un plus petit entier S(c), appelé nombre de Schur, tel que l'ensemble fini {1, ..., S(c)} ne puisse pas être partitionné en c ensembles sans sommes (on appelle parfois plutôt[6] « nombre de Schur » l'entier s(c) = S(c) – 1, c'est-à-dire le plus grand entier tel que {1, ..., s(c)} puisse être partitionné en c ensembles sans sommes). En 2024 on ne connaît la valeur de S(c) que pour c = 1, 2, 3, 4 et 5 : 0, 5, 14, 45 et 161.
Cas c = 2
Montrons que S(2) = 5.
- Il existe une partition et une seule de {1, … ,4} en deux parties dont aucune ne contient trois entiers x, y, z tels que x + y = z. En effet, la partition 1, 2, 3, 4 convient, et c'est bien la seule car en appelant « bleu » la couleur de 1 et « vert » l'autre couleur, 2 doit être vert (car 1 + 1 = 2) donc 4 doit être bleu (car 2 + 2 = 4) donc 3 doit être vert (car 1 + 3 = 4).
- Il est impossible d'ajouter 5 à l'une des deux parties sans créer une somme x + y = 5 dans cette partie, car on aura 5 = 1 + 4 ou 5 = 2 + 3.
Cas c = 3
Montrons que S(3) est au moins égal à 14. Il existe une partition de {1, … ,13} en trois parties dont aucune ne contient trois entiers x, y, z tels que x + y = z, à savoir la partition suivante : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13. On remarque qu'il est impossible d'ajouter 14, car selon la couleur du nombre 14, on prendra : 14 = 1 + 13 ou 14 = 2 + 12 ou 14 = 9 + 5. En recensant toutes les partitions analogues de {1, … ,13} (car ce n'est pas la seule de ce type) on s'apercevrait qu'on ne peut jamais ajouter 14. Par suite, S(3) = 14.
Cas c = 4 et c = 5
La détermination des nombres de Schur suivants est difficile. On a S(4) = 45, mais ce n’est qu’en 2017 qu’on a pu démontrer que S(5) = 161, par une démonstration occupant 2 Po (deux millions de milliards de caractères)[7].
En combinatoire
Un autre théorème de Schur concerne le nombre de manières d'exprimer un entier naturel comme combinaison linéaire à coefficients entiers (positifs) d'un ensemble donné d'entiers premiers entre eux. Plus précisément, si est un ensemble de n entiers (strictement positifs et distincts) tels que PGCD, alors le nombre de n-uplets d'entiers naturels tels que admet comme comportement asymptotique, quand tend vers l'infini :
La série génératrice associée est la fraction rationnelle . Comme les sont premiers entre eux, ses pôles sont : 1, d'ordre n, et d'autres racines de l'unité, d'ordres < n.
Or la décomposition en éléments simples associée à chaque pôle ω d'ordre r est de la forme et pour tout entier k > 0, . Puisque , il reste donc : , où c est déterminé par : est l'élément simple d'indice maximum associé au pôle multiple 1, soit .
En particulier, pour tout ensemble d'entiers premiers entre eux, il existe une valeur de m telle que tout entier plus grand admet au moins une représentation comme combinaison linéaire de . Cette conséquence du théorème est en rapport avec le contexte plus familier du problème des pièces de monnaie de représenter un certain montant d'argent à l'aide de pièces de monnaie de valeur faciale donnée. Si ces valeurs faciales sont premières entre elles, comme 2 et 5, tout montant assez grand peut être représenté en utilisant uniquement ces pièces.
Schur a démontré en 1912 que :
- tout polynôme non constant a une infinité de diviseurs premiers, c.-à-d. qu'il existe une infinité de nombres premiers divisant au moins une valeur , avec ;
- pour tout entier et tout sous-groupe H de (ℤ/nℤ)×, il existe un polynôme non constant tel que pour presque tout diviseur premier p de P, la classe de p mod n appartient à H ;
- Si , il existe une démonstration élémentaire de l'existence d'une infinité de nombres premiers dans la classe de m mod n.
Notes et références
- ↑ Sans compter un théorème de géométrie différentielle d'Axel Schur (de).
- ↑ (en) Boaz Tsaban, Combinatorial Number Theory, (lire en ligne), chap. 1, Theorem 3.3.
- ↑ (en) Hans Jürgen Prömel (de), Ramsey Theory for Discrete Structures, Springer, (ISBN 978-3-31901315-2, lire en ligne), p. 13-15.
- ↑ (en) Alexander Soifer (ed.), Ramsey Theory: Yesterday, Today, and Tomorrow, Birkhäuser, coll. « Progress in Mathematics », (ISBN 978-0817680916, lire en ligne), p. 4.
- ↑ Démonstration en anglais sur Wikibooks.
- ↑ (en) Eric W. Weisstein, « Schur Number », sur MathWorld donne des références pour les deux acceptions.
- ↑ (en) Heule, Marijn JH., « Schur Number Five », arXiv:1711.08076, (lire en ligne).
Portail des mathématiques