Erdős Problem #873

Round 2 continuation for Erdős Problem #873

1) ROUND-2 OBJECTIVE

I pursue path (C). The most promising Round-2 advance is to identify a genuine obstruction to any fixed-$k$ strategy. Round 1 already explained that the known Erdős--Szemerédi bound for $k=3$ settles the problem only for exponents $\varepsilon>1/3$. What was still missing was a rigorous reason that one cannot hope to settle the full conjecture with one universal, fixed value of $k$. I will prove exactly that.

2) Round-1 FOUNDATION USED

I use the following Round 1 results without reproving them.

1. Round 1 defined \[ F(A,X,k)=\#\Big\{i\ge 1:\operatorname{lcm}(a_i,a_{i+1},\dots,a_{i+k-1})<X\Big\} \] for $A=\{a_1<a_2<\cdots\}\subset \mathbf{N}$.
2. Round 1 proved monotonicity in the block length: \[ k'\ge k \implies F(A,X,k')\le F(A,X,k). \]
3. Round 1 noted that the known Erdős--Szemerédi theorem for $k=3$ gives \[ F(A,X,3)\ll X^{1/3}\log X, \] so the original problem is only difficult for $\varepsilon\le 1/3$.

3) NEW INSIGHT / TOOL (ROUND-2)

The new tool is a divisor-block construction. For each large parameter $y$, take the primorial \[ P(y):=\prod_{p\le y}p, \] pick a prime $q>y$ coprime to $P(y)$, and form the block \[ B=\{qd:d\mid P(y)\}. \] Inside such a block, every $k$ consecutive terms have least common multiple at most $qP(y)$, while the block length is exactly the divisor count $\tau(P(y))=2^{\pi(y)}$. By concatenating many such blocks far apart, one gets an infinite sequence for which $F(A,X,k)$ is very large infinitely often for any fixed $k$.

4) ATTACK PLAN (ROUND-2)

The precise Round 1 gap was the absence of a theorem showing that $k$ really must depend on the set $A$. I will now prove the following claim.

Target claim. For every fixed integer $k\ge 1$, there exists an infinite set $A\subset \mathbf{N}$ and a sequence $X_t\to\infty$ such that \[ F(A,X_t,k)\ge \exp\!\left((\log 2+o(1))\frac{\log X_t}{\log\log X_t}\right). \]

This implies that no upper bound of polylogarithmic size can hold uniformly for all sets $A$ with a single fixed $k$. Hence any eventual proof of the original conjecture must use the freedom to choose $k=k(A,\varepsilon)$.

5) WORK (ROUND-2)

Let $k\ge 1$ be fixed once and for all.

Claim 873.1. There exists an infinite increasing set $A\subset \mathbf{N}$ and a sequence $X_t\to\infty$ such that \[ F(A,X_t,k)\ge \exp\!\left((\log 2+o(1))\frac{\log X_t}{\log\log X_t}\right). \] In particular, for every constant $C>0$, \[ F(A,X_t,k)>(\log X_t)^C \] for all sufficiently large $t$.

Proof. Choose a sequence $y_t\to\infty$ recursively so rapidly that, for every $t\ge 2$, \[ y_t>q_{t-1}P_{t-1}, \] where $P_{t-1}$ and $q_{t-1}$ are objects defined at the previous stage.

For each $t$, define \[ P_t:=\prod_{p\le y_t}p. \] By Bertrand's postulate, there exists a prime $q_t$ with \[ y_t<q_t<2y_t. \] Since every prime factor of $P_t$ is at most $y_t$, we have \[ \gcd(q_t,P_t)=1. \]

Now define the finite block \[ B_t:=\{q_t d:d\mid P_t\}, \] listed in increasing order. Because $q_t>q_{t-1}P_{t-1}$, every element of $B_t$ is larger than every element of $B_{t-1}$. Hence the disjoint union \[ A:=B_1\cup B_2\cup B_3\cup \cdots \] is an infinite increasing sequence.

Set \[ X_t:=q_tP_t+1. \] Consider any run of $k$ consecutive elements lying entirely inside the block $B_t$, say \[ q_t d_1<q_t d_2<\cdots<q_t d_k \] with each $d_j\mid P_t$. Since $q_t$ is coprime to $P_t$, \[ \operatorname{lcm}(q_t d_1,\dots,q_t d_k)=q_t\,\operatorname{lcm}(d_1,\dots,d_k)\le q_tP_t<X_t. \] Therefore every starting position of a length-$k$ window wholly contained in $B_t$ contributes to $F(A,X_t,k)$. So \[ F(A,X_t,k)\ge |B_t|-k+1. \]

