Erdős Problem #683

Erdős Problem 683 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/683

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/683.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/683.tex.

FORMAL RESTATEMENT. Let $P(m)$ be the largest prime divisor of $m$ (with $P(1)=1$). Does there exist an absolute constant $c>0$ such that for all integers $n\ge1$ and $1\le k\le n$, \[ P\!\binom{n}{k}\ \ge\ \min\left(n-k+1,\ k^{1+c}\right)? \] The problem text notes two related facts (treated as given): $1$ Sylvester--Schur: if $k\le n/2$ then $P\!\binom{n}{k}>k$. $2$ Erdős $1935$: $P\!\binom{n}{k} \gg k\log k$.

QUICK LITERATURE/CONTEXT CHECK. I do not import anything beyond the two stated facts above.

ATTACK PLAN. The inequality has two regimes:

• If $k$ is close to $n$, then $n-k+1$ is small and one only needs a modest prime divisor.
• If $k$ is far from $n$ and $k^{1+c}$ is the smaller term, one needs a genuinely superlinear prime divisor in $k$.

The Sylvester--Schur theorem completely handles the "$n-k+1$" regime when $k>n/2$. The difficult part is forcing $P\!\binom{n}{k} \ge k^{1+c}$ for a uniform $c>0$ across the remaining range.

WORK. Lemma 1 (The $k>n/2$ range is automatic from Sylvester--Schur). Assume the Sylvester--Schur statement from the problem: for $t\le n/2$, $P\!\binom{n}{t}>t$. Then for every $n$ and every $k$ with $k>n/2$, \[ P\!\binom{n}{k}\ \ge\ n-k+1. \] Consequently, for $k>n/2$ the desired inequality holds for every $c>0$ (since then $\min(n-k+1,k^{1+c})=n-k+1$).

Proof. Let $t:=n-k$ (so $0\le t < n/2$). Then $\binom{n}{k}=\binom{n}{t}$. By Sylvester--Schur applied to $t\le n/2$, we have $P\!\binom{n}{t}>t=n-k$. Hence $P\!\binom{n}{k}=P\!\binom{n}{t}\ge (n-k)+1=n-k+1$. Also $k>n/2$ implies $k^{1+c}>k>n-k+1$, so the minimum is $n-k+1$. $\square$

Lemma 2 (A small-$n$ obstruction bounds how large $c$ could be). If the inequality holds for all $n,k$, then necessarily \[ c\le \frac{\log 5}{\log 3}-1\approx 0.464974\,. \]

Proof. Take $(n,k)=(10,3)$. Then $\binom{10}{3}=120$ has $P(120)=5$. Also $\min(n-k+1,k^{1+c})=\min(8,3^{1+c})$. For any $c$ such that $3^{1+c}\le 8$, the minimum equals $3^{1+c}$ and the inequality forces $5\ge 3^{1+c}$, i.e. \[c\le \frac{\log 5}{\log 3}-1. \] This gives an absolute upper bound on any admissible $c$. $\square$

VERIFICATION (FAST REALITY CHECK). I brute-forced the inequality for all pairs $(n,k)$ with $n\le 500$ and numerically maximized the largest $c$ for which it holds simultaneously on this finite range. The computation found the same obstruction as Lemma 2:

For N=30,50,100,200,500:
  maximum c for which P(binomial(n,k)) >= min(n-k+1,k^(1+c)) for all n<=N
  is c ~= 0.464974, and the first failing pair when c is increased is (n,k)=(10,3).

This does not indicate what happens asymptotically as $n\to\infty$; it only confirms that small cases already cap any possible $c$.

FINAL. UNRESOLVED.

(i) Strongest proved partial result. Using the Sylvester--Schur fact stated in the problem, the conjectured inequality holds for all $k>n/2$ (Lemma 1). Also, any feasible constant $c$ must satisfy $c\le \log 5/\log 3 -1$ (Lemma 2).

(ii) First gap (crisp). One needs an unconditional lower bound of the form \[P\!\binom{n}{k}\ \ge\ k^{1+c} \] uniformly over all $n$ and all $k$ in the regime where $k^{1+c}\le n-k+1$ (in particular, for many $k\le n/2$). The results quoted in the problem ($P>k$ and $P\gg k\log k$) fall short of any $k^{1+c}$.

(iii) Top 3 next moves. $1$ Identify a structural source of large prime divisors of $\binom{n}{k}$ (e.g. via gcd cancellations in the numerator/denominator) that can force a prime of size $k^{1+c}$. $2$ Compute (for large $n$, say $n\le 10^6$) the minimal value of \[\frac{\log P\!\binom{n}{k}}{\log k}-1 \] over the subrange where $k^{1+c}\le n-k+1$ to guess the best possible $c$. $3$ Attempt to reduce the problem to a statement about prime factors of products of $k$ consecutive integers and then seek "large prime factor" results in that setting.

(iv) Minimal counterexample structure. A counterexample to the existence of a uniform $c>0$ would be an infinite family of pairs $(n,k)$ with $k$ large and $k^{1+c}\le n-k+1$ such that all prime divisors of $\binom{n}{k}$ are $\le k^{1+c}$ (indeed much smaller), despite $k$ itself being large.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

