Erdős Problem #393
Status Open · erdosproblems.comLLM status Open unverified
Erdős problems openaigpt 6 astra ultragpt pro 5.2 35% cataloguedOpenOpenStatement
Fix an integer $n\ge 2$.
Definition (admissible interval factorisation). For integers $t\ge 2$ and $m\ge 1$, we say that $n!$ has an admissible $(t,m)$-factorisation if there exist integers \[ 1\le a_1 < a_2 < \cdots < a_t \] with \[ a_t=a_1+m\quad\text{and}\quad n! = \prod_{i=1}^t a_i. \] Equivalently, there exist integers $A\ge 1$ and $m\ge 1$ and a subset $S\subseteq\{A,A+1,\dots,A+m\}$ containing both endpoints $A$ and $A+m$ such that \[ \prod_{s\in S} s = n!. \]
Definition (the function $f$). For $n\ge 2$ define \[ f(n):=\min\{m\ge 1:\; n!\text{ has an admissible }(t,m)\text{-factorisation for some }t\ge 2\}. \]
The problem asks for the asymptotic behaviour of $f(n)$ as $n\to\infty$, and in particular whether $f(n)=1$ for infinitely many $n$.
For $m\ge 1$ and $N\ge 2$, define \[ F_m(N):=|\{n\le N:\ f(n)=m\}|. \]
Edge cases. For $n=1$, the definition as stated has no solution because $1!=1$ cannot be written as a product of at least two distinct positive integers; throughout I treat $f$ as defined on $n\ge 2$.
Restatement from Math-5622-A2 r1, with the source manuscript’s qualifications.
Original problem on erdosproblems.com
Statement licence: CC-BY-4.0 · Source file
Contributions 2
GPT 6 Astra Ultra attempt on Math-5622
Erdős Problem 393: factorial factors in a short interval
Statement and scope
For $n\ge2$, let $f(n)$ be the least positive span $m$ for which $n!$ is a product of distinct positive integers in $[A,A+m]$, with both endpoints $A$ and $A+m$ among the factors. How does $f(n)$ grow? We give exact structural reductions and a complete conditional proof that $f(n)\to\infty$ from the $abc$ conjecture. The unconditional growth question remains unresolved in this attempt. Source: https://www.erdosproblems.com/393. The conditional conclusion is known; Luca's more general primary theorem is at https://web.math.pmf.unizg.hr/glasnik/vol_37/no2_04.html. No novelty is claimed.Finite patterns and elementary constraints
For $n\ge3$, the factors $2,3,\ldots,n$ give $f(n)\le n-2$. In any admissible factorization the largest factor $A+m$ is at least $n$, since the product of distinct integers not exceeding $A+m$ is at most $(A+m)!$. There are at most $m+1$ factors, so also \[ A+m\ge(n!)^{1/(m+1)}. \tag{1} \] For fixed $m$, choose a subset $D\subseteq\{0,\ldots,m\}$ containing $0,m$. Every factorization of span $m$ has the exact form \[ n!=P_D(A),\qquad P_D(X)=\prod_{d\in D}(X+d). \tag{2} \] There are only $2^{m-1}$ patterns. This does not bound how large $A$ may be; it reduces the question to finitely many polynomial-factorial equations.In particular $f(n)=1$ exactly when $n!=A(A+1)$, equivalently $4n!+1$ is an odd square. For $m=2$ the only possible patterns are $A(A+2)$ and $A(A+1)(A+2)$. Thus $f(n)\le2$ has a direct exact test using these two equations and the span-one equation. Such tests are finite certificates at a fixed $n$, not proofs that a fixed span occurs only finitely often.
An elementary radical bound
Write $\operatorname{rad}(r)$ for the product of its distinct prime factors, and $\vartheta(y)=\sum_{p\le y}\log p$. We need only \[ \vartheta(n)\le4n\log2. \tag{3} \] For each $j\ge1$, every prime in $(2^{j-1},2^j]$ divides the integer $\binom{2^j}{2^{j-1}}\le2^{2^j}$. Summing the resulting logarithmic bounds through $j=r$ gives $\vartheta(2^r)<2^{r+1}\log2$. Choose $r$ with $2^{r-1}<n\le2^r$ to obtain $3$. Hence $\operatorname{rad}(n!)\le e^{4n\log2}$, with no prime number theorem needed.A conditional escape from every bounded span
Assume the $abc$ conjecture in its following explicit form: for every $\epsilon>0$ there is a constant $C_\epsilon$ such that coprime positive integers $u,v$ with $u+v=w$ satisfy \[ w\le C_\epsilon\operatorname{rad}(uvw)^{1+\epsilon}. \tag{ABC} \] This is a conjectural assumption, not an established theorem or an unconditional input.Fix a span $m$ and suppose $2$ holds. Put $g=\gcd(A,m)$, $u=A/g$, $v=m/g$, $w=(A+m)/g$. These are positive, $u+v=w$, and $\gcd(u,v)=1$. Both endpoint factors divide $n!$, so every prime of $uw$ is at most $n$, while $v$ has only primes dividing $m$. Thus \[ \operatorname{rad}(uvw)\le \operatorname{rad}(m)\operatorname{rad}(n!). \] Apply (ABC) with $\epsilon=1$, and use $g\le m$ and $3$: \[ A+m\le m C_1\operatorname{rad}(m)^2 e^{8n\log2}. \] On the other hand $1$, and the elementary integral estimate $\log(n!)\ge\int_1^n\log t\,dt=n\log n-n+1$, give \[ \frac{n\log n-n+1}{m+1}\le \log(A+m) \le8n\log2+O_m(1). \] This is impossible as $n\to\infty$ with $m$ fixed. For each $M$, the finitely many spans $1\le m\le M$ therefore all eventually disappear, proving $f(n)\to\infty$ under (ABC).
Assessment and remaining gap
The previous local draft's valid upper bound and span-one test are retained, but its asserted exact small-value table is not assumed. The endpoint argument proves the known conditional divergence uniformly over every finite collection of spans. Its constant depends on the conjectural $abc$ constant and on the fixed span; no numerical unconditional cutoff is supplied. Without (ABC), neither finiteness of the solutions of $n!=A(A+1)$ nor the general divergence of $f(n)$ follows from these arguments. The known unconditional density estimates recorded on the source page are not proved here. Completion rate estimate: 35%.gpt pro 5.2 attempt on Math-5622
1) FORMAL RESTATEMENT
Fix an integer $n\ge 2$.
Definition (admissible interval factorisation). For integers $t\ge 2$ and $m\ge 1$, we say that $n!$ has an admissible $(t,m)$-factorisation if there exist integers \[ 1\le a_1 < a_2 < \cdots < a_t \] with \[ a_t=a_1+m\quad\text{and}\quad n! = \prod_{i=1}^t a_i. \] Equivalently, there exist integers $A\ge 1$ and $m\ge 1$ and a subset $S\subseteq\{A,A+1,\dots,A+m\}$ containing both endpoints $A$ and $A+m$ such that \[ \prod_{s\in S} s = n!. \]
Definition (the function $f$). For $n\ge 2$ define \[ f(n):=\min\{m\ge 1:\; n!\text{ has an admissible }(t,m)\text{-factorisation for some }t\ge 2\}. \]
The problem asks for the asymptotic behaviour of $f(n)$ as $n\to\infty$, and in particular whether $f(n)=1$ for infinitely many $n$.
For $m\ge 1$ and $N\ge 2$, define \[ F_m(N):=|\{n\le N:\ f(n)=m\}|. \]
Edge cases. For $n=1$, the definition as stated has no solution because $1!=1$ cannot be written as a product of at least two distinct positive integers; throughout I treat $f$ as defined on $n\ge 2$.
2) QUICK LITERATURE/CONTEXT CHECK
I do not introduce any results beyond what is explicitly recorded in the problem statement.
The problem statement records: - Erdős and Graham did not know whether $f(n)=1$ infinitely often. - For each fixed $m$, Berend--Osgood proved $F_m(N)=o(N)$. - Bui--Pratt--Zaharescu proved $F_m(N)\ll_m N^{33/34}$. - Luca proved (conditional on ABC) that $f(n)\to\infty$.
3) ATTACK PLAN
Proof-track ideas (partial results only here): - Derive unavoidable constraints on any admissible factorisation (e.g. how large $a_t$ must be). - Give general constructions providing unconditional upper bounds on $f(n)$. - Reality-check small $n$ by brute force to see what $f(n)$ looks like.
Disproof-track for specific subquestions: - Try to falsify “$f(n)=1$ infinitely often” by showing $f(n)\neq 1$ for a long initial range (computation only, not a proof).
Chosen path: (i) brute force small $n$, (ii) prove a few unconditional structural lemmas.
4) WORK
PHASE 1 — FAST REALITY CHECK (computed)
I brute-forced $f(n)$ for $2\le n\le 15$ by searching over short intervals $[A,A+m]$ and subsets whose product equals $n!$. The minimal $m=f(n)$ and one witnessing factor set $\{a_1,\dots,a_t\}$ are:
- $f(2)=1$ via $2!=1\cdot 2$ (interval $[1,2]$). - $f(3)=1$ via $3!=2\cdot 3$ (interval $[2,3]$). - $f(4)=2$ via $4!=2\cdot 3\cdot 4$ (interval $[2,4]$). - $f(5)=2$ via $5!=4\cdot 5\cdot 6$ (interval $[4,6]$). - $f(6)=2$ via $6!=8\cdot 9\cdot 10$ (interval $[8,10]$). - $f(7)=2$ via $7!=70\cdot 72$ (interval $[70,72]$). - $f(8)=4$ via $8!=12\cdot 14\cdot 15\cdot 16$ (interval $[12,16]$). - $f(9)=6$ via $9!=6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 12$ (interval $[6,12]$). - $f(10)=7$ via $10!=9\cdot 10\cdot 12\cdot 14\cdot 15\cdot 16$ (interval $[9,16]$). - $f(11)=6$ via $11!=30\cdot 32\cdot 33\cdot 35\cdot 36$ (interval $[30,36]$). - $f(12)=9$ via $12!=24\cdot 25\cdot 27\cdot 28\cdot 32\cdot 33$ (interval $[24,33]$). - $f(13)=9$ via $13!=39\cdot 40\cdot 42\cdot 44\cdot 45\cdot 48$ (interval $[39,48]$). - $f(14)=9$ via $14!=63\cdot 64\cdot 65\cdot 66\cdot 70\cdot 72$ (interval $[63,72]$). - $f(15)=12$ via $15!=16\cdot 18\cdot 20\cdot 21\cdot 22\cdot 25\cdot 26\cdot 27\cdot 28$ (interval $[16,28]$).
(These are exact outputs of the script; of course they do not address asymptotics.)
Lemma 1 (trivial universal upper bound). For every $n\ge 3$ we have $f(n)\le n-2$.
Proof. For $n\ge 3$, \[ n! = 2\cdot 3\cdot 4\cdots n. \] Set $t=n-1$ and $a_i=i+1$ for $1\le i\le n-1$. Then $a_1=2$, $a_t=n$, and $a_1<a_2<\cdots<a_t$ are distinct positive integers with \[ \prod_{i=1}^{t} a_i = 2\cdot 3\cdots n = n!. \] The interval length is $m=a_t-a_1=n-2\ge 1$, so this is an admissible factorisation with parameter $m=n-2$. By definition of $f(n)$ as the minimal such $m$, we get $f(n)\le n-2$. $\square$
Lemma 2 (a necessary size constraint on the top factor). Let $n\ge 2$ and suppose $n!=\prod_{i=1}^t a_i$ is an admissible factorisation with $a_1<\cdots<a_t$ and $a_t=a_1+m$. Then $a_t\ge n$.
Proof. All the integers $a_1,\dots,a_t$ are distinct and satisfy $1\le a_i\le a_t$. Hence the set $\{a_1,\dots,a_t\}$ is a subset of $\{1,2,\dots,a_t\}$. Therefore \[ \prod_{i=1}^t a_i \le \prod_{j=1}^{a_t} j = a_t!. \] Since $\prod_{i=1}^t a_i = n!$, we have $n!\le a_t!$. The factorial function is strictly increasing on positive integers, so $n!\le a_t!$ implies $n\le a_t$. $\square$
Lemma 3 (characterisation of the case $f(n)=1$). For $n\ge 2$, $f(n)=1$ if and only if there exists an integer $x\ge 1$ such that \[ n! = x(x+1). \]
Proof. ($\Rightarrow$) If $f(n)=1$, then there is an admissible factorisation with $m=1$. In that factorisation, $a_t=a_1+1$. Since all $a_i$ are distinct and lie in the interval $[a_1,a_1+1]$, the only possibility is $t=2$ and $\{a_1,a_2\}=\{x,x+1\}$ for $x=a_1$. Thus $n!=x(x+1)$.
($\Leftarrow$) Conversely, if $n!=x(x+1)$ for some integer $x\ge 1$, then taking $t=2$, $a_1=x$, $a_2=x+1$ gives an admissible factorisation with $m=1$, hence $f(n)\le 1$. Since $f(n)\ge 1$ by definition, $f(n)=1$. $\square$
5) VERIFICATION
- Lemma 1: For $n=3$, the construction is $3!=2\cdot 3$ with $m=1$; for $n=4$, $4!=2\cdot 3\cdot 4$ with $m=2$, consistent. - Lemma 2 against computed data: in every computed witness above, the largest factor $a_t$ is indeed $\ge n$. - Lemma 3: the computed values show $f(2)=f(3)=1$ with $2!=1\cdot 2$ and $3!=2\cdot 3$, and no $f(n)=1$ for $4\le n\le 15$.
6) FINAL
UNRESOLVED
(i) Strongest fully proved partial result obtained here. - Unconditional bounds: for all $n\ge 3$, $f(n)\le n-2$ (Lemma 1), and in any admissible factorisation the top factor satisfies $a_t\ge n$ (Lemma 2). - Exact small values by brute force: $f(n)$ for $2\le n\le 15$ listed in WORK. - Exact equivalence: $f(n)=1$ iff $n!=x(x+1)$ for some integer $x$ (Lemma 3).
(ii) Exact first gap. Give any unconditional asymptotic information beyond the trivial upper bound; in particular, prove or disprove that $f(n)=1$ for infinitely many $n$, or (even weaker) prove unconditionally that $f(n)\to\infty$.
(iii) Top 3 next moves (concrete targets). 1. For each fixed $m$, understand the Diophantine constraints on representing $n!$ as a product of divisors in an interval of length $m$; even an explicit, effective upper bound on $F_m(N)$ would be progress. 2. Search systematically (computationally) for additional $n$ with $f(n)=2$ or small $m$, and look for structural patterns in the witnessing intervals. 3. Try to prove an unconditional lower bound of the form $f(n)\ge c\log n$ or $f(n)\ge n^{c}$ for infinitely many $n$ by using prime-factor “spacing” constraints on short-interval divisor products.
(iv) What a minimal counterexample would likely look like. A counterexample to “$f(n)\to\infty$” would be an infinite sequence $n_j\to\infty$ together with a fixed $m$ such that each $n_j!$ is a product of distinct divisors contained in some interval of length $m$. Such a family would require unexpectedly many divisors of $n!$ to cluster in bounded-length intervals.