代数的組合せ論の問題

方針（部分空間束上の包除原理 = メビウス反転）

$g\in G=G{L}_n({\mathbb{F}}_q)$ に対し固定部分空間 $\mathrm{Fix}(g)=\{v:gv=v\}$ を考える。部分空間 $W\subseteq V$ に対し
$$f(W)=\#\{g:\mathrm{Fix}(g)=W\},F(W)=\#\{g:\mathrm{Fix}(g)\supseteq W\}=\sum _{U\supseteq W}f(U)$$
とおく。部分空間束のメビウス関数は $\dim W=k$ のとき $\mu (0,W)=(-1{)}^k{q}^{\left(\genfrac{}{}{0ex}{}{k}{2}\right)}$ であるから、メビウス反転により
$$D_n(q)=f(0)=\sum _W\mu (0,W)F(W)=\sum _{k=0}^n(-1{)}^k{q}^{\left(\genfrac{}{}{0ex}{}{k}{2}\right)}{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}_q{F}_k,$$
ただし $F_k$ は $\dim W=k$ のときの $F(W)$ である（$W$ によらない）。これは通常の包除原理の $q$ 類似である。

$F_k$ の計算　$W$ の基底を延長して $V$ の基底をとると、$g$ が $W$ の各元を固定する条件は、$g$ の行列が
$$\left(\begin{array}{cc}{I}_k& \ast \\ 0& A\end{array}\right),A\in G{L}_{n-k}({\mathbb{F}}_q),\ast \text{ は任意の }k\times (n-k)\text{ 行列}$$
の形であることと同値。よって $F_k=q^{k(n-k)}|G{L}_{n-k}({\mathbb{F}}_q)|$。

$n=3$ の場合　$|G{L}_0|=1,|G{L}_1|=q-1,|G{L}_2|=q(q^2-1)(q-1),|G{L}_3|=q^3(q^3-1)(q^2-1)(q-1)$、${\left(\genfrac{}{}{0ex}{}{3}{1}\right)}_q={\left(\genfrac{}{}{0ex}{}{3}{2}\right)}_q=q^2+q+1$ であり、$(q^2+q+1)(q-1)=q^3-1$ を使うと各項は
- $k=0$: $q^3(q^3-1)(q^2-1)(q-1)$
- $k=1$: $-(q^2+q+1)\cdot q^2\cdot q(q^2-1)(q-1)=-q^3(q^3-1)(q^2-1)$
- $k=2$: $+q\cdot (q^2+q+1)\cdot q^2(q-1)=q^3(q^3-1)$
- $k=3$: $-q^3\cdot 1\cdot 1=-q^3$

よって
$$D_3(q)=q^3\left[(q^3-1)(q^2-1)(q-2)+q^3-2\right].$$
$(q^3-1)(q^2-1)(q-2)=q^6-2q^5-q^4+q^3+2q^2+q-2$ なので
$$D_3(q)=q^3(q^6-2q^5-q^4+2q^3+2q^2+q-4)=q^9-2q^8-q^7+2q^6+2q^5+q^4-4q^3.$$

検算　$q=2$ のとき $D_3(2)=8\cdot 6=48$。$G{L}_3({\mathbb{F}}_2)$（位数 $168$）で $1$ を固有値にもたないのは特性多項式が既約 $3$ 次式の元、すなわち位数 $7$ の元で、その個数は $48$ であり一致する。

$g$ が固有値 $1$ をもたない $⟺$ $g-1$ が正則。巡回指数（cycle index）の恒等式 ${\sum }_{n\ge 0}{u}^n={\prod }_{\phi \ne z}{\prod }_{i\ge 1}(1-u^{\mathrm{deg}\phi }/q^{i\mathrm{deg}\phi }{)}^{-1}$ から、多項式 $z-1$ に対応する因子 ${\prod }_{i\ge 1}(1-u/q^i{)}^{-1}$ を除くと、${\sum }_n\frac{D_n(q)}{|G{L}_n({\mathbb{F}}_q)|}{u}^n=\frac{1}{1-u}{\prod }_{i\ge 1}(1-u/q^i)$ となる。オイラーの恒等式 ${\prod }_{i\ge 1}(1-u{t}^i)={\sum }_k\frac{(-1{)}^k{t}^{k(k+1)/2}{u}^k}{(1-t)\cdots (1-t^k)}$ ($t=1/q$) より
$$\frac{D_n}{|G{L}_n|}=\sum _{k=0}^n\frac{(-1{)}^k{t}^{k(k+1)/2}}{(1-t)\cdots (1-t^k)}.$$
$n=3$ では $\frac{D_3}{|G{L}_3|}=1-\frac{1}{q-1}+\frac{1}{(q-1)(q^2-1)}-\frac{1}{(q-1)(q^2-1)(q^3-1)}$。$|G{L}_3|=q^3(q-1)(q^2-1)(q^3-1)$ を掛けて
$$D_3=q^3\left[(q^3-1)(q^2-1)(q-2)+q^3-2\right]=q^3(q^6-2q^5-q^4+2q^3+2q^2+q-4)=q^9-2q^8-q^7+2q^6+2q^5+q^4-4q^3.$$
検算: $q=2$ のとき $512-512-128+128+64+16-32=48$。$G{L}_3({\mathbb{F}}_2)$（位数 168）で固有値 1 をもたない元は位数 7 の元のみで、その個数は $8\cdot 6=48$ で一致する。