FORMAL RESTATEMENT. Let $P(m)$ be the largest prime divisor of $m$ (with $P(1)=1$). Does there exist an absolute constant $c>0$ such that for all integers $n\ge1$ and $1\le k\le n$, \[ P\!\binom{n}{k}\ \ge\ \min\left(n-k+1,\ k^{1+c}\right)? \] The problem text notes two related facts (treated as given): $1$ Sylvester--Schur: if $k\le n/2$ then $P\!\binom{n}{k}>k$. $2$ Erdős $1935$: $P\!\binom{n}{k} \gg k\log k$.

QUICK LITERATURE/CONTEXT CHECK. I do not import anything beyond the two stated facts above.

ATTACK PLAN. The inequality has two regimes:

• If $k$ is close to $n$, then $n-k+1$ is small and one only needs a modest prime divisor.
• If $k$ is far from $n$ and $k^{1+c}$ is the smaller term, one needs a genuinely superlinear prime divisor in $k$.

The Sylvester--Schur theorem completely handles the "$n-k+1$" regime when $k>n/2$. The difficult part is forcing $P\!\binom{n}{k} \ge k^{1+c}$ for a uniform $c>0$ across the remaining range.

WORK. Lemma 1 (The $k>n/2$ range is automatic from Sylvester--Schur). Assume the Sylvester--Schur statement from the problem: for $t\le n/2$, $P\!\binom{n}{t}>t$. Then for every $n$ and every $k$ with $k>n/2$, \[ P\!\binom{n}{k}\ \ge\ n-k+1. \] Consequently, for $k>n/2$ the desired inequality holds for every $c>0$ (since then $\min(n-k+1,k^{1+c})=n-k+1$).

Proof. Let $t:=n-k$ (so $0\le t < n/2$). Then $\binom{n}{k}=\binom{n}{t}$. By Sylvester--Schur applied to $t\le n/2$, we have $P\!\binom{n}{t}>t=n-k$. Hence $P\!\binom{n}{k}=P\!\binom{n}{t}\ge (n-k)+1=n-k+1$. Also $k>n/2$ implies $k^{1+c}>k>n-k+1$, so the minimum is $n-k+1$. $\square$

Lemma 2 (A small-$n$ obstruction bounds how large $c$ could be). If the inequality holds for all $n,k$, then necessarily \[ c\le \frac{\log 5}{\log 3}-1\approx 0.464974\,. \]

Proof. Take $(n,k)=(10,3)$. Then $\binom{10}{3}=120$ has $P(120)=5$. Also $\min(n-k+1,k^{1+c})=\min(8,3^{1+c})$. For any $c$ such that $3^{1+c}\le 8$, the minimum equals $3^{1+c}$ and the inequality forces $5\ge 3^{1+c}$, i.e. \[c\le \frac{\log 5}{\log 3}-1. \] This gives an absolute upper bound on any admissible $c$. $\square$

VERIFICATION (FAST REALITY CHECK). I brute-forced the inequality for all pairs $(n,k)$ with $n\le 500$ and numerically maximized the largest $c$ for which it holds simultaneously on this finite range. The computation found the same obstruction as Lemma 2:

For N=30,50,100,200,500:
  maximum c for which P(binomial(n,k)) >= min(n-k+1,k^(1+c)) for all n<=N
  is c ~= 0.464974, and the first failing pair when c is increased is (n,k)=(10,3).

This does not indicate what happens asymptotically as $n\to\infty$; it only confirms that small cases already cap any possible $c$.

FINAL. UNRESOLVED.

(i) Strongest proved partial result. Using the Sylvester--Schur fact stated in the problem, the conjectured inequality holds for all $k>n/2$ (Lemma 1). Also, any feasible constant $c$ must satisfy $c\le \log 5/\log 3 -1$ (Lemma 2).

(ii) First gap (crisp). One needs an unconditional lower bound of the form \[P\!\binom{n}{k}\ \ge\ k^{1+c} \] uniformly over all $n$ and all $k$ in the regime where $k^{1+c}\le n-k+1$ (in particular, for many $k\le n/2$). The results quoted in the problem ($P>k$ and $P\gg k\log k$) fall short of any $k^{1+c}$.

(iii) Top 3 next moves. $1$ Identify a structural source of large prime divisors of $\binom{n}{k}$ (e.g. via gcd cancellations in the numerator/denominator) that can force a prime of size $k^{1+c}$. $2$ Compute (for large $n$, say $n\le 10^6$) the minimal value of \[\frac{\log P\!\binom{n}{k}}{\log k}-1 \] over the subrange where $k^{1+c}\le n-k+1$ to guess the best possible $c$. $3$ Attempt to reduce the problem to a statement about prime factors of products of $k$ consecutive integers and then seek "large prime factor" results in that setting.

(iv) Minimal counterexample structure. A counterexample to the existence of a uniform $c>0$ would be an infinite family of pairs $(n,k)$ with $k$ large and $k^{1+c}\le n-k+1$ such that all prime divisors of $\binom{n}{k}$ are $\le k^{1+c}$ (indeed much smaller), despite $k$ itself being large.