Polynomials Vanishing on Cartesian Products: The Elekes-Szabó Theorem Revisited

Raz, Orit E.; Sharir, Micha; de Zeeuw, Frank

doi:10.4230/LIPIcs.SOCG.2015.522

Document

Polynomials Vanishing on Cartesian Products: The Elekes-Szabó Theorem Revisited

Authors Orit E. Raz, Micha Sharir, Frank de Zeeuw

Part of: Volume: 31st International Symposium on Computational Geometry (SoCG 2015)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: Symposium on Computational Geometry (SoCG)
License: Creative Commons Attribution 3.0 Unported license
Publication Date: 2015-06-12

PDF

File

PDF

LIPIcs.SOCG.2015.522.pdf

Filesize: 0.52 MB
15 pages

Document Identifiers

DOI: 10.4230/LIPIcs.SOCG.2015.522
URN: urn:nbn:de:0030-drops-51031

Subject Classification

Keywords

Combinatorial geometry
incidences
polynomials

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

Abstract

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.

Cite As Get BibTex

Orit E. Raz, Micha Sharir, and Frank de Zeeuw. Polynomials Vanishing on Cartesian Products: The Elekes-Szabó Theorem Revisited. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 522-536, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.SOCG.2015.522

Author Details

Orit E. Raz

Micha Sharir

Frank de Zeeuw

Any Issues?

Feedback on the Current Page

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail