Erdős Problem #685

Erdős Problem 685 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

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

Erdős Problem 685

1) FORMAL RESTATEMENT.

For integers $n\ge 2$ and $1\le k\le n-1$, write \[ \omega\!\left(\binom{n}{k}\right):=\#\{\,\text{primes }p:\ p\mid \binom{n}{k}\,\} \] for the number of distinct prime divisors of $\binom{n}{k}$. The question is whether the following asymptotic statement is true.

Conjectured asymptotic. Fix $\epsilon>0$. As $n\to\infty$, uniformly for all integers $k$ with \[ n^\epsilon<k\le n^{1-\epsilon}, \] do we have \[ \omega\!\left(\binom{n}{k}\right) =(1+o(1))\,k\sum_{\substack{\text{prime }p\\ k<p<n}}\frac1p\,? \] Here $o(1)$ means a quantity tending to $0$ as $n\to\infty$ (possibly depending on $\epsilon$).

2) QUICK LITERATURE/CONTEXT CHECK.

No external literature is used or claimed here beyond what is explicitly written in the problem statement. The main heuristic is that for primes $p>k$, the event $p\mid \binom{n}{k}$ is equivalent to a simple residue condition ($n\bmod p<k$), which has "probability" about $k/p$ if residues behave randomly; summing $k/p$ over primes $p\in(k,n)$ gives the proposed main term.

3) ATTACK PLAN.

• Proof-track idea: reduce (most of) $\omega(\binom{n}{k})$ to a sum of indicators $\sum_{k<p<n}\mathbf 1_{n\bmod p<k}$ (Lemma 685.1 below) and then prove concentration around its mean $k\sum_{k<p<n}1/p$ via a variance/correlation estimate (e.g. large-sieve--type bounds).
• Disproof-track idea: try to construct $n$ (as a function of $k$) so that $n\bmod p$ lies in $\{0,1,\dots,k-1\}$ for "too many" primes $p\in(k,n)$, i.e. make $n$ unusually close to a multiple of many primes; then check whether this can beat the conjectured main term.

4) WORK.

Lemma 685.1 (exact divisibility criterion for primes $p>k$). Let $n\ge 1$, $1\le k\le n$, and let $p$ be a prime with $p>k$. Write $n=ap+b$ with integers $a\ge 0$ and $0\le b<p$. Then \[ p\mid \binom{n}{k}\quad\Longleftrightarrow\quad b<k, \] i.e. $p\mid \binom{n}{k}$ if and only if $n\bmod p\in\{0,1,\dots,k-1\}$.

Proof. We use Vandermonde's identity: \[ \binom{ap+b}{k}=\sum_{i=0}^k \binom{ap}{i}\binom{b}{k-i}. \] Fix an integer $i$ with $1\le i\le k<p$. We claim $p\mid \binom{ap}{i}$. Indeed, \[ \binom{ap}{i}=\frac{ap(ap-1)\cdots (ap-i+1)}{i!}. \] Among the $i$ consecutive integers $ap,ap-1,\dots,ap-i+1$ with $i<p$, exactly one is divisible by $p$, namely $ap$. Hence the numerator has $p$-adic valuation exactly $1$. On the other hand $i!$ is not divisible by $p$ because $i<p$. Therefore $v_p\!\left(\binom{ap}{i}\right)=1$ and in particular $p\mid \binom{ap}{i}$.

Reducing Vandermonde's sum modulo $p$, all terms with $i\ge 1$ vanish, so \[ \binom{ap+b}{k}\equiv \binom{b}{k}\pmod p. \] If $b<k$ then $\binom{b}{k}=0$, so $p\mid \binom{n}{k}$. If $b\ge k$, then $\binom{b}{k}$ is a nonzero integer whose numerator and denominator involve only factors $<p$, so neither is divisible by $p$, hence $p\nmid \binom{b}{k}$ and thus $p\nmid \binom{n}{k}$. This proves the equivalence. $\square$

