Archive

Archives pour la catégorie ‘Maths difficiles’

Partage de secret

07/07/2010 Tukikun Aucun commentaire

Supposons que le PDG d’une grande compagnie de soda veuille garder secrète la recette qui a fait la fortune de l’entreprise. Il l’enferme donc dans un coffre fort blindé, qui s’ouvre à l’aide d’une certaine clé (qu’il garde secrète). Cette solution est très sécuritaire dans le sens où seul le PDG peut accéder au secret. Mais elle revêt un gros défaut : si le PDG perd cette clé, ou vient à décéder dans un accident, la clé est perdue et personne ne peut jamais accéder à la recette, entraînant inévitablement la déroute de la multinationale.

Une des solutions est de donner des copies de cette clé secrète à des collaborateurs au travail. Mais répliquer la clé augmente les chances des espions de l’obtenir et de rapporter la recette à l’entreprise concurrente. Le PDG est bien conscient qu’il ne peut pas faire entièrement confiance à un de ses 5 subordonnés. Il veut donc mettre en place un schéma où tout groupe contenant au moins 3 de ses subordonnés puisse ouvrir le coffre alors que tout groupe contenant strictement moins de 3 subordonnés ne puisse rien savoir sur la clé.
Une solution qui consisterait à donner des bouts du secret aux subordonnés de manière à ce qu’ensemble ils puissent le reconstruire ne convient pas parce qu’ils connaîtraient alors partiellement la clé secrète.

Ce problème peut-être résolu par la mise en place d’un schéma de partage de secret.

Le partage de secret avec seuil

Notons 2\leq t<n des entiers. Notre but est de partager une clé secrète K entre un ensemble de n personnes \mathcal P = \{P_1, \ldots, P_n\} de telle manière que toute coalition de t ou plus de ces personnes puisse calculer K facilement, et que toute coalition de t-1 ou moins de ces personnes ne puisse rien déterminer sur la valeur de K, autrement dit que toutes les valeurs de K possibles soient équiprobables. Un tel schéma est appelé un schéma au seuil (t,n). Dans l’exemple introductif, le PDG cherche un schéma au seuil (3,5).

La valeur du secret est choisie par un participant spécial D (le dealer) (que l’on suppose bien évidemment ne pas faire partie de \mathcal P). Le dealer va donner à chaque participant une clé de partage. Cette distribution sera secrète bien entendu, pour qu’aucun des participants ne connaissent les clés de partage des autres participants.

Le problème de construire un tel schéma a été résolu indépendamment par Sharmir [1] et Blakley [2] en 1979.

Schéma de Shamir

Commençons par présenter le schéma de Shamir, qui repose sur l’interpolation polynômiale.

Le dealer veut partager la clé secrète K\in \mathbf F_q où q\geq n+1 est la puissance d’un nombre premier (on peut prendre q=p premier et raisonner dans \mathbf F_p bien évidemment). Il choisit de manière aléatoire n éléments distincts de \mathbf F_q que l’on note x_1, \ldots, x_n. Ces éléemnts ne sont pas les clés de partages secrètes, ce sont des clés publiques : chaque P_i reçoit la clé x_i. Dans l’exemple du PDG, on pourrait dire par exemple que x_i représente l’ordre d’arrivée de l’employé dans l’entreprise. Ensuite, il réalise les étapes suivantes :

  1. Il choisit secrètement et aléatoirement t-1 éléments de \mathbf F_q notés a_1, \ldots, a_{t-1}.
  2. Pour tout 1\leq i\leq n, le dealer calcule y_i=a(x_i) où

    a(X) = K+\sum_{i=1}^{t-1}a_jX^j.

  3. Pour tout 1\leq i\leq n, le dealer donne secrètement la clé de partage y_i à P_i

Regardons comment un groupe B=\left\{P_{i_1}, \ldots, P_{i_t}\right\} de t personnes (avec leur clé publique x_i) peut retrouver les coefficients secrets du polynôme a(X) par interpolation, et ainsi retrouver K=a(0). Comme y_{i_k} = a(x_{i_k}) pour tout 0\leq k\leq t, le groupe B obtient t équations linéaires en les t inconnues K, a_1, \ldots, a_{t-1}. Ainsi, le système obtenu par B peut-être écrit sous la forme

