Problems & Puzzles: Conjectures

Conjecture 17.  The Ludovicus conjecture about the Euler trinomials

The "Euler Trinomial" T=X^2+X+A has a specific "smallest prime divisor" for each integer A, in certain X value, when X runs for 0<=X<=infinite.

We will write in short this fact as: "SPD(T, A)=p, for X=b".

By example:

1) SPD(T,13)=3 for X=1
2) SPD(T,5)=5 for X=0

Luis Rodríguez, (self-named "Ludovicus") from Venezuela, conjectures that:

the set of SPD(T,A) values - for A & X the set of natural numbers - is the set of the prime values without one exception.

The question is far from being trivial because many A values share the same SPD, for example SPD(T,3)=3, for X=0 and SPD(T,6)=3 for X=0, SPD(T,7)=3 for X=1, SPD(T,9)=3 for X=0, SPD(T,13)=3 for X=1, and so on... So, it may happens that the set of SPD values is finite.

And the numerical evidence is also far for probing or disapproving the conjecture. In the following table we show the least known A value that exhibits each prime value as its SPD (I recalculated the A values up to 999999999, giving only a better result that the previously obtained by Luis for the prime 109):

(*) the minimal A  for the corresponding prime, calculated by Jud McCranie.
Values (new & corrected) in this color calculated by Phil Carmody.

But there is not any known A value for the following primes: 151, 157, 197, 223, 229, 233, 239, 241 y 269

Incidentally, it happens - as Luis Rodríguez noted - that for each A, the X value where emerges its SPD(T,A), is such that b<SPD(T,A)/2, but there is not know reason for that.

One last Rodríguez's observation is that for A=>11 all the A least values end or in 1 or in 7.

Questions:

a) Can you prove or disapprove the Luis Rodríguez's conjecture?
b) Can you get the unknown smallest A values for the following primes 151, 157, 197, 223, 229, 233, 239, 241 y 269 as SPD?
c) Can you improve the A values for p=>113
d) Can you explain why b<SPD(T,A)/2
e) Can you argue why for A=>11 the ending digit for A is or "1" or "7" (that is to say why A  does not ends in "3" or "9", the only other ending possibilities)

Notes:
There are only six A values such that SPD(T,A)=A. These are named - after Le Lionnais - the "Euler Lucky numbers": A=2, 3, 5, 11, 17 & 41. After A=41 it never happens again that SPD(T,A)=A. Any idea why?

References given by Luis Rodríguez:
1) Lukes, Patterson y Williams, ´Numerical Sieving Devices, his History and some Applications´ Neuew Archief voor Wiskunde Vol 13 No 1, 1995
2) Quadratic Polynomials with High Density of Primes´. FUNG & WILLIAMS Mathematics of Computation No 53 - 1990.

Solution

Jud McCranie has obtained the true minimal A's for several (3) primes (113, 131, 137), and he has also found the minimal (unknown) A for two new primes: 151 & 157. See Table above. His search is running still...

***

Chris Nash has solved (12/02/2000) the Ludovicus Conjecture, showing that positively exist an A value for each p, such that A<p#. Base in the proof discovered he answer also the rest of the questions, in particular showing a method to tackle the b) & c) items. Chris is currently running a code that uses his method to solve the remaining A unknown values for the primes:197, 223, 229, 233, 239, 241 y 269.

"I have a proof of the Ludovicus conjecture 17 - in fact I am surprised nobody has attempted it yet.

Part (a)

Luis Rodriguez claims that the set SPD(T,A) covers all primes. To prove it, it is sufficient to construct a value A for each prime p, such that i) X^2+X+A is never divisible by any prime smaller than p;ii) X^2+X+A is divisible by p for some value of X.

The proof is as follows. Consider a prime q, and the values of X^2+X mod q. If q=2, X^2+X is always divisible by 2. Hence X^2+X takes the value {0] mod 2.

For any odd prime, let S(q) be the set of values of X^2+X mod q. I claim S(q) has precisely (q+1)/2 members. For if X^2+X=s mod q 4X^2+4X+1=4s+1 mod q

The left hand side is (2X+1)^2, hence must be zero or a non-zero quadratic residue mod q, hence it takes 1+(q-1)/2 possible distinct values. Each leads to a solution for s, and thus S(q) has precisely (q+1)/2 members.

Now the proof. It is sufficient to choose A such that -A mod q is not in S(q) for all primes q less than p. And to choose A such that -A mod p is a member of S(p). For an odd prime p, there is at least one solution to each of these congruences. By the Chinese Remainder theorem, there is thus at least one value of A less than p# which satisfies SPD(T,A)=p.

Perhaps an example would be good. I was surprised SPD(T,A)=7 has such a large solution. We have S(2)={0} S(3)={0,2} S(5)={0,1,2} S(7)={0,2,5,6} And so there are 1*1*2*4=8 solutions to SPD(T,A)=7 for A<210, we need to solve

A=1 mod 2
A=2 mod 3
A=1 or 2 mod 5
A=0 or 1 or 2 or 5 mod 7

The smallest solution is indeed 47.

Parts (b) and (c)

The proof is constructional, hence for any prime p it is sufficient to construct the list of conguences modulo all primes up to and including p, and solve all possible permutations. The solution for each p is certainly less than p#.

Note however that since (approximately) half of the values of A are possible modulo each congruence, we expect 2^n possible solutions for the n'th prime (in fact, the actual value is a little smaller than that), and we may expect the smallest solution to be about p#/2^n (which is in fact approximately (e/2)^n).

However the number of permutations of these solutions soon becomes very large. (It is very like the method of 'covering sets' used in the Sierpinski and Brier constructions). Fortunately it is possible to quickly sieve the value of A. I do not propose any solutions to these parts, just those hints for searching :)

Part (d)

Is b<SPD(T,A)/2, where b is the value of X at which SPD(T,A)=p appears as a factor? Yes. It is sufficient to prove that X^2+X takes all (p+1)/2 values of S(p) in the range 0<=X<=(p-1)/2. That is quite easy using quadratic residues but here is a more direct proof. We show those (p+1)/2 values of X^2+X are distinct. Assume 0<=Y<X<=(p-1)/2, and X^2+X=Y^2+Y mod p, so X^2-Y^2+X-Y=0 mod p, (X-Y)(X+Y+1)=0 mod p

We are forced to conclude either X-Y=0 mod p or X+Y+1=0 mod p. Both are a contradiction. Hence the (p+1)/2 distinct values of X^2+X+A mod p are taken in the terms X=0 thru X=(p-1)/2. In particular b<SPD(T,A)/2.

Part (e)

Why for A>11 is the ending digit 1 or 7? We have S(2)={0} S(5)={0,1,2} and hence, in order for no member of X^2+X+A to be divisible by 2 or 5 we require

A=1 mod 2
A=1 or 2 mod 5

Hence A=1 or 7 mod 10.

Finally

You mention Euler's 2, 3, 5, 11, 17, 41 as the only values where SPD(T,A)=A (in the small print). This list is indeed complete. I will attempt briefly explain, it is to do with 'class number theory', which essentially explains how 'uniqueness of factorization' fails in number systems other than the integers.

Let Y=X^2+X+A. As before we write 4Y=4X^2+4X+4A=(2X+1)^2-(1-4A). We aim to factor Y. Write d=1-4A. If we add a=sqrt(d) to our number system, we have an obvious factorization of 4Y as a difference of two squares:

4Y=(2X+1)^2-a^2=(2X+1-a)(2X+1+a) (*)

In the integers we often use the fundamental theorem of arithmetic - if a prime p divides the left hand side of this equation, it must divide one of the factors on the right. Does a similar definition of prime exist in this number system with the imaginary number a? The answer is, no, not always. (Kummer fixed this by introducing the notion of 'prime ideals' and Gauss considered the 'class number' h(d) to be how non-unique the factorization is).

There are only six negative values of d with h(d)=1 (i.e. where uniqueness of factorization still holds). They correspond precisely to the six Euler numbers and it's been proven they are the only six. For our purposes, it's sufficient to state that, because (*) is not necessarily unique for other A values, there is a corresponding 'alternative' factorization of 4Y - in other words Y is composite, for some value of X less than A (and hence must have a factor less than A, and so SPD(T,A) must be less than A).

Hope this helps!

****
Phil Carmody - working in a test of sieving code of his own - found (22/4/01) more results pertinent for this conjecture. They have been added to the table above, eliminating the unknown minimal A values for the primes 197, 233, 239, 241. He also notes two typos in the A values given by Rodríguez for the primes 211 & 227.

In this very moment the unknown least A values are only for the primes below 281 are: 223, 229 & 269, and none for a prime larger than 281.

***

Luis Rodríguez noticed that the A solution for the prime 241 is not correct. Carmody has confirmed (24/4/01) that  as a matter of fact "it was a bad one..." result. Then, below 281 we have still 4 unknown primes unsolved.

***

Three days later Carmody came up with new and better results!, Here is his email (27/4/01):

"Hi Carlos, I'm pleased to have some new results for you:

2944970554938947 : 223 divisor
7736679448281671 : 229 divisor
33239521957671707 : 257 divisor
57991585459229687 : 241 divisor

The 223 and 229 result I had in the past, just didn't realize! The 241 is a real result this time! The 257 is lower than what you currently have and is minimal. I can also confirm that all the results you now have >150 and <=263 are minimal. The list of wanted SRPs is now only 269 and >281. The hunt continues."