62
$\begingroup$

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

Improve this question
$\endgroup$
11
  • 15
    $\begingroup$ This is equivalent to say that among two numbers having the same radical, there is at least one prime number. $\endgroup$
    – Konstantinos Gaitanas
    Commented Nov 26, 2017 at 15:45
  • 4
    $\begingroup$ 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. $\endgroup$
    – Stanley Yao Xiao
    Commented Nov 26, 2017 at 15:51
  • 15
    $\begingroup$ 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. $\endgroup$
    – fedja
    Commented Nov 26, 2017 at 16:28
  • 2
    $\begingroup$ 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? $\endgroup$
    – Yaakov Baruch
    Commented Nov 26, 2017 at 16:52
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yaakov Baruch
    Commented Nov 26, 2017 at 17:46

2 Answers 2

Reset to default
44
$\begingroup$

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.

Improve this answer
$\endgroup$
10
  • 2
    $\begingroup$ 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) $\endgroup$
    – Lucia
    Commented Nov 26, 2017 at 17:58
  • 5
    $\begingroup$ 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! $\endgroup$
    – BR Pahari
    Commented Nov 26, 2017 at 23:24
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Yaakov Baruch
    Commented Nov 27, 2017 at 13:18
  • 7
    $\begingroup$ 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. $\endgroup$
    – Pasten
    Commented Nov 27, 2017 at 18:00
  • 1
    $\begingroup$ @BasantaR.Pahari I think your formulation is very elegant and it makes the problem look more natural. $\endgroup$
    – Pasten
    Commented Nov 28, 2017 at 0:12
9
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Gerhard Paseman
    Commented Nov 26, 2017 at 23:54

You must log in to answer this question.

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