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

Re: [PrimeNumbers] always prime?

Expand Messages
  • Yves Gallot
    ... It is also because of the m indeterminates. If f is a non constant polynomial with integral coefficients, in 1 indeterminate, then there exist infinitely
    Message 1 of 6 , May 12, 2001
      > >It was proved that:
      > >If f is a polynomial with complex coefficients in m indeterminates, such
      > >that its values at natural numbers are, in absolute value, prime numbers,
      > >then f must be a constant.
      >
      > Yes, and interestingly, the above doesn't hold true without the "absolute
      > value" part. There are non-constant polynomials whose positive values (at
      > non-negative integers) are all prime.

      It is also because of the m indeterminates. If f is a non constant
      polynomial with integral coefficients, in 1 indeterminate, then there exist
      infinitely many integers n such that f(n) is a composite integer.
      According to Ribenboim (The New Book of Prime Number Records) page 192, the
      same hold for polynomials in 2 indeterminates. Jones found a non-constant
      polynomial of degree 5 whose positive values (at non-negative integers)
      are all prime. The problem seems to be open for degree 3 and 4.

      Yves
    • Liu Fengsui
      Hi everyone. If anyone ask again: why is this? FYI ,I will say as follows. There are three definitions: explicit,recursive and implicit. It was proved that the
      Message 2 of 6 , May 14, 2001
        Hi everyone.
        If anyone ask again: why is this? FYI ,I will say as follows.
        There are three definitions: explicit,recursive and implicit.
        It was proved that the definiyion of primes is recursive.See Liu's prime formula:
        T1=<1>,
        T[n+1]=(Tn+<0,mn,2*mn,...,(P-1)*mn>)\<Pn>*Tn,
        p1=3,
        p[n+1]=U(T[n+1]).
        The primitive recursive operator can't reduced to the composition,thus there is no explicit definition of primes. There is implicit definition of primes,they are all old prime formulas.
        Of cause,the original definition of primes is a predicate.A polynomial in m indeterminates with the predicate "positive values" can define the primes,but can't abandon the condition "positive values" .
        china Liu Fengsui.


        > >It was proved that:
        > >If f is a polynomial with complex coefficients in m indeterminates, such
        > >that its values at natural numbers are, in absolute value, prime numbers,
        > >then f must be a constant.
        >
        > Yes, and interestingly, the above doesn't hold true without the "absolute
        > value" part. There are non-constant polynomials whose positive values (at
        > non-negative integers) are all prime.

        >It is also because of the m indeterminates. If f is a non constant
        polynomial with integral coefficients, in 1 indeterminate, then there exist
        infinitely many integers n such that f(n) is a composite integer.
        According to Ribenboim (The New Book of Prime Number Records) page 192, the
        same hold for polynomials in 2 indeterminates. Jones found a non-constant
        polynomial of degree 5 whose positive values (at non-negative integers)
        are all prime. The problem seems to be open for degree 3 and 4.

        Yves






        [Non-text portions of this message have been removed]
      • 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 3 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.