////////////////////////////////////////////////////////////////////// // // This is an implementation of the numbers game by Kimmo Eriksson, // as described by Bjorner/Brenti in Combinatorics of Coxeter Groups. // ////////////////////////////////////////////////////////////////////// #include #include #include #include #include #include #include using namespace std; const int DEBUG_VERBOSE = 0; const int DEBUG_VERBOSE_CP = 0; const int DATATYPE_BITLENGTH = 64; // corresponds to long long, used for calculating subsets via masks. This should be long enough to calculate through D_11... class CoxeterSystem { public: int size; int *coxeter_matrix; int automorphism_group_size; int *automorphism_group; int CoxeterSystem::equals(CoxeterSystem* cs); CoxeterSystem::CoxeterSystem(int n, int cm[], int ags, int ag[]); CoxeterSystem::CoxeterSystem(const CoxeterSystem& cs); int CoxeterSystem::get_exponent(int x, int y); int CoxeterSystem::get_automorphism(int i, int j); void CoxeterSystem::print_matrix(); virtual int right_multiply(int one_line[], int i); CoxeterSystem::~CoxeterSystem(); }; class TypeDCoxeterSystem : public CoxeterSystem { public: TypeDCoxeterSystem(int n, int cm[], int ags, int ag[]) : CoxeterSystem(n, cm, ags, ag) {} TypeDCoxeterSystem(const CoxeterSystem& cs) : CoxeterSystem(cs) {} virtual int right_multiply(int one_line[], int i); }; ////////////////////////////////////////////////////////////////////// // // Coxeter matricies for various groups: // ////////////////////////////////////////////////////////////////////// // Type A: Linear... // A_2: *--* // 0 1 static int aa2[] = { 0,3, 3,0 }; static int ga2[] = { 1, 0 }; static CoxeterSystem A2 = CoxeterSystem(2, aa2, 1, ga2); // A_3: *--*--* // 0 1 2 static int aa3[] = { 0,3,2, 3,0,3, 2,3,0 }; static int ga3[] = { 2, 1, 0 }; static CoxeterSystem A3 = CoxeterSystem(3, aa3, 1, ga3); // A_4: *--*--*--* // 0 1 2 3 static int aa4[] = { 0,3,2,2, 3,0,3,2, 2,3,0,3, 2,2,3,0 }; static int ga4[] = { 3, 2, 1, 0 }; static CoxeterSystem A4 = CoxeterSystem(4, aa4, 1, ga4); static int aa5[] = { 0,3,2,2,2, 3,0,3,2,2, 2,3,0,3,2, 2,2,3,0,3, 2,2,2,3,0 }; static int ga5[] = { 4, 3, 2, 1, 0 }; static CoxeterSystem A5 = CoxeterSystem(5, aa5, 1, ga5); static int aa6[] = { 0,3,2,2,2,2, 3,0,3,2,2,2, 2,3,0,3,2,2, 2,2,3,0,3,2, 2,2,2,3,0,3, 2,2,2,2,3,0 }; static int ga6[] = { 5, 4, 3, 2, 1, 0 }; static CoxeterSystem A6 = CoxeterSystem(6, aa6, 1, ga6); // A_7: *--*--*--*--*--*--* // 0 1 2 3 4 5 6 static int aa7[] = { 0,3,2,2,2,2,2, 3,0,3,2,2,2,2, 2,3,0,3,2,2,2, 2,2,3,0,3,2,2, 2,2,2,3,0,3,2, 2,2,2,2,3,0,3, 2,2,2,2,2,3,0 }; static int ga7[] = { 6, 5, 4, 3, 2, 1, 0 }; static CoxeterSystem A7 = CoxeterSystem(7, aa7, 1, ga7); static int aa8[] = { 0,3,2,2,2,2,2,2, 3,0,3,2,2,2,2,2, 2,3,0,3,2,2,2,2, 2,2,3,0,3,2,2,2, 2,2,2,3,0,3,2,2, 2,2,2,2,3,0,3,2, 2,2,2,2,2,3,0,3, 2,2,2,2,2,2,3,0 }; static int ga8[] = { 7, 6, 5, 4, 3, 2, 1, 0 }; static CoxeterSystem A8 = CoxeterSystem(8, aa8, 1, ga8); static int aa9[] = { 0,3,2,2,2,2,2,2,2, 3,0,3,2,2,2,2,2,2, 2,3,0,3,2,2,2,2,2, 2,2,3,0,3,2,2,2,2, 2,2,2,3,0,3,2,2,2, 2,2,2,2,3,0,3,2,2, 2,2,2,2,2,3,0,3,2, 2,2,2,2,2,2,3,0,3, 2,2,2,2,2,2,2,3,0 }; static int ga9[] = { 8, 7, 6, 5, 4, 3, 2, 1, 0 }; static CoxeterSystem A9 = CoxeterSystem(9, aa9, 1, ga9); static int aa10[] = { 0,3,2,2,2,2,2,2,2,2, 3,0,3,2,2,2,2,2,2,2, 2,3,0,3,2,2,2,2,2,2, 2,2,3,0,3,2,2,2,2,2, 2,2,2,3,0,3,2,2,2,2, 2,2,2,2,3,0,3,2,2,2, 2,2,2,2,2,3,0,3,2,2, 2,2,2,2,2,2,3,0,3,2, 2,2,2,2,2,2,2,3,0,3, 2,2,2,2,2,2,2,2,3,0 }; static int ga10[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }; static CoxeterSystem A10 = CoxeterSystem(10, aa10, 1, ga10); static int aa11[] = { 0,3,2,2,2,2,2,2,2,2,2, 3,0,3,2,2,2,2,2,2,2,2, 2,3,0,3,2,2,2,2,2,2,2, 2,2,3,0,3,2,2,2,2,2,2, 2,2,2,3,0,3,2,2,2,2,2, 2,2,2,2,3,0,3,2,2,2,2, 2,2,2,2,2,3,0,3,2,2,2, 2,2,2,2,2,2,3,0,3,2,2, 2,2,2,2,2,2,2,3,0,3,2, 2,2,2,2,2,2,2,2,3,0,3, 2,2,2,2,2,2,2,2,2,3,0 }; static int ga11[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }; static CoxeterSystem A11 = CoxeterSystem(11, aa11, 1, ga11); static int aa12[] = { 0,3,2,2,2,2,2,2,2,2,2,2, 3,0,3,2,2,2,2,2,2,2,2,2, 2,3,0,3,2,2,2,2,2,2,2,2, 2,2,3,0,3,2,2,2,2,2,2,2, 2,2,2,3,0,3,2,2,2,2,2,2, 2,2,2,2,3,0,3,2,2,2,2,2, 2,2,2,2,2,3,0,3,2,2,2,2, 2,2,2,2,2,2,3,0,3,2,2,2, 2,2,2,2,2,2,2,3,0,3,2,2, 2,2,2,2,2,2,2,2,3,0,3,2, 2,2,2,2,2,2,2,2,2,3,0,3, 2,2,2,2,2,2,2,2,2,2,3,0 }; static int ga12[] = { 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }; static CoxeterSystem A12 = CoxeterSystem(12, aa12, 1, ga12); // Type B: Linear, 4-edge on the left... // B_3: *-4-*--*--*--*--* // 0 1 2 3 4 4 static int ab3[] = { 0,4,2, 4,0,3, 2,3,0 }; static CoxeterSystem B3 = CoxeterSystem(3, ab3, 0, NULL); // B_4: *-4-*--*--*--*--* // 0 1 2 3 4 4 static int ab4[] = { 0,4,2,2, 4,0,3,2, 2,3,0,3, 2,2,3,0 }; static CoxeterSystem B4 = CoxeterSystem(4, ab4, 0, NULL); // B_5: *-4-*--*--*--*--* // 0 1 2 3 4 5 static int ab5[] = { 0,4,2,2,2, 4,0,3,2,2, 2,3,0,3,2, 2,2,3,0,3, 2,2,2,3,0 }; static CoxeterSystem B5 = CoxeterSystem(5, ab5, 0, NULL); // B_6: *-4-*--*--*--*--* // 0 1 2 3 4 5 static int ab6[] = { 0,4,2,2,2,2, 4,0,3,2,2,2, 2,3,0,3,2,2, 2,2,3,0,3,2, 2,2,2,3,0,3, 2,2,2,2,3,0 }; static CoxeterSystem B6 = CoxeterSystem(6, ab6, 0, NULL); // B_7: *-4-*--*--*--*--*--* // 0 1 2 3 4 5 6 static int ab7[] = { 0,4,2,2,2,2,2, 4,0,3,2,2,2,2, 2,3,0,3,2,2,2, 2,2,3,0,3,2,2, 2,2,2,3,0,3,2, 2,2,2,2,3,0,3, 2,2,2,2,2,3,0 }; static CoxeterSystem B7 = CoxeterSystem(7, ab7, 0, NULL); // F_4: *---*-4-*--* // 0 1 2 3 static int af4[] = { 0,3,2,2, 3,0,4,2, 2,4,0,3, 2,2,3,0 }; static CoxeterSystem F4 = CoxeterSystem(4, af4, 0, NULL); // G_2: *-6-* // 0 1 static int ag2[] = { 0,6, 6,0 }; static CoxeterSystem G2 = CoxeterSystem(2, ag2, 0, NULL); // Type D: Branch on the left, 0, 1 are branch points connected to 2, then linear... // D_8: 1 // *--- // *---*--*--*--*--*--* // 0 2 3 4 5 6 7 static int ad3[] = { 0,2,3, 2,0,3, 3,3,0 }; static int gd3[] = { 1, 0, 2 }; static TypeDCoxeterSystem D3 = TypeDCoxeterSystem(3, ad3, 1, gd3); static int ad4[] = { 0,2,3,2, 2,0,3,2, 3,3,0,3, 2,2,3,0 }; static int gd4[] = { 1, 0, 2, 3 }; static TypeDCoxeterSystem D4 = TypeDCoxeterSystem(4, ad4, 1, gd4); static int ad5[] = { 0,2,3,2,2, 2,0,3,2,2, 3,3,0,3,2, 2,2,3,0,3, 2,2,2,3,0 }; static int gd5[] = { 1, 0, 2, 3, 4 }; static TypeDCoxeterSystem D5 = TypeDCoxeterSystem(5, ad5, 1, gd5); // D_6: 0 // *-- // *--*--*--*--* // 1 2 3 4 5 // // Automorphisms: interchange 0<->1, fix all others. static int ad6[] = { 0,2,3,2,2,2, 2,0,3,2,2,2, 3,3,0,3,2,2, 2,2,3,0,3,2, 2,2,2,3,0,3, 2,2,2,2,3,0 }; static int gd6[] = { 1, 0, 2, 3, 4, 5 }; static TypeDCoxeterSystem D6 = TypeDCoxeterSystem(6, ad6, 1, gd6); // D_7: 0 // *-- // *--*--*--*--*--* // 1 2 3 4 5 6 // // Automorphisms: interchange 0<->1, fix all others. // Parabolic subgroups: must use 6 (or get D_6). static int ad7[] = { 0,2,3,2,2,2,2, 2,0,3,2,2,2,2, 3,3,0,3,2,2,2, 2,2,3,0,3,2,2, 2,2,2,3,0,3,2, 2,2,2,2,3,0,3, 2,2,2,2,2,3,0 }; static int gd7[] = { 1, 0, 2, 3, 4, 5, 6 }; static TypeDCoxeterSystem D7 = TypeDCoxeterSystem(7, ad7, 1, gd7); // D_8: 0 // *-- // *--*--*--*--*--*--* // 1 2 3 4 5 6 7 // // Automorphisms: interchange 0<->1, fix all others. // Parabolic subgroups: must use 0 (or get A_7), must use 7 (or get D_7), must use 6/7 (or get D_6). static int ad8[] = { 0,2,3,2,2,2,2,2, 2,0,3,2,2,2,2,2, 3,3,0,3,2,2,2,2, 2,2,3,0,3,2,2,2, 2,2,2,3,0,3,2,2, 2,2,2,2,3,0,3,2, 2,2,2,2,2,3,0,3, 2,2,2,2,2,2,3,0}; static int gd8[] = { 1, 0, 2, 3, 4, 5, 6, 7 }; static TypeDCoxeterSystem D8 = TypeDCoxeterSystem(8, ad8, 1, gd8); static int ad9[] = { 0,2,3,2,2,2,2,2,2, 2,0,3,2,2,2,2,2,2, 3,3,0,3,2,2,2,2,2, 2,2,3,0,3,2,2,2,2, 2,2,2,3,0,3,2,2,2, 2,2,2,2,3,0,3,2,2, 2,2,2,2,2,3,0,3,2, 2,2,2,2,2,2,3,0,3, 2,2,2,2,2,2,2,3,0 }; static int gd9[] = { 1, 0, 2, 3, 4, 5, 6, 7, 8 }; static TypeDCoxeterSystem D9 = TypeDCoxeterSystem(9, ad9, 1, gd9); static int ad10[] = { 0,2,3,2,2,2,2,2,2,2, 2,0,3,2,2,2,2,2,2,2, 3,3,0,3,2,2,2,2,2,2, 2,2,3,0,3,2,2,2,2,2, 2,2,2,3,0,3,2,2,2,2, 2,2,2,2,3,0,3,2,2,2, 2,2,2,2,2,3,0,3,2,2, 2,2,2,2,2,2,3,0,3,2, 2,2,2,2,2,2,2,3,0,3, 2,2,2,2,2,2,2,2,3,0 }; static int gd10[] = { 1, 0, 2, 3, 4, 5, 6, 7, 8, 9 }; static TypeDCoxeterSystem D10 = TypeDCoxeterSystem(10, ad10, 1, gd10); // E_6: 5 // * // *--*--*--*--* // 0 1 2 3 4 // // Automorphisms: interchange 0<->4, 1<->3, fix 2 and 5. static int ae6[] = { 0,3,2,2,2,2, 3,0,3,2,2,2, 2,3,0,3,2,3, 2,2,3,0,3,2, 2,2,2,3,0,2, 2,2,3,2,2,0 }; static int ge6[] = { 4, 3, 2, 1, 0, 5 }; static CoxeterSystem E6 = CoxeterSystem(6, ae6, 1, ge6); // TEMPORARY: to compare with coxeter 1.0. // E_6: 2 // * // *--*--*--*--* // 0 1 3 4 5 6 // // Automorphisms: interchange 1<->6, 3<->5, fix 2 and 4. //static int ae6[] = { 0,2,2,2,2,2,2, // 2,0,2,3,2,2,2, // 2,2,0,2,3,2,2, // 2,3,2,0,3,2,2, // 2,2,3,3,0,3,2, // 2,2,2,2,3,0,3, // 2,2,2,2,2,3,0 }; //static int ge6[] = { 0, 6, 2, 5, 4, 3, 1 }; //static CoxeterSystem E6 = CoxeterSystem(7, ae6, 1, ge6); // E_7: 5 // * // *--*--*--*--*--* // 0 1 2 3 4 6 // // Parabolic subgroups: must use 0 (or get D_6), 6 (or get E_6) static int ae7[] = { 0,3,2,2,2,2,2, 3,0,3,2,2,2,2, 2,3,0,3,2,3,2, 2,2,3,0,3,2,2, 2,2,2,3,0,2,3, 2,2,3,2,2,0,2, 2,2,2,2,3,2,0 }; static CoxeterSystem E7 = CoxeterSystem(7, ae7, 0, NULL); // E_8: 5 // * // *--*--*--*--*--*--* // 0 1 2 3 4 6 7 // // Parabolic subgroups: must use 0 (or get D_7), 6/7 (or get E_6), 7 (or get E_7), 5 (or get A_7) static int ae8[] = { 0,3,2,2,2,2,2,2, 3,0,3,2,2,2,2,2, 2,3,0,3,2,3,2,2, 2,2,3,0,3,2,2,2, 2,2,2,3,0,2,3,2, 2,2,3,2,2,0,2,2, 2,2,2,2,3,2,0,3, 2,2,2,2,2,2,3,0 }; static CoxeterSystem E8 = CoxeterSystem(8, ae8, 0, NULL); class CoxeterNames { public: map names; CoxeterNames::CoxeterNames() { names["A2"] = &A2; names["A3"] = &A3; names["A4"] = &A4; names["A5"] = &A5; names["A6"] = &A6; names["A7"] = &A7; names["A8"] = &A8; names["A9"] = &A9; names["A10"] = &A10; names["A11"] = &A11; names["A12"] = &A12; names["B3"] = &B3; names["B4"] = &B4; names["B5"] = &B5; names["B6"] = &B6; names["B7"] = &B7; names["D3"] = &D3; names["D4"] = &D4; names["D5"] = &D5; names["D6"] = &D6; names["D7"] = &D7; names["D8"] = &D8; names["D9"] = &D9; names["D10"] = &D10; names["E6"] = &E6; names["E7"] = &E7; names["E8"] = &E8; names["F4"] = &F4; names["G2"] = &G2; } };