Talk:Prime number/Draft

Greg Martin has nominated this version of this article for approval. One other editor currently supports the approval (Jitse Niesen). The Mathematics Workgroup is overseeing this approval. Unless this notice is removed, the article will be approved on May 6, 2007.

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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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)

Large primes

I think the article needs to discuss in some more detail the state of the art in primality testing (a lot of readers would probably be interested in knowing what the largest known prime is) and the use of prime numbers in cryptography. Fredrik Johansson 21:14, 23 April 2007 (CDT)

Yes, that's a good point. We don't talk much about primality testing, but we might start out with, say, Mersenne primes. Greg Woodhouse 23:05, 23 April 2007 (CDT)

Prime number records

I've been thinking about what to do here. Paulo Ribenboim's The Little Book of Bigger Primes (see the references) has all kinds of prime numbert records in it, but it hardly seems interesting to just quote results from another source hardly seems that interesting (and I'm not so sure it isn't plagiarism). Where do we draw the line? Greg Woodhouse 18:01, 24 April 2007 (CDT)

You'll find much more up-to-date records on the web, for example at the prime pages. In any case, I think it would be sufficient to mention the current largest Mersenne prime, as well as outline (in a few sentences) the history of computing large prime numbers (maybe we should have a separate prime number records or even mathematical records article?). Then mention somewhere that in cryptographical applications, primes need "only" be a few hundred digits long in which case primality testing on a PC is dirt cheap (while semiprime factorization is not). Fredrik Johansson 02:23, 25 April 2007 (CDT)

I agree with Fredrik Johansson here. A list of records would be too much, I think, but mentioning a couple of interesting and important records in the article somewhere would enhance the article. --Catherine Woodgold 09:56, 29 April 2007 (CDT)

uh oh - suggestions for changes

It's super to see a lot of quality work being put into this article, which will be one of the most important ones in the Mathematics section. I do have several suggestions for altering and improving the article. All of them are (of course) debatable.

My suggestion for the first sentence - "A prime number is a whole number that can be evenly divided by exactly two numbers, namely 1 and itself."

Most readers' default reaction to "number" is to think of whole numbers, so I think the existing parenthetical comment is more distracting than helpful. The changes to the second part of the sentence are motivated by wanting the definition to be simple enough while still not admitting 1 as a prime number. (In fact not calling 1 a prime number is a relatively recent development, something like a hundred years old. To me the two most important reasons why 1 shouldn't be a prime number are (a) the annoyance it would cause when stating the unique factorization property of integers and (b) the modern understanding of the difference between "units" and "irreducibles" in other rings. Maybe this is worth mentioning briefly in an appropriate part of the article.)

Move all the details of the Riemann zeta function, the proof of the prime number theorem, and the Riemann hypothesis to (a) newly created article(s) devoted to those topics.

In other words, most of the "Distribution of prime numbers" section. This echoes one of my comments about the Complex number article, namely that an introductory article on prime numbers should mention what we know but should be careful about putting in too much detail about how we know it. Mentioning these three things, particularly the prime number theorem, is a great idea - this is important folklore surrounding the primes - but formal descriptions and proofs are probably more suitable for articles more directly concerning them. We should keep the statement of the prime number theorem and perhaps a bit of commentary; it might also be helpful to add a description of the prime number theorem for arithmetic progressions, the most concrete example of which is the fact that roughly a quarter of all prime numbers end in each of the digits 1, 3, 7, and 9 - thus tying into a remark in the primality testing section. Perhaps these two results can be grouped in a section called "Solved problems" or something like that, to partner with the section on "Unsolved problems" ... the "Solved problems" section can include Bertrand's Postulate, that there's always a prime between n and 2n.

Add a section early on that addresses the question "Why is this random definition of 'prime number' at all worthwhile?"

Two answers: one, that every number has at least two divisors, namely 1 and itself (yes, 1 is weird), and so numbers with no other divisors are special; and two, the statement of unique factorization. (Other answers?) I always find it useful to make an analogy with physical chemistry: if integers are the molecules, then prime numbers are the atomic elements, and unique factorization is analogous to the statement that particlar molecules always have the same atomic structure. This can then lead into the desire to understand the distribution of primes, and the unhappy(?) fact that the answer is nowhere near as simple and patterned as the periodic table of elements.

Take out the proof of unique factorization, and either take out the "Definition" section or else move it much to much later in the article.

Same reasoning as above. Most non-mathematicians are confused by the simple assertion that there's anything to prove in the statement of unique factorization! As for "Definition", the difference between "prime" and "irreducible" in general rings is nuanced enough - and it doesn't even manifest itself in the integers! - and I don't think the layperson will get too much out of it. At the very least, put it much later, once the more accessible facts surrounding prime numbers have been laid out.

Keep Euclid's proof that there are infinitely many prime numbers.

I know that's not a suggestion for a change! Here, not only is the fact itself incredibly important, but Euclid's proof is an amazingly great example of a proof - known in antiquity, sleek and elegant, rigorous and logically sophisticated (a proof by contradiction, after all) yet one of the few rigorous mathematical proofs totally accessible to a layperson. In fact I think we should take great care in crafting this proof to be as clear and accessible as possible. One suggestion already is to take out the notation for "does not divide", simply using those words instead (it only happens once after all). The current version is a bit on the terse side; I think moderate expansion would help it.

Rename "Locating primes" to "Determining whether a number is prime"...

... and also include subsections describing Fermat's "difference of squares" method and the Fermat's Little Theorem test (necessary condition) for primality. These can be introduced by commentary to the effect that roundabout ways of testing primality can be paradoxically more effective in practice. (By the way, in the typesetting of the sieve of Eratosthenes diagrams, the horizontal strokes that indicate composite numbers are exactly the same height, on my browser at least, as the horizontal bar of the digit 4. The effect is that 4 itself doesn't look crossed off. This exact phenomenon was present in the typesetting of my Ph.D. thesis! Can another crossing-off indicator be employed?)

In "Unsolved problems", add the old chestnut conjecture that there's always a prime number between consecutive squares.

Another possibility, though less well-known outside of number theory circles, is the conjecture that there are infinitely many primes of the form n^2+1. (Really this can be extended to just about all irreducible polynomials.) We should also describe Mersenne primes (related to perfect numbers) and Fermat primes (related to constructible regular polygons), both of which correspond to unsolved problems about whether there are infinitely many or not (experts seem to believe yes and no, respectively). I'm unsure whether that's best done in this article or in articles created for those purposes ... maybe the latter (in which case mentions and links should still be put in this one).

Add the following fantastic quote somewhere! (maybe in the suggested separate article on the distribution of prime numbers?)

"It is evident that the prime numbers are randomly distributed but, unfortunately, we don't know what 'random' means." - R. C. Vaughan

I'm pretty sentimental about prime numbers, whence the length of the above commentary - but they're so cool, it's impossible not to want this article to be fantastic! It's well on its way; keep up the great work. - Greg Martin 01:12, 25 April 2007 (CDT)

Greg, you are able to make the changes you suggest above as editor, yourself. If you feel these are best incorporated before you can nominate the article for approval- I urge you to do so. Nancy Sculerati 09:37, 29 April 2007 (CDT)

I'm not sure about that. An approving editor is not supposed to have been significantly involved in authoring the article, I think, so sometimes it may be worthwhile to step back and let others make the suggested changes so that one is available to approve the article. An editor might not necessarily want to tread as close as possible to that line, either. Or might prefer that others do it for other reasons. --Catherine Woodgold 09:48, 29 April 2007 (CDT)

Catherine, you bring up an important issue that deserves explicit discussion. In this case, since Greg Martin has reviewed a highly developed article written by others - and done so consistently in the role of editor, he certainly is not only allowed to make editorial changes in the actual article in order to finalize the version needed for approval (especially in the exact manner he has done so here, after open discussion with the authors on the talk page), as an editor - he is expected to do so. That's what editors do. On the other hand, just as you insinuate, it is mandatory that an author who happens to also be an editor does not write an article in his or her workgroup and then nominate his or her own work for approval. That's the "legal theory" (if you will) behind the "nominating editor cannot be author" rule. And it is part of the quality assurance mechanism at CZ, it is not primarily an instrument that serves to ensure user participation, but one that serves the readers of the articles by disallowing an article that is not actually checked by another pair of expert eyes over the ones that constructed the article. If all of the available mathematics editors had a major hand in the generation of this article from a stub to a developed article, then (as was true for the first approved version of the first approved article Biology), three of the primary author/editors would have to agree to nominate for approval. Since we do not have 3 active math editors, that would be trouble, and no stable version could be approved at this time, as you rightly suggest. But one reason that the position of Approvals Management Editor was created was to put judgement to work to help facilitate the approvals process. In this case, there is no doubt in my mind- NONE- that Greg Martin is acting strictly within the bounds of editor on an article that was created and extensively developed by others. In no way is this his article that he is nominating for approval, except in the sense that he has edited it - which is, of course, exactly what an editor anywhere does: edit. What this article is, by the way, is a credit to all of you, as far as I'm concerned, and particularly to Greg Woodhouse - and, of course, to CZ. Good work! :-) Nancy Sculerati 22:59, 29 April 2007 (CDT)

Targeted audience

I'm not a mathmetition and wouldn't say a bad word about the fine work in the article but ..... Who does the article target? Certainly not a grade school student, looking for reliable information about Prime Numbers. Would a Junior High Schoool student benefit? A high school student? An average citizen? Some level of education is needed to appreciate the article, who is the audience? As the article displays itself, the first thing that attracts my eye is 12 square blocks. 12 isn't prime, 4 isn't prime, but finally I see a character, "3" which I know is prime. So, I read the ==Definition== and it is full of symbols I don't know. I stop right there but I see there are lots more symbols I don't know and have never heard of. Impressive? YES. Useful, user friendly ? I'm not enthused, but I'm only one person. Terry E. Olsen 08:33, 29 April 2007 (CDT)

I moved things around a bit, to put the part about infinitely many primes closer to the beginning of the article, because it's easier to understand than some other parts of the article, as Greg Martin pointed out. I also added a few words to explain the notation in some places. Maybe we need an article "mathematical notation" which lists the meanings of all the symbols used in all the math articles.

I like what user dlehavi said in the forum: "Keep in mind three audiences when writing an article: general readers, math students and professionals." [1]. I think it's good to aim for as broad an audience as possible. When it's possible to make it easy to understand and also provide information concisely enough that professionals don't have to wade through a lot of stuff they already know, that's the way to go in my opinion. (Professionals don't always remember everything from school, either, though). However, it's not always possible to please everyone, and I believe Citizendium articles are supposed to be "pitched at the university student level" [2]. I interpret this to mean a typical university student -- that is, math articles should not be aimed only at students specializing in math; on the other hand, a university student who has studied a lot less math than the typical student may be left behind, but only if necessary and with regret. --Catherine Woodgold 09:35, 29 April 2007 (CDT)

Conjecture

Greg Woodhouse added this in the conjecture section, and I changed the wording to the following to indicate that it is a conjecture (which I presume it is, based on where it was put): "It has not been proved whether there are infinitely many primes of the form $n^{2}+1$. (Not all numbers of this form are prime, but some are.)" Are you sure you mean $n^{2}+1$ and not $2^{n}+1$? Do we say "proven" or "proved"? --Catherine Woodgold 10:36, 29 April 2007 (CDT)

Yes, I meant n^2 + 1, though I'm taking Greg Martin's word for it on this one. It seems strange to me that this could not be true, given that y = x^2 + 1 describes a curve of genus 0, meaning it is rationally equivalent to a line, and it's already known (Dirichlet) that there are infinitely many primes in an arithmetic progression (where a and b are coprime, of course). Greg Woodhouse 10:57, 29 April 2007 (CDT)

The way the article now stands, the sentence "There are ininitely many primes of the form $n^{2}+1$", besides having a spelling error, is listed under "Some unsolved problems" but is stated as if it's known. This leaves the reader wondering whether this is a statement which has been proven, or not. Similarly for the statements about Mersenne and Fermat primes, modulo the spelling error.

OK, I'm confused. I said I had changed the wording, but perhaps I hadn't. Anyway, my point is it needs to be changed: are these statements known, or not? --Catherine Woodgold 11:23, 29 April 2007 (CDT)

No, they are all conjectures. Greg Woodhouse 11:26, 29 April 2007 (CDT)

I verify that n^2+1 is intended, although 2^n+1 is a separate and equally interesting conjecture. Also, my dictionary says that both "proved" and "proven" are valid. I'd probably use "proven" myself, but I don't mind either one. - Greg Martin 19:38, 29 April 2007 (CDT)

I like "proven". --Catherine Woodgold 19:40, 29 April 2007 (CDT)

Introduction

Personally, I don't like the introduction, because it's not an introduction. The first two paragraphs are a (well readable) definition, but should, in this length, go to the first paragraph below the contents, titled "Definitions". The third paragraph is a good start for an intro, but perhaps should be wrangled to answer the following questions short, but well readable:
1) What is a prime number?
2) Which science does it belong to and how does it fit into this science?
3) Why are prime numbers so important and well researched?
Or in other words: Why should I as a "mathematical end user" read the rest of the article?

Generally speaking, this article should become an example for others as, especially in nature sciences and computers, the "end user" is often forced to read encyclopedic articles that feel like science papers.--Erkenbrand 14:38, 2 May 2007 (CDT)
(Uh, I thought Erkenbrand was my login name only??)

---

Found this a nice and clear article - but in the lead - "evenly divided" to me seems a rather unclear descriptor.Gareth Leng 04:01, 3 May 2007 (CDT)

Unique factorization property

I rewrote the definition of unique factorization a bit. I think Catherine's change was on the right track, but since sets don't have repeated elements, it wasn't technically correct. There didn't seem to be a simple rewording that would work, though, so I sent ahead and rewrote the paragraph. Greg Woodhouse 21:55, 3 May 2007 (CDT)

Good catch. I was thinking about how it doesn't matter if you reorder things in sets, but I forgot about the repeated elements. Looks OK now. You're right, it's not easy to say. --Catherine Woodgold 07:24, 4 May 2007 (CDT)

Deletete analogy of primes and chemical elements?

This one sentence seems to be a bit of an orphan and (at least now) it disrupts the flow of the article. Can we just delete it? Greg Woodhouse 21:57, 3 May 2007 (CDT)

I hope this sentence won't be deleted. I like it (or something espressing a similar concept). Erkenbrand said the introduction should say why prime numbers are important. This sentence is an answer to that question. Rather than deleting, I might expand it: Because of this, prime numbers play a role in arithmetic analogous to that of atoms in chemistry: every positive integer > 1 can be built up from the primes using multiplication." or something similar. --Catherine Woodgold 07:28, 4 May 2007 (CDT)

Hmm... Well, I guess there are really two issues then. My original concern was that the sentence caused an unnatural break in the narrative, but that could be addressed by moving it to somewhere else. But now that I think about it, I'm not even sure that I agree with what is being said. Primes do provide a notation independent way of decomposing integers, but is that really why they are important? I need to think about that one and come back to it later, but my point of view is something a little different but close: Primes correspond to "simple" objects (like simple groups in group theory). Greg Woodhouse 09:09, 4 May 2007 (CDT)

In classical chemistry, atoms were introduced (and so named, even) because they too are "simple" (i.e., indecomposable) objects. In fact there's really no difference between "a way to decompose widgets" and "a simple widget", since the former is defined in terms of the latter. ... Anyway, that being said, I agree that the atom sentence is a bit flow-disrupting. Improvements welcome! - Greg Martin 23:40, 4 May 2007 (CDT)

Another characterization

I wonder whether the beginning of this " Another characterization is that a prime number p cannot be factored as the product of two numbers..." could be changed to "In other words, a prime number p..." The two characterizations seem just about equivalent to me. Maybe something more neutral: "Another way of describing them is", "Another definition is" or "This means that..." or "Equivalently,..." The trouble with "another characterization" is that it raises the expectation that a significantly different definition will be given (e.g. one that might describe different objects than the other definition in some rings), and then I'm disappointed to see practically the same definition expressed in different words. --Catherine Woodgold 07:34, 4 May 2007 (CDT)

That's a good point. I changed it to "Another way of saying this..." Greg Woodhouse 08:49, 4 May 2007 (CDT)

I agree that the two characterizations are very close to each other, so I'm wondering whether we really need them both. Another issue is that 1 is a prime according to the second characterization (a number which cannot be factored ...). -- Jitse Niesen 09:01, 4 May 2007 (CDT)

Here's my reasoning for including both versions: The first sentence is the complete formal definition. But the "can't be unboringly factored" version is the version that's implicitly used in the rest of the introduction - read for example the reason why 9 and 15 aren't prime, or look at the caption of the rectangles figure: both refer to factorizations, not divisors. Jitse raises a good point that the second version doesn't rule out 1; but (depending on the beginning of the sentence) the second version doesn't purport to be an if-and-only-if statement. Maybe starting the sentence with "In particular," would make that point clear, as well as mitigate the critique above. I'll give it a try. - Greg Martin 23:51, 4 May 2007 (CDT)

what's "this"?

General writing-style point: using "this" as a pronoun. In the version I'm about to edit, there are four instances of this ailment in the introduction alone:

• Another way of saying this is ...
• Because this is a bit complicated to say, ...
• Because of this, prime numbers ...
• While this used to be the case, ...

I won't assert an unbreakable rule, but in general: using "this" to refer to "an unspecified amount of stuff I just got done saying" tends to lead to vague-sounding prose - partially because of the pronoun itself, but also because we writers who allow ourselves to use this "this" are usually struggling with a concept we're having trouble phrasing well, or with a way to write a transition from one sentence to another, and the "this" lets us off the hook. - Greg Martin 23:47, 4 May 2007 (CDT)

Existence of at least one prime factorization

There's something missing in the proof that there are infinitely many primes. It is made to depend (unnecessarily) on the proof of unique factorization. But the proof given on the unique factorization page proves only that there are not two different factorizations. It does not prove that every number has at least one prime factorization, which is the part of the proof that the "infinitely many primes" proof depends on. So that part is missing from both pages. One way to fix this would be to replace this:

On the other hand, every number N > 1 is divisible by some prime (in fact, it factors completely into prime numbers, due to unique factorization).

with something like this:

Now, $N$ must be either prime, or divisible by some number less than itself. That number, in turn, must be either prime or divisible by an even smaller number. Continuing in this way, since the number of numbers between 0 and $N$ is finite, we must eventually reach a prime number $q$ which divides $N$. Since none of the primes $p_{1},p_{2},\cdots p_{n}$ divide $N$, $q$ must be a prime that was not already included in that list. This contradicts the hypothesis, therefore proving that the list of primes is not finite.

An alternative would be to include, on the unique factorization page, a proof that every number has at least one factorization into prime numbers. --Catherine Woodgold 07:43, 5 May 2007 (CDT)

True observation. I think this would go better on the unique factorization page. - Greg Martin 04:30, 6 May 2007 (CDT)

Connecting up mention of the prime number theorem

In the section "There are infinitely many primes", it says "One mathematical milestone known as the Prime Number Theorem estimates how many of the numbers between 1 and $x$ are prime numbers: approximately $x/\ln x$ of them are." This idea is treated in much more detail, and with a different logarithm notation, in a later section. Possible edits could include: Append "(See below)"; change the log notation to match that used below and append a footnote or parenthetic remark defining it as the natural logarithm and linking to the logarithm page; (or append such a remark while keeping the ln x notation); Shortening this mention to "One mathematical milestone known as the Prime Number Theorem estimates the distribution of prime numbers (see below)". --Catherine Woodgold 18:23, 5 May 2007 (CDT)