Loading article…
ラテン方陣と有限準群は、前者が組み合わせ論的な性質を持ち、後者がより代数的な性質を持つものの、数学的には同等の対象です。以下のリストでは、正方形の一辺の長さ、または同等の準群の要素数である非常に小さな位数の例を検討します
n個の要素を持つ準群Qが与えられたとき、そのケイリー表(ほぼ普遍的に乗算表と呼ばれる) は、境界を含む( n + 1) × ( n + 1)の表です。境界とは、上段の列ヘッダーと左段の行ヘッダーのことです。境界を取り除くと、n × nの配列、つまりラテン方陣が残ります。このプロセスは逆方向にも実行でき、ラテン方陣から始めて境界となる行と列を導入することで、準群の乗算表が得られます。境界の付け方には完全な任意性がありますが、異なる選択によって得られる準群は、以下に示す意味で等価になることがあります。
n次の2つのラテン方陣L1とL2（つまり、L 1の行、列、記号からL 2の行、列、記号への3 つの全単射が存在し、L 1をL 2に写像する場合、それらの正方形は同位である。[ 1 ]同位は同値関係であり、同値類は同位類と呼ばれる。
同値関係のより強い形式が存在する。共通の記号集合Sを持ち、各正方形の行と列のインデックス集合でもある辺n の 2 つのラテン方陣L 1とL 2は、すべての i 、 j ∈ Sに対してg ( L 1 ( i、j )) = L 2 ( g ( i ) 、g ( j ))となるような全単射g : S → Sが存在する場合に同型である。[ 1 ]同型ラテン方陣を定義する別の方法は、同位ラテン方陣のペアが同型であるのは、それらが同位であることを示すために使用される 3 つの全単射が実際に等しい場合であると言うことである。[ 2 ]同型性も同値関係であり、その同値類は同型類と呼ばれる。
ラテン方陣の別の表現方法として、直交配列があります。n次ラテン方陣の場合、これはn 2 × 3行列で、列はr、c 、 sとラベル付けされ、行はラテン方陣の 1 つの位置、つまり、位置の行、位置の列、位置の記号に対応します。したがって、3 次ラテン方陣の場合、
直交配列は次のように表される。
適切なサイズの行列がラテン方陣を表すための条件は、任意の2 つの列について、それらの列の行によって決定されるn 2個の順序対が、1 ≤ i、j ≤ nを満たすすべてのペア ( i、j ) であり、それぞれ 1 回ずつ出現することです。
This property is not lost by permuting the three columns (but not the labels), so another orthogonal array (and thus, another Latin square) is obtained. This is the operation of choosing a single consistent way to permute each triplet (r, c, s) where r is the row index, c the column index, and s the symbol number. For example, by permuting the first two columns, which corresponds to transposing the square (reflecting about its main diagonal) gives another Latin square, which may or may not be isotopic to the original. In this case, if the quasigroup corresponding to this Latin square satisfies the commutative law, the new Latin square is the same as the original one. Altogether there are six possibilities including "do nothing", giving at most six Latin squares called the conjugates (also parastrophes) of the original square.[3]
Two Latin squares are said to be paratopic, also main class isotopic, if one of them is isotopic to a conjugate of the other. This is also an equivalence relation, with the equivalence classes called main classes, species, or paratopy classes.[3] Each main class contains up to six isotopy classes.
A main class is a disjoint union of isotopy classes and an isotopy class is a disjoint union of isomorphism classes.[4]
Let (Q,∘) and (R,∗) be two quasigroups. An ordered triple (f, g, h) of bijections from Q onto R is called an isotopism of (Q,∘) onto (R,∗) if f(x) ∗ g(y) = h(x ∘ y) for all x, y in G. Such quasigroups are said to be isotopic.[5]
If in the above definition f = g = h then the quasigroups are said to be isomorphic.[2]
ラテン方陣の場合とは異なり、2 つの同位準群がケイリー表 (境界付きラテン方陣) で表されている場合、順列fとgは境界見出しのみに作用し、列と行は移動しませんが、h は表本体に作用します。[ 5 ]
ケイリー表の行と列（見出しを含む）を並べ替えても、それが定義する準群は変わりませんが、この表に関連付けられたラテン方陣は同位ラテン方陣に並べ替えられます。したがって、ケイリー表を正規化（見出しを含む行と列を並べ替えて境界見出しをあらかじめ決められた固定の順序にする）すると、関連付けられたラテン方陣の同位類が保持されます。さらに、2 つの正規化されたケイリー表が同型準群を表す場合、それらに関連付けられたラテン方陣も同型です。したがって、与えられた位数の異なる準群の数は、その位数のラテン方陣の同型類の数になります。[ 6 ]
ラテン方陣（または準群）で使用される記号の集合は任意であり、個々の記号は、他の文脈では意味を持つ場合であっても、それ自体には意味を持ちません。したがって、記号の集合{1, 2, ..., n } または{0, 1, ..., n − 1 } が最も一般的に使用されていることから、これらの記号には数値的な意味がないことを覚えておく必要があります。この点を強調するために、小さなラテン方陣では、記号の集合としてアルファベットの文字が使用されることもあります。
ラテン方陣は組み合わせ論的な対象であるため、方陣を記述するために使用される記号セットは重要ではない。したがって、ラテン方陣として、これらは同じものとみなされるべきである。
同様に、同じ理由で、
同じものとして考えるべきである。したがって、
これらは異なるラテン方陣とは考えられない。
この直感的な議論は、より正確にすることができる。ラテン方陣
はいくつかの点で同位である。集合S = { a , b } 上の対合置換を( a , b )とし、 aをbに、bをaに写すとする。このとき、同位置換{( a , b ), id , id } は最初の正方形の 2 つの行を交換して 2 番目の正方形を与える ( idは恒等置換である)。しかし、 2 つの列を交換する{ id , ( a , b ), id } も同位置換であり、 2 つの記号を交換する{ id , id , ( a , b ) } も同位置換である。しかし、{( a , b ), ( a , b ), ( a , b ) } も 2 つの正方形間の同位置換であり、したがってこれらの正方形は同型である。
与えられたラテン方陣の同型類を求めることは、位数が大きい方陣の場合、計算が困難な問題となることがあります。この問題をある程度軽減するために、ラテン方陣は常に簡約方陣と呼ばれる標準形に変換できます。簡約方陣では、最上行の要素が記号セットに対して自然な順序（例えば、整数は昇順、文字はアルファベット順）で記述されます。左列の要素も同じ順序で記述されます。これは行と列の置換によって行うことができるため、すべてのラテン方陣は簡約方陣と同位です。したがって、すべての同位類には簡約ラテン方陣が含まれる必要がありますが、ラテン方陣にはそれと同位な簡約方陣が複数存在する場合があります。実際、与えられた同型類には複数の簡約方陣が存在する可能性があります。[ 7 ]
例えば、4次の縮小ラテン方陣、
両方とも、縮約平方も含む同型類に属している。
これは、同型写像 {(3,4), (3,4), (3,4)} および {(2,3), (2,3), (2,3)} によってそれぞれ示すことができる。[ 8 ]
同位体クラスは互いに排他的であるため、縮小ラテン方陣の数は同位体クラスの数の上限を与える。また、ラテン方陣の総数は、縮小方陣の数のn !( n − 1)!倍である。 [ 9 ]
準群のケイリー表は、縮小ラテン方陣と同様の方法で正規化できる。すると、縮小ラテン方陣に対応する準群は、（両側）単位元（すなわち、行ヘッダーの最初の要素）を持つ。両側単位元を持つ準群はループと呼ばれる。ループの中には群となるものもあるが、すべてが群となるわけではない。群であるためには、結合法則も成り立たなければならない。
ラテン方陣における様々な部分構造の数は、それらを区別する上で有用である。これらの数の中には、ラテン方陣のすべての同位体で同じ値をとるものがあり、同位体不変量と呼ばれる。そのような不変量の1つは、2×2の部分正方形の数であり、これは挿入部分と呼ばれる。もう1つは、n次のラテン方陣において、各行に1つ、各列に1つずつあるn個の位置のうち、同じ要素を2回含まない位置の総数である。これらの数の値が異なるラテン方陣は、異なる同位体クラスに属する。挿入部分の数もまた、主要クラスの不変量である。
位数 1 の場合、記号 1 を持つラテン方陣は 1 つだけであり、基礎となる集合 {1} を持つ準群も 1 つだけ存在します。それは群であり、自明群です。
次数が２の縮小ラテン方陣は１つだけ（全部で２つだけ）で、それは
この位数の縮約平方は 1 つしかないので、同位クラスは 1 つだけです。実際、この同位クラスは同型クラスでもあります (上記参照)。[ 8 ] [ 1 ]
ラテン方陣の同型類は1つしかないので、位数2の準群（同型を除いて）は1つしかなく、それは通常、で表されます。位数2の巡回群。
また、次数3の縮小ラテン方陣は（12個中）1つしかない。
したがって、同位体クラスは1つだけである。[ 8 ]ただし、この同位体クラスは5つの同型クラスの和集合である。[ 1 ]
5 つの同型クラスのうち 3 つはそれぞれ 3 つのラテン方陣を含み、1 つは 2 つ、1 つは 1 つだけを含みます。縮約方陣は 3 つの要素を持つ同型クラスに属し、対応する準群はループであり、実際には群です。位数３の巡回群。これらの同型類それぞれを代表するラテン方陣は、次式で与えられる（各同型類の下の数字は、対応する同型類の正方形の数である）。
576個のラテン方陣のうち、次数4の縮小ラテン方陣は4個あります。それらは以下のとおりです。
これらのうち最後の3つは同型である（上記参照）。主なクラスは2つ、同位クラスは2つ、同型クラスは35つある。35の準群のうち、ループは2つだけであり、それらは実際には群である。上の最初の正方形に対応するのはクライン4群であり、他の3つの正方形のいずれかに対応するのは巡回群である。最初の正方形には8本の横断線と12本の挿入線があり、他の正方形には横断線はなく、挿入線は4本ある。
クライン4群の同型類は4つの要素を持ち、巡回群の同型類は12の要素を持つ。576 個のラテン方陣のうち、288個は数独の4×4版（Shi Dokuとも呼ばれる） の解である。。
位数５のラテン方陣１６１２８０個のうち、縮約方陣は５６個である。主なクラスは２つ、同位類は２つしかないが、同型類は１４１１個ある。縮約方陣を含む同型類は６つあり、すなわち、ループは６つあるが、そのうち群であるのは位数５の巡回群の１つだけである。[ 1 ]
以下に、各同位体クラスから1つずつ、次数5の縮小ラテン方陣を2つ示します。[ 10 ]
最初の正方形は15本の横断線を持ち、挿入線はなく、巡回群の境界のないケイリー表である。2番目の正方形には3つの横断線と4つの挿入線があります。これはループを表していますが、例えば2 + (3 + 4) = 2 + 0 = 2であるのに対し、(2 + 3) + 4 = 0 + 4 = 4であるため、結合法則は成り立ちません。
ラテン方陣の数は、次数が増加するにつれて、組み合わせ爆発として知られる現象を示します。つまり、サイズがわずかに増加するだけでも、種類は大幅に増加します。基本的な数は次の 2 つの表[ 1 ]に示されており、ここで示されている以上のことは正確にはわかっていません。
この記述はMcKay、Meynert & Myrvold (2007 、p. 100)に従っています。
ラテン方陣の数え上げには長い歴史があるが、発表された記録には多くの誤りがある。1782年のオイラー[ 11 ]と1890年のケイリー[ 12 ]は、いずれも次数5までの簡約ラテン方陣の数を知っていた。1915年、マクマホン[ 13 ]は別の方法でこの問題に取り組んだが、当初は次数5の誤った値を得た。1890年のM.フロロフ[ 14 ]と1901年のタリー[ 15 ] [ 16 ]は、次数6の簡約方陣の数を見つけた。M.フロロフは次数7の簡約方陣の数を誤って数えた。RAフィッシャーとF.イェーツ[ 17 ]は、 E.シェーンハルト[ 18 ]の以前の研究を知らずに、次数6までの同位体クラスの数を与えた。 1939年、HW Nortonは7次の同位体クラスを562個発見したが[ 19 ]、その方法は不完全であることを認めた。A. Sadeは1951年に[ 20 ]、1948年に私的に発表し、PN Saxena [ 21 ]はさらに多くのクラスを発見し、1966年にDA Preeceは、これによりNortonの結果が564の同位体クラスに修正されたと指摘した[ 22 ] 。しかし、1968年にJW Brownは563という誤った値を発表し[ 23 ] 、これはしばしば繰り返された。彼はまた、8次の同位体クラスの数も間違っていた。8次の縮約平方の正しい数は、すでに1967年にMB Wellsによって発見されており[ 24 ]、同位体クラスの数は1990年にG. Kolesova、CWH Lam、L. Thielによって発見されている。[ 25 ] 9 次数の縮約平方の数は SE Bammel と J. Rothstein によって得られ、[ 26 ] 10 次数はBD McKayと E. Rogoyski によって得られ、[ 27 ] 11 次数は BD McKay と IM Wanless によって得られました。[ 28 ]
