What are some real-world applications of cyclic groups and Galois fields?

[jimmycricket]

Can anybody name some real world applications of group theory? I would be particularly interested to hear any uses of cyclic groups to solve everyday problems one could encounter.

 

[Useful nucleus]

Can anybody name some real world applications of group theory? I would be particularly interested to hear any uses of cyclic groups to solve everyday problems one could encounter.

You can study kinship systems in societies using group theory based on marriage rules, as Andre Weil and Levi-Strauss did. Or may be you can use group theory to study phonons and spontaneous polarization in ferroelectric materials and use your study to design a ferroelectric RAM for modern fast computers.

The number of applications that can be listed for this beautiful theory are uncountable!

 

[lpetrich]

Classification of spatial symmetries, like crystal structures and symmetries of molecules.

There are two main types of spatial-symmetry groups: point groups and space groups.

Point groups: for rotations / reflections R, x' = R.x
The R's are matrices, of course.

Space groups: for R and translations D, x' = R.x + D
As a bigger matrix:
R D
0 1
Important for crystal structure.

Some group theory will help elucidate these properties.

The R/R groups have homomorphisms from matrices R to their determinants, the parity values.

• Pure rotation = 1
• Reflection = -1

The kernel of this homomorphism is the pure rotations in a R/R group. It's easy to show that this quotient group is isomorphic to the cyclic group Z2.

Likewise, the (R,D) combinations of space groups have a homomorphism onto the group of R values, with a kernel being a pure translation group. The group of R's is thus the quotient group of this combination.Discrete point groups for 1, 2, and 3 dimensions:

1D:
Rotation = {identity} or {1}
With reflection = {identity, inversion} or {1,-1}
# groups: 2

2D:
Rotation = infinite family of cyclic groups C(n)
With reflection = infinite family of dihedral groups D(n)
# groups: 2 infinite families

3D:
Rotation = 2 axial-group infinite families C(n), D(n), 3 quasi-spherical groups T, O, I
With reflection = 5 axial-group infinite families C(n,h), S(2n), C(n,v), D(n,h), D(n,d), 4 quasi-spherical groups Th, Td, Oh, Ih
# groups = 7 axial-group infinite families, 7 quasi-spherical groups
Axial = prismatic, etc. Quasi-spherical = ?

All n-D point groups are subgroups of SO(n) (alll pure rotations) or O(n) (all rotations and reflections), both continuous.Discrete space group. All elements (R,D) have the form (R,D(lattice)+D(R)) where D(identity) = 0. A group of R's may have several different sets of values of D(R).

Only certain groups of the R's are possible in discrete space groups; these are the crystallographic groups. That's according to the "crystallographic restriction theorem". For 2D, there are 10 of them: C1, C2, C3, C4, C6, D1, D2, D3, D4, D6, and for 3D, there are 32 of them: several axial groups and all the quasi-spherical ones except I, Ih, the icosahedral ones.

For 1D, there are only two discrete space groups, one for R group {1} and the other for R group {1,-1}.

For 2D and a 1D lattice, one gets the 7 "frieze groups", with R groups C1, C2, D1, D2. The 3D axial point groups can be interpreted as wrapped-around frieze groups.

For 2D and a 2D lattice, one gets the 17 "wallpaper groups", with all the crystallographic R groups.

For 3D and a 1D lattice, one gets some infinite families associated with the 3D axial point groups. They can be interpreted as wrapped-around wallpaper groups. Specializing to the crystallographic point groups gets about 70 "rod groups".

For 3D and a 2D lattice, one gets about 70 "layer groups".

For 3D and a 3D lattice, one gets a bit more than 200 groups.

All n-D space groups are subgroups of Euc(n), the Euclidean group: all n-D rotations, reflections, translations, and combinations of them.

 

[lpetrich]

Wikipedia articles: Point group, Space group

How many groups by dimension:

Point groups:
1D: 2
2D: 2(inf) -- crys: 10
3D: 7(inf) + 7 -- crys: 32
The "crys" is crystallographic groups, those that can be symmetries of lattices.
The (inf) refers to infinite families.

Space groups:
1,1D: 2
2,1D: 7 -- frieze groups
2,2D: 17 -- wallpaper groups
3,1D: 13(inf) -- crys: 75 -- rod groups
3,2D: 80 -- layer groups
3,3D: 230 -- including 11 pairs of mirror-image groups

 

