The art of ornament contains in implicit form the oldest piece
of higher mathematics known to us. [1]
(Weyl-52, page 103.)

... Neither the passive contemplation of wallpaper patterns,
nor the passive contemplation of abstract definitions, is mathematics ;
since the latter is above all an activity in which definitions
are used to produce concrete results.  [2]
(Schw-74.)

 On suppose que le lecteur
d’une part jouit d’une certaine familiarité avec la géométrie plane
et d’autre part maîtrise le vocabulaire de base de la théorie des groupes.

1. Pavages polygonaux du plan et groupes de symétrie

On suppose connues les propriétés usuelles du plan euclidien,
ici noté $\mathbf E$.
Rappelons qu’un polygone est une partie compacte connexe du plan,
limitée par un nombre fini de segments, et qui est d’intérieur non vide.
Un tel polygone est simplement connexe si tout lacet qu’il contient
est continûment déformable en un point à l’intérieur du polygone.
Il est convexe si, avec deux points,
il contient toujours le segment de droite qui les joint ;
définition équivalente : un polygone est convexe
s’il est intersection de demi-espaces fermés.
Un polygone convexe est a fortiori simplement connexe ;
un polygone simplement connexe est homéomorphe à un disque.
La figure 1 montre quelques exemples ;
les trois premiers sont simplement connexes
(comme tous ceux qui apparaissent dans la suite)
et les deux premiers sont même convexes.

Figure. 1 : Quelques polygones plans

On considère dans ce texte que deux polygones sont égaux
s’ils sont isométriques
(les isométries ne conservent
pas nécessairement l’orientation du plan).

Soit $\mathbf F$ une partie du plan,
par exemple un polygone,
ou une réunion de plusieurs polygones,
ou le plan tout entier.
Un pavage de $\mathbf F$,
ou un pavage du plan si $\mathbf F = \mathbf E$,
est un recouvrement
$\mathcal P = \left( P_i \right)_{i \in I}$ de $\mathbf F$ par
des polygones à intérieurs disjoints :
\[ \mathbf F \, = \, \bigcup_{i \in I} P_i , \qquad \overset{\circ}{P_i} \cap \overset{\circ}{P_j} = \emptyset \quad \forall i,j \in I, i \ne j . \]
Les polygones d’un pavage sont aussi appelés pavés ou briques.
(On pourrait généraliser de manière évidente
à des pavés plus généraux que des polygones.)

Une famille de polygones
$\mathcal M = \left\{P^{(\kappa)}\right\}_{\kappa \in K}$
est une famille de
pavés modèles d’un pavage $\mathcal P = \left( P_i \right)_{i \in I}$
si chacun des $P_i$ est isométrique à l’un des $P^{(\kappa)}$ ;
un $\mathcal M$-pavage est un pavage
par copies des pavés du modèle $\mathcal M$.
Un pavage est dit monoédral s’il a un seul pavé modèle,
c’est-à-dire si tous ses polygones sont égaux,
diédral [respectivement triédral, ...]
s’il a deux [resp. trois, ...] pavés modèles.

Un pavage est côte-à-côte ou strict
si l’intersection de deux polygones distincts est

• ou bien vide,
• ou bien un sommet commun de plusieurs polygones,
• ou bien une arête commune des deux polygones.
  Dans ce cas, on définit de manière naturelle ce que sont
  un sommet, une arête (ou côté) et une face
  du pavage.

Une symétrie d’un pavage $\mathcal P = \left( P_i \right)_{i \in I}$
est une isométrie $\gamma$ du plan telle que $\gamma(P_i)$
est un pavé $P_j$ pour tout $i \in I$ ;
l’ensemble de ces symétries constitue le groupe de symétrie de $\mathcal P$.
Un pavage est périodique s’il possède une
 [3] symétrie de translation.
Rappelons qu’une isométrie du plan autre que l’identité
peut être de quatre types :

• une rotation (en particulier : un demi-tour, aussi dit symétrie centrale, un tiers de tour, un quart de tour, etc.),

• une translation,

• une symétrie (sous-entendu relativement à un axe),

