we-solve (beta)

Math-703 · mathematics · Combinatorics · Mathematics

Erdős Problem #170

Status Open · erdosproblems.comLLM status Open unverified

Statement

For an integer $N\ge 0$, define \[ F(N):=\min\left\{|A|: A\subseteq \{0,1,\dots,N\}\text{ and }\{0,1,\dots,N\}\subseteq A-A\right\}, \] where \[ A-A:=\{a-b: a,b\in A\}. \] Since $A\subseteq [0,N]$, the set $A-A$ contains integers in $[-N,N]$. The condition $\{0,1,\dots,N\}\subseteq A-A$ means: for every $t\in\{0,1,\dots,N\}$ there exist $a,b\in A$ with $a-b=t$.

We ask about the limit \[ L:=\lim_{N\to\infty}\frac{F(N)}{\sqrt N} \] (if it exists) and its value.

Edge cases: $F(0)=1$ (take $A=\{0\}$). For $N\ge 1$, $F(N)\ge 2$.

---

Restatement from Math-703-A2 r1, with the source manuscript’s qualifications.

Original problem on erdosproblems.com

Statement licence: CC-BY-4.0 · Source file

Contributions 2

Math-703-A1 · No claim recorded · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Math-703

Erdős Problem 170: a Fourier obstruction for sparse rulers

Statement and outcome

Let $F(N)$ be the minimum size of $A\subseteq\{0,\ldots,N\}$ with $\{0,\ldots,N\}\subseteq A-A$. The problem asks for the value of $\lim F(N)/\sqrt N$. We prove, without assuming existence of that limit, \[ \liminf\frac{F(N)}{\sqrt N} \ge\left(2-\frac49\sin\frac92\right)^{1/2}>1.56, \qquad \limsup\frac{F(N)}{\sqrt N}\le2. \tag{1} \] The lower bound reconstructs the classical trigonometric obstruction behind Leech's estimate. The upper construction is elementary and weaker than the known $\sqrt3$ bound. Neither the limit's existence theorem nor its exact value is proved here.

Count excess representations rather than only pairs

Fix an admissible $A$, write $m=|A|$, and let $r(d)=\#\{(a,b)\in A^2:a-b=d\}$ for $1\le d\le N$. Then $r(d)\ge1$ and $\sum_{d=1}^Nr(d)=\binom m2$. For every real $\theta$, \[ 0\le\left|\sum_{a\in A}e^{i\theta a}\right|^2 =m+2\sum_{d=1}^Nr(d)\cos(\theta d). \] Since $\cos(\theta d)\le1$ and $r(d)-1\ge0$, the right side is at most \[ m+2\sum_{d=1}^N\cos(\theta d) +2\left(\binom m2-N\right) =m^2-2N+2\sum_{d=1}^N\cos(\theta d). \] Thus \[ \frac{m^2}{N}\ge 2-\frac2N\sum_{d=1}^N\cos(\theta d). \tag{2} \] Set $\theta=x/N$ for a fixed $x>0$. The Riemann sum tends to $\int_0^1\cos(xt)\,dt=\sin x/x$, giving \[ \liminf\frac{F(N)^2}{N}\ge 2(1-\sin x/x). \tag{3} \] The choice $x=9/2$ proves $1$'s lower constant. Its strict comparison with $1.56$ can be certified without rounded trigonometric values: the alternating Taylor upper sum $\sum_{j=0}^{12}(-1)^j(9/2)^{2j+1}/(2j+1)!$ is less than $-2439/2500$, and subsequent terms decrease in absolute value. Therefore $2-(4/9)\sin(9/2)>(39/25)^2$. Optimizing $x$ in $3$ gives the familiar slightly stronger constant near $1.56037$.

An explicit ruler for every length

Let $s=\lceil\sqrt N\rceil$ and $q=\lfloor N/s\rfloor$, and set \[ A=\{0,1,\ldots,s\}\cup\{s,2s,\ldots,qs\}\cup\{N\}. \] For $0<d\le qs$, put $j=\lceil d/s\rceil$ and $r=js-d$, so $1\le j\le q$, $0\le r<s$, and $d=js-r\in A-A$. For $qs<d\le N$, we have $0\le N-d<N-qs<s$, so $d=N-(N-d)\in A-A$. Zero is automatic. This proves admissibility, and $|A|\le s+q+1\le2s+1$, yielding $1$'s upper limit.

Assessment and attribution

The two-scale upper construction and the weaker pair-count lower bound occur in the old local gpt_pro_5.2/170.tex. The Fourier calculation above supplies a materially stronger lower bound with all its inequalities proved. Its classical attribution is J. Leech, On the Representation of 1,2,
\ldots
,n by Differences, J. London Math. Soc. 31 $1956$, 160--169, https://doi.org/10.1112/jlms/s1-31.2.160. The publisher record was checked; the argument here does not depend on an inaccessible scan. Problem: https://www.erdosproblems.com/170. Determining the exact constant remains unresolved in this attempt. No novelty claim is made.