Lemma 685.2 (mean value over $n$ for the $p>k$ contribution). Fix integers $N>k\ge 1$. For each $n\in\{1,2,\dots,N\}$ define \[ A(n):=\#\{\,\text{primes }p:\ k<p\le N,\ \ p\mid \binom{n}{k}\,\}. \] Then \[ \frac1N\sum_{n=1}^N A(n)=k\sum_{\substack{\text{prime }p\\ k<p\le N}}\frac1p\;+\;O\!\left(\frac{k\,\pi(N)}{N}\right), \] where $\pi(N)$ is the number of primes $\le N$.

Proof. By Lemma 685.1, \[ A(n)=\sum_{\substack{\text{prime }p\\ k<p\le N}} \mathbf 1_{\,n\bmod p<k}. \] Averaging over $n\in\{1,\dots,N\}$ and interchanging sum and average gives \[ \frac1N\sum_{n=1}^N A(n)=\sum_{\substack{\text{prime }p\\ k<p\le N}} \left(\frac1N\sum_{n=1}^N \mathbf 1_{\,n\bmod p<k}\right). \] Fix such a prime $p$. Partition $\{1,\dots,N\}$ into $\lfloor N/p\rfloor$ full blocks of length $p$ and one final incomplete block of length $<p$. In each full block, exactly $k$ residues satisfy $n\bmod p<k$, so the count of $n\le N$ with $n\bmod p<k$ is \[ k\left\lfloor\frac{N}{p}\right\rfloor + r_p, \qquad\text{with}\qquad 0\le r_p\le k, \] where $r_p$ is the contribution of the final incomplete block. Therefore \[ \frac1N\sum_{n=1}^N \mathbf 1_{\,n\bmod p<k} =\frac{k}{p}+O\!\left(\frac{k}{N}\right). \] Summing this over primes $k<p\le N$ yields \[ \frac1N\sum_{n=1}^N A(n)=k\sum_{k<p\le N}\frac1p+O\!\left(\frac{k}{N}\cdot \pi(N)\right), \] as claimed. $\square$

FAST REALITY CHECK (local computation). I computed $\omega\!\left(\binom{n}{k}\right)$ exactly using Legendre's formula for prime exponents in factorials, and compared it to the heuristic main term $k\sum_{k<p<n}1/p$ (computed in floating point). For $n=100000$ (primes up to $n$ are $9592$) the script printed:

n=100000
k=   10  omega=   16  pred=  15.290817028567766  ratio=1.046379665004641
k=   31  omega=   40  pred=  35.32683562243201   ratio=1.1322836958145384
k=  100  omega=  107  pred=  90.2454977998395    ratio=1.1856547152891908
k=  177  omega=  167  pred= 139.45259620695515   ratio=1.1975395549621968
k=  316  omega=  264  pred= 215.74872169726672   ratio=1.2236457204619655
k= 1000  omega=  636  pred= 507.19205187217455   ratio=1.253962868014912
k= 3162  omega= 1481  pred=1125.679237358206     ratio=1.315650098935534

These are only sanity checks at a single $n$, not evidence of an asymptotic theorem.

5) VERIFICATION.

• Lemma 685.1 uses only the hypothesis $p>k$ (so that $p\nmid k!$ and $i!$ for $i\le k$), and otherwise is an exact congruence.
• Lemma 685.2 is a direct averaging identity and does not assume any distribution of primes beyond their finiteness up to $N$.
• The conjecture concerns all primes dividing $\binom{n}{k}$, including primes $p\le k$; Lemmas 685.1--685.2 address only $p>k$. A complete proof would have to show that the contribution of $p\le k$ is lower order (or is absorbed into the stated main term).

FINAL.

UNRESOLVED

(i) Strongest proved partial result. For every prime $p>k$, we have an exact criterion \[ p\mid \binom{n}{k}\ \Longleftrightarrow\ n\bmod p<k \] (Lemma 685.1), and consequently the mean over $n\le N$ of the count of such primes equals $k\sum_{k<p\le N}1/p$ up to an explicit $O(k\pi(N)/N)$ error (Lemma 685.2).