• une symétrie glissante
  (composition d’une symétrie
  et d’une translation parallèle à l’axe de la symétrie).
  Dans le groupe de symétrie $\Gamma$ d’un pavage,
  une symétrie glissante est banale
  si son axe est aussi l’axe d’une symétrie de $\Gamma$,
  et non banale sinon.
  Une manière de décrire un tel groupe $\Gamma$ consiste à décrire
  ses éléments de chacun des types ci-dessus,
  et leurs classes de conjugaison.

La littérature traitant des pavages est considérable.
Le traité de Grünbaum et Shephard [GrSh-87]
est l’une des références obligées.
Après les exposés de Goutelas,
l’auteur a découvert un récent livre
de Conway, Burgiel et Goodman-Strauss [CoBG-08],
très abondamment illustré,
qui est un candidat sérieux à devenir un classique du sujet.

2. Equidécompositions

Il existe une tradition bien établie de
récréations mathématiques, de plusieurs espèces.
L’une d’elles consiste à trouver des équidécompositions :
étant donné deux parties du plan comme ci-dessus,
$\mathbf F_1$ et $\mathbf F_2$, le jeu consiste à imaginer un assortiment
$\{P_1,...,P_k\}$ de polygones permettant de paver
à la fois $\mathbf F_1$ et $\mathbf F_2$,
de préférence avec $k$ minimum.
En d’autres termes, trouver une équidécomposition
de $\mathbf F_1$ et $\mathbf F_2$,
c’est trouver un assortiment de pièces de puzzles
qui ait au moins ces deux solutions.
Il s’agit ici de puzzles au sens de ceux qu’on trouve dans le commerce :
une solution d’un puzzle utilise toutes les pièces disponibles,
chacune exactement une fois.

Les familles de pavés modèles du chapitre 1
et des chapitres suivants
définissent aussi des sortes de puzzles,
mais dans un sens différent,
puisqu’on y considère des pavages (par exemple du plan)
dans lesquels chaque pavé modèle apparaît
un nombre arbitraire de fois, et même souvent un nombre infini de fois.

Une condition évidemment nécessaire pour que deux parties du plan
$\mathbf F_1$ et $\mathbf F_2$ soient équidécomposables
est que leurs aires soient égales.
Cette condition est également suffisante :
c’est le théorème de Bolyai-Gerwein-Wallace,
qui date des années 1830, voir par exemple [Bolt-78] et [Fred-97].
(En dimension $3$, la condition analogue pour les volumes
n’est pas suffisante, ce qu’on connaît au moins depuis 1901,
qui est la date de publication par Max Dehn
de la solution du troisième problème
 [4] qu’il jugeait importants,
et qui ont effectivement joué un rôle moteur
dans la recherche mathématique du XXe siècle.
Nous revenons aux chapitres 5 et 11 ci-dessous
sur deux des trois parties du XVIIIe problème.]] de Hilbert.)

Il est important de ne pas supposer
a priori $\mathbf F_1$ et $\mathbf F_2$ connexes.
Par exemple, $\mathbf F_1$ peut être un polygone d’aire $a$
et $\mathbf F_2$ la réunion de deux polygones d’aires $b$ et $c$,
avec $a = b+c$.

Avant de proposer quelques exemples,
notons qu’il y a de nombreuses sources disponibles
pour les équidécompositions.
Citons d’abord l’un des ouvrages classiques [Dude-70],
en particulier son chapitre de « geometrical problems »
(incluant les tangrams).
Renvoyons aussi à un livre [Fred-97]
et aux nombreux sites ouèbes
(par exemple [Rous] et [WaBG])
où on peut en trouver bien davantage.

La figure 2 résume une démonstration du théorème de Pythagore
pour laquelle $k=3$ ;
elle est copiée de la page 89 de [BaCo-87],
et fait allusion à la démonstration dite de Perigal [Peri-73],
un mathématicien anglais amateur (1801-1898).

Figure 2. Le théorème de Pythagore.

$ \ $

Exercice. Exhiber des équidécompositions pour

(i) un triange de côtés $a$, $b$, $c$ et un parallélogramme de côtés $a,b/2$ ;

