# Function on two variables that restricts to a polynomial

Lets say that I have a function $$F(x,y)$$ that is defined on nonnegative integers (or at least those are the values I care about) and is symmetric, so that $$F(x,y)=F(y,x)$$. Moreover, I know that for any fixed value of $$y$$ I have that $$F(x,y)$$ is a polynomial in $$x$$ of degree $$y$$. What can I say about the form of the function $$F(x,y)$$?

Does it change what we would know if I just know that for any fixed $$y$$ we have that $$F(x,y) = O(x^y)$$ rather than a polynomial?

• The first guess would of course be to guess that $F(x,y)=x^y$ but then you aren't symmetric. And if you say $F(x,y)=x^y+y^x$ then you are no longer $O(x^y)$... – user61388 Jan 11 at 20:06
• $F(x,y)$ is a polynomial of degree exactly $y$ or at most $y$? – Fedor Petrov Jan 11 at 20:09
• An example would be ${x+y\choose y}$ – juan Jan 11 at 20:20
• @juan, $\binom{x + y}y$ is not symmetric in $x$ and $y$. – LSpice Jan 11 at 22:53
• @LSpice is not it, really? – Fedor Petrov Jan 12 at 0:32

Theorem: Assuming that $$F(x,y)$$ is a polynomial in $$x$$ of degree $$y$$ for any $$y\in \mathbb Z_{\geq 0}$$ we have that $$F(x,y)=\sum_{k\geq 0}\alpha_k (x+y)^k\binom{x+y-2k}{y-k}$$ for some arbitrary sequence $$\alpha_0,\alpha_1,\dots.$$
Proof: There exist coefficients $$\alpha_{k,y}$$ such that for each $$y\in \mathbb Z_{\geq 0}$$ we can write $$F(x,y)=\sum_{0\le k\le y} \alpha_{k,y}(x+y)^k \binom{x+y-2k}{y-k}.$$ Notice that the terms in this expression are nonzero only if $$k\le \min{x,y}$$. We can prove by induction on $$k$$ that $$\alpha_{k,y}$$ doesn't depend on $$y$$. For the base case $$k=0$$ we have $$F(x,0)=F(0,x)$$ which gives $$\alpha_{0,0}=\alpha_{0,x}$$. For the general case, assume we have shown our claim for $$k\le m-1$$. Looking at $$F(x,m)=F(m,x)$$ for arbitrary $$x\geq m$$, we cancel out the equal terms that we have from the induction hypothesis and we are left with $$\alpha_{m,m}(x+m)^m\binom{x-m}{0}=\alpha_{m,x}(m+x)^m\binom{x-m}{x-m}\implies \alpha_{m,m}=\alpha_{m,x}$$ finishing our proof.
• If you're stating the theorem in generality, you should mention that $F$ is symmetric. – mathworker21 Jan 18 at 3:48
The general solution for the polynomial case is $$F(x,y) := \sum_{k=0}^{\textrm{min}(x,y)} a_k {x \choose k}{y \choose k}. \tag1$$ where $$a_k$$ are any coefficients. Clearly it is symmetric in $$x$$ and $$y$$. For a fixed $$y$$ the function is a polynomial in $$x$$ with maximum degree $$y$$, and iff all of the $$a_k$$ are non-zero, then the degree is exactly $$y$$.
For the $$O(x^y)$$ case, $$F(x,y)$$ as defined in equation $$(1)$$ is a solution, but otherwise the solutions are very general. In brief, they should not grow too fast, but there does not seem to be a simple way to describe the general solution except to state the obvious. That is, $$F(x,0) = O(1),\, F(x,1) = O(x),\, F(x,2) = O(x^2),\, \dots. \tag2$$