BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Frank de Zeeuw

Frank de Zeeuw appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COmath.MGComputational Geometrymath.NTDiscrete Mathematics

Catalog footprint

What is connected

15works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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

Published work

15 published item(s)

preprint2022arXiv

A Sylvester-Gallai theorem for cubic curves

We prove a variant of the Sylvester-Gallai theorem for cubics (algebraic curves of degree three): If a finite set of sufficiently many points in $\mathbb{R}^2$ is not contained in a cubic, then there is a cubic that contains exactly nine of the points. This resolves the first unknown case of a conjecture of Wiseman and Wilson from 1988, who proved a variant of Sylvester-Gallai for conics and conjectured that similar statements hold for curves of any degree.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A survey of Elekes-Rónyai-type problems

We give an overview of recent progress around a problem introduced by Elekes and Rónyai. The prototype problem is to show that a polynomial $f\in \mathbb{R}[x,y]$ has a large image on a Cartesian product $A\times B\subset \mathbb{R}^2$, unless $f$ has a group-related special form. We discuss a number of variants and generalizations. This includes the Elekes-Szabó problem, which generalizes the Elekes-Rónyai problem to a question about an upper bound on the intersection of an algebraic surface with a Cartesian product, and curve variants, where we ask the same questions for Cartesian products of finite subsets of algebraic curves. These problems lie at the crossroads of combinatorics, algebra, and geometry: They ask combinatorial questions about algebraic objects, whose answers turn out to have applications to geometric questions involving basic objects like distances, lines, and circles, as well as to sum-product-type questions from additive combinatorics. As part of a recent surge of algebraic techniques in combinatorial geometry, a number of quantitative and qualitative steps have been made within this framework. Nevertheless, many tantalizing open questions remain.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the number of ordinary conics

We prove a lower bound on the number of ordinary conics determined by a finite point set in $\mathbb{R}^2$. An ordinary conic for a subset $S$ of $\mathbb{R}^2$ is a conic that is determined by five points of $S$, and contains no other points of $S$. Wiseman and Wilson proved the Sylvester-Gallai-type statement that if a finite point set is not contained in a conic, then it determines at least one ordinary conic. We give a simpler proof of their result and then combine it with a result of Green and Tao to prove our main result: If $S$ is not contained in a conic and has at most $c|S|$ points on a line, then $S$ determines $Ω_c(|S|^4)$ ordinary conics. We also give a construction, based on the group structure of elliptic curves, that shows that the exponent in our bound is best possible.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Elekes-Szabó Theorem in four dimensions

Let $F\in\mathbb{C}[x,y,s,t]$ be an irreducible constant-degree polynomial, and let $A,B,C,D\subset\mathbb{C}$ be finite sets of size $n$. We show that $F$ vanishes on at most $O(n^{8/3})$ points of the Cartesian product $A\times B\times C\times D$, unless $F$ has a special group-related form. A similar statement holds for $A,B,C,D$ of unequal sizes. This is a four-dimensional extension of our recent improved analysis of the original Elekes-Szabó theorem in three dimensions. We give three applications: an expansion bound for three-variable real polynomials that do not have a special form, a bound on the number of coplanar quadruples on a space curve that is neither planar nor quartic, and a bound on the number of four-point circles on a plane curve that has degree at least five.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Distinct distances between points and lines

We show that for $m$ points and $n$ lines in the real plane, the number of distinct distances between the points and the lines is $Ω(m^{1/5}n^{3/5})$, as long as $m^{1/2}\le n\le m^2$. We also prove that for any $m$ points in the plane, not all on a line, the number of distances between these points and the lines that they span is $Ω(m^{4/3})$. The problem of bounding the number of distinct point-line distances can be reduced to the problem of bounding the number of tangent pairs among a finite set of lines and a finite set of circles in the plane, and we believe that this latter question is of independent interest. In the same vein, we show that $n$ circles in the plane determine at most $O(n^{3/2})$ points where two or more circles are tangent, improving the previously best known bound of $O(n^{3/2}\log n)$. Finally, we study three-dimensional versions of the distinct point-line distances problem, namely, distinct point-line distances and distinct point-plane distances. The problems studied in this paper are all new, and the bounds that we derive for them, albeit most likely not tight, are non-trivial to prove. We hope that our work will motivate further studies of these and related problems.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Distinct distances on algebraic curves in the plane

Let $P$ be a set of $n$ points in the real plane contained in an algebraic curve $C$ of degree $d$. We prove that the number of distinct distances determined by $P$ is at least $c_d n^{4/3}$, unless $C$ contains a line or a circle. We also prove the lower bound $c_d' \min(m^{2/3}n^{2/3}, m^2, n^2)$ for the number of distinct distances between $m$ points on one irreducible plane algebraic curve and $n$ points on another, unless the two curves are parallel lines, orthogonal lines, or concentric circles. This generalizes a result on distances between lines of Sharir, Sheffer, and Solymosi in arXiv:1302.3081.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Distinct values of bilinear forms on algebraic curves

Let $B$ be a bilinear form on pairs of points in the complex plane, of the form $B(p,q) = p^TMq$, for an invertible $2\times2$ complex matrix $M$. We prove that any finite set $S$ contained in an irreducible algebraic curve $C$ of degree $d$ in $\mathbb{C}^2$ determines at least $c_d|S|^{4/3}$ distinct values of $B$, unless the curve $C$ has an exceptional form. This strengthens a result of Charalambides in several ways. The proof is based on that of Pach and De Zeeuw, who proved a similar statement for the Euclidean distance function in the real plane. Our main motivation for this paper is that for bilinear forms, this approach becomes more natural, and should better lend itself to understanding and generalization.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Incidence bounds for complex algebraic curves on Cartesian products

We prove bounds on the number of incidences between a set of algebraic curves in $\mathbb{C}^2$ and a Cartesian product $A\times B$ with finite sets $A,B\subset \mathbb{C}$. Similar bounds are known under various conditions, but we show that the Cartesian product assumption leads to a simpler proof. This assumption holds in a number of interesting applications, and with our bound these applications can be extended from $\mathbb{R}$ to $\mathbb{C}$. The proof is a new application of the polynomial partitioning technique introduced by Guth and Katz.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Bisector energy and few distinct distances

We introduce the bisector energy of an $n$-point set $P$ in $\mathbb{R}^2$, defined as the number of quadruples $(a,b,c,d)$ from $P$ such that $a$ and $b$ determine the same perpendicular bisector as $c$ and $d$. If no line or circle contains $M(n)$ points of $P$, then we prove that the bisector energy is $O(M(n)^{\frac{2}{5}}n^{\frac{12}{5}+ε} + M(n)n^2).$. We also prove the lower bound $Ω(M(n)n^2)$, which matches our upper bound when $M(n)$ is large. We use our upper bound on the bisector energy to obtain two rather different results: (i) If $P$ determines $O(n/\sqrt{\log n})$ distinct distances, then for any $0<α\le 1/4$, either there exists a line or circle that contains $n^α$ points of $P$, or there exist $Ω(n^{8/5-12α/5-ε})$ distinct lines that contain $Ω(\sqrt{\log n})$ points of $P$. This result provides new information on a conjecture of Erdős regarding the structure of point sets with few distinct distances. (ii) If no line or circle contains $M(n)$ points of $P$, then the number of distinct perpendicular bisectors determined by $P$ is $Ω(\min\{M(n)^{-2/5}n^{8/5-ε}, M(n)^{-1} n^2\})$. This appears to be the first higher-dimensional example in a framework for studying the expansion properties of polynomials and rational functions over $\mathbb{R}$, initiated by Elekes and Rónyai.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Few distinct distances implies no heavy lines or circles

We study the structure of planar point sets that determine a small number of distinct distances. Specifically, we show that if a set P of n points determines o(n) distinct distances, then no line contains Ω(n^{7/8}) points of P and no circle contains Ω(n^{5/6}) points of P. We rely on the bipartite and partial variant of the Elekes-Sharir framework that was presented by Sharir, Sheffer, and Solymosi in \cite{SSS13}. For the case of lines we combine this framework with a theorem from additive combinatorics, and for the case of circles we combine it with some basic algebraic geometry and a recent incidence bound for plane algebraic curves by Wang, Yang, and Zhang \cite{WYZ13}. A significant difference between our approach and that of \cite{SSS13} (and other recent extensions) is that, instead of dealing with distances between two point sets that are restricted to one-dimensional curves, we consider distances between one set that is restricted to a curve and one set with no restrictions on it.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Extensions of a result of Elekes and Rónyai

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 $cn^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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Rational Distances with Rational Angles

In 1946 Erd\H os asked for the maximum number of unit distances, $u(n)$, among $n$ points in the plane. He showed that $u(n)> n^{1+c/\log\log n}$ and conjectured that this was the true magnitude. The best known upper bound is $u(n)<cn^{4/3}$, due to Spencer, Szemerédi and Trotter. We show that the upper bound $n^{1+6/\sqrt{\log n}}$ holds if we only consider unit distances with rational angle, by which we mean that the line through the pair of points makes a rational angle in degrees with the x-axis. Using an algebraic theorem of Mann we get a uniform bound on the number of paths between two fixed vertices in the unit distance graph, giving a contradiction if there are too many unit distances with rational angle. This bound holds if we consider rational distances instead of unit distances as long as there are no three points on a line. A superlinear lower bound is given, due to Erd\H os and Purdy. If we have at most $n^α$ points on a line then we get the bound $O(n^{1+α})$ or $n^{1+α+6/\sqrt{\log n}}$ for the number of rational distances with rational angle depending on whether $α\ge 1/2$ or $α< 1/2$ respectively.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

On a question of Erdos and Ulam

Ulam asked in 1945 if there is an everywhere dense \emph{rational set}, i.e. a point set in the plane with all its pairwise distances rational. Erd\H os conjectured that if a set $S$ has a dense rational subset, then $S$ should be very special. The only known types of examples of sets with dense (or even just infinite) rational subsets are lines and circles. In this paper we prove Erd\H os's conjecture for algebraic curves, by showing that no irreducible algebraic curve other than a line or a circle contains an infinite rational set.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Simultaneous Arithmetic Progressions on Algebraic Curves

A simultaneous arithmetic progression (s.a.p.) of length k consists of k points (x_i, y_σ(i)), where x_i and y_i are arithmetic progressions and σis a permutation. Garcia-Selfa and Tornero asked whether there is a bound on the length of an s.a.p. on an elliptic curve in Weierstrass form over Q. We show that 4319 is such a bound for curves over R. This is done by considering translates of the curve in a grid as a graph. A simple upper bound is found for the number of crossings and the 'crossing inequality' gives a lower bound. Together these bound the length of an s.a.p. on the curve. We then use a similar method to extend the result to arbitrary real algebraic curves. Instead of considering s.a.p.'s we consider k^2/3 points in a grid. The number of crossings is bounded by Bezout's Theorem. We then give another proof using a result of Jarnik bounding the number of grid points on a convex curve. This result applies as any real algebraic curve can be broken up into convex and concave parts, the number of which depend on the degree. Lastly, these results are extended to complex algebraic curves.

0 citations0 reviewsNo code linkedOpen access