Divot classification for missing differences

From papers

Let SS be chosen uniformly at random from [n]={0,1,,n1}[n]=\{0,1,\dots,n-1\}. Write

PnH(k)=Pr(SS=k)P_n^{\mathrm{H}}(k)=\Pr\bigl(|S-S|=k\bigr)

for the probability that the diffset has size kk, and call kk a divot when its probability is lower than the neighboring values in the distribution. For knk\ll n, the typical diffset size is k(k1)+1k(k-1)+1.

Divot classification conjecture. For every k>1k>1, k(k1)+3k(k-1)+3 is a divot of PnHP_n^{\mathrm{H}} for sufficiently large nn. Furthermore, these are the only divots.

The conjecture predicts the complete pattern of divots in the distribution of diffset sizes when the selected-set size is small relative to nn. The source gives no resolution status.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Scott Harvey-Arnold, Steven J. Miller and Fei Peng, “Distribution of missing differences in diffsets”, arXiv:2001.08931 (2020).

Solutions 0

No solutions have been posted yet.