we-solve (beta)

Math-739-A2 · revision r1 · on Math-739

gpt pro 5.2 attempt on Math-739

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

Contents
  1. Problem 271
  2. Problem statement (as given)
  3. 1. Formal restatement
  4. 2. Quick literature/context check
  5. 3. Attack plan
  6. 4. Work
  7. 4.1 Small-case computation
  8. 4.2 Explicit determination of $A(1)$ (complete)
  9. 4.3 Growth rate of $A(1)$ (complete)
  10. 4.4 A general quadratic upper bound for all $n$ (complete)
  11. 5. Verification
  12. 6. Final
  13. 7. Completion estimate

Problem 271

Problem statement (as given)

For $n$ a positive integer, let $A(n)$ be the Stanley sequence generated by $\{0,n\}$. Can $a_k$ be explicitly determined? How fast do they grow?

1. Formal restatement

Fix $n\in\mathbb{N}$. Define the Stanley sequence $A(n)=(a_k)_{k\ge 0}$ by: \[ a_0=0,\qquad a_1=n, \] and for $k\ge 1$, $a_{k+1}$ is the smallest integer $>a_k$ such that the set \[ \{a_0,a_1,\dots,a_k,a_{k+1}\} \] contains no nontrivial 3-term arithmetic progression, i.e. no distinct $x<y<z$ with $y-x=z-y$.

Questions:

  • Can we write a closed form for $a_k$ (for general $n$)?
  • What is the asymptotic growth of $a_k$ as $k\to\infty$ (depending on $n$)?

2. Quick literature/context check

The Erdős Problems Project lists this as open in general and summarizes known structure for some special $n$ (e.g. $n=1$, and more generally $n=3^k$ and $n=2\cdot 3^k$) going back to Odlyzko--Stanley and others. % citeturn1view1

There is an extensive modern literature on Stanley sequences; for example, a 2025 preprint studies "irregular" behavior of Stanley sequences beyond the well-structured cases. % citeturn21view0

3. Attack plan

  1. Compute small examples to see patterns (especially $n=1$ versusS$0,1$ and a "generic" $n$ like $4$).
  2. Prove what can be proved cleanly:
    • an explicit description and growth rate for $A(1)$;
    • a general, elementary upper bound $a_k \le n + O(k^2)$ valid for all $n$.
  3. Compare with the conjectural dichotomy "structured" vs "irregular" Stanley sequences (but not attempt to resolve the full open problem).

4. Work

4.1 Small-case computation

For $n=1$, the greedy sequence begins \[ A(1):\ 0,1,3,4,9,10,12,13,27,28,30,31,36,37,39,\dots \] For $n=4$, it begins \[ A(4):\ 0,4,5,6,9,11,13,14,15,19,20,22,23,24,29,\dots \] The $n=1$ case is highly structured; $n=4$ already looks less obviously structured.

4.2 Explicit determination of $A(1)$ (complete)

Let \[ S:=\left\{\sum_{i\ge 0}\varepsilon_i 3^i:\ \varepsilon_i\in\{0,1\}\right\}, \] i.e. the set of nonnegative integers whose base-$3$ expansion uses only digits $0$ and $1$ (no digit $2$).

Lemma (No carries): If $x=\sum x_i3^i$ and $z=\sum z_i3^i$ with $x_i,z_i\in\{0,1\}$, then the base-$3$ addition $x+z$ has no carries; equivalently, the $i$th ternary digit of $x+z$ is $x_i+z_i\in\{0,1,2\}$.
Proof: Write the usual carry recursion in base $3$: $c_0=0$ and for each $i\ge 0$, \[ x_i+z_i+c_i = d_i + 3c_{i+1},\qquad d_i\in\{0,1,2\}. \] We show by induction that $c_i=0$ for all $i$. For $i=0$, $x_0+z_0+c_0\le 2$, so $c_1=0$. Assume $c_i=0$; then $x_i+z_i+c_i\le 2$ implies $c_{i+1}=0$. Hence all carries vanish. ∎
Lemma ($S$ is 3AP-free): There are no distinct $x<y<z$ in $S$ with $x+z=2y$.
Proof: Write $x=\sum x_i3^i$, $y=\sum y_i3^i$, $z=\sum z_i3^i$ with digits in $\{0,1\}$. By Lemma Lemma (No carries), $x+z$ is computed digitwise: the $i$th digit is $x_i+z_i\in\{0,1,2\}$ with no carry. Also $2y=\sum 2y_i 3^i$ is computed digitwise with digits $2y_i\in\{0,2\}$ and no carries (since $2\cdot 1=2<3$).