(ii) un parallélogramme de côtés $a,b$
et un rectangle dont l’un des côtés est $a$ ;

(iii) un rectangle de côtés $a,b$
et un rectangle de côtés $c,d$ avec $ab = cd$ ;

(iv) un octogone régulier
et un carré de même surface.

[Indication pour (iii). On ne restreint pas la généralité
en supposant $a > c$, et il convient de supposer dans un premier temps
que $c$ n’est pas beaucoup plus petit que $a$.

Une solution des parties (i), (ii) et (iii) de l’exercice fournit « presque »
une démonstration du théorème de Bolyai-Gerwein-Wallace ;
voir le chapitre III de [BaCo-87].
La partie (iv) est susceptible d’infinies variations.]

Exercice-projet.
Etudier les pavages archimédiens,
qui sont les pavages
dont tous les pavés sont des polygones réguliers
et dont tous les sommets ont des voisinages
congrus par isométries préservant l’orientation.
On sait qu’il y a $11$ tels pavages à similitude près
($12$ à similitude propre près).
Voir [GrSh-87], pages 58-64 et 102-107.

Exercice.
Soit $\mathcal P$ un pavage régulier du plan.
Vérifier que le groupe $\Gamma$ de symétrie de $\mathcal P$
agit simplement transitivement
sur l’ensemble des drapeaux de $\mathcal P$.

Un drapeau $(S,A,P)$ d’un pavage $\mathcal P$
est formé d’un sommet $S$,
d’une arête $A$ et d’un pavé $P$ de $\mathcal P$
tels que $S \in A \subset P$.
Pour un pavage du plan, on peut d’ailleurs
définir la régularité par la condition que
$\Gamma$ soit transitif sur l’ensemble des drapeaux.

Exercice.
Décrire deux pavages monoédraux du plan par des triangles rectangles isocèles,
l’un périodique et l’autre non périodique.

Noter que, au contraire, il existe à isométrie près un seul pavage du plan
par des hexagones réguliers, pavage qui est périodique.
Cette propriété, dite de monomorphie,
vaut aussi pour un hexagone ayant trois paires
de côtés opposés parallèles et de même longueur,
ainsi que pour plusieurs autres polygones
(voir la figure 1.5.1 de [GrSh-87]).

Remarque.
Une famille $\mathcal M = \{P^{(1)}, ..., P^{(n)}\}$ de modèles est
monomorphe, dimorphe, ..., $r$-morphe, ...
s’il existe à isométrie près
exactement $1$, $2$, ..., $r$, ..., $\mathcal M$-pavages du plan.
Au n° 1.5 de [GrSh-87], le problème de savoir
s’il existe des modèles $r$-morphes pour tout $r \ge 1$
est cité comme toujours ouvert (idem pour $r$ infini dénombrable) ;
on sait qu’il existe de tels modèles pour $r \le 10$.

Digression concernant un problème resté longtemps ouvert : la conjecture de Minkowski

A première vue, les pavages par des carrés
et leurs analogues en d’autres dimensions
peuvent sembler « faciles » ;
mais à première vue seulement.
Soit $\mathcal P$ un pavage de $\mathbf R^n$ par des
translatés du cube unité ;
est-ce qu’il existe nécessairement
une paire de pavés dont l’intersection
est une $(n-1)$-face de chacun d’eux ?

Si on suppose de plus que les pavés de $\mathcal P$
sont tous les translatés du cube unité
par un réseau (de translations),
la réponse affirmative a été conjecturée
en 1907 par Minkowski
(qui avait donné de nombreuses autres formulations,
la première en théorie des nombres).
Cette conjecture de Minkowski
a été démontrée pour $n \le 3$ par lui,
pour $n \le 6$ par Jansen (1909),
et enfin démontrée pour tout $n$ par Hajos (1942).

La conjecture fut généralisée par Keller (1930)
à tous les pavages par des translatés du cube unité
(la condition impliquant un réseau est donc supprimée).
Cette conjecture de Keller a été démontrée
pour $n \le 6$ par Perron (1940),
mais infirmée pour $n \ge 10$ par
Lagarias et Shor (1992).
(Sauf erreur : infirmée depuis pour $n \ge 8$.)