[lpetrich]

Some more uses of group theory.

Many groups are continuous, and many of them can be generated from powers of elements arbitrarily close to the identity: Lie groups. Rotation groups are Lie groups, as are translation groups and translation-rotation groups. Reflection introduces the complication of elements that cannot be obtained from such elements. Here are 2D rotations:
$$ D_{rot}(\theta) = \begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix} $$
Here are 2D reflections:
$$ D_{rfl}(\theta) = \begin{pmatrix} \cos\theta & \sin\theta \\ \sin\theta & -\cos\theta \end{pmatrix} $$
For small $\theta$, we get for the rotations
$$ D_{rot}(\theta) = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} + \theta \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix} + \cdots $$
The second matrix in this expression generates the group's "Lie algebra". More generally,
$$ D = \exp(a \cdot L) $$
where D is the group matrices, a is a vector of parameters, one per Lie-algebra generator, and L is the Lie-algebra generators. It can be shown that the Lie algebra of a Lie group is closed under commutation: $[L_i,L_j] = f_{ij}{}^k L_k$, where the f's are the algebra's "structure constants".

It's often much easier to work with Lie algebras than with the groups that they generate, and many of those groups' properties are known from their algebras.

If an algebra does not have subalgebras with certain properties, then it is called a "semisimple" one, and every semisimple one is a sum of "simple" ones. All the simple ones are known. They are 4 infinite families, A(n), B(n), C(n), D(n), and 5 "exceptional" ones, G2, F4, E6, E7, E8. I've written some code for doing some operations with semisimple ones: SemisimpleLieAlgebras.zip It's in Mathematica, Python, and C++.

A(n) -- SU(n+1) -- special unitary matrices
B(n) -- SO(2n+1) -- odd special orthogonal matrices
C(n) -- Sp(2n) -- "symplectic" matrices
D(n) -- SO(2n) -- even special orthogonal matrices
Special: determinant = 1
Orthogonal = like rotation
Unitary = like orthogonal, but generalized to complex numbers in a certain way
All unitary matrices with some dimensions: U(n) = SU(n) * U(1)These algebras have a lot of applications in quantum mechanics, like decomposing by angular momentum, and particle physics, where the gauge-symmetry groups are all Lie groups. Each algebra generator corresponds to a member of the symmetry's gauge-particle multiplet. Symmetry breaking involves getting subalgebras from algebras, and there are a number of candidate Grand Unified Theory algebras that have been proposed.

The Standard Model has gauge symmetry SU(3) * SU(2) * U(1) -- QCD, weak isospin, weak hypercharge

I've seen these gauge-symmetry algebras proposed for GUT's: SU(5), SU(6), SO(6)*SO(4) ~ SU(4)*SU(2)*SU(2), SO(10), SU(3)^3, E6, E8One can extend Lie algebras to include closure under anticommutation as well as commutation, getting "superalgebras". One adds anticommuting elements Q to normal ones L. Schematically, their commutation is [L,L] = L, [L,Q] = Q, {Q,Q} = L. If one adds anticommuting generators to the rotation-translation algebra, those generators are supersymmetry (SUSY) generators. So supersymmetry is a sort of extension of space-time symmetry.

 

[lpetrich]

Groups form the basis of other abstract-algebra objects.

An algebraic field is a set of entities with binary operations + and *. The * is distributive over +, like multiplication and addition. The field's elements form a group over +, and the field's elements minus the additive identity form a group over * -- no division by zero. All the finite ones are known, the "Galois fields". They have pⁿ elements, where the p is a prime number. They are thus polynomials with degree less than n in some variable x with coefficients 0, 1, ..., p-1 over addition and multiplication modulo p. A certain degree-n polynomial in x must be zero. The + group is Z(p)ⁿ, and the * group Z(pⁿ-1).

Finite fields are useful for constructing error-correcting codes. These codes have built-in redundancy that enables them to correct small numbers of errors.

