Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR25-037 | 31st March 2025 20:20

Uniform Bounds on Product Sylvester-Gallai Configurations

RSS-Feed




Revision #1
Authors: Abhibhav Garg, Rafael Mendes de Oliveira, Akash Sengupta
Accepted on: 31st March 2025 20:21
Downloads: 45
Keywords: 


Abstract:

In this work, we explore a non-linear extension of the classical Sylvester-Gallai configuration. Let $\mathbb{K}$ be an algebraically closed field of characteristic zero, and let $\mathcal{F} = \{F_1, \ldots, F_m\} \subset \mathbb{K}[x_1, \ldots, x_N]$ denote a collection of irreducible homogeneous polynomials of degree at most $d$, where each $F_i$ is not a scalar multiple of any other $F_j$ for $i \neq j$.
We define $\mathcal{F}$ to be a product Sylvester-Gallai configuration if, for any two distinct polynomials $F_i, F_j \in \mathcal{F}$, the following condition is satisfied:
$$\prod_{k \neq i, j} F_k \in \textrm{rad} \left( F_i, F_j \right).$$

We prove that product Sylvester-Gallai configurations are inherently low dimensional. Specifically, we show that there exists a function $\lambda : \mathbb{N} \rightarrow \mathbb{N}$, independent of $\mathbb{K}$, $N$, and $m$, such that any product Sylvester-Gallai configuration must satisfy:
$$ \dim (\text{span}_{\mathbb{K}}(\mathcal{F})) \leq \lambda(d). $$

This result generalizes the main theorems from [S19,PS20a, OS23], and gets us one step closer to a full derandomization of the polynomial identity testing problem for the class of depth 4 circuits with bounded top and bottom fan-in.



Changes to previous version:

Added authors to pdf


Paper:

TR25-037 | 31st March 2025 17:26

Uniform Bounds on Product Sylvester-Gallai Configurations


Abstract:

In this work, we explore a non-linear extension of the classical Sylvester-Gallai configuration. Let $\mathbb{K}$ be an algebraically closed field of characteristic zero, and let $\mathcal{F} = \{F_1, \ldots, F_m\} \subset \mathbb{K}[x_1, \ldots, x_N]$ denote a collection of irreducible homogeneous polynomials of degree at most $d$, where each $F_i$ is not a scalar multiple of any other $F_j$ for $i \neq j$.
We define $\mathcal{F}$ to be a product Sylvester-Gallai configuration if, for any two distinct polynomials $F_i, F_j \in \mathcal{F}$, the following condition is satisfied:
$$\prod_{k \neq i, j} F_k \in \textrm{rad} \left( F_i, F_j \right).$$

We prove that product Sylvester-Gallai configurations are inherently low dimensional. Specifically, we show that there exists a function $\lambda : \mathbb{N} \rightarrow \mathbb{N}$, independent of $\mathbb{K}$, $N$, and $m$, such that any product Sylvester-Gallai configuration must satisfy:
$$ \dim (\text{span}_{\mathbb{K}}(\mathcal{F})) \leq \lambda(d). $$

This result generalizes the main theorems from [S19,PS20a, OS23], and gets us one step closer to a full derandomization of the polynomial identity testing problem for the class of depth 4 circuits with bounded top and bottom fan-in.



ISSN 1433-8092 | Imprint