Erdős Problem #1097

Erdős Problem 1097 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/1097

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/1097.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/1097.tex.

FORMAL RESTATEMENT

Let $A\subset\mathbb{Z}$ be a finite set with $|A|=n$. Define the set of (positive) three-term AP differences \[ D(A):=\{d\in\mathbb{Z}_{>0}:\ \exists a\in\mathbb{Z}\text{ such that }a,a+d,a+2d\in A\}. \] (The problem statement does not specify whether $d$ can be negative; counting positive differences avoids a factor of $2$ and excludes the trivial $d=0$.)

Question. Determine the maximal possible size of $D(A)$ over all $n$-element sets $A\subset\mathbb{Z}$. In particular, is it always true that \[ |D(A)|=O\left(n^{3/2}\right) \] for all such $A$?

QUICK LITERATURE/CONTEXT CHECK

The problem text states that Erdős had constructions giving $n^{1+c}$ and a probabilistic construction giving $n^{3/2}$, and relates the question to a sum-differences inequality connected to Kakeya-type problems. Per the integrity rule for this task, I do not assert any additional literature beyond what is written in the problem file.

ATTACK PLAN

• Prove easy general bounds: $|D(A)|\le |A-A|\le n^2$.
• Produce an explicit existence lower bound $|D(A)|\gg n^{3/2}$ by a self-contained probabilistic argument (showing that $n^{3/2}$ is attainable up to constants).
• Do small-$n$ computations to sanity-check how $\max|D(A)|$ behaves at very small scales.

WORK

Lemma 1097.1 (trivial upper bound). For every finite $A\subset\mathbb{Z}$ with $|A|=n$, \[ |D(A)|\le |A-A|\le n^2. \]

Proof. If $d\in D(A)$, then there exist $a,a+d\in A$, hence $d=(a+d)-a\in A-A$. Thus $D(A)\subseteq (A-A)\cap\mathbb{Z}_{>0}$ and $|D(A)|\le |A-A|$.

Also, $A-A=\{x-y:x\in A,y\in A\}$ is the image of the map $A\times A\to\mathbb{Z}$ given by $(x,y)\mapsto x-y$, so $|A-A|\le |A\times A|=n^2$. $\square$

Lemma 1097.2 (interval example). If $A=\{0,1,2,\dots,n-1\}$, then \[ |D(A)|=\left\lfloor\frac{n-1}{2}\right\rfloor. \]

Proof. A positive integer $d$ belongs to $D(A)$ iff there exists $a\in\{0,\dots,n-1\}$ such that $a+2d\le n-1$, i.e. iff $2d\le n-1$. Thus $d\in\{1,2,\dots,\lfloor (n-1)/2\rfloor\}$ and all such $d$ occur (take $a=0$). $\square$

Lemma 1097.3 (probabilistic lower bound $\gg n^{3/2}$). There exists an absolute constant $c>0$ such that for all sufficiently large integers $n$, there exists a set $A\subset\mathbb{Z}$ with $|A|=n$ and \[ |D(A)|\ge c\,n^{3/2}. \]

Proof. Let $N:=\lfloor n^{3/2}\rfloor$ and consider a random subset $A\subseteq\{1,2,\dots,N\}$ chosen uniformly among all subsets of size $n$.

