# S1: search of abstract Theta for W_X = (Z/2)^n (A1^n), gamma_j^vee = 2 e_j, = v_j, # colours v in {-1,0,1}^n (type T split pairs {v, 2e_j - v}, v_j = 1) or 2e_j (type G). # Admissibility: belongs-iff-positive (Lemma 7.1.2 shape), Theta = minimal W- and (-1)-stable multiset, # Theta+ = Theta cap cone(colours), cone pointed, Theta = Theta+ |_| -Theta+ (7.1.5 part 1), # N_Theta(s_j) = D_j as multisets (7.1.5 part 2 + uniqueness), (E) cone(Theta+) cap C^- = 0. # Exponents: r = 1/2 for type-T colours (x = y), r_G for type G. Reports a_J(y) and real roots in (0, 3^-1/2]. from fractions import Fraction as Fr from itertools import product, combinations import sys, time def in_cone(v, gens): # exact LP-free test for small cases: v in cone(gens) via Fourier-Motzkin is heavy; use brute force # over nonnegative rational combinations is not finite -> use simplex-free approach: since all vectors # are in {-2..2}^n with n<=4, test by solving with all subsets of gens of size <= n (Caratheodory). n = len(v) for k in range(0, n + 1): for S in combinations(gens, k): sol = solve(S, v) if sol is not None and all(x >= 0 for x in sol): return True return False def solve(S, v): # find x >= ? with sum x_i S_i = v (exact; S linearly independent assumed or least-norm unique); return None if no solution n = len(v); k = len(S) if k == 0: return [] if all(x == 0 for x in v) else None M = [[Fr(S[j][i]) for j in range(k)] + [Fr(v[i])] for i in range(n)] r = 0; piv = [] for c in range(k): pr = next((i for i in range(r, n) if M[i][c] != 0), None) if pr is None: return None # dependent set; skip (Caratheodory uses independent sets) M[r], M[pr] = M[pr], M[r] M[r] = [x / M[r][c] for x in M[r]] for i in range(n): if i != r and M[i][c] != 0: f = M[i][c]; M[i] = [a - f * b for a, b in zip(M[i], M[r])] piv.append(c); r += 1 if any(M[i][k] != 0 for i in range(r, n)): return None return [M[i][k] for i in range(r)] def poly_add(a, b, s=1): c = dict(a) for k, v in b.items(): c[k] = c.get(k, 0) + s * v if c[k] == 0: del c[k] return c def roots_small(p): # real roots of polynomial p(y) (dict exp->coef) in (0, 0.5774], by sign changes on a fine grid + bisection f = lambda y: sum(c * y ** e for e, c in p.items()) out = []; N = 4000; a = 1e-9; prev = f(a) for i in range(1, N + 1): b = 0.57736 * i / N; cur = f(b) if prev == 0 or prev * cur < 0: out.append(round(b, 4)) prev = cur return out def run(n, rG, limit=None): E = [tuple(2 if k == j else 0 for k in range(n)) for j in range(n)] choices = [] for j in range(n): opts = [("G", (E[j],))] for rest in product((-1, 0, 1), repeat=n - 1): v = list(rest); v.insert(j, 1); v = tuple(v) w = tuple(2 * (k == j) - v[k] for k in range(n)) opts.append(("T", (v, w))) choices.append(opts) W = list(product((1, -1), repeat=n)) nadm = 0; found = []; seen = set(); t0 = time.time() for cfg in product(*choices): # colours as multiset: shared colours counted once, but {e_j, e_j} counted twice D = [c[1] for c in cfg] colours = {} for j, Dj in enumerate(D): for v in Dj: colours.setdefault(v, set()).add(j) # multiplicity of a colour vector: number of distinct colours with that valuation. # A pair {e_j,e_j} gives 2 colours; a vector shared by D_j and D_k is one colour. mult = {} for v, js in colours.items(): m = max(sum(1 for u in D[j] if u == v) for j in js) mult[v] = m # belongs iff positive pairing ok = True for v, js in colours.items(): pos = {k for k in range(n) if v[k] > 0} if pos != js: ok = False; break if not ok: continue # Theta multiset: orbit-max multiplicities, closed under negation Th = {} for v, m in mult.items(): for s in W: u = tuple(s[k] * v[k] for k in range(n)) Th[u] = max(Th.get(u, 0), m) for u in list(Th): mu = tuple(-x for x in u); Th[mu] = max(Th.get(mu, 0), Th[u]); Th[u] = Th[mu] gens = list(mult) key = tuple(sorted(Th.items())) + tuple(sorted(gens)) if key in seen: continue seen.add(key) # Theta+ = Theta cap cone(colours); pointed; partition P = {u: m for u, m in Th.items() if in_cone(u, gens)} if any(tuple(-x for x in u) in P for u in P): continue if any(u not in P and tuple(-x for x in u) not in P for u in Th): continue # 7.1.5 part 2: N(s_j) = D_j as multisets for j in range(n): N = {} for u, m in P.items(): su = tuple(-u[k] if k == j else u[k] for k in range(n)) if su not in P: N[u] = m Dm = {} for v in D[j]: Dm[v] = Dm.get(v, 0) + 1 if N != Dm: ok = False; break if not ok: continue # (E): cone(Theta+) cap C^- = 0 : test vertices of C^- rays (-e_k) and the cone; enough to check no # nonzero nonpositive vector is a nonneg combination -> check -sum e_k-type vectors over sign subsets bad = False for S in product((0, -1), repeat=n): if any(S) and in_cone(S, list(P)): bad = True; break if bad: continue nadm += 1 # a_J for all J x = lambda u: (1 if 2 in [abs(c) for c in u] and sum(abs(c) for c in u) == 2 else 0) res = [] for J in [J for k in range(1, n + 1) for J in combinations(range(n), k)]: a = {} for k in range(len(J) + 1): for S in combinations(J, k): term = {0: (-1) ** k} for u, m in P.items(): su = tuple(-u[t] if t in S else u[t] for t in range(n)) if su not in P: isG = sorted(abs(c) for c in u)[-1] == 2 e = int(2 * rG) if isG else 1 for _ in range(m): term = {kk + e: -vv for kk, vv in term.items()} a = poly_add(a, term) rts = roots_small(a) res.append((J, a, rts)) if rts: found.append((cfg, J, a, rts)) if nadm <= 6 or any(r[2] for r in res): print("adm#%d colours %s" % (nadm, sorted(mult.items()))) for J, a, rts in res: print(" J=%s a_J=%s roots in (0,3^-1/2]: %s" % (J, sorted(a.items()), rts)) if limit and nadm >= limit: break print("n=%d r_G=%s: admissible configurations %d, with a zero of some a_J at q>=3: %d (%.1fs)" % (n, rG, nadm, len(found), time.time() - t0)) if __name__ == "__main__": n = int(sys.argv[1]); rG = Fr(sys.argv[2]) if len(sys.argv) > 2 else Fr(1) run(n, rG)