Shortlist 2012, A7

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

Concepts : Polynômes : racines, relations de Viète, factorisation · Principe extrémal

Solution officielle : Shortlist officielle 2012 (avec solutions), p. 17 (page 17 du PDF)

Énoncé

We say that a function \(f : \mathbb{R}^k \to \mathbb{R}\) is a metapolynomial if, for some positive integers \(m\) and \(n\), it can be represented in the form

\[f(x_1, \ldots, x_k) = \max_{i = 1, \ldots, m} \; \min_{j = 1, \ldots, n} P_{i,j}(x_1, \ldots, x_k)\]

where \(P_{i,j}\) are multivariate polynomials. Prove that the product of two metapolynomials is also a metapolynomial.

Indices : les idées clés

• Échanger min et max : \(\min_i \max_j a_{i,j} = \max_{(j_1, \ldots, j_m)} \min_i a_{i,j_i}\), ce qui montre que les métapolynômes sont stables par max, min, opposé et somme.
• Parties positive et négative : \(f = f^+ - f^-\) avec \(f^\pm \in \mathcal{M}\), donc il suffit de traiter le produit de deux métapolynômes positifs.
• Une identité : \(u^+ v^+ = \max\{0, \min\{uv, u, v\}, \min\{uv, uv^2, u^2v\}, \min\{uv, u, u^2v\}, \min\{uv, uv^2, v\}\}\), vérifiée cas par cas, montre que \(P^+ Q^+\) est un métapolynôme pour des polynômes \(P\), \(Q\).

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2012 (une solution et une remarque).

Solution

On note \(f(x) = f(x_1, \ldots, x_k)\) pour \(x = (x_1, \ldots, x_k)\), et \([m] = \{1, 2, \ldots, m\}\).

Si un métapolynôme \(f(x)\) admet une représentation comme dans l'énoncé pour des entiers \(m\) et \(n\), on peut les remplacer par n'importe quels \(m' \geq m\) et \(n' \geq n\). Par exemple, pour remplacer \(m\) par \(m + 1\), il suffit de poser \(P_{m+1,j}(x) = P_{m,j}(x)\) et de remarquer que répéter des éléments d'un ensemble ne change ni son maximum ni son minimum. On peut donc supposer que deux métapolynômes sont définis avec les mêmes \(m\) et \(n\). Les lettres \(P\) et \(Q\) désignent toujours des polynômes.

Commençons par un lemme utile pour transformer les expressions de la forme \(\min \max f_{i,j}\) en expressions de la forme \(\max \min g_{i,j}\).

Lemme. Soient \(a_{i,j}\) des réels, pour \(i \in [m]\) et \(j \in [n]\). Alors

\[\min_{i \in [m]} \max_{j \in [n]} a_{i,j} = \max_{j_1, \ldots, j_m \in [n]} \; \min_{i \in [m]} a_{i,j_i},\]

où le maximum du membre de droite porte sur tous les vecteurs \((j_1, \ldots, j_m)\) avec \(j_1, \ldots, j_m \in [n]\).

Preuve. On peut supposer que, pour tout \(i\), \(a_{i,n} = \max\{a_{i,1}, \ldots, a_{i,n}\}\), et que \(a_{m,n} = \min\{a_{1,n}, \ldots, a_{m,n}\}\). Le membre de gauche vaut alors \(a_{m,n}\), et il faut prouver qu'il en va de même du membre de droite. Si \((j_1, j_2, \ldots, j_m) = (n, n, \ldots, n)\), alors \(\min\{a_{1,j_1}, \ldots, a_{m,j_m}\} = \min\{a_{1,n}, \ldots, a_{m,n}\} = a_{m,n}\), donc le membre de droite est au moins \(a_{m,n}\). Il reste l'inégalité inverse, qui équivaut à \(\min\{a_{1,j_1}, \ldots, a_{m,j_m}\} \leq a_{m,n}\) pour tout \((j_1, \ldots, j_m)\). C'est vrai, car \(\min\{a_{1,j_1}, \ldots, a_{m,j_m}\} \leq a_{m,j_m} \leq a_{m,n}\). \(\square\)

Il s'agit de montrer que la famille \(\mathcal{M}\) des métapolynômes est stable par multiplication, mais il est plus facile de prouver davantage : elle est aussi stable par addition, par maximum et par minimum.

Commençons par les maxima et les minima. Si \(f_1, \ldots, f_r\) sont des métapolynômes, définis avec les mêmes \(m\) et \(n\), alors

\[f = \max\{f_1, \ldots, f_r\} = \max\Big\{\max_{i \in [m]} \min_{j \in [n]} P^1_{i,j}, \ldots, \max_{i \in [m]} \min_{j \in [n]} P^r_{i,j}\Big\} = \max_{s \in [r], \, i \in [m]} \; \min_{j \in [n]} P^s_{i,j}.\]

Donc \(f = \max\{f_1, \ldots, f_r\}\) est un métapolynôme. Le même argument fonctionne pour les minima, mais il faut d'abord transformer \(\min \max\) en \(\max \min\), ce que permet le lemme.

