#!/usr/bin/env python3 """Exact finite checks for Definability and Lifting in Model Subgroupoids. Python 3 standard library only. No random sampling or floating-point algebra. Run: python3 finite_lifting.py > finite_results.json """ from collections import Counter, deque from fractions import Fraction from itertools import product import json import math class FiniteGroup: def __init__(self, elements, operation, identity): self.elements = [identity] + [x for x in elements if x != identity] self.index = {x: i for i, x in enumerate(self.elements)} self.n = len(self.elements) self.mul = [[self.index[operation(a, b)] for b in self.elements] for a in self.elements] self.inv = [next(j for j in range(self.n) if self.mul[i][j] == self.mul[j][i] == 0) for i in range(self.n)] def closure(self, generators): generators = tuple(set(generators) | {self.inv[g] for g in generators}) found, queue = {0}, deque([0]) while queue: x = queue.popleft() for g in generators: y = self.mul[x][g] if y not in found: found.add(y) queue.append(y) return frozenset(found) def subgroups(self): known = {frozenset([0]): ()} queue = deque(known) while queue: subgroup = queue.popleft() generators = known[subgroup] remaining = set(range(self.n)) - set(subgroup) while remaining: g = min(remaining) # Elements in one right coset generate the same overgroup. remaining.difference_update(self.mul[h][g] for h in subgroup) overgroup = self.closure(generators + (g,)) if overgroup not in known: known[overgroup] = generators + (g,) queue.append(overgroup) return sorted(known, key=lambda h: (len(h), tuple(sorted(h)))) def conjugate(self, subgroup, g): return frozenset(self.mul[self.mul[g][h]][self.inv[g]] for h in subgroup) def normalizer(self, subgroup): return frozenset(g for g in range(self.n) if self.conjugate(subgroup, g) == subgroup) def center(self): return frozenset(g for g in range(self.n) if all(self.mul[g][h] == self.mul[h][g] for h in range(self.n))) def central_free_data(group): center = group.center() all_subgroups = group.subgroups() allowed = {h for h in all_subgroups if h & center == {0}} rows = [] while allowed: subgroup = min(allowed, key=lambda h: (len(h), tuple(sorted(h)))) conjugates = {group.conjugate(subgroup, g) for g in range(group.n)} allowed.difference_update(conjugates) normalizer = group.normalizer(subgroup) rows.append({ 'subgroup_order': len(subgroup), 'conjugacy_class_size': len(conjugates), 'normalizer_order': len(normalizer), 'automorphism_order': len(normalizer) // len(subgroup), 'multiplicity_weight': group.n // (len(center) * len(subgroup)), }) return { 'group_order': group.n, 'center_order': len(center), 'all_subgroup_count': len(all_subgroups), 'allowed_subgroup_classes': rows, } def sl2(p): elements = [(a, b, c, d) for a, b, c, d in product(range(p), repeat=4) if (a*d - b*c) % p == 1] def operation(x, y): a, b, c, d = x e, f, g, h = y return ((a*e+b*g) % p, (a*f+b*h) % p, (c*e+d*g) % p, (c*f+d*h) % p) return FiniteGroup(elements, operation, (1, 0, 0, 1)) def heisenberg(p, r): elements = list(product(range(p), repeat=2*r+1)) def operation(x, y): z = [(x[i]+y[i]) % p for i in range(2*r)] z.append((x[-1]+y[-1]+sum(x[i]*y[r+i] for i in range(r))) % p) return tuple(z) return FiniteGroup(elements, operation, (0,) * (2*r+1)) def semigroup_data(weights, limit): reachable = [False] * (limit+1) reachable[0] = True for m in range(1, limit+1): reachable[m] = any(m >= w and reachable[m-w] for w in weights) return { 'weights': weights, 'computed_through': limit, 'positive_members': [m for m in range(1, limit+1) if reachable[m]], } def series_counts(rows, limit): # The class series is a product (1-z^w)^(-1), one factor per class. coefficients = [0] * (limit+1) coefficients[0] = 1 for row in rows: w = row['multiplicity_weight'] for m in range(w, limit+1): coefficients[m] += coefficients[m-w] # If M(z)=exp(sum c_w z^w), then n M_n=sum_w w c_w M_(n-w). exponent = Counter() for row in rows: exponent[row['multiplicity_weight']] += Fraction(1, row['automorphism_order']) mass = [Fraction(0)] * (limit+1) mass[0] = Fraction(1) for m in range(1, limit+1): mass[m] = sum((w*c*mass[m-w] for w, c in exponent.items() if w <= m), Fraction(0)) / m return {str(m): {'isomorphism_classes': coefficients[m], 'mass': str(mass[m])} for m in range(limit+1) if coefficients[m]} def isotropic_count(p, r, k): numerator = math.prod(p**(2*r-i)-p**i for i in range(k)) denominator = math.prod(p**k-p**i for i in range(k)) assert numerator % denominator == 0 return numerator // denominator def run(): sl = central_free_data(sl2(5)) assert sl['group_order'] == 120 and sl['center_order'] == 2 assert sorted((row['subgroup_order'], row['multiplicity_weight'], row['automorphism_order']) for row in sl['allowed_subgroup_classes']) == [ (1, 60, 120), (3, 20, 4), (5, 12, 4)] sl['multiplicities'] = semigroup_data([12, 20, 60], 100) sl['series'] = series_counts(sl['allowed_subgroup_classes'], 100) members = set(sl['multiplicities']['positive_members']) assert all(m in members for m in range(32, 101, 4)) assert all(m not in members for m in [4, 8, 16, 28]) h = central_free_data(heisenberg(3, 1)) assert h['group_order'] == 27 and h['center_order'] == 3 summary = Counter((row['subgroup_order'], row['multiplicity_weight'], row['automorphism_order']) for row in h['allowed_subgroup_classes']) assert summary == Counter({(1, 9, 27): 1, (3, 3, 3): 4}) h['series'] = series_counts(h['allowed_subgroup_classes'], 27) h['isotropic_counts'] = {str(k): isotropic_count(3, 1, k) for k in range(2)} cyclic = {} for p in [2, 3, 5]: n = p*p group = FiniteGroup(list(range(n)), lambda x, y: (x+y) % n, 0) subgroup_n = frozenset(range(0, n, p)) weights = sorted({n // (p*len(l)) for l in group.subgroups() if l & subgroup_n == {0}}) assert weights == [p] cyclic[str(p)] = weights return {'method': 'Exact subgroup enumeration from multiplication tables', 'sl2_f5': sl, 'heisenberg_3_rank1': h, 'cyclic_prime_square': cyclic, 'heisenberg_formula_counts': { f'p={p},r={r}': [isotropic_count(p, r, k) for k in range(r+1)] for p, r in [(3, 2), (3, 3), (5, 2)]}} if __name__ == '__main__': print(json.dumps(run(), indent=2, sort_keys=True))