Idea for a white-box PIT deterministic algorithm in polynomial time

Question

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?

Answer 1

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:

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