Erdős Problem #792

Erdős Problem 792 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

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

FORMAL RESTATEMENT

For $n\ge 1$, let $f(n)$ be the largest integer with the property: for every set $A\subset\mathbb Z$ with $|A|=n$, there exists a subset $B\subset A$ with $|B|\ge f(n)$ such that $B$ is sum-free in the 3-term sense: there are no distinct $a,b,c\in B$ with $a+b=c$. The task is to estimate $f(n)$.

QUICK LITERATURE/CONTEXT CHECK

From the problem statement: Erdős proved $f(n)>n/3$ and conjectured the true order is $n/2$. A random-set argument gives an upper bound $f(n)\le n/2+o(n)$, and there are quoted refinements $f(n)\ge n/3 + \tfrac13\log n$ (Alon--Kleitman) and $f(n)\le n/2-\log n$ (Eberhard--Green--Manners).

Below I reprove the classical $n/3$ lower bound by an elementary "random dilation on the circle" argument.

ATTACK PLAN

1) Show that selecting elements whose fractional parts lie in the middle third of $[0,1)$ produces a sum-free set.

2) Average over the dilation parameter to guarantee a choice giving $\ge n/3$ elements.

3) Reality check: brute force worst cases for $n\le 8$ inside $[-8,8]$.

WORK

Lemma 792.1 (Middle-third selection is sum-free). Fix a real number $\theta$. For any finite $A\subset\mathbb Z$, define \[ B_\theta := \{a\in A: \{\theta a\}\in (1/3,2/3)\}, \] where $\{x\}$ denotes the fractional part of $x$ in $[0,1)$. Then $B_\theta$ contains no distinct $a,b,c$ with $a+b=c$.

Proof. Suppose $a,b,c\in B_\theta$ are distinct. Then $\{\theta a\},\{\theta b\},\{\theta c\}\in (1/3,2/3)$. If $a+b=c$ held, then in $\mathbb R/\mathbb Z$ we would have \[ \{\theta c\} = \{\theta(a+b)\} = \{\theta a + \theta b\}. \] But $\theta a$ and $\theta b$ have fractional parts in $(1/3,2/3)$, so their sum has fractional part in $(2/3,4/3)$, which modulo $1$ lies in $(0,1/3)\cup(2/3,1)$. This set is disjoint from $(1/3,2/3)$, so $\{\theta a+\theta b\}\notin (1/3,2/3)$, contradiction. Therefore $a+b\ne c$ for all distinct $a,b,c\in B_\theta$. $\square$

Lemma 792.2 (Averaging gives $|B_\theta|\ge n/3$ for some $\theta$). For every finite $A\subset\mathbb Z$ with $|A|=n$, there exists $\theta\in[0,1]$ such that \[|B_\theta|\ge \lceil n/3\rceil. \] In particular, $f(n)\ge \lceil n/3\rceil$.

Proof. Choose $\theta$ uniformly at random from $[0,1]$. Fix $a\in A$ with $a\ne 0$. Then $\{\theta a\}$ is uniform on $[0,1)$, so \[\mathbb P\left(\{\theta a\}\in (1/3,2/3)\right)=1/3. \] If $a=0$, then $\{\theta a\}=0\notin(1/3,2/3)$ for all $\theta$, so its contribution is $0$. Therefore \[ \mathbb E|B_\theta| = \sum_{a\in A} \mathbb P(a\in B_\theta) \ge (n-1)\cdot\frac13. \] In particular, $\mathbb E|B_\theta|\ge n/3 - 1/3$. Since $|B_\theta|$ is an integer-valued random variable, there must exist some $\theta$ with $|B_\theta|\ge \lceil n/3\rceil$. By Lemma 792.1 such a $B_\theta$ is sum-free, proving the claim. $\square$

Fast reality check (small brute force in a bounded window). For each $n\le 8$, I brute-forced over all $A\subset[-8,8]$ with $|A|=n$ and computed the maximum size of a 3-term sum-free subset $B\subset A$, then minimized over those $A$. The restricted-window minima found were:

Again, this is only a sanity check (the true $f(n)$ is a minimum over all integer sets $A$).

VERIFICATION

-- Lemma 792.1 uses only modular arithmetic on $\mathbb R/\mathbb Z$ and the fact that the middle third is disjoint from the sumset of two copies of itself.

-- In Lemma 792.2 the boundary points $1/3,2/3$ have Lebesgue measure $0$, so open vs closed intervals do not affect the expectation.

FINAL

UNRESOLVED

(i) Strongest proved partial result here: $f(n)\ge \lceil n/3\rceil$ for all $n$, by Lemmas 792.1--792.2.

(ii) First gap (crisp): Determine whether $f(n)/n\to 1/2$ or even prove any constant strictly bigger than $1/3$ in the limit: \[\liminf_{n\to\infty} \frac{f(n)}{n} > \frac13. \]

(iii) Top 3 next moves:

1. Try to refine the interval method by using unions of intervals in $\mathbb R/\mathbb Z$ whose sumset avoids itself, aiming for density $>1/3$ and quantifying the improvement as a function of $n$.
2. Compute (or bound) exact $f(n)$ for small $n$ by searching worst-case $A$ in increasing windows, to guess extremal configurations and whether the constant drifts toward $1/2$.
3. Develop an upper-bound construction (a family of sets $A$) that forces the largest sum-free subset to have density at most some $c<1/2$, to test the conjectured $1/2$ limit.

(iv) Minimal counterexample structure to watch for: Worst-case sets $A$ that minimize the largest sum-free subset typically have many additive relations $a+b=c$ (high additive energy), e.g. long arithmetic progressions or dense chunks of generalized progressions. Any improvement over $1/3$ must exploit a structural dichotomy: either $A$ is structured (then extract a large sum-free subset by a tailored construction), or $A$ is pseudorandom (then a probabilistic selection gives near-$1/2$ density).

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

For $n\ge 1$, let $f(n)$ be the largest integer with the property: for every set $A\subset\mathbb Z$ with $|A|=n$, there exists a subset $B\subset A$ with $|B|\ge f(n)$ such that $B$ is sum-free in the 3-term sense: there are no distinct $a,b,c\in B$ with $a+b=c$. The task is to estimate $f(n)$.

QUICK LITERATURE/CONTEXT CHECK

From the problem statement: Erdős proved $f(n)>n/3$ and conjectured the true order is $n/2$. A random-set argument gives an upper bound $f(n)\le n/2+o(n)$, and there are quoted refinements $f(n)\ge n/3 + \tfrac13\log n$ (Alon--Kleitman) and $f(n)\le n/2-\log n$ (Eberhard--Green--Manners).

Below I reprove the classical $n/3$ lower bound by an elementary "random dilation on the circle" argument.

ATTACK PLAN

1) Show that selecting elements whose fractional parts lie in the middle third of $[0,1)$ produces a sum-free set.

2) Average over the dilation parameter to guarantee a choice giving $\ge n/3$ elements.

3) Reality check: brute force worst cases for $n\le 8$ inside $[-8,8]$.

WORK

Lemma 792.1 (Middle-third selection is sum-free). Fix a real number $\theta$. For any finite $A\subset\mathbb Z$, define \[ B_\theta := \{a\in A: \{\theta a\}\in (1/3,2/3)\}, \] where $\{x\}$ denotes the fractional part of $x$ in $[0,1)$. Then $B_\theta$ contains no distinct $a,b,c$ with $a+b=c$.

