19
$\begingroup$

Let $p:F_2^n\rightarrow F_2$ be a multivariate polynomial, let's say of degree 3. (Both the degree and the order of the field could probably be replaced by other constants without affecting this question.)

I'm interested in the following computational problem: we're given $p$ as input, simply by a listing of its $O(n^3)$ coefficients. Our goal is to find the smallest positive integer $k$ such that $p(x)$ can be rewritten in the form $q(Ax)$, where $q$ is some other degree-3 polynomial, and $A$ is a $k \times n$ matrix over $F_2$.

What's known about this problem? Does it have a standard name? Is it known how to solve it in polynomial time, or is it conjectured to be hard? (To lay my cards on the table, it's not hard to solve this problem in quantum polynomial time---hence my interest!)

Update (3/13): I've now learned from several people---including Greg Kuperberg and Alex Arkhipov---that it might indeed be possible to learn the matrix $A$, by looking at all the second partial derivatives of $p$ and then taking their linear span. I still don't have a rigorous proof that this approach works, and also it's possible that it works only if $\operatorname{char}(F)>\deg(p)$ (i.e., the field characteristic exceeds the polynomial degree) and not otherwise. However, the outlook is not looking too great right now for this problem being hard classically...

$\endgroup$
  • 2
    $\begingroup$ When the size of the field is smaller than the degree of the polynomial, we can have two different polynomials that give the same function. For example, $x^2-x$ is identically zero on $\mathbb{F}_2$. Do you want to work with the polynomial as an abstract object, or with the polynomial as a function on $\mathbb{F}_2^n$? $\endgroup$ – David E Speyer Mar 13 '14 at 19:22
  • $\begingroup$ With the polynomial as a function on $F_2^n$. $\endgroup$ – Scott Aaronson Mar 13 '14 at 19:26
7
$\begingroup$

Let $d$ be the degree of the polynomial $f$, $n$ the number of variables, $p$ the characteristic and $q=p^e$ the size of the field. Assuming $d<p$, there is an easy polynomial algorithm.

Lemma Let $h(x)$ be a univariate polynomial of degree $d<p$ in characteristic $p$. Then $h$ is constant on $\mathbb{F}_q$ if and only if $dh/dx$ is evaluates to $0$ at each point of $\mathbb{F}_q$.

Proof Since $\deg h < |\mathbb{F}_q|$, the function $h$ is constant if and only if the polynomial is a constant polynomial. Since $\deg h < p$, all the positive exponents in $h$ are nonzero mod $p$, so $h$ is a constant polynomial if and only if $dh/dx$ is the zero polynomial. Finally, using $d<q$ once more, this happens if and only if $dh/dx$ is zero on each point of the field. $\square$

Corollary Let $f$ be a multivariate polynomial as above and let $(v_1, \ldots, v_n)$ be a vector in $\mathbb{F}_q^n$. Then $f$ is constant on lines of the form $(a_1, a_2, \ldots, a_n) + t (v_1, \ldots, v_n)$ if and only if all coefficients of $\partial f(x_1+t v_1, \ldots, x_n+t v_n)/\partial t|_{t=0}$ are zero.

Proof From the previous lemma, $f$ is constant the line $(a_1, a_2, \ldots, a_n) + t (v_1, \ldots, v_n)$ if and only if, for any $u$ in $\mathbb{F}_q$ we have $$\partial f(x_1+t v_1, \ldots, x_n+t v_n)/\partial t|_{t=0, x_i = a_i+u v_i}=0.$$ So $f$ is constant on all lines of this form if and only if $\partial f(x_1+t v_1, \ldots, x_n+t v_n)/\partial t|_{t=0}$ is $0$ for all points in $\mathbb{F}_q^n$. Since this is a degree $d-1$ polynomial in $(x_1, \ldots, x_n)$ and $d<q$, this happens if and only if all coefficients of $\partial f(x_1+t v_1, \ldots, x_n+t v_n)/\partial t|_{t=0}$ are zero. $\square$

Now, notice that $\partial f(x_1+t v_1, \ldots, x_n+t v_n)/\partial t|_{t=0}$ is linear in $(v_1, \ldots, v_n)$. So we can find such $v$ by solving $\binom{n+d}{d-1}=O(n^{d-1})$ equations (the number of coefficients in a degree $d-1$ polynomial in $n$ variables). By Gaussian elimination, we can do this in $O(n^{d+1})$.

I'm not so sure about the case where the field is small.

