Erdős Problem #875

Round 2 continuation for Erdős Problem #875

1) ROUND-2 OBJECTIVE

I pursue path (C). Round 1 contained a concrete factual gap: it treated polynomial-growth infinite admissible sets as if they might still be unknown. The most promising and necessary Round-2 move is therefore to correct the statement of what is already known, and then to extract the strongest rigorous consequences for the growth and gap questions.

2) Round-1 FOUNDATION USED

I use the following Round 1 ingredients without reproving them.

1. Round 1 set up the infinite admissible-set problem for \[ A=\{a_1<a_2<\cdots\}\subset \mathbf{N}, \] where the sets of sums of exactly $r$ distinct elements are pairwise disjoint for different $r$.
2. Round 1 observed that every finite initial segment $A\cap [1,N]$ is itself admissible.
3. Round 1 therefore reduced universal upper bounds for infinite admissible sets to finite extremal results inside $[1,N]$.

3) NEW INSIGHT / TOOL (ROUND-2)

There are two new external inputs.

1. Erdős, Nicolas, and Sárkőzy proved in 1991 that there exists an infinite admissible set $A$ with \[ A(x):=\#\{a\in A:a\le x\}\gg x^{5-2\sqrt 6}. \] This corrects the main factual gap in Round 1.
2. Deshouillers and Freiman proved that, for all sufficiently large $N$, every admissible subset $B\subset [1,N]$ satisfies \[ |B|\le 2\sqrt{N+\tfrac14}-1. \] Applied to $A\cap [1,N]$, this yields the sharp universal upper bound \[ A(N)\le 2\sqrt N+O(1). \]

Together these produce a genuine growth window for infinite admissible sets.

4) ATTACK PLAN (ROUND-2)

The exact Round 1 issue was that the status summary for Problem #875 was too pessimistic. I will now do four things.

1. Correct the Round 1 error by importing the 1991 Erdős--Nicolas--Sárkőzy construction.
2. Derive a polynomial upper bound for the $n$-th term: \[ a_n\ll n^{5+2\sqrt 6}. \]
3. Combine the finite Deshouillers--Freiman theorem with the initial-segment observation to obtain \[ A(x)\le 2\sqrt x+O(1),\qquad a_n\ge \frac{n^2}{4}+O(n). \]
4. Convert these into consequences for gaps $a_{n+1}-a_n$, especially the bracket \[ c<\frac12 \text{ impossible},\qquad c>5+2\sqrt 6 \text{ possible}. \]

This directly resolves the main Round 1 gap and gives a sharper quantitative status report.

5) WORK (ROUND-2)

Correction 875.0. Round 1 overlooked the following theorem of Erdős, Nicolas, and Sárkőzy: there exists an infinite admissible set $A\subset \mathbf{N}$ such that \[ A(x)\gg x^{5-2\sqrt 6}. \]

Claim 875.1. There exists an infinite admissible sequence $A=\{a_n\}_{n\ge 1}$ such that \[ a_n\ll n^{5+2\sqrt 6}. \] Consequently, \[ \liminf_{n\to\infty}\frac{a_{n+1}}{a_n}=1. \]

Proof. Let \[ \alpha:=5-2\sqrt 6. \] By Correction 875.0 there exists an admissible infinite set with \[ A(x)\ge c x^\alpha \] for all sufficiently large $x$, where $c>0$. Evaluate this at $x=a_n$. Then \[ n=A(a_n)\ge c a_n^\alpha \] for all large $n$, so \[ a_n\le C n^{1/\alpha} \] for some constant $C>0$. Since \[ \frac1{5-2\sqrt6}=5+2\sqrt6, \] we obtain \[ a_n\ll n^{5+2\sqrt6}. \]

Now suppose, for contradiction, that \[ \liminf_{n\to\infty}\frac{a_{n+1}}{a_n}>1. \] Then there exist $\eta>0$ and $n_0$ such that \[ a_{n+1}\ge (1+\eta)a_n \] for all $n\ge n_0$. Iterating gives \[ a_n\ge a_{n_0}(1+\eta)^{n-n_0}, \] so $a_n$ grows exponentially. This contradicts the polynomial bound $a_n\ll n^{5+2\sqrt6}$. Hence \[ \liminf_{n\to\infty}\frac{a_{n+1}}{a_n}=1. \] $\Box$

