"""Compute a translated untwisted KR principal exchange matrix in Bourbaki numbering. The reduced word is obtained by stripping the smallest available left descent. Positions in ``word`` are counted from one in ``mutable_positions``. Matrix and ``tau`` indices are zero based. No third-party packages are required. """ import argparse import json from collections import defaultdict, deque from fractions import Fraction def finite_cartan(kind, n): kind = kind.upper() allowed = ((kind == 'A' and n >= 1) or (kind in ('B', 'C') and n >= 2) or (kind == 'D' and n >= 4) or (kind == 'E' and n in (6, 7, 8)) or (kind == 'F' and n == 4) or (kind == 'G' and n == 2)) if not allowed: raise ValueError(f'Unsupported finite type {kind}{n}') matrix = [[2 * int(i == j) for j in range(n)] for i in range(n)] if kind == 'D': edges = [(i, i + 1) for i in range(n - 2)] + [(n - 3, n - 1)] elif kind == 'E': edges = [(0, 2), (1, 3)] + [(i, i + 1) for i in range(2, n - 1)] else: edges = [(i, i + 1) for i in range(n - 1)] for i, j in edges: matrix[i][j] = matrix[j][i] = -1 if kind == 'B': matrix[n - 1][n - 2] = -2 if kind == 'C': matrix[n - 2][n - 1] = -2 if kind == 'F': matrix[2][1] = -2 if kind == 'G': matrix[0][1] = -3 return matrix def reflect(root, i, cartan): result = list(root) result[i] -= sum(a * b for a, b in zip(cartan[i], root)) return tuple(result) def root_data(kind, n): matrix = finite_cartan(kind, n) simple = [tuple(int(i == j) for j in range(n)) for i in range(n)] roots = set(simple) queue = deque(simple) while queue: root = queue.popleft() for i in range(n): other = reflect(root, i, matrix) if other not in roots: roots.add(other) queue.append(other) positive = sorted(root for root in roots if min(root) >= 0) highest = max(positive, key=sum) relative = {0: Fraction(1)} queue = deque([0]) while queue: i = queue.popleft() for j in range(n): if i != j and matrix[i][j] and j not in relative: relative[j] = relative[i] * Fraction(matrix[j][i], matrix[i][j]) queue.append(j) lengths = [int(relative[i] / min(relative.values())) for i in range(n)] if any(c % t for c, t in zip(highest, lengths)): raise ArithmeticError('Highest coroot has a nonintegral coefficient') comarks = [c // t for c, t in zip(highest, lengths)] affine = [[2] + [-sum(comarks[i] * matrix[i][j] for i in range(n)) for j in range(n)]] for i, row in enumerate(matrix): affine.append([-sum(a * b for a, b in zip(row, highest))] + row) return affine, positive, (1, *highest), [1, *lengths], [1, *comarks] def schubert_word(positive, delta, cartan, r, chosen=None): inversions = set() for root in positive: for mode in range(root[r - 1]): inversions.add(tuple(a + mode * b for a, b in zip((0, *root), delta))) size = len(cartan) simple = [tuple(int(i == j) for j in range(size)) for i in range(size)] word = [] while inversions: descents = [i for i in range(size) if simple[i] in inversions] if not descents: raise ArithmeticError('Nonempty inversion set with no simple root') if chosen is not None and len(word) >= len(chosen): raise ValueError('Supplied word is too short') i = min(descents) if chosen is None else chosen[len(word)] if i not in descents: raise ValueError('The supplied expression is not a reduced word for this element') word.append(i) inversions.remove(simple[i]) inversions = {reflect(root, i, cartan) for root in inversions} if chosen is not None and len(chosen) != len(word): raise ValueError('Supplied word has incorrect length') return word def word_matrix(word, cartan): size = len(word) chains = defaultdict(list) for k, letter in enumerate(word): chains[letter].append(k) prev = [-1] * size nxt = [size] * size for chain in chains.values(): for a, b in zip(chain, chain[1:]): nxt[a], prev[b] = b, a matrix = [{} for _ in word] for k in range(size): if nxt[k] == size: continue row = matrix[k] row[nxt[k]] = -1 if prev[k] >= 0: row[prev[k]] = 1 for j in range(size): a = cartan[word[j]][word[k]] if j < k < nxt[j] < nxt[k] and a: row[j] = a if k < j < nxt[k] < nxt[j] and a: row[j] = -a return matrix, chains def mutate(rows, k): pivot = rows[k] for i, row in enumerate(rows): incident = row.get(k, 0) if i == k or not incident: continue for j, value in pivot.items(): if incident * value > 0: updated = row.get(j, 0) + abs(incident) * value if updated: row[j] = updated else: row.pop(j, None) row[k] = -incident rows[k] = {j: -value for j, value in pivot.items()} def reversal_path(word, chains): """CGL reversal in the fixed slots, indexed by occurrence rank per letter.""" seen = defaultdict(int) path = [] for letter in word: seen[letter] += 1 chain = chains[letter] path.extend(chain[:len(chain) - seen[letter]]) return path def residue_degrees(word, cartan, active): """LND degrees of shortened-word minors via reversal and the adapted chart.""" rows, chains = word_matrix(word, cartan) path = reversal_path(word, chains) path.extend(chains[active][:-1]) history = [] for k in path: history.append((k, rows[k])) mutate(rows, k) degrees = [0] * len(word) degrees[chains[active][-1]] = 1 for k, row in reversed(history): plus = sum(v * degrees[j] for j, v in row.items() if v > 0) minus = -sum(v * degrees[j] for j, v in row.items() if v < 0) degrees[k] = max(plus, minus) - degrees[k] if min(degrees) < 0: raise ArithmeticError('A regular minor has negative string degree') return degrees def translated_seed(cartan_type, rank, node, word=None): if not 1 <= node <= rank: raise ValueError('Invalid finite node') cartan, positive, delta, lengths, comarks = root_data(cartan_type, rank) word = schubert_word(positive, delta, cartan, node, word) if word[0] != node: raise ArithmeticError('Unexpected first descent') coroot = [int(i == node) for i in range(rank + 1)] origin = [1] for letter in word[1:]: coroot[letter] -= sum(c * cartan[j][letter] for j, c in enumerate(coroot)) origin.append(coroot[letter]) degrees = origin.copy() active = None if delta[node] > 1: residue_root = list(delta) residue_root[node] -= 1 for letter in word[1:]: residue_root = reflect(residue_root, letter, cartan) if min(residue_root) != 0 or sum(residue_root) != 1: raise ArithmeticError('Boundary root is not simple') active = residue_root.index(1) additions = [0] + residue_degrees(word[1:], cartan, active) degrees = [a + b for a, b in zip(origin, additions)] rows, chains = word_matrix(word, cartan) mutable = [k for k, row in enumerate(rows) if row] principal = [[rows[k].get(j, 0) for j in mutable] for k in mutable] tau = None if active is not None: tau = len(mutable) last = [] for row, k in zip(principal, mutable): entry = -sum(value * degrees[j] for j, value in rows[k].items()) row.append(entry) numerator = -lengths[word[k]] * entry if numerator % lengths[node]: raise ArithmeticError('Non-integral new row') last.append(numerator // lengths[node]) principal.append(last + [0]) for i, chain in chains.items(): if degrees[chain[-1]] != lengths[node] * comarks[i]: raise ArithmeticError('Terminal degree does not match the comark formula') return {'type': cartan_type.upper(), 'rank': rank, 'node': node, 'word': word, 'mutable_positions': [k + 1 for k in mutable], 'tau': tau, 'active': active, 'origin_degrees': origin, 'translated_degrees': degrees, 'principal': principal} if __name__ == '__main__': cli = argparse.ArgumentParser(description=__doc__) cli.add_argument('type') cli.add_argument('rank', type=int) cli.add_argument('node', type=int) args = cli.parse_args() print(json.dumps(translated_seed(args.type, args.rank, args.node)))