Divot classification for missing differences

At least 5 years old · documented by

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

PnH(k)=Pr⁡(∣S−S∣=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 k≪nk\ll n, the typical diffset size is k(k−1)+1k(k-1)+1.

Divot classification conjecture. For every k>1k>1, k(k−1)+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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.