Claim 875.2. Every infinite admissible sequence $A=\{a_n\}$ satisfies \[ A(x)\le 2\sqrt x+O(1). \] More precisely, for all sufficiently large integers $N$, \[ A(N)\le 2\sqrt{N+\tfrac14}-1. \] Consequently, \[ a_n\ge \frac{n(n+2)}{4} \] for all sufficiently large $n$, and in particular \[ a_n\ge \frac{n^2}{4}+O(n). \]

Proof. Fix an infinite admissible set $A\subset \mathbf{N}$. For every sufficiently large integer $N$, the finite set \[ A\cap [1,N] \] is an admissible subset of $[1,N]$. By the Deshouillers--Freiman theorem, \[ |A\cap [1,N]|\le 2\sqrt{N+\tfrac14}-1. \] This is exactly the stated bound for $A(N)$, and replacing $N$ by $\lfloor x\rfloor$ yields \[ A(x)\le 2\sqrt x+O(1). \]

Now put $x=a_n$. Then \[ n=A(a_n)\le 2\sqrt{a_n+\tfrac14}-1 \] for all sufficiently large $n$. Therefore \[ n+1\le 2\sqrt{a_n+\tfrac14}, \] and squaring gives \[ a_n\ge \frac{(n+1)^2-1}{4}=\frac{n(n+2)}{4}. \] The displayed $n^2/4+O(n)$ bound follows immediately. $\Box$

Claim 875.3. If an infinite admissible sequence satisfies \[ a_{n+1}-a_n\le c n \] for all sufficiently large $n$, then necessarily \[ c\ge \frac12. \] Equivalently, \[ \limsup_{n\to\infty}\frac{a_{n+1}-a_n}{n}\ge \frac12. \]

Proof. Assume instead that there exist $\varepsilon>0$ and $n_0$ such that \[ a_{n+1}-a_n\le \Big(\frac12-\varepsilon\Big)n \] for all $n\ge n_0$. Summing from $n_0$ to $n-1$ yields \[ a_n\le a_{n_0}+\Big(\frac12-\varepsilon\Big)\sum_{j=n_0}^{n-1}j = \Big(\frac14-\frac{\varepsilon}{2}\Big)n^2+O(n). \] But Claim 875.2 shows that every admissible sequence satisfies \[ a_n\ge \frac{n(n+2)}{4}=\frac14 n^2+\frac12 n \] for all sufficiently large $n$. The quadratic coefficients are incompatible: \[ \frac14-\frac{\varepsilon}{2}<\frac14. \] So the assumed eventual gap bound is impossible. This proves the claim. $\Box$

Claim 875.4. For every real number $c>5+2\sqrt 6$, there exists an infinite admissible sequence with \[ a_{n+1}-a_n\le n^c \] for all sufficiently large $n$.

Proof. Take the admissible sequence from Claim 875.1. For some constant $C>0$, \[ a_n\le C n^{5+2\sqrt 6} \] for all sufficiently large $n$. Hence \[ a_{n+1}-a_n\le a_{n+1}\le C(n+1)^{5+2\sqrt 6}. \] If $c>5+2\sqrt 6$, then \[ C(n+1)^{5+2\sqrt 6}\le n^c \] for all sufficiently large $n$. Therefore the same sequence satisfies \[ a_{n+1}-a_n\le n^c \] eventually. $\Box$

Updated quantitative status. The original Problem #875 remains open, but the Round 1 status summary must be replaced by the following corrected bracket: \[ c<\frac12 \text{ is impossible},\qquad c>5+2\sqrt 6 \text{ is possible}. \] Moreover there exists an admissible infinite set of polynomial growth, and in particular one with \[ \liminf_{n\to\infty}\frac{a_{n+1}}{a_n}=1. \]

6) ADVERSARIAL VERIFICATION

The main points that could fail are the following.

1. Did Round 2 really identify an error in Round 1? Yes. Round 1 treated polynomial-growth admissible sets as still potentially unknown, but Erdős--Nicolas--Sárkőzy already constructed one in 1991.
2. Does polynomial growth imply $a_{n+1}/a_n\to 1$? No, and I do not claim that. The rigorous conclusion proved above is only \[ \liminf_{n\to\infty}\frac{a_{n+1}}{a_n}=1. \]
3. Does the finite Deshouillers--Freiman theorem really transfer to the infinite problem? Yes. Every initial segment $A\cap [1,N]$ is admissible, so the finite extremal theorem applies directly.
4. Is the gap obstruction coefficient-level sharp? The proof of Claim 875.3 uses only the leading quadratic coefficient, so lower-order terms cannot repair the contradiction.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 2 corrects a concrete Round 1 error and substantially sharpens the status of Problem #875.

1. Infinite admissible sets of polynomial growth already exist: \[ A(x)\gg x^{5-2\sqrt 6},\qquad a_n\ll n^{5+2\sqrt 6}. \]
2. Every infinite admissible set satisfies the universal upper bound \[ A(x)\le 2\sqrt x+O(1), \] hence \[ a_n\ge \frac{n^2}{4}+O(n). \]
3. For the gap exponent question, one now has the rigorous bracket \[ c<\frac12 \text{ impossible},\qquad c>5+2\sqrt 6 \text{ possible}. \]

The full optimal growth law is still unknown, so the original Erdős problem remains open.

8) COMPLETION ESTIMATE

COMPLETION: 72%

9) REFERENCES

1. T. F. Bloom, Erdős Problem #875, problem page.
2. T. F. Bloom, Erdős Problem #874, problem page.
3. P. Erdős, J.-L. Nicolas, and A. Sárkőzy, Sommes de sous-ensembles, Journal de Théorie des Nombres de Bordeaux 3 $1991$, 55--72.
4. 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 #875 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 #875: correcting Round 1 and pushing the consequences

Round 1 stated, in effect, that polynomial growth and even $\liminf a_{n+1}/a_n=1$ might still be open for infinite admissible sets. This is incorrect.

