Maths A

# Sujet — Mathématiques A, filière MP — X / ENS — 2016

ÉCOLE POLYTECHNIQUE – ÉCOLES NORMALES SUPÉRIEURES

CONCOURS D’ADMISSION 2016

FILIÈRE MP

**COMPOSITION DE MATHÉMATIQUES – A – (XLCR)**

(Durée : 4 heures)

L’utilisation des calculatrices n’est pas autorisée pour cette épreuve.

*Toute affirmation doit être clairement et complètement justifiée.*

Soit $n \geqslant 1$ un entier. On appelle *point entier* de $\mathbb{R}^n$ un point dont toutes les coordonnées sont entières, c’est-à-dire un point de $\mathbb{Z}^n$. Si $\mathcal{K}$ est une partie de $\mathbb{R}^n$, on note $\mathring{\mathcal{K}}$ son intérieur. On appelle points entiers de $\mathcal{K}$ (resp. points entiers intérieurs) les points de $\mathcal{K} \cap \mathbb{Z}^n$ (resp. les points de $\mathring{\mathcal{K}} \cap \mathbb{Z}^n$). On note respectivement $\mathrm{Card}(\mathcal{K} \cap \mathbb{Z}^n)$ et $\mathrm{Card}(\mathring{\mathcal{K}} \cap \mathbb{Z}^n)$, le nombre (éventuellement infini) de points entiers de $\mathcal{K}$ et de son intérieur $\mathring{\mathcal{K}}$.

Soit $h_\beta$ l’homothétie de rapport $\beta \in \mathbb{R}$ (centrée en $0$), on note $\beta\mathcal{K} = h_\beta(\mathcal{K})$ l’image de $\mathcal{K}$ par $h_\beta$. Si $\tau_x$ est la translation de vecteur $x \in \mathbb{R}^n$, on note $\mathcal{K} - x = \tau_{-x}(\mathcal{K})$ l’image de $\mathcal{K}$ par $\tau_{-x}$.

Si $M = (m_{ij})$ est une matrice de $M_n(\mathbb{R})$, $m_{ij}$ est le coefficient de la $i$-ème ligne et de la $j$-ème colonne.

On note $(x_1 \mid \cdots \mid x_n)$ la matrice de $M_n(\mathbb{R})$ dont les colonnes sont les vecteurs $x_1, \ldots, x_n \in \mathbb{R}^n$.

On note $I_n$ la matrice identité de $M_n(\mathbb{R})$ et $E_{ij}$ la matrice de $M_n(\mathbb{R})$ dont tous les coefficients sont nuls sauf celui de la $i$-ème ligne et $j$-ème colonne qui vaut $1$.

On note $M_n(\mathbb{Z})$ l’ensemble des matrices de $M_n(\mathbb{R})$ dont tous les coefficients sont entiers.

On note $\lfloor a \rfloor$ la partie entière d’un réel $a$ : c’est le plus grand entier inférieur ou égal à $a$ ; et $\{a\} = a - \lfloor a \rfloor \in [0, 1[$ la partie fractionnaire de $a$. On note $\rfloor a \lfloor$ le plus grand entier strictement inférieur à $a$.

Pour des entiers $a_1, \ldots, a_k$ non tous nuls, on note $\mathrm{pgcd}(a_1, \ldots, a_k)$ le plus grand entier (strictement positif) qui divise tous les $a_i$.

## Première partie

**1.** Soit $M \in M_n(\mathbb{R})$ une matrice inversible et à coefficients entiers.

**1a.** Montrer que $M^{-1}$ est à coefficients rationnels.

**1b.** Montrer l’équivalence des propositions suivantes :

i) $M^{-1}$ est à coefficients entiers.

ii) $\mathrm{det}\, M$ vaut $1$ ou $-1$.

