Howell Matrices - more

[Richard A. DeVenezias]

For k=3 (the generalized KTS problem), we can proceed as follows.

We need to be able to construct the first row in such a way that it guarantees that every pair appears exactly once. We start by assuming that the top-left cell is always [][0,0][1,0] (it is possible to show that any solution can be transformed into a solution in which this is true). The remaining triples will be of 4 types:

1) 3 even symbols
2) 2 even symbols and 1 odd symbol
3) 1 even symbol and 2 odd symbols
4) 3 odd symbols

We may assume that r is always even, and the modulus 3r+1 (for which I will write q) is always odd. Thus, the above example has r=2 and q=7. The next case of interest has r=4 and q=13. (Note that q is also the row count.) Each triple of type 1 (resp. type 4) contains 3 even-even (resp. odd-odd) pairs, while the triples of type 2 (resp. type 3) contain 1 even-even (resp. odd-odd) pair and 2 odd-even pairs. I'll write t1, t2, t3, t4 for the number of triples of each type. There must be 3qr/2 even-even (resp. odd-odd) pairs in all, therefore 3r/2 in each row, including the top row. Thus, 3t1 + t2 = 3t4 + t3 = 3r/2. Similarly, there must be q² = 3qr+q even-odd pairs in all, therefore 3r+1 in each row including the top row, one of which is in the leftmost triple. Thus, 2t2 + 2t3 = 3r, i.e. t2+t3 = 3r/2. We can derive from this that t1 + t2 + t3 + t4 = 2r, thus t1 + t4 = r/2. Note that t2 and t3 must always be multiples of 3. We can assign t1 arbitrarily to any number in the range 0..r/2, and from this we have t2 = 3(r/2 - t1), t4 = r/2 - t1, t3 = 3t1. It is slightly less confusing to let i be a value in the range 0..r/2, then [t1,t2,t3,t4] = [i,3(r/2-i),3i,r/2-i]. Since this gives the correct number of triples 2r+1 (including the triple on the left), this is a general solution.

If we always take i = r/2, then there will be r/2 triples of type 1 and 3r/2 triples of type t3, and none at all of types 2 or 4. In the r=4 case, writing E1..E12 for the 12 even symbols other than [0,0] and O1..O12 for the 12 odd symbols other than [1,0], we are looking for a top row of the form:

[][0,0][1,0]  E1;E2;E3  E4;E5;E6  E7;O1;O12  E8;O2;O11  E9;O3;O10  E10;O4;O9  E11;O5;O8  E12;O6;O7

I'm going to test out one further assumption, namely that Ot = [1,t] for t=1..12, since this is the simplest way of generating all the odd-odd pairs.

Next, I note that 2 is a primitive root mod 13, and if I lay out the powers of 2 mod 13 in the following way:

1	3	9
2	6	5
4	12	10
8	11	7

I note that the differences of the set [1,3,9] are the set [±2,±6,±5], while the differences of the set [2,6,5] are the set [±4,±12,±10] = [±4,±1,±3], so if I use the symbols corresponding to these two sets for E1;E2;E3 and E4;E5;E6, I will get every pair exactly once. This means that the symbols [0,4], [0,12], [0,10], [0,8], [0,11], [0,7] must correspond in some order to E7..E12.

