59

For $n,m \geq 3$, define $ P_n = \{ p : p$ is a prime such that $ p\leq n$ and $ p \nmid n \}$ .

For example : $P_3= \{ 2 \}$ $P_4= \{ 3 \}$ $P_5= \{ 2, 3 \}$, $P_6= \{ 5 \}$ and so on.

Claim: $P_n \neq P_m$ for $m\neq n$.

While working on prime numbers I formulated this problem and it has eluded me for a while so I decided to post it here. I am not sure if this is an open problem or solved one. I couldn't find anything that looks like it. My attempts haven't come to fruition though I have been trying to prove it for a while. If $m$ and $n$ are different primes then it's clear. If $m \geq 2n$, I think we can find a prime in between so that case is also taken care of. My opinion is that it eventually boils down to proving this statement for integers that share the same prime factors. My coding is kind of rusty so would appreciate anybody checking if there is a counterexample to this claim. Any ideas if this might be true or false? Thanks.

PS: I asked this question on mathstackexchage and somebody recommended I post it here as well. Here is the link to the original post

https://math.stackexchange.com/questions/2536176/a-conjecture-regarding-prime-numbers

BR Pahari
  • 623
  • 13
    This is equivalent to say that among two numbers having the same radical, there is at least one prime number. – Konstantinos Gaitanas Nov 26 '17 at 15:45
  • 4
    This does not seem terribly easy... in fact, I don't have a good intuition as to whether it should be true or not. Let $S = {p_1, \cdots, p_k}$. The question can be thought of whether there exist two $S$-units $m, n$, say $N < m < n \leq 2N$, such that $|n - m| \ll \log N$ say. If the answer is yes, then one would expect that there are no primes between $m$ and $n$ typically, so the conjecture would be false. – Stanley Yao Xiao Nov 26 '17 at 15:51
  • 14
    If you just consider $n^2(n+1)$ and $n(n+1)^2$, then this would imply that there always is a prime between $n^3$ and $(n+1)^3$. That is known, but highly non-trivial. However, those two are just the simplest products with guaranteed same radical that jump to one's mind. Whether a more clever construction would allow one to deduce something that we certainly do not know today remains to be seen. – fedja Nov 26 '17 at 16:28
  • 2
    Maybe then an easier and more interesting question would be to prove some bound function $b(m)$ on $n-m$ if $m<n$ have the same radical? – Yaakov Baruch Nov 26 '17 at 16:52
  • It's a close miss between 48 and 54... – Yaakov Baruch Nov 26 '17 at 17:07
  • @Yaakov Baruch: Wouldn't $(P_{-}(m)-1)m$ with $P_{-}(m)$ the smallest prime factor of $m$ be a rather obvious lower bound? – Sylvain JULIEN Nov 26 '17 at 17:12
  • @SylvainJULIEN: the radical of $m$ would be an even larger lower bound. I didn't put well, but what I had in mind was some simple well behaved monotonic function (like, say, $\log(m)^2) that is a lower bound and gets "very close" to being optimal infinitely often. – Yaakov Baruch Nov 26 '17 at 17:27
  • It feels like the $abc$ conjecture would have something to say on the how close numbers with the same radical can be. – Yaakov Baruch Nov 26 '17 at 17:30
  • I'm sorry but I don't see how the radical of an integer could be anyhow greater than the integer itself, let alone this integer times another positive integer. But I may have misunderstood what you meant. – Sylvain JULIEN Nov 26 '17 at 17:40
  • 1
    Say, based on the highest quality $abc$ triple known to date, you have that $48407720661$ and $48407720661+15042$ have the same radical. Now even such a small number as $15042$ is so much larger than $\log(48407720661)$ that the chance of not there being primes in that interval is practically nil. So my expectation is that the OP conjecture is true, but this reasoning clearly needs work to be made into a clean euristic argument. – Yaakov Baruch Nov 26 '17 at 17:46
  • Well - Lucia did the work! – Yaakov Baruch Nov 26 '17 at 17:49

2 Answers2

42

This is true (for large $m$ and $n$) under ABC plus the assumption that there is a prime in $[x,x+x^{1/2-\delta}]$ for some positive $\delta$ (which is widely believed, but beyond RH). To see this, suppose $m <n$ and that they have the same radical $r$. Write $m=gM$ and $n=gN$ where $g$ is the gcd of $m$ and $n$, so that $M$ and $N$ are coprime. Applying the ABC conjecture to $M + (N-M) = N$, we conclude that $$ (N-M) r \ge N^{1-\epsilon}, $$ so that $$ n-m \ge n^{1-\epsilon}/r. $$ On the other hand, clearly $n-m$ is also $\ge r$ (since it is divisible by $r$). It follows that $n-m \ge n^{1/2-\epsilon}$, and the assumption that there are primes in short intervals finishes the (conditional) proof.

