Erdős Problem #789

Round 2 continuation for Erdős Problem #789

1) ROUND-2 OBJECTIVE

I pursue path (C). The most promising Round-2 move is not a full solution of the asymptotic problem, but a correction and strengthening of the upper-bound side: Round 1 proved only $h(n)\le \sqrt{7n}$, while the finite interval companion problem #874 is already solved sharply enough to force \[ h(n)\le 2\sqrt n + O(1). \] This is a strict advance over Round 1 and isolates the real remaining obstruction: the exponent gap between $1/3$ and $1/2$.

2) Round-1 FOUNDATION USED

I use the following Round 1 results without reproving them.

1. Round 1 corrected the intended meaning of the problem to the standard distinct-summand admissibility condition.
2. Round 1 proved the lower bound \[ h(n)\gg n^{1/3}. \]
3. Round 1 observed that to upper-bound the universal guarantee $h(n)$, it is enough to exhibit one specific $n$-element set whose admissible subsets are small.

3) NEW INSIGHT / TOOL (ROUND-2)

The new tool is a transfer from the now-solved finite interval problem #874. Deshouillers and Freiman proved that, for all sufficiently large $N$, every admissible subset $A\subset [1,N]$ satisfies \[ |A|\le 2\sqrt{N+\tfrac14}-1. \] Applying this to the specific $n$-set $\{1,2,\dots,n\}$ immediately sharpens the Round 1 upper bound for $h(n)$.

4) ATTACK PLAN (ROUND-2)

The exact Round 1 gap was this: the upper bound $h(n)\le \sqrt{7n}$ had the correct exponent but a weak constant, and it did not use the full strength of the solved interval problem.

The plan is:

1. import the Deshouillers--Freiman theorem for admissible subsets of $[1,N]$;
2. apply it to the specific set $A_0=\{1,2,\dots,n\}$;
3. conclude that the universal Erdős quantity $h(n)$ satisfies \[ h(n)\le 2\sqrt{n+\tfrac14}-1 \] for all sufficiently large $n$.

This overcomes the Round 1 obstacle because the interval extremal problem has already been settled.

5) WORK (ROUND-2)

Recall the corrected formulation from Round 1: a finite set $B\subset \mathbf{Z}$ is admissible if, whenever \[ a_1+\cdots+a_r=b_1+\cdots+b_s \] with all summands distinct on each side and drawn from $B$, one must have $r=s$.

Let $h(n)$ denote the largest integer such that every $n$-element set $A\subset \mathbf{Z}$ contains an admissible subset of size at least $h(n)$.

External theorem used. Deshouillers and Freiman proved the following sharpened form of the finite interval problem: there exists $N_0$ such that for every integer $N\ge N_0$ and every admissible set $C\subset [1,N]$, \[ |C|\le 2\sqrt{N+\tfrac14}-1. \]

Claim 789.1. For all sufficiently large $n$, \[ h(n)\le 2\sqrt{n+\tfrac14}-1. \] In particular, \[ h(n)\le 2\sqrt n + O(1). \]

Proof. Take the particular $n$-element set \[ A_0:=\{1,2,\dots,n\}. \] If $B\subseteq A_0$ is admissible, then $B$ is an admissible subset of $[1,n]$. Hence, for all sufficiently large $n$, the Deshouillers--Freiman theorem gives \[ |B|\le 2\sqrt{n+\tfrac14}-1. \] Therefore no admissible subset of $A_0$ can be larger than $2\sqrt{n+\tfrac14}-1$. Since $h(n)$ is the size guaranteed inside every $n$-element set, it cannot exceed the maximum admissible subset size inside this specific $A_0$. Thus \[ h(n)\le 2\sqrt{n+\tfrac14}-1 \] for all sufficiently large $n$, proving the claim. $\Box$

Corollary 789.2. Combining Claim 789.1 with the Round 1 lower bound yields \[ n^{1/3}\ll h(n)\le 2\sqrt n + O(1). \] If one also imports the Choi improvement recorded on the problem page, the lower side becomes \[ (n\log n)^{1/3}\ll h(n)\le 2\sqrt n + O(1). \]

What is still missing. The exponent remains unknown. Round 2 improves the upper constant sharply, but the real open question is still whether the true order is closer to $n^{1/3}$, $n^{1/2}$, or something in between.

6) ADVERSARIAL VERIFICATION

There are only two possible weak points.

