"""The presentation each orbifold symbol reads off, for o, 2222, 333 and *442. Checked exactly. For each group: the generators the symbol names, as actual isometries; every relation the symbol gives holds (and no proper power of a corner product is already 1); the generators generate (words for the lattice translations and every coset representative); and the Magic Theorem cost is 2. That these relations are ENOUGH (no others are needed) is the theorem of Conway's orbifold notation (Conway & Huson 2002; Coxeter & Moser ch. 4 list the same presentations); this script does not test it. Also for *442: no two elements generate it (it maps onto (Z/2)^3, checked on G/2Z^2), and two of the triangle's mirrors make only a finite kaleidoscope: a and b, or b and c, the 8 motions at a 4-corner; c and a, the 4 at the 2-corner. Coordinates: o and 2222 on Z^2 (any lattice will do); 333 as in p3_pairs.py; *442 on the square lattice. """ from fractions import Fraction as F from wallpaper import (Aff, T, rot_about, I2, mm, WGroup, find_words, evaluate, word_str, magic_cost, FiniteQuotient, fmt_fr) e = Aff(I2) def order(g, cap=12): h = g for k in range(1, cap + 1): if h == e: return k h = h * g return None def check(name, G, gens, relations, orders): G.check_is_group() for g in gens.values(): assert G.contains(g) for word, label in relations: assert evaluate(word, gens) == e, (name, label) for word, n, label in orders: # exact orders: g^n = 1 and no smaller power is 1 assert order(evaluate(word, gens)) == n, (name, label) targets = G.standard_generators() found = find_words(gens, targets) assert set(found) == set(targets), (name, set(targets) - set(found)) for lab, w in found.items(): assert evaluate(w, gens) == targets[lab] c = magic_cost(name) assert c == 2 longest = max(len(w) for w in found.values()) print(f"{name:>5}: relations hold; generators generate (longest word for a standard generator: {longest}); " f"cost {fmt_fr(c)}") return found # ---- o Go = WGroup("o", "p1", [Aff(I2)]) X, Y = T((1, 0)), T((0, 1)) check("o", Go, {"X": X, "Y": Y}, [([("X", 1), ("Y", 1), ("X", -1), ("Y", -1)], "XYX^-1Y^-1")], []) # ---- 2222: half-turns about (0,0), (1/2,0), (1/2,1/2), (0,1/2) mI = ((-1, 0), (0, -1)) G2 = WGroup("2222", "p2", [Aff(I2), Aff(mI)]) A = rot_about(mI, (0, 0)) B = rot_about(mI, (F(1, 2), 0)) C = rot_about(mI, (F(1, 2), F(1, 2))) D = rot_about(mI, (0, F(1, 2))) g2 = {"A": A, "B": B, "C": C, "D": D} check("2222", G2, g2, [([(k, 1), (k, 1)], f"{k}^2") for k in "ABCD"] + [([("A", 1), ("B", 1), ("C", 1), ("D", 1)], "ABCD")], [([(k, 1)], 2, k) for k in "ABCD"]) assert evaluate([("B", 1), ("A", 1)], g2) == T((1, 0)) # ---- 333 R = ((-1, -1), (1, 0)) R2 = mm(R, R) G3 = WGroup("333", "p3", [Aff(I2), Aff(R), Aff(R2)]) x = rot_about(R, (0, 0)) y = rot_about(R, (F(1, 3), F(1, 3))) z = rot_about(R, (F(-1, 3), F(2, 3))) g3 = {"x": x, "y": y, "z": z} check("333", G3, g3, [([(k, 1)] * 3, f"{k}^3") for k in "xyz"] + [([("x", 1), ("y", 1), ("z", 1)], "xyz")], [([(k, 1)], 3, k) for k in "xyz"]) # ---- *442: the reflections in the three sides of the triangle (0,0), (1/2,0), (1/2,1/2) D4 = [] r4 = ((0, -1), (1, 0)) M_ = I2 for k in range(4): D4 += [M_, mm(M_, ((1, 0), (0, -1)))] M_ = mm(r4, M_) G4 = WGroup("*442", "p4m", [Aff(Mx) for Mx in D4]) a = Aff(((1, 0), (0, -1))) # mirror y = 0 b = Aff(((0, 1), (1, 0))) # mirror y = x c = Aff(((-1, 0), (0, 1)), (1, 0)) # mirror x = 1/2 g4 = {"a": a, "b": b, "c": c} check("*442", G4, g4, [([(k, 1), (k, 1)], f"{k}^2") for k in "abc"] + [([("a", 1), ("b", 1)] * 4, "(ab)^4"), ([("b", 1), ("c", 1)] * 4, "(bc)^4"), ([("c", 1), ("a", 1)] * 2, "(ca)^2")], [([("a", 1), ("b", 1)], 4, "ab"), ([("b", 1), ("c", 1)], 4, "bc"), ([("c", 1), ("a", 1)], 2, "ca")]) # two of the triangle's mirrors: a finite kaleidoscope def finite_closure(gs, cap=100): seen = {e} frontier = [e] while frontier: nxt = [] for g in frontier: for s in gs: h = g * s if h not in seen: seen.add(h) nxt.append(h) frontier = nxt assert len(seen) <= cap return seen sizes = {"": len(finite_closure([a, b])), "": len(finite_closure([b, c])), "": len(finite_closure([c, a]))} assert sizes == {"": 8, "": 8, "": 4} print(f" two of the triangle's mirrors make a finite kaleidoscope: {sizes} " "(a, b and b, c meet at a 4-corner; c, a at the 2-corner)") # *442 needs three generators: G/2Z^2 (order 32) is not generated by any two of its elements, and its # abelianisation is (Z/2)^3 Q = FiniteQuotient(G4, 2) assert Q.N == 32 and not Q.some_k_generate(2) and Q.some_k_generate(3) comm = set() for i in range(Q.N): for j in range(Q.N): # commutator i j i^-1 j^-1 ii = next(k for k in range(Q.N) if Q.tab[i][k] == Q.e) jj = next(k for k in range(Q.N) if Q.tab[j][k] == Q.e) comm.add(Q.tab[Q.tab[Q.tab[i][j]][ii]][jj]) Cg = Q.generated(list(comm)) assert Q.N // len(Cg) == 8 and all(Q.tab[g][g] in Cg for g in range(Q.N)) # quotient of order 8, exponent 2 print(" *442 needs three generators: no two of the 32 elements of G/2Z^2 generate it; its abelianisation " "is (Z/2)^3 (at most 8 elements, as a, b, c of order 2 generate; at least 8, the abelianisation of G/2Z^2)") print("costs: " + "; ".join(f"{s} {fmt_fr(magic_cost(s))}" for s in ["o", "2222", "333", "442", "632", "**", "xx", "*x", "*2222", "22*", "22x", "2*22", "*442", "4*2", "*333", "3*3", "*632"])) assert all(magic_cost(s) == 2 for s in ["o", "2222", "333", "442", "632", "**", "xx", "*x", "*2222", "22*", "22x", "2*22", "*442", "4*2", "*333", "3*3", "*632"]) print("HEADLINE presentations: o [X,Y] = 1; 2222 A^2=B^2=C^2=D^2=ABCD=1; 333 x^3=y^3=z^3=xyz=1; " "*442 a^2=b^2=c^2=(ab)^4=(bc)^4=(ca)^2=1 -- all relations hold, all generate, each costs 2; " "*442 needs 3 generators")