Arithmetic subsequences in a random ordering of an additive set

Abstract

For a finite set $A$ of size $n$, an ordering is an injection from $\{1,2,\dots ,n\}$ to $A$. We present results concerning the asymptotic properties of the length $L_n$ of the longest arithmetic subsequence in a random ordering of an additive set $A$. In the torsion-free case where $A=[1,n{]}^d\subseteq {\mathbf{Z}}^d$, we prove that $L_n\sim 2d\log n/\log \log n$. We show that the case $A=\mathbf{Z}/n\mathbf{Z}$ behaves asymptotically like the torsion-free case with $d=1$, and then use this fact to compute the expected length of the longest arithmetic subsequence in a random ordering of an arbitrary finite abelian group. We also prove that the number of orderings of $\mathbf{Z}/n\mathbf{Z}$ without any arithmetic subsequence of length $3$ is $2^{n-1}$ when $n\ge 2$ is a power of $2$, and zero otherwise. We conclude with a concrete application to elementary $p$-groups and a discussion of possible noncommutative generalisations.

15 pages, 2 tables. Various edits to match journal version