Last time I gave a brief introduction to groups and a bit of motivation of group theory (symmetry). I suppose the next logical thing to do would be to introduce the notion of subgroups. However, there’s not terribly much to say on subgroups at this time, so I’ll say what they are, then proceed to examples and more examples of groups in general, and then talk about group homomorphisms.

Subgroups

It should be relatively obvious what type of concept is coming here. Just as a subset is a “set within a set,” a subgroup is a “group within a group.” That is,

Definition: Let G be a group. If H is a subset of G, and H is a group under the operation of G, then H is a subgroup of G.

This is fairly straightforward, the only thing we should notice is that the subset H has to be a group under the same operation as G to be a subgroup. For example, we know that \mathbb{Z} is a group under addition. It can be verified without much trouble that 2\mathbb{Z} is also a group under addition, as associativity of addition is already satisfied, 0\in 2\mathbb{Z}, and 0 + 2k = 2k + 0 = 2k for any 2k\in 2\mathbb{Z} (so we have an identity), and whenever 2k\in 2\mathbb{Z}, we also have -2k\in 2\mathbb{Z} (if 2k is even, so is -2k). Since 2\mathbb{Z}\subseteq\mathbb{Z}, 2\mathbb{Z} is a subgroup of \mathbb{Z}. Similarly, for any n\in\mathbb{Z}, we have n\mathbb{Z} as a subgroup of \mathbb{Z}. However, is it also illustrative to look at a non-example: let \mathbb{Q} be the group of rational numbers under addition (if it’s not obvious, you should verify that this is indeed a group). We can see that \mathbb{Q}^+ is a group under multiplication (again, you should be able to verify this without much trouble); however, even though \mathbb{Q}^+\subseteq\mathbb{Q}, \mathbb{Q}^+ under multiplication is not a subgroup of \mathbb{Q} under addition, because they do not use the same operation. I’m not going to spend too much time on examples here; we’ll see a few in a moment when we look at homomorphisms.

Exercise: Let G be a group, and let H, K be subgroups of $G$. Show that the intersection H\cap K is a subgroup of G.

Group Homomorphisms

Mathematicians are very interested in the structure of objects. One might even go so far as to say that mathematics is the study of structure. What do I mean by “structure”? I mean the way something “looks” mathematically. The best way to do this is to look at an example: let’s look at two sets, A = \{a,b\} and C = \{c,d\}, and let’s suppose we equip A with the binary operation * and C with the binary operation +. We can describe these operations completely by just listing how they affect each of the combinations of elements in A and C, say

  • a*a = a
  • a*b = a
  • b*a = a
  • b*b = b
  • c+c = c
  • c + d = d
  • d + c = d
  • d + d = d

We can also write these in tables, which makes the structure of the binary operations a bit more apparent:

atable

ctable

(I made you MS Paint tables because I don’t know how to format tables in WordPress. I’ll edit it if I ever figure out how to do so…) Now we see that if we swap the c’s and d’s in the second table, we have two tables that are basically the same, except the letters are different. In mathematics, we don’t really care too much about the names of the objects, just the way they behave. Here, the binary structures behave the same way, and we can create a bijective function between them that preserves the way they behave: take

f : A\to C
a \mapsto d
b \mapsto c

We see that this mapping preserves the structures of the two sets, in that f(g*h) = f(g) + f(h) for any g,h\in A. We also don’t lose information, because f is a bijection. As it turns out, this first condition is exactly what we want to describe functions betwixt groups. Without the structure-preserving condition above, the functions between groups would fail to give us very much information about the structure of the groups in question. So now we’ll define a group homomorphism with that in mind:

