Voici la suite de l’histoire du Oddtown. Les habitants se sont révoltés contre les règles restrictives de la mairie et ont réélu le maire qui a promis de supprimer la moitié des restrictions pour créer les clubs. Les clubs dorénavant peuvent avoir un nombre quelconque de membres, pair ou impair. Tous les habitants étaient alors certains que rien ne pourra arrêter la croissance exponentielle des clubs ! Mais le nouveau maire a trouvé une autre solution…

Clubs avec un nombre arbitraire de membres

Notre question est la suivante. Supposons que nous permettions toutes sortes de clubs, pairs ou impairs, qu’est-ce qui doit être changé dans la règle (2.) pour maintenir une estimation du nombre maximal de clubs qui soit linéaire en $n$ ?

Ici, « linéaire en $n$ » signifie que l’on cherche des contraintes pour que le nombre maximal possible de clubs soit majoré par un multiple de $n$ (par exemple, $\leq 3 n$
ou $\leq 10000 n$).

La question ci-dessus semble être très naïve si l’on prend en compte la vaste littérature sur le sujet appelé « combinatoire extrémale » ou « théorie extrémale des ensembles ». Toutefois, l’énoncé suivant semble avoir échappé à l’attention des experts.

Pour le formuler, nous avons besoin de la notion de distance de Hamming. Si $X$
est un club, on note $|X|$ le nombre de ses adhérents (son cardinal). Etant donnés deux clubs $X$ et $Y$, la distance $d(X,Y)$ est définie comme le nombre de membres qui n’appartiennent qu’à un seul club, soit à $X$, soit à $Y$. Autrement dit, la distance est égale à la cardinalité de la différence symétrique entre $X$ et $Y$ : \[ \begin{equation} d(X,Y) =|X|+|Y|- 2\,|X\cap{}Y|. \end{equation} \]
Rappelons (voir la Partie I) que l’on peut coder chaque club par une suite de $0$ et de $1$. Pour cela, on ordonne les habitants (par exemple par ordre alphabétique), ce qui permet de parler de l’habitant numéro $i$ pour $i$ entre $1$ et $n$, où $n$ est le nombre total d’habitants. Ceci étant fait, un club est déterminé par une liste de $n$ nombres successifs qui valent $0$ ou $1$ : le nombre placé en position $i$ vaut $1$ si le $i$-ème habitant est membre du club, et $0$ sinon. En termes de telles suites, la distance $d(X,Y)$ peut être obtenue comme suit :

• on crée la suite $X+Y$ : la valeur en $i$-ème position est un $1$ si l’habitant numéro $i$ est dans un seul des deux clubs et vaut $0$ sinon ; de manière équivalente, on lit les valeurs $0$ ou $1$ pour $X$ et $Y$ en position $i$ et l’on associe la somme des deux avec les règles $0+0=0$, $0+1=1=1+0$, $1+1=0$.
• on calcule le poids de $X+Y$ : par définition, c’est la somme des termes de la suite ; c’est donc le nombre de $1$ qui apparait (le poids d’un club est le nombre de ses habitants).

Alors la distance de Hamming $d(X,Y)$ est égale au poids de $X+Y$.

Exemple. La distance entre les clubs \[ \begin{array}{rcl} X&=&(1\,0\,0\,1\,1\,1\,0)\\ Y&=&(0\,1\,0\,1\,0\,1\,1) \end{array} \] est $d(X,Y)=4$.

Notre énoncé est le suivant.

Théorème. Soit $F$ une famille de clubs dans une ville à $n$ habitants. Si la distance entre deux clubs n’est jamais un multiple de $4$, alors le nombre $|F|$ de clubs dans la famille est majoré par :

• $|F|\leq 2n$ pour $n\equiv0,1,2\mod4$ (c’est-à-dire si $n$, $n-1$ ou $n-2$ est un multiple de $4$)
• $|F|\leq 2n+2$ pour $n\equiv3\mod4$ (c’est-à-dire si $n-3$ est un multiple de $4$).

Cette borne est exacte.

A noter que la valeur $4$ dans la condition « la distance entre les deux clubs n’est pas un multiple de $4$ » est une valeur exceptionnelle. En remplaçant le $4$ par un autre nombre, par exemple par $3$ ou $5$, on s’aperçoit que le nombre de clubs peut grandir comme $n^2$ (en effet, on pourrait choisir tous les clubs avec deux membres).

Le but de ce texte n’est pas de donner une preuve du théorème, mais plutôt de montrer des exemples de « clubbing » et de convaincre le lecteur que le sujet est lié à de nombreuses notions remarquables, comme les Matrices de Hadamard et les codes binaires doublement pairs [1].

Considérations élémentaires

