Problems & Puzzles: Conjectures

Conjecture 26. The Calendar-like square Conjecture

Questions:

1. Can you find a counterexample?
2. Otherwise, what can you argue on favor of each part of the conjecture?
3. How is this conjecture related to other known Conjectures?

Solution

Jud McCranie wrote " I tested it for p <= 23929, and it holds for those values. It is almost certainly true".

Aguilar has tested the column-conjecture for p<790000.

***

Ribenboim adds that "In 1963 this conjecture was spelled out once more by Kanold...(and) a quantitative version of the Conjectures in the paper of Schinzel and Sierpinski was formulated by Bateman and Horn (1962)"

***

In short, we may say that while the Aguilar's conjectures are not exactly equivalent to the Sierpinski and Schinzel Conjectures, the truth of the falsity of both come together. Or as Rodríguez says "it's a novelty that Aguilar's proposal makes n=p because in such a case ALL the columns must have at least one prime, not only these k coprimes with n, as Schinzel states".

***

Days ago Enoch Haga and me were discussing more aspects from this double Aguilar's conjecture, in particular what a minimal solution could be. I suggested that a minimal solution for a square pxp must be one consisting of p primes along any of the diagonals. 

Enoch corrected my statement replying that while p primes are enough to have a complete solution to both conjectures the p primes do not need to be along the diagonals but just in such a way that no two of these primes share row and file. Very soon he sent me several examples of these minimal solutions. I only provide two examples:

***

Enoch has gotten - by trial an error - the minimal solutions for squares 11x11, 13x13, 17x17 and obviously has made the following conjecture:

Enoch's Conjecture: The Aguilar double conjecture can always be satisfied with p primes such as the needed in the minimal solutions.

And I have the opportunity to add two more questions:

4. Can you disapprove the Enoch's Conjecture?

5. Do you devise an algorithm to obtain the minimal solutions for a square pxp whenever the solution exists?

***

I have verified (with the help of a little code) the Haga's solutions up to to 17x17 and found other up to the 31x31 squares. Enoch and myself - each one by his side, have devised that some squares admit more than one minimal solution, preserving the same mean.

***

Daniel Gronau makes two contributions to this Conjecture:

1) regarding the algorithm asked in the question 5: 

I have asked to Daniel he to implement that Hungarian method and advises to us if the Enoch Haga's conjecture results confirmed or refuted

2) regarding my insinuation that a minimal solution may be if p primes occur in the main diagonals he wrote:

... this is not right (how E.H. pointed out) this is also NOT POSSIBLE for p>3. The main diagonal contains 1 and p², both not prime. And I sent you the following proof that the other diagonal contains composites for p>3:

There are p "diagonal numbers" D(n) = n*p - n + 1 in the p-square (n = 1..p). Let q be prime and q < p. Then D(n) is composite if D(n) = 0 mod q.

np - n + 1 = 0 | mod q
np - n = - 1 | mod q
n(p - 1) = -1 | mod q
n(1 - p) = 1 | mod q

If p is not equal 1 mod q we can always find an n which solves the last equation. The solution is smaller than q, hence smaller than p. So this D(n) is IN the p-square. We have our first result:

(*) For every prime q smaller than p p must be 1 mod q or one of the D(n) in the p-quare is composite (and a multiple of q).

[Example: 7 = 2 mod 5, so n(1-p) = 1 mod 5 has a solution: n = 4. So D(4) = 25 is composite in the 7-square and 5|25]

For every n >= 2 there is a prime p with n < p < 2n. Hence for every prime p >= 5 there is a prime q with (p-1)/2 < q < p-1. So:

(p-1)/2 < q
p-1 < 2q
p < 2q + 1

And:

q < p-1
q+1 < p

All together now:

q+1 < p < 2q+1
1 < p-q < q+1

This means that p can never be 1 mod q. So for every prime p >= 5 we can find a prime q violating the condition (*).

***

"...here is the the description of a heuristic for conjecture 26. The algorithm is quite easy:

Let p = 7, so our square looks like (we can ignore composites):

-- 2 3 -- 5 -- 7
-- -- -- 11 -- 13 --
-- -- 17 -- 19 -- --
-- 23 -- -- -- -- --
29 -- 31 -- -- -- --
-- 37 -- -- -- 41 --
43 -- -- -- 47 -- --

The trick is to get first "lonely" primes in the solution. We count the number of primes in every row and column:

2 3 3 1 3 2 1

=====================

-- 2 3 -- 5 -- 7 | 4
-- -- -- 11 -- 13 -- | 2
-- -- 17 -- 19 -- -- | 2
-- 23 -- -- -- -- -- | 1
29 -- 31 -- -- -- -- | 2
-- 37 -- -- -- 41 -- | 2
43 -- -- -- 47 -- -- | 2

Now we start to take the "best" primes first. I used the criteria "minimal (row + column) value".

prime criteria

2 3+4=7
3 3+4=7
5 3+4=7
7 1+4=5
11 1+2=3 <-
13 2+2=4
17 3+2=5
19 3+2=5
23 3+1=4
29 2+2=4
31 3+2=5
37 3+2=5
41 2+2=4
43 2+2=4
47 3+2=5

So we will take the prime 11, and cross out this row and column in the matrix and the "lost" primes in our list:

-- 2 3 ## 5 -- 7
####################
-- -- 17 ## 19 -- --
-- 23 -- ## -- -- --
29 -- 31 ## -- -- --
-- 37 -- ## -- 41 --
43 -- -- ## 47 -- --

prime criteria