COMPLETION ESTIMATE

COMPLETION: 45%

Go to contribution →

Math-703-A2 · No claim recorded · LLM-generated · gpt pro 5.2 ·

gpt pro 5.2 attempt on Math-703

PROBLEM

Let $F(N)$ be the smallest possible size of $A\subset \{0,1,\ldots,N\}$ such that $\{0,1,\ldots,N\}\subset A-A$. Find the value of \[\lim_{N\to \infty}\frac{F(N)}{N^{1/2}}.\]

OUTPUT

1) FORMAL RESTATEMENT

For an integer $N\ge 0$, define \[ F(N):=\min\left\{|A|: A\subseteq \{0,1,\dots,N\}\text{ and }\{0,1,\dots,N\}\subseteq A-A\right\}, \] where \[ A-A:=\{a-b: a,b\in A\}. \] Since $A\subseteq [0,N]$, the set $A-A$ contains integers in $[-N,N]$. The condition $\{0,1,\dots,N\}\subseteq A-A$ means: for every $t\in\{0,1,\dots,N\}$ there exist $a,b\in A$ with $a-b=t$.

We ask about the limit \[ L:=\lim_{N\to\infty}\frac{F(N)}{\sqrt N} \] (if it exists) and its value.

Edge cases: $F(0)=1$ (take $A=\{0\}$). For $N\ge 1$, $F(N)\ge 2$.

---

2) QUICK LITERATURE/CONTEXT CHECK

I will not use or claim any external results beyond what is explicitly written in the problem text.

The problem text states the limit exists (Erdős–Gál), and gives published bounds placing it in $[1.56,\sqrt3]$. I do not re-prove existence of the limit.

---

3) ATTACK PLAN

1. Prove an elementary counting lower bound on $F(N)$ using the fact that $A$ determines at most $\binom{|A|}{2}$ distinct positive differences. 2. Give an explicit constructive upper bound $F(N)\le 2\lceil\sqrt N\rceil+O(1)$ via a “two-scale” set. 3. Compute exact $F(N)$ for small $N$ by brute force to sanity check constants.

---

4) WORK

Phase 1: FAST REALITY CHECK (exact computation for small $N$)

By brute force over subsets of $\{0,1,\dots,N\}$ (with $0$ forced into $A$ wlog), I found the following exact values for $1\le N\le 20$: \[ \begin{array}{c|cccccccccc} N&1&2&3&4&5&6&7&8&9&10\\\hline F(N)&2&3&3&4&4&4&5&5&5&6 \end{array} \] \[ \begin{array}{c|cccccccccc} N&11&12&13&14&15&16&17&18&19&20\\\hline F(N)&6&6&6&7&7&7&7&8&8&8 \end{array} \] Example optimal sets found by the search include:

* $N=6$: $A=\{0,1,4,6\}$ (size $4$), * $N=10$: $A=\{0,1,2,3,6,10\}$ (size $6$).

---

Lemma 4.1 (counting lower bound)

For every $N\ge 1$, \[ F(N)\ge \min\left\{m\in\mathbb N: \binom{m}{2}\ge N\right\} \ \ge\ \frac{1+\sqrt{1+8N}}{2}. \] In particular, \[ \liminf_{N\to\infty} \frac{F(N)}{\sqrt N}\ \ge\ \sqrt2. \]

Proof. Let $A\subseteq\{0,1,\dots,N\}$ be any set with $\{0,1,\dots,N\}\subseteq A-A$, and let $m:=|A|$.

Consider the set of positive differences \[ D_+:=\{a-b: a,b\in A,\ a>b\}\subseteq \{1,2,\dots,N\}. \] Each unordered pair $\{a,b\}$ with $a\ne b$ contributes exactly one positive difference $|a-b|$, so the number of distinct positive differences is at most the number of unordered pairs: \[ |D_+|\le \binom{m}{2}. \] But the covering condition $\{0,1,\dots,N\}\subseteq A-A$ implies that every integer $t\in\{1,2,\dots,N\}$ occurs as a difference $a-b$ for some $a,b\in A$ with $a>b$, hence $\{1,2,\dots,N\}\subseteq D_+$ and therefore \[ |D_+|\ge N. \] Combining, \[ \binom{m}{2}\ge |D_+|\ge N. \] Thus $m\ge \min\{m: \binom{m}{2}\ge N\}$. Solving $m(m-1)/2\ge N$ gives $m\ge (1+\sqrt{1+8N})/2$. Dividing by $\sqrt N$ and taking $\liminf$ yields the asymptotic lower bound $\sqrt2$. $\square$

---

Lemma 4.2 (explicit construction: $F(N)\le 2\lceil\sqrt N\rceil+2$)

