Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR22-131 | 18th September 2022 06:27

TR22-131
Authors: Rafael Mendes de Oliveira, Akash Sengupta
Publication: 18th September 2022 11:52
Keywords:

Abstract:

Let $\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.

ISSN 1433-8092 | Imprint