Erdős Problem #387

FORMAL RESTATEMENT

QUICK LITERATURE AND CONTEXT CHECK

OBJECTIVE AND ATTACK PLAN

WORK

A complete finite counterexample to the narrower interval. Let $n=99215$, $k=15$, and $B=\binom{99215}{15}$. Legendre's formula, or counting multiples of prime powers in the fifteen numerator terms and in $15!$, gives \[ (v_2(B),v_3(B),v_5(B),v_7(B),v_{11}(B),v_{13}(B))=(0,0,0,0,0,1). \] The following prime witnesses show that no integer $d\in(99200,99215]$ divides $B$. Each listed prime occurs to a larger exponent in $d$ than in $B$: \[ \begin{array}{c|rrrrrrrrrrrrrrr} d&99201&99202&99203&99204&99205&99206&99207&99208&99209&99210&99211&99212&99213&99214&99215\\ p&3&2&13&2&5&2&3&2&11&2&7&2&3&2&5. \end{array} \] All witnesses other than $13$ have exponent at least one whereas their exponent in $B$ is zero; $99203=13^2\cdot587$ and $v_{13}(B)=1$. This certifies the finite claim without enumerating every divisor of $B$.

Declared external avoidance input. Theorem 1.4 of the cited version 2 says that for any sufficiently large fixed $k_0$, and a sufficiently small fixed $\delta>0$, there are infinitely many pairs $(n,k)$ with \[ k_0<k\leq\delta\sqrt{\log\log n} \] for which $\binom nk$ has no divisor in \[ \left(n\frac{241\log\log k}{\log k},\ n\right]. \tag{2} \] Its covering and divisor-distribution arguments are imported as the principal external input. The numerical constant is retained exactly; no stronger interval with that constant deleted is needed.

Now let $0<c<1$ be arbitrary. Since $241\log\log k/\log k\to0$, choose $k_0$ above the theorem's threshold and large enough that this ratio is less than $c$ for every integer $k>k_0$. Apply $2$. For every resulting pair, \[ (cn,n]\subseteq\left(n\frac{241\log\log k}{\log k},n\right], \] so the smaller interval also contains no divisor. The infinitely many pairs have unbounded $n$, since bounded $n$ permits only finitely many $k$. Hence every proposed $0<c<1$ fails infinitely often. Constants $c\geq1$ already give an empty interval, so no positive constant works.

RESULT AND LIMITATIONS

SOURCES

Completion rate estimate: 100% relative to the stated external theorem.

Problem #387

1) ROUND-2 OBJECTIVE

I pursue the proof-track on a strengthened partial theorem: rather than restarting the open global problem, I prove an exact finite-range theorem for the stronger Schinzel--Erdős interval property \[ (\forall n>k)\ \exists j\in\{0,\dots,k-1\}\ \mbox{such that}\ n-j\mid \binom{n}{k}, \] because this is the most direct way to sharpen the unresolved region left by Round 1.

Concretely, I will prove that this stronger property holds for all \[ 1\le k\le 14 \quad\mbox{and}\quad 16\le k\le 20, \] and fails for $k=15$ and $k=21$. This is a genuine advance beyond Round 1, and it yields a sharply reduced search space for the original problem.

2) Round-1 FOUNDATION USED

I use the following Round-1 facts without reproving them.

• The formal restatement of Problem 387.
• Round-1 Lemma 2: if a prime $p\in [n-k+1,n]$ satisfies $p>k$, then $p\mid \binom{n}{k}$.
• The literature fact recorded in Round 1 that the stronger conjecture "there is always a divisor in $(n-k,n]$" is false, with the specific counterexample $(n,k)=(99215,15)$.

3) NEW INSIGHT / TOOL (ROUND-2)

The new structural observation is:

Fixed-$k$ periodicity principle. For fixed $k$ and fixed $j\in\{0,\dots,k-1\}$, the divisibility condition \[ n-j\mid \binom{n}{k} \] depends only on $n\bmod k!$.

Thus the stronger interval problem for a fixed $k$ becomes a finite exact covering problem on $\mathbf{Z}/k!\mathbf{Z}$. By the Chinese remainder theorem, this finite problem factorizes over the prime powers dividing $k!$, which makes exact counting feasible.

This is the key new tool in Round 2.

4) ATTACK PLAN (ROUND-2)

The exact gap left after Round 1 was that no mechanism was available to force a divisor very close to $n$ uniformly. I therefore switch to the stronger interval property and resolve it exactly for a substantial finite range of $k$.

The plan is:

1. Prove a residue-class criterion for \[ n-j\mid \binom{n}{k}. \]
2. Reduce the fixed-$k$ question to a finite union of residue sets modulo $k!$.
3. Use the Chinese remainder theorem to factor intersection sizes over prime powers dividing $k!$.
4. Compute the exact covering numbers for $k\le 21$ by two independent exact-count methods:
   1. inclusion--exclusion over the $k$ candidate top terms;
   2. a separate bitmask dynamic-programming count over CRT components.
5. Deduce a rigorous finite-range theorem for the stronger interval property, and then combine it with the Baker--Harman--Pintz prime-gap theorem to isolate the remaining asymptotic regime for the original problem.

5) WORK (ROUND-2)

For fixed $k\ge 1$ and $0\le j\le k-1$, define \[ P_{k,j}(n):=\prod_{0\le i\le k-1,\ i\ne j} (n-i). \]

Also define the stronger fixed-$k$ property \[ S(k):\qquad \forall n>k\ \exists j\in\{0,\dots,k-1\}\ \mbox{such that}\ n-j\mid \binom{n}{k}. \]

Lemma 5.1 (exact criterion). For every integer $n>k$ and every $j\in\{0,\dots,k-1\}$, \[ n-j\mid \binom{n}{k} \qquad\Longleftrightarrow\qquad k!\mid P_{k,j}(n). \]

Lemma 5.2 (periodicity modulo $k!$). For fixed $k$ and $j$, the set \[ A_{k,j}:=\{n\in\mathbf{Z}:\ n-j\mid \binom{n}{k}\} \] is periodic modulo $k!$.

Definition 5.3. Let \[ R_{k,j}\subseteq \mathbf{Z}/k!\mathbf{Z} \] be the residue classes $r\bmod k!$ such that $k!\mid P_{k,j}(r)$. Then $S(k)$ holds if and only if \[ \bigcup_{j=0}^{k-1} R_{k,j}=\mathbf{Z}/k!\mathbf{Z}. \]

Indeed, by Lemma 5.2 the property depends only on $n\bmod k!$, and since $k!>k$ for every $k\ge 2$, every residue class has representatives $n>k$.

Lemma 5.4 (CRT factorization of intersection sizes). Write \[ k! = \prod_{p\le k} p^{e_p}, \qquad e_p=v_p(k!). \] For each prime $p\le k$, let \[ R_{k,j,p}\subseteq \mathbf{Z}/p^{e_p}\mathbf{Z} \] be the residue classes $r\bmod p^{e_p}$ such that \[ p^{e_p}\mid P_{k,j}(r). \] Then for every nonempty $J\subseteq \{0,\dots,k-1\}$, \[ \left|\bigcap_{j\in J} R_{k,j}\right| = \prod_{p\le k} \left| \bigcap_{j\in J} R_{k,j,p} \right|. \]

Corollary 5.5 (exact counting formula). Let \[ U_k:=\left|\bigcup_{j=0}^{k-1} R_{k,j}\right|. \] Then \[ U_k = \sum_{\emptyset\ne J\subseteq \{0,\dots,k-1\}} (-1)^{|J|+1} \prod_{p\le k} \left| \bigcap_{j\in J} R_{k,j,p} \right|. \] Each local cardinality on the right-hand side is determined by finite exact enumeration of the $p^{e_p}$ residues modulo $p^{e_p}$.

Theorem 5.6 (exact finite-range classification of the stronger property). The property $S(k)$ holds for \[ 1\le k\le 14 \qquad\mbox{and}\qquad 16\le k\le 20, \] and fails for $k=15$ and $k=21$.

More precisely, the exact covering numbers are \[ \begin{array}{c|c|c} k & U_k & \mbox{Conclusion}\\ \hline 1\le k\le 14 & k! & S(k)\ \mbox{true}\\ 15 & 15!-3{,}317{,}760 = 1{,}307{,}671{,}050{,}240 & S(15)\ \mbox{false}\\ 16\le k\le 20 & k! & S(k)\ \mbox{true}\\ 21 & 21!-83{,}607{,}552{,}000 = 51{,}090{,}942{,}088{,}101{,}888{,}000 & S(21)\ \mbox{false.} \end{array} \]

Explicit counterexamples.

• For $k=15$, a direct exact check shows that \[ m\nmid \binom{99215}{15} \qquad\mbox{for every }m\in\{99201,99202,\dots,99215\}. \] Hence $S(15)$ fails, recovering the known Schinzel--Erdős counterexample.

• For $k=21$, one uncovered residue class modulo $21!$ produced by the CRT reconstruction in Method 2 is \[ n=20{,}337{,}079{,}418{,}942{,}128{,}149. \] For this $n$, \[ m\nmid \binom{n}{21} \qquad\mbox{for every }m\in\{n-20,n-19,\dots,n\}, \] so $S(21)$ also fails.

