Robust Sylvester-Gallai type theorem for quadratic polynomials

Abstract

In this work, we extend the robust version of the Sylvester-Gallai theorem, obtained by Barak, Dvir, Wigderson and Yehudayoff, and by Dvir, Saraf and Wigderson, to the case of quadratic polynomials. Specifically, we prove that if $\mathcal{Q}\subset \mathbb{C}[x_1.\dots ,x_n]$ is a finite set, $|\mathcal{Q}|=m$, of irreducible quadratic polynomials that satisfy the following condition: There is $\delta >0$ such that for every $Q\in \mathcal{Q}$ there are at least $\delta m$ polynomials $P\in \mathcal{Q}$ such that whenever $Q$ and $P$ vanish then so does a third polynomial in $\mathcal{Q}\setminus \{Q,P\}$, then $\dim (\text{span}(\mathcal{Q}))=\text{poly}(1/\delta )$. The work of Barak et al. and Dvir et al. studied the case of linear polynomials and proved an upper bound of $O(1/\delta )$ on the dimension (in the first work an upper bound of $O(1/{\delta }^2)$ was given, which was improved to $O(1/\delta )$ in the second work).

arXiv admin note: text overlap with arXiv:2006.08263