44
$\begingroup$

This is an elementary question about something way outside my area of expertise. A well-known observation due to Euler is that the polynomial $P(x)=x^2+x+41$ takes on only prime values for the first 40 integer values of $x$ starting with $x=0$, namely the values $41,43,47,53,61,71,83,\cdots,1601$. In particular this gives a rather long sequence of primes such that the differences between successive terms form an arithmetic progression, namely $2,4,6,\cdots$, which is a consequence of $P(x)$ being quadratic. All this is related to the fact that the discriminant of $x^2+x+41$ is $-163$ and the field ${\mathbb Q}(\sqrt{-163})$ has class number 1.

Suppose one asks about the next 40 values of $P(x)$ after the value $P(40)=41^2$. We have $P(41)=1763=41\cdot 43$, also not a prime. After this the next two values $P(42)=1847$ and $P(43)=1933 $ are primes. Then comes $P(44)=2021=43\cdot 47$, then four primes, then $P(49)=2491=47\cdot 53$, then six primes, then $P(56)=3233=53\cdot 61$, then eight primes, then $P(65)=4331=61\cdot 71$, then ten primes, then $P(76)=5893=71\cdot 83$. The next four values are prime as well for $x=77,\ 78,\ 79,\ 80$, completing the second forty values. But then the pattern breaks down and one has $P(81)=6683=41\cdot 163$. Thus, before the breakdown, not only do we get sequences of $2,\ 4,\ 6,\ 8,\ 10$ primes but the non-prime values are the products of two successive terms in the original sequence of prime values $41,\ 43,\ 47,\ 53,\ 61,\ \cdots$. There is a simple explanation for this last fact, the easily-verified identity $P(40+n^2)=P(n-1)P(n)$, so when $n=1,2,3,\cdots$ we get $P(41)=P(0)P(1)=41\cdot 43$, $P(44)=P(1)P(2)=43\cdot47$, etc. However, this does not explain why the intervening values of $P(x)$ should be prime.

I've done an online search to find where this might be discussed, without success, so my question is, what is a reference for this curious behavior of the second 40 values of $P(x)$ (or anything related)? I'm also a little puzzled by the identity for $P(40+x^2)$, though perhaps it comes from the norm function in ${\mathbb Q}(\sqrt{-163})$.

$\endgroup$
  • 3
    $\begingroup$ A similar phenomeon occurs for $x^2+x+11$ and $x^2+x+17$ (which corresponds to $\mathbb{Q}(\sqrt{-43}).$ and $\mathbb{Q}(\sqrt{-67}).$). $\endgroup$ – LeechLattice Jun 10 '19 at 15:01
  • 14
    $\begingroup$ I was about to say that the same observation appears in page 95 of this book draft, but I just realized you wrote it! $\endgroup$ – pregunton Jun 10 '19 at 15:05
  • 6
    $\begingroup$ @pregunton, The 1st OP sentence, "This is an elementary question about something way outside my area of expertise," combined with the existence of that book draft, certainly challenge one's perception. :) $\endgroup$ – Michael Jun 10 '19 at 17:02
  • 2
    $\begingroup$ As I look at this question, it has $41$ up-votes. If I vote for it, will a Sign from the supernatural realm be obscured by noise? Will the ghost of Douglas Adams take over supervising this question from Above? $\endgroup$ – Michael Hardy Jul 25 at 19:15
24
$\begingroup$

Let's start by recalling the classical explanation of why the values of $P(x)$ are prime for small $x$. Suppose that $K = \mathbf{Q}(\sqrt{-D})$ has class number one, and also that $D$ is squarefree and $D \equiv 3 \bmod 8$. The latter assumption is not much of an assumption; in all other cases, the prime $2$ is either split or ramified which forces the existence (under the class number one assumption) of an element of norm $2$, and thus $D = -1$, $-2$, or $-7$. The class number one assumption also implies that $D$ must be prime. The ring of integers of $K$ are given by

$$\mathbf{Z}[\theta], \qquad \theta = \frac{1 + \sqrt{-D}}{2},$$

and the norm form is

$$N( a + b \theta) = a^2 + a b + b^2 \left(\frac{1+D}{4}\right).$$

Note that

$$P(x) = N(x + \theta) = x^2 + x + \frac{1+D}{4}$$

When $D=163$, this is Euler's polynomial. Also note that if $b = 0$, then the norm is a square, and otherwise the norm is at least $(1+D)/4$.

Claim: if $p < (1+D)/4$, then $p$ is inert in $K$. If $N(\alpha)$ is divisible by $p$ in this range, then $\alpha$ is divisible by $p$.

