Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR22-037 | 10th March 2022 19:28

Robust Radical Sylvester-Gallai Theorem for Quadratics

RSS-Feed

Abstract:

We prove a robust generalization of a Sylvester-Gallai type theorem for quadratic polynomials, generalizing the result in [S'20].
More precisely, given a parameter $0 < \delta \leq 1$ and a finite collection $\mathcal{F}$ of irreducible and pairwise independent polynomials of degree at most 2, we say that $\mathcal{F}$ is a $(\delta, 2)$-radical Sylvester-Gallai configuration if for any polynomial $F_i \in \mathcal{F}$, there exist $\delta(|\mathcal{F}| -1)$ polynomials $F_j$ such that $|\mathrm{rad}(F_i, F_j) \cap \mathcal{F}| \geq 3$, that is, the radical of $F_i, F_j$ contains a third polynomial in the set.

In this work, we prove that any $(\delta, 2)$-radical Sylvester-Gallai configuration $\mathcal{F}$ must be of low dimension: that is
$$\dim \mathrm{span}(\mathcal{F}) = \mathrm{poly}(1/\delta).$$



ISSN 1433-8092 | Imprint