From $x+z=2y$, comparing ternary digits gives $x_i+z_i=2y_i$ for each $i$. But the only way to have $x_i,z_i,y_i\in\{0,1\}$ and $x_i+z_i=2y_i$ is $x_i=z_i=y_i$. Hence $x=y=z$, contradicting distinctness. ∎

Lemma (Every integer has a "Cantor" 2-term representation): For every $t\ge 0$ and every integer $m$ with $0\le m<3^t$, there exist $x,y\in S$ with $0\le x\le y\le m$ such that \[ m=2y-x, \] and moreover if $m\notin S$ then $y<m$.
Proof: We prove this by induction on $t$.

Base $t=0$: the only $m$ is $0$, and $0=2\cdot 0-0$.

Inductive step $t\to t+1$. Let $0\le m<3^{t+1}$. Write uniquely \[ m=a\cdot 3^t + r,\qquad a\in\{0,1,2\},\quad 0\le r<3^t. \] Apply the induction hypothesis to $r$ to get $x_0,y_0\in S$ with $r=2y_0-x_0$ and $0\le x_0\le y_0\le r$, and if $r\notin S$ then $y_0<r$.

Case 1: $a=0$ or $a=1$. Set \[ x:=a\cdot 3^t + x_0,\qquad y:=a\cdot 3^t + y_0. \] Then $x,y\in S$ (their ternary digit at position $t$ is $a\in\{0,1\}$ and lower digits come from $x_0,y_0$), and \[ 2y-x = a\cdot 3^t + (2y_0-x_0) = a\cdot 3^t + r = m. \] Also $y\le a\cdot 3^t + r = m$, and if $m\notin S$ in this case, then necessarily $r\notin S$, so $y_0<r$ and hence $y<m$.

Case 2: $a=2$. Set \[ x:=x_0,\qquad y:=3^t + y_0. \] Then $x\in S$ and $y\in S$ (digit $t$ equals $1$), and \[ 2y-x = 2(3^t+y_0)-x_0 = 2\cdot 3^t + (2y_0-x_0)=2\cdot 3^t + r = m. \] Finally, $y=3^t+y_0\le 3^t+r < 2\cdot 3^t+r=m$, so $y<m$.

This completes the induction. ∎

Theorem (Explicit description of $A(1)$): The Stanley sequence $A(1)$ is exactly the increasing enumeration of $S$, the set of nonnegative integers with ternary digits in $\{0,1\}$. Equivalently, if $k=\sum_{i\ge 0}\varepsilon_i 2^i$ is the binary expansion of $k$, then \[ a_k=\sum_{i\ge 0}\varepsilon_i 3^i. \]
Proof: We prove by induction on $m\ge 0$ that, when the greedy algorithm for $A(1)$ has processed all integers $<m$, the chosen set equals $S\cap[0,m)$.

Induction base $m=0$ is trivial. Assume it holds for $m$.

If $m\in S$: all previously chosen numbers lie in $S$, and $S$ is 3AP-free by Lemma lem:S3free, so adjoining $m$ creates no 3-term arithmetic progression. Hence the greedy algorithm accepts $m$.

If $m\notin S$: choose $t$ with $m<3^t$. By Lemma Lemma (Every integer has a "Cantor" 2-term representation), there exist $x,y\in S$ with $m=2y-x$ and $y<m$. In particular $x<y<m$ and $x,y\in S\cap[0,m)$. By the induction hypothesis, $x$ and $y$ have already been selected before $m$ is considered, so $m$ would complete the 3AP $(x,y,m)$ and is therefore rejected by the greedy rule.

Thus the greedy algorithm accepts exactly the integers in $S$, in increasing order. The final formula $a_k=\sum\varepsilon_i3^i$ follows because mapping a binary string $(\varepsilon_i)$ to the ternary string $(\varepsilon_i)$ gives an order-preserving bijection $\mathbb{N}\to S$. ∎

4.3 Growth rate of $A(1)$ (complete)

Corollary: Let $\alpha:=\log_2 3$. Then $a_k$ for $A(1)$ satisfies \[ k^{\alpha}\ \le\ a_k\ <\ 3\,k^{\alpha}\qquad(k\ge 1), \] so $a_k=\Theta(k^{\log_2 3})$.
Proof: Let $m$ be such that $2^m\le k<2^{m+1}$. Then in binary, $k$ has at most $m+1$ digits, so by Theorem thm:A1, $a_k$ has ternary digits only $0/1$ and has largest possible value $<\sum_{i=0}^{m}3^i<3^{m+1}$, hence $a_k<3^{m+1}$. Also $a_{2^m}=3^m$ (binary $10\cdots0$ maps to ternary $10\cdots0$), so $a_k\ge a_{2^m}=3^m$. Since $3^m=(2^m)^{\log_2 3}\le k^{\log_2 3}$ and $3^{m+1}=3\cdot (2^{m+1})^{\log_2 3}\le 3k^{\log_2 3}$, the stated bounds follow. ∎

