Shortlist 2020, A2¶
Domaine : Algèbre · Difficulté : ★☆☆☆☆ · Proposé par : Venezuela
Concepts : Polynômes : racines, relations de Viète, factorisation
Solution officielle : Shortlist officielle 2020 (avec solutions), p. 16 (page 18 du PDF)
Énoncé¶
Let \(\mathcal{A}\) denote the set of all polynomials in three variables \(x, y, z\) with integer coefficients. Let \(\mathcal{B}\) denote the subset of \(\mathcal{A}\) formed by all polynomials which can be expressed as
with \(P, Q, R \in \mathcal{A}\). Find the smallest non-negative integer \(n\) such that \(x^i y^j z^k \in \mathcal{B}\) for all non-negative integers \(i, j, k\) satisfying \(i + j + k \geq n\).
Indices : les idées clés
- Fonctions symétriques élémentaires : on pose \(p = x+y+z\), \(q = xy+yz+zx\), \(r = xyz\) ; alors \(\mathcal{B}\) est l'ensemble des \(pP + qQ + rR\), stable par somme et par multiplication par un élément de \(\mathcal{A}\).
- Relations de Viète : \(x\) est racine de \((t-x)(t-y)(t-z) = t^3 - pt^2 + qt - r\), d'où \(x^3 \in \mathcal{B}\).
- Identification des coefficients : pour montrer que \(x^2y \notin \mathcal{B}\), on ne garde que les termes de degré \(3\) et on compare les coefficients des deux membres.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2020 (une solution et deux remarques).
Réponse : \(n = 4\).
Solution¶
Notons \(p = x+y+z\), \(q = xy+yz+zx\) et \(r = xyz\). Par définition, \(\mathcal{B} = \{pP + qQ + rR : P, Q, R \in \mathcal{A}\}\) ; en particulier, tout multiple (dans \(\mathcal{A}\)) d'un élément de \(\mathcal{B}\) est encore dans \(\mathcal{B}\).
Tout monôme de degré au moins \(4\) est dans \(\mathcal{B}\) (donc \(n \leq 4\)). Soit \(f = x^i y^j z^k\) avec \(i + j + k \geq 4\) ; on suppose \(i \geq j \geq k\), les autres cas étant analogues. D'après les relations de Viète, \(x\), \(y\), \(z\) sont les racines de \(t^3 - pt^2 + qt - r\) ; en remplaçant \(t\) par \(x\) :
donc \(x^3 = p\,x^2 - q\,x + r \in \mathcal{B}\). Ensuite
- Si \(k \geq 1\), alors \(r = xyz\) divise \(f\), donc \(f \in \mathcal{B}\).
- Si \(k = 0\) et \(j \geq 2\), alors \(x^2y^2\) divise \(f\), donc \(f \in \mathcal{B}\).
- Si \(k = 0\) et \(j \leq 1\), alors \(i \geq 3\), donc \(x^3\) divise \(f\) et \(f \in \mathcal{B}\).
Le monôme \(x^2y\) n'est pas dans \(\mathcal{B}\) (donc \(n \geq 4\)). Supposons au contraire que
pour certains \(P, Q, R \in \mathcal{A}\). Comparons les termes de degré \(3\) ; seuls y contribuent la partie de degré \(2\) de \(P\), la partie de degré \(1\) de \(Q\) et le terme constant de \(R\). Si \(P\) contient le monôme \(x^2\) avec un coefficient non nul, alors \(pP + qQ + rR\) contient \(x^3\) avec ce même coefficient (chaque monôme de \(q\) et de \(r\) fait intervenir au moins deux variables, et dans \(pP\) le monôme \(x^3\) ne provient que de \(x \cdot x^2\)) ; c'est impossible puisque le membre de gauche ne contient pas \(x^3\). Ainsi \(P\) ne contient ni \(x^2\), ni \(y^2\), ni \(z^2\), et l'on peut écrire, pour les termes de degré \(3\),
où \(a, b, c\) ; \(d, e, f\) ; \(g\) sont respectivement les coefficients de \(xy, yz, zx\) dans \(P\), de \(x, y, z\) dans \(Q\), et de \(1\) dans \(R\) (les autres coefficients n'influent pas sur les termes de degré \(3\)).
En comparant les coefficients de \(xy^2\), on obtient \(a + e = 0\), soit \(e = -a\). De même, avec \(y^2z\), \(yz^2\), \(z^2x\) et \(x^2z\) : \(e = -b\), \(f = -b\), \(f = -c\), \(d = -c\). Donc \(a = b = c\) et \(d = e = f = -a\). Mais alors le coefficient de \(x^2y\) dans le membre de droite vaut \(a + d = 0 \neq 1\) : contradiction.
Le plus petit entier cherché est donc \(n = 4\). \(\blacksquare\)
Remarques¶
Remarque 1 (généralisation à \(n\) variables). Appelons gentil un polynôme \(f(x_1, \ldots, x_n)\) à coefficients entiers, symétrique et de terme constant nul, et notons \(I\) l'ensemble des polynômes de la forme \(p_1q_1 + \cdots + p_mq_m\), où les \(p_i\) sont gentils et les \(q_i\) quelconques à coefficients entiers. Le plus petit \(N\) tel que tout monôme de degré au moins \(N\) soit dans \(I\) est \(N = \frac{n(n-1)}{2} + 1\).
- Minoration. Le polynôme \(F = x_2 x_3^2 x_4^3 \cdots x_n^{n-1}\) n'est pas dans \(I\). Si \(F = \sum p_i q_i\), on peut supposer tous les \(p_i, q_i\) homogènes avec \(\deg p_i > 0\) et \(\deg p_i + \deg q_i = \frac{n(n-1)}{2}\). On considère la somme alternée \(\sum_\pi \operatorname{sign}(\pi) F(x_{\pi_1}, \ldots, x_{\pi_n}) = \sum_i p_i \sum_\pi \operatorname{sign}(\pi)\, q_i(x_{\pi_1}, \ldots, x_{\pi_n})\). Comme \(\deg q_i < \frac{n(n-1)}{2}\), chaque monôme de \(q_i\) a deux variables de même exposant ; les termes correspondant à deux permutations qui diffèrent par la transposition de ces deux variables s'annulent, donc le membre de droite est nul. Or le membre de gauche est un polynôme non nul : contradiction.
- Majoration. On montre par récurrence sur \(n\) que tout monôme \(h = x_1^{c_1} \cdots x_n^{c_n}\) de degré \(\frac{n(n-1)}{2} + 1\) est dans \(I\) (avec des \(p_i, q_i\) homogènes), par une récurrence interne sur le nombre \(S\) d'exposants nuls. Si \(S = 0\), \(h\) est divisible par le polynôme gentil \(x_1 \cdots x_n\). Sinon, on écrit \(h = x_1 \cdots x_T\, g(x_1, \ldots, x_{n-1})\) avec \(T = n - S\) et \(\deg g \geq \frac{(n-1)(n-2)}{2} + 1\) ; on applique l'hypothèse de récurrence à \(g = \sum p_i q_i\) en \(n-1\) variables, on relève chaque \(p_i\) en un polynôme gentil \(P_i\) en \(n\) variables avec \(p_i - P_i = x_n g_i\), et on obtient \(h = (x_1 \cdots x_T x_n) \sum g_i q_i + \sum P_i (x_1 \cdots x_T q_i)\), où le premier terme est dans \(I\) par l'hypothèse de récurrence interne.
Remarque 2. Ces arguments valent aussi pour des polynômes à coefficients réels. Avec des coefficients entiers, on peut prouver plus simplement que \(x^2y \notin \mathcal{B}\) : pour tout \(f \in \mathcal{B}\), la somme des coefficients de \(x^2y\), \(x^2z\), \(y^2x\), \(y^2z\), \(z^2x\), \(z^2y\) est paire. Un fait analogue vaut pour un nombre quelconque de variables et donne aussi la minoration \(N \geq \frac{n(n-1)}{2} + 1\) de la remarque 1.