循環ふるい分け

組合せ数学において、巡回ふるい分けとは、有限集合の1の根における生成関数を評価することで巡回群の作用を受けるオブジェクトの対称類を数える現象である。^[1]

C をn位の 元cによって生成される巡回群とする。C が集合 Xに作用するとする。X ( q ) を整数係数の多項式とする。このとき、すべての整数dに対して、 値X ( e ^{2 π id / n} ) がc ^dによって固定される元数である 場合 、三つ組 ( X、  C 、X ( q )) は巡回ふるい現象 ( CSP ) を示すと言われる。特に、 X ( 1 )は集合Xの濃度であり 、このためX ( q ) はXの生成関数と見なされる 。

q二項係数

${\displaystyle \left[{n \atop k}\right]_{q}}$

はqの多項式で定義される 。

${\displaystyle \left[{n \atop k}\right]_{q}={\frac {\prod _{i=1}^{n}(1+q+q^{2}+\cdots +q^{i-1})}{\left(\prod _{i=1}^{k}(1+q+q^{2}+\cdots +q^{i-1})\right)\cdot \left(\prod _{i=1}^{nk}(1+q+q^{2}+\cdots +q^{i-1})\right)}}.}$

q  = 1 におけるその値は通常の二項係数 であることは容易に分かるので、これは サイズ kの {1, 2, ..., n } の部分集合に対する生成関数である。これらの部分集合は、 n を法として集合の各要素に 1 を加えるという n次巡回群Cの自然な作用を持つ。例えば、n  = 4 およびk  = 2 のとき、群軌道は ${\displaystyle {\binom {n}{k}}}$

${\displaystyle \{1,3\}\to \{2,4\}\to \{1,3\}}$（サイズ2）

そして

${\displaystyle \{1,2\}\to \{2,3\}\to \{3,4\}\to \{1,4\}\to \{1,2\}}$（サイズ4）

^[2]によれば、qがn乗根のときにq二項係数を評価すると、対応する群要素によって固定された部分集合の数が与えられることが分かる。

n = 4、k = 2の例では、q二項係数は

${\displaystyle \left[{4 \atop 2}\right]_{q}=1+q+2q^{2}+q^{3}+q^{4};}$

この多項式をq = 1 で評価すると 6 になります (6 つの部分集合すべてが群の単位元によって固定されるため)。q =  −1 で評価すると 2 になります (部分集合 {1, 3} と {2, 4} は群生成子を 2 回適用することで固定されます)。q = ± i で評価すると0 になります (群生成子を 1 回または 3 回適用しても部分集合は固定されません)。

ライナー・スタントン・ホワイト論文では、次の例が示されています。

α をnの合成とし、W ( α ) を長さnで α _i文字がiに等しいすべての単語の集合とします。単語wの降下は、 となる任意のインデックスjです。単語の主要なインデックスをすべての降下の合計として定義します。 ${\displaystyle w_{j}>w_{j+1}}$${\displaystyle \operatorname {maj} (w)}$

この三つ組は巡回ふるい分け現象を示し、ここで[ n −1]の交差しない(1,2)配置の集合である 。^[3]${\displaystyle (X_{n},C_{n-1},{\frac {1}{[n+1]_{q}}}\left[{2n \atop n}\right]_{q})}$${\displaystyle X_{n}}$

λ をサイズnの長方形分割とし、X を形状λの標準ヤング図の集合とします。C = Z / nZ が昇格を介して Xに作用するとします。すると、巡回ふるい分け現象が示されます。多項式はフック長さの公式のq類似物であることに注意してください。 ${\displaystyle (X,C,{\frac {[n]!_{q}}{\prod _{(i,j)\in \lambda }[h_{ij}]_{q}}})}$

さらに、λ をサイズnの長方形分割とし、X を形状λの半標準ヤング図の集合とする。C = Z / kZ がk昇格を介してXに作用するとする。すると 巡回ふるい分け現象が現れる。ここで、s λ_はシュア多項式である。^[4]${\displaystyle (X,C,q^{-\kappa (\lambda )}s_{\lambda }(1,q,q^{2},\dotsc ,q^{k-1}))}$${\displaystyle \kappa (\lambda )=\sum _{i}(i-1)\lambda _{i}}$

増加するタブローは、行と列の両方が厳密に増加し、エントリの集合が何らかの に対しての形になる半標準ヤングタブローです。長さnの2つの行と最大エントリを持つ増加するタブローの集合を と表します。次に、 巡回ふるい分け現象を示します。ここで、 はKプロモーションを介して作用します。^[5]${\displaystyle 1,2,\dotsc ,\ell }$${\displaystyle \ell }$${\displaystyle Inc_{k}(2\times n)}$${\displaystyle 2n-k}$${\displaystyle (\operatorname {Inc} _{k}(2\times n),C_{2n-k},q^{n+{\binom {k}{2}}}{\frac {\left[{n-1 \atop k}\right]_{q}\left[{2n-k \atop n-k-1}\right]_{q}}{[n-k]_{q}}})}$${\displaystyle C_{2n-k}}$

をサイクル型λの順列の集合とし、超過数はちょうどj個とします。 とし、 が共役によってに作用するとします。 ${\displaystyle S_{\lambda ,j}}$${\displaystyle a_{\lambda ,j}(q)=\sum _{\sigma \in S_{\lambda ,j}}q^{\operatorname {maj} (\sigma )-\operatorname {exc} (\sigma )}}$${\displaystyle C_{n}}$${\displaystyle S_{\lambda ,j}}$

そして周期的ふるい分け現象を示す。^[6]${\displaystyle (S_{\lambda ,j},C_{n},a_{\lambda ,j}(q))}$