Submit progress

on Difference Bases (AlphaEvolve problem 7)

The statement

For any natural number $n$ , let $\Delta(n)$ be the size of the smallest set $B$ of integers such that every natural number from $1$ to $n$ is expressible as a difference of two elements of $B$ (such sets are known as difference bases for the interval $\{1,\dots,n\}$ ). Write $C(n) \coloneqq \Delta^2(n)/n$ , and $C \coloneqq \inf_{n \geq 1} C(n)$ . Establish upper and lower bounds on $C$ that are as strong as possible.

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.