Updates on a least prime factor conjecture by Erdos

Question

In the 1993 article "Estimates of the Least Prime Factor of a Binomial Coefficient," Erdos et al. conjectured that $$\operatorname{lpf} {N \choose k} \leq \max(N/k,13)$$

With finitely many exceptional $(N,k)$. Here, $\operatorname{lpf}(x)$ denotes the smallest prime factor of $x$.

I am posting here to ask whether any progress has been made toward this conjecture.

Answer 1

The authors of the paper you mention, Erdos, Lacampagne, and Selfridge, define $p(m)$ to be the least prime divisor of $m$ and concern themselves what can be said about $p(\binom{n}{k}).$ I suspect that Selfridge wrote the article. It has his style of saying a lot in a succinct way which is puzzling but solvable with some thought on the part of the reader. The conjecture stated in the abstract is $$p(\binom{n}{k}) \leq \max(\frac{n}{k},29).$$ That shouldn't be thought of as their big conjecture but rather a terse and amusing way of capturing some of the the main points.

The short answer to your question is that they did a lot of computation, made some observations that had theoretical backing and strong computational support. No-one, as far as I know, has challenged or refuted them and perhaps it isn't especially attractive to try further computation. Or perhaps it is, but not to report "I didn't find anything else either."

Aside: They are perhaps more interested in the growth rate of $g(k),$ the minimal $n>k$ with $p(\binom{n}{k})>k.$ I feel compelled to quote a small stretch of the article:

That is a whole mess of conjectures, but not snappy enough for an abstract. That is the subject of section 1 of the paper. They and others explored $g(k)$ up to about $k=140$ and with more powerful computers the results were later extended to about $k=200.$ The current record lower bound is $$g(k) \geq exp(c(\log^3k/\log \log k)^{1/2}).$$

Getting back to the conjecture you ask about, the first puzzle is

• The stated conjecture is clearly false. $\binom{n}{n-1}=n$ is prime when $n$ is. I can imagine Selfridge saying "Well of course we don't mean that." And if you read in further, the investigation is only for $k<n/2.$ The case $n=2k$ is a very small puzzle left to you.

Another puzzle is

• Why $\frac{n}{k}?$ Is that best possible? Here is my take on that, read the article for a more elegant and general treatment: Suppose $p=q(k-1)!+1$ is prime. Then, for $n=pk,$ $$\binom{n}{k}=\prod_{i=0}^{k-1}\frac{n-i}{k-i}$$ where the $k$ factors are integers. If they all happen to be prime then $p(\binom{n}{k})=p=\frac{n}{k}.$ I can convince myself that for every $k$ we would expect that to happen infinitely often. Perhaps that is alluded to in the article or perhaps it is too obviously right (or wrong) to mention.

Another (small) puzzle is

• How you could ever have $p(\binom{n}{k})>\frac{n}{k}?$ After all, there is a $0 \leq j <k$ with $\frac{n-j}{k}$ an integer, so $\frac{n}{k}$ seems a clear upper bound. And it is, for large enough $n.$ However, while $\binom{62}{6}$ is divisible by some divisor of $\frac{60}{6},$ that divisor is $1$ ! $$\binom{62}{6}=\frac{62}{2}\cdot 61 \cdot \frac{60}{60}\cdot 59 \cdot \frac{58}{2} \cdot \frac{57}{3}$$

They conjecture that, for $n \gt k^2$, $p(\binom{n}{k}) \geq \frac{n}{k}$ with that one exception of $p(\binom{62}{6})=\frac{n-5}{3}=19$

They also conjecture that this one, along with $p(\binom{959}{6})=19,p(\binom{474}{66})=23$ and $p(\binom{284}{28})=29$ are the only cases with $p(\binom{n}{k}) \gt \min(\frac{n}{k},19).$

They find eight cases with $p(\binom{n}{k})=17>\frac{n}{k}.$

They say that they wrote a program to find all cases of $p(\binom{n}{k})=p>\frac{N}{k}$ with $p>5$ and $k \leq 12000.$ It must not have been entirely exhaustive because they say that there was only one output other than the twelve mentioned for $331 <k <625$ and that was $p(\binom{3574}{406})=13$. They continue "Thus, at this point in time, it is possible that $p(\binom{n}{k})\leq\max(\frac{n}{k},13).$" So that is short of making a conjecture, but I don't know that there are any exceptions known other than the thirten they mention.

One might wonder why they said $p>5.$ Anyone familiar with Pascal's Triangle $\mod 2$ will realize that for every $k>2$ there are lots of cases of $p(\binom{n}{k})=3$ with $2k<n<3k.$ The article gives a nice proof that there is always at least one case of $p(\binom{n}{k})=5$ with $3k<n<4k.$

There is much more in that article, but I will stop there.

Answer 2

The conjecture as written is false:

Let $N=194+(2*3*5*7*11*13)*2n$, $k=N-2$, where $n$ is a natural number.

Then $C(N,k)=C(N,2)=(97+2*3*5*7*11*13*n)(193+2*3*5*7*11*13*2n)$, having no prime factors $\leq 13$.