---

Claim. Let $F(N)$ be the least size of a set $A\subseteq\{0,1,\ldots,N\}$ with $\{0,1,\ldots,N\}\subseteq A-A$, the quantity Problem 170 asks about. Then $F(N)/\sqrt N$ converges as $N\to\infty$. This is part $1^\circ$ of the Theorem of P. Erdős and I. S. Gál, On the representation of $1,2,\ldots,N$ by differences, Nederl. Akad. Wetensch., Proc. 51 (1948), no. 9, 1155--1158, reprinted as Indag. Math. 10 (1948), fasc. 5, 379--382, communicated at the meeting of 30 October 1948, cited as [ErGa48] on the problem page (card). The paper's $n_0=\min l(n)$, the least number of terms of a restricted difference basis with respect to $n$ in Brauer's sense, is $F(n)$, and the convergence of $n_0/\sqrt n$ is the question Rédei asked, as the paper and the site's commentary record. The proof covers $\{0,\ldots,N\}$ by the differences of a union of two sets, a dilated copy of a minimal basis for a smaller $n$ with a Singer perfect difference set modulo $p^2+p+1$ added, and two short tails, $0,1,\ldots,[\sqrt M]$ at the bottom end and $N,N-[\sqrt M],\ldots,N-([\sqrt M]+1)[\sqrt M]$ at the top end, and chooses the prime $p$ by the prime number theorem; the same construction, with the restriction $0\le a_i\le n$ dropped, gives the paper's new proof of Rédei and Rényi's results for unrestricted bases.

The Theorem has two further parts, which this page does not cover. Part $2^\circ$ asserts $\lim n_0/\sqrt n=\inf_n n_0/\sqrt n$, and part $3^\circ$, through $2^\circ$ and the basis $\{0,1,4,6\}$ for $n=6$, asserts $\sqrt{2+4/(3\pi)}\le\lim n_0/\sqrt n\le\sqrt{8/3}$. The printed argument has a slip: on p. 1157 the covering step sets $N-M+1=nm+1$, while the paper's own equation (2), $M=N-(n+1)(p^2+p+1)$ with $m=p^2+p+1$, gives $N-M+1=(n+1)m+1$, so the differences strictly between $nm$ and $(n+1)m$ are not shown to be represented. The slip sits in the argument the paper gives for $1^\circ$ and $2^\circ$ together. The identification in $2^\circ$ would put the limit at most $4/\sqrt6=\sqrt{8/3}=1.633\ldots$, below Wichmann's upper bound $\sqrt3$ ([[problems/additive_combinatorics/E0170/claims/1963_01_01_wichmann|his claim page]]) and against the computational evidence the site records that $\sqrt3$ is the value. The existence of the limit is the part the site's commentary and the formal-conjectures catalog credit to the paper, and it is the only part recorded here.

Covers. The existence of $\lim_{N\to\infty}F(N)/\sqrt N$, Rédei's question. Not covered: the value of the limit, which the problem asks for; the paper's identification of the limit with $\inf_n n_0/\sqrt n$; and its numerical bounds $\sqrt{2+4/(3\pi)}$ and $\sqrt{8/3}$, which rest on that identification.

Depends on. Nothing in this wiki: the construction is the paper's own, with Singer's perfect difference sets and the prime number theorem as its cited inputs.

Acceptance. Refereed: the paper appeared in the Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen, volume 51 (1948), no. 9, 1155--1158, and in Indagationes Mathematicae, volume 10 (1948), fasc. 5, 379--382, the Rényi Institute's copy linked above; the corpus treats Indagationes Mathematicae (Proceedings) as a journal publication, and the page is named by the communication date the paper prints. Reviewed is not listed: the site labels the problem OPEN, and its commentary crediting the existence of the limit to Erdős and Gál is commentary on an open problem, not acceptance of a solution. Formalized is not listed: the formal-conjectures catalog states the existence of the limit, within Leech's and Wichmann's bounds, as the lemma erdos170.existing_bounds of its file for the problem, pinned above, and marks it research solved, but states it without a proof, and this corpus has built no proof of it.