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 の対応表

重要なのは、表の上半分は単なる比喩ではなく完全な対応である一方、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は解決宣言ではない。