(7)
• NextPrevious
• ... 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, 2008
View Source
• 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.
• 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, 2008
View Source
• 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
• ... 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, 2008
View Source
• 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
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
• ... 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, 2008
View Source
• 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.