Théorème de Schur

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur les redirections 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 \{a_1,\ldots,a_n\} est un ensemble de n entiers (strictement positifs et distincts) tels que PGCD(a_1,\ldots,a_n)=1, alors le nombre b_m de n-uplets (c_1,\ldots,c_n) d'entiers naturels tels que m=c_1a_1 + \cdots + c_na_n admet comme comportement asymptotique, quand m tend vers l'infini :

b_m=\frac{m^{n-1}}{(n-1)!~a_1\cdots a_n}+O(m^{n-2}).

En particulier, pour tout ensemble \{a_1,\ldots,a_n\} 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 a_1,\ldots,a_n. 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.