mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2017-12-30, 13:28   #34
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by guptadeva View Post
well ... so far so good
do you happen to know some necessary and sufficient condition for a number to be a prime - other than a sieve ?
a simple deterministic primality test would be fine
Not sure it's simple but numberphile did a video on aks testing.


Last fiddled with by science_man_88 on 2017-12-30 at 13:35
science_man_88 is offline   Reply With Quote
Old 2017-12-30, 13:36   #35
guptadeva
 
Dec 2017

1100102 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
Not sure it's simple but numberphile did a few videos on aks testing.
agree ... the aks test is astonishing as to the fact, that it exists,

yet as our mathematical knowledge increases it would be truelly wonderful to know somethig even more simple and beautiful than that ...
besides that, the aks test (ignoring their very nice contribution through appropriate polynomial division for a moment) is nothing than the trivial fact that p is prime iff p divides the all binomial coefficients (p over q) with 1 < q < p ... naively spoken it's a sieve in disguise.

(the terms simple and beautiful might not be defined properly, yet i believe we will know and recognize it as soon as we see it ?)

Last fiddled with by guptadeva on 2017-12-30 at 14:01
guptadeva is offline   Reply With Quote
Old 2017-12-31, 00:26   #36
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by guptadeva View Post
besides that, the aks test (ignoring their very nice contribution through appropriate polynomial division for a moment) is nothing than the trivial fact that p is prime iff p divides the all binomial coefficients (p over q) with 1 < q < p ... naively spoken it's a sieve in disguise.
I’m not sure I can agree. If it were a sieve in disguise I’d expect it to take at least as long as enumerating the primes in the relevant interval. But that’s not the case — it’s vastly faster. So while one might argue that it owes some heritage to sieves I certainly can’t agree that it’s a sieve (in disguise or otherwise).
CRGreathouse is offline   Reply With Quote
Old 2017-12-31, 01:20   #37
guptadeva
 
Dec 2017

2×52 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
I’m not sure I can agree. If it were a sieve in disguise I’d expect it to take at least as long as enumerating the primes in the relevant interval. But that’s not the case — it’s vastly faster. So while one might argue that it owes some heritage to sieves I certainly can’t agree that it’s a sieve (in disguise or otherwise).
Click image for larger version

Name:	aks test.png
Views:	82
Size:	20.2 KB
ID:	17431

step 3 of the aks-test (see attachment above) is in fact a classical sieve.
the reason for aks being vastly faster than a full sieve is the existence of the parameter r in step 2, so that the sieve only has to run until min(r,n-1) ...
yet in the (relatively rare) case, that r>=n-1 a full sieve is executed.
also the step 5 is relatively slow ...

the main contribution of agrawal, kayal and saxena was in fact the introduction of an appropriate polynomial division (with x^r -1) based on group-theoretical arguments and also to proove that their algorithm is complete.

Last fiddled with by guptadeva on 2017-12-31 at 01:49
guptadeva is offline   Reply With Quote
Old 2017-12-31, 02:34   #38
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

32·101 Posts
Default

Certainly we would want to read more about the AKS test rather than rely on that video. "the aks test [...] is nothing than the trivial fact that [...]" is what everyone thinks after watching that video, which is a disservice to the AKS paper, which the video rolls up in "well that's not quite the same" at 2:35-2:50.

It's like a video about the Lucas-Lehmer test spending almost all the time explaining Wilson's Theorem, then at the end saying "and then using some fiddly bits from Lucas, Lehmer did some twiddling to make it a bit faster, but we won't show that."

"yet in the (relatively rare) case, that r>=n-1 a full sieve is executed."

Once above tiny size numbers, r is *much* smaller than sqrt(n). The time taken in steps 1-4 is very small relative to step 5.

"also the step 5 is relatively slow ... "

Yes it is, but it's faster than trial division once past small inputs and clearly shows polynomial growth in empirical implementations. Much different than trial division.
danaj is offline   Reply With Quote
Old 2017-12-31, 02:53   #39
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

11100011012 Posts
Default

Quote:
Originally Posted by guptadeva View Post
a simple unconditional deterministic primality test would be fine
At the last Pari/GP Atelier, I had a discussion with a number theorist who was genuinely mystified as to why anyone would think ECPP was at all complicated. It was quite obvious to him and his colleagues. Not that it was obvious in original conception of course, but given a short description of the complete method and a reference to a few papers, what would be any sort of hold up?

"simple" is relative.


I also assume you want "fast" added to your list of items. It's also relative, but without it there are quite a few useless choices. You can also get some not useless but not really fast tests like the BLS75 methods (partial factoring of n-1 and/or n+1). They're simple, unconditional, and deterministic. They're also a lot faster than trial division.

I do agree that, given the state of most programs / programmers, it'd be nice to have something else. Multiple Miller-Rabin tests is the height of most non-math programs. At least adding a strong Lucas test would be nice. APR-CL and ECPP do have open source libraries but certainly not many users.
danaj is offline   Reply With Quote
Old 2017-12-31, 02:56   #40
robtaylor501
 
Dec 2017
California

23 Posts
Default

Quote:
Originally Posted by guptadeva View Post
ok ... i will give you some hopefully fruitful hints:

in order to find an expression or inequality for your 'accomodation lemma' you really do not need to consider perfect accomodations for all different arrangements.
it is sufficient to consider perfect accomodations of the actual arrangements for/of the sets of all odd numbers between n^2 and (n+1)^2 for increasing n ...
if you start to see a pattern in these arrangements you would then maybe be able to find a form of the general 'shape' (we really need a better word for that) and then try to apply induction from there

you could also consider taking one step back and include the prime 2 and all even numbers back into your considerations

another approach could be to succesively sieve all numbers which can be accomodated by the primes 2,3,5,... out from [n^2, (n+1)^2] and see if you might be able to start to see some pattern in the sets remaining ...

alternatively you could also start with a proof of the oppermann conjecture instead

finally you could also step out of the box and attempt to find some new relation or pattern among the prime numbers themself
Thank you. Helpful hints indeed. Time for a pot of tea and a new perspective!
robtaylor501 is offline   Reply With Quote
Old 2017-12-31, 03:05   #41
guptadeva
 
Dec 2017

2×52 Posts
Default

Quote:
Originally Posted by danaj View Post
Certainly we would want to read more about the AKS test rather than rely on that video. "the aks test [...] is nothing than the trivial fact that [...]" is what everyone thinks after watching that video, which is a disservice to the AKS paper, which the video rolls up in "well that's not quite the same" at 2:35-2:50.
yes - it is indeed a disservice to the aks-paper

aks.pdf

to make such simplifying statements - yet sometimes simplification may improve understanding.

Last fiddled with by guptadeva on 2017-12-31 at 03:24
guptadeva is offline   Reply With Quote
Old 2017-12-31, 03:15   #42
guptadeva
 
Dec 2017

2·52 Posts
Default

Quote:
Originally Posted by danaj View Post
At the last Pari/GP Atelier, I had a discussion with a number theorist who was genuinely mystified as to why anyone would think ECPP was at all complicated. It was quite obvious to him and his colleagues. Not that it was obvious in original conception of course, but given a short description of the complete method and a reference to a few papers, what would be any sort of hold up?

"simple" is relative.


I also assume you want "fast" added to your list of items. It's also relative, but without it there are quite a few useless choices. You can also get some not useless but not really fast tests like the BLS75 methods (partial factoring of n-1 and/or n+1). They're simple, unconditional, and deterministic. They're also a lot faster than trial division.

I do agree that, given the state of most programs / programmers, it'd be nice to have something else. Multiple Miller-Rabin tests is the height of most non-math programs. At least adding a strong Lucas test would be nice. APR-CL and ECPP do have open source libraries but certainly not many users.
very informative ... THANKS

yet, honestly i'm not interested in "fast" algorithms at the moment - so which algorithms do you have in mind when when mentioning "quite a few useless choices" ?
maybe they are "beautiful" ?

Last fiddled with by guptadeva on 2017-12-31 at 04:05
guptadeva is offline   Reply With Quote
Old 2017-12-31, 03:33   #43
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by robtaylor501 View Post
That assumes I know how to code. I don't.
Elementary is not trivial though.
science_man_88 is offline   Reply With Quote
Old 2017-12-31, 05:49   #44
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

32·101 Posts
Default

Quote:
Originally Posted by guptadeva View Post
to make such simplifying statements - yet sometimes simplification may improve understanding.
It would be a great intro if it were a bit clearer about what it was demonstrating, and then put a little more time in about what the rest of the paper did. I enjoy their videos, and it is a heck of a job to simplify enough to explain to a more general audience and make it very interesting. So I'd really wish it was clearer.

There are a lot of people posting on the internet who see that video then believe that lemma is the AKS test entirely. Sometimes with some confusion over what all the fuss was about or how it could be efficient, but sometimes just recommending people implement it to check 10 digit inputs because it is Moar Faster.


Wilson's theorem is quite elegant and simple, but not fast. Similarly the statement about binomials equaling zero, which is elegant though slower than simple trial division. Trial division itself, whether naive, wheel optimized, or using primes generated with a sieve. Miller's test using either n/4 or various proven reductions is pretty straightforward (getting all the way down to 2*log^2(n) requires the GRH). Underwood collects lots of oddball formulas in his 1983 paper Formulas for Primes, most of which devolve into either Wilson's Theorem or a sieve.

In practice one usually uses APR-CL and/or ECPP. Typically with BPSW used as a pre-test. Of course if the input is a special form with an efficient test we would use that.
danaj is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Claimed proof of the ABC conjecture (Zha, 2009) R.D. Silverman Math 6 2019-04-22 00:03
Collatz Conjecture Proof Steve One Miscellaneous Math 21 2018-03-08 08:18
The Beal Conjecture Proof Arxenar Miscellaneous Math 1 2013-09-07 09:59
A proof for the Twin Prime Conjecture Carl Fischbach Miscellaneous Math 7 2009-06-24 05:52
Proof of Goldbach Conjecture vector Miscellaneous Math 5 2007-12-01 14:43

All times are UTC. The time now is 20:35.


Wed May 25 20:35:32 UTC 2022 up 41 days, 18:36, 0 users, load averages: 1.42, 1.49, 1.41

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