| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| 0 | ∞0 | 25 | 16 | 34 | |||
| 1 | 45 | ∞1 | 36 | 20 | |||
| 2 | 31 | 56 | ∞2 | 40 | |||
| 3 | 42 | 60 | ∞3 | 51 | |||
| 4 | 62 | 53 | 01 | ∞4 | |||
| 5 | 03 | 64 | 12 | ∞5 | |||
| 6 | 14 | 05 | 23 | ∞6 |
Figure 16 Cyclic Room square
The Room square in Figure 16 has a special property. The pairs in any
element of the array are obtained by simply adding 1 (mod 7) to the pair
in the element immediately above and to the left; along with the
condition that \[\infty+1 = \infty\] This special property means that
the entire square can be determined by the pairs in the first row, with
successive rows being developed in a cyclical manner according the
simple addition rule. We call squares like the one in Figure 16 cyclic
Room squares.
Also notice that \(\{\infty,i\}\) occurs in position \((i,i)\). A square
with this property is said to be standardised. It is important to
realise that any Room square can be standardised. As mentioned
previously neither interchanging the rows or columns nor permuting the
symbol-set on which the Room square is based has any effect of the
``Room"-ness of that square.
The significance of cyclic Room squares is that the problem of
constructing a Room square is (potentially) reduced to that of finding
an appropriate first row. These rows cannot be chosen arbitrarily, both
the pairs used and the positions in which they appear need to satisfy
certain criteria, but when they do exist a corresponding Room square
always exists. So proving the existence of this subclass of Room squares
is a matter only of proving the existence of these special first rows.
Suppose we wish to construct another Room square of the same size as
Figure 16 based on the same symbols. This new square will also be
standardized so we need only determine the three pairs that accompany
\(\{0,\infty\}\) in the first row (the starter), and the positions they
occupy.
The set we will use to build our starter will be {1,2,…,6}.
Each member of this set must occur exactly once in the pairs of the
starter – in order to satisfy the row condition for a Room square.
Because of the cyclical construction the condition is automatically true
for successive rows if true for the first.
Consider the existence in Figure 16 of an arbitrary pair \(\{a,b\}\). We
know one of the following must be true.
Either:
\[\{2+i,5+i\}=\{a,b\} \hspace{0.5cm} \mathrm{or} \hspace{0.5cm} \{1+i,6+i\}=\{a,b\} \hspace{0.5cm}
\mathrm{or} \hspace{0.5cm} \{3+i,4+i\}=\{a,b\} \hspace{0.5cm} \mathrm{for} \hspace{0.1cm} i=0,1,2,...,6\]
Say \(a-b=1\). Then \(\{2+i,5+i\}=\{a,b\}\) could never be true because
\((2+i)-(5+i)=-3(\)mod $ 7)=4$ and \((5+i)-(2+i)=3\). Similarly, the
differences in \(\{1,6\}\) are \(\pm5\) so \(\{a,b\}\) couldn’t be generated
from \(\{1,6\}\).
However, \((4+i)-(3+i)=1\) so \(\{a,b\}\) will inevitably be generated by
\(\{3,4\}\) for some value of \(i=0,1,...,6\).
e.g. \(\{2,3\}=\{3+6,4+6\}\)
Because \(a\) and \(b\) separately take on all values from
\(\{0,1,2,...,6\}\), their differences will similarly take on all these
values (except 0 because there are no pairs of the form \(\{a,a\}\)) and
so an essential property for the starter must be that the six
differences generated by its three pairs contain all of
\(\{1,2,...,6\}\).
When a starter satisfies this property, and the condition that the pairs
contain in their union all of \(\{1,2,...,6\}\), it is clear that it will
inevitably generate the correct pairs which populate a 7x7 Room square.
There are three pairs in the starter, each generates seven unique pairs
under cyclical construction, which along with the seven pairs generated
by \(\{0,\infty\}\) counts for all the 28 unordered pairs from
\(\{\infty,0,1,...,6\}\).
A starter for larger Room squares of course has to obey the same
criterion. We include a general definition based on [8]:
(1,0)450
Definition: If \(G\) is an additive Abelian group of order \(g\), then a
starter in \(G\) is a set of unordered pairs:
\[S=\{\{s_i,t_i\}:1 \leq i \leq (g-1)/2\}\] which satisfies these
properties:
\(\{s_i:1 \leq i \leq (g-1)/2\} \cup \{t_i : 1 \leq i \leq (g-1)/2\} = G \backslash \{0\}\)
\(\{\pm (s_i - t_i ) : 1 \leq i \leq (g-1)/2 \} = G \backslash \{0\}\)
(1,0)450
Whenever we have any \(t\) sets \(D_1,...,D_t\) each of size \(k\) in which
each non-zero member of an additive abelian group can be represented as
a difference between members of the \(D_i \lambda\) times, we say those
sets form a difference system.
Much use will be made of difference systems throughout this work.
Notice that the definition of a starter presumes standardization, and
therefore that \(\{\infty,i\}\) is in position \((i,i)\).
The following pairs form a starter in \(G=\{0,1,2,...,6\}\) (an additive
abelian group with order \(g=7\).)
\[\{1,3\} \hspace{1cm} \{2,6\} \hspace{1cm} \{4,5\}\] Property 1 is
satisfied because
\(\{1,3\} \cup \{2,6\} \cup \{4,5\} = G \backslash \{0\}\)
Property 2 is also satisfied because
\[\{1-3=5,3-1=2,2-6=3,6-2=4,4-5=6,5-4=1\}=\{1,2,3,4,5,6\}=G\backslash \{0\}\]
Hence
| \(\infty 0\) | 13 | 26 | 45 |
|---|---|---|---|
| \(\infty 1\) | 24 | 30 | 56 |
| \(\infty 2\) | 35 | 41 | 60 |
| \(\infty 3\) | 46 | 52 | 01 |
| \(\infty 4\) | 50 | 63 | 12 |
| \(\infty 5\) | 61 | 04 | 23 |
| \(\infty 6\) | 02 | 15 | 34 |
Table 1
are all the unordered pairs from \(\{\infty,0,1,...6\}\) sorted into seven rows that contain each of \(\{\infty,0,1,...,6\}\) exactly once. ALl that remains is to determine the columns.
In constructing the starter we made use of the fact that each row has to
contain each symbol exactly once and all unordered pairs from the symbol
set have to occur exactly once in the whole array. The remaining
condition – namely, that each symbol must occur once in each column – is
now employed to finish the construction.
Again, because of the cyclical nature of Room squares generated from
starters we can be sure that if one column contains each member of the
symbol set, all columns will.
Also, because we have decided to construct a standardized Room Square we
know that column \(i\) contains \(\{\infty,i\}\). So the final column
(column 6) contains \(\{\infty,6\}\), and depending on where we place the
starter pairs it will also include:
\[\{1,3\}+x \hspace{1cm} \{2,6\}+y \hspace{1cm} \{4,5\}+z\] For some
distinct values of \(x,y\) and \(z\) (only one pair allowed per box).
Considering that the new pairs to form column 6 must contain in their
union each of \(\{0,1,2,...,5\}\) we build the following table.
| \(x\) | \(13+x\) | \(y\) | \(26+y\) | \(z\) | \(45+z\) |
|---|---|---|---|---|---|
| \(0\) | 13 | 0 | 26 | 0 | 45 |
| \(1\) | 24 | 1 | 30 | 1 | 56 |
| \(2\) | 35 | 2 | 41 | 2 | 60 |
| \(3\) | 46 | 3 | 52 | 3 | 01 |
| \(4\) | 50 | 4 | 63 | 4 | 12 |
| \(5\) | 61 | 5 | 04 | 5 | 23 |
Table 2
Our task is simply to determine three unique values for \(x,y\) and \(z\)
such that \(13+x,26+y\) and \(45+z\) contain in their union each of
\(\{0,1,2,...,5\}\). These values will then determine the positions to
place 13, 26 and 45 in row 1.
Choosing 4 from the first column corresponds to having 50 appear in the
final column of the Room Square and forces the selection of \(y=2\) from
the next column of the table, (41 being the only pair not containing any
of the already used 5,6 or 0). 23 is the only possible choice from the
final column, accompanied by a value of \(z=5\). These three numbers are
known as an adder corresponding to the starter 13,26,45. This is not
necessarily the only adder.
If 50 is to be generated in the final column of the Room square by the
pair 13 in the first row, then 13 must go in column \(7-4=3\). Similarly
26 has to be put in column \(7-2=5\) and 45 in \(7-5=2\).
We can now construct our cyclic room square.
| \(\infty 0\) | 45 | 13 | - | 26 | - | - | |
|---|---|---|---|---|---|---|---|
| - | \(\infty 1\) | 56 | 24 | - | 30 | - | |
| - | - | \(\infty 2\) | 60 | 35 | - | 41 | |
| 52 | - | - | \(\infty 3\) | 01 | 46 | - | |
| - | 63 | - | - | \(\infty 4\) | 12 | 50 | |
| 61 | - | 04 | - | - | \(\infty 5\) | 23 | |
| 34 | 02 | - | 15 | - | - | \(\infty 6\) |
Figure 17
In general, we define an adder by considering the elements which must
accompany \(\{\infty,0\}\) in column 0. Therefore an adder is defined in
the following way:
(1,0)450
An adder for a starter \(S=\{\{s_i,t_i\}: 1 \leq i \leq (g-1)/2 \}\) is
a set of \((g-1)/2\) distinct non-zero elements \(a_1,a_2,...,a_{(g-1)/2}\)
of \(G\) such that:
\(s_1 + a_1,t_1 + a_1,s_2 + a_2,...,s_{(g-1)/2} + a_{(g-1)/2}, t_{(g-1)/2}+a_{(g-1)/2}\)
are precisely all the non-zero elements of \(G\).
(1,0)450
The starter-adder method employed in the above example was introduced
in 1968[^4] by Stanton and Mullin [23], who used it to construct Room
squares of side 11. They also went on to apply the method to larger
squares and gave the first real suggestions that the number of Room
squares is infinite.
Two simple Lemmas given by Stanton and Mullin demonstrated that the
problem of finding starters for larger Room squares was straightforward.
In fact they can be guaranteed always to exist, and the only difficulty
comes from finding a corresponding adder, which is not guaranteed to
exist.
In an additive abelian group \(G\) of order \(g=2n-1\), then pairs
\[\{n-1,n\},\{n-2,n+1\},\{n-3,n+2\},\{n-4,n+3\},...\{1,2n-2\}\] are a
starter for a Room square of side \(2n-1\).
Example 3.2
A Room square of side \(2n-1=19\).
\(n=10, G=Z_{19}\)
The set of pairs
\(S_{19} = \{\{9,10\},\{8,11\}, \{7,12\}, \{6,13\}, \{5,14\}, \{4,15\}, \{3,16\}, \{2,17\}, \{1,18\}\}\)
is a starter.
Indeed, the differences are
\(\{\pm(10-9),\pm(11-8),\pm(12-7),\pm(13-6),\pm(14-5),\pm(3-16),\pm(2-17),\pm(18-1)\}\)
\(=\{1,18,3,16,5,14,7,12,9,10,8,11,6,13,4,15,2,17\}=G \backslash \{0\}\)
In the Galois field of order \(k-1\), with primitive root \(a\) the
following pairs form a starter for a Room square of side \(k\).
\[\{a,a^n\},\{a^2,a^{n+1}\},\{a^3,a^{n+2}\},...,\{a^{n-1},a^{2n-2}\}\]
Example 3.3
A Room square of side \(2n-1=23\). \(n=12\). \(a=5\).
The set of pairs
\[S_{23}=\{\{5,5^{12}\},\{5^2,5^{13}\},\{5^3,5^{14}\},...,\{5^{11},5^{22}\}\}\]
\[=\{\{5,18\},\{2,21\},\{10,13\},\{4,19\},\{20,3\},\{8,15\},\{17,6\},\{16,7\},\{11,12\},\{9,14\},\{22,1\}\}\]
is a starter.
On closer inspection the two types of starters are identical[^5] , with
a general element being of the form \[\{j,-j\}\] Starters of this form
are called patterned starters.
Stanton and Mullin went on to show that using the method outlined in
Example 2.1 they could find adders corresponding to the patterned
starters for \(k=7,11,13,15,17\). They had problems with 9 (but were able
to construct one using a different method) and finding it too laborious
for \(k>19\) they developed an algorithm which, when implemented in
Fortran, was able to find patterned starters with adders for all odd \(k\)
up to 49, with no further gaps. Suggesting the possibility (which they
conjectured) that there are Room squares for all odd side greater than
5.
They also found an interesting result regarding the number of Room
Squares which could be obtained from patterned starters, summarised in
Table 3.
| Value of \(k\) | Number of PRS |
|---|---|
| 7 | 2 |
| 9 | 0 |
| 11 | 4 |
| 13 | 8 |
| 15 | 44 |
| 17 | 416 |
| 19 | The programme was turned off after the production of 967 PRS |
Table 3
Stanton & Mullin’s results suggest that the number of PRS (patterned
Room squares) increases very rapidly. Which, bearing in mind that the
PRS are a sub-class of CRS (cyclic Room squares), which are in turn a
sub-class of Room squares, implies that there are vast numbers of Room
squares of large order.
Before introducing a class of starters for which the existence of a
corresponding adder is guaranteed we quickly confirm that when a starter
and adder exist then a Room square will always result. This seems
obvious from the method outlined in the previous section, but now we
prove it explicitly.
[17]
If an Abelian group \(G\) of odd order \(2n-1\) admits a starter and an
adder, then there exists a Room square of order \(2n\).
Proof
A square is constructed on the set \(G \cup \{\infty\}\), where \(G\) is an
additive Abelian group of order \(2n-1\).
\[G=\{g_0=0,g_1,g_2,...,g_{2n-2}\}\] The columns and rows of the square
are labelled as follows
| \(g_0\) | \(g_1\) | \(g_2\) | … | \(g_{2n-1}\) | |
|---|---|---|---|---|---|
| \(g_0\) | |||||
| \(g_1\) | |||||
| \(g_2\) |
\(g_0\)
Figure 18
If a starter \(\{\{s_1,t_1\},\{s_2,t_2\}...\{s_{n-1},t_{n-1}\}\}\) and an adder \(\{a_1,a_2,...,a_{n-1}\}\) can be ontained from \(G\) and if the square is populated by pairs of elements from \(G\) according to the following rules:
\(\{\infty,g_i\}\) goes in \((g_i,g_i)\)
While \(\{s_i+g_i,t_i+g_i\}\) goes in \((g_i,g_i-a_i)\)
for all \(g_i \in G\). The remaining square will be a Room square on
\(G \cup \{\infty\}\).
Proof
Row \(g_0=0\), contains the pairs \(\{s_i,t_i\}:1 \leq i \leq n-1\), which are the elements of the starter, hence all of \(G \backslash \{0\}\). These pairs are accompanied by \(\{\infty,0\}\), so row 0 contains all of \(G \cup \{\infty\}\). Subsequent rows simple contain a permutation of the same elements, hence the row property of Room squares is satisfied for all rows.
As mentioned before, the starter forms a difference system in \(G \backslash \{0\}\), so all unordered pairs of this set occur along with all unordered pairs of the form \(\{\infty,g_i\}: 1 \leq i \leq n-1\), hence all unordered pairs from \(G \cup \{\infty\}\) occur in the square exactly once.
All pairs of the form \(\{s_i+a_i,t_i+a_i\}\) go in \((a_i,0)\), i.e. column 0. According to the definition of a starter these pairs are all of \(G \backslash \{0\}\), and we know that \(\{\infty,0\}\) is also in column 0. So the first column, and hence all others, contains all of \(G \cup \{\infty\}\), thus satisfying the column property of Room squares.