Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, September 19, 2013, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Micha Sharir (Tel Aviv University)

Recent progress on incidences and distinct distances: Variants of the Elekes-Ronyai problem

Consider the following scenario, related to studies by Elekes and Ronyai and by Elekes and Szabo. Let A,B,C be three sets of n real numbers each, let z=f(x,y) be a bivariate polynomial, and let M denote the number of points (x,y,z) of A x B x C at which z=f(x,y). It was shown that if M=Ω(n^1.95) then f must be of one of the special forms p(q(x)+r(y)) or p(q(x)r(y)), for suitable polynomials p,q,r.

We present a different approach to the problem, and `almost' get an alternative proof, improving, in doing so, the threshold on M to O(n^11/6).

Instead of closing the gap in the general alternative proof, which is still open for us, we consider several concrete problems that fit into this framework, where the gap in the analysis can be closed, and we get improved bounds (and simpler proofs).

Two of the problems that we consider are:

(i) Let p1, p2, p3 be three non-collinear points in the plane, and let P be a set of n other points in the plane. We show that the number of distinct distances between p1,p2,p3 and the points of P is Ω(n^6/11), improving an earlier upper bound of Ω(n^0.502) of Elekes and Szabo. (This problem was initiated by Erdos, Lovasz and Vesztergombi.)

(ii) Let L1, L2 be two lines in the plane which are neither parallel nor orthogonal, let P1 be a set of m points on L1, and let P2 be a set of n points on L2. We show that the number of distinct distances between P1 and P2 is Ω(\min \{ m^2/3n^2/3, m², n² \}), improving an earlier bound by Elekes. (This problem was initiated by Purdy.)

Joint work with A. Sheffer, J. Solymosi, and others.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login