/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/modulepublicimportFormalConjecturesUtil
[Er80] Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math.
6 (1980), 89-115. PDF
[HaRo66] Halberstam, H. and Roth, K. F., Sequences. Vol. I. Oxford University Press, Oxford
(1966), xx+291.
[Le04] Lev, Vsevolod F., Reconstructing integer sets from their representation functions.
Electron. J. Combin. 11 (2004), Research Paper 78, 6 pp.
Link
IsPerfectDifferenceSetInt A says that A is a set of positive integers such that every
nonzero integer is $a - b$ for exactly one pair (a, b) of distinct elements of A. This is the
notion over $\mathbb{Z}$ of [Er80] and [Le04], that is, IsPerfectDifferenceSet A 0
(as ZMod 0 = ℤ).
IsLargerElement A n a says that a is the larger element of a representation
$n = a - b$ with $a, b \in A$. If A is a perfect difference set and $n \geq 1$, there is exactly
one such a, and it is the element $a_n$ of the problem (not the $n$th element of A).
HasLargeElement A f says that $a_n \geq f(n)$ for infinitely many $n$, where $a_n$ is the
larger element of the representation of $n$ as a difference of two elements of A.
Let $A\subset\mathbb{N}$ be such that every integer $n\geq 1$ can be written uniquely as
$a_n-b_n$ for some $a_n,b_n\in A$. How fast must $a_n/n$ increase?
A question of Erdős [Er80, p. 100]. Here $a_n$ is the larger element of the representation of
$n$, not the $n$th element of $A$. We read "must increase" as: the answer is the set of
non-decreasing $G$ such that every such $A$ has $a_n \geq c,n,G(n)$ for infinitely many $n$,
for some $c>0$ depending on $A$.
Such a set is called a perfect difference set; they can be constructed, for example, by a greedy
approach (as detailed by Lev [Le04]).
Erdős [Er80, p. 100] remarks that it is easy to construct such a sequence, and [Le04, Section 3]
constructs a perfect difference set $A\subseteq\mathbb{N}$ (positive integers) greedily.
In the greedy construction of [Le04, Section 3], step $k$ adds $z_k$ and $z_k+d_k$, where $d_k$ is
the least non-negative integer that is not yet a difference and $z_k$ is the least admissible
positive integer. There are $O(k^3)$ excluded choices for $z_k$ and $d_k=O(k^2)$, so every element
added by step $k$ is $O(k^3)$. As $d_1=0$ and the $d_k$ increase, $n$ is represented by step
$n+1$, which gives $a_n\ll n^3$.
Erdős [Er80, p. 100] wrote it is 'easy to see' that
$$\limsup_{n\to \infty}\frac{a_n}{n}=\infty.$$
Indeed, since $A$ must be a Sidon set, if $a_n \leq f(n)n$ for all $n$, then all differences in
$[1,x/f(x)]$ can be realised by differences from $A\cap [1,x]$, and hence
$\lvert A\cap [1,x]\rvert^2 \gg x/f(x)$. Erdős (see for example [HaRo66]) proved that for
infinitely many $x$, $\lvert A\cap [1,x]\rvert \ll (x/\log x)^{1/2}$, which is a contradiction for
a suitable choice of $f$.
Formally: for every perfect difference set $A$ and every $C$, $a_n \geq Cn$ for infinitely many
$n$.