Théorème de Schur

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour d'autres théorèmes de Schur[1], voir Issai Schur.

En mathématiques, il existe plusieurs théorèmes de Schur.

En théorie de Ramsey[modifier | modifier le code]

Un théorème de Schur garantit qu'il n'existe pas de partition finie de l'ensemble des entiers strictements positifs par des sous-ensembles sans somme.

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),

Ce résultat est généralisé par le théorème de Folkman.

Exemple 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.

Exemple 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.

En combinatoire[modifier | modifier le code]

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 :

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 monnaies 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.

Notes et références[modifier | modifier le code]

  1. Sans compter un théorème de géométrie différentielle d'Axel Schur (en).
  2. (en) Boaz Tsaban, Combinatorial Number Theory, (lire en ligne), chap. 1, Theorem 3.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.
  4. (en) Alexander Soifer (en) (ed.), Ramsey Theory: Yesterday, Today, and Tomorrow, Birkhäuser, coll. « Progress in Mathematics », (ISBN 978-0817680916, lire en ligne), p. 4.
  5. Démonstration en anglais sur Wikibooks.
  6. (en) Eric W. Weisstein, « Schur Number », MathWorld donne des références pour les deux acceptions.