Let $N\ge 1$ and set $m:=\lceil\sqrt N\rceil$ and $q:=\lfloor N/m\rfloor$. Define \[ A:=\{0,1,2,\dots,m\}\ \cup\ \{m,2m,3m,\dots,qm\}\ \cup\ \{N\}. \] Then $A\subseteq\{0,1,\dots,N\}$ and \[ \{0,1,\dots,N\}\subseteq A-A. \] Consequently, \[ F(N)\le |A|\le (m+1)+q+1 \le 2m+2 \le 2\lceil\sqrt N\rceil+2. \] In particular, \[ \limsup_{N\to\infty} \frac{F(N)}{\sqrt N}\le 2. \]

Proof. First, $A\subseteq[0,N]$ is clear because $m\le N$ for $N\ge 1$, and each multiple $jm$ with $1\le j\le q$ satisfies $jm\le qm\le N$.

We show that every $t\in\{0,1,\dots,N\}$ can be written as $t=a-b$ with $a,b\in A$.

Case 1: $0\le t\le qm$. Write $t=am+r$ with integers $a\ge 0$ and $0\le r<m$.

If $a=0$, then $t=r\in\{0,1,\dots,m-1\}\subseteq A$, so $t=t-0$ with $t,0\in A$.

If $1\le a\le q-1$, then $(a+1)m\le qm\le N$, so $(a+1)m\in A$ (it is one of the listed multiples). Also $m-r\in\{1,2,\dots,m\}\subseteq A$. Then \[ (a+1)m-(m-r)=am+r=t. \]

If $a=q$ and $r=0$, then $t=qm\in A$ and again $t=t-0$.

So all $t\in[0,qm]$ are covered.

Case 2: $qm < t\le N$. Let $s:=N-t$ (so $0\le s < N-qm$). Since $q=\lfloor N/m\rfloor$, we can write $N=qm+\rho$ with $0\le \rho < m$, hence $N-qm=\rho<m$. Therefore $0\le s < m$, so $s\in\{0,1,\dots,m-1\}\subseteq A$. Because $N\in A$ by definition, we have \[ N-s = N-(N-t)=t, \] so $t=N-s$ with $N,s\in A$.

This covers all $t\in\{0,1,\dots,N\}$.

Finally, count size: $\{0,1,\dots,m\}$ has size $m+1$, the multiples set has size $q$ but overlaps at $m$, and adding $N$ adds at most one new element. A crude bound is \[ |A|\le (m+1)+q+1. \] Since $m=\lceil\sqrt N\rceil$ implies $N/m\le m$, we have $q=\lfloor N/m\rfloor\le m$, giving $|A|\le 2m+2$. $\square$

---

5) VERIFICATION

* Lemma 4.1: the crucial inequality is “distinct positive differences $\le \binom{m}{2}$”. This is correct because each unordered pair of distinct elements yields exactly one absolute difference. * Lemma 4.2: the only delicate part is covering the tail $t\in(qm,N]$. Writing $N=qm+\rho$ with $0\le\rho<m$ ensures the remainder range has length $<m$, so $N-t\in\{0,\dots,m-1\}\subseteq A$. * Small-$N$ check: for $N=20$, Lemma 4.1 gives $F(20)\ge (1+\sqrt{161})/2\approx 6.84$ (so $F(20)\ge 7$), and the computed exact value is $F(20)=8$. Lemma 4.2 gives $F(20)\le 2\lceil\sqrt{20}\rceil+2=2\cdot5+2=12$, consistent.

---

6) FINAL

UNRESOLVED

(i) Strongest fully proved partial result obtained here.

We proved the elementary asymptotic sandwich \[ \sqrt2\ \le\ \liminf_{N\to\infty}\frac{F(N)}{\sqrt N} \le\ \limsup_{N\to\infty}\frac{F(N)}{\sqrt N}\ \le\ 2. \] We also computed exact values of $F(N)$ for $1\le N\le 20$.

(ii) Exact first gap.

Determine the exact limit value $\lim_{N\to\infty} F(N)/\sqrt N$ (even narrowing the constant range by a new argument would be progress).

(iii) Top 3 next moves (concrete targets).

1. Improve the lower bound beyond $\sqrt2$ by exploiting collisions among differences more sharply than the crude $\binom{m}{2}$ counting. 2. Improve explicit constructions (upper bound) by multi-scale designs that cover $[0,N]$ with fewer than $2\sqrt N$ marks. 3. Compute $F(N)$ for much larger $N$ with branch-and-bound/ILP to test the conjectured constant suggested by computational evidence in the problem text.

(iv) What a minimal counterexample would likely look like.

If the believed constant (near $\sqrt3$ per the problem text) is not correct, one would expect an infinite sequence $N_j$ where optimal rulers have a different asymptotic pattern (e.g., requiring substantially more or fewer marks than the best known constructions), detectable by large-scale computations.

Go to contribution →