1. Compatibility of definitions. Round 1 corrected the problem to the standard distinct-summand admissibility notion. This is exactly the notion used in the finite interval problem #874, so the transfer is legitimate.
2. Universal-versus-specific extremal parameter. The proof uses only one specific $n$-element set $A_0=\{1,\dots,n\}$. This is correct because $h(n)$ is a universal guarantee across all $n$-element sets; any one hard example bounds it from above.

No hidden quantifier issue remains: the Deshouillers--Freiman theorem applies to all sufficiently large $n$, which is exactly the regime relevant for estimating $h(n)$.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 2 strictly improves the Round 1 upper bound from $h(n)\le \sqrt{7n}$ to \[ h(n)\le 2\sqrt n + O(1), \] while retaining the Round 1 lower bound $h(n)\gg n^{1/3}$. The corrected current bracket is therefore \[ (n\log n)^{1/3}\ll h(n)\le 2\sqrt n + O(1), \] but the true asymptotic order of $h(n)$ remains open.

8) COMPLETION ESTIMATE

COMPLETION: 46%

9) REFERENCES

1. T. F. Bloom, Erdős Problem #789, problem page.
2. T. F. Bloom, Erdős Problem #874, problem page.
3. J.-M. Deshouillers and G. A. Freiman, On an additive problem of Erdős and Straus, 2, Astérisque 258 $1999$, 141--148.

10) OUTPUT FORMAT NOTE

This file intentionally starts at \section and contains no preamble and no \begin{document}, so it can be pasted directly into an existing LaTeX document.

Archive note. This extract contains the work on Problem #789 from a joint report on Problems #789, #873, and #875. The shared introduction, verification, conclusions, and references are retained. The source's 68% completion estimate applies to the joint report.

Round 2 continuation for Erdős problems #789, #873, #875

1) ROUND-2 OBJECTIVE

Because Round 1 bundled three Erdős problems into a single file, this continuation also treats the three problems together. I am pursuing path (C): I identify and correct a concrete Round 1 error for Problem #875 (a missed theorem from the literature), then propagate the corrected consequences. In the same pass I also strengthen the Round 1 upper bound for Problem #789 and prove a new fixed-$k$ obstruction for Problem #873. None of the three problems is fully solved, so the global status remains unresolved.

2) Round-1 FOUNDATION USED

I use the following Round 1 facts without reproving them.

1. For Problem #789, Round 1 already corrected the statement to the standard distinct-summand notion of admissibility, and proved the lower bound $h(n) \gg n^{1/3}$.
2. For Problem #873, Round 1 proved the monotonicity of $F(A,X,k)$ in $k$, namely that $F(A,X,k') \le F(A,X,k)$ whenever $k'\ge k$.
3. For Problem #875, Round 1 observed that every finite initial segment $A\cap [1,N]$ of an infinite admissible set is itself admissible, so any sharp finite bound inside $[1,N]$ immediately yields a universal density bound for infinite admissible sets.

3) NEW INSIGHT / TOOL (ROUND-2)

There are three genuinely new ingredients in this round.

1. Problem #789. I import the sharp Deshouillers--Freiman theorem for finite admissible subsets of $[1,N]$, which upgrades the Round 1 upper bound from $\sqrt{7n}$ to $2\sqrt{n}+O(1)$.
2. Problem #873. I introduce a new divisor-block construction: concatenate scaled divisor sets of primorials. This produces, for every fixed $k$, an infinite set $A$ for which $F(A,X,k)$ is larger than every power of $\log X$ infinitely often. This does not disprove the Erdős--Szemerédi conjecture, but it shows that any proof must use the freedom to let $k$ depend on $A$ and $\varepsilon$.
3. Problem #875. Round 1 missed Erdős--Nicolas--Sárkőzy's 1991 theorem constructing an infinite admissible set with polynomial density $A(x)\gg x^{5-2\sqrt6}$. After correcting this, I derive new consequences: existence of polynomial-growth admissible sets, existence of an admissible set with $\liminf a_{n+1}/a_n = 1$, a sharpened universal lower bound $a_n\ge n(n+2)/4$ for all large $n$, and a sharpened gap obstruction $\limsup (a_{n+1}-a_n)/n\ge 1/2$.

4) ATTACK PLAN (ROUND-2)

After Round 1, the exact remaining gaps were as follows.

1. For Problem #789, the upper bound was only $O(\sqrt n)$ with a weak constant. The natural gap was to import the sharp finite-interval extremal theorem and transfer it immediately to $h(n)$ by taking the special set $[1,n]$.
2. For Problem #873, Round 1 had no construction showing how badly a fixed value of $k$ can fail. The precise target now is to prove that for every fixed $k$, there is an infinite $A$ for which $F(A,X,k)$ is still very large infinitely often.
3. For Problem #875, the most serious issue is factual: Round 1 treated polynomial growth as if it might still be unknown. I first repair that mistake using the 1991 theorem, and then extract the strongest easy corollaries for growth and gap questions.

5) WORK (ROUND-2)

Problem #789: sharpening the universal upper bound

Let $h(n)$ be the corrected distinct-summand quantity from Round 1.

Claim 789.1. For all sufficiently large $n$, \[ h(n) \le 2\sqrt{n+\tfrac14}-1. \] In particular, \[ h(n) \le 2\sqrt n + O(1). \]

Proof. Deshouillers and Freiman proved that there exists $N_0$ such that for every integer $N\ge N_0$, every admissible subset $C\subset [1,N]$ satisfies \[ |C| \le 2\sqrt{N+\tfrac14}-1. \] Now take the special $n$-element set \[ A_0 := \{1,2,\dots,n\}. \] Any admissible subset $B\subseteq A_0$ is an admissible subset of $[1,n]$, so for $n\ge N_0$, \[ |B| \le 2\sqrt{n+\tfrac14}-1. \] But $h(n)$ is the largest integer guaranteed inside every $n$-element set, so in particular it cannot exceed the largest admissible subset size inside this specific set $A_0$. Hence \[ h(n) \le 2\sqrt{n+\tfrac14}-1 \] for all sufficiently large $n$, which is exactly the claim. $\Box$

Consequence. Combining Claim 789.1 with the Round 1 lower bound $h(n)\gg n^{1/3}$, and with Choi's recorded improvement $h(n)\gg (n\log n)^{1/3}$, the corrected state of play is now \[ (n\log n)^{1/3} \ll h(n) \le 2\sqrt n + O(1). \] This is strictly sharper than the Round 1 upper bound $h(n)\le \sqrt{7n}$.

6) ADVERSARIAL VERIFICATION

Problem #789.

Problem #873.

Problem #875.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The strict advances over Round 1 are these.

1. Problem #789: the upper bound is sharpened from $\sqrt{7n}$ to $2\sqrt n+O(1)$.
2. Problem #873: a new fixed-$k$ obstruction is proved. For every fixed $k$, some infinite $A$ has $F(A,X,k)$ larger than every power of $\log X$ infinitely often.
3. Problem #875: a concrete Round 1 error is corrected. Polynomial-growth admissible sets already exist. As a result, the old final status for #875 must be replaced by the sharper quantitative bracket \[ c<\frac12 \text{ impossible}, \qquad c>5+2\sqrt6 \text{ possible}. \] Moreover there exists an admissible set with $\liminf a_{n+1}/a_n=1$.

8) COMPLETION ESTIMATE

COMPLETION: 68%

9) REFERENCES

1. T. F. Bloom, Erdős Problem #789, problem page and discussion thread.
2. T. F. Bloom, Erdős Problem #873, problem page and discussion thread.
3. T. F. Bloom, Erdős Problem #875, problem page and discussion thread.
4. J.-M. Deshouillers and G. A. Freiman, On an additive problem of Erdős and Straus, 2, in Structure theory of set addition, Astérisque 258 $1999$, 141--148.
5. P. Erdős, J.-L. Nicolas, and A. Sárkőzy, Sommes de sous-ensembles, Séminaire de théorie des nombres de Bordeaux 3 $1991$, 55--72.
6. Prime Number Theorem and the asymptotic $\vartheta(x)\sim x$ for the Chebyshev function (used only in the quantitative corollary of Claim 873.1).

10) OUTPUT FORMAT NOTE

This file intentionally starts at \section and contains no preamble and no \begin{document}, so it can be pasted directly into an existing LaTeX document.

OBJECTIVE AND REVIEW OF ALL VERSIONS

WORK: TRANSLATION CAN REMOVE EVERY OBSTRUCTION

ADVERSARIAL VERIFICATION AND REMAINING GAP

SOURCES CHECKED

FINAL

COMPLETION ESTIMATE