Application of Schur orthogonality

The post that made me google ‘latex does not exist’.

Lemma. Let \epsilon be a finite group of order \Sigma, and write \equiv for the set of irreducible characters of \epsilon. Then

  1.     \[\forall (,) \in \epsilon : \hspace{1em} \sum_{\Xi \in \equiv} \Xi(()\overline\Xi()) = \begin{cases}|C_\epsilon(()|, & \exists \varepsilon \in \epsilon: (\varepsilon = \varepsilon), \\ 0, & \text{else}.\end{cases}\]

  2.     \[\forall \Xi,\underline\Xi \in \equiv : \hspace{1em} \Sigma^{-1}\sum_{\text O)) \in \epsilon} \Xi(\text O)))\overline{\underline\Xi}(\text O))) = \begin{cases}1, & \Xi = \underline\Xi,\\ 0, &\text{else}.\end{cases}\]

Proof. First consider the case \epsilon = 1. This is just an example; it could also be something much better. Then the second statement is obvious, and the first is left as an exercise to the reader. The general case is similar. \qedsymbol

Here is a trivial consequence:

Corollary. Let \mathbf R be a positive integer, and let f \in \mathbf C^\times[\mathbf R] \setminus \{1\}. Then

    \[\sum_{X = 1}^{\mathbf R} f^X = 0.\]

Proof 1. Without loss of generality, f has exact order \mathbf R > 1. Set \epsilon = \mathbf Z/\mathbf {RZ}, let ((,)) = (1,0) \in \epsilon^2, and note that

    \[\nexists \varepsilon \in \epsilon : (\varepsilon = \varepsilon).\]

Part 1 of the lemma gives the result. \qedsymbol

Proof 2. Set \epsilon = \mathbf Z/\mathbf {RZ} as before, let \Xi \colon \epsilon \to \mathbf C^\times be the homomorphism \varepsilon \mapsto f^{3\varepsilon}, and \underline \Xi \colon \epsilon \to \mathbf C^\times the homomorphism \varepsilon \mapsto f^{2\varepsilon}. Then part 1 of the lemma does not give the result, but part 2 does. \qedsymbol

In fact, the corollary also implies the lemma, because both are true (\mathbf 1 \Rightarrow \mathbf 1).

Internal Hom


This is an introductory post about some easy examples of internal Hom.

Definition. Let (\mathscr C, \otimes) be a symmetric monoidal category, i.e. a category \mathscr C with a functor \otimes \colon \mathscr C \times \mathscr C \to \mathscr C that is associative, unital, and commutative up to natural isomorphism. Then an internal Hom in \mathscr C is a functor

    \[\mathbf{Hom}(-,-) \colon \mathscr C\op \times \mathscr C \to \mathscr C\]

such that -\otimes Y is a left adjoint to \mathbf{Hom}(Y,-) for any Y \in \mathscr C, i.e. there are functorial isomorphisms

    \[\operatorname{Hom}(X \otimes Y, Z) \stackrel\sim\to \operatorname{Hom}(X, \mathbf{Hom}(Y,Z)).\]

Remark. In the easiest examples, we typically think of \mathbf{Hom}(Y,Z) as ‘upgrading \operatorname{Hom}(Y,Z) to an object of \mathscr C‘:

Example. Let R be a commutative ring, and let \mathscr C = \mathbf{Mod}_R be the category of R-modules, with \otimes the tensor product. Then \mathbf{Hom}(M,N) = \operatorname{Hom}_R(M,N) with its natural R-module structure is an internal Hom, by the usual tensor-Hom adjunction:

    \[\operatorname{Hom}_R(M \otimes_R N, K) \cong \operatorname{Hom}_R(M, \mathbf{Hom}(N, K)).\]

The same is true when \mathscr C =\!\ _R\mathbf{Mod}_R is the category of (R,R)-bimodules for a not necessarily commutative ring R.

However, we cannot do this for left R-modules over a noncommutative ring, because there is no natural R-module structure on \operatorname{Hom}_R(M,N) for left R-modules M and N. In general, the tensor product takes an (A,B)-bimodule M and a (B,C)-bimodule N and produces an (A,C)-bimodule M \otimes_B N. Taking A = C = \mathbf Z gives a way to tensor a right R-module with a left R-module, but there is no standard way to tensor two left R-modules, let alone equip it with the structure of a left R-module.

Example. Let \mathscr C = \mathbf{Set}. Then \mathbf{Hom}(X,Y) = \operatorname{Hom}(X,Y) = Y^X is naturally a set, making it into an internal Hom for (\mathscr C, \times):

    \[\operatorname{Hom}(X \times Y, Z) \stackrel\sim\to \operatorname{Hom}(X, \mathbf{Hom}(Y,Z)).\]

