we-solve (beta)

Math-6151-A2 · revision r1 · on Math-6151

gpt pro 5.2 attempt on Math-6151

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

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.