Grokking Group Multiplication with Cosets — part 7/7
Cleaned-text code points [83048, 87386). Bibliography omitted here; source.md includes it.
Grokking Group Multiplication with Cosets H.2. Other Examples of Coset Circuits Forming 4 2 0 2 4 0 10 20 30# of Permutations 140,000 Steps Coset S3 × S2(13245) S3 × S2(14235) S3 × S2(15234) S3 × S2(21345) S3 × S2(24135) S3 × S2(25134) S3 × S2(34125) S3 × S2(35124) S3 × S2(45123) S3 × S2 4 2 0 2 4 150,000 Steps 4 2 0 2 4 Pre-Activation Value 160,000 Steps (a) S3×S2 Left Permutations 4 2 0 2 4 0 10 20 30# of Permutations 140,000 Steps Coset S3 × S2(12354) S3 × S2(12534) S3 × S2(15234) S3 × S2(21345) S3 × S2(21354) S3 × S2(21534) S3 × S2(23145) S3 × S2(23154) S3 × S2(23415) S3 × S2 4 2 0 2 4 150,000 Steps 4 2 0 2 4 Pre-Activation Value 160,000 Steps (b) S3×S2 Right Permutations Figure 7. The formation of an S3×S2 neuron. 2.5 0 2.5 0 5 10 15 20 25# of Permutations 100,000 Steps Coset A4(12354) A4(12435) A4(12453) A4(12534) A4(12543) A4(13245) A4(13254) A4(23145) A4(23154) A4 2.5 0 2.5 150,000 Steps 2.5 0 2.5 200,000 Steps 2.5 0 2.5 Pre-Activation Value 250,000 Steps (a) A4 Left Permutations 2.5 0 2.5 0 5 10 15 20 25# of Permutations 100,000 Steps Coset (12354)A4 (12435)A4 (12453)A4 (12534)A4 (12543)A4 (14235)A4 (14253)A4 (41235)A4 (41253)A4 A4 2.5 0 2.5 150,000 Steps 2.5 0 2.5 200,000 Steps 2.5 0 2.5 Pre-Activation Value 250,000 Steps (b) A4 Right Permutations Figure 8. The formation of an A4 neuron. 25 Grokking Group Multiplication with Cosets I. Irreducible Representations I.1. Symmetric GroupS5 For a subgroupH≤G, we can investigate the Fourier transform of the indicator function 1H by looking at its evaluation at each irrep. Concretely, we first center the indicator function by defining f (g) = −|H| |G|, g̸∈H 1−|H| |G|, g∈H. By doing so, ˆf evaluates to 0 on the trivial representation ofG. Given an irrepρ∈ Irr(G), we first denote the value of the Fourier transform off atρ by ˆf|ρ. The contribution ofρ to ˆf is defined by the following: ∥ ˆf|ρ∥2 P δ∈Irr(G) ∥ ˆf|δ∥2 Here, we list all the conjugacy classes of subgroups ofS5 and how each irrep ofS5 contributes to their centered indicator function. We center the indicator function to remove the contribution of the trivial irrep, which is only based on the index of the subgroup. This step makes the contributions comparable. In the first column, we show the homomorphism type of each subgroup. Recall that two groupsG,G′ are homomorphic if there exists a functionf :G→G′ such that for allg, h∈G, f (gh) = f (g)f (h). Every group within a conjugacy class is a homomorphic, with the homomorphism of two subgroups H, H′ ofG given by conjugation by an element ofg∈G,h7→ghg−1. Two conjugacy classes of subgroups, however, may be homomorphic as groups, but no homomorphism can be given as conjugation by an element ofG. Different conjugacy classes of subgroups that are homomorphic are distinguished in the second column by an example set of generators. In the list: • Cn means cyclic groups of ordern. • Sn means the symmetric group ofn elements. • An means the alternating group of n elements,the subgroup ofSn consisting of even permutations. Recall than an “even” permutation is one that consists of an even number of transpositions. • D2n means then-gon dihedral group of order 2n (the symmetric group of regular polyhedron withn edges). • F20 means the Frobenius group of order 20, isomorphic toC4 ⋉C5 [10]. 26 Grokking Group Multiplication with Cosets Isomorphism type Generators Size (4, 1) (3 , 2) (3 , 12) (2 2, 1) (2 , 13) (1 5) C2 ⟨(12)⟩ 2 20.3% 25.4% 30.5% 17% 6.8% - C2 ⟨(12)(34)⟩ 2 13.6% 25.4% 20.3% 25.4% 13.6 1.7% C3 ⟨(123)⟩ 3 20.1% 12.8% 30.8% 12.8% 20.5% 2.6% C4 ⟨(1234)⟩ 4 13.6% 25.4% 20.3% 25.4% 13.6% 1.7% C2×C2 ⟨(12), (34)⟩ 4 27.6% 34.5% 20.7% 17.2% - - C2×C2 ⟨(12)(34), (13)(24)⟩ 4 13.8% 34.5% - 34.5% 13.8% 3.5% C5 ⟨(12345)⟩ 5 - 21.7% 52.2% 21.7% - 4.4% C6 ⟨(123), (45)⟩ 6 21.1% 26.3% 31.6% - 21.1% - S3 ⟨(123), (12)⟩ 6 42.1% 26.3% 31.6% - - - S3 5 ⟨(123), (12)(45)⟩ 6 21.1% 26.3% - 26.3% 21.1% 5.3% D8 ⟨(1234), (13)⟩ 8 28.6% 35.7% - 35.7% - - D10 ⟨(12345), (25)(34)⟩ 10 - 45.5% - 45.5% - 1% S3×S2 ⟨(123), (12), (45)⟩ 12 55.6% 44.4% - - - - A4 ⟨(12)(34), (123)⟩ 12 44.4% - - - 44.4% 11.2% F20 ⟨(12345), (2354)⟩ 20 - - - 100% - - S4 ⟨(12345), (12)⟩ 24 100% - - - - - A5 ⟨(12345), (123)⟩ 60 - - - - - 100% Table 5. Subgroups of S5 and the contribution of each irrep to their centered indicator function. 27