Extensions of a result of Elekes and Rónyai

Abstract

Many problems in combinatorial geometry can be formulated in terms of curves or surfaces containing many points of a cartesian product. In 2000, Elekes and Rónyai proved that if the graph of a polynomial contains $c{n}^2$ points of an $n\times n\times n$ cartesian product in ${\mathbb{R}}^3$, then the polynomial has the form $f(x,y)=g(k(x)+l(y))$ or $f(x,y)=g(k(x)l(y))$. They used this to prove a conjecture of Purdy which states that given two lines in ${\mathbb{R}}^2$ and $n$ points on each line, if the number of distinct distances between pairs of points, one on each line, is at most $cn$, then the lines are parallel or orthogonal. We extend the Elekes-Rónyai Theorem to a less symmetric cartesian product. We also extend the Elekes-Rónyai Theorem to one dimension higher on an $n\times n\times n\times n$ cartesian product and an asymmetric cartesian product. We give a proof of a variation of Purdy's conjecture with fewer points on one of the lines. We finish with a lower bound for our main result in one dimension higher with asymmetric cartesian product, showing that it is near-optimal.

23 pages

Cited by in corpus (4)

• Distinct distances on algebraic curves in the plane
• Distinct Distances: Open Problems and Current Bounds
• Three-variable expanding polynomials and higher-dimensional distinct distances
• Convex Polygons in Cartesian Products