# Monthly Archives: October 2012

## Intermediate Group Theory (6)

In this post, we’ll only focus on additive abelian groups. By additive, we mean the underlying group operation is denoted by +. The identity and inverse of x are denoted by 0 and –x respectively. Similarly, 2x+3y refers to x+x+y+y+y. Etc … Continue reading

## Polynomial Multiplication, Karatsuba and Fast Fourier Transform

Let’s say you want to write a short program to multiply two linear functions f(x) = ax+b and g(x) = cx+d and compute the coefficients of the resulting product: You might think it’ll take 4 multiplications (for ac, ad, bc and bd) and 1 addition (for ad+bc), but there’s … Continue reading

## Intermediate Group Theory (5)

Free Groups To motivate the concept of free groups, let’s consider some typical group G and elements a, b of G. Recall that , the subgroup generated by {a, b}, is defined to be the intersection of all subgroups of G containing a and b. Immediately, we see … Continue reading

## Intermediate Group Theory (4)

Applications We’ll use the results that we obtained in the previous two posts to obtain some very nice results about finite groups. Example 1. A finite group G of order p2 is isomorphic to either Z/p2 or (Z/p) × (Z/p). In particular, it … Continue reading

## Intermediate Group Theory (3)

Automorphisms and Conjugations of G We’ve seen how groups can act on sets via bijections. If the underlying set were endowed with a group structure, we can restrict our attention to bijections which preserve the group operation. Definition. An automorphism of … Continue reading