← Lights Out and Snake Lemma
main.tex
\def\pgfsysdriver{pgfsys-dvipdfmx.def} % ★PGFドライバを強制
\documentclass{amsart}
\usepackage[left=2cm, right=2cm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage{amsfonts, amsthm, amssymb, mathtools,etoolbox}
\usepackage{blindtext}
\usepackage[colorlinks=true, urlcolor=blue, linkcolor=blue, citecolor=blue]{hyperref}
\usepackage{tikz,tikz-cd}
\usepackage{cleveref}
\usepackage{array}
\usepackage{quiver}
\usepackage[style=alphabetic,sorting=nyt]{biblatex}
\renewbibmacro{in:}{}
% \addbibresource{biblio.bib}
\addbibresource{CommonBiblio20240922.bib}
\tikzset{pullback/.style={minimum size=1.2ex,path picture={
\draw[opacity=1,black,-,#1] (-0.5ex,-0.5ex) -- (0.5ex,-0.5ex) -- (0.5ex,0.5ex);%
}}}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{todo}[theorem]{Todo}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{fact}[theorem]{Fact}
\theoremstyle{definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{question}[theorem]{Question}
\newtheorem{idea}[theorem]{Idea}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{answer}[theorem]{Answer}
\newcommand{\dq}[1]{``#1"}
\newcommand{\memo}[1]{\textcolor{red}{memo: #1}}
\newcommand{\invmemo}[1]{\textcolor{blue}{memo: #1}}
\newcommand{\para}[1]{\paragraph{\textbf{#1}}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\E}{\mathcal{E}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\id}{\mathrm{id}}
\newcommand{\op}{\mathrm{op}}
\newcommand{\ob}{\mathrm{ob}}
\newcommand{\Set}{\mathbf{Set}}
\newcommand{\FinSet}{\mathbf{FinSet}}
\newcommand{\PSh}{\mathbf{PSh}}
\newcommand{\Sh}{\mathbf{Sh}}
\newcommand{\Vect}{\mathbf{Vect}}
\newcommand{\Cont}{\mathbf{Cont}}
\newcommand{\Func}[2]{[#1,#2]}
\newcommand{\abs}[1]{\left|#1\right|}
\newcommand{\demph}[1]{\textbf{#1}}
\font\maljapanese=dmjhira at 2.5ex
\newcommand{\yo}{\textrm{\!\maljapanese\char"48}}
\newcommand{\Pow}{\mathcal{P}}
\newcommand{\cod}{\mathrm{cod}}
\newcommand{\Image}{\mathrm{Im}}
% \newcommand{\SolExt}{\mathrm{SolExt}}
\newcommand{\Solvable}{\mathrm{Solvable}}
% \DeclareMathOperator{\ker}{ker}
\DeclareMathOperator{\coker}{coker}
\DeclareMathOperator{\Ker}{Ker}
\DeclareMathOperator{\Coker}{Coker}
\DeclareMathOperator{\corank}{corank}
\DeclareMathOperator{\rank}{rank}
\title{Lights Out and Snake Lemma}
\author{げんがくとほら}
\thanks{ZEN University. \url{ryuya_hora@zen.ac.jp}}
% \date{\today}
\subjclass[2020]{MSC}
\keywords{Keywords}
\begin{document}
\begin{abstract}
\end{abstract}
\maketitle
\tableofcontents
\section{一次元ライツアウト}
\subsection{問題と有限体不変量による解法}
\begin{problem}
$n$個のランプが一列に並んでいる．$n$個のランプのうち一つを叩くと，そのランプとその隣のランプの明滅が逆転する．(端っこを叩くと$2$個変化し，端っこ以外を叩くと$3$個変化する．)
\begin{enumerate}
\item どんな初期状態から始めても全てのライトを消せるような$n$を全て求めよ
\item 初期状態が与えられたときに，全てのライトを消せるか判定する方法はあるか?
\end{enumerate}
\end{problem}
\begin{center}
\href{https://editor.p5js.org/hora/full/RSb6d6oJT}{[実際に遊べるボタン \url{https://editor.p5js.org/hora/full/RSb6d6oJT}]}
\end{center}
% \begin{answer}[洞の回答 unsophisticated]
% $\F_4\cong \F_2[x]/(x^2+x+1)$の元を不変量として取ると良い．詳しくは，次のように考える．右から$k$番目($0\leq k<n$)番目のランプがついていたら$x^k$を足すことで，ランプの各状態$s$に$\F_2 [x]$の元$f_s(x)$を割り当てる．例えば，
% \[
% s={\circ} {\bullet} {\circ} {\bullet} {\bullet}{\circ} {\bullet} {\circ}
% \]
% には点灯部分$\circ$が右から$7,5,2,1$部分にあるので$f_s(x)=x^7+x^5+x^2+1\in \F_2 [x]$を割り当てる．すると，端っこでは\demph{ない}ランプ$0<k<n-1$を叩く操作は，$x^{k+1}+x^k+x^{k-1} =x^{k-1}(x^2+x+1)$を足す操作に対応する．従って，$x^2+x+1$で割った剰余環$\F_2[x]/(x^2+x+1)= \F_2[\omega]= \F_4$の元$f_s(\omega)$としては不変になる．
% 一方で，端っこのランプを叩く操作は
% \begin{itemize}
% \item 右端を叩くと$x+1$を足す
% \item 左端を叩くと$x^{n-1}+x^{n-2}$を足す
% \end{itemize}
% という操作になっているから，$x+1$と$x^{n-1}+x^{n-2}$が$\F_2[x]/(x^2+x+1)= \F_2[\omega]= \F_4$の元として等しいのはいつか，という問題になる．$x+1=x^2$, $x^{n-1}+x^{n-2}=x^n$だから，これは$x^2=x^n$となる$n$はいくつかという問題になるから，($\F_4^{\times}\cong \Z/3\Z$より)
% \[x+1=x^{n-1}+x^{n-2} \iff n\equiv 2\mod 3\]
% を得る．
% 結果として，状態$s$からライトを全て消せるための必要条件は，$\F_2$線形空間$\langle 1+\omega, \omega^{n-1}+\omega^{n-2}\rangle \subset \F_4$に
% $f_s(\omega)\in \F_4$が入っていることである．これが十分条件であることは，具体的に手順を示すことでわかる. (実際，まずは両端を使って不変量を$0$に調整してから，端でない部分を用いて点灯部分を\dq{右に移して}いくと消える．) これは，$(2)$の答えを与えている．
% 従って，$(1)$の答えは，$n\not\equiv 2\mod 3$なる全ての$n$である．実際，$n\not\equiv 2\mod 3$のとき，$\langle 1+\omega, \omega^{n-1}+\omega^{n-2}\rangle \subset \F_4$は全体になっているので可能であるし，$n\equiv 2\mod 3$のときは$1$次元部分空間になっているから，$s$として不変量がずれているもの(例えば$s={\bullet}{\bullet}\dots {\bullet} {\bullet} {\circ}$など)を取ればライトが消せないことがわかる．
% \end{answer}
\begin{answer}
% [もう少し整理された回答]
次の$2$ステップに分けて考える．
\begin{enumerate}
\item まず，両端のランプを叩けないルールで考える．
\item 次に，両端のランプを叩けるルールで考え直す．
\end{enumerate}
\begin{enumerate}
\item \textbf{まず，両端のランプを叩けないルールで考える．}
$0,\dots, n-$で添字付けられた$n$個のランプの点滅パターンに$\F_4=\F_2 [\omega]$の元を次のように割り振る．
\begin{description}
\item[{[$\F_4$不変量]}] $i$番目のランプに$\omega^i\in \F_4$を割り振り，点灯しているランプにわたって足し合わせる. (e.g. Figure \ref{fig:F4Invariant})
\end{description}
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[x=1cm,y=1cm]
% ---- 設定 ----
\def\n{12} % 箱の個数
\def\w{1.2} % 箱の幅
\def\h{0.8} % 箱の高さ
% ---- ランプパターン ----
% 1=点灯, 0=消灯
\def\lamppattern{{1,1,0,1,1,1,0,0,1,0,0,1}}
% 計算式の位置
\def\yFormula{-0.8}
% ---- 本体 ----
\foreach \i in {1,...,\n}{
\pgfmathsetmacro{\x}{(\i-1)*\w}
\draw (\x,0) rectangle ++(\w,\h);
% 周期3でラベル (1, ω, ω^2) → 常に箱の中に表示
\pgfmathtruncatemacro{\r}{mod(\i-1,3)}
\ifcase\r
\node at (\x+0.5*\w,0.5*\h) {$1$};
\def\val{$1$}
\or
\node at (\x+0.5*\w,0.5*\h) {$\omega$};
\def\val{$\omega$}
\or
\node at (\x+0.5*\w,0.5*\h) {$\omega^2$};
\def\val{$\omega^2$}
\fi
% ランプ状態取得
\pgfmathparse{\lamppattern[\i-1]}
\ifnum\pgfmathresult=1
% 点灯ランプ
\fill[yellow] (\x+0.5*\w, \h+0.5) circle (0.2);
\draw (\x+0.5*\w, \h+0.5) circle (0.2);
% 下の式に値を出力
\node at (\x+0.5*\w,\yFormula) {\val};
% プラス記号（最後以外）
\ifnum\i<\n
\node at (\x+\w,\yFormula) {$+$};
\else
\node at (\x+\w,\yFormula) {\hspace{30pt}$=\omega^2$};
\fi
\else
% 消灯ランプ
\draw (\x+0.5*\w, \h+0.5) circle (0.2);
% 下は空欄（プラスも書かない）
\fi
}
\end{tikzpicture}
\caption{An example of the $\F_4$-invariant}
\label{fig:F4Invariant}
\end{figure}
すると，$0<i<n-1$のどのランプを叩いても，$\F_4$不変量には$\omega^{i-1}+\omega^{i}+\omega^{i+1}=0$が足し合わされるだけで，$\F_4$不変量は(名前のとおり)不変である．
実は$\F_4$不変量が$0$であることは，全て消せることの必要十分条件であることがわかる．必要性は不変量であることからok. 十分性は貪欲法でわかる．つまり，不変量が$0$なら，今点灯しているランプのうち一番左にあるものを$i$として，$i+1$を押せばいい! (この操作は，右$2$つのランプ以外が消えるところまでは明らかに順調にすすむ．そして，右$2$つのランプは$\F_4$上の$\F_2$基底なので，右$2$つのランプ以外が消えたときには$\F_4$不変量のおかげで自動的に消えている.)
\item \textbf{次に，両端のランプを叩けるルールで考え直す．}
端を例外扱いしたくないので，左右にライトを$1$個ずつ付け加えて，合計で$n+2$個のランプを$0\leq i \leq n+1$で添字づけて考える．このとき，操作は$0<i<n+1$を選んで押すことにすると，$0<i<n+1$番目のランプへの作用は変わらない．よって問題は前半の議論に帰着され「$n$個のランプの明滅状態が与えられている．これの左右に明滅をうまく選択したランプを$1$つずつ配置することで，全体の$\F_4$不変量を$0$にできるか？」という問題になる！
$n=0,1$は問題は簡単だから，$n\geq 2$の場合を考える．すると，真ん中の$n$個で$\F_4$の元は全て実現されるから，問題は「$1, \omega^{n+1}$が$\F_2$線型空間として$\F_4$を張るような$n$を求めよ」というものになる．これは，$n+1 \not\equiv 0\mod 3$だから，$n\equiv 0,1 \mod 3$が答えである．さらに，$n\equiv 2$のときは，(長さ$n$のままの)$\F_4$不変量が$\F_2$に入ることと，消灯できることは同値になる．
\end{enumerate}
\end{answer}
後の参照のため，消灯可能性の判定方法をメモしておこう．
\begin{proposition}[消灯可能性]\label{prop:OnedimChecking}
与えられたランプの配置$a=(a_i)_{i=1}^n\in \F_2^n$について，以下は同値
\begin{itemize}
\item $a$は消灯可能
\item $\F_4$不変量$\sum_i a_i \omega^i\in \F_4$が，両端の$\F_4$値の張る部分$\F_2$線形空間$\langle1, \omega^{n+1}\rangle\subset \F_4$に入っている．
\end{itemize}
\end{proposition}
\subsection{線型写像のランクとして}\label{ssec:LinearRankSolution}
この問題は，次のような自己線型写像のランクの問題と思える．$\F_2^n$の標準基底を$e_1, \dots, e_n$として，$e_i$と$i$番目のランプを同一視する．
そして，$\phi_n\colon \F_2^n \to \F_2^n$を
\[
\phi_n(e_i)=
\begin{cases}
e_1+e_2 &(i=1)\\
e_{i-1}+e_{i}+e_{i+1} &(1<i<m)\\
e_{n-1}+e_n &(i=n)
\end{cases}
\]
で定める．例えば，$\phi_5$の行列表示は
\[
\begin{pmatrix}
1&1&0&0&0\\
1&1&1&0&0\\
0&1&1&1&0\\
0&0&1&1&1\\
0&0&0&1&1\\
\end{pmatrix}
\]
である．
$\phi_n$を用いると，ランプの消灯可能性問題は次のような同値な命題に言い換えられる:
\begin{itemize}
\item $n$個のランプのライツアウトが全て消灯可能
\item $\phi_n$は全射
\item $\phi_n$は同型
\item $n$個のランプのライツアウトが全て，本質的に一意的な方法で消灯可能
\end{itemize}
\begin{lemma}\label{lem:CokerExpression}
$\Coker\phi_n$は，ライトの明滅状態の操作で移りあう同値類の集合である．したがってその個数は$\#\Coker \phi_n = 2^{\corank \phi_n}$に等しい．
\end{lemma}
我々の議論で示したことは，
\begin{equation}\label{eq:OneDimensioncorank}
\corank \phi_n =
\begin{cases}
0&(n\not \equiv 2 \mod 3)\\
1&(n \equiv 2 \mod 3)\\
\end{cases}
\end{equation}
である．
% 我々の左右にランプを追加する論法は，大袈裟に書けば次のような構造になっている．
% % https://q.uiver.app/#q=WzAsMTAsWzIsMiwiXFxtYXRoYmJ7Rn1fMl57bisyKD1cXHRleHRybXthbGx9KX0iXSxbMSwxLCJcXG1hdGhiYntGfV8yXnsyKD1cXHRleHRybXtlZGdlfSl9Il0sWzEsMywiXFxtYXRoYmJ7Rn1fNCJdLFszLDEsIlxca2VyIFxcdGF1Il0sWzQsMCwiMCJdLFswLDQsIjAiXSxbMiwwLCJLIl0sWzMsMywiXFxtYXRoYmJ7Rn1fMl57big9XFx0ZXh0cm17YnVsa30pfSJdLFswLDAsIjAiXSxbNCw0LCIwIl0sWzAsMiwiXFx0YXUiLDAseyJzdHlsZSI6eyJoZWFkIjp7Im5hbWUiOiJlcGkifX19XSxbMywwLCIiLDAseyJzdHlsZSI6eyJ0YWlsIjp7Im5hbWUiOiJtb25vIn19fV0sWzQsM10sWzIsNV0sWzAsNywiXFxwaV97XFx0ZXh0cm17YnVsa319IiwwLHsic3R5bGUiOnsiaGVhZCI6eyJuYW1lIjoiZXBpIn19fV0sWzEsMCwiaV97XFx0ZXh0cm17ZWRnZX19IiwwLHsic3R5bGUiOnsidGFpbCI6eyJuYW1lIjoibW9ubyJ9fX1dLFs4LDFdLFs3LDldLFszLDcsIlxcc2lnbWEiLDAseyJjdXJ2ZSI6LTR9XSxbNiwzLCJcXGtlciBcXHNpZ21hIiwwLHsic3R5bGUiOnsidGFpbCI6eyJuYW1lIjoibW9ubyJ9fX1dLFsxLDIsIlxcdGF1X3tcXHRleHRybXtlZGdlfX0iLDIseyJjdXJ2ZSI6NH1dLFs2LDEsIlxca2VyIFxcdGF1X3tcXHRleHRybXtlZGdlfX0iLDIseyJzdHlsZSI6eyJ0YWlsIjp7Im5hbWUiOiJtb25vIn19fV0sWzYsMCwiIiwyLHsic3R5bGUiOnsibmFtZSI6ImNvcm5lciJ9fV1d
% \[\begin{tikzcd}
% 0 && K && 0 \\
% & {\F_2^{2(=\textrm{edge})}} && {\Ker \tau \cong \F_2^{n(=\textrm{bulk})}} \\
% && {\F_2^{n+2(=\textrm{all})}} \\
% & {\F_4} && {\F_2^{n(=\textrm{bulk})}} \\
% 0 &&&& 0
% \arrow[from=1-1, to=2-2]
% \arrow["{\ker \tau_{\textrm{edge}}}"', tail, from=1-3, to=2-2]
% \arrow["{\ker \sigma}", tail, from=1-3, to=2-4]
% \arrow["\lrcorner"{anchor=center, pos=0.125, rotate=-45}, draw=none, from=1-3, to=3-3]
% \arrow[from=1-5, to=2-4]
% \arrow["{i_{\textrm{edge}}}", tail, from=2-2, to=3-3]
% \arrow["{\tau_{\textrm{edge}}}"', curve={height=24pt}, from=2-2, to=4-2]
% \arrow[tail, from=2-4, to=3-3]
% \arrow["\phi_n", curve={height=-24pt}, from=2-4, to=4-4]
% \arrow["\tau", two heads, from=3-3, to=4-2]
% \arrow["{\pi_{\textrm{bulk}}}", two heads, from=3-3, to=4-4]
% \arrow[from=4-2, to=5-1]
% \arrow[from=4-4, to=5-5]
% \end{tikzcd}\]
% ここで，左上から右下に降りる完全列は，ランプの列の
\subsection{\texorpdfstring{$\F_4$}{F4}不変量とランクを構造的に理解する}\label{ssec:StructualOneDim}
我々は，\begin{description}
\item[bulk] 長さ$n$のランプ列の議論を，
\item[all] 一旦$n+2$に拡張することで，
\item[edge] 結果的に両端の$\F_4$不変量の話に帰着した．
\end{description}
このことは，次のように蛇の補題の形の\footnote{この形の図式を選んだのは恣意的である．Kernelの交換という基本的な事実より，蛇の補題というパッケージの方が有名なので牛刀割鶏だが借りている．}図式で理解できる．考えている圏は$\Vect_{\F_2}$．
% https://q.uiver.app/#q=WzAsMTgsWzIsMSwiXFxGXzJee24rMig9XFx0ZXh0cm17YWxsfSl9Il0sWzEsMSwiXFxGXzJeezIoPVxcdGV4dHJte2VkZ2V9KX0iXSxbMywxLCJcXEZfMl57big9XFx0ZXh0cm17YnVsa30pfSJdLFswLDEsIjAiXSxbNCwxLCIwIl0sWzIsMCwiXFxTb2xFeHQgXFxjb25nIFxcRl8yXntuKD1cXHRleHRybXtidWxrfSl9Il0sWzMsMiwiMCJdLFszLDAsIlxcRl8yXntuKD1cXHRleHRybXtidWxrfSl9Il0sWzIsMiwiXFxGXzQiXSxbMSwyLCJcXEZfNCJdLFswLDAsIjAiXSxbMiwzLCIwIl0sWzEsMCwiSyJdLFswLDIsIjAiXSxbNCwyLCIwIl0sWzEsMywiPyJdLFszLDMsIjAiXSxbNCwzLCIwIl0sWzcsMiwiPSIsMSx7InN0eWxlIjp7ImhlYWQiOnsibmFtZSI6Im5vbmUifX19XSxbMiw2XSxbOCw2XSxbOSw4LCI9IiwxLHsic3R5bGUiOnsiaGVhZCI6eyJuYW1lIjoibm9uZSJ9fX1dLFszLDFdLFsxLDAsIiIsMCx7InN0eWxlIjp7InRhaWwiOnsibmFtZSI6Im1vbm8ifX19XSxbMCwyLCIiLDAseyJzdHlsZSI6eyJoZWFkIjp7Im5hbWUiOiJlcGkifX19XSxbMiw0XSxbMSw5LCJcXHRhdV97XFxtYXRocm17ZWRnZX19Il0sWzAsOCwiXFx0YXUiLDAseyJzdHlsZSI6eyJoZWFkIjp7Im5hbWUiOiJlcGkifX19XSxbOCwxMV0sWzEyLDEsIiIsMCx7InN0eWxlIjp7InRhaWwiOnsibmFtZSI6Im1vbm8ifX19XSxbMTAsMTJdLFsxMiw1LCIiLDAseyJzdHlsZSI6eyJ0YWlsIjp7Im5hbWUiOiJtb25vIn19fV0sWzUsNywiXFxwaGlfbiJdLFs1LDAsIiIsMCx7InN0eWxlIjp7InRhaWwiOnsibmFtZSI6Im1vbm8ifX19XSxbMTMsOV0sWzYsMTRdLFs5LDE1XSxbMTUsMTFdLFs3LDE1LCJcXGRlbHRhIiwxLHsibGFiZWxfcG9zaXRpb24iOjYwLCJzdHlsZSI6eyJib2R5Ijp7Im5hbWUiOiJkb3R0ZWQifSwiaGVhZCI6eyJuYW1lIjoiZXBpIn19fV0sWzExLDE2XSxbMTYsMTddLFs2LDE2XV0=
\[\begin{tikzcd}[row sep=30pt]
0 & {\F_2^{2(=\textrm{edge})}} & {\F_2^{n+2(=\textrm{all})}} & {\F_2^{n(=\textrm{bulk})}} & 0 \\
0 & {\F_4} & {\F_4} & 0 & 0
\arrow[from=1-1, to=1-2]
\arrow[tail, from=1-2, to=1-3]
\arrow["{\tau_{\mathrm{edge}}}", from=1-2, to=2-2]
\arrow[two heads, from=1-3, to=1-4]
\arrow["\tau", two heads, from=1-3, to=2-3]
\arrow[from=1-4, to=1-5]
\arrow[from=1-4, to=2-4]
\arrow[from=2-1, to=2-2]
\arrow["{=}"{description}, no head, from=2-2, to=2-3]
\arrow[from=2-3, to=2-4]
\arrow[from=2-4, to=2-5]
\end{tikzcd}\]
上の短完全列は，単に長さ$n$のランプ列に端っこ$2$つを追加して$n+2$個にしたことを表している．下の自明な短完全列は$\F_4$不変量の列で，左$2$箇所に置いた理由はedgeとallでは$\F_4$不変量を考えたいから\footnote{元の証明でも，結局不変量を測るのはここ．Allで消えているかは消灯可能性そのものだし，証明のトドメはedgeでの不変量の次元を見ることだった．Bulkでは，「allに拡張して不変量を$0$にできますか？」という形でしか聞かれていなくて，結局allで考えてる．}．$\tau$は，$\F_4$不変量をとる写像で，$\tau_{\textrm{edge}}$はその両端への制限である．
この図式に関して，\demph{蛇の補題を適用しよう！}
右列，中列，左列の順ににkernel, cokernelを計算していく．
\[\begin{tikzcd}[row sep=30pt]
0 & \Ker \tau_{\mathrm{edge}} & {
% \Ker \tau
\Solvable
} & {\F_2^{n(=\textrm{bulk})}} \\
0 & {\F_2^{2(=\textrm{edge})}} & {\F_2^{n+2(=\textrm{all})}} & {\F_2^{n(=\textrm{bulk})}} & 0 \\
0 & {\F_4} & {\F_4} & 0 & 0 \\
& \Coker \tau_{\mathrm{edge}} & 0 & 0 & 0
\arrow[from=1-1, to=1-2]
\arrow[tail, from=1-2, to=1-3]
\arrow[tail, from=1-2, to=2-2]
\arrow["{\sigma_n}", from=1-3, to=1-4]
\arrow[tail, from=1-3, to=2-3]
\arrow["{=}"{description}, no head, from=1-4, to=2-4]
\arrow["\delta"{description, pos=0.6}, dotted, two heads, from=1-4, to=4-2]
\arrow[from=2-1, to=2-2]
\arrow[tail, from=2-2, to=2-3]
\arrow["{\tau_{\mathrm{edge}}}", from=2-2, to=3-2]
\arrow[two heads, from=2-3, to=2-4]
\arrow["\tau", two heads, from=2-3, to=3-3]
\arrow[from=2-4, to=2-5]
\arrow[from=2-4, to=3-4]
\arrow[from=3-1, to=3-2]
\arrow["{=}"{description}, no head, from=3-2, to=3-3]
\arrow[two heads, from=3-2, to=4-2]
\arrow[from=3-3, to=3-4]
\arrow[from=3-3, to=4-3]
\arrow[from=3-4, to=3-5]
\arrow[from=3-4, to=4-4]
\arrow[from=4-2, to=4-3]
\arrow[from=4-3, to=4-4]
\arrow[from=4-4, to=4-5]
\end{tikzcd}\]
\begin{description}
\item[右列] 右列は簡単で，$\Ker$は当然$\F_2^n$のままだし，$\Coker$は$0$になる．
\item[中列] 中列が$\F_4$不変量に関する本質的な部分である．$\Coker$は簡単で，$n\geq 2$という仮定のもと，$\tau$ ($=$ $\F_4$不変量をとる射)は全射であるから，$\Coker \tau=0$となる．問題は$\Ker \tau$である．{$\Ker \tau$}は$\F_4$不変量が消えているような$n+2$長さのランプ列の空間である．不変量の議論を用いて言い換えれば，\demph{$\Ker \tau$はbulk操作だけで消せるランプ配置の空間}である！ これを$\Solvable$と図式内では書いている．
\item[左列] 左列が$n\equiv 2\mod 3$の現れる場所である! けどすぐ後で計算する．
\end{description}
我々の不変量の議論は，標準的に生える射(図で$\sigma_n\colon \Solvable \to \F_2^n$と書かれた射)に注目している．(前節の$\phi_n$との関係は Remark \ref{rem:RelationWithPhi}に書いた．) 実際，初期配置$\in \F_2^n$が消灯可能なのは，Solvableな$n+2$配置に拡張できるとき,
つまり$\sigma_n$の像に入っているときである！ 知りたい操作同値類の個数は$\Coker\sigma_n$である(cf. Lemma \ref{lem:CokerExpression})が，蛇の補題より
\[
\Coker\sigma_n \cong \Coker \tau_{\mathrm{edge}}
\]
である！(左辺の次元はa prioriには難しいが)右辺の次元は具体的な$2\to2$次元$\F_2$線型写像なので，次のように計算できる：
$\tau_{\mathrm{edge}}\colon \F_2^2\to \F_4$は，$2$つの基底$e_0, e_{n+1}$をそれぞれ$1, \omega^{n+1}\in \F_4$に送る．したがって，$n\not \equiv 2 \mod 3$のときは($\F_2$線型空間として)同型で，$\Coker \tau_{\mathrm{edge}}$は$0$次元になる．$n\not \equiv 2 \mod 3$のときは$\Coker \tau_{\mathrm{edge}}$は$1$次元になる．
\[
\dim_{\F_2}(\Ker \tau_{\mathrm{edge}} )= \dim_{\F_2}(\Coker \tau_{\mathrm{edge}})=
\begin{cases}
0 &(n\not \equiv 2 \mod 3)\\
1 &(n\equiv 2 \mod 3)
\end{cases}
\]
これで数え上げ問題が解けた！
\begin{remark}[前節の$\phi_n$はどこにいるのか]\label{rem:RelationWithPhi}
操作の空間$\F_2^{n(=\textrm{bulk})}$を全消灯状態状態に作用させることで，線型写像$\alpha:\F_2^{n(=\textrm{bulk})} \to \Ker_{\tau}$を得る．これが実は同型になり，その同型$ \F_2^{n(=\textrm{bulk})}\cong \Ker_{\tau}$を介して，$\phi_n$と$\sigma_n$は同一視される．
実際，両者の次元は共に$n$であることが(上の完全列を見るなどして)わかる．さらに，比較写像$\alpha$が単射であることが組み合わせ論的議論からわかる．(Kernelに入っているとして，左端のランプから順に見ていくといい．)
\end{remark}
\subsection{消灯可能性を境界準同型で理解する}
では，消灯可能性の判定方法(Proposition \ref{prop:OnedimChecking})はどのように理解できるのだろうか？実は，これこそ蛇の補題の完全性に関わる部分である．ランプの配置$a=(a_i)\in \F_2^n$について，
\[
\text{$a$は消灯可能} \iff a\in \Image(\sigma_n) \iff \delta(a)=0
\]
である．左の同値性はいわゆる不変量の議論で，右の同値性は蛇の補題における境界準同型の定義域での完全性そのものである．そして，$\delta(a)=0$という条件はまさにProposition \ref{prop:OnedimChecking}における条件
\begin{itemize}
\item $\F_4$不変量$\sum_i a_i \omega^i\in \F_4$が，両端の$\F_4$値の張る部分$\F_2$線形空間$\langle1, \omega^{n+1}\rangle\subset \F_4$に入っている．
\end{itemize}
そのものである！！境界準同型の構成では，「下，左，下，左，下」と二回ほど左に"遡る"ステップがある．それぞれで何をするか見てみよう．
\begin{description}
\item[下] 最初の下は$=$なので何もしない．
\item[左] 最初の左は，両端になんでもいいのでライトをくっつける操作に対応する．なんでもいいので，我々は両端に消えたランプがつけることにする．
\item[下] $\F_4$不変量を見る．両端に消えたランプをつけたので，これは元の配置の$\F_4$不変量を見ているのと同じ．
\item[左] $=$なので何もしない．
\item[下] ここで，$\Image(\tau_{\mathrm{edge}})= \langle1, \omega^{n+1}\rangle \subset\F_4$に入っているかによって場合わけする．
\end{description}
なんてこった！
\newpage
\section{二次元ライツアウト}
\begin{problem}[$2$次元の場合](同様に$d$次元もできるはず)
$n,m$は$2$以上の整数とする．
$n \times m$個のランプが長方形状に並んでいる．$n\times m$個のランプのうち一つを叩くと，そのランプとその隣のランプの明滅が逆転する．
\begin{enumerate}
\item どんな初期状態から始めても全てのライトを消せるような$n,m$を全て求めよ
\item 与えられた$n,m$に対して，操作による同値類がいくつあるか答えよ．
\item 初期状態が与えられたときに，全てのライトを消せるか判定する方法はあるか?
\end{enumerate}
\end{problem}
\begin{center}
\href{https://editor.p5js.org/hora/sketches/G6H7A2lv5}{[実際に遊べるボタン \url{https://editor.p5js.org/hora/sketches/G6H7A2lv5}]}
\end{center}
\subsection{テンソル線型写像のランクとして}
(1),(2)に関しては，テンソルを用いて簡潔に計算できる！
次の線形代数の事実を使う．
\begin{lemma}\label{lem:corankCalculus}
体$K$上の線型写像$f_0\colon V_0 \to W_0$, $f_1\colon V_1 \to W_1$について，
\[
\rank(f_0\otimes f_1) = \rank (f_0)\cdot \rank(f_1)
\]
% \[
% \corank(f_0\otimes f_1) = \dim_K W_1 \cdot \corank (f_0) + \dim_K W_0 \cdot \corank (f_1)- \rank (f_0)\cdot \rank(f_1)
% \]
\end{lemma}
これを用いれば，$\rank f + \corank f = \dim_K (\cod f)$と合わせてテンソルの$\corank$もわかる．
\begin{answer}[A short answer for (1),(2).]
Subsection \ref{ssec:LinearRankSolution}の方法を用いれば，$1$次元の場合に帰着できる．実際，我々が計算するべきものは線型写像
\[
\phi_{n,m} \colon \F_2^{nm}\to \F_2^{nm}
\]
\[
\phi_{n,m}(e_{i,j}) \coloneqq \sum_{1\leq i',j'\leq n,\; |i-i'|\leq 1,\; |j-j'|\leq 1} e_{i',j'}
\]
の$\corank\phi_{n,m}$である．これさえわかれば，(2)の答えは
\[
\text{(2)の答え} = 2^{\corank\phi_{n,m}}
\]
とわかり，したがって
\[
\text{(1)の答え} = \text{$\corank\phi_{n,m}=0$となる$n,m$}
\]
もわかる．
ところで，標準的な基底を自然に対応させることで，$\phi_{n,m}$は$\phi_n \otimes \phi_m$と同一視できる！
\[
\begin{tikzcd}
\F_2^{nm}\ar[r, "\phi_{n,m}"] \ar[d, "\cong"]&\F_2^{nm} \ar[d, "\cong"]\\
\F_2^n \otimes \F_2^m \ar[r, "\phi_{n} \otimes \phi_{m}"]&\F_2^n \otimes \F_2^m
\end{tikzcd}
\]
% (体上では)一般にimage factorizationはテンソルで保たれるから，
よって，
\[
\rank (\phi_{n,m}) = \rank (\phi_{n}\otimes \phi_{m}) = \rank (\phi_{n})\times \rank( \phi_{m})
\]
となり，
\begin{align*}
\corank (\phi_{n,m}) &= nm- \rank (\phi_{n})\times \rank( \phi_{m})\\
&= nm- (n-\corank (\phi_{n}))\times (m-\corank( \phi_{m}))\\
&= m\cdot \corank (\phi_{n})+ n\cdot\corank( \phi_{m}) - \corank (\phi_{n})\cdot\corank( \phi_{m})
\end{align*}
を得る．Eq.\ref{eq:OneDimensioncorank}を用いると，次のように(2)の答えを得る．
\begin{proposition}\label{prop:CountingTwoDim}
\[
\text{操作による同値類の個数} =
\begin{cases}
1 &(n,m \not \equiv 2 \mod 3)\\
2^n &(n \not \equiv 2 \mod 3,\text{ and } m \equiv 2 \mod 3)\\
2^m &(n \equiv 2 \mod 3,\text{ and } m \not \equiv 2 \mod 3)\\
2^{n+m-1} &(n,m \equiv 2 \mod 3)
\end{cases}
\]
\end{proposition}
特に，どんな配置でも消灯できるための必要十分条件は$n,m \not \equiv 2 \mod 3$.
\end{answer}
\subsection{構造的な解析}
前節の証明は簡潔であり個数までわかる定量的なものであったが，この節ではより構造的な理解を目指す．具体的には，不変量を用いることで，ライトを消す最短手順や消せない場合の判定もできるようにより多くの情報を見る．内容はSubsection \ref{ssec:StructualOneDim}とパラレルである．
$1$次元の場合と同様に$(1+n+1)\times (1+m+1)$に拡張して内部のマスしか押せないルールに帰着する．
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[x=1.4cm,y=-1.2cm] % 上→下に行を描画
% ====== 基本設定 ======
\def\nr{4} % 行数
\def\nc{6} % 列数
\def\rad{0.14} % ランプ半径
% ====== 点灯パターン（行優先；要素数 = nr*nc；1=点灯, 0=消灯） ======
\def\lamppattern{%
1,0,1,0,1,0,%
0,1,0,1,0,1,%
1,1,0,0,1,0,%
0,0,1,1,0,1%
}
% ====== 行・列ラベル（必要に応じて編集；数式は $...$ で） ======
\def\rowsums{$0$, $0$, $\omega^2$, $1$} % 要素数 = nr
\def\colsums{$\omega$, $\omega$, $0$, $\omega^2$, $\omega^2$, $\omega$} % 要素数 = nc
% ====== 本体：セルとランプ ======
% lamppattern を順番に消費して配置（行優先）
\foreach[count=\k from 1] \lamp in \lamppattern {
% 行列位置を k から復元
\pgfmathtruncatemacro{\i}{ceil(\k/\nc)}
\pgfmathtruncatemacro{\j}{mod(\k-1,\nc)+1}
\pgfmathsetmacro{\x}{\j}
\pgfmathsetmacro{\y}{\i}
% (i+j+1) mod 3 により 1, ω, ω^2 を表示
\pgfmathtruncatemacro{\m}{mod(\i+\j+1,3)}
\ifcase\m
\node at (\x,\y) {$1$};
\or
\node at (\x,\y) {$\omega$};
\or
\node at (\x,\y) {$\omega^2$};
\fi
% ランプ（\lamp が 1 なら点灯, 0 なら消灯）
\ifnum\lamp=1
\fill[yellow] (\x,\y-0.45) circle (\rad);
\draw (\x,\y-0.45) circle (\rad);
\else
\draw (\x,\y-0.45) circle (\rad);
\fi
}
% ====== 行ラベル（右側） ======
\pgfmathsetmacro{\xlab}{\nc + 0.8}
\foreach[count=\ri from 1] \rtext in \rowsums {
\node at (\xlab,\ri) {\rtext};
}
% ====== 列ラベル（下側） ======
\pgfmathsetmacro{\ylab}{\nr + 0.8}
\foreach[count=\cj from 1] \ctext in \colsums {
\node at (\cj,\ylab) {\ctext};
}
\end{tikzpicture}
\end{figure}
\begin{lemma}\label{lem:TwoDimBulk}
内部しか押せない場合，全て消せるための必要十分条件は，全ての行と全ての列で$\F_4$不変量が$0$になることである．
\end{lemma}
より厳密に言えば，「$i,j$成分に$\omega^{i+j}\in \F_4$を割り振ったとき，どの行とどの列を見ても点灯ランプにおける値の総和が$0$になっていること」と同値になっている．
\begin{proof}
証明も$1$次元と同様である．必要性は，この量($\F_4^{\text{行数}+\text{列数}}$の元)が任意の(内部！)操作で不変になっていることからわかる．十分性は，貪欲に下$2$行と右$2$列に押し込むと不変量を見るだけで残りが自動的に$0$になってくれることからわかる．
\end{proof}
よって問題1は「任意に明滅状態$(a_{i,j})_{0< i< n+1, 0< j< m+1}$が与えられたときに，$n+2$行と$m+2$列全てで$\F_4$不変量が$0$になるような拡張$(a_{i,j})_{0\leq i\leq n+1, 0\leq j\leq m+1}$が存在するか」という問題に帰着できる．
\begin{remark}[$\tau$の具体的な表示]\label{rem:ConcreteDescriptionOfTau}
後の参照のために，$\tau$の具体的な表示を持っておこう．ランプの明滅配置を$\F_2$上$(n+2)(m+2)$次元空間の元だと思った場合には我々の不変量は$\F_2$線型写像
\[
\tau\colon \F_{2}^{(n+2)(m+2)} \to \F_4^{n+2}\times \F_4^{m+2}
\]
である．ここで，
\[
\tau((a_{i,j})_{i,j}) = (x_0, \dots, x_{n+1}, y_0, \dots, y_{m+1})
\]
と書くなら，
\begin{equation}\label{eq:x}
x_i =\sum_{j=0}^{m+1} a_{i,j} \omega^{i+j}
\end{equation}
\begin{equation}\label{eq:y}
y_j =\sum_{i=0}^{n+1} a_{i,j} \omega^{i+j}
\end{equation}
が定義である\footnote{今，$a_{i,j}$は$\F_2$の元だが，$\F_2\subset \F_4$で$\F_4$の元だと思っている．}．
\end{remark}
$1$次元の場合と同様の図式を書こう．再び，考えている圏は$\Vect_{\F_2}$である．
\[\begin{tikzcd}[row sep=30pt]
0 & {\F_2^{2n+2m+4(=\textrm{edge})}} & {\F_2^{(n+2)(m+2)(=\textrm{all})}} & {\F_2^{nm(=\textrm{bulk})}} & 0 \\
0 & {\F_4^{n+2} \times \F_4^{m+2}} & {\F_4^{n+2} \times \F_4^{m+2}} & 0 & 0
\arrow[from=1-1, to=1-2]
\arrow[tail, from=1-2, to=1-3]
\arrow["{\tau_{\mathrm{edge}}}", from=1-2, to=2-2]
\arrow[two heads, from=1-3, to=1-4]
\arrow["\tau", from=1-3, to=2-3]
\arrow[from=1-4, to=1-5]
\arrow[from=1-4, to=2-4]
\arrow[from=2-1, to=2-2]
\arrow["{=}"{description}, no head, from=2-2, to=2-3]
\arrow[from=2-3, to=2-4]
\arrow[from=2-4, to=2-5]
\end{tikzcd}\]
全て$1$次元の場合と同様である．強いて言えば，$\tau$の全射性がわからない\footnote{実際に成り立たない}ので二重矢印ではなくなっているところだけ違う．
この図式に関して，蛇の補題を適用する．
\[\begin{tikzcd}[row sep=30pt]
0 & \Ker \tau_{\mathrm{edge}} & {
% \Ker \tau
\Solvable
} & {\F_2^{nm(=\textrm{bulk})}} \\
0 & {\F_2^{2n+2m+4(=\textrm{edge})}} & {\F_2^{(n+2)(m+2)(=\textrm{all})}} & {\F_2^{nm(=\textrm{bulk})}} & 0 \\
0 & {\F_4^{n+2} \times \F_4^{m+2}} & {\F_4^{n+2} \times \F_4^{m+2}} & 0 & 0\\
& \Coker \tau_{\mathrm{edge}} & ? & 0 & 0
\arrow[from=1-1, to=1-2]
\arrow[tail, from=1-2, to=1-3]
\arrow[tail, from=1-2, to=2-2]
\arrow["{\sigma_{n,m}}", from=1-3, to=1-4]
\arrow[tail, from=1-3, to=2-3]
\arrow["{=}"{description}, no head, from=1-4, to=2-4]
\arrow["\delta"{description, pos=0.6}, dotted, two heads, from=1-4, to=4-2]
\arrow[from=2-1, to=2-2]
\arrow[tail, from=2-2, to=2-3]
\arrow["{\tau_{\mathrm{edge}}}", from=2-2, to=3-2]
\arrow[two heads, from=2-3, to=2-4]
\arrow["\tau", from=2-3, to=3-3]
\arrow[from=2-4, to=2-5]
\arrow[from=2-4, to=3-4]
\arrow[from=3-1, to=3-2]
\arrow["{=}"{description}, no head, from=3-2, to=3-3]
\arrow[two heads, from=3-2, to=4-2]
\arrow[from=3-3, to=3-4]
\arrow[two heads, from=3-3, to=4-3]
\arrow[from=3-4, to=3-5]
\arrow[from=3-4, to=4-4]
\arrow[from=4-2, to=4-3]
\arrow[from=4-3, to=4-4]
\arrow[from=4-4, to=4-5]
\end{tikzcd}\]
右列の計算は自明で，左列の計算は延期する．中列のkernelは$1$次元の場合と同様に不変量が消える場所だからちょうど内部操作で消せるランプ配置の空間である．問題は中列のcokernel，つまり$\Coker \tau$，である．
\begin{lemma}
$\F_2$線形空間として，$\Coker \tau \cong \F_4^2$.
\end{lemma}
\begin{proof}
まず，$\corank \tau = \dim_{\F_2} (\Coker \tau)$が$4$以下であることを$\tau$の定義に戻って示す．(cf. Remark \ref{rem:ConcreteDescriptionOfTau})
${\F_4^{n+2} \times \F_4^{m+2}}$の元$(x_0, \dots, x_{n+1}, y_0, \dots, y_{m+1})$を任意にとる．すると，$x_0,x_1$以外で一致する$(a_{i,j})_{0\leq i\leq n+1, 0\leq j\leq m+1} \in \F_2^{(n+2)(m+2)(=\textrm{all})}$を次のように取ってこれる．まず，$i,j\geq 3$なる$a_{i,j}$は全て$0$にしてしまう．その上で，$0\leq j\leq m+1$について $\omega^{0+j}, \omega^{1+j}$は$\F_4$の$\F_2$基底なので，$a_{0,j}, a_{1,j}$をうまく選ぶことで，$y_j$の値を揃えることができる．同様に，$2\leq i\leq n+1$に関しては$a_{i,0}, a_{i,1}$の値がまだ自由に動かせるので，$x_i$の値を揃えることができる．($x_0,x_1$は$y_0,y_1$を調整するのに使った部分と重複するので選べない．)\memo{write! diagram}
あとは，実際に$4$次元分($=\F_4$上$2$次元分)のcokernelを作ってしまえばいい．$\F_4$線型写像(従って$\F_2$線型写像)
\[
\alpha\colon \F_4^{n+2} \times \F_4^{m+2} \to \F_4
\]
を単に総和
\[
\alpha(x_i,y_j) = \sum_{i} x_i - \sum_{j} y_j
\]
で定義すれば
\begin{align*}
\alpha(\tau(a_{i,j})) = \sum_{i} \sum_j a_{i,j} \omega^{i+j}- \sum_{j}\sum_i a_{i,j}\omega^{i+j} =0
\end{align*}
となる．さらに，フロベニウス準同型${-}^2\colon \F_4 \to \F_4$を利用すれば，
\[
y_j^2 =\sum_{i=0}^{n+1} a_{i,j} \omega^{2i+2j}
\]
だから，
$\F_2$線型写像(今度は$\F_4$線型写像ではない！)
\[
\beta\colon \F_4^{n+2} \times \F_4^{m+2} \to \F_4
\]
を\dq{ねじった総和}
\[
\beta(x_i,y_j) = \sum_{i} x_i \omega^i - \sum_{j} y_j^2 \omega^{2j}
\]
で定義すれば
\begin{align*}
\beta(\tau(a_{i,j})) = \sum_{i} \sum_j a_{i,j} \omega^{i+j} \omega^i - \sum_{j}\sum_i a_{i,j}\omega^{2i+2j}\omega^{2j} =0
\end{align*}
となる．
すると，これらを合わせてできる$\F_2$線型写像
\[
\langle \alpha, \beta\rangle \colon \F_4^{n+2} \times \F_4^{m+2} \to \F_4^2
\]
は$\Coker \tau$を経由する.これが全射であることは$x_2, \dots, x_{n+1},y_0, \dots y_{m+1}=0$に限って$x_0,x_1$を動かすだけでわかる\footnote{$x_0,x_1$の振る舞い$\F_4^2\to \F_4^2$を見れば，($x_0,x_1$に関しては$\F_4$線形になっていて)$2\times 2$の$\F_4$行列
$\begin{pmatrix}
1&1\\
1& \omega
\end{pmatrix}$
の正則性に帰着される．
}．
\end{proof}
これで，我々は次の図式を得た．
\[\begin{tikzcd}[row sep=30pt]
0 & \Ker \tau_{\mathrm{edge}} & {
% \Ker \tau
\Solvable
} & {\F_2^{nm(=\textrm{bulk})}} \\
0 & {\F_2^{2n+2m+4(=\textrm{edge})}} & {\F_2^{(n+2)(m+2)(=\textrm{all})}} & {\F_2^{nm(=\textrm{bulk})}} & 0 \\
0 & {\F_4^{n+2} \times \F_4^{m+2}} & {\F_4^{n+2} \times \F_4^{m+2}} & 0 & 0\\
& \Coker \tau_{\mathrm{edge}} & \F_4^2 & 0 & 0
\arrow[from=1-1, to=1-2]
\arrow[tail, from=1-2, to=1-3]
\arrow[tail, from=1-2, to=2-2]
\arrow["{\sigma_{n,m}}", from=1-3, to=1-4]
\arrow[tail, from=1-3, to=2-3]
\arrow["{=}"{description}, no head, from=1-4, to=2-4]
\arrow["\delta"{description, pos=0.6}, dotted, two heads, from=1-4, to=4-2]
\arrow[from=2-1, to=2-2]
\arrow[tail, from=2-2, to=2-3]
\arrow["{\tau_{\mathrm{edge}}}", from=2-2, to=3-2]
\arrow[two heads, from=2-3, to=2-4]
\arrow["\tau", from=2-3, to=3-3]
\arrow[from=2-4, to=2-5]
\arrow[from=2-4, to=3-4]
\arrow[from=3-1, to=3-2]
\arrow["{=}"{description}, no head, from=3-2, to=3-3]
\arrow[two heads, from=3-2, to=4-2]
\arrow[from=3-3, to=3-4]
\arrow["{\langle \alpha,\beta\rangle}", two heads, from=3-3, to=4-3]
\arrow[from=3-4, to=3-5]
\arrow[from=3-4, to=4-4]
\arrow[from=4-2, to=4-3]
\arrow[from=4-3, to=4-4]
\arrow[from=4-4, to=4-5]
\end{tikzcd}\]
ここまで来れば，何をどうやっても求めたい量$\corank \sigma_{n,m}$の計算は左列の計算
\[
\begin{tikzcd}
0\ar[r]&\Ker \tau_{\textrm{edge}}\ar[r, rightarrowtail]&\F_2^{2n+2m+4(=\textrm{edge})}\ar[r, "\tau_{\mathrm{edge}}"]&{\F_4^{n+2} \times \F_4^{m+2}} \ar[r, twoheadrightarrow]& \Coker \tau_{\mathrm{edge}} \ar[r, twoheadrightarrow]& 0
\end{tikzcd}
\]
に帰着できる．一つの方法は，中列を見て$\dim_{\F_2}\Solvable =n\times m$を導き，$\Ker \tau_{\textrm{edge}}$の次元計算に帰着するもの．別の方法は
蛇の補題のよる完全列
\[
\begin{tikzcd}
% 0\ar[r]&\Ker \tau_{\textrm{edge}}\ar[r, rightarrowtail]&
\Solvable \ar[r, "\sigma_{m,n}"]
& {\F_2^{nm(=\textrm{bulk})}}\ar[r, "\delta"] & \Coker \tau_{\mathrm{edge}} \ar[r, twoheadrightarrow]& \F_4^2 \ar[r]& 0
\end{tikzcd}
\]
を見て$\Coker \tau_{\textrm{edge}}$の次元計算に帰着するもの．どちらも似たようなものだが，今回は$\Ker \tau_{\textrm{edge}}$を見ることにする．$1$次元のときとほぼ同じで，向かい合う辺についた$\omega^i+j$の重みが同じかどうかだけで議論が終わって，
\[
\dim_{\F_2}(\Ker \tau_{\textrm{edge}}) =
\begin{cases}
0 &(n,m \not \equiv 2 \mod 3)\\
n &(n \not \equiv 2 \mod 3,\text{ and } m \equiv 2 \mod 3)\\
m &(n \equiv 2 \mod 3,\text{ and } m \not \equiv 2 \mod 3)\\
{n+m-1} &(n,m \equiv 2 \mod 3)
\end{cases}
\]
を得る．$\dim_{\F_2} \Solvable= \dim_{\F_2} \F_2^{nm}$より$\dim_{\F_2}(\Ker \tau_{\textrm{edge}}) = \dim_{\F_2}(\Coker \sigma_{m,n})$もわかり，結果としてProposition \Cref{prop:CountingTwoDim} と同じ結果を得る．
% を得た！よって求めたい量$\corank \sigma_{n,m}$は
% \[
% \corank \sigma_{n,m} = \corank \tau_{\mathrm{edge}} -4
% \]
% となる．
\subsection{消灯可能性を境界準同型で理解する}
$1$次元のときと全く同様に，明滅の配置$a=(a_{i,j})_{i,j} \in \F_2^{nm}$について，
\[
\text{$a$は消灯可能} \iff a\in \Image(\sigma_{n,m}) \iff \delta(a)=0
\]
がわかる．さらにこれは，明滅の配置について，最短の消灯方法も教えてくれる．
\begin{description}
\item[$(n,m \not \equiv 2 \mod 3)$の場合] このとき， 必ず解ける上に，最短の解き方もわかる．どんな初期配置でも，solvableな$(n+2)(m+2)$配置に\demph{一意的に}拡張できる．(次元を見ればわかるし，向かい合う空欄が$\F_4$の$\F_2$基底になっていることからもわかる) そして，拡張した上で，内部操作を用いてランプを左上から貪欲に消していき，右$2$列と左$2$列に押し込むと，その時点で不変量が残りの全ての消灯を保証してくれる．この消灯アルゴリズムは同じランプを操作しないし，さらに解法は一意(次元からわかる)なので，最短の消灯方法である！
\item[$(n \not \equiv 2 \mod 3,\text{ and } m \equiv 2 \mod 3)$の場合]このとき， 消灯できることと，「$n$行全てについて，(内部の)$\F_4$不変量が(拡張された)両端の$\F_4$値(これは一致してしまっている)の$\F_2$倍になっていること」が必要十分である．消灯できるなら，まず$n$行全てについて，$\F_4$不変量を$0$にする．そのような方法は$2^n$通りあるが，そのどれを選んでも良い．(例えば，左端のランプを全て消灯させるとすると，残りは一意に決まって便利\footnote{これが最短ではないとしても実用上十分はやそう})そのあと，$m+2$列全てについて$\F_4$不変量を$0$にする．この方法はちょうど$1$つ．あとは同じで，ランプを右下に押し込めば良い．この消灯アルゴリズムは，同じランプを叩かないという意味で無駄はないものの，$2^n$通りの中で最短であるかはわからない．
\item[$(n \equiv 2 \mod 3,\text{ and } m \not \equiv 2 \mod 3)$の場合] 上と同じ．
\item[$(n,m \equiv 2 \mod 3)$の場合]次の操作で消灯可能性も，消灯できる場合の消灯方法もわかる．まず，$(n+2)(m+2)$に拡張されたもののうち，$1$行目と$1$列目を全て消灯させることにする．
% の左から$n-1$個と$1$列目の上から$m-1$個($1$個ダブってるので合計で$n+m-1$個)を全て消灯させることにする．($n+m-1$は例のKernelの次元に合わせている)
この状態から，全ての行と列で$\F_4$不変量が$0$になるように残りの$n+m+1$個の端のランプを調整する．(これができるのは，全ての行と列で$\F_4$不変量が端の$\F_4$値の倍数になっている\demph{だけでなく}それらの値が一致していてかつ右下の頂点の$\F_4$値と一致していなくてはならない！) やってみるとわかるが，この操作は可能なら常に「迷いなく」できる．(実際，可能ならば一意的である)
この操作が不可能ならそもそも消灯不可能であり，この操作が完遂されれば右下に押し込むことで解けてしまう．
\end{description}
\memo{これ実際に試せるコード書きたいね...}
\section{おまけsurvey}
1989年，\cite{sutner1989linear}で任意の有限グラフで全消灯$\to$全点灯が可能であることを示した．このゲームは論文中で\dq{The All-Ones Problem}と呼ばれている．その手法は興味深く，この問題をセルオートマトンの「エデンの園問題」に帰着している．(自己写像$f\colon X \to X$のエデンの園とは，単に$X\setminus \Image(f)$の元のことを指す．$f$で到達できないのでエデンの園と呼ばれているらしい．) あとは線形代数をする．
1998年，\cite{anderson1998turning}で2次元のlights outが線形代数で解かれた．(しかしここでは上下左右のランプの反転を考えていて，斜めは考慮していない．) この論文は$n,m=5$でしか解いていない\footnote{正確には，他の小さい$n$については数値だけ書いて規則は述べていない}が$100$回以上引用されている．
% その後Lights outが活発に研究されているようである．
Lights out研究の歴史は2013年のsurvey論文\cite{fleischer2013survey}が詳しい．特に，グラフ理論，アルゴリズム理論，セルオートマトン理論との関連から興味が持たれ研究されてきたようである．この論文の被引用を見ると，現代でも研究があることがわかる．(先月もpreprint\cite{forrest2025lights}が出ている．)
(我々の話がその界隈に面白がられるかはわからないが，我々のルールにおける$\F_4$不変量やホモロジー代数との関わりは既に調べられていていいと思う．Surveyしてないけど．むしろこの話はグラフラプラシアンの文脈で知られていて良さそう．「グラフ上の微分幾何学」界隈は当然同様の行列をホモロジー的文脈で使っているので．例えば\cite{jekel2018algebraic}ではホモロジー代数を用いて同様の構造を調べてSIAM Journal of Discrete Mathematicsに載っている．)
\printbibliography
\end{document}