Perfect difference families, perfect systems of difference sets and their applications

Abstract

Let $v$ be a positive odd integer. A $(v,k,\hat{I}»)$-perfect difference family (PDF) is a collection $\mathcal{F}$ of $k$-subsets of $\{0,1,\dots ,v-1\}$ such that the multiset ${\bigcup }_{F\in \mathcal{F}}\{x-y:x,y\in F,x>y\}$ covers each element of $\left\{1,2,\dots ,(v-1)/2\right\}$ exactly $\hat{I}»$ times. Perfect difference families are a special class of perfect systems of difference sets. They were introduced by Bermond, Kotzig, and Turgeon in the 1970s, following a problem suggested by Erdős. In this paper, we prove that a $(v,4,\hat{I}»)$-PDF exists if and only if $\hat{I}»(v-1)\equiv 0(\mathrm{mod}12)$, $v\ge 13$, and $(v,\hat{I}»)\notin \{(25,1),(37,1)\}$. This result resolves a nearly 50-year-old conjecture posed by Bermond. Perfect difference families find applications in radio astronomy, optical orthogonal codes for optical code-division multiple access systems, geometric orthogonal codes for DNA origami, difference triangle sets, additive sequences of permutations, and graceful graph labelings. To establish our main result, we introduce a new concept termed a layered difference family. This concept provides a powerful and unified perspective that not only facilitates our proof of the main theorem but also simplifies recent existence proofs for various cyclic difference packings.

32 pages