For each integer $d$ with $1\le d\le \lfloor N/4\rfloor$, define the random variable \[ X_d := \#\{a\in\mathbb{Z}:\ 1\le a\le N-2d,\ a,a+d,a+2d\in A\}, \] the number of three-term arithmetic progressions in $A$ with common difference $d$. Then $d\in D(A)$ exactly when $X_d\ge 1$.

Step 1: first moment lower bound. For each fixed $a$ with $1\le a\le N-2d$, the triple $\{a,a+d,a+2d\}$ lies in $A$ with probability \[ \mathbb{P}(\{a,a+d,a+2d\}\subseteq A)=\frac{\binom{N-3}{n-3}}{\binom{N}{n}}=\frac{n(n-1)(n-2)}{N(N-1)(N-2)}=:P_3. \] Therefore \[ \mu_d:=\mathbb{E}[X_d]=(N-2d)P_3. \] For $d\le N/4$ we have $N-2d\ge N/2$. Also, for $n\ge 4$ and $N\ge 2n$, \[ P_3=\frac{n(n-1)(n-2)}{N(N-1)(N-2)}\ge \frac{n\cdot (n/2)\cdot (n/2)}{N^3}=\frac{n^3}{4N^3}. \] Hence for $d\le N/4$, \[ \mu_d\ge \frac{N}{2}\cdot \frac{n^3}{4N^3}=\frac{n^3}{8N^2}. \] Because $N=\lfloor n^{3/2}\rfloor$, we have $N^2\le n^3$, so $\mu_d\ge 1/8$ for all large $n$ (in particular once $N\ge 2n$).

Step 2: second moment upper bound. Write $X_d=\sum_{a=1}^{N-2d} I_a$ where $I_a$ is the indicator that $\{a,a+d,a+2d\}\subseteq A$. Then \[ \mathbb{E}[X_d^2]=\sum_a \mathbb{E}[I_a] + 2\sum_{a<b}\mathbb{E}[I_a I_b]. \] If two progressions with the same difference $d$ start at $a$ and $b$, their point-sets overlap only when $b-a\in\{d,2d\}$:

• If $b=a+d$, the union has $4$ distinct points $\{a,a+d,a+2d,a+3d\}$.
• If $b=a+2d$, the union has $5$ distinct points $\{a,a+d,a+2d,a+3d,a+4d\}$.
• Otherwise the two triples are disjoint, so the union has $6$ distinct points.

For a fixed $t$-point set $T\subseteq\{1,\dots,N\}$, the probability that $T\subseteq A$ equals \[ P_t:=\frac{\binom{N-t}{n-t}}{\binom{N}{n}}=\frac{n(n-1)\cdots (n-t+1)}{N(N-1)\cdots (N-t+1)}. \] Thus $\mathbb{E}[I_a I_b]$ is $P_4$, $P_5$, or $P_6$ according to overlap type.

Counting pairs: there are at most $N$ pairs of the form $(a,a+d)$ and at most $N$ of the form $(a,a+2d)$, while the total number of pairs $(a,b)$ is at most $N^2/2$. Hence \[ \mathbb{E}[X_d^2]\le (N-2d)P_3 + 2N P_4 + 2N P_5 + N^2 P_6. \] Now note that for $N\ge 2n$ and fixed $t$, we have the crude upper bound $P_t\le (n/N)^t$ (each factor $(n-j)/(N-j)\le n/N$). Therefore \[ 2N P_4 \le 2N\left(\frac{n}{N}\right)^4=2\frac{n^4}{N^3},\qquad 2N P_5 \le 2\frac{n^5}{N^4},\qquad N^2 P_6\le \frac{n^6}{N^4}. \] Since $N\asymp n^{3/2}$, the three error terms are respectively $O(n^{-1/2})$, $O(n^{-1})$, and $O(1)$ as $n\to\infty$. Moreover, the leading term is $\mu_d=(N-2d)P_3=\Theta(1)$ (from Step 1). Consequently there exists an absolute constant $C$ such that for all sufficiently large $n$ and all $d\le N/4$, \[ \mathbb{E}[X_d^2]\le C(\mu_d+\mu_d^2). \]

Step 3: Paley--Zygmund to get $\mathbb{P}(X_d\ge 1)$ bounded below. Since $X_d\ge 0$, Paley--Zygmund gives \[ \mathbb{P}(X_d>0)\ge \frac{\mu_d^2}{\mathbb{E}[X_d^2]}\ge \frac{\mu_d^2}{C(\mu_d+\mu_d^2)}=\frac{\mu_d}{C(1+\mu_d)}. \] From Step 1 we have $\mu_d\ge 1/8$ for all $d\le N/4$ and all sufficiently large $n$, so $\mathbb{P}(X_d>0)\ge c_0$ for some absolute $c_0>0$ independent of $d$.

Step 4: expected number of good differences. Let $Y:=\#\{d\in\{1,\dots,\lfloor N/4\rfloor\}:\ X_d>0\}$. Then by linearity of expectation, \[ \mathbb{E}[Y]=\sum_{d=1}^{\lfloor N/4\rfloor} \mathbb{P}(X_d>0)\ge c_0\,\frac{N}{4}. \] Therefore there exists at least one choice of $A$ (of size exactly $n$) such that $Y\ge c_0 N/4$. Since each such $d$ lies in $D(A)$, we get \[ |D(A)|\ge Y\ge \frac{c_0}{4}N\ge c\,n^{3/2} \] for $c:=c_0/5$ (absorbing the floor in $N=\lfloor n^{3/2}\rfloor$). This proves the lemma. $\square$

FAST REALITY CHECK (small $n$ exhaustive + random tests).

Exhaustive search in small universes. Restricting to $A\subseteq\{0,1,\dots,2n\}$ and searching over all $n$-subsets gave the following maxima: \[ \begin{array}{r|r|l} n & \max |D(A)| & \text{one maximizer }A\subseteq\{0,\dots,2n\} \\\hline 3&1&(0,1,2)\\ 4&2&(0,1,2,4)\\ 5&3&(0,1,2,4,7)\\ 6&4&(0,1,2,4,5,8)\\ 7&6&(0,1,2,4,7,8,14)\\ 8&8&(0,2,4,5,8,9,10,16) \end{array} \] (These are only sanity checks in a restricted search space.)

Random sets. For $n\in\{20,50,100,200\}$, choosing $A$ uniformly at random of size $n$ from $\{1,\dots,\lfloor n^{3/2}\rfloor\}$, the mean values of $|D(A)|$ over $30$ trials were approximately: \[ \begin{array}{r|r|r} n & N=\lfloor n^{3/2}\rfloor & \text{mean }|D(A)| \\\hline 20&89&14.53\\ 50&353&61.17\\ 100&1000&172.9\\ 200&2828&502.47 \end{array} \]

VERIFICATION

• Lemma 1097.1 and Lemma 1097.2 are direct and check all quantifiers.
• In Lemma 1097.3, Step 2 uses an overlap classification specific to progressions with fixed difference $d$. The fact that overlaps occur only for shifts by $d$ or $2d$ was checked by direct inspection of the triple sets.
• The probabilistic argument produces a set $A$ of size exactly $n$ (uniform $n$-subset model), so no later size adjustment is needed.

UNRESOLVED

(i) Strongest proved partial result here. We proved a general upper bound $|D(A)|\le n^2$ (Lemma 1097.1) and a self-contained probabilistic lower bound showing that $|D(A)|\ge c n^{3/2}$ is achievable for some absolute $c>0$ (Lemma 1097.3).

(ii) First gap (crisp). Prove the conjectured upper bound $|D(A)|=O(n^{3/2})$ for all $n$-element integer sets $A$.

(iii) Top 3 next moves.

1. Try to rephrase the set of differences as an incidence problem (triples $a,a+d,a+2d$) and apply sharp incidence bounds or additive-energy inequalities to bound the number of realizable $d$.
2. Investigate extremal constructions suggested by the probabilistic lower bound (random sets in $[1,n^{3/2}]$) and by structured sum-product sets, to understand what features maximize the number of realized differences.
3. Extend exact computations for small $n$ with larger search spaces (or integer programming) to guess extremal configurations and guide conjectures about the sharp constant/exponent.

(iv) Minimal counterexample structure. A counterexample to the $O(n^{3/2})$ conjecture would be a family of sets $A_n$ with $|A_n|=n$ and $|D(A_n)|\ge n^{3/2+\eta}$ for some fixed $\eta>0$. Such a family would have an unusually large set of differences $d$ each supporting at least one 3-term progression, suggesting strong additive structure (many solutions to $x+z=2y$) without forcing $A_n$ to be too dense in an interval.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

FORMAL RESTATEMENT

Let $A\subset\mathbb{Z}$ be a finite set with $|A|=n$. Define the set of (positive) three-term AP differences \[ D(A):=\{d\in\mathbb{Z}_{>0}:\ \exists a\in\mathbb{Z}\text{ such that }a,a+d,a+2d\in A\}. \] (The problem statement does not specify whether $d$ can be negative; counting positive differences avoids a factor of $2$ and excludes the trivial $d=0$.)

Question. Determine the maximal possible size of $D(A)$ over all $n$-element sets $A\subset\mathbb{Z}$. In particular, is it always true that \[ |D(A)|=O\left(n^{3/2}\right) \] for all such $A$?

QUICK LITERATURE/CONTEXT CHECK

The problem text states that Erdős had constructions giving $n^{1+c}$ and a probabilistic construction giving $n^{3/2}$, and relates the question to a sum-differences inequality connected to Kakeya-type problems. Per the integrity rule for this task, I do not assert any additional literature beyond what is written in the problem file.

ATTACK PLAN

• Prove easy general bounds: $|D(A)|\le |A-A|\le n^2$.
• Produce an explicit existence lower bound $|D(A)|\gg n^{3/2}$ by a self-contained probabilistic argument (showing that $n^{3/2}$ is attainable up to constants).
• Do small-$n$ computations to sanity-check how $\max|D(A)|$ behaves at very small scales.

WORK

Lemma 1097.1 (trivial upper bound). For every finite $A\subset\mathbb{Z}$ with $|A|=n$, \[ |D(A)|\le |A-A|\le n^2. \]

Proof. If $d\in D(A)$, then there exist $a,a+d\in A$, hence $d=(a+d)-a\in A-A$. Thus $D(A)\subseteq (A-A)\cap\mathbb{Z}_{>0}$ and $|D(A)|\le |A-A|$.

Also, $A-A=\{x-y:x\in A,y\in A\}$ is the image of the map $A\times A\to\mathbb{Z}$ given by $(x,y)\mapsto x-y$, so $|A-A|\le |A\times A|=n^2$. $\square$

Lemma 1097.2 (interval example). If $A=\{0,1,2,\dots,n-1\}$, then \[ |D(A)|=\left\lfloor\frac{n-1}{2}\right\rfloor. \]

Proof. A positive integer $d$ belongs to $D(A)$ iff there exists $a\in\{0,\dots,n-1\}$ such that $a+2d\le n-1$, i.e. iff $2d\le n-1$. Thus $d\in\{1,2,\dots,\lfloor (n-1)/2\rfloor\}$ and all such $d$ occur (take $a=0$). $\square$

Lemma 1097.3 (probabilistic lower bound $\gg n^{3/2}$). There exists an absolute constant $c>0$ such that for all sufficiently large integers $n$, there exists a set $A\subset\mathbb{Z}$ with $|A|=n$ and \[ |D(A)|\ge c\,n^{3/2}. \]

Proof. Let $N:=\lfloor n^{3/2}\rfloor$ and consider a random subset $A\subseteq\{1,2,\dots,N\}$ chosen uniformly among all subsets of size $n$.

For each integer $d$ with $1\le d\le \lfloor N/4\rfloor$, define the random variable \[ X_d := \#\{a\in\mathbb{Z}:\ 1\le a\le N-2d,\ a,a+d,a+2d\in A\}, \] the number of three-term arithmetic progressions in $A$ with common difference $d$. Then $d\in D(A)$ exactly when $X_d\ge 1$.

Step 1: first moment lower bound. For each fixed $a$ with $1\le a\le N-2d$, the triple $\{a,a+d,a+2d\}$ lies in $A$ with probability \[ \mathbb{P}(\{a,a+d,a+2d\}\subseteq A)=\frac{\binom{N-3}{n-3}}{\binom{N}{n}}=\frac{n(n-1)(n-2)}{N(N-1)(N-2)}=:P_3. \] Therefore \[ \mu_d:=\mathbb{E}[X_d]=(N-2d)P_3. \] For $d\le N/4$ we have $N-2d\ge N/2$. Also, for $n\ge 4$ and $N\ge 2n$, \[ P_3=\frac{n(n-1)(n-2)}{N(N-1)(N-2)}\ge \frac{n\cdot (n/2)\cdot (n/2)}{N^3}=\frac{n^3}{4N^3}. \] Hence for $d\le N/4$, \[ \mu_d\ge \frac{N}{2}\cdot \frac{n^3}{4N^3}=\frac{n^3}{8N^2}. \] Because $N=\lfloor n^{3/2}\rfloor$, we have $N^2\le n^3$, so $\mu_d\ge 1/8$ for all large $n$ (in particular once $N\ge 2n$).

Step 2: second moment upper bound. Write $X_d=\sum_{a=1}^{N-2d} I_a$ where $I_a$ is the indicator that $\{a,a+d,a+2d\}\subseteq A$. Then \[ \mathbb{E}[X_d^2]=\sum_a \mathbb{E}[I_a] + 2\sum_{a<b}\mathbb{E}[I_a I_b]. \] If two progressions with the same difference $d$ start at $a$ and $b$, their point-sets overlap only when $b-a\in\{d,2d\}$:

• If $b=a+d$, the union has $4$ distinct points $\{a,a+d,a+2d,a+3d\}$.
• If $b=a+2d$, the union has $5$ distinct points $\{a,a+d,a+2d,a+3d,a+4d\}$.
• Otherwise the two triples are disjoint, so the union has $6$ distinct points.

For a fixed $t$-point set $T\subseteq\{1,\dots,N\}$, the probability that $T\subseteq A$ equals \[ P_t:=\frac{\binom{N-t}{n-t}}{\binom{N}{n}}=\frac{n(n-1)\cdots (n-t+1)}{N(N-1)\cdots (N-t+1)}. \] Thus $\mathbb{E}[I_a I_b]$ is $P_4$, $P_5$, or $P_6$ according to overlap type.

Counting pairs: there are at most $N$ pairs of the form $(a,a+d)$ and at most $N$ of the form $(a,a+2d)$, while the total number of pairs $(a,b)$ is at most $N^2/2$. Hence \[ \mathbb{E}[X_d^2]\le (N-2d)P_3 + 2N P_4 + 2N P_5 + N^2 P_6. \] Now note that for $N\ge 2n$ and fixed $t$, we have the crude upper bound $P_t\le (n/N)^t$ (each factor $(n-j)/(N-j)\le n/N$). Therefore \[ 2N P_4 \le 2N\left(\frac{n}{N}\right)^4=2\frac{n^4}{N^3},\qquad 2N P_5 \le 2\frac{n^5}{N^4},\qquad N^2 P_6\le \frac{n^6}{N^4}. \] Since $N\asymp n^{3/2}$, the three error terms are respectively $O(n^{-1/2})$, $O(n^{-1})$, and $O(1)$ as $n\to\infty$. Moreover, the leading term is $\mu_d=(N-2d)P_3=\Theta(1)$ (from Step 1). Consequently there exists an absolute constant $C$ such that for all sufficiently large $n$ and all $d\le N/4$, \[ \mathbb{E}[X_d^2]\le C(\mu_d+\mu_d^2). \]

Step 3: Paley--Zygmund to get $\mathbb{P}(X_d\ge 1)$ bounded below. Since $X_d\ge 0$, Paley--Zygmund gives \[ \mathbb{P}(X_d>0)\ge \frac{\mu_d^2}{\mathbb{E}[X_d^2]}\ge \frac{\mu_d^2}{C(\mu_d+\mu_d^2)}=\frac{\mu_d}{C(1+\mu_d)}. \] From Step 1 we have $\mu_d\ge 1/8$ for all $d\le N/4$ and all sufficiently large $n$, so $\mathbb{P}(X_d>0)\ge c_0$ for some absolute $c_0>0$ independent of $d$.

Step 4: expected number of good differences. Let $Y:=\#\{d\in\{1,\dots,\lfloor N/4\rfloor\}:\ X_d>0\}$. Then by linearity of expectation, \[ \mathbb{E}[Y]=\sum_{d=1}^{\lfloor N/4\rfloor} \mathbb{P}(X_d>0)\ge c_0\,\frac{N}{4}. \] Therefore there exists at least one choice of $A$ (of size exactly $n$) such that $Y\ge c_0 N/4$. Since each such $d$ lies in $D(A)$, we get \[ |D(A)|\ge Y\ge \frac{c_0}{4}N\ge c\,n^{3/2} \] for $c:=c_0/5$ (absorbing the floor in $N=\lfloor n^{3/2}\rfloor$). This proves the lemma. $\square$

FAST REALITY CHECK (small $n$ exhaustive + random tests).

Exhaustive search in small universes. Restricting to $A\subseteq\{0,1,\dots,2n\}$ and searching over all $n$-subsets gave the following maxima: \[ \begin{array}{r|r|l} n & \max |D(A)| & \text{one maximizer }A\subseteq\{0,\dots,2n\} \\\hline 3&1&(0,1,2)\\ 4&2&(0,1,2,4)\\ 5&3&(0,1,2,4,7)\\ 6&4&(0,1,2,4,5,8)\\ 7&6&(0,1,2,4,7,8,14)\\ 8&8&(0,2,4,5,8,9,10,16) \end{array} \] (These are only sanity checks in a restricted search space.)

Random sets. For $n\in\{20,50,100,200\}$, choosing $A$ uniformly at random of size $n$ from $\{1,\dots,\lfloor n^{3/2}\rfloor\}$, the mean values of $|D(A)|$ over $30$ trials were approximately: \[ \begin{array}{r|r|r} n & N=\lfloor n^{3/2}\rfloor & \text{mean }|D(A)| \\\hline 20&89&14.53\\ 50&353&61.17\\ 100&1000&172.9\\ 200&2828&502.47 \end{array} \]

VERIFICATION

• Lemma 1097.1 and Lemma 1097.2 are direct and check all quantifiers.
• In Lemma 1097.3, Step 2 uses an overlap classification specific to progressions with fixed difference $d$. The fact that overlaps occur only for shifts by $d$ or $2d$ was checked by direct inspection of the triple sets.
• The probabilistic argument produces a set $A$ of size exactly $n$ (uniform $n$-subset model), so no later size adjustment is needed.

UNRESOLVED

(i) Strongest proved partial result here. We proved a general upper bound $|D(A)|\le n^2$ (Lemma 1097.1) and a self-contained probabilistic lower bound showing that $|D(A)|\ge c n^{3/2}$ is achievable for some absolute $c>0$ (Lemma 1097.3).

(ii) First gap (crisp). Prove the conjectured upper bound $|D(A)|=O(n^{3/2})$ for all $n$-element integer sets $A$.

(iii) Top 3 next moves.

1. Try to rephrase the set of differences as an incidence problem (triples $a,a+d,a+2d$) and apply sharp incidence bounds or additive-energy inequalities to bound the number of realizable $d$.
2. Investigate extremal constructions suggested by the probabilistic lower bound (random sets in $[1,n^{3/2}]$) and by structured sum-product sets, to understand what features maximize the number of realized differences.
3. Extend exact computations for small $n$ with larger search spaces (or integer programming) to guess extremal configurations and guide conjectures about the sharp constant/exponent.

(iv) Minimal counterexample structure. A counterexample to the $O(n^{3/2})$ conjecture would be a family of sets $A_n$ with $|A_n|=n$ and $|D(A_n)|\ge n^{3/2+\eta}$ for some fixed $\eta>0$. Such a family would have an unusually large set of differences $d$ each supporting at least one 3-term progression, suggesting strong additive structure (many solutions to $x+z=2y$) without forcing $A_n$ to be too dense in an interval.