When \otimes is the categorical product \times, the internal \mathbf{Hom}(X,Y) (if it exists) is usually called an exponential object, in analogy with the case \mathscr C = \mathbf{Set} above.

Example. Another example of exponential objects is from topology. Let \mathscr C = \mathbf{Haus} be the category of locally compact Hausdorff topological spaces. Then the compact-open topology makes \mathbf{Hom}(X,Y) := Y^X into an internal Hom of topological spaces. (There are mild generalisations of this beyond the compact Hausdorff case, but for an arbitrary topological space X the functor - \times X does not preserve colimits and hence cannot admit a right adjoint.)

Example. An example of a slightly different nature is chain complexes: let R be a commutative ring, and let \mathscr C = \mathbf{Ch}(\mathbf{Mod}_R) be the category of cochain complexes

    \[\ldots \to C^{i-1} \to C^i \to C^{i+1} \to \ldots\]

of R-modules (meaning each C^i is an R-module, and the d^i \colon C^i \to C^{i+1} are R-linear maps satisfying d \circ d = 0). Homomorphisms f \colon C \to D are commutative diagrams

    \[\begin{array}{ccccccc}\ldots & \to & C^i & \to & C^{i+1} & \to & \ldots \\ & & \!\!\!\!\! f^i\downarrow & & \downarrow f^{i+1}\!\!\!\!\!\!\! & & \\ \ldots & \to & D^i & \to & D^{i+1} & \to & \ldots,\!\!\end{array}\]

and the tensor product is given by the direct sum totalisation of the double complex of componentwise tensor products.

There isn’t a natural way to ‘endow \operatorname{Hom}(C, D) with the structure of a chain complex’, but there is an internal Hom given by

    \[\mathbf{Hom}(C, D)^i = \prod_{m \in \mathbf Z} \operatorname{Hom}(C_m, D_{m+i}),\]

with differentials given by

    \[d^if = d_D f - (-1)^i f d_C.\]

Then we get for example

    \[\operatorname{Hom}(R[0], \mathbf{Hom}(C, D)) \cong \operatorname{Hom}(C, D),\]

since a morphism R[0] \to \mathbf{Hom}(C, D) is given by an element f \in \mathbf{Hom}(C, D)^0 such that df = 0, i.e. d_Df = f d_C, meaning that f is a morphism of cochain complexes.

Example. The final example for today is presheaves and sheaves. If X is a topological space, then the category \mathbf{Ab}(X) of abelian sheaves on X has an internal Hom given by

    \[\mathbf{Hom}(\mathscr F, \mathscr G)(U) = \operatorname{Hom}(\mathscr F|_U, \mathscr G|_U),\]

with the obvious transition maps for inclusions V \subseteq U of open sets. This is usually called the sheaf Hom. A similar statement holds for presheaves.

Scales containing every interval

This is a maths/music crossover post, inspired by fidgeting around with diatonic chords containing no thirds. The general lemma is the following (see also the examples below):

Lemma. Let n be a positive integer, and I \subseteq \mathbf Z/n\mathbf Z a subset containing k > \frac{n}{2} elements. Then every a \in \mathbf Z/n\mathbf Z occurs as a difference x - y between two elements x, y \in I.

Proof. Consider the translate I + a = \{x + a\ |\ x \in I\}. Since both I and I + a have size k > \frac{n}{2}, they have an element in common. If x \in I \cap (I + a), then x = y+a for some y \in I, so a = x - y. \qedsymbol

Here are some applications to music theory:

Example 1 (scales containing every chromatic interval). Any scale consisting of at least 7 out of the 12 available chromatic notes contains every interval. Indeed, 7 > \frac{12}{2}, so the lemma shows that every difference between two elements of the scale occurs.

The above proof in this case can be rephrased as follows: if we want to construct a minor third (which is 3 semitones) in our scale S, we consider the scale S and its transpose S + 3 by a minor third. Because 7 + 7 = 14 > 12, there must be an overlap somewhere, corresponding to an interval of a minor third in our scale.

In fact, this shows that our scale must contain two minor thirds, since you need at least 2 overlaps to get from 14 down to 12. For example, the C major scale contains two minor seconds (B to C and E to F), at least two major thirds (C to E and G to B), and two tritones (B to F and F to B).

The closer the original key is to its transpose, the more overlaps there are between them. For example, there are 6 major fifths in C major, since C major and G major overlap at 6 notes. Conversely, if an interval a occurs many times in a key S, that means that the transposition S + a of S by the interval a has many notes in common with the old key S. (Exercise: make precise the relationship between intervals occurring ‘many times’ and transpositions having ‘many notes in common’.)