Because $P_t$ is squarefree, the number of divisors of $P_t$ is \[ |B_t|=\tau(P_t)=2^{\pi(y_t)}, \] where $\pi(y_t)$ is the number of primes at most $y_t$. Hence \[ F(A,X_t,k)\ge 2^{\pi(y_t)}-k+1. \]

Now use the prime number theorem and the standard asymptotic $\vartheta(y)\sim y$ for the Chebyshev function. Since \[ \log P_t=\vartheta(y_t)\sim y_t, \qquad \pi(y_t)\sim \frac{y_t}{\log y_t}, \] and $q_t<2y_t$, we get \[ \log X_t=\log(q_tP_t+1)=(1+o(1))y_t, \qquad \log\log X_t=(1+o(1))\log y_t. \] Substituting into the lower bound for $F(A,X_t,k)$ yields \[ \log F(A,X_t,k)\ge (\log 2+o(1))\frac{\log X_t}{\log\log X_t}, \] which is equivalent to \[ F(A,X_t,k)\ge \exp\!\left((\log 2+o(1))\frac{\log X_t}{\log\log X_t}\right). \]

Finally, since \[ \frac{\log X_t}{\log\log X_t}\gg \log\log X_t, \] the above lower bound dominates every power of $\log X_t$. Thus for any fixed $C>0$, \[ F(A,X_t,k)>(\log X_t)^C \] for all sufficiently large $t$. $\Box$

Corollary 873.2. Fix $k_0\ge 1$. There is no bound of the form \[ F(A,X,k_0)\le (\log X)^C \] that can hold uniformly for all infinite $A\subset \mathbf{N}$ and all large $X$.

Proof. Apply Claim 873.1 with $k=k_0$. The resulting set $A$ violates any such bound along the sequence $X_t$. $\Box$

Interpretation. This does not disprove the Erdős--Szemerédi problem, because the original statement allows $k$ to depend on $A$ and on $\varepsilon$. What it proves is a genuine obstruction: a proof with one fixed universal $k$ cannot work.

6) ADVERSARIAL VERIFICATION

I check the potential failure points one by one.

1. Are the blocks really increasing? Yes. The recursive choice $y_t>q_{t-1}P_{t-1}$ implies $q_t>y_t>q_{t-1}P_{t-1}$, so every element of $B_t$ exceeds every element of $B_{t-1}$.
2. Do the lcm computations use hidden assumptions? No. Since $\gcd(q_t,P_t)=1$, one has \[ \operatorname{lcm}(q_t d_1,\dots,q_t d_k)=q_t\operatorname{lcm}(d_1,\dots,d_k). \]
3. Do cross-block windows matter? No. I only need a lower bound for $F(A,X_t,k)$, so it suffices to count windows lying entirely inside $B_t$.
4. Is the quantitative asymptotic consistent? Yes. The divisor count of a primorial is $2^{\pi(y_t)}$, and the prime number theorem gives exactly the stated exponential-in-$\log X/\log\log X$ size.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 2 proves a new obstruction absent from Round 1: for every fixed $k$, there exists an infinite set $A$ for which $F(A,X,k)$ is larger than every power of $\log X$ infinitely often. Thus any proof of the original conjecture must use the freedom to let $k$ depend on $A$ and $\varepsilon$. The full Erdős--Szemerédi question nevertheless remains open.

8) COMPLETION ESTIMATE

COMPLETION: 38%

9) REFERENCES

1. T. F. Bloom, Erdős Problem #873, problem page.

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 #873 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 #873: a new fixed-$k$ obstruction

