Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If $G$ is a finite group then the composition table of $G$ is a latin square (ie, each row and column contains each group element exactly once).

Assume now that $|G| = n^2$ for some natural number $n$. We can then split the composition table for $G$ into $n^2$ $n\times n$ squares, and we can ask whether the resulting table is a solved sudoku (of size $n^2\times n^2$ rather than the usual $9\times 9$).

When making the composition table for $G$, there are two choices to be made. One is the ordering of the elements for the rows, and the other is an ordering of the elements for the columns. By looking at the row and column corresponding to the identity, one can see that if we pick the same ordering for rows and columns, then the composition table cannot be a sudoku (if we label the entries in the composition table as $a_{i,j}$ and the row/column corresponding to the identity is $k$ then we have $a_{k-1,k} = a_{k,k-1}$ and $a_{k+1,k} = a_{k,k+1}$ and at least one of these pairs belong to the same $n\times n$ square).

If $G$ is cyclic, then we can indeed make the composition table a sudoku as follows: Write $G = \{0,1,\dots ,n^2 - 1\}$ (identified with the integers mod $n^2$). Order the columns in the natural way (ie, in increasing order with the chosen representatives), and order the rows in blocks of $n$ such that in each block, the difference between consecutive terms is $n$ (so each block consists of those elements with a given residue mod $n$ in increasing order).

For the non-cyclic group of order $4$, it is also possible (it is easy to do by trial and error). For the non-cyclic group of order $9$, it is again possible, but it takes a while to find some orderings that work. Ones that work are as follows: Let the group be generated by two elements $a$ and $b$ and order the columns as $1,ab,a^2b^2,a,b^2,a^2b,a^2,ab^2,b$ and the rows as $1,a,b,ab,a^2,b^2,a^2b,ab^2,a^2b^2$.

My question is: For what groups is it possible to find orderings of the rows and columns that turn the composition table into a sudoku?

Edit: Note that if this is possible for some group $G$ then each of those $n\times n$ squares correspond to a pair of subsets $A,B\subseteq G$, each of size $n$, such that $AB = G$.

In fact, it is possible iff there are subsets $A_i$ and $B_i$ of $G$ all of size $n$ such that $$G = \bigcup_{i=1}^n A_i = \bigcup_{i=1}^n B_i$$ and such that for all $i,j$ we have $A_iB_j = G$.

share|improve this question
    
And one can ask the converse problem: what sudoku tables can be viewed as a composition table? –  awllower Feb 21 '13 at 3:10

1 Answer 1

One case where a sudoku arrangement is possible is when $G$ has a subgroup $H$ of order $n$. Let $Ha_1, Ha_2, \ldots Ha_n$ be the right cosets of $H$ and let $T_1, T_2, \ldots, T_n$ be a partition of $G$ into complete sets of left coset representatives. That is, each $T_i$ contains exactly one element from each left coset of $H$ and $T_i \cap T_j = \emptyset$ for $i \neq j$.

Order the columns by listing every element of $Ha_1$ first, then every element of $Ha_2$ and so on until $Ha_n$. Similarly order the rows by listing each element of $T_1$ first, then $T_2$ and so on until $T_n$. Then each $n \times n$ block is contains elements of a $Ha_i$ in the columns and elements of some $T_j$ in the rows. It turns out that this arrangement gives us a sudoku table.

We should show that every element of $G$ occurs exactly once in the block corresponding to $Ha_i$ and $T_j$. That is, we want to show that $T_jHa_i = G$, and this follows from the fact that there are no repetitions in the block. Suppose that $s_k, s_{k_0} \in T_j$ and $h, h_0 \in H$. If $s_kha_i = s_{k_0}h_0a_i$, then $s_kH = s_{k_0}H$ so $s_k = s_{k_0}$ since $T_j$ contains exactly one representative for each left coset. Thus $h = h_0$ as well.

I found the idea for the construction here, where a bit more general problem is considered. If $|G| = ab$ and $[G:H] = a$, then the same construction as in this answer gives you a sudoku table with blocks of size $a \times b$.

share|improve this answer
2  
Very nice observation. So that paper discusses a more general case, but only provides a partial answer (essentially the one above). So we are left with looking at those groups of order $n^2$ and with no subgroup of order $n$. –  Tobias Kildetoft Feb 20 '13 at 17:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.