Talk:Prime number/Draft

Article Checklist for "Prime number/Draft"

Workgroup category or categories	Mathematics Workgroup [Categories OK]
Article status	Developed article: complete or nearly so
Underlinked article?	No
Basic cleanup done?	Yes
Checklist last edited by	Greg Woodhouse 10:58, 22 April 2007 (CDT)

To learn how to fill out this checklist, please see CZ:The Article Checklist.

---

Primes and their generalizations

After some thought, I added a clarification to the introductory material. The reason is that while the rational primes (i.e., primes in $\mathbb {Z}$) are very important in cryptographic applications, other engineering applications (notably error detecting and correcting codes, where linear codes are very important) depend upon properties of primes and factorization in other rings (such as $\mathbb {F} _{2}[x]$). It may seem like a small thing, but I do want to be sure that the claims made in the introductory section are correct. Greg Woodhouse 05:41, 5 April 2007 (CDT)

Just delete this?

I noticed that someone removed the hyperlinks from the latter part of the introductory paragraph, and I agree that this was a good idea. To be honest, I wouldn't mind just deleting

Understanding properties of prime numbers and their generalizations is essential to modern cryptography, and to public key ciphers that are crucial to Internet commerce, wireless networks, telemedicine and, of course, military applications. Less well known is that other computer algorithms also depend on properties of prime numbers. These algorithms allow computers to run faster, computer networks to carry more data with a greater degree of reliability, and are basic to the operation of many consumer electronics devices, such as television sets, DVD players, GPS devices, and more. Life as we know it today would not be possible without an understanding of prime numbers.

I put it in there to provide some motivation for the study of prime numbers, but I'm not so sure I don't find it distracting (or just plain too long) without the hyperlinks. Greg Woodhouse 10:14, 5 April 2007 (CDT)