Dans la suite, on note $\mathrm{GL}_n(\mathbb{Z})$ l’ensemble des matrices carrées de taille $n$ à coefficients entiers et de déterminant $\pm 1$. C’est un sous-groupe de $\mathrm{GL}_n(\mathbb{R})$. On remarque que pour $i \neq j$ et $c \in \mathbb{Z}$, la matrice $I_n + c E_{ij}$ appartient à $\mathrm{GL}_n(\mathbb{Z})$.

**2.** Soit $M = (x_1 \mid \cdots \mid x_n) \in \mathrm{GL}_n(\mathbb{R})$.

**2a.** Montrer que $M \in \mathrm{GL}_n(\mathbb{Z})$ si et seulement si $M(\mathbb{Z}^n) = \mathbb{Z}^n$.

**2b.** Montrer l’équivalence des propositions suivantes :

i) $M \in \mathrm{GL}_n(\mathbb{Z})$.

ii) Les points entiers du parallélépipède $\displaystyle \mathcal{P} = \left\{ \sum_{i=1}^{n} t_i x_i \mid \forall i \in \{1, \ldots, n\},\; t_i \in [0, 1] \right\}$ sont exactement les $2^n$ points $\displaystyle \sum_{i=1}^{n} \varepsilon_i x_i$, où $\varepsilon_i \in \{0, 1\}$ pour tout $i \in \{1, \ldots, n\}$.

**3.** Pour tout $\alpha$ dans $\mathbb{R}$ et pour tous entiers $i$ et $j$ distincts compris entre $1$ et $n$, décrire l’effet sur une matrice carrée $M$ de taille $n$ de la multiplication à gauche par $I_n + \alpha E_{ij}$. Même question pour la multiplication à droite.

**4.** Soient $n \geqslant 2$ et $a_1, \ldots, a_n$ des entiers non tous nuls. Le but de cette question est de montrer qu’il existe une matrice de $M_n(\mathbb{Z})$ dont la première colonne est $(a_1, \ldots, a_n)$ et de déterminant le $\mathrm{pgcd}(a_1, \ldots, a_n)$. Pour cela on raisonne par récurrence sur $n$.

Soit $N \in M_{n-1}(\mathbb{Z})$ une matrice dont la première colonne est $(a_2, \ldots, a_n)$. Étant donnés $u, v \in \mathbb{Q}$, on considère la matrice

$$
M = \left(
\begin{array}{c|c}
a_1 \quad 0 \quad \cdots \quad 0 & u \\
\hline
N &
\begin{matrix}
va_2 \\
va_3 \\
\vdots \\
va_n
\end{matrix}
\end{array}
\right).
$$

**4a.** Exprimer $\mathrm{det}\, M$ en fonction de $\mathrm{det}\, N$, $u$ et $v$.

**4b.** On suppose que les $a_2, \ldots, a_n$ sont non tous nuls et que $\mathrm{det}\, N = \mathrm{pgcd}(a_2, \ldots, a_n)$. Montrer que l’on peut choisir $u, v$ de sorte que $M$ réponde à la question.

**4c.** Conclure la récurrence.

**5.** Soit $M \in M_n(\mathbb{Z})$, de déterminant non nul. On souhaite montrer qu’il existe une matrice $A$ dans $\mathrm{GL}_n(\mathbb{Z})$ telle que $MA$ soit triangulaire supérieure et en notant $MA = (c_{ij})$, on ait les inégalités $0 < c_{11}$ et $0 \leqslant c_{ij} < c_{ii}$ pour tous $i, j \in \{1, \ldots, n\}$ tels que $i < j$.

**5a.** On note $M = (x_1 \mid \cdots \mid x_n)$. Soient $x'_1, \ldots, x'_n$ les éléments de $\mathbb{Z}^{n-1}$ obtenus en prenant les $(n-1)$ dernières coordonnées de $x_1, \ldots, x_n$.

Montrer qu’il existe $a_1, \ldots, a_n$ dans $\mathbb{Q}$, non tous nuls, tels que $\displaystyle \sum_{i=1}^{n} a_i x'_i = 0$. Montrer que l’on peut choisir les $a_i$ entiers et premiers entre eux dans leur ensemble.

