Let $f: \mathbb{Z}^2\to \mathbb{R}$ be a function. It is known that for any integer $C$ the four functions of $x$ \[f(x,C), f(C,x), f(x,x+C), f(x, C-x)\]are polynomials of degree at most $100$. Prove that $f$ is equal to a polynomial in two variables and find its maximal possible degree. Remark: The degree of a bivariate polynomial $P(x,y)$ is defined as the maximal value of $i+j$ over all monomials $x^iy^j$ appearing in $P$ with a non-zero coefficient.
Problem
Source: 2022 Israel TST test 10 P2
Tags: function, algebra, polynomial
Phorphyrion
25.08.2022 23:50
I'll add a solution because I think this is a really cool problem.
First, we show that $f$ is a polynomial. Indeed, let $g(x,y)$ be a polynomial of degree $\leq 100$ in each variable separately, such that $g(x,y)=f(x,y)$ for any integers $0\leq x,y\leq 100$ (of course such $g$ exists, by taking a linear combination of the polynomials $\frac{\prod_{i=0}^{100}(x-i)(y-i)}{(x-a)(y-b)}$ for $0\leq a, b\leq 100$). Then $f-g$ is a polynomial of degree $\leq 100$ on each horizontal or vertical line, and it vanishes whenever $0\leq x, y\leq 100$. Because a polynomial of degree $\leq 100$ with $101$ roots is 0, we get $g(x,y)=f(x,y)$ whenever $0\leq x\leq 100$ or $0\leq y\leq 100$, and this in turn implies $f=g$ in the whole plane.
The maximum degree is $133$. A construction is $f(x,y)=x^{33}y^{33}(x-y)^{33}(x+y)^{34}$.
Let $d=\deg f$. We'll show $d\leq 133$.
First, the condition tells us that the polynomials $f(x,y), f(x,x+y), f(x,y-x)$ have degree $\leq 100$ in each variable. Upon these substitutions, monomials of different total degrees cannot mix with each other, so the condition holds also for each homogeneous summand of $f$. Thus we may assume $f$ is homogeneous of degree $d$.
Write $f=x^a y^b P(y/x)$ where $P\in \mathbb{R}[x]$ has degree $k\leq a$ and does not vanish at 0, and $a+b=d$. Looking at the $x$-degree we see $a\leq 100$, and the $y$-degree says $b+k\leq 100$. Summing we see $d+k\leq 200$.
We can factor
\[P(t)=\prod_{i=1}^k (t-\alpha_i)\]over the complex numbers. Then
\[f(x,y)=x^{a-k}y^b \prod_{i=1}^k (y-\alpha_i x)\]From here
\[g(x)=f(x,y\pm x)=x^{a-k}(y\pm x)^b \prod_{i=1}^k (y-(\alpha_i\mp 1)x))\]For at least one of the choices of sign, at most $\frac{k}{2}$ of the factors in the product are divisible by $y$ (as each factor is divisible by $y$ in at most one of the choices). For that choice, we get
\[100\geq \deg g\geq (a-k)+b+\frac{k}{2}=a-\frac{k}{2}+b=d-\frac{k}{2}\]Sum this with $100\geq \frac{d}{2}+\frac{k}{2}$ we get $200\geq \frac{3}{2}d$, or $d\leq 133$. $\blacksquare$
Ru83n05
07.06.2023 18:30
(a) We will only be using that $f(x, C)$ and $f(C, x)$ are always polynomials of degree at most 100. From this information, we may use Lagrange Interpolation twice to construct $f$ from a finite set of points, namely $f(\{0, \cdots, 100\}^2)$. Here are the details. Consider the polynomial $$F(x, y)=\sum_{i=0}^{100} \left(\left(\sum_{j=0}^{100} f(i, j) \cdot \prod_{0\leq k \leq 100, \quad k\neq j} \frac{y-k}{j-k}\right) \cdot \prod_{0\leq l \leq 100, \quad l\neq i} \frac{x-l}{i-l} \right).$$I claim that $F(a, b)$ is equal to $f(a, b)$ for every $(a, b)\in \mathbb{Z}^2$. By construction, $F-f$ is zero on $\{0, \cdots, 100\}^2$, so, since $F-f$ has degree at most 100 in each variable, it is zero whenever $1\leq x\leq 100$ or $1\leq y\leq 100$, so, taking any hortzontal line $y=a$, it is 0 in 101 points on this line (namely when $0\leq x\leq 100$), so the polynomial $(F-f)(x, a)$ is always 0. Hence $F$ and $f$ agree on $\mathbb{Z}^2$. $\square$ (b) The answer is 133, with a possible construction being $f(x, y)=(x-y)^{34}(x+y)^{33}x^{33}y^{33}$. The key idea in this solution is to let $P(x, y)$ be the Taylor polynomial of degree 100 of $f$, and let $g(x,y)=f(x,y)-P(x,y)$, so that, since $f$ is a polynomial, all monomials $x^ay^b$ of $g$ satisfy $a+b\geq 101$. Lemma: $xy(x+y)(x-y)$ divides $g(x, y)$. Proof: To prove this, we will perform four different polynomial divisions. Consider $g(x,x)$. On one hand, it is a multiple of $x^{101}$. On the other hand, it is $f(x,x)-P(x,x)$, the diference of two polynomials of degree $\leq100$ by virtue of the problem statement and the definition of $P$. Thus, $g(x,x)$ is the $0$ polynomial. By Ruffini we may write $g(x,y)=(x-y)Q(x,y)+r(x)$, so we conclude $r\equiv 0$ and hence $x-y\mid g(x,y)$. Consider $g(x,0)$. By the same reasoning as above, we conclude $x\mid g(x,y)$. Consider $g(0,y)$. By the same reasoning as above, we conclude $y\mid g(x,y)$. Consider $g(x,-x)$. By the same reasoning as above, we conclude $x+y\mid g(x,y)$. This proves the lemma. $\square$ Now, the polynomial $\frac{g(x, y)}{xy(x-y)(x+y)}$ has the same properties as $f$, but for 97 instead of 100. This means that we may repeat the above procedure and induct down 33 times, until we find a polynomial that has the same properties for 1. For the base case of 1, it is not hard to see that $f$ can have degree at most 1, as any $x^2, y^2, xy$ terms lead to a contradiction to the asumptions made in the problem statement. Thus, we find that the original degree of $f$ is at most $33*4+1=133$ as the answer. $\blacksquare$