Let $p$ be a prime. Given a bivariate polynomial $f(X,Y)\in \mathbb{F}_p[X,Y]$ with degrees $d_1,d_2$ in $X,Y$ respectively, what is the lowest known upper bound on the smallest integer $k$ such that $f(X,Y)$ can be expressed as a sum of products $$ f(X,Y) = \sum\limits_{i=1}^{k-1} f_{i,1}(X)\cdot f_{i,2}(Y) $$ with the polynomials $f_{i,1}(X)$, $f_{i,2}(Y)$ all univariate?

  • $\begingroup$ $1 + \min(d_{1}, d_{2})$ is one such upper bound. Try to solve $f_{i,2}(Y)$ when you set $f_{i,1}(X)= X^{i-1}$ $\endgroup$ Apr 27, 2023 at 19:29
  • $\begingroup$ @user3257842 I see that my question was poorly phrased. Meant to ask for the lowest known upper bound. $\endgroup$ Apr 27, 2023 at 19:43
  • 1
    $\begingroup$ Given that $a^p = a$ in $\mathbb{F}_p$, the complete formula is probably $min(p-1,d_1,d_2) + 1$. This can be proven by treating the bi-variate polynomial as a matrix and the problem as witting it as a sum of rank-$1$ matrices (outer products of vectors, where the vectors are the univariate polynomials in $X$ and $Y$), $\endgroup$ Apr 27, 2023 at 19:53
  • $\begingroup$ @user3257842 I also think that looking at this with rank-1 matrices is the key. However, we cannot identify a bivariate polynomial uniquely from knowing its values at $(x,y)\in\Bbb{F}_p^2$. At least I don't see it. More or less for the reason you stated ($a^p=a$ for all $a\in\Bbb{F}_p$ but $X$ and $X^p$ are distinct polynomials). $\endgroup$ Apr 27, 2023 at 19:58
  • 1
    $\begingroup$ @user3257842 True, but the question is not about functions from $\Bbb{F}_p^2$ to $\Bbb{F}_p$ but rather about the elements of the polynomial ring $\Bbb{F}_p[X,Y]$. Those are formal polynomials. That polynomial ring is an infinite dimensional vector space over $\Bbb{F}_p$. A (formal) polynomial $f(X,Y)$ can be uniquely identified from knowing its values at all the points $(x,y)\in\Bbb{F}_q^2$ only when $q=p^n$ exceeds the degree of $f$ (in $x$ and $y$ separately). $\endgroup$ Apr 29, 2023 at 7:58


You must log in to answer this question.