0
$\begingroup$

Just a warning, I am an amateur and this algorithm probably doesn't work.

A high level description of the algorithm:

Be $f(x_1,...,x_n)$ a polynomial, $n$ the number of variables and $d$ is the maximum degree of a variable in $f$.

  1. Find a vector set with at least $m=n*d$ elements such that any combination of $n$ elements forms a linearly independent subset of vectors.

    As pointed out by @SashoNikolov and @kodlu in another question, just use the geometric progressions in a Vandermonde matrix to create this set: $$ \begin{bmatrix} 1 & \alpha_1 & \alpha_1^2 & \dots & \alpha_1^{n-1}\\ 1 & \alpha_2 & \alpha_2^2 & \dots & \alpha_2^{n-1}\\ 1 & \alpha_3 & \alpha_3^2 & \dots & \alpha_3^{n-1}\\ \vdots & \vdots & \vdots & \ddots &\vdots \\ 1 & \alpha_m & \alpha_m^2 & \dots & \alpha_m^{n-1} \end{bmatrix} $$

    Where $\alpha_i = i$

  2. Now we use the line-vectors of the Vandermonde matrix above to change the original polynomial $f$ into $m$ univariate polynomials $f_i(t)$ which corresponds to the values of the original polynomial $f$ along the line passing through the origin with the line-vector.

    This is where it needs to be white-box, you go in the arithmetic circuit changing all variables according to the transformation: $$f_i(t)=f(\alpha_i^{0}t,\alpha_i^{1}t,...,\alpha_i^{n-1}t)$$

  3. Being a univariate polynomial, it is trivial to normalise this polynomial and check if it is identically $0$ or not.

  4. If and only if all the univariate polynomials are identically $0$ then the original polynomial $f$ is identically $0$.


The geometrical reasoning:

Supposing $f$ is not identically $0$, to maximize the amount of non-colinear lines through the origin where $f=0$, $f$ should be a union of hypersurfaces (homogeneous polynomial).

Supposing $f$ is an homogenous polynomial (worst case), each hypersurface is able at best to make $f=0$ along $n-1$ of the Vandermonde line-vectors. So a union of $d$ hypersurfaces (best case as d is the maximum degree of a variable in $f$) is able at best to make $f=0$ along $(n-1)*d<m$ vector-lines.


Would this work? What is wrong?

$\endgroup$
  • 4
    $\begingroup$ First, a polynomial represented by an arithmetical circuit may well have exponentially large degree. Second, I don't see how the linear independence of the Vandermonde vectors should imply correctness of the test. Unless I'm missing something, your test declares $f(x,y,z)=xz-y^2$ identically 0. $\endgroup$ – Emil Jeřábek Jan 4 '15 at 12:37
  • $\begingroup$ @EmilJeřábek You are correct. Linear independence is not enough... $\endgroup$ – Flávio Botelho Jan 4 '15 at 18:52
5
$\begingroup$

Would this work? What is wrong?

No proof sketch that this is a polynomial time algorithm is given. The point where the algorithm might stop being a polynomial time algorithm is step 3:

  1. Being a univariate polynomial, it is trivial to normalise this polynomial and check if it is identically 0 or not.

Even so normalising a univariate polynomial is trivial from a conceptual point of view, it's unclear whether it can be done in polynomial time (or even polynomial space). For multivariate polynomials, it's obvious that polynomials like $(1+x_1)(1+x_2)\dots(1+x_n)$ can't be normalized in polynomial space. For univariate polynomials, the details of the problem formulation become important. If the input polynomial is given by an arithmetic circuit and the coefficients are from $\mathbb Z$, then repeated squaring will give you abundant examples of polynomials which cannot be normalized in polynomial space. (PIT is often done over finite fields, which avoids this sort of space explosion.)

The proof sketch that the algorithm works as intended has too many holes for being a valid mathematical proof. However, it is quite possible that there is a proper mathematical proof showing that the proposed algorithm works as intended, and this wouldn't even be a surprise. Here are some of the holes:

$f$ should be a union of hypersurfaces (homogeneous polynomial)

This reads like a claim that $f$ is a homogeneous polynomial iff $f=0$ is a union of hypersurfaces (through the origin). But $f(x,y,z)=x^2+y^2-z^2$ is a homogeneous polynomial for which $f=0$ is not a finite union of hypersurfaces.

Supposing $f$ is an homogenous polynomial (worst case), each hypersurface is able at best to make $f=0$ along $n−1$ of the Vandermonde line-vectors.

This seems to assume that $f(x_1,\dots,x_n)=\prod_i(\sum_j a_{ij}x_j)$, which might be yet another interpretation of "union of hypersurfaces". The hole in the proof here is that the "(worst case)" claim isn't proved. Note that $f(x,y,z)=x^2+y^2-z^2$ is a homogeneous polynomial, but it cannot be written in the assumed form.

$\endgroup$
  • $\begingroup$ "Homogeneous polynomial" is completely wrong. The correct notion would be a polynomial that factors to linear components.. $\endgroup$ – Flávio Botelho Jan 4 '15 at 18:45
  • 2
    $\begingroup$ @FlávioBotelho Even so EmilJeřábek's counterexample shows that linear independence is not enough, I have seen similar reductions to univariate polynomials (but relying on randomness) in related work by Erich Kaltofen and Barry Trager: www4.ncsu.edu/~kaltofen/bibliography/88/focs88.ps.gz and www4.ncsu.edu/~kaltofen/bibliography/90/KaTr90.pdf $\endgroup$ – Thomas Klimpel Jan 4 '15 at 19:50
  • 2
    $\begingroup$ PIT (for circuits) is in fact deterministically polynomial-time reducible to its univariate version using Kronecker substitution: replace $f(x_0,\dots,x_{n-1})$ with $f(x,x^d,\dots,x^{d^{n-1}})$, where $d$ is larger than the degree of $f$ (which is at worst exponential in the size of the original circuit). You can implement $x^{d^i}$ by a circuit of size $O(i\log d)$ using repeated squaring. Over $\mathbb Z$ (or $\mathbb Q$), PIT is even reducible to its 0-variate version, i.e., zero-testing for integer constant circuits: replace $f(x)$ with $f(c)$, where $c$ is a suitably huge constant, ... $\endgroup$ – Emil Jeřábek Jan 4 '15 at 21:10
  • 2
    $\begingroup$ ... which you again compute by repeated squaring. None of this actually seems to help solving the problem. $\endgroup$ – Emil Jeřábek Jan 4 '15 at 21:11
  • 1
    $\begingroup$ About checking if the univariate polynomial is identically 0, maybe that could be overcome by changing the step to evaluate this univariate polynomial at $d+1$ or $n*d+1$ points (black box). Probably that should be enough to show that the line is a subvariety of the algebraic variety correspondent to the original polynomial. But Emil's counterexample to the whole scheme withstands. The vectors cannot have any polynomial patterns (limited to some degree of polynomials)... $\endgroup$ – Flávio Botelho Jan 5 '15 at 1:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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