Document Open Access Logo

Robust Radical Sylvester-Gallai Theorem for Quadratics

Authors Abhibhav Garg , Rafael Oliveira , Akash Kumar Sengupta

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2022.42.pdf
  • Filesize: 0.71 MB
  • 13 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Theory of computation → Computational geometry
Keywords
  • Sylvester-Gallai theorem
  • arrangements of hypersurfaces
  • locally correctable codes
  • algebraic complexity
  • polynomial identity testing
  • algebraic geometry
  • commutative algebra

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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 Get BibTex

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) https://doi.org/10.4230/LIPIcs.SoCG.2022.42

Author Details

Abhibhav Garg
  • Cheriton School of Computer Science, University of Waterloo, Canada
Rafael Oliveira
  • Cheriton School of Computer Science, University of Waterloo, Canada
Akash Kumar Sengupta
  • Department of Mathematics, Columbia University, New York, NY, USA

References

  1. Boaz Barak, Zeev Dvir, Amir Yehudayoff, and Avi Wigderson. Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC '11, pages 519-528, New York, NY, USA, 2011. Association for Computing Machinery. URL: https://doi.org/10.1145/1993636.1993705.
  2. Peter Borwein and William OJ Moser. A survey of sylvester’s problem and its generalizations. Aequationes Mathematicae, 40(1):111-135, 1990. Google Scholar
  3. Chi-Ning Chou, Mrinal Kumar, and Noam Solomon. Closure results for polynomial factorization. Theory of Computing, 15(1):1-34, 2019. Google Scholar
  4. J-L Colliot-Thélene, J-J Sansuc, and P Swinnerton-Dyer. Intersections of two quadrics and châtelet surfaces. i. Journal für die reine und angewandte Mathematik, 373:37-107, 1987. Google Scholar
  5. Leonard Eugene Dickson. The points of inflexion of a plane cubic curve. The Annals of Mathematics, 16(1/4):50-66, 1914. Google Scholar
  6. Pranjal Dutta, Prateek Dwivedi, and Nitin Saxena. Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits. In Proceedings of the 36th Computational Complexity Conference, CCC '21, Dagstuhl, DEU, 2021. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.CCC.2021.11.
  7. Zeev Dvir. Incidence theorems and their applications. arXiv preprint, 2012. URL: http://arxiv.org/abs/1208.5073.
  8. Zeev Dvir, Shubhangi Saraf, and Avi Wigderson. Improved rank bounds for design matrices and a new proof of kelly’s theorem. In Forum of Mathematics, Sigma, volume 2. Cambridge University Press, 2014. Google Scholar
  9. Paul Erdos, Richard Bellman, Hubert S Wall, James Singer, and Victor Thébault. Problems for solution: 4065-4069. The American Mathematical Monthly, 50(1):65-66, 1943. Google Scholar
  10. Tibor Gallai. Solution of problem 4065. American Mathematical Monthly, 51:169-171, 1944. Google Scholar
  11. Ankit Gupta. Algebraic geometric techniques for depth-4 pit & sylvester-gallai conjectures for varieties. In Electron. Colloquium Comput. Complex., volume 21, page 130, 2014. Google Scholar
  12. Sten Hansen. A generalization of a theorem of sylvester on the lines determined by a finite point set. Mathematica Scandinavica, 16(2):175-180, 1965. Google Scholar
  13. William Vallance Douglas Hodge and Daniel Pedoe. Methods of Algebraic Geometry: Volume 2. Cambridge University Press, 1994. Google Scholar
  14. Neeraj Kayal and Shubhangi Saraf. Blackbox polynomial identity testing for depth 3 circuits. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 198-207. IEEE, 2009. Google Scholar
  15. Leroy Milton Kelly. A resolution of the sylvester-gallai problem of j.-p. serre. Discrete & Computational Geometry, 1(2):101-104, 1986. Google Scholar
  16. Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. Superpolynomial lower bounds against low-depth algebraic circuits. Electron. Colloquium Comput. Complex., page 81, 2021. URL: https://eccc.weizmann.ac.il/report/2021/081.
  17. Eberhard Melchior. Uber vielseite der projektiven ebene. Deutsche Math, 5:461-475, 1940. Google Scholar
  18. Rafael Oliveira and Akash Sengupta. Radical sylvester-gallai theorem for cubics. Manuscript, 2021. Google Scholar
  19. Shir Peleg and Amir Shpilka. A generalized sylvester-gallai type theorem for quadratic polynomials. CoRR, abs/2003.05152, 2020. URL: http://arxiv.org/abs/2003.05152.
  20. Shir Peleg and Amir Shpilka. Polynomial time deterministic identity testing algorithm for Σ^[3]ΠΣΠ^[2] circuits via edelstein-kelly type theorem for quadratic polynomials. CoRR, abs/2006.08263, 2020. URL: http://arxiv.org/abs/2006.08263.
  21. Shir Peleg and Amir Shpilka. Robust sylvester-gallai type theorem for quadratic polynomials. CoRR, abs/2202.04932, 2022. URL: http://arxiv.org/abs/2202.04932.
  22. Nitin Saxena and Comandur Seshadhri. From sylvester-gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuits. Journal of the ACM (JACM), 60(5):1-33, 2013. Google Scholar
  23. Jean-Pierre Serre. Advanced problem 5359. Amer. Math. Monthly, 73(1):89, 1966. Google Scholar
  24. Amir Shpilka. Sylvester-gallai type theorems for quadratic polynomials. Discrete Analysis, page 14492, 2020. Google Scholar
  25. Gaurav Sinha. Reconstruction of real depth-3 circuits with top fan-in 2. In 31st Conference on Computational Complexity (CCC 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  26. James Joseph Sylvester. Mathematical question 11851. Educational Times, 59(98):256, 1893. Google Scholar
  27. Endre Szemerédi and William T. Trotter. Extremal problems in discrete geometry. Combinatorica, 3(3):381-392, 1983. Google Scholar
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
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact