Exo Maths X MP #53 - Loi uniforme impossible

Exercice d'oral de maths de Polytechnique filière MP tombé en 2018.

Soit $p$ un nombre premier. Montrer qu'on ne peut pas avoir 2 variables aléatoires $X$ et $Y$ à valeurs dans $\mathbb{N}$, indépendantes, non constantes presque sûrement, telles que $X+Y$ suive une loi uniforme sur $[[0,p-1]]$.

Merci à Milan Arrouas d'avoir partagé l'exercice qu'il a eu à l'oral de l'X ! Pour partager les tiens, contacte Lucas Willems.

Correction

Bravo à Enzo Tavera (MP, Mariette) et Nino Emery (MP*, Faidherbe) d'avoir réussi à résoudre cet exercice et merci à eux d'avoir rédigé leur correction !

Rejoins le groupe Facebook Exos Maths X MP pour te préparer à l'X.

Soit $p$ un nombre premier. Supposons l'existence de variables aléatoires $X$ et $Y$ à valeurs dans $\mathbb{N}$, indépendantes, presque sûrement non constantes, telles que $X+Y$ suit une loi $\mathcal{U}$ uniforme sur $[[0,p-1]]$.

Nous en déduisons cette égalité sur les fonctions génératrices :

Par définition, $G_{X+Y}$, $G_X$, $G_Y$ sont trois séries entières, mais puisque $P(X+Y\ge p)=0$ et donc que $P(X\ge p)=P(X\ge p)=0$, on peut les identifier à trois polynômes :

• $G_{X+Y}={\sum }_{k=0}^{p-1}P(X+Y=k)X^k=\frac{1}{p}{\sum }_{k=0}^{p-1}{X}^k$,
• $G_X={\sum }_{k=0}^{r}P(X=k)X^k$ avec $1\le r<p$ et $P(X=r)>0$,
• $G_Y={\sum }_{k=0}^{s}P(Y=k)X^k$ avec $1\le s<p$ et $P(Y=s)>0$.

On introduit les polynômes unitaires associés :

• $H_{X+Y}=p{G}_{X+Y}={\sum }_{k=0}^{p-1}{X}^k$,
• $H_X=\frac{1}{P(X=r)}{G}_X={\sum }_{k=0}^r{a}_k{X}^k$,
• $H_Y=\frac{1}{P(Y=s)}{G}_Y={\sum }_{k=0}^s{b}_k{X}^k$.

On a alors $\frac{1}{p}{H}_{X+Y}=P(X=r)P(Y=s)H_X{H}_Y$. En identifiant les coefficients dominants, on a : $\frac{1}{p}=P(X=r)P(Y=s)$. Et donc :

On suppose sans perte de généralité que $r\le s$.

Étape 1 : $\forall k\in [[0,r]],a_k=a_{r-k}$ et $\forall k\in [[0,s]],b_k=b_{s-k}$

$\forall t\in \mathbb{R}\backslash \{1\},{\sum }_{k=0}^{p-1}{t}^k=\frac{1-t^p}{1-t}$. Ainsi, les racines de $H_{X+Y}$ sont dans ${\mathbb{U}}_p\backslash \{1\}$ et donc les racines de $H_X$ et $H_Y$ sont aussi dans ${\mathbb{U}}_p\backslash \{1\}$.

$H_X$ est à coefficients réels, donc $a\in Z(H_X)⟺\bar{a}\in Z(H_X)$. Si $a\in Z(H_X)$, alors $\bar{a}=\frac{|a{|}^2}{a}=\frac{1}{a}$. Ainsi $a\in Z(H_X)⟺\frac{1}{a}\in Z(H_X)$.

Notons $a_1,...,a_r$ les racines de $H_X$. On a d'une part :

et d'autre part :

On remarque alors que :

En évaluant en $t=1$, on en déduit que $\frac{(-1{)}^r}{a_1...a_r}=1$, et donc :

Or, $\forall t\in {\mathbb{R}}^{\ast },t^r{H}_X\left(\frac{1}{t}\right)={\sum }_{k=0}^r{a}_{r-k}{t}^k$. L'égalité étant vraie pour une infinité de $t$, on peut identifier les coefficients et donc :

Le même résultat tient pour les coefficients de $H_Y$.

Étape 2 : $\forall k\in [[1,r]],a_k{b}_k=0$

En identifiant les coefficients de degré $r$ dans $G_{X+Y}$ et dans $G_X{G}_Y$, on en déduit que $1={\sum }_{k=0}^r{a}_{r-k}{b}_k$. D'après l'étape 1, $1={\sum }_{k=0}^r{a}_k{b}_k$. Or, $a_0=a_r=1$ et $b_0=b_s=1$. Donc $1=1+{\sum }_{k=1}^r{a}_k{b}_k$. Donc ${\sum }_{k=1}^r{a}_k{b}_k=0$. Or, tous les termes de la somme sont positifs, donc tous les termes sont nuls, i.e. $\forall k\in [[1,r]],a_k{b}_k=0$.

Étape 3 : $\forall k\in [[0,r]],a_k\in \{0,1\}$ et $\forall k\in [[0,s]],a_s\in \{0,1\}$

Pour simplifier la rédaction ici, on note $H_X={\sum }_{k=0}^s{a}_k{X}^k$ avec $a_0,...,a_r$ les coefficients définis précédemment et $a_{r+1}=0,...,a_s=0$.

Montrons par récurrence que $\forall k\in [[0,s]],a_k,b_k\in \{0,1\}$

Initialisation : D'après l'étape 1, $a_0=a_r=1$ et $b_0=b_s=1$. Donc $a_0,b_0\in \{0,1\}$.

Hérédité : Soit $1\le k\le s$. On suppose que $\forall i\in [[0,k-1]],a_i\in \{0,1\}$. En identifiant les coefficients de degré $k$ de $H_X{H}_Y$ et $H_{X+Y}$, on en déduit que $a_k+b_k+{\sum }_{i=1}^k{a}_i{b}_{k-i}=1$ puisque $a_0=b_0=1$.

Par hypothèse de récurrence, $\forall i\in [[1,k]],a_i{b}_{k-i}\in \{0,1\}$. Or, ${\sum }_{i=1}^k{a}_i{b}_{k-i}\le 1$. Donc ${\sum }_{i=1}^k{a}_i{b}_{k-i}\in \{0,1\}$. On a donc 2 cas :

• Si ${\sum }_{i=1}^k{a}_i{b}_{k-i}=0$, alors $a_k+b_k=1$. De plus, $a_k{b}_k=0$ d'après l'étape 2. Donc $a_k,b_k\in \{0,1\}$.
• Si ${\sum }_{i=1}^k{a}_i{b}_{k-i}=1$, alors $a_k+b_k=0$ et donc $a_k=b_k=0$.

Donc $a_k,b_k\in \{0,1\}$.

Étape 4 : Absurdité

On remarque que :

• $H_{X+Y}(1)=p$.
• $H_X(1)={\sum }_{k=0}^r{a}_k$. Or, $\forall k\in [[1,r]],a_k\in \{0,1\}$, et $a_0=a_r=1$. Donc $H_X(1)\in [[2,+\infty [[$.
• $H_Y(1)={\sum }_{k=0}^s{b}_k$. Or, $\forall k\in [[1,s]],b_k\in \{0,1\}$, et $b_0=b_s=1$. Donc $H_Y(1)\in [[2,+\infty [[$.

Ce qui est absurde car $p$ est premier.