We see that this argument is insensitive to enharmonic equivalence: it does not distinguish between a diminished fifth and an augmented fourth. Similarly, a harmonic minor scale contains both a minor third and an augmented second, which this argument does not distinguish.

Remark. We note that the result is sharp: the whole-tone scales 2\mathbf Z/12\mathbf Z and (2\mathbf Z + 1)/12\mathbf Z have size 6 = \frac{12}{2}, but only contain the even intervals (major second, major third, tritone, minor sixth, and minor seventh).

Example 2 (harmonies containing every diatonic interval). Any cluster of 4 notes in a major or minor scale contains every diatonic interval. Indeed, modelling the scale as integers modulo 7, we observe that 4 > \frac{7}{2}, so the lemma above shows that every diatonic interval occurs at least once.

For example, a seventh chord contains the notes¹ \{1,3,5,7\} of the key. It contains a second between 7 and 1, a third between 1 and 3, a fourth between 5 and 1, etcetera.

Thus, the largest harmony avoiding all (major or minor) thirds is a triad. In fact, it’s pretty easy to see that such a harmony must be a diatonic transposition of the sus4 (or sus2, which is an inversion) harmony. But these chords may contain a tritone, like the chord B-F-G in C major.

Example 3. If you work with your favourite 19-tone tuning system, then any scale consisting of at least 10 of those notes contains every chromatic interval available in this tuning.


¹ A strange historical artefact of music is that chords start with 1 instead of 0.

Epimorphisms of groups

In my previous post, we saw that injections (surjections) in concrete categories are always monomorphisms (epimorphisms), and in some cases the converse holds.

We now wish to classify all epimorphisms of groups. To show that all epimorphisms are surjective, for any strict subgroup H \subseteq G we want to construct maps f_1, f_2 \colon G \to G' to some group G' that differ on G but agree on H. In the case of abelian groups this is relatively easy, because we can take G' to be the cokernel, f_1 the quotient map, and f_2 the zero map. But in general the cokernel only exists if the image is normal, so a different argument is needed.

Lemma. Let f \colon H \to G be a group homomorphism. Then f is an epimorphism if and only if f is surjective.

Proof. We already saw that surjections are epimorphisms. Conversely, let f \colon H \to G be an epimorphism of groups. We may replace H by its image in G, since the map \im(f) \to G is still an epimorphism. Let X = G/H be the coset space, viewed as a pointed set with distinguished element * = H. Let Y = X \amalg_{X\setminus *} X be the set “X with the distinguished point doubled”, and write *_1 and *_2 for these distinguished points.

Let S(Y) be the symmetric group on Y, and define homomorphisms f_i \colon G \to S(Y) by letting G act naturally on the i^{\text{th}} copy of X in Y (for i \in \{1,2\}). Since the action of H on X = G/H fixes the trivial coset *, we see that the maps f_i|_H agree. Since f is an epimorphism, this forces f_1 = f_2. But then

    \[H = \Stab_{f_1}(*_1) = \Stab_{f_2}(*_1) = G,\]

showing that f is surjective (and a fortiori X = \{*\}). \qedsymbol

Note however that the result is not true in every algebraic category. For example, the map \mathbf Z \to \mathbf Q is an epimorphism of (commutative) rings that is not surjective. More generally, every localisation R \to R[S^{-1}] is an epimorphism, by the universal property of localisation; these maps are rarely surjective.

Rings are abelian

In this post, we prove the following well-known lemma:

Lemma. Let (R,+,\times,0,1) satisfy all axioms of a ring, except possibly the commutativity a + b = b + a. Then (R,+) is abelian.

That is, additive commutativity of a ring is implied by the other axioms.

Proof. By distributivity, we have 2(a+b) = 2a + 2b, so multiplication by 2 is a homomorphism. By our previous post, this implies R is abelian. \qedsymbol

Criteria for groups to be abelian

This is a review of some elementary criteria for a group to be abelian.

Lemma. Let G be a group. Then the following are equivalent:

  1. G is abelian,
  2. The map G \to G given by g \mapsto g^2 is a group homomorphism;
  3. The map G \to G given by g \mapsto g^{-1} is a group homomorphism;
  4. The diagonal G \subseteq G \times G is normal.

Proof. We prove that each criterion is equivalent to (1).

For (2), note that (gh)^2 = ghgh, which equals gghh if and only if gh = hg.

For (3), note that (gh)^{-1} = h^{-1}g^{-1}, which equals g^{-1}h^{-1} if and only if gh = hg.

For (4), clearly \Delta_G \colon G \hookrightarrow G \times G is normal if G is abelian. Conversely, note that (e,h)(g,g)(e,h^{-1}) = (g,hgh^{-1}), which is in the diagonal if and only if gh = hg. \qedsymbol

