"""Proposition 22.5, steps 1 and 2.
Step 1 (Lie algebra level, integer matrices in so_{2m}): the exchanges U_{e_r-e_j} <-> U_{e_j-e_m}, j=n..m-1,
starting from Lie(U_desc) + Lie(max unipotent of H), character = pairing with f.
Step 2 (root level): interleaving with A_i=e_i, B_j=e_{n+j-1}, d=-1 inside D_m, auxiliary roots included;
final group = {positive degree for D} minus the root e_n-e_1."""
import sys, itertools
import numpy as np
import os; sys.path.insert(0,os.path.dirname(os.path.abspath(__file__)))
from exchange_checker import State
from fractions import Fraction
import sympy as sp
def run(n):
    m=2*n; r=n-1; N=2*m
    e=lambda i:i-1; f=lambda i:m+i-1
    def E(a,b):
        M=np.zeros((N,N),dtype=object); M[a,b]=1; return M
    def Em(i,j): return E(e(i),e(j))-E(f(j),f(i))      # e_i-e_j
    def Ep(i,j): return E(e(i),f(j))-E(e(j),f(i))      # e_i+e_j
    def br(X,Y): return X.dot(Y)-Y.dot(X)
    fn=sum((Em(i,i+1).T for i in range(1,r)),np.zeros((N,N),dtype=object))-Em(r,m).T+Ep(r,m).T
    fn=fn+sum((Em(j,j+1).T for j in range(n,m-1)),np.zeros((N,N),dtype=object))+Ep(m-1,m).T
    zeta=lambda X: Fraction(int(np.trace(X.dot(fn))),2)
    def span_contains(basis,X):
        A=sp.Matrix([list(b.flatten()) for b in basis]).T
        v=sp.Matrix(list(X.flatten()))
        return A.rank()==A.row_join(v).rank()
    def check_alg(basis,what,log):
        for a,b in itertools.combinations(basis,2):
            c=br(a,b)
            if c.any():
                if not span_contains(basis,c): log.append(what+': not closed')
                if zeta(c)!=0: log.append(what+': character not trivial on commutator')
    # initial algebra
    basis=[]
    for i in range(1,r+1):
        for j in range(i+1,m+1): basis+= [Em(i,j),Ep(i,j)]
    for j in range(n,m):
        for k in range(j+1,m): basis+=[Em(j,k),Ep(j,k)]
        basis.append(Em(j,m)+Ep(j,m))
    log=[]
    check_alg(basis,'initial',log)
    def same(a,b): return not (a-b).any()
    for j in range(n,m):
        x=Em(r,j); y=Em(j,m)
        U=[b for b in basis if not same(b,x)]
        if len(U)!=len(basis)-1: log.append('x not found')
        check_alg(U,f'step1 j={j} common',log)
        if zeta(x)!=0 or zeta(y)!=0: log.append('character on X or Y')
        c=br(x,y)
        if not span_contains(U,c) or zeta(c)==0: log.append(f'j={j}: pairing')
        for nm,v in (('X',x),('Y',y)):
            for u in U:
                c=br(v,u)
                if c.any():
                    if not span_contains(U,c): log.append(f'j={j}: {nm} does not normalize')
                    elif zeta(c)!=0: log.append(f'j={j}: {nm} changes character')
        basis=U+[y]
    # after step 1 the algebra should be spanned by root vectors
    roots_after=[]
    def v(*t):
        x=[0]*m
        for s,i in t: x[i-1]+=s
        return tuple(x)
    S=set()
    for i in range(1,r+1):
        for j in range(i+1,m+1):
            if not (i==r and n<=j<=m-1): S.add(v((1,i),(-1,j)))
            S.add(v((1,i),(1,j)))
    for j in range(n,m+1):
        for k in range(j+1,m+1): S.add(v((1,j),(-1,k))); S.add(v((1,j),(1,k)))
    def vec(rt):
        idx=[i+1 for i,t in enumerate(rt) if t]; i,j=idx
        if rt[i-1]==1 and rt[j-1]==-1: return Em(i,j)
        if rt[i-1]==1 and rt[j-1]==1: return Ep(i,j)
    ok_span=all(span_contains(basis,vec(rt)) for rt in S) and len(S)==len(basis)
    # step 2
    chi={v((1,i),(-1,i+1)) for i in range(1,r)}|{v((1,r),(-1,m)),v((1,r),(1,m)),v((1,m-1),(1,m))}|{v((1,j),(-1,j+1)) for j in range(n,m-1)}
    def is_root(x):
        nz=[t for t in x if t]; return len(nz)==2 and all(abs(t)==1 for t in nz)
    st=State(S,chi,is_root)
    A=lambda i:i; B=lambda j:n+j-1; d=-1; b=r-d
    for i in range(r-1,0,-1):
        for j in range(1,i-d+1):
            st.exchange(v((1,A(i)),(-1,B(j))),v((1,B(j)),(-1,A(i+1))),f'step2 ({i},{j})')
    D=lambda k: 2*(n-k) if k<n else 2*(m-k)
    exp=set()
    for i in range(1,m+1):
        for j in range(i+1,m+1):
            for a in (1,-1):
                for c in (1,-1):
                    if a*D(i)+c*D(j)>0: exp.add(v((a,i),(c,j)))
    delta=v((1,n),(-1,1))
    print(f'n={n}: step1 problems={len(log)} root span after step1={ok_span}; step2 problems={len(st.log)} '
          f'final = positive degree minus e_n-e_1: {st.S==exp-{delta}} (delta in positive degree: {delta in exp}); '
          f'character roots all of degree 2: {all(sum(x*D(i+1) for i,x in enumerate(rt))==2 for rt in chi)}',log[:3],st.log[:3])
for n in (2,3,4): run(n)