Eventual affine mex則

Trigger

Multi-select sumと普遍monoid と The Bouton monoid で得た selective sum の eventual birthday phenomenon を，mex/rev-mex双対力学系 の mex 力学系も含む一般の well-founded game operation に抽象化した．

Result

定理（abstract eventual affine mex theorem）． well-founded impartial games の二項 operation $\diamond$ と test games $H_k$ があり，次を満たすとする．

1. $\operatorname{Gr}(H_k)=d(H_k)=k$．
2. $A\diamond H_k$ とその全 options は $A\diamond H_{k+1}$ の options に含まれる．
3. $d(A\diamond H_k)\le d(A)+k$．
4. deepest option $A'$ of $A$ と任意の $j\le k$ に対し，$A'\diamond H_j$ は $A\diamond H_k$ の option である．

このとき任意の finite short impartial game $A$ について

が成り立つ．ここで $d(A)$ は最大 play length である．

Proof

$f_A(k)=\operatorname{Gr}(A\diamond H_k)$ と置く．仮定2より，$A\diamond H_{k+1}$ の options は $A\diamond H_k$ とその全 options を含む．mex の定義から後者の Grundy values は $0,\dots,f_A(k)-1$ を含み，前者自身が $f_A(k)$ を与えるので

従って $\delta_A(k)=f_A(k)-k$ は非減少である．一方，Grundy number は depth 以下なので

よって $\delta_A(k)\le d(A)$．従って $\delta_A(k)$ は最終的に定数 $e$ になる．

$d(A)=d>0$ とし，$d(A')=d-1$ の option $A'$ を取る．depth に関する帰納法により

もし $e\le d-1$ なら

と取れる．仮定4より $A'\diamond H_j$ は $A\diamond H_k$ の option だが

となり，position とその option が同じ Grundy number を持つという矛盾を得る．従って $e=d$．

Selective-sum corollary

$\diamond=\nabla$ を selective sum，$H_k=*k$ を Nim heap とすると仮定1--4が成立し，

特に

であり，selective contexts は birthday/depth を復元する．

Interpretation

大きな test object との compound が eventual affine になる機構は，個別の floor formula ではなく，

• mex による strict growth；
• depth による upper bound；
• deepest option による lower forcing；

の三点で説明される．

Status

抽象定理と selective-sum specialization は証明済み．他の game operations・rev-mex dynamics・misère analogues が仮定を満たすかは未調査である．