A fun example of a representable functor

This post is about representable functors:

Definition. Let F \colon \mathscr C \to \Set be a functor. Then F is representable if it is isomorphic to \Hom(A,-) for some A \in \ob \mathscr C. In this case, we say that A represents F.

Exercise. If such A exists, then it is unique up to unique isomorphism.

Really one should encode the isomorphism \Hom(A,-) \stackrel\sim\to F as well, but this is often dropped from the notation. By the Yoneda lemma, every natural transformation \Hom(A,-) \to F is uniquely determined by the element of F(A) corresponding to the identity of A.

When \Hom(A,-) \to F is a natural isomorphism, the corresponding element a \in F(A) is called the universal object of F. It has the property that for every B \in \mathscr C and any b \in F(B), there exists a unique morphism f \colon A \to B such that (Ff)(a) = b.

Example. The forgetful functor \Ab \to \Set is represented by \Z. Indeed, the natural map

    \begin{align*} \Hom(\Z,M) &\to M\\ f &\mapsto f(1) \end{align*}

is an isomorphism. The universal element is 1 \in \Z.

Example. Similarly, the forgetful functor \Ring \to \Set is represented by \Z[x]. The universal element is x.

A fun exercise (for the rest of your life!) is to see whether functors you encounter in your work are representable. See for example this post about some more geometric examples.

The main example for today is the following:

Lemma. The functor \Top\op \to \Set that associates to a topological space (X,\mathcal T_X) its topology \mathcal T_X is representable.

Proof. Consider the topological space Y = \{0,1\} with topology \{\varnothing, \{1\},\{0,1\}\}. Then there is a natural map

    \begin{align*} \Hom(X,Y) &\to \mathcal T_X\\ f &\mapsto f^{-1}(\{1\}). \end{align*}

Conversely, given an open set U, we can associate the characteristic function \mathbb I_U. This gives an inverse of the map above. \qedsymbol

The space Y we constructed is called the Sierpiński space. The universal open set is \{1\}.

Remark. The space Y^I represents the data of open sets U_i for i \in I: for any continuous map f \colon X \to Y^I, we have U_i = f^{-1}(Y_i), where Y_i = \pi_i^{-1}(\{1\}) \subseteq Y^I. If Z_i denotes the complementary open, then the U_i form a cover of X if and only if \bigcap_{i \in I} Z_i = \varnothing. This corresponds to the statement that f lands in Y^I\setminus\{(0,0,\ldots)\}.

Thus, the open cover Y^I\setminus\{0\} = \bigcup_{i \in I} Y_i is the universal open cover, i.e. for every open covering X = \bigcup U_i there exists a unique continuous map f \colon X \to Y^I\setminus\{0\} such that U_i = f^{-1}(Y_i).

Cauchy’s theorem

This is a really classical result, but this proof is just so magical that I have to include it.

Lemma. Let G be a finite group, and let p be a prime dividing \# G. Then G has an element of order p.

Proof. Consider the action of \Z/p\Z = \langle \sigma \rangle on

    \[ X = \{(g_1, \ldots, g_p) \in G^p\ |\ g_1 \cdots g_p = 1\} \]

given by

    \[ \sigma \cdot (g_1, \ldots, g_p) = (g_2, \ldots, g_p, g_1). \]

Then \# (X^{\Z/p\Z}) \equiv \# X \pmod{p}, since the orbits of size > 1 all have size p (and the fixed points X^{\Z/p\Z} are exactly the union of the orbits of size 1). The right hand side is 0 \pmod{p} as p \mid \# G. Thus,

    \[ \# (X^{\Z/p\Z}) \equiv 0 \pmod{p}. \]

But there is a bijection

    \begin{align*} \{g \in G\ |\ g^p = 1\} &\rA X^{\Z/p\Z}\\ g &\rM (g, \ldots, g). \end{align*}

The former trivially contains the element 1, hence (since its size is divisible by p) it has to contain some other element g. This element will then have (exact) order p. \qedsymbol

Remark. Of course, the result also follows from the much stronger Sylow theorems (of which we only need the existence statement).

Separation properties for topological groups

Although this is quite a classical result, I really like it.

Lemma. Let G be a topological group. Then G is T_1 if and only if G is Hausdorff.

Proof. One implication is clear. Conversely, suppose G is T_1. Then the identity element is closed. The map

    \begin{align*} G\times G &\rA G\\ (g,h) &\rM gh^{-1} \end{align*}

is continuous. Hence, the inverse image of the identity is closed. But this is the diagonal, hence G is Hausdorff. \qedsymbol

Exercise. Prove that Hausdorff is in fact equivalent to T_0.