A note on the distinct distances problem over finite fields

2025/10/13 by Brukhim, Nataly, Bruner, Ariel, Raz, Orit E.
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2510.10869

Abstract

We study a finite-field analogue of the Erdős distinct distances problem under the Hamming metric. For a set \(S⊆ \mathbbF_qⁿ\) let Δ(S) denote the set of Hamming distances determined by \(S\). We prove the lower bound |Δ(S)| ≥ (log |S|)/(2log(2nq)), and show this bound is tight when \(|S|=O(poly(n))\), where the constant of proportionality depends only on q. We then also study the problem of finding a large rainbow set, that is, a subset \(S⊆ \mathbbF_qⁿ\) for which all \(\binom|S|2\) pairwise Hamming distances spanned by S are distinct. In contrast to the Euclidean setting, we show that a set with many distinct distances does not imply the existence of a large rainbow set, by giving an explicit construction. Nevertheless, we establish the existence of large rainbow sets, and prove that every large set in \(\mathbbF_qⁿ\) necessarily contains a non-trivial rainbow subset.

Citations

• Unit and distinct distances in typical norms
• Distinct distances on non-ruled surfaces and between circles
• Hamming Distances in Vector Spaces over Finite Fields
• Distinct Distances: Open Problems and Current Bounds

Related

• Hamming Distances in Vector Spaces over Finite Fields
• The Erdős-Falconer distance problem between arbitrary sets and k-coordinatable sets in finite fields
• Note on the pinned distance problem over finite fields
• Structural theorems on the distance sets over finite fields
• Distinct Distances: Open Problems and Current Bounds