They are also used in some cryptographic algorithms, like Rijndael.Algebraic fields and groups are also useful in the Galois theory of polynomial roots. Consider the roots of some polynomials whose coefficients are defined over the rational-number field Q, and add the polynomials' roots to Q, making a superset field. For x² - 1 = 0, the roots are 1 and -1, and one gets Q again. For x² - 2 = 0, the roots are sqrt(2) and -sqrt(2), and one gets a larger field: Q(sqrt(2)). Now consider the fields' automorphisms, mappings onto themselves. Q has only the identity automorphism, while Q(sqrt(2)) has automorphisms derived from sqrt(2) -> sqrt(2) (the identity one) and sqrt(2) -> -sqrt(2). Thus, Q(sqrt(2)) has automorphism group Z2.

If a polynomial's roots can be expressed in terms of radicals, nth roots, then its field-extension automorphism group (its "Galois group") must be "solvable", decomposable into a series of cyclic groups. The order of each one of them determines the n of an nth root in the solution. Thus, Q(sqrt(2))/Q has Galois group Z2, and the 2 connects with the power in sqrt(2) = 2^1/2. More generally, one finds that the maximum possible Galois group of an nth degree polynomial is the group S(n) or Sym(n), the "symmetric group". That is the group of all n! permutations of n symbols.

This group's elements can be split up into even permutations and odd permutations, the even and odd referring to the number of interchanges needed to build each permutation. The even permutations form a subgroup, A(n) or Alt(n), the "alternating group". Its S(n) coset is the odd permutations, and the quotient group is Z2, with multiplication table { {even, odd}, {odd, even} }. Thus, A(1) = S(1) and for n > 1,
S(n) -Z2-> A(n)

The alternating groups decompose further in some cases.

S1 = A1 = identity group
S2 -Z2-> A2 = identity group
S3 -Z2-> A3 = Z3
S4 -Z2-> A4 -Z3-> Z2*Z2

This means that a general cubic polynomial's roots have cube roots along with square roots, and likewise for a general quartic polynomial's roots. This can be used to solve some unsolved problems from antiquity, duplicating the cube and trisecting an angle using only ruler and compass. Those two tools produce arithmetic operations and square roots, so they cannot produce cube roots in a finite number of steps. They thus cannot solve those problems. But if one uses a "neusis" or marked ruler, one can indeed solve both problems, because one can find cube roots with it.

Can one solve higher degrees with nth roots, like a quintic? In general, one cannot. This is from S5 -Z2-> A5, and it is because cannot decompose A5 any further -- it is "simple".So in summary,

• Error-correcting codes
• Certain cryptographic algorithms
• Impossibility theorems for construction of various polynomial roots

 

[homeomorphic]

If you just want applications of cyclic groups, those are big in cryptography because cyclic groups are not too far from the integers.

Go watch this series:


Also, in a way, it is sort of a "real world" application to know that you shouldn't try to solve general quintic equations by radicals, the big application of Galois theory, because polynomial eqations arise in applications. Of course, you could just say that it gets too ugly, so you'd rather solve it numerically anyway, but it's a nice factoid to know if you ever run into a big polynomial equation in real life.

 

[lpetrich]

Sometimes one wants analytic results. They can be useful in showing that cancellations, for instance, are exact, because one does not have roundoff error.Another application: computer-algebra algorithms for factoring polynomials (Factorization of polynomials - Wikipedia). They use factoring over finite algebraic fields as an intermediate step, even though the originals may be defined over the rational numbers Q or extensions of them with irrational roots of rational-number polynomials, like Q(sqrt(2)).

Now a bit more detail on the Galois fields. The simplest ones are GF(p), addition and multiplication of integers modulo p. All the others are GF(pⁿ) for positive-integer powers n. Their elements can be expressed as polynomials in variable x:
$$ \sum_{k=0}^{n-1} c_k x^k $$
where the c_k are members of GF(p) and addition and multiplication proceed as expected over a polynomial. There is a further constraint: xⁿ + (some element) = 0, where that expression in x is a polynomial that cannot be factored over GF(p) -- a "primitive polynomial".

The smallest fields:
GF(2) = {0, 1} mod 2
GF(3) = {0, 1, 2} mod 3
GF(4) = {0, 1, x, x+1} mod 2
where
x² + x + 1 = 0

x² rather obviously factors, x² + 1 = (x + 1)² (remember that this is modulo 2), and x² + x = x*(x+1)

AES's Galois Field, about Rijndael's field GF(256) -- one element for each byte. Since it uses modulo-2 arithmetic, it can be implemented using bit shifts and bit xors. Its primitive polynomial is x⁸ + x⁴ + x³ + x + 1.