No free lunch [was: always prime?]
- RE: Diophantine Representation of the Set of Prime Numbers
There was something about this subject that perplexed me.
It seemed to imply a free lunch in primality proving.
As there is no such thing, I sought the demystification.
For what it's worth, here is what I ended up with.
Corrections welcomed! If busy, skip to joke at end.
A probable primality test (and, in an utterly negligible
subset of cases, a BLS proof) of a number N is fast because
it involves only O(d) multiplications of numbers with O(d)
digits, where d=log(N). With FFT, the test scales like d^2.
Contrast this with a Wilsonian proof that (N-1)!=-1 mod N,
needing O(exp(d)) multiplications at O(d) digits.
But what about certificate validation?
It may take O(d^5) multiplications at O(d) digits to make
an ECPP certificate, but to validate that certificate takes
perhaps O(d^2) multiplications, it seems me. If so Cert_Val
scales like d^3, though Titanix scales like d^6. The O(d^3)
ECPP *proof* time is then asymptotically less than the
O(d^4) Miller *test* time that would furnish a proof if GRH
were to be proven, one fine day. [Please don't repeat that
the Titanix running time is longer: that is not the point
at issue here, which is certificate validation.]
It is less well known that every prime has at least one
certificate of primality consisting of a *fixed* number,
O(100), of multiplications however large the prime!
This is implicit in Ribenboim's  brief account of the
Jones-Sato-Wada-Wiens polynomial  in 26 indeterminates.
It is legitimate public relations, but perhaps not good
pedagogy, to give a polynomial that maps 26 integers to
primes or negative integers. The transparent device of
subtracting squares from 1 shows what is really going on.
Primality of k+2 is proven by 14 simultaneous diophantine
equations, namely the vanishing of the things that refs
[1,2] put in squared square-brackets. Moreover, 7 of
these (brackets 2,1,3,11,9,12,13 in Ribenboim's ordering)
may be taken as mere definitions of the integers
z,q,e,l,y,m,x (in that order) in terms of k and 26-1-7=18
auxiliary integers, subject to 14-7=7 conditions. Of these,
6 conditions are Pellian square tests (in brackets
4,5,6,7,8,10) and the last (14) is a factorization test.
The theorem of  thus tells us that for every prime
there exists a certificate of primality with 18
auxiliary integers proving 7 necessary and sufficient
conditions in less than 100 elementary operations.
So what's the snag?
Well the obvious snag is to create that certificate!
Yet that is not the subject of concern, here.
A less obvious snag is that it would take *exponentially*
longer to validate this certificate than it takes to
validate an ECPP certificate for a prime of the same size.
This second point is made particularly clear by Cristoph
Baxa . The underlying sleight of hand of the method of
Jones et al  is that it replaces the equation G=(k+1)!
by a set of necessary and sufficient diophantine equations,
with no reference to primality. Then one adds the Wilsonian
remark that G=(k+1)! may be written as G=g*k+2*g+k+1, in
Ribenboim's second bracket, if and only if k+2 is prime.
All the skull-duggery resides in solving Pellian equations
by exponentially growing Lucas sequences and hence creating
factorially large solutions for the diophantine equations.
The morsel of prime number theory was stated by John Wilson
(1741-1793) and proven by Joseph-Louis Lagrange (1736-1813)
in the oft-repeated process of adding francophone rigour to
opportunistic anglophone assertion. [Yves: plaisanterie!]
So the number of digits in the elements of the certificate
is O(d*exp(d)). One trades the vast Wilsonian expense of
O(exp(d)) multiplications at O(d) digits for the also vast
expense of a few multiplications at O(d*exp(d)) digits.
There is no free lunch, even in certificate validation!
Maybe this is the purgatory that awaits mathematicians.
Outside the pearly gates, Sao Pedro (or Sao Paulo?) says:
> So you are the guys and gals that read how to prove thisDavid Broadhurst
> number prime with only 87 multiplications and additions.
> Here's the input; there are pencils and paper: do it,
> and then the Boss will let you in. She's ordered lunch
> for you in 10^87 minutes time; do try not to be late!
 Paulo Ribenboim
The New Book of Prime Number Records
Springer, 1995, p.191.
 James Jones, Daihachiro Sato, Hideo Wada, Douglas Wiens
Diophantine Representation of the Set of Prime Numbers
American Mathematical Monthly
Vol 83, Issue 6, 1976, pp.449-464.
 Cristoph Baxa
A Note on Diophantine Representations
American Mathematical Monthly
Vol 100, Issue 2, 1993, pp.138-143.