1
$\begingroup$

I've found an argument that if valid suggests that there is always a prime $p > n$ that divides ${{x+n} \choose n}$ when $x > \pi(n)$.

As a math amateur, I am always doubtful about my results so I cannot claim that my argument is without mistake (for those interested in the argument, I have posted it here in mse).

My question is whether this result is within possibility and if it is within possibility, what are well-known results related to the number of distinct primes when $x > \pi(n)$.

If it is a well-known result, if someone could provide a citation, that would be awesome.

If the argument is not within the realm of possibility, I would be very interested in the theorem(s) that would exclude the result which will help me to find my mistake and improve my intuition. :-)


Edit: I removed the following based on Gerry's comment:

Further, if $x > \pi(n) + c$, then there are at least $\min(n,c)$ such primes.

This statement is clearly wrong for $n=c=100 , x=125, {{225+100}\choose{100}}$ since there are less than $100$ primes.

$\endgroup$
2
  • $\begingroup$ $n=c=100$, $x=125$, ${225+100\choose100}$ can't be divisible by 100 primes $p>100$ since there aren't that many primes between 100 and 225. $\endgroup$ May 17 '18 at 12:42
  • $\begingroup$ Thanks, Gerry. I’ll update my question to remove the comment about $c$. That is clearly wrong. $\endgroup$ May 17 '18 at 15:05
4
$\begingroup$

Gerry Myerson's observation should help you find the mistake in your argument. Even though there are many on MathOverflow who might find what I write below unsuitable for this forum, I will take the time to critique the linked proof. The argument against doing this on MathOverflow is that much of what is to be said is part of "basic mathematical training", both in thinking and in exposition, that many readers here do not need to see yet again, and that such basic training is outside the forum. Indeed I can see reasons for doing this privately in an email. The argument for putting it on MathOverflow is twofold: reminders of what "basic mathematical training" is should be somewhere, and if a new reader to the forum wants to know what is to be expected in order to have discourse here beyond the phrase "mathematical maturity", it would be good to have an explicit example of what that means. The second part of the argument is that this relates to some combinatorial number theory I am researching and writing about here, and this post helps me solidify my own work.

Before I begin criticism, I say that I admire your effort and I believe it shows evidence of talent. If the criticism is ego deflating, I apologize for that; my intention is to point out flaws and places for improvement, and make clear as much as I can many elements of "basic training".

(I will post now to get my foot in the door, and add remarks later today.)

The first motto of basic training is answered by Gerry Myerson's example, which is "Check that what you just said is wrong (or isn't)." Indeed your statements above are not quite what you attempt in your linked proof (you use $n/2$ instead of $\pi(n)$ behind the link), and if you attempt a natural generalization, you should always make such an attempt conjectural until you have something that can convince and later be formalized. Indeed, easy counterexamples are what often appear on MathOverflow, because that is an easy tool to use. You may not catch the easy counterexample, but you are expected to have looked for it before posting.

Another early motto is "If it isn't wrong, more power!" (Thanks to Tim Taylor, character of the TV series Home Improvement). This is an attempt to generalize to find what the truth is exactly. Finding the exact statement is often a challenge, but finding 'nearby' but wrong statements is easy. Even if you can't find a real good spot to pitch a tent, you can at least find a creek, bear cave, and/or roaring fire nearby to tell you what to avoid. In research you often encounter what are perceived to be dead ends. They aren't dead, they are indicators of where in the exploratory space you do not need to spend time. If you have done the easy work but do not share some of it in your post, you invite the situation of others finding the same creek or bear cave or fire and not finding (and telling you about) the poison ivy.

Edit 2018.05.18

Along the lines of sharing what you know is wrong, share what you don't know. (Choosing what and how much to share in a MathOverflow question, comment, or answer is an issue that will be addressed later.). In starting your proof, I am glad you called out your assumption of the basic inequality that is a key point in your linked proof. I believe that the power of the prime $p$ dividing $\binom{x+n}{n}$ is indeed smaller than the maximum of the powers of $p$ dividing any of the terms $x+j$ in the numerator, where $x,n,j$ are positive integers and $j$ is at most $n$. It is hard to come up with a nice combinatorial proof of this, and your attempt is a nice approach. (I won't comment in detail on your proof of this inequality besides saying that your step 8 where "the largest power is in the middle" needs more, and the other steps will benefit from the commentary below.)

I believe this inequality because of Kummer's theorem relating the number of carries in base p to the valuation, and that in order to get $k$ many carries, at least one of the $x+j$ has to be a multiple of $p^k$. Formalizing this belief simply and thoroughly is taking me a long time, and I think the motto "Understand Your Ignorance" was well applied by you in the linked proof.

A word on style. It is clear you are being careful, and that you proceed in small steps, which is good for debugging, and somewhat of a challenge for reading. There is also a mix of clarity and ambiguity, where in many cases it seems I can understand what you want to say, but you have left out some words. I will highlight some of these and suggest alternatives to help the reader.

Your introduction and your steps (1) and (2) I find clear. (Often the default is to assume $x$ is not an integer. You should state $x$ and $n$ are integers.) I understand (3) and (4) after some effort, but you should motivate them and perhaps use fewer symbols. For motivation, you might say "We are going to pick a proper subset $S$ of $T$, multiply the terms in $S$ together, and try to get this product to be as small a multiple of $\binom{x+n}{n}$ as we can. The inequality and the assumption that no large primes larger than $n$ divide the left hand side show that $S$ need no more than $\pi(n)$ many members."

You introduce $U'$ and $V$, and then in later statements ((5) through (8)) make some claims which are a little confusing. In (5) you mention that x might increase, but it is not clear why. (I understand you want to prove a contradiction for large x, but this is not the way to make it clear.) Also your assertion of what is clearly impossible is wrong. V can change if U' changes as long as the product U'V stays constant.

You have bounds on $V$ in (6) which may be useful, but I do not see how. The second (7) and (8) are an attempt at finishing the proof but are not clear nor convincing. Let me suggest what you could do.

Once you pick $S$ and create the product you call $UU'$ and which I will call $P$ you have $n!U=PV$. A clean observation to make here is that since $U|P$, then $V|n!$. From this you can write an expression that says your assumption that $U$ has no big prime factors, means $V \leq n!$ and that $x$ is less than a fractional power of $n$ and so less than $(n^2)/4$ (once $\pi(n) \leq n/2$).

End Edit 2018.05.18

Gerhard "Is His Own Strongest Critic" Paseman, 2018.05.17.

$\endgroup$
2
  • 1
    $\begingroup$ Gerhard, it is ego deflating to work on number theory. I appreciate your comments. My inequality $\pi(n) \le \frac{n}{2}$ is called out in step #8. I didn’t think a proof necessary since this result is so well known and so weak relative other well-known results. I will follow the pointers you call out to find the mistake. Gerry’s observation really helps. $\endgroup$ May 17 '18 at 16:34
  • $\begingroup$ Gerhard, Thanks very much for your comments! I will work to improve my argument on mse to address your observations. $\endgroup$ May 18 '18 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.