Sharp Thresholds for Distance Patterns in Random Subsets of ℤd
Abstract
Let d ≥ 5, 0 < γ< d − 2, and ΩN be the binomial random subset of QN = [−N,N]d ∩ ℤd with retention probability pN = N−γ. We prove that, with failure probability of optimal exponential order, every subset B ⊆ ΩN of fixed positive relative density realizes, at each scale pN−2/(d − 2) ≲ λ≲ N2, a squared distance of the form q2 λ, where q belongs to a fixed finite set depending only on the dimension and the density. The lower scale pN−2/(d − 2) is sharp. As a consequence,the squared-distance set D2(B) of B has maximal order N2 and contains affine copies of every fixed finite subset of ℤ. The main new input is a finite multidilate supersaturation theorem for dense subsets of QN, which, together with boundedness estimates for the associated spherical distance graphs down to the sharp scale, allows us to apply Schacht's transference theorem.
Related
- Very sharp distance and range transitions for random walk bridges on Ramanujan graphs
- Sharp detection thresholds for random geometric graphs with polynomial average degrees
- Nonparametric Regression on Fixed-Cardinality Subsets:Minimax Risk and Random-Design Effects
- Sharp Thresholds for Linear Determinacy and Zero Wave Speed in Lotka-Volterra Competition-Diffusion Systems
- Sharp thresholds and convergence for a nonlocal bistable equation
BibTeX
@misc{giannitsi2026sharp,
title = {{Sharp Thresholds for Distance Patterns in Random Subsets of $\mathbb Z^d$}},
author = {Christina Giannitsi and Eyvindur Ari Palsson},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.36022},
eprint = {2609.36022},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.36022},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Sharp Thresholds for Distance Patterns in Random Subsets of ℤ^d
AU - Christina Giannitsi
AU - Eyvindur Ari Palsson
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.36022
UR - https://arxiv.org/abs/2609.36022
AB - Let d ≥ 5, 0 < γ< d − 2, and Ω_N be the binomial random subset of Q_N = [−N,N]^d ∩ ℤ^d with retention probability p_N = N^−γ. We prove that, with failure probability of optimal exponential order, every subset B ⊆ Ω_N of fixed positive relative density realizes, at each scale p_N^−2/(d − 2) ≲ λ≲ N^2, a squared distance of the form q^2 λ, 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 ℤ. 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.
ER -