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 least A for a certain new  SPD(T,A) X=b SPD(T,A)=p 2 0 2 3 0 3 5 0 5 11 0 11 17 0 17 41 0 41 47 1 7 221 0 13 941 1 23 1217 7 19 2747 13 29 8081 8 31 9281 2 37 19421 16 47 55661 10 43 333491 21 53 601037 15 61 1262201 28 59 5237651 18 67 9063641 2 71 12899891 3 73 24073871 5 83 26149427 24 79 28537121 21 89 67374467 47 107 146452961 20 109 160834691 39 103 352031501 34 97 398878547 32 101 From here on values are provided and calculated only by Luis Rodríguez, not necessarily the least values!!! 1137972888897 (*)24169417397 26 51 113 13236860171 41 127 557117821697 (*)17959429571 63 63 131 91766156208737 (*)68962024247 48 31 137 57391479317 53 139 143882037107 74 149 From here on the values are provided by Luis Rodríguez, taken from the given references, not necessarily the least values!!! (*)436857844727 64 151 (*)619919883881 69 157 1266645025817 80 163 358204454087 5 167 1694704300631 10 173 4125444938831 59 179 185526075673377 20 181 7514981191031 74 191 94621748329721 94 193 1058690153381297 5 197 27646977664127 8 199 1077881853647981 96 211 2944970554938947 46 223 2618101778697017 36 227 7736679448281671 44 229 6230021315870771 9 233 11703458947939931 116 239 57991585459229687 0 241 5565451343405111 8 251 33239521957671707 105 257 110474750554698347 50 263 The most wanted! ? 269 569627439464847077 10 271 1423557568911254741 116 277 2457080965043150051 120 281

(*) 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."

***

Liu Fengsui from China sent (1/5/01) the following email, according to which he has found another solution to this conjecture and provides another algorithm to calculate the A values.

Dear Carlos Rivera:

I sent the post “A weaker conjecture of prime k-tuples”(01-4-18,primenumbers@yahoogroups.com) to enhance and improve your anthology. Please referrer and comment it.

The post may be a little contribution for the conjecture 3#. But Micheal Bell hinted it is another solution for the

Regards.    Liu Fengsui.

A weaker conjecture of prime k-tuples.

With an algorithm I elementarily proved a weaker conjecture of prime k-tuples:

Given random integer k>0, for every integer n>1 there exists an integer a such that all primes p<pn does not divide  x^2 - x + a  for  x = 0,1,...,k.

Let   A = <a1, a2,...,ai,...,an>  be the finite set of natural numbers.

If       A = <a1,a2,...,ai,...,an>  ,   B = <b1,b2,...,bj,...bm>,

We define    A + B = <a1+b1,a2+b1,...,ai+bj,...,a[n-1]+bm, an+bm>,

A * B = <a1*b1,a2*b1,...,ai*bj,...,a[n-1]*bm, an*bm>.

We define the solution of the system of congruencies

X =  <a1,a2,...,ai,...,an>  mod a,

X =  <b1,b2,...,bj,...bm>  mod b

be            X =  D = <d[1,1],d[2,1],...,d[i,j],...,d[n-1,m],d[n,m]>  mod ab.

where  x = d[i, j]  mod ab is the solution of the system of congruencies

x =  ai   mod a    ,    x = bj   mod b.

Let   pn  be n-th prime ,     P0 = 2.

For random prime pi > 2, we consider the set

Bi = {a: pi | x^2 - x + a for some 0<=x<=k }

= {a: x^2 -x + a = 0 mod pi for some 0<=x<=k }.

By  (pi +1 - x)^2 - (pi +1 -x ) =(pi + 1 -x)*(pi - x) =x^2 - x  mod pi, it is easy to prove that, in the congruence   x^2 -x + a = 0 mod pi , when  x  runs through the complete system mod pi , a runs through the classes of residues  <0,-2,-6,...,(pi+1)/2 – ((pi+1)^2)/4> mod  pi. Thus the set  Bi  are the classes of residues:

Bi = <0,-2,-6,..., (pi+1)/2 – ((pi+1)^2)/4> mod  pi , (pi+1)/2<= k.

Bi = <0,-2,-6,..., k - k^2>   mod pi,       (pi+1)/2 > k.

For example, let k = 4 , the first few terms of the sets  Bi  are

B1 = <0,-2> = <0,1>      mod  3,

B2 =<0,-2,-6> =<0,3,4>    mod 5,

B3 = <0,-2,-6,-12> = <0,5,1,2>    mod  7,

B4 = < 0,-2,-6,-12> = <0,9,5,10>  mod 11.

Let  m[n+1] = p0*p1*...*pn, from the set of all odd numbers  X = <1>  mod 2  we cancel the classes  B1,B2,...,Bn  successively, and obtain the class  T[n+1]  mod  m[n+1]  such that

T[n+1] = {a: x^2 - x + a =/= 0 mod pi, for x = 0,1,2,...,k and pi = p1,p2,...,pn}.

Then the recursive formula of T[n+1], which is the set of non- negative representatives mod  m{n+1]  is as follows:

T1 = <1>,

T[n+1] = (<Tn  +<mn>*<0,1,2,...,pn-1> \ Dn

where         X = Dn  mod m[n+1]  is the solution of the system of congruencies

X = Tn  mod  mn,

X = Bn  mod pn.

For example, let  k = 4 , the first few terms of  T[n+1]  are

T1 = <1>,

T2 = (<1>+<0,2,4>) \ <1,3> = <5>,

T3 = (<5> + <0,6,12,18,24>) \ <5,23,25> = <11,17>,

T4 = (<11,17>+,0,30,60,...,180> \ <47,71,77,107,131,,161,191>

=  <11,17,41,101,137,167>.

Given random integer k>1, take an integer  s  such that

(ps+1)/2<=k<(p[s+1]+1)/2,

then the number of all elements of the set  T[n+1] is

| T[n+1] | = (p1-1)/2 * (p2-1)/2 *...*(p[s+1]-k) *...*(pn-k).

Obviously,  | T[n+1] | > 0, thus we have proved the weaker conjecture of prime k-tuples with this algorithm.

Let R(k, a) denote the prime k-tuples:  x^2 - x + a  assumes prime values for   x = 0,1,2,…,k, obviously the criteria of prime k-tuples is
R(k,a)  iff   a = pn = min Tn > k-1.

This criteria R(k ,a) recursively enumerate all prime k-tuples.

Where min Tn is the smallest number of the set Tn.

As another solution For the Conjecture 17, let (pn+1)/2<= k, let A= min Dn,    | Dn | = | Tn |*(pn+1), then we obtain

SPD(T,A) = pn for x=b.

Where min Dn is the smallest number of the set Dn.

The part d and part e of the Conjecture 17is obviously proved with the algorithm above.

China

Liu Fengsui.

***

Michael John Jacobson, Jr. - who wrote a paper in collaboration with Hugh Williams about this subject - communicated to Luis Rodríguez and me by email:

"...I was able to find A values with SPD(T,A)=p for p=269 and for all p between 283 and 401. Unfortunately these A values are almost certainly not minimal (they are the smallest known to me)... A = 31050477690288203269136717357, SPD(T,A) = 269, b = 91...As described in the paper, these A values were found using an electronic number sieve, a special-purpose machine which rapidly solves simultaneous systems of linear congruences. This machine has a fixed number of moduli (229 is the maximum), so to get A values with SPD(T,A) > 229, I had to resort to Lehmer's trick (again described in the paper). This is why these A values are not minimal".

Thus, the most wanted unknown value now has been provided, no matter if it's not the minimal one

***

 Records   |  Conjectures  |  Problems  |  Puzzles