Montrons que le théorème Oddtown/Eventown implique directement la borne supérieure $|F|\leq2n+2$ pour tout $n$.
Soit $F$ une famille des clubs, et soit $F_0\subset F$ la sous-famille des clubs avec nombre pair de membres. On commence par vérifier que la distance $d$ est invariante par translation : \[ d(X+Z,Y+Z)=d(X,Y). \]
Nous pouvons alors supposer sans perte de généralité que $F_0$ contient le club vide [3].
Chaque club non-vide $X\in F_0$ doit contenir $4k+2$ membres pour un certain $k$, car sa distance au club vide n’est pas un multiple de $4$. La formule (1) implique que deux clubs non vides différents pairs doivent avoir une intersection impaire. Nous concluons par le théorème-jumeau du Oddtown que $|F_0|\leq{}n+1$. Pour la sous-famille $F_1$ des clubs impairs la borne $|F_1|\leq{}n+1$ peut être obtenue par des arguments analogues. Ces deux estimations fournissent $|F|\leq{}2n+2$.

En outre, dans le cas où $n$ est divisible par $4$, la borne peut être facilement améliorée en $|F|\leq2n$. En effet, considérons l’élément de poids maximal de \[ \omega=(1,1,\ldots,1), \] à savoir, le club qui contient tous les habitants. Alors, pour chaque $X$ et $Y$ on a

• $4$ divise $d(X,Y)$ si et seulement si $4$ divise $d(X+\omega,Y)$,

car $n$ est un multiple de $4$. Tout club $X$ de la famille $F$ peut être remplacé par $X+\omega$. En faisant ce remplacement si nécessaire, on peut supposer que $x_n=0$ pour tout $X$, puis appliquer la borne $|F|\leq2n+2$ en remplaçant $n$ par $n-1$.

En conclusion, lorsque $n$ ou $n-3$ est divisible par $4$, la borne du théorème ci-dessus peut être obtenue par des méthodes élémentaires, mais les deux autres cas restants (lorsque $n-1$ ou $n-2$ est multiple de $4$) résistent à de telles considérations. Il semble que le théorème ne puisse pas être prouvé par des méthodes simples d’algèbre linéaire. Du moins, l’auteur n’a pas réussi à trouver une preuve élémentaire et se demande si le lecteur est plus inventif !

Extremal clubbing

Notre but principal, maintenant, est de proposer des constructions explicites de familles de clubs $F$ atteignant la borne supérieure du théorème.

Lorsque $4$ divise $n-3$.— Dans ce cas, le nombre maximal de clubs est $2n+2$. On choisit les clubs suivants :

• Le club vide ;
• Le club plein $\omega$ ;
• $n$ clubs avec $1$ membre ;
• $n$ clubs avec $n-1$ membres.

La distance entre deux clubs n’est jamais un multiple de $4$. [4]

Lorsque $4$ divise $n-1$.— La construction ci-dessus peut être appliquée, mais le club vide et le club plein ne sont plus autorisés. La famille des clubs à un membre et des clubs à $n-1$ membres atteint la borne supérieure $2n$.

Lorsque $4$ divise $n-2$.— La limite supérieure est à nouveau $ 2n $ [5]. Pour construire une famille qui satisfait aux contraintes du théorème, nous pouvons choisir le club vide, $ n $ clubs à un membre et $ n-1 $ clubs à deux membres partageant un membre commun.

Lorsque $n$ est multiple de $4$.— Ce cas a été discuté ci-dessus. La façon la plus simple d’atteindre la limite $2n$ est d’exclure un habitant de tous les clubs et ensuite d’utiliser notre première construction.

Matrices de Hadamard

Notre théorème comme il est formulé « ne sent pas » la véritable périodicité (de Bott) modulo $8$ que nous avons évoquée dans la remarque ci-dessus ... mais cette périodicité n’est pas loin. Il y a un cas remarquable,lorsque $n-3$ est multiple de $8$, pour lequel une autre construction de famille maximale $F$ existe. A partir de maintenant, nous utilisons les notions de base d’algèbre linéaire !

Une matrice de Hadamard est une matrice $H$ de taille $m\times{}m$ avec $\pm1$ comme éléments, telle que $H^tH=HH^t=m\mathrm{I}$, où $H^t$ est la matrice transposée et $\mathrm{I}$ est la matrice identité, voir [6]. Les matrices \[ \left(1 \right), \qquad \left( \begin{array}{rr} 1&1\\ 1&-1 \end{array} \right), \qquad \left( \begin{array}{rrrr} 1&1&1&1\\ 1&-1&1&-1\\ 1&1&-1&-1\\ 1&-1&-1&1 \end{array} \right) \] sont les premiers exemples. Modulo normalisation évidente, nous pouvons supposer que la première ligne et la première colonne de $H$ n’ont que des $1$, voir  [7] pour les détails. Les matrices de Hadamard ne peuvent exister que si $m=1,2$ ou $m=4k$.

Si $m=8k+4$, alors une matrice de Hadamard de taille $m\times{}m$ donne naissance à une famille de clubs pour $n=m-1$. La construction, bien connue dans la théorie des codes binaires, est la suivante.

• On retire la première colonne de $ H $ (qui ne contient pas d’information) ;
• On définit la matrice $H_1$ de taille $(m-1)\times{}m$ en remplaçant $1$ par $0$ et $-1$ par $1$ ;
• On définit la matrice $H_2$ en remplaçant $-1$ par $0$.

Nous affirmons que les lignes de matrices $H_1$ et $H_2$ forment une famille $F$ qui satisfait aux conditions du théorème.

En effet, soient $X,Y$ deux lignes différentes de $H_1$, nous voulons montrer que $d(X,Y)=4k+2$. Chaque ligne de la matrice de Hadamard $H$ est de la forme \[ \left(1,\,(-1)^{x_1},\,(-1)^{x_2},\ldots,(-1)^{x_n}\right), \] où $X=(x_1,x_2,\ldots,x_n)$ est la ligne correspondante de $ H_1 $. Par définition d’une matrice de Hadamard, ses lignes sont deux à deux orthogonales. Cela signifie que l’égalité $x_i+y_i=1$ se produit exactement $m/2=4k+2$ fois lorsque $i$ parcourt $1,\ldots,n$.

Par ailleurs, les lignes de $ H_1 $ et $H_2 $ sont en dualité : $X\leftrightarrow{}X+\omega$, où $\omega$ est l’élément le plus long. Cela implique que la distance entre deux lignes de $ H_2 $ est aussi égale à $4k+2$, et que les distances entre une ligne de $H_1$ et une ligne $H_2$ sont impaires.

Exemple. L’unique, à équivalence près, matrice de Hadamard $H$ de taille $12\times12$ correspond aux matrices de taille $12\times11$ binaires suivantes : \[ H_1= \left( \begin{array}{rrrrrrrrrrr} 1&1&1&1&1&1&1&1&1&1&1\\ 0&1&0&1&1&1&0&0&0&1&0\\ 0&0&1&0&1&1&1&0&0&0&1\\ 1&0&0&1&0&1&1&1&0&0&0\\ 0&1&0&0&1&0&1&1&1&0&0\\ 0&0&1&0&0&1&0&1&1&1&0\\ 0&0&0&1&0&0&1&0&1&1&1\\ 1&0&0&0&1&0&0&1&0&1&1\\ 1&1&0&0&0&1&0&0&1&0&1\\ 1&1&1&0&0&0&1&0&0&1&0\\ 0&1&1&1&0&0&0&1&0&0&1\\ 1&0&1&1&1&0&0&0&1&0&0 \end{array} \right) \] et \[ H_2= \left( \begin{array}{rrrrrrrrrrr} 0&0&0&0&0&0&0&0&0&0&0\\ 1&0&1&0&0&0&1&1&1&0&1\\ 1&1&0&1&0&0&0&1&1&1&0\\ 0&1&1&0&1&0&0&0&1&1&1\\ 1&0&1&1&0&1&0&0&0&1&1\\ 1&1&0&1&1&0&1&0&0&0&1\\ 1&1&1&0&1&1&0&1&0&0&0\\ 0&1&1&1&0&1&1&0&1&0&0\\ 0&0&1&1&1&0&1&1&0&1&0\\ 0&0&0&1&1&1&0&1&1&0&1\\ 1&0&0&0&1&1&1&0&1&1&0\\ 0&1&0&0&0&1&1&1&0&1&1 \end{array} \right) \] Les lignes des matrices $ H_1 $ et $H_2 $ constituent une famille $F$ de clubs dans une ville à $11$ habitants, de cardinal $24$. Notons que cet exemple est lié au code de Golay qui est un code correcteur d’erreurs très célèbre et utile.

L’existence de matrices $4k\times4k$ de Hadamard pour $k$ arbitraire est la conjecture de Hadamard classique qui a une histoire fascinante. Nous avons juste montré que pour un nombre impair $k$ cela est équivalent à l’existence d’une famille $F$ de vecteurs de $\mathbb F_2^{4k-1}$ (espace vectoriel de dimension $4k-1$ sur le corps à $2$ éléments) tels que la distance entre deux des vecteurs est toujours $2k$. Notons que l’existence d’une telle famille de vecteurs est confirmée pour les petites valeurs de $k$, voir la table [8]