\begin{pmatrix}1& x_{i_1}& x_{i_1}^2& \cdots& x_{i_1}^{t-1}\\1& x_{i_2}& x_{i_2}^2& \cdots& x_{i_2}^{t-1}\\\vdots& \vdots & \vdots & & \vdots\\1& x_{i_t}& x_{i_t}^2& \cdots& x_{i_t}^{t-1}\\\end{pmatrix}\begin{pmatrix}K\\a_1\\\vdots\\a_{t-1}\end{pmatrix} = \begin{pmatrix}y_{i_1}\\y_{i_2}\\\vdots\\y_{i_t}\end{pmatrix}.

Or, la matrice A des coefficients x_i est appelée matrice de Vandermonde et son déterminant vaut \det(A) = \prod_{1\leq k<j\leq t}\left(x_{i_j}-x_{i_k}\right)\neq 0. Comme il est non nul (par choix des x_i), le système admet une unique solution sur \mathbf F_q, et K peut-être retrouvé.

Supposons maintenant que t-1 des n clés de partages secrètes sont révélées à un ennemi. Pour chaque candidat K'\in \mathbf F_q pour le secret, l'ennemi peut construire un et un unique polynôme a'(X) de degré t-1 tel que a'(0)=K' et a'(x_i)=y_i pour les t-1 clés connues. Par construction, ces q possibles polynômes sont équiprobables, en conséquence de quoi l'espion ne peut rien déduire sur la valeur de la clé secrète K.

Bien entendu, il y a une méthode alternative basée sur la formule de l'interpolation de Lagrange. La formule est la suivante :

a(X) = \sum_{j=1}^t y_{i_j} \prod_{\substack{1\leq k\leq t\\k\neq j}}\frac{X-x_{i_k}}{x_{i_j}-x_{i_k}}.

Étant donné qu’un groupe recherche la valeur du secret K=a(0), ils peuvent calculer

K = \sum_{j=1}^{t}y_{i_j}b_j, \qquad \text{avec} \quad b_j = \prod_{\substack{1\leq k\leq t\\k\neq j}}\frac{x_{i_k}}{x_{i_k}-x_{i_j}}.

Remarquons que les valeurs b_j ne dépendent que des x_i et peuvent-être pré-calculées.

Un exemple concret

Donnons un petit exemple concret pour soulager notre PDG qui a vraiment peur de faire un infarctus qui perdrait à tout jamais la recette ! Supposons que q=17 et que les coordonnées publiques sont x_i = i pour tout 1\leq i\leq 5. Supposons maintenant que les collaborateurs P_1, P_3 et P_5 veuillent retrouver le secret. Ils mettent en commun leurs clés de partages secrètes qui sont respectivement 8, 10 et 11. Comme a(X) = K+a_1X+a_2X^2, ils obtiennent le système d’équation suivant :

\left\{\begin{array}{lll}K+a_1+a_2 &=&8\\K+3a_1+9a_2&=&10\\K+5a_1+8a_2&=&11\end{array}\right.

Ce système admet une unique solution dans \mathbf F_{17}=\mathbf Z/17\mathbf Z : K=13, a_1=10 et a_2=2. Le secret est donc K=13 !

Schéma de Blakley

Donnons un autre exemple : le schéma de Blakley basé sur la géométrie des hyperplans sur les corps finis. Le secret est un point d’un espace t-dimensionnel, et les n clés de partages secrètes sont des hyperplans affines passant par ce point. Un hyperplan dans un espace t-dimensionnel à coordonnées dans un corps \mathbf F peut être décrit par une équation de la forme suivante :

a_1x_1 + a_2x_2 + \cdots + a_tx_t = y.

Le point d’intersection est obtenu en trouvant l’intersection d’un ensemble quelconque de t de ces hyperplans. Par exemple, le secret peut être la première coordonnée du point d’intersection.

Disons que \mathbf F = \mathbf F_q est le corps sur lequel on travaille. Le dealer génère un point x dans \mathbf F_q^t, où la première coordonnée x_1 est la clé secrète et les autres coordonnées sont choisies aléatoirement dans \mathbf F_q. Le ième participant recevra comme clé de partage secrète l’hyperplan sur \mathbf F_q d’équation

a_{i,1}x_1+a_{i,2}x_2+\cdots+a_{i,t}x_t=y_i.

Pour obtenir un schéma au seuil (t, n), il y aura n équations d’hyperplan, et on obtient alors un système linéaire n\times t: Ax=y.

Le dealer donne en pratique la clé de partage secrète y_i ainsi que les coordonnées (qui peuvent être publiques) a_{i,1}, \ldots, a_{i,t} au participant P_i. un choix judicieux pour la matrice A est de faire en sorte que ses lignes soient les lignes d’une matrice de Vandermonde pour se ramener à une situation similaire à celle du schéma de Shamir.

Pour aller plus loin…

Bien entendu, ceci n’est qu’une introduction sommaire à un domaine toujours en pleine expansion en cryptologie. On pourra trouver d’autres schémas basés sur la géométrie, sur les graphes, sur le théorème des restes chinois… Une excellente introduction au sujet est l’article [3].

Pour les plus intrépides d’entre vous, remarquez que jusquà présent nous avons travaillé sur des corps, s’autorisant allégrement la possibilité d’inverser pour retrouver le secret si nécessaire. Un sujet intéressant est de vouloir construire des schémas valables sur n’importe quel groupe abélien (sans connaître le groupe, c’est-à-dire un schéma en boîte noire), qui ont fait l’objet de deux articles récents [4] et [5].

Références
  • [1] A. Shamir – « How to share a secret », Communications of the ACM 22 (1979), no. 11, p. 612 – 613.
  • [2] G. R. Blakley – « Safeguarding cryptographic keys », AFIPS Conference Proceedings 48 (1979), p. 313 – 317.
  • [3] D. R. Stinson – « An explication of secret sharing schemes », Designs, Codes and Cryptography 2 (1992), no. 4, p. 357 – 390.
  • [4] R. Cramer & S. Fehr – « Optimal black-box secret sharing over arbitrary Abelian groups », Advances in Cryptology – CRYPTO’02 (2002), p. 272 – 287.
  • [5] R. Cramer, S. Fehr & M. Stam – « Black-box secret sharing from primitive sets in algebraic number fields », Advances in Cryptology – CRYPTO 2005, Springer, 2005, p. 344-360.
Categories: Maths difficiles, Vulgarisation Tags: , , , , , , , , ,

Le troisième problème de Hilbert avec du produit tensoriel

26/02/2010 Tukikun 2 commentaires

En 1900, lors de l’Exposition Universelle, à Paris, a lieu le deuxième congrès de mathématiques. L’exposé de David Hilbert (1862-1943, mathématicien allemand, considéré comme un des plus grands mathématiciens du XXème siècle) est l’un des plus attendus. Le 8 août 1890, il présente donc sa liste de 23 problèmes qui tiennent les mathématiciens en échec et qui marqueront le cours des mathématiques du XXème siècle.

On s’intéresse dans cet article au troisième problème de Hilbert, qui est considéré comme le plus facile, et qui a eu une existence brève puisque la solution a été apportée par Dehn dès 1900. Il fallait spécifier deux tétraèdres de même base et de même hauteur, qui ne se subdivisent d’aucune manière en tétraèdres superposables, et qui ne se laissent pas compléter par des tétraèdres superposables en des polyèdres pour lesquels une telle subdivision en tétraèdres superposables soit possible (Ouf ! On peut respirer…). Autrement dit, si deux polyèdres ont même volume, peut-on produire un puzzle pour passer de l’un à l’autre ? Ou encore, si l’on a deux polyèdres de même volume, peut-on découper le premier en un nombre fini de morceaux (polyèdres) et obtenir le second en recollant les morceaux ?

La réponse à ce problème est négative. En particulier il est impossible de découper un cube en un nombre fini de polyèdres et de reconstituer un tétraèdre régulier (de même volume) à partir des morceaux. La démonstration de Dehn repose sur l’introduction d’un nouvel invariant appelé l’invariant de Dehn.

Découpages et recollements

Soient A et B deux parties de \mathbb R^d. On dit qu’elles sont équivalentes par découpage et recollement (ou équidécomposables) s’il existe une partition de A (resp. de B),

A=A_1 \cup A_2 \cup \cdots \cup A_n (resp. B=B_1 \cup B_2 \cup \cdots \cup B_n)

et, pour chaque i=1, 2, \ldots, n, une isométrie g_i:A_i\to B_i qui applique A_i sur B_i. On note alors A\sim B.

Cette relation est clairement une relation d’équivalence.

Polygones, polyèdres, tétraèdres

Afin de se mettre d’accord, il est nécessaire de définir clairement les notions de polygones (ou devrait-on dire de domaines polygonaux) dans le plan, de polyèdre et de tétraèdre dans l’espace.

Un polygone est une figure géométrique plane, formée d’une suite de segments, chacun d’entre eux partageant une extrémité avec le précédent et le suivant, délimitant ainsi un contour fermé. Par exemple, les triangles, les rectangles, les hexagones sont des polygones…

Un polyèdre est traditionnellement une forme tridimensionnelle qui se compose d’un nombre fini de faces polygonales qui sont des parties de plans; les faces se rencontrent par paires le long des arêtes qui sont des segments de droite, et les arêtes se rencontrent aux points nommés sommets.

Icosadodécaèdre

Un tétraèdre est un polyèdre dont les 4 faces sont des triangles. Il est dit régulier si ses 4 faces sont des triangles équilatéraux.

Découpage des polyèdres : pourquoi cette question ?

Nous connaissons tous la formule élémentaire qui donne l’aire d’un triangle : la base fois la hauteur divisé par deux. La preuve de ce résultat consiste à découper le triangle en petits polygones et à les réarranger afin d’obtenir un rectangle qui a la même aire.

Peut-on utiliser un argument semblable (c’est-à-dire une preuve par découpage et recollement) afin d’obtenir le volume d’une pyramide ? En effet, on obtiendrait une preuve « élémentaire » du théorème XII.5 d’Euclide (qui dit que deux pyramides de même base et de même hauteur ont même volume). Et nous obtiendrions ainsi une définition élémentaire du volume d’un polyèdre. En effet, Euclide utilise un processus infini, l’exhaustion (un passage à la limite). Les démonstrations ultérieures de cette formule font toutes appel à des méthodes relevant de près ou de loin à un calcul intégral et aucune démonstration géométrique plus simple n’a pu être trouvée.

Le tétraèdre régulier n’est pas équidécomposable avec le cube de même volume.

Pour prouver ce théorème, Dehn a introduit un nouvel invariant qui porte son nom : l’invariant de Dehn.

Invariant de Dehn, version produit tensoriel

Les sous-groupes de \mathbb R étant soit dense, soit de la forme \alpha\mathbb Z, \alpha\in\mathbb R^*, on a \pi\mathbb Z qui est un sous-groupe distingué (car (\mathbb R, +) est abélien) de \mathbb R. On peut ainsi considérer le groupe quotient \mathbb R/\pi\mathbb Z, qui peut être vu comme le groupe des angles de droite (au moyen de la mesure des angles en radians).

On pourra alors définir l’invariant de Dehn dans le produit tensoriel \mathbb R \otimes_{\mathbb Z} (\mathbb R/\pi\mathbb Z).

Par définition du produit tensoriel, on a une application \mathbb Z-bilinéaire naturelle

i : \begin{array}[t]{rcl}\mathbb R\times(\mathbb R/\pi\mathbb Z) & \to & \mathbb R\otimes_{\mathbb Z}(\mathbb R/\pi\mathbb Z) \\ (a,\theta) & \mapsto & a\otimes\theta\end{array}

On a aussi une fonction \mathbb Z-bilinéaire

\overline f : \begin{array}[t]{rcl}\mathbb R\times(\mathbb R/\pi\mathbb Z) & \to & \mathbb R \\ (a,\theta) & \mapsto & af(\theta)\end{array}

Par la propriété universelle du produit tensoriel, il existe une unique application \mathbb Z-linéaire

F : \begin{array}[t]{rcl}\mathbb R\otimes_{\mathbb Z}(\mathbb R/\pi\mathbb Z) & \to & \mathbb R \\ a\otimes\theta & \mapsto & af(\theta)\end{array}

On peut ainsi définir l’invariant de Dehn indépendamment de la fonction f en l’exprimant dans le produit tensoriel.

Soit un polyèdre P dans l’espace. On définit l’invariant de Dehn de P comme le nombre réel :

\delta(P)=\sum_{e\in P}\ell(e) \otimes \alpha(e)

où l’on somme sur toutes les arêtes e du polyèdre, \ell(e) représentant la longueur de l’arête e et \alpha(e) l’angle entre deux faces dont l’intersection est e.

On a donc le théorème suivant :

Si deux polyèdres sont équidécomposables, ils ont le même invariant de Dehn.

qui repose sur le caractère additif de l’invariant de Dehn : si un polyèdre P est réunion disjointe de polyèdres P_1, \ldots, P_r, on a

\delta(P)=\delta(P_1)+\cdots+\delta(P_r)

On souhaite donc calculer l’invariant de Dehn du cube et celui du tétraèdre. Pour cela on a besoin d’un résultat préliminaire :

Un élément t=a\otimes\theta \in \mathbb R\otimes_{\mathbb Z}(\mathbb R/\pi\mathbb Z) , avec a\neq 0, est nul si et seulement si \frac\theta\pi est rationnel. En effet, si \frac\theta\pi = \frac pq, on a

t=(q\frac aq)\otimes\frac pq \pi = \frac aq \otimes (q\frac pq \pi) = \frac aq \otimes p\pi = \frac aq \otimes 0 = 0.

Supposons maintenant que \frac\theta\pi est irrationnel. Par la propriété universelle du produit tensoriel, étant donnés

\overline f : \begin{array}[t]{rcl}\mathbb R\times(\mathbb R/\pi\mathbb Z) & \to & \mathbb R \\ (a,\theta) & \mapsto & af(\theta)\end{array} et i : \begin{array}[t]{rcl}\mathbb R\times(\mathbb R/\pi\mathbb Z) & \to & \mathbb R\otimes_\mathbb Z(\mathbb R/\pi\mathbb Z) \\ (a,\theta) & \mapsto & a\otimes\theta\end{array}

deux applications bilinéaires, il existe une unique application \mathbb Z-linéaire

F : \begin{array}[t]{rcl}\mathbb R\otimes_\mathbb Z(\mathbb R/\pi\mathbb Z) & \to & \mathbb R \\ a\otimes\theta & \mapsto & af(\theta)\end{array}

On aura gagné si on trouve f telle que f(\theta)\neq0. Comme \mathbb R est un \mathbb Q-espace vectoriel et qu’il existe des bases de \mathbb R comme \mathbb Q-espace vectoriel, et comme \theta et \pi sont \mathbb Q-indépendants, on les complète en une base et on envoie \pi sur 0 et \theta sur 1. Cet homomorphisme se factorise par \pi\mathbb Z et c’est ce que l’on désirait.

Preuve du théorème

Considérons le cube C. On utilisant la bilinéarité du produit tensoriel sur \mathbb Z on a

\delta(C)=\sum_{e\in C} \ell(e)\otimes \frac\pi2 = \sum_{e\in C} 2\frac{\ell(e)}2\otimes \frac\pi2 = \sum_{e\in C} \frac{\ell(e)}2\otimes 2\frac\pi2 = \sum_{e\in C} \frac{\ell(e)}2\otimes \pi = 0

Considérons maintenant le tétraèdre régulier T de volume 1 avec des cotés de longueur \ell (=6\sqrt2). En utilisant le résultat préliminaire et la liberté de la famille \{\alpha,\pi\} où \alpha est tel que \cos \alpha = \frac 13, on a

\delta(T)=\sum_{e\in T} \ell(e)\otimes \alpha = \sum_{e\in T} \ell\otimes\alpha = 6 \underbrace{\ell\otimes \alpha}_{\neq0}\neq 0.

Jolie application du produit tensoriel non ?

Categories: Maths difficiles Tags: , , , , , , ,

Preuve topologique de l’infinitude des nombres premiers

03/02/2010 Valvino 6 commentaires

Voilà un titre qui en jette un maximum! J’ai lu dans l’excellent livre Raisonnements divins (chez Springer) une démonstration étonnante du fait qu’il existe une infinité de nombres premiers. Elle est d’un niveau élevé car elle fait appel à des notions de topologie générale, mais elle est assez élémentaire pour qui connait cette théorie. Je la livre donc ici.

On définit une topologie sur \mathbb Z en disant que les ouverts sont le vide et les O \subset \mathbb Z vérifiant que pour tout entier a\in O, il existe un entier b>0 tel que a+b\mathbb Z\subset O. Il est clair que la réunion quelconque d’ouverts est un ouvert. De plus, si O_1,O_2 sont des ouverts, ou bien l’intersection est vide et O_1 \cap O_2 est un ouvert, ou bien pour a \in O_1 \cap O_2, on a a+b_1b_2\mathbb Z \subset O_1 \cap O_2, avec  des entiers b_1,b_2>0 tels que a+b_1\mathbb Z\subset O_1 et a+b_2\mathbb Z\subset O_2. Finalement,  O_1 \cap O_2 est un ouvert. On a donc bien une topologie sur \mathbb Z.

On remarque d’une part que tout ouvert non vide est infini (car par définition il contient un ensemble infini), et d’autre part que tout ensemble du type a+b\mathbb Z, avec a,b des entiers (b>0), est un fermé. En effet, on a

\displaystyle a+b\mathbb Z=\mathbb Z-\left(\bigcup_{k=1}^{b-1} [a+k+b\mathbb Z]\right),

c’est donc le complémentaire d’un ouvert.

Comme tout entier différent de 1 et -1 admet un diviseur premier, on a

\displaystyle \mathbb Z-\{-1,1\}=\bigcup_p 0+p\mathbb Z

où la réunion se fait sur tous les nombres premiers p. S’ils étaient en nombre fini, \bigcup_p 0+p\mathbb Z serait fermé comme réunion finie d’ensembles fermés. Par passage au complémentaire, \{-1,1\} serait ouvert, ce qui est absurde car c’est un ensemble fini non vide. Il existe donc une infinité de nombres premiers.

Joli, non?

Categories: Maths difficiles Tags: , , ,

Le théorème de Wielandt

26/01/2010 Valvino Aucun commentaire

La fonction gamma \Gamma prolonge la notion de factorielle sur l’ensemble des nombres complexes privés des entiers négatifs ou nul. Il s’agit là d’une fonction holomorphe, sauf aux entiers négatifs ou nul où elle admet des pôles. C’est donc une fonction méromorphe sur les nombres complexes.

On dispose de plusieurs caractérisations de cette fonction. Citons le théorème de Bohr-Mollerup :

Soit une fonction f:]0,+\infty[ \to ]0,+\infty[ telle que

  1. f(1)=1;
  2. f(x+1)=xf(x) pour tout x>0;
  3. f est log-convexe, c’est-à-dire que \log(f) est une fonction convexe.

Alors f(x)=\Gamma(x) pour tout x>0.

On dispose d’une autre caractérisation, il s’agit du théorème de Wielandt :

Soit f une fonction holomorphe sur \mathrm{Re}(z)>0 telle que

  1. f(1)=1;
  2. f(z+1)=zf(z) pour tout \mathrm{Re}(z)>0;
  3. f est bornée dans la bande 1 \leq \mathrm{Re}(z) \leq 2.

Alors f(z)=\Gamma(z) pour tout \mathrm{Re}(z)>0.

Je me propose de faire une esquisse de la démonstration.

On remarque tout d’abord que l’on peut étendre f sur l’ensemble des nombres complexes privés des entiers négatifs ou nul par 2. en suivant la même méthode que pour la fonction gamma. Ensuite, on remarque avec 1. que les résidus aux pôles sont les mêmes que ceux de la fonction gamma. Ainsi, la fonction g=f-\Gamma est une fonction entière.

Ensuite, on remarque que g est bornée sur la bande 0 \leq \mathrm{Re}(z) \leq 1. Pour cela, il suffit de remarquer que c’est le cas sur la bande 1 \leq \mathrm{Re}(z) \leq 2, en faisant une majoration explicite sur la formule définissant \Gamma. On utilise ensuite 2. pour se ramener à la bande 0 \leq \mathrm{Re}(z) \leq 1, le problème en 0 étant effaçable par 1.

Enfin, on pose h(z)=g(z)g(1-z).  Par ce qui précède, c’est une fonction entière bornée dans la bande 0 \leq \mathrm{Re}(z) \leq 1. De plus, h(z+1)=-h(z), ce qui montre que h est une fonction bornée sur l’ensemble des nombres complexes. Par le théorème de Liouville, elle est constante. Comme h(1)=0, on a h=0, c’est-à-dire g=0. Finalement, f=\Gamma.

Categories: Maths difficiles Tags: , , , ,

Mesure et pavés

01/08/2009 Tukikun 3 commentaires

Le problème

Plaçons nous dans l’espace \mathbb{R}^n, n\geq 2. On appelle un pavé un ensemble de la forme
P=I_1\times I_2\times \cdots\times I_n
où les I_j, j\in\left\{1, \ldots, n\right\} c’est-à-dire le produit cartésien d’intervalles bornés de \mathbb{R} (fermés, ouverts, demi-fermés : ça n’a pas d’importance !). On définie alors la mesure d’un pavé comme le produit des longueurs des intervalles :
mes(P)=\ell(I_1) \times \ell(I_2) \times \cdots \times \ell(I_n)
On rappelle que \ell(I_j) = sup(I_j)-inf(I_j).

Considérons alors N pavés de \mathbb{R}^n : P_1, P_2, \ldots, P_N, et un pavé P\subset \bigcup_{i=1}^N P_i. Si dans les dimensions 2 ou 3, il semble trivial que la mesure de P est inférieure à la somme des mesures des P_i, c’est-à-dire respectivement que l’aire d’un rectangle inclus dans une union d’autres rectangles est inférieure à la somme des aires de ces rectangles, et que le volume d’un parallélépipède rectangle inclus dans une union d’autres parallélépipèdes rectangles est inférieure à la somme des volumes de ces parallélépipèdes rectangles, est-ce vraiment si trivial dans \mathbb{R}^n ? Ca le semble, bien entendu, mais à ce jour je n’ai pas trouvé de démonstration simple de ce résultat.

P\subset \bigcup_{i=1}^N P_i \Longrightarrow mes(P)\leq\sum_{i=1}^N mes(P_i)

Une démonstration

On peut déjà supposer sans perte de généralité (WLOG) que les pavés sont tous fermés.

Idée de la démonstration :

Idée de démonstration

Idée de démonstration



On va raisonner par récurrence sur N le nombre de pavés.

Le cas N=1 est clair : si P=I_1\times I_2\times \cdots \times I_n et Q=J_1\times J_2 \times \cdots \times J_n, alors on a

P\subset Q \Longleftrightarrow \forall i \in \left\{1, \ldots, d\right\}, I_i \subset J_i

et dans ce cas,

mes(P) = \ell (I_1)\times \ell(I_2) \times \cdots \times \ell(I_n) \leq\ell (J_1)\times \ell(J_2) \times \cdots \times \ell(J_n) = mes(Q)

Considérons alors le cas général. Notons P=I_1\times I_2 \times \cdots \times I_n et P_i = I_{i,1}\times I_{i,2}\times \cdots \times I_{i,n}. Pour chaque j\in \left\{1,\ldots, n\right\}, on subdivise l’intervalle I_j de la façon suivante :

I_j=\left[a^j_1,a^j_2\right]\cup \left[a^j_2,a^j_3\right]\cup \cdots \cup \left[a^j_{m_j},a^j_{m_j+1}\right]

où \left\{a^j_k\right\}_{k\in\left\{1, \ldots, m_j\right\}} est l’ensemble des extrémités des intervalles I_j\cap I_{i,j} pour i parcourant 1,2,\ldots, N.

Notons alors

E=\left\{k=(k_1, \ldots, k_n) \in \mathbb{N}^n \mid 1\leq k_1\leq n_1, \ldots, 1\leq k_n\leq m_n\right\}

Pour k\in E, on note Q_k = \left[a^1_{k_1}, a^1_{k_1+1}\right] \times \left[a^1_{k_2}, a^1_{k_2+1}\right] \times \cdots \times \left[a^1_{k_n}, a^1_{k_n+1}\right]. Avec ces notations, on a que P=\bigcup_{k\in E}Q_k, et que

(E): \qquad mes(P) = \prod_{j=1}^n \ell(I_j) = \prod_{j=1}^n \sum_{k_j=1}^{m_j} \ell \left(\left[a_{k_j}^j, a_{k_j+1}^j\right]\right) = \sum_{k\in E} mes(Q_k)

Or,

\sum_{k\in E} mes(Q_k) \leq \sum_{i=1}^N\left(\sum_{k \mid Q_k\subset P_i}mes(Q_k)\right)

et en appliquant (E) à P_i\cap P, on obtient

\sum_{k\in E} mes(Q_k) \leq \sum_{i=1}^N mes(P_i\cap P) \leq \sum_{i=1}^N mes(P_i)

Et c’est, enfin, ce que l’on désirait.

Auriez-vous une idée pour simplifier cette démonstration ? Peut-on réellement considérer le résultat comme trivial sinon ? Je suis preneur de toute réflexion à ce sujet !

Categories: Maths difficiles Tags: , ,