On Erdős Chains in the Plane

Abstract

Let $P$ be a finite point set in ${\mathbb{R}}^2$ with the set of distance $n$-chains defined as $${\Delta }_n(P)=\{(|p_1-p_2|,|p_2-p_3|,\dots ,|p_n-p_{n+1}|):p_i\in P\}.$$ We show that for $2\le n=O_{|P|}(1)$ we have $$|{\Delta }_n(P)|\gtrsim \frac{|P{|}^n}{{\log }^{\frac{13}{2}(n-1)}|P|}.$$ Our argument uses the energy construction of Elekes and a general version of Rudnev's rich-line bound implicit in Rudnev's recent hinge paper which allows one to iterate efficiently on highly intersecting nested subsets of Guth-Katz lines. Let $G$ is a simple connected graph on $m=O(1)$ vertices with $m\ge 2$. Define the graph-distance set ${\Delta }_G(P)$ as $${\Delta }_G(P)=\{(|p_i-p_j|{)}_{\{i,j\}\in E(G)}:p_i,p_j\in P\}.$$ Combining with results of Guth and Katz and Rudnev with the above, if $G$ has a Hamiltonian path we have $$|{\Delta }_G(P)|\gtrsim \frac{|P{|}^{m-1}}{\text{polylog}|P|}.$$ \end{abstract}

25 pages