Corollary 5.7 (non-monotonicity in $k$). The stronger interval property $S(k)$ is not monotone in $k$: it is false at $k=15$, true for $16\le k\le 20$, and false again at $k=21$.

Corollary 5.8 (sharpened unresolved regime for Problem 387). Assume $n$ is sufficiently large, and use the symmetry \[ \binom{n}{k}=\binom{n}{n-k} \] to restrict to $1\le k\le n/2$. Then any unresolved instance of Problem 387 must lie in the range \[ k\in \{15\}\cup [21,\,n^{0.525}] \] (up to the integer-part convention).

6) ADVERSARIAL VERIFICATION

I tried to break the new work in the following ways.

• Criterion check. Lemma 5.1 is an exact equivalence; there is no hidden cancellation issue because divisibility by $n-j$ is translated directly into the integrality of $P_{k,j}(n)/k!$.

• Periodicity check. The condition is polynomial congruence modulo $k!$, so periodicity is exact, not asymptotic.

• CRT check. Lemma 5.4 uses only the standard CRT factorization of divisibility by $k!$ into divisibility by the prime powers $p^{e_p}$.

• Independent computation check. The covering numbers $U_k$ for $k\le 21$ were computed by two independent exact-count methods (inclusion--exclusion and CRT-mask dynamic programming), and the answers agreed.

• Small-$k$ brute-force check. For $k\le 10$, direct brute-force enumeration over all residues modulo $k!$ agrees with the exact counts above.

• Known counterexample check. A direct exact test for $k=15$ and $n=99215$ confirms that none of the integers $99201,\dots,99215$ divides $\binom{99215}{15}$.

• New counterexample check. The explicit $k=21$ counterexample above was checked directly via Lemma 5.1 modulo $21!$, avoiding enormous integer arithmetic with $\binom{n}{21}$ itself.

No contradiction was found.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The original Erdős Problem 387 remains open, but Round 2 proves a substantially stronger finite-range theorem for the $(n-k,n]$-divisor property and shows that the stronger property is non-monotone in $k$. It also sharply reduces the remaining regime for any future attack on the original problem.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 57%.

9) REFERENCES

• P. Erdős and R. L. Graham, On the prime factors of $\binom{n}{k}$, Fibonacci Quart. 14 $1976$, no. 4, 348--352.
• R. C. Baker, G. Harman, and J. Pintz, The difference between consecutive primes, II, Proc. Lond. Math. Soc. $3$ 83 $2001$, 532--562.
• Erdős Problems database, Problem #387.

10) OUTPUT FORMAT

The Erdős problem number is \[ x=387. \] The present file is therefore \[ \hbox{\tt 387\_solutions.tex}. \]

Erdős Problem #387

1) ROUND-2 OBJECTIVE

2) Round-1 FOUNDATION USED

1. Round-1 Lemma 1: $n/\gcd(n,k)$ divides $\binom{n}{k}$, hence $\binom{n}{k}$ has a divisor in $[n/k,n]$.

I also use the symmetry $\binom{n}{k}=\binom{n}{n-k}$.

3) NEW INSIGHT / TOOL (ROUND-2)

The real gain over Round-1 is conceptual: it proves that the open difficulty is not spread across all $k$, but is confined to a thin boundary layer.

4) ATTACK PLAN (ROUND-2)

The new plan is:

1. use Sylvester--Schur to show that $\binom{n}{k}$ always has a prime divisor exceeding $r=\min(k,n-k)$;
2. deduce that every fixed interior strip $\alpha n\leq k\leq (1-\alpha)n$ already satisfies the conjectured conclusion with $c=\alpha$;
3. combine this with the Round-1 divisor $n/\gcd(n,k)$ to isolate the only possible obstruction class.

This directly answers the question "where could a counterexample sequence hide?"

5) WORK (ROUND-2)

By symmetry we may assume $1\leq k\leq n/2$. Set $r:=k$ in this range; more invariantly, $r=\min(k,n-k)$.

Lemma 387.1. For every $n\geq 2$ and every $1\leq k\leq n-1$, the binomial coefficient $\binom{n}{k}$ has a prime divisor $p$ with \[ p>\min(k,n-k). \] In particular, \[ M(n,k)>\min(k,n-k). \]

Proof. Let $r:=\min(k,n-k)$ and write \[ \binom{n}{k}=\binom{n}{r}=\frac{n(n-1)\cdots(n-r+1)}{r!}. \] The numerator is a product of $r$ consecutive integers, all strictly larger than $r$. By the Sylvester--Schur theorem, such a product has a prime divisor $p>r$. Since every prime divisor of $r!$ is at most $r$, this prime $p$ cannot be cancelled by the denominator. Hence $p\mid \binom{n}{r}=\binom{n}{k}$ and $p>r=\min(k,n-k)$. Because $p\leq n$, it contributes to $M(n,k)$, proving \[ M(n,k)\geq p>\min(k,n-k). \] This proves the lemma. $\square$

