We say that a function $f:\mathbb{R}^k \rightarrow \mathbb{R}$ is a metapolynomial if, for some positive integer $m$ and $n$, it can be represented in the form $$f(x_1,\cdots , x_k )=\max_{i=1,\cdots , m} \min_{j=1,\cdots , n}P_{i,j}(x_1,\cdots , x_k)$$ where $P_{i,j}$ are multivariate polynomials. Prove that the product of two metapolynomials is also a metapolynomial.

This problem was given in the IMO Shortlist 2012 A7, I want to know if there is some paper on this topic metapolynomials. I searched on the web but I found nothing. I found this topic interesting. So a reference would be helpful.

  • 1
    $\begingroup$ in computer science a meta-polynomial is a vector of polynomials that operates on strings, say $a\cdot A\oplus B$ is the meta-polynomial that represents the vector $(a_1 A_1+B_1,a_2 A_2+B_2,\ldots a_t A_t+B_t)$, with $A,B$ strings of length $t$. see, for example, cs.technion.ac.il/~yuvali/pubs/IK02.ps $\endgroup$ – Carlo Beenakker Jun 28 '14 at 14:05
  • 5
    $\begingroup$ I suspect the name was made up for the IMO problem, and doesn't exist (with that meaning) elsewhere. $\endgroup$ – Gerry Myerson Jun 28 '14 at 14:18
  • $\begingroup$ Yes, since google didn't give a hit on that name. I second Gerry's decision. $\endgroup$ – shadow10 Jun 28 '14 at 14:56
  • 2
    $\begingroup$ In view of the votes to close I would like to state that I do not understand why the question is off-topic. The question does not ask for a solution to the problem, this would indeed be off-topic. It asks if a certain notion comes up in the (research) literature; as opposed to being only an artefact for some contest. This seems on-topic to me, especially since the name chosen in the contest might not be the name under which it actually comes up and it could be hard to find it. $\endgroup$ – user9072 Jun 28 '14 at 15:56

If you put an absolute value around your polynomial, then this sort of max-min comes up in the construction of local height functions. In the terminology of Lang's Fundamentals of Diophantine Geometry (see especially Chapter 10, Theorem 3.5, page 261), the equation displayed at the top of page 262 is $$ \lambda = \sup_j \inf_i \lambda_{ij}. $$ Unsorting the definitions, one has essentially $$ \lambda_{ij}(x_1,\ldots,x_n) = \log\bigl| f_{ij}(x_1,\ldots,x_n)\bigr| $$ for a certain collection of polynomials (or maybe rational functions) $f_{ij}$. So aside from having taken logs, the function $\lambda$ is the IMO max-min with absolute values.

These Weil functions are associated to divisors and do satisfy an addition formula $\lambda_{D_1}+\lambda_{D_2}=\lambda_{D_1+D_2}$, which is related to the IMO question. The IMO question is less general, but more precise because the Weil function $\lambda_D$ associated to a divisor $D$ is only well-defined up to what Lang calls an $M_K$-bounded function. On the other hand, the proof of the addition formula probably comes down to doing the IMO problem (modulo those pesky absolute value signs).

Final Comment: In Lang's setup, the absolute value may be the usual one on $\mathbb R$ or $\mathbb C$, but it could also be a $p$-adic absolute value; and more generally, one really wants a collection of Weil height $\lambda_{D,v}$, one for each absolute value $v$, that have some sort of uniformity as one varies over $v$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.