Pour tout ceci, voir [Stei-74],
l’excellente monographie [StSz-94],
et un panorama plus récent [Zong-05].

4. Polygones qui pavent le plan

Convenons qu’un polygone $P$ pave le plan
s’il existe un pavage du plan qui est monoédral, par des copies de $P$.
Ainsi, la proposition 3.1
montre qu’un $n$-gone régulier
pave le plan si et seulement si $n \in \{3,4,6\}$.
Plus généralement, une famille
$\mathcal M = \{P^{(1)}, ..., P^{(n)}\}$ de modèles
pave le plan s’il existe un pavage du plan par des copies des $P^{(j)}$.

Il est (presqu’ ...) évident que tout triangle pave le plan.
En effet, la réunion d’un triangle $P$ et de son symétrique
relativement à un côté de $P$ est un parallélogramme,
et il est (encore plus) évident
que tout parallélogramme pave le plan,
comme l’illustre la figure 4.

Figure 4. Pavage plan par des triangles tous égaux.

Exercice.
Soit $P$ un hexagone ayant une paire de côtés opposés
parallèles et de même longueur.
Vérifier que $P$ pave le plan.

Exercice.
Montrer que tout quadrilatère pave le plan.

Exercice.
Exhiber des pentagones qui pavent le plan
et des pentagones qui ne le pavent pas.

Remarques.

1. L’art des pavages est vieux comme le monde.
   En témoignent parmi beaucoup d’autres
   de superbes exemples de l’Egypte ancienne
   ou de l’art islamique.
   Parmi les nombreux sites ouèbes proposant
   des illustrations, voir [Tess] et [Tess.org] ;
   certains d’entre eux indiquent des pavages d’autres surfaces,
   dont la sphère et le plan hyperbolique.
2. Il existe un article de 1968 qui fournit une liste
   de pentagones convexes qui pavent le plan,
   s’appuyant sur une « démonstration » de la complétude de cette liste.
   Toutefois, sept ans plus tard,
   Martin Gardner présenta ces résultats
   dans le Scientific American,
   un journal de vulgarisation scientifique,
   et plusieurs lecteurs exhibèrent des pentagones convexes
   qui pavent le plan, mais sans figurer dans la liste !
   Parmi ces lecteurs remarquablement perspicaces figurait Majorie Rice,
   qui ne faisait pas officiellement partie de la confrérie
   des mathématiciens professionnels,
   mais à qui elle sut bel et bien damer le pion.
   Pour en savoir plus sur ce thème, voir notamment
   [Scha-78] et [Scha-81].
3. On sait caractériser exactement
   quels sont les hexagones convexes qui pavent le plan :
   il y en a trois familles, dont celle d’un exercice précédent.
   Voir [Rein-18],
   qui est une thèse dirigée par Hilbert,
   ainsi que [Kers-68] et [Boll-63].

En effet, vu les exercices et remarques qui précèdent
ainsi que la proposition qui suit,
le problème de caractériser
quels sont les polygones convexes à $n$ côtés qui pavent le plan
est donc résolu à la seule exception du cas $n=5$.

Il existe de jolies conditions suffisantes pour qu’un polygone
$P$ pave le plan, par exemple celle de [Scha-80].

Plus généralement, notons que les pavages offrent
de nombreux problèmes ouverts de formulation simple ;
on en trouve de petites collections
au chapitre C de [CrFG-91]
et au chapitre 4 de [BrMP-05].

Remarques.

1. La démonstration qui suit est une paraphrase de celle de [Nive-78].
2. Le nombre de côtés de $P^{(\omega)}$, au moins $7$,
   peut varier avec $\omega$.
3. Il résulte du théorème isopérimétrique
   que $B = \pi d^2 / 4$ convient.
