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...



Minimum number of variables on which a multivariate polynomial depends?
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.