Autre propriété utile : si \(f = \max \min P_{i,j}\) est un métapolynôme, alors \(-f\) aussi. En effet, \(-f = \min(-\min P_{i,j}) = \min \max (-P_{i,j})\). (Le livret écrit \(\min \max P_{i,j}\) ; il faut lire \(\min \max (-P_{i,j})\).)

Pour la stabilité par addition, soient \(f = \max \min P_{i,j}\) et \(g = \max \min Q_{i,j}\). Alors

\[\begin{aligned} f(x) + g(x) &= \max_{i \in [m]} \min_{j \in [n]} P_{i,j}(x) + \max_{i \in [m]} \min_{j \in [n]} Q_{i,j}(x) \\ &= \max_{i_1, i_2 \in [m]} \Big(\min_{j \in [n]} P_{i_1,j}(x) + \min_{j \in [n]} Q_{i_2,j}(x)\Big) = \max_{i_1, i_2 \in [m]} \; \min_{j_1, j_2 \in [n]} \big(P_{i_1,j_1}(x) + Q_{i_2,j_2}(x)\big), \end{aligned}\]

donc \(f(x) + g(x)\) est un métapolynôme.

On a donc prouvé que \(\mathcal{M}\) est stable par somme, maximum et minimum ; en particulier, toute fonction qui s'exprime à l'aide de sommes, de max, de min, de polynômes ou même de métapolynômes est dans \(\mathcal{M}\).

On voudrait procéder de même pour la multiplication, mais il y a une différence essentielle : en général, le produit des maxima de deux ensembles n'est pas le maximum des produits. Le problème vient de ce que \(a < b\) et \(c < d\) n'impliquent pas \(ac < bd\) ; c'est cependant vrai pour \(a, b, c, d \geq 0\).

Décomposons donc chaque fonction \(f(x)\) en sa partie positive \(f^+(x) = \max\{f(x), 0\}\) et sa partie négative \(f^-(x) = \max\{0, -f(x)\}\). On a \(f = f^+ - f^-\), et \(f^+, f^- \in \mathcal{M}\) si \(f \in \mathcal{M}\). Tout le problème se ramène à l'affirmation suivante : si \(f\) et \(g\) sont des métapolynômes positifs ou nuls, alors \(fg\) est un métapolynôme.

En admettant cette affirmation, considérons \(f, g \in \mathcal{M}\) quelconques. On a

\[fg = (f^+ - f^-)(g^+ - g^-) = f^+g^+ - f^+g^- - f^-g^+ + f^-g^-,\]

donc \(fg \in \mathcal{M}\). En effet, \(\mathcal{M}\) est stable par addition, et \(f^+g^+, f^+g^-, f^-g^+, f^-g^- \in \mathcal{M}\) puisque \(f^+, f^-, g^+, g^- \geq 0\).

Il reste à prouver l'affirmation. Dans ce cas \(f, g \geq 0\), et l'on peut reprendre l'argument de la somme. Plus précisément, soient \(f = \max \min P_{i,j} \geq 0\) et \(g = \max \min Q_{i,j} \geq 0\). Alors

\[fg = \max \min P_{i,j} \cdot \max \min Q_{i,j} = \max \min P^+_{i,j} \cdot \max \min Q^+_{i,j} = \max \min P^+_{i_1,j_1} \cdot Q^+_{i_2,j_2}.\]

Il suffit donc de vérifier que \(P^+ Q^+ \in \mathcal{M}\) pour tout couple de polynômes \(P\) et \(Q\). Cela se ramène à l'identité

\[u^+ v^+ = \max\big\{0, \; \min\{uv, u, v\}, \; \min\{uv, uv^2, u^2v\}, \; \min\{uv, u, u^2v\}, \; \min\{uv, uv^2, v\}\big\},\]

avec \(u\) remplacé par \(P(x)\) et \(v\) par \(Q(x)\). On la prouve par une étude de cas. Si \(u \leq 0\) ou \(v \leq 0\), les deux membres valent \(0\). Si \(u, v \geq 0\), le membre de droite est clairement au plus \(uv\). Pour l'inégalité inverse, on utilise que \(uv\) est égal à

\[\begin{cases} \min\{uv, u, v\} & \text{si } 0 \leq u, v \leq 1, \\ \min\{uv, uv^2, u^2v\} & \text{si } 1 \leq u, v, \\ \min\{uv, u, u^2v\} & \text{si } 0 \leq v \leq 1 \leq u, \\ \min\{uv, uv^2, v\} & \text{si } 0 \leq u \leq 1 \leq v. \qquad \blacksquare \end{cases}\]

Remarque

Le cas \(k = 1\) est plus simple : on peut montrer qu'une fonction \(f : \mathbb{R} \to \mathbb{R}\) est un métapolynôme si et seulement si elle est continue et polynomiale par morceaux.

Il suffit de prouver que toutes ces fonctions sont des métapolynômes, ce qui se ramène facilement au cas suivant : pour un polynôme \(P(x)\) avec \(P(0) = 0\), la fonction \(f\) définie par \(f(x) = P(x)\) pour \(x \geq 0\) et \(0\) sinon est un métapolynôme. Pour cela, il suffit de prouver que \((x^+)^n\) est un métapolynôme, ce qui découle de la formule \((x^+)^n = \max\{0, \min\{x^{n-1}, x^n\}, \min\{x^n, x^{n+1}\}\}\).