Correction 875.0. Erdős--Nicolas--Sárkőzy proved in 1991 that there exists an infinite admissible set $A\subset \mathbf{N}$ such that \[ A(x) := \#\{a\in A : a\le x\} \gg x^{5-2\sqrt6}. \] Thus polynomial-density admissible sets are already known.

Claim 875.1. There exists an infinite admissible sequence $A=\{a_n\}_{n\ge 1}$ such that \[ a_n \ll n^{5+2\sqrt6}. \] Consequently, \[ \liminf_{n\to\infty}\frac{a_{n+1}}{a_n}=1. \]

Proof. Let $\alpha:=5-2\sqrt6$. By Correction 875.0 there is an admissible infinite set with \[ A(x) \ge c x^{\alpha} \] for all large $x$, with some constant $c>0$. Evaluating at $x=a_n$ gives \[ n = A(a_n) \ge c a_n^{\alpha} \] for all large $n$, hence \[ a_n \le C n^{1/\alpha} \] for some $C>0$. Since \[ \frac{1}{5-2\sqrt6}=5+2\sqrt6, \] this becomes \[ a_n \ll n^{5+2\sqrt6}. \]

Now suppose, for contradiction, that \[ \liminf_{n\to\infty}\frac{a_{n+1}}{a_n} > 1. \] Then there exist $\eta>0$ and $n_0$ such that \[ a_{n+1} \ge (1+\eta)a_n \] for all $n\ge n_0$. Iterating, \[ a_n \ge a_{n_0}(1+\eta)^{n-n_0}, \] so $a_n$ grows exponentially. This contradicts the polynomial upper bound $a_n\ll n^{5+2\sqrt6}$. Therefore \[ \liminf_{n\to\infty}\frac{a_{n+1}}{a_n}=1. \] $\Box$

Claim 875.2. Every infinite admissible sequence $A=\{a_n\}$ satisfies \[ A(x) \le 2\sqrt x + O(1), \qquad a_n \ge \frac{n^2}{4} + O(n). \] More precisely, for all sufficiently large integers $N$, \[ A(N) \le 2\sqrt{N+\tfrac14}-1, \] and hence for all sufficiently large $n$, \[ a_n \ge \frac{n(n+2)}{4}. \]

Proof. Let $A$ be any infinite admissible set. For every sufficiently large integer $N$, the finite set \[ A\cap [1,N] \] is an admissible subset of $[1,N]$. By the Deshouillers--Freiman theorem, \[ |A\cap [1,N]| \le 2\sqrt{N+\tfrac14}-1. \] This is the asserted bound for $A(N)$. Replacing $N$ by $\lfloor x\rfloor$ gives \[ A(x) \le 2\sqrt x + O(1). \] Now take $x=a_n$. Then for all large $n$, \[ n = A(a_n) \le 2\sqrt{a_n+\tfrac14}-1. \] Hence \[ n+1 \le 2\sqrt{a_n+\tfrac14}, \] so after squaring, \[ a_n \ge \frac{(n+1)^2-1}{4} = \frac{n(n+2)}{4}. \] This implies $a_n\ge n^2/4 + O(n)$. $\Box$

Claim 875.3. If an infinite admissible sequence satisfies \[ a_{n+1}-a_n \le c n \] for all sufficiently large $n$, then necessarily \[ c\ge \frac12. \] Equivalently, \[ \limsup_{n\to\infty}\frac{a_{n+1}-a_n}{n} \ge \frac12. \]

Proof. Assume to the contrary that there exists $\varepsilon>0$ and $n_0$ such that \[ a_{n+1}-a_n \le \left(\frac12-\varepsilon\right)n \] for every $n\ge n_0$. Summing from $n_0$ to $n-1$ gives \[ a_n \le a_{n_0} + \left(\frac12-\varepsilon\right)\sum_{j=n_0}^{n-1} j = \left(\frac14-\frac{\varepsilon}{2}\right)n^2 + O(n). \] But Claim 875.2 shows that every admissible sequence satisfies \[ a_n \ge \frac{n(n+2)}{4} = \frac14 n^2 + \frac12 n \] for all sufficiently large $n$. These two estimates are incompatible for large $n$. Hence the assumed eventual bound is impossible, and the stated conclusions follow. $\Box$

Claim 875.4. For every real $c>5+2\sqrt6$, there exists an infinite admissible sequence with \[ a_{n+1}-a_n \le n^c \] for all sufficiently large $n$.

Proof. Take the sequence from Claim 875.1. Then there is a constant $C>0$ such that \[ a_n \le C n^{5+2\sqrt6} \] for all sufficiently large $n$. Therefore \[ a_{n+1}-a_n \le a_{n+1} \le C(n+1)^{5+2\sqrt6}. \] If $c>5+2\sqrt6$, then $C(n+1)^{5+2\sqrt6} \le n^c$ for all sufficiently large $n$, and the claim follows. $\Box$

Updated state of Problem #875. Round 1's final discussion must therefore be replaced by the following corrected bracket.

• There do exist infinite admissible sets of polynomial growth: in fact $A(x)\gg x^{5-2\sqrt6}$, so $a_n\ll n^{5+2\sqrt6}$.
• Consequently, there exists an admissible set with $\liminf a_{n+1}/a_n = 1$.
• Every admissible set satisfies $A(x)\le 2\sqrt x + O(1)$, hence $a_n\ge n^2/4 + O(n)$.
• For the gap exponent question, it is now rigorously known that \[ c<\frac12 \quad \text{is impossible}, \qquad c>5+2\sqrt6 \quad \text{is possible}. \]

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.

Erdős Problem #875: independent continuation

1) TARGET AND SOURCE AUDIT

All supplied versions considered: 875.tex, 875_v2.tex. Both versions use the same valid published polynomial-density construction and finite upper bounds. Their discussion mixes a linear-gap coefficient with a power exponent. I give a self-contained sum-of-terms inequality improving their stated linear-gap obstruction, and a stronger interpretation of the known polynomial-growth example.

2) WORK

Count all subset-sum cardinalities together.

Polynomial growth controls the frequency of relative jumps.

3) ADVERSARIAL VERIFICATION

4) FINAL

5) SOURCES CHECKED

6) COMPLETION ESTIMATE