Return to Answer

From this it follows, that the permutation must p(i,j)=p(j,i).

However, it is more important to give a condition when a coloring can be constructed:

Lemma 1: If p(x,y) = p(v,w) for xy = vw, then a coloring can be constructed.

Lemma 2: For each n a permutation exists such that p(x,y) = p(v,w) for xy = vw.

By each prime number > n (the x values in the coloring), you can choose a color, but you have to continue with the permutation of that color.

Lemma 1 is trivial to prove, because it follows that c(xy) is c(yx).

I haven't proven lemma 2 yet. For n is 1,2,3,4, there is only 1 permutation matrix. For n = 5 there are a few. The condition p(x,y) = p(v,w) for xy = vw becomes relative weaker for larger n. So, I don't think it is a problem to create such permutation matrix (also given the number of different Sudokus). Of course, lemma 2 needs to be proven properly.

Edit: For Lema 1, it might be necessary to add an associativity condition. That p(x,p(y,z)) = p(p(x,y),z). With associativity, the proof is trivial. I don't know if it can be done without.

Edit 2: The associativity condition is indeed necessary. And this is also part of the solution. If you have a permutation that consists of 1 cycle, then the full permutation matrix can be created by applying the permutation multiple times. This ensures the associativity condition.

It is important that after n times applying the permutation, the colors are in original order again. This means that for n = 5, you must have 1 cycle, because one cycle of 3 plus one cycle of 2 does not come in original order after applying 5 times.

However, this does not count for n = 6. The solution of François as matrix looks like this:
abcdef
bdface
cfbead
daebfc
ecafdb
fedcba

The first permutation, brings you from ato b, from b to d and back to a. However, this can still be categorized as 1 cycle permutation, if you look the permutation from 1 row to third row. a->c->b->f->d->e->a.

I think it is not difficult to create a coloring with a permutation of 1 cycle. You only need to ensure that the few multiplications that are below n fit, and then create the permutation to have 1 cycle. I think for larger n, there is plenty of possibilities for that.

It is more important to give a condition when the above condition is met.

Lemma 1: If p(x,y) is reflexive (p(x,y)=p(y,x)) and associative (p(x,p(y,z))=p(p(x,y),z)) and p(x,y)=p(1,xy) for xy ≤ n, then a coloring can be constructed.

Lemma 2: For each n a permutation exists such that it reflexive and associative and for p(x,y)=p(1,xy) for xy ≤ n.

By each prime number a > n (the x values in the coloring), you can choose a color for c(a), but you have to continue with the permutation of that color for c(ma).

Lemma 1 is trivial to prove, because the associative and reflexive conditions makes that reaching a number by different values of a, factoring the number and re-arranging makes that it must have the same value. For the values xy ≤ n, you can't factor anymore, and the condition must just met.

I haven't proven lemma 2 fully. A permutation matrix with reflexive and associative conditions, can be constructed by starting with 1 permutation that has a single cycle. The full matrix can be constructed by applying this permutation multiple times, up to n. It can be proven, that such matrix has the reflexive and associative condition, but not necessary the condition that p(x,y)=p(1,xy) for xy ≤ n;

The solution of François as matrix looks like this:
abcdef
bdface
cfbead
daebfc
ecafdb
fedcba

The permutation from first row to second row is not a permutation with a single cycle. It brings you from row 1, to row 2 to row 4, back to row 1. However, this can still be categorized as 1 cycle permutation, because the permutation from first row to third row, is a permutation with a single cycle.

Instead of looking at the permutation per color, it is better to look which colors are passed, when the permutation is applied multiple times. In above example the cycle is (first row to third row) a->c->b->f->d->e->a.

If we just make the second row a permutation with one cycle, then the cycle starts with: 1->2->4->8->16->32->64 etc. Then we can add 3 and the other primes.

For n = 27 we can get:
1->2->4->8->16->3->6->12->24->x->9->18->5->10->20->27->x->15->7->14->11->22->x->21->25->13->26->1

In above sequence, multiplications with 2, have 1 step, multiplication with 3, 5 steps, multiplications with 5 have 12 steps. The remaining primes 17, 19, 23 can be placed on any of the x values. The short parts 11->22 and 13->26 can easily be exchanged. From this cycle, you can make a permutation and permutation matrix that has the condition that p(x,y) = p(1,xy) for xy ≤ n. From that permutation the coloring can be constructed.

As you can see, it is not very difficult to construct a coloring this way. But, the sequence is also rather crowded. It is not a prove yet that it is always possible.

However, this does not count for n = 6. The solution of François is not a permutation of 1 cycle:
abcdef
bdface
cfbead
daebfc
ecafdb
fedcba

As you can see, a brings you to b, from b to d and back to a. You need a second permutation to bring a to c, b to f etc.

A permutation with 1 cycle for n = 6 from which a coloring can be created, also exists.

I think it is easier to create a coloring with a permutation of 1 cycle. You only need to ensure that the few multiplications that are below n fit, and then create the permutation to have 1 cycle. I think for larger n, there is plenty of possibilities for that.

However, this does not count for n = 6. The solution of François as matrix looks like this:
abcdef
bdface
cfbead
daebfc
ecafdb
fedcba

The first permutation, brings you from ato b, from b to d and back to a. However, this can still be categorized as 1 cycle permutation, if you look the permutation from 1 row to third row. a->c->b->f->d->e->a.

I think it is not difficult to create a coloring with a permutation of 1 cycle. You only need to ensure that the few multiplications that are below n fit, and then create the permutation to have 1 cycle. I think for larger n, there is plenty of possibilities for that.

Edit 2: The associativity condition is indeed necessary. And this is also part of the solution. If you have a permutation that consists of 1 cycle, then the full permutation matrix can be created by applying the permutation multiple times. This ensures the associativity condition.

It is important that after n times applying the permutation, the colors are in original order again. This means that for n = 5, you must have 1 cycle, because one cycle of 3 plus one cycle of 2 does not come in original order after applying 5 times.

However, this does not count for n = 6. The solution of François is not a permutation of 1 cycle:
abcdef
bdface
cfbead
daebfc
ecafdb
fedcba

As you can see, a brings you to b, from b to d and back to a. You need a second permutation to bring a to c, b to f etc.

A permutation with 1 cycle for n = 6 from which a coloring can be created, also exists.

I think it is easier to create a coloring with a permutation of 1 cycle. You only need to ensure that the few multiplications that are below n fit, and then create the permutation to have 1 cycle. I think for larger n, there is plenty of possibilities for that.