(ii) First gap (crisp statement). Prove uniform concentration for \[ \sum_{\substack{\text{prime }p\\ k<p<n}} \mathbf 1_{\,n\bmod p<k} \] around its mean $k\sum_{k<p<n}1/p$ for all $n^\epsilon<k\le n^{1-\epsilon}$, and also control the contribution of primes $p\le k$ to $\omega\!\left(\binom{n}{k}\right)$.

(iii) Top 3 next moves.

1. Compute the second moment over $n\le N$ of $A(n)$ from Lemma 685.2, i.e. bound $\sum_{n\le N}(A(n)-\mathbb E A)^2$ by estimating correlations $\#\{n\le N:\ n\bmod p<k,\ n\bmod q<k\}$ for distinct primes $p,q$.
2. Attempt a large-sieve--type inequality to show that for most $n$, the residue constraints $n\bmod p<k$ do not hold for too many primes.
3. Isolate primes $p\le k$: express $\omega\!\left(\binom{n}{k}\right)$ as $\omega_{>k}(\binom{n}{k})+\omega_{\le k}(\binom{n}{k})$ and prove a uniform upper bound on $\omega_{\le k}(\binom{n}{k})$ that is $o\!\left(k\sum_{k<p<n}1/p\right)$ in the regime $n^\epsilon<k\le n^{1-\epsilon}$.

(iv) What a minimal counterexample would likely look like. A counterexample would require some $n,k$ with $n^\epsilon<k\le n^{1-\epsilon}$ such that $n$ lies in the "small residue" set $n\bmod p\in\{0,\dots,k-1\}$ for significantly more (or fewer) primes $p\in(k,n)$ than the heuristic $k/p$ suggests, i.e. $n$ is unusually close to multiples of many primes in $(k,n)$; additionally, primes $\le k$ would need to contribute non-negligibly.

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.

Erdős Problem 685

1) FORMAL RESTATEMENT.

For integers $n\ge 2$ and $1\le k\le n-1$, write \[ \omega\!\left(\binom{n}{k}\right):=\#\{\,\text{primes }p:\ p\mid \binom{n}{k}\,\} \] for the number of distinct prime divisors of $\binom{n}{k}$. The question is whether the following asymptotic statement is true.

Conjectured asymptotic. Fix $\epsilon>0$. As $n\to\infty$, uniformly for all integers $k$ with \[ n^\epsilon<k\le n^{1-\epsilon}, \] do we have \[ \omega\!\left(\binom{n}{k}\right) =(1+o(1))\,k\sum_{\substack{\text{prime }p\\ k<p<n}}\frac1p\,? \] Here $o(1)$ means a quantity tending to $0$ as $n\to\infty$ (possibly depending on $\epsilon$).

2) QUICK LITERATURE/CONTEXT CHECK.

No external literature is used or claimed here beyond what is explicitly written in the problem statement. The main heuristic is that for primes $p>k$, the event $p\mid \binom{n}{k}$ is equivalent to a simple residue condition ($n\bmod p<k$), which has "probability" about $k/p$ if residues behave randomly; summing $k/p$ over primes $p\in(k,n)$ gives the proposed main term.

3) ATTACK PLAN.

• Proof-track idea: reduce (most of) $\omega(\binom{n}{k})$ to a sum of indicators $\sum_{k<p<n}\mathbf 1_{n\bmod p<k}$ (Lemma 685.1 below) and then prove concentration around its mean $k\sum_{k<p<n}1/p$ via a variance/correlation estimate (e.g. large-sieve--type bounds).
• Disproof-track idea: try to construct $n$ (as a function of $k$) so that $n\bmod p$ lies in $\{0,1,\dots,k-1\}$ for "too many" primes $p\in(k,n)$, i.e. make $n$ unusually close to a multiple of many primes; then check whether this can beat the conjectured main term.

