A generalized Sylvester–Gallai-type theorem for quadratic polynomials

Shir Peleg ; Amir Shpilka

Forum of Mathematics, Sigma, Tome 10 (2022)

Résumé

In this work, we prove a version of the Sylvester–Gallai theorem for quadratic polynomials that takes us one step closer to obtaining a deterministic polynomial time algorithm for testing zeroness of $\Sigma ^{[3]}\Pi \Sigma \Pi ^{[2]}$ circuits. Specifically, we prove that, if a finite set of irreducible quadratic polynomials ${\mathcal {Q}}$ satisfies that for every two polynomials $Q_1,Q_2\in {\mathcal {Q}}$ there is a subset ${\mathcal {K}}\subset {\mathcal {Q}}$ such that $Q_1,Q_2 \notin {\mathcal {K}}$ and whenever $Q_1$ and $Q_2$ vanish, then $\prod _{i\in {\mathcal {K}}} Q_i$ vanishes, then the linear span of the polynomials in ${\mathcal {Q}}$ has dimension $O(1)$. This extends the earlier result [21] that holds for the case $|{\mathcal {K}}| = 1$.

Détail

DOI : 10.1017/fms.2022.100