Loading ...
Sorry, an error occurred while loading the content.
 

No free lunch [was: always prime?]

Expand Messages
  • d.broadhurst@open.ac.uk
    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
    Message 1 of 6 , May 22, 2001
      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 [1] brief account of the
      Jones-Sato-Wada-Wiens polynomial [2] 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 [2] 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 [3]. The underlying sleight of hand of the method of
      Jones et al [2] 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 this
      > 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!

      David Broadhurst

      References:

      [1] Paulo Ribenboim
      The New Book of Prime Number Records
      Springer, 1995, p.191.

      [2] 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.

      [3] Cristoph Baxa
      A Note on Diophantine Representations
      American Mathematical Monthly
      Vol 100, Issue 2, 1993, pp.138-143.
    Your message has been successfully submitted and would be delivered to recipients shortly.