For a fixed infinite set $A=\{a_1<a_2<\cdots\}\subset \mathbf{N}$, recall \[ F(A,X,k) := \#\big\{i\ge 1 : \mathrm{lcm}(a_i,a_{i+1},\dots,a_{i+k-1}) < X\big\}. \]

Claim 873.1. Fix $k\ge 1$. There exists an infinite increasing set $A\subset \mathbf{N}$ and a sequence $X_t\to\infty$ such that \[ F(A,X_t,k) \ge \exp\!\left((\log 2 + o(1))\frac{\log X_t}{\log\log X_t}\right). \] In particular, for every fixed $C>0$, \[ F(A,X_t,k) > (\log X_t)^C \] for all sufficiently large $t$.

Proof. Choose a rapidly increasing sequence of real numbers $y_t\to\infty$ recursively so that \[ y_t > q_{t-1}P_{t-1} \] for every $t\ge 2$, where $P_{t-1}$ and $q_{t-1}$ will be defined below. For each $t$, let \[ P_t := \prod_{p\le y_t} p, \] where the product runs over all primes $p\le y_t$.

By Bertrand's postulate there exists a prime $q_t$ with \[ y_t < q_t < 2y_t. \] Since every prime factor of $P_t$ is at most $y_t$, this gives \[ \gcd(q_t,P_t)=1. \] Also, because $y_t > q_{t-1}P_{t-1}$, we have \[ q_t > y_t > q_{t-1}P_{t-1}, \] so the intervals $[q_t, q_tP_t]$ are strictly increasing and pairwise disjoint.

Now define a finite block \[ B_t := \{q_t d : d\mid P_t\}, \] listed in increasing order. Because the blocks are disjoint and ordered by size, the infinite union \[ A := B_1 \cup B_2 \cup B_3 \cup \cdots \] forms an increasing sequence.

Set \[ X_t := q_tP_t + 1. \] Take any $k$ consecutive elements of the block $B_t$, say \[ q_t d_1 < q_t d_2 < \cdots < q_t d_k, \] with each $d_j\mid P_t$. Since $\gcd(q_t,P_t)=1$, \[ \mathrm{lcm}(q_t d_1,\dots,q_t d_k) = q_t\,\mathrm{lcm}(d_1,\dots,d_k) \le q_tP_t < X_t. \] Hence every starting position of a length-$k$ run entirely inside the block $B_t$ contributes to $F(A,X_t,k)$. Therefore \[ F(A,X_t,k) \ge |B_t|-k+1. \] Now $|B_t|$ is the number of divisors of $P_t$, and since $P_t$ is squarefree, \[ |B_t| = \tau(P_t)=2^{\pi(y_t)}, \] where $\pi(y_t)$ is the number of primes at most $y_t$. Thus \[ F(A,X_t,k) \ge 2^{\pi(y_t)}-k+1. \] Taking logarithms and using the prime number theorem together with the standard asymptotic \[ \log P_t = \vartheta(y_t) \sim y_t, \] we obtain \[ \pi(y_t) = (1+o(1))\frac{y_t}{\log y_t}, \qquad \log X_t = \log(q_tP_t+1) = (1+o(1))y_t, \qquad \log\log X_t = (1+o(1))\log y_t. \] Substituting into the previous bound yields \[ \log F(A,X_t,k) \ge (\log 2 + o(1))\frac{\log X_t}{\log\log X_t}, \] which is the claimed quantitative lower bound.

Finally, for any fixed $C>0$, \[ (\log 2 + o(1))\frac{\log X_t}{\log\log X_t} \gg \log\log X_t, \] so exponentiating gives \[ F(A,X_t,k) > (\log X_t)^C \] for all large $t$. $\Box$

Corollary 873.2. No theorem of the form \[ F(A,X,k_0) \le (\log X)^C \] can hold uniformly for all infinite $A$ with a fixed value of $k_0$.

Explanation. Claim 873.1 gives a counterexample for every fixed $k_0$. This does not refute the original Erdős--Szemerédi problem, because that problem allows $k$ to depend on $A$ and on $\varepsilon$. What it does show is that allowing $k$ to grow is genuinely necessary.

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 #873: independent continuation

1) TARGET AND SOURCE AUDIT

All supplied versions considered: 873.tex, 873_v2.tex. Both versions give the same divisor-block lower bound and claim it forces dependence of $k$ on $A$ and $\epsilon$. That inference is not justified: their lower bound is $X^{o(1)}$, compatible with every fixed positive power. The blocks themselves do not depend on $k$, so one set already works simultaneously for every fixed $k$. I replace the inference by a precise elementary obstruction from $A=\mathbb N$.

2) WORK

Consecutive integers give the right fixed-$k$ obstruction.

Every $m$ with $m+k-1<X^{1/k}$ is counted by $F(\mathbb N,X,k)$, while $1$ shows every counted $m$ is smaller than $((k-1)!X)^{1/k}$. Therefore \[ F(\mathbb N,X,k)=\Theta_k(X^{1/k})\qquad(X\to\infty). \] In particular no fixed $k$ can handle every $\epsilon>0$: choose $\epsilon<1/k$. A necessary condition for a proposed $k$ at exponent $\epsilon$ is $1/k\le\epsilon$. This argument does not establish that $k$ must depend on $A$; uniformity over $A$ at a fixed $\epsilon$ remains a different issue.

The source's primorial lower bound has exponent $(\log2+o(1))/\log\log X\to0$, so it proves a super-polylogarithmic obstruction only. Calling it an obstruction to all power bounds confuses two different scales.

3) ADVERSARIAL VERIFICATION

4) FINAL

5) SOURCES CHECKED

6) COMPLETION ESTIMATE