4. La proposition exclut l’existence de certains pavages
   stricts et non stricts du plan.
   Remarquons qu’un pavage non strict avec certains modèles $P^{\omega}$
   peut toujours être vu comme pavage strict avec une famille
   de modèles obtenus à partir des $P^{\omega}$
   en introduisant des sommets d’angles internes $\pi$
   sur certains côtés des $P^{\omega}$.
   Par exemple, un heptagone régulier, avec $7$ angles $5\pi/7$,
   peut être vu comme un polygone à $14$ sommets,
   dont $7$ d’angle $5\pi/7$ et $7$ d’angle $\pi$.
   Noter qu’un pavage non strict ayant un nombre fini de modèles
   devient dans le second point de vue un pavage strict
   pouvant nécessiter un nombre infini de modèles.
5. A titre d’exercice :
   exhiber un heptagone non convexe qui pave le plan.

Digression concernant un autre problème ouvert, nombres de Heesch

Soit $P$ un polygone plan.
Etant donné une partie $Q$ du plan,
compacte et connexe,
on dit que $Q$ possède une $P$-couronne s’il existe un pavage
ayant les deux propriétés suivantes :
d’abord c’est un pavage d’une partie du plan $C(Q)$ contenant
$\{ x \in \mathbf E \ \vert \ d(x,Q) \le \epsilon \}$,
pour une constante $\epsilon > 0$ convenable,
ensuite tout pavé de ce pavage contenu dans $C(Q) - Q$
est isométrique à $P$.
Pour $k$ un entier $\ge 0$ ou l’infini,
on dit que $Q$ a un nombre de Heesch au moins $k$ si,
pour tout $j \in \{1,2,...,k\}$, il existe une $P$-couronne
$C^j(Q) = C(C^{j-1}(Q))$ de $C^{j-1}(Q)$.
Le nombre de Heesch d’un polygone $P$
est l’entier (ou le symbole $\infty$) $k$
tel que $P$ possède un nombre de Heesch au moins $k$,
mais ne possède pas un nombre de Heesch au moins $k+1$
(à prendre cum grano salis si $k = \infty$).

Par exemple : un pentagone régulier a nombre de Heesch zéro,
le polygone de la figure 5 a nombre de Heesch $1$,
et un triangle a nombre de Heesch $\infty$
(idem pour tout polygone qui pave le plan).
La liste des « records de Heesch » est pour l’instant courte :

• (1968)
  H. Heesch définit « son » nombre et décrit un exemple
  de nombre de Heesch $1$ (a posteriori, on peut trouver
  des exemples antérieurs à la définition de Heesch) ;
• (1991)
  A. Fontaine décrit des polyominos de nombre de Heesch $2$
  et R. Ammann présente un exemple de nombre de Heesch $3$
  (le record tiendra une douzaine d’années) ;
• (2004)
  C. Mann décrit des exemples de nombre de Heesch $4$ et $5$
  (démonstration partiellement « à l’ordinateur »).

Il semble que, dans le plan hyperbolique,
on ne connaisse aucun exemple de nombre de Heesch $\ge 2$.
Dans l’espace euclidien de dimension trois, il y a des candidats
de nombre de Heesch $8$, mais pas d’exemples avec démonstration
surpassant les nombres de Heesch connus pour le plan.
Dans la sphère $\mathbf S^2$, il existe un exemple de nombre de Heesch $3$.

Pour tout ceci, voir [Mann-04] et [Mann],
ainsi que l’original [Hees-68] (page 23).

Figure. 5 : Nombre de Heesch 1

Je remercie Réza Bourquin, qui m’a fourni
les figures de ce texte.

Références

[BaCo-87]
W.W. Rouse Ball et H.S.M. Coxeter,
Mathematical recreations and essays,
Thirteenth Edition, Dover, 1987.
[En fait, $27$e édition !
la première édition, de Ball seul, date de 1892,
les éditions de 1947, 1974 et 1987 sont à deux auteurs.]

[Boll-63]
B. Bollobás,
Filling the plane with congruent convex hexagons without overlapping,
Ann. Univ. Sci. Budapest, Eötvös Sect. Math.,
6 (1963), 117-123.

[Bolt-78]
V.G. Boltianskii,
Hilbert’s third problem,
J. Wiley, 1978.

[BrMP-05]
P. Brass, W.O.J. Moser et J. Pach,
Research problems in discrete geometry,
Springer, 2005.

