Difference Bases

The problem

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.

Statement quoted from problem 7 of the AlphaEvolve repository of problems (Google DeepMind, CC BY 4.0).

What AI did

AlphaEvolve found a construction that improved on the best bound known at the time; the problem itself remains open. Status in the repository: New result. See Section 6.3 in "Mathematical Exploration and Discovery at Scale" paper. Records may have moved since; the repository's notes below list the latest bounds it knows of.

How it was checked

The results are explicit constructions or programs; the repository's notebooks include the verification code used to score them.

Limitations

An improved bound is progress, not a solution: the exact answer to the problem is still unknown. The authors report that results were better when experts set up and guided the search.

∎