Re: [PrimeNumbers] Little result about primes (Tao)
- From: Jack Brennen <jb@...>
> Phil Carmody wrote, quoting Terry Tao: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".
> > """
> > 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
> I can test its primality without looking at all the digits.
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, IDitto.
> have to know what X is to know whether the number is prime.
> Similarly, if a positive integer has the decimal digitsPresumably that's an ordered list, not a multiset?
> 1,6,7,1,8,X,Y, I know that it's composite without
> knowing the value of either X or Y.
However, it's still not a deterministic binary predicate.
> I think Tao's result falls firmly into recreational mathThat's a good point. It was early when I responded, and my
> and he's not proposing a practical primality test. A
> better way to describe what he's getting at: you have
> 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.
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.
Looking for last minute shopping deals?
Find them fast with Yahoo! Search. http://tools.search.yahoo.com/newsearch/category.php?category=shopping
> I think Tao's result falls firmly into recreational mathIndeed he is continuing an old line of puzzles from
> and he's not proposing a practical primality test.
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
- Phil Carmody wrote:
> my comment above about wanting a "test" to be a deterministicIf the binary input number is 101 then you can prove primality
> binary predicate still stands.
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
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