4) WORK.

Lemma 685.1 (exact divisibility criterion for primes $p>k$). Let $n\ge 1$, $1\le k\le n$, and let $p$ be a prime with $p>k$. Write $n=ap+b$ with integers $a\ge 0$ and $0\le b<p$. Then \[ p\mid \binom{n}{k}\quad\Longleftrightarrow\quad b<k, \] i.e. $p\mid \binom{n}{k}$ if and only if $n\bmod p\in\{0,1,\dots,k-1\}$.

Proof. We use Vandermonde's identity: \[ \binom{ap+b}{k}=\sum_{i=0}^k \binom{ap}{i}\binom{b}{k-i}. \] Fix an integer $i$ with $1\le i\le k<p$. We claim $p\mid \binom{ap}{i}$. Indeed, \[ \binom{ap}{i}=\frac{ap(ap-1)\cdots (ap-i+1)}{i!}. \] Among the $i$ consecutive integers $ap,ap-1,\dots,ap-i+1$ with $i<p$, exactly one is divisible by $p$, namely $ap$. Hence the numerator has $p$-adic valuation exactly $1$. On the other hand $i!$ is not divisible by $p$ because $i<p$. Therefore $v_p\!\left(\binom{ap}{i}\right)=1$ and in particular $p\mid \binom{ap}{i}$.

Reducing Vandermonde's sum modulo $p$, all terms with $i\ge 1$ vanish, so \[ \binom{ap+b}{k}\equiv \binom{b}{k}\pmod p. \] If $b<k$ then $\binom{b}{k}=0$, so $p\mid \binom{n}{k}$. If $b\ge k$, then $\binom{b}{k}$ is a nonzero integer whose numerator and denominator involve only factors $<p$, so neither is divisible by $p$, hence $p\nmid \binom{b}{k}$ and thus $p\nmid \binom{n}{k}$. This proves the equivalence. $\square$

Lemma 685.2 (mean value over $n$ for the $p>k$ contribution). Fix integers $N>k\ge 1$. For each $n\in\{1,2,\dots,N\}$ define \[ A(n):=\#\{\,\text{primes }p:\ k<p\le N,\ \ p\mid \binom{n}{k}\,\}. \] Then \[ \frac1N\sum_{n=1}^N A(n)=k\sum_{\substack{\text{prime }p\\ k<p\le N}}\frac1p\;+\;O\!\left(\frac{k\,\pi(N)}{N}\right), \] where $\pi(N)$ is the number of primes $\le N$.

Proof. By Lemma 685.1, \[ A(n)=\sum_{\substack{\text{prime }p\\ k<p\le N}} \mathbf 1_{\,n\bmod p<k}. \] Averaging over $n\in\{1,\dots,N\}$ and interchanging sum and average gives \[ \frac1N\sum_{n=1}^N A(n)=\sum_{\substack{\text{prime }p\\ k<p\le N}} \left(\frac1N\sum_{n=1}^N \mathbf 1_{\,n\bmod p<k}\right). \] Fix such a prime $p$. Partition $\{1,\dots,N\}$ into $\lfloor N/p\rfloor$ full blocks of length $p$ and one final incomplete block of length $<p$. In each full block, exactly $k$ residues satisfy $n\bmod p<k$, so the count of $n\le N$ with $n\bmod p<k$ is \[ k\left\lfloor\frac{N}{p}\right\rfloor + r_p, \qquad\text{with}\qquad 0\le r_p\le k, \] where $r_p$ is the contribution of the final incomplete block. Therefore \[ \frac1N\sum_{n=1}^N \mathbf 1_{\,n\bmod p<k} =\frac{k}{p}+O\!\left(\frac{k}{N}\right). \] Summing this over primes $k<p\le N$ yields \[ \frac1N\sum_{n=1}^N A(n)=k\sum_{k<p\le N}\frac1p+O\!\left(\frac{k}{N}\cdot \pi(N)\right), \] as claimed. $\square$

FAST REALITY CHECK (local computation). I computed $\omega\!\left(\binom{n}{k}\right)$ exactly using Legendre's formula for prime exponents in factorials, and compared it to the heuristic main term $k\sum_{k<p<n}1/p$ (computed in floating point). For $n=100000$ (primes up to $n$ are $9592$) the script printed:

n=100000
k=   10  omega=   16  pred=  15.290817028567766  ratio=1.046379665004641
k=   31  omega=   40  pred=  35.32683562243201   ratio=1.1322836958145384
k=  100  omega=  107  pred=  90.2454977998395    ratio=1.1856547152891908
k=  177  omega=  167  pred= 139.45259620695515   ratio=1.1975395549621968
k=  316  omega=  264  pred= 215.74872169726672   ratio=1.2236457204619655
k= 1000  omega=  636  pred= 507.19205187217455   ratio=1.253962868014912
k= 3162  omega= 1481  pred=1125.679237358206     ratio=1.315650098935534

These are only sanity checks at a single $n$, not evidence of an asymptotic theorem.

5) VERIFICATION.

