- 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

> 0,

> 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, I

Ditto.

> don't

> have to know what X is to know whether the number is prime.

> Similarly, if a positive integer has the decimal digits

Presumably 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 math

That'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

> 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.

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 > I think Tao's result falls firmly into recreational math

Indeed 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

journals...

CC- Phil Carmody wrote:
> my comment above about wanting a "test" to be a deterministic

If 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

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