Proof. Suppose $a,b,c\in B_\theta$ are distinct. Then $\{\theta a\},\{\theta b\},\{\theta c\}\in (1/3,2/3)$. If $a+b=c$ held, then in $\mathbb R/\mathbb Z$ we would have \[ \{\theta c\} = \{\theta(a+b)\} = \{\theta a + \theta b\}. \] But $\theta a$ and $\theta b$ have fractional parts in $(1/3,2/3)$, so their sum has fractional part in $(2/3,4/3)$, which modulo $1$ lies in $(0,1/3)\cup(2/3,1)$. This set is disjoint from $(1/3,2/3)$, so $\{\theta a+\theta b\}\notin (1/3,2/3)$, contradiction. Therefore $a+b\ne c$ for all distinct $a,b,c\in B_\theta$. $\square$

Lemma 792.2 (Averaging gives $|B_\theta|\ge n/3$ for some $\theta$). For every finite $A\subset\mathbb Z$ with $|A|=n$, there exists $\theta\in[0,1]$ such that \[|B_\theta|\ge \lceil n/3\rceil. \] In particular, $f(n)\ge \lceil n/3\rceil$.

Proof. Choose $\theta$ uniformly at random from $[0,1]$. Fix $a\in A$ with $a\ne 0$. Then $\{\theta a\}$ is uniform on $[0,1)$, so \[\mathbb P\left(\{\theta a\}\in (1/3,2/3)\right)=1/3. \] If $a=0$, then $\{\theta a\}=0\notin(1/3,2/3)$ for all $\theta$, so its contribution is $0$. Therefore \[ \mathbb E|B_\theta| = \sum_{a\in A} \mathbb P(a\in B_\theta) \ge (n-1)\cdot\frac13. \] In particular, $\mathbb E|B_\theta|\ge n/3 - 1/3$. Since $|B_\theta|$ is an integer-valued random variable, there must exist some $\theta$ with $|B_\theta|\ge \lceil n/3\rceil$. By Lemma 792.1 such a $B_\theta$ is sum-free, proving the claim. $\square$

Fast reality check (small brute force in a bounded window). For each $n\le 8$, I brute-forced over all $A\subset[-8,8]$ with $|A|=n$ and computed the maximum size of a 3-term sum-free subset $B\subset A$, then minimized over those $A$. The restricted-window minima found were:

Again, this is only a sanity check (the true $f(n)$ is a minimum over all integer sets $A$).

VERIFICATION

-- Lemma 792.1 uses only modular arithmetic on $\mathbb R/\mathbb Z$ and the fact that the middle third is disjoint from the sumset of two copies of itself.

-- In Lemma 792.2 the boundary points $1/3,2/3$ have Lebesgue measure $0$, so open vs closed intervals do not affect the expectation.

FINAL

UNRESOLVED

(i) Strongest proved partial result here: $f(n)\ge \lceil n/3\rceil$ for all $n$, by Lemmas 792.1--792.2.

(ii) First gap (crisp): Determine whether $f(n)/n\to 1/2$ or even prove any constant strictly bigger than $1/3$ in the limit: \[\liminf_{n\to\infty} \frac{f(n)}{n} > \frac13. \]

(iii) Top 3 next moves:

1. Try to refine the interval method by using unions of intervals in $\mathbb R/\mathbb Z$ whose sumset avoids itself, aiming for density $>1/3$ and quantifying the improvement as a function of $n$.
2. Compute (or bound) exact $f(n)$ for small $n$ by searching worst-case $A$ in increasing windows, to guess extremal configurations and whether the constant drifts toward $1/2$.
3. Develop an upper-bound construction (a family of sets $A$) that forces the largest sum-free subset to have density at most some $c<1/2$, to test the conjectured $1/2$ limit.

(iv) Minimal counterexample structure to watch for: Worst-case sets $A$ that minimize the largest sum-free subset typically have many additive relations $a+b=c$ (high additive energy), e.g. long arithmetic progressions or dense chunks of generalized progressions. Any improvement over $1/3$ must exploit a structural dichotomy: either $A$ is structured (then extract a large sum-free subset by a tailored construction), or $A$ is pseudorandom (then a probabilistic selection gives near-$1/2$ density).