• Lemma 685.1 uses only the hypothesis $p>k$ (so that $p\nmid k!$ and $i!$ for $i\le k$), and otherwise is an exact congruence.
• Lemma 685.2 is a direct averaging identity and does not assume any distribution of primes beyond their finiteness up to $N$.
• The conjecture concerns all primes dividing $\binom{n}{k}$, including primes $p\le k$; Lemmas 685.1--685.2 address only $p>k$. A complete proof would have to show that the contribution of $p\le k$ is lower order (or is absorbed into the stated main term).

FINAL.

UNRESOLVED

(i) Strongest proved partial result. For every prime $p>k$, we have an exact criterion \[ p\mid \binom{n}{k}\ \Longleftrightarrow\ n\bmod p<k \] (Lemma 685.1), and consequently the mean over $n\le N$ of the count of such primes equals $k\sum_{k<p\le N}1/p$ up to an explicit $O(k\pi(N)/N)$ error (Lemma 685.2).

(ii) First gap (crisp statement). Prove uniform concentration for \[ \sum_{\substack{\text{prime }p\\ k<p<n}} \mathbf 1_{\,n\bmod p<k} \] around its mean $k\sum_{k<p<n}1/p$ for all $n^\epsilon<k\le n^{1-\epsilon}$, and also control the contribution of primes $p\le k$ to $\omega\!\left(\binom{n}{k}\right)$.

(iii) Top 3 next moves.

1. Compute the second moment over $n\le N$ of $A(n)$ from Lemma 685.2, i.e. bound $\sum_{n\le N}(A(n)-\mathbb E A)^2$ by estimating correlations $\#\{n\le N:\ n\bmod p<k,\ n\bmod q<k\}$ for distinct primes $p,q$.
2. Attempt a large-sieve--type inequality to show that for most $n$, the residue constraints $n\bmod p<k$ do not hold for too many primes.
3. Isolate primes $p\le k$: express $\omega\!\left(\binom{n}{k}\right)$ as $\omega_{>k}(\binom{n}{k})+\omega_{\le k}(\binom{n}{k})$ and prove a uniform upper bound on $\omega_{\le k}(\binom{n}{k})$ that is $o\!\left(k\sum_{k<p<n}1/p\right)$ in the regime $n^\epsilon<k\le n^{1-\epsilon}$.

(iv) What a minimal counterexample would likely look like. A counterexample would require some $n,k$ with $n^\epsilon<k\le n^{1-\epsilon}$ such that $n$ lies in the "small residue" set $n\bmod p\in\{0,\dots,k-1\}$ for significantly more (or fewer) primes $p\in(k,n)$ than the heuristic $k/p$ suggests, i.e. $n$ is unusually close to multiples of many primes in $(k,n)$; additionally, primes $\le k$ would need to contribute non-negligibly.