Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The Real Conjecture

  1. Dec 4, 2007 #1
    Now that we've all warmed up a bit...

    Let's try this little gem of a conjecture...

    Instead of 2^x - 3^y or 3^y - 2^x, which together can be represented as
    abs( 2^x - 3^y ) since all we care about are the positive solutions, where
    abs( ) is absolute value,

    instead of that, let's try the following...

    set p(n) to be the nth prime
    separate all of the primes from 2 to p(n) (inclusive) into two disjoint sets, A* and B*
    Take all of the primes in A*, exponentiate them at will with positive integer exponents, and
    multiply the resulting numbers together to get a number called A.
    Do the same with B* to get B.

    So far, an example might be...
    A = 2^6 * 7^9 * 11^3
    B = 3^1 * 5^12

    where p(n) = 11

    Proven result: If q = abs( A +/- B ), where +/- means "plus or minus", AND q < [ p(n+1) ]^2, then q is either prime or the number 1.

    in the example, if abs( 2^5 * 7^9 * 11^14 +/- 3^1 * 5^7 ) were less than 169, then it would be 1 or prime.

    Unproven conjecture: If q is prime, then q = abs( A +/- B ) as constructed above, where the largest prime factor in AB is also the largest prime less than the square root of q.

    So far this works for in fact all primes up to 1369 = 37^2 (I stopped past 1000 because I was doing it by hand, and 31^2 = 961 didn't make it to 1000 so I kept going).

    Note that the "plus" in the +/- becomes useless, and unnecessary, after p(n) = 11.

    I was on a couple of chat rooms some years ago about this, so you may have seen it before, but some of you seem to have some new approaches, so I'm curious what you think?

    Here's an example, where I let all the exponents remain fixed except the exponent on 2.

    abs( 45 +/- 2^x ) < 49
    this gets alot of the primes under 49. To get more, try other exponents:
    abs( 15 +/- 2^x ) < 49
    or repartition the primes in A* and B*
    abs( 10 +/- 3^x )
    abs( 20 +/- 3^x )
    abs( 40 +/- 3^x )
    abs( 50 +/- 3^x )
    abs( 80 +/- 3^x )
    abs( 100 +/- 3^x )
    abs( 6 +/- 5^x )
    abs( 12 +/- 5^x )
    abs( 18 +/- 5^x )
    abs( 24 +/- 5^x )
    abs( 36 +/- 5^x )
    etc.
    Now try abs( 105 +/- 2^x ) < 121
    etc.
    you only need a few partitions, though, and fairly low exponents, as far as I've seen, to get all the primes less than the square of the next prime.

    Thanks again for all your ideas.

    approx
     
    Last edited: Dec 4, 2007
  2. jcsd
  3. Dec 4, 2007 #2
    I think this problem is much harder than the one we did in the other thread, and cannot be approached via the same techniques. I will think about it more later.
     
  4. Dec 4, 2007 #3

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    I don't understand the conjecture. Is this what you mean, or do you mean something else?

    Conjecture 1: If q = A + B is prime, the largest prime factor in AB is also the largest prime less than the square root of q.
    Conjecture 2: If q = abs(A - B) is prime, the largest prime factor in AB is also the largest prime less than the square root of q.

    where A and B are as in your post.

    If so, it can be simplified to
    Conjecture: If q = A - B is prime, the largest prime factor in AB is also the largest prime less than the square root of q, where A and B are as in your post.

    since small numbers can be checked (so A + B isn't needed) and A can be taken to be the larger without loss of generality.
     
  5. Dec 4, 2007 #4
    I thought the OP meant that every prime less than [tex]p^2[/tex] can be made as a difference between elements in sets A and B, where A is the set of products of powers of some of the primes up to p and B is the set of products of powers of the rest of the primes up to p (that weren't used in A).
     
  6. Dec 4, 2007 #5
    yes

    EDIT: not exactly, see explanation later. Ignore the rest of this post. you are both correct, although I should say that small numbers are the ONLY ones where the plus is used, so to use your simplification, you should check numbers greater than 121.
    IOW:

    A-B, where gcd(A,B)=1, where p(1)*p(2)*...*p(n) divides A*B and where p(k) doesn't divide A*B when k>n

    OR

    [p(1)]^a1 * [p(2)]^a2 *... * [p(n)]^an - [p(1)]^b1 * [p(2)]^b2 *... * [p(n)]^bn
    where aj*bj=0 for all j and where aj+bj>0 for all j
    this guarantees the exponent on, for example, 3 is zero on one side only

    all just different ways to say the same think... take your pick
     
    Last edited: Dec 5, 2007
  7. Dec 4, 2007 #6

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Conjecture: If
    • p# | AB for some prime p
    • AB | (p#)^k for some k
    • gcd(A, B) = 1, and
    • A - B is prime
    then p is the largest prime less than the square root of A - B.

    Case: p = 2
    B = 1, A = 2^k for some k in {2, 3, 5, 7, 13, 17, 19, ...} (A000043).
    Conjecture fails for k > 4.

    Case: p = 3, B = 1
    A = 2^a * 3^b for some a, b > 0.
    Conjecture fails for A in {27, 32, 36, 48, 54, 64, 72, ...} (A003586)

    Case: p = 3, A = 2^a, B = 3^b
    Fails for
    2^4 - 3^1 = 13
    2^5 - 3^0 = 31
    2^5 - 3^1 = 29
    2^5 - 3^2 = 23
    2^6 - 3^1 = 61
    2^6 - 3^3 = 37
    2^7 - 3^0 = 127
    2^7 - 3^3 = 101
    2^7 - 3^4 = 47
    2^8 - 3^3 = 229
    2^8 - 3^5 = 13
    2^9 - 3^1 = 509
    2^9 - 3^2 = 503
    2^9 - 3^4 = 431
    2^9 - 3^5 = 269
    2^10 - 3^1 = 1021
    2^10 - 3^3 = 997
    2^11 - 3^2 = 2039
    2^11 - 3^6 = 1319
    2^12 - 3^1 = 4093
    2^12 - 3^5 = 3853
    2^13 - 3^0 = 8191
    2^13 - 3^4 = 8111
    2^13 - 3^5 = 7949
    2^14 - 3^1 = 16381
    2^14 - 3^5 = 16141
    2^14 - 3^7 = 14197
    2^15 - 3^4 = 32687
    2^16 - 3^5 = 65293
    2^16 - 3^9 = 45853
    2^17 - 3^0 = 131071
    2^17 - 3^2 = 131063
    2^17 - 3^5 = 130829
    2^17 - 3^6 = 130343
    2^19 - 3^0 = 524287
    2^19 - 3^3 = 524261
    2^19 - 3^11 = 347141
    2^20 - 3^1 = 1048573
    2^20 - 3^3 = 1048549
    2^20 - 3^7 = 1046389
    2^20 - 3^9 = 1028893
    2^21 - 3^2 = 2097143
    2^21 - 3^5 = 2096909
    2^21 - 3^10 = 2038103
    2^21 - 3^13 = 502829
    2^22 - 3^1 = 4194301
    2^22 - 3^3 = 4194277
    2^22 - 3^13 = 2599981
    2^23 - 3^3 = 8388581
    2^23 - 3^6 = 8387879
    2^23 - 3^11 = 8211461
    2^24 - 3^1 = 16777213
    2^24 - 3^5 = 16776973
    2^24 - 3^11 = 16600069
    2^26 - 3^3 = 67108837
    2^27 - 3^14 = 129434759
    2^29 - 3^1 = 536870909
    2^29 - 3^14 = 532087943
    2^30 - 3^17 = 944601661
    2^31 - 3^0 = 2147483647
    2^32 - 3^13 = 4293372973
    2^33 - 3^2 = 8589934583
    2^33 - 3^16 = 8546887871
    2^33 - 3^17 = 8460794429
    2^34 - 3^17 = 17050729021
    2^34 - 3^19 = 16017607717
    2^35 - 3^8 = 34359731807
    2^35 - 3^12 = 34359206927
    2^35 - 3^19 = 33197476901
    2^36 - 3^5 = 68719476493
    2^36 - 3^13 = 68717882413
    2^37 - 3^9 = 137438933789
    2^37 - 3^16 = 137395906751
    2^39 - 3^14 = 549751030919
    2^40 - 3^9 = 1099511608093
    2^40 - 3^17 = 1099382487613
    2^41 - 3^13 = 2199021661229
    2^41 - 3^20 = 2195536471151
    2^42 - 3^13 = 4398044916781
    2^42 - 3^23 = 4303903332277
    2^42 - 3^25 = 3550757901661
    2^45 - 3^4 = 35184372088751
    2^45 - 3^8 = 35184372082271
    2^45 - 3^17 = 35184242948669
    2^45 - 3^26 = 32642506260503
    2^46 - 3^11 = 70368744000517
    2^46 - 3^15 = 70368729828757
    2^46 - 3^19 = 70367581916197
    2^46 - 3^21 = 70358283824461
    2^47 - 3^7 = 140737488353141
    2^47 - 3^11 = 140737488178181
    2^47 - 3^26 = 138195622526999
    2^48 - 3^5 = 281474976710413
    2^48 - 3^25 = 280627688101213
    2^49 - 3^4 = 562949953421231
    2^49 - 3^12 = 562949952889871
    2^49 - 3^16 = 562949910374591
    2^49 - 3^22 = 562918572361703
    2^49 - 3^25 = 562102664811869
    2^50 - 3^3 = 1125899906842597
    2^50 - 3^7 = 1125899906840437
    2^50 - 3^11 = 1125899906665477
    2^50 - 3^19 = 1125898744581157
    2^51 - 3^14 = 2251799808902279
    2^51 - 3^22 = 2251768432625639
    2^51 - 3^28 = 2228923021230287
    2^51 - 3^31 = 1634126417401301
    2^55 - 3^19 = 36028795856702501
    2^56 - 3^3 = 72057594037927909
    2^57 - 3^8 = 144115188075849311
    2^57 - 3^13 = 144115188074261549
    2^57 - 3^22 = 144115156694796263
    2^57 - 3^29 = 144046557698490989
     
  8. Dec 4, 2007 #7
    You said:
    Conjecture: If
    p# | AB for some prime p
    AB | (p#)^k for some k
    gcd(A, B) = 1, and
    A - B is prime
    then p is the largest prime less than the square root of A - B.

    Is this your conjecture, or what you think mine is?
    All I'm saying is that
    the group of ALL PRIMES, FROM p(n+1) TO p(n+1)^2, can be generated using A-B,
    where all of the primes from 2 to p(n) are in either A or B (that's p#dividesAB)
    and no larger prime is a factor of either A or B (that's p(k) doesn't divide AB for k>n)
    and p(i) is only in A or B, not both (that's gcd(A,B)=1)

    IOW, use ALL primes from 2 to p(n), some on each side of the +/-, making sure none are on both sides, exponentiate at will with positive integers, THEN
    you can produce all primes from p(n+1) to p(n+1)^2.

    abs(15 +/- 2^x) gives 17,19,23,31,47 with the plus and
    13,11,7,1,17,
    abs(45 +/- 2^x) gives 47 and 43,41,37,29,13,19
     
    Last edited: Dec 5, 2007
  9. Dec 4, 2007 #8
    remember, ALL primes from 2 to p(n) must be used, and the exponents are POSITIVE integers, not zero

    Also remember, we are only finding primes up to p(n+1)^2, so if we have 3^b * 5^c +/- 2^a, it is only good for primes LESS THAN 49!!!!!!

    3^b - 2^a is only good for primes LESS THAN 25!!!!!
     
    Last edited: Dec 4, 2007
  10. Dec 5, 2007 #9
    ok, now I get the confusion! The bit about the square root -- that just means that if your "target prime" is 47 then its square root is less than seven so you only need to use 2, 3, and 5 in A and B. if your target prime is, for example, 83 then its square root is less than 11 so you only need to use 2, 3, 5, and 7, seven being the maximum prime less than its square root. IOW, this isn't the conjecture but one of the conditions. Please reread it keeping that in mind.
     
    Last edited: Dec 5, 2007
  11. Dec 5, 2007 #10

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    That's what I said: "p# | AB for some prime p". p# is the primorial, that is 2 * 3 * 5 * ... * p. The special cases I showed above deal with p = 2 or p = 3 so there are only one or two primes to consider. (It's often easiest to deal with the smallest special cases first.)
     
  12. Dec 5, 2007 #11

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Can you rewrite the conjecture? The original statement is very hard to make sense of, even with your clarification: "If q is prime, then q = abs( A +/- B ) as constructed above, where the largest prime factor in AB is also the largest prime less than the square root of q."

    Maybe just break it down into the things that are assumed and the things that are conjectured to follow? Anything you can do to make it stand alone (i.e. no "as constructed above") would help.
     
  13. Dec 6, 2007 #12
    ok

    This first part is not a conjecture but rather something easily proven.

    If we construct A and B so that their prime factorization includes all of the primes up to p(n) only AND each prime is in A or B but not both AND their difference is less than [p(n+1)]^2 THEN that difference will be either prime or 1.

    This second part is the conjecture.

    If p is a prime, and p(n) is the last prime before the square root of p, then we can construct A and B so that their prime factorization includes all of the primes up to p(n) only AND each prime is in A or B but not both AND their difference will be p.

    In other words, the first part asserts that such an A-B will always produce a noncomposite if it passes the less-than test, and the second part conjectures that FOR EACH PRIME SUCH AN A AND B CAN BE FOUND. The first part only claims some primes will be found, though each output will be prime, or 1.
     
    Last edited: Dec 6, 2007
  14. Dec 6, 2007 #13
    examples

    for primes from 5 to 25, use factors of 2 and 3 in A and B

    27-16=11
    16-3=13
    81-64=17
    27-8=19
    27-4=23

    for primes less than 49 use factors of 2, 3, and 5

    45-16=29
    81-50=31
    45-8=37
    45-4=41
    45-2=43
    50-3=47

    for primes less than 121 use factors 2, 3, 5, and 7

    60-7=53
    80-21=59
    70-9=61
    70-3=67
    120-49=71
    105-32=73
    100-21=79
    90-7=83
    105-16=89
    105-8=97
    105-4=101
    105-2=103
    350-243=107
    189-80=109
    120-7=113

    if you allow the use of 1 and a factor of 2, for primes less than 9 you can get:

    4-1=3
    4+1=5
    8-1=7

    The question that my conjecture is about is whether or not there is any prime which can't be generated this way.
     
  15. Dec 6, 2007 #14
    answer to your question

    Ok, now that I have a few minutes to concentrate, I'll try to answer your question clearly...

    Let p be any given prime.
    Let 2, 3, 5, ... p(n) be all of the primes less than square root of p.
    Then my conjecture is that you CAN CONSTRUCT A and B WITH p=A-B such that:
    CONDITIONS:
    (1.)Each p(i) from 2 to p(n) inclusive is a factor of either A or B but not both.
    (2.)Each such p(i) has an integer exponent > 0.
    (3.)No prime larger than p(n) is a factor of either A or B

    The other part, which is not a conjecture but is easy to prove is kind of like reversing
    the conditions with the result,

    Choose a p(n) and construct A and B as in (1.), (2.), and (3.) above. Then A-B will be SOME prime (or the number 1) IF
    (condition): A-B < [p(n+1)]^2

    Note that this part I've proven doesn't say all primes are constructed this way, only that this construction will always produce a prime, or 1, when it satisfies the less-than condition. The conjecture says that EVERY prime can be found this way.
     
    Last edited: Dec 6, 2007
  16. Dec 6, 2007 #15
    Here's a simpler and more formal statement of your conjecture.

    approx's Prime Difference Conjecture

    Suppose that [tex]p_k[/tex] is the [tex]k^{th}[/tex] prime, and [tex]k \ge 3[/tex]. Then for each prime [tex]q[/tex] with [tex]p_{k-1}^2 < q < p_k^2[/tex] there exist positive integers [tex]m, n[/tex] such that

    (1) [tex]q = m - n[/tex]

    (2) If [tex]j < k[/tex] then [tex]p_j \mid m[/tex] or [tex]p_j \mid n[/tex].
     
  17. Dec 6, 2007 #16
    and

    Yes, exactly, and (3) if r>k or r=k then p(r) doesn't divide m and p(r) doesn't divide n.
     
    Last edited: Dec 6, 2007
  18. Dec 7, 2007 #17
    OK I think we can show the conjecture is true for sufficiently big [tex]k[/tex] by the following ideas:

    (1) There exists a primitive root mod [tex]n[/tex] which is smaller than [tex]cn^{1/4}[/tex] for some absolute constant [tex]c[/tex] when [tex]n[/tex] is sufficiently large.

    (2) Observe that we can make any number between 2 and [tex]p_k > q^{1/2}[/tex] as a product of some primes no bigger than [tex]p_{k-1}[/tex].

    So if we believe (1) (I don't have a reference but I think something like this is true), we can construct a primitive root mod [tex]q[/tex] which is a product of some of the primes up to [tex]p_{k-1}[/tex]. Call this number [tex]r[/tex]. Now we use a combinatorial argument to show that we can find another number [tex]s[/tex] which is a product of the other primes smaller than [tex]p_k[/tex] with [tex]s - r^n = q[/tex].

    ... okay I am stuck here, at least for now. It seems that [tex]r^n[/tex] grows too quickly for my crude way of counting the possibilities for [tex]s[/tex]. If anyone has any suggestions I'd be delighted to hear them. I'll continue to work on this later, but I'll have much more time during winter break so don't too expect much from me for another week and a half...
     
  19. Dec 7, 2007 #18
    Reasons to expect the conjecture to be true: If you recall, the earlier conjecture about powers of 2 and 3 was false because if you looked mod certain big numbers, the powers of 2 and 3 didn't hit that many residues, so differences of them didn't hit all residues. But since we now get to use all primes up to [tex]p_{k-1}[/tex], there are way more possible residues, so it's likely that the same argument would require us to find a VERY large number before we couldn't hit all residues. But then the first example would be much bigger than [tex]p_k^2[/tex] and would therefore be irrelevant anyway.

    Also, there was the intuitive issue that powers of 2 and 3 don't seem to be very close together when the powers are big. But now, again, we have many more possible combinations without making the powers too big, so we have more "small" numbers available.

    These reasons suggest that we should be able to prove the conjecture using some kind of combinatorial argument.


    Reasons to think the conjecture is false: To me, the main problem is that when k is big, since we must use all of the [tex]p_j, j < k[/tex] as factors of m or n, both m and n will have to be much bigger than q. This makes me suspect that even though you get many more possible combinations when k is big, the products will be so huge that the number of small differences will still be small.

    My friend also pointed out that if q-1 is divisible by many small primes, then it may be hard to find appropriate m and n. This is because if [tex]p_j \mid n[/tex] then [tex]p_j \mid m-1[/tex] and if [tex]p_j \mid m[/tex] then [tex]p_j \mid n+1[/tex] (except maybe for 3, and its trivial for 2). This turned out not to be a serious problem for 71 = 120 - 49; observe that 49+1 = 50 = 5 * 10 and 120 - 1 = 119 = 7 * 17. But it may make things difficult for larger primes.



    In summary, could someone with programming ability please try to produce m and n for the following primes?
    173
    331
    509
    2311

    Seeing those decompositions might help a lot with getting some intuition about what's actually going on.
     
  20. Dec 7, 2007 #19

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Oof. That's not an easy task.

    173 = 693 - 520
    331 = 2431 - 2100
    509 = 51714 - 51205
     
  21. Dec 7, 2007 #20

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    The code I'm using is very efficient for small numbers, less so for large. (I mean that there are obvious, if not so easily implemented, methods that would be much slower for n < 200 but faster for large n.)

    Actually in that range there are some significantly harder problems than the ones you asked. 431 in particular was tough to make work. I haven't been able to find solutions for 397, 419, 433, or 487; I've searched up to a billion on each.

    Of course 2311 is super-hard because it's very large -- just finding N and M with 47#|NM is hard enough. I'm going to have to write a whole new program and throw a lot of cycles at it if I'm to have any chance to solving it. Of course I don't know that it's solvable.

    Code (Text):
    127 = 490 - 363
    131 = 231 - 100
    137 = 165 - 28
    139 = 154 - 15
    149 = 275 - 126
    151 = 165 - 14
    157 = 220 - 63
    163 = 198 - 35
    167 = 1575 - 1408
    173 = 693 - 520
    179 = 1089 - 910
    181 = 286 - 105
    191 = 455 - 264
    193 = 1183 - 990
    197 = 1352 - 1155
    199 = 364 - 165
    211 = 715 - 504
    223 = 1848 - 1625
    227 = 3087 - 2860
    229 = 385 - 156
    233 = 728 - 495
    239 = 330 - 91
    241 = 780 - 539
    251 = 1001 - 750
    257 = 455 - 198
    263 = 770 - 507
    269 = 819 - 550
    271 = 546 - 275
    277 = 420 - 143
    281 = 1001 - 720
    283 = 1053 - 770
    293 = 2295 - 2002
    307 = 2925 - 2618
    311 = 20111 - 19800
    313 = 18513 - 18200
    317 = 11900 - 11583
    331 = 2431 - 2100
    337 = 1724800 - 1724463
    347 = 7497 - 7150
    349 = 910 - 561
    353 = 3213 - 2860
    359 = 1430 - 1071
    367 = 7150 - 6783
    373 = 88825 - 88452
    379 = 35700 - 35321
    383 = 53865 - 53482
    389 = 3315 - 2926
    **397
    401 = 247401 - 247000
    409 = 122265 - 121856
    **419
    421 = 4620 - 4199
    431 = 14189175 - 14188744
    **433
    439 = 44044 - 43605
    443 = 77520 - 77077
    449 = 230945 - 230496
    457 = 372400 - 371943
    461 = 4641 - 4180
    463 = 452200 - 451737
    467 = 65637 - 65170
    479 = 25350 - 24871
    **487
    491 = 270215 - 269724
    499 = 206250 - 205751
    503 = 25935 - 25432
    509 = 51714 - 51205
    I'm beginning to seriously doubt this conjecture. Finding small solutions is easy, but large ones depend on finding smooth numbers in short intervals. A generalization of Sto/rmer's theorem could disprove this conjecture -- although I'm not seen any work in that direction.
     
    Last edited: Dec 7, 2007
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: The Real Conjecture
  1. Poincare conjecture? (Replies: 2)

  2. The Hodge Conjecture (Replies: 16)

  3. Poincare conjecture (Replies: 5)

  4. A conjecture (Replies: 9)

Loading...