**5b.** Montrer qu’il existe une matrice $A_1$ dans $\mathrm{GL}_n(\mathbb{Z})$ telle que la première colonne de $\tilde{C} = MA_1$ ait tout ses coefficients $\tilde{c}_{i1}$ nuls sauf le premier $\tilde{c}_{11}$ que l’on peut prendre strictement positif.

**5c.** En considérant pour tout $j = 2, \ldots, n$ la division euclidienne $\tilde{c}_{1j} = q_j \tilde{c}_{11} + r_j$, $0 \leqslant r_j < \tilde{c}_{11}$, montrer que l’on peut supposer $\tilde{c}_{11} > \tilde{c}_{1j}$, quitte à changer $A_1$.

**5d.** Conclure par récurrence.

**6.** Soit $M \in M_n(\mathbb{Z})$, de déterminant non nul. Montrer qu’il existe une matrice $A$ dans $\mathrm{GL}_n(\mathbb{Z})$ telle que $AM$ soit triangulaire inférieure et en notant $AM = (c_{ij})$, on ait l’inégalité $0 \leqslant c_{ij} < c_{jj}$ pour tous $i, j \in \{1, \ldots, n\}$ tels que $j < i$.

## Deuxième partie

Soient $s_0, s_1, \ldots, s_n$ des points de $\mathbb{R}^n$ tels que les vecteurs $s_1 - s_0$, $s_2 - s_0$, $\ldots$, $s_n - s_0$ soient linéairement indépendants. On appelle *simplexe de sommets* $s_0, s_1, \ldots, s_n$ l’ensemble :

$$
\begin{aligned}
\mathcal{S}
&= \left\{ \sum_{i=0}^{n} t_i s_i \mid \forall i = 0, \ldots, n,\; t_i \geqslant 0,\; \sum_{i=0}^{n} t_i = 1 \right\} \\
&= \left\{ s_0 + \sum_{i=1}^{n} t_i (s_i - s_0) \mid \forall i = 1, \ldots, n,\; t_i \geqslant 0,\; \sum_{i=1}^{n} t_i \leqslant 1 \right\}.
\end{aligned}
$$

Si de plus les $s_i$ sont tous des points entiers, on dit que $\mathcal{S}$ est un simplexe entier.

On définit le volume du simplexe $\mathcal{S}$ de sommets $s_0, s_1, \ldots, s_n$ par

$$
\mathrm{Vol}(\mathcal{S}) := \frac{1}{n!} \bigl| \mathrm{det}(s_1 - s_0,\, s_2 - s_0,\, \ldots,\, s_n - s_0) \bigr|.
$$

**7.** Soit $\mathcal{S}$ le simplexe de sommets $s_0, s_1, \ldots, s_n$.

**7a.** Montrer $\mathcal{S}$ est un compact convexe de $\mathbb{R}^n$.

**7b.** Montrer que

$$
\mathring{\mathcal{S}} = \left\{ \sum_{i=0}^{n} t_i s_i \mid \forall i = 0, \ldots, n,\; t_i > 0,\; \sum_{i=0}^{n} t_i = 1 \right\}.
$$

