問い #276

Multi-select sumと普遍monoid ## Trigger Notion「研究テーマ」DBの `Multi-select sum of Games/ Universal Monoids`（優先度★★★、進行状況 ●○○、coresearcher: J.Koizumi, Tomoaki Abuku、Subfield: game theory、Last Edited 2023-09-01）から瓶化した。coresearcher 欄の2人は議論相手としての記録であり、共著の裏は取っていない。 ## Idea Games $A_1,\dots,A_n$ に対して、それらの **multi-select sum**（正の有限個の成分を選んでプレイする和）を考える。これは不偏ゲームの monoidal product で、Conway addition に似ている。 **問い: この operation に関する普遍的な monoid 不変量（universal monoid invariant）は何か。** 原メモの観察・部分結果: - LN(3,2) は 2山Nim と 1山Nim の multi-select sum なので、universal monoid invariant が分かれば LN(3,2) が解けるはず。 - 予想（原メモ自身が曖昧と注記）: universal monoid invariant は Birthday と Grundy number のペアか？（「しなさそう．いや，するかも」） - 性質: $1\mathrm{Nim}(n)+1\mathrm{Nim}(m)=1\mathrm{Nim}(n+m)$（一山）、$LN(3,2)(a,b,c)=2\mathrm{Nim}(a,c)+1\mathrm{Nim}(b)$、$X_1+\dots+X_1=\mathrm{Nim}_n$（$X_{n+1}=\{X_n\},\ X_0=0$）。 - Lemma: $A+B$ が P-position $\iff$ $A$ も $B$ も P-position（LN(3,2) のときに観察済み）。よって universal monoid では P-position は全て単位元（後手必勝ゲーム全体のなす同値類）につぶれる。 - universal monoid は群ではない: $\mathrm{Nim}_n$（$n>0$）に何を multi-sum しても単位元になれない（Lemma より）。 - $\{P,N\}$-universal monoid は $\{P,N\}$ 自体。だから本命は **Grundy-universal monoid** で、単位元も考え直す必要がある。Birthday が関わるかも。 - 「Game Operation and Universal Monoids」という観点からは、パス付き三山ニムの未解決問題も関連しそう。"Recursive aspect" にも注目する。 - 例の候補: Grundy数 / Remoteness / Selective sum + PN / 逆形ゲーム / Selective sum + Grundy / Selective and Conway sum（知りたい）/ パスつき3山Nim（"dependent sum"）。 ## Personal context Universal monoid・recursive coalgebras・monoidal structure を全部駆使したい方向（原メモの結び）。*Games as recursive coalgebras* 系の公開問題 [[f98jzd]]（Bouton monoid）・[[tauvfv]]（monoidal closed structures）と近い場所にあるが、multi-select sum という別の operation の普遍不変量を問う点で独立した問い。 ## 2026-08-26 AI研究監査：eventual birthday theorem selective compound を $A\nabla B$，Nim heap を $*k$，$d(A)$ を $A$ からの最大 play 長（birthday/depth）とする．任意の short finite impartial game $A$ について \[ \operatorname{Gr}(A\nabla *k)=k+d(A) \] が十分大きいすべての $k$ で成り立つ． 証明：$f_A(k)=\operatorname{Gr}(A\nabla *k)$ と置く．$A\nabla*(k+1)$ の option set は $A\nabla*k$ とその全 option を含むので $f_A(k+1)>f_A(k)$．一方 Grundy number は depth 以下だから $f_A(k)\le k+d(A)$．従って $\delta_A(k)=f_A(k)-k$ は非減少かつ $d(A)$ 以下で，最終的に定数 $e$ となる．$d=d(A)>0$ とし depth $d-1$ の option $A'$ を取る．帰納法で $\operatorname{Gr}(A'\nabla *j)=j+d-1$（$j\gg0$）．もし $e\le d-1$ なら $j=k+e-(d-1)\le k$ と置くと $A'\nabla *j$ は $A\nabla*k$ の option であり，その Grundy number は $k+e=f_A(k)$ となって mex に反する．よって $e=d$． 従って selective contexts に関する universal monoid は birthday を検出する： \[ d(A)=\lim_{k\to\infty}(\operatorname{Gr}(A\nabla*k)-k). \] また $(d,\operatorname{Gr})$ は普遍不変量ではない．$G=\{*2\}$ と $H=\{*1,*2\}$ はともに $(d,\operatorname{Gr})=(3,0)$ だが \[ \operatorname{Gr}(G\nabla*1)=1,\qquad \operatorname{Gr}(H\nabla*1)=4. \] Bouton monoid 全体の決定には，異なる hereditarily finite games を有限 selective context が必ず分離するか，または collision があるかを決める必要がある．