[CoBG-08]
J.H. Conway, H. Burgiel et C. Goodman-Strauss,
The symmetries of things,
A.K. Peters, 2008.

[CrFG-91]
H.T. Croft, K.J. Falconer et R.K. Guy,
Unsolved problems in geometry,
Springer, 1991.

[Dude-70]
H.E. Dudeney,
Amusements in mathematics,
Dover, 1970.

[Fred-97]
G.N. Frederickson,
Dissections : plane & fancy,
Cambridge University Press, 1997.

[GrSh-87]
B. Grünbaum et G.C. Shephard,
Tilings and patterns,
Freeman and co, 1987.

[Hart-00]
R. Hartshorne,
Geometry : Euclid and beyond,
Springer, 2000.

[Hees-68]
H. Heesch,
Reguläres Parkettierungsproblem,
Westdeutscher Verlag, 1968.

[Hilb-71]
D. Hilbert,
Les fondements de la géométrie,
traduction, introduction et compléments de P. Rossier,
Dunod, 1971
(première édition,
Grundlagen der Geometrie, de 1899).

[Kepl-19]
J. Kepler,
Harmonice mundi,
C.H. Beck, Munich, Johannes Kepler gesammelte Werke,
Band VI, 1940 [première édition 1619].
Voir en particulier le
« Liber II, de congruentia figurarum harmonicarum »,
pages 65-89.

[Kers-68]
R.B. Kershner,
On paving the plane,
Amer. Math. Monthly 75:8 (1968), 839-844
[attention au théorème de cet article concernant les pentagones,
qui n’est pas correct].

[Mann-04]
C. Mann,
Heesch’s tiling problem,
Amer. Math. Monthly 111 (2004), 509-517.

[Mann]
C. Mann,
Heesch’s problem.

[Nive-78]
I. Niven,
Convex polygons that cannot tile the plane,
Amer. Math. Monthly 85:10 (1978), 785-792.

[Peri-73]
H. Perigal,
On geometric dissections and transformations,
The Messenger of Mathematics 1873, 103-106,
version en ligne.

[Rein-18]
K. Reinhardt,
Über die Zerlegung der Ebene in Polygone,
Dissertation der Naturwiss. Fakultät,
Universität Frankfurt/Main, Borna, 1918.

[Rous]
A. Rousseau,
Liste des animations du dossier « Dissection »,
en ligne.

[Scha-78]
D. Schattschneider,
Tiling the plane with congruent pentagons,
Mathematics magazine 51:1 (1978), 29-44.

[Scha-80]
D. Schattschneider,
Will it tile ? Try the Conway criterion !
Math. Mag. 53:4 (1980), 224-233.

[Scha-81]
D. Schattschneider,
In praise of amateurs,
in « The mathematical Gardner »,
A. Klarner éditeur, Wadsworth (1981), 140-166.

[Schw-93]
R.E. Schwartz,
Pappus’s theorem and the modular group,
Publ. Math. I.H.É.S. 78 (1993), 187-206.

[Schw-74] R.L.E. Schwarzenberger,
The $17$ plane symmetry groups,
Math. Gaz. 58 (1974), 123-131.

[Stei-74]
S.K. Stein,
Algebraic tiling,
Amer. Math. Monthly 81:5 (1974), 445-462.

[StSz-94]
S.K. Stein et S. Szabó,
Algebra and tiling,
Carus Mathematical Monograph 25,
Mathematical Association of America, 1994.

[Tess]
Tessellations.

[Tess.org]
Tessellations.org.

[Thur-89]
W.P. Thurston,
Groups, tilings, and finite state automata,
Lecture notes distributed in conjunction with
the Colloquium Lectures given at the ninety-second summer meeting
of the American Mathematical Society,
University of Colorado, Boulder,
August 7-10, 1989 (non publié).

[WaBG]
Wallace-Bolyai-Gerwien Theorem.

[Weyl-52]
H. Weyl,
Symmetry,
Princeton University Press, 1952.

[Zong-05]
C. Zong,
What is known about unit cubes,
Bull. Amer. Math. Soc. 42 (2005), 181-211.