gpt pro 5.2 attempt on Math-946

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.