mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > carpetpool

Reply
 
Thread Tools
Old 2020-02-13, 01:37   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

2×3×43 Posts
Post Agrawal's conjecture revisited

While the AKS test was published almost decades ago, I was wondering if Agrawal's conjecture might be true if some variant or other condition is added to it?

Here is what I have figured out so far, but I'm stuck on a few proofs.

Does anyone got any further ideas?

Last fiddled with by carpetpool on 2020-02-13 at 01:41 Reason: Changed link
carpetpool is offline   Reply With Quote
Old 2020-02-13, 05:08   #2
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

2·3·43 Posts
Post

Quote:
Originally Posted by carpetpool View Post
While the AKS test was published almost decades ago, I was wondering if Agrawal's conjecture might be true if some variant or other condition is added to it?

Here is what I have figured out so far, but I'm stuck on a few proofs.

Does anyone got any further ideas?
Pdf had multiple format/syntax errors and I've attempted to fix them;

Try this link.
carpetpool is offline   Reply With Quote
Old 2020-02-13, 15:17   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

5×557 Posts
Default

Remarks on Agrawal's Conjecture indicates the conjecture is likely false.
Dr Sardonicus is online now   Reply With Quote
Old 2020-02-13, 22:33   #4
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

1000000102 Posts
Post

Quote:
Originally Posted by Dr Sardonicus View Post
Remarks on Agrawal's Conjecture indicates the conjecture is likely false.
Yes, it should be false in general (Roman B. Popovych's conjecture could be true however).

Assuming the falsehood of the original conjecture, what I was trying to illustrate is that counterexamples should have very specific properties, namely that the only counterexamples (with r prime) should be Carmichael numbers of order(m) where m = (r-1)/2. There is no proof (that I know of), but there is evidence that this should be true.

There should also exist upper bounds on either the Carmichael numbers of order(m) < x (and show that it is 0 for some x), or there is a lower bound such that the smallest Carmichael numbers of order(m) > L.

If these two arguments are true, then there should exist a modified version of the conjecture that is true as we will have conditions for which n must be prime.

Last fiddled with by carpetpool on 2020-02-13 at 22:33
carpetpool is offline   Reply With Quote
Old 2020-02-13, 23:18   #5
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

10216 Posts
Post

[1]
n is a primitive root mod r, and Agrawal's conjecture holds for (n, r), then n is either prime, or a Carmichael number of order (r-1)/2.

[2]
There exist a lower bound such that the smallest Carmichael number of order(m) > Lm.

If these two arguments are true, then there should exist a modified version of the conjecture that is true as we will have necessary and sufficient conditions for which n must be prime.

Assuming the truth of these two arguments, and more specifically, the assumption that the lower bound L (as defined above), exists:

[3]

Find a prime r which n is a primitive root (mod r). Then check that

(x - 1)^n = x^n - 1 mod (n, x^r - 1), n < Lm, and (r - 1) > 2*m.

If so, then n is (or should be) prime.

The problem with this test (apart from the unproven assumptions) is that r may be significantly large (for instance, if L = log^2(n) by the GRH). This would make this test (if true) impractical for large numbers. In particular, the complexity is dependent on the size of r.

As pointed out earlier, for any individual prime q, n will be a prime or Carmichael number of order (q-1)/2 if n is a primitive root mod q (condition [1]).

Now for q2, check that the conditions outlined in [1] are true. If so, n must also be (prime) or Carmichael number of order (q2-1)/2. Assume n is not prime. This implies that n is a Carmichael number of order

lcm((q-1)/2, (q2-1)/2) which is equivalent to λ(r)/4 where λ(r) is the Carmichael function of r.

We can r by the conditions outlined in [3] as long as λ(r) > 4*m. However, this would be more practical as we will only have two to run [3] with two smaller primes q and q2 versus r, and this could decrease the complexity (and running time) drastically.

What about r's with more factors? It is feasible to find a set of small primes [q, q2, q3,... qi] for which n is a primitive root mod every prime in the set. Then r is their product and as long as λ(r) > 2^i*m, tests in [3] can be applied to n.

m is defined in [2] to be the smallest integer such that there is no Carmichael number of order m ≤ n.

While I had a hard time attempting to put this all together it appears to be worthwhile to investigate the truth of [1] and [2] if not [3], at the very least. If you have any remarks, or (want) clarification, please let me know.

Last fiddled with by carpetpool on 2020-02-13 at 23:19
carpetpool is offline   Reply With Quote
Old 2020-02-15, 20:06   #6
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

2×3×43 Posts
Post

Quote:
Originally Posted by carpetpool View Post
Yes, it should be false in general (Roman B. Popovych's conjecture could be true however).

Assuming the falsehood of the original conjecture, what I was trying to illustrate is that counterexamples should have very specific properties, namely that the only counterexamples (with r prime) should be Carmichael numbers of order(m) where m = (r-1)/2. There is no proof (that I know of), but there is evidence that this should be true.

There should also exist upper bounds on either the Carmichael numbers of order(m) < x (and show that it is 0 for some x), or there is a lower bound such that the smallest Carmichael numbers of order(m) > L.

If these two arguments are true, then there should exist a modified version of the conjecture that is true as we will have conditions for which n must be prime.
I can't seem to get away with it

(x - 1)^(t*n + n) = x^n - 1 mod(n, x^r - 1) where t = 2*r*(n^((r - 1)/2) - 1) if jacobi(n | r) = -1
or
(x - 1)^(t*n + n) = x^n - 1 mod(n, x^r - 1) where t = (n^((r - 1)/2) - 1) if jacobi(n | r) = 1
if
n^2 ≠ 1 mod r and r > 5.

As there are infinitely many values of w such that (x - 1)^w = x^n - 1 mod(n, x^r - 1), proving that w = t*n + n is the smallest such integer (apart from n itself) is false:

n = 61, r = 7

So now I seem to have dug a deeper hole into solving this problem. We need a lower bound B such that
(x - 1)^w ≠ x^n - 1 mod(n, x^r - 1)

if w is any integer (n < w < B).
carpetpool is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
I think I have a conjecture MathDoggy Miscellaneous Math 11 2019-04-17 07:05
Revisited "Primorial as Product of Consective Number" MARTHA Miscellaneous Math 7 2018-11-02 01:24
This conjecture may be useful. reddwarf2956 Prime Gap Searches 2 2016-03-01 22:41
Problem Ten revisited Harvey563 Open Projects 97 2011-09-30 20:19
Intel Atom revisited hj47 Hardware 15 2010-07-08 20:19

All times are UTC. The time now is 00:02.

Mon Feb 24 00:02:30 UTC 2020 up 23 days, 18:34, 2 users, load averages: 2.20, 2.23, 2.36

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.