Erdős Problem #684

Erdős Problem 684 --- collection record

PROVENANCE AND STATUS

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

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/684.tex.

REUSED SOURCE 1

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

FORMAL RESTATEMENT. For $0\le k\le n$, write \[\binom{n}{k}=u\,v\] where every prime divisor of $u$ lies in $[2,k]$ and every prime divisor of $v$ lies in $(k,n]$. Define $f(n)$ to be the smallest $k$ such that $u>n^{2}$. Find upper and lower bounds for $f(n)$ as $n\to\infty$.

QUICK LITERATURE/CONTEXT CHECK. The problem statement notes (treated as given) that Mahler's theorem implies $f(n)\to\infty$ but ineffectively. I do not assume further results.

ATTACK PLAN. The quantity $u$ is exactly the $k$-smooth part of $\binom{n}{k}$: it is built from the prime powers $p^{v_p(\binom{n}{k})}$ for primes $p\le k$. Thus one seeks a $k$ where the contribution from small primes to $\binom{n}{k}$ already exceeds $n^2$. A first step is an exact expression for $u$ in terms of prime-adic valuations, then to try to lower bound $\log u$.

WORK. Lemma 1 (Prime-valuation formula for $u$). Let $v_p(m)$ be the exponent of a prime $p$ in $m$. For $0\le k\le n$, \[ u = \prod_{p\le k} p^{\,v_p\left(\binom{n}{k}\right)}. \] Equivalently, \[\log u = \sum_{p\le k} v_p\left(\binom{n}{k}\right)\,\log p. \]

Proof. By the fundamental theorem of arithmetic, $\binom{n}{k}=\prod_p p^{v_p(\binom{n}{k})}$. The definition of the factorization $\binom{n}{k}=uv$ requires $u$ to contain exactly the prime powers with primes $p\le k$, and $v$ to contain those with primes $p>k$. Therefore $u=\prod_{p\le k} p^{v_p(\binom{n}{k})}$, and taking logs gives the second identity. $\square$

Lemma 2 ($k=0$ and $k=1$ never witness $u>n^2$). For every $n\ge2$ and $k\in\{0,1,n-1,n\}$, the corresponding $u$ satisfies $u\le n$, hence $u\le n^{2}$. In particular $f(n)\ge 2$ whenever $f(n)$ is finite.

Proof. If $k=0$ or $k=n$, then $\binom{n}{k}=1$ and (vacuously) $u=1\le n^{2}$. If $k=1$ or $k=n-1$, then $\binom{n}{k}=n$. By definition, $u$ only uses primes $\le k$. For $k=1$ there are no primes $\le1$, so $u=1$. For $k=n-1$, all primes $\le n-1$ are allowed, so $u=n$, but still $u=n\le n^{2}$. Thus none of these $k$ can satisfy $u>n^{2}$. $\square$

VERIFICATION (FAST REALITY CHECK). I implemented the exact definition of $u$ via Lemma 1 and brute-forced $f(n)$ for many $n$. For each $n$, I searched the smallest $k\in\{0,1,\dots,n\}$ with $u>n^{2}$. Results:

For n<=60: f(n) is undefined for n in {2..9,11..15,17,19,20,23}.
For n<=1000: the same undefined set occurs; for all n>=24 up to 1000, f(n) exists.
For n<=20000:
  f(n) exists for all n>=24 in this range,
  max f(n) observed is 73 (attained at n=12119),
  median f(n) over n=2..20000 where defined is 29.

These computations suggest that $f(n)$ is finite for all $n\ge 24$ and grows very slowly (at least up to $n=2\cdot 10^{4}$), but this is only empirical.

FINAL. UNRESOLVED.

(i) Strongest proved partial result. The factor $u$ is exactly the $k$-smooth part of $\binom{n}{k}$ and admits the exact valuation formula of Lemma 1. Also, trivial $k\in\{0,1,n-1,n\}$ never witness $u>n^{2}$ (Lemma 2).

(ii) First gap (crisp). I do not have an effective lower bound on \[\log u = \sum_{p\le k} v_p\left(\binom{n}{k}\right)\log p\] that produces an explicit $k=k(n)$ with $\log u > 2\log n$ for all sufficiently large $n$. Without such a bound I cannot prove any explicit asymptotic upper bound on $f(n)$.

(iii) Top 3 next moves. $1$ For a candidate scale $k=k(n)$ (e.g. $k\sim c\log n$ suggested by numerics), lower bound $v_p\left(\binom{n}{k}\right)$ for small primes $p\le k$ using Legendre's formula for $v_p(n!)$ and optimize the resulting sum. $2$ Use sieve/entropy-style bounds: show that the contribution to $\binom{n}{k}$ from primes $>k$ cannot dominate too heavily, forcing a definite portion of $\log\binom{n}{k}$ to come from primes $\le k$. $3$ Extend computation (say to $n\le 10^{6}$) and fit $f(n)$ against functions like $\log n$, $(\log n)^2$, $\log n\,\log\log n$ to guess the correct order of growth and then target that scale analytically.