The problem is likely very hard, as fedja's observation in the comments already shows. There is a conjecture of Hall that $|x^3-y^2| \gg x^{1/2-\epsilon}$ which is wide open. The best results that are known here (going back to Baker's method) are of the flavor $|x^3-y^2| \gg (\log x)^C$ for some $C$. If $x^3-y^2$ does get as small as in the Baker result, then take $n=x^4y$ and $m=xy^3$, which clearly have the same radical and then $|n-m|$ is of size essentially $n^{5/11}$. In other words, either you have to improve work towards Hall's conjecture, or work towards gaps between primes!

Added Thanks to Pasten's comment, I learned that this problem is already in the literature and is known as Dressler's conjecture. The conditional proof above is recorded in work of Cochrane and Dressler who give more information on the conjecture.

Lucia
  • 43,311
  • I think we need a tiny bit more than this. Assume that $m<n$, and they don't have the same radical. Then there is a prime $p$ such that either $p\mid m$ and $p\nmid n$, or $p\nmid m$ and $p\mid n$. In the first case it is automatic that $p\in P_n-P_m$. In the second case we need the extra condition that $p\leq m$ to conclude that $p\in P_m-P_n$. Am I missing something? – GH from MO Nov 26 '17 at 17:53
  • 2
    If $n$ is divisible by a prime larger then $m$, then won't $n$ have to be that prime? (or one would have $n\ge 2m$ and then it should be obvious) – Lucia Nov 26 '17 at 17:58
  • I agree. In the second case either $p\leq m$ in which case we are done, or by Bertrand's postulate we get easily that $n=p$ is prime, and then taking any prime divisor $q\mid m$ leads us back to the first case. Nice (conditional) proof! – GH from MO Nov 26 '17 at 18:09
  • 5
    Nice! I am surprised that it is beyond the reach of RH. But that explains why my elementary approach (since I don't have any analytic number theory background ) weren't getting me anywhere. Regardless, it's really satisfying to see that the claim is actually true assuming the conjectures you mentioned. Great work! – BR Pahari Nov 26 '17 at 23:24
  • 1
    There is a simple sequence where $n−m<(\frac{3}{4}n)^{1/2}$: $n=\frac{3}{4}9^k(9^k−1)$ and $m=\frac{3}{4}(9^k−1)^2$. – Yaakov Baruch Nov 27 '17 at 13:18
  • @YaakovBaruch: Nice example! – Lucia Nov 27 '17 at 14:40
  • 7
    cf. Dressler's conjecture. Often misquoted as a consequence of abc, while in fact it is a well-known consequence of abc and existence of primes in short intervals. – Pasten Nov 27 '17 at 18:00
  • @Pasten: Ah, good to know that the conjecture is already in the literature. The observation I made above (on abc + gaps between primes) seems to have been recorded by Cochrane and Dressler (in Math. Comp.). – Lucia Nov 27 '17 at 18:10
  • @Pasten Thanks for pointing out that the conjecture is well-known . My formulation looks different but no doubt is equivalent to Dressler's conjecture. I think the way I wrote the problem in terms of sets made it difficult to find references or literature already published pertaining to the problem. – BR Pahari Nov 27 '17 at 21:27
  • 1
    @BasantaR.Pahari I think your formulation is very elegant and it makes the problem look more natural. – Pasten Nov 28 '17 at 00:12
9

I am working on a related project involving Grimm's conjecture. The hope is to show that every interval of consecutive composite numbers below $10^{12}$ contains an injective divisor map, see On comparing two almost injective divisor maps for more detail. The upshot is that there are about 700 opportunities for your event to happen (because the map $L(m)$ being largest prime factor of m is often injective, and in your case it won't be) below 2.5 times $10^{10}$, and that your event won't happen because the numbers involved are too close. (Specifically, $L(m)=L(n)=p$, and $m-n =kp$ where $L(k)$ is less than $p$ and usually less than 3, and in those cases $m/p$ and $n/p$ have sufficiently different sets of prime factors.). If I can achieve my aims while offloading data regarding your claim (e.g. a data file of the estimated 3000 $L$ pairs below $10^{12}$), I will do so and report back. If you have several months of computer cycles to spare, I can provide a program so that you can join in the fun, AND get some data on your problem.

Gerhard "Another Opportunity For Communal Computing" Paseman, 2017.11.26.

Glorfindel
  • 2,743
Gerhard Paseman
  • 12,968
  • I think it should be the case (that there is an elementary proof) that for fixed j, there are only finitely many cases where your conjecture fails with all primes involved less than j. You might even be able to give an explicit bound. If I get any more along this line I will also report it. Gerhard "Maybe Only Finitely Many J?" Paseman, 2017.11.26. – Gerhard Paseman Nov 26 '17 at 23:54