Perfect difference sets: how fast must $a_n/n$ grow when every $n$ is uniquely $a-b$? (Erdős #1194)
Statement
Let $A\subset\mathbb{N}$ be such that every integer $n\geq 1$ can be written uniquely as $n=a_n-b_n$ for some $a_n,b_n\in A$ — such an $A$ is called a perfect difference set, and $a_n$ denotes the larger element in the unique representation of $n$. How fast must $a_n/n$ increase? That is, determine the growth that the perfect-difference property forces on $a_n$, ideally with matching lower bounds (for all such $A$) and constructions (witnessing optimality).
Acceptance. FULLY RESOLVES: determine the forced growth of $a_n$ up to $n^{o(1)}$: a proven lower bound valid for every perfect difference set together with a construction (with full proof of the perfect-difference property and its growth) matching it, pinning the optimal exponent; machine-checkable (Lean/Coq) proofs preferred, else complete written proofs. ADVANCES: (a) a proven lower bound strictly stronger than the best stated in the background (state yours precisely and show it beats $n^2/f(n)$ infinitely often for every admissible $f$, or upgrades infinitely-often to all large $n$); (b) any nontrivial for-all-large-$n$ lower bound (e.g. $a_n\gg n^{1+\delta}$ for all large $n$, $\delta>0$ explicit), with proof; (c) a construction with proven $a_n\ll n^{3-\delta}$ for explicit $\delta>0$, strictly better than the greedy bound stated in the background — in particular a fully proved $n^{2+o(1)}$ construction via the Sidon-set transfer would nearly close the gap; (d) reproducible computation of a long initial segment of the greedy perfect difference set with growth diagnostics (code + data), as a calibration artifact. Deliver the proof file(s), or the construction + proofs, or the code + data.
Background
Posed by Erdős [Er80, p.100]; listed as open on erdosproblems.com/1194 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics | additive basis | sidon sets'). Perfect difference sets exist: a greedy construction (detailed by Lev [Le04]) achieves $a_n\ll n^3$. On the lower-bound side, Erdős wrote it is 'easy to see' that $\limsup a_n/n=\infty$: any perfect difference set is a Sidon set, and if $a_n\leq f(n)n$ for all $n$ then all differences in $[1,x/f(x)]$ are realised within $A\cap[1,x]$, giving $\lvert A\cap[1,x]\rvert^2\gg x/f(x)$, which contradicts Erdős's bound (see [HaRo66]) that $\lvert A\cap[1,x]\rvert\ll (x/\log x)^{1/2}$ for infinitely many $x$; this argument yields $a_n\gg n\log n$ for infinitely many $n$. Cilleruelo–Nathanson [CiNa08] give a method for building dense perfect difference sets out of dense Sidon sets, transferring many Sidon-set results. The current record lower bound, recorded in the site remarks and credited to an argument by GPT-5.4 Pro in the problem's comment thread, is $a_n\gg n^{2-o(1)}$ infinitely often — more precisely $a_n\gg n^2/f(n)$ infinitely often for any $f$ with $\sum 1/(nf(n))$ divergent. The frontier gap is thus between $n^{2-o(1)}$ (infinitely often, lower) and $n^3$ (greedy construction, upper), with no nontrivial for-all-$n$ lower bound recorded. Closely related in spirit to the venue problem on the growth of the greedy (Mian–Chowla) Sidon sequence, but the perfect-difference object is different. The attacker's tool: constructions — instantiate the Cilleruelo–Nathanson transfer on dense Sidon sets (e.g. Singer-type) and prove the resulting growth exponent; plus exact computation of greedy perfect difference sets over long ranges to calibrate conjectural growth before proving bounds.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1194 (T. F. Bloom) | website |
| REF-02 | Erdős #1194 discussion thread (contains the GPT-5.4 Pro lower-bound argument) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.