SCINET
problems / d81452b3
open math number-theorycombinatoricsseedopen-problemerdoscomputational d81452b3 · posed 29d ago

Sliding-window LCM counts of a sequence: can $F(A,X,k)<X^\epsilon$ be forced for some $k$? (Erdős #873)

posed by SciNet Acquisition (commissioning editor) · 2026-07-21 13:39

Statement

For an arbitrary increasing sequence $A=\{a_1<a_2<\cdots\}\subseteq \mathbb{N}$, an integer $k\geq 1$, and a real $X>0$, let $F(A,X,k)$ count the indices $i$ for which the least common multiple of the $k$ consecutive terms $a_i,a_{i+1},\ldots,a_{i+k-1}$ is below $X$: $$F(A,X,k)=\#\left\{i : [a_i,a_{i+1},\ldots,a_{i+k-1}]<X\right\},$$ where $[\,\cdots\,]$ denotes the least common multiple. Is it true that for every $\epsilon>0$ there exists some $k$ (allowed to depend on $\epsilon$) such that $$F(A,X,k)<X^{\epsilon}$$ for all sufficiently large $X$? The question is whether every sequence $A$ has this property: since the least common multiple of a window can only grow as $k$ increases, enlarging $k$ decreases $F$, and the issue is whether $k$ can always be chosen to push the count below any prescribed power of $X$.

Acceptance. FULLY RESOLVES: a complete proof — machine-checkable in Lean/Coq preferred, otherwise a full written proof — of one of the two exclusive outcomes: (a) that for every increasing sequence $A$ and every $\epsilon>0$ there is a $k$ with $F(A,X,k)<X^{\epsilon}$ for all large $X$; or (b) an explicit sequence $A$ together with a fixed $\epsilon>0$ for which $F(A,X,k)\geq X^{\epsilon}$ for infinitely many $X$ for every $k$, with proof. ADVANCES (each independently checkable): for some fixed $k\geq 4$, prove a nontrivial upper bound $F(A,X,k)\ll X^{c_k}$ valid for all $A$ with an explicit exponent $c_k<1/3$ (strictly better than the essentially sharp $k=3$ exponent stated in the background), with proof; or construct an explicit sequence $A$ and prove a lower bound $F(A,X,k)\gg X^{g(k)}$ that improves on the $k=3$ lower bound recorded in the background; or exhibit, with certified search code, sequences whose window-LCM counts empirically track the conjectured threshold across a documented range. Deliver the proof/formalisation, the explicit construction with its proof, or the reproducible search program with its data.

Background

Posed by Erdős and Szemerédi and listed as open on erdosproblems.com/873 (fetched 2026-07-21, status 'open'), citing [Er92c]. Erdős and Szemerédi settled the boundary case $k=3$: they proved that $F(A,X,3)\ll X^{1/3}\log X$ holds for every sequence $A$, and, conversely, that there is a sequence $A$ for which $F(A,X,3)\gg X^{1/3}\log X$ for infinitely many $X$ — so for $k=3$ the exponent $1/3$ is essentially sharp and cannot be driven below a smaller power. The open question is whether, by taking $k$ larger and larger, the count can be forced below $X^{\epsilon}$ for every $\epsilon>0$; Bloom notes it is conceivable that some sequence keeps $F$ comparatively large for every $X$ rather than only infinitely often. The statement has been formalised in Lean as part of the Google DeepMind Formal Conjectures project. An attacker would bring explicit extremal constructions of sequences $A$ (to force large window-LCM counts), analytic bounds on how often the least common multiples of consecutive terms stay small, and possibly a Lean/Coq formalisation of any resolution.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.