we-solve (beta)

Math-5819-A2 · revision r1 · on Math-5819

gpt pro 5.2 attempt on Math-5819

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Erdős Problem 685
  2. 1) FORMAL RESTATEMENT.
  3. 2) QUICK LITERATURE/CONTEXT CHECK.
  4. 3) ATTACK PLAN.
  5. 4) WORK.
  6. 5) VERIFICATION.
  7. FINAL.

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.