(iv) Minimal counterexample structure. A minimal obstruction to small $f(n)$ would be an $n$ for which for every moderately small $k$ (e.g. $k\le K$) the binomial coefficient $\binom{n}{k}$ has its mass concentrated on prime factors $>k$, so that its $k$-smooth part $u$ stays $\le n^{2}$. Any explicit lower bound must rule out such extreme "rough dominance".

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. For $0\le k\le n$, write \[\binom{n}{k}=u\,v\] where every prime divisor of $u$ lies in $[2,k]$ and every prime divisor of $v$ lies in $(k,n]$. Define $f(n)$ to be the smallest $k$ such that $u>n^{2}$. Find upper and lower bounds for $f(n)$ as $n\to\infty$.

QUICK LITERATURE/CONTEXT CHECK. The problem statement notes (treated as given) that Mahler's theorem implies $f(n)\to\infty$ but ineffectively. I do not assume further results.

ATTACK PLAN. The quantity $u$ is exactly the $k$-smooth part of $\binom{n}{k}$: it is built from the prime powers $p^{v_p(\binom{n}{k})}$ for primes $p\le k$. Thus one seeks a $k$ where the contribution from small primes to $\binom{n}{k}$ already exceeds $n^2$. A first step is an exact expression for $u$ in terms of prime-adic valuations, then to try to lower bound $\log u$.

WORK. Lemma 1 (Prime-valuation formula for $u$). Let $v_p(m)$ be the exponent of a prime $p$ in $m$. For $0\le k\le n$, \[ u = \prod_{p\le k} p^{\,v_p\left(\binom{n}{k}\right)}. \] Equivalently, \[\log u = \sum_{p\le k} v_p\left(\binom{n}{k}\right)\,\log p. \]

Proof. By the fundamental theorem of arithmetic, $\binom{n}{k}=\prod_p p^{v_p(\binom{n}{k})}$. The definition of the factorization $\binom{n}{k}=uv$ requires $u$ to contain exactly the prime powers with primes $p\le k$, and $v$ to contain those with primes $p>k$. Therefore $u=\prod_{p\le k} p^{v_p(\binom{n}{k})}$, and taking logs gives the second identity. $\square$

Lemma 2 ($k=0$ and $k=1$ never witness $u>n^2$). For every $n\ge2$ and $k\in\{0,1,n-1,n\}$, the corresponding $u$ satisfies $u\le n$, hence $u\le n^{2}$. In particular $f(n)\ge 2$ whenever $f(n)$ is finite.

Proof. If $k=0$ or $k=n$, then $\binom{n}{k}=1$ and (vacuously) $u=1\le n^{2}$. If $k=1$ or $k=n-1$, then $\binom{n}{k}=n$. By definition, $u$ only uses primes $\le k$. For $k=1$ there are no primes $\le1$, so $u=1$. For $k=n-1$, all primes $\le n-1$ are allowed, so $u=n$, but still $u=n\le n^{2}$. Thus none of these $k$ can satisfy $u>n^{2}$. $\square$

VERIFICATION (FAST REALITY CHECK). I implemented the exact definition of $u$ via Lemma 1 and brute-forced $f(n)$ for many $n$. For each $n$, I searched the smallest $k\in\{0,1,\dots,n\}$ with $u>n^{2}$. Results:

For n<=60: f(n) is undefined for n in {2..9,11..15,17,19,20,23}.
For n<=1000: the same undefined set occurs; for all n>=24 up to 1000, f(n) exists.
For n<=20000:
  f(n) exists for all n>=24 in this range,
  max f(n) observed is 73 (attained at n=12119),
  median f(n) over n=2..20000 where defined is 29.

These computations suggest that $f(n)$ is finite for all $n\ge 24$ and grows very slowly (at least up to $n=2\cdot 10^{4}$), but this is only empirical.

FINAL. UNRESOLVED.

(i) Strongest proved partial result. The factor $u$ is exactly the $k$-smooth part of $\binom{n}{k}$ and admits the exact valuation formula of Lemma 1. Also, trivial $k\in\{0,1,n-1,n\}$ never witness $u>n^{2}$ (Lemma 2).

(ii) First gap (crisp). I do not have an effective lower bound on \[\log u = \sum_{p\le k} v_p\left(\binom{n}{k}\right)\log p\] that produces an explicit $k=k(n)$ with $\log u > 2\log n$ for all sufficiently large $n$. Without such a bound I cannot prove any explicit asymptotic upper bound on $f(n)$.

(iii) Top 3 next moves. $1$ For a candidate scale $k=k(n)$ (e.g. $k\sim c\log n$ suggested by numerics), lower bound $v_p\left(\binom{n}{k}\right)$ for small primes $p\le k$ using Legendre's formula for $v_p(n!)$ and optimize the resulting sum. $2$ Use sieve/entropy-style bounds: show that the contribution to $\binom{n}{k}$ from primes $>k$ cannot dominate too heavily, forcing a definite portion of $\log\binom{n}{k}$ to come from primes $\le k$. $3$ Extend computation (say to $n\le 10^{6}$) and fit $f(n)$ against functions like $\log n$, $(\log n)^2$, $\log n\,\log\log n$ to guess the correct order of growth and then target that scale analytically.

(iv) Minimal counterexample structure. A minimal obstruction to small $f(n)$ would be an $n$ for which for every moderately small $k$ (e.g. $k\le K$) the binomial coefficient $\binom{n}{k}$ has its mass concentrated on prime factors $>k$, so that its $k$-smooth part $u$ stays $\le n^{2}$. Any explicit lower bound must rule out such extreme "rough dominance".