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

Re: [PrimeNumbers] Little result about primes (Tao)

Expand Messages
  • Phil Carmody
    From: Jack Brennen ... What if I want a primality test to be deterministic binary predicate with values is prime or is not prime ? A
    Message 1 of 7 , Feb 26, 2008
    • 0 Attachment
      From: Jack Brennen <jb@...>
      > Phil Carmody wrote, quoting Terry Tao:
      > >
      > > """
      > > As a consequence, it is not always possible to test
      > whether a number is prime from its base $a$ expansion
      > without reading all of its digits. We also present some
      > slight generalisations of these results.
      > > """
      > >
      > > I've got a generalisation of that result:
      > >
      > > It's *not ever possible to even know the value of
      > a number* from its base $a$ expansion without reading all
      > of its digits.
      > >
      > > If you can't even know its value, you certainly
      > > can't test its primality.
      >
      > Ah, but you *can* know a number's primality without
      > knowing the number's value.
      >
      > If a positive integer's decimal representation ends in
      > 0,
      > I can test its primality without looking at all the digits.

      What if I want a primality test to be deterministic binary predicate with values "is prime" or "is not prime"? A "decision problem" in the language of computability theory. The above returns "is not prime" or "don't know", but never "is prime".

      If you've not run something which can return "is prime", then you've not "tested whether a number is prime", surely?

      > If a positive integer has the decimal digits 2,0,X, I
      > don't
      > have to know what X is to know whether the number is prime.

      Ditto.

      > Similarly, if a positive integer has the decimal digits
      > 1,6,7,1,8,X,Y, I know that it's composite without
      > knowing the value of either X or Y.

      Presumably that's an ordered list, not a multiset?
      However, it's still not a deterministic binary predicate.

      > I think Tao's result falls firmly into recreational math
      > and he's not proposing a practical primality test. A
      > better way to describe what he's getting at: you have
      > a
      > base B number. How many of its digits do you need to
      > examine to deterministically describe its primality?
      >
      > Tao shows that it is possible to construct a sieve which
      > yields a positive density of primes for which every
      > binary digit must be examined -- because if you flip
      > any binary digit, you change the primality result.
      >
      > I think you might be caught up on thinking that a
      > primality test must be practical. Obviously, Tao is
      > not proposing that any practical primality test for
      > general numbers would ever purposely avoid examining
      > all of the bits/digits.

      That's a good point. It was early when I responded, and my
      brain wasn't quite in the right mode to get that. However,
      my comment above about wanting a "test" to be a deterministic
      binary predicate still stands.


      Phil


      ____________________________________________________________________________________
      Looking for last minute shopping deals?
      Find them fast with Yahoo! Search. http://tools.search.yahoo.com/newsearch/category.php?category=shopping
    • Chris Caldwell
      ... Indeed he is continuing an old line of puzzles from Erdos in the 1950 s forward; using the same key idea that he did (start with a (partial) covering
      Message 2 of 7 , Feb 26, 2008
      • 0 Attachment
        > I think Tao's result falls firmly into recreational math
        > and he's not proposing a practical primality test.

        Indeed he is continuing an old line of puzzles from
        Erdos in the 1950's forward; using the same key idea
        that he did (start with a (partial) covering congruence...)
        It had nothing to do with a new test, he was creating,
        and counting, composites.

        But lets be serious here a moment, by what measure
        is primality testing not recreation mathematics? Or
        number theory for that matter? It is a game we play.

        Mathematicians usually classify something as elementary
        or not. It should all provide recreation. Tao
        classified this as elementary. But it, and the previous
        articles, are all published in mainline peer-reviewed
        journals...

        CC
      • Jens Kruse Andersen
        ... If the binary input number is 101 then you can prove primality without reading the middle bit, since 101 (decimal 5) and 111 (decimal 7) are both prime.
        Message 3 of 7 , Feb 26, 2008
        • 0 Attachment
          Phil Carmody wrote:
          > my comment above about wanting a "test" to be a deterministic
          > binary predicate still stands.

          If the binary input number is 101 then you can prove primality
          without reading the middle bit, since 101 (decimal 5) and
          111 (decimal 7) are both prime. You don't know the exact
          value of the input number but you can still prove it must be a prime.

          Consider base 10. If the input number is 17 then you cannot
          say whether it's prime if you only know the digits are x7,
          or if you only know they are 1x. But suppose the digits are
          binary coded and you are only missing one bit from one of the
          digits. If you know the number is either 17 or 37 then you
          can prove primality without knowing the precise value of each
          digit. But if the number is 294001 or another weakly prime in
          http://www.research.att.com/~njas/sequences/A050249 then
          you must know the precise value of each digit to prove
          primality, because any change to any digit will make it composite.

          Tao shows that for all bases, there are infinitely many primes
          for which you cannot prove primality without knowing the
          precise value of each digit.

          --
          Jens Kruse Andersen
        Your message has been successfully submitted and would be delivered to recipients shortly.