← mathematical-space-topos-note
tex__body__notes-current.tex
% Imported from legacy/ノート2024.tex. Explicit internal memos were moved to tex/private/internal-memos.tex.
\part{2024}
\section{2024/09/28}
\subsection{対称群の部分アーベル群}
\begin{question}
自然数$n$について，対称群$S_n$の可換部分群の位数で最大のもの$a_n$を求めよ
\end{question}
\begin{table}[ht]
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} \hline
$n$& $1$& $2$& $3$& $4$& $5$ &$6$& $7$& $8$& $9$&$10$\\ \hline
$a_n$& $1$& $2$& $3$& $4$& $6$ &$9$& $12$& $18$& $27$&$36$\\ \hline
\end{tabular}
\end{table}
$n\leq 7$までは，対称群の元の共役類とシローの定理により具体的に求めた．
\begin{lemma}
\label{lem:20240928AbelianUpperBound}
$n=\sum_{i=1}^r k_i$と正整数の和に分割すると，$a_n \geq \prod_{i=1}^r k_i$. 特に，
\[
a_n \geq
\begin{cases}
3^k & (n=3k)\\
4\cdot 3^{k-1} & (n=3k+1)\\
2\cdot 3^k & (n=3k+2).
\end{cases}
\]
\end{lemma}
\begin{proof}
$\prod_{i=1}^r \Z/ k_i \Z \subset S_n$
\end{proof}
$n\leq 7$まではこの不等式は等式になっている．
\begin{description}
\item[$n=1,2$] $S_n$自身が可換なので$a_n=n!$.
\item[$n=3$] $\langle (1,2,3)\rangle$が最大可換部分群
\item[$n=4$] $\langle (1,2,3,4)\rangle$やクラインの四元群$\langle (1,2)(3,4), (1,3)(2,4)\rangle$が$4$元可換部分群を与える．．$24$の約数$1,2,3,4,6,8,12,24$を考え，$6,8,12,24$が実現しないことを示せば良い．もし$a_4$が$6$の倍数なら，$S_n$は位数$6$の元を含まねばならず，矛盾する．よって，$8$が実現しないことを示せば良い．位数$8$の部分群はシロー$2$-部分群であるから，全て共役で，従ってそのうち一つでも非可換なものが存在することを示せば良い．実際，$D_4 \subset S_4$が非可換なので証明終わり．
% $24,12$はそれぞれ一つ($S_4$と$A_4$)しかないため，非可換性がわかる．よって，あとは$6,8$を除去すれば良い．
\item[$n=5$] $a_5\geq 6$はわかっている．$a_5$が6の倍数なら，対応する可換部分群$A$のある共役は$\sigma = (1,2,3)(4,5)$の共役類を含むが，$\sigma$と可換な元は$\sigma^i (i\in \Z)$しかないため，$A= \langle \sigma \rangle $となって$|A|=6$となってしまう．また，$a_5$が$5$の倍数なら，同様に$(1,2,3,4,5)$の共役で生成され矛盾する．よって，$5! = 120$の約数$1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120$のうち，残り$8$が実現しないことを見れば良い．位数$8$の部分群はシロー$2$部分群であり全て共役で，$D_4 \subset S_4 \subset S_5$は非可換なので証明終了．
\item[$n=6$] $a_6\geq 9$はわかっている．似た方法で，$a_6$が$5,6$で割り切れないことがわかり，$6!$の約数のうち$16$が実現しないことのみを示せばいい．これはシロー$2$部分群で，$D_4 \times \Z/2\Z \subset S_6$が非可換なことからok.
\item[$n=7$] $a_7\geq 12$なことはわかっている．これまでと類似の議論で，
\begin{itemize}
\item $a_n$を$5$が割り切るなら$a_n\leq 10$，
\item $a_n$を$6$が割り切るなら$a_n\leq 12$,
\item $a_n$を$7$が割り切るなら$a_n\leq 7$,
\end{itemize}がわかる．
よって，$7!$の約数$14、15、16、18、20、21、24、28、30、35、36、40、42、45、48、56、60、63、70、72、80、84、90、105、112、120、126、140、144、168、180、210、240、252、280、315、336、360、420、504、560、630、720、840、1008、1260、1680、2520、5040$のうち，$16$が実現しないことだけ見ればいい．これはシロー$2$部分群で，$D_4 \times \Z/2\Z \subset S_6 \subset S_7$よりok.
\item[$n=8$] 後の Dixon の定理から$a_8=18$である．Dixon の定理を使わない直接計算として，前と類似の(しかしより複雑な)議論により，
\begin{itemize}
\item $a_n$を$5$が割り切るなら$a_n\leq 15$，
\item $a_n$を$6$が割り切るなら$a_n\leq 18$\footnote{補足: $a_n$を$6$が割り切るなら，$\sigma = (123456)(78)$か$\sigma = (123456)(7)(8)$か$\sigma = (123)(456)(78)$か$\sigma = (123)(45)(67)(8)$か$\sigma = (123)(45)(6)(7)(8)$のいずれかの共役が対応する可換部分群に含まれる．それぞれ，その中心化群は$\Z/6\Z, \Z/6\Z \times \Z/2\Z, \text{位数36の非可換群}，\text{位数24の非可換群}，\text{位数36の非可換群}$であるので，可換部分群$A$の位数は$18$以下になる．}，
\item $a_n$を$7$が割り切るなら$a_n\leq 7$,
\end{itemize}がわかる．よって，$8!=2^7 \cdot 3^2 \cdot 5\cdot 7$の約数のうち，$2$べき，つまり$32,64,128$が実現しないことを観察すれば良い．位数$2$べきの部分群は，全てシロー$2$部分群に含まれる．そして，$S_8$のシロー$2$部分群は次の\dq{モビール}の自己同型群として与えられる：
\begin{center}
\begin{tikzpicture}[
level 1/.style={sibling distance=4cm},
level 2/.style={sibling distance=2cm},
level 3/.style={sibling distance=1cm},
every node/.style={circle, draw, minimum size=0.5cm, inner sep=0pt}
]
\node {}
child {
node {}
child {
node {}
child {node {}}
child {node {}}
}
child {
node {}
child {node {}}
child {node {}}
}
}
child {
node {}
child {
node {}
child {node {}}
child {node {}}
}
child {
node {}
child {node {}}
child {node {}}
}
};
\end{tikzpicture}
\end{center}
よって$a_8$を求める問題は，このモビールの自己同型群の可換部分群を求める問題に帰着された．
\end{description}
\begin{proposition}[\cite{dixon1971maximal}]
\Cref{lem:20240928AbelianUpperBound}の不等号は等号である．
\end{proposition}
\begin{proof}
$A\subset S_n$が可換部分群なら，$A$は$\{1,2, \dots n\}$にfaithfulに作用する．そのorbit を$X_i$ とすれば，$A$は可換なので各orbit
ごとに(その元の)stabilizer $H_i \subset A$ がwell-definedに定まる．
$A$作用の忠実性から
\[
A \to \prod_{i} A/{H_i}
\]
は単射である($i$はorbitをめぐっている．ここで，Stabilizerがorbitだけで決まることを使っている！そのおかげで，本来は全ての元についてstabilizerを見ないといけないのに，orbitごとに見るだけで良くなっている．)さらに
\[
\abs{\prod_{i} A/{H_i}} = \prod_{i} \abs{A/H_i} = \prod_{i} \abs{X_i}
\]
である．$\sum_{i} \abs{X_i} = n$と合わせて，上からの評価が完成した．
\end{proof}
\begin{answer}$n\geq 2$なら
\[
a_n =
\begin{cases}
3^k & (n=3k)\\
4\cdot 3^{k-1} & (n=3k+1)\\
2\cdot 3^k & (n=3k+2).
\end{cases}
\]
\end{answer}
\subsection{Non-trivial rigid abelian group: \texorpdfstring{$\End(A)\cong \Z$}{EndACongZ}}
\begin{question}
アーベル群$A$であって，その自己準同型環$\End(A)$が$\Z$と同型になるものは，$\Z$以外に存在するか？
\end{question}
\begin{context}
鈴木さん(と榎本くん)が考えていた問題．
\end{context}
\begin{answer}[小泉さん]
存在する．$A\coloneqq \{q\in \Q\mid \text{$q$を既約分数表示した時の分母が平方因子を持たない．}\}$とすると，$A$の自己準同型$f$で$\Z = \{q\in A \mid \forall p \text{ : prime, }\exists x\in A,\; px=q\}$は$\Z$に移ることからわかる．
\end{answer}
\section{2024/10/05}
\subsection{Square-free sequence and free idempotent monoid \texorpdfstring{$M_n$}{Mn}}
% $\Sigma$ を有限集合とする．
\begin{question}
$n\geq 3$とする．$[n]\coloneqq \{0, \dots , n-1\}$の無限列$p$であって，square-freeなもの，(i.e., 任意の正の長さの文字列$w\in [n]^*$について$ww$が$p$の連続部分文字列とならないもの)は存在するか？
\end{question}
\begin{context}
Anti-FibonacciからのThue–Morse sequenceからの派生．
\end{context}
次はこの問題の代数的な類似である．
\begin{question}
$n$元生成Free idempotent monoidは，有限か？
\end{question}
(この問題は，\cite{green1952semi}で肯定的に解かれた．\cite[][Section 2]{rogers2024free}はそのsurveyになっている．例えば，$3$元生成free idempotnet monoidは$160$元モノイドらしい．)
これらの問題はある意味では類似なのだが，次の例が示すように$ww\mapsto w$という操作に関する\dq{合流性}はない．つまり，一つの文字列から，(操作の適用箇所/順番に依存して)相異なる$2$つのsquare-free文字列が得られることがある．二つの問いの等価性はよくわからない．
\begin{example}[合流性の破れ{\cite[][Example 2.4, due to Dylan McDermot]{rogers2024free}}]
\[
\begin{tikzcd}[row sep = 1pt]
& ababc \ar[r,"ab"]& abc\\
ababcbabc\ar[ru, "babc"]\ar[rd,"ab"]&&\\
&abcbabc&
\end{tikzcd}
\]
\end{example}
\section{2024/10/19}
\subsection{アダマール行列の存在}
\begin{definition}
\demph{$n$次アダマール行列}とは，$A\in M_n (\Z)$であって，
\begin{itemize}
\item 全ての成分が$1$か$-1$
\item 相異なる行が直交している．
\end{itemize}
を満たすものをいう．
\end{definition}
\begin{example}$n=1,2,4,8$の場合は以下のような例がある．
\begin{description}
\item[$n=1$]
\[
\begin{bmatrix}
1
\end{bmatrix}
\]
\item[$n=2$]
\[
\begin{bmatrix}
1 & 1 \\
1 & -1
\end{bmatrix}
\]
\item[$n=4$]
\[
\begin{bmatrix}
1 & 1 & 1 & 1 \\
1 &-1 & 1 &-1 \\
1 & 1 &-1 &-1 \\
1 &-1 &-1 & 1
\end{bmatrix}
\]
\item[$n=8$]
\[
\begin{bmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 \\
1 & 1 & -1 & -1 & 1 & 1 & -1 & -1 \\
1 & -1 & -1 & 1 & 1 & -1 & -1 & 1 \\
1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 \\
1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 \\
1 & 1 & -1 & -1 & -1 & -1 & 1 & 1 \\
1 & -1 & -1 & 1 & -1 & 1 & 1 & -1
\end{bmatrix}
\]
\end{description}
\end{example}
\begin{fact}
$n$次アダマール行列が存在するなら，$n$は$n=1,2$であるか$4$の倍数であるかのいずれかである．
\end{fact}
\begin{conjecture}[アダマール予想]
$n$は$n=1,2$であるか$4$の倍数であるかのいずれかであるとき，$n$次アダマール行列が存在する
\end{conjecture}
\begin{fact}次の生成法が知られている．
\begin{description}
\item[Sylvester's construction] アダマール行列はテンソルで閉じている．よって，$n$次アダマール行列と$m$次アダマール行列から$nm$次アダマール行列を構成できる．特に，$2^n$次アダマール行列が存在する．
\item[Paley construction] 奇素数冪$q$について，$q \cong 3 \mod 4$なら$q+1 $次の，$q\cong 1 \mod 4$なら$ 2(q+1)$次のアダマール行列が構成できる．
\end{description}
\end{fact}
これらの構成で，$100$以下の$4$の倍数は$92$以外構成できる．
\begin{itemize}
\item $1=2^0$
\item $2=2^1$
\item $4=2^2$
\item $8=2^3 = 7+1$
\item $12 = 11+1$
\item $16 = 2^4$
\item $20 = 19+1$
\item $24 = 23+1$
\item $28 = 3^3+1$
\item $32 = 2^5$
\item $36 = 2(17+1)$
\item $40 = 2\times (19+1)$ (テンソル)
\item $44= 43+1$
\item $48 = 47+1$
\item $52 = 2(5^2+1)$
\item $56 = 2 \times (3^3+1)$
\item $60 = 59+1$
\item $64 = 2^6$
\item $68 = 67+1$
\item $72 = 71+1$
\item $76 = 2(37+1)$
\item $80 = 2^2\times (19+1)$
\item $84 = 83+1$
\item $88 = 87+1$
\item $92$ Non-trivial!
\item $96 = 2(47+1)$
\item $100 = 49+1$
\end{itemize}
\section{2024/10/26}
\begin{question}
$\lfloor n \varphi \rfloor$の階差数列を$d_n$とする．
\[
d_n \coloneqq \lfloor (n+1) \varphi \rfloor - \lfloor n \varphi \rfloor
\]
これは
\begin{align*}
1&\mapsto 2\\
2& \mapsto 21
\end{align*}
という操作に関する自己相似性を持つか？
\end{question}
追記(11/02): \href{https://onlinemathcontest.com/contests/omc190/tasks/6631}{OMC190(F)}が関連するらしい?
\begin{align*}
&2\\
&21\\
&212\\
&21221\\
&21221212\\
\end{align*}
\section{2024/11/02}
\begin{question}
位数$3$のモノイドの同型類を分類せよ．
\end{question}
文脈は，Baezらの``causality graph".
\cite{lawvere1989display}も文脈だし，今書いてる論文も文脈．全部で$7$個ある．位数$4$は？... 私はよく知らないけど世間はよく知ってるはず．クソほどありそう．
\section{2024/11/09}
囚人のパズルをやって，離散時間が大事だという話になった．これはトポスの内部言語で書けると思うけど，どうだろう？
中村くんが，正$4,8$面体を合同な多角形$4$つに非自明に分解していた．すごい．
正六面体を$3$つ配置した図形の凸包の体積を求める，近大数コンの過去問が出て，みんなで苦しんでいた．難しい．
\section{2024/11/16}
\subsection{}
Ryo Suzukiが，「ニム和ってアッカーマン対応で何になるの？」と質問した．対称差じゃん！になった．
\subsection{自己相似数列について}
$a_n=\lfloor n\sqrt{d}\rfloor$という数列の階差数列$b_n=a_{n+1}-a_n$が自己相似性を持つ理由が大体わかった．例えば$d=2$の場合を考えよう．$f(n)=n+a_n$と定める．このとき，$b_n$が$b_{f(n)},\dots,b_{f(n+1)-1}$を決定していることが次のように示せる．
$a_n=k$とすると
$$
k<n\sqrt{2}<k+1
$$
となる．これに$n$を加えて
$$
n+k<n(\sqrt{2}+1)<n+k+1
$$
とし，さらに$(\sqrt{2}-1)$を掛けて
$$
(n+k)(\sqrt{2}-1)<n<(n+k+1)(\sqrt{2}-1)
$$
を得る．これを移項すると
$$
(n+k)\sqrt{2}<2n+k,\quad 2n+k+1<(n+k+1)\sqrt{2}
$$
となるので$a_{n+k}=2n+k-1$および$a_{n+k+1}=2n+k+1$が得られる．
ここで$b_n=1$と仮定すると，$(n,k)$を$(n+1,k+1)$に置き換えたものも成り立つので
$$
a_{n+k}=2n+k-1,\ a_{n+k+1} = 2n+k+1,\ a_{n+k+2} = 2n+k+2
$$
が得られ，
$$
b_{n+k} = 2,\ b_{n+k+1} = 1
$$
がわかる．同様に$b_n=2$の場合は
$$
a_{n+k}=2n+k-1,\ a_{n+k+1} = 2n+k+1,\ a_{n+k+2} = 2n+k+2,\ a_{n+k+3} = 2n+k+3
$$
となるので
$$
b_{n+k} = 2,\ b_{n+k+1} = 1,\ b_{n+k+2} = 1
$$
がわかる．これらを合わせると，$b_n$は
$$
\begin{cases}
1\mapsto 21\\
2\mapsto 211
\end{cases}
$$
という変換の不動点となっていることがわかる．
\section{2024/12/07}
\href{https://arxiv.org/abs/2407.13951}{arXiv:2407.13951 The category of topological spaces and open maps does not have products}の話になった．なんだそれ．
\begin{question}
Locally finite category $C$ であって，$\mathbf{FinSet}$ へのfaithful functor $C \to \mathbf{FinSet}$ を持たないものを構成せよ
\end{question}
という話題になり，回答は出なかった．
\section{2024/12/15}
\begin{itemize}
\item 三角形を組み合わせて大きい三角形を作る問題が出た．特に，$(3,5,7)$の三角形を用いて正三角形を作る問題が盛り上がった．
\item \href{https://en.wikipedia.org/wiki/Rogers–Ramanujan_identities}{[Rogers–Ramanujan identity]}の問題が出た．
\end{itemize}
\section{2024/12/23}
三次方程式$x^3+2x-1=0$とか$x^3=x^2+1$を解いたりした．ガロア理論との関係は部分的にだけわかった．
\part{2025}
\section{2025/01/11}
\subsection{\texorpdfstring{$S_5$}{S5}の作用するグラフ}
神尾くんの出題で下のグラフ (\Cref{fig:Stargraph}) の自己同型群を求めた．$\{1,2,3,4,5\}$の$2$元部分集合とdisjointnessのグラフだと思うと$S_5$が作用する．
\begin{figure}[ht]
\centering
\begin{tikzpicture}
% 頂点の座標を設定
\foreach \i in {0,1,...,4} {
\coordinate (outer\i) at ({90 + 72 * \i}:3cm); % 外側の正五角形
\coordinate (inner\i) at ({90 + 72 * \i}:1.5cm); % 内側の星型
}
% 外側の正五角形を描画
\foreach \i in {0,1,...,4} {
\pgfmathsetmacro\next{int(mod(\i+1,5))}
\draw (outer\i) -- (outer\next);
}
% 内側の星型を描画
\foreach \i in {0,1,...,4} {
\pgfmathsetmacro\next{int(mod(\i+2,5))}
\draw (inner\i) -- (inner\next);
}
% 中外の頂点を結ぶ
\foreach \i in {0,1,...,4} {
\draw (outer\i) -- (inner\i);
}
% 頂点を描画
\foreach \i in {0,1,...,4} {
\fill[black] (outer\i) circle (2pt); % 外側の頂点
\fill[black] (inner\i) circle (2pt); % 内側の頂点
}
\end{tikzpicture}
\caption{Petersen graph}
\label{fig:Stargraph}
\end{figure}
これを用いて$S_6$の外部自己同型を作る問題に移行した．
\subsection{ニューイヤー問題}
$n^4+3^n = \left(\frac{m(m+1)}{2}\right)^2$の正整数解を全て求める問題を出した．答えは$(6,9)$しかなくて，この場合両辺は2025になる．このことは，次のようにしてわかる．
\[
3^n = \left(\frac{m(m+1)}{2} - n^2\right)\left(\frac{m(m+1)}{2} + n^2\right)
\]
としてから
\[
3^a = \left(\frac{m(m+1)}{2} - n^2\right),
\]
\[
3^b = \left(\frac{m(m+1)}{2} + n^2\right),
\]
とおくことで，$a+b= n$ と$3^b-3^a=2n^2$という等式が出てくる．
$a+a+(b-a)=n$より$a,b-a \geq \frac{n}{3}$なので，$0\leq a<b$より
\[
2n^2 = 3^a (3^{b-a}-1) \geq 3^{\frac{n}{3}}-1
\]
ここから$n\leq 17$を得る．
% これは$n\geq 18$だと解を持ち得ない．
($n=18$で 左辺が$8*9*9$になり，右辺が$9*9*9-1$になる．)
あとは頑張ると，$n=6$のみになる．
\section{2025/01/18}
\subsection{フィボナッチ多項式}
$n\times n$行列
\[
A_n = \begin{pmatrix}
1 & i & 0 & 0 & \cdots & 0 \\
i & 1 & i & 0 & \cdots & 0 \\
0 & i & 1 & i & \cdots & 0 \\
0 & 0 & i & 1 & \cdots & 0 \\
\vdots & \vdots & \vdots & \vdots & \ddots & i \\
0 & 0 & 0 & 0 & i & 1
\end{pmatrix}
\]
を考えた．
$|A_1|=1, |A_2|=2$で，それ以降はフィボナッチ数列になる(小野くんが余因子展開で計算した)．
$A_n$の固有多項式を$f_n(\lambda)$とする．
\[
f_n(\lambda) = \det(\lambda I - A) = \det\begin{pmatrix}
\lambda-1 & -i & 0 & 0 & \cdots & 0 \\
-i & \lambda-1 & -i & 0 & \cdots & 0 \\
0 & -i & \lambda-1 & -i & \cdots & 0 \\
0 & 0 & -i & \lambda-1 & \cdots & 0 \\
\vdots & \vdots & \vdots & \vdots & \ddots & -i \\
0 & 0 & 0 & 0 & -i & \lambda-1
\end{pmatrix}.
\]
固有多項式を $\mu = \lambda -1$で スライドした$g_n(\mu)\coloneqq f_n(\mu +1)$は漸化式$g_{n+2} = \mu g_{n+1} + g_n$を満たす．
\begin{align*}
g_0(\mu) &= 1\\
g_1(\mu) &= \mu\\
g_2(\mu) &= \mu^2 +1\\
g_3(\mu) &= \mu^3 + 2\mu\\
g_4(\mu) &= \mu^4 + 3\mu^2 + 1
\end{align*}
これは，$g_n(1)=F_n$であるという意味で，\dq{パラメータ付きフィボナッチ}もしくは\dq{フィボナッチ多項式}と呼びうるものである．
フィボナッチの一般項と同様にしてフィボナッチ多項式の一般項を求めると，
\[
\begin{pmatrix}
\mu & 1\\
1 & 0
\end{pmatrix}
\]
の二つの固有値
\begin{align*}
\alpha &= \frac{\mu+ \sqrt{\mu^2+4}}{2}\\
\beta &= \frac{\mu- \sqrt{\mu^2+4}}{2}
\end{align*}
を用いて，
\[
g_n(\mu) = \frac{\alpha^{n+1}-\beta^{n+1}}{\alpha-\beta}
\]
を得る．
% $g_n(\mu) = \frac{\alpha^{n+1}-\beta^{n+1}}{\alpha-\beta}$
% の形になり，
これを用いて
$g_n (\mu) = \prod_{1\leq k\leq n} (\alpha - \zeta_{n+1}^k \beta)$と因数分解される．このことから，
$g_n (\mu)^2 = \prod_{1\leq k\leq n} \left(\mu^2+ 4\cos\left(\frac{\pi k}{n+1}\right)\right)$
が分かり，$g_n(\mu)$の根は $1\leq k \leq n$による
\[
2i \cos\left(\frac{\pi k}{n+1}\right)
\]
であることがわかる．よって，行列$A_n$の固有値は$1\leq k \leq n$による
\[
1+2i \cos\left(\frac{\pi k}{n+1}\right)
\]
となり，フィボナッチ数の円分体$\Q(\zeta_{n+1}, i)$での分解
\[
F_n =\det A_n = \prod_{1\leq k\leq n} \left(1+2i\cos{\left(\frac{\pi k}{n+1}\right)}\right)
\]
が得られる！
最初の$5$つを例示するとこんなかんじ．
\begin{align*}
F_1 = 1 &= 1\\
F_2 = 2 &= (1+i)\times (1-i)\\
F_3 = 3 &= (1+\sqrt{-2})\times 1 \times (1-\sqrt{-2})\\
F_4 = 3 &= (1+\sqrt{-2})\times 1 \times (1-\sqrt{-2})\\
F_5 = 5 &= (1+\varphi i)\times (1-\psi i) \times 1 \times (1+\psi i)(1-\varphi i)\\
\end{align*}
\section{2025/01/25}
\subsection{言語の個数}
\internalmemoref{memo-20250125-01}
$\Sigma$をalphabetとする．つまり，空でない有限集合とする． ($\Sigma= \{0,1\}$や$\Sigma=\{a,b, \dots, z\}$を想像すると良い．)
\demph{言語}とは，$\Sigma$の有限文字列の集合$\Sigma^{*}$の部分集合のことである．つまり，($\Sigma$に依存した)言語の集合$L$は，$\Pow(\Sigma^*)$のことである．
\begin{question}
$n= |\Sigma|$としたとき，言語の個数はいくつだろうか？
\end{question}
当然，まともな答えは$|L|= 2^{\aleph_0}$である．一方，ここでは
\[
\text{$n$文字の言語の個数} = \frac{1}{\sqrt[n-1]{2}}
\]
というスローガンを二つの方法で提示する．
\subsubsection{方法1: coalgebraic method}
\begin{lemma}
自然な全単射
$L \cong L^{\Sigma} \times \{\top, \bot\}$
が存在する．
\end{lemma}
\begin{proof}
$\Sigma^* $は，空文字列からなるsingleton $\{\varepsilon\}$と，$a\in \Sigma$ごとの$a\Sigma^*$へ直和分解される．
\[
\Sigma^* = \{\varepsilon\} \sqcup\coprod_{a\in \Sigma} a\Sigma^*.
\]
これを$\{\top, \bot\}$の指数部分に載せて指数法則を使えば，上記の全単射が得られる．
\end{proof}
\begin{remark}[coalgebraic back grouond]
オートマトンは自己関手$2x^{\Sigma}\colon \mathbf{Set} \to \mathbf{Set}$のcoalgebraである．Adamek's constructionより，言語$L$はterminal coalgebraになり，Lambekの補題より構造射
$L \to L^{\Sigma} \times \{\top, \bot\}$が同型になるのである．
\end{remark}
ここで，自然な全単射 $L \cong L^{\Sigma} \times \{\top, \bot\}$ から，濃度の等式
\[
|L| \cong |L|^{|\Sigma|} \times |\{\top, \bot\}|
\]
つまり
\[
|L| \cong 2 |L|^n
\]
を得る．
もちろん，この方程式の\dq{健全}な解は$2^{\aleph_0}$なのだが，これを正実数の範囲で解けば，
\[
|L| \overset{?}{=} \frac{1}{\sqrt[n-1]{2}}
\]
を得る．
\subsubsection{方法2: Species method}
有限集合$C$について，有限集合から$C$への単射のspeciesは
$(1+x)^{|C|}$をその母関数に持つ．
特に，$C$として高々$k$文字の$\Sigma$文字列の集合を考えれば，母関数は
\[
(1+x)^{1+n+ n^2 \dots +n^k}
\]
となる．
ここで，$n$が自然数であったことを忘れ，$-1<n<1$なる実数だと思いかえてみる．(もちろんこの操作は正当化がなされていない．)
すると，$k \to \infty$で\dq{任意有限文字列の母関数}
\[
(1+x)^{\frac{1}{1-n}}
\]
が得られる．
ここで，speciesの"groupoid cardinality"はその母関数に$1$を代入した値に一致するのだから，
\[
2^{\frac{1}{1-n}} = \frac{1}{\sqrt[n-1]{2}}
\]
に一致する．
\subsubsection{考察}
どちらの考察も，非自明な部分は
\[
|\Sigma^*| \overset{?}{=} \frac{1}{1-n}
\]
という\dq{等式}に依存している．(例えば，\dq{2文字の文字列の個数}は$-1$個．)
この等式は，自然な全単射
\[
\Sigma^* = \{\varepsilon\} \sqcup\coprod_{a\in \Sigma} a\Sigma^*.
\]
による濃度の等式
\[
|\Sigma^*| = 1+n |\Sigma^*|
\]
によるもの．
この等式も，$1+\Sigma x$という自己関手の，algebraに関するLambekの補題の定量的反映である．
\internalmemoref{memo-20250125-02}
\subsection{\texorpdfstring{Erd\H{o}s}{Erdos} Problem \texorpdfstring{\#96}{96}}
凸$n$角形$p=(p_1,\dots,p_n)$に対して$U(p)=\#\{(i,j)\mid i<j,\ d(p_i,p_j)=1\}$と定め、
$$
f(n)=\max_{p: \text{convex $n$-gon}}U(p)
$$
とする。このとき
\begin{enumerate}
\item $f(4),f(5),f(6)$を求めよ
\item $f(n)=O(n)$か？
\end{enumerate}
という問題を考えた（二つ目はErdősの未解決問題96番）。$f(4)=5$, $f(5)=6$, $f(6)=8$, $f(7)=10$まで求めた。
一般に
$$
i\neq j \neq k\neq i,\quad i<j,\quad d(p_i,p_j)=1
$$
を満たす$(i,j,k)$をダブルカウントすると
$$
f(n)\leq \dfrac{n}{n-2}f(n-1)
$$
が得られるので、これとグラフ理論的な考察を組み合わせた。また、$f(4)=5$の構成を一つの頂点を中心に回転・複製することで$\dfrac{5}{3}n+O(1)$の構成が得られることに気づいた。現在知られている最良の評価は
$$
2n-7\leq f(n)\leq n\log_2n+4n
$$
らしい。
\section{2025/02/01}
\subsection{自己写像の平方根}
\begin{question}
以下の写像$f$について，$g\circ g =f$なる$g$は存在するか？
\begin{enumerate}
\item $f\colon \N \xrightarrow{+k} \N $ \label{que:20250201First}
\item $f\colon \Z/n\Z \xrightarrow{+k} \Z/n\Z $
\item $f\colon \F_p \xrightarrow{\times k} \F_p$
\item $f\colon \F_p \xrightarrow{{-}^k} \F_p$
\end{enumerate}
\end{question}
Question \ref{que:20250201First}のみを湯澤くんとやった．
\begin{proof}[\textbf{湯澤くんの解法 to Question \ref{que:20250201First}}]
$k$が偶数なら，$g(n) = n+ \frac{k}{2}$とすれば良い．
$k$が奇数のとき，$g\circ g = f$なる$g$が存在すると仮定して矛盾を導く．
$g$の存在を仮定する．$g$と$f$は可換なので，$g(n+k)= g(n)+k$となる．したがって$g\colon \N \to \N$は$\hat{g}\colon \Z/k\Z \to \Z/k\Z$を誘導し，さらにinvolutionになる $\hat{g} \circ \hat{g}= \mathrm{id}_{\Z/k\Z}$．$k$は奇数なので，$\hat{g}$は不動点$\overline{i}\in \Z/k\Z,\; i\in \{0,1,\dots, k-1\}$を持つ．このとき，($g$自体は不動点を持てないので)正整数$a>0$で$g(i)=i+ak$とかけて，$gg(i)= g(i+ak)=g(i)+ak =i+2ak>i+k= f(i)$となり矛盾．
\end{proof}
\begin{proof}[\textbf{想定解の一つ to Question \ref{que:20250201First}}]
離散力学系の圏において，$f\colon \N \xrightarrow{+k} \N $ は $ \N \xrightarrow{+1} \N $の$k$個の直和である．もし$g$があれば，$g$は単射であり，全単射パートと$k'$個の $ \N \xrightarrow{+1} \N $の直和としてかける．すると$f=g\circ g$は全単射パートと$2k'$個の $ \N \xrightarrow{+1} \N $の直和になる．よって，$k=2k'$となり．$k$は偶数でなければならない．$k$が偶数のとき，$g$は簡単に構成できる．
\end{proof}
\subsection{直角二等辺三角形からなる多面体}
全ての面が$(1,1,\sqrt{2})$の直角二等辺三角形であるような凸多面体がどのくらいあるかを考えた。長さ$\sqrt{2}$の辺を挟んで隣り合う面を組にすることで、面の数$F$が偶数であることや、各頂点に集まる角の和が$\pi/2$の倍数（特に$3\pi/2$以下）であることがわかる。これと
$$
\sum_{v:\text{ vertex}} (2\pi - (\text{sum of angles at }v)) = 4\pi
$$
という定理（離散Gauss-Bonnetの定理とも呼ばれ、Eulerの多面体定理から容易に示せる）から、頂点数は$8$以下とわかる。Eulerの多面体定理および全ての面が三角形であることから$V=(F/2)+2$となるので、$F$は$12$以下の偶数である。$F=4$は不可能性を示すことができ、$F=6,8$はそれぞれ例が構成できた。$F=10,12$はおそらく存在しないだろうという話になったが、完全な証明はできていない。
\section{2025/02/09}
\subsection{超立方体グラフの埋め込み}
グラフ$C_n$を，$n$次元超立方体の頂点と辺からなるグラフとする．
\begin{figure}[ht]
\centering
\begin{tikzpicture}[scale=1, every node/.style={draw, circle, inner sep=1.5pt, fill}]
% 1次元超立方体 (線分)
\node (A) at (0,0) {};
\node (B) at (1,0) {};
\draw (A) -- (B);
\end{tikzpicture}
\caption{1次元超立方体グラフ \(C_1\)}
\label{fig:cube1}
\end{figure}
\begin{figure}[ht]
\centering
\begin{tikzpicture}[scale=1.5, every node/.style={draw, circle, inner sep=1.5pt, fill}]
% 2次元超立方体 (正方形)
\node (A) at (0,0) {};
\node (B) at (1,0) {};
\node (C) at (1,1) {};
\node (D) at (0,1) {};
\draw (A) -- (B) -- (C) -- (D) -- (A);
\end{tikzpicture}
\caption{2次元超立方体グラフ \(C_2\)}
\label{fig:cube2}
\end{figure}
\begin{figure}[ht]
\centering
\begin{tikzpicture}[scale=1.5, every node/.style={draw, circle, inner sep=1.5pt, fill}]
% 3次元超立方体 (立方体)
\node (A) at (0,0) {};
\node (B) at (1,0) {};
\node (C) at (1,1) {};
\node (D) at (0,1) {};
\node (E) at (0.5,0.5) {};
\node (F) at (1.5,0.5) {};
\node (G) at (1.5,1.5) {};
\node (H) at (0.5,1.5) {};
\draw (A) -- (B) -- (C) -- (D) -- (A);
\draw (E) -- (F) -- (G) -- (H) -- (E);
\draw (A) -- (E);
\draw (B) -- (F);
\draw (C) -- (G);
\draw (D) -- (H);
\end{tikzpicture}
\caption{3次元超立方体グラフ \(C_3\)}
\label{fig:cube3}
\end{figure}
\begin{question}[出題者:湯澤くん]
$n\geq 2$について，$C_{n}$の中に$C_{n-1}$と同型な部分グラフはいくつあるか？
\end{question}
答えが$2n$であることはすぐに見当がつくが，どう示すか？という話題．
\begin{answer}[洞の解答]
$C_n$は，$n$元集合$A$の冪集合 $\Pow(A)$に$|S\triangle S'|=1$で辺を入れたものだと思える．そこで，$n$元集合$X$と$m$元集合$Y$を用いて，単射グラフ準同型$\Pow(X) \rightarrowtail \Pow(Y)$がちょうど$2^m\frac{m!}{(m-n)!}$個あることを示そう．
単射$f\colon X \rightarrowtail Y$と$A\in \Pow(Y)$を好きにとれば，$F(S) \coloneqq f[S] \triangle A$はグラフ準同型になる．ここで，部分集合$S\subset X$の$f$での像を$f[S]$と書いている．これらだけで，$2^m\frac{m!}{(m-n)!}$個の相異なる準同型がある．(相異なることは空集合とsingletonの行き先を見ればいい)これらしかないことを示そう．単射グラフ準同型$F\colon \Pow(X) \rightarrowtail \Pow(Y)$を任意にとる．
グラフ同型
\[
{-} \triangle F(\emptyset) \colon \Pow(Y) \to \Pow(Y)
\]
を後ろに合成して，新たな単射グラフ準同型$F'\colon \Pow(X) \rightarrowtail \Pow(Y)$で$F'( \emptyset) = \emptyset$なものを得る．
% グラフ$C_n$は等質なので，$f(\emptyset) = \emptyset$ としてよい．
グラフ準同型は辺を保つので，$F'$はsingletonをsingletonに移す．よって，写像$f\colon X \rightarrowtail Y$で$\forall x \in X,\;F'(\{x\}) = \{f(x)\}$なるものを取れる．
$0\leq k \leq n$元部分集合$S \subset X$について$F'(S)=f[S]$が成り立つことを帰納法で示す．$k=0,1$の時は定義より明らか．$k\geq 2$の場合，$k-1, k-2$で成り立つことを仮定する．相異なる元$a,b\in S$をとれば，
\begin{itemize}
\item $F'(S\setminus\{a,b\})=f[(S\setminus\{a,b\}] = f[S] \setminus \{f(a), f(b)\}$,
\item $F'(S\setminus\{a\})=f[(S\setminus\{a\}] = f[S] \setminus \{f(a)\}$,
\item $F'(S\setminus\{b\})=f[(S\setminus\{b\}] = f[S] \setminus \{f(b)\}$
\end{itemize}
が帰納法の仮定からわかる．$f[S]\setminus\{f(a)\},f[S]\setminus\{f(b)\}$の間の距離は$2$であり，これらからちょうど距離が$1$ずつ離れた頂点は$f[S] \setminus \{f(a), f(b)\}$と$ f[S]$のみである．$F'$の単射性より，$F'(S) = f[S]$となる．よって，$F(S) = F'(S) \triangle F(\emptyset) = f[S] \triangle F(\emptyset)$となる．
あとは，単射グラフ準同型$C_{n-1}\rightarrowtail C_n$の個数$2^{n}n!$を単射グラフ準同型$C_{n-1}\xrightarrow{\cong} C_{n-1}$の個数$2^{n-1}(n-1)!$で割れば，答え$2n$を得る．
\end{answer}
\begin{answer}[小泉の解答]
$C_n$は以下のように記述できる：
\begin{itemize}
\item $C_n$の頂点集合は$\mathbb{F}_2^n$である。
\item $v,w\in \mathbb{F}_2^n$が辺で結ばれるのは、ある$i\in \{1,2,\dots,n\}$が存在して$v-w=e_i$が成り立つときである。
\end{itemize}
ただし$e_i\in \mathbb{F}_2^n$は第$i$成分のみが$1$、他の成分が$0$であるベクトルを表す。
任意のグラフ準同型$f\colon C_{n-1}\to C_n$に対し、あるベクトル$v\in \mathbb{F}_2^n$と$i_1,\dots,i_{n-1}\in \{1,\dots,n\}$が存在して
\begin{align}\label{eq:graph_hom}
f(a_1,\dots,a_{n-1})=v+a_1e_{i_1}+\dots+a_{n-1}e_{i_{n-1}}
\end{align}
が成り立つことを示す。このような$f$が単射となるのはちょうど$i_1,\dots,i_{n-1}$が相異なるときであることに注意すれば、単射グラフ準同型$C_{n-1}\to C_n$の像としてあり得る集合は$2n$種類であることが帰結される。
グラフ$C_n$は直積$\underbrace{C_1\square \cdots\square C_1}_{n}$と同一視できる。
グラフ$G$に対し、グラフ$e(G)$を次のように定義する：
\begin{itemize}
\item $e(G)$の頂点集合は$\{(v,w)\in V(G)^2\mid \{v,w\}\in E(G)\}$である。
\item $(v,w)$と$(v',w')$が辺で結ばれるのは、$\{v,v'\},\{w,w'\}\in E(G)$となるときである。
\end{itemize}
するとグラフ準同型$G\square C_1\to H$とグラフ準同型$G\to e(H)$は一対一に対応する（つまり$e({-})$は${-}\square C_1$の右随伴）。よってグラフ準同型$C_{n-1}\to C_n$はグラフ準同型
$$
\ast \to \underbrace{e\circ\dots\circ e}_{n-1}(C_n)=:e^{n-1}(C_n),
$$
つまり$e^{n-1}(C_n)$の頂点と一対一に対応する。ここで
$$
e(C_n)\cong C_n\times \{0,1,\dots,n\};\quad (v,v+e_i)\mapsto (v,i)
$$
という同型が存在するので、これを繰り返し用いることで同型
$$
e^{n-1}(C_n)\cong C_n\times \{0,1,\dots,n\}^{n-1}
$$
が得られる。対応を追うと、右辺のグラフの頂点$(v,i_1,\dots,i_{n-1})$がちょうど\eqref{eq:graph_hom}と対応していることがわかる。以上で示された。
\end{answer}
\section{2025/02/15}
\subsection{\texorpdfstring{$\mathbb{Q}(\sqrt{10})$}{Qroot10}の類数}
類数が$1$でない最初の実二次体は$\mathbb{Q}(\sqrt{10})$らしいという話になり、実際に類数を求めた。
$$
(\sqrt{10}-1)(\sqrt{10}+1)=9=3\cdot 3
$$
にヒントを得て、$\mathfrak{p}=(\sqrt{10}-1,3)$が単項でないと（洞が）予想した。$\mathfrak{p}$の剰余体は
$$
\mathbb{Z}[\sqrt{10}]/\mathfrak{p}
\cong\mathbb{Z}[X]/(X^2-10,X-1,3)\cong\mathbb{F}_3$$
なので、$N_{\mathbb{Q}(\sqrt{10})/\mathbb{Q}}(\mathfrak{p})=(3)$である。もし$\mathfrak{p}=(a+b\sqrt{10})$と表せたとすると
$$
(3)=N_{\mathbb{Q}(\sqrt{10})/\mathbb{Q}}(\mathfrak{p})=((a+b\sqrt{10})(a-b\sqrt{10}))=(a^2-10b^2)\subset \mathbb{Z}
$$
となる。よって
$$
a^2-10b^2=\pm 3
$$
となるが、これはmod $5$で見るとおかしい。よって$\mathfrak{p}$は単項でない。Minkowski boundより類数は$3$以下なので、$\mathfrak{p}$のイデアル類の位数を見れば類数が$2$か$3$かが判別できる。
$$
\mathfrak{p}^2=(11-2\sqrt{10},3\sqrt{10}-3,9)=(\sqrt{10}-1)
$$
なので類数は$2$であるとわかった。
\subsection{原始ピタゴラス数を生成する三分木}
誰か書いて
\subsection{\texorpdfstring{Erd\H{o}s}{Erdos} 288}
\href{https://www.erdosproblems.com/go_to/288}{[Erd\H{o}s open problem \#288]}を考えた．
\begin{question}[{\href{https://www.erdosproblems.com/go_to/288}{[Erd\H{o}s open problem \#288]}}]
Is it true that there are only finitely many pairs of intervals $I_1,I_2$ such that
\[
\sum_{n_1\in I_1} \frac{1}{n_1} + \sum_{n_2\in I_2} \frac{1}{n_2} \in \N \text{ ?}
\]
\end{question}
本質的な$3$つ
\begin{align*}
\left(\frac{1}{2}\right) + \left(\frac{1}{2}\right) &= 1\\
\left(\frac{1}{2}+\frac{1}{3}\right) + \left(\frac{1}{6}\right) &= 1\\
\left(\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}\right) + \left(\frac{1}{20}\right) &= 1\\
\end{align*}
とその自明な$8$つの派生系
\begin{align*}
\left(\frac{1}{1}\right) + \left(\frac{1}{1}\right) &= 2\\
\left(\frac{1}{1}+\frac{1}{2}\right) + \left(\frac{1}{2}\right) &= 2\\
\left(\frac{1}{2}\right)+ \left(\frac{1}{1}+\frac{1}{2}\right) &= 2\\
\left(\frac{1}{1}+\frac{1}{2}\right) + \left(\frac{1}{1}+\frac{1}{2}\right) &= 3\\
\left(\frac{1}{6}\right)+ \left(\frac{1}{2}+\frac{1}{3}\right) &= 1\\
\left(\frac{1}{1}+\frac{1}{2}+\frac{1}{3}\right) + \left(\frac{1}{6}\right) &= 2\\
\left(\frac{1}{6}\right)+ \left(\frac{1}{1}+\frac{1}{2}+\frac{1}{3}\right) &= 2\\
\left(\frac{1}{20}\right)+\left(\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}\right) &= 1\\
\end{align*}
の合計$11$個しか見つからなかった．他にあるんだろうか. Pythonで探索しても，これ以外見つからなかった．
\section{2025/02/22}
\subsection{二次方程式の解の公式の極限}
\begin{question}
$b>0$ のとき，
\[
\lim_{a\to 0} \frac{-b + \sqrt{b^2- 4ac}}{2a}
\]
の値を求めよ．
\end{question}
$a$が十分小さいとき，
\begin{align*}
\frac{-b + \sqrt{b^2- 4ac}}{2a} &= \frac{(-b + \sqrt{b^2- 4ac}) (-b - \sqrt{b^2- 4ac})}{2a(-b - \sqrt{b^2- 4ac})}\\
&= \frac{b^2 -(b^2 -4ac)}{2a(-b - \sqrt{b^2- 4ac})}\\
&= - \frac{2c}{b +\sqrt{{b^2- 4ac}}}\\
&\xrightarrow{a\to 0} - c/b
\end{align*}
関連して，全単射
\[
\C^n / S_n \to \C^n
\]
の話をした．
\section{2025/03/01}
\subsection{K会の問題}
chatGPTによる解説:
\begin{problem}
Let $n \geq 2$ be an integer, and let $a_1, a_2, \dots, a_{n-1}$ be positive real numbers. Define:
\[
\min_{i=1,2,\dots,n-1} \frac{a_{i-1} + a_{i+1}}{a_i}
\]
where the boundary conditions are given by:
\[
a_0 = 0, \quad a_n = 0.
\]
Find the maximum possible value of this minimum expression in terms of $n$.
\end{problem}
\begin{answer}
To maximize the minimum value, we assume a uniform ratio across all indices:
\[
\frac{a_{i-1} + a_{i+1}}{a_i} = c, \quad \text{for all } i = 1,2,\dots,n-1.
\]
Rearranging, we obtain the recurrence relation:
\[
a_{i+1} = c a_i - a_{i-1}.
\]
Our goal is to determine the largest possible value of $c$.
The characteristic equation associated with the recurrence relation is:
\[
r^2 - c r + 1 = 0.
\]
Solving for $r$, we get:
\[
r = \frac{c \pm \sqrt{c^2 - 4}}{2}.
\]
For a stable oscillatory solution (which ensures $a_i > 0$ for all valid $i$), the characteristic roots must be complex, which happens when:
\[
c^2 < 4 \quad \Rightarrow \quad |c| < 2.
\]
Thus, we parametrize $c$ as:
\[
c = 2\cos\theta, \quad 0 < \theta < \pi.
\]
Since the characteristic roots are complex, the general solution takes the trigonometric form:
\[
a_i = A \sin(i\theta) + B \cos(i\theta).
\]
Using the boundary condition $a_0 = 0$, we get $B = 0$, so that:
\[
a_i = A\sin(i\theta).
\]
Applying the second boundary condition $a_n = 0$, we obtain:
\[
A\sin(n\theta) = 0.
\]
Since $A \neq 0$, we require:
\[
\sin(n\theta) = 0 \quad \Rightarrow \quad \theta = \frac{\pi}{n}.
\]
Thus, the optimal choice of $a_i$ is:
\[
a_i = A \sin \left(\frac{\pi i}{n} \right).
\]
We now compute:
\[
\frac{a_{i-1} + a_{i+1}}{a_i}.
\]
Using the sine function representation:
\[
a_{i-1} = A \sin \left(\frac{\pi (i-1)}{n} \right), \quad
a_{i+1} = A \sin \left(\frac{\pi (i+1)}{n} \right).
\]
Using the sum-to-product identity:
\[
\sin A + \sin B = 2 \sin \left( \frac{A+B}{2} \right) \cos \left( \frac{A-B}{2} \right),
\]
we obtain:
\[
\frac{\sin \frac{\pi (i-1)}{n} + \sin \frac{\pi (i+1)}{n}}{\sin \frac{\pi i}{n}}
= 2\cos \frac{\pi}{n}.
\]
Since this value is constant for all $i$, the minimum value is:
\[
\min_{i=1,2,\dots,n-1} \frac{a_{i-1} + a_{i+1}}{a_i} = 2\cos \frac{\pi}{n}.
\]
Thus, the maximum possible value of this minimum expression is:
\[
\boxed{2\cos \frac{\pi}{n}}.
\]
This is achieved when $a_i$ follows the sine wave function:
\[
a_i = A\sin \left(\frac{\pi i}{n}\right).
\]
This completes the proof.
\end{answer}
補足: 定数だけでいいことは，最大値の存在を示した上で，定数でなければ最大でないことを示せば良い．$\theta = \pi/n$を導くところでは，$a_i>0$という条件も使っている．
\section{2025/03/08}
\subsection{Steiner system}
\begin{definition}
整数$0\leq t\leq k\leq n$について，Steiner system $S(t,k,n)$とは，$n$元集合$S$と$S$のk元部分集合からなる集合$\B\subset \{B\subset S \mid |B|=k\}$の組であって，次の条件を満たすものをいう．
\begin{description}
\item[条件] 任意の$t$元部分集合 $A\subset S$について，$A$を含む$\B$の元がただ一つ存在する．
\end{description}
\end{definition}
注意: $S(t,k,n)$は存在するとは限らないし，存在しても一意とは限らない．
context: マシュー群
$S(2,3,7)$からはじめて，$S(4,5,11)$を作ろうと試みていた．
\section{2025/03/15}
\subsection{貪欲展開}
小泉さんの出題．
非負実数$r$について，$r\geq \frac{1}{n}$となる最小の正整数$n$を考え$r$から引くという操作を繰り返すと，$r=\frac{1}{n_1}+ \frac{1}{n_2}+ \dots$という級数展開が得られる．これを\demph{貪欲展開}と呼ぶことにする．
\begin{question}
非負有理数の貪欲展開は有限ステップで終了することを示せ
\end{question}
これは，(既約分数表示の)分子が単調に減少することを示せることからわかる．このことを確かめる．$a,b$は互いに素な正整数とし，$r=\frac{a}{b}$ に対して$\frac{a}{b}\geq \frac{1}{n}$なる最小の正整数$n$を取る．
\[
\frac{a}{b} - \frac{1}{n} = \frac{an -b}{bn}
\]
なので，$a> an-b$を示せばいい．
$n=1$なら分子が$a-b$になり確かに減少している．
$n\geq 2$なら，$n$の最小性から
\[
\frac{1}{n-1} > \frac{a}{b}
\]
となり，この不等式は示したい不等式$a> an-b$と同値である．
\begin{question}
$\frac{7-\sqrt{5}}{2}$の貪欲展開は何で与えられるか?
\end{question}
具体計算によって，
\[
\frac{7-\sqrt{5}}{2} = \dfrac{1}{1}+\dfrac{1}{1}+\dfrac{1}{3}+\dfrac{1}{21}+\dfrac{1}{987}+\cdots = \sum_{n=0}^{\infty}\frac{1}{F_{2^n}}
\]
であることが推測された．ここで，$F_n$は$F_0 =0, F_1= 1$とした場合のフィボナッチ数である．この等式は以下のようにして正当化される．(Ueoroさんのアイデア)
(フィボナッチの一般項($\frac{1}{\sqrt{5} F_n} = \frac{1}{\phi^n - \psi^n}$)を使い，さらに例外的な$n=0$の振る舞いを避けるために)以下では(両辺から$1$を引いて$\sqrt{5}$で割った)
\[
\frac{\sqrt{5}-1}{2} = \sum_{n=1}^{\infty}\frac{1}{\sqrt{5} F_{2^n}}
\]
を示そう．正整数$n$については$2^n$が偶数なので，$\phi^{2^n} = (-\frac{1}{\psi})^{2^n} = \frac{1}{\psi^{2^n}}$となり，
\[
\frac{1}{\sqrt{5} F_{2^n}} = \frac{1}{\phi^{2^n} - \psi^{2^n}} = \frac{\psi^{2^n}}{1-\psi^{2\cdot 2^{n}}} = \psi^{2^n} + \psi^{3\cdot 2^n}
+ \psi^{5\cdot 2^n}+ \psi^{7\cdot 2^n}+ \dots
\]
を得る．つまり，$\psi$の指数に$2$でちょうど$n$回割れる正整数を入れたものを足している．したがって，
\[
\sum_{n=1}^{\infty}\frac{1}{\sqrt{5} F_{2^n}} = \sum_{k=1}^{\infty} \psi^{2k} = \frac{\psi^2}{1-\psi^2} =\frac{\sqrt{5} -1}{2}
\]
を得る．(これが貪欲展開で与えられることを，洞は理解していない．)
% % \begin{align*}
% % \frac{1}{F_n} = \frac{\sqrt{5}}{\phi^n - \psi^n}
% % \end{align*}
% \[
% \frac{1}{F_n} = \frac{\sqrt{5}}{\phi^n - \psi^n}
% \]
% より，
% \[
% \frac{1}{\sqrt{5} F_n} = \frac{1}{\phi^n - \psi^n}
% \]
\subsection{Steiner system \texorpdfstring{$S(3,4,10)$}{S}}
Steiner system $S(3,4,10)$は，完全グラフ$K_5$を用いて以下のように構成できる．まず，$5$次完全グラフには$\binom{5}{2}=10$本の辺があり，これをSteiner systemの台集合とする．
% \begin{figure}[ht]
% \centering
% \begin{tikzpicture}
% \def\n{5} % 頂点の数
% \def\r{2} % 半径
% \foreach \i in {1,2,...,\n} {
% \coordinate (V\i) at ({360/\n * (\i-1)}:\r);
% }
% \foreach \i in {1,2,...,\n} {
% \foreach \j in {\i,...,\n} {
% \ifnum\i<\j
% \draw (V\i) -- (V\j);
% \fi
% }
% }
% \foreach \i in {1,2,...,\n} {
% \fill (V\i) circle (3pt);
% }
% \end{tikzpicture}
% \caption{完全グラフ \(K_5\)}
% \end{figure}
ブロック ($=$ 選び出される$4$元部分集合)の個数は一般論により
\[
\frac{\binom{10}{3}}{\binom{4}{3}} =30
\]
となる．ブロックは，辺$4$つの集まりであって，\Cref{fig:Blocks}のいずれかと同型であるものを取れば良い．
\begin{figure}[ht]
\centering
\begin{minipage}{0.3\textwidth}
\centering
\begin{tikzpicture}
\def\n{5} % 頂点の数
\def\r{2} % 半径
\foreach \i in {1,2,...,\n} {
\coordinate (V\i) at ({360/\n * (\i-1)}:\r);
}
% すべての辺をグレーで描画
\foreach \i in {1,2,...,\n} {
\foreach \j in {\i,...,\n} {
\ifnum\i<\j
\draw[gray] (V\i) -- (V\j);
\fi
}
}
% 黒で強調する辺 (1-2, 2-3, 3-1, 4-5)
\draw[black, line width=1pt] (V1) -- (V2);
\draw[black, line width=1pt] (V2) -- (V3);
\draw[black, line width=1pt] (V3) -- (V1);
\draw[black, line width=1pt] (V4) -- (V5);
% 頂点を描画
\foreach \i in {1,2,...,\n} {
\fill (V\i) circle (3pt);
}
\end{tikzpicture}
\end{minipage}
\hfill
\begin{minipage}{0.3\textwidth}
\centering
\begin{tikzpicture}
\def\n{5} % 頂点の数
\def\r{2} % 半径
\foreach \i in {1,2,...,\n} {
\coordinate (V\i) at ({360/\n * (\i-1)}:\r);
}
% すべての辺をグレーで描画
\foreach \i in {1,2,...,\n} {
\foreach \j in {\i,...,\n} {
\ifnum\i<\j
\draw[gray] (V\i) -- (V\j);
\fi
}
}
% 黒で強調する辺 (1-2, 2-3, 3-1, 4-5)
\draw[black, line width=1pt] (V1) -- (V2);
\draw[black, line width=1pt] (V1) -- (V3);
\draw[black, line width=1pt] (V1) -- (V4);
\draw[black, line width=1pt] (V1) -- (V5);
% 頂点を描画
\foreach \i in {1,2,...,\n} {
\fill (V\i) circle (3pt);
}
\end{tikzpicture}
\end{minipage}
\hfill
\begin{minipage}{0.3\textwidth}
\centering
\begin{tikzpicture}
\def\n{5} % 頂点の数
\def\r{2} % 半径
\foreach \i in {1,2,...,\n} {
\coordinate (V\i) at ({360/\n * (\i-1)}:\r);
}
% すべての辺をグレーで描画
\foreach \i in {1,2,...,\n} {
\foreach \j in {\i,...,\n} {
\ifnum\i<\j
\draw[gray] (V\i) -- (V\j);
\fi
}
}
% 黒で強調する辺 (1-2, 2-3, 3-1, 4-5)
\draw[black, line width=1pt] (V2) -- (V3);
\draw[black, line width=1pt] (V3) -- (V4);
\draw[black, line width=1pt] (V4) -- (V5);
\draw[black, line width=1pt] (V5) -- (V2);
% 頂点を描画
\foreach \i in {1,2,...,\n} {
\fill (V\i) circle (3pt);
}
\end{tikzpicture}
\end{minipage}
\caption{$10+ 5 + 15 = 30$個のブロック}
\label{fig:Blocks}
\end{figure}
これの自己同型群がいわゆるMathieu group $M_{10}$というやつらしい(文献求)(Twelve Sporadic Groups(Robert L. Jr. Griess)とかがいいんじゃない,S(3,4,10)が書いてあるかは怪しいけど... by 神尾)．これは単純ではないが，almost simple groupというクラスに入るらしい．
我々の構成から，$M_{10}$が$S_5$を部分群にもつことはわかるが，$S_5$は全体ではなく，指数$6$の部分群になっているらしい．
\section{2025/03/22}
\subsection{4周期数列 (エレガントな回答を求む)}
\begin{question}
実数$x,y,z,w$であって，
\begin{align*}
\frac{2x}{1-x^2}&=y\\
\frac{2y}{1-y^2}&=z\\
\frac{2z}{1-z^2}&=w\\
\frac{2w}{1-w^2}&=x\\
\end{align*}
を満たすものを全て求めよ．
\end{question}
\begin{answer}[大釋くんのアイデア]
${\tan}$の倍角公式
\[
\tan(2\theta) = \frac{2\tan\theta}{1-(\tan \theta)^2}
\]
を利用したい．$\tan$の値は無限も取りうるから，一旦
$\R P_1$ 上の自己写像 $\frac{2x}{1-x^2}$，つまり
\[
x \mapsto
\begin{cases}
\frac{2x}{1-x^2} &(x\neq 1,-1,\infty)\\
\infty &(x=1,-1)\\
0 &(x= \infty)
\end{cases}
\]
を考えよう．まずはこの力学系 $(\R P_1, \frac{2x}{1-x^2})$ の$4$周期点を全て求め，その後に$\infty$を通るものを除外することを考える．
$\tan$の倍角公式より，我々の知りたい力学系 $(\R P_1, \frac{2x}{1-x^2})$ はより単純な力学系$(\R/\Z, 2x)$と
\[
\R/\Z \ni \alpha \mapsto \tan (\alpha \pi) \in \R P_1
\]
で同型である\footnote{位相力学系として同型だが，それは使わない．}．
よって，$\R/\Z$の元$\alpha$で$2^4 \alpha \equiv \alpha \mod \Z$なるものを決定すれば良い．$i\in \Z$を用いて$\alpha\equiv \frac{i}{15} \mod \Z$となるしかないので，元の問題の答えは $(x,y,z,w)=$
\begin{itemize}
\item $(\tan(\frac{0\pi}{15}),\tan(\frac{0\pi}{15}),\tan(\frac{0\pi}{15}),\tan(\frac{0\pi}{15})) =(0,0,0,0)$,
\item $(\tan(\frac{5\pi}{15}),\tan(\frac{10\pi}{15}),\tan(\frac{5\pi}{15}),\tan(\frac{10\pi}{15})) =(\sqrt{3},-\sqrt{3},\sqrt{3},-\sqrt{3})$,
\item $(\tan(\frac{1\pi}{15}),\tan(\frac{2\pi}{15}),\tan(\frac{4\pi}{15}),\tan(\frac{8\pi}{15}))$,
\item $(\tan(\frac{3\pi}{15}),\tan(\frac{6\pi}{15}),\tan(\frac{12\pi}{15}),\tan(\frac{9\pi}{15}))$,
\item $(\tan(\frac{7\pi}{15}),\tan(\frac{14\pi}{15}),\tan(\frac{13\pi}{15}),\tan(\frac{11\pi}{15}))$,
\end{itemize}
とこれを巡回的に並べ替えたものに限られる．(ここには無限$\infty \in \R P_1$が現れていないことに注意．)
\end{answer}
\subsection{三角関数×有理式の積分}
\begin{question}
\[
\int_{-\infty}^\infty \frac{\cos x}{(1+x^2)^2} dx
\]
を求めよ．
\end{question}
\begin{answer}
\[
I =\int_{-\infty}^\infty \frac{\cos x}{(1+x^2)^2} dx
\]
とすると，
\[
\int_{-\infty}^\infty \frac{\sin x}{(1+x^2)^2} dx =0
\]
より
\[
I =\int_{-\infty}^\infty \frac{e^{ix}}{(1+x^2)^2} dx
\]
である．$f(z) \coloneqq \frac{e^{iz}}{(1+z^2)^2}$を原点を中心とした上半円で積分すると，留数定理より
\[
I = 2\pi i \mathrm{Res}_{z=i} f(z)
\]
となり，留数計算によって$I=\pi/e$がわかる．
\end{answer}
これって，$\frac{1}{1+x^2}$のフーリエ変換がわかってることからすぐにわかるんですか？また，初等的には計算できるんでしょうか．
\section{2025/04/05}
\subsection{フロベニウスの定理}
$S_5$の元で$x^{10}=1$なるものの個数が$50$らしい．
$S_{10}$の元で$x^{100}=1$なるものの個数は$100$の倍数らしいが，具体的な値は求めるに至らなかった．
一般に，次が知られているらしい．
\begin{fact}[フロベニウスの定理: フロベニウスの定理引用求]
有限群$G$と，その位数を割り切る正整数$n\mid \#G$について，
\[
\#\{x\in G\mid x^n=1\}
\]
は$n$の倍数である．
\end{fact}
非常に簡単な場合として$G=\Z/nm\Z$を考えると，$\{x\in G\mid x^n=1\}=m\Z/nm\Z$ の元の個数は$n$になっている．
非可換な場合を考えれば，これは部分群にもならないから，元の個数に整数論的制約がかかるのは非自明に感じる．
\section{2025/05/10}
\subsection{グラフ理論の問題}
\begin{question}
任意の単純グラフに対し、以下の操作を有限回行うことで空にできることを示せ。
\begin{enumerate}
\item 次数が奇数または$0$の頂点を削除する。
\item グラフを複製し、対応する頂点同士を辺で結ぶ。
\end{enumerate}
\end{question}
上苙さんの出題。出典はJMO春合宿らしい。
\begin{answer}
グラフを適当に彩色しておく。以下の一連の操作をこの順に繰り返す：
\begin{itemize}
\item 操作1を可能な限り行う。
\item 全ての頂点の次数が正の偶数になったら操作2を行う（全ての頂点の次数が奇数になる）。
\item 複製の片側は元の色で塗り、もう片側は元の色を巡回的にずらしたもので塗る。
\item 頂点を任意に選び、同じ色の頂点を全て削除する（同じ色の頂点は隣り合わないので全て消せる）。
\end{itemize}
すると毎回色が減っていくのでどこかで空になる。
\end{answer}
\subsection{群論の問題}
\begin{question}
自明でない有限群$G$に対し、以下のような部分集合$A\subset G$が存在することはあるか？
\begin{itemize}
\item $A\times A\to G;\ (a,b)\mapsto ab$は全単射である。
\end{itemize}
\end{question}
神尾の出題。
\begin{answer}（高梨）
このような$A$は決して存在しないことを示す。$\varnothing\neq S\subset G$に対し、群環$\mathbb{C}[G]$の元$e_S$を
$$
e_S=\dfrac{1}{\#S}\sum_{g\in S}g
$$
で定める。このとき
$$
e_Se_G=e_Ge_S=e_G
$$
が成り立つことに注意する。問題文の条件を満たす$A\subset G$が存在したとすると
$$
e_A^2=e_G
$$
となる（$\#A^2=\#G$に注意）。よって
\begin{align*}
(e_A-e_G)^2&{}=e_A^2-e_Ae_G-e_Ge_A+e_G^2\\
&{}=e_G-e_G-e_G+e_G=0
\end{align*}
となるので$e_A-e_G$は冪零である。特に$e_A\curvearrowright\mathbb{C}[G]$と$e_G\curvearrowright\mathbb{C}[G]$のトレースは一致する。前者は$0$または$\#G/\#A$であり後者は$1$なので$\#G=\#A$が得られ、$G$が自明でないという仮定に反する。
\end{answer}
\subsection{多項式の微分の問題}
\begin{question}
実数係数多項式$f$が$\mathbb{R}$上非負ならば
$$
g=f+f'+f''+\cdots
$$
も$\mathbb{R}$上非負であることを示せ。
\end{question}
神田の中学生の頃の日記からの出題。
\begin{answer}（神田）
$f\geq 0$より$f$の次数は偶数であり、したがって$g$の次数も偶数である。特に$g$は最小値を持つ。$g(a)$が最小値であるとすると
$$
g(a)=g(a)-g'(a)=f(a)\geq 0
$$
なので$g\geq 0$となる。
\end{answer}
\begin{answer}（小泉）
部分積分により
$$
\displaystyle\int_x^\infty f(t)e^{-t}dt = f(x)+f'(x)+f''(x)+\cdots=g(x)
$$
となる。被積分関数は非負なので$g(x)$も非負である。
\end{answer}
\section{2025/05/17}
\subsection{格子三角形の重心}
\begin{question}
格子点を頂点とする三角形$ABC$が内部にちょうど$3$つの格子点を含むとき、三角形$ABC$の重心は格子点ではないことを示せ。
\end{question}
American Mathematical Monthlyからの出題。「$3$つ」を「$n$個」に変えたときどのような$n$に対して同じことが成り立つかはわかっていないらしい。
\begin{answer}
三角形$ABC$の重心$G$が格子点だと仮定して矛盾を導く。
辺$AB,BC,CA$の内部に含まれる格子点の個数をそれぞれ$a,b,c$とする。
三角形$ABC$の周上の格子点を反時計回りに
$$
A,P_1,P_2,\cdots,P_a,B,Q_1,\cdots,Q_b,C,R_1,\cdots,R_c\\
$$
とおく。
$a$が偶数のときは$a=2k$とし、$a$が奇数のときは$a=2k-1$とすると
$$
G,\ G+\overrightarrow{P_0P_1},\ G-\overrightarrow{P_0P_1},\ G+\overrightarrow{P_kG}
$$
はすべて格子点である。これらのいずれかが三角形$ABC$の内部に含まれないことから$a\leq 2$がわかる。
同様に$b,c\leq 2$である。
一方でPickの定理より
$$
3\mathrm{Area}(\triangle ABG)=\mathrm{Area}(\triangle ABC)=3+\dfrac{a+b+c+3}{2}-1=\dfrac{a+b+c+7}{2}
$$
である。$\mathrm{Area}(\triangle ABG)$は半整数なので
$$
a+b+c\equiv 2\pmod 3
$$
となる。以上より$(a,b,c)$は
$$
(1,1,0),\ (2,0,0),\ (2,2,1)
$$
のいずれかであるとして一般性を失わない。
\begin{itemize}
\item $(a,b,c)=(1,1,0)$の場合、$P_1+\overrightarrow{BQ_1}$は辺$CA$の内部の格子点となり矛盾する。
\item $(a,b,c)=(2,0,0)$の場合、$G+\overrightarrow{P_1G}$は辺$BC$の内部の格子点となり矛盾する。
\item $(a,b,c)=(2,2,1)$の場合、$P_1+\overrightarrow{BQ_1}$は辺$CA$の内部の格子点となり矛盾する。
\end{itemize}
以上のようにいずれの場合も矛盾するため、$G$は格子点ではあり得ない。
\end{answer}
\section{2025/05/24}
\subsection{二次の不定方程式}
\begin{question}
正整数$d$であって
$$
d(d+1)x^2-y^2=d^2-1
$$
が整数解$(x,y)$を持つようなものを全て求めよ。
\end{question}
American Mathematical Monthlyからの出題。
$d=k^2-1$と表せる場合には$(x,y)=(1,k)$が解になる。
それ以外の場合、$d\leq 16$の範囲では解がないことが適切な法で還元することで示せた。
$d=17$の場合、簡単な議論によって
$$
17x^2-2y^2=1
$$
に整数解があるかという問題に帰着される。
有理数解$(1/3,2/3),(3/5,8/5)$が存在するので、任意の正整数$n$に対して$\mathbb{Z}/n\mathbb{Z}$に解を持つ。よって、適切な法で還元することで解の非存在を示すという手法は通用しない。
これについてはChatGPTが以下のように解の非存在を示してくれた。まず全体を$17$倍して
$$
(17x)^2-34y^2=17
$$
とする。
この式は$17$が$\alpha:=17x+y\sqrt{34}\in \mathbb{Z}[\sqrt{34}]$のノルムであることを意味する。
$\mathbb{Z}[\sqrt{34}]$において$17$は$(17)=(17,\sqrt{34})^2$と分岐するので、$(17,\sqrt{34})=(\alpha)$となる必要がある。
一方で$\beta=17+3\sqrt{34}$とすると
$$
\mathrm{Nm}_{\mathbb{Q}(\sqrt{34})/\mathbb{Q}}(\beta)=17^2-9\cdot 34=-17
$$
なので$(17,\sqrt{34})=(\beta)$である。
よって単数$u$が存在して$\alpha=u\beta$となる。
$\mathbb{Z}[\sqrt{34}]$の単数群は基本単数$\varepsilon=35+6\sqrt{34}$で生成され、
$$
\mathrm{Nm}_{\mathbb{Q}(\sqrt{34})/\mathbb{Q}}(\varepsilon)=35^2-36\cdot 34=1
$$
なので、$\mathrm{Nm}_{\mathbb{Q}(\sqrt{34})/\mathbb{Q}}(\alpha)=\mathrm{Nm}_{\mathbb{Q}(\sqrt{34})/\mathbb{Q}}(\beta)=-17$となり矛盾する。
\section{2025/06/28}
\subsection{極限の計算}
\begin{problem}
次の値を求めよ
\[
\sqrt{1+ 2\sqrt{1+ 3\sqrt{1+ 4\sqrt{1+ \cdots}}}}
\]
\end{problem}
我々の考察は次のように進んだ．
Informalなアイデアは以下のとおりである．
まず，一旦収束を気にせずに次の関数
\[
h(x)= \sqrt{1+ x\sqrt{1+ (x+1)\sqrt{1+ (x+2)\sqrt{1+ \cdots}}}}
\]
を考える．すると，$h(x)\; (x>0)$が収束するなら，
\begin{align*}
h(x)^2 &= 1+ x\sqrt{1+ (x+1)\sqrt{1+ (x+2)\sqrt{1+ \cdots}}} \\
&=1+xh(x+1)
\end{align*}
を満たす．この関数方程式 $f(x)^2 =1+xf(x+1)$は$f(x)=x+1$で満たされることを観察し，我々は $h(x)=x+1$となることを予想した．これが正しければ，答えは$h(2)=3$である．
ここから厳密な議論に入る．
非負整数$n$ごとに関数$h_n\colon (0, \infty) \to (0, \infty)$を
\begin{align*}
h_0(x) &= 1\\
h_{n+1}(x)&=\sqrt{1+ xh_{n}(x+1)} \; (n\geq 0)
\end{align*}
で再帰的に定義する．$h(x)$は$\lim_{n\to \infty} h_n(x)$で定義されている．
$x+1$の満たす関数方程式$f(x)^2 =1+xf(x+1)$ i.e., $f(x) =\sqrt{1+xf(x+1)}$ から，再帰的に
\[
1+x =\sqrt{1+x (x+2)} = \sqrt{1+x \sqrt{1+(x+1) (x+3)}}= \sqrt{1+x \sqrt{1+(x+1) \sqrt{1+(x+2) (x+4)}}}= \cdots
\]
を得る．形を見比べる(最後の$x+n$の部分を1に置き換える)と，
$x>0$を固定するごとに
$1=h_0(x)<h_1(x)<h_2(x) < \cdots x+1$が成立していることがわかり，$\lim_{n\to \infty} h_n(x)$は有界単調増加列の極限となり，$1$以上$x+1$以下の値へ収束することわかる．また，各$h_n$が単調増加なので，$h$も講義単調増加である．
下からの評価は繊細で，神尾くんが示した．(洞が改変しているから，ミスがあれば洞の責任) まず，(今や厳密に示された)関係式 $h(x)^2 =1+xh(x+1)$を用いて，$h(x)\geq x^{\frac{2^{k} -1}{2^{k}}}$が自然数$k$について帰納的に示される:
\begin{description}
\item[\textbf{$k=0$:}] $h(x)\geq h_0(x) =1 = x^0$
\item[\textbf{$k\to k+1$:}] $h(x)= \sqrt{1+xh(x+1)} \geq \sqrt{xh(x)} \geq \sqrt{x\cdot x^{\frac{2^k-1}{2^k}}}=x^{\frac{2^{k+1}-1}{2^{k+1}}}$.
\end{description}
よって，$k \to \infty$として，$h(x)\geq x$を得る．
さらに，任意の自然数$k$について$h(x) \geq x+\frac{2^k-1}{2^k}$が成立することを帰納法で以下のように示せる:
\begin{description}
\item[\textbf{$k=0$:}] $h(x)\geq x$ (上記)
\item[\textbf{$k\to k+1$:}] $h(x)= \sqrt{1+xh(x+1)} \geq \sqrt{1+x (x+1+ \frac{2^k-1}{2^k})} = \sqrt{x^2 + 2\cdot \frac{2^{k+1}-1}{2^{k+1}} x + 1} \geq x+ \frac{2^{k+1}-1}{2^{k+1}}$
\end{description}
よって，$k \to \infty$として，$h(x)\geq x+1$を得る．
\section{2025/7/5}
\subsection{\texorpdfstring{$q$}{q}-二項係数は多項式}
$q$-二項係数$\binom{n}{m}_{q}$を，以下で定める．
\begin{itemize}
\item $[n]_q \coloneqq 1+q+q^2+ \dots + q^{n-1} \in \Z[q]$.
\item $[n]_q! \coloneqq [1]_q \times [2]_q \times \dots \times [n]_q!$
\item $\binom{n}{m}_{q} \coloneqq \frac{[n]_q!}{[m]_q![n-m]_q!} \in \Q(q)$.
\end{itemize}
$\binom{n}{m}_{q}$は(a prioriには$\Q(q)$の元だが実は)$\Z[q]$の元になることを示せ．
おそらく想定解の一つは$\mathbb{F}_q$上のグラスマン多様体の元の数え上げなのだが，ここでは初等的に示す．
\[
\binom{n+1}{m+1}_{q} =\binom{n}{m}_{q} + q^{m+1}\binom{n}{m+1}_{q}
\]
を示せば帰納的に全ての$q$-二項係数が多項式であることがわかる．非負整数$a,b$について$[a]_q+q^a[b]_q=[a+b]_q$が成り立つことに注目すると，
\begin{align*}
\binom{n}{m}_{q} + q^{m+1}\binom{n}{m+1}_{q}
&= \frac{[n]_q!}{[m]_q![n-m-1]_q!} \times \left(\frac{1}{[n-m]_q}+\frac{q^{m+1}}{[m+1]_q}\right)\\
&= \frac{[n]_q!}{[m]_q![n-m-1]_q!} \times \left(\frac{[n+1]_q}{[n-m]_q [m+1]_q}\right)\\
&= \frac{[n+1]_q!}{[m+1]_q![n-m]_q!} \\
&= \binom{n+1}{m+1}_{q}
\end{align*}
でOK.
\href{https://manabitimes.jp/math/3957}{[高校数学の美しい物語: 組み合わせ論による q-二項係数の定義]}
に組み合わせ論的解釈が載っていたので参照しておきます．
\subsection{\texorpdfstring{$F_2$}{F2}のケーリーグラフ上のランダムウォーク}
$F_2$のケーリーグラフ(次数$4$の無限正則木)上のランダムウォークで，スタート地点に(少なくとも1回)帰ってくる確率を求めよ．
各移動で点が原点に近づく確率は(点が原点にいるときは$0$でそうでない限り)$1/4$である．そして，遠ざかる確率は(点が原点にいるときは$1$でそうでない限り)$3/4$である．よって，
$2n+2$秒でちょうど原点に帰ってくる確率は，カタラン数$C_n$を用いて
\[
C_n \left(\frac{3}{4}\right)^{n} \left(\frac{1}{4}\right)^{n+1}= \frac{1}{4} C_n \left(\frac{3}{16}\right)^{n}
\]
と表せる．ここで，カタラン数の母関数
\[
g(x) = \sum_{n=0}^{\infty}C_n x^n = \frac{1-\sqrt{1-4x}}{2x}
\]
を用いれば，求めたい値は
\[
\sum_{n=0}^{\infty}\frac{1}{4} C_n \left(\frac{3}{16}\right)^{n} = \frac{1}{4} g\left(\frac{3}{16}\right) = \frac{1}{3}
\]
と求まる．
\section{2025/7/26}
\subsection{二重否定除去}
直観主義命題論理における二重否定除去則の証明不可能性の話を，遠藤くんからの不完全性定理の質問の文脈で話した．
\subsection{素数生成数列}
整数$n\geq 2$に対して数列$a_1,a_2,\dots,a_n$を以下のように定める：
$$
a_1=n,\quad a_{k+1}=a_k+\gcd(a_k,n-k).
$$
例えば$n=8$のときは以下のようになる：
$$
8\xrightarrow{+\gcd(8,7)}9\xrightarrow{+\gcd(9,6)}12\xrightarrow{+\gcd(12,5)}13
\xrightarrow{+\gcd(13,4)}14\xrightarrow{+\gcd(14,3)}15\xrightarrow{+\gcd(15,2)}16\xrightarrow{+\gcd(16,1)}17.
$$
このとき$a_n$が必ず素数になるという予想があるらしい（https://oeis.org/A375345）。
$a_k+(n-k)$はひとたび素数になるとそこから一定の値になるので、確率的には妥当な予想である。
後ろから辿ることで、（$n$が十分大きいとき）$a_n$が$2,3,5$の倍数にならないことが示せた。$7$の倍数にならないことも示せたつもりになったが自信はない。
\section{2025/08/02}
\subsection{白黒の石の問題}
小泉さん出題:
\begin{problem}
白黒の石を$n$枚円形に並べる．次の操作を繰り返し，白い石$2$つにできるような初期配置の数を求めよ．ただし回転や反転で移り合うものも区別して数えることとする．
\begin{description}
\item[操作] 白い石を一つ選んで取り除き，その左右の石の色を反転させる．
\end{description}
\end{problem}
\begin{answer}
白い石に$\sigma \coloneqq (1,2,3) \in S_3$ 黒い石に$\tau \coloneqq (1,2)\in S_3$を割り当てる．円形の石の配置について，ある石から時計周りに$S_3$の元として演算していくと，$S_3$の元が定まる．これは最初の石の選び方に依存するが，(一般に群で$ba = a^{-1}(ab)a$なので)$S_3$の共役類$[e], [\sigma], [\tau]$はwell-definedに定まる．さらに，以下の関係式よりこの量$\in \{[e], [\sigma], [\tau]\}$は問題の操作で不変である．
\begin{itemize}
\item $\sigma\sigma\sigma = \tau \tau$
\item $\sigma \sigma \tau = \tau \sigma$
\item $\tau \sigma \sigma= \sigma \tau$
\item $\tau \sigma\tau= \sigma\sigma$
\end{itemize}
石の初期配置に対して，白い石$2$つにできることと，不変量が$[\sigma]$であることは同値であることを示す．実際，白い石が$2$つの時不変量は$[\sigma \sigma] =[\sigma]$であるので，必要性はすぐにわかる．十分性を見る．まず，不変量が$[\sigma]$なら，$[\sigma]\neq [\tau^k]$なので，白い石が少なくとも一つある．従って石を$2$つまで減らすことが可能である．石が$2$つまで減れば， $[\sigma \tau]=[\tau\sigma]=[\tau]$と$[\tau\tau]=[e]$により，不変量を見るだけで白い石$2$つにならざるを得ないことがわかる．(つまり，不変量が$[\sigma]$であれば，白い石を適当に選択すれば白い石$2$つにできる．)
これで，以下の数え上げ問題に帰着された．
$\sigma$と$\tau$の長さ$n$の文字列であって，$S_3$の元として計算した時に$\sigma$か$\sigma^2$になるものの個数を数えよ．漸化式を立てて解くと
\[
\frac{2^n-(-1)^n}{3}
\]
になる．オートマトンから直接有理式の母関数を取り出すこともできる．
\end{answer}
\subsection{半径1の円周での積分が消える関数}
\begin{problem}
平面上の実連続関数$f(x,y)$で,
半径$1$の任意の円周での積分が$0$となるものは$f=0$以外にあるか.
\end{problem}
\begin{answer}
ある.
天下り的には以下のとおり.
$f(x,y)=\cos(ax)$とする.
ここで$a$は
\[
\int_0^{2\pi}\cos(a\cos\theta) d\theta=0
\]
を満たす実数である.
このような$a$の存在は,
中間値の定理を用いれば高校数学の範囲で示すことができる.
(ちなみに$a$を変数として見ると,
これは第一種ベッセル関数である. )
$(x_0,y_0)$を中心とした半径$1$の円で積分すると
\begin{align*}
\int_0^{2\pi} f(x_0+\cos \theta, y_0+\sin \theta) d\theta
&= \int_0^{2\pi} \cos(a(x_0+\cos \theta)) d\theta \\
&= \int_0^{2\pi} (\cos(ax_0)\cos(a\cos\theta)-\sin(ax_0)\sin(a\cos\theta) ) d\theta \\
&= \cos(ax_0)\int_0^{2\pi}\cos(a\cos\theta) d\theta-\sin(ax_0)\int_0^{2\pi}\sin(a\cos\theta) d\theta.
\end{align*}
第$1$項は$a$の取り方より,
第$2$項は$\sin$が奇関数であることより$0$となる.
\end{answer}
\begin{context}
神田がふと思いついた問題.
ほら君が「円周測度のフーリエ変換の零点をサポートに持つ関数の
逆フーリエ変換を考えればいいのでは」と言ってすぐ解けた.
アイデアの詳細は以下のとおり.
実連続関数で求める必要があるが,
複素で求めて実部を取ればいいので,
複素で考えることにする.
$E$を円周測度とする.
これは$\R^2$上の超関数であり,
テスト関数を単位円周上で積分することでevaluateするものである.
求めたい関数を$f$とすると,
条件は$E * f=0$となる.
これをフーリエ変換すると$\hat{E} \hat{f}=0$となるが,
$\hat{E}$は以下のよう計算できる.
\[
\hat{E}(\xi,\mu)
=\int_0^{2\pi} e^{-i(\xi \cos\theta+\mu \sin\theta)} d\theta
\]
$r=\sqrt{\xi^2+\mu^2}$とすれば,
\[
\hat{E}(\xi,\mu)=\int_0^{2\pi} e^{-ir\cos\theta} d\theta =2\pi J_0(r).
\]
となる.
$J_0$は第一種ベッセル関数である(Hansenの積分表示).
ベッセル関数の零点で$0$以上のものは離散的に出現することが知られているので,
それらを$0<a_1<a_2<\cdots$とする.
原点を中心とした半径$a_1, a_2,\ldots$の円の和集合を$A$とする.
$\hat{E} \hat{f}=0$となるには,
$\hat{f}$のサポートが$A$に含まれていればよい.
たとえば$a=a_1$として,
点$(a,0)$をサポートに持つデルタ関数$\delta_{(a,0)}$をとる.
$\delta_{(a,0)}$の逆フーリエ変換は
定数倍を除いて$e^{iax}$となり,
その実部は$\cos (ax)$である.
これらの考察からわかるよう,
条件を満たす関数はたくさんある.
なお,
$\R^3$で半径$1$の球面での積分を考えても同様の解法でできる.
球面測度$E$のフーリエ変換さえ求まればよいが,
これはH\"{o}rmanderのPDEの教科書の$1$巻の演習問題$7.1.42$であり,
\[
\hat{E}(\xi_1,\xi_2,\xi_3)=4\pi \frac{\sin r}{r}
\]
となる. ここで$r=\sqrt{\xi_1^2+\xi_2^2+\xi_3^2}$.
よってたとえば$\delta_{(\pi,0,0)}$を逆フーリエ変換して定数倍し実部をとった
$f(x,y,z)=\cos(\pi x)$は条件をみたす.
$2$次元の場合よりも状況が簡単になるのは少し不思議である.
$4$次元以上の場合の球面測度のフーリエ変換については計算したことがない.
$3$次元の場合には極座標$(r,\theta,\phi)$を用いて計算した.
$4$次元以上も一般化極座標で計算できるのかもしれない.
計算できたら教えて欲しい.
\end{context}
\section{2025/08/17}
\subsection{湯山さんのバランス語問題}
$a,b$からなる有限文字列が\demph{バランス語}であるとは，$a,b$の個数が等しいことをいう．例えば，$aabbab$ や$bbbbaaaabbaaaaabbbbbaa$や $\epsilon$(空文字列)はバランス語であり，$a$や$bbbbaaa$はバランス語ではない．
\begin{problem}[湯山さんのバランス語問題]
全てのバランス語は，以下の操作で生成できるか？
\begin{enumerate}
\item 文字列$XY$を考える．
\item 次の操作を有限回繰り返す
\begin{itemize}
\item 「$X$の左」「$X$の右」「$Y$の左」「$Y$の右」から相異なる$2$箇所を選び，$a,b$を一つずつ追加する．
\end{itemize}
\item $X$と$Y$を除去する．
\end{enumerate}
\end{problem}
\begin{example}
例えば，バランス語$abbaba$は次のように生成できる．
\[XY\to \underline{aXb}Y \to a\underline{bX}b\underline{Ya} \to abXb\underline{aYb}a\to abXbaYba \]
% abbaba\]
% \begin{enumerate}
% \item $XY$
% \begin{itemize}
% \item $XY\to \underline{aXb}Y$
% \item $aXbY \to a\underline{bX}b\underline{Ya}$
% \item $abXbYa \to abXb\underline{aYb}a$
% \item $abXbYa \to abXbaYba$
% \end{itemize}
% \end{enumerate}
\end{example}
この問題はまだ誰も(湯山さんも)解けていない．
\begin{remark}
数理空間トポス的には，この問題は以前の中村君の問題に類似している．中村君の問題は，(文脈自由文法を用いて書き直すと)次のようなものだった．
\begin{problem}[中村君のコネクトフォー数え上げ問題]
以下の操作を考える．
\begin{enumerate}
\item 文字列$X$を考える．
\item 次の操作を有限回繰り返す
\begin{itemize}
\item $X$を$abX,baX,aXb,bXa,Xab,Xba$のいずれかに置き換える．
\end{itemize}
\end{enumerate}
この操作で，得られる文字列について考察せよ．(特に，自然数$n$について，長さ$n$の文字列$w,v$で $wXv$と表せるものが何通り生成可能か数えよ．)
\end{problem}
バランス語の問題に似せるため，次の例題を考えてみよう．
\begin{problem}[バランス語問題の類題]\label{problem_easybalanced}
全てのバランス語は，以下の操作で生成できるか？
\begin{enumerate}
\item 文字列$X$を考える．
\item 次の操作を有限回繰り返す
\begin{itemize}
\item $X$を$abX,baX,aXb,bXa,Xab,Xba$のいずれかに置き換える．
\end{itemize}
\item $X$を除去する．
\end{enumerate}
\end{problem}
与えられたバランス語が上のルールで生成可能かどうかは，上の操作の逆再生を考えれば良い．バランス語に$X$を一つ挿入した語($abbaXab$など)が\demph{消去可能}とは，上の操作の逆再生で$X$のみにできることをいう．
問題は，「任意のバランス語に対して，適切に$X$を挿入すれば消去可能になるか？」と言い換えられる．
\begin{answer}[\cref{problem_easybalanced}の答え]
できない．
\end{answer}
\begin{proof}
最初の考察は，$X$の挿入位置の距離$2$の範囲に$a,b$の両方が登場する必要がある，ということである．このことは，最後の操作(逆再生の視点では最初の操作)を考えれば直ちにわかる．(例えば，$aaaabbXbb$は消去可能でない．)
私が最初に思いついた反例は$a^{100}b^{100}a^{10}b^{10}$であった．($10$はそこそこ大きい自然数であればなんでもよく，$100$はそれより十分大きい自然数であればなんでもいい．実際，$a^5b^5a^3b^3$でもギリギリいい．)
上記の距離$2$制約から，$X$の挿入位置は($a$の塊と$b$の塊の境目付近である必要があるので)
\begin{itemize}
\item 左から$100$番目あたり($a^{100}$と$b^{100}$の境目付近)か
\item 右端の高々$30$箇所($a^{10}$の両端付近)
\end{itemize}
のいずれかでなければならない．
$X$の挿入位置が左から$100$番目あたりであるとすると，最初の逆操作で必ず$a^{99}Xb^{99}a^{10}b^{10}$になる．その後$98$手で必ず$aXba^{10}b^{10}$となり，次の一手で$Xa^{10}b^{10}$か$aXa^9b^{10}$となる．ここでスタックする．
もし右端の高々$30$箇所あたりに$X$を挿入してしまうと，もっとあからさまに消去不可能である．実際，どのように逆操作を進めても，(右側の貴重な$a$を使い切ってしまうから)$10$回操作をしたところで$a^{100} b^{\text{$90$以上}}Xb^{\text{10以下}}$という形になってしまい，スタックしてしまう．
\end{proof}
chatGPTに聞いてみたところ，最小の反例は$aabbbbaa$だと言われた．(私は最小性はちゃんと示してないが)これも類似の方法でできない．$X$の挿入位置は，左右対称性より$aXabbbbaa, aaXbbbbaa, aabXbbbaa$のいずれかを考えればいいが，どれにしたところで$1$手で$aXbbbaa$になり，次に$Xbbaa$になりスタックする．
\end{remark}
\section{2025/08/24}
\subsection{三角形上のアリ問題}
\begin{problem}
一辺が$n$の正三角形を，一辺が$1$の正三角形に，\cref{fig:AntSeven}のように分割する．全ての$\frac{(n+1)(n+2)}{2}$個の頂点に，アリが1匹ずついる．アリが以下の条件を満たしながら動き続けられるような$n$を全て決定せよ．
\begin{itemize}
\item アリは，毎秒隣の頂点に移動する．
\item 複数のアリが同一頂点に来ることはない．
\item どのアリも，二秒間同じ方向に進むことはない．
\item どのアリも，直前にいた頂点に戻ることはない．
\end{itemize}
\end{problem}
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[scale=0.9]
%==== parameters ====
\def\n{8} % side length of the big equilateral triangle (integer >=1)
\def\h{0.866025403784} % = sqrt(3)/2
%---- boundary (draw thicker) ----
\draw[line width=1pt]
(0,0) -- (\n,0) -- (\n/2,\n*\h) -- cycle;
%---- three families of parallel lines (unit-triangle grid) ----
% horizontal
\foreach \j in {0,...,\n}{
\draw ( \j/2 , \j*\h ) -- ( \n - \j/2 , \j*\h );
}
% up-left
\foreach \i in {0,...,\n}{
\draw ( \i , 0 ) -- ( \i/2 , \i*\h );
}
% up-right
\foreach \k in {0,...,\n}{
\draw ( \k , 0 ) -- ( \n/2 + \k/2 , \n*\h - \k*\h );
}
%---- dots at all lattice vertices ----
\foreach \j in {0,...,\n}{
\foreach \i in {0,...,\numexpr\n-\j\relax}{
\fill (\i + \j/2, \j*\h) circle (1.4pt);
}
}
\end{tikzpicture}
\caption{The case of $n=7$}
\label{fig:AntSeven}
\end{figure}
例えば，$n=1$ (\cref{fig:AntOne})では，$3$匹のアリは常に時計回りに回り続けることができる．
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[scale=3]
%==== parameters ====
\def\n{1} % side length of the big equilateral triangle (integer >=1)
\def\h{0.866025403784} % = sqrt(3)/2
%---- boundary (draw thicker) ----
\draw[line width=1pt]
(0,0) -- (\n,0) -- (\n/2,\n*\h) -- cycle;
%---- three families of parallel lines (unit-triangle grid) ----
% horizontal
\foreach \j in {0,...,\n}{
\draw ( \j/2 , \j*\h ) -- ( \n - \j/2 , \j*\h );
}
% up-left
\foreach \i in {0,...,\n}{
\draw ( \i , 0 ) -- ( \i/2 , \i*\h );
}
% up-right
\foreach \k in {0,...,\n}{
\draw ( \k , 0 ) -- ( \n/2 + \k/2 , \n*\h - \k*\h );
}
%---- dots at all lattice vertices ----
\foreach \j in {0,...,\n}{
\foreach \i in {0,...,\numexpr\n-\j\relax}{
\fill (\i + \j/2, \j*\h) circle (1.4pt);
}
}
%==== clockwise rounded arrow inside ====
% center at centroid, radius scaled to n
\coordinate (C) at (\n/2, \n*\h/3);
\def\r{0.18*\n} % tweak this if you want a larger/smaller arrow
\draw[very thick, line cap=round, -{Latex[length=3.2mm]}]
(C) ++(0:\r) arc[start angle=0, end angle=-290, radius=\r]; % clockwise
\end{tikzpicture}
\caption{The case of $n=1$}
\label{fig:AntOne}
\end{figure}
一方，$n=2$では，辺に沿った全単射はそもそも時計回りと反時計回りしかない(\cref{fig:AntTwo})．したがって条件を満たしながら$2$ステップ移動することは不可能である．
\begin{figure}[htbp]
\centering
%==== clockwise version ====
\begin{subfigure}{0.45\textwidth}
\centering
\begin{tikzpicture}[scale=2.0]
%==== parameters ====
\def\n{2} % side length
\def\h{0.866025403784} % sqrt(3)/2
%---- boundary ----
\draw[line width=1pt]
(0,0) -- (\n,0) -- (\n/2,\n*\h) -- cycle;
%---- three families of parallel lines ----
% horizontal
\foreach \j in {0,...,\n}{
\draw ( \j/2 , \j*\h ) -- ( \n - \j/2 , \j*\h );
}
% up-left
\foreach \i in {0,...,\n}{
\draw ( \i , 0 ) -- ( \i/2 , \i*\h );
}
% up-right
\foreach \k in {0,...,\n}{
\draw ( \k , 0 ) -- ( \n/2 + \k/2 , \n*\h - \k*\h );
}
%---- dots ----
\foreach \j in {0,...,\n}{
\foreach \i in {0,...,\numexpr\n-\j\relax}{
\fill (\i + \j/2, \j*\h) circle (1.4pt);
}
}
%==== clockwise arrow ====
\coordinate (C) at (\n/2, \n*\h/3); % centroid
\def\r{0.25*\n} % radius
\draw[very thick, line cap=round, -{Latex[length=3mm]}]
(C) ++(0:\r) arc[start angle=0, end angle=-290, radius=\r];
\end{tikzpicture}
\caption{時計回り}
\end{subfigure}
\hfill
%==== counter-clockwise version ====
\begin{subfigure}{0.45\textwidth}
\centering
\begin{tikzpicture}[scale=2.0]
%==== parameters ====
\def\n{2}
\def\h{0.866025403784}
%---- boundary ----
\draw[line width=1pt]
(0,0) -- (\n,0) -- (\n/2,\n*\h) -- cycle;
%---- three families of parallel lines ----
% horizontal
\foreach \j in {0,...,\n}{
\draw ( \j/2 , \j*\h ) -- ( \n - \j/2 , \j*\h );
}
% up-left
\foreach \i in {0,...,\n}{
\draw ( \i , 0 ) -- ( \i/2 , \i*\h );
}
% up-right
\foreach \k in {0,...,\n}{
\draw ( \k , 0 ) -- ( \n/2 + \k/2 , \n*\h - \k*\h );
}
%---- dots ----
\foreach \j in {0,...,\n}{
\foreach \i in {0,...,\numexpr\n-\j\relax}{
\fill (\i + \j/2, \j*\h) circle (1.4pt);
}
}
%==== counter-clockwise arrow ====
\coordinate (C) at (\n/2, \n*\h/3);
\def\r{0.25*\n}
\draw[very thick, line cap=round, -{Latex[length=3mm]}]
(C) ++(0:\r) arc[start angle=0, end angle=290, radius=\r];
\end{tikzpicture}
\caption{反時計回り}
\end{subfigure}
\caption{The case of $n=2$: clockwise and counter-clockwise arrows}
\label{fig:AntTwo}
\end{figure}
% \begin{figure}[htbp]
% \centering
% \begin{tikzpicture}[scale=0.9]
% %==== parameters ====
% \def\n{2} % side length of the big equilateral triangle (integer >=1)
% \def\h{0.866025403784} % = sqrt(3)/2
% %---- boundary (draw thicker) ----
% \draw[line width=1pt]
% (0,0) -- (\n,0) -- (\n/2,\n*\h) -- cycle;
% %---- three families of parallel lines (unit-triangle grid) ----
% % horizontal
% \foreach \j in {0,...,\n}{
% \draw ( \j/2 , \j*\h ) -- ( \n - \j/2 , \j*\h );
% }
% % up-left
% \foreach \i in {0,...,\n}{
% \draw ( \i , 0 ) -- ( \i/2 , \i*\h );
% }
% % up-right
% \foreach \k in {0,...,\n}{
% \draw ( \k , 0 ) -- ( \n/2 + \k/2 , \n*\h - \k*\h );
% }
% %---- dots at all lattice vertices ----
% \foreach \j in {0,...,\n}{
% \foreach \i in {0,...,\numexpr\n-\j\relax}{
% \fill (\i + \j/2, \j*\h) circle (1.4pt);
% }
% }
% \end{tikzpicture}
% \caption{The case of $n=2$}
% \label{fig:AntTwo}
% \end{figure}
% 一般に，$n$で可能なら$n+2$でも可能である．なぜなら，
$n=3$の時は，可能である．実際，各アリは\cref{fig:AntThree}のように黒色に塗った部分を「左手に触りながら」移動すれば良い．
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[scale=0.9]
%==== parameters ====
\def\n{3}
\def\h{0.866025403784} % sqrt(3)/2
%---- boundary ----
\draw[line width=1pt]
(0,0) -- (\n,0) -- (\n/2,\n*\h) -- cycle;
%---- grid ----
\foreach \j in {0,...,\n}{
\draw ( \j/2 , \j*\h ) -- ( \n - \j/2 , \j*\h );
}
\foreach \i in {0,...,\n}{
\draw ( \i , 0 ) -- ( \i/2 , \i*\h );
}
\foreach \k in {0,...,\n}{
\draw ( \k , 0 ) -- ( \n/2 + \k/2 , \n*\h - \k*\h );
}
%---- dots ----
\foreach \j in {0,...,\n}{
\foreach \i in {0,...,\numexpr\n-\j\relax}{
\fill (\i + \j/2, \j*\h) circle (1.4pt);
}
}
%==== 塗りたい三角形のリスト ====
% 上向き三角形
\foreach \i/\j in {0/0, 2/0, 0/2} {
\fill[black!100]
(\i+\j/2, \j*\h) --
(\i+1+\j/2, \j*\h) --
(\i+0.5+\j/2, \j*\h+\h) -- cycle;
}
% 下向き三角形の例
\foreach \i/\j in {0/1} {
\fill[black!100]
(\i+\j/2, \j*\h) --
(\i+1+\j/2, \j*\h) --
(\i+0.5+\j/2, \j*\h-\h) -- cycle;
}
\end{tikzpicture}
\caption{A construction for $n=3$}
\label{fig:AntThree}
\end{figure}
一般に，$n$でできれば$n+2$でもできる．実際，$n=2$の場合を利用して，一番下の段に$n$個の菱形と$1$個の正三角形を置けばいい (cf. \cref{fig:AntFive})．
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[scale=0.9]
%==== parameters ====
\def\n{5}
\def\h{0.866025403784} % sqrt(3)/2
%---- boundary ----
\draw[line width=1pt]
(0,0) -- (\n,0) -- (\n/2,\n*\h) -- cycle;
%---- grid ----
\foreach \j in {0,...,\n}{
\draw ( \j/2 , \j*\h ) -- ( \n - \j/2 , \j*\h );
}
\foreach \i in {0,...,\n}{
\draw ( \i , 0 ) -- ( \i/2 , \i*\h );
}
\foreach \k in {0,...,\n}{
\draw ( \k , 0 ) -- ( \n/2 + \k/2 , \n*\h - \k*\h );
}
%---- dots ----
\foreach \j in {0,...,\n}{
\foreach \i in {0,...,\numexpr\n-\j\relax}{
\fill (\i + \j/2, \j*\h) circle (1.4pt);
}
}
%==== 塗りたい三角形のリスト ====
% 上向き三角形
\foreach \i/\j in {0/0, 2/0, 4/0, 0/2, 2/2, 0/4} {
\fill[black!100]
(\i+\j/2, \j*\h) --
(\i+1+\j/2, \j*\h) --
(\i+0.5+\j/2, \j*\h+\h) -- cycle;
}
% 下向き三角形の例
\foreach \i/\j in {0/1, 2/1, 0/3} {
\fill[black!100]
(\i+\j/2, \j*\h) --
(\i+1+\j/2, \j*\h) --
(\i+0.5+\j/2, \j*\h-\h) -- cycle;
}
\end{tikzpicture}
\caption{A construction for $n=5=3+2$}
\label{fig:AntFive}
\end{figure}
これまでの考察から，$n$が奇数の時は可能であることがわかった．偶数$n=2k$の場合はどうなるだろうか？$n=2k$の場合，全体の頂点の個数は$\frac{(2k+1)(2k+2)}{2} =(2k+1)(k+1)$個ある．一方で，\cref{fig:AntSix}の青色の頂点の個数は，$\frac{(k+1)(k+2)}{2}$個であり，全体の$\frac{k+2}{4k+2}$ほどの割合を占める．
一方で，ルールから各アリは青い頂点から別の青い頂点に移動するのに，最低でも$3$ステップかかる．従って，(例えば全てのアリが最初の$3$箇所で踏む頂点の色を考えることで)次の不等式
\[
\frac{k+2}{4k+2}\leq \frac{1}{3} \iff 3k+6 \leq 4k+2 \iff4\leq k
\]
が必要であることがわかる!!(賢い)特に，$n=2,4,6$では不可能なことがわかった！
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[scale=0.9]
%==== parameters ====
\def\n{6}
\def\h{0.866025403784} % sqrt(3)/2
%---- boundary ----
\draw[line width=1pt]
(0,0) -- (\n,0) -- (\n/2,\n*\h) -- cycle;
%---- grid ----
\foreach \j in {0,...,\n}{
\draw ( \j/2 , \j*\h ) -- ( \n - \j/2 , \j*\h );
}
\foreach \i in {0,...,\n}{
\draw ( \i , 0 ) -- ( \i/2 , \i*\h );
}
\foreach \k in {0,...,\n}{
\draw ( \k , 0 ) -- ( \n/2 + \k/2 , \n*\h - \k*\h );
}
%---- dots ----
\foreach \j in {0,...,\n}{
\foreach \i in {0,...,\numexpr\n-\j\relax}{
% 偶数判定：mod(\i,2)=0 かつ mod(\j,2)=0
\ifnum\numexpr\i-\i/2*2\relax=0
\ifnum\numexpr\j-\j/2*2\relax=0
\fill[blue] (\i + \j/2, \j*\h) circle (5pt); % 青で塗る
\else
\fill[black] (\i + \j/2, \j*\h) circle (1.4pt);
\fi
\else
\fill[black] (\i + \j/2, \j*\h) circle (1.4pt);
\fi
}
}
\end{tikzpicture}
\caption{The case of $n=6$, even-even vertices in blue}
\label{fig:AntSix}
\end{figure}
あとは，$8$以上の偶数が未知なわけだが，実は$n=8$が\cref{fig:AntEight}のように構成でき，従って$8$以上の偶数は全て可能なことがわかる．
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[scale=0.8]
%==== parameters ====
\def\n{8}
\def\h{0.866025403784} % sqrt(3)/2
%---- boundary ----
\draw[line width=1pt]
(0,0) -- (\n,0) -- (\n/2,\n*\h) -- cycle;
%---- grid ----
\foreach \j in {0,...,\n}{
\draw ( \j/2 , \j*\h ) -- ( \n - \j/2 , \j*\h );
}
\foreach \i in {0,...,\n}{
\draw ( \i , 0 ) -- ( \i/2 , \i*\h );
}
\foreach \k in {0,...,\n}{
\draw ( \k , 0 ) -- ( \n/2 + \k/2 , \n*\h - \k*\h );
}
% %---- dots ----
% \foreach \j in {0,...,\n}{
% \foreach \i in {0,...,\numexpr\n-\j\relax}{
% \fill (\i + \j/2, \j*\h) circle (1.4pt);
% }
% }
%---- dots ----
\foreach \j in {0,...,\n}{
\foreach \i in {0,...,\numexpr\n-\j\relax}{
% 偶数判定：mod(\i,2)=0 かつ mod(\j,2)=0
\ifnum\numexpr\i-\i/2*2\relax=0
\ifnum\numexpr\j-\j/2*2\relax=0
\fill[black] (\i + \j/2, \j*\h) circle (1.4pt); % 青で塗る
\else
\fill[black] (\i + \j/2, \j*\h) circle (1.4pt);
\fi
\else
\fill[black] (\i + \j/2, \j*\h) circle (1.4pt);
\fi
}
}
%==== 塗りたい三角形のリスト ====
% 上向き三角形
\foreach \i/\j in {0/0, 2/0, 4/0, 7/0, 2/2, 3/2, 5/2, 0/3, 2/3, 3/4, 0/5, 0/7} {
\fill[black!100]
(\i+\j/2, \j*\h) --
(\i+1+\j/2, \j*\h) --
(\i+0.5+\j/2, \j*\h+\h) -- cycle;
}
% 下向き三角形の例
\foreach \i/\j in {5/1,0/2, 2/2, 2/3, 3/3, 1/4, 1/6} {
\fill[black!100]
(\i+\j/2, \j*\h) --
(\i+1+\j/2, \j*\h) --
(\i+0.5+\j/2, \j*\h-\h) -- cycle;
}
\end{tikzpicture}
\caption{A symmetric construction for $n=8$}
\label{fig:AntEight}
\end{figure}
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[scale=0.8]
%==== parameters ====
\def\n{8}
\def\h{0.866025403784} % sqrt(3)/2
%---- boundary ----
\draw[line width=1pt]
(0,0) -- (\n,0) -- (\n/2,\n*\h) -- cycle;
%---- grid ----
\foreach \j in {0,...,\n}{
\draw ( \j/2 , \j*\h ) -- ( \n - \j/2 , \j*\h );
}
\foreach \i in {0,...,\n}{
\draw ( \i , 0 ) -- ( \i/2 , \i*\h );
}
\foreach \k in {0,...,\n}{
\draw ( \k , 0 ) -- ( \n/2 + \k/2 , \n*\h - \k*\h );
}
% %---- dots ----
% \foreach \j in {0,...,\n}{
% \foreach \i in {0,...,\numexpr\n-\j\relax}{
% \fill (\i + \j/2, \j*\h) circle (1.4pt);
% }
% }
%---- dots ----
\foreach \j in {0,...,\n}{
\foreach \i in {0,...,\numexpr\n-\j\relax}{
% 偶数判定：mod(\i,2)=0 かつ mod(\j,2)=0
\ifnum\numexpr\i-\i/2*2\relax=0
\ifnum\numexpr\j-\j/2*2\relax=0
\fill[black] (\i + \j/2, \j*\h) circle (1.4pt); % 青で塗る
\else
\fill[black] (\i + \j/2, \j*\h) circle (1.4pt);
\fi
\else
\fill[black] (\i + \j/2, \j*\h) circle (1.4pt);
\fi
}
}
%==== 塗りたい三角形のリスト ====
% 上向き三角形
\foreach \i/\j in {0/0, 2/0, 4/0, 7/0, 5/2, 0/3, 3/4, 0/5, 0/7} {
\fill[black!100]
(\i+\j/2, \j*\h) --
(\i+1+\j/2, \j*\h) --
(\i+0.5+\j/2, \j*\h+\h) -- cycle;
}
% 下向き三角形の例
\foreach \i/\j in {5/1,0/2, 2/2, 3/3, 1/4, 1/6} {
\fill[black!100]
(\i+\j/2, \j*\h) --
(\i+1+\j/2, \j*\h) --
(\i+0.5+\j/2, \j*\h-\h) -- cycle;
}
\end{tikzpicture}
\caption{Another symmetric construction for $n=8$}
\label{fig:AntEight2}
\end{figure}
\subsection{隣接平方根の和の冪乗}
\begin{problem}
正整数$m,k$に対して
$$
(\sqrt{m}+\sqrt{m+1})^k=\sqrt{n}+\sqrt{n+1}
$$
となる正整数$n$が存在することを示せ。
\end{problem}
\begin{answer}
左辺を二項展開する：
$$
(\sqrt{m}+\sqrt{m+1})^k=\sum_{i=0}^k\binom{k}{i}\sqrt{m^i(m+1)^{k-i}}.
$$
右辺の平方根の中身の非平方部分は$i$の偶奇のみで決まるので、正整数$A,B$を用いて
$$
\sum_{i\text{: odd}}\binom{k}{i}\sqrt{m^i(m+1)^{k-i}} = \sqrt{A},\quad \sum_{i\text{: even}}\binom{k}{i}\sqrt{m^i(m+1)^{k-i}} = \sqrt{B}
$$
と表せる。よって
\begin{align}\label{eq:sqrtsum}
(\sqrt{m}+\sqrt{m+1})^k=\sqrt{A}+\sqrt{B}
\end{align}
と表せる。あとは$B-A=1$を示せばよい。上と同様に二項展開を考えると
\begin{align}\label{eq:sqrtdiff}
(\sqrt{m+1}-\sqrt{m})^k = \sqrt{B}-\sqrt{A}
\end{align}
となる。\eqref{eq:sqrtsum}と\eqref{eq:sqrtdiff}の積を取ることで$B-A=1$が得られる。
\end{answer}
\section{2025/08/31}
\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}{[実際に遊べるボタン]}
\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. \Cref{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}
\href{redacted-overleaf-private-url}{[進展を書いたもの]}
% \begin{problem}[$2$次元の場合](同様に$d$次元もできるはず)
% $n,m$は$2$以上の整数とする．
% $n \times m$個のランプが長方形状に並んでいる．$n\times m$個のランプのうち一つを叩くと，そのランプとその隣のランプの明滅が逆転する．
% \begin{enumerate}
% \item どんな初期状態から始めても全てのライトを消せるような$n$を全て求めよ
% \item 初期状態が与えられたときに，全てのライトを消せるか判定する方法はあるか?
% \end{enumerate}
% \end{problem}
% \begin{answer}[Answer for 1.\footnote{答えを知るだけなら，$1$次元の場合の問題を操作空間$\to$状態空間の線型写像の同型性問題に帰着し，それらをテンソルすればわかる．}]
% 必ず揃えられることと，$n,m$がどちらも$3$で割って$2$余らないこと
% \[n,m\not\equiv 2\mod 3\]
% は同値である．
% 実際，$1$次元の場合と同様に$(1+n+1)\times (1+m+1)$に拡張して内部のマスしか押せないルールに帰着すると良い．内部しか押せない場合，全て消せるための必要十分条件は，全ての行と全ての列で$\F_4$不変量が$0$になることである．より厳密に言えば，「$i,j$成分に$\omega^{i+j}\in \F_4$を割り振ったとき，どの行とどの列を見ても点灯ランプにおける値の総和が$0$になっていること」と同値になっている．証明も$1$次元と同様である．必要性は，この量($\F_4^{\text{行数}+\text{列数}}$の元)が任意の(内部！)操作で不変になっていることからわかる．十分性は，貪欲に下$2$行と右$2$列に押し込むと不変量を見るだけで残りが自動的に$0$になってくれることからわかる．
% よって問題1は「任意に明滅状態$(a_{i,j}\in \F_2)_{0<i,j<n+1}$が与えられたときに，$n+2$行と$m+2$列全てで$\F_4$不変量が$0$になるような拡張$(a_{i,j}\in \F_2)_{0\leq i,j\leq n+1}$が存在するか」という問題に帰着できる．
% \end{answer}
\subsection{ルービックキューブの角}
\begin{problem}[渡邉倖成くんの問題]
ルービックキューブの$8$つの角を(違法に)回転させるとき，その回転角度の総和($\Z/3\Z$の元だと思える)が$0$であることと，ルービックキューブとして揃えられることは同値であることを示せ．
\end{problem}
\begin{proof}
ルービックキューブの$6$面のうち，向かい合う$2$面を選び，それらに属するような($\frac{1}{3}$サイズの)正方形$18$枚をA面と呼ぶことにする．(例えば，世界標準のルービックキューブでオレンジと赤の面をA面と呼べばいい．)
% A面に属するような(\frac{1}{3}サイズの)正方形は$18$個ある．
ルービックキューブの(違法かもしれない)状態$s$について，各頂点ごとに「(今A面がある場所)から(元々A面があった場所)に移すための回転の数$\in \Z/3\Z$」を足した量$i_s\in \Z_3\Z$を考える．この量は，合法な操作で変化しない．実際，元々A面があった場所を回しても，各頂点での値が変わらないし，そうでない$4$面のいずれかを回した場合は，頂点での値が$+1-1+1-1$となり打ち消し合う．
これで，$i_s=0 \in \Z/3\Z$は$s$からルービックキューブを揃えられるための必要条件であることがわかった．逆にこれが十分条件であることを示すには，隣り合う二つの頂点をそれぞれ時計回り，反時計回りに回した状態$s_0$を揃えられることを示せば十分である．なぜならどんな$i_s=0$からなる状態も，となりあう頂点を逆向きに回す操作の繰り返しで実現できるからである．$s_0$が揃えられることを示すには，実際にルービックキューブを用いて揃えてしまえばいい．
\end{proof}
\section{2025/09/13}
\subsection{下3桁の問題}
\begin{problem}
以下を満たすような$3$桁の自然数$???$を求めよ
\begin{itemize}
\item 任意の自然数$m$について，数列\[m,m^2,m^3,\dots\]の下$3$桁として
\begin{itemize}
\item $000$
\item $001$
\item $625$
\item $???$
\end{itemize}
のうちちょうど$1$つが現れる．
\end{itemize}
\end{problem}
つまり，任意の自然数を$4$つのグループに分けるというもの．例えば，$k=5$は
\[
5, 25, 125, 625, 3125, 15625, \dots
\]
なので「$625$が現れるグループ」に分類される．
背景は次の命題:
\begin{proposition}\label{prop:UniqueIdempotentPower}
任意の有限モノイド$M$とその元$m$について，その(正の)冪
\[
\{m^k\mid k>0\}
\]
の中には，ちょうど一つの冪等元が含まれる．
\end{proposition}
\begin{proof}
$M$が有限なので，鳩の巣論法から$M$の元の無限列
\[
m, m^2, m^3, \dots
\]
はいつか巡回し，
$m^{a+b}=m^a$
を満たす最小の$a\geq 0$, $b>0$が取れる．このとき，$b$の倍数であって$a$以上のものを適当に取り$B$とすると，$m^B$が唯一の冪等元である．
\end{proof}
\begin{answer}
\Cref{prop:UniqueIdempotentPower}を乗法モノイド$M=\Z/1000\Z$に適用する．$\Z/1000\Z$の冪等元は
\[
x^2\equiv x\mod 1000
\]
の解のことだから，中国式剰余定理$\Z/1000\Z \cong \Z/8\Z\times \Z/125\Z$より，以下の$4$つの元を考えればよくて，答えは$376$.
\begin{table}[ht]
\centering
\begin{tabular}{c|c|c}
${x \mod 1000}$& ${x \mod 8}$ & ${x \mod 125}$\\ \hline
000& 0 &0 \\ \hline
376& 0& 1\\ \hline
625& 1& 0\\ \hline
001& 1& 1\\ \hline
\end{tabular}
\end{table}
\end{answer}
今回は，$k^{100}$の下$3$桁を見ると本当に$000, 376, 625, 001$のどれかになる． (これ，$\Z_{10}\cong \Z_2\times \Z_5$でもいいけど，多分profinite rieg $\N_{\infty, 10^{\infty}}\cong \N \sqcup \Z_2\times \Z_5$における$k^{(0,0)}=\lim_{n\to \infty} k^{10^{n}}$の話なんだよな...すると指数部分の連続性を用いてformalに指数法則で冪等になるし，実際の構成ともあっている．)
\section{2025/09/27}
\subsection{整数部分の和の問題}
\begin{problem}[出題:神田]
以下の値を求めよ
\[
\sum_{k=1}^{100} \left(\left\lfloor{\frac{k^2}{100}}\right\rfloor+\left\lfloor{10\sqrt{k}}\right\rfloor \right )
\]
\end{problem}
\begin{answer}
$10000$個の格子点$\{(i,j)\}_{1\leq i,j\leq 100}$を考える．グラフ$y=\frac{x^2}{100}$の下(グラフ上の点を含む)にある格子点は
\[
\sum_{k=1}^{100} \left\lfloor{\frac{k^2}{100}}\right\rfloor
\]
個で，グラフの上(グラフ上の点を含む)にある格子点は
\[
\sum_{k=1}^{100} \left\lfloor{10\sqrt{k}}\right\rfloor
\]
個である．よって，求める値は$10000$にグラフ上の格子点の個数$10$を足した$10010$である．
\end{answer}
\section{2025/10/05}
\subsection{四元数群のガロア逆問題}
\begin{problem}
$K=\Q\left(\sqrt{(2+\sqrt{{2}})(3+\sqrt{3})}\right)$として，
$K/\Q$がガロア拡大であることを示し，そのガロア群を求めよ．
\end{problem}
\begin{answer}
一旦，$\Q(\sqrt{2}, \sqrt{3})/\Q$のガロア理論は認める．
\begin{description}
\item[Step 1:] \underline{$\Q(\sqrt{2}, \sqrt{3})\subset K$を示す．} $K\cap \Q(\sqrt{2}, \sqrt{3})$は拡大$\Q(\sqrt{2}, \sqrt{3})/\Q$の中間体である．また，ガロア群$\Gal(\Q(\sqrt{2}, \sqrt{3})/\Q)$のどの元でも固定されない元
$(2+\sqrt{{2}})(3+\sqrt{3})\in K\cap \Q(\sqrt{2}, \sqrt{3})$を含む．従って$K\cap \Q(\sqrt{2}, \sqrt{3})=K$となる．
\item[Step 2:] \underline{$K/\Q$が$2$次拡大であることを示す．} $(2+\sqrt{{2}})(3+\sqrt{3})$が$ \Q(\sqrt{2}, \sqrt{3})$の中で平方数でないことを示せば良い．拡大$ \Q(\sqrt{2}, \sqrt{3})/\Q(\sqrt{6})$でのノルムを見れば$\mathrm{N}_{ \Q(\sqrt{2}, \sqrt{3})/\Q(\sqrt{6})}((2+\sqrt{{2}})(3+\sqrt{3}))=(2+\sqrt{{2}})(3+\sqrt{3})(2-\sqrt{{2}})(3-\sqrt{3})=12$であり，$\sqrt{12}\notin\Q(\sqrt{6})$なのでok.
\item[Step 3:] \underline{$K/\Q$がガロア拡大であることを示す．} $\alpha\coloneqq \sqrt{(2+\sqrt{{2}})(3+\sqrt{3})}$と$\alpha'$が仮に$\Q$上共役なら，両辺を$2$乗した$(2+\sqrt{{2}})(3+\sqrt{3})=\alpha^2$と$\alpha'$も$\Q$上共役なので，
\begin{itemize}
\item $\alpha\coloneqq \sqrt{(2+\sqrt{{2}})(3+\sqrt{3})}$,
\item $\beta \coloneqq \sqrt{(2-\sqrt{{2}})(3+\sqrt{3})}$,
\item $\gamma\coloneqq \sqrt{(2+\sqrt{{2}})(3-\sqrt{3})}$,
\item $\delta\coloneqq \sqrt{(2-\sqrt{{2}})(3-\sqrt{3})}$,
\end{itemize}
とすると，$\pm \alpha, \pm \beta, \pm \gamma, \pm \delta \in K$を示せば良い．ここで，
\begin{itemize}
\item $\alpha\beta=\sqrt{2}(3+\sqrt{3})$
\item $\alpha\gamma = (2+\sqrt{{2}})\sqrt{6}$
\item $\alpha\delta = \beta\gamma = 2\sqrt{3}$
\end{itemize}
であるので，$\beta, \gamma, \delta$は$\Q(\sqrt{2}, \sqrt{3})$の元を$\alpha$で割った形をしており，Step 1より$\beta, \gamma, \delta\in K$.
\item[Step 4:] \underline{ガロア群を決定する} 以上の議論で，$K/\Q$が$8$次ガロア拡大であることはわかった．$\alpha$が単拡大としての生成元を与えているので，上記の$\pm \alpha, \pm \beta, \pm \gamma, \pm \delta \in K$が$\alpha$の$8$つの共役になり，$\alpha$をそれぞれに移すガロア群の元がただ一つ存在する．$\sigma\colon \alpha\mapsto \beta$，$\tau\colon \alpha \mapsto \gamma$となるような$\sigma, \tau\in \Gal(K/\Q)$をそれぞれとり，これらが非可換であることを示そう．関係式
\begin{itemize}
\item $\alpha\beta=\sqrt{2}(3+\sqrt{3}),\; \gamma\delta=\sqrt{2}(3-\sqrt{3})$,
\item $\alpha\gamma = (2+\sqrt{{2}})\sqrt{6},\; \beta\delta = (2-\sqrt{{2}})\sqrt{6}$,
\item $\alpha\delta = \beta\gamma = 2\sqrt{3}$
\end{itemize}
より$\tau(\sigma(\alpha))=\tau(\beta)=\delta$と$\sigma(\tau(\alpha))=\sigma(\gamma)=-\delta$となり\footnote{流石に雑すぎるか}，実際に$\tau \sigma \neq \sigma \tau$が確かめられた．非可換な元がある時点で$\Gal(K/\Q)$は$D_4$か$Q_8$であるが，$\sigma, \tau$のオーダーがどちらも$4$であることを確かめることができて，$D_4$の可能性が除かれる．(実際，$D_4$の位数$4$の元はちょうど$2$つでそれらは可換である．) よって，
\[
\Gal\left(\Q\left(\sqrt{(2+\sqrt{{2}})(3+\sqrt{3})}\right)/\Q\right)\cong Q_8
\]
を得る．
\end{description}
\end{answer}
\subsection{対称式で生成されるイデアル}
\begin{problem}
$\mathbb{Z}[x,y,z]$のイデアル$I=(x+y+z,xy+yz+zx,xyz)$に含まれない単項式の次数の最大値はいくつか？
\end{problem}
IMOのshortlistの問題らしい。
\begin{answer}
（さすがにオーバーキルかも）
$x,y,z$の$i$次基本対称式を$e_i$で表す。$B=\mathbb{Z}[x,y,z]$と定める。$B/I$において
$$
xy\equiv -yz-zx\equiv -z(x+y)\equiv z^2
$$
となるので
$$
z^3\equiv xyz\equiv 0,\quad x^2y^2\equiv z^4\equiv 0
$$
が得られる。$x,y,z$の$4$次以上の単項式は$x^3,y^3,z^3,x^2y^2,y^2z^2,z^2x^2,xyz$のいずれかで割り切れるので$I$に属することがわかる。
$x^2y\not \in I$を示そう。簡単な計算により、$B/I$において
$$
x^2y\equiv y^2z\equiv z^2x\equiv -xy^2\equiv-yz^2\equiv -zx^2
$$
となることがわかる。仮に$x^2y\in I$とすると$3$次単項式が全て$I$に属することになるので、$B/I$は$\mathbb{Z}$加群として$1,x,y,xy,yz$で生成されることになる。
よって、$B/I$が$\mathbb{Z}$加群として階数$6$の有限生成自由加群であることを示せば十分である。
$A=\mathbb{Z}[e_1,e_2,e_3]$とすると、以下の押出図式が存在する。
$$
\xymatrix{
A\ar[r]^-{e_i\mapsto 0}\ar[d]&\mathbb{Z}\ar[d]\\
B\ar[r]&B/I
}
$$
よって$B$が$A$加群として階数$6$の有限生成射影加群であることを示せばよい。
任意の$f\in B$に対し、$\sigma\in \mathfrak{S}_3$で変数を置換したものを$f^\sigma$で表すと
$$
\prod_{\sigma\in \mathfrak{S}_3}(X-f^\sigma)
$$
は$A$係数モニック多項式であって$f$を根に持つ。よって$B$は$A$上整である。$B$が$A$代数として有限生成であることと合わせると、$B$は$A$加群として有限生成であることがわかる。さらに$A$および$B$は正則なので、Miracle flatness theoremより$B$は$A$上平坦である。よって$B$は$A$加群として射影的であり、その階数は
$$
[\mathbb{Q}(x,y,z):\mathbb{Q}(e_1,e_2,e_3)]=6
$$
である。
\end{answer}
\subsection{\texorpdfstring{$C^\infty(\mathbb{R})$}{CinftyR}のテンソル積}
\begin{problem}[\href{https://mathoverflow.net/questions/501384/what-are-the-conditions-for-a-function-to-be-expressed-as-a-sum-of-multiplicativ}{MathOverflow}]\label{C_infty_tensor}
$\mathbb{R}^2$上の滑らかな関数$f$であって、$\mathbb{R}$上の滑らかな関数$g_i,h_i$を用いて
$$
f(x,y)=\sum_{i=1}^n g_i(x)h_i(y)
$$
と表せないものの例を挙げよ。
\end{problem}
つまり$C^\infty(\mathbb{R}^2)$の元であって$C^\infty(\mathbb{R})\otimes_\mathbb{R} C^\infty(\mathbb{R})$に属さないものを挙げよ、という問題である。
\begin{answer}
一般に$f\in C^\infty(\mathbb{R}^2)$および$a\in \mathbb{R}$に対して
$$
f_a:=f(a,{-})\in C^\infty(\mathbb{R})
$$
と定める。$f(x,y)=\sum_{i=1}^n g_i(x)h_i(y)$と表せるならば
$$
f_a=\sum_{i=1}^n g_i(a)h_i
$$
となるので、$f_a$は$h_1,\dots,h_n$の線型結合で表せる。特に$\{f_a\mid a\in \mathbb{R}\}$の張る$C^\infty(\mathbb{R})$の部分空間は有限次元である。
よってこれが無限次元になるような関数を挙げればよい。例えば$f(x,y)=e^{xy}$とすれば、$e^y,e^{2y},\dots$は線型独立なのでよい。
\end{answer}
代数的な類似として次のような問題も考えられる。
\begin{problem}
$2$変数の形式的冪級数$f\in\mathbb{R}[\![x,y]\!]$であって、$1$変数の形式的冪級数$g_i,h_i$を用いて
$$
f(x,y)=\sum_{i=1}^n g_i(x)h_i(y)
$$
と表せないものの例を挙げよ。
\end{problem}
つまり$\mathbb{R}[\![x,y]\!]$の元であって$\mathbb{R}[\![x]\!]\otimes_\mathbb{R} \mathbb{R}[\![y]\!]$に属さないものを挙げよ、という問題である。
\begin{answer}
自然な$\mathbb{R}$ベクトル空間の同型$\Map(\mathbb{N},\mathbb{R})\cong \mathbb{R}[\![x]\!]$および$\Map(\mathbb{N}^2,\mathbb{R})\cong \mathbb{R}[\![x,y]\!]$を通じて、自然な写像$\mathbb{R}[\![x]\!]\otimes_\mathbb{R}\mathbb{R}[\![y]\!]\to \mathbb{R}[\![x,y]\!]$は
$$
\Map(\mathbb{N},\mathbb{R})\otimes_\mathbb{R}\Map(\mathbb{N},\mathbb{R})\to \Map(\mathbb{N}^2,\mathbb{R});\quad f\otimes g\mapsto f(x)g(y)
$$
に対応する。よってこの問題はProblem \ref{C_infty_tensor}の$\mathbb{R}^2$を$\mathbb{N}^2$に置き換えたものと等価である。例えば$f(x,y)=\sum_{m,n=0}^\infty e^{mn}x^my^n$が例となる。
\end{answer}
\subsection{超立方体グラフのクーポン彩色}
グラフ$G$のクーポン彩色とは、$G$の頂点彩色であって以下を満たすものを指す：
\begin{itemize}
\item 任意の頂点に対し、その近傍（自分自身は除く）に全ての色が含まれる。
\end{itemize}
$G$が$m$色でクーポン彩色できるような最大の$m$を$G$のクーポン彩色数といい、$\chi_c(G)$で表す。クーポン彩色数はtotal domatic numberとも呼ばれている（こちらの方が文献は多い）。
\begin{problem}
$n$次元超立方体グラフ$Q_n$のクーポン彩色数はいくつか？
\end{problem}
これは完全には知られていないようである。$Q_n$の各頂点の次数は$n$なので、明らかに$\chi_c(Q_n)\leq n$である。
また$\chi_c(Q_n)\leq \chi_c(Q_{n+1})$である。
\begin{lemma}
$n$が$2$の冪のときは$\chi_c(Q_n)=n$.
\end{lemma}
\begin{proof}
本質的にはハミング符号と同じである。
$n=2^k$とすると、$Q_n$の頂点は$\mathbb{F}_2^k$の部分集合と対応する。
$S\subset\mathbb{F}_2^k$に対して「$S$の元の総和」を色として割り当ると、$n=2^k$色によるクーポン彩色が得られる。
\end{proof}
上の補題は次のような「コインのパズル」としてよく知られている。
\begin{screen}
囚人のアリスとボブが次のようなゲームを行う。まず看守がアリスに$1$以上$64$以下の整数$n$を告げる。アリスは$64$枚のコインが置かれた部屋に通される。コインの表裏はあらかじめ看守によって決められている。アリスは$64$枚のコインの中から$1$枚を選んで裏返す必要がある。アリスが部屋を出た後、ボブが部屋に入り、コインの状態を見て$n$を当てられれば二人は釈放される。二人はあらかじめ相談して作戦を立てることができるが、ゲーム中はコミュニケーションが禁止されている。確実に釈放されるためには、二人はどのような作戦を立てればよいか？
\end{screen}
コインの表裏の状態は$Q_{64}$の頂点と一対一に対応する。アリスがコインを$1$枚選んで裏返すことは、隣接する頂点にうつることに対応する。よって、二人であらかじめ$Q_{64}$の$64$色によるクーポン彩色を共有しておけば、頂点の色によって$n$を伝達できるわけである。
\begin{lemma}
$n$が$2$の冪でないときは$\chi_c(Q_n)<n$.
\end{lemma}
\begin{proof}
$Q_n$の$n$色によるクーポン彩色が存在するならば、各頂点の近傍には全ての色が$1$回ずつ現れる。するとどの色の頂点も同数ずつ存在しなければならないので$n\mid 2^n$となる。
\end{proof}
\href{https://link.springer.com/article/10.1007/s40840-023-01504-3}{Francis-Rajendraprasad (2023)}によれば、$n\leq 17$に対する$\chi_c(Q_n)$の値は以下のようになるらしい。
黒字は上の二つの補題からわかる。赤字は非自明な結果である。
\begin{table}[ht]
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline
$n$& $1$& $2$& $3$& $4$& $5$ &$6$& $7$& $8$& $9$&$10$&$11$&$12$&$13$&$14$&$15$&$16$&$17$\\ \hline
$\chi_c(Q_n)$& $1$& $2$& $2$& $4$& $4$ &{\color{red}$4$}& {\color{red}$5$}& $8$& $8$& {\color{red}$8$}&$8$-{\color{red}$9$}&$8$-$11$&$8$-{\color{red}$11$}&{\color{red}$10$}-$13$&{\color{red}$10$-$13$}&$16$&$16$\\ \hline
\end{tabular}
\end{table}
\begin{problem}
$\chi_c(6)=4$, $\chi_c(7)=5$を示す簡単な方法はないだろうか？
\end{problem}
\begin{problem}
$\chi_c(11)$は$8$か、それとも$9$か？
\end{problem}
\section{2025/10/19}
\subsection{位数\texorpdfstring{$12$}{12}の群の分類}
\begin{problem}
位数$12$の群を分類せよ
\end{problem}
% \begin{description}
% \item[可換なとき:] 分類定理より，$G\cong \Z/12\Z$か$G\cong \Z/2\Z\times \Z/6\Z$である．
% \item[非可換なとき:]
シローの定理より，シロー$3$部分群の個数$n_3$は$1$個か$4$個である．
\begin{description}
\item[(1) $n_3=4$のとき:] このとき，$G\cong A_4$であることを示そう．シロー$3$部分群を$T_1, T_2,T_3,T_4$とすると，これらに$G$が共役作用することで準同型
\[
\sigma\colon G \to S_4
\]
を得る．$\sigma$のKernelは正規化群を用いて$\ker\sigma=\cap_{i=1}^{4} N(T_i)$とかけるが，$\#G/N(T_i)$はシロー$3$部分群の個数である$4$と一致するはずなので，$\#N(T_i)=3$となり，従って$N(T_i)=T_i$が全ての$i=1,2,3,4$で成立する．よって，$\ker\sigma=\cap_{i=1}^{4} T_i$は($T_1\cong \Z/3\Z$の真部分群なので)自明群になり，$\sigma$は単射である．結果，$G$は$S_4$の部分群であって位数$12$なものと同型であり，それは$G\cong A_4$を意味する．
\item[(2) $n_3=1$のとき:] このとき，唯一のシロー$3$部分群$T$は$G$の正規部分群である．その剰余群$G/T$は位数$4$なので，$\Z/4\Z$か$\Z/2\Z\times \Z/2\Z$と同型である．
\begin{description}
\item[(2.1) $G/T\cong \Z/4\Z$のとき:]このとき，短完全列
\[
\begin{tikzcd}
0\ar[r]&T\ar[r, rightarrowtail]&G\ar[r,"p",twoheadrightarrow] &\Z/4\Z\ar[r]&0
\end{tikzcd}
\]
が分裂することを証明できる．(例えば，$p(x)=1$なる$x\in G$を取れば，$G$の位数は$4$か$12$である．前者なら$1\mapsto x$が，後者なら$1\mapsto x^9$が分裂$\Z/4\Z\to G$を与える．) よって，$G$は$T\cong\Z/3\Z$と$\Z/4\Z$の半直積である．$\Z/4\Z$の$\Z/3\Z$への作用は非自明なものが$1$つあり，$G\cong\Z/3\Z\times \Z/4\Z$か$G\cong \Z/3\Z\rtimes \Z/4\Z$となる．
\item[(2.2) $G/T\cong \Z/2\Z\times \Z/2\Z$のとき:] シローの定理より，シロー$2$部分群の個数$n_2$は$1$か$3$である．
\begin{description}
\item[(2.2.1) $n_2=1$のとき:] 唯一のシロー$2$部分群を$F$とすると， $G\cong G/T \times G/F\cong \Z/2\Z\times \Z/2\Z\times \Z/3\Z$となる．
\item[(2.2.2) $n_2=3$のとき:] このとき，$G\cong D_6$であることを示そう．我々の戦略は，各位数の元の個数を完全に特定することである．シロー$3$部分群は$1$つなので，位数$3$の元はちょうど$2$個ある．
\begin{table}[ht]
\centering
\begin{tabular}{c|c|c|c|c|c|c}
位数& 1& 2& 3& 4& 6& 12\\\hline
元の数& 1& ?& 2& ?& ?& ?\\
\end{tabular}
\end{table}
まず，$G/T\cong \Z/2\Z\times \Z/2\Z$という仮定から，$G$が位数$4$の元を持たないことがわかる．実際，$x\in G$の位数が$4$なら，$x^2\in T$となり矛盾する．
% したがって，$G$のシロー$2$部分群は全て$\Z/2\Z\times \Z/2\Z$と同型である．
\begin{table}[ht]
\centering
\begin{tabular}{c|c|c|c|c|c|c}
位数& 1& 2& 3& 4& 6& 12\\\hline
元の数& 1& ?& 2& 0& ?& 0\\
\end{tabular}
\end{table}
シロー$2$部分群を$F_1,F_2,F_3$とすると，これらに$G$が共役作用することで準同型
\[
\sigma\colon G \to S_3
\]
を得る．$\sigma$のKernelは正規化群を用いて$\ker\sigma=\cap_{i=1}^{3} N(F_i)$とかけるが，$\#G/N(F_i)$はシロー$2$部分群の個数である$3$と一致するはずなので，$\#N(F_i)=4$となり，従って$N(F_i)=F_i$が全ての$i=1,2,3$で成立する．元の個数を見れば$\sigma$は単射でないから，$\ker\sigma=\cap_{i=1}^{3} F_i$の位数は$2$以上であり，$\cap_{i=1}^{3} F_i$は各$F_i$の真部分群でもあるので，位数はちょうど$2$である．したがって，$F_1, F_2, F_3$は位数$2$の部分群を互いに共有している．ここまでの考察から，位数$2$の元は各$F_i$に$3$つずつあり，そのうち$1$つが共有されているので，ちょうど$7$つあることがわかる．
\begin{table}[ht]
\centering
\begin{tabular}{c|c|c|c|c|c|c}
位数& 1& 2& 3& 4& 6& 12\\\hline
元の数& 1& 7& 2& 0& 2& 0\\
\end{tabular}
\end{table}
これで，各位数の元の個数が完全に特定できた．位数$6$の元があるので，$G$は$\Z/6\Z$を部分群に含み，短完全列
\[
\begin{tikzcd}
0\ar[r]&\Z/6\Z\ar[r, rightarrowtail]&G\ar[r,twoheadrightarrow] &\Z/2\Z\ar[r]&0
\end{tikzcd}
\]
を得る．さらに，位数$2$の元が$7$つあるので，部分群$ \Z/6\Z\subset G$に含まれない$G$の元の位数は全て$2$であることまでわかる．従ってこの短完全列は分裂し，$G\cong D_6$となる．
\end{description}
\end{description}
\end{description}
% \end{description}
従って，位数$12$の群は
% $A_4, \Z/3\Z\times \Z/4\Z, \Z/3\Z\rtimes \Z/4\Z, \Z/2\Z\times \Z/2\Z \times \Z/3\Z, D_6$
\begin{itemize}
\item $A_4$,
\item $\Z/3\Z\times \Z/4\Z$,
\item $\Z/3\Z\rtimes \Z/4\Z$,
\item $\Z/2\Z\times \Z/2\Z \times \Z/3\Z$,
\item $D_6$
\end{itemize}
のいずれかと同型である．
\begin{question}
$\Z/3\Z\rtimes \Z/4\Z$に``自然な" (or 目にみえる) 解釈はあるだろうか？
\end{question}
多分これ$\langle \omega,j\rangle\subset\mathbb{H}^\times$だよね（見えないけど）
そうそうすぎる
てことは$\mathop{\mathrm{Spin}}(3)$に実現できるのか
\begin{answer}
$\mathbb{C}\times\mathbb{R}$の$6$元部分集合$X=\{1,\omega,\omega^2\}\times \{-1,1\}$を考える（正三角柱の頂点）。
ここには自然に
$$
\sigma\colon (z,t)\mapsto (\overline{z},-t),\quad \tau\colon (z,t)\mapsto (\omega z,t)
$$
で生成される二面体群$D_3\cong S_3\subset \mathop{\mathrm{SO}}(3)$が作用する。
これの$\mathop{\mathrm{Spin}}(3)$における逆像が$C_3\rtimes C_4$である。
無理やり幾何学的に解釈するなら、正三角形の持ち手を持つ吊り革の自己同型群だと思える（ベルトの捩れがスピンの情報を持っている）。ただし持ち手の平行移動は無視して考える。
\end{answer}
\begin{figure}
\centering
\missinggraphic{tsurikawa.jpg}{原画像未配置。正三角形の持ち手を持つ吊り革の図として後で差し替える。}
\end{figure}
\subsection{\texorpdfstring{$\phi$}{phi}進展開}
$\phi$を$x^2-x-1$の正の根（黄金数）とする。
\begin{problem}
任意の正整数$n$は相異なる整数$a_1,\dots,a_k$を用いて
$$
\phi^{a_1}+\cdots+\phi^{a_k}
$$
と表せることを示せ。
\end{problem}
例えば
$$
1=\phi^0,\quad 2=\phi^1+\phi^{-2},\quad 3=\phi^2+\phi^{-2}
$$
のようになる。
\begin{answer}
より強く、$a_1,\dots,a_k$であって$a_i+2\leq a_{i+1}$を満たすものを用いて$\phi^{a_1}+\cdots+\phi^{a_k}$と表せることを示す。
$n$についての帰納法。
$n=1$は明らか。
$n\geq 2$とする。
帰納法の仮定より、$a_1,\dots,a_k$であって$a_i+2\leq a_{i+1}$を満たすものを用いて
$$
n-1=\phi^{a_1}+\cdots+\phi^{a_k}
$$
と表せる。これに$1$を足して
$$
n=\phi^{a_1}+\cdots+\phi^{a_k}+1
$$
を得る。
この右辺を変形して所望の形に持っていく。以下のようなアルゴリズムに従う：
\begin{itemize}
\item 係数が$2$の項$2\phi^i$があるならば、それを$\phi^i+\phi^{i-1}+\phi^{i-2}$に置き換える。これを繰り返すといずれ全ての項の係数が$1$になる（証明略）。
\item その後、$\phi^i$と$\phi^{i-1}$が両方含まれるような$i$が存在するならば、そのような$i$のうち最大のものを取り、$\phi^i+\phi^{i-1}$を$\phi^{i+1}$に置き換える。$i$の最小性より、これによって係数が$2$の項が生じることはない。また項の個数が減っていくのでこの操作は止まる。
\end{itemize}
\end{answer}
\section{2025/11/08}
\subsection{All-Ones Problem}
\begin{problem}
任意有限グラフ上のLights outで，全点灯$\to$全消灯にできるか？
\end{problem}
\begin{answer}
できる．$\F_2$上の対称二次形式の話．\cite[Theorem 3.2]{sutner1989linear}
\end{answer}
\begin{problem}
$\mathrm{Aut}(Q_8)$を求めよ
\end{problem}
\begin{answer}
$\mathrm{Aut}(Q_8) \cong S_4$である．$\pm i, \pm j, \pm k$を$8$頂点とする正$8$面体に自然に作用している！
\end{answer}
\section{2025/11/16}
\subsection{7995001の素因数分解}
\begin{question}
$7995001$は素数$3$つの積である．何と何と何か？
\end{question}
\begin{answer}
まず，小さい方から素数で割ってみると，$7$で割れることがわかる．どうせ何かしらの因数分解公式に値を代入したものなので，
$7995001$が$200^3=8000000$に近いことから$3$次式の因数分解公式
\[
x^3+y^3+z^3-3xyz=(x+y+z)(x^2+y^2+z^2-xy-yz-zx)
\]
を連想する．
\[
\begin{cases}
x&=200\\
y&= 10\\
z&= 1
\end{cases}
\]
とすることで，
\[7995001=200^3+10^3+1^3-3\cdot 200\cdot 10\cdot1=(200+10+1)(200^2+10^2+1^2-200\cdot 10 -10\cdot 1 - 1\cdot 200),\]
つまり
% を得る．
$7995001=
% 211\times (40101-2210)=
211\times 37891=211\times (7\times 5413)$を得る．答えは$7, 211, 5413$.
\end{answer}
\section{2025/11/22}
\subsection{ノースコットのゲーム}
石取りゲームの数学4.1章から．実質Nim．
\subsection{1元生成Free Heyting algebra}
\cite{nishimura1960formulas}の話．
\section{2025/12/06}
\subsection{二項係数に関する等式}\label{ssec:BinomEqqAndNonIsomorphicSpecies}
\begin{question}
$n\geq 0$について，\[a_n\coloneqq \frac{\binom{2n}{n}}{4^n}\]とすると，\[\sum_{k=0}^na_k=(2n+1)a_n\]となることを示せ．
\end{question}
\begin{answer}[回答1: 帰納法で示す]
略
\end{answer}
\begin{answer}[回答2: 母関数で示す]
\[F(x)\coloneqq \frac{1}{\sqrt{1-x^2}}\]を
テイラー展開すると，一般化二項定理より
\[
F(x) = \sum_{n=0}^\infty a_{n}x^{2n}
\]
となる．
一方，$F$を微分することで
\[
F'(x)=\frac{x}{1-x^2}F(x)
\]
を得る．両辺の$2n-1$次の係数を比較すると
\[
2n\cdot a_n=\sum_{k=0}^{n-1} a_k
\]
を得て証明完了．
\end{answer}
\begin{answer}[回答3?]
$b_n=(2n)!\cdot a_n=((2n-1)!!)^2$と定めると，示すべき式は
$$
\dfrac{b_n}{(2n-1)!}=\sum_{k=0}^{n-1}\dfrac{b_k}{(2k)!}
$$
と表せる．実は$b_n$は$2n$元集合$\{1,2,\dots,2n\}$上の「すべてのサイクル長が偶数である置換」の個数に等しい.実際，以下のアルゴリズムで置換$\sigma$を構成すれば，$((2n-1)!!)^2$通りであることがわかる．
\begin{enumerate}
\item $3$変数$(x_0, x,S)$の初期値を$(1,1,\{1, 2,3,\dots , 2n\})$とする．
% \item $x=\min S$とする．
\item $S\leftarrow S\setminus \{x\}$とする．\#\#これが実行されるとき，必ず$x\in S$．
\item $\# S$の偶奇で場合わけする．
\begin{itemize}
\item $\#S$が奇数のとき，\underline{$y\in S$を一つ選び}，$\sigma(x)\coloneqq y$と定める．
\begin{itemize}
\item $x\leftarrow y$として$2$に戻る．
\end{itemize}
\item $\#S$が偶数のとき，\underline{$y\in S\sqcup \{x_0\}$を一つ選び}，$\sigma(x)\coloneqq y$と定める．
\begin{itemize}
\item $y\in S$のとき，$x\leftarrow y$として$2$に戻る．
\item $y=x_0$かつ$S\neq \emptyset$のとき，$x_0,x\leftarrow \min S$として$2$に戻る．
\item $y=x_0$かつ$S=\emptyset$のとき，終了する．
\end{itemize}
\end{itemize}
\end{enumerate}
このような置換のうち$1\in \{1,2,\dots,2n\}$を含むサイクルの長さが$2m$であるようなものの個数は
$$
(2n-1)(2n-2)\cdots (2n-2m+1)b_{n-m}=\dfrac{(2n-1)!}{(2n-2m)!}b_{n-m}
$$
なので
$$
b_n=\sum_{m=1}^n\dfrac{(2n-1)!}{(2n-2m)!}b_{n-m}
$$
となる．両辺を$(2n-1)!$で割れば目的の式が得られる．
\end{answer}
$b_n$は$2n$頂点完全グラフ上の完全マッチングを$2$つとる方法とも個数は同じなんだが，speciesとしては同型ではないことに気がついた．この非同型性，$D_{2n}$の指数$2$の部分群が複数あることに起因しているんだなあ
\section{2025/12/13}
\Cref{ssec:BinomEqqAndNonIsomorphicSpecies}の話
\subsection{群不変な部分環と整拡大}
\begin{problem}
有限群$G$が可換環$A$に作用しているとき，$A$はその不変部分環$A^G\subset A$上整拡大であることを示せ.
\end{problem}
\begin{proof}
任意の$a\in A$について，
\[
\prod_{g\in G} (x-g\cdot a)
\]
は$A^G$係数のモニック多項式であり，$a$はその根である．
\end{proof}
これの具体例を考えていた．特に，$\Z/n\Z$が$x_1, x_2, \dots, x_n $に巡回的に作用しているときに何になるかを話していた．榎本くん出題で，鈴木くん(ケンタ)と宮内くん(新しくきた)で考えていた．
\section{2025/12/21}
\subsection{随伴の分類}
\begin{question}
$\mathcal{E}=\mathbf{Set}, \mathbf{Cat}, \mathbf{Grp}, \mathbf{Poset}$について，$\mathcal{E}$と$\mathcal{E}$の間の随伴を決定せよ
\end{question}
$\mathbf{Set}$に関しては，左随伴の圏は$\mathbf{Set}$と同型．$\mathbf{Grp}$に関しては，左随伴の圏は$\mathbf{Grp}$-internal cogroupの圏と圏同値になるが，これは(集合上のcomonoidから来る)自由群上のcogroup structureしかなさそう. \url{https://pctseminar.github.io/Garner_12_12_25.pdf}がcontextにあって，左随伴の圏はuniversal enrichmentを与えている． $\mathbf{Cat}$の場合はまだ誰も綺麗には書いていないらしい．
\part{2026}
\section{2026/01/10}
\subsection{東工大入試の過去問}
\begin{question}
$n>0$個の正の実数$x_1, \dots, x_n$とその総和$k=x_1 + \dots+ x_n$について，次の不等式を示せ．
\[
\sum_{i=1}^n x_i \log x_i \geq k (\log k - \log n)
\]
\end{question}
% \begin{proof}
% 両辺を$nk$で割り，
% \[
% \sum_{i=1}^n \frac{x_i}{k} \log x_i \geq \log k - \log n
% \]
% さらに両辺から $\log k$を引くと，
% 示すべき式は
% \[
% \sum_{i=1}^n \frac{x_i}{k} \log \frac{x_i}{k} \leq - \log n
% \]
% となる．
% $y_i\coloneqq x_i/k$と書き換え，両辺を$n$で割れば，さらに
% \[
% \frac{1}{n}\sum_{i=1}^n y_i\log y_i \geq \frac{1}{n} \log \frac{1}{n}
% \]
% へと変形される．
% この不等式は，$f(x)= x \log x$という関数を用いて
% \[f(y_i)\text{の平均} \geq f(y_i\text{の平均})= f\left (\frac{1}{n}\right )\]
% と書けるが，$f$が下に凸なことから証明が終わる．
% \end{proof}
\begin{proof}
両辺を$n$で割ると，示すべき式は
\[
\frac{1}{n}\sum_{i=1}^n {x_i} \log x_i \geq \frac{k}{n}\log\left( \frac{k}{n}\right)
\]となる．
% さらに両辺から $\log k$を引くと，
% 示すべき式は
% \[
% \sum_{i=1}^n \frac{x_i}{k} \log \frac{x_i}{k} \leq - \log n
% \]
% となる．
% $y_i\coloneqq x_i/k$と書き換え，両辺を$n$で割れば，さらに
% \[
% \frac{1}{n}\sum_{i=1}^n y_i\log y_i \geq \frac{1}{n} \log \frac{1}{n}
% \]
% へと変形される．
この不等式は，$f(x)= x \log x$という関数を用いて
\[f(x_i)\text{の平均} \geq f(x_i\text{の平均})\]
と書けるが，これは$f$が下に凸なことから従う．
\end{proof}
\subsection{六角形の問題}
\begin{question}
正六角形内に点をおき，$6$つの頂点と線分で結んだところ，図 \Cref{fig:HexDec}のようになった．面積$A,B,C$を求めよ．
\end{question}
\begin{figure}[ht]
\centering
\begin{tikzpicture}[scale=2]
% 六角形の頂点（正六角形）
\coordinate (V1) at (90:1);
\coordinate (V2) at (30:1);
\coordinate (V3) at (-30:1);
\coordinate (V4) at (-90:1);
\coordinate (V5) at (-150:1);
\coordinate (V6) at (150:1);
% 擬似的な分点（真の中心ではない）
\coordinate (O) at (-0.08,-0.10);
% 外側の正六角形
\draw[line width=1.2pt]
(V1)--(V2)--(V3)--(V4)--(V5)--(V6)--cycle;
% 中心から各頂点への分割線
\foreach \v in {V1,V2,V3,V4,V5,V6} {
\draw[line width=1pt] (O)--(\v);
}
% 各三角形の重心付近にラベル
\node at ($(O)!0.5!(V6)!0.33!(V1)$) {$11$};
\node at ($(O)!0.5!(V5)!0.33!(V6)$) {$9$};
\node at ($(O)!0.5!(V4)!0.33!(V5)$) {$8$};
\node at ($(O)!0.5!(V1)!0.33!(V2)$) {$A$};
\node at ($(O)!0.5!(V2)!0.33!(V3)$) {$B$};
\node at ($(O)!0.5!(V3)!0.33!(V4)$) {$C$};
\end{tikzpicture}
\caption{六角形の分割}
\label{fig:HexDec}
\end{figure}
\begin{answer}[神田の想定解]
与えられた正六角形と同じ辺長の正三角形の面積を$T$とする．このとき，図\Cref{fig:HexDecExt}の右側に着目すると，
\[
A+C=B+T
\]
がわかる．
\begin{figure}[ht]
\centering
\begin{tikzpicture}[scale=2]
% 六角形の頂点（正六角形）
\coordinate (V1) at (90:1);
\coordinate (V2) at (30:1);
\coordinate (V3) at (-30:1);
\coordinate (V4) at (-90:1);
\coordinate (V5) at (-150:1);
\coordinate (V6) at (150:1);
% 擬似的な分点（真の中心ではない）
\coordinate (O) at (-0.08,-0.10);
%右の点
\coordinate (R) at (1.732,0);
\draw[line width = 1.2pt] (V1) -- (R) -- (V4);
% 外側の正六角形
\draw[line width=1.2pt]
(V1)--(V2)--(V3)--(V4)--(V5)--(V6)--cycle;
% 中心から各頂点への分割線
\foreach \v in {V1,V2,V3,V4,V5,V6} {
\draw[line width=1pt] (O)--(\v);
}
\draw[line width = 0.3pt, dashed] (O) --(R);
% 各三角形の重心付近にラベル
\node at ($(O)!0.5!(V6)!0.33!(V1)$) {$11$};
\node at ($(O)!0.5!(V5)!0.33!(V6)$) {$9$};
\node at ($(O)!0.5!(V4)!0.33!(V5)$) {$8$};
\node at ($(O)!0.5!(V1)!0.33!(V2)$) {$A$};
\node at ($(O)!0.5!(V2)!0.33!(V3)$) {$B$};
\node at ($(O)!0.5!(V3)!0.33!(V4)$) {$C$};
\node at ($(R)!0.5!(V2)!0.33!(V3)$) {$T$};
\end{tikzpicture}
\caption{六角形の分割を拡張}
\label{fig:HexDecExt}
\end{figure}
同様にして，
\begin{align*}
A+C&=B+T\\
B+8&=C+T\\
C+9&=8+T\\
8+11&=9+T\\
9+A&=11+T\\
11+B&=A+T
\end{align*}
がわかる．すると，$(A,B,C,T)=(12,11,9,10)$となるしかない．
\end{answer}
正$n$角形でも同じことができる.
正$n$角形$X_1 X_2 \ldots X_n$とその内部の点$P$について,
$S_n \coloneqq \lvert X_i X_{i+1}P \rvert =(\text{三角形$X_i X_{i+1}P$の面積})$
としたとき, 図\Cref{fig:nDecExt}より常に
\[
\frac{\lvert X_{i+1} Q \rvert}{\lvert X_i X_{i+1} \rvert}(S_i+S_{i+2})-S_{i+1}
=\lvert X_{i+1}X_{i+2}Q\rvert
\]
が成立. ここで$Q$は$X_iX_{i+1}$と$X_{i+2}X_{i+3}$の交点. この式を具体的に計算すると
\[
\frac{1}{2\cos{\frac{2\pi}{n}}}\left( S_i + S_{i+2}\right)-S_{i+1}
= \frac{1}{2}\left( \frac{\sin{\frac{\pi}{n}}}{\cos{\frac{2\pi}{n}}} \right)^2
\sin{\frac{4\pi}{n}}
\]
が成立する. ただし添え字$i$は$\mod{n}$で見る.
\begin{figure}[ht]
\centering
\begin{tikzpicture}[scale=1, line cap=round, line join=round]
% --- coordinates (adjust freely) ---
\coordinate (L) at (-3,0); % i+3 (left top)
\coordinate (R) at ( 3,0); % i (right top)
\coordinate (Lb) at (-3.5,-1.2); % left foot
\coordinate (Rb) at ( 3.5,-1.2); % right foot
\coordinate (Q) at (0,2); % apex
\coordinate (U) at (-1.2,1.2); % i+2 on left slope
\coordinate (V) at ( 1.2,1.2); % i+1 on right slope
\coordinate (P) at (-1.6,-1.2);% point P on base
% --- outer frame ---
\draw[line width=1.1pt] (L)--(Q)--(R);
\draw[line width=1.1pt] (L)--(Lb);
\draw[line width=1.1pt] (R)--(Rb);
% --- inner segments ---
\draw[line width=1pt] (U)--(V); % top horizontal
\draw[line width=1pt] (U)--(P); % down to P
\draw[line width=1pt] (P)--(Q); % diagonal to Q
\draw[line width=1pt] (P)--(V); % diagonal to V
\draw[line width=1pt] (P)--(L);
\draw[line width=1pt] (P)--(R);
% --- points ---
\fill (P) circle (1.2pt);
% --- labels ---
\node[above] at (Q) {$Q$};
\node[below] at (P) {$P$};
\node[left] at (L) {$X_{i+3}$};
\node[left=3pt] at (U) {$X_{i+2}$};
\node[right=3pt] at (V) {$X_{i+1}$};
\node[right] at (R) {$X_i$};
\end{tikzpicture}
\caption{$n$角形の分割の拡張}
\label{fig:nDecExt}
\end{figure}
つまり, 正$n$角形を点$P$によって$n$個の三角形に分割したとき,
隣り合う$3$つの三角形の面積がわかると全ての三角形の面積がわかる.
$n$を無限大にすると先の線形関係式は$2$階の微分方程式になる.
以下の問題でそれを解説する.
\begin{question}
単位円$C$とその内部の点$P$を考える.
円周上の点$X$に対し実数$F(X)$を$X$における$C$の接線と$P$の距離と定める.
このとき
\[
F''=1-F
\]
が成立することを示せ.
ただし$F$の変数は$X$の$C$における中心角でパラメトライズされ,
$2\pi$周期の$\R$上の関数とみなす.
\end{question}
\begin{answer}
$0 < \theta <2\pi$に対し$X_{\theta}$を,
円周$C$を$X$から半時計周りに中心角$\theta$進んだ点とする.
また$f_{\theta}(X) \coloneqq \lvert XX_{\theta}P \rvert$とする.
このとき$F$は
\[
F(X) = \lim_{\theta \to 0} \frac{2f_{\theta}(X)}{\theta}
\]
となる. 実際図\Cref{fig:VertFromP}を見ると
\[
\lim_{\theta \to 0} \frac{2f_{\theta}(X)}{\theta}=
\lim_{\theta \to 0} \frac{2}{\theta} \cdot \frac{1}{2} \cdot
\lvert XX_{\theta}\rvert \cdot\lvert PH_{X,\theta}\rvert=
\lim_{\theta \to 0} \frac{\lvert XX_{\theta}\rvert}{\theta} \cdot
\lvert PH_{X,\theta}\rvert
=\lvert PH_X \rvert=F(X)
\]
である.
\begin{figure}[ht]
\centering
\begin{tikzpicture}[scale=1]
% --- points (手置き) ---
\coordinate (X) at (0,0);
\coordinate (C) at (0,2); % 中心（ラベルは付けない）
\coordinate (H) at (1.5,0);
\coordinate (P) at (1.5,2.7);
\coordinate (R) at (2.035,0.6105);
\coordinate (Q) at (1.10,0.33); % 斜め線と円の交点（手置き）
% --- ground line (finite) ---
\draw (-2,0) -- (5,0);
% --- circle and radius OX (Oは書かない) ---
\draw (C) circle (2);
\draw (X) -- (C);
% --- slanted segment XR ---
\draw (X) -- (R);
% --- four segments from P ---
\draw (P) -- (X);
\draw (P) -- (Q);
\draw (P) -- (R);
\draw (P) -- (H);
% --- right angle marks ---
\draw pic[draw,angle radius=7pt] {right angle = X--H--P};
\draw pic[draw,angle radius=7pt] {right angle = X--R--P};
% --- dots ---
\fill (X) circle (1.3pt);
\fill (C) circle (1.3pt);
\fill (P) circle (1.3pt);
\fill (Q) circle (1.3pt);
\fill (R) circle (1.3pt);
\fill (H) circle (1.3pt);
% --- labels ---
\node[below] at (X) {$X$};
\node[below] at (H) {$H_X$};
\node[above] at (P) {$P$};
\node[above left] at (Q) {$X_{\theta}$};
\node[below right] at (R) {$H_{X,\theta}$};
\end{tikzpicture}
\caption{Pから各直線へ垂線をおろす}
\label{fig:VertFromP}
\end{figure}
さて, 正$n$角形のときに得られた線形関係式を今回の場合に一般化しておく.
今回の$\theta$は正$n$角形のときの$2\pi/n$に対応する.
正$n$角形のときと全く同様の計算により
\[
\frac{1}{2\cos{\theta}}\left( f_{\theta}(X-\theta) + f_{\theta}(X+\theta)\right)
-f_{\theta}(X)
= \frac{1}{2}\left( \frac{\sin{\frac{\theta}{2}}}{\cos{\theta}} \right)^2
\sin{2\theta}
\]
となる. 整理すると
\[
f_{\theta}(X-\theta) + f_{\theta}(X+\theta)
-2\cos{\theta} \cdot f_{\theta}(X)
= \frac{1}{\cos{\theta}} \cdot
\left( \sin{\frac{\theta}{2}} \right)^2 \cdot\sin{2\theta}
\]
となる. これを用いて$F''$を計算していく.
\begin{align*}
F''(X) &= \lim_{h \to 0} \frac{1}{h^2} \left( F(X-h)+F(X+h)-2F(X)\right)\\
&= \lim_{h \to 0} \lim_{\theta \to 0} \frac{1}{h^2}
\left( \frac{2f_{\theta}(X-h)}{\theta}+\frac{2f_{\theta}(X+h)}{\theta}-
2\cdot\frac{2f_{\theta}(X)}{\theta} \right)\\
&= \lim_{\theta \to 0} \frac{2}{\theta^3}
\left( f_{\theta}(X-\theta) + f_{\theta}(X+\theta)-2f_{\theta}(X) \right)\\
&= \lim_{\theta \to 0} \frac{2}{\theta^3}
\left( f_{\theta}(X-\theta) + f_{\theta}(X+\theta)-
2\cos{\theta}\cdot f_{\theta}(X) - 2\left( 1-\cos{\theta}\right) f_{\theta}(X) \right) \\
&= \lim_{\theta \to 0} \frac{2}{\theta^3}
\left( \frac{1}{\cos{\theta}} \cdot
\left( \sin{\frac{\theta}{2}} \right)^2 \cdot\sin{2\theta} - 2\left( 1-\cos{\theta}\right) f_{\theta}(X) \right) \\
&= \lim_{\theta \to 0}
\left( \frac{1}{\cos{\theta}} \cdot
\left( \frac{2}{\theta}\sin{\frac{\theta}{2}} \right)^2 \cdot
\frac{\sin{2\theta}}{2\theta} -
\frac{2(1-\cos{\theta})}{\theta^2} \cdot \frac{2f_{\theta}(X)}{\theta} \right) \\
&=1-F(X).
\end{align*}
よって示された.
途中で$\lim$を$\theta=h$として考えるという雑な扱いをしているが,
$X$を固定して$f_{\theta}(X-h) + f_{\theta}(X+h)-2f_{\theta}(X)$
を$h$と$\theta$の$2$変数関数と考えると,
これは原点近傍で解析的なので問題ない.
\end{answer}
\begin{answer}[直接解く]
もちろん正$n$角形の極限などとらなくても高校数学で直接解ける.
$P,X$の座標を$(a,b),(\cos{\theta},\sin{\theta})$とすれば$X$における単位円の接線は
\[
\cos{\theta} \cdot x + \sin{\theta} \cdot y =1
\]
なのでこれと$P$との距離は
\[
F(X)=1-(a\cos{\theta}+b\sin{\theta})
\]
となり, 微分すると
\begin{align*}
F'(X) &= a\sin{\theta}-b\cos{\theta}, \\
F''(X) &= a\cos{\theta}+b\sin{\theta}
\end{align*}
となるので, 確かに$F''=1-F$を満たす.
\end{answer}
ちなみに$F$をフーリエ級数展開することで,
この微分方程式をみたす$F$は実数$(a,b)$を用いて
$F(X)=1-(a\cos{\theta}+b\sin{\theta})$
とかけるもの全体であることがわかる.
つまり点$P$を円周の内部に限定せず任意の点とし,
接線との符号付き距離をとることで,
上記の微分方程式をみたすような$F$はいつでも$X$での接線と$P$との距離として実現できることがわかる.
\section{2027/01/17}
\subsection{一般化四元数群}
\begin{question}
次の群の位数を求めよ
\[
G=\langle a,b \mid a^4=b^2=abab\rangle
\]
\end{question}
\begin{answer}
$b^2 = abab$を$ba^{-1}=ab$と書き直すことで，$b^4=a^4b^2=ba^{-4} b = e$となる．よって$a^8=e$もわかる．全ての元は$b^i a^j$ ($0\leq i < 2$, $0\leq j< 8$)のいずれかと等しいので，$G$の位数は$16$以下．
群$G$は，16元集合$\Z/8\Z \times \{\pm 1\}$に
\[
\begin{tikzcd}
(x,u)\ar[r, mapsto,"a"] & (x+u, u)\\
(x,u)\ar[r, mapsto,"b"] & (x+2, -u)
\end{tikzcd}
\]
でtransitiveに作用するので，位数$16$以上である．実際，$a^4,b^2,abab$の作用は全て$(x,u)\mapsto (x+4,u)$になる．
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[
scale=1.2,
every node/.style={circle, fill=black, inner sep=1.4pt},
bluearr/.style={->, very thick, blue!70},
redarr/.style={->, very thick, red!60},
lab/.style={fill=none, inner sep=0pt, font=\small}
]
% nodes: (x,+) on top row, (x,-) on bottom row
\foreach \x in {0,...,7}{
\node (T\x) at (\x,1) {};
\node (B\x) at (\x,0) {};
}
% labels for rows / generators
\node[lab] at (-0.7,1) {$u=+1$};
\node[lab] at (-0.7,0) {$u=-1$};
\node[lab, blue!70] at (0.2,1.35) {$a$};
\node[lab, blue!70] at (0.2,-0.35) {$a$};
\node[lab, red!60] at (-0.3,0.5) {$b$};
% a-action: (x,u) -> (x+u,u)
% top row: u=+1 : x -> x+1 (to the right)
\foreach \x in {0,...,7}{
\pgfmathtruncatemacro{\y}{mod(\x+1,8)}
\draw[bluearr] (T\x) -- (T\y);
}
% bottom row: u=-1 : x -> x-1 (to the left)
\foreach \x in {0,...,7}{
\pgfmathtruncatemacro{\y}{mod(\x+7,8)} % x-1 mod 8
\draw[bluearr] (B\x) -- (B\y);
}
% b-action: (x,u) -> (x+2,-u)
% top -> bottom, and bottom -> top (both shift by +2)
\foreach \x in {0,...,7}{
\pgfmathtruncatemacro{\y}{mod(\x+2,8)}
\draw[redarr] (T\x) -- (B\y);
\draw[redarr] (B\x) -- (T\y);
}
\end{tikzpicture}
\caption{Action of $G=\langle a,b \mid a^4=b^2=abab\rangle$ on $\mathbb{Z}/8\mathbb{Z}\times\{\pm1\}$ }
\end{figure}
\end{answer}
これは一般化四元数群と呼ばれる群．
\section{2026/01/24}
\subsection{パウリ群}
\begin{question}\label{que:Pauli}
行列
\[
X=\begin{pmatrix}
0&1\\
1&0
\end{pmatrix},
Y=\begin{pmatrix}
0&-i\\
i&0
\end{pmatrix},
Z=\begin{pmatrix}
1&0\\
0&-1
\end{pmatrix}
\]
で生成される$\mathrm{GL}_2(\C)$の部分群の位数を求めよ
\end{question}
\begin{answer}
まず，$\Z[i]$係数のユニタリ行列は
\[
\begin{pmatrix}
\Z[i]^\times&0\\
0&\Z[i]^\times
\end{pmatrix},
\begin{pmatrix}
0& \Z[i]^\times\\
\Z[i]^\times &0
\end{pmatrix}
\]
のいずれかの形をしているしかないので，全部で$32$通りある．そのうち，行列式が実数であるものは$X,Y,Z$を含む$16$個である．あとは$16$個あること($9$個以上あること)をcheckすればいい．
\end{answer}
\begin{question}[神尾]
行列
\[
A=\frac{1}{\sqrt{2}}
\begin{pmatrix}
1&1\\
1&-1
\end{pmatrix},
B=\begin{pmatrix}
1&0\\
0&i
\end{pmatrix}
\]
で生成される$\mathrm{GL}_2(\C)$の部分群$G$の位数を求めよ
\end{question}
% こっちは多分(神尾以外)まだ解けていない．
% Internal memo moved to memo-20260124-01
\begin{answer}[洞とAIと石毛さんと高梨さんの雑談結果]
$A,B$による共役作用は$6$元集合$\{\pm X,\pm Y,\pm Z\}$を保つ (cf. \Cref{que:Pauli})．さらにそれぞれ正八面体 (\Cref{fig:PauliHachimentai})への
\begin{itemize}
\item $A$の共役作用：$X+Z$軸を中心とする$\frac{1}{2}$回転 ($(X,Z)(-X,-Z)(Y,-Y)$)
\item $B$の共役作用：$Z$軸を中心とする$\frac{1}{4}$回転 ($(X, -Y, -X,Y)$)
\end{itemize}
になっており，これは正八面体群$\cong S_4$を生成するので全射準同型$\phi \colon G \twoheadrightarrow S_4$を得る．
% \[
% \begin{tikzcd}
% X\ar[r, red, "S"]\ar[rr,blue, "H", leftrightarrow, bend left]& Y \ar[r, red, "S"]\ar[d,blue, "H", leftrightarrow]& Z\ar[r, red, "S"]\\
% X\ar[r, red, "S"]\ar[rr,blue, "H"', leftrightarrow, bend right]& Y \ar[r, red, "S"]\ar[r,blue, "H"]& Z\ar[r, red, "S"]\ar[r,blue, "H"]
% \end{tikzcd}
% \]
\begin{figure}[ht]
\centering
\begin{tikzpicture}[scale=2.2,
x={(1cm,-0.25cm)},
y={(0.7cm,0.45cm)},
z={(0cm,1cm)}]
% style for octahedron edges
\tikzset{octedge/.style={draw=black, line width=0.9pt}}
% axes
\draw[->] (-1.5,0,0) -- (1.5,0,0) node[below] {};
\draw[->] (0,-1.5,0) -- (0,1.5,0) node[left] {};
\draw[->] (0,0,-1.5) -- (0,0,1.5) node[right] {};
% vertices
\coordinate (Xp) at (1,0,0);
\coordinate (Xm) at (-1,0,0);
\coordinate (Yp) at (0,1,0);
\coordinate (Ym) at (0,-1,0);
\coordinate (Zp) at (0,0,1);
\coordinate (Zm) at (0,0,-1);
% edges (thicker & darker)
\foreach \A in {Xp,Xm,Yp,Ym}{
\draw[octedge] (Zp)--(\A);
\draw[octedge] (Zm)--(\A);
}
\draw[octedge] (Xp)--(Yp)--(Xm)--(Ym)--cycle;
\draw[octedge, dashed] (Xp)--(Ym);
\draw[octedge, dashed] (Xm)--(Yp);
% points
\foreach \P in {Xp,Xm,Yp,Ym,Zp,Zm}{
\fill (\P) circle (0.5pt);
}
% vertex labels
\node[font=\small, above right] at (Xp) {$X$};
\node[font=\small, below left] at (Xm) {$-X$};
\node[font=\small, above] at (Yp) {$Y$};
\node[font=\small, left] at (Ym) {$-Y$};
\node[font=\small, above right] at (Zp) {$Z$};
\node[font=\small, below left] at (Zm) {$-Z$};
\end{tikzpicture}
\caption{\texorpdfstring{$\pm$}{pm}パウリ行列のなす正八面体}
\label{fig:PauliHachimentai}
\end{figure}
残りの部分で，
\[
\ker \phi = \{\zeta_8^k I\mid k\in \Z/8\Z\}
\]
を示す．
まず，$M_{2\times 2}(\C)$は$\C$線型空間として$\langle I, X, Y,Z\rangle$で生成できるので，
$\ker \phi$の元
% $M \in G \subset M_{2\times 2}(\C)$
は$M_{2\times 2}(\C)$の中心に入っており，従ってスカラー行列$\alpha I$である．さらに，その行列式$\det (\alpha I) = \alpha ^2$は$\{\pm 1, \pm i\} = \langle \det A, \det B\rangle \subset \C^{\times}$に入っているので，$\alpha $は$\zeta_8^k$の形をしている．逆の包含は$\zeta_8 I = (AB)^3\in G$からわかる．
結果，完全列
\[
\begin{tikzcd}
1 \ar[r] &\Z/8\Z\ar[r, rightarrowtail]&G\ar[r, "\phi", twoheadrightarrow]&S_4 \ar[r]&1\text{: exact}
\end{tikzcd}
\]
を得るので，$\abs{G}=8\times 24 = 192$である．
\end{answer}
\begin{answer}[たぶん]
$\mathbb{C}^2\cong\mathbb{R}^4;\ (z,w)\mapsto (\Re z,\Re w,\Im z, \Im w)$により$\mathrm{GL}_2(\mathbb{C})\subset \mathrm{GL}_4(\mathbb{R})$とみなすと
\[
A=\dfrac{1}{\sqrt{2}}
\begin{pmatrix}
1&1&0&0\\
1&-1&0&0\\
0&0&1&1\\
0&0&1&-1
\end{pmatrix},\quad
B=\begin{pmatrix}
1&0&0&0\\
0&0&0&-1\\
0&0&1&0\\
0&1&0&0
\end{pmatrix}
\]
と表示できる。これらの行列は$\mathrm{SO}_4(\mathbb{R})$に属しており、さらに
\[
J=\begin{pmatrix}
i&0\\0&i
\end{pmatrix}
=\begin{pmatrix}
0&0&-1&0\\
0&0&0&-1\\
1&0&0&0\\
0&1&0&0
\end{pmatrix}
\]
と可換であることに注意する。以下の$48$個の点からなる$\mathbb{R}^4$の部分集合を$S$とする：
\begin{itemize}
\item $(\pm 2,0,0,0)$の並べ替え（8個）
\item $(\pm \sqrt 2,\pm\sqrt{2},0,0)$の並べ替え（24個、複号任意）
\item $(\pm 1,\pm 1,\pm 1,\pm 1)$（16個、複号任意）
\end{itemize}
すると$G=\langle A,B\rangle$は$S$に推移的に作用する。$(2,0,0,0)$の固定部分群$H$が$\{1,B,B^2,B^3\}$に等しいことを示す。$H$の元は$(2,0,0,0)$からの距離が$2\sqrt{2}$である$6$点のなす正$8$面体
\[
P=\{(0,\pm 2,0,0),(0,0,\pm 2,0),(0,0,0,\pm 2)\}\subset S
\]
に作用する。$J$によって$(2,0,0,0)$は$(0,0,2,0)$にうつるので、$H$の作用は$(0,0,2,0)$を固定する。このような回転は$1,B,B^2,B^3$に限られる。以上より$\#G=\#S\cdot\#H=48\cdot 4=192$である。
ちなみに$S$を構成する$3$種類の点はそれぞれ半径$2$の球面に内接する正$16$胞体、正$24$胞体、正$8$胞体の頂点をなす。
\end{answer}
\section{2026/01/31}
\subsection{q-パスカルの変形}
\newcommand{\qbinom}[2]{\begin{bmatrix}#1\\#2\end{bmatrix}_x}
\begin{problem}
複素数 $x\in\mathbb C$ を固定し，整数 $\ell\ge 1$ と $0\le p\le \ell$ に対して数（$x$ の多項式とみなせる）
$a_p^\ell$ を次で定める：
\[
a_0^\ell=2^{\ell-1}(\ell\ge 1),\qquad a_\ell^\ell=0\ (\ell\ge 2),
\]
および $\ell\ge 2,\ 1\le p\le \ell-1$ の範囲で
\[
a_p^\ell
=
\bigl(x^{p-1}+x^{\ell-2}\bigr)\,a_{p-1}^{\ell-1}
+
(x^{p}+1)\,a_p^{\ell-1}.
\tag{$\dagger$}
\]
このとき，$x\in\mathbb C^\times$ が$1$の冪根でなければ，
任意の $\ell\ge 1$ と $0\le p\le \ell-1$ について $a_p^\ell(x)\neq 0$となることを示せ
\end{problem}
以下，chatGPTの解答に洞が書き加えたもの．
\subsubsection{Preliminaries on $q$-整数・$q$-二項係数.}
\[
[n]_x:=1+x+\cdots+x^{n-1},\qquad
[n]_x!:={\prod_{i=1}^n [i]_x},
\qquad
\qbinom{n}{p}:=\frac{[n]_x!}{[p]_x!\,[n-p]_x!}.
\]
\begin{lemma}[$q$-パスカル恒等式]
$n\ge 1,\ 0\le p\le n$ に対して
\[
\qbinom{n}{p}
=
\qbinom{n-1}{p}
+
x^{n-p}\qbinom{n-1}{p-1},
\tag{P1}
\]
\[
\qbinom{n}{p}
=
x^{p}\qbinom{n-1}{p}
+
\qbinom{n-1}{p-1}
\tag{P2}
\]
が成り立つ（ここで $\qbinom{n-1}{-1}=\qbinom{n-1}{n}=0$ と約束する）．
\end{lemma}
\begin{proof}
(P1) (P2)の両辺を$\frac{[n-1]_x!}{[p]_x!\,[n-p]_x!}$で割ると，示すべき式は
\[
[n]_x = [n-p]_x + x^{n-p} [p]_x \tag{P1'}
\]
と
\[
[n]_x = x^p [n-p]_x + [p]_x \tag{P2'}
\]
になり，これらは正しい．
\end{proof}
\begin{corollary}[(P1)(P2)の加法型]
$n\ge 1,\ 0\le p\le n$ に対して
\[
2\qbinom{n}{p}
=
(1+x^{p})\qbinom{n-1}{p}
+
(1+x^{n-p})\qbinom{n-1}{p-1}
\tag{P$+$}
\]
が成り立つ．
\end{corollary}
\begin{proof}
(P1) と (P2) を辺々足せばよい．
\end{proof}
\subsubsection{解答}
上の再帰 $(\dagger)$ と境界条件で定まる $a_p^\ell$ は
\[
a_p^\ell
=
2^{\ell-1}\,x^{\binom{p}{2}}\,
\qbinom{\ell-1}{p}
\qquad(0\le p\le \ell)
\tag{$\heartsuit$}
\]
で与えられる．
\begin{proof}
$\ell$ による帰納法で示す．
\emph{境界ケース}：
$\ell=1$ のとき $a_0^1=1$ は $(\heartsuit)$ 右辺
$2^{0}x^{0}\qbinom{0}{0}=1$ と一致し，また $a_1^1=0$ も
$\qbinom{0}{1}=0$ から従う．
一般の $\ell$ でも $p=0$ は $\qbinom{\ell-1}{0}=1$ より $a_0^\ell=2^{\ell-1}$ と一致し，
$p=\ell$ は $\qbinom{\ell-1}{\ell}=0$ より $a_\ell^\ell=0$ と一致する．
\emph{帰納ステップ}：
$\ell\ge 2$ とし，$\ell-1$ 段について $(\heartsuit)$ が成り立つと仮定する．
$1\le p\le \ell-1$ に対し，再帰 $(\dagger)$ の右辺を計算する：
\[
\begin{aligned}
&\bigl(x^{p-1}+x^{\ell-2}\bigr)a_{p-1}^{\ell-1}+(x^{p}+1)a_{p}^{\ell-1}\\
&=
\bigl(x^{p-1}+x^{\ell-2}\bigr)\,2^{\ell-2}x^{\binom{p-1}{2}}
\qbinom{\ell-2}{p-1}
+
(x^{p}+1)\,2^{\ell-2}x^{\binom{p}{2}}
\qbinom{\ell-2}{p}.
\end{aligned}
\]
ここで
\[
x^{p-1}x^{\binom{p-1}{2}}=x^{\binom{p}{2}},\qquad
x^{\ell-2}x^{\binom{p-1}{2}}=x^{\binom{p}{2}}x^{\ell-p-1}
\]
より，$2^{\ell-2}x^{\binom{p}{2}}$ をくくると
\[
2^{\ell-2}x^{\binom{p}{2}}
\Bigl(
(1+x^{p})\qbinom{\ell-2}{p}
+
(1+x^{\ell-p-1})\qbinom{\ell-2}{p-1}
\Bigr).
\]
コロラリー (P$+$) に $n=\ell-1$ を代入すると
\[
(1+x^{p})\qbinom{\ell-2}{p}
+
(1+x^{\ell-p-1})\qbinom{\ell-2}{p-1}
=
2\qbinom{\ell-1}{p}.
\]
したがって右辺全体は
\[
2^{\ell-2}x^{\binom{p}{2}}\cdot 2\qbinom{\ell-1}{p}
=
2^{\ell-1}x^{\binom{p}{2}}\qbinom{\ell-1}{p},
\]
すなわち $(\heartsuit)$ の右辺に一致する．よって帰納法が閉じる．
\end{proof}
\begin{corollary}[非消滅（root of unity でない場合）]
$x\in\mathbb C^\times$ が root of unity でなければ，
任意の $\ell\ge 1$ と $0\le p\le \ell-1$ について $a_p^\ell(x)\neq 0$．
\end{corollary}
\begin{proof}
$(\heartsuit)$ より $a_p^\ell$ の零点は $\qbinom{\ell-1}{p}$ の零点に限られる．
一方
\[
[n]_x=\frac{x^n-1}{x-1}
\]
なので $[n]_x$ の零点は $1$ 以外の $n$ 乗根（root of unity）に限られる．
$q$-二項係数は $[k]_x$ の積と商（実際には多項式）で表されるから，
その零点も root of unity に限られる．よって $x$ が root of unity でないなら
$\qbinom{\ell-1}{p}\neq 0$，従って $a_p^\ell(x)\neq 0$．
\end{proof}
\subsection{三角関数に関する最小値問題}
\begin{problem}
\begin{enumerate}
\item $\cos{2x} + 2\cos{x}$ の最小値を求めよ
\item $\cos{3x} + 2\cos{2x} + 3\cos{x}$ の最小値を求めよ
\item $\cos{4x} + 2\cos{3x}+ 3\cos{2x}+ 4\cos{x}$ の最小値を求めよ
\end{enumerate}\internalmemoref{memo-20260131-01}
\end{problem}
\section{2026/02/15}
\subsection{群作用に関する不等式(東大院試)}
\begin{problem}
有限群$G$が有限集合$X$($\# X>1$)に推移的に作用している．このとき，$g\in G$に対して，$n_g\coloneqq \#\{x\in X \mid gx=x\}$を$g$による作用の不動点の個数とし，$G_0\coloneqq \{g\in G\mid n_g=0\}$と定める．
\begin{enumerate}
\item $\sum_{g\in G} n_g = \#G$を示せ
\item 不等式$\frac{\#G_0}{\#G}\geq (\# X)^{-1}$を示せ
\item $\frac{\#G_0}{\#G}= (\# X)^{-1}$が成立するような$\#X=4$なる例を挙げよ．
\end{enumerate}
\end{problem}
\begin{proof}
\begin{enumerate}
\item これはBurnsideの(でない)補題の特別な場合．Orbit-Stabilizer theoremから\[\sum_{g\in G} n_g = \#\{(g,x)\in G \times X\mid gx=x\} = \sum_{x\in X} \#\Stab(x) = \# X \times \frac{\# G}{\# X}\]
となりok.
\item $G$の$X^{(2)}\coloneqq \{(x,y)\in X^2\mid x\neq y\}$への各点での作用を考え，その軌道の個数$\# (X^{(2)}/G)$を上下から評価する．まず自明な下からの評価として，仮定$\#X >1$より
\begin{equation}\label{eq:grouplowerinequality}
1\leq \# (X^{(2)}/G)
\end{equation}
を得る．
一方で，Burnsideの(でない)補題を$X^{(2)}$に適用することで，
\[
\# (X^{(2)}/G) = \frac{1}{\# G} \sum_{g\in G} n_g (n_g-1)
\]
を得る．これを用いると，$\# (X^{(2)}/G)$は次のように上から評価できる
\begin{equation}\label{eq:groupupperinequality}
\# (X^{(2)}/G) =\frac{1}{\# G}\sum_{g\in G} n_g (n_g-1) = \frac{1}{\# G}\sum_{g\in G \setminus G_0} n_g (n_g-1) \leq \frac{\# X}{\# G}\sum_{g\in G \setminus G_0} (n_g-1) = \frac{\# X \cdot \# G_0}{\# G}
\end{equation}
(不等号部分は，$n_g \leq \# X$だけでなく，$g\in G \setminus G_0$についての$n_g-1 \geq 0$も使っていることに注意．)
不等式(\ref{eq:grouplowerinequality})と不等式(\ref{eq:groupupperinequality})を合わせると，証明が完成する．
\item $A_4$の$4$元への標準作用が条件を満たす．
\end{enumerate}
\end{proof}
\begin{remark}[等号成立条件]
より詳細な解析として，等号成立条件を考察する．
\begin{itemize}
\item 不等号(\ref{eq:grouplowerinequality})が等号になるためには，作用が$2$-transitiveなことが必要十分である．(ほぼ定義)
\item 不等号(\ref{eq:groupupperinequality})が等号になるためには，任意の$g\in G$について$n_g\geq 2 \implies n_g = \# X$となることが必要十分である．つまり，$g\in G$が$2$点を固定するなら全体を固定する．
\end{itemize}
この二つの論理積を取れば
\begin{itemize}
\item $\frac{\#G_0}{\#G}= (\# X)^{-1}\iff$ ある正規部分群$N\triangleleft G$が存在し$G$集合として$X^{(2)}\cong G/N$となる
\end{itemize}
がわかる．
群$G$を$G/N$に置き換えれば同じ議論が回るから，$N=1$の例に興味がある．典型例は有限体上の$1$次元Affine変換$(G=\F_q \rtimes \F_q^\times, X=\F_q, N=1)$である．$q=4$の場合$\F_4 \rtimes \F_4^\times \cong A_4$となり，小問3の答えを与えている．%($N=1$のときには，$G$集合として$X^{(2)}\cong G$になるから，特に$\# G = \# X^2 - \# X$という強い制約が入っている)
\end{remark}
\subsection{正20面体と$\F_5$}
話題(神尾)
$\F_5^3\setminus \{(0,0,0)\}$の元であって，$x^2+y^2+z^2$が$0, \pm1, \pm 2$になるものの個数は，それぞれ正$20$面体の頂点，辺，面の数の$2$倍に等しい．
正$20$面体の頂点の座標は$\Z\left[\frac{1+\sqrt{5}}{2}\right]$を用いて書けて，それを$\Z\left[\frac{1+\sqrt{5}}{2}\right]\twoheadrightarrow \F_5$でreductionするという話らしい．
頂点座標は$\left(0, \pm 1, \pm \frac{1+\sqrt{5}}{2}\right)$という$4$つと，それらの座標をサイクリックに回して得られる合計$4\times 3 = 12$個らしい．
\section{2026/02/22}
\subsection{二項係数の\texorpdfstring{$\mod 4$}{mod4}和}
\begin{problem}
正整数$n>0$について，以下の値を求めよ
\[\sum_{k\equiv 0 \pmod 4} \binom{n}{k} \]
\end{problem}
\begin{answer}
\[(1+i)^n +(1+i^2)^n +(1+i^3)^n +(1+i^4)^n \]
を二項展開して足し合わせると，
\[
4\left(\sum_{k\equiv 0 \pmod 4} \binom{n}{k} \right)
\]
になることがわかる．よって，求める値は
\[
\sum_{k\equiv 0 \pmod 4} \binom{n}{k} =\frac{1}{4}\left( 2^n + 2\sqrt{2}^n \cos\left(\frac{\pi n}{4}\right)\right)
\]
\end{answer}
宮内くんから，$n=0$では$1$になるべきなのに$0.75$になっているという指摘があった．実際，考えるべき母関数は
\[
\frac{1}{1-(1+i^1)x}+\frac{1}{1-(1+i^2)x}+\frac{1}{1-(1+i^3)x}+\frac{1}{1-(1+i^4)x}
\]
であり，この第二項の効果を勘案すれば$n=0$での値も$1$になり揃う．
\subsection{お金の分配と行列の核}
\begin{problem}
$n$を正整数として，$2n+1$次の正方行列$A$で
\begin{enumerate}
\item 対角成分は全て$0$
\item 対角成分以外は全て$\pm 1$のいずれか．
\item どの行についても，行にわたるの成分和は$0$．
\end{enumerate}
このとき，$\R$線型空間として
\[
\ker A = \{(x_0, \dots x_{2n})\mid x_0 = \dots = x_{2n}\}であることを示せ．
\]
\end{problem}
\begin{example}
$n=1$のとき，例えば\[A=
\begin{pmatrix}
0& 1& -1\\
1 & 0 &-1 \\
1&-1&0
\end{pmatrix}
\]
を考えられるが，
\[
A\cdot \begin{pmatrix}
x \\y\\ z
\end{pmatrix}
=\begin{pmatrix}
0 \\0\\ 0
\end{pmatrix}
\]
なら$x=y=z$となるので，$\ker A $は$1$次元．
\end{example}
\begin{proof}
実は，$\ker A \cap \Z^{2n+1}$が$\Z$加群としてランク$1$であることを示せば十分である．
$x=(x_0, \dots x_{2n})\in \ker A\cap \Z^{2n+1}$を任意にとる．このとき$x_0, \dots, x_{2n}$の偶奇は全て$x_0+ \dots + x_{2n}$の偶奇と一致する．実際，$x = (I+A)x - Ax = (I+A) x$を$\mathop{\mathrm{mod}} 2$で見れば良い．
このとき，まず$x$の成分全てに十分大きな正の整数を足すことで，$x$の成分は全て非負整数であるとして良い．その後，$x\in \N^{2n+1}$に対して以下の操作を繰り返す．
\begin{itemize}
\item $x$の全ての成分が偶数なら，全ての成分を$2$で割る．
\item $x$の全ての成分が奇数なら，全ての成分から$1$を引いて，さらに全ての成分を$2$で割る．
\end{itemize}
(つまり，全ての成分において同時に，$2$進数展開の1桁目を除去する．)
この操作は終了しない(かつ$\N^{2n+1}$はwell-foundedなので)この操作で成分が減少しない唯一の$\N^{2n+1}$の元$(0, \dots 0)$へ辿り着く．この操作を逆向きに辿ることで，$x_0 = \dots = x_{2n}$がわかる．
\end{proof}
\section{2026/02/28}
\subsection{無向辺しりとり}
有限無向グラフ$G=(V,E)$とその頂点$v_0\in V$の組が与えられたときに，$v_0$を初期位置として二人のプレイヤーが交互に辺に沿って移動するゲームを考える．すでに(どちらかの)プレイヤーが通った辺は二度と通ることはできない．先に動けなくなったプレイヤーの負けである．
\begin{proposition}
$G$が二部グラフのとき，先手必勝か後手必勝かを多項式時間で判定できるらしい．どうやる？
\end{proposition}
cf. Undirected Edge Geography
\section{2026/03/08}
\subsection{警官数}
\begin{problem}
グラフ $G$ に対して，以下をみたす最小の自然数 $a$ を $G$ の警官数という．
プレイヤー $D,K$ が以下のゲームを行うとき，$K$ が必ず勝つ：
\begin{itemize}
\item $K$：$G$ の頂点上に $a$ 人の警官を置く．
\item $D$：$G$ の頂点上に $1$ 人の泥棒を置く．
\item 以後，交互に
\begin{itemize}
\item $K$：警官を何人か($0$以上$a$以下人)選び，隣接する頂点に移動させる．
\item $D$：何もしない，あるいは泥棒を隣接する頂点に移動させる．
\end{itemize}
\item ある警官が泥棒と同じ頂点にいる場合，$K$ の勝ちとする．
\end{itemize}
\begin{enumerate}
\item 木の警官数は $1$ であることを示せ．
\item 平面的グラフの警官数は $3$ 以下らしい．
\end{enumerate}
\end{problem}
1は追い詰めればいいが，2が難しい．平面グラフであって，警官数が3のものを宮内くんが構成していた．すべての次数が$3$であるようなグラフ($3$-正則グラフ)であって，すべての"面"が五角形であるものを使うといいらしい．
\section{2026/03/28}
\subsection{ガウス整数の\texorpdfstring{$-1+i$}{theta}進展開とフラクタル}
\begin{problem}
\begin{enumerate}
\item $\theta\coloneqq -1+i$とする．任意の$z\in \mathbb{Z}[i]$が
\[
z=\sum_{j=0}^{\ell} a_j \theta^j \qquad (a_j\in \{0,1\})
\]
と一意的に表示できることを示せ．
\item 次を満たす$\alpha\in \mathbb{Z}[i]$を全て求めよ．ある自然数$k$が存在して，任意の$z\in \mathbb{Z}[i]$が
\[
z=\sum_{j=0}^{\ell} a_j \alpha^j \qquad (a_j\in \{0,1,\dots,k\})
\]
と一意的に表示できる．
\end{enumerate}
\end{problem}
\begin{proof}[(1)のproofと(2)の途中]
$k\coloneqq N(\alpha) -1=\# \Z[i]/(\alpha) -1$とおく．
まず，$\alpha$が条件を満たすなら，集合$D\coloneqq \{0,1,\dots,k\}$は$\mathbb{Z}[i]/(\alpha)$の完全代表系でなければならない．
% したがって
% \[
% k+1=\#(\mathbb{Z}[i]/(\alpha))=N(\alpha)
% \]
% であり，特に
% \[
% D=\{0,1,\dots,N(\alpha)-1\}
% \]
% である．
各 $z\in \mathbb{Z}[i]$ に対して $d_\alpha(z)\in D$ を
\[
z\equiv d_\alpha(z)\pmod{\alpha}
\]
をみたす唯一の元とし，
\[
T_\alpha(z)\coloneqq \frac{z-d_\alpha(z)}{\alpha}
\]
と定める．
これは「$z$ を $\alpha$ で割ったとき，余りを $D$ の中で取り，商を返す写像」とみなせる．
すると，この問題は離散力学系$T_\alpha \colon \Z[i]\to \Z[i]$の連結性の問題に帰着される．実際，
\[
z=d_\alpha(z)+\alpha T_\alpha(z)
\]
であり，これを繰り返すと任意の $m\ge 1$ に対して
\[
z
=
d_\alpha(z)
+\alpha d_\alpha(T_\alpha(z))
+\alpha^2 d_\alpha(T_\alpha^2(z))
+\cdots
+\alpha^{m-1} d_\alpha(T_\alpha^{m-1}(z))
+\alpha^m T_\alpha^m(z)
\]
を得る．$\alpha$での剰余をみれば，($m$が十分大きいときの)上式が存在しうる唯一の表示であることがわかる．さらに，$z$ が有限表示できることは，$z$ の $T_\alpha$-軌道が有限回で $0$ に到達することと同値である．\internalmemoref{memo-20260328-01}
言い換えると，問題の条件は
\[
\text{「$T_\alpha$ が $\mathbb{Z}[i]$ 上で $0$ を大域吸引固定点にもつ」}
\]
ことである．
\begin{figure}[ht]
\centering
\missinggraphic[0.9\linewidth]{orange.png}{原画像未配置。$T_\alpha$が$0$に到達するまでの時間を表す図として後で差し替える。}
\caption{The time until reaching $T_\alpha$}
\label{fig:orange}
\end{figure}
次に $\alpha=a+bi$ とおく．
$\alpha$ の整数係数多項式はすべて $\mathbb{Z}[bi]$ に属するので，
その虚部は必ず $b$ の倍数である．
ところが仮定より $i$ 自身もそのように表示できなければならないから，
$b=\pm 1$ である．
よって
\[
\alpha=a+i \quad \text{または}\quad \alpha=a-i
\]
に限られる．特に，$k=N(\alpha)-1$は$a^2$であり，つまり$D=\{0,1, \dots , a^2\}$である．
% 以下，$\varepsilon=\pm 1$ として $\alpha=a+\varepsilon i$ と書く．
$a\ge 1$のとき，$T_\alpha$は$1-\overline{\alpha}$を不動点にもつ．このことは
\[
(1-\overline{\alpha}) = (1-\alpha)(1-\overline{\alpha})+\alpha (1-\overline{\alpha})
\]
と(実数同士の)不等式
\[
(1-\alpha)(1-\overline{\alpha})\in D
% \iff 0 \leq(1-\alpha)(1-\overline{\alpha}) \leq k
\iff 0 \leq1- 2a + (a^2+1) \leq a^2 \iff 1\leq a
\]
からわかる．よって，$a$は$0$以下でなければならず，$a=0$ (i.e. $\alpha=\pm i$) が不適なことも簡単にわかるため，$a$は負の整数でなくてはならない．
以上より必要条件として
\[
\alpha=-n+i \quad \text{または}\quad \alpha=-n-i
\qquad (n=1,2,3,\dots)
\]
を得た．
あとは，$T_\alpha$が$0\mapsto 0 \mapsto \dots$ 以外の連結成分の軌道を持つかを調べる．自己写像$T_\alpha$はおおよそ$\alpha$での商なので，有限個の例外をのぞいて絶対値を小さくする．実際，
\[
\abs{z}\leq \abs{T_\alpha (z)} \implies \sqrt{a^2+1}\abs{z}\leq \abs{\alpha T_\alpha (z)} = \abs{z-d}\leq \abs{z}+ a^2 \iff \abs{z}\leq 1+\sqrt{1+a^2}
\]
である．したがって，具体的な$a$については有限時間内で判定できる．(一般の$a$については知らない...)
\end{proof}
% \begin{remark}[1]
% $n=1$ のとき
% \[
% \alpha=-1+i,\qquad D=\{0,1\}
% \]
% である．
% このとき $d_\alpha(z)$ は
% \[
% z\equiv 0 \ \text{or}\ 1 \pmod{-1+i}
% \]
% で決まる余りであり，
% \[
% T_\alpha(z)=\frac{z-d_\alpha(z)}{-1+i}
% \]
% は「$-1+i$ で割った商」を返す写像である．
% この写像のすべての軌道が有限回で $0$ に入ることが，
% ガウス整数の $(-1+i)$ 進展開の存在と一意性にちょうど対応している．
% \end{remark}
\section{2026/04/04}
\subsection{分数の小数部分}
\begin{problem}
正の有理数$x$を用いて，$x+\frac{1}{x}$の小数部分として書ける有理数$\in \Q\cap[0,1)$は何か？
\end{problem}
$1/n$ができることはok．
素数$p$と正整数$k$と整数$0<i<p^k$について，
$i/p^k$が実現できることと$i=1$は同値．
それ以上は，初等整数論にするとこまではできた．
\begin{problem}
連続写像$f\colon (0,\infty) \to \R$が次の条件を満たしているとする．
\begin{description}
\item[条件] ある写像$g\colon (0,\infty)\to \R$が存在して，$f(xy)=f(x)+g(x)f(y)$を満たす．
\end{description}
$f$の形を決定せよ．
\end{problem}
Group-cohomologyだという話を小泉さんがしていた．
\section{2026/04/11}
\subsection{二項係数の約数}
\begin{problem}
$2$以上の整数$n$と整数$0<i,j<n$について，$\binom{n}{i}$と$\binom{n}{j}$は互いに素ではないことを示せ
\end{problem}
\begin{proof}（AI-proof, which is 賢いし正しい）
$i,j$を入れ替えてよいので，$i\le j$としてよい．
まず
\[
\binom{n}{j}\binom{j}{i}
=
\binom{n}{i}\binom{n-i}{j-i}
\]
が成り立つ．
これは，$[n]$から$j$個選んでその中からさらに$i$個選ぶ方法を，
\begin{itemize}
\item 先に$j$個選んでからその中で$i$個選ぶ
\item 先に$i$個選んでから残り$n-i$個の中から$j-i$個選ぶ
\end{itemize}
の2通りに数えたものだと思えばよい．
もし $\binom{n}{i}$ と $\binom{n}{j}$ が互いに素だとすると，
上の等式より$\binom{n}{i}\mid \binom{j}{i}$
が従う．
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[x=1cm,y=1cm]
% 左：\binom{n}{j}\binom{j}{i}
\draw[thick] (0,0) rectangle (4.5,3.2);
\node at (4.2,2.9) {$[n]$};
\node at (2.25,2.95) {$n-j$};
\draw[thick, rounded corners=6pt, fill=blue!8] (0.5,0.45) rectangle (4.0,2.75);
\node at (3.7,2.45) {$J$};
\node at (2.25,2.3) {$j-i$};
\draw[thick, rounded corners=6pt, fill=orange!18] (1.35,1.0) rectangle (3.05,1.95);
\node at (2.7,1.68) {$I$};
\node at (2.2,1.52) {$i$};
\end{tikzpicture}
\caption{$I\subset J\subset [n]$, $|I|=i$, $|J|=j$をダブルカウント}
\end{figure}
しかし，$0<i$ を固定すると $\binom{m}{i}$ は $m$ に関して単調増加であるから，
$j<n$ より
\[
\binom{j}{i}<\binom{n}{i}
\]
である．
したがって正整数 $\binom{n}{i}$ がそれより小さい正整数 $\binom{j}{i}$ を割ることはできず，
矛盾する．
よって $\binom{n}{i}$ と $\binom{n}{j}$ は互いに素ではない．
\end{proof}
上の証明は非構成的だが、少し考えると構成を取り出すことができる。実際
\[
\dfrac{\binom{n}{i}}{\gcd\bigl(\binom{n}{i},\binom{j}{i}\bigr)}>1
\]
の最小の素因数を$p$とすれば、$v_p\bigl(\binom{n}{i}\bigr)>v_p\bigl(\binom{j}{i}\bigr)$となるので、$p$は$\binom{n}{i}$と$\binom{n}{j}$の共通素因数となる。
\subsection{entropy modulo prime}
フェルマー微分を使うと，公理的なエントロピーが$\F_p$上にもできるらしい？ あまり理解が進んだ感じはしない
\section{2026/04/18}
\begin{figure}[ht]
\centering
\missinggraphic[0.75\linewidth]{geometry-angle-chase-step-2.png}{原画像未配置。角追い図として後で差し替える。}
\caption{An AI-generated figure}
\label{fig:Geometry20260418}
\end{figure}
\section{2026/0509}
\subsection{平面上の円板の配置}
\begin{problem}
$n\geq 3$ とする．
平面上に半径 $1$ の円板 $D_1,\ldots,D_n$ があり，
どの直線も $3$ つ以上の円板とは交わらないとする．
$D_i$ と $D_j$ の中心間距離を $d_{ij}$ とおく．
このとき
\[
\sum_{1\leq i<j\leq n}\frac{1}{d_{ij}}<\frac{n\pi}{4}
\]
を示せ．
また，この評価がどのくらい改善できるか考えよ．
\end{problem}
\begin{proof}（AI-proof）
まず任意の $i\neq j$ について $D_i\cap D_j=\varnothing$ である．
実際，もし交われば，その交点と第三の円板 $D_k$ の一点を結ぶ直線が
$D_i,D_j,D_k$ のすべてと交わってしまう．
よって
\[
d_{ij}>2
\]
である．
方向を一つ固定し，その方向に垂直な直線へ各円板を正射影する．
$D_i$ の射影を $I_i$ と書くと，これは長さ $2$ の区間である．
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[x=1cm,y=1cm,scale=0.9]
% projection line
\draw[thick,->] (-0.5,0) -- (7.3,0);
% disks
\foreach \x/\y/\name in {1.2/2.5/D_1,3.0/3.0/D_2,5.0/2.3/D_3}{
\draw[thick, fill=blue!8] (\x,\y) circle (0.55);
\fill (\x,\y) circle (1.5pt);
\node[above right] at (\x+0.35,\y+0.25) {$\name$};
\draw[dashed] (\x,\y) -- (\x,0);
\draw[thick] (\x-0.55,0.08) -- (\x+0.55,0.08);
\draw[thick] (\x-0.55,-0.05) -- (\x-0.55,0.20);
\draw[thick] (\x+0.55,-0.05) -- (\x+0.55,0.20);
}
% interval labels
\node[below] at (1.2,-0.18) {$I_1$};
\node[below] at (3.0,-0.18) {$I_2$};
\node[below] at (5.0,-0.18) {$I_3$};
\end{tikzpicture}
\caption{円板を一方向に射影して区間を見る}
\end{figure}
仮定より，区間族 $I_1,\ldots,I_n$ は三重交点を持たない．
したがって，交わっている区間の組の個数は高々 $n-1$ である．
実際，各交わりは，二つの区間のうち左端が右にある方を見た瞬間に一度だけ数えられ，
そのとき既に重なっている区間は高々一つだからである．
ゆえに，射影方向をランダムに取ると
\[
\mathbb{E}\#\{(i,j)\mid i<j,\ I_i\cap I_j\neq\varnothing\}\leq n-1
\]
である．
一方，中心間距離が $d_{ij}$ の二つの円板の射影が交わる確率は
\[
\frac{2}{\pi}\arcsin\frac{2}{d_{ij}}
\]
である．
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[x=1cm,y=1cm,scale=0.95]
% parameters
\coordinate (Oi) at (0,2.2);
\coordinate (Oj) at (4.2,3.0);
% projection line
\draw[thick,->] (-1,0) -- (6.2,0);
\node[right] at (6.2,0) {射影先};
% vertical projection arrows
\draw[dashed,->] (Oi) -- (0,0);
\draw[dashed,->] (Oj) -- (4.2,0);
% disks
\draw[thick,fill=blue!8] (Oi) circle (0.5);
\draw[thick,fill=orange!12] (Oj) circle (0.5);
\fill (Oi) circle (1.4pt);
\fill (Oj) circle (1.4pt);
\node[above left] at (Oi) {$D_i$};
\node[above right] at (Oj) {$D_j$};
% center distance
\draw[thick] (Oi) -- (Oj);
\node[above] at (2.1,2.6) {$d_{ij}$};
% projected intervals
\draw[very thick] (-0.5,0.15) -- (0.5,0.15);
\draw[very thick] (3.7,0.15) -- (4.7,0.15);
\draw[thick] (-0.5,0.03) -- (-0.5,0.27);
\draw[thick] (0.5,0.03) -- (0.5,0.27);
\draw[thick] (3.7,0.03) -- (3.7,0.27);
\draw[thick] (4.7,0.03) -- (4.7,0.27);
\node[below] at (0,-0.15) {$I_i$};
\node[below] at (4.2,-0.15) {$I_j$};
% projected center distance
\draw[<->] (0,-0.55) -- (4.2,-0.55);
\node[below] at (2.1,-0.55) {$d_{ij}\sin\theta$};
% direction and angle
\draw[->] (Oi) -- ++(0,1.25);
\node[left] at (0,3.45) {射影方向};
\draw (0,2.85) arc (90:101:0.65);
\node at (-0.22,3.05) {$\theta$};
% condition
\node at (3.2,1.25) {$I_i\cap I_j\neq\varnothing$};
\node at (3.2,0.85) {$\Longleftrightarrow\ d_{ij}|\sin\theta|\leq 2$};
\end{tikzpicture}
\caption{二つの円板の射影が交わる条件}
\end{figure}
したがって
\[
\sum_{1\leq i<j\leq n}
\frac{2}{\pi}\arcsin\frac{2}{d_{ij}}
\leq n-1
\]
である．
さらに $0<x<1$ に対して $\arcsin x>x$ なので，
\[
\frac{4}{\pi}
\sum_{1\leq i<j\leq n}\frac{1}{d_{ij}}
<
n-1.
\]
よって
\[
\sum_{1\leq i<j\leq n}\frac{1}{d_{ij}}
<
\frac{(n-1)\pi}{4}
<
\frac{n\pi}{4}.
\]
\end{proof}