Definition: Let G and H be two groups with operations *_G and *_H , respectively. A function f : G\to H is called a (grouphomomorphism if we have

f(s*_G t) = f(s)*_H f(t) for all s,t\in G.

Notice that the operation on the left side of the equation happens in G, while the operation on the right side happens in H. Also note that we relaxed the condition that f be a bijection. If it is, then we call f a (groupisomorphism. In the case of a homomorphism, we can lost some of the information of G, whereas in the case of an isomorphism, we essentially retain all of the information about the original group. Let’s look at some properties and examples to get a feel for these creatures.

Property: If f : G\to H is a homomorphism of groups, and e\in G is the identity of G, then f(e) = e' is the identity of H.

Intuitively, this makes sense. If we’re going to respect the group structure, we should be sending the identity to the identity. We can also give a formal proof of this: f(e) = f(e*e) = f(e)*f(e), and since we’re in a group, we can multiply by the inverse of f(e) on the right on both sides of the equation (remember, multiplication on the right and left are two different things in general!) to see f(e)*(f(e))^{-1} = f(e)*f(e)*(f(e))^{-1}, but this simplifies to e' = f(e)*e' = f(e), which is what we wanted. In a similar manner, one can show

Property: If f : G\to H is a homomorphism of groups, and g\in G is any element of G and g^{-1} is the inverse of g, then f(g^{-1}) = (f(g))^{-1}, where (f(g))^{-1}\in H is the inverse of f(g)\in H.

What this is saying is that homomorphisms also respect inverses, which makes sense, again thinking that we defined them to be a structure-preserving map.

Here is also a good time to introduce the convention of “powers” in groups. It means exactly what you might think: g^n = g*g*\ldots *g, where we have n\,g‘s on the right hand side. However, this isn’t how we define it formally, because when mathematicians want to be super precise, they abhor don’t like \ldots‘s.

Definition: Let G be a group (written multiplicatively), let g\in G, and let n\in\mathbb{Z}. Then we define g^n as follows:

  • g^0 = e, where e is the identity of G,
  • If n\in\mathbb{N}, g^n = g\cdot g^{n-1}, and
  • If -n\in\mathbb{N}, then g^n = g^{-1}\cdot g^{n + 1}, where g^{-1} is the inverse of g.

These powers work the way we want them to; i.e. g^{n}g^{m} = g^{n + m}, which also shows that powers of g commute. Now, we’ll generally write arbitrary groups in multiplicative notation, but when working with commutative (AKA abelian) groups, we will usually write them additively. In this case, we won’t write g^n, but rather ng. One has to be careful: we’re not actually multiplying g by n. This might not even make sense, as G might not be a subset of the real numbers at all. However, even when it is, we’re technically not multiplying the element of the group by n. (For the most part, if you do multiply g by n, you’ll get the right answer, but there are strange times when it won’t turn out right.)

Another property you might now suspect is

Property: If f : G\to H is a homomorphism of groups, and g\in G, then f(g^n) = (f(g))^n.

This can be proven via induction on n.

Example: First, we’ll have to define a new group: let n\in\mathbb{N} and \mathbb{Z}_n = \{0, 1, 2, \ldots, n-1\}. We can make this set into a group under addition, but if we try to add these normally, we see that \mathbb{Z}_n isn’t closed. So we have to make a small modification. You’ll note that this set has all the remainders one can get upon division by \mathbb{Z}_n, so when we add up two numbers and get a number larger than n, we’ll just “wrap around” by defining an equivalence relation that relates each number to its remainder upon division by n. This is the same equivalence relation I talked about in my post on basic set theory, except I used 5 rather than an arbitrary natural number. Formally, a\equiv b\mod n if n\mid a - b, where n\mid d means n divides d (recall that n\mid d if and only if there exists some k\in\mathbb{Z} such that nk = d). Then \mathbb{Z}_n is a set of equivalence class representatives, and we’ll define addition on \mathbb{Z}_n to be normal addition, and when we wind up with a number outside of the set of representatives, we simply take the number inside \mathbb{Z}_n that is equivalent to the sum. If this seems confusing, don’t panic – just think about clocks! Whenever you need to calculate times, you work mod 12 (or mod 24 if you use 24 hour time). The only difference: when doing “clock arithmetic,” you use 12 as the equivalence class representative instead of 0. For example, 11 + 3\equiv 2\mod 12: 11 o’clock plus 3 hours gives 2 o’clock. Under addition modulo n, \mathbb{Z}_n becomes a group. We call \mathbb{Z}_n the “cyclic group of order n.”

Now, we can define a homomorphism \phi : \mathbb{Z}\to\mathbb{Z}_n (actually we can define several). For the sake of concreteness, let’s use n = 12. First, let’s observe that any integer is the sum of some amount of 1′s or -1′s. What this means is that we can just take the element 1 in \mathbb{Z} and add it to itself over and over (or add its inverse) to get any element of \mathbb{Z}. So since a homomorphism has to respect the group operation, we only need to specify where 1 is sent under \phi. We’ll denote the homomorphism that sends 1\mapsto k\in\mathbb{Z}_{12} by \phi_k: after that, it’s clear sailing! Let’s look at a few \phi_k:

  1. \phi_0 : \mathbb{Z}\to\mathbb{Z}_{12}: This homomorphism actually takes EVERYTHING in \mathbb{Z} to 0, as we can see by writing n = n\cdot 1 (remember, this n isn’t really multiplication, it’s operating by 1 n times) so that \phi_0(n) = \phi_0(n\cdot 1) = n\phi_0(1) = 0. This homomorphism is the trivial homomorphism: we can always send everything in one group to the identity of another group. However, this homomorphism doesn’t give us any new information about the original group, so we focus on more interesting ones.
  2. \phi_1 : \mathbb{Z}\to\mathbb{Z}_{12}: This homomorphism takes any member of \mathbb{Z} and sends it to its equivalence class representative (where equivalence is modulo 12) in \mathbb{Z}_{12}, which is the same as saying that the fiber over any element of \mathbb{Z}_{12} is the equivalence class of that element under modulo 12 arithmetic. There’s some major collapsing going on for \mathbb{Z}, but all of \mathbb{Z}_{12} is hit.
  3. \phi_2 : \mathbb{Z}\to\mathbb{Z}_{12}: Here, we only hit half of \mathbb{Z}_{12}: we see \phi_2(0) = 0, \phi_2(1) = 2, \phi_2(2) = 4, \phi_2(3) = 6, \phi_2(4) = 8, \phi_2(5) = 10, and \phi_2(n) = \phi_2(n+6). That gives us all the information we need to know about this homomorphism.

I could keep going, but there’s not much new that happens after this. For other \phi_k, we basically see the same phenomena. If we look at how much of \mathbb{Z}_{12} is hit by \phi_k, we see that \phi_0 hits 1 element, \phi_1 hits 12 elements, \phi_2 hits 6 elements, \phi_3 hits 4 elements, \phi_4 hits three elements, \phi_5 hits 12 elements, \phi_6 hits 2 elements, \phi_7 hits 12 elements… do we see the pattern? That’s right, the homomorphism \phi_k : \mathbb{Z}\to\mathbb{Z}_{12} hits 12/\gcd(k,12) elements. There are other patterns as well, two of which I am going to talk about next, and others that I will discuss in another post on cyclic groups.

A Taste of Some Special Subgroups Related to Homomorphisms

So far, I haven’t talked too much about subgroups. However, there are a few important subgroups that come up when we talk about homomorphisms. Before I give them away, go back and look at the homomorphisms \phi_k above and play with them for a bit. Try finding some homomorphisms \mathbb{Z}\to\mathbb{Z}_k for various k, or other homomorphisms in general. Once you’re done (or now, if you’re too lazy to experiment yourself) read on, fearless champion.

Image: Recall that the image of a function f : S\to T is defined as \textrm{im}\,f = f(S) = \{t\in T\mid f(s) = t\textrm{ for some }s\in S\}. As it turns out, the image of a group homomorphism \phi : G\to H is always a subgroup of H. This shouldn’t be a surprise: when we make a homomorphism, we’re trying to preserve the group structure, and it wouldn’t make much sense if we were preserving structure while somehow mapping to something that isn’t a group. It isn’t hard to check that in each \phi_k above, the image is a subgroup. It would be good of you to try to prove such a thing.

Kernel: The kernel of a group homomorphism is possibly even more important than the idea of the image of a group homomorphism. We’ll begin with the definition:

Definition: Let \phi : G\to H be a group homomorphism. Then the kernel of \phi is defined to be

\ker\phi := \{g\in G\mid \phi(g) = e_H\},

where e_H is the identity of H.

So the kernel of a group homomorphism is the set of elements in the domain that map to the identity element in the image, or the fiber over the identity in the image. This is also easily seen to be a subgroup (exercise!) and it relates homomorphisms of groups to other objects (that we will talk about soon) and gives us information about when a group homomorphism is injective.

Example: Consider the map \phi_1 : \mathbb{Z}\to\mathbb{Z}_{12}. What is the kernel? Well, it’s the elements that map to the identity, 0. So what maps to 0? Obviously, \phi_1(0) = 0. We can also see that since \phi_1(1) = 1, we have \phi_1(n) = n\cdot\phi_1(1)\equiv n\mod 12. Noting that n\equiv 0\mod 12 exactly when n = 12k for some k\in\mathbb{Z}, we see that \ker\phi_1 = 12\mathbb{Z} (and this is certainly a subgroup of \mathbb{Z}).

So that’s it for now! Next time, I may or may not discuss more things about kernels. I also may or may not talk about other just straight up important concepts. Please accept my apologies for the wait on this post, and I’ll see you then!

This summer, I was a counselor at PROMYS, a math camp for high schoolers at Boston University. The counselors were able to give “minicourses” on topics of their choice, so I talked about group theory in music. I’m not going to write up my talk, but here’s a pdf of the written version: ALGEBRAIC MUSIC THEORY
Enjoy!

Before I make another post on actual real life group theory, there are some concepts one should be familiar with, because they arise not only all the time in group theory, but also all the time in every single other topic as well. Let’s crank ‘em out and get to the real meat, eh wot?

You probably already know a decent amount of this information, but for completeness, I’ll post it anyway. Obviously, we can’t work without sets without knowing what a set is! So

Definition: A set is a collection of objects.

And that’s the best we can do. Seriously. As it turns out, eventually you hit a point where an intuitive understanding of the concept has to be accepted, and in math, this is it. One rule I’ll mention is that any given object is either in a set or it is not. There is no in-between. Now there are other axioms of set theory to keep bad things from happening; for example, some sets are too large to exist: the set of all sets is just not a well-defined object in the standard set theory universe. If it was, it would have as a subset the set of all sets that do not contain themselves as members, but if this set belongs to itself then it doesn’t, and vice versa (going against the one rule for sets we mentioned). This is called Russell’s Paradox, and indicates one reason such a set should be disqualified from the game of set theory.

Let’s suppose we wanted to write a set, maybe the set A of the first five letters in the English alphabet. This set has a finite number of elements, and we can just write all of them out: A = \{a,b,c,d,e\}. (Quick note: sets cannot contain duplicates; that is, we consider \{a,a,b,c,d,e\} to be the same set as \{a,b,c,d,e\}.) But sometimes we want to be more sophisticated: perhaps we want to write the set of even integers, 2\mathbb{Z}. This is an infinite set, and while we could write something like 2\mathbb{Z} = \{\ldots,-4,-2,0,2,4,\ldots\}, we might want to simply have a description of the elements rather than list them. For that, we use what is called “set-builder notation,” which looks something like this:

T = \{r\in R \mid \textrm{ requirements on r}\}.

Then T is the set of r that are members of (the symbol \in means “is a member of”) R such that the requirements on r are satisfied. Using this notation, we can write
2\mathbb{Z} = \{2k\mid k\in\mathbb{Z}\}.
You might notice that I didn’t place any requirement that 2k belong to some other set (they do of course). It isn’t always needed to specify that the r belong to some other set R, but often it is. This brings us to the next definition:

Definition: Let S and T be two sets. If s\in T for all s\in S, we say S is a subset of T.

So a if a set S is a subset of another set T, every element of S is also a member of T. We write this as S\subseteq T. Some examples:

  • \{a,b,d\}\subseteq\{a,b,c,d,e\}
  • 2\mathbb{Z}\subseteq\mathbb{Z}
  • S\subseteq S for any set S
  • \emptyset\subseteq S for any set S, where \emptyset = \{\,\} (\emptyset is aptly called the empty set, as it has no elements).

Some other important but basic definitions and notations:

Definition: The union U of a collection of sets S_i is the smallest set containing each S_i as a subset.

Another way of reading this is that to get U, we take all the elements from all the S_i, throw them into one set, and violá! You’ve got yourself a union. We write the union of two sets S, T as S\cup T, and similarly for unions of more sets. Now that we’ve introduced unions, we should introduce the opposing concept:

Definition: The intersection I of a collection of sets S_i is the largest set that is a subset of each S_i.

So the intersection of sets is the set of elements that belongs to all of the original sets. We write S\cap T to mean the intersection of S and T. For example, \{a,b,c,d,e\}\cap\{c,d,e,f,g\} = \{c,d,e\}. Simple!

Definition: The order or cardinality of a set S is the number of elements in S, and is written \left|S\right|.

We have certain names for the sizes of infinite sets, but we’ll leave that be for now. I’ll probably talk about that in another post.

Definition: The cartesian product of two sets S and T is the set S\times T = \{(s,t)\mid s\in S, t\in T\}.

So the cartesian product is the set of ordered pairs, with the first element belonging to the first set and the second element belonging to the second set. Think \mathbb{R}^2 = \mathbb{R}\times\mathbb{R}, the real plane.

SOME COMMON SETS:

  • \mathbb{N} = \{1, 2, 3, \ldots\}, the set of natural numbers
  • \mathbb{Z} = \{\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots\}, the set of integers (the \mathbb{Z} comes from the German word “Zahlen” for numbers)
  • \mathbb{Q} = \{a/b\mid a,b\in\mathbb{Z}, b\neq 0\}, the set of rational numbers (the \mathbb{Q} stands for “quational”)
  • \mathbb{R} = \{\textrm{all decimal expansions }\pm d_1d_2\ldots d_n.a_1a_2\ldots\}, the set of real numbers
  • \mathbb{C} = \{a + bi\mid a,b\in\mathbb{R}, i^2 = -1\}, the set of complex numbers

I’ll also write \mathbb{Q}^+, \mathbb{R}^+, \mathbb{Q}_{\geq 0}, \mathbb{R}_{\geq 0} to denote the sets of positive rational numbers, positive real numbers, nonnegative rational numbers, and nonnegative real numbers, respectively.

Alright, that’s the basics about sets themselves. Now onto cool things, like functions. We all know what a function is: some “rule” that takes an element of one set and gives exactly one element of another set. We can formalize this by saying

Definition: A function f from A to B, written f : A\to B or A \xrightarrow{f} B, is a subset of A\times B such that whenever (a,b) = (a,c), we have b = c. A is called the domain of f, and B is called the codomain of f.

But I’d be lying if I told you anyone actually thought of functions like that. Everyone things of them as mappings that take every member of one set to exactly one member of another. Another bit of notation: sometimes we want to specify how the function works on elements, in which case I might write f : a\mapsto b, where a and b are members of A and B, respectively. One extremely important concept that one might not  be familiar with yet is the notion of a well defined function: one which is unambiguously determined.

You might think “whenever I’ve seen functions, they were just defined in terms of what every single element mapped to,” to which I would respond, “but we might want to define more crazy functions now. Like say we wanted to create a function f : A = A_1\cup A_2\to\{0,1\}, where f(a) = 0 if a\in A_1 and f(b) = 1 if b\in A_2. If there’s any overlap between A_1 and A_2, we don’t know know where we should send those members. So here we would have to check that A_1\cap A_2 = \emptyset.” Being of the skeptical mind that you are, you might wonder “does this ever happen” to which I would say “yes, it does, now calm down and let me finish.” It’s about to get a bit dry, but just push on through so we can get to the real good stuff.

Definition: Let f : A\to B. The set f(A) = \{b\in B\mid b = f(a)\textrm{ for some }a\in A\} is a subset of B, called the range or image of f, or the image of A under f.
Similarly, we could look at the image of a subset of A.

Definition: Let f : A\to B, and let C\subseteq B. The set f^{-1}(C) = \{a\in A\mid f(a)\in C\} is called the preimage or inverse image of C under f.

If C = \{b\} consists of a single element, the preimage of \{b\} under f is called the fiber of f over b. ACHTUNG! f^{-1} is not in general a function, there will often be multiple elements in any given fiber of f. For example, if we look at f : \mathbb{R}\to\mathbb{R} given by f : x\mapsto x^2, we see that f^{-1}(1) = \{\pm 1\}.

Definition: If f: A\to B and g: B\to C, then the composite map g\circ f: A\to C is defined by (g\circ f)(a) = g(f(a)).

Definition(s): Let f: A\to B.

  1. f is injective or is an injection if f(a_1) = f(a_2) implies that a_1 = a_2.
  2. f is surjective or is a surjection if for all b\in B, there exists some a\in A such that f(a) = b.
  3. f is bijective or is a bijection if it is both injective and surjective.

Informally, a function is injective if it doesn’t repeat any of its values, surjective if it hits everything in the target set, and bijective if it does both of these things.
There’s a bit of a subtlety here that is important to note: the two functions f_1 : \mathbb{R}\to\mathbb{R} and f_2 : \mathbb{R}\to\mathbb{R}_{\geq 0} given by f_1(x) = f_2(x) = x^2 aren’t really the same function. Although they have the same values at any point x\in\mathbb{R}, f_2 is surjective while f_1 is not. Almost there! Only a few more definitions to go.

Definition: A permutation of a set A is a bijection f: A\to A.

Definition: Let A be a nonempty set. A binary operation * on A is a function *: A\times A\to A.
For example: addition and multiplication of real numbers are binary operations on \mathbb{R}.

Definition: A binary relation on a set A is a subset R\subseteq A\times A, and we write a\sim b if (a,b)\in R.

Definition: A binary relation \sim on a set A is an equivalence relation if it satisfies the following properties:

  1. \sim is reflexive; that is, a\sim a, for all a\in A.
  2. \sim is symmetric; that is, a\sim b implies b\sim a for all a,b\in A.
  3. \sim is transitive; that is, if a\sim b and b\sim c, then a\sim c.

This is a REALLY important concept, so I’ll go through a couple of examples:

EXAMPLE: Let A = \mathbb{R}. Then equality is an equivalence relation. Let x\in\mathbb{R}. Is x = x? Yes, of course. Let’s say x = y. Then is y = x true? You bet. And what if x = y and y = z? Well, you can be sure that x = z. So equality satisfies all the properties we wanted above, and is thus an equivalence relation.

EXAMPLE: Consider \mathbb{Z}, and define a\equiv_5 b if a - b is divisible by 5. Is \equiv_5 an equivalence relation on \mathbb{Z}? Well let’s check: let n, m, k\in\mathbb{Z}. n\equiv_5 n, since n - n = 0 is certainly divisible by 5. Suppose n\equiv_5 m. Then n - m is divisible by 5, hence so is -(n-m) = m - n, which implies that m\equiv_5 n, so \equiv_5 is symmetric. Now, suppose n\equiv_5 m and m\equiv_5 k. Then we have that n - m and m - k are both divisible by 5. So if we have two multiples of 5, we can add them and get another multiple of 5: so (n - m) + (m - k) = n - k is a multiple of 5, and we see n\equiv_5 k, so \equiv_5 is reflexive, symmetric, and transitive: an equivalence relation!

So, the reason equivalence relations are so nice is that they give us groups of objects within a set that share some property: and there is no overlap! So we say that an equivalence relation partitions a set into equivalence classes, which I’ll state formally now:

Definition: If \sim is an equivalence relation on A, then the equivalence class of a\in A is defined to be the set C_a = \{x\in A\mid x\sim a\}. The elements of C_a are said to be equivalent to a, and any element of C_a is called a representative of C_a.

Definition: A partition of a set A is a collection A_i of nonempty subsets of A such that the union of all the A_i is equal to A, and the intersection of any two distinct A_i is empty.

In the example above of \mathbb{Z}, there are five equivalence classes, corresponding to the remainder one gets upon dividing a given number by 5. The notion of equivalence relations will be really useful in many discussions later on, so it would be good to develop an intuition for these things. Here’s one more example of an equivalence relation, which is a bit more abstract: let f : A\to B be a surjective function. Then the relation defined by a \sim b if and only if f(a) = f(b) is an equivalence relation. To see this? Let a, b, c\in A. Certainly a\sim a, since f(a) = f(a) (as f is a function). Suppose a\sim b. Then f(a) = f(b), so certainly f(b) = f(a), which shows that b\sim a. Lastly, we have to check transitivity. Suppose a\sim b and b\sim c. Then f(a) = f(b) and f(b) = f(c), but since equality is an equivalence relation, we know f(a) = f(c), so a\sim c, and hence \sim is an equivalence relation on A. We can also see that the equivalence classes are exactly the fibers of f from the definitions of fiber and equivalence classes. Nifty.

After an insanely long hiatus during which I went to college and learned some actual math, I’ve decided to start posting here again about some higher level concepts, like algebra and number theory, and maybe some other fun stuff I decide to mess around with. Since I just finished a course on group theory, and algebra is a lot of fun, I figure I’ll start with some basic ideas about that. I won’t be assuming terribly much of the reader, a modest mathematical background should be enough to follow the posts.

What is a group?

Before I get into the formal definition, let’s talk about symmetry. There are all sorts of symmetries, and pretty much all of them are really nice when it comes to math. Symmetries make your integrals collapse, and your shapes easier to work with. So group theory tries to capture the notion of “symmetry” in some abstract sense. For an example, let’s take a look at a square. Picture your favorite square. What symmetries does it have? Well, first of all, we should figure out what we mean by a symmetry of a square (or polygon). We’ll say a motion or movement is a symmetry of the square if after the motion is completed, the square is in the position it was originally (but perhaps with the corners in different locations). Also, we should require that the motions be rigid: so no cutting the square and moving only the cut piece. So, what are these symmetries then? First off, we can keep the square exactly where it is. This is a bit boring, but it qualifies. We can also rotate the square by 90 degrees counterclockwise about its center, or by 180 degrees, or by 270 degrees. These also qualify, as you can see if you move your favorite square about in your head. We can also draw two imaginary lines connecting opposite corners on the square and two more imaginary lines connecting the midpoints of opposite edges, and flip the square about any one of these lines. After some thought, it seems like we’ve found them all, and we have. These symmetries satisfy some nice properties. First, if we perform any number of them on the square, we get another symmetry! This isn’t hard to see, especially from our definition of a symmetry. Second, we can always undo a symmetry with another symmetry to put the square back into its original position. Keeping these in mind, we’ll now define a group (and see that the symmetries of the square are indeed such an object).

Definition: A group G is a set equipped with a binary operation *: G\times G\to G satisfying the following properties:

  1. * is associative: For all g,h,k\in G, (g*h)*k = g*(h*k)
  2. There exists an identity element: There exists e\in G such that e*g = g*e = g for all g\in G.
  3. There exist inverses: For any g\in G, there exists g'\in G such that g*g' = g'*g = e.

And that, folks, is the formal definition of a group! Let’s look at some examples:

EXAMPLE: The Trivial Group

The simplest group we can imagine is the group that has only one element, the identity. So here, G = \{e\}, and the operation is given by e*e = e (as if we had a choice). This is a group, but it’s pretty much as boring as a group can be, so let’s move on to another example.

EXAMPLE: The Integers, \mathbb{Z}

Henceforth, I’ll be writing \mathbb{Z} to mean the integers; that is, \mathbb{Z} = \{\ldots, -3, -2, -1, 0, 1, 2, 3,\ldots\}. This set forms a group under addition in the usual sense: we already know addition is associative, so point one is satisfied. We know that n + 0 = 0 + n = n for any integer n, so we have an identity, 0. We also have inverses: n + (-n) = (-n) + n = 0, and thus \mathbb{Z} is indeed a group! Notice that we have m + n = n + m for any m, n\in\mathbb{Z}, so the operation is not only associative, but commutative. Speaking of commutativity, one might wonder “is \mathbb{Z} a group under multiplication? That’s also associative and commutative.” The answer would be no: while we do have associativity and an identity, we don’t have inverses for most elements: in fact, there are only two elements in \mathbb{Z} that have a multiplicative inverse in \mathbb{Z}.

EXAMPLE: Symmetries of a Square, D_4

Time to come full circle. Or full square. But enough silliness: we’ll call the set of symmetries of a square “the dihedral group of order 8″ and denote it D_4. Now, we want to see that this set is indeed a group! First of all, let’s give judicious names to a few chosen motions: the identity, doing nothing, will of course be e, as usual. Besides that, we’ll let r be the rotation of the square by 90 degrees counterclockwise, and we’ll let f be the flip about the vertical line passing through the center of the square. You might ask “what about the rest of the motions that we talked about above?” to which I would respond, “they can actually all be represented by repeated applications of r and f.” To get the other rotations, we simply rotate by 90 degrees until we get the amount of rotating we want: for example, the rotation by 180 degrees counterclockwise would be given by r*r, and we will ignore the * and simply write it as if we’re multiplying: r*r = r^2. Great! So now we have all the rotations: e (the trivial rotation), r, r^2 and r^3. These are half of the motions we talked about above: and since we have another element that we haven’t really looked at yet, it would be a pretty good guess to say that if we apply any of these motions and then apply f, we’ll get the other four. So, let’s try it out. (ACHTUNG! Read the multiplication of elements in this group from right to left, that is, if we have abc, where a, b, and c are all symmetries of a square, we move the square according to c first, then b, then a). It wouldn’t be unwise to actually get a paper square with the corners labeled A, B, C, and D or whatever your favorite four letters are to see all the motions happening here. fe = f gives us the flip about the vertical line, fr is first a rotation by 90 degrees counterclockwise, and then a flip about the vertical line through the center (not what used to be the vertical line, what is now the “new” vertical line). With a little thought, we see that this is the same as flipping the square about the diagonal going from lower left to upper right. Similarly, fr^2 is the flip across the horizontal line through the center of the square, and fr^3 is the flip about the diagonal going from upper left to lower right. Geometrically, we see that we have inverses: flips are obviously their own inverses, and the inverse of a rotation is given by going the rest of the way around: r*r^3 = r^2*r^2 = r^3*r = r^4 = e. Associativity is a little more annoying to prove, as is showing that we don’t get any more elements upon further multiplication, but all of that can be worked out with a bit of work in the privacy of one’s own bedroom. Ignoring those few details, we can see that D_4 = \{e, r, r^2, r^3, f, fr, fr^2, fr^3\} is indeed a group!

One last thing: while the operation of the trivial group and the operation of addition in \mathbb{Z} were both commutative, group operations are not commutative in general: to see this, simply look at D_4 and see what happens to the square in the case of the motion fr and in the case of the motion rf. Here’s a tip: they’re not the same!

I meant to post this a long time ago, and since I wrote it it’s just been sitting in my drafts. I guess now’s as good a time to post it as any…

In my first post, I talked about the floor function a little bit. I’ll go into a bit more calculusy depth here with a small dissertation on it. The floor function floor(x)=\left\lfloor x\right\rfloor is defined as the largest integer not greater than x, in symbols \left\lfloor x\right\rfloor =\max\left\{ n\in\mathbb{Z\mid}n\leq x\right\}, where \mathbb{Z} is the set of integers. Keep in mind throughout the post that I’ll be using n to represent an integer, unless otherwise stated.

Essentially, it’s a big staircase that increases by one at every integer, like so.
It’s quite useful in number theory and other applications, but it is not really a “standard” function. Being such, it becomes hard to visualize what an equation involving the floor function would look like graphically, especially because it doesn’t have a “normal” function definition (such as f(x)=x^{2}) which makes finding a derivative and integral slightly trickier. Before we proceed to derive each one, I’ll remind you (or teach you, if you haven’t learned) what the derivative and the integral are, in basic
terms.

DERIVATIVE: First off, the derivative of a function f is defined as the instantaneous rate of change of f at any point x, meaning the slope of the tangent line to f at x. So if you take the normal slope definition, \frac{f(b)-f(a)}{b-a}, you can find the derivative of f (denoted \frac{d}{dx}[f(x)]) at b by making a obscenely close to b. Of course, it isn’t always that simple (ironically, usually it’s much more simple, especially after you learn the shortcuts) and the “definition” I crudely put forth is hardly rigorous, but it works as a basic explanation. Obviously (if not from the definition of the floor function, at least from the picture), the floor function only increases at the integers.
On any “segment” of the function you can take \frac{f(b)-f(a)}{b-a}=\frac{\lfloor b\rfloor-\lfloor a\rfloor}{b-a} and find that it is 0. Using the interval \left[1.1,1.9\right] within \left[1,2\right] as an example we have \frac{f(1.9)-f(1.1)}{1.9-1.1}=\frac{\lfloor1.9\rfloor-\lfloor1.1\rfloor}{1.9-1.1}=\frac{1-1}{.8}=\frac{0}{.8}=0. However, \left\lfloor x\right\rfloor  is discontinuous at the integers, and therefore there is no slope at those points. We can take a limit to see what it should be, though. Let’s look at \frac{\left\lfloor 2\right\rfloor -\left\lfloor a\right\rfloor }{2-a} for values of a approaching 2 to give us an idea of what \underset{a\rightarrow2}{\lim}\frac{\left\lfloor 2\right\rfloor -\left\lfloor a\right\rfloor }{2-a} should be. When a=1.5, \frac{\left\lfloor 2\right\rfloor -\left\lfloor a\right\rfloor }{2-a}=\frac{\left\lfloor 2\right\rfloor -\left\lfloor 1.5\right\rfloor }{2-1.5}=\frac{2-1}{.5}=\frac{1}{.5}=2. When a=1.75, \frac{\left\lfloor 2\right\rfloor -\left\lfloor a\right\rfloor }{2-a}=\frac{\left\lfloor 2\right\rfloor -\left\lfloor 1.75\right\rfloor }{2-1.75}=\frac{2-1}{.25}=\frac{1}{.25}=4. When a=1.9, \frac{\left\lfloor 2\right\rfloor -\left\lfloor a\right\rfloor }{2-a}=\frac{\left\lfloor 2\right\rfloor -\left\lfloor 1.9\right\rfloor }{2-1.9}=\frac{2-1}{.1}=\frac{1}{.1}=10. As you can see, the top of the fraction remains 1 no matter how close we take a (smaller than 2) to be to 2, but the bottom becomes increasingly smaller and so increases the value of the entire fraction. We can make \frac{\left\lfloor 2\right\rfloor -\left\lfloor a\right\rfloor }{2-a} as large as we choose by taking a closer and closer to 2, and we can write \underset{a\rightarrow2^{-}}{\lim}\frac{\left\lfloor 2\right\rfloor -\left\lfloor a\right\rfloor }{2-a}=\underset{a\rightarrow2^{-}}{\lim}\frac{1}{2-a}=+\infty (2^{-} because we must remember that we were taking values less than 2) . Taking the limit from the other side, meaning taking
values of a greater than 2, we find \underset{a\rightarrow2^{+}}{\lim}\frac{\left\lfloor 2\right\rfloor -\left\lfloor a\right\rfloor }{2-a}=0. This is trivial to show, because for all 2\leq a<3, \left\lfloor a\right\rfloor =2 and therefore \left\lfloor 2\right\rfloor -\left\lfloor a\right\rfloor =2-2=0 as a\rightarrow2^{+}. In this case, the denominator does not matter, because for all a>2, it will return a finite number, and 0 divided by any finite number is still 0. So now that we have limits from both the right and the left sides, we see that +\infty=\underset{a\rightarrow2^{-}}{\lim}\frac{\left\lfloor 2\right\rfloor -\left\lfloor a\right\rfloor }{2-a}\neq\underset{a\rightarrow2^{+}}{\lim}\frac{\left\lfloor 2\right\rfloor -\left\lfloor a\right\rfloor }{2-a}=0 and as such \underset{a\rightarrow2}{\lim}\frac{\left\lfloor 2\right\rfloor -\left\lfloor a\right\rfloor }{2-a} does not exist. This is the case for all integers. Using this knowledge, we can write \frac{d}{dx}\left[\left\lfloor x\right\rfloor \right]=\begin{cases} 0, & x\notin\mathbb{Z}\\DNE, & x\in\mathbb{Z}\end{cases}. Which is 0 almost everywhere, and we can reasonably say that the derivative is identically 0, and account for error at the integers as it arises.

INTEGRAL: This one’s a bit trickier. The integral of a function is the anti-derivative, meaning if you derive the integral, you get the function back. So, the slope of the integral of a function (the integral of f is denoted \int f(x)dx) is given by the function itself. A useful property of the integral is that when it is evaluated at a value a and subtracted from the value of the integral at b, it gives the area between the graph of f and the x-axis. This is represented by \intop_{a}^{b}f(x)dx. We will be using this property to derive a general anti-derivative for the floor function.

To start, let’s take a look at the graph again.

The area under the graph from 0 to 1 is 0. The area from 1 to 2 is 1. The area from 2 to 3 is 2. These can be calculated by simple rectangles and A=l\cdot w. So, the integral from 0 to n is the same as the integral from 1 to n (because the area from 0 to 1 is 0), and is equal to the sum of the integers from 1 to n-1. Symbolically: \int_{0}^{n}\left\lfloor x\right\rfloor dx=\int_{1}^{n}\left\lfloor x\right\rfloor dx=\sum_{k=1}^{n-1}k=\frac{(n-1)\cdot(n)}{2}, \forall n\in\mathbb{Z}. Now that we have an integral defined for the area under the function from 0 to integer n, we just have to extend that definition to n+\alpha, where 0\leq\alpha<1. We can write this as \int_{0}^{n+\alpha}\left\lfloor x\right\rfloor dx=\int_{1}^{n+\alpha}\left\lfloor x\right\rfloor dx=\int_{1}^{n}\left\lfloor x\right\rfloor dx+\int_{n}^{n+\alpha}\left\lfloor x\right\rfloor dx

=\sum_{k=1}^{n-1}k+\int_{n}^{n+\alpha}\left\lfloor x\right\rfloor dx

=\frac{(n-1)\cdot(n)}{2}+\int_{n}^{n+\alpha}\left\lfloor x\right\rfloor dx

Notice also that \left\lfloor n+\alpha\right\rfloor =n, so that \frac{(n-1)\cdot(n)}{2}+\int_{n}^{n+\alpha}\left\lfloor x\right\rfloor dx=\frac{(\left\lfloor n+\alpha\right\rfloor -1)\cdot(\left\lfloor n+\alpha\right\rfloor )}{2}+\int_{n}^{n+\alpha}\left\lfloor x\right\rfloor dx. (This way, we can make the integral an explicit function of x, rather than stating you need to take the decimal part for this, etc.) Next, we must find what the value of \int_{n}^{n+\alpha}\left\lfloor x\right\rfloor dx is. This is easy, however, because looking at it geometrically, it is just a rectangle with width \alpha and height \lfloor n+\alpha\rfloor. Therefore, \int_{n}^{n+\alpha}\left\lfloor x\right\rfloor dx=l\cdot w=\alpha\cdot\lfloor n+\alpha\rfloor. But, \alpha=n+\alpha-n=n+\alpha-\lfloor n+\alpha\rfloor, so \int_{n}^{n+\alpha}\left\lfloor x\right\rfloor dx=l\cdot w=\alpha\cdot\lfloor n+\alpha\rfloor=\left[n+\alpha-\lfloor n+\alpha\rfloor\right]\cdot\lfloor n+\alpha\rfloor. Looks like we have our integral!

\int_{0}^{n+\alpha}\left\lfloor x\right\rfloor dx=\frac{(n-1)\cdot(n)}{2}+\left[n+\alpha-\lfloor n+\alpha\rfloor\right]\cdot\lfloor n+\alpha\rfloor, which will simplify to \frac{(\lfloor n+\alpha\rfloor-1)\cdot\lfloor n+\alpha\rfloor+2\cdot\left[n+\alpha-\lfloor n+\alpha\rfloor\right]\cdot\lfloor n+\alpha\rfloor}{2}=\frac{\lfloor n+\alpha\rfloor\cdot\left[-\lfloor n+\alpha\rfloor+2\cdot(n+\alpha)-1\right]}{2}

=\frac{-\lfloor n+\alpha\rfloor\cdot\left[\lfloor n+\alpha\rfloor-2\cdot(n+\alpha)+1\right]}{2} Thus, we have the integral as an explicit function of n+\alpha,
which we can set equal to any real x, so that \int_{0}^{x}\left\lfloor t\right\rfloor dt=\frac{-\lfloor x\rfloor\cdot\left[\lfloor x\rfloor-2\cdot x+1\right]}{2} (using t as the dummy variable so as to avoid ambiguity). Since we used a variable as the upper limit of integration, we obtain a formula for the indefinite integral by simply adding +C to the final result (you didn’t think I’d forget, did you?), and saying that \int\lfloor x\rfloor dx=\frac{-\lfloor x\rfloor\cdot\left[\lfloor x\rfloor-2\cdot x+1\right]}{2}+C. From this we can define integration of the floor function on any interval [a,b] by evaluating \int_{a}^{b}\lfloor x\rfloor dx.

CONCLUSION: In summary, the calculus for the floor function wasn’t too hard to define. It took a bit of work, but was really quite simple in the end. I did some more work to find the second integration of the floor function, and it turns out to be as easy (if not more) to find as the first integration! I’ll leave that to you to figure out, though. If you have any novel ideas that you use to figure it out, post them. Or post if you just think you’ve found it. Or post just because you like me and want to say “Gee, you’re doing swell.” I know this wasn’t very rigorous or mind-blowing, but I’m working on learning some abstract algebra, complex analysis, advanced calculus, and topology in the meantime and hopefully I’ll find something there that will be post-worthy. If you find anything interesting, or have any interesting ideas, let me know!

I’m back from the dark chasms of school and other things. I know I haven’t posted in what seems like forever, but I’m still trying to complete some thoughts on things. I have a few ideas that I’m working on, however, and as soon as I get [La]TeX back and group my thoughts, I’ll be sure to post them.  Until then, here’s something fun to tide you over: my 4Sight math test! Screwing with the graders gets you a perfect score, every time. (Results not typical)

One day at work, I was doodling graphs and came up with something like this:

Looking at this graph, I was curious about two things. One, what would the equation be to describe such a function; two, what would this function look like in polar form.To start, I thought about an ellipse with x-intercepts at \pm\frac{\pi}{2}, so using standard analytic geometry knowledge, the equation of the ellipse turns out to be \frac{4x^{2}}{\pi^{2}}+y^{2}=1, and this looks like, well, an ellipse.

Taking this ellipse apart piece by piece and then pasting those pieces together accordingly would result in the cuspy periodic function above. Solving for y yields y=\pm\frac{\sqrt{\pi^{2}-4x^{2}}}{\pi}. From there, I defined a piece-wise function that described the function; we’ll call it f(x). f(x)=\begin{cases}-\sqrt{1-\frac{4(x-k\pi)^{2}}{\pi^{2}}}+1, & \forall x\in\begin{cases}\left[k\pi,\frac{(2k+1)\pi}{2}\right], & \mbox{if k}\in 2\mathbb{Z}\\\left[\frac{(2k+1)\pi}{2},k\pi\right], & \mbox{if k}\in 2\mathbb{Z}+1\end{cases}\\\sqrt{1-\frac{4(x-k\pi)^{2}}{\pi^{2}}}-1, & \forall x\in\begin{cases}\left[k\pi,\frac{(2k+1)\pi}{2}\right], & \mbox{if k}\in 2\mathbb{Z}+1\\\left[\frac{(2k-1)\pi}{2},k\pi\right], & \mbox{if k}\in 2\mathbb{Z}\end{cases}\end{cases}

So that’s f(x). In a nutshell, this equation takes an x, decides on which of the four interval descriptions it fits, and depending on that, takes either the corresponding point on the top of the ellipse or the bottom of the ellipse, shifts it with a magnitude corresponding to the shifting function in place of x: (x-k\pi), and lastly, depending on the part of the period (which interval) said x value is in, shifts the point up by one or down by one to place it in the correct location. The problem with this equation is that it is messy to write out and complicated to understand. I want a function that gives the graph in a nice, compact form.

So, I need a function that will take the main part of the piecewise equation, \sqrt{1-\frac{4(x-k\pi)^{2}}{\pi^{2}}}, and decide several things based on where x is located: whether to place a negative sign out front, whether to add or subtract one, and how much it should be shifted. When you think about it, this function could be described using several pieces: f(x)=s(x)\cdot m(k(x))+o(x): s(x) will yield \pm1 depending on which part of the period x is in, m(x) is the main part of the piecewise equation, k(x) is the shifting function (I guess technically it shouldn’t be m(k(x)), because k(x) is replacing k, but I’ll just ignore this for now because it makes f(x) easier to define by parts of other functions), and o(x) decides whether to add or subtract the final 1. I’ll describe what I determined to be s(x), m(x), k(x), and o(x) next.

For s(x), I just need a 1 or -1, depending on x. The obvious idea that comes to me is describing s(x) as -1 to some power that varies. Just taking (-1)^{x} will give alternating 1′s and -1′s, but only at the integers, and is indeed undefined for many non-integer x. To remedy this problem, I’ll take (-1)^{\left\lfloor x\right\rfloor }, where \lfloor x\rfloor is the floor function:

Unfortunately, (-1)^{\lfloor x\rfloor} still gives me the values at the wrong places:

What can I do to make \lfloor x\rfloor change values at different places? Scaling x by some number would work. Let’s take x=\frac{\pi}{4} as an example. At x=\frac{\pi}{4}, we want a -1, but (-1)^{\lfloor\frac{\pi}{4}\rfloor}=1, because on the part of the period of f(x) from 0 to \pi, the bottom part of the ellipse is used. \lfloor\frac{x}{\pi}\rfloor gives the floor function, but changes at intervals of \pi instead of at the integers. (-1)^{\lfloor\frac{x}{\pi}\rfloor} actually gives the opposite values that we want for the parts of the period:

However, a solution is obvious: Instead of using (-1)^{\lfloor\frac{x}{\pi}\rfloor}, use (-1)^{\lfloor\frac{x}{\pi}\rfloor-1}. Now we’ve got our s(x)! Two down (counting the main part of the equation that we already know), two to go!

Let’s do o(x) next, because it’s very similar to s(x). o(x) should actually return the OPPOSITE of s(x), because we want a +1 at the beginning when we want a -1 at the end, and vice versa. So o(x) is actually very easy to obtain, it’s one of the equations suggested for s(x): (-1)^{\lfloor\frac{x}{\pi}\rfloor} Just one part left and we’ll have our function!

The only part we still have to determine is k(x), how much we should shift the function. By looking at the graph of f(x), we can see that from -\frac{\pi}{2} to \frac{\pi}{2}, the ellipse is in the right spot but moved up or down, which is fixed by o(x). From \frac{\pi}{2} to \frac{3\pi}{2}, the ellipse should be moved over by \pi. From \frac{3\pi}{2} to \frac{5\pi}{2}, it should be moved over by 2\pi, and so on. The shift, then, is taking the original domain of the ellipse, \left[-\frac{\pi}{2},\frac{\pi}{2}\right] and shifting it by k\cdot\pi when x is k\cdot\pi (k\in\mathbb{Z}) from it’s spot on the original domain. Since k(x) will be multiplied by \pi, it will have to be fixed to return a while number for all values of x. Sounds like another job for the floor function! Taking \lfloor\frac{x}{\pi}\rfloor gives this graph:

which is correct, but moved to the right too far by \frac{\pi}{2}. To solve this problem, we’ll just shift it left \frac{\pi}{2}, and this is the final equation for k(x): \lfloor\frac{x+\frac{\pi}{2}}{\pi}\rfloor

Looks like that’s about all we need: we have s(x), m(x), k(x), and o(x). Combining these equations correctly results in the “good” version of f(x).

f(x)=(-1)^{\lfloor\frac{x}{\pi}\rfloor-1}\cdot\sqrt{1-\frac{4\left(x-\lfloor\frac{x+\frac{\pi}{2}}{\pi}\rfloor\cdot\pi\right)^{2}}{\pi^{2}}}+(-1)^{\lfloor\frac{x}{\pi}\rfloor}

That was fun, but it feels like I cheated, using the floor function. Considering that the floor function does not have a standard (or at least well known) derivative or integral, this makes f(x) ineligible for almost any calculus manipulation. The fact that it is just pieces of a shifted ellipse tells us that we can just use the original ellipse’s equation to determining the properties of f(x), but it would be nice to be able to do it directly from f(x). If anyone has any ideas on how to get a more analytic version of f(x), please comment. That’s about all for now, I think I’ll post a proof of some summation rules that I’ve derived next.

By the way, if you’re curious about what this graph looks like in polar form, here’s a link: http://tinyurl.com/periodic-cusps . It shows the real graph, and a polar form.

Follow

Get every new post delivered to your Inbox.