Writing m7..m12 for the m-components of the symbols E7..E12, and with the other assumptions in place, the even-odd differences will be m7±1, m8±2, m9±3, m10±4, m11±5, m12±6, for some permutation m7..m12 of the residues [4,12,10,8,11,7]. If we can find a permutation such that the even-odd differences are a permutation of 1..12, then we will be done. (I don't know if this can be done other than by brute force.) If we change the order of the odd m-components slightly, we can produce the differences 4±1, 12±3, 10±9, 8±2, 11±6, 7±5, which constitute the set [5,3,2,9,6,1,10,6,4,5,12,2]:  close -- 5, 6 and 2 appear twice, while 7, 11 and 8 do not appear at all.

The above choices are not as random as the might appear. The set [1,3,9] is the set of cube roots of 1 mod 13. Multiplying by 2, 4, 8 in turn gives the sets [2,6,5], [4,12,10] and [8,11,7]. The set [a,3a,9a] will always be one of these 4 sets. I wanted to arrange the differences in the preceding paragraph so that there would be one difference in each of the 4 sets, but instead I ended up with two copies of [2,6,5] and no copy of [8,11,7]. I think I can fix that: If I choose 4±5 as a seed, then the differences will be 9,12, one of which is in [1,3,9] and the other is in [4,12,10]. Extending this to the remaining values in the set [4,12,10] gives 4±5, 12±2, 10±6, so that the differences are [9,1,3] using the + sign, and [12,10,4] using the - sign. If I then double [4,12,10], I get [8,11,7], which together with [4,12,10] covers the residues m7..m12. Multiplying the whole thing by 2 then gives 8±10, 11±4, 7±12. This uses every required difference needed to generate the odd-odd pairs, and gives the differences [5,2,6] using the + sign, and [11,7,8] using the - sign. The full solution is then:

[][0,0][1,0]	[0,1][0,3][0,9]	[0,2][0,6][0,5]	[0,4][1,9][1,12]	[0,12][1,1][1,10]	[0,10][1,3][1,4]	[0,8][1,5][1,11]	[0,11][1,2][1,7]	[0,7][1,8][1,6]
[][0,1][1,1]	[0,2][0,4][0,10]	[0,3][0,7][0,6]	[0,5][1,10][1,0]	[0,0][1,2][1,11]	[0,11][1,4][1,5]	[0,9][1,6][1,12]	[0,12][1,3][1,8]	[0,8][1,9][1,7]
[][0,2][1,2]	[0,3][0,5][0,11]	[0,4][0,8][0,7]	[0,6][1,11][1,1]	[0,1][1,3][1,12]	[0,12][1,5][1,6]	[0,10][1,7][1,0]	[0,0][1,4][1,9]	[0,9][1,10][1,8]
[][0,3][1,3]	[0,4][0,6][0,12]	[0,5][0,9][0,8]	[0,7][1,12][1,2]	[0,2][1,4][1,0]	[0,0][1,6][1,7]	[0,11][1,8][1,1]	[0,1][1,5][1,10]	[0,10][1,11][1,9]
[][0,4][1,4]	[0,5][0,7][0,0]	[0,6][0,10][0,9]	[0,8][1,0][1,3]	[0,3][1,5][1,1]	[0,1][1,7][1,8]	[0,12][1,9][1,2]	[0,2][1,6][1,11]	[0,11][1,12][1,10]
[][0,5][1,5]	[0,6][0,8][0,1]	[0,7][0,11][0,10]	[0,9][1,1][1,4]	[0,4][1,6][1,2]	[0,2][1,8][1,9]	[0,0][1,10][1,3]	[0,3][1,7][1,12]	[0,12][1,0][1,11]
[][0,6][1,6]	[0,7][0,9][0,2]	[0,8][0,12][0,11]	[0,10][1,2][1,5]	[0,5][1,7][1,3]	[0,3][1,9][1,10]	[0,1][1,11][1,4]	[0,4][1,8][1,0]	[0,0][1,1][1,12]
[][0,7][1,7]	[0,8][0,10][0,3]	[0,9][0,0][0,12]	[0,11][1,3][1,6]	[0,6][1,8][1,4]	[0,4][1,10][1,11]	[0,2][1,12][1,5]	[0,5][1,9][1,1]	[0,1][1,2][1,0]
[][0,8][1,8]	[0,9][0,11][0,4]	[0,10][0,1][0,0]	[0,12][1,4][1,7]	[0,7][1,9][1,5]	[0,5][1,11][1,12]	[0,3][1,0][1,6]	[0,6][1,10][1,2]	[0,2][1,3][1,1]
[][0,9][1,9]	[0,10][0,12][0,5]	[0,11][0,2][0,1]	[0,0][1,5][1,8]	[0,8][1,10][1,6]	[0,6][1,12][1,0]	[0,4][1,1][1,7]	[0,7][1,11][1,3]	[0,3][1,4][1,2]
[][0,10][1,10]	[0,11][0,0][0,6]	[0,12][0,3][0,2]	[0,1][1,6][1,9]	[0,9][1,11][1,7]	[0,7][1,0][1,1]	[0,5][1,2][1,8]	[0,8][1,12][1,4]	[0,4][1,5][1,3]
[][0,11][1,11]	[0,12][0,1][0,7]	[0,0][0,4][0,3]	[0,2][1,7][1,10]	[0,10][1,12][1,8]	[0,8][1,1][1,2]	[0,6][1,3][1,9]	[0,9][1,0][1,5]	[0,5][1,6][1,4]
[][0,12][1,12]	[0,0][0,2][0,8]	[0,1][0,5][0,4]	[0,3][1,8][1,11]	[0,11][1,0][1,9]	[0,9][1,2][1,3]	[0,7][1,4][1,10]	[0,10][1,1][1,6]	[0,6][1,7][1,5]

This gives us a CHM with [r,k] = [4,3]. I'll try to find a general solution next.

[Richard A. DeVenezias]

So far, we will be limited to cases where q is prime. This isn't very restrictive, since there are an infinite number of even values r for which q = 3r+1 is prime. Then let's suppose that q is prime, and let s be a primitive root mod q. The set [1,s^r,s^2r] is the set of cube roots of 1 mod q, and I can prove that it is possible to take the sets [1,s^r,s^2r],[s,s^r+1,s^2r+1],...,[s^3r/2-1,s^5r/2-1,s^r/2-1] for the totally even triples; which is to say, I will prove later that the differences generated by these triples will guarantee that each even-even pair appears exactly once. The remaining triples are obtained by multiplying these by s^3r/2 = -1, so one of the isolated even values will be -1. We want to arrange it so that when ±a is added to this, giving -1±a, we will have it such that -1+a is in a group complementary to -1-a, i.e. we want (-1+a)/(-1-a) to be one of the values [s^3r/2,s^5r/2,s^r/2] = [-1,-s^r,-s^2r]. We also have to reject the values 0, ±1 for a, since we don't want any zeroes. One equation that we obtain is (-1+a) = (1+a)s^r, which gives a(s^r-1) = (-1-s^r), or a = -(s^r+1)/(s^r-1). Actually, if a satisfies the condition, then -a also satisfies it, and if (-1+a)/(-1-a) = s^r, then (-1-a)/(-1+a) = s^2r, since s^r and s^2r are reciprocals. Thus, there is actually a unique solution, given by a = ±(s^r+1)/(s^r-1).

Let's reconstruct the solution for q = 13, s = 2, using this approach. We have s^r = s⁴ = 3 mod 13, and s^2r = s⁸ = 9 mod 13. Thus, for the totally even triples we take [1,3,9] and [2,6,5] (as in the posted solution). This leaves the residues [-1,-3,-9] = [12,10,4] and [-2,-6,-5] = [11,7,8] for the remaining even values. We calculate a = ±(3+1)/(3-1) = ±2, so the remaining triples must correspond to 12±2, 10±6, 4±5, 11±4, 7±1, 8±3. In the notation I've been using, 12±2 is the same as the triple [0,12][1,2][1,11], and similarly for the others. The odd-odd pairs therefore occur exactly once in the matrix, and the even-odd differences in the top row will be [1,10,3,4,9,12,2,7,8,6,11,5], and similarly for the remaining rows. This therefore is a general solution for the case that q is prime.

Just as a doublecheck, we can also calculate the top row for the case q = 19 (i.e. r = 6), and s = 2. The triple of cube roots of 1 will be (1,7,11). The totally even triples will be (1,7,11), (2,14,3), (4,9,6). The remaining even symbols will correspond to 18,12,8,17,5,16,15,10,13. a = ±(7+1)/(7-1) mod 19 = ±5. Thus, the top row will consist of the symbols (written vertically here and color-coded for convenience):

[     ][ 0, 0][ 1, 0]

[ 0, 1][ 0, 7][ 0,11]

[ 0, 2][ 0,14][ 0, 3]

[ 0, 4][ 0, 9][ 0, 6]

[ 0,18][ 1, 5][ 1,14]

[ 0,12][ 1,16][ 1, 3]

[ 0, 8][ 1,17][ 1, 2]

[ 0,17][ 1,10][ 1, 9]

[ 0, 5][ 1,13][ 1, 6]

[ 0,16][ 1,15][ 1, 4]

[ 0,15][ 1, 1][ 1,18]

[ 0,10][ 1, 7][ 1,12]

[ 0,13][ 1,11][ 1, 8]

[/pre]

This is therefore a CHM for q = 19, i.e. [r,k] = [6,3].

[Ian Wakeling]

Bill,

I am still working through your posts but have a few questions.

There will be a lot of KTS that you can not construct since q is composite, but can you use Galois Fields to mop up a few more where q is a prime power, for example KTS[33] q=16 and KTS[51] q=25?

Is there any reason why you can not construct a CHM for the [r,k] pair [2,5]?  I believe this corresponds to a v=45, k=5, lambda=1 resolvable balanced incomplete block design (BIBD), which I believe to be an open problem.

Ian.

[Bill Daly]

Bill,

I am still working through your posts but have a few questions.

There will be a lot of KTS that you can not construct since q is composite, but can you use Galois Fields to mop up a few more where q is a prime power, for example KTS[33] q=16 and KTS[51] q=25?

Is there any reason why you can not construct a CHM for the [r,k] pair [2,5]?  I believe this corresponds to a v=45, k=5, lambda=1 resolvable balanced incomplete block design (BIBD), which I believe to be an open problem.

Ian.

q=16 won't work because q has to be odd. I couldn't find an easy way to solve the q=25 case because there is only one cube root of 1 mod 25. I may keep plugging away at it, though. It's certainly possible that there's another simple solution based on finite fields. If I find one, I'll post it. Good thinking.

I don't see any reason why there shouldn't be a [2,5] solution, so I'll look for one. If it's an open problem, then it's definitely worth attacking.

I think I've constructed KTS's for an infinite number of sizes. Has that been done before? I'm not an academic, so I don't ordinarily think in terms of writing papers for publication, but if someone wants to do so and is willing to have me as a co-author, I'd be glad to pitch in.

[Bill Daly]

I left a hole in one of my previous posts, which I can fill in here. I claimed above that using the triples [s^x,s^r+x,s^2r+x] with x = 0..r/2-1 for the r/2 totally even triples would ensure that the even-even pairs are all accounted for. The reason that this works can be seen from the following. Let's start with the triple of cube roots of 1, [1,s^r,s^2r]. There are 6 pairwise differences which we can write as ±(s^r-1), ±(s^2r-s^r) and ±(1-s^2r). If we factor out the term ±(s^r-1), we get the triple [1,s^r,-1-s^r], and since s^r is a cube root of 1, we have -1-s^r = s^2r. Putting it all together in another way, we can say that the pairwise differences of the triple [1,s^r,s^2r] are given by the union of the triples (s^r-1)[1,s^r,s^2r] and -(s^r-1)[1,s^r,s^2r]. We can multiply this result by any arbitrary power of s, say s^x, to show that the pairwise differences of any triple which is a multiple of [1,s^r,s^2r] is the union of two other triples of the same form which are complementary, i.e. one is equal to the other multiplied by -1. We also know that s^3r/2 = -1, from which we can derive that the triples s^x[1,s^r,s^2r] = [s^x,s^r+x,s^2r+x], for x = 0..r/2-1 are complementary to the triples s^x[1,s^r,s^2r] for x = r/2..r-1, and together they are all the triples which are multiples of [1,s^r,s^2r]. This implies that the pairwise differences generated by this set of r/2 triples are distinct, and together constitute all the nonzero residues mod q.

[Bill Daly]

Ian suggested looking for a CHM solution for [r,k] = [2,5], so I'll give it a shot. Using my earlier terminology, there will be q = rk+1 = 11 rows, with kn = k(q-r) = 45 symbols. We will assume that there is one fixed symbol, and that the remaining 44 symbols can be arranged as 4 cycles of 11 symbols each. Again, I'll use [] to represent the fixed symbol, and [j,m] with j = 0..3 and m = 0..10 for the other symbols. What I'll try to do is create a top row where the top-left 5-tuple is [][0,0][1,0][2,0][3,0] and the other 8 5-tuples in the top row contain the remaining 40 symbols without repetition.

First, we need to come up with a feasible pattern, if there is one. It is no longer possible to refer to the cycles as even and odd, since there are 4 of them, so I'll just refer to them as the J₀, J₁, J₂ and J₃ cycles, where the subscript corresponds to the j in my notation. First we need to count the number of J_j-J_j pairs. Let's count the J₀-J₀ pairs. None of these will be in the left column, so there will be q(q-1)/2 = 55 such pairs in the entire matrix, i.e. (q-1)/2 = 5 in each row. Next, we need to count the number of J_j-J_j' pairs, for j' distinct from j. Let's count the number of J₀-J₁ pairs. There will be q = 11 in the left column, i.e. 1 per row, and (q²-q) in the other 4 columns, i.e. (q-1) = 10 in each row not in the left column. Each 5-tuple contains 10 pairs, so there are 80 pairs in the top row but not in the left column. We can immediately see that there cannot be a 5-tuple of symbols all belonging to the same cycle. In fact, there cannot be more than 3 of the same cycle in any 5-tuple, since there cannot be more than 5 same cycle pairs in the top row; and since there are only 4 cycles in all, there is no 5-tuple with 1 each of 5 different cycles. That leaves us with 4 possible classes of 5-tuples:

• t₁ is the number of 5-tuples with 3 symbols of one cycle and 2 of another
  
• t₂ is the number of 5-tuples with 3 symbols of one cycle and 1 each of two others
  
• t₃ is the number of 5-tuples with 2 symbols each of two cycles and 1 of a third cycle
  
• t₄ is the number of 5-tuples with 2 symbols of one cycle and 1 each of the remaining three
  

We can break down the pair counts in each of these classes as follows:

• t₁ contains 3 pairs of one same-cycle set, 1 pair of another same-cycle set, and 6 pairs of some specific different-cycle set
  
• t₂ contains 3 pairs of one same-cycle set, 3 of some different-cycle set, 3 of some other different-cycle set, and 1 of a third different-cycle set
  
• t₃ contains 1 pair of one same-cycle set, 1 of some other same-cycle set, 4 of the different-cycle set using the previous two cycles,
  2 of a different-cycle set using one of the same two cycles, and 2 of the different-cycle set using the other of these cycles and a third cycle
  
• t₄ contains 1 pair of some same-cycle set, 2 each of the three different cycle sets combining this cycle with each of the other three cycles, and 1 each of the 3 different-cycle sets combining two of the other three cycles
  

There must be 5 J_j-J_j pairs in the top row. These can be partitioned in the following ways:

3+2+0+...+0
3+1+1+0+...+0
2+2+1+0+...+0
2+1+1+1+0+...+0
1+1+1+1+1+0+0+0

It's starting to get messy, so let's just try to construct the 5-tuple possibilities. The counts of the J_j must be vectors of length 8 (ignoring the top-left cell) such that the sum of the elements is 10 and the sum of x(x-1)/2 over all 8 components is 5. There are only two (unordered) solutions, given that each element must be between 0 and 3: (3,2,2,1,1,1,0,0) and (2,2,2,2,2,0,0,0). Thus, the counts of each J_j must be a permutation of one of these vectors. Furthermore, there cannot be two distinct J_j whose counts are permutations of the second of these, since each term of the pair count between the two would have to be a multiple of 4, but the sum of all these counts must be 10, which is not a multiple of 4. It follows that at least three of the cycles must have counts which are permutations of (3,2,2,1,1,1,0,0). At this point, I'm beginning to doubt that there is a solution, but just in case, I'll do a brute force search.

Nope, there is at least one feasible solution.

Here's a table to describe the 8 5-tuples in the top row, where the columns are cycles and the rows are 5-tuples. Thus, the sum of each row must be 5, and the sum of each column must be 10 (representing the symbols in each cycle apart from the [j,0] symbol).

5-tuple	J0	J1	J2	J3
1	2	3	0	0
2	0	2	0	3
3	0	2	3	0
4	2	1	1	1
5	2	1	1	1
6	0	1	2	2
7	2	0	1	2
8	2	0	2	1

I'll see if I can find a CHM using this pattern, in the next post.

[Ian Wakeling]

Hi Bill,

I am not an academic either.  The source I was referring to earlier was the Handbook of Combinatorial Designs, I have the first edition from 1996, so quite old now, but it lists the (45,5,1) RBIBD as the smallest BIBD, in terms of the number of replicates of symbols, for which resolvability is undecided.  To try to check on what may have hapenned between 1996 and now, I tried googling the search term:

"45 5 1" resolvable

and I do get a hit to a relatively recent paper.  I can't see the text of the paper without paying, but I fancy that Lemma 5.5 is going to be bad news.

All the KTS[n],  n=3 mod 6 were shown to exist in 1970, it was a celebrated problem for over 100 years.  I did try to program the proof a while back.

Regards,

Ian.

[Bill Daly]

I'm plugging away at the [2,5] problem, but so far it looks like it will take a fair amount of time. I've managed to divide the problem into two pieces, more or less as I suggested earlier. Define a q-pattern as an 8*4 matrix whose 8 rows correspond to the 8 5-tuples other that the 5-tuple in the left column, and whose 4 columns correspond to the 4 cycles, with the following provisos:

• Each cell contains an integer in the range 0..3, corresponding to the number of symbols of the corresponding cycle in the corresponding 5-tuple.
• The sum of the cells in each row is 5.
• Each column is a permutation of either (2,2,2,2,2,0,0,0) -- an even column -- or (3,2,2,1,1,1,0,0) -- an odd column.
• There is at most one even column.
• The inner product of any two columns is 10.

When I first started, I found almost 1.5 million such q-patterns, but there are many symmetries. I was able to reduce the count to 6 even q-patterns (those with an even column) and 7 odd q-patterns (those with no even column). Here are the even q-patterns:

[0, 0, 2, 3]

[0, 3, 0, 2]

[2, 1, 0, 2]

[1, 1, 2, 1]

[2, 0, 2, 1]

[3, 1, 0, 1]

[1, 2, 2, 0]

[1, 2, 2, 0]

[t₁,t₂,t₃,t₄] = [2,1,4,1]

[0, 0, 2, 3]

[0, 2, 1, 2]

[2, 1, 0, 2]

[2, 1, 1, 1]

[2, 1, 1, 1]

[2, 2, 0, 1]

[0, 3, 2, 0]

[2, 0, 3, 0]

[t₁,t₂,t₃,t₄] = [3,0,3,2]

[0, 0, 2, 3]

[0, 3, 0, 2]

[2, 0, 1, 2]

[2, 1, 1, 1]

[2, 1, 1, 1]

[2, 2, 0, 1]

[0, 2, 3, 0]

[2, 1, 2, 0]

[t₁,t₂,t₃,t₄] = [3,0,3,2]

[0, 0, 2, 3]

[0, 3, 0, 2]

[2, 1, 0, 2]

[2, 0, 2, 1]

[2, 1, 1, 1]

[2, 1, 1, 1]

[0, 2, 3, 0]

[2, 2, 1, 0]

[t₁,t₂,t₃,t₄] = [3,0,3,2]

[0, 1, 1, 3]

[2, 0, 1, 2]

[2, 1, 0, 2]

[0, 2, 2, 1]

[0, 2, 2, 1]

[2, 1, 1, 1]

[2, 0, 3, 0]

[2, 3, 0, 0]

[t₁,t₂,t₃,t₄] = [2,1,4,1]

[0, 0, 2, 3]

[1, 2, 0, 2]

[2, 1, 0, 2]

[1, 1, 2, 1]

[1, 1, 2, 1]

[2, 2, 0, 1]

[0, 3, 2, 0]

[3, 0, 2, 0]

[t₁,t₂,t₃,t₄] = [3,0,3,2]

and here are the odd q-patterns:

[0, 0, 2, 3]

[0, 3, 0, 2]

[2, 0, 1, 2]

[1, 2, 1, 1]

[2, 1, 1, 1]

[3, 1, 0, 1]

[1, 1, 3, 0]

[1, 2, 2, 0]

[t₁,t₂,t₃,t₄] = [2,2,2,2]

[0, 1, 1, 3]

[0, 1, 2, 2]

[2, 0, 1, 2]

[1, 3, 0, 1]

[2, 2, 0, 1]

[3, 0, 1, 1]

[1, 1, 3, 0]

[1, 2, 2, 0]

[t₁,t₂,t₃,t₄] = [0,4,4,0]

[0, 0, 2, 3]

[0, 3, 0, 2]

[3, 0, 0, 2]

[1, 1, 2, 1]

[1, 2, 1, 1]

[2, 1, 1, 1]

[1, 1, 3, 0]

[2, 2, 1, 0]

[t₁,t₂,t₃,t₄] = [3,1,1,3]

[0, 1, 1, 3]

[0, 1, 2, 2]

[3, 0, 0, 2]

[1, 2, 1, 1]

[1, 3, 0, 1]

[2, 0, 2, 1]

[1, 1, 3, 0]

[2, 2, 1, 0]

[t₁,t₂,t₃,t₄] = [1,3,3,1]

[0, 0, 2, 3]

[1, 2, 0, 2]

[2, 1, 0, 2]

[0, 3, 1, 1]

[1, 1, 2, 1]

[3, 0, 1, 1]

[1, 1, 3, 0]

[2, 2, 1, 0]

[t₁,t₂,t₃,t₄] = [1,3,3,1]

[0, 1, 1, 3]

[1, 0, 2, 2]

[2, 1, 0, 2]

[0, 2, 2, 1]

[1, 3, 0, 1]

[3, 0, 1, 1]

[1, 1, 3, 0]

[2, 2, 1, 0]

[t₁,t₂,t₃,t₄] = [0,4,4,0]

[0, 1, 1, 3]

[2, 0, 1, 2]

[2, 1, 0, 2]

[0, 2, 2, 1]

[1, 0, 3, 1]

[1, 3, 0, 1]

[1, 2, 2, 0]

[3, 1, 1, 0]

[t₁,t₂,t₃,t₄] = [0,4,4,0]

I've added the [t₁,t₂,t₃,t₄] values below each pattern, mainly because if two patterns are symmetrically equivalent, then their t-counts must be identical. I can't be sure that there are even as few as 6 and 7 q-patterns, since there may be symmetries that I haven't considered, but because of the t-counts, there must be at least 2 even q-patterns and at least 4 odd q-patterns.

I've picked one q-pattern of each type and written code to search for solutions, but they have both been running for 2 days now without coming up with anything. It is of course possible that there is a bug in my code. I'll try to find some way of speeding up the search.

[Bill Daly]

Well, one of my programs ended without finding a solution (which doesn't necessarily mean much, because there could easily be a bug in it), and the other looks like it will run for weeks. I'll keep it running for now (or until Windows decides to reboot the PC to install an update). Meanwhile, I'll see if I can make any progress with a different q-pattern. I'm not happy with the ones that I picked. Maybe I'm overlooking some obvious symmetry that will simplify the job.

[Bill Daly]

I've given this some more thought, as well as writing some code in a real high-level language rather than PARI/GP, which should be faster (at least in principle). I've found two major kinds of symmetry which in principle should be exploitable.

Before getting into that, let me restate what I am looking for, consolidating several posts into this one.  I'm focusing specifically on the problem of finding a CHM with [r,k] = [2,5]. There are 45 symbols, one fixed symbol designated [], and 44 moving symbols arranged in 4 cycles of 10 symbols each, designated [j,m], where j = 0..3 is the cycle number, and m is a residue mod 11. It is sufficient to specify the top row correctly, because the remaining rows (derived by incrementing the m values in the preceding row mod 11) will automatically satisfy the requirements. There are 9 cells in each row, each containing 5 symbols. The left-most cell consists of the fixed symbol [] together with the element of each cycle with m=0 (i.e. the symbols [j,0] for j=0..3), and the remaining 40 symbols are all of the form [j,m], with m a nonzero residue mod 11. Furthermore, there can be no repetitions of symbols anywhere in the top row, which implies that each symbol appears exactly once.

The constraints on the top row are based on the "differences" between pairs of symbols. There are two types of such differences: inner differences are the differences between the m values of elements of the same cycle within each cell, and outer differences are the differences between the m values of elements of different cycles within each cell. The top row is said to solve the problem if the number of inner differences in it totals 10 (note that each pair, say [j,m₁] and [j,m₂], generates two differences, m₁-m₂ and m₂-m₁); the number of outer differences in it totals 10 (here, each difference counts only once, because given [j₁,m₁] and [j₂,m₂] with j₁ ≠ j₂, we can take m₁-m₂ to be the j₁-j₂ difference, and m₂-m₁ to be the j₂-j₁ difference); and further, that each set of 10 differences is a permutation of the nonzero residues mod 11, i.e. there are no repetitions. If this is the case, then in the full CHM, every symbol will appear exactly once in each row, and every pair of symbols will appear together exactly once in the same cell.

To try to subdivide the problem a bit, I defined what I've been calling a q-pattern, which is an 8*4 array whose 8 rows correspond to the 8 5-tuples in the top row other than the leftmost, and whose 4 columns correspond to the 4 cycles. Each cell in the q-pattern is the total number of symbols of the corresponding cycle which are part of the corresponding 5-cycle. This implies that the sum of the cells in each row must be 5, and the sum of the cells in each column must be 10 (note that 5*8 = 10*4). I wrote a little PARI/GP program to show that the columns must be a permutation of either 3,2,2,1,1,1,0,0 (an odd cycle), or 2,2,2,2,2,0,0,0 (an even cycle); and that furthermore there is at most one even cycle in any q-pattern. The program checks to ensure that there are exactly 5 pairs from each cycle in the column, in order to account for the 10 inner differences required; and that the number of pairs formed from any given two distinct cycles is equal to 10, in order to account for the 10 outer differences required.

Now, to symmetry.

If we have a solution, then there are two types of symmetry that allow us to find equivalent solutions. The first of these involves "multipliers". In this specific case, a multiplier may be any non-zero residue mod 11. More generally, it may be any reduced residue which is coprime to the modulus rk+1, which is 11 in this case. If we multiply all the m values in the matrix mod 11, then the result will be another solution. This is one of the symmetries that I intend to use.

The other symmetry is that the cycles may be permuted in any of 24 possible ways, and the 5-tuples (other than the left-most) can be permuted in any of 40320 ways, without affecting the solution. In terms of q-patterns, it implies that the columns and rows of the q-pattern may be permuted arbitrarily. I haven't started to use this yet, but I'll look at it more closely in a bit.

The first thing that I did was to find all ways in which the m values of an odd cycle may be assigned such that the inner differences are correct. I started with the idea that each odd cycle has one group of 3 in some 5-tuple, and that I could assume that these 3 were in ascending order, since the order doesn't affect the differences (whether inner or outer). Similarly, I could assume that each of the two groups of 2 are in ascending order. It can make a difference which group of 2 is which, because it will affect the outer differences, and similarly it can make a difference how the three groups of 1 are arranged, for the same reason. However, I was at this point interested only in the inner differences, so I imposed the additional requirement that the groups of 2 and the groups of 1 had to be in ascending lexicographical order, as well. Furthermore, I recognized that for every solution of this subproblem, there were 9 others that could be obtained by applying multipliers.

So I wrote a program to find all the solutions of this subproblem (enumerating all possible solutions for inner differences of odd cycles), and found that there were 52 distinct solutions, each with the following properties:

• No two solutions differed by a multiplier;
• No two solutions differed by interchanging the two groups of 2;
• No two solutions differed by permuting the three groups of 1;
• No two solutions differed by the order of the elements in the 3-group or either of the 2-groups.

Then, by applying the possible multipliers and rearranging the groups of 2 and groups of 1, I found that there were 120 general solutions corresponding to each of these 52, giving a total of 52*120 = 6240 general solutions constrained only by the last property listed (I didn't actually bother to sort the 3-group or the two 2-groups).

Next, I wanted to know which possible q-patterns could conceivably satisfy both the inner and outer difference constraints. I wrote another program to solve this, which came up with a humongous number of solutions that I then reduced by hand to a total of 13, 6 of which contained an even cycle and 7 of which contained only odd cycles.

Thus armed (and ever hopeful), I then wrote two more programs (using PARI/GP as usual) to attempt to find a solution. My first effort involved taking one of the totally odd q-patterns and attempting to find some 4 of the subproblem solutions that I discussed above, to try to satisfy the outer differences. (I used the full set of 6240 solutions for this purpose, which is one reason that the work is going so slowly.) I've been running this program for over a week now, without finding anything, and it is progressing so slowly that I may abandon it soon. My second effort involved using one of the q-patterns with an even cycle, assuming that this cycle had a specific solution, and attempting to fit the other three odd cycles. This program finished a few days ago without finding anything. (I hasten to add that it is always possible that I made a coding error.) To date, I haven't attempted the similar subproblem with even cycles.

So, since it was taking so long with no apparent hint of progress, I decided to rewrite the search in a faster language (C#), and to take better advantage of symmetry. I started that going yesterday, and so far haven't found anything -- it looks like it may finish in a couple of weeks, so I may let it go or I might kill it. (One of these days I'll remember to add checkpoint/restart logic to code of this type.)

Anyway, there is another application of symmetry that I just noticed today, more or less by accident. I listed the 13 feasible q-patterns in an earlier post, together with their t-counts (i.e. the values of t₁..t₄ among the 5-tuples). I started by looking at q-patterns one at a time, with the idea of finding some column/row swap that was an automorphism. Some of the q-patterns (including unfortunately the one I chose for my C# version) have no automorphisms, but others do. Here's an example, which will also serve as an illustration:

[3, 0, 1, 1]

[1, 3, 0, 1]

[1, 1, 3, 0]

[0, 1, 1, 3]

[0, 1, 2, 2]

[2, 0, 1, 2]

[2, 2, 0, 1]

[1, 2, 2, 0]

This pattern has 4 5-tuples of type t₂ (the top 4 listed) and 4 of type t₃ (the bottom 4 listed). The following permutation, of order 4, is an automorphism of the matrix: (c0 c1 c2 c3) (r0 r1 r2 r3)(r4 r5 r6 r7). Here the c's refer to columns and the r's to rows, so that it can be described more readably as rotating the 4 columns one position to the right, followed by rotating the top 4 rows one position down, followed by rotating the bottom 4 rows one column down. It implies that if we have a solution for this q-pattern, then we can apply the same automorphism to it to obtain 3 other solutions. In practice, it implies (for this q-pattern) that any one cycle can be required to be lexically smaller (or greater) than the other 3, which should also reduce the computation time required for a search.

I haven't completed this analysis, and I haven't yet applied it to my code.

[Bill Daly]

The two programs that I was running were killed by a Windows update, so I've started another. I haven't found anything yet, so I'll take some time to check the logic of my code if nothing good happens.

Meanwhile, let's work out the automorphisms of the remaining q-patterns. I just plunged into it earlier without explaining what I was doing, so here are a couple of details. For one thing, I rearranged the rows of several of the patterns in an effort to make the automorphisms more obvious. For another, I noticed several little details about the automorphisms that help to narrow it down a bit. One point is that it is safe to assume that the column permutations can all precede the row permutations. Another point is that if a row pattern is unique, then any column which contains one of the unique values in that row must remain fixed, e.g. if there is only one 3-2-0-0 row in the q-pattern, then the columns containing the 3 and 2 must remain fixed, which means that there is at most one automorphism other than the identity, namely one that swaps the other two columns.

There are 4 q-pattern whose t-counts are [3,0,3,2] and 2 others whose t-counts are [2,1,4,1]. The first of the [3,0,3,2] patterns is:

[0, 3, 2, 0]

[2, 0, 3, 0]

[0, 0, 2, 3]

[2, 1, 1, 1]

[2, 1, 1, 1]

[0, 2, 1, 2]

[2, 1, 0, 2]

[2, 2, 0, 1]

There is no unique row here, but the two rows with the pattern 2-1-1-1 both have the 2 in the leftmost column, so this column must remain fixed. Similarly, column 2 must remain fixed. However, we may swap columns 1 and 3, leading to this automorphism:

(c1 c3) (r0 r2) (r6 r7)

This allows us to assume that columns 1 and 3 are in a specific lexicographical order.

The second q-pattern is:

[0, 3, 0, 2]

[0, 2, 3, 0]

[0, 0, 2, 3]

[2, 1, 1, 1]

[2, 1, 1, 1]

[2, 0, 1, 2]

[2, 2, 0, 1]

[2, 1, 2, 0]

Column 0 must remain fixed, but the remaining 3 columns may be rotated, giving the following nontrivial automorphisms:

(c1 c2 c3) (r0 r1 r2) (r5 r6 r7)
(c1 c3 c2) (r0 r2 r1) (r5 r7 r6)

Thus we can assume that any specific column among 1, 2 and 3 is lowest (or highest) of the three in the lexicographical ordering.

Here is the 3rd pattern:

[0, 3, 0, 2]

[0, 2, 3, 0]

[0, 0, 2, 3]

[2, 1, 1, 1]

[2, 1, 1, 1]

[2, 0, 2, 1]

[2, 1, 0, 2]

[2, 2, 1, 0]

Again, column 0 must be fixed, but the remaining columns may be rotated, i.e. there are two automorphisms other than the identity:

(c1 c2 c3) (r0 r1 r2) (r5 r6 r7)
(c1 c3 c2) (r0 r2 r1) (r5 r7 r6)

Thus we can assume that any specific column among 1, 2 and 3 is lowest (or highest) of the three in the lexicographical ordering. There is however no transformation of this pattern into the previous one.

Here is the 4th pattern:

[3, 0, 2, 0]

[0, 3, 2, 0]

[0, 0, 2, 3]

[1, 1, 2, 1]

[1, 1, 2, 1]

[1, 2, 0, 2]

[2, 1, 0, 2]

[2, 2, 0, 1]

The third column must be fixed, because of the two 2-1-1-1 patterns, but we can swap any other pair of columns, thus the following are all automorphisms:

(c0 c1) (r0 r1) (r5 r6)
(c0 c3) (r0 r2) (r5 r7)
(c1 c3) (r1 r2) (r6 r7)
(c0 c1 c3) (r0 r1 r2) (r5 r6 r7)
(c0 c3 c1) (r0 r2 r1) (r5 r7 r6)

We may therefore assume that columns 0, 1 and 3 are in a specific lexicographical order.

The remaining two patterns have t-counts [2,1,4,1]. Here is the first:

[0, 3, 0, 2]

[0, 0, 2, 3]

[3, 1, 0, 1]

[1, 1, 2, 1]

[2, 0, 2, 1]

[2, 1, 0, 2]

[1, 2, 2, 0]

[1, 2, 2, 0]

Since there is a unique 3-1-1-0 row, columns 0 and 2 must be fixed. This also takes care of the unique 2-1-1-1 row. But if we swap columns 1 and 3, then the first row becomes [0,2,0,3], which does not match any row in the pattern, thus the only automorphism is the identity, and no optimization is possible.

The last pattern in this group is:

[2, 3, 0, 0]

[2, 0, 3, 0]

[0, 1, 1, 3]

[2, 1, 1, 1]

[2, 0, 1, 2]

[2, 1, 0, 2]

[0, 2, 2, 1]

[0, 2, 2, 1]

As above, columns 0 and 3 must be fixed, but here we can swap columns 1 and 2, i.e. (c1 c2) (r0 r1) (r4 r5) is an automorphism, which means that we may assume that columns 1 and 2 are in a specific lexicographical order. This also implies that there is no way of transforming this pattern into the preceding one.

(Note: I've left the definition of "lexicographical order" aside, because it can be a complicated issue. In principle, any valid ordering of the columns should do. The one I am actually using in my code is a bit abstruse.)

[Bill Daly]

I think one of my posts got lost somewhere (maybe I forgot to post it). I'll try to reconstruct it.

[Bill Daly]

I had to give up on this for the time being. I'll get back to it later.