Shortlist 2018, A6¶

Domaine : Algèbre · Difficulté : ★★★★☆ · Proposé par : Brazil

Concepts : Partie entière et majorations · Polynômes : racines, relations de Viète, factorisation

Solution officielle : Shortlist officielle 2018 (avec solutions), p. 20 (page 22 du PDF)

Énoncé¶

Let $m, n \geq 2$ be integers. Let $f(x_1, \ldots, x_n)$ be a polynomial with real coefficients such that

\[f(x_1, \ldots, x_n) = \left\lfloor \frac{x_1 + \cdots + x_n}{m} \right\rfloor \quad \text{for every } x_1, \ldots, x_n \in \{0, 1, \ldots, m-1\}.\]

Prove that the total degree of $f$ is at least $n$.

Indices : les idées clés

Se ramener à une variable : un lemme montre que si $F(x_1, \ldots, x_n) = G(x_1 + \cdots + x_n)$ sur une grille assez grande, alors $\deg F \geq \deg G$.
Différences finies : l'opérateur $\Delta p(x) = p(x+1) - p(x)$ fait baisser le degré d'exactement $1$, ce qui permet une récurrence sur $\deg G$.
Partie entière et majorations : le polynôme $g$ qui interpole $\lfloor x/m \rfloor$ vérifie $g(x+m) = g(x) + 1$ aux points de la grille.
Polynômes : racines, relations de Viète, factorisation : $h(x) = g(x+m) - g(x) - 1$ est non nul et a au moins $(n-1)(m-1)$ racines, d'où la borne sur son degré.

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2018 (une solution et trois remarques).

Solution¶

On ramène le problème à une question à une seule variable grâce au lemme suivant.

Lemme. Soient $a_1, \ldots, a_n$ des entiers positifs ou nuls et $G(x)$ un polynôme non nul avec $\deg G \leq a_1 + \cdots + a_n$. Supposons qu'un polynôme $F(x_1, \ldots, x_n)$ vérifie

\[F(x_1, \ldots, x_n) = G(x_1 + \cdots + x_n) \quad \text{pour } (x_1, \ldots, x_n) \in \{0, 1, \ldots, a_1\} \times \cdots \times \{0, 1, \ldots, a_n\}.\]

Alors $F$ n'est pas le polynôme nul, et $\deg F \geq \deg G$.

Pour prouver le lemme, on utilise les différences finies (« différences avant ») des polynômes. Pour un polynôme $p(x)$ d'une variable, on pose $(\Delta p)(x) = p(x+1) - p(x)$. Il est bien connu que, si $p$ n'est pas constant, $\deg \Delta p = \deg p - 1$. Pour un polynôme $p(x_1, \ldots, x_n)$ de $n$ variables et $1 \leq k \leq n$, on pose

\[(\Delta_k p)(x_1, \ldots, x_n) = p(x_1, \ldots, x_{k-1}, x_k + 1, x_{k+1}, \ldots, x_n) - p(x_1, \ldots, x_n).\]

Il est aussi bien connu que $\Delta_k p$ est soit le polynôme nul, soit de degré $\deg(\Delta_k p) \leq \deg p - 1$.

Preuve du lemme. Par récurrence sur le degré de $G$. Si $G$ est constant, $F(0, \ldots, 0) = G(0) \neq 0$, donc $F$ n'est pas le polynôme nul.

Supposons $\deg G \geq 1$ et le lemme vrai pour les degrés inférieurs. Comme $a_1 + \cdots + a_n \geq \deg G > 0$, l'un au moins des $a_i$ est strictement positif ; supposons sans perte de généralité $a_1 \geq 1$. Considérons les polynômes $F_1 = \Delta_1 F$ et $G_1 = \Delta G$. Sur la grille $\{0, \ldots, a_1 - 1\} \times \{0, \ldots, a_2\} \times \cdots \times \{0, \ldots, a_n\}$, on a

\[F_1(x_1, \ldots, x_n) = F(x_1 + 1, x_2, \ldots, x_n) - F(x_1, x_2, \ldots, x_n) = G(x_1 + \cdots + x_n + 1) - G(x_1 + \cdots + x_n) = G_1(x_1 + \cdots + x_n).\]

Comme $G$ n'est pas constant, $\deg G_1 = \deg G - 1 \leq (a_1 - 1) + a_2 + \cdots + a_n$. On peut donc appliquer l'hypothèse de récurrence à $F_1$ et $G_1$ : $F_1$ n'est pas le polynôme nul et $\deg F_1 \geq \deg G_1$. Ainsi $\deg F \geq \deg F_1 + 1 \geq \deg G_1 + 1 = \deg G$. $\square$

Preuve de l'énoncé. Soit $g(x)$ l'unique polynôme tel que $g(x) = \left\lfloor \frac{x}{m} \right\rfloor$ pour $x \in \{0, 1, \ldots, n(m-1)\}$ et $\deg g \leq n(m-1)$. On prescrit exactement $n(m-1) + 1$ valeurs de $g$, donc $g$ existe et est unique (interpolation de Lagrange). De plus, les contraintes $g(0) = g(1) = 0$ et $g(m) = 1$ imposent $\deg g \geq 2$.