4.4 A general quadratic upper bound for all $n$ (complete)

Theorem (Elementary bound): For every $n\in\mathbb{N}$ and every $k\ge 1$, the Stanley sequence $A(n)$ satisfies \[ a_k \le n+\frac{(k-1)(k+2)}{2}. \] In particular $a_k = O(k^2)$ uniformly in $n$.
Proof: Fix $k\ge 1$. Consider the moment just before the algorithm chooses $a_k$; at that time the selected set is \[ \{a_0,a_1,\dots,a_{k-1}\}. \] Now look at all integers $m$ with \[ n\le m < a_k. \] Such an $m$ is not selected by time $a_k$ is chosen, so when the greedy algorithm inspected $m$ (which happens before choosing $a_k$), it must have rejected $m$ because adding $m$ would create a 3-term AP with two earlier selected elements.

Since $m$ is larger than all elements present at that stage, $m$ can only play the role of the third term in a 3AP, so there exist indices $0\le i<j\le k-1$ such that \[ m = 2a_j - a_i. \] For each ordered pair $(i,j)$ with $0\le i<j\le k-1$ there is at most one integer $m$ satisfying $m=2a_j-a_i$. Therefore, the number of rejected integers $m$ in $[n,a_k)$ is at most the number of pairs $(i,j)$ with $0\le i<j\le k-1$, namely $\binom{k}{2}$.

But the interval $[n,a_k)$ contains exactly $a_k-n$ integers, of which exactly $k-1$ are selected (namely $a_1,\dots,a_{k-1}$). Hence the number of rejected integers in $[n,a_k)$ equals \[ (a_k-n) - (k-1), \] so we have \[ (a_k-n)-(k-1)\le \binom{k}{2}=\frac{k(k-1)}{2}. \] Rearranging gives $a_k \le n + (k-1) + k(k-1)/2 = n + (k-1)(k+2)/2$, as claimed. ∎

5. Verification

  • The proof of Theorem thm:A1 hinges on Lemma Lemma (Every integer has a "Cantor" 2-term representation). I checked the induction carefully: the key is that for $a=2$ we force $y<m$ automatically, which is what makes "digit 2" positions genuinely forbidden.
  • Theorem Theorem (Elementary bound) is a clean counting argument that avoids the earlier "pairs involving the last element" overcount: any $m<a_k$ is rejected before $a_k$ is chosen, so the witness pair must come from $\{a_0,\dots,a_{k-1}\}$.
  • These results do not settle the explicit structure of $A(n)$ for general $n$ (the main open part).

6. Final

UNRESOLVED.

  1. Farthest-reaching partial results proved here.
    • Complete explicit description of $A(1)$ (Theorem thm:A1), and the growth $a_k=\Theta(k^{\log_2 3})$ (Corollary Corollary).
    • A uniform quadratic upper bound $a_k\le n + (k-1)(k+2)/2$ for all $n$ (Theorem Theorem (Elementary bound)).

  2. Precise obstacle. For general $n$, the greedy choices depend on the evolving pattern of forbidden values $2a_j-a_i$. Unlike $n=1$ (and a few other special $n$), there is no known closed-form description of which candidates survive, and the structure can be "irregular" in ways that defeat current techniques.

  3. Most promising next steps.
    • Identify additional classes of $n$ for which $A(n)$ is "regular" (self-similar / described by digital constraints), extending the known $n=3^t$ and $n=2\cdot 3^t$ families.
    • Develop invariants that detect and control irregularity (as explored in recent work). % citeturn21view0
    • Improve general bounds (both upper and lower) on $a_k$ and/or the counting function of $A(n)$, possibly with explicit constants.

  4. Belief about truth value. It is plausible that most $A(n)$ are "irregular" and do not admit a simple closed form, but that there are infinitely many structured $n$ with explicit descriptions; current evidence supports a mix rather than a uniform behavior.

7. Completion estimate

\[ \textbf{55\%} \] (I gave complete proofs for $n=1$ and a strong general upper bound, but not an explicit formula or sharp growth for general $n$.)