On the determination of sets by their triple correlation in finite cyclic groups

Abstract

Let $G$ be a finite abelian group and $E$ a subset of it. Suppose that we know for all subsets $T$ of $G$ of size up to $k$ for how many $x\in G$ the translate $x+T$ is contained in $E$. This information is collectively called the $k$-deck of $E$. One can naturally extend the domain of definition of the $k$-deck to include functions on $G$. Given the group $G$, when is the $k$-deck of a set in $G$ sufficient to determine the set up to translation? The $2$-deck is not sufficient (even when we allow for reflection of the set, which does not change the $2$-deck) and the first interesting case is $k=3$. We further restrict $G$ to be cyclic and determine the values of $n$ for which the $3$-deck of a subset of ${\mathbb{Z}}_n$ is sufficient to determine the set up to translation. This completes the work begun by Grünbaum and Moore [GM] as far as the $3$-deck is concerned. We additionally estimate from above the probability that for a random subset of ${\mathbb{Z}}_n$, there exists another subset, not a translate of the first, with the same $3$-deck. We give an exponentially small upper bound when the previously known one was $O(1/\sqrt{n})$.