En appliquant le lemme avec $a_1 = \cdots = a_n = m - 1$ aux polynômes $f$ et $g$, on obtient $\deg f \geq \deg g$. Il suffit donc de minorer convenablement $\deg g$.

Considérons le polynôme $h(x) = g(x + m) - g(x) - 1$. Le degré de $g(x + m) - g(x)$ vaut $\deg g - 1 \geq 1$, donc $\deg h = \deg g - 1 \geq 1$, et $h$ n'est pas le polynôme nul. D'autre part, comme $\left\lfloor \frac{x+m}{m} \right\rfloor = \left\lfloor \frac{x}{m} \right\rfloor + 1$ (partie entière), $h$ s'annule aux points $0, 1, \ldots, n(m-1) - m$ : $h$ a donc au moins $(n-1)(m-1)$ racines. Par conséquent,

\[\deg f \geq \deg g = \deg h + 1 \geq (n-1)(m-1) + 1 \geq n. \qquad \blacksquare\]

Remarques¶

Remarque 1. Dans le lemme, il y a égalité pour le choix $F(x_1, \ldots, x_n) = G(x_1 + \cdots + x_n)$ : le lemme transforme donc bien le problème en une question équivalente à une variable.

Remarque 2 (une meilleure borne sur $\deg g$). Si $m \geq 3$, on peut remplacer $h$ par $\Delta g$. On a

\[(\Delta g)(x) = \begin{cases} 1 & \text{si } x \equiv -1 \pmod m, \\ 0 & \text{sinon,} \end{cases} \qquad \text{pour } x = 0, 1, \ldots, n(m-1) - 1.\]

Donc $\Delta g$ s'annule en tous les entiers $x$ tels que $0 \leq x < n(m-1)$ et $x \not\equiv -1 \pmod m$, ce qui donne $\deg g \geq \frac{(m-1)^2 n}{m} + 1$.

Si $m$ est pair, cette borne peut être améliorée en $n(m-1)$. Pour $0 \leq N < n(m-1)$, la $(N+1)$-ième différence finie en $0$ vaut

\[\left(\Delta^{N+1} g\right)(0) = \sum_{k=0}^{N} (-1)^{N-k} \binom{N}{k} (\Delta g)(k) = \sum_{\substack{0 \leq k \leq N \\ k \equiv -1 \ (\mathrm{mod}\ m)}} (-1)^{N-k} \binom{N}{k}. \tag{$*$}\]

Comme $m$ est pair, tous les signes de la dernière somme sont égaux ; avec $N = n(m-1) - 1$, on obtient $\Delta^{n(m-1)} g(0) \neq 0$, ce qui montre que $\deg g \geq n(m-1)$.

En revanche, il existe une infinité de cas où tous les termes de $(*)$ se compensent, par exemple si $m$ est un diviseur impair de $n + 1$. Dans ces cas, $\deg f$ peut être inférieur à $n(m-1)$.

Remarque 3 (lien avec la borne d'Alon–Füredi). Le lemme est très proche de la borne d'Alon–Füredi : soient $S_1, \ldots, S_n$ des ensembles finis non vides d'un corps, et $P(x_1, \ldots, x_n)$ un polynôme qui s'annule en tous les points de la grille $S_1 \times \cdots \times S_n$ sauf un. Alors $\deg P \geq \sum_{i=1}^{n} \left(|S_i| - 1\right)$. (Une application célèbre de cette borne est le problème 6 de l'OIM 2007 ; depuis, ce résultat est devenu populaire et fait partie de la préparation de nombreuses équipes.)

On peut remplacer la preuve du lemme par une application de cette borne. Soient $d = \deg G$ et $G_0$ l'unique polynôme tel que $G_0(x) = G(x)$ pour $x \in \{0, 1, \ldots, d-1\}$ et $\deg G_0 < d$. Les polynômes $G_0$ et $G$ sont différents (ils n'ont pas le même degré) et prennent les mêmes valeurs en $0, 1, \ldots, d-1$ ; cela impose $G_0(d) \neq G(d)$. Choisissons des entiers positifs ou nuls $b_1 \leq a_1, \ldots, b_n \leq a_n$ avec $b_1 + \cdots + b_n = d$, et considérons

\[H(x_1, \ldots, x_n) = F(x_1, \ldots, x_n) - G_0(x_1 + \cdots + x_n)\]

sur la grille $\{0, 1, \ldots, b_1\} \times \cdots \times \{0, 1, \ldots, b_n\}$. Au point $(b_1, \ldots, b_n)$, $H(b_1, \ldots, b_n) = G(d) - G_0(d) \neq 0$. En tous les autres points de la grille, la somme des coordonnées est au plus $d - 1$, $F = G$ et donc $H = G - G_0 = 0$. Par la borne d'Alon–Füredi, $\deg H \geq b_1 + \cdots + b_n = d$. Comme $\deg G_0 < d$, on en déduit $\deg F = \deg(H + G_0) = \deg H \geq d = \deg G$.