Proof: If $p$ was split in $K$, then it would split principally, but then there would be an element of norm $p < (1+D)/4$ which is impossible. ($p$ can't ramify because $p < D$ and $D$ is the only prime which ramifies).

Since $P(n) < ((1+D)/4)^2$ for $n < (D+1)/4 - 1$, this explains why the small values of $P(n)$ are prime. So what then about the next $(D+1)/4$ range of values?

Let's start with the following:

Claim: If $D > p$ and $p$ splits in $K$, then $p = P(n)$ for some $n$.

Proof: If $p$ splits it must be a norm of $a + b \theta$ for some $b \ge 1$. But if $b \ge 2$ then $p \ge D$.

Now consider the values of $P(n)$ for the next half of the values, namely $(D-1)/2 > n$. Note that

$$P(n) < P\left(\frac{D-1}{2}\right) = \frac{D(1+D)}{4}.$$

In particular, suppose that $P(n)$ for $n$ in this range is not prime, and it had a prime divisor $\ge D$. Then it would also have a prime divisor less than $(1+D)/4$, which is a contradiction from the discussion above (any such prime divisor would be a norm). In particular, the only prime divisors (if it is not prime) are less than $D$ - but that means exactly from the previous claim that they have the shape $P(i)$ for some value of $i$. As you observe, one has

$$P(i-1) P(i) = P\left( \frac{D-3}{4} + i^2 \right) = P(P(i) - i - 1),$$ and also: $$P(i) P(i+1) = P(P(i) + i).$$

(These are not mysterious identities, they hold for any monic quadratic polynomial.) So now the question reduces to showing why these account for all non-trivial factorizations of $P(n)$

for $(D-1)/2 > n > (D+1)/4$. From above, any such factorization is of the form

$$P(n) = P(i) \cdot C$$

for some $i < (D+1)/4$ and some other factor $C$ (which then has to be of the form $P(j)$ for some $j$ but that is not relevant).

Write $P(i) = p$ which is prime. The roots of $P(x) \bmod p$ are given by $x = i \bmod p$ and $x = -1-i \bmod p$ since the sum of the roots is $-1 \bmod p$. It follows that

$$n \equiv i, -1-i \bmod P(i).$$

Since $P(i) > (D+1)/4$, and $n < (D-1)/2$, the only possibilities are

$$n = P(i) - 1 - i, \quad n = P(i) + i,$$

because already one can easily check that

$$2 P(i) - 1 - i > \frac{D-1}{2} > n.$$

But now one sees that $n = P(i)+i$ or $P(i)-1-i$ lead exactly to the two factorizations above, and thus $P(n)$ in this range is prime except for the values coming from the above factorizations.

| cite | improve this answer | |
$\endgroup$
19
$\begingroup$

If $P(x)=N\left(x+\frac{1+\sqrt{-163}}{2}\right)$ (norm in $\mathbb Q(\sqrt{-163})$) was composite, it would follow $x+\frac{1+\sqrt{-163}}{2}$ is not prime, so it would factor into a product of two elements of $\mathbb Z\left[\frac{1+\sqrt{-163}}{2}\right]$. Clearly it's not divisible by any rational integer, so it is a product of some elements $a+b\frac{1+\sqrt{-163}}{2}$, which have norms $a^2+ab+41b^2$, with $b\neq 0$.

If $x$ is small, $b$ has to be small as well. Indeed, if $|b|\geq 2$, we get $a^2+ab+41b^2\geq 163$, and we find that if $x<81$, $b=\pm 1$ for both factors of $x+\frac{1+\sqrt{-163}}{2}$. By considering cases according to the signs of $b$ you see that you get imaginary part $1/2$ only in a handful of cases. One such case is $(a+\frac{1+\sqrt{-163}}{2})(a-\frac{1+\sqrt{-163}}{2})=a^2+40+\frac{1+\sqrt{-163}}{2}$. Computing the norms and using the symmetries of $P$ explains the identity $P(x^2+40)=P(x)P(x-1)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ If $P(x)= x^2+x+A$ then the identity $P(x)P(x-1) = P(x^2+A-1)$ is trivial to verify. It doesn't have anything to do with $163$. $\endgroup$ – Lucia Jun 10 '19 at 17:32
  • 1
    $\begingroup$ @Lucia Of course I agree, but it can still be seen as coming from the norm in a quadratic field. More generally, there is an identity expressing a product of two numbers of the form $x^2+xy+Ay^2$ as another such number, which is most easily derived by looking at the form in the quadratic field $\mathbb Q(\sqrt{1-4A})$ whenever $A$ is an integer. Of course, just like the $P$ identity, the resulting identity can be immediately seen to be true algebraically, but I still think it's nice to observe that it can be explained in terms of norms (like the OP was suspecting). $\endgroup$ – Wojowu Jun 10 '19 at 18:17
12
$\begingroup$

Here is a completely elementary and very simple proof.

With the identity $P(A+m^2-1)=P(m-1)P(m)$ in mind, it suffices to prove that if$P(x):=x^2+x+A$ is prime for all $x\in[0,A-2]$, while $P(A+k)$ is composite for some $k\in[1,A-2]$, then $k+1$ is a complete square.

Let $p$ be the smallest prime divisor of $P(A+k)$. If we had $p<A$, then for a suitable integer $s$ we would have $A+k-sp\in[0,A-2]$, which along with $P(A+k-sp)\equiv P(A+k)\equiv 0\pmod p$ would give $p=P(A+k-sp)>A$, a contradiction.

Thus, $p\ge A$. On the other hand, $p^2\le P(A+k)<(A+k+1)^2$, implying $p\le A+k$. As a result, $0\le A+k-p\le k\le A-2$. Consequently, \begin{align*} p &= P(A+k-p) \\ &= (A+k-p)^2+(A+k-p)+A \\ &= (A+k-p+1)^2 + p - k -1, \end{align*} whence $k+1=(A+k-p+1)^2$.


For completeness, here is an elementary proof that if $P(x):=x^2+x+A$ is prime for all $0\le x<\sqrt{A/3}$, then in fact $P(x)$ is prime for all $0\le x\le A-2$. (Incidentally, this is Problem 6 of the 1987 International Math Olympiad.)

Let $k$ be the smallest non-negative integer such that $k^2+k+A$ is composite, and suppose for a contradiction that $\sqrt{A/3}<k\le A-2$. Denoting by $p$ the smallest prime divisor of $k^2+k+A$, we thus have $p^2\le k^2+k+A<4k^2+k$, whence $p\le 2k-1$. Indeed, $p\le k$: otherwise from $$(p-k-1)^2+(p-k-1)+A\equiv k^2+k+A\equiv 0\pmod p$$ and $$0\le p-k-1<k$$ we would obtain $p-k-1<\sqrt{A/3}$ and $(p-k-1)^2+(p-k-1)+A=p$, whence $k+1=A+(p-k-1)^2\ge A$, a contradiction. We thus conclude that $p\le k$; as a result, from $$(k-p)^2+(k-p)+A\equiv k^2+k+A\equiv 0\pmod p$$ and $$0\le k-p<k$$ we get $(k-p)^2+(k-p)+A=p$, implying $k\ge p\ge A$, a final contradiction concluding the proof.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ That was a nice proposal, Professor Vsevolod! $\endgroup$ – José Hdz. Stgo. Jun 12 '19 at 20:21
  • 1
    $\begingroup$ This problem is where I (and probably many other former olympians) first time saw your name. $\endgroup$ – Fedor Petrov Jul 25 at 15:18
11
$\begingroup$

The Rabinowitsch criterion says that the discriminant $\Delta=-163$ is not a square modulo any odd prime $p<41$, see this nice article by Pete Clark. So every prime factor of $P(x)$ must be $\geq 41$. But for the primes $p=43,47,53,\ldots$ it is easy to find the roots of $P(x)$ mod $p$, thanks to the fact that these primes are the first values of $P(x)$. For $p=43$ the roots are $\{1,-2\}$, for $p=47$ they are $\{2,-3\}$ and so on. This provides better bounds for the possible prime factors of $P(x)$ for $x>41$ and should explain your observation.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Please check my post.

It indicates that the number of divisors of $x^2+x+41$ is equal to the number of lattice points of $X^2+163Y^2-2(2x+1)Y-1=0$.

This formula is transformed in this way.

$$163X^2+163^2Y^2-2\cdot163(2x+1)Y=163$$ $$163X^2+\{163Y-(2x+1)\}^2-(2x+1)^2=163$$ $$163X^2+(163Y-2x-1)^2=4x^2+4x+164$$

$X':=163Y-2x-1,\ Y':=X$ and we divide both sides by 4,

$$\frac{{X'}^2+{163Y'}^2}{4}=x^2+x+41=P(x)$$

$$N\left(\frac{X'+Y'\sqrt{-163}}{2}\right)=P(x)$$

$\frac{X'+Y'\sqrt{-163}}{2}$ is an element of $\mathbb Q(\sqrt{-163})$.

This formula indicates that the elements of $\mathbb Q(\sqrt{-163})$ with norm $P(x)$ is linked to the product pattern of two integers of $P(x)$.

The phenomenon you are interested in is based on this fact.

For example, let $x$ be $76$.

\begin{eqnarray*} P(x)&=&76^2+76+41\\ &=&1\cdot5893\\ &=&71\cdot83 \end{eqnarray*}

The number of product pattern of $P(x)$ is $2$.

On the other hand, the elements of $\mathbb Q(\sqrt{-163})$ with norm $P(x)$ (ignore sign) are

$$\frac{153+\sqrt{-163}}{2},\ 5+6\sqrt{-163}\ .$$

The number is $2$.

The left one is a trivial element $\frac{(2x+1)+\sqrt{-163}}{2}$.The other one is a non-trivial element that indicates that $P(x)$ is a composite number.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.