Système couvrant

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, un système couvrant (ou « système complet de résidus ») est un recouvrement fini de l'ensemble ℤ des entiers par des classes résiduelles, c'est-à-dire un ensemble fini

\{a_1(\mathrm{mod}\ {n_1}),\ \ldots,\ a_m(\mathrm{mod}\ {n_m})\}

de classes

a_i(\mathrm{mod}\ {n_i})=\{ a_i + n_ik~|~k\in\Z\}

dont la réunion est égale à ℤ.

Problème non résolu
Existe-t-il, pour tout entier N, un système couvrant dont les modules ni sont distincts et supérieurs à N ?

Cette notion a été introduite par Paul Erdős en 1950[1],[2],[3].

Exemples et définitions[modifier | modifier le code]

Les deux premiers exemples suivants sont non seulement des recouvrements mais des partitions de ℤ, c'est-à-dire que les classes résiduelles sont disjointes deux à deux. On les appelle des systèmes couvrants « disjoints », ou « exacts » :

\{0(\mathrm{mod}\ {3}),\ 1(\mathrm{mod}\ {3}),\ 2(\mathrm{mod}\ {3})\}

et

\{1(\mathrm{mod}\ {2}),\ 2(\mathrm{mod}\ {4}),\ 4(\mathrm{mod}\ {8}),\ 0(\mathrm{mod}\ {8})\}.

Contrairement aux deux précédents, le système couvrant ci-dessous est « distinct », ou « incongruent », c'est-à-dire que tous ses modules ni sont distincts (et > 1).

\{0(\mathrm{mod}\ {2}),\ 0(\mathrm{mod}\ {3}),\ 1(\mathrm{mod}\ {4}),
\ 5(\mathrm{mod}\ {6}),\ 7(\mathrm{mod}\ {12})
\}.

Chacun de ces trois exemples est « non redondant », c'est-à-dire minimal (pour l'inclusion, parmi les systèmes couvrants) : si on oublie l'une des classes, le sous-système n'est plus couvrant.

Un système couvrant est dit « m-couvrant » (resp. « exactement m-couvrant ») si chaque entier appartient à au moins (resp. exactement) m classes du système (les systèmes exactement 1-couvrants sont donc les systèmes couvrants disjoints, définis plus haut).

Pour tout m ≥ 2, il existe des systèmes exactement m-couvrants qui ne peuvent pas s'écrire comme réunion de deux systèmes couvrants disjoints[4]. Par exemple le système

\{1(\mathrm{mod}\ {2});\ 0(\mathrm{mod}\ {3});\ 2(\mathrm{mod}\ {6});\ 0,4,6,8(\mathrm{mod}\ {10});1,2,4,7,10,13(\mathrm{mod}\ {15});\ 5,11,12,22,23,29(\mathrm{mod}\ {30})\}

est exactement 2-couvrant mais n'est pas réunion de deux systèmes couvrants disjoints.

Théorème de Mirsky-Newman[modifier | modifier le code]

Le théorème de Mirsky-Newman, cas particulier de la conjecture de Herzog-Schönheim, établit qu'un système couvrant ne peut être à la fois « disjoint » et « distinct ». Erdős rend compte, pour cet énoncé qu'il avait conjecturé en 1950, d'une preuve non publiée aussitôt donnée par Leon Mirsky (en) et Donald J. Newman (en) puis retrouvée indépendamment par Harold Davenport et Richard Rado[5],[6]. En 1970, un problème de coloration géométrique équivalent à ce théorème a été posé aux olympiades de mathématiques de l'URSS[5] : montrer que si les sommets d'un polygone régulier sont colorés de telle façon que chaque sous-polygone formé des sommets d'une même couleur soit régulier, alors deux de ces sous-polygones sont congruents. Plus précisément, il existe au moins deux de ces sous-polygones dont le nombre de sommets est minimum.

Suites sans nombres premiers[modifier | modifier le code]

