Is the notorious n2+n+41n^2 + n + 41 prime generator the last of its type?

The polynomial n2+n+41 famously takes prime values for all 0n<40. I have read that this is closely related to the fact that 163 is a Heegner number, although I don’t understand the argument, except that the discriminant of n2+n+41 is 163. The next smaller Heegner number is 67, and indeed n2+n+17 shows the same behavior, taking prime values for 0n<16.

But 163 is the largest Heegner number, which suggests that this is the last such coincidence, and that there might not be any k>41 such that n2+n+k takes on an unbroken sequence of prime values.

Is this indeed the case? If not, why not?

Secondarily, is there a k>41, perhaps extremely large, such that n2+n+k takes on prime values for 0<n<j for some j>39?

Answer

See http://en.wikipedia.org/wiki/Heegner_number#Consecutive_primes

Here is a longer piece Rabinowitz published on the topic below

Rabinowitz showed, in 1913, that x2+x+p represent the maximal number of consecutive primes if and only if x2+xy+py2 is the only (equivalence class of) positive binary quadratic form of its discriminant. This condition is called "class number one." For negative discriminants the set of such discriminants is finite, called Heegner numbers.

Note that if we take x2+x+ab so that the constant term is composite, we get composite outcome both for x=a and x=b, so the thing quits early. In the terms of Rabinowitz, we would also have the form ax2+xy+by2, which would be a distinct "class" in the same discriminant, thus violating class number one. So it all fits together. That is, it is "reduced" if 0<ab, and distinct from the principal form if also a>1.

For binary forms, I particularly like Buell, here is his page about class number one: BUELL. He does everything in terms of binary forms, but he also gives the relationship with quadratic fields. Furthermore, he allows both positive and indefinite forms, finally he allows odd b in ax2+bxy+cy2. Note that I have often answered MSE questions about ideals in quadratic fields with these techniques, which are, quite simply, easy. Plus he shows the right way to do Pell's equation and variants as algorithms, which people often seem to misunderstand. Here I mean Lagrange's method mostly.

EEDDIITT: I decided to figure out the easier direction of the Rabinowitz result in my own language. So, we begin with the principal form, 1,1,p with some prime p3. It follows that 2p4p1 and
p2p12.
Now, suppose we have another, distinct, reduced form of the same discriminant,
a,b,c. There is no loss of generality in demanding b>0. So reduced means 1bac with b odd, both a,c2, and
4acb2=4p1. As b2ac, we find 3b24p1 and, as p is positive,
bp.

Now, define b=2β+1 or β=b12. From earlier we have
βp2.
However, from 4acb2=4p1 we get 4ac+1=b2+4p, then
4ac+1=4β2+4β+1+4p, then 4ac=4β2+4β+4p, then
ac=β2+β+p,
with 0βp2. That is, the presence of a second equivalence class of forms has forced x2+x+p to represent a composite number (ac) with a small value x=βp2, thereby interrupting the supposed sequence of primes.

EEDDIITTEEDDIITT: I should point out that the discriminants in question must actually be field discriminants, certain things must be squarefree. If I start with x2+x+7, the related x2+xy+7y2 of discriminant 27 is of class number one, but there is the imprimitive form 3,3,3 with the same discriminant. Then, as above, we see that x2+x+7=9 with x=1=(31)/2.

[ Rabinowitz, G. “Eindeutigkeit der Zerlegung in Primzahlfaktoren in quadratischen Zahlkörpern.” Proc. Fifth Internat. Congress Math. (Cambridge) 1, 418-421, 1913. ]

Edit October 30, 2013. Somebody asked at deleted question
Smallest positive integer n s.t. f(n) = n2+n+41 is composite?
about the other direction in Rabinowitz (1913), and a little fiddling revealed that I also know how to do that. We have a positive principal form 1,1,p where Δ=4p1 is also prime. Otherwise there is a second genus unless Δ=27 or Δ=343 or similar prime power, which is a problem I am going to ignore; our discriminant is minus a prime, Δ=14p.

We are interested in the possibility that n2+n+p is composite for 0np2. If so, let q be the smallest prime that divides such a composite number. We have n^2 + n + p \equiv 0 \pmod q. This means (2n+1)^2 \equiv \Delta \pmod q, so we know \Delta is a quadratic residue. Next n^2 + n + p \leq (p-1)^2 + 1. So, the smallest prime factor is smaller than p-1, and q < p, so q < - \Delta.

Let's see, the two roots of n^2 + n + p \pmod q add up to q-1. One may confirm that if m = q-1-n, then m^2 + m + p \equiv 0 \pmod q. However, we cannot have n = (q-1)/2 with n^2 + n + p \pmod q, because that implies \Delta \equiv 0 \pmod q, and we were careful to make - \Delta prime, with q < - \Delta. Therefore there are two distinct values of n \pmod q, the two values add to q-1. As a result, there is a value of n with n^2 + n + p \equiv 0 \pmod q and n < \frac{q-1}{2}.

Using the change of variable matrix

\left(
\begin{array}{cc}
1 & n \\
0 & 1
\end{array}\right)

written on the right, we find that
\langle 1,1,p \rangle \sim \langle 1,2n+1,qs \rangle
where n^2 + n + p = q s, with 2n+1 < q and q \leq s. As a result, the new form
\langle q,2n+1,s \rangle
is of the same discriminant but is already reduced, and is therefore not equivalent to the principal form. Thus, the class number is larger than one.

Attribution
Source : Link , Question Author : MJD , Answer Author : Community

Leave a Comment