I think it's a bit too much; especially the last sentence. However, don't throw out the baby with the bath water. We do need some motivation. A simple solution would be to retain only the first sentence (personally, I'd also delete telemedicine).

I had some other comments when I read through the article. I'll just jot them down here for you to consider or ignore as you see fit. You already resolved one of them (in Euclid's proof, explain why it's impossible that no prime divides N) by adding a discussion on unique factorization.

• The aside on notation. I think the definition of prime number without symbols works perfectly fine, making me wonder why you praise the virtues of notation at that place. Incidentally, you need to explain the notation a | b.
• The equivalence of the two definitions for prime numbers is in fact quite important (unique factorization depends on it), and should perhaps be stressed more.
• What do you have in mind when you say that the second definition is preferred in advanced number theory? It's a long time ago that I looked at number theory, but I thought both were used (they are called irreducible and prime elements, respectively).
• On a first reading, the proof of unique factorization looks a bit messy, though I can't articulate exactly what the problem is. I'll try to have a look at it later.

-- Jitse Niesen 19:52, 5 April 2007 (CDT)

• I deleted the last sentence of the introduction, along with the reference to telemedicine.
• What I think I was trying to do with the notation for "divides" (not that I really planned it out in advance) is inrouce the notation by using it, and then step back and explain what it means. I'll add something there.
• The comment about the latter definition of "prime" being more characteristic of advanced work was inappropriate (and probably wrong). It's gone now. As I'm sure you realize, what I had in mind is that the concepts prime and irreducible just happen to coincide in Z because it's a PID. Right now, you're seeing my thoughts in rather raw form, and I guess I was thinking that I didn't want to get involved with a discussion of primes vs. irreducible elements, but I wanted to at least note that there is a difference.
• I don't like what I wrote about unique factorization, either. I didn't really want to dwell on it too much, but by the time I had written it out, the argument was just too long, and a bit awkward sounding. I'll see what I can do. Greg Woodhouse 23:49, 5 April 2007 (CDT)

Okay, I've rewritten the proof of prime factorization and filled in Euler's proof that there are infinitely many primes. Greg Woodhouse 08:26, 6 April 2007 (CDT)

What to include?

The topic of this article is obviously a big subject. When I picked up this article (from the "most requested" list on the WG page), I wasn't sure how much I wanted to cover, though some of the basics are clear. I at least want to state the prime number theorem, and But what about, say, say something about unsolved problems about prime numbers.But what about, say primality testing? I haven't even talked about the sieve of Eraosthenes yet! I thought about covering, say, the primes in the rings of Gaussian and Eisenstein integers, but that should probably be left to another article. What do you think? Greg Woodhouse 08:41, 6 April 2007 (CDT)

I've added a section on primality testing. I'd say: include full descriptions of both trial division and the sieve of Eratosthenes, but leave out detailed discussion of optimizations and complexity analysis (leave those aspects for subarticles). Mention that there are faster algorithms such as the Miller-Rabin test, but don't describe them in this article. I agree that generalizations of primes in other rings should largely be left to another article.

Looking at the Wikipedia article for inspiration:

• We should definitely have a section on the distribution of primes (PNT, prime counting function), on the general problem of finding patterns in the primes (mentioning Ulam's spiral, etc)
• We should describe applications of prime numbers in some more detail. This could look similar to the section in the Wikipedia article.
• We don't need trivia lists like Wikipedia's "Properties of primes" and "Primes in popular culture" and "Trivia" sections. That's not to say all of the content of those sections would be inappropriate here, but I'm sure we can come up with a more coherent article structure.
• There are lots and lots of special classes/categorizations/subsequences of primes. Except for perhaps twin primes and Mersenne primes, I think these are mostly trivia and should be left to another article.

Fredrik Johansson 10:06, 6 April 2007 (CDT)

I'll largely be echoing Fredrik here. PNT is important as a standard non-trivial result. Riemann hypothesis is worth a million bucks; need I say more? Twin prime conjecture is accessible and drives home the point that not everything in maths has been done centuries ago. I'm reserving judgement about Ulam's spiral. Primality testing, beyond Eratosthenos, should probably be kept brief: something about the quest for the largest known prime number, and the polynomial algorithm found recently by the Indians (AKS?). Generalizations should also be briefly mentioned. Perhaps a paragraph about Gaussian integers as an example. And applications; can be contrasted with Hardy's "number theory is beautiful because it's useless". All that will probably be enough. -- Jitse Niesen 12:22, 6 April 2007 (CDT)

I had never heard of Ulam's spiral, but looking at the article in Mathworld, I see Athur C. Clarke mentioned it in "The City and the Stars". It seem to be a popular culture connection (which has nothing to do with whether or not it's mathematically interesting, of course!) I'd leave it out of this article, at least for now. I'm trying to think of a good way to handle the PNT (and the Riemann hypothesis). Simply stating these results without giving any indication of their significance or how they fit in to number theory in general hardly seems enough. In my opinion, just stating results or definitions is where we move from being an encyclopedia to being a dictionary, at least so far as mathematics is concerned. Greg Woodhouse 16:28, 6 April 2007 (CDT)

Prime Number Theorem

I just added a formal statement of the theorem. Obviously, more exposition is needed.

The Sieve of Eratosthenes

I just added a verbal description of the algorithm. I'm not at all good with diagrams, so if you have ideas for making it look better, by all means do!

The Riemann Hypothesis

Okay, I know the Riemman hypothesis is central to the study of prime numbers, but I'm really struggling with this section. I don't see any easy ways to motivate it. In fact, you have to grapple with the idea of analytic continuation before the staement even makes sense. Now, I know that one thing that has always intrigued me is how function fields (in positive characteristic) are so much easier to analyze. But that's not an answer, and it's certainly not something that can be discussed in this article. On the other hand, I'm really loathe to say, "Well there's this mysterious thing out there that's really exciting, but it just can't be explained in layman's terms". Any ideas? Greg Woodhouse 17:55, 9 April 2007 (CDT)

I had a quick go at it and did some major restructuring in the process:

• I removed the bit on extending the list in the sieve of Eratosthenes. It doesn't seem that important.
• Added an introduction to PNT to smoothen the transition.
• Moved the discussion of the zeta function further down because it is rather tricky.
• Removed the discussion about elementary proof of PNT, because I couldn't make it fit.
• Removed the details about the Riemann Hypothesis. It's impossible to explain properly without mentioning analytic continuation. It can be explained in layman's terms (at least, we can try to), but it will take up quite a bit of space and perhaps this article is the proper place to do it.

As I said, it was a quick job and only meant as a possible suggestion of where to go. In my experience it's good to have at least a rough idea of the possible ways to structure the article instead of discussing it in abstracto. In particular, I wrote from memory that Hadamard and de la Vallee Poussin use the location of zeros of the Riemann zeta function, but I may well be mistaken here.

By the way, Euler's proof needs more explanation (why are the sum and the product equal?). -- Jitse Niesen 22:58, 9 April 2007 (CDT)

I think that your reorganization has improved the article, and certainly agree that the section on the sieve of Eratosthenes was too long. I made a few attempts last night to be more explicit about the Euler product (other than noting, as I always have, that it follows from unique factorization), but it just came across as pedantic, so I cancelled both edits. I'm not sure how to fit in either, but the elementary proof of the prime number theorem was a major achievement, and something that can hardly be omitted from an article on prime numbers. Finally, the section on Euler's proof is starting to take on a less significant role in the article (for example, I had intended to use it to establish that $\sum 1/p$ diverges). Perhaps that section should be omitted? Greg Woodhouse 11:46, 10 April 2007 (CDT)

I admit that I was surprised to see Euler's proof. It relies on the divergence of the harmonic series and the sum of the infinite geometric series, both of which are fairly advanced topics (in comparison with what precedes and follows). On the other hand, it ties in nicely with unique prime factorization and the Riemann zeta function (it explains why this function could give information on the distribution of primes). Therefore, I decided not to remove it immediately.

Perhaps it's better to explain the sum=product stuff where we introduce the Riemann zeta function. At that point, we can assume some more mathematical sophistication on the part of the reader, so it will be easier to explain why the sum and product are equal. We can then make a short remark there that $\zeta (1)=\infty$ because the harmonic series diverges, which implies that there is an infinite number of primes. -- Jitse Niesen 07:24, 15 April 2007 (CDT)

This sounds like a better approach. Fredrik Johansson 10:43, 15 April 2007 (CDT)

I implemented my suggestion. I see that my writing style is rather bland, especially when juxtaposed with Greg's lively writings, so it does need some rewriting (apart from fixing the mistakes which probably crept in). -- Jitse Niesen 11:09, 19 April 2007 (CDT)

Some comments

The article ends by mentioning "π(n)". I don't think this function was mentioned earlier in the article, so a definition is needed. (Something to do with the density of primes in the integers?)

I wasn't able to follow the Euler proof of infinite number of primes as it stood. I got help from elsewhere, and have added some words to help others over the same hurdle. I also rearranged the equation to put the product on the left and the harmonic series on the right, because I can figure out that the two are equal by starting with the product and manipulating it, but I can't if I start with the harmonic series.

In Euclid's proof, I took out the q-hat notation, which I found confusing.

I made a few other relatively minor changes.

Thanks for your comments and input! Yes, $\pi (x)\scriptstyle$ does have to do with the distribution of primes (I thought I defined it?) Anyway $\pi (x)\textstyle$ is the number of primes $\leq x\scriptstyle$. Greg Woodhouse 13:01, 15 April 2007 (CDT)

I apologize; the definition was right there in the article the whole time; I'd just read it. Maybe it would be easier to notice, though, if the same variable were used. I mean, is there a reason why in one place it's given as $\pi (x)\textstyle$ and in another place as $\pi (n)\textstyle$? Would it be OK to change the $n\textstyle$ to an $x\textstyle$? It also helps that "textstyle" or "scriptstyle" have been put in so it doesn't display in a tiny script -- I hadn't known how to do that.

Re the Euler formula: good, there's a lot more guidance for the reader now in following this proof. I suggest inserting something to let the reader know where they're heading: I would insert, just before "Using the formula for the sum of a geometric series," a phrase which tells the reader that we're about to prove the Euler formula as opposed to assuming it's true and based on that prove something else. I would insert something like "Euler established this result as follows." or "It can be seen as follows that this sum is equal to this product." or "This can be established by ..." or another phrase which accomplishes this purpose. (I don't know how Euler actually did it.) Comments? --Catherine Woodgold 09:21, 22 April 2007 (CDT)

I went ahead and changed the language a bit. The notation $\pi (x)$ vs. $\pi (n)$ is a bit more problematic, though, because it's important that $\pi$ is a function of a real variable, and using n as a parameter would tend to obscure that fact. Greg Woodhouse 10:49, 22 April 2007 (CDT)

What about using $x\scriptstyle$ in both places? Is there a reason why $n\scriptstyle$ has to be used? This is not a terribly important point, anyway. --Catherine Woodgold 18:47, 23 April 2007 (CDT)

Request for approval

Editors: Could you take a look at this article and, if you think it's ready, initiate the approval process? Greg Woodhouse 13:31, 22 April 2007 (CDT)