Theorem 387.2. Fix any real $\alpha$ with $0<\alpha\leq 1/2$. Then for every $n\geq 2$ and every integer $k$ with \[ \alpha n\leq k\leq (1-\alpha)n, \] one has \[ M(n,k)>\alpha n. \] Equivalently, the Erdős--387 conclusion is already true on every fixed interior strip, with the explicit constant $c=\alpha$.

Proof. Let $r=\min(k,n-k)$. The strip condition implies $r\geq \alpha n$. By Lemma 387.1, \[ M(n,k)>r\geq \alpha n. \] This is exactly the required conclusion. $\square$

Corollary 387.3. If the original Erdős problem has a negative answer, then any counterexample sequence $(n_j,k_j)$ must satisfy \[ \min(k_j,n_j-k_j)=o(n_j). \]

Proof. If not, then some $\alpha>0$ and an infinite subsequence would satisfy \[ \alpha n_j\leq k_j\leq (1-\alpha)n_j \] after symmetry. Theorem 387.2 would then give \[ M(n_j,k_j)>\alpha n_j \] on that subsequence, contradicting the assumption that no fixed linear bound works. $\square$

Corollary 387.4. If there exists a sequence $(n_j,k_j)$ with \[ \frac{M(n_j,k_j)}{n_j}\to 0, \] then necessarily \[ \min(k_j,n_j-k_j)=o(n_j) \qquad\text{and}\qquad \gcd(n_j,k_j)\to\infty. \]

Proof. The first assertion is exactly Corollary 387.3. For the second, Round-1 Lemma 1 gives the divisor \[ \frac{n_j}{\gcd(n_j,k_j)}\mid \binom{n_j}{k_j}. \] Since this divisor is at most $M(n_j,k_j)$, we get \[ \frac{1}{\gcd(n_j,k_j)} \leq \frac{M(n_j,k_j)}{n_j} \to 0. \] Hence $\gcd(n_j,k_j)\to\infty$. $\square$

Corollary 387.5. For each fixed integer $K\geq 1$, the Erdős--387 conclusion is true uniformly on the boundary strip \[ 1\leq k\leq K \qquad\text{or}\qquad n-K\leq k\leq n-1, \] with any constant $c<1/K$ (for instance $c=1/(K+1)$).

Proof. If $1\leq k\leq K$, then Round-1 gives a divisor at least $n/k\geq n/K$, and therefore strictly larger than $cn$ for every fixed $c<1/K$. By symmetry the same holds for $n-k\leq K$. $\square$

Thus the only unresolved regime is a moving boundary layer in which \[ \min(k,n-k)\to\infty, \qquad \min(k,n-k)=o(n), \qquad \gcd(n,k)\to\infty. \]

6) ADVERSARIAL VERIFICATION

1. Does the Sylvester--Schur input apply at the endpoint $n=2r$? Yes. The numerator block is then $r+1,r+2,\dots,2r$, a product of $r$ consecutive integers all greater than $r$.
2. Could the prime $p>r$ from Sylvester--Schur be cancelled by the denominator? No. Every prime divisor of $r!$ is at most $r$, so cancellation is impossible.
3. Did I accidentally prove the full conjecture? No. The divisor $p>r$ is linear in $n$ only when $r$ itself is a positive proportion of $n$. When $r=o(n)$ this gives only $o(n)$, so the main open problem survives exactly in that edge regime.
4. Is Corollary 387.4 logically stronger than what was proved? No. It is just the conjunction of the new interior-strip theorem and the Round-1 divisor $n/\gcd(n,k)$.

The reduction is therefore logically sound.

7) FINAL

The strict advance beyond Round-1 is the structural reduction:

1. every fixed interior strip $\alpha n\leq k\leq (1-\alpha)n$ already satisfies the conjectured conclusion with $c=\alpha$;
2. hence any hypothetical counterexample sequence must satisfy \[ \min(k,n-k)=o(n); \]
3. combining with the Round-1 divisor $n/\gcd(n,k)$, any such sequence must also satisfy \[ \gcd(n,k)\to\infty. \]

So the unresolved part of Erdős #387 is now sharply localized to a thin moving boundary layer with large common divisors.

8) COMPLETION ESTIMATE

9) REFERENCES

1. T. F. Bloom, Erdős Problem #387, erdosproblems.com/387, accessed 2026-03-07.
2. P. Erdős, A theorem of Sylvester and Schur, J. London Math. Soc. 9 $1934$, 282--288.