867-5309

The number 8,675,309 is the title of a song. It is also a prime number, and as far as I can tell, it's the largest prime number to appear in a song title. According to this list of songs with numbers in the title from Wikipedia (which is currently in the "Wikilists" space because it was deleted from mainstream Wikipedia, larger numbers in song titles are: 9 million, 30 million, 93 million, 100 million, 1 billion, 1 trillion, 1 quadrillion, 1 googolplex, infinity minus one, and infinity.

I'm not surprised to see that most of these are "round numbers", simply because they're easier to say; in particular by inspection they are not prime, since they're all multiples of large powers of 10. But I'm wondering if anybody out there has written a song titled, say, "six billion and one".

(No fair going out and writing such a song.)

Primes is in P

It appears to not be widely known, at least among some people who would like to know it, that primality testing can be done in polynomial time. The "naive" methods for determining whether a number is prime -- trial division and the like -- take time which is polynomial in the size of the input (the polynomial may be n^1/2, but it's still a polynomial) which is considered "large" because it's exponential in the number of digits or bits in the input.

The fact that primality testing can be done in polynomial time -- and without recourse to a randomized algorithm -- I've heard about here and there; not surprisingly, the exponent is large. Namely, to test n for primality takes time O~(log⁶ n), where O~(t(n)) = O(t(n) * P(log t(n))) and P is a polynomial. (If you don't like the O~ notation, you can say O(log^6+ε n) for any positive real ε.) It's conjectured that "6" can be replaced by "3". The proof is based on a generalization of Fermat's Little Theorem; of course it's nothing like the "naive" method of trial division, but the paper is surprisingly accessible given the strength of the result.