$\endgroup$
  • $\begingroup$ Thanks, David! But I confess I don't see why $df(x_1+tv_1,\ldots,x_n+tv_n)/dt$ is linear in $(v_1,...,v_n)$. For example, $d(x_1+tv_1)(x_2+tv_2)/dt=x_2 v_1 + x_1 v_2 + 2t v_1 v_2$. Should we be taking (d-1)st derivatives instead? $\endgroup$ – Scott Aaronson Mar 13 '14 at 22:28
  • 1
    $\begingroup$ You're right. Should be $df(x+tv)/dt|_{t=0}$. But, because I wasn't thinking straight, the other lemma isn't set up right for this. Editing now. $\endgroup$ – David E Speyer Mar 13 '14 at 23:09
  • $\begingroup$ Thanks! I assume "nonzero" should be "zero" in the corollary and its proof? (I'll change this; change it back if I screwed up) $\endgroup$ – Scott Aaronson Mar 13 '14 at 23:35
  • $\begingroup$ Thanks! Not sure what I was thinking there; zero it is. $\endgroup$ – David E Speyer Mar 13 '14 at 23:40
  • 1
    $\begingroup$ $df/dx=0$ doesn't imply $f=0$ when $\deg f \geq p$ (consider $f(x) = x^p$) so you have to think a bit harder. I do feel like I was jumping between points and polynomials a bit too often, but I think there is something to think about here. $\endgroup$ – David E Speyer Mar 14 '14 at 1:42
7
$\begingroup$

Just an update: with help from Dan Shepherd and Greg Kuperberg, I now understand how to solve this problem in deterministic, classical polynomial time, even when the degree $d$ is as large as the field characteristic or larger (the case that originally interested me, and that David Speyer's excellent answer doesn't treat). As a consequence, I now know that (alas) no exponential quantum speedup is possible for this problem.

For concreteness, let's assume we're working with a degree-$d$ polynomial $p:\mathbb{F}_2^n \rightarrow \mathbb{F}_2$, whose coefficients are given to us explicitly. Our goal is to find the subspace of "secret directions" $s \in \mathbb{F}_2^n$ such that $p(x)=p(x\oplus s)$ for all $x\in \mathbb{F}_2^n$. If $\operatorname{char}(\mathbb{F})$ were large enough, then (as David's answer discusses) we would simply use Gaussian elimination to find those $s$'s for which the formal partial derivative, $\frac{\partial p}{\partial s}$, is the identically-$0$ polynomial. Our problem is that formal partial derivatives are no longer "semantically sane" when $d \ge \operatorname{char}(\mathbb{F})$. For example, over $\mathbb{F}_2$, we can have a formal polynomial like $x^3 + x$ that's constant even though its derivative $3x^2+1=x+1$ is nonzero, or conversely, a formal polynomial like $x^2$ that's non-constant even though its derivative is $2x=0$. Likewise, one can construct examples of polynomials $p:\mathbb{F}_2^3 \rightarrow \mathbb{F}_2$ that have a "secret direction" even though their three partial derivatives

$\frac{\partial p}{\partial x},\frac{\partial p}{\partial y},\frac{\partial p}{\partial z}$

are linearly independent (e.g., $p(x,y,z)=xy+yz+xz+x+y+z$); or conversely, that have no "secret direction" even though their three partial derivatives are linearly dependent (e.g., $p(x,y,z)=xy+yz+xz$).

But we can solve this problem with the help of two new ideas. The first idea is to look at the "finite differences,"

$\frac{dp}{ds}(x) := p(x)+p(x\oplus s)$,

instead of formal partial derivatives. Finite differences are "semantically sane" over $\mathbb{F}_2$; in particular, the problem we're trying to solve is simply to find the subspace of $s$'s such that $\frac{dp}{ds}(x)$ is the identically-$0$ polynomial.

Now, the problem with finite differences is that they don't behave simply under linear combinations: in particular, it's not true in general that

$\frac{dp}{d(s+t)}(x) = \frac{dp}{ds}(x) + \frac{dp}{dt}(x)$.

But this brings us to the second new idea: namely, the above equation is true "to leading order." In more detail, $\frac{dp}{ds}(x)$ can be expanded out as a polynomial in both $s$ and $x$, which has total degree at most $d$, and degree at most $d-1$ in $x$ (since the degree-$d$ terms cancel). Now, suppose we look only at the terms of $\frac{dp}{ds}(x)$ that have degree $d-1$ in $x$, and not those terms that involve products of $d-2$ of the $x_i$'s or fewer. Then those terms will depend linearly on $s$, since the total degree can never exceed $d$. Thus, letting $q_s(x)$ be the degree-$(d-1)$ component of $\frac{dp}{ds}(x)$, we do indeed have

$q_{s+t}(x) = q_s(x) + q_t(x).$

Now let $S$ be the set of all $s\in \mathbb{F}_2^n$ on which $q_s(x)$ is the identically-$0$ polynomial---or in other words, on which $\frac{dp}{ds}(x)$ has degree at most $d-2$, considered as a polynomial in $x$. Then what we learn from the above is that $S$ is a subspace of $\mathbb{F}_2^n$. Moreover, it's a subspace that can be found in polynomial time, by simply using Gaussian elimination to find those $s$'s for which $q_s(x)$ is the identically-$0$ polynomial.

Now, once we've found this degree-$(d-2)$ subspace $S$, we can then simply apply the same algorithm inductively, in order to find the subspace $S' \le S$ of directions $s$ such that $\frac{dp}{ds}(x)$ has degree at most $d-3$, considered as a polynomial in $x$. Once again, the trick is to restrict attention to the "leading-order," degree-$(d-2)$ components of the polynomials $\frac{dp}{ds}(x)$ (for $s\in S$), and then use Gaussian elimination to find the subspace of directions $s$ on which those degree-$(d-2)$ components vanish. (Once again, we take advantage of the fact that these degree-$(d-2)$ components behave linearly as functions of $s$, even though the rest of the polynomials don't.)

Next we find the subspace $S'' \le S'$ of directions such that $\frac{dp}{ds}(x)$ has degree at most $d-4$, and so on, until we're down to the subspace on which $\frac{dp}{ds}(x)$ has degree $0$, and then we're done. Or rather, we're almost done: we still need to find the subspace on which $\frac{dp}{ds}(x)$ is the identically-$0$ polynomial, rather than the identically-$1$ polynomial. But that last part is trivial.

$\endgroup$

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.