737 - From the computation of Erdös-Woods Numbers to the quadratic Goldbach Conjecture

N. Lygeros

Erdös-Woods Numbers are defined as the length of an interval ofconsecutive integers whose every element is not coprime with itsextremeties. Woods was the first to find such numbers, Dowe proved there exists an infinity and Cégielski, Heroult and Richard that their set is recursive. Our aim is to study the arithmetical proprieties of those numbers in relation with Goldbach Conjecture.

History and Conjecture

Conjecture Erdös-Woods : There is a positive integer k such that every x is uniquely determined by the list of prime divisors of x+1, x+2,…,x+k.

For x less than 100000 k=3 is sufficient.

For primes less than 23 there are four ambiguous cases for k=2 :(x+1,x+2)=(2,3) or (8,9) ; (6,7) or (48,49) ; (14,15) or (224,225); (75,76) or (1215,1216).

The first three of these are members of the infinite family :(2^n-2,2^n-1),(2^n(2^n-2),(2^n-1)^2)

Conjecture, Counterexample and Theorem

Conjecture (Woods 1981) : For any ordered pair of natural numbers, with d>2, there exists a natural number c such that a < c < a+d and c is coprime with a and with a+d.

Counterexample (Woods) : <2184, 16>

2184,2185,2186,2187,2188,2189,2190,2191,2192,2193,2194,2195,2196,2197,2198,2199,2200
2,3,7,13/5,19,23/2,1093/3/2,547/11,199/2,3,5,73/7,313/2,137/3,17,43/2,1097/5,439/2,3,61/13/2,7,157/3,733/2,5,11

Theorem (Dowe 1989) : There exists an infinity of such counterexamples to the Woods’conjecture.

Elementary Propositions

Proposition 1 : If d is an Erdös-Woods number there exists two primes dividing d-1.

Idea : Primality of consecutive numbers.

Proposition 2 : a and a+d are composite numbers.

Idea : Primality of consecutive numbers.

Remark : d can be prime.

Proposition 3 : The complementary set in N of the set of Erdös-Woods number is infinite.

Idea : For every prime p, p^n + 1 belongs to this set.

Proposition 4 : For every couple of integers a and d, such that d is an Erdös-Woods number we have d

Idea : Bertrand-Tchebychev’s Theorem

Theorem (Cégielski-Heroult-Richard 2000)
An integer d is an Erdös-Woods number if and only if there exist apartition of the set P_{

(i) for any integer i, 0

(ii) for 0

Idea : Analogous to the Cantor Theorem on consecutive primes inarithmetic progression.

First Erdös-Woods numbers

16,22,34,36,46,56,64,66,70,76,78,86,88,92,94,96,100,106,112,116,118,120,124,130,134,142,144,146,154,160,162,186,190,196,204,210,216,218,220,222,232,238,246,248,250,256,260,262,268,276,280,286,288,292,296,298,300,302,306,310,316,320,324,326,328,330,336,340,342,346,356,366,372,378,382,394,396,400,404,406,408,414,416,424,426,428,430,438,446,454,456,466,470,472,474,476,484,486,490,494,498,512,516,518,520,526,528,532,534,536,538,540.

Open Problems

Let EW(n) be the n-th Erdös-Woods number. EW(1) = 16, EW(2) = 22, EW(3) = 34,…

Problem : Find a lower bound for EW(n).

Problem : Find a (simple) function f such that EW(n)~f(n).

Problem : Is the density rho(n) of Erdös-Woods numbers linear ? More precisely : rho(n) = O(n) ? Perhaps rho(n)/n -> 1/4 ?

Conjectures

Conjecture (Dowe 1989) : Every Erdös-Woods number is even.

Conjecture (Dowe 1989) : Every a associated to Erdös-Woods numbers is even.

Conjecture (CHR 2000) : There exists an infinity of twins Erdös-Woods numbers.

Conjecture (CHR 2000) : For any integer k, there exists an integer d such that d, d+2, d+4, … , d+2k are Erdös-Woods numbers.

Conjecture (Vsemirnov 2000) : Every square greater than 16 is an Erdös-Woods number.

Results

Theorem : If for an odd integer number d, there exists a sequenceS_d=d_0,d_1,d_2,… such that :

* d_0=1

* For all 0

* For all 0 d

* It exists i

Corollary : 903,2545,4533,… are Erdös-Woods numbers.

Ideas

903, [[41, 39], [431, 22], [59, 43], [211, 84], [173, 139], [73, 58], [83, 27]]

2545, [[53, 13], [89, 4], [307, 135], [373, 207], [181, 45], [197, 67],[587, 100]]

4533, [[103, 48], [443, 331], [409, 252], [1031, 92]]

Theorem : If for an even integer number d^2 with d+1 prime, there exists a sequence S_{d^2}=d_0,d_1,d_2,… such that :

* d_0=1

* d_1=d+1

* For all 1

* For all 1 d^2

* It exists i

Remark 1: Vsemirnov’s conjecture is false for 26^2 and 34^2 (by direct computation)

Remark 2: As 8^2, 14^2 and 20^2 are Erdös-Woods numbers the theorem can be only sufficient.

Corollaries and Certificates

Corollary : 16, 36, 100, 144, 256, 324, 484, 784, 900, 1296,1600, 1764, 2116,,… are Erdös-Woods numbers.

Certificates

16, [[5, 1], [11, 6]]

36, [[7, 1], [29, 6]]

100, [[11, 4], [89, 30]]

144, [[13, 4], [131, 75]]

256, [[17, 1], [239, 221]]

324, [[19, 10], [61, 31], [263, 60]]

484, [[23, 4], [461, 206]]

784, [[29, 14], [151, 40], [211, 16], [191, 41], [593, 15]]

900, [[31, 3], [79, 52], [821, 364]]

1296, [[37, 17], [1259, 989]]

1600, [[41, 17], [1559, 1055]]

1764, [[43, 11], [1721, 403]]

2116, [[47, 4], [2069, 1068]]

Corollary : If d+1 and d^2-d-1 are primes then d^2 is an Erdös-Woods number.

In other words, if a contrained quadratic goldbach condition holds then d^2 is an Erdös-Woods number. This CQGC implies the last condition of the theorem.

This also means that the quadratic goldbach condition would not besufficient to prove the theorem because we need a special goldbachpartition. On the other side, this theorem could lead to a new strategy for the proof of a special case of Goldbach conjecture with the quadratic formulation.

Conjecture: (Quadratic Goldbach Conjecture) For all n>1, it exist p and q such that (2n)^2=p+q

Computational Results on Consecutive Erdös-Woods numbers

n=2: 34,36

n=3: 92,94,96

n=4: 216,218,220,222

n=5: 532,534,536,538,540

n=6: 1834,1836,1838,1840,1842,1844

n=7: 2166,2168,2170,2172,2174,2176,2178

n=8: 4312,4314,4316,4318,4320,4322,4324,4326