2025-Ens-MpD-Corrigé

Écoles normales supérieures — 2025

Mathématiques D — Filière MP

Points entiers dans les polytopes

Le problème vise à démontrer une généralisation, due à Michel Brion, de l’identité {\sum\limits_{i=m}^{n-1}x^i=(x^m-x^n)/(1-x)} pour {m\lt n} entiers.

On note {\mathbb N=\{0,1,\ldots\}}, {\mathbb N^*=\{1,2,\ldots\}} et {\operatorname{Card}A} le cardinal d’un ensemble {A}. Sur {\mathbb R^n}, {\langle\cdot,\cdot\rangle} désigne le produit scalaire canonique. Pour {x\in\mathbb R}, {\lfloor x\rfloor} est sa partie entière et {\{x\}=x-\lfloor x\rfloor}.

Partie préliminaire

Une fonction {P:\mathbb Z\to\mathbb C} est quasi-polynomiale si {P(n)=\sum\limits_{i=0}^kc_i(n)n^i}, avec des fonctions périodiques {c_i}. Si {c_k} n’est pas identiquement nulle, {k} est le degré et {c_k} le coefficient dominant.

On appelle désormais quasi-polynomiale sur {\mathbb N} la restriction d’une telle fonction sur {\mathbb Z}, son prolongement étant unique par (2).

1. Décomposition d’un entier en parties

Soient {k\geq1} et {a_1,\ldots,a_k\geq1} entiers, premiers entre eux dans leur ensemble si {k\geq2}. On pose {P(n)=\operatorname{Card}\{(n_1,\ldots,n_k)\in\mathbb N^k:\textstyle\sum_i a_in_i=n\},}puis {F(x)=\sum\limits_{n\geq0}P(n)x^n}.

Dans la suite de cette partie, {k=2}.

2. Étude des polytopes

Un polytope est un compact non vide {P\subset\mathbb R^n} défini par un nombre fini d’inégalités {\ell_i(x)\leq a_i}, {i\in I}, avec {\ell_i} linéaire. Sa dimension est celle de {\vec P=\operatorname{Vect}\{x-y:x,y\in P\}}.

Une face est un ensemble non vide {F_J=\{x\in P:\ell_j(x)=a_j\text{ pour }j\in J\}}, pour {J\subset I}. On pose {S_F=\{i\in I:\ell_i(x)=a_i\text{ pour tout }x\in F\},}et {F^\circ=\{x\in P:\ell_i(x)=a_i\Longleftrightarrow i\in S_F\}}. Une face de dimension {0} est un sommet.

On note {\operatorname{Conv}(X)} l’ensemble des combinaisons convexes finies de points de {X}. Les notions de face et d’intérieur relatif ne dépendent pas de la présentation de {P} par inégalités ; ce fait est admis.

2.1. Enveloppe convexe des sommets

On fixe maintenant un ensemble fini non vide {V\subset\mathbb R^n} et l’on veut montrer que {\operatorname{Conv}(V)} est un polytope.

On admet que, si {C} est un convexe fermé non vide et {x\notin C}, il existe un unique {y\in C} tel que {\langle x-y,z-y\rangle\leq0} pour tout {z\in C}.

2.2. Formule d’Euler

On note {\mathcal F_n} l’espace des fonctions {\mathbb R^n\to\mathbb R} et {U_n} le sous-espace engendré par les indicatrices {\mathbf1_P} des polytopes.

On définit {\chi_1(f)=\sum\limits_{x\in\mathbb R}(f(x)-f(x+))}, somme à support fini.

2.3. Triangulations

Un complexe est une famille finie non vide {\mathcal C} de polytopes telle que l’intersection de deux membres soit vide ou une face commune. Sa réalisation est {|\mathcal C|=\bigcup_{P\in\mathcal C}P}. Ses faces sont toutes les faces des membres, chacune comptée une seule fois, et {\chi(\mathcal C)=\sum\limits_F(-1)^{\dim F}}.

Un simplexe de dimension {k} est un polytope ayant {k+1} sommets. Une triangulation de {P} est un complexe de simplexes de réalisation {P}.

3. Le polytope de Birkhoff

Une matrice {M\in\mathcal M_n(\mathbb R)} est bistochastique si ses coefficients sont positifs ou nuls et si chaque somme de ligne et chaque somme de colonne vaut {1}. On note {B_n} l’ensemble de ces matrices et {\mathfrak S_n} le groupe des permutations.

4. Développement des fractions rationnelles

On note {\mathbb C[[\mathbb Z^n]]} l’espace des fonctions {\mathbb Z^n\to\mathbb C} et {x^\gamma} la fonction valant {1} en {\gamma} et zéro ailleurs. Ainsi {f=\sum\limits_{\gamma\in\mathbb Z^n}f(\gamma)x^\gamma}. Une somme de fonctions est définie lorsque chaque coefficient ne reçoit qu’un nombre fini de contributions non nulles.

Le produit est la convolution {(fg)(\gamma)=\sum_{\alpha+\beta=\gamma}f(\alpha)g(\beta),}lorsque chaque somme est finie. On admet sa commutativité et son associativité quand il est défini. Les fonctions à support fini forment une algèbre intègre {\mathbb C[\mathbb Z^n]}, dont on note {\mathbb C(\mathbb Z^n)} le corps des fractions.

Deux fractions {P_1/Q_1} et {P_2/Q_2} y sont égales si {P_1Q_2=P_2Q_1}.

Un élément {f} est rationnel s’il existe un polynôme de Laurent non nul {Q} tel que {Qf} ait un support fini. Il est de torsion si l’on peut avoir {Qf=0}. On note {\mathcal R} et {\mathcal T} les espaces correspondants.

5. Séries d’Euler–Maclaurin

Pour {A\subset\mathbb R^n}, on pose {E_A=\sum\limits_{\gamma\in A\cap\mathbb Z^n}x^\gamma}. Si cette série est rationnelle, on note {IE_A=I(E_A)}. On écrit {\gamma+A=\{\gamma+a:a\in A\}}.

5.1. Rationalité des séries associées aux cônes

5.2. Le théorème de Brion

On écrit {P=\{x:\ell_i(x)\leq a_i,\ i\in I\}}. On dit que {P} est rationnel lorsque les {a_i} et les coefficients des {\ell_i} sont entiers. Pour {y\notin P}, on dit que {y} voit {x\in P} si {[x,y]\cap P=\{x\}}, et l’on note {\Sigma_y} l’ensemble des points ainsi vus.

Dans la suite de cette section, {P} est rationnel.

5.3. Application au théorème d’Ehrhart

Soient {\gamma_1,\ldots,\gamma_k\in\mathbb Z^n}, {k\geq1}, et {P=\operatorname{Conv}(\gamma_1,\ldots,\gamma_k)}. Pour {t\in\mathbb N}, on pose {tP=\{tx:x\in P\}}.

Pour {k\geq1}, on note {H_n(k)} le nombre de matrices entières à coefficients positifs ou nuls dont toutes les sommes de lignes et de colonnes sont égales à {k}.