Search Results

Documents authored by Garg, Abhibhav


Document
Radical Sylvester-Gallai Theorem for Tuples of Quadratics

Authors: Abhibhav Garg, Rafael Oliveira, Shir Peleg, and Akash Kumar Sengupta

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)


Abstract
We prove a higher codimensional radical Sylvester-Gallai type theorem for quadratic polynomials, simultaneously generalizing [Hansen, 1965; Shpilka, 2020]. Hansen’s theorem is a high-dimensional version of the classical Sylvester-Gallai theorem in which the incidence condition is given by high-dimensional flats instead of lines. We generalize Hansen’s theorem to the setting of quadratic forms in a polynomial ring, where the incidence condition is given by radical membership in a high-codimensional ideal. Our main theorem is also a generalization of the quadratic Sylvester-Gallai Theorem of [Shpilka, 2020]. Our work is the first to prove a radical Sylvester-Gallai type theorem for arbitrary codimension k ≥ 2, whereas previous works [Shpilka, 2020; Shir Peleg and Amir Shpilka, 2020; Shir Peleg and Amir Shpilka, 2021; Garg et al., 2022] considered the case of codimension 2 ideals. Our techniques combine algebraic geometric and combinatorial arguments. A key ingredient is a structural result for ideals generated by a constant number of quadratics, showing that such ideals must be radical whenever the quadratic forms are far apart. Using the wide algebras defined in [Garg et al., 2022], combined with results about integral ring extensions and dimension theory, we develop new techniques for studying such ideals generated by quadratic forms. One advantage of our approach is that it does not need the finer classification theorems for codimension 2 complete intersection of quadratics proved in [Shpilka, 2020; Garg et al., 2022].

Cite as

Abhibhav Garg, Rafael Oliveira, Shir Peleg, and Akash Kumar Sengupta. Radical Sylvester-Gallai Theorem for Tuples of Quadratics. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 20:1-20:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.CCC.2023.20,
  author =	{Garg, Abhibhav and Oliveira, Rafael and Peleg, Shir and Sengupta, Akash Kumar},
  title =	{{Radical Sylvester-Gallai Theorem for Tuples of Quadratics}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{20:1--20:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.20},
  URN =		{urn:nbn:de:0030-drops-182903},
  doi =		{10.4230/LIPIcs.CCC.2023.20},
  annote =	{Keywords: Sylvester-Gallai theorem, arrangements of hypersurfaces, algebraic complexity, polynomial identity testing, algebraic geometry, commutative algebra}
}
Document
Robust Radical Sylvester-Gallai Theorem for Quadratics

Authors: Abhibhav Garg, Rafael Oliveira, and Akash Kumar Sengupta

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)


Abstract
We prove a robust generalization of a Sylvester-Gallai type theorem for quadratic polynomials. More precisely, given a parameter 0 < δ ≤ 1 and a finite collection ℱ of irreducible and pairwise independent polynomials of degree at most 2, we say that ℱ is a (δ, 2)-radical Sylvester-Gallai configuration if for any polynomial F_i ∈ ℱ, there exist δ(|ℱ|-1) polynomials F_j such that |rad (F_i, F_j) ∩ ℱ| ≥ 3, that is, the radical of F_i, F_j contains a third polynomial in the set. We prove that any (δ, 2)-radical Sylvester-Gallai configuration ℱ must be of low dimension: that is dim span_ℂ{ℱ} = poly(1/δ).

Cite as

Abhibhav Garg, Rafael Oliveira, and Akash Kumar Sengupta. Robust Radical Sylvester-Gallai Theorem for Quadratics. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 42:1-42:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.SoCG.2022.42,
  author =	{Garg, Abhibhav and Oliveira, Rafael and Sengupta, Akash Kumar},
  title =	{{Robust Radical Sylvester-Gallai Theorem for Quadratics}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{42:1--42:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.42},
  URN =		{urn:nbn:de:0030-drops-160505},
  doi =		{10.4230/LIPIcs.SoCG.2022.42},
  annote =	{Keywords: Sylvester-Gallai theorem, arrangements of hypersurfaces, locally correctable codes, algebraic complexity, polynomial identity testing, algebraic geometry, commutative algebra}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail