A note on the distinct distances problem over finite fields

We study a finite-field analogue of the Erdős distinct distances problem under the Hamming metric. For a set $S\subseteq {\mathbb{F}}_q^n$ let $\mathrm{\Delta }(S)$ denote the set of Hamming distances determined by $S$. We prove the lower bound $$\mathrm{\mid }\mathrm{\Delta }(S)\mathrm{\mid }\ge \frac{\log \mathrm{\mid }S\mathrm{\mid }}{2\log (2nq)},$$ and show this bound is tight when $\mathrm{\mid }S\mathrm{\mid }=O(\text{poly}(n))$, where the constant of proportionality depends only on $q$. We then also study the problem of finding a large \emph{rainbow set}, that is, a subset $S\subseteq {\mathbb{F}}_q^n$ for which all $\left(\genfrac{}{}{0px}{}{\mathrm{\mid }S\mathrm{\mid }}{2}\right)$ 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 ${\mathbb{F}}_q^n$ necessarily contains a non-trivial rainbow subset.