Les systèmes couvrants peuvent être utilisés pour trouver des suites sans nombres premiers (en), c'est-à-dire des suites de nombres composés vérifiant la même relation de récurrence an + 2 = an + 1 + an que les nombres de Fibonacci et telles que deux termes consécutifs de la suite soient premiers entre eux. Un exemple de telle suite est celle trouvée par Herbert Wilf, déterminée par

a0 = 20615674205555510 et a1 = 3794765361567513 (suite A083216 de l'OEIS).

Dans cette suite, les indices des termes divisibles par un nombre premier donné forment une progression arithmétique (par exemple : les an pairs sont ceux pour lesquels n est congru à 0 modulo 3) et il existe dix-huit nombres premiers tels que les progressions correspondantes forment un système couvrant. Ces nombres premiers forment donc un ensemble couvrant (en) de la suite.

Quelques problèmes non résolus[modifier | modifier le code]

Le problème suivant, posé par Erdős en 1963[7], n'est actuellement pas résolu : existe-t-il, pour tout entier N, un système couvrant « distinct » dont tous les modules sont supérieurs à N ? Il est facile d'en construire pour lesquels le plus petit module est 2 ou 3 (Erdős avait donné un exemple où les modules étaient des diviseurs de 120 ; par exemple 0(3), 0(4), 0(5), 1(6), 1(8), 2(10), 11(12), 1(15), 14(20), 5(24), 8(30), 6(40), 58(60), 26(120) convient) ; D. Swift en a construit un pour lequel le plus petit module est 4 (et tous les modules divisent 2880)[7]. S. L. G. Choi a démontré[8] qu'il existe un exemple pour N = 20, et Pace P. Nielsen[9] pour N = 40, contenant plus de 1050 classes de congruences.

Une autre conjecture célèbre, d'Erdős et Selfridge (en), n'est toujours pas démontrée : qu'il n'existe pas de système couvrant « distinct » dont tous les modules sont impairs (et > 1). On sait que s'il en existait, le plus petit commun multiple des modules devrait avoir au moins 22 facteurs premiers[10].

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

  1. (en) P. Erdős, « On integers of the form 2k + p and some related problems », Summa Brasil. Math., vol. 2, no 8,‎ 1950, p. 113-123 (lire en ligne)
  2. (en) [PDF] Zhi Wei Sun, Problems and Results on Covering Systems
  3. (en) [PDF] Zhi Wei Sun, Classified Publications on Covering Systems
  4. (en) Richard K. Guy, Unsolved Problems in Number Theory, Springer,‎ 2004 (ISBN 978-0-387-20860-2, lire en ligne)
  5. a et b (en) Alexander Soifer (en), The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators, Springer,‎ 2008 (ISBN 978-0-387-74640-1, lire en ligne), chap. 1, (« A Story of Colored Polygons and Arithmetic Progressions »), p. 3-9
  6. (hu) Pál Erdős, « Egy kongruenciarendszerekrõl szóló problémáról (On a problem concerning congruence-systems) », Mat. Lapok, vol. 4,‎ 1952, p. 122-128 (lire en ligne)
  7. a et b (en) James H. Jordan, « Covering classes of residues », Canad. J. Math., vol. 19,‎ 1967, p. 514-519 (lire en ligne)
  8. (en) S. L. G. Choi, « Covering the set of integers by congruence classes of distinct moduli », Math. Comp., vol. 25, no 116,‎ 1971, p. 885-895 (lire en ligne)
  9. (en) Pace P. Nielsen, « A covering system whose smallest modulus is 40 », J. Number Theory, vol. 129, no 3,‎ 2009, p. 640-666 (lire en ligne)
  10. (en) Song Guo et Zhi-Wei Sun, « On odd covering systems with distinct moduli », Adv. Appl. Math., vol. 35, no 2,‎ 2005, p. 182-187, arXiv:math/0412217

Articles connexes[modifier | modifier le code]