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

Re: [PrimeNumbers] always prime?

Expand Messages
  • Jud McCranie
    ... Yes, and interestingly, the above doesn t hold true without the absolute value part. There are non-constant polynomials whose positive values (at
    Message 1 of 6 , May 12, 2001
    • 0 Attachment
      At 11:19 PM 5/11/2001 +0200, Yves Gallot wrote:
      >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.
    • 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 2 of 6 , May 12, 2001
      • 0 Attachment
        > >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 3 of 6 , May 14, 2001
        • 0 Attachment
          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 4 of 6 , May 22, 2001
          • 0 Attachment
            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.