Open Collections

Sylvester-Gallai Type Theorems for Quadratic Polynomials

Banff International Research Station for Mathematical Innovation and Discovery

We prove Sylvester-Gallai type theorems for quadratic polynomials. Specifically, we prove that if a finite collection Q, of irreducible polynomials of degree at most 2, satisfy that for every two polynomials Q1,Q2 â Q there is a third polynomial Q3â Q so that whenever Q1 and Q2 vanish then also Q3 vanishes, then the linear span of the polynomials in Q has dimension O(1). We also prove a colored version of the theorem: If three finite sets of quadratic polynomials satisfy that for every two polynomials from distinct sets there is a polynomial in the third set satisfying the same vanishing condition then all polynomials are contained in an O(1)-dimensional space. This answers affirmatively two conjectures of Gupta [Electronic Colloquium on Computational Complexity (ECCC), 21:130, 2014] that were raised in the context of solving certain depth-4 polynomial identities. To obtain our main theorems we prove a new result classifying the possible ways that a quadratic polynomial Q can vanish when two other quadratic polynomials vanish. Our proofs also require robust versions of a theorem of Edelstein and Kelly (that extends the Sylvester-Gallai theorem to colored sets).

Mathematics; Computer science; Theoretical computer science

video/mp4

Author affiliation: Tel Aviv U

2020-01-06

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/73136

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/