Reused writeup on Math-946 (gpt pro 5.2)

Erdős Problem 817 --- collection record

PROVENANCE AND STATUS

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

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/817.tex.

REUSED SOURCE 1

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

Erdos Problem #817

FORMAL RESTATEMENT.

Fix $k\ge 3$. For a finite set $A\subset\mathbb{N}$, define its subset-sum set \[ \langle A\rangle := \Big\{\sum_{a\in A}\varepsilon_a a:\ \varepsilon_a\in\{0,1\}\Big\}. \] Define $g_k(n)$ to be the least integer $N$ such that $\{1,2,\dots,N\}$ contains a subset $A$ of size $|A|=n$ for which $\langle A\rangle$ contains no nontrivial $k$-term arithmetic progression, i.e. no set of the form \[ x, x+d, x+2d,\dots,x+(k-1)d\quad\text{with }d\ne0 \] all lying in $\langle A\rangle$. The problem asks for asymptotics of $g_k(n)$, and in particular whether $g_3(n)\gg 3^n$.

QUICK LITERATURE/CONTEXT CHECK.

The statement records that Erdős and Sárközy proved $g_3(n)\gg 3^n/n^{O(1)}$. I do not use any results not already stated in the problem text.

ATTACK PLAN.

Proof track: attempt to show that if $A\subset[1,N]$ has $|A|=n$, then the additive structure of $\langle A\rangle$ inevitably creates 3-term progressions unless $N$ is exponentially large. Construction track: build explicit $A$ whose subset sums are 3-AP-free (hence $k$-AP-free for all $k\ge3$), giving explicit upper bounds for $g_k(n)$.

WORK.

Lemma 817.1 (explicit 3-AP-free subset sums; a Cantor-type construction). Let \[ A_n := \{2\cdot 3^0,\ 2\cdot 3^1,\ \dots,\ 2\cdot 3^{n-1}\}. \] Then $A_n\subseteq\{1,\dots,2\cdot 3^{n-1}\}$ has $|A_n|=n$ and $\langle A_n\rangle$ contains no nontrivial $3$-term arithmetic progression. Consequently, \[ g_3(n) \le 2\cdot 3^{n-1}. \]

Proof. Every element of $\langle A_n\rangle$ can be written uniquely as \[ x=\sum_{i=0}^{n-1}\varepsilon_i\,(2\cdot 3^i)\quad(\varepsilon_i\in\{0,1\}), \] so $x$ has a base-$3$ expansion using only digits $0$ and $2$ in positions $0$ through $n-1$. Let $C_n$ denote this set of "$0/2$-digit" ternary numbers. We prove by induction on $n$ that $C_n$ has no nontrivial 3-term arithmetic progression.

Base $n=1$: $C_1=\{0,2\}$ has no nontrivial 3-term AP. Induction step: assume $C_{n-1}$ is 3-AP-free. Take $x,y,z\in C_n$ with $x+z=2y$. Reduce the equality modulo $3$. Each of $x,y,z$ is congruent to either $0$ or $2$ modulo $3$, determined by its least significant ternary digit. Write $x=3x'+d_x$, $y=3y'+d_y$, $z=3z'+d_z$ with $d_x,d_y,d_z\in\{0,2\}$ and $x',y',z'\in C_{n-1}$. Then \[ (3x'+d_x) + (3z'+d_z) = 2(3y'+d_y) \] implies \[ 3(x'+z'-2y') = 2d_y - d_x - d_z. \] The right-hand side takes values in $\{-4,-2,0,2,4\}$. The only value divisible by $3$ is $0$, hence $2d_y-d_x-d_z=0$. Since $d_x,d_y,d_z\in\{0,2\}$, the equality $2d_y=d_x+d_z$ forces $d_x=d_y=d_z$. With $d_x=d_y=d_z=:d$, the displayed equation reduces to $x'+z'=2y'$. By the induction hypothesis on $C_{n-1}$, we must have $x'=y'=z'$, hence $x=y=z$. Thus there is no nontrivial 3-term AP in $C_n=\langle A_n\rangle$. Therefore $A_n$ witnesses $g_3(n)\le \max A_n=2\cdot 3^{n-1}$. $\square$

