ルービックキューブグループのジェネレーターと関係 - 定義

導入

当時非常に人気があったパズルであるルービックキューブを数学的に表現することができます。この記事は、ルービックキューブの数学理論に関するシリーズの一部です。

導入

使用される表記法

$$ {G \,} $$
法的運動のグループ（キューブを解体せずに！）
$$ {H \,} $$
拡張グループ (ここで立方体を爆破できます)
$$ {C_n \, = \, \mathbb Z/n\mathbb Z} $$
$$ {\mathfrak{S}_n \,} $$
n 次の対称群
$$ { \rtimes \,} $$
セミダイレクト商品のシンボルとして
$$ {\epsilon \,} $$
の順列に署名するため
$$ {\mathfrak{S}_n \,} $$
$$ { P : \begin{matrix}\mathfrak{S}_n \times C_k^n & \rightarrow & C_k^n \\ (s,(x_1,x_2,…,x_n)) & \mapsto & (x_{s(1)},x_{s(2)},…,x_{s(n)})\end{matrix}} $$

（または

$$ {C_k^n} $$

指定します

$$ {C_k \times C_k \times … \times C_k } $$

)

順方向への 4 分の 1 回転を呼びます。
$$ {R \,} $$
、
$$ {U \,} $$
、
$$ {L \,} $$
、
$$ {F \,} $$
、
$$ {B \,} $$
、
$$ {D \,} $$
顔用

右、上、左、前、後ろ、下。

$$ {* \,} $$
合成演算子 (
$$ {(f*g)(x) = g[f(x)] \,} $$
）。
$$ { (i,j) = f \in \mathfrak{S}_n : \forall k \in C_n , (k \ne i \ et \ k \ne j \Rightarrow f(k)=k) \ et \ f(i) = j \ et \ f(j)=i } $$

ジェネレーターと関係性: グループのプレゼンテーション

Xの要素ジェネレータ上の自由グループ( F _{X で示される) は、} Xの縮小されたワードのグループです。
デモ:

$$ {(F_X, \circ )} $$

はグループです:

法律
$$ { \circ } $$
グループの内部にある（法律
$$ { \circ } $$
得られた単語の縮小に加えて合成法則として定義される)
中性要素 1 を許容します
結合 (順列に関する合成法則)
一言
$$ {y_1^{e_1}…y_N^{e_N}} $$
逆から反転可能です
$$ { y_N^{-e_N}…y_1^{-e_1}} $$
。

定義: G のすべてのg に対してg ^{− 1} * H * g = Hが成立する場合、H を G の正規部分群と呼びます。

X を n =_カードX の有限集合とします。Yを縮小された単語のグループとします。

Dem: Fn/R はグループであり、これらの関係を満たす最大のグループです。前の表記法では、(G, o) は定義上、R の関係を満たす群 ( F n上の商群) であり、G’ を R の関係を満たす同じ生成子 X 上に構築された別の群であるとします。

$$ {\begin{matrix} \phi : & F_X & & \rightarrow & \ G’ \\ \ & w & & \mapsto \ & b_1^{e_1}b_2^{e_2}…b_l^{e_l}\end{matrix}} $$

(G’ の生成子に従って単語 w をその分解に関連付けます)。このアプリケーションは、次の群射です。

$$ { R \subset ker(f) } $$

G’ は R の関係を満たすため、f(R) = 1 となります。射に関する定理によれば、G は G’ の拡張であるため、G は R の関係を満たす X によって生成される最大のグループになります。G をグループとします。 G がF _n / Rと同型の場合、G は生成子として集合 X を持ち、関係 Y として持つと言います。ジェネレーターとリレーションシップのセットはプレゼンテーションと呼ばれます。表記法では、R の要素 r は r = 1 の形式の方程式として表されます。

例: 次数 n の巡回群には生成器 x と関係x ⁿ = 1があるため、次のようになります。

$$ { R=\{(x^n)^k | k \in Z\} \subset F_1={x^k | k \in Z}} $$

。したがって、 C _{n は}提示として認められ_ます。 x ⁿ = 1表示用の次数 na の二面体群D _n = { a , b | a ⁿ = 1、 b ² = 1、 a b a = b }

問題の概要

言葉の定義

Xを集合とする

$$ { X=\{x_1 , x_2 ,… , x_n \}\,} $$

そして別の素集合は次のように示されます

$$ { X^{-1}=\{x_1^{-1},…,x_{n}^{-1}\}} $$

これらのセットの任意の要素について、

$$ { x_k*x_k^{-1}=1 } $$

(中性要素)、

$$ { x_k^0=1 } $$

。単語は次の要素で構成されるシーケンスです。

$$ { X \cup X^{-1} \,} $$

力によって重み付けされる

$$ { e_i=\{-1,0,1\}\, } $$

。言葉が書かれています

$$ { w=x_1^{e_1}…x_N^{e_N} } $$

そしてその反対の言葉は次のように定義されます。

$$ { x_N^{-e_N}…x_1^{-e_1} } $$

縮小された単語は、空の単語 (1 つだけで構成される)、または次の形式の連続する 2 つの記号がない単語のいずれかです。

$$ { x*x^{-1} \,} $$

。もし

$$ { w = y_1^{e_1}…y_N^{e_N} } $$

が縮小された単語である場合、 l ( w ) = Nによってwの長さを定義します。

ルービックキューブに興味がある

Cube を研究するために使用される表記法によれば、問題は 2 つの形式で現れる可能性があります。完全に数学的な表記を使用してそれを扱うことも、R、U などのそれぞれの文字から単語の形式で扱うこともできます。順列に対応します (Cube の番号付けを参照)。したがって、X = {R,L,U,D,F,B} 上の単語の集合から立方体の順列の集合までの全射関数が存在します。順列の場合、長さは、解決された立方体から開始して、順列を取得するために実行される最小の移動数(= 考慮されるジェネレーター) として定義されます。

最初のアプリケーション: 最小限の動き

これらの動きから、各ノードが立方体の位置 (解決された立方体に適用される順列) を表すツリーを構築できます。恒等式から始めて、各ステップで n 回の基本動作で達成可能な立方体の可能な位置の数に等しいシーケンス ( S _n ) を構築できます。 S ₀ = 1、 S ₁ = 18、 S ₂ = 18 * 18 + 27があり、すべての n について、 S _n = 12 S _{n − 1} − 18 S _{n − 2}になります。実際、計算の精度を高めるためには、すでに到達した位置に戻ることを可能にするすべての順列を数えるべきではありません。したがって、これを行うには、条件を設定する必要があります (ここでは中央セクションの動きをカウントします)。同じ面上の 2 つの連続した動きや、同じ軸の周りの3 つの動きによって得られた位置はカウントしません。特定の状況では、 S _{n − 1 の}可能な動きの位置には 12 個と、 S _{n − 2}で実行できる 18 個だけが残っています。これらの動きは、動きが繰り返されていない位置 (または、我々が行った位置に対応します) に対応します。アイデンティティに戻る動きを繰り返した）。次に、シーケンスの一般項( S _n )を計算し、それを N (立方体の可能な位置の総数) に等しくして、n を決定します。次に、n = 17.3 がわかります。これは、18 回未満の移動では到達できない立方体の位置が存在することを示しています。 1 つの位置 (立方体の中心) には 20 回の動きが必要であることも証明されています (ルービックキューブの最適解を参照)。

ルービックキューブグループのジェネレーターと関係 – 定義

導入