Problems & Puzzles: Conjectures

Conjecture 26. The Calendar-like square Conjecture

Julio Cesar Aguilar, from México, has the following double-conjecture:

In a calendar-like and square array of numbers from 1 to p2, being p any prime number:

a) there is always at least one prime per row
b) there is always at least one prime per column

For example if p=5, this is the calendar-like square and the primes inside:

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

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

Luis Rodríguez wrote (17/11/01):

"In reference to the rows, this conjecture is equivalent to the Sierpinski conjecture (Ribenboim p. 397). The Sierpinski conjecture can be expressed more succinctly: 'For any n>=2 and any 1 <k <= n there exists a prime number between (k-1)n and kn"

***

As a matter of fact, The Sierpinski's Conjecture (S), in the Ribenboim book says:

"(S) For every integer n>1, let n2 integers 1, 2, 3, ... n2 be written in an array with n rows, each with n integers, like an nxn matrix:

1             2          ...         n
n+1,        n+2                  2n
.
.
.
(n-1)n+1   (n-1)n+2          n2

Then, there exists a prime in each row"

***

Moreover, I found that two pages ahead, that Schinzel made the "transposed from the Sierpinski Conjecture", or the second part of the Aguilar's Conjecture:

"(S') For every integer n>1, let n2 integers 1, 2, 3, ... n2 be written in an array with n rows, each with n integers (just like in S). If 1<=k<=n and gcd(k,n)=1, then the kth column contains at least one prime"

***

Schinzel & Sierpinski wrote these Conjectures in 1958. According to Ribenboim they added "We do not know what will be the fate of our hypotheses, however we think that, even if they are refutes, this will not be without profit for number theory".

Ribenboim comments "It's my impression that none of the conventional present day methods of number theory will lead to a proof of any of the conjectures (D), (B), (H), (S), (S'). Perhaps will be the role of the logicians, investigating the inner structure of arithmetic, to decide whether such statements are, or are not, provable from the Peano axioms."

***

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:

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

***

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

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:

If I understand question 4 of conjecture 26 right, there is an easy answer: We are searching an 1:1 "assignment" from rows to columns, and we want to use only some of the possible fields (the fields which are prime) for this. If we treat the fields in the matrix as "expenses" (and the prime fields are the cheap ones) we have an optimization problem of the linear programming: the classical Assignment Problem. All we have to do is to write 1 in every field containing a composite number and 0 in every field containing a prime:

1 0 0 1 0
1 0 1 1 1
0 1 0 1 1
1 0 1 0 1
1 1 0 1 1

To get a minimal solution for an assignment with this "expense matrix", we could use the Simplex or the Transport Algorithm, but there is a special, easy and efficient algorithm only for this problem: the Hungarian Method. It's an exact algorithm. If we got expenses equal 0, we have a "Haga-minimal" solution.

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

***

Daniel Gronau wrote:

I've tested the Haga-minimality for p-squares (conjecture 26) up to p = 2699. The "initial solution" found by a heuristic algorithm was almost always the minimal solution. I try to speed up this part of code. I think Enoch's conjecture is true, because growing p yields more and more minimal solutions.

This is the "heuristic algorithm" devised by Daniel:

"...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:

I send you a contribution to conjecture 26 a). It is almost a proof, but at least a heavy argument. I write this email in HTML and hope, you can post the two diagrams on your site, because they are an essential part.

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

***