Lemma 817.2 (3-AP-free implies $k$-AP-free). If a set $S$ contains no nontrivial $3$-term arithmetic progression, then $S$ contains no nontrivial $k$-term arithmetic progression for any $k\ge3$. Consequently, for all $k\ge3$ and all $n$, \[ g_k(n) \le g_3(n). \]

Proof. Suppose $S$ contains a nontrivial $k$-term AP $x,x+d,\dots,x+(k-1)d$ with $d\ne0$. Then the first three terms $x,x+d,x+2d$ form a nontrivial 3-term AP contained in $S$, contradicting the assumption. Thus $S$ is $k$-AP-free for every $k\ge3$. Taking $S=\langle A\rangle$ for a witness set $A$ gives the inequality $g_k(n)\le g_3(n)$. $\square$

FAST REALITY CHECK (exact small $n$ for $g_3(n)$). I ran an exact backtracking search for minimal $N$ for which there exists $A\subseteq[1,N]$ of size $n$ with $\langle A\rangle$ 3-AP-free. The search found: \[ \begin{array}{c|c|c} n & g_3(n)\ \text{(found)} & \text{one witness }A\\\hline 1 & 1 & \{1\}\\ 2 & 3 & \{1,3\}\\ 3 & 8 & \{5,7,8\}\\ 4 & 22 & \{7,19,21,22\} \end{array} \] For $n=5$, the same search verified that no such $A$ exists inside $[1,N]$ for any $N\le 30$ (so $g_3(5)>30$); determining the exact value for $n=5$ was not completed within the computational budget.

VERIFICATION.

Lemma 817.1: the key check is that the least ternary digit $d\in\{0,2\}$ must match across a 3-AP; the divisibility-by-$3$ argument forces $2d_y-d_x-d_z=0$, and the restriction to $\{0,2\}$ forces $d_x=d_y=d_z$. Then induction is applied on the truncated expansions. Lemma 817.2: every nontrivial $k$-AP contains a nontrivial 3-AP as a subset. The computational claims were produced by an explicit backtracking search and can be rechecked by directly verifying 3-AP-freeness of the listed subset-sum sets.

FINAL.

UNRESOLVED.

1. (i) Strongest proved partial results here: an explicit construction gives $g_3(n)\le 2\cdot 3^{n-1}$ (Lemma 817.1), and hence $g_k(n)\le 2\cdot 3^{n-1}$ for all $k\ge3$ (Lemma 817.2). Exact values were computed for $n\le4$: $g_3(1)=1$, $g_3(2)=3$, $g_3(3)=8$, $g_3(4)=22$.
2. (ii) First gap: prove any super-constant-factor lower bound of the form $g_3(n)\ge c\,3^n$ (or refute it) without appealing to results not stated in the problem text.
3. (iii) Top 3 next moves: $1$ analyze structural constraints on $\langle A\rangle$ (e.g. many additive quadruples) that would force a 3-AP by a purely combinatorial lemma; $2$ compute $g_3(n)$ exactly for $n=5,6$ by improving backtracking (symmetry breaking, meet-in-the-middle) to identify the true growth for small $n$; $3$ attempt to show that any 3-AP-free $\langle A\rangle$ must resemble a "digital" set (as in Lemma 817.1), and leverage that to lower-bound $\max A$.
4. (iv) A minimal counterexample to $g_3(n)\gg 3^n$ would be an infinite family of sets $A_n\subset[1,C\cdot 3^{n-1}]$ with $|A_n|=n$ and $\langle A_n\rangle$ 3-AP-free, with $C$ arbitrarily small; Lemma 817.1 shows $C$ can be at most $2/3$ but does not rule out smaller constants.

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.