5
$\begingroup$

I came across this question while doing some research at an REU this summer. It was supposed to be just a small part of a larger proof, but we've been stumped on it for a while. I don't have much of a background in number theory, but so far I haven't been able to find any properties or things to help me prove the following. Would appreciate any advice on how to proceed!

Consider: $ x = (n+k)(n+k-1)... (n+2)$ where $n≥k$ and $n,k \in \mathbb{N}$. I want to show that the prime factorization of $x$ will have at least one prime factor greater than $k$ when $k≥3$.

$\endgroup$
4
  • $\begingroup$ Well, I think you can remove the denominator from the question, as it does not really matter... $\endgroup$ Commented Jul 26, 2016 at 2:05
  • $\begingroup$ This sounds a bit stronger than Sylvester's theorem (generalization of Chebyshev), which says that $(n+1) \times \cdots \times (n+k)$ is divisible by a prime greater than $k$. $\endgroup$
    – user325968
    Commented Jul 26, 2016 at 2:51
  • $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$
    – Will Jagy
    Commented Jul 26, 2016 at 2:56
  • $\begingroup$ As written it's false when $k=3,n=6$. $\endgroup$
    – Zander
    Commented Jul 26, 2016 at 12:51

1 Answer 1

1
$\begingroup$

This is a really awesome question. I haven't spent much time thinking about this problem, so I'm sure you have better intuition on it than me. I have a heuristic argument that appears to suggest that what you want is indeed true for large $n$. My reasoning is as follows.

Let $P(i)$ denote the largest prime factor of a positive integer $i$, and let $S(x)$ be defined by $$S(x) = \sum_{2 \leq i \leq x} P(i).$$ It is a result of Krishnaswami Alladi and Paul Erdos (see their paper: Pacific J. Math. 71(1977) 275-294) that $$S(x) \sim \frac{\pi^2}{12}\frac{x^2}{\log x},$$ where by ``$\sim$'' I mean asymptotic equivalence (approximate order of growth -- remember, this is a heuristic argument, not meant to be precise). Then the sum of the largest prime factors of the numbers $n+2, \dots, n+k$ is given approximately by $$\sum_{i = n+2}^{n+k} P(i) = \sum_{i = 2}^{n+k} P(i) - \sum_{i = 2}^{n+2} P(i) \sim \frac{\pi^2}{12}\left(\frac{(n+k)^2}{\log(n+k)} - \frac{(n+2)^2}{\log(n+2)}\right).$$ To leading order in $n$, the last expression above is approximately $$\frac{\pi^2k}{6}\frac{n}{\log n}.$$

Now, if your claim is true, that the product $(n+2)\cdots(n+k)$ has a prime factor greater than $k$ for all $n \geq k \geq 3$, then the above approximate sum should be bigger than $k$ times the number of factors being multiplied, which is $n+k - (n+2) + 1 = k - 1$, so again working to leading order, you end up getting the approximate inequality $$\frac{\pi^2k}{6}\frac{n}{\log n} \gg k(k-1),$$ and this inequality actually does hold for large $n$. This intuition tells me that your conjecture is true!

To conclude, let me mention where the above argument is not rigorous. I used the result of Alladi and Erdos in a subtraction, but perhaps the error term on their result is so large that such an argument is invalid. I also threw out a lot of non-leading terms in places that may have actually been important.

An alternative strategy would be to try improving upon Sylvester's Theorem; look up a proof and see if you can optimize the methods!

$\endgroup$
3
  • $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$
    – Will Jagy
    Commented Jul 26, 2016 at 2:58
  • $\begingroup$ I think there was a small mistake in what you wrote, the number of factors being multiplied there is $k-1$ not $n+k-1$, though I'm not sure if that changes your argument. I think there might be something to Sylvester's theorem mentioned above though! $\endgroup$
    – EJ701
    Commented Jul 26, 2016 at 3:07
  • $\begingroup$ @EdgarJ You are absolutely right on the money. That changed things very much indeed! Now, my argument suggests that your conjecture is right. Let me know if you can turn my argument into a real solid proof! You can use my argument to deal with large $n$, and then just use a computer program to check the smaller values of $n$. $\endgroup$ Commented Jul 26, 2016 at 3:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .