Talk:Prime number/GA1

GA Review

Article (edit | visual edit | history) · Article talk (edit | history) · Watch

Reviewer: Jakob.scholbach (talk · contribs) 14:44, 28 January 2018 (UTC)

I will review the GA nomination in the next few days. Additional reviews welcome! Jakob.scholbach (talk) 14:44, 28 January 2018 (UTC)

I really like this article and I think it meets the 6 good article criteria. Heck why not nominate it for featured article status? Since one of the primary contributors of this article is Professor User:David Eppstein who is himself a reliable source of information, I would support the nomination directly to featured article status. Brian Everlasting (talk) 19:52, 28 January 2018 (UTC)

From previous experiences with FA, I am not sure that hasting to an FA nomination is a good idea. Anyway, it is a pleasure to review this article, which is already in a very good shape. Jakob.scholbach (talk) 20:45, 31 January 2018 (UTC)

General remarks

All comments addressed Jakob.scholbach (talk) 12:59, 13 February 2018 (UTC)

• The formatting of mathematical symbols is highly inconsistent, mixing wiki markup, <math> markup and {{math|...}} markup in a seemingly random way. I personally like to have wiki markup wherever this does not lead to a sacrifice in formatting (this includes the large majority of expressions in this article), and <math> markup when this is not possible. In any case, a more uniform presentation is desirable, beginning in §1. Jakob.scholbach (talk) 20:45, 31 January 2018 (UTC)
  • I thought I had been doing this in my pre-nomination pass over the article, consistently using <math> because it is the only markup capable of supporting all the expressions in the article. I see that after I had done this, some other users including Derek M went back through and made it inconsistent again. Boo! And thanks for catching this. Anyway, the {{math}} should be gone again now. I also found a little more opportunity for removing notation altogether, the better approach (because less technical) when it can be accomplished. —David Eppstein (talk) 21:27, 31 January 2018 (UTC)
• The referencing seems to be highly detailed. While I appreciate this in general, this high number of references disturbs the reading flow, IMO. In some cases it might be better to move the references at least to the end of the phrases? E.g. in the first paragraph of §1, but also elsewhere. Jakob.scholbach (talk) 20:45, 31 January 2018 (UTC)
  • Uh. What? You are saying that, when specific claims are supported by specific citations, we should instead just put a catchall citation at the end of that piece of material and let the readers figure out which sources go with which claims? Taken to an extreme, this would mean having a bibliography at the end and no footnotes. Is that really what you mean? And can you explain which GA criterion you are interpreting as justifying this request? —David Eppstein (talk) 21:27, 31 January 2018 (UTC)

Yes, exaggerating my comment to the extreme makes it absurd. My point is just that in some cases we have references for utterly elementary and non-controversial facts. While, again, I appreciate your intense work on the references, I feel we are on the border of overdoing it. Since you gladly often even provide google links to the books, it is not at all hard to find the intended reference, if we put them at the end of the sentence. This is for the readers who doubt certain statements in the article. For those who just want to read more, most readers will use a book etc. of their choice to learn. So, while adding more and more references gives a certain plus, it also has a marginal negative effect when it comes to readability.

Anyway, I don't want to make a big point here; maybe just keep it in mind in case you add further references. Jakob.scholbach (talk) 22:40, 2 February 2018 (UTC)

Definition and examples

All comments addressed Jakob.scholbach (talk) 12:59, 13 February 2018 (UTC)

• What is the motivation to print the primes up to 1000? Either the list could be shrinked, or at least be used to illustrate some more content. E.g. the notion of a twin prime could be illustrated here, or the notion of a prime gap. A glimpse of the distribution of primes could also be illustrated here. None of this is mandatory, though, but just the bare list is a bit dry. Jakob.scholbach (talk) 20:45, 31 January 2018 (UTC)
  • I think the motivation is that readers expect to see a list of primes in this article (though not as detailed as list of prime numbers) and that 1000 is a nice round number. But it would be reasonable to shorten the list, for instance to 100. I'd prefer to keep the concepts very simple here rather than talking about prime gaps, though, which even some of our regular editors on this article have complained about as being too technical a concept. And I don't know what you mean by "A glimpse of the distribution". An illustration? Of what? —David Eppstein (talk) 21:33, 31 January 2018 (UTC)

re distribution: (If we keep the list up to 1000:) I was thinking of pointing out: there are ... primes less than 100, ... less than 1000 and maybe refer to later in the article when the prime number theorem is stated. Or alternatively, refer back to the top in the § on the prime number theorem.

In case I was unclear, I should say I am not totally opposed to having a little longer list, but I would suggest to "use" it more in the article. Jakob.scholbach (talk) 13:03, 1 February 2018 (UTC)

• The explanation "that divide n evenly (without a remainder)" should be moved up to where the word "evenly" first occurs.
  • Done. —David Eppstein (talk) 21:33, 31 January 2018 (UTC)

• The section is not well orderedfirst the definition of primes + examples, the list, further (non-)examples, then again comments on the definition (almost in the same words as in the beginning). This should be reordered.
  • Reordered. —David Eppstein (talk) 21:43, 31 January 2018 (UTC)
    • Much better. Jakob.scholbach (talk) 13:03, 1 February 2018 (UTC)

• " Therefore, the prime numbers other than two are all odd numbers. They are often called odd primes." -- Is there a wording which avoids the possiblilty of mixing "They" with "all odd numbers". Also, why "often"?
  • Reworded. —David Eppstein (talk) 21:43, 31 January 2018 (UTC)

• Algorithm: Pr = (6n+1) and (6n+5); but Pr ≠ {(6n+1)^k • (6n+5)^m} Csikoszi 23:10, 7 February 2018 (UTC)
  • @Csikoszi: Sorry, this is too cryptic for me to understand. Do you have some specific change to the article that you think should be made? —David Eppstein (talk) 00:22, 8 February 2018 (UTC)

This is the simplicity of prime numbers.Csikoszi 09:47, 8 February 2018 (UTC) — Preceding unsigned comment added by Csikoszi (talk • contribs)

Unique factorization and primality of one

All comments addressed Jakob.scholbach (talk) 12:59, 13 February 2018 (UTC)

• I feel the importance of the fundamental theorem of arithmetic should be stated more strongly?
  • It used to say "crucial" but I took that out as an unsourced editorialization. We would need a source for such an editorialization. They probably exist, but did you have one in mind? —David Eppstein (talk) 22:36, 31 January 2018 (UTC)
    • Barry Mazur, in §IV.1.4 of the Princeton companion to mathematics, writes:

The fundamental fact that any ordinary integer greater than 1 can be uniquely expressed as a product of (positive) prime numbers (that is, that Z enjoys the unique factorization property) is crucial for much of the number theory done with ordinary integers. That this unique factorization property for integers actually required proof was itself a hard-won realization of Gauss, who also provided its proof (see the fundamental theorem of arithmetic [V.16]).

(If you search through the book [email me if you want a pdf], there are a bunch of other statements along these lines.) Another way to testify its importance is to refer to it later in the article: in Euclid's proof, also in the discussion about ζ(s). Jakob.scholbach (talk) 13:03, 1 February 2018 (UTC)

• I added back a different adverb "central" which I think conveys the meaning and looks less like hyperbole than "crucial". I left it unsourced, though, to avoid contributing to the proliferation of many sources for small details that you were complaining about. And it is now mentioned in Euclid's proof, and was long since mentioned wrt the product formula for zeta. —David Eppstein (talk) 18:14, 1 February 2018 (UTC)

• The first sentence in the § is quite long. Can we break it into pieces and explain the two aspects: existence and unicity more slowly and maybe also separately? We do have the reference to different algorithms below, IMO this rather nicely explains the relevance of unicity, but is disconnected from the lead of the §.
  • Broken and rearranged. —David Eppstein (talk) 22:36, 31 January 2018 (UTC)
    • Good. Jakob.scholbach (talk) 13:03, 1 February 2018 (UTC)

• The wording with "prime factors" and wikilink is not optimal: the link goes to divisor! Can the term "prime factor" be introduced less implicitly? Maybe also restructure: first the example 23244 = ..., then refer to the terms as prime factors. Then state the theorem?
  • Ok, I put the example first. —David Eppstein (talk) 05:18, 1 February 2018 (UTC)

• Why not state the converse to Euclid's lemma?
  • I think there is more than one way of formulating a converse? But I added the one where a number that behaves like the p in Euclid's lemma must be prime. —David Eppstein (talk) 22:36, 31 January 2018 (UTC)
    • That's what I had in mind. Jakob.scholbach (talk) 13:03, 1 February 2018 (UTC)

• The coexistence of the fundamental theorem of arithmetic and the primality of one in one § is odd, IMO. The former is a cornerstone of maths, the latter a historic oddity, which IMO takes way too much space in this article. The § about primality of 1 should focus on the key points, which are that the notion just becomes inconvenient otherwise, e.g. in the fundamental theorem. Parts of this should go to the history section. Precisely identifying the last professional mathematician to call 1 a prime is pointless, IMO.
  • Primality of one section moved in its entirety to become a subsection of history (and shortened a little by removing the incorrect factoid about the last mathematician and its refutation) and the fundamental theorem promoted to be a whole section rather than a subsection. —David Eppstein (talk) 05:04, 1 February 2018 (UTC)
    • The move is good, but I still think the content-length ratio of that § is low. E.g. "In the 19th century many mathematicians still considered the number 1 to be a prime.[43] For example, Derrick Norman Lehmer's list of primes up to 10,006,721, reprinted as late as 1956,[44] started with 1 as its first prime.[45]" -- the second sentence does not seem to be an "example" of the first (19th vs. 20th century). Also, the level of detail is excessive, naming the list itself is hardly relevant, nor is the number of primes in it. I will comment again in more detail when I read the history section. Jakob.scholbach (talk) 13:03, 1 February 2018 (UTC)
      • Ok, I removed a lot of the detail from the Lehmer example, and also tightened the history section more generally. —David Eppstein (talk) 21:49, 1 February 2018 (UTC)
• The wording "began to arrive at the consensus that 1 is not a prime number," is not optimal, I would say "that 1 should not be regarded a prime number" -- after all these are just definitions.
  • That would be even longer and therefore more technical, so instead I reworded this as "began to agree that 1 should not be listed as prime". —David Eppstein (talk) 05:04, 1 February 2018 (UTC)

History

All comments addressed Jakob.scholbach (talk) 12:59, 13 February 2018 (UTC)

• Is the term "Islamic mathematician" or "Islamic mathematics" a standard term among scholars?
  • I don't know what's "standard", but it's definitely a title in use; see doi:10.1007/978-94-011-4301-1_9. The title of the Wikipedia article on this subject, Mathematics in medieval Islam, is longer and more awkward to use in this context. This exact phrase has been the topic of significant past discussions; see, e.g., Talk:Mathematics in medieval Islam/Archive 1#Proposed titles. The leading alternative and similarly-concise phrase "Arabic mathematics" isn't good in general because a lot of the mathematics of this era was done in Persia by non-Arabs, although as it happens the two mathematicians we mention were Arabs. —David Eppstein (talk) 20:08, 4 February 2018 (UTC)

OK, I don't have a preference either way, just wanted to make sure the term is not connotated in any way in our context. Jakob.scholbach (talk) 21:33, 4 February 2018 (UTC)

• "The next significant developments took place" -- this sounds a bit too general to me; maybe something like "The next significant development in the understanding of prime numbers..."?
  • Ok, yes, probably the Protestant Reformation was a significant development, but surely readers of the article can be expected to understand that this article is about prime numbers? —David Eppstein (talk) 20:08, 4 February 2018 (UTC)

Yes, we can expect that. I was trying to make a point that the sentence is quite generic and not too precise (17th and 18th century, why not also 19th?). I don't want to dig in my heels here, but I think the sentence could either be removed (maybe add "French mathematician" next to Fermat if you want to emphasize the geographical shift), or made into a somewhat sharper statement. Jakob.scholbach (talk) 21:33, 4 February 2018 (UTC)

Ok, removed. It was just a transitional sentence and the paragraph works well enough without it.

• Did Alhazen phrase things really in terms of (n-1)! \cong (-1) mod n? If not (which I suspect), it would be worthwile to clarify this. From my superficial experience with other pieces of history of mathematics, these early insights were often formulated much less clearly than modern notation suggests.
  • My guess would be something more like (n-1)!+1 is divisible by n. But I haven't read Alhazen in the original and the source doesn't specify. I was trying to write the theorem clearly and concisely, leaving the precise details to the linked article on Wilson's theorem. —David Eppstein (talk) 20:08, 4 February 2018 (UTC)

Yes, I would also guess that. Should we than just state it this way? Or maybe write "characterizing the prime numbers, in modern notation as the solutions to the equation ..." Jakob.scholbach (talk) 21:33, 4 February 2018 (UTC)

The divisibility formulation isn't really any longer or trickier, and this isn't part of the section on modular arithmetic where the choice of congruence vs divisibility would matter, so why not just state it that way? I changed it to use divisibility. —David Eppstein (talk) 04:46, 5 February 2018 (UTC)

Good: [probably] historically more accurate, and also simpler to understand for the modern reader. Jakob.scholbach (talk) 08:10, 5 February 2018 (UTC)

• I miss some sort of general statement what kind of methods were used in the historical development: is it true that people before Euler mainly used elementary combinatorial means and that Euler reshaped the field by bringing in analytic methods?
  • That seems a fair summary of the theoretical side to me but I'd have to find a source for it. And there was a lot of more elementary work later, on the primality testing and factorization method side of things. —David Eppstein (talk) 20:08, 4 February 2018 (UTC)
    • I added that Euler "introduced analytic methods" (I think that's clear enough without a source though if you want me to I'm sure I can find one), and reordered the list of Euler contributions to put the Euler–Euclid theorem on the pre-analysis side of things (since his proof is elementary) even though I think chronologically the analysis came earlier. —David Eppstein (talk) 04:42, 5 February 2018 (UTC)

OK, good. Now "He introduced methods from mathematical analysis to this area in his proofs of the infinitude of the primes and the divergence of the sum of the reciprocals of the primes" -- maybe reword as "He introduced methods from mathematical analysis to this area to show the divergence of the sum of the reciprocals of the primes and thereby the infinitude of primes"? Jakob.scholbach (talk) 08:10, 5 February 2018 (UTC)

That's actually a little inaccurate. In the same work, Euler gave two different analytic proofs of the infinitude of primes (both of which we discuss at different points in the article): one involving the Euler product formula for the sum of reciprocals of all positive integers (zeta(1)), and the other involving the sum of reciprocals of only the primes. —David Eppstein (talk) 08:17, 5 February 2018 (UTC)

OK, I take it back then. Thanks Jakob.scholbach (talk) 08:20, 5 February 2018 (UTC)

• "More recent algorithms like" -- aren't these post 1950? If so, the wording should reflect the timing a little more precisely.
  • I rearranged this paragraph, took out the detailed listing of the more recent algorithms (since it's covered in more detail later), and made clear that these were post-RSA. —David Eppstein (talk) 06:55, 5 February 2018 (UTC)
• "have been found by computers " -- maybe have been found using computers?
  • Reworded. —David Eppstein (talk) 06:55, 5 February 2018 (UTC)
• "Plato, Aristotle, Euclid, and a majority of the other Greek mathematicians" -- are Plato and Aristotle considered mathematicians in the scholarly literature?
  • I removed Plato and Aristotle since I think nowadays we care more about what the mathematicians of that day thought about mathematics than the philosophers. —David Eppstein (talk) 07:00, 5 February 2018 (UTC)
• It is entirely clear to me that Euler didn't consider 1 a prime, since otherwise the Euler products fail. I keep wondering: how did "serious" mathematicians after Euler continue to assume 1 is a prime? I can imagine that the search of certain fancy categories of prime numbers gives little relevance to the primeness of 1. This comment might not be fully actionable, but somehow I am left unsatisfied by the section. Maybe it is possible to delineate more clearly in which parts of number theory the primality of 1 plays a role?
  • Our article states a pretty clear path for this in its description of how to handle the fundamental theorem: just talk about "primes greater than one" where today we would say "primes", listing 1 as prime for form's sake but then not really considering it. It's not really different in principle from what we do when we talk about the nontrivial zeros of the zeta function, say, listing the even negative integers as zeros for form's sake (because historically we use zeta and not some other reformulation that eliminates those zeros) but only really paying attention to the other zeros. —David Eppstein (talk) 20:08, 4 February 2018 (UTC)

Yes, OK, maybe I am asking for something unreasonable.

Anyway, to me, your argument makes it pretty clear that the primality of one is maybe not too relevant, since it can always be excluded at the expense of adding "greater than 1" throughout. Do we really want to spend this much space on the discussion of primality of 1? (Imagine a whole long subsection in Riemann hypothesis devoted to discussing whether the RH was first formulated for zeta(s), then later for the completed zeta-function?) Jakob.scholbach (talk) 21:33, 4 February 2018 (UTC)

I think we do want to spend the space, because it's the sort of question beginning students are likely to want to know. For instance, it seems to be a frequent topic in lower-level textbooks (lower-level than I've been trying to use as sources here): [1] [2] [3]. —David Eppstein (talk) 04:49, 5 February 2018 (UTC)

OK, thanks for these links. (I doubt, though, that beginning students will want (or need) to know about the historical ramifications of this point in this level of detail.) While I still disagree, I respect your editorial choice -- let's leave it as is for now. Jakob.scholbach (talk) 08:10, 5 February 2018 (UTC)

Number of primes

All comments addressed Jakob.scholbach (talk) 12:59, 13 February 2018 (UTC)

• Is there a section title which makes the infinitude of primes immediate (and maybe also avoids the word "number" appearing twice)?
  • Renamed as "Infiniteness". —David Eppstein (talk) 21:45, 31 January 2018 (UTC)
• We could refer up to the fundamental theorem when discussing the prime factorization of N.
  • Done. —David Eppstein (talk) 18:16, 1 February 2018 (UTC)
• The section on Euclid should be reworked to make it more accessible (a ten-year old kid should be able to read this §): currently, the words "equivalently", "finite set", the product notation in Euclid's section should be avoided. The space needed for these explanations can be afforded by removing "It is often erroneously reported ..." -- this rather belongs to the subarticle.
  • Done, mostly by Purgy Purgatorio. —David Eppstein (talk) 18:16, 1 February 2018 (UTC)
• Euler: the term partial sum could be avoided. Since we (rightfully) don't talk about the series \sum 1 / p, I would just omit the term altogether.
  • Done. I also removed the part about the growth rate being doubly logarithmic as unnecessary technical detail, and just left the pointer to the Mertens article where the growth rate is described. —David Eppstein (talk) 18:28, 1 February 2018 (UTC)
• "For any arbitrary ..." -- it is not clear from the wording that this statement is not obvious (i.e., must be believed at this point). Again, this could be more welcoming: something like: while the terms 1 / p get smaller and smaller, the sums S(p) surpass any given threshold x, but one needs more and more primes p to do so (just sketching).
  • I added "Euler showed that" at the start of the sentence, to clarify that it needs a proof that we are not supplying. —David Eppstein (talk) 18:28, 1 February 2018 (UTC)
• "occur more often" -- maybe clarify that both sets are infinite, but primes are "more dense" or the like? Jakob.scholbach (talk) 20:45, 31 January 2018 (UTC)
  • Added "although both sets are infinite". —David Eppstein (talk) 18:28, 1 February 2018 (UTC)

Computation

All comments addressed Jakob.scholbach (talk) 12:55, 13 February 2018 (UTC)

• Is there a more meaningful title than "computation"?
  • Would you prefer "Algorithms"? If so I'd be happy to make that change. But I think that's a little more technical, something we were trying to avoid. —David Eppstein (talk) 04:11, 4 February 2018 (UTC)

Hm, "Algorithms" sounds reasonable as well, but is kind of unspecific. How about "Testing primeness and factorization into primes"? ("Factorization" is even more technical, I agree, than "computation", but the first sentence in the intro could say what it means. As the article progresses, we may not be able to completely avoid technical terms, but factorization is not too bad a term, I think.) Jakob.scholbach (talk) 10:38, 4 February 2018 (UTC)

We are supposed to avoid the title of the article in section headings, but I suppose sometimes it's unavoidable. —David Eppstein (talk) 16:58, 4 February 2018 (UTC)r

• The hatnotes in the beginning of the subsections are sometimes capitalized, sometimes not.
  • I think PP fixed these. —David Eppstein (talk) 05:40, 5 February 2018 (UTC)
• Trial division: "grows too rapidly" -- do you think it is worthwile to explain this in more detail, especially in comparison to the modern methods outlined below?
  • Changed to say something about exponential growth. —David Eppstein (talk) 05:40, 5 February 2018 (UTC)
• I have a general concern about the entire section: we spend lots of space about elementary (and nearly useless) methods, and barely touch the methods that are really used. Can we find a better balance here? E.g. the sieve of E is nicely summarized in the image caption, and also discussed in a certain detail in the text itself. This could be trimmed. The more recent methods, or at least one of them, should be explained at least in a superficial way.
  • Ok, I replaced the abstract general testing algorithm and its failure probability epsilon with an explanation of Solovay–Strassen and its failure probability 1/2. Again, I phrased the algorithm in terms of divisibility not congruence, since the section explaining congruence is far below. Also I skipped over the quadratic reciprocity part very superficially. But trial division and the sieve of Eratosthenes are not useless. —David Eppstein (talk) 06:05, 5 February 2018 (UTC)

Thanks, that's the right direction, I believe. Jakob.scholbach (talk) 09:48, 6 February 2018 (UTC)

• Along these lines: "Probabilistic tests with this behavior include the Solovay–Strassen primality test and the Miller–Rabin primality test" -- this gives no additional information compared to the table below.
  • Removed. —David Eppstein (talk) 06:05, 5 February 2018 (UTC)
• "When using these methods to generate large random prime numbers" -- I am not sure how this fits into this section? From the surrounding text, the methods are used to test whether a given number is prime?
  • I added a little more to explain the connection between primality testing and random prime generation. —David Eppstein (talk) 06:10, 5 February 2018 (UTC)
• " can be tested for primality more easily" -- maybe more rapidly or efficiently?
  • Changed to "quickly" but I think the algorithms are also simpler. —David Eppstein (talk) 06:10, 5 February 2018 (UTC)
• "This is why the largest known prime has frequently been a Mersenne prime." -- the book (great that you often give the google links!) said that the largest known prime has been a Mersenne prime from 1992. Maybe add this more precise information?
  • One of the other editors did this one. —David Eppstein (talk) 06:10, 5 February 2018 (UTC)
• "The largest number to be factored" -- maybe I am lame, but I think this needs more precision: 2^n can be factored for any n?

  I think that's covered by the "by a general-purpose algorithm" clause which immediately follows. Reading off the exponent of 2^n is a special-purpose algorithm. XOR'easter (talk) 18:06, 3 February 2018 (UTC)

@XOR'easter, would you mind to check the (last?) version I provided, please? Purgy (talk) 18:36, 3 February 2018 (UTC)

OK, I am lame. Anyhow, maybe it could not hurt to clarify what "general purpose" means? Jakob.scholbach (talk) 01:47, 4 February 2018 (UTC)

Distribution

• I kind of like the quote by Zagier, but I feel it is a bit disconnected from the sequel. Can we explain better how the "growing like weed" and "almost military precision" means in more concrete terms?
  • One of the few things removed in the big reorganization. It's a poetic quote but I don't think it actually adds much meaning. —David Eppstein (talk) 01:35, 11 February 2018 (UTC)
• "The corresponding question for quadratic polynomials is less well understood." -- I think a more precise statement here could not hurt, e.g. the one later in the article "No quadratic polynomial has been proven to take infinitely many prime values."
  • Done. —David Eppstein (talk) 22:40, 17 February 2018 (UTC)
• Again, there is a (IMO) too strong emphasis on the more elementary aspects: we mention twice (!) the existence of arbitrarily long prime gaps; we also in a way explain that this argument is almost useless by pointing out that gaps occur much earlier. IMO such detailed observations about an essentially trivial point should go to the subarticle. Here, we have more important things to say.
  • Moved the elementary material elsewhere. —David Eppstein (talk) 03:20, 18 February 2018 (UTC)
• "This implies that the likelihood" -- I would say it is equivalent to it.
  • No, it's a stronger statement, because it states the constant of proportionality to be 1 rather than just that there is a constant. —David Eppstein (talk) 22:43, 17 February 2018 (UTC)
• The fact that the Li estimate is more accurate is hidden in the notation $\sim$ vs. $\approx$. Can we do better?
  • Is there a qualitative difference in the approximation that this notation was supposed to convey? They both have relative error going to zero, and we now have an illustration showing how much more rapidly it goes to zero for the better estimate. I changed both notations to $\sim$ since that's the notation we actually explain. —David Eppstein (talk) 02:43, 18 February 2018 (UTC)

OK, the new image is a good step forward. (It could use a more detailed image caption to help the uninitiated reader though. Also, can you easily add "n" as a label to the x-axis?)

I think it is worthwile to pointing out the difference between the two approximations even more poignantly by comparing, e.g. pi(10^10) to the two approximations.

Isn't that comparison what the figure does (at the data point for n=10^10)? I expanded the caption to state something about the greater accuracy of Li. But there is already an "n" as label to the x-axis — it's under the 10^15. —David Eppstein (talk) 07:40, 22 February 2018 (UTC)

• "The prime number theorem implies that the n th prime ..." -- I am not convinced it is good to disconnect this from the preceding explanation (which incidentally uses almost the same words).
  • Reordered to reconnect them, and the elementary material on gaps moved elsewhere. —David Eppstein (talk) 03:19, 18 February 2018 (UTC)
• " which happens when their greatest common divisor is one" -- I think the wording is unclear here, it should be: "which means that ..." or something which clarifies that this is the definition of the term coprime. (In the section intro we already mention the word coprime without explanation; one might move the explanatory definition up there).
  • Moved the explanation to the first instance, and also more consistently write "relatively prime" rather than mixing up both "relatively prime" and the more technical "coprime". —David Eppstein (talk) 07:44, 22 February 2018 (UTC)
• Dirichlet's theorem, in its finer form (or more generally the Cebotarev density theorem), means that asymptotically each progression a+nq has the same density of primes. The article repeatedly (in the intro and the image caption) says they have a similar number. This should be made more precise.
  • Well, taken literally, "have the same density" isn't what you want to say — it's even less informative than what's there now, because their natural density is zero. The primes and the primes-in-an-arithmetic-sequence and the squares and the powers of two all have the same density. The wording was intentionally vague in an attempt to avoid saying that specific wrong thing and remain nontechnical while still hinting at what you actually want to say, that the primes in two sequences with the same b have inverse-log densities with the same constant factor. —David Eppstein ([[User

talk:David Eppstein|talk]]) 07:56, 22 February 2018 (UTC)

OK. Jakob.scholbach (talk) 14:55, 23 February 2018 (UTC)

• I feel the section is a bit shallow: we should at least give a glimpse on how the prime number theorem is obtained. The remarkable use of (harmonic) analysis in Dirichlet's thereom is something we should convey here, I think.

• I am also not so sure that the current article structure is optimal: the organization would be much smoother, it seems, if we aligned things along their mathematical content as opposed to whether it is conjectural "knowledge" or not. I.e., it might be good to merge the Riemann hypothesis into the distribution section. This would give an opportunity to at least point to the analytic methods used in the study of primes; would allow to at least mention Dirichlet's zeta functions. What do you think?
  • I just tried a big reorganization, along lines discussed earlier: elementary/analytic/algebraic/computational/other. Better? —David Eppstein (talk) 01:35, 11 February 2018 (UTC)

Overall, I think the sectioning is a definite improvement, thank you. Due to this massive reorganization, there are now various spots which need massaging. E.g. "Euler's analytical proof" should be relabeled, since we are no longer in the Infiniteness section.

Retitled as "Analytical proof of Euclid's theorem" —David Eppstein (talk) 03:31, 18 February 2018 (UTC)

Similarly "Computational methods" opens with a discussion about the (non-)applicability of primes; this is no longer reflecting the section content. Also the intro of "Related topics" does not fully fit its contents. Probably it is necessary to carefully review the entire article to look for such inconsistencies.

[Added later:] It might make sense to move much of the comments about the (non-)existence of applications to the cryptographic protocols? Jakob.scholbach (talk) 10:24, 19 February 2018 (UTC)

It's there at the start of the computational methods section because the applications were a significant motivation for the development of the general-purpose primality testing and factorization algorithms. And also it serves to summarize the whole section. —David Eppstein (talk) 08:02, 22 February 2018 (UTC)

The elementary observation about prime gaps could be moved to "Formulas for primes" or also to "Open questions".

Moved to "Open questions". —David Eppstein (talk) 03:20, 18 February 2018 (UTC)

Fermat's theorem on p=x^2+y^2 does fit into the arithmetic progressions section, but I think it would also be a good piece of motivation for the section on Gaussian primes. Jakob.scholbach (talk) 19:43, 11 February 2018 (UTC)

Moved. —David Eppstein (talk) 08:07, 22 February 2018 (UTC)

Open questions

All comments adressed Jakob.scholbach (talk) 14:55, 23 February 2018 (UTC)

• In the § on zeta(s), it takes a long while until we arrive at an open question.
  • I added a couple introductory sentences mentioning the question.

• Is the discussion of zeta(-1) crucial to this article? The wording "is sometimes used to assign a finite value" is at least suboptimal: it leaves it unclear what "sometimes" means, and also how that assignment is actually possible. I would remove this sentence altogether.
  • The intent was to include it as an example of how the function is not the same thing as the sum, a point many sources get confused on. (I found far too many sources saying that zeta is defined as sum 1/n^s, rather than that it is an analytic function that happens to equal the sum for the values at which the sum converges.)

This is indeed important to understand, but does it belong to this article? Jakob.scholbach (talk) 10:44, 5 February 2018 (UTC)

Ok, you raise a valid point. As there is little connection to primes themselves, I removed it (and the statement about zeta having a single pole, which is similarly an important fact about zeta but not particularly connected to primes). —David Eppstein (talk) 19:50, 5 February 2018 (UTC)

