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

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

Expand Messages
  • Jack Brennen
    ... 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
    Message 1 of 7 , Feb 26 1:00 AM
    • 0 Attachment
      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.

      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.

      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.


      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.
    • 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 2 of 7 , Feb 26 4:10 AM
      • 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 3 of 7 , Feb 26 6:19 AM
        • 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 4 of 7 , Feb 26 7:39 AM
          • 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.