Système couvrant

En mathématiques, un système couvrant est un recouvrement fini de l'ensemble ℤ des entiers relatifs 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_{i}k~|~k\in \mathbb {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 n_i sont distincts et supérieurs à N ?

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

Exemples et définitions

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 n_i 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

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

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 a_{n + 2} = a_{n + 1} + a_n 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

a₀ = 20615674205555510 et a₁ = 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 a_n 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

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 10⁵⁰ classes de congruences.

Une autre conjecture célèbre, d'Erdős et Selfridge, 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

(en) P. Erdős, « On integers of the form 2^k + p and some related problems », Summa Brasil. Math., vol. 2, n^o 8,‎ 1950, p. 113-123 (lire en ligne)
(en) [PDF] Zhi Wei Sun, Problems and Results on Covering Systems
(en) [PDF] Zhi Wei Sun, Classified Publications on Covering Systems
(en) Richard K. Guy, Unsolved Problems in Number Theory, New York, Springer, 2004, 437 p. (ISBN 978-0-387-20860-2, lire en ligne)
(en) Alexander Soifer, 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
(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)
(en) James H. Jordan, « Covering classes of residues », Canad. J. Math., vol. 19,‎ 1967, p. 514-519 (lire en ligne)
(en) S. L. G. Choi, « Covering the set of integers by congruence classes of distinct moduli », Math. Comp., vol. 25, n^o 116,‎ 1971, p. 885-895 (lire en ligne)
(en) Pace P. Nielsen, « A covering system whose smallest modulus is 40 », J. Number Theory, vol. 129, n^o 3,‎ 2009, p. 640-666 (lire en ligne)
(en) Song Guo et Zhi-Wei Sun, « On odd covering systems with distinct moduli », Adv. Appl. Math., vol. 35, n^o 2,‎ 2005, p. 182-187, arXiv:math/0412217

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Covering system » (voir la liste des auteurs).

Articles connexes

Arithmétique et théorie des nombres

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] (en) P. Erdős, « On integers of the form 2^k + p and some related problems », Summa Brasil. Math., vol. 2, n^o 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, New York, Springer, 2004, 437 p. (ISBN 978-0-387-20860-2, lire en ligne)

[Soifer-5] (en) Alexander Soifer, 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)

[Jordan-7] (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, n^o 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, n^o 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, n^o 2,‎ 2005, p. 182-187, arXiv:math/0412217