En déduire que si $0 \in \mathring{\mathcal{S}}$, alors, pour tout $\lambda \in [0, 1[$, $\lambda \mathcal{S} \subset \mathring{\mathcal{S}}$.

**7c.** Pour $i = 0, \ldots, n$, on note $\hat{s}_i = (1, s_i)$ le point de $\mathbb{R}^{n+1}$ dont les coordonnées sont $1$ suivi des coordonnées de $s_i$. Exprimer $\bigl| \mathrm{det}(\hat{s}_0, \hat{s}_1, \ldots, \hat{s}_n) \bigr|$ en fonction de $\mathrm{Vol}(\mathcal{S})$.

En déduire que le volume d’un simplexe ne dépend pas de l’ordre des sommets.

**8.** Soit $V \geqslant 0$ un réel.

**8a.** Donner un exemple de simplexe entier de $\mathbb{R}^2$, de volume supérieur ou égal à $V$, et n’ayant aucun point intérieur entier.

**8b.** Donner un exemple de simplexe entier de $\mathbb{R}^3$, de volume supérieur ou égal à $V$, et dont les seuls points entiers sont les sommets.

**9.** Soit $\mathcal{K}$ un compact convexe de $\mathbb{R}^n$ tel que $0 \in \mathring{\mathcal{K}}$.

**9a.** Montrer que l’ensemble des $\lambda \geqslant 0$ tels que $-\lambda \mathcal{K} \subset \mathcal{K}$ est un intervalle.

On note

$$
a(\mathcal{K}) = \sup\{\lambda \geqslant 0 \mid -\lambda \mathcal{K} \subset \mathcal{K}\}.
$$

**9b.** Montrer que $a(\mathcal{K}) < \infty$ et que $a(\mathcal{K}) = \max\{\lambda \geqslant 0 \mid -\lambda \mathcal{K} \subset \mathcal{K}\}$.

**9c.** Montrer que $0 < a(\mathcal{K}) \leqslant 1$.

En déduire que $a(\mathcal{K}) = 1$ si et seulement si $\mathcal{K}$ est symétrique par rapport à $0$.

On admet le résultat suivant que l’on pourra utiliser sans démonstration pour la suite de cette partie.

**Théorème 1.** *Soit $\mathcal{S}$ un simplexe de $\mathbb{R}^n$ et $k$ un entier. Si $\mathrm{Vol}(\mathcal{S}) \geqslant k$, il existe $k+1$ points distincts $v_0, \ldots, v_k$ de $\mathcal{S}$ tels que $v_i - v_j \in \mathbb{Z}^n$ quels que soient $i$ et $j$ entre $0$ et $k$.*

**10.** Dans toute cette question, $\mathcal{S}$ est un simplexe de $\mathbb{R}^n$ tel que $0 \in \mathring{\mathcal{S}}$. On veut montrer que

$$
\mathrm{Card}\bigl(\mathring{\mathcal{S}} \cap \mathbb{Z}^n\bigr) \geqslant 2 \left\lfloor \mathrm{Vol}(\mathcal{S}) \left( \frac{a(\mathcal{S})}{a(\mathcal{S})+1} \right)^{\!n} \right\rfloor + 1.
$$

On pose alors $a = a(\mathcal{S})$, et $\displaystyle k = \left\lfloor \mathrm{Vol}(\mathcal{S}) \left( \frac{a}{a+1} \right)^{\!n} \right\rfloor$.

**10a.** Exprimer, pour $\beta \in \mathbb{R}^{*}$ et $x \in \mathbb{R}^n$, $\mathrm{Vol}(\beta \mathcal{S})$ et $\mathrm{Vol}(\mathcal{S} - x)$.

Montrer que pour $\lambda \in [0, 1[$ suffisamment proche de $1$, $\displaystyle \mathrm{Vol}\left( \frac{\lambda a}{a+1} \mathcal{S} \right) > k$.

**10b.** Pour $\lambda$ comme dans la question précédente, soient $v_0, \ldots, v_k$ les $k+1$ points distincts dans $\dfrac{\lambda a}{a+1}\mathcal{S}$ vérifiant $v_i - v_j \in \mathbb{Z}^n$ pour tout $i, j$ dont l’existence est assurée par le Théorème 1. Montrer que les points $v_i - v_j$ sont dans $\lambda \mathcal{S}$. En déduire que les $v_i - v_j$ sont dans $\mathring{\mathcal{S}}$.

**10c.** Montrer qu’il existe un indice $j \in \{0, \ldots, k\}$ tels que les $(2k+1)$ points $0$, $\pm(v_i - v_j)$, pour $i \in \{0, \ldots, k\} \setminus \{j\}$ soient distincts. En déduire l’énoncé de la question 10, puis que

$$
\mathrm{Card}\bigl(\mathring{\mathcal{S}} \cap \mathbb{Z}^n\bigr) \geqslant \mathrm{Vol}(\mathcal{S}) \left( \frac{a(\mathcal{S})}{2} \right)^{\!n}.
$$

## Troisième partie

On dit que deux simplexes $\mathcal{S}$ et $\mathcal{S}'$ de $\mathbb{R}^n$ sont *équivalents* s’il existe un ordre d’énumération des sommets $s_0, s_1, \ldots, s_n$ de $\mathcal{S}$, et $s'_0, s'_1, \ldots, s'_n$ de $\mathcal{S}'$, et une matrice $A$ de $\mathrm{GL}_n(\mathbb{Z})$ tels que $A(s_i - s_0) = s'_i - s'_0$ pour tout $i = 1, \ldots, n$.

**11.** Montrer que deux simplexes entiers $\mathcal{S}$ et $\mathcal{S}'$ sont équivalents si et seulement s’il existe une matrice $A \in \mathrm{GL}_n(\mathbb{Z})$ et un vecteur $b \in \mathbb{Z}^n$ tels que $\mathcal{S}' = A(\mathcal{S}) - b$.

**12.** Montrer que le volume, le nombre de points entiers et le nombre de points intérieurs entiers sont les mêmes pour deux simplexes entiers équivalents.

**13.** Montrer qu’un simplexe entier $\mathcal{S}$ est équivalent à un simplexe entier contenu dans le cube $[0,\, n!\, \mathrm{Vol}(\mathcal{S})]^n$.

*On pourra utiliser la question 6 pour une matrice $M$ bien choisie.*

On admet le résultat suivant que l’on pourra utiliser sans démonstration.

**Théorème 2.** *Pour tout entier strictement positif $k$, il existe une constante strictement positive $C(n, k)$ telle que pour tout simplexe entier $\mathcal{S}$ de $\mathbb{R}^n$ possédant exactement $k$ points intérieurs entiers, $\mathrm{Vol}(\mathcal{S}) \leqslant C(n, k)$.*

**14.** Déduire du Théorème 2 que pour tout entier strictement positif $k$, il n’existe à équivalence près qu’un nombre fini de simplexes entiers de $\mathbb{R}^n$ ayant exactement $k$ points intérieurs.

## Quatrième partie

Le but de cette partie, qui ne faisait pas partie du sujet du concours, est de démontrer les Théorèmes 1 et 2 énoncés et utilisés dans les deuxième et troisième parties.

**15.** Soit $\mathcal{S}$ un simplexe de $\mathbb{R}^n$ et $k$ un entier tel que $\mathrm{Vol}(\mathcal{S}) > k$.

**15a.** Montrer qu’il existe $x \in [0, 1[^n$ et $(k+1)$ éléments de $\mathbb{Z}^n$ $u_0, \ldots, u_k$ tels que $x \in \mathcal{S} - u_i$ pour $i = 0, \ldots, k$.

*On pourra étudier les ensembles $(u + [0, 1[^n) \cap \mathcal{S}$ quand $u$ décrit $\mathbb{Z}^n$ ; et admettre le fait – hors programme de CPGE – que le volume d’un simplexe est sa mesure de Lebesgue, qui est sous-additive.*

**15b.** En déduire l’existence des $(k+1)$ points $v_0, \ldots, v_k$ qui satisfont aux conditions du Théorème 1.

**15c.** Montrer le Théorème 1, c’est-à-dire qu’ici, on suppose seulement que $\mathrm{Vol}(\mathcal{S}) \geqslant k$.

**16.** Soient $t_1, \ldots, t_n$ des réels strictement positifs tels que $\displaystyle \sum_{i=1}^{n} t_i = 1$ et soit $N \geqslant n$ un entier. On souhaite montrer qu’il existe des entiers positifs ou nuls $p_1, \ldots, p_n$ et $q$ tels que

i) $1 \leqslant q \leqslant N^{n-1}$,

ii) $\displaystyle \sum_{i=1}^{n} p_i = q$,

iii) $\displaystyle \bigl| q t_1 - p_1 \bigr| \leqslant \frac{n}{N}$,

iv) pour tout $i = 2, \ldots, n$, $\displaystyle \bigl| q t_i - p_i \bigr| \leqslant \frac{1}{N}$.

**16a.** En considérant les vecteurs de coordonnées $\bigl(\{kt_2\}, \ldots, \{kt_n\}\bigr) \in [0, 1[^{n-1}$ quand $k$ décrit $\{0, \ldots, N^{n-1}\}$, montrer qu’il existe des entiers $p_2, \ldots, p_n$, $q \geqslant 0$ vérifiant les conditions i) et iv).

**16b.** Conclure.

**17.** Le but de cette question est de montrer que quels que soient les entiers strictement positifs $n$ et $k$, il existe une constante $\alpha(k, n) \in \, ]0, 1[$ telle que, si $t_1, \ldots, t_n$ sont des réels strictement positifs vérifiant $\displaystyle 1 > \sum_{i=1}^{n} t_i > 1 - \alpha(k, n)$, alors il existe des entiers positifs ou nuls $p_1, \ldots, p_n \geqslant 0$ et $q$ tels que

$$
\sum_{i=1}^{n} p_i = q > 0,
\quad
\text{et pour tout } i = 1, \ldots, n,
\quad
(kq + 1) t_i > k p_i.
$$

On procède par récurrence sur $n$.

**17a.** Traiter le cas $n = 1$ en montrant que la constante $\displaystyle \alpha(k, 1) = \frac{1}{k+1}$ convient.

On suppose l’énoncé vrai jusqu’au rang $n - 1 \geqslant 1$. En particulier, $\alpha(k, n-1) > 0$ est définie pour tout $k \geqslant 1$. On pose pour $k \geqslant 1$

$$
\alpha(k, n) = \frac{1}{4k N^{n-1}}
\quad \text{où} \quad
N = 1 + \max\left( \frac{4k}{\alpha(k, n-1)},\; 2kn(n+1) \right).
$$

On se donne $t_1 \geqslant t_2 \geqslant \cdots \geqslant t_n > 0$, et on suppose que $\displaystyle \sum_{i=1}^{n} t_i = 1 - \alpha$ avec $0 < \alpha < \alpha(k, n)$.

**17b.** Si $t_n < \alpha(k, n-1) - \alpha$, établir l’énoncé au rang $n$.

**17c.** Si $t_n \geqslant \alpha(k, n-1) - \alpha$, appliquer le résultat de la question 16 aux $\dfrac{t_i}{1-\alpha}$, $i = 1, \ldots, n$.

Avec ses notations, montrer que

$$
\alpha(k, n) < \min\left( \frac{1}{n+1},\; \frac{1}{2}\alpha(k, n-1) \right)
\quad \text{et} \quad
1 - qk \frac{\alpha}{1-\alpha} \geqslant \frac{1}{2}.
$$

Conclure en distinguant les cas $i \geqslant 2$ et $i = 1$.

**18.** Soit $\mathcal{S}$ un simplexe entier de $\mathbb{R}^n$ de sommets $0, s_1, \ldots, s_n$ ayant exactement $k$ points intérieurs entiers et soit $\displaystyle x = \sum_{i=1}^{n} t_i s_i$ un point entier intérieur de $\mathcal{S}$.

**18a.** Montrer que $\displaystyle \sum_{i=1}^{n} t_i \leqslant 1 - \alpha(k, n)$. (On pourra raisonner par l’absurde et construire alors $k+1$ points entiers distincts intérieurs à $\mathcal{S}$).

**18b.** Montrer que $\displaystyle \frac{\alpha(k, n)}{1 - \alpha(k, n)} \, x \in (\mathcal{S} - x)$.

**18c.** En déduire que $\displaystyle a(\mathcal{S} - x) \geqslant \frac{\alpha(k, n)}{1 - \alpha(k, n)}$.

**19.** Conclure la preuve du Théorème 2.