2 7
3 7
5 7
7 5
17 5
19 5
23 4
29 4
31 5
37 5
41 3 <- (corrected)
43 4
47 5

Because we've "lost" the prime 13, we must decrease the criteria values for all primes in this row by 1. So the 41 gets the new value 3. (This "correction" is only the short way for counting the remaining primes in rows and columns again and making a new list with criteria values) Now prime 41 is the best choice:

-- 2 3 ## 5 ## 7
####################
-- -- 17 ## 19 ## --
-- 23 -- ## -- ## --
29 -- 31 ## -- ## --
## ## ## ## ## ## ##
43 -- -- ## 47 ## --

prime criteria

2 7
3 7
5 7
7 5
17 5
19 5
23 3 <- (corrected)
29 4
31 5
43 4
47 5

Prime 23 was corrected because we've lost the 37. The best choice is now 23:

-- ## 3 ## 5 ## 7
####################
-- ## 17 ## 19 ## --
## ## ## ## ## ## ##
29 ## 31 ## -- ## --
## ## ## ## ## ## ##
43 ## -- ## 47 ## --
prime criteria

3 6 (corrected)
5 6 (corrected)
7 4 <-(corrected)
17 5
19 5
29 4
31 5
43 4
47 5

We could take now the 7, the 29 or the 43. Let's take simply the first one:

## ## ## ## ## ## ##
####################
-- ## 17 ## 19 ## ##
## ## ## ## ## ## ##
29 ## 31 ## -- ## ##
## ## ## ## ## ## ##
43 ## -- ## 47 ## ##

prime criteria

17 4 <- (corrected)
19 4 (corrected)
29 4
31 4 (corrected)
43 4
47 4 (corrected)

Again the first one (17):

## ## ## ## ## ## ##
####################
## ## ## ## ## ## ##
## ## ## ## ## ## ##
29 ## ## ## -- ## ##
## ## ## ## ## ## ##
43 ## ## ## 47 ## ##

prime criteria

29 3 (corrected)
43 4
47 3 (corrected)

In the next two steps we would take 29 and 47. We had luck, all rows and columns were deleted. So we got a "Haga-minimal" solution for the 7-square: 7, 11, 17, 23, 29, 41, 47

***

Rudolph Knjzek sent the following contribution to this conjecture:

"... Let p be the given prime number. I enumerate the rows of the calendar from 1 to p and the numbers of the lines from 0 to p-1. Row p contains only one prime, namely p. Line 0 contains all primes q<=p. All the other numbers can be written in the form n=a+bp with natural numbers a,b less than p. a is the number of the row and b the number of the line.

Now the double-conjecture can be written that way:

a) For all natural numbers a<p exists at least one natural number b<p so that a+bp is prime.

b) For all natural numbers b<p exists at least one natural number a<p so that a+bp is prime.

(what an amazing symmetry!)

How can we find the primes in a given line b?

I calculate all residues r of bp modulo q<p. The rownumber a must not have the residues q-r. Therefore I cut out all these numbers from the set {1...(p-1)}, similar to the Euclidean prime sieve.

The remaining numbers are the rows, containing primes, because all numbers are less than p^2.

There is an example:

p=11
b=2
bp=22

22=0 (mod_2) => a!=0...cuts out 2,4,6,8,10
22=1 (mod_3) => a!=2...cuts out 2,5,8
22=2 (mod_5) => a!=3...cuts out 3,8
22=1 (mod_7) => a!=6...cuts out 6

The remaining values for row a are 1,7,9 and we find the primes 23,29,31.

How can we find the primes in a given row a?

There is a little more work to be done, but we also get one forbidden remainder of b(mod_q) for every prime q<p. I'll show this in a small example:

p=11
a=4

4+11b!=0 (mod_2) => b!=0...cuts out 2,4,6,8,10
4+11b!=0 (mod_3) => b!=1...cuts out 1,4,7
4+11b!=0 (mod_5) => b!=1...cuts out 1,6
4+11b!=0 (mod_7) => b!=6...cuts out 6

The remaining values for line b are 3,5,9 and we find the primes 37,59,103.

Clearly, this is no proof, but the probability that the set of p-1 numbers gets empty when cutting out the numbers with the forbidden residues is very small and it seems, the conjecture holds.

Maybe this is helpful for anybody, who tries to proof the conjecture.

***

One more time, Rudolph Knjzek contributed to this conjecture with another argument:

Between (a-1)p and ab there are (p-1) consecutive numbers. We don't know, if they are  composite or not. (a-1)p and ap are composite. If (a-1) is odd, (a-1)p-1 is composite, because it is even. If (a-1) is even, a is odd and ap+1 is composite, because it is even. We have got now a serie of (p+2) numbers, starting and ending with a save composite. Aguilar's conjecture a) holds, if there are no composite series of length n>=(p+2) starting with or before (p-1)p.

There are computed values of c(n), the first number of the first composite serie of length n. Aguilar's conjecture a) is true, if c(n)>(n-1)(n-3) for all n.

Cramer and Shanks conjectured:
c(n) ~ exp(sqrt(n))
I'll better write this as an inequation:
c(n) > exp(sqrt(n))

Wolf  conjectured:
c(n) ~ sqrt(n)exp(sqrt(n))
The two diagrams show the logarithm of these values and (n-1)(n-3).

If c(n)>exp(sqrt(n)) holds for all the larger values of n - and there is no doubt looking at the diagrams - , Aguilar's conjecture holds for p>69. For p<69 the computed values show, that Aguilar' conjecture is true. For p=11 and n=13 c(n)=114 and (p-1)p=110. This is the most critical point, but 114>110 and the conjecture is true for p=11

***