2026-07-20T14:52:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5103 2024-03-06T10:35:54Z ddc:004 open_access

Polynomials Vanishing on Cartesian Products: The Elekes-Szabó Theorem Revisited Raz, Orit E. Sharir, Micha de Zeeuw, Frank Combinatorial geometry incidences polynomials Let F in Complex[x,y,z] be a constant-degree polynomial, and let A,B,C be sets of complex numbers with |A|=|B|=|C|=n. We show that F vanishes on at most O(n^{11/6}) points of the Cartesian product A x B x C (where the constant of proportionality depends polynomially on the degree of F), unless F has a special group-related form. This improves a theorem of Elekes and Szabo [ES12], and generalizes a result of Raz, Sharir, and Solymosi [RSS14a]. The same statement holds over R. When A, B, C have different sizes, a similar statement holds, with a more involved bound replacing O(n^{11/6}). This result provides a unified tool for improving bounds in various Erdos-type problems in combinatorial geometry, and we discuss several applications of this kind. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Orit E. Raz and Micha Sharir and Frank de Zeeuw 2015 Is Part Of LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SOCG.2015.522 urn:nbn:de:0030-drops-51031 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.522 eng https://creativecommons.org/licenses/by/3.0/legalcode