Sharp Thresholds for Distance Patterns in Random Subsets of ${\mathbb{Z}}^d$

Abstract

Let $d\ge 5$, $0<\gamma <d-2$, and ${\Omega }_N$ be the binomial random subset of $Q_N=[-N,N{]}^d\cap {\mathbb{Z}}^d$ with retention probability $p_N=N^{-\gamma }$. We prove that, with failure probability of optimal exponential order, every subset $B\subseteq {\Omega }_N$ of fixed positive relative density realizes, at each scale $p_N^{-2/(d-2)}\lesssim \lambda \lesssim N^2$, a squared distance of the form $q^2\lambda$, where $q$ belongs to a fixed finite set depending only on the dimension and the density. The lower scale $p_N^{-2/(d-2)}$ is sharp. As a consequence,the squared-distance set $D^2(B)$ of $B$ has maximal order $N^2$ and contains affine copies of every fixed finite subset of $\mathbb{Z}$. The main new input is a finite multidilate supersaturation theorem for dense subsets of $Q_N$, which, together with boundedness estimates for the associated spherical distance graphs down to the sharp scale, allows us to apply Schacht's transference theorem.