IMO 2012 Shortlist A7

IMO 2012 Shortlist A7

Category: Algebra

Problem

We say that a function f : Rk → R is a metapolynomial if, for some positive integers m and n, it can be represented in the form f(x1,...,xk) = max i=1,...,m min j=1,...,n Pi,j(x1,...,xk) where Pi,j are multivariate polynomials. Prove that the product of two metapolynomials is also a metapolynomial. Solution. We use the notation f(x) = f(x1,...,xk) for x = (x1,...,xk) and [m] = {1,2,...,m}. Observe that if a metapolynomial f(x) admits a representation like the one in the statement for certain positive integers m and n, then they can be replaced by any m′ ≥ m and n′ ≥ n. For instance, if we want to replace m by m+1 then it is enough to define Pm+1,j(x) = Pm,j(x) and note that repeating elements of a set do not change its maximum nor its minimum. So one can assume that any two metapolynomials are defined with the same m and n. We reserve letters P and Q for polynomials, so every function called P,Pi,j,Q,Qi,j,... is a polynomial function. We start with a lemma that is useful to change expressions of the form minmaxfi,j to ones of the form maxmingi,j. Lemma. Let {ai,j} be real numbers, for all i ∈ [m] and j ∈ [n]. Then min i∈[m] max j∈[n] ai,j = max j1,...,jm∈[n] min i∈[m] ai,ji , where the max in the right-hand side is over all vectors (j1,...,jm) with j1,...,jm ∈ [n]. Proof. We can assume for all i that ai,n = max{ai,1,...,ai,n} and am,n = min{a1,n,...,am,n}. The left-hand side is = am,n and hence we need to prove the same for the right-hand side. If (j1,j2,...,jm) = (n,n,...,n) then min{a1,j1,...,am,jm} = min{a1,n,...,am,n} = am,n which implies that the right-hand side is ≥ am,n. It remains to prove the opposite inequality and this is equivalent to min{a1,j1,...,am,jm} ≤ am,n for all possible (j1,j2,...,jm). This is true because min{a1,j1,...,am,jm} ≤ am,jm ≤ am,n.  We need to show that the family M of metapolynomials is closed under multiplication, but it turns out easier to prove more: that it is also closed under addition, maxima and minima. First we prove the assertions about the maxima and the minima. If f1,...,fr are metapoly- nomials, assume them defined with the same m and n. Then f = max{f1,...,fr} = max{max i∈[m] min j∈[n] P1 i,j,...,max i∈[m] min j∈[n] Pr i,j} = max s∈[r],i∈[m] min j∈[n] Ps i,j. It follows that f = max{f1,...,fr} is a metapolynomial. The same argument works for the minima, but first we have to replace min max by max min, and this is done via the lemma. Another property we need is that if f = maxminPi,j is a metapolynomial then so is −f. Indeed, −f = min(−minPi,j) = minmaxPi,j. To prove M is closed under addition let f = maxminPi,j and g = maxminQi,j. Then f(x) + g(x) = max i∈[m] min j∈[n] Pi,j(x) + max i∈[m] min j∈[n] Qi,j(x) = max i1,i2∈[m] (min j∈[n] Pi1,j(x) + min j∈[n] Qi2,j(x)) = max i1,i2∈[m] min j1,j2∈[n] Pi1,j1(x) + Qi2,j2(x)
, and hence f(x) + g(x) is a metapolynomial. We proved that M is closed under sums, maxima and minima, in particular any function that can be expressed by sums, max, min, polynomials or even metapolynomials is in M. We would like to proceed with multiplication along the same lines like with addition, but there is an essential difference. In general the product of the maxima of two sets is not equal18 to the maximum of the product of the sets. We need to deal with the fact that a < b and c < d do not imply ac < bd. However this is true for a,b,c,d ≥ 0. In view of this we decompose each function f(x) into its positive part f+ (x) = max{f(x),0} and its negative part f− (x) = max{0,−f(x)}. Note that f = f+ − f− and f+ ,f− ∈ M if f ∈ M. The whole problem reduces to the claim that if f and g are metapolynomials with f,g ≥ 0 then fg it is also a metapolynomial. Assuming this claim, consider arbitrary f,g ∈ M. We have fg = (f+ − f− )(g+ − g− ) = f+ g+ − f+ g− − f− g+

• f− g− , and hence fg ∈ M. Indeed, M is closed under addition, also f+ g+ ,f+ g− ,f− g+ ,f− g− ∈ M because f+ ,f− ,g+ ,g− ≥ 0. It remains to prove the claim. In this case f,g ≥ 0, and one can try to repeat the argument for the sum. More precisely, let f = maxminPij ≥ 0 and g = maxminQij ≥ 0. Then fg = maxminPi,j · maxminQi,j = maxminP+ i,j · maxminQ+ i,j = maxminP+ i1,j1 · Q+ i2,j2 . Hence it suffices to check that P+ Q+ ∈ M for any pair of polynomials P and Q. This reduces to the identity u+ v+ = max{0,min{uv,u,v},min{uv,uv2 ,u2 v},min{uv,u,u2 v},min{uv,uv2 ,v}}, with u replaced by P(x) and v replaced by Q(x). The formula is proved by a case-by-case analysis. If u ≤ 0 or v ≤ 0 then both sides equal 0. In case u,v ≥ 0, the right-hand side is clearly ≤ uv. To prove the opposite inequality we use that uv equals min{uv,u,v} if 0 ≤ u,v ≤ 1, min{uv,uv2 ,u2 v} if 1 ≤ u,v, min{uv,u,u2 v} if 0 ≤ v ≤ 1 ≤ u, min{uv,uv2 ,v} if 0 ≤ u ≤ 1 ≤ v. Comment. The case k = 1 is simpler and can be solved by proving that a function f : R → R is a metapolynomial if and only if it is a piecewise polinomial (and continuos) function. It is enough to prove that all such functions are metapolynomials, and this easily reduces to the following case. Given a polynomial P(x) with P(0) = 0, the function f defined by f(x) = P(x) for x ≥ 0 and 0 otherwise is a metapolynomial. For this last claim, it suffices to prove that (x+)n is a metapolynomial, and this follows from the formula (x+)n = max{0,min{xn−1,xn},min{xn,xn+1}}.19