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?

  • $\begingroup$ 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)$... $\endgroup$ – user61388 Jan 11 at 20:06
  • 1
    $\begingroup$ $F(x,y)$ is a polynomial of degree exactly $y$ or at most $y$? $\endgroup$ – Fedor Petrov Jan 11 at 20:09
  • $\begingroup$ An example would be ${x+y\choose y}$ $\endgroup$ – juan Jan 11 at 20:20
  • $\begingroup$ @juan, $\binom{x + y}y$ is not symmetric in $x$ and $y$. $\endgroup$ – LSpice Jan 11 at 22:53
  • $\begingroup$ @LSpice is not it, really? $\endgroup$ – Fedor Petrov Jan 12 at 0:32

With the polynomiality assumption a characterization is possible. I doubt that much can be said without it.

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.

  • $\begingroup$ If you're stating the theorem in generality, you should mention that $F$ is symmetric. $\endgroup$ – 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$$


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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