The paper is Manindra Agrawal, Neeraj Kayal, Nitin Saxena. PRIMES is in P. Annals of Mathematics, 160 (2004), 781-793. (http://www.math.princeton.edu/~annals/issues/2004/Sept2004/Agrawal.pdf)

Edited, 7:21 pm: It's been pointed out to me that this result is widely known among people who work in the appropriate fields, and that's true. But a lot of people who are just looking for some sort of color when they're giving an example of a hard algorithmic problem, and whose specialty is not in that area, either don't know this or don't remember it. I'm claiming that the result deserves to be more well-known among mathematicians in general.

Subprime?

If you live in the U. S. and pay any attention to the news, you know that there's a mess going on in the mortgage markets, as companies which have lent to "subprime" borrowers are having trouble. And because of the way that the markets work, this has had effects spread far and wide.

But doesn't "subprime" sound like it should be a mathematical term? It seems like it would either mean:

• numbers which are just less than a prime (let's say numbers of the form p-1, where p is a prime)


• numbers which are "almost prime" (say, products of two primes)

But what would a "superprime" be? In the first case, the analogous definition is clearly numbers of the form p+1; in the second case, the only extension I can think of is numbers which are products of 0 primes, i. e. the number 1.

Numbers that "look prime"

From MathNotations, which is a math education blog. A suggested activity for high schoolers:

Using positive integers, think of primes ending in 1 or 3 (you may want to use the technically precise phrase 'whose units digit is 1 or 3'). For example, 21 'ends in' 1, but it is not prime. You must go in order and you are not allowed to ask the number the previous person gave!

I tried doing this myself; it's surprisingly hard! I would never be so foolish as to say 51 is prime... but I said to myself "41... 43... um, what comes next?" It's something about looking at that list of numbers out of context; a significant part of my knowledge about which numbers are prime is apparently just being able to recite the first thirty or forty (up to 150 or so) pretty quickly. ("Recite" is not quite the right word; I tried to actually do this and once I got past 37 I realized that I was not quite working from memory so much as doing trial division.)

Also, I have to share the old joke that 91 is the first number that "looks prime" but isn't. The argument is that multiples of 2 and 5 "look composite" (by looking at their last digit); multiples of 3 "look composite" since people know the fact that a number is divisible by 3 if and only if the sum of its digits is; and (two-digit) multiples of 11 "look composite" because of their repeated digits. Furthermore, squares don't "look prime". So the smallest number that looks prime, but isn't, is 7 times 13, or 91. After that, numbers that look prime but aren't are:
119, 133, 143?, 161, 187, 203, 209?, 217, 221, 247, 253?, 259, 287, 299.
(I put a question mark after multiples of 11 because I'm not sure how to count multiples of 11 which are greater than 100. And of course, this criterion of "looks prime" is subjective; for example, I don't think 217 or 287 look prime, since they can easily be written as 210 + 7 or 280 + 7 and thus their factorizations as 7 × 31 and 7 × 41 are obvious)

so there are 14 "psuedoprimes" in the range from 100 to 300, compared with 32 actual primes in that range. So this test isn't too bad in that range. Of course, eventually it becomes quite bad; it identifies (1/2)(2/3)(4/5)(10/11) = 8/33 of all integers as primes (ignoring the fact that it identifies squares as nonprimes), when the actual density of the primes is zero. In the limit, almost all of the numbers identified by this test as primes are in fact composite.

Twin primes

Are There Infinitely Many Primes, by D. A. Goldston, via Casting Out Nines. This was based on a talk given to motivated high school students, so you don't need much background to understand it.

Since this is at least nominally a probability blog, I draw your attention to the following: Call p and p+2 a twin prime pair if they're both prime. Then it's conjectured that the number of twin prime pairs with smaller member less than or equal to x, denoted π₂(x), is asymptotically

and there is probabilistic reasoning that leads to this, which is a version of the Twin Prime Conjecture; basically, the "probability" that a number near t is prime is 1/(log t), and so the probability that two numbers near t are both prime should be the square of this. So the number of twin prime pairs under x should be just that integral, except that we have to take some divisiblity information into account, which is what the product out front does. If a number n is odd, then n+2 is twice as likely to be prime as it would ``otherwise" be; if n is not divisible by some odd prime p, then n+2 has ``probability" (p-2)/(p-1) of being not divisible by p (we must have that n isn't two less than a multiple of p), which is 1 - 1/(p-1)² times the "naive" probability that n+2 isn't divisible by p, namely (p-1)/p.

I rather like results of this form, where we can guess properties of the primes by assuming that the probability that a given integer is divisible by a prime p is 1/p and these events are independent for different primes p; I've talked about this before, when I sketched a heuristic argument for the Goldbach conjecture. Sure,.the primes have no business behaving randomly. But what reason is there that they should behave nonrandomly?

How common are prime powers?

The Mathematics Weblog at sixthform.info shows a cute little theorem: that the group table for any cyclic group can be arranged so that all the instances of the same element lie along a (possibly broken) diagonal, and that this isn't possible for noncyclic groups.

This reminds me of the addition tables one sees in the back of notebooks, which in base 10 look like

+	0	1	2	3	4	5	6	7	8	9
0	0	1	2	3	4	5	6	7	8	9
1	1	2	3	4	5	6	7	8	9	10
2	2	3	4	5	6	7	8	9	10	11
3	3	4	5	6	7	8	9	10	11	12
4	4	5	6	7	8	9	10	11	12	13
5	5	6	7	8	9	10	11	12	13	14
6	6	7	8	9	10	11	12	13	14	15
7	7	8	9	10	11	12	13	14	15	16
8	8	9	10	11	12	13	14	15	16	17
9	9	10	11	12	13	14	15	16	17	18

If you just look at the last digits -- thus considering this as addition in the group Z₁₀ -- then you see this pattern. All the numbers ending in, say, 5 -- the 5s and the 15s -- lie along a single broken diagonal.

You don't see the same pattern when you consider the analogous multiplication table, and so you think "hmm, the integers mod 10 under multiplication don't form a cyclic group?" But as it turns out, they do, and it's a cyclic group of order 4, because when we're considering the integers mod k under multiplication we only look at the invertible elements; these are 1, 3, 7, and 9, and we get the following little table:

×	1	3	9	7
1	1	3	9	7
3	3	9	7	1
9	9	7	1	3
7	7	1	3	9

Is this something special about 10, or is it common? Now, if we pick a random number k, what are the chances that the group of units (i. e. invertible elements) mod k is cyclic? From looking at the small cases, you'd think the probability is rather large: k = 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, and 14 have this property. But in general, it's actually pretty rare. Given k, we can write k = p^aq^br^c... where p, q, r... are primes, and consider the integers modulo each of the prime powers p^a, q^b, r^c, ... separately. For example, the group of units mod 10 is the direct product of the group of units mod 2 (trivial) and mod 5 (cyclic of order 4). The group of units mod 12, in contrast, is the direct product of the group of units mod 4 (cyclic of order 2) and mod 3 (cyclic of order 2, again), which isn't cyclic.

It turns out (this is a fairly basic result in classical number theory) that the units mod k form a cyclic group if and only if k is 2, 4, a power of an odd prime, or twice a power of an odd prime. This is a quite restrictive condition, although it doesn't seem so from the list I made; I suspect this sequence is only a bit less sparse than the primes themselves.

However, I can't show this quickly. The number of odd prime powers up to N is a bit smaller than log₃ N + log₅ N + log₇ N + ..., where the indices run over all the primes (the exact number is this with a floor function applied to each term); this is

(log N)(1/log 3 + 1/log 5 + 1/log 7 + ...)

and we can approximate the jth prime by j log j; thus this is approximately

(log N)(1/(2 log 2) + 1/(3 log 3) + 1/(4 log 4) + ...)

or at least has the same convergence behavior as this sum. But this sum can be approximated by the integral of 1/x log x from, say, 2 to infinity; that integral is log log x, so the sum diverges, although very slowly. As you may have guessed, I don't actually know analytic number theory, and I'm just fooling around here. I might actually be wrong; prime powers might end up being more common than primes for large enough numbers.

Primeshooter

Primeshooter, from 1729.com. You shoot numbers with their prime factors; when you hit a number with one of its prime factors (2, 3, 5, 7, 11, 13, 17, or 19) it is divided by that number. Once you reduce a number to a prime, you can hit it with a "prime" bullet that makes it go away; numbers also go away if you successfully get them down to 1. You lose a life if a number hits you; if a number reaches the bottom of the screen without getting down to 1 it reappears at the top. Sometimes (I don't know when) it appears in a bright red box, in which case you'll lose a life if it reaches the bottom. Sometimes you get an extra life.

I got a score of 834 (= 2 × 3 × 139, although that's irrelevant), which means I successfully shot at 834 prime numbers. I don't recommend trying to beat me, because even if you succeed you will lose about thirty-five minutes of your real life.

The rest of the web page looks kind of fun, too.

An exercise for the reader: why is it fitting that this is on 1729.com?

secret messages in human DNA?

In yesterday's New York Times, Dennis Overbye writes about the possibility of hiding secret messages in human DNA.

This seems vaguely plausible. Each strand of DNA is composed of a sequence of the four bases adenine, cytosine, guanine, and thymine. One could use these like the digits 0, 1, 2, and 3 in a base-4 number system; equivalently, they could be used as 00, 01, 10, 11 in a binary number system, so each base represents two bits.

Humans have done things like this. Freshly allocated memory in certain computing environments is filled with the repeated string (in hexadecimal notation) DEADBEEF; also ABADBABE, BAADF00D, CAFEBABE have been used. (CAFEBABE is apparently used in Java-related contexts; see this archive of a thread "why CAFEBABE?" on comp.lang.java.) It is of course quite unlikely that any of these strings would be found repeatedly in a computer's memory, if the memory is filled at random; the chance of getting, say, ten DEADBEEFs in a row (assuming there's not a process that's just copying some string over and over again) is one in 2³²⁰, which is more than the number of subatomic particles in the universe. As you may know, the Central Dogma of molecular biology says that DNA is transcribed into RNA, which is translated into proteins; each triplet of DNA bases maps to a single amino acid, of which there are twenty. There's a code that assigns a letter to each amino acid; the letters B, X, and Z are "special" letters; U, O, and J aren't used. It's possible to spell things with the remaining twenty letters, though, and I've heard that some genetically engineered food includes the name of the company doing the engineering in the junk DNA.

So what if someone designed us? Maybe they'd hide a message in the DNA? (For the record, I don't believe in intelligent design; however, if we were intelligently designed, that leads inexorably to the question of "who designed the designer"?) But how would they hide that message? They don't know what language we speak, and they certainly don't know that we'll invent this twenty-letter way of describing protein sequences concisely. And unlike in the DEADBEEF example, there appear to be reasons why you'd want stretches of DNA to be the same thing over and over again; these occur in the so-called junk DNA. Like many mathematicians, I'm inclined to believe that they'd hide the prime numbers. The idea behind this is that the primes should never occur due to a natural process, but any culture which is the least bit mathematically sophisticated should have them. (The idea comes from people who are searching for extraterrestrial intelligence; they assume that both us and the other species involved have radio astronomy, and inventing radios without mathematics is Hard.) The sequence

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, ...

which in base-4 is

2, 3, 11, 13, 23, 31, 101, 103, 113, 131, 133, 211, 221, 223, 233, ...

(Note that a very large number of these base-4 numbers, when read in base 10, are also prime! This is just a coincidence, although the fact that 4 and 10 are both even -- and therefore numbers which are odd remain odd under this transformation -- helps.) Replacing 0, 1, 2, 3 with A, C, G, T, we get

GTCCCGGTTACACCATCCTCTCCTTGCCGGCGGTGTT

and so if we see this string in DNA, perhaps we should be suspicious? Well, it's 37 base-pairs long; thus we expect it to occur once in every 4³⁷ base pairs. The human genome is about 3,000,000,000 base-pairs long, so if the genome were random, the probability of this string occuring is 3,000,000,000/4³⁷ = 1.6 × 10^-13.

So if we find it? Then yes, there's probably a Designer. But this doesn't mean that creationists should go fishing for hidden patterns in the genome. First, my choice of how to encode the primes was entirely random. We could reorder A, C, G, and T. We could have encoded the primes in base 3, using the fourth base to separate them. We could have encoded the primes as

CAACAAACAAAAACAAAAAAAC...

where the number of A's between each pair of C's is prime. And so on. Creationists looking in DNA would, I suspect, take a Bible code-like approach to the search. And if there were slight errors? They'd blame it on mutations, which are inevitable (the Times article points out that there are certain "ultraconserved" segments of the genome -- but those sections also appear to be functional, so it would be harder to hide a message in them -- but then if these hypothetical designers are so smart, maybe they can make those sections be functional and hide messages...)

Sequencing the human genome is good for lots of reasons. But the search for messages from the past probably isn't one of them. They might be there, but we'd be searching for a needle in a haystack. And there would be lots of shiny things that aren't needles there, too.