{ "cells": [ { "cell_type": "markdown", "id": "2911b641", "metadata": {}, "source": [ "# Plans projectifs\n", "\n", "Marc Lorenzi\n", "\n", "5 juin 2023" ] }, { "cell_type": "code", "execution_count": null, "id": "8c0fad15", "metadata": {}, "outputs": [], "source": [ "import matplotlib.pyplot as plt\n", "import math" ] }, { "cell_type": "markdown", "id": "7049083f", "metadata": {}, "source": [ "## 1. Introduction" ] }, { "cell_type": "markdown", "id": "2429ad00", "metadata": {}, "source": [ "### 1.1 Qu'est-ce qu'un plan projectif ?" ] }, { "cell_type": "markdown", "id": "77188476", "metadata": {}, "source": [ "L'un des premiers objectifs de la géométrie est de parler de points et de droites. Tout le monde sait, ou croit savoir ce que sont un point ou une droite. En réalité, on n'a pas besoin de savoir ce que c'est : c'est la clé de *l'approche axiomatique*. Pour faire de la géométrie, il suffit de posséder un ensemble $P$ dont les éléments sont appelés *points*, un ensemble *D* dont les éléments sont appelés *droites*, et une relation entre les points et les droites, la relation *d'incidence* (intuitivement le point est sur la droite, ou la droite passe par le point). On se donne ensuite un certain nombre d'axiomes vérifiés par la relation d'incidence.\n", "\n", "Il existe plusieurs systèmes d'axiomes possibles, conduisant à des géométries différentes. La géométrie qui nous intéressera ici est la *géométrie projective plane*. Voici les axiomes." ] }, { "cell_type": "markdown", "id": "ea62243e", "metadata": {}, "source": [ "**Définition.** Un *plan projectif* est un triplet $\\mathbb P=(P,D,I)$ où $P$ et $D$ sont deux ensembles et $I\\subseteq P\\times D$ vérifiant les propriétés suivantes.\n", "\n", "$(P1)$ Pour tous $p,p'\\in P$ distincts, il existe un unique $d\\in D$ tel que $pId$ et $p'Id$.\n", "\n", "$(P2)$ Pour tous $d,d'\\in D$ distincts, il existe un unique $p\\in P$ tel que $pId$ et $pId'$.\n", "\n", "$(P3)$ Il existe un ensemble $Q\\subseteq P$ de cardinal 4 tel que pour tout $d\\in D$, il existe au plus deux éléments $p$ de $Q$ tels que $pId$.\n", "\n", "Les éléments de $P$ sont appelés les *points*, ceux de $D$ sont les *droites*. Lorsque $pId$, on dit que $p$ est *incident* à $d$ ou que $d$ est incidente à $p$." ] }, { "cell_type": "markdown", "id": "a107ceea", "metadata": {}, "source": [ "**Commentaires.** L'axiome $P1$ est un grand classique. En géométrie élémentaire il s'énonce : « par deux points il passe une unique droite ». L'axiome $P2$ est un peu plus surprenant : deux droites se coupent en un unique point. Ainsi, en géométrie projective, le parallélisme n'existe pas. L'axiome $P3$ est là pour éviter des cas dégénérés. L'ensemble $Q$ dont l'existence est assurée par cet axiome s'appelle un *quadrangle*." ] }, { "cell_type": "markdown", "id": "bf44e09c", "metadata": {}, "source": [ "Dans ce notebook, nous nous focaliserons sur les plans projectifs *finis*, c'est à dire ceux pour lesquels l'ensemble $P$ est fini. Plusieurs questions se posent. \n", "\n", "1. Quels sont les entiers $m$ pour lesquels il existe un plan projectif ayant $m$ points ?\n", "2. Comment construire un plan projectif fini ? \n", "3. Si un plan projectif possède $m$ points, combien possède-t-il de droites ?\n", "4. Combien de points sont incidents à une droite donnée ? Combien de droites sont incidentes à un point donné ? \n", "\n", "On ne connaît pas, à l'heure actuelle la réponse à la question 1.\n", "\n", "Nous allons nous intéresser dans ce notebook à une famille de plans projectifs fabriqués à partir du corps $\\mathbb Z/n\\mathbb Z$ des entiers modulo $n$, où $n$ est un nombre premier. Dans ce cas particulier, nous allons pouvoir répondre à toutes les questions." ] }, { "cell_type": "markdown", "id": "74182745", "metadata": {}, "source": [ "### 1.2 Le plan de Fano" ] }, { "cell_type": "markdown", "id": "c1787d6c", "metadata": {}, "source": [ "Commençons par examiner un exemple très simple (en fait le plus simple) de plan projectif fini, le *plan de Fano*. En voici une représentation graphique." ] }, { "cell_type": "code", "execution_count": null, "id": "5f1fc6ac", "metadata": {}, "outputs": [], "source": [ "def plot_fano():\n", " r3 = math.sqrt(3) / 2\n", " x1, x2, x3 = -r3, r3, 0\n", " y1, y2, y3 = -1/2, -1/2, 1\n", " x4, x5, x6 = (x1 + x2) / 2, (x1 + x3) / 2, (x2 + x3) / 2\n", " y4, y5, y6 = (y1 + y2) / 2, (y1 + y3) / 2, (y2 + y3) / 2\n", " xs = [x1, x2, x3, 0, x4, x5, x6]\n", " ys = [y1, y2, y3, 0, y4, y5, y6]\n", " plt.plot(xs, ys, 'ok', ms=10)\n", " plt.plot([x1, x2, x3, x1], [y1, y2, y3, y1], 'k')\n", " plt.plot([x1, x6], [y1, y6], 'k')\n", " plt.plot([x2, x5], [y2, y5], 'k')\n", " plt.plot([x3, x4], [y3, y4], 'k')\n", " d = math.sqrt(x4 ** 2 + y4 ** 2)\n", " circle = plt.Circle((0, 0), d, color='k', fill=False)\n", " plt.gca().add_patch(circle)\n", " plt.text(x3,y3+.1,'[011]')\n", " plt.text(x5-.2,y5,'[010]')\n", " plt.text(x1-.1,y1-.1,'[001]')\n", " plt.text(x4,y4-0.1,'[100]')\n", " plt.text(x2,y2-0.1,'[101]')\n", " plt.text(x6+.1,y6,'[110]')\n", " plt.text(.03,.1,'[111]')\n", " \n", " plt.text(0.2, 0.7, '(111)', fontsize=8)\n", " plt.text(-0.4, 0.7, '(100)', fontsize=8)\n", " plt.text(-0.4, -0.6, '(010)', fontsize=8)\n", " plt.text(0.03, 0.6, '(011)', fontsize=8)\n", " plt.text(0.52, -0.3, '(101)', fontsize=8)\n", " plt.text(-0.65, -0.3, '(110)', fontsize=8)\n", " plt.text(0.15, -0.4, '(001)', fontsize=8)\n", " plt.axis('off')\n", " plt.axis('equal')\n", " plt.savefig('fano2.png', bbox_inches='tight')" ] }, { "cell_type": "code", "execution_count": null, "id": "bcb8d9c8", "metadata": {}, "outputs": [], "source": [ "plot_fano()" ] }, { "cell_type": "markdown", "id": "35181d3f", "metadata": {}, "source": [ "Le plan de Fano est $\\mathbb P=(P,D,I)$ où $P=D=\\{001,010,011,100,101,110,111\\}$. Il possède donc 7 points et 7 droites. $I$ est la relation d'incidence. Sur le dessin, si $p\\in P$ et $d\\in D$ on a $pId$ lorsque le point $p$ est sur la ligne $d$. Par exemple, $[111]I(101)$.\n", "\n", "Sur le dessin, on a conventionnellement représenté les points par des ... points, et les droites par des lignes (6 segments et 1 cercle). Les droites sont étiquetées par leur valeur entre parenthèses, les points par leur valeur entre crochets.\n", "\n", "Ce n'est pas évident à voir, mais il y a une « formule » pour la relation d'incidence $I$. Si $p$ et $p'$ sont deux points distincts, l'unique droite incidente à $p$ et $p'$ est $p\\land p'$ où $\\land$ désigne le « produit vectoriel » modulo 2. Par exemple, l'unique droite incidente à $[001]$ et $[101]$ est $(010)$ car\n", "\n", "$$\\begin{pmatrix}0\\\\0\\\\1\\end{pmatrix}\\land \\begin{pmatrix}1\\\\0\\\\1\\end{pmatrix}=\\begin{pmatrix}0\\\\1\\\\0\\end{pmatrix}$$\n", "\n", "De même, Si $d$ et $d'$ sont deux droites distinctes, l'unique point incident à $d$ et $d'$ est $d\\land d'$. Par exemple, l'unique point incident à $(001)$ et $(101)$ est $[010]$.\n", "\n", "Chaque point du plan de Fano est incident à 3 droites, et chaque droite est incidente à 3 points. Si $p$ et $p'$ sont deux points distincts incidents à une droite $d$, le troisième point de $d$ est $p+p'$, où l'addition est faite bit par bit modulo 2. De même, si $d$ et $d'$ sont deux droites distinctes incidentes à un point $p$, la troisième droite incidente à $p$ est $d+d'$. Par exemple,\n", "\n", "$$001+101=100$$\n", "\n", "Ainsi,\n", "\n", "- Les points $[001]$, $[101]$ et $[100]$ sont les 3 points incidents à la droite $(010)$.\n", "- Les droites $(001)$, $(101)$ et $(100)$ sont les 3 droites incidentes au point $[010]$.\n", "\n", "Pour l'axiome $P3$, on peut par exemple considérer l'ensemble\n", "\n", "$$Q=\\{[001], [101], [011], [111]\\}$$\n", "\n", "Chaque droite autre que $(001)$ est incidente à exactement deux points de $Q$. La droite $(001)$ n'est incidente à aucun point de $Q$. L'ensemble $Q$ vérifie donc $P3$." ] }, { "cell_type": "markdown", "id": "3923e41f", "metadata": {}, "source": [ "### 1.3 Notations" ] }, { "cell_type": "markdown", "id": "f9808372", "metadata": {}, "source": [ "Dans ce notebook, $n$ désigne un nombre premier. \n", "\n", "On pose également $m=n^2+n+1$. L'entier $m$ apparaîtra régulièrement.\n", "\n", "Nous noterons $\\mathbb F=\\mathbb Z/n\\mathbb Z$ le corps des entiers modulo $n$. L'ensemble $\\mathbb F^3$ est un $\\mathbb F$-espace vectoriel de dimension 3. Comme $\\mathbb F$ est fini, de cardinal $n$, $\\mathbb F^3$ est de cardinal $n^3$. \n", "\n", "Enfin, nous poserons $E=\\mathbb F^3\\setminus\\{0\\}$." ] }, { "cell_type": "markdown", "id": "9211408c", "metadata": {}, "source": [ "### 1.4 Le corps $\\mathbb F$ en Python" ] }, { "cell_type": "markdown", "id": "55108921", "metadata": {}, "source": [ "Avant de parler de plans projectifs, mettons en place des outils pour manipuler facilement les éléments de $\\mathbb F$. Écrivons une classe `F`. Un objet de cette classe sera alors créé par une instruction du genre `x = F(4)`, pour créer la classe de 4 dans $\\mathbb Z/11\\mathbb Z$.\n", "\n", "Comme la classe `F` dépend du nombre premier $n$, nous allons en fait écrire une fonction `corps_fini` qui prend l'entier $n$ en paramètre et qui renvoie la classe `F`." ] }, { "cell_type": "markdown", "id": "5faeafa8", "metadata": {}, "source": [ "Le calcul de l'inverse d'un élément de $\\mathbb F$ peut être effectué au moyen de l'algorithme d'Euclide étendu, effectué dans la fonction `bezout`. Cette dernière prend en paramètres deux entiers relatifs. Elle renvoie un triplet $(u,v,d)$ tel que $ua+vb=d$ et $d=a\\land b$." ] }, { "cell_type": "code", "execution_count": null, "id": "656944b0", "metadata": {}, "outputs": [], "source": [ "def bezout(a, b):\n", " u1, v1, d1 = 1, 0, a\n", " u2, v2, d2 = 0, 1, b\n", " while d2 != 0:\n", " q = d1 // d2\n", " u, v, d = u1 - q * u2, v1 - q * v2, d1 - q * d2\n", " u1, v1, d1 = u2, v2, d2\n", " u2, v2, d2 = u, v, d\n", " return u1, v1, d1" ] }, { "cell_type": "code", "execution_count": null, "id": "ffc4dfa3", "metadata": {}, "outputs": [], "source": [ "bezout(123, 457)" ] }, { "cell_type": "code", "execution_count": null, "id": "58bcdf9a", "metadata": {}, "outputs": [], "source": [ "-26 * 123 + 7 * 457" ] }, { "cell_type": "markdown", "id": "280f459a", "metadata": {}, "source": [ "La fonction `inv_mod` prend en paramètres deux entiers $a$ et $m$ tels que $a\\land m=1$. Elle renvoie un entier $u$ tel que $ua\\equiv 1\\bmod m$." ] }, { "cell_type": "code", "execution_count": null, "id": "6d3b3dea", "metadata": {}, "outputs": [], "source": [ "def inv_mod(a, m):\n", " u, v, d = bezout(a, m)\n", " if d != 1: raise Exception('non inversible')\n", " else: return u % m" ] }, { "cell_type": "code", "execution_count": null, "id": "ecaefd0a", "metadata": {}, "outputs": [], "source": [ "inv_mod(123, 457)" ] }, { "cell_type": "code", "execution_count": null, "id": "97949f37", "metadata": {}, "outputs": [], "source": [ "(123 * 431) % 457" ] }, { "cell_type": "markdown", "id": "b845b1b8", "metadata": {}, "source": [ "La fonction `corps_fini` prend en paramètre un nombre premier $n$. Elle renvoie la classe `F` qui permet la manipulation des entiers modulo $n$. On y a prévu toutes les opérations élémentaires dans $\\mathbb F$ (addition, soustraction, multiplication, division). On a également prévu de pouvoir opérer entre un objet de la classe `F` et un entier (un objet de type `int`)." ] }, { "cell_type": "code", "execution_count": null, "id": "868943f7", "metadata": {}, "outputs": [], "source": [ "def corps_fini(n):\n", "\n", " class F:\n", "\n", " modulo = n\n", "\n", " def __init__(self, a): self.val = a % F.modulo\n", "\n", " def __repr__(self):\n", " return str(self.val)\n", "\n", " def __eq__(self, y):\n", " if isinstance(y, int): y = F(y)\n", " return self.val == y.val\n", "\n", " def __req__(self, y): return self == y\n", "\n", " def __add__(self, y):\n", " if isinstance(y, int): y = F(y)\n", " x = (self.val + y.val) % F.modulo\n", " return F(x)\n", "\n", " def __radd__(self, y): return self + y\n", "\n", " def __neg__(self):\n", " x = (-self.val) % F.modulo\n", " return F(x)\n", "\n", " def __sub__(self, y):\n", " return self + (-y)\n", "\n", " def __rsub__(self, y): return -(self - y)\n", "\n", " def __mul__(self, y):\n", " if isinstance(y, int): y = F(y)\n", " x = (self.val * y.val) % F.modulo\n", " return F(x)\n", "\n", " def __rmul__(self, y): return self * y\n", "\n", " def inverse(self):\n", " z = inv_mod(self.val, F.modulo)\n", " return F(z)\n", "\n", " def __truediv__(self, y):\n", " if isinstance(y, int): y = F(y)\n", " return self * y.inverse()\n", "\n", " def __rtruediv__(self, y): return F(y) / self\n", " \n", " return F" ] }, { "cell_type": "markdown", "id": "6d50faa2", "metadata": {}, "source": [ "Voici par exemple les tables de multiplication et de division dans $\\mathbb Z/13\\mathbb Z$." ] }, { "cell_type": "code", "execution_count": null, "id": "0dafdd62", "metadata": {}, "outputs": [], "source": [ "F = corps_fini(13)" ] }, { "cell_type": "code", "execution_count": null, "id": "59509f4b", "metadata": {}, "outputs": [], "source": [ "n = 13\n", "for x in range(n):\n", " for y in range(n):\n", " print('%3s' % (F(x) * F(y)), end='')\n", " print()" ] }, { "cell_type": "code", "execution_count": null, "id": "8d1f83d8", "metadata": {}, "outputs": [], "source": [ "n = 13\n", "for x in range(1, n):\n", " for y in range(1, n):\n", " print('%3s' % (F(x) / F(y)), end='')\n", " print()" ] }, { "cell_type": "markdown", "id": "c180e0b3", "metadata": {}, "source": [ "Remarquer les 1 et les 12 sur les deux diagonales de la table de division. On a en effet pour tout $x\\in\\mathbb Z/n\\mathbb Z$ non nul, $\\frac x x=1$ et $\\frac {-x}x=-1$." ] }, { "cell_type": "markdown", "id": "0d6ad465", "metadata": {}, "source": [ "## 2. Points" ] }, { "cell_type": "markdown", "id": "a6cff3fb", "metadata": {}, "source": [ "### 2.1 Une relation d'équivalence" ] }, { "cell_type": "markdown", "id": "194fb57a", "metadata": {}, "source": [ "Définissons sur $E=\\mathbb F^3\\setminus\\{0\\}$ une relation $\\simeq$ en posant\n", "\n", "$$u\\simeq v\\iff \\exists \\lambda\\in\\mathbb F^*, v=\\lambda u$$\n", "\n", "**Proposition.** $\\simeq$ est une relation d'équivalence sur $E$.\n", "\n", "**Démonstration.**\n", "\n", "- Réflexivité. Soit $u\\in E$. On a $u=1u$, donc $u\\simeq u$.\n", "- Symétrie. Soient $u,v\\in E$. Supposons $u\\simeq v$. Il existe $\\lambda\\in\\mathbb F^*$ tels que $v=\\lambda u$. On a donc $u=\\frac 1 \\lambda v$, donc $v\\simeq u$.\n", "- Transitivité. Soient $u,v,w\\in E$. Supposons $u\\simeq v$ et $v\\simeq w$. Il existe $\\lambda,\\mu\\in\\mathbb F$ tels que $v=\\lambda u$ et $w=\\mu v$. On a donc $w=(\\mu\\lambda)u$, donc $u\\simeq w$.\n", "\n", "**Définition.** Un *point* est un élément de l'ensemble quotient $P=E\\ /\\simeq$.\n", "\n", "Un point $p$ est un ensemble de triplets d'éléments de $\\mathbb F$ pas tous nuls. Précisément, il existe $u\\in E$ tel que\n", "\n", "$$p=\\{\\lambda u:\\lambda\\in[|1,n-1|]\\}$$\n", "\n", "Un point est ainsi un ensemble fini de cardinal $n-1$.\n", "\n", "**Proposition.** $|P|=n^2+n+1$.\n", "\n", "**Démonstration.** Comme $\\simeq$ est une relation d'équivalence, l'ensemble $P$ des points est une partition de $E$. On a donc\n", "\n", "$$E=\\bigcup_{p\\in P}p$$\n", "\n", "Cette union est disjointe (partition) donc\n", "\n", "$$|E|=\\sum_{p\\in P}|p|$$\n", "\n", "L'ensemble $E$ est de cardinal $n^3-1=(n-1)(n^2+n+1)$ et chaque point est un ensemble de cardinal $n-1$. On a donc\n", "\n", "$$(n-1)(n^2+n+1)=\\sum_{p\\in P}(n-1)=(n-1)|P|$$\n", "\n", "d'où le résultat en divisant par $n-1$." ] }, { "cell_type": "code", "execution_count": null, "id": "81375a31", "metadata": {}, "outputs": [], "source": [ "def card_P(n):\n", " return n ** 2 + n + 1" ] }, { "cell_type": "code", "execution_count": null, "id": "7504554d", "metadata": {}, "outputs": [], "source": [ "for n in [2, 3, 5, 7, 11, 13]:\n", " print('%3d%5d' % (n, card_P(n)))" ] }, { "cell_type": "markdown", "id": "37d21fbf", "metadata": {}, "source": [ "### 2.2 Représentant normalisé" ] }, { "cell_type": "markdown", "id": "c33a0114", "metadata": {}, "source": [ "Soit $p\\in P$. Il existe $u\\in E$ tel que\n", "\n", "$$p=\\{\\lambda u:\\lambda\\in[|1,n-1|]\\}$$\n", "\n", "Nous noterons $p=[u]$. Si $u=(x,y,z)$, nous écrirons $[x,y,z]$ au lieu de $[(x,y,z)]$.\n", "\n", "Il n'y a pas unicité du triplet $(x,y,z)$. Le point $p$ possède donc, d'une certaine manière, $p-1$ triplets de coordonnées. Aucun de ces triplets n'est préférable à un autre, mais nous pouvons décider d'un représentant particulier. Choisissons la méthode suivante :\n", "\n", "- Si $z\\ne 0$, choisissons $(x/z,y/z,1)$.\n", "- Si $z=0$ et $y\\ne 0$, choisissons $(x/y,1,0)$.\n", "- Si $z=0$ et $y=0$, alors $x\\ne 0$. Choisissons $(1,0,0)$.\n", "\n", "Il est maintenant facile de décider si deux points sont égaux. C'est le cas si et seulement si ils ont le même représentant normalisé." ] }, { "cell_type": "markdown", "id": "a583bf89", "metadata": {}, "source": [ "### 2.3 Les points en Python" ] }, { "cell_type": "markdown", "id": "f94c7738", "metadata": {}, "source": [ "Voici la classe `DP`. Pourquoi ce nom ? Lorsque nous aurons défini les droites la raison sera évidente. Lors de l'appel du constructeur, le point est normalisé, ce qui permet de tester facilement si deux points sont égaux." ] }, { "cell_type": "code", "execution_count": null, "id": "5b93f1a5", "metadata": {}, "outputs": [], "source": [ "class DP:\n", " \n", " def __init__(self, F, x, y, z):\n", " self.corps = F\n", " if isinstance(x, int): self.x = self.corps(x)\n", " else: self.x = x\n", " if isinstance(y, int): self.y = self.corps(y)\n", " else: self.y = y\n", " if isinstance(z, int): self.z = self.corps(z)\n", " else: self.z = z\n", " self.normaliser()\n", " \n", " def __repr__(self):\n", " return '[%s,%s,%s]' % (self.x, self.y, self.z)\n", " \n", " def __eq__(self, q):\n", " return self.x == q.x and self.y == q.y and self.z == q.z\n", " \n", " def normaliser(self):\n", " if self.z != 0:\n", " self.x = self.x / self.z\n", " self.y = self.y / self.z\n", " self.z = self.corps(1)\n", " elif self.y != 0:\n", " self.x = self.x / self.y\n", " self.y = self.corps(1)\n", " else:\n", " self.x = self.corps(1)\n", " \n", " def vecteur(self):\n", "\n", " return (self.x, self.y, self.z)" ] }, { "cell_type": "code", "execution_count": null, "id": "de2fe939", "metadata": {}, "outputs": [], "source": [ "F = corps_fini(7)\n", "p = DP(F, 1, 2, 0)\n", "q = DP(F, 4, 1, 4)\n", "p == q" ] }, { "cell_type": "code", "execution_count": null, "id": "b1033a23", "metadata": {}, "outputs": [], "source": [ "p = DP(F, 5, 3, 5)\n", "q = DP(F, 4, 1, 4)\n", "p == q" ] }, { "cell_type": "markdown", "id": "f04ac42f", "metadata": {}, "source": [ "### 2.4 Énumérer les points" ] }, { "cell_type": "markdown", "id": "1778f3f0", "metadata": {}, "source": [ "La fonction `enum_points` énumère les éléments de $P$. Cette énumération établit un ordre conventionnel entre les points.\n", "\n", "- On énumère d'abord les $n^2$ points de la forme $[x,y,1]$, dans l'ordre lexicographique du couple $(x,y)$ :\n", "\n", "$$(0,0), (0,1), \\ldots, (0,n-1), (1, 0),\\ldots,(n-1,n-1)$$\n", "\n", "- On énumère ensuite les points de la forme $[x,1,0]$.\n", "\n", "- On termine par le point $[1,0,0]$." ] }, { "cell_type": "code", "execution_count": null, "id": "e82ff780", "metadata": {}, "outputs": [], "source": [ "def enum_points(F):\n", " n = F.modulo\n", " for x in range(n):\n", " for y in range(n):\n", " yield DP(F, x, y, 1)\n", " for x in range(n):\n", " yield DP(F, x, 1, 0)\n", " yield DP(F, 1, 0, 0)" ] }, { "cell_type": "code", "execution_count": null, "id": "ed314aed", "metadata": {}, "outputs": [], "source": [ "F = corps_fini(5)\n", "for p in enum_points(F): print(p, end=' ')" ] }, { "cell_type": "markdown", "id": "8f9aa9e7", "metadata": {}, "source": [ "Il est également facile, étant donné un entier $k\\in[|0,n^2+n|]$ de trouver quel est le $k$ième point de l'énumération ci-dessus.\n", "\n", "- Si $k=xx'+yy'+zz'$$\n", "\n", "On note $u\\perp v$ lorsque $=0$.\n", "\n", "**Proposition.** Pour tous $u,v\\in\\mathbb F^3$ et $\\lambda,\\mu\\in\\mathbb F^*$, $u\\perp v$ si et seulement si $(\\lambda u)\\perp(\\mu v)$.\n", "\n", "**Démonstration.** C'est évident, car $<\\lambda u,\\mu v>=\\lambda\\mu$.\n", "\n", "Cette propriété montre que la relation $\\perp$ « passe au quotient ». Elle justifie la définition suivante.\n", "\n", "**Définition.** Soient $p=[u]\\in P$ et $d=[v]\\in D$. Le point $p$ est incident à la droite $d$ si $u\\perp v$.\n", "\n", "Si $p=[x,y,z]$ et $d=[a,b,c]$, on a donc $pId$ si et seulement si\n", "\n", "$$ax+by+cz=0$$\n", "\n", "**Remarque.** L'égalité ci-dessus est symétrique en $p$ et $d$. Nous dirons donc aussi que la droite $d$ est incidente au point $p$." ] }, { "cell_type": "code", "execution_count": null, "id": "1bca8e60", "metadata": {}, "outputs": [], "source": [ "def prod_scal(u, v):\n", " x1, y1, z1 = u\n", " x2, y2, z2 = v\n", " return x1 * x2 + y1 * y2 + z1 * z2" ] }, { "cell_type": "code", "execution_count": null, "id": "27482d64", "metadata": {}, "outputs": [], "source": [ "def incidents(p, d):\n", " return prod_scal(p.vecteur(), d.vecteur()) == 0" ] }, { "cell_type": "code", "execution_count": null, "id": "30c85492", "metadata": {}, "outputs": [], "source": [ "F = corps_fini(7)\n", "p = DP(F, 2, 3, 3)\n", "d = DP(F, 3, 1, 4)\n", "incidents(p, d)" ] }, { "cell_type": "markdown", "id": "22c45537", "metadata": {}, "source": [ "## 4. Le plan projectif" ] }, { "cell_type": "markdown", "id": "24a1e240", "metadata": {}, "source": [ "**Définition.** Le *plan projectif* est $\\mathbb P=(P,D,I)$.\n", "\n", "Nous allons évidemment prouver que tous les axiomes de plan projectif sont vérifiés par $\\mathbb P$." ] }, { "cell_type": "markdown", "id": "34576858", "metadata": {}, "source": [ "### 4.1 La matrice d'incidence" ] }, { "cell_type": "markdown", "id": "7cd40178", "metadata": {}, "source": [ "Rappelons que $m=n^2+n+1$. Soientt $p_0,\\ldots,p_{m-1}$ une énumération de $P$ et $d_0,\\ldots,d_{m-1}$ une énumération de $D$. La matrice d'incidence de $\\mathbb P$ (relative à ces deux énumérations) est la matrice $A\\in\\mathcal M_n(\\mathbb Z)$ définie pour $i,j\\in[|0,m-1|]$ par $A_{ij}=1$ si $p_i$ est incident à $d_j$ et $A_{ij}=0$ sinon." ] }, { "cell_type": "code", "execution_count": null, "id": "52863fb2", "metadata": {}, "outputs": [], "source": [ "def matrice_incidence(F):\n", " n = F.modulo\n", " m = card_P(n)\n", " A = m * [None]\n", " for i in range(m): A[i] = m * [0]\n", " for i in range(m):\n", " for j in range(m):\n", " if incidents(point_numero(F, i), point_numero(F, j)):\n", " A[i][j] = 1\n", " return A" ] }, { "cell_type": "code", "execution_count": null, "id": "92b7cc5c", "metadata": {}, "outputs": [], "source": [ "A = matrice_incidence(corps_fini(3))\n", "A" ] }, { "cell_type": "markdown", "id": "dcfea75b", "metadata": {}, "source": [ "### 4.2 Dénombrements" ] }, { "cell_type": "markdown", "id": "426e0e81", "metadata": {}, "source": [ "Regardons la matrice d'incidence de $\\mathbb P$ que nous avons obtenue pour $n=3$. Elle possède quatre 1 sur chaque ligne et chaque colonne : chaque point est incident à 4 droites et chaque droite est incidente à 4 points. Ceci se généralise facilement. \n", "\n", "Combien y a-t-il de points incidents à une droite donnée (ou, ce qui revient au même, de droites incidentes à un point donné) ?\n", "\n", "Donnons-nous une droite $d=[a,b,c]$ où $(a,b,c)\\in E$. Les points incidents à $d$ sont les points $[x,y,z]$ vérifiant $ax+by+cz=0$. Considérons le plan $F$ de l'espace vectoriel $\\mathbb F^3$ d'équation\n", "\n", "$$(F)\\ aX+bY+cZ=0$$\n", "\n", "$F$ est un $\\mathbb F$-espace vectoriel de dimension 2, il est donc isomorphe à $\\mathbb F^2$, qui est de cardinal $n^2$. Ainsi, $|F|=n^2$. En enlevant le triplet $(0,0,0)$, on a donc\n", "\n", "$$|F\\setminus\\{0\\}|=n^2-1=(n-1)(n+1)$$\n", "\n", "Cet ensemble est la réunion disjointe de classes modulo $\\simeq$, chacune de cardinal $n-1$. Il est donc l'union de $n+1$ classes, c'est à dire de $n+1$ points de $\\mathbb P$. Nous venons de montrer le résultat suivant.\n", "\n", "**Proposition.** Pour toute droite $d$ de $\\mathbb P$, $d$ est incidente à $n+1$ points.\n", "\n", "On a bien sûr gratuitement la proposition sur les points.\n", "\n", "**Proposition.** Pour tout point $p$ de $\\mathbb P$, $p$ est incident à $n+1$ droites.\n" ] }, { "cell_type": "markdown", "id": "bc2d2f46", "metadata": {}, "source": [ "### 4.3 Points incidents à deux droites distinctes" ] }, { "cell_type": "markdown", "id": "23c2f527", "metadata": {}, "source": [ "En géométrie affine, deux droites distinctes peuvent s'intersecter en un unique point, ou alors avoir une intersection vide si elles sont parallèles. En géométrie projective, le parallélisme n'existe pas.\n", "\n", "**Proposition.** Soient $d$ et $d'$ deux droites distinctes. Il existe un unique point incident à $d$ et $d'$.\n", "\n", "**Démonstration.** Posons $d=[a,b,c]$ et $d'=[a',b',c']$. Considérons les plans de $\\mathbb F^3$ d'équations\n", "\n", "$$(F)\\ ax+by+cz=0$$\n", "\n", "$$(F')\\ a'x+b'y+c'z=0$$\n", "\n", "Les droites $d$ et $d'$ étant distinctes, les plans $F$ et $F'$ sont distincts. Leur intersection $F\\cap F'$ est donc une droite (au sens usuel dans l'espace vectoriel $\\mathbb F^3$) $\\delta$. Il existe $(x_0,y_0,z_0)\\in \\mathbb F^3\\setminus\\{0\\}$ tel que\n", "\n", "$$\\delta=\\{\\lambda(x_0,y_0,z_0):\\lambda\\in\\mathbb F\\}$$\n", "\n", "En enlevant le triplet $(0,0,0)$, on constate que $\\delta\\setminus\\{0\\}$ est un point $p$ de $\\mathbb P$. Ainsi, $d$ et $d'$ sont incidentes à un et un seul point, le point $p$.\n", "\n", "**Notation.** Nous noterons $p=d\\cap d'$. Nous appellerons $p$ *l'intersection* de $d$ et $d'$." ] }, { "cell_type": "markdown", "id": "d56d2fb5", "metadata": {}, "source": [ "Le calcul de $d\\cap d'$ se fait facilement par un « produit vectoriel » : $d\\cap d'=p$ où\n", "\n", "$$p=[yz'-y'z,zx'-z'x,xy'-x'y]$$" ] }, { "cell_type": "code", "execution_count": null, "id": "d751c982", "metadata": {}, "outputs": [], "source": [ "def prod_vect(u, v):\n", " x1, y1, z1 = u\n", " x2, y2, z2 = v\n", " return (y1 * z2 - y2 * z1, z1 * x2 - z2 * x1, x1 * y2 - x2 * y1)" ] }, { "cell_type": "code", "execution_count": null, "id": "4b0223c6", "metadata": {}, "outputs": [], "source": [ "def intersection(F, d1, d2):\n", " x, y, z = prod_vect(d1.vecteur(), d2.vecteur())\n", " return DP(F, x, y, z)" ] }, { "cell_type": "code", "execution_count": null, "id": "fc45933d", "metadata": {}, "outputs": [], "source": [ "F = corps_fini(7)\n", "d1 = DP(F, 2, 1, 2)\n", "d2 = DP(F, 3, 1, 1)\n", "print(intersection(F, d1, d2))" ] }, { "cell_type": "markdown", "id": "312c5c8c", "metadata": {}, "source": [ "### 4.4 Droites incidentes à deux points distincts" ] }, { "cell_type": "markdown", "id": "28577321", "metadata": {}, "source": [ "Dans notre plan projectif, il y a symétrie complète entre les points et les droites. Nous avons donc gratuitement le théorème suivant.\n", "\n", "**Proposition.** Soient $p$ et $p'$ deux points distincts de $\\mathbb P$. Il existe une unique droite incidente à $p$ et $p'$.\n", "\n", "**Notation.** Nous noterons $(pp')$ l'unique droite incidente à $p$ et $p'$." ] }, { "cell_type": "code", "execution_count": null, "id": "9caed8c3", "metadata": {}, "outputs": [], "source": [ "def droite_incidente(F, p1, p2):\n", " return intersection(F, p1, p2)" ] }, { "cell_type": "markdown", "id": "06ef4a97", "metadata": {}, "source": [ "Voici la liste des 21 paires de points distincts du plan de Fano, avec l'unique droite qui leur est incidente." ] }, { "cell_type": "code", "execution_count": null, "id": "fe922189", "metadata": {}, "outputs": [], "source": [ "def str_fano(p):\n", " return str(p.x) + str(p.y) + str(p.z)" ] }, { "cell_type": "code", "execution_count": null, "id": "b533922a", "metadata": {}, "outputs": [], "source": [ "def str_point(p):\n", " return '[' + str_fano(p) + ']'" ] }, { "cell_type": "code", "execution_count": null, "id": "37c2ba88", "metadata": {}, "outputs": [], "source": [ "def str_droite(d):\n", " return '(' + str_fano(d) + ')'" ] }, { "cell_type": "code", "execution_count": null, "id": "d23ae3df", "metadata": {}, "outputs": [], "source": [ "n = 2\n", "F = corps_fini(n)\n", "m = card_P(n)\n", "for i in range(m):\n", " p1 = point_numero(F, i)\n", " for j in range(i + 1, m):\n", " p2 = point_numero(F, j)\n", " d = droite_incidente(F, p1, p2)\n", " print(str_point(p1), end=' ')\n", " print(str_point(p2), end=' ')\n", " print(str_droite(d))" ] }, { "cell_type": "markdown", "id": "61a43e29", "metadata": {}, "source": [ "### 4.5 Retour à la matrice d'incidence." ] }, { "cell_type": "markdown", "id": "37b51372", "metadata": {}, "source": [ "Soit $A$ la matrice d'incidence de $\\mathbb P$. Rappelons que $m=n^2+n+1$." ] }, { "cell_type": "markdown", "id": "72453953", "metadata": {}, "source": [ "**Proposition.** $AA^T=nI_m+J_m$ où $I_m$ est la matrice identité d'ordre $m$ et $J_m$ est la matrice de taille $m$ qui ne contient des 1.\n", "\n", "**Démonstration.** Soient $i,j\\in[|0,m-1|]$. Pour tout $k\\in[|0,m-1|]$, on a $A_{ik}A_{jk}=1$ si $p_i$ et $p_j$ sont incidents à $d_k$, et 0 sinon. Ainsi, $\\sum_{k=0}^{m-1} A_{ik}A_{jk}$ est le nombre de droites incidentes à $p_i$ et $p_j$.\n", "\n", "\n", "- Cas 1, $i=j$. $p_i$ est incident à exactement $n+1$ droites, donc\n", "\n", "$$\\sum_{k=0}^{m-1} A_{ik}A_{jk}=n+1$$\n", "\n", "- Cas 2, $i\\ne j$. $p_i$ et $p_j$ sont incidents à exactement une droite, donc\n", "\n", "$$\\sum_{k=0}^{m-1} A_{ik}A_{jk}=1$$\n", "\n", "Finalement,\n", "\n", "$$AA^T=\\begin{pmatrix}\n", "n+1&1&1&\\ldots&1\\\\\n", "1&n+1&1&\\ldots&1\\\\\n", "\\vdots&\\vdots&\\ddots&&\\vdots\\\\\n", "1&1&\\ldots&n+1&1\\\\\n", "1&1&\\ldots&1&n+1\\\\\n", "\\end{pmatrix}$$" ] }, { "cell_type": "markdown", "id": "1acf8e7d", "metadata": {}, "source": [ "Faisons un petit test." ] }, { "cell_type": "code", "execution_count": null, "id": "598de305", "metadata": {}, "outputs": [], "source": [ "def prod_mat(A, B):\n", " p, q = len(A), len(A[0])\n", " q1, r = len(B), len(B[0])\n", " assert q == q1\n", " C = p * [None]\n", " for i in range(p):\n", " C[i] = r * [0]\n", " for i in range(p):\n", " for j in range(r):\n", " for k in range(q):\n", " C[i][j] += A[i][k] * B[k][j]\n", " return C" ] }, { "cell_type": "code", "execution_count": null, "id": "61e582f4", "metadata": {}, "outputs": [], "source": [ "def transposee(A):\n", " p, q = len(A), len(A[0])\n", " C = q * [None]\n", " for i in range(q):\n", " C[i] = p * [0]\n", " for i in range(q):\n", " for j in range(p):\n", " C[i][j] = A[j][i]\n", " return C" ] }, { "cell_type": "code", "execution_count": null, "id": "55738c13", "metadata": {}, "outputs": [], "source": [ "A = matrice_incidence(corps_fini(3))\n", "prod_mat(A, transposee(A))" ] }, { "cell_type": "markdown", "id": "94897524", "metadata": {}, "source": [ "**Proposition.** $\\det(A)=\\pm(n+1)n^{\\frac 1 2n(n+1)}$.\n", "\n", "**Démonstration.** Soit $B=AA^T\\in\\mathcal M_m(\\mathbb Z)$. On a \n", "\n", "$$\\det(B)=\\begin{vmatrix}\n", "n+1&1&1&\\ldots&1\\\\\n", "1&n+1&1&\\ldots&1\\\\\n", "\\vdots&\\vdots&\\ddots&&\\vdots\\\\\n", "1&1&\\ldots&n+1&1\\\\\n", "1&1&\\ldots&1&n+1\\\\\n", "\\end{vmatrix}$$\n", "\n", "Soustrayons la première ligne à toutes les autres pour obtenir\n", "\n", "$$\\det(B)=\\begin{vmatrix}\n", "n+1&1&1&\\ldots&1\\\\\n", "-n&n&0&\\ldots&0\\\\\n", "\\vdots&\\vdots&\\ddots&&\\vdots\\\\\n", "-n&0&\\ldots&n&0\\\\\n", "-n&0&\\ldots&0&n\\\\\n", "\\end{vmatrix}$$\n", "\n", "Ajoutons à la première colonne la somme de toutes les autres. Comme $m+n=(n+1)^2$,\n", "\n", "$$\\det(B)=\\begin{vmatrix}\n", "(n+1)^2&1&1&\\ldots&1\\\\\n", "0&n&0&\\ldots&0\\\\\n", "\\vdots&\\vdots&\\ddots&&\\vdots\\\\\n", "0&0&\\ldots&n&0\\\\\n", "0&0&\\ldots&0&n\\\\\n", "\\end{vmatrix}$$\n", "\n", "On a là un déterminant de matrice triangulaire. On en déduit\n", "\n", "$$\\det(B)=(n+1)^2n^{m-1}=(n+1)^2n^{n(n+1)}$$\n", "\n", "Or, $\\det(B)=\\det(A)^2$, d'où le résultat.\n", "\n", "**Remarque.** Le signe exact de $\\det(A)$ n'a pas grand intérêt. En effet la matrice $A$ n'est définie qu'à condition d'avoir fixé une énumération des éléments de $P$ et de $D$. Un changement d'énumération conduit à des échanges de lignes et de colonnes de la matrice, et donc à un changement de signe de son déterminant." ] }, { "cell_type": "code", "execution_count": null, "id": "d4393155", "metadata": {}, "outputs": [], "source": [ "def detA(n):\n", " return (n + 1) * n **(n * (n + 1) // 2)" ] }, { "cell_type": "code", "execution_count": null, "id": "49279f9b", "metadata": {}, "outputs": [], "source": [ "for n in [2, 3, 5, 7]:\n", " print('%3d %d' % (n, detA(n)))" ] }, { "cell_type": "markdown", "id": "bea9f243", "metadata": {}, "source": [ "### 4.6 Quadrangles et quadrilatères" ] }, { "cell_type": "markdown", "id": "2f079789", "metadata": {}, "source": [ "Il nous reste à montrer que $\\mathbb P$ vérifie l'axiome $P3$ des plans projectifs.\n", "\n", "**Définition.** Un *quadrangle* est un ensemble $Q$ de 4 points tel que toute droite est incidente à au plus deux points de $Q$.\n", "\n", "**Définition.** Un *quadrilatère* est un ensemble $Q$ de 4 droites tel que tout point est incident à au plus deux droites de $Q$.\n", "\n", "**Proposition.** Il existe un quadrangle et un quadrilatère.\n", "\n", "**Démonstration.** Étant données les symétries entre points et droites, l'existence d'un quadrangle équivaut à celle d'un quadrilatère. Concentrons nous sur les quadrangles. Considérons les 4 points $p_1=[0, 0, 1]$, $p_2=[1, 0, 1]$, $p_3=[0, 1, 1]$ et $p_4=[1, 1, 1]$. Montrons que l'ensemble $Q$ de ces 4 points est un quadrangle. Soit $d=[a,b,c]$ une droite, où $(a,b,c)\\ne(0,0,0)$.\n", "\n", "Supposons que $d$ est incidente à, par exemple, $p_2$, $p_3$ et $p_4$. On a alors\n", "\n", "$$\\left\\{\\begin{array}{lll}\n", "a+c&=&0\\\\\n", "b+c&=&0\\\\\n", "a+b+c&=&0\n", "\\end{array}\\right.$$\n", "\n", "d'où, facilement, $a=b=c=0$. Contradiction. On laisse en exercice les trois autres cas, tout aussi impossibles." ] }, { "cell_type": "markdown", "id": "f9685f0b", "metadata": {}, "source": [ "## 5. Conclusion" ] }, { "cell_type": "markdown", "id": "a28e83b2", "metadata": {}, "source": [ "Nous avons montré au fil de ce notebook que le triplet $\\mathbb P$ créé à partir du corps $\\mathbb Z/n \\mathbb Z$ était un plan projectif fini. En réalité, la construction que nous avons faite et les théorèmes que nous avons montré restent valables en remplaçant $\\mathbb F$ par n'importe quel corps fini.\n", "\n", "Existe-t-il des plans projectifs autres que ceux-ci ? La réponse est oui. Dans un plan projectif fini quelconque (c'est à dire vérifiant les axiomes $P1$, $P2$ et $P3$), on peut montrer la propriété suivante.\n", "\n", "**Proposition.** Soit $\\mathbb P=(P, D, I)$ un plan projectif fini. Il existe un unique entier $n\\ge 2$ tels que\n", "\n", "- $|P|=|D|=n^2+n+1$.\n", "- Pour toute droite $d$, $d$ est incidente à $n+1$ points.\n", "- Pour tout point $p$, $p$ est incident à $n+1$ droites.\n", "\n", "L'entier $n$ est appelé *l'ordre* du plan projectif." ] }, { "cell_type": "markdown", "id": "207294d1", "metadata": {}, "source": [ "Dans ce notebook, nous avons montré que pour tout $n$ premier, il existe au moins un plan projectif d'ordre $n$. En étendant nos résultats à des corps finis quelconques, on peut montrer que pour tout $n$ premier et tout $k\\ge 1$, il existe un plan projectif d'ordre $n^k$. Les entiers $n\\le 14$ pour lesquels nous avons montré qu'il existe un plan projectif d'ordre $n$ sont donc\n", "\n", "$$2,3,4,5,7,8,9,11,13$$\n", "\n", "Manquent à cette liste : 6, 10, 12 et 14.\n", "\n", "Citons le théorème suivant.\n", "\n", "**Théorème de Bruck-Ryser.** Soit $n\\ge 2$. On suppose que $n\\equiv 1\\bmod 4$ ou $n\\equiv 2\\bmod 4$. S'il existe un plan projectif fini d'ordre $n$, alors il existe $a,b\\in\\mathbb N$ tels que $n=a^2+b^2$.\n", "\n", "Les entiers 6 et 14 sont congrus à 2 modulo 4, mais ne sont pas la somme de deux carrés. Il n'existe donc pas de plan projectif d'ordre 6 ou 14.\n", "\n", "Remarquons que $10\\equiv 2\\bmod 4$ mais $10=3^2+1^2$ est une somme de deux carrés. Le théorème de Bruck-Ryser reste donc muet sur le statut de l'entier 10. Lam, Thiel et Swiercz ont démontré en 1989 qu'il n'existe pas de plan projectif d'ordre 10. Leur démonstration traitait un certain nombre de cas avec l'aide d'ordinateurs. Le calcul a pris 800 heures. L'entier 10 est ainsi le plus petit contre-exemple à la réciproque du théorème de Bruck-Ryser.\n", "\n", "Comme $12\\equiv 0\\bmod 4$, le théorème de Bruck-Ryser ne peut pas s'appliquer à $n=12$. Existe-t-il un plan projectif d'ordre 12 ? La question reste à ce jour une question ouverte." ] }, { "cell_type": "markdown", "id": "3805bd2f", "metadata": {}, "source": [ "**Bibliographie**\n", "\n", "- A. Pál, *An Introduction to Finite Projective Planes*, Imperial College, London, 2018\n", "\n", "- C.W.H. Lam, L. Thiel, S. Swiercz, *The Non-existence of Finite Projective Planes of Order 10*, Canadian Journal of Mathematics, Vol. XLI, No 6, pp 1117-1123, 1989\n", "\n", "- R.H. Bruck, H.J. Ryser, *The Nonexistence of Certain Finite Projective Planes*, Canadian Journal of Mathematics, Vol. I, pp. 88–93, 1948" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.10.8" } }, "nbformat": 4, "nbformat_minor": 5 }