Discrete Math Seminar: Micha Sharir
Topic
The Elekes-Ronyai-Szabo theory and its applications
Speakers
Details
Let F(x,y,z) be a real trivariate polynomial of constant degree, and let A,B,C be three sets of real numbers, each of size n.
How many roots can F have on A x B x C?
This setup arises in many interesting problems in combinatorial geometry, including distinct distances between points on curves, distinct distances from three points, collinear triples of points on curves (the `orchard problem'), unit-area triangles, triple intersection points of families of circles, and more.
This question has been studied by Elekes and R\'onyai and then by Elekes and Szab\'o about 15 years ago. One of their striking results is that, for the special case where F(x,y,z) = z-f(x,y), either F vanishes at only a subquadratic number (o(n^2)) of points of A x B x C, or else f must have one of the special forms f(x,y) = h(p(x)+q(y)) or f(x,y) = h(p(x)q(y)), for univariate polynomials p, q, h.
In this talk I will survey recent progress on this problem, in which the analysis is greatly simplified, and the bounds become sharp: If F does not have a special form, the number of roots is at most O(n^{11/6}). Moreover, the results also hold over the complex field. This yields significantly improved bounds for many geometric problems, as listed above.
The proofs use techniques from algebra and algebraic geometry, which are somewhat related to the recent growing body of work on algebraic techniques for incidences and distance problems, inspired by Guth and Katz's seminal papers.
Joint work with Orit Raz, Jozsef Solymosi, and Frank de Zeeuw (and others).
How many roots can F have on A x B x C?
This setup arises in many interesting problems in combinatorial geometry, including distinct distances between points on curves, distinct distances from three points, collinear triples of points on curves (the `orchard problem'), unit-area triangles, triple intersection points of families of circles, and more.
This question has been studied by Elekes and R\'onyai and then by Elekes and Szab\'o about 15 years ago. One of their striking results is that, for the special case where F(x,y,z) = z-f(x,y), either F vanishes at only a subquadratic number (o(n^2)) of points of A x B x C, or else f must have one of the special forms f(x,y) = h(p(x)+q(y)) or f(x,y) = h(p(x)q(y)), for univariate polynomials p, q, h.
In this talk I will survey recent progress on this problem, in which the analysis is greatly simplified, and the bounds become sharp: If F does not have a special form, the number of roots is at most O(n^{11/6}). Moreover, the results also hold over the complex field. This yields significantly improved bounds for many geometric problems, as listed above.
The proofs use techniques from algebra and algebraic geometry, which are somewhat related to the recent growing body of work on algebraic techniques for incidences and distance problems, inspired by Guth and Katz's seminal papers.
Joint work with Orit Raz, Jozsef Solymosi, and Frank de Zeeuw (and others).
Additional Information
Location: ESB 4127
Micha Sharir, Tel Aviv University
Micha Sharir, Tel Aviv University