Corrigé ENS Ulm 2025 Maths D MP — Partie 5.3 (Q45 à Q48) : Théorème d'Ehrhart : polynôme (ou quasi-polynôme) de comptage, matrices magiques de Birkhoff

Sujet officiel du concours ENS Ulm, session 2025, épreuve Maths D MP. Corrigé rédigé par Ibrahim Alame.

Énoncé

Soient $γ_{1}, \dots, γ_{k} \in Z^{n}$ et $P = Conv (γ_{1}, \dots, γ_{k})$ ; pour $t \in N$ , $tP = {t x : x \in P}$ . Les cônes $C_{v}$ sont ceux de la partie 5.2, relatifs à un système d'inégalités de $P$ .

Q45. Pour $t \in N^{*}$ , $I E_{tP} = \sum_{v} x^{t v - v} I E_{C_{v}}$ , la somme portant sur les sommets $v$ de $P$ .
Q46. Il existe un polynôme $f_{P} \in C [X]$ tel que $Card (tP \cap Z^{n}) = f_{P} (t)$ pour tout $t \in N$ .
Q47. Si $P$ est seulement un polytope rationnel, il existe une fonction quasi-polynomiale $f_{P}$ telle que $Card (tP \cap Z^{n}) = f_{P} (t)$ pour tout $t \in N$ .
Pour $k \geq 1$ , $H_{n} (k)$ est le nombre de matrices de $M_{n} (Z)$ à coefficients $\geq 0$ dont toutes les sommes de lignes et de colonnes valent $k$ .
Q48. $H_{n} (k)$ est un polynôme en $k$ ; déterminer son degré.

Corrigé

On reprend les notations de la partie 5.2 : $K_{F} = {w : ℓ_{i} (w) \leq 0, i \in S_{F}}$ , $C_{v} = v + K_{v}$ , et les lemmes L10, L11.

Préliminaires. $P$ est un polytope (Q17) dont les sommets sont parmi les $γ_{i}$ (Q18), donc dans $Z^{n}$ . Fixons un système $P = {ℓ_{i} \leq a_{i}, i \in I}$ . Pour $t > 0$ , $tP = {x : ℓ_{i} (x) \leq t a_{i}, i \in I}$ et l'homothétie $x \mapsto t x$ conserve les contraintes saturées : les faces de $tP$ sont les $tF$ , de même dimension, ses sommets sont les $t v$ , et $S_{t v} = S_{v}$ . Le cône de $tP$ au sommet $t v$ est donc

$C_{t v} (tP) = {x : ℓ_{i} (x) \leq t a_{i}, i \in S_{v}} = t v + K_{v},$

puisque $ℓ_{i} (t v) = t a_{i}$ pour $i \in S_{v}$ .

Q45. Soit $t \in N^{*}$ . Le polytope $tP$ a des sommets $t v$ entiers ; par Q44 (valable pour les polytopes à sommets rationnels) : $I E_{tP} = \sum_{v} I E_{t v + K_{v}}$ . Or $t v + K_{v} = (t - 1) v + C_{v}$ avec $(t - 1) v \in Z^{n}$ , donc $E_{t v + K_{v}} = x^{(t - 1) v} E_{C_{v}}$ (Q36), et $I (x^{(t - 1) v} E_{C_{v}}) = x^{t v - v} I E_{C_{v}}$ (Q34). D'où

$I E_{tP} = v sommet de P \sum x^{t v - v} I E_{C_{v}} .$

Q46. Étape 1 : le cas $t = 0$ . Montrons, pour tout polytope à sommets rationnels, $\sum_{F} (- 1)^{d i m F} 1_{K_{F}} = 1_{{0}}$ sur $R^{n}$ . En $w = 0$ , qui est dans tous les $K_{F}$ , la somme vaut $1$ (Q24). Soit $w \neq = 0$ et $x_{0} \in P$ ; posons $y = x_{0} + M w$ . Pour $i \in I$ : si $ℓ_{i} (w) \leq 0$ , $ℓ_{i} (y) \leq ℓ_{i} (x_{0}) \leq a_{i}$ pour tout $M \geq 0$ ; si $ℓ_{i} (w) > 0$ , $ℓ_{i} (y) > a_{i}$ dès que $M > (a_{i} - ℓ_{i} (x_{0})) / ℓ_{i} (w)$ . Pour $M$ assez grand (nombre fini de conditions, et $M ∥ w ∥$ supérieur au diamètre de $P$ ), on a donc $y \in / P$ et, pour toute face $F$ , $y \in C_{F} ⟺ w \in K_{F}$ . L'égalité ponctuelle établie en Q43 donne alors $\sum_{F} (- 1)^{d i m F} 1_{K_{F}} (w) = 1_{P} (y) = 0$ . En restreignant à $Z^{n}$ : $\sum_{F} (- 1)^{d i m F} E_{K_{F}} = 1$ . Pour $dim F > 0$ , $E_{K_{F}}$ est de torsion (même argument qu'en Q42 : $K_{F} + γ = K_{F}$ pour $γ \in F \cap Z^{n}$ non nul), et $E_{K_{v}}$ est rationnel (L10 et Q38). En appliquant $I$ :

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →