Polynomials Vanishing On Cartesian Products: The Elekes-Szabo Theorem Revisited

Let F 2 C[x; y; z] be a constant-degree polynomial, and let A; B; C subset of C be finite sets of size n. We show that F vanishes on at most O(n(11/6))points of the Cartesian product A X B X C, unless F has a special group-related form. This improves a theorem of Elekes and Szab and generalizes a result of Raz, Sharir, and Solymosi. The same statement holds over R, and a similar statement holds when A; B; C have different sizes (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.