Extensions of a result of Elekes and Rónyai

preprint2012arXivOpen access

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 cn2cn^2 points of an n×n×nn\times n\times n cartesian product in R3\mathbb{R}^3, then the polynomial has the form f(x,y)=g(k(x)+l(y))f(x,y)=g(k(x)+l(y)) or f(x,y)=g(k(x)l(y))f(x,y)=g(k(x)l(y)). They used this to prove a conjecture of Purdy which states that given two lines in R2\mathbb{R}^2 and nn points on each line, if the number of distinct distances between pairs of points, one on each line, is at most cncn, 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×n×n×nn\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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.