yet another 'proof' of the legendary conjecture

[science_man_88]

Originally Posted by guptadeva

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.

[guptadeva]

Originally Posted by science_man_88

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 ?)

[CRGreathouse]

Originally Posted by guptadeva

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).

[guptadeva]

Originally Posted by CRGreathouse

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).

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.

[danaj]

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]

Originally Posted by guptadeva

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.

[robtaylor501]

Originally Posted by guptadeva

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!

[guptadeva]

Originally Posted by danaj

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.

[guptadeva]

Originally Posted by danaj

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" ?

[science_man_88]

Originally Posted by robtaylor501

That assumes I know how to code. I don't.

Elementary is not trivial though.

[danaj]

Originally Posted by guptadeva

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.