• Again I am wondering about a more global reshaping of the article: would it make sense to have a section "Analytical properties" or "Analytical study of primes" or the like, beginning, say with the Basel problem (which I think fits nicely before the general discussion of zeta), then zeta(s), maybe the prime number theorem, and going on to Dirichlet's theorem, and the Green-Tao theorem? I would not go as far as making this into a criterion for the GA review, but maybe we could at least discuss the global structure here?
  • I'm far from convinced that the current structure is the right one. I don't think thinking of it as an elementary/analytic dichotomy is right, though — that misses too much of the current content. I could imagine a reorganization like (in some order, not necessarily this one)
    1. History
    2. Elementary properties
    3. Analytic properties
    4. Computational methods
    5. Abstract algebra
    6. Other

  This would at least allow grouping the connections to group theory better than where they're placed now. But some current topics (e.g. formulas for primes, or the twin prime conjecture) are not easy to classify along those lines. Is a problem elementary if it has an elementary statement even if the best methods for solving it are not? Is the prime number theorem elementary because it has an elementary proof? Is there anything analytic about the Ulam spiral?

  • • Sounds better. How about this tweak of your suggestion:
      1. Elementary algebraic aspects (Fundamental theorem; Infiniteness à la Euclid; arithmetic in Z/p; Lagrange's theorem(?))
      2. History
      3. Distribution of primes (Euler's proof of infiniteness and zeta(s); prime number thm; RH; Dirichlet; primes in quadratic functions; further conjectures (twin prime etc); formulas for primes [this one is a bit misplaced, but I think distribution is still the best umbrella we have for it])
      4. Computation [part of this needs modular arithmetic to come before] (trial division, sieve theory including additive number theory and Goldbach etc., rest [if we want to avoid Lagrange's theorem in the beginning, this would also fit in the section on the algorithms which need it])
      5. Other (Applications, generalizations, pop culture)
    • This would require a somewhat more thorough exposition of sieving and its relation to additive aspects than we currently have. The distribution section would be pretty long, but this is the only disadvantage I see right now. Jakob.scholbach (talk) 10:09, 6 February 2018 (UTC)

• The fact that the RH is one of the big open problems is not at all clear. Also, e.g. in Zagier's "50 million" article there is a nice chart showing how precise this estimate related to the RH is. Our current picture shows this also, but less interestingly in that one can barely distinguish the blue and red lines.
  • Being unable to distinguish the blue and red lines was sort of the point, I thought? Unfortunately we can't just copy Zagier's images wholesale. —David Eppstein (talk) 08:28, 7 February 2018 (UTC)

I guess this is not mandatory for the GA process, but I do think his illustration conveys more: for numbers up to 10^9, the deviation never gets more than about 600! (Deviating around ca. 5*10^6) -- this is way more precise than the pixels of the current illustration (which only goes to 10^5) can tell.

I leave it to you or anyone interested (Purgy Purgatorio, XOR'easter, what are you up to tonight?) to create an illustration using some standard software. If we don't have that illustration, it is not a big deal, but it would be kind of nice, wouldn't it? Jakob.scholbach (talk) 18:17, 7 February 2018 (UTC)

Replaced by a new image showing the (tiny) relative error. —David Eppstein (talk) 02:41, 18 February 2018 (UTC)

• I am not sure this comment is actionable, but I find the conjectures of primes in other sequences a bit odd: in some cases there is an expectation, in others there isn't. One gets no clue of how these expectation arise. Does the literature offer more rationales behind these conjectures? Also, are they really crucial? E.g. the fact that prime order groups are cyclic is just very briefly mentioned, I personally consider such aspects of primes way more important than these conjectures. (This remark also fits maybe more nicely next to some of the primality tests, I think.)
  • Based on this comment I removed this paragraph, with only a little bit moved elsewhere. I think the Fermat and Mersenne questions are somewhat important but they're both covered in more detail elsewhere (constructible polygons and large primes, respectively). Wieferich used to have some importance in connection with Fermat's last theorem but has become less relevant, the Euclid numbers are again mentioned in the large prime section. That leaves the Fibonacci prime and super-primes which I agree are unimportant and are really only mentioned here as an excuse to link to some related articles. As for where these expectations arise, as far as I know there are two factors behind those conjectures: (1) if we pretend primes are random numbers with the right density, then sparse sequences have O(1) expected elements and denser sequences have infinitely many (this already explains the difference between Fermat and Mersenne), and (2) sequences whose elements' factors must have a special form are likely to have more primes than the random-number hypothesis would suggest (this is true for both Mersenne and Fermat, but apparently doesn't make enough of a difference to make the expected number of Fermat primes become non-constant). But this reasoning belongs in the articles on those sequences, I think, not so much here. —David Eppstein (talk) 08:26, 7 February 2018 (UTC)

OK, thanks for explaining. The next paragraph starts with "A third group", this should be massaged. Jakob.scholbach (talk) 18:17, 7 February 2018 (UTC)

I think XOR'easter fixed this at some point. —David Eppstein (talk) 22:49, 17 February 2018 (UTC)

• "prime gaps up to n" -- does this mean primes p <= n?
  • Yes, although the "approximately" here hides log factors so it wouldn't make any difference if it meant the nth prime. Clarified, anyway. —David Eppstein (talk) 08:05, 7 February 2018 (UTC)
• Around the Hardy–Littlewood conjecture, I think it would be nice to convey the heuristics behind the conjectures.
  • Done. —David Eppstein (talk) 22:48, 17 February 2018 (UTC)

Applications

All comments adressed Jakob.scholbach (talk) 14:46, 23 February 2018 (UTC)

• "including abstract algebra and elementary geometry." -- what applications in elementary geometry are these? If this is about Gauss' theorem concerning constructibility of n-gons, I would rather call this a place where primes occur, but not so much an application.
  • Removed the whole sentence as not relevant for the surrounding context. —David Eppstein (talk) 08:17, 22 February 2018 (UTC)
• There is a break of text flow: 1) primes have no application outside maths, 2) they have applications in abstract algebra 3) they do have applications.
  • I reordered the first paragraph. XOR'easter (talk) 02:29, 7 February 2018 (UTC)

Thanks, but not good yet: as a first sentence, "Prime numbers have many applications to other areas within mathematics" should be rounded off (what are "other" areas if "the one" area is not specified?); also the following sentence does not blend in well. Jakob.scholbach (talk) 18:56, 7 February 2018 (UTC)

As stated above, this first sentence is gone now. —David Eppstein (talk) 08:17, 22 February 2018 (UTC)

• Maybe a picture with prime numbered gear teeth would fit nicely here?
  • Added. —David Eppstein (talk) 05:30, 5 February 2018 (UTC)
• "We write that" -- avoid we.
  • Fixed by XOR'easter. —David Eppstein (talk) 05:32, 5 February 2018 (UTC)
• "division is not as easy to define as the other operations" -- I would directly say it is not possible, maybe illustrate with n = 6.
  • Took out that transitional sentence and added the mod 6 example. —David Eppstein (talk) 22:46, 5 February 2018 (UTC)
• "In a similar theory, a polygon may be constructed ..." -- I don't understand this sentence (without looking into subarticles): what does "its prime factors" refer to? The number of edges?

  I reworked that line a bit (though some copy-and-paste weirdness in the Visual Editor put in an invisible wiki-link, which David Eppstein fixed). XOR'easter (talk) 21:47, 4 February 2018 (UTC)

• Do you think it makes sense to explain Diffie-Hellmann or RSA in a bit more detail? E.g. the point that the arithmetic is happening in Z/p or Z/p^x would be notable in connection to this article.
  • The images I've seen trying to explain D-H simply (e.g. [4] do not look so simple to me, especially when one factors in trying to explain what it means to be a cryptographic protocol, who the participants are, what they know and don't know, etc. And RSA does its arithmetic modulo a composite; the primes show up only more subtly in being able to compute its totient. —David Eppstein (talk) 08:20, 12 February 2018 (UTC)

I wasn't necessarily thinking of a complete explanation of Alice and Bob etc., but of explaining in a bit more detail (2, 3 lines) what modular exponentiation is and the discrete log. The point of contact with this article is of course that all this happens in Z/p (or Z/p^x). Conveying the bit of information that computations in Z/p have a practical impact would be a reasonable goal of this snippet, IMO. Jakob.scholbach (talk) 11:59, 14 February 2018 (UTC)

But the computations in question (modular exponentiation) don't depend in any way on the modulus being prime. Primality goes into the security of the algorithm (the fact that it generates the entire key space and is harder to attack than modular exponentiation mod a composite). —David Eppstein (talk) 08:36, 22 February 2018 (UTC)

• The part about illegal primes strikes me as a bit funny: this "application" consists of avoiding legal hassle because you can say "hey, this is a prime"? In my mind it makes more sense to say a little more on the real applications, such as the cryptography protocols.
  • Yeah, that's mostly there for entertainment value; there's not much deep there other than that the primes are reasonably dense and you can test primality for big enough numbers. It can go if you think it would be better removed. —David Eppstein (talk) 08:46, 11 February 2018 (UTC)

I believe its relevance is epsilon compared to, say, the cryptographic protocols. Spending these 3 lines on Diffie-Hellman or RSA or more generally on emphasizing the practical relevance of modular arithmetic modulo p strikes me as a better plan. Jakob.scholbach (talk) 11:59, 14 February 2018 (UTC)

Ok, I'm still not convinced about how to expand the cryptography but that should be irrelevant to the cost-benefit of keeping the illegal prime material. Removed as having too big a cost (in increased article length) for its benefit. —David Eppstein (talk) 20:59, 22 February 2018 (UTC)

Generalizations

All comments adressed Jakob.scholbach (talk) 14:55, 23 February 2018 (UTC)

• Again, I'd love some pictures! Maybe a non-prime knot?

• • Done. —David Eppstein (talk) 06:31, 9 February 2018 (UTC)
• Can we offer an illustration for the Gaussian primes? Including the splitting of 2 = (1+i)(1-i)? And maybe also relate this discussion to the decomposition of primes into sums of squares? (We have it somewhere else, I don't find it right now).
  • I added an illustration but it doesn't particularly show the splitting. Nothing like that seems to exist in Commons:Category:Gaussian integers, which is where I would expect to find it. I found a few other images of the Gaussian primes and added them to the category, but maybe I missed something. Unless you mean File:Spec Zi.png, which is probably not understandable by people who haven't seen such diagrams before without some explanation. —David Eppstein (talk) 06:31, 9 February 2018 (UTC)

Why not File:Gauss_prime_numbers.svg? It lists the primes in a way which is closer to the text (the a+ib is completely missing in the black-dots-picture we have right now). In the image caption we could briefly allude to the splitting of 2 and relate it to the question of writing p = x^2 + y^2. Jakob.scholbach (talk) 12:41, 9 February 2018 (UTC)

Because it's illegible at any reasonable size? —David Eppstein (talk) 16:37, 9 February 2018 (UTC)

That's right, I take suggestion back.

The current one is not so much better, though: the points are clearly discernible, but their meaning is unclear without a longer explanation of the image content. Jakob.scholbach (talk) 23:36, 10 February 2018 (UTC)

• I enjoy reading the section on Prime ideals, but I believe only since I already know its content. To simplify the transition to the more advanced topics, I suggest to begin with Z[sqrt[-5]] or the like, briefly explain its non-UFD-ness (again, maybe with a picture?) and state that prime ideals are the way out.
  • Added the sqrt(-5) example. (Wouldn't a picture require too much off-topic setup to explain how complex multiplication looks geometrically?) —David Eppstein (talk) 08:11, 12 February 2018 (UTC)
• "may be viewed as geometric points" -- maybe "The spectrum of a ring R is a geometric object whose points are the prime ideals in R"?
  • Done, close to that. —David Eppstein (talk) 07:43, 12 February 2018 (UTC)
• To give the reader a little bit of a feeling, Cebotarev might be linked to Dirichlet's theorem above. The current text is correct etc., but will only mean something to people fluent in algebraic number theory.
  • Mentioned Dirichlet. This also ties into another nearby sentence about Kummer and cyclotomic integers. —David Eppstein (talk) 07:50, 12 February 2018 (UTC)
• I feel the § on valuations should precede prime ideals: the former are easier, and also less general.
  • Done in the reorganization. —David Eppstein (talk) 07:41, 12 February 2018 (UTC)
• The § on valuations is not very welcoming: I suggest beginning with the definition of |-|_p or v_p(-), give a mini-example. Then the product formula, briefly link it to local-global principle. Then state the existence of Q_p, Ostrowski. Finally talk about places etc. (I am not sure places are actually a must in this article.)
  • Reordered. —David Eppstein (talk) 18:52, 22 February 2018 (UTC)
• The § on valuations could be renamed "p-adic numbers", to make the connection to primes more apparent from the title already.
  • Done in the reorganization. —David Eppstein (talk) 08:47, 11 February 2018 (UTC)

In games ...

• The text itself is fine, but where do "games" appear in it?

  I removed "games" from the section title. XOR'easter (talk) 19:46, 8 February 2018 (UTC)

References

• Magnificent! One minor typo: "GrrlScientist".

  That's not a typo [5]. XOR'easter (talk) 19:42, 8 February 2018 (UTC)

Conclusion

I am happy to pass this good article nomination. Kudos and thanks to David Eppstein for his tireless work! If this article is going to be an FA nominee in the future, I think a fresh look, in particular with regard to the recent massive reorganization, would be helpful. Also, in certain spots I think the article could be made yet more welcoming / entertaining to non-specialists, but this is well beyond the GA criteria. Jakob.scholbach (talk) 14:55, 23 February 2018 (UTC)