Wythoff Nim 完全値の計算量：A2 Hall 作用素、word 並列化、affine-tail

結論

完全な計算量分類には到達していないが、次の三点まで進んだ。

1. Wythoff の合法手は A2 の三正根方向そのものであり、PBW data 上の root-component Nim を
   weight へ existential pushforward すると正確に Wythoff game graph が得られる。
2. follower の色集合は Boolean 化した Hall support との convolution で正確に表せる。この
   作用を bitset へコンパイルすると、0<=a,b<=N の完全表を word-RAM で
   O(N^3/log N) word operations で計算できる。
3. 各固定行 m |-> G(r,m) は有限個の例外を除き affine symmetric group の元である。ただし
   隣接行の相対変換は短い Coxeter word ではなく、単純な局所更新による高速化は成立しない。

以下では、証明・機械検証・観察・反証・未解決を混ぜない。

表現論と Wythoff game の対応表

Wythoff game	表現論・幾何側	状態	計算量上の意味
位置 (a,b)	A2 正根格子の weight a alpha_1+b alpha_2	厳密な同一視	盤面を二次元正根錐として扱える
一方の山から k 個取る	k alpha_1 または k alpha_2 を引く	厳密な同一視	二本の単純根 ray
両方から同数 k を取る	k(alpha_1+alpha_2) を引く	厳密な同一視	最高根 ray
一位置の内部lift	PBW/Kostant fiber (a-z,z,b-z), 0<=z<=min(a,b)	厳密	fiber は min(a,b)+1 個で、basis変更だけでは圧縮されない
三方向の合法手全体	PBW multiplicityを一成分ずつ減らし、fiber全体を存在量化してweightへ射影	厳密	root-component Nim の existential image が Wythoff graph
色 g の follower が存在する	正根 indecomposable の直和による Hall 積の support を Boolean 化し、weightへ射影	厳密	split extensionの存在により、Hall geometryは三本のray convolutionへ潰れる
follower色集合	F_g と positive-root kernel K の Boolean convolution	厳密	bitset OR として実装できる
mex	Boolean supportの補集合に現れる最初の色	厳密だが標準Hall演算ではない	難所は positivity でなく complement / first-zero
固定行 `m	-> G(r,m)`	最終的な balanced affine permutation w_r in S-tilde_(p_r)	既知結果からの厳密な系
行の加法周期 p_r	affine permutation のwindow size	存在は証明済み	windowを展開せず評価する圧縮が必要
隣接行 r -> r+1	相対 affine permutation w_(r+1) w_r^(-1)	小規模計算では非局所的	bounded Coxeter update は使えない
P-positionの黄金比・Zeckendorf表示	A2 表現論側の標準object	対応未発見	G=0 の数論的解法は、現在のHall作用素とは別の構造
quiver Grassmannian / cluster character	固定representationのsubrepresentation支持	反証	合法手が不足または過剰になる
canonical / semicanonical basis	同じKostant weight spaceの別basis	圧縮として反証	fiberの要素数 min(a,b)+1 は減らない
Demazure / 0-Hecke root string	coroot pairingで切られるroot string	反証	Wythoffの正根錐境界によるcutoffと一致しない
word-parallel mex	Boolean Hall supportをline bitsetへコンパイル	厳密	完全表 O(N^3/log N) word operations

重要なのは、表の上半分は単なる比喩ではなく完全な対応である一方、mexはHall algebraの
通常の正係数演算からは出ず、Boolean complementとfirst-zeroを追加して初めて現れることである。

証明済み1：A2 PBW--Wythoff 対応

A2 の正根を alpha_1, alpha_2, alpha_12=alpha_1+alpha_2 とする。PBW multiplicityを
(x,z,y) とし、weight mapを

pi(x,z,y)=(x+z,y+z)

と置く。weight (a,b) のfiberは正確に

pi^(-1)(a,b)={(a-z,z,b-z) : 0<=z<=min(a,b)}

である。

PBW dataの一成分から正の整数 k を引き、結果のweightだけを見る。

• x を減らすと (a-k,b)。
• y を減らすと (a,b-k)。
• z を減らすと (a-k,b-k)。

逆に、それぞれのWythoff moveには、その成分を十分多く持つfiber elementが存在する。例えば
(a,b)->(a-k,b-k) には z>=k のliftを選べばよい。従って、fiber全体について存在量化した
PBW-Nimのweight像は、Wythoffの合法手と完全に一致する。

証明済み2：Boolean Hall--mex 作用素

色 g の位置のBoolean形式級数を

F_g(X,Y) = OR_(G(a,b)=g) X^a Y^b

とし、三正根のkernelを

K(X,Y)=X/(1-X) OR Y/(1-Y) OR XY/(1-XY)

とする。このとき

[X^a Y^b](F_g K)=1

であることと、位置 (a,b) のfollowerに色 g が存在することは同値である。従って

G(a,b)=min{g>=0 : [X^a Y^b](F_g K)=0}

となる。

Hall algebra側では、正根 beta のindecomposableを X_beta とすると、
[M] [X_beta^(direct-sum k)] のsupportをdimension vectorへBoolean射影したものが、この
root-ray kernelに一致する。split extension M direct-sum X_beta^(direct-sum k) が常に存在するため、
non-split extensionやHall数の情報はweight射影後には残らない。

従ってHall supportは合法手を正確に与えるが、mexを圧縮する標準作用素ではない。mexに必要なのは
正係数の積ではなく、色supportの補集合とfirst-zeroである。

証明済み3：完全表の O(N^3/log N) word-RAM算法

各行、各列、各difference diagonalについて、それまでに現れたGrundy値のbitsetを持つ。
row-majorに (a,b) を処理するとき、

S = Row_a OR Column_b OR Diagonal_(b-a)

をwordごとに計算する。S の最初の0 bitが、三方向の全follower色のmex、すなわち
G(a,b) である。求めたbitを三つのline bitsetへ追加する。

Nivaschのbound G(a,b)<=a+b により、0<=a,b<=N では各bitsetは O(N) bitsで足りる。
word sizeを w とすると、一cellは O(N/w)、全cellは

O(N^3/w+N^2)

word operationsである。w=Theta(log N) のword-RAMでは O(N^3/log N)。出力表を除く
補助領域は O(N^2/w) wordsである。

この評価はword-RAMでは真にsubcubicだが、bit complexityでは O(N^3) のままである。
固定行で三本のbit stringをNORしてmexを取る発想はLandman系で既知なので、全表へのこの
計算量評価の文献上の新規性は未確認とする。

証明済み4：Wythoff affine-tail 系

固定行を L_r(m)=G(r,m) とする。既知結果により、各 L_r は非負整数全体の置換であり、
ある P_r,p_r に対して

L_r(m+p_r)=L_r(m)+p_r for m>=P_r

を満たす。

周期窓を使い、整数全体へ

w_r(m+k p_r)=L_r(m)+k p_r

と延長する。L_r の単射性から、window内の像の剰余類は相異なり、w_r は整数全体の
全単射になる。また L_r が非負整数全体の置換なので、tailの像が作る有限のdefectはprefixの
個数と一致する。一周期で数えれば

sum_(i=0)^(p_r-1) (w_r(P_r+i)-(P_r+i))=0

となる。従って w_r はbalanced affine permutation、すなわち affine symmetric group
S-tilde_(p_r) の元である。

これは行の置換性と加法周期性という既知結果からの系である。今回の調査ではWythoff文献に
この包装を見つけていないが、独立した新規定理とはまだ主張しない。

機械検証

• line-bitset recurrenceと通常のmex動的計画法を N=20,80,180 の全cellで照合し、不一致なし。
• 行0から30を m=10^6 まで計算し、検出した最小候補周期とpreperiod後の6周期以上を照合。
• 全検出windowで、剰余類が置換になり、変位和が0になることを確認。
• 隣接行を共通周期へliftし、相対 affine permutationを計算。行0から30の全比較で、相対変換は
  windowの全剰余類を動かした。

代表的な周期列は

1,3,3,6,12,24,12,24,24,24,24,48,48,96,96,96,192,192,384,384,384,768,...

であり、OEIS A046875の既存計算と一致する。

観察

計算済みの非零行では、最小加法周期はすべて 3*2^k の形である。公開されている行53までの
データでも同じである。

Dyadic period予想：任意の r>=1 に対し、固定行の最小加法周期 p_r は 3*2^k の形である。

これは証明ではない。またperiod自体が急増し得るので、この予想だけでは高速算法にならない。
必要なのはperiod windowの短いgrammarまたはrenormalizationである。

反証済みの自然な表現論候補

Quiver Grassmannian / cluster character

quiver 1->2 のdimension (1,1) のindecomposable M のsubrepresentation dimensionsは
(0,0),(0,1),(1,1) で、(1,0) を欠く。一方、Wythoffの (1,1) からは
(0,0),(0,1),(1,0) のすべてへ動ける。semisimple representationを選ぶと一般weightで
任意のcoordinate-wise subdimensionが現れ、今度は不正な同時減少が入る。

従って固定representationのquiver Grassmannianはgame graphと一致せず、そのEuler characteristicを
使うcluster characterもこのsupport不一致を引き継ぐ。

Canonical / semicanonical basis

weight (a,b) のKostant partition数は min(a,b)+1。canonicalまたはsemicanonical basisへ
取り替えてもweight spaceのbasis数は変わらない。balanced weightでは一cellあたり線形個のdataが
残るため、basis変更だけではsubcubic化しない。

Demazure / 0-Hecke

lambda=a alpha_1+b alpha_2 に対する標準root-string長はcoroot pairing

2a-b, -a+2b, a+b

で決まる。一方、Wythoffの三方向の最大長は

a, b, min(a,b)

である。例えば (a,b)=(3,5) では前者が 1,7,8、後者が 3,5,3 となる。標準Demazure
operatorはreflection endpointで切れ、Wythoffはpositive-root coneの境界で切れるため一致しない。

反証済みの有限状態・自己相似候補

自然なZeckendorf prefix

両endpointへ同じFibonacci block C を足す (a,b)->(a+C,b+C) はdifferenceを保存する。
しかしrow 0では各色 h が (0,h) にあるため、difference h とendpoint h は色 h に
すでに使用されている。source birth (0,g,d=g) に対し、色を固定するshiftはtargetの
D_g に、色にも C を足すshiftはtarget endpointに阻まれる。

birth一点だけを保存するstate-dependent shiftを選んでも、合法性word全体は保存できない。
固定difference上のtarget色は互いに異なり非有界だが、row-zero anchorにより各target色 q は
常に q in D_q を満たすため、十分大きなtranslationでsourceとtargetのlegalityが食い違う。

bounded-hole summary

Cover(n,m,t) を「全色 h<t がfollowerに現れる」とすると、mexの定義から厳密に

Cover(n,m,t) iff t<=G(n,m)

である。従って完全なcover判定は元問題と同値である。

また各方向の先頭K個のholeだけを保存する案も、

G(1,3q)=3q+1, G(2,3q)=3q+2

という無限族で失敗する。3q>K+3 なら二位置の各方向の先頭K holeは同じだが、Grundy値は異なる。

bounded Coxeter update

行0から30の計算では、相対変換 w_(r+1) w_r^(-1) は共通period windowの全成分を動かした。
周期768の領域では768剰余類すべてが変化する。これは一般的no-go定理ではないが、隣接行を
O(1)個またはO(log r)個の単純反射で更新する最も直接的な案を有限データ上で否定する。

未解決と次の標的

未解決なのは次である。

• bit complexityでcubicを破れるか。
• 完全表を O(N^2 polylog N) で計算できるか。
• binary入力 (n,m) 一組を poly(log n+log m) 時間で計算できるか。
• 一般算法に対する自明な入出力下界を越える下界を証明できるか。

最小の次標的を次の形に固定する。

Affine dyadic-cover補題：WSGで色 h と行 r に生じる三禁止集合
D_h, B_h-r, L_r について、dyadic intervalがその和集合で完全被覆されるかを
polylog N sizeの注釈付きaffine cut-setから判定し、更新も polylog N で行える。

この補題があれば、最初の非被覆differenceを区間二分で求められ、一つの (r,h) を
polylog N で処理できる。全 O(N^2) 組に対して O(N^2 polylog N) が得られる。

表現論の役割は、ここで魔法のscalar invariantを探すことではない。合法手をA2 Boolean Hall
convolutionとして固定し、affine permutation / cut-setがそのBoolean zero-testをどこまで短く
表現できるかを問うことである。

主張の境界

• O(N^3/log N) はword-RAM上の証明済み上界であり、bit complexityの改善ではない。
• affine-tailは既知の行置換性と加法周期性から得た系で、新規性は未審査である。
• dyadic periodとbounded Coxeter updateは有限計算による観察である。
• cluster、canonical basis、Demazureの反証は記載した自然な直接対応を排除するが、非自明な
  decoderを伴うあらゆる表現論的方法を排除するものではない。
• 完全な計算量分類は未解決であり、このreportは解決宣言ではない。

@misc{sumire:2610.00003:34:v3,
  author = {hora},
  title = {{AI research report (2026-08-25): Wythoff Nim完全値の計算量}},
  year = {2026},
  note = {SUMIRE:2610.00003/34, v3},
  url = {https://sumire.aiformath.jp/p/2610.00003/n/34/v/3}
}