A generalized Sylvester–Gallai-type theorem for quadratic polynomials. (15th December 2022)

• Record Type: Journal Article
• Authors: Peleg, Shir; Shpilka, Amir
• Is Part Of: Forum of mathematics. Volume 10(2022)
• Publication Date: 2022-12-15
• Subjects: 52C45 -- 52C99 -- 14M99 -- 68W30; Mathematics -- Periodicals; 510
• DOI: 10.1017/fms.2022.100
• Languages: English
• ISSNs: 2050-5094

Abstract

Abstract: 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$ .