Erdős Problem #390

Problem 390. Factorizing $n!$ into distinct integers larger than $n$

1) ROUND-2 OBJECTIVE

Path (A) is not currently realistic: the limit question \[ f(n)-2n\sim c\,\frac{n}{\log n} \] is still open.

So the correct Round-2 goal is the fail-safe route: extract a rigorous theorem that is strictly stronger than the Round-1 black-box summary.

I will prove an explicit lower bound \[ f(n)-2n\ge \left(\frac{1}{9}+o(1)\right)\frac{n}{\log n}. \] This does not settle the constant $c$, but it gives a concrete asymptotic obstruction, not just the qualitative statement "of order $n/\log n$."

2) Round-1 FOUNDATION USED

I use the following Round-1 reformulation.

Let $f(n)$ be the least $m$ for which there exist distinct integers \[ n<a_1<\cdots<a_t=m \] with \[ n!=a_1a_2\cdots a_t. \]

Round 1 rewrote the problem using \[ (n+1)(n+2)\cdots(2n)=n!\,{2n\choose n}. \] If $H=f(n)-2n$, and if we compare an optimal factorization with the full interval $(n,2n]$, then there exist sets \[ B\subseteq \{n+1,\dots,2n\},\qquad C\subseteq \{2n+1,\dots,2n+H\} \] such that \[ \prod_{b\in B} b={2n\choose n}\prod_{c\in C} c. \] Here $B$ is the set of numbers omitted from $(n,2n]$, and $C$ is the set of numbers inserted beyond $2n$.

Round 1 also recorded the known theorem of Erdős, Guy and Selfridge that \[ f(n)-2n \] is of order $n/\log n$.

3) NEW INSIGHT / TOOL (ROUND-2)

The new tool is a prime-counting argument on the interval \[ \left(\frac{n}{2},\frac{2n}{3}\right]. \]

For each prime $p$ in this interval, the central binomial coefficient ${2n\choose n}$ contributes one factor of $p$, but inside $(n,2n]$ the only multiples of $p$ are $2p$ and $3p$. Therefore every such prime forces at least one omitted number carrying an extra factor $2$ or $3$. This converts a count of medium primes into a lower bound on the total $2$-adic and $3$-adic mass that must be supplied by the overhang interval $(2n,2n+H]$.

That mechanism yields the explicit constant $1/9$.

4) ATTACK PLAN (ROUND-2)

The exact Round-1 gap was that the known lower bound was only quoted abstractly. I now prove a concrete lower bound by the following chain.

1. Show that every prime $p\in(n/2,2n/3]$ satisfies \[ v_p\!\left({2n\choose n}\right)=1. \]

2. Deduce that for each such prime, at least one of $2p$ or $3p$ must lie in $B$.

3. Count how much $2$-adic and $3$-adic valuation the set $C\subseteq(2n,2n+H]$ can contribute in total.

4. Compare both sides and apply the prime number theorem to the interval $(n/2,2n/3]$.

This gives a fully rigorous explicit asymptotic lower bound for $H=f(n)-2n$.

5) WORK (ROUND-2)

Let \[ H=f(n)-2n. \] Choose an optimal representation of $n!$ and the corresponding sets $B$ and $C$ from the Round-1 reformulation: \[ \prod_{b\in B} b={2n\choose n}\prod_{c\in C} c, \] with \[ B\subseteq \{n+1,\dots,2n\},\qquad C\subseteq \{2n+1,\dots,2n+H\}. \]

Claim 1. For every sufficiently large $n$ and every prime $p$ with \[ \frac{n}{2}<p\le \frac{2n}{3}, \] one has \[ v_p\!\left({2n\choose n}\right)=1. \]

Proof. For $n\ge 9$ and $p>n/2$, we have $p^2>2n$. Hence, by Legendre's formula, \[ v_p\!\left({2n\choose n}\right) = \left\lfloor\frac{2n}{p}\right\rfloor-2\left\lfloor\frac{n}{p}\right\rfloor. \] Now \[ \left\lfloor\frac{n}{p}\right\rfloor=1 \qquad\text{because}\qquad \frac{n}{2}<p\le n, \] and \[ \left\lfloor\frac{2n}{p}\right\rfloor=3 \qquad\text{because}\qquad 3\le \frac{2n}{p}<4 \] when $n/2<p\le 2n/3$. Therefore \[ v_p\!\left({2n\choose n}\right)=3-2=1. \] QED.

Claim 2. For every sufficiently large $n$ and every prime $p$ with $n/2<p\le 2n/3$, at least one of $2p$ or $3p$ belongs to $B$.

Proof. By Claim 1, the right-hand side \[ {2n\choose n}\prod_{c\in C} c \] is divisible by $p$.

Hence the left-hand side $\prod_{b\in B}b$ is divisible by $p$, so some element of $B$ is divisible by $p$. But any multiple of $p$ lying in $(n,2n]$ must equal $2p$ or $3p$, because a multiplier $r$ with $rp\in(n,2n]$ satisfies \[ 1<r<4 \] when $p>n/2$. Thus at least one of $2p$ or $3p$ lies in $B$. QED.

Claim 3. Let \[ P_n:=\left\{p\ \text{prime}:\ \frac{n}{2}<p\le \frac{2n}{3}\right\}. \] Then \[ |P_n|\le v_2\!\left(\prod_{b\in B}b\right)+v_3\!\left(\prod_{b\in B}b\right). \]

Proof. For each $p\in P_n$, Claim 2 lets us choose a number \[ b_p\in B\cap\{2p,3p\}. \] Each such $b_p$ contributes exactly $1$ to \[ v_2(b_p)+v_3(b_p), \] because $2p$ has $(v_2,v_3)=(1,0)$ and $3p$ has $(v_2,v_3)=(0,1)$.

Also the numbers $b_p$ are distinct. Indeed, if $b_p=b_q$ for distinct $p,q\in P_n$, then that common number in $(n,2n]$ would be divisible by two distinct primes $>n/2$, impossible because their product would exceed $2n$.

Therefore \[ |P_n| = \sum_{p\in P_n} 1 = \sum_{p\in P_n}\left(v_2(b_p)+v_3(b_p)\right) \le v_2\!\left(\prod_{b\in B}b\right)+v_3\!\left(\prod_{b\in B}b\right). \] QED.

Claim 4. One has \[ v_2\!\left(\prod_{b\in B}b\right)+v_3\!\left(\prod_{b\in B}b\right) \le \frac{3}{2}H+O(\log n). \]

Proof. From \[ \prod_{b\in B} b={2n\choose n}\prod_{c\in C} c \] we get \[ v_2\!\left(\prod_{b\in B}b\right)+v_3\!\left(\prod_{b\in B}b\right) = v_2\!\left({2n\choose n}\right)+v_3\!\left({2n\choose n}\right) + v_2\!\left(\prod_{c\in C}c\right)+v_3\!\left(\prod_{c\in C}c\right). \]

First, the central binomial coefficient contributes only $O(\log n)$ to the $2$- and $3$-adic valuations. Indeed, by Legendre's formula, \[ v_p\!\left({2n\choose n}\right) = \sum_{j\ge 1}\left(\left\lfloor\frac{2n}{p^j}\right\rfloor-2\left\lfloor\frac{n}{p^j}\right\rfloor\right), \] and each summand is at most $1$, while all summands vanish once $p^j>2n$. Hence \[ v_2\!\left({2n\choose n}\right)\le \lfloor \log_2(2n)\rfloor+1, \qquad v_3\!\left({2n\choose n}\right)\le \lfloor \log_3(2n)\rfloor+1, \] so \[ v_2\!\left({2n\choose n}\right)+v_3\!\left({2n\choose n}\right)=O(\log n). \]

Second, because $C\subseteq \{2n+1,\dots,2n+H\}$, \[ v_2\!\left(\prod_{c\in C}c\right) \le \sum_{m=2n+1}^{2n+H} v_2(m) = \sum_{j\ge 1} \#\{m\in[2n+1,2n+H]:2^j\mid m\}. \] For each $j$, this count is at most $H/2^j+1$, and only $O(\log n)$ values of $j$ can occur because $2^j\le 2n+H$ is necessary for the count to be nonzero. Hence \[ v_2\!\left(\prod_{c\in C}c\right) \le \sum_{j\ge 1}\left(\frac{H}{2^j}+1\right) = H+O(\log n). \] Similarly, \[ v_3\!\left(\prod_{c\in C}c\right) \le \sum_{j\ge 1}\left(\frac{H}{3^j}+1\right) = \frac{H}{2}+O(\log n), \] again because only $O(\log n)$ values of $j$ contribute.

Adding these bounds gives \[ v_2\!\left(\prod_{b\in B}b\right)+v_3\!\left(\prod_{b\in B}b\right) \le \frac{3}{2}H+O(\log n). \] QED.

Claim 5. For sufficiently large $n$, \[ H\ge \left(\frac{1}{9}+o(1)\right)\frac{n}{\log n}. \]

Proof. By Claim 3 and Claim 4, \[ |P_n|\le \frac{3}{2}H+O(\log n). \] By the prime number theorem, \[ |P_n| = \pi\!\left(\frac{2n}{3}\right)-\pi\!\left(\frac{n}{2}\right) = \left(\frac{2}{3}-\frac{1}{2}+o(1)\right)\frac{n}{\log n} = \left(\frac{1}{6}+o(1)\right)\frac{n}{\log n}. \] Hence \[ \left(\frac{1}{6}+o(1)\right)\frac{n}{\log n} \le \frac{3}{2}H+O(\log n). \] Since $O(\log n)=o(n/\log n)$, division by $3/2$ gives \[ H\ge \left(\frac{1}{9}+o(1)\right)\frac{n}{\log n}. \] Because $H=f(n)-2n$, this is exactly \[ f(n)-2n\ge \left(\frac{1}{9}+o(1)\right)\frac{n}{\log n}. \] QED.

6) ADVERSARIAL VERIFICATION

I check the vulnerable points.

• Did I use the Round-1 set identity correctly? Yes. The identity \[ \prod_{b\in B} b={2n\choose n}\prod_{c\in C} c \] is exactly the Round-1 reformulation, and every valuation argument starts from it.

• Could a prime $p\in(n/2,2n/3]$ be absorbed by some number in $(n,2n]$ other than $2p$ or $3p$? No. Multipliers $1$ and $4$ are impossible because $p\le n$ and $4p>2n$ in this interval. So only $2p$ and $3p$ occur.

• Could two different primes share the same omitted number? No. Any number in $(n,2n]$ has at most one prime factor greater than $n/2$, because two such primes would have product $>2n$.

• Does $C$ perhaps contribute more $2$- and $3$-adic mass than estimated? No. I bounded the valuation of the entire interval $[2n+1,2n+H]$, so the bound automatically applies to its subset $C$.

• Small $n$. Claim 1 was stated only for sufficiently large $n$ because I used $p^2>2n$. That is harmless: the final statement is asymptotic, and finitely many small values do not affect the $o(1)$ term.

• Interaction with the known upper bound. Round 1 already cited the Erdős--Guy--Selfridge upper bound \[ f(n)-2n=O\!\left(\frac{n}{\log n}\right). \] The new theorem is compatible with that and strengthens only the lower-bound side.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The strict Round-2 advance is the explicit theorem \[ f(n)-2n\ge \left(\frac{1}{9}+o(1)\right)\frac{n}{\log n}. \]

Thus the previously quoted qualitative lower bound has been replaced by a concrete asymptotic constant. Combined with the known upper bound of Erdős--Guy--Selfridge, \[ f(n)-2n=O\!\left(\frac{n}{\log n}\right), \] we now have a sharper quantitative bracket.

What remains open is the actual question of the problem: does the normalized quantity \[ \frac{(f(n)-2n)\log n}{n} \] converge, and if so to what constant $c$?

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 60%

9) REFERENCES

1. P. Erdős, R. K. Guy, and J. L. Selfridge, The product of the divisors of an integer, for the classical upper and lower bounds showing that $f(n)-2n$ is of order $n/\log n$.

2. The Erdős Problems site, Problem 390, for the statement of the problem and the citation to the Erdős--Guy--Selfridge result.

3. The prime number theorem, used in the standard form \[ \pi(an)-\pi(bn)=\left((a-b)+o(1)\right)\frac{n}{\log n} \] for fixed $0<b<a$.

Problem 390: four prime intervals strengthen the valuation lower bound

1) OBJECTIVE AND SOURCE REVIEW

2) WORK

3) ADVERSARIAL VERIFICATION

4) FINAL

5) SOURCES CHECKED

6) COMPLETION ESTIMATE

Problem 390. Factorizing $n!$ into distinct integers larger than $n$ and the constant $c$

Formal restatement

Given that $f(n)-2n\asymp n/\log n$ (two-sided order of magnitude), does there exist a constant $c$ such that \[ f(n)-2n\sim c\,\frac{n}{\log n}\qquad(n\to\infty)? \]

Quick literature/context check (browsing available)

Attack plan

1. Understand the "baseline" $2n$ barrier: explain why trying to realize (eq:P390-def) using only numbers in $(n,2n]$ is sometimes impossible.
2. Summarize the mechanism behind the known $\Theta(n/\log n)$ bounds: relate the problem to factoring the central binomial coefficient $\binom{2n}{n}$ into distinct integers in $(n,2n]$ and accounting for leftover small-prime powers.
3. Attempt to isolate the main term that would determine the constant $c$ (if it exists), and identify the bottleneck that prevents a clean asymptotic.

Work

A convenient reformulation via $\binom{2n}{n}$.

Why $f(n)$ is close to $2n$.

Known bounds (as a black box).

Where the constant $c$ would come from.

Verification

• (eq:P390-central) is the standard formula for the central binomial coefficient.
• The reformulation in terms of selecting a subset $B\subset(n,2n]$ is a direct algebraic rearrangement of (eq:P390-prod).

Final

UNRESOLVED.

1. (i) Strongest proved partial result: The known theorem of Erdős--Guy--Selfridge gives $f(n)=2n+\Theta(n/\log n)$, i.e. (eq:P390-asymp).
2. (ii) First gap / obstruction: To prove the existence of a limit constant $c$ (or to disprove it) one needs substantially sharper control on the optimal packaging of the prime-power content of $\binom{2n}{n}$ into distinct integers in $(n,2n]$ and on the minimal "overhang" beyond $2n$ needed to absorb the leftover. The available arguments give only coarse $\Theta(\cdot)$ bounds.
3. (iii) Top 3 next moves: $1$ Develop an "optimal transport" viewpoint for prime powers from $\binom{2n}{n}$ into $(n,2n]$ and $(2n,2n+H]$, and prove a limit shape for the leftover. $2$ Improve both upper and lower bounds by using several small primes (not just $2$) in the absorption step, potentially tightening $c_1,c_2$ toward a common value. $3$ Investigate whether $\left(f(n)-2n\right)\log n/n$ exhibits persistent oscillation (e.g. depending on prime distribution in short intervals), which would rule out the existence of a limit.
4. (iv) What a minimal counterexample would look like: If the limit does not exist, one would expect two sequences $n_t$ and $n'_t$ along which the optimal leftover after the best choice of $B$ has systematically different size (or different small-prime structure), forcing different limiting values for $(f(n)-2n)\log n/n$.

Completion estimate