ECCC-Report TR22-131https://eccc.weizmann.ac.il/report/2022/131Comments and Revisions published for TR22-131en-usSun, 18 Sep 2022 11:52:56 +0300
Paper TR22-131
| Radical Sylvester-Gallai for Cubics |
Rafael Mendes de Oliveira,
Akash Sengupta
https://eccc.weizmann.ac.il/report/2022/131Let $\mathcal{F} = \{F_1, \ldots, F_m\}$ be a finite set of irreducible homogeneous multivariate polynomials of degree at most $3$ such that $F_i$ does not divide $F_j$ for $i\neq j$.
We say that $\mathcal{F}$ is a cubic radical Sylvester-Gallai configuration if for any two distinct $F_i,F_j$ there exists a third polynomial $F_k$ such that whenever $F_i,F_j$ vanish, $F_k$ also vanishes. In particular, for any two indices $i, j \in [m]$, there exists $k \in [m] \setminus \{i,j\}$ such that $F_k \in \rad(F_i, F_j)$.
We prove that any cubic radical Sylvester-Gallai configuration is low-dimensional, that is
$$ \dim span_{\mathbb{K}}{\mathcal{F}} = O(1).$$
This solves a conjecture of Gupta [G14] in degree $3$ and generalizes the result in [S20], which proved that quadratic radical Sylvester-Gallai configurations are low-dimensional.
Our result takes us one step closer towards solving the non-linear Sylvester-Gallai conjectures of Gupta [G14], which would yield the first deterministic polynomial time algorithm for the PIT problem for depth-4 circuits of bounded top and bottom fanins.
To prove our Sylvester-Gallai theorem, we develop several new tools combining techniques from algebraic geometry and elimination theory.
Among our technical contributions, we prove a structure theorem characterizing non-radical ideals generated by two cubic forms, generalizing the structure theorems of [HP94, CTSSD87, S20].
Moreover, building upon the groundbreaking work [AH20a], we introduce the notion of wide Ananyan-Hochster algebras and show that these algebras allow us to transfer the local conditions of Sylvester-Gallai configurations into global conditions. Sun, 18 Sep 2022 11:52:56 +0300https://eccc.weizmann.ac.il/report/2022/131