Le coloriage de la parité : la fractale de Sierpiński

Le troisième tiroir promis par les Coulisses est un coloriage. La pièce « La fractale cachée » l’annonçait : noircissez chaque cellule impaire du triangle de Pascal, laissez chaque cellule paire en blanc, et une figure émerge, à toutes les échelles. Voici cette figure, calculée et non dessinée, puis le théorème qui la commande.

Le coloriage, sur trente-deux lignes

La figure ci-dessous est le triangle de Pascal réduit modulo $2$ : chaque cellule impaire est coloriée, chaque cellule paire laissée vide. Elle a été engendrée par un court programme Python qui calcule la parité de chaque coefficient, jamais à la main. Les trente-deux premières lignes suffisent à voir naître le motif.

Les grands triangles vides, emboîtés à toutes les échelles dans un triangle plein, sont la signature du triangle de Sierpiński, l’une des fractales les plus célèbres. Le prodige n’est pas qu’il apparaisse, c’est que sa présence était prévisible par pure arithmétique, plus d’un demi-siècle avant que Sierpiński ne le dessine en 1915.

Le théorème de Lucas (1878)

La clé est un critère de parité dû à Édouard Lucas en 1878. Énoncé précis, tel que les Coulisses le citent, sans démonstration complète :

Écrivons $n$ et $k$ en base $2$. Alors $\binom{n}{k}$ est impair si et seulement si chaque $1$ de l’écriture binaire de $k$ fait face à un $1$ de l’écriture binaire de $n$.

Autrement dit, l’écriture binaire de $k$ doit être « incluse » dans celle de $n$, chiffre par chiffre. Le théorème général de Lucas dit davantage, en réduisant $\binom{n}{k}$ modulo n’importe quel nombre premier $p$ à partir des chiffres de $n$ et $k$ en base $p$ ; le cas $p = 2$ est exactement ce critère de parité.

Vérifions-le sur une ligne, comme dans les Coulisses. La ligne $n = 4$ s’écrit $100$ en binaire. Les $k$ dont l’écriture binaire est incluse dans $100$ sont $k = 0$ (soit $000$) et $k = 4$ (soit $100$), et eux seuls. On doit donc trouver des nombres impairs exactement aux positions $0$ et $4$ :

$\binom{4}{k} : \quad 1,\ 4,\ 6,\ 4,\ 1 \quad\longrightarrow\quad \text{parités } 1,\ 0,\ 0,\ 0,\ 1.$

Impair aux deux bouts, pair au milieu : exactement la prédiction. C’est ce mécanisme, répété ligne après ligne, qui creuse les trous et fait émerger la fractale.

Pourquoi la fractale, et pas autre chose

Un détail rend la structure inévitable. Le nombre de cellules impaires sur la ligne $n$ vaut $2^{s(n)}$, où $s(n)$ compte les $1$ dans l’écriture binaire de $n$ (résultat de Glaisher, 1899). Les puissances de deux qui commandent les emboîtements de la figure sont donc écrites dans les nombres eux-mêmes. Et l’outil de fond est encore plus ancien : dès 1852, Kummer savait lire la divisibilité de $\binom{n}{k}$ par un nombre premier $p$ dans les retenues de l’addition de $k$ et $n-k$ en base $p$. Pour $p = 2$, aucune retenue signifie coefficient impair.

Il faut rester prudent sur la paternité de la synthèse « Pascal modulo $2$ égale Sierpiński » : c’est une convergence reconnue après coup, popularisée notamment par l’étude des automates cellulaires, et non une découverte datée d’un seul auteur. Ce qui est sûr, et déjà remarquable, c’est que le motif fractal était arithmétiquement connu, par Kummer, Lucas et Glaisher, avant que Sierpiński ne lui donne un nom géométrique en 1915. Les nombres savaient qu’ils formaient une fractale un demi-siècle avant qu’on ne la dessine.

La figure, calculée et vérifiée

La figure ci-dessus n’a pas été tracée à la main : un programme Python a calculé la parité de chacun des coefficients des trente-deux premières lignes, puis n’a colorié que les impairs. Les parités ont été vérifiées de deux façons indépendantes qui doivent coïncider, sous peine d’erreur signalée : d’un côté la relation de Pascal réduite modulo $2$, de l’autre le critère de Lucas $\binom{n}{k}$ impair si et seulement si $(k \text{ ET } n) = k$ en binaire. Les deux méthodes s’accordent sur les $528$ cellules, et le compte des impairs par ligne redonne bien $2^{s(n)}$, conformément à Glaisher.

Sources

• Coulisses A2, L’envers du triangle, pièce 24 (« La fractale cachée »), et le paragraphe 6 du cours pour le triangle et sa parité.
• Édouard Lucas, Sur les congruences des nombres eulériens et des coefficients différentiels des fonctions trigonométriques, 1878 (théorème de Lucas).
• Ernst Kummer, 1852 (valuation $p$-adique de $\binom{n}{k}$ par les retenues) ; James Glaisher, 1899 (nombre d’impairs par ligne, $2^{s(n)}$).
• Wacław Sierpiński, 1915 (la courbe fractale, indépendamment du triangle de Pascal). La synthèse « Pascal mod 2 = Sierpiński » est une convergence postérieure, sans découvreur unique daté.