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 ni sont distincts et supérieurs à N ?

Cette notion a été introduite par Paul Erdős en 1950.

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. 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 puis retrouvée indépendamment par Harold Davenport et Richard Rado. 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 : 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, 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). S. L. G. Choi a démontré qu'il existe un exemple pour N = 20, et Pace P. Nielsen 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.

Notes et références

• (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

• Système modulaire de représentation
• Théorème des restes chinois