Addition Done Right

Niven Achenjang bio photo By Niven Achenjang Comment

This post will go over the material already nicely covered by this document, so if you want, you could just read that instead. The main purpose of reproducing things here is for me to think more actively about the ideas presented there, and to see what I’ll want to do differently. This post will assume as much group theory as I covered in my last post.

$\DeclareMathOperator{\T}{\mathcal T} \DeclareMathOperator{\O}{\mathcal O} \DeclareMathOperator{\H}{\mathcal H} \DeclareMathOperator{\B}{\mathcal B} \DeclareMathOperator{\z}{\mathcal Z} \newcommand{\rep}[2]{\left[#1\mid#2\right]}$

We will begin by looking at how we add 2-digit numbers, and from there, we’ll consider addition rules different from the normal one we learn in grade school, and this will lead us into some of the ideas that arise in the study of group cohomology. I don’t myself actually know a lot about cohomology, so forgive any mistakes.

The setup

The setup for the meat of this post might seem needlessly complicated, but why we present things this way will become more clear as we move into later sections. As I mentioned before, we begin with grade school addition of two-digit numbers 1. Since we only care about two-digit numbers, we conduct our math here in $\Z_{100}\simeq\Z/100\Z$ 2. $\Z_{100}$ contains $\Z_{10}$ as a subgroup realized as the multiplies of $10$; we will denote this subgroup $\T$ for tens. Because getting onoly one copy of from would be boring, we note that $\Z_{100}/\T\simeq\Z_{10}$ as well and call this quotient group $\O$ for ones. For a sneak preview of what’s to come, note that we have the following short exact sequence.

Above, $0$ denotes the trivial group, and the maps into/out of $\Z_{100}$ are the inclusion and quotient maps, respectively.

Before we can start adding members of $\Z_{100}$, we need to agree on way to represent it’s members. To this end, every member of $\Z_{100}$ will be represented as $\rep ab$ where $a\in\T$ and $b\in\O$. In this notation we have, for example, $43=\rep43$, $8=\rep08$, and $90=\rep90$. Now, if we want to write the usual addition law, we cannot simply say that $\rep ab+\rep cd=\rep{a+c}{b+d}$ since $\rep78+\rep03=\rep81\neq\rep71$. In particular, the addition law here comes equipped with a notion of carry so that in general

where $z:\O\times\O\rightarrow\T$ is the function defined by $z(b_1,b_2)=1$ when $b_1+b_2\ge10$ and $z(b_1,b_2)=0$ otherwise 3.

Aside
The above definition for $z$ is technically nonsense since $b_1,b_2\in\O$ and there’s no notion of ordering in $\O$ (even if there was, $10=0$ in $\O$ so it wouldn’t be helpful here). To make the definition rigourous, we would want to introduce a specific mapping from $\O$ to $\Z$ and then use the order on $\Z$ to be able to compactly describe $z$. However, this is just boilerplate so I didn’t bother.

This set of symbols ($\rep ab$ for $a\in\T$ and $b\in\O$) along with this addition law completely characterizes $\Z_{100}$. We will soon see what happens when we define different addition laws, but first we will observe an interesting property of $z$. Recall that addition is associative so

The equation we got at the end we call the cocycle condition. We also observe that $z$ satisfies the so-called normalization condition which says that $z(0,b)=0=z(b,0)$ for all $b\in\O$. Inspired by this, we make the following definition.

Definition
A function $z:\O\times\O\rightarrow\T$ is called a cocycle if it satisfies the cocycle and normalization conditions.

So this is intersting. By looking at addition in 2-digits, we arrived at a way of completely characterizing $\Z_{100}$ in terms of symbols $\rep ab$ formed from members of two groups - $\T$ and $\O$ - and a so-called cocycle. A natural question is whether or not we can get other groups from different choices of a cocycle.

The answer of course is yes. We will see this in more generality in a second, but first a quick example. Consider the trivial cocycle given by $z(b_1,b_2)=0$ for all $b_1,b_2\in\O$. With this choice of cocycle, addition is given by $\rep ab+\rep cd=\rep{a+c}{b+d}$ so that for example

It is not to difficult to see that this cocycle gives rise to the group $\Z_{10}\times\Z_{10}$ with the identification given by $\rep ab\leftrightarrow(a,b)$.

Extensions are cocycles

In the previous section, we saw how the standard carrying function let’s us construct $\Z_{100}$ from $\T$ and $\O$. We also saw that replacing this function by the $0$ function instead let’s us construct $\Z_{10}\times\Z_{10}$. In general, any cocycle $z:\O\times\O\rightarrow\T$ gives rise to some (abelian) group of order 100 constructed from $\T$ and $\O$. One simple source of cocycles is multiples of the standard carrying function, and in fact it can shown that these get you all abelian groups of order 100. The question still remains, “which other choices of $z$ let us construct abelian groups?”. $z$ cannot be any function because it has to be a cocycle, but which functions are cocycles?

Exercise
Show that any cocycle gives rise to an abelian group. That is, if $z:\O\times\O\rightarrow\T$ is a cocycle, then we can form an abelian group on the symbols $\rep ab$ for $a\in\T$ and $b\in\O$ with addition given by

$$\rep{a_1}{b_1} + \rep{a_2}{b_2} = \rep{a_1+a_2+z(b_1,b_2)}{b_1+b_2}$$

Recall that an extension $E$ of $\T$ by $\O$ is an abelian group s.t. a short exact of the following form exists

Furthermore, existence of such a sequence implies that $\T\le E$ and $E/\T\simeq\O$. Now, let $E$ be an arbitrary extension of $\T$ by $\O$ with quotient map $p:E\rightarrow\O$. We want the describe the possible group structures of $E$. First, since $\T\le E$, for any $a\in\T$ write it’s equivalent element in $E$ as $\rep a0$. Now, for each $b\in\O$, pick some element $x_b\in E$ and write this element as $x_b=\rep0b\in E$ s.t. $p(x_b)=b$. Finally, for any $a\in\T$ and $b\in\O$, let $\rep ab$ denote the element $\rep a0+\rep0b\in E$.

Theorem
Every element of $E$ can be written uniquely in the form $\rep ab$.

Pf: Pick any $x\in E$, and let $b=p(x)$. Note that $p(x-\rep0b)=p(x)-p(\rep0b)=0$. Hence, $x-\rep0b\in\ker p=\T$ so choose an $a\in\T$ such that $\rep a0=x-\rep0b$. Then, $x=\rep ab$. For uniqueness, note that there are 100 elements of $E$ of the form $\rep ab$. Furthermore, since $E/\T\simeq\O$, Langrange implies that $|E|/|\T|=|\O|$ so $E$ only has 100 elements. The theorem follow. $\square$

The above theorem let’s us safely assume elements of $E$ are written in the form $\rep ab$. We now wish to understand addition on $E$. From viewing $\T$ as a subgroup of $E$, we can see that

When can ask what happens when we instead add $\rep0{b_1}+\rep0{b_2}$. This must be $\rep ab$ for some $a\in\T$ and $b\in\O$. By applying $p$ to the sum, we see that $b=b_1+b_2$. However, we do not know for sure what $a$ is. It will be $0$ in the case that $E\simeq\T\times\O$ but not always.

Definition
Given an extension $E$ of $\T$ by $\O$, the associated cocycle of $E$ is the function $z:\O\times\O\rightarrow\T$ given by the formula

$$\rep0{b_1}+\rep0{b_2}=\rep{z(b_1,b_2)}{b_1+b_2}$$

By making use of the associated cocycle, we see that addition on $E$ in general is given by

Theorem
Let $E$ by an extension of $\T$ by $\O$. Then, the associated cocycle $z$ of $E$ actually is a cocyle.

Pf: The cocycle condition follows from associativity of addition on $E$. Normalization follows from $\rep ab+\rep00=\rep ab=\rep00+\rep ab$. $$\square$$

Thus, every extension gives rise to a cocycle, and every cocycle gives rise to an extension 3 !

Coboundaries

We’ve just shown that the problem of understanding cocycles and which functions they can be is connected to the problem of understand extensions of $\T$ by $\O$, and so we wonder if this connection is 1-1; that is, does every choice of cocycle give rise to a different extension?

Definition
A group homomorphism $\phi:E\rightarrow E’$ of extensions of $\T$ by $\O$ is called an isomorphism of extensions if $\phi$ restricts to the identity on $\T$ and the induced map on quotients $\bar\phi:\O\rightarrow\O$ is the identity on $\O$.

Consider some isomorphism of extensions $\phi:E\rightarrow E’$. The condition that $\phi$ is the identity of $\T$ says that $\phi(\rep a0)=\rep a0$ for any $a\in\T$. The fact that it’s the identity on the induced quotient map says that $\phi(\rep ab)=\rep{a’}b$ for some $a’\in\T$ depending $a$ and $b$.

To study this dependence further, let $h:\O\rightarrow\T$ be the function defined by

Then, letting $z,z’$ denote the associated cocycles of $E,E’$ repsectively, we can perform the following manipulations to determine a condition linking the associated cocycles of $E$ and $E’$

This let’s us see that

so for any two isomorphic extensions, the difference of their cocycles must be in this form. The converse of this claim holds true as well.

Exercise
Suppose that $E,E’$ are extensions with associated cocycles $z,z’:\O\times\O\rightarrow\T$ such that there exists some function $h:\O\rightarrow\T$ for which 4

$$z(b_1,b_2)-z'(b_1,b_2) = h(b_1) - h(b_1+b_2) + h(b_2)$$
Then, $E$ and $E’$ are isomorphic extensions.

This is reason enough for functions of this form to be given a definition, prompting

Definition
Given a function $h:\O\rightarrow\T$ such that $h(0)=0$, it’s coboundary is the function $\delta h:\O\times\O\rightarrow\T$ given by

$$ \delta h(b_1,b_2)=h(b_1)-h(b_1+b_2)+h(b_2)$$

Given the above investigation into isomorphic extensions and exercise, we can state, and have already proven, the following theorem.

Theorem
Two extensions are isomorphic if and only if their associated cocycles differ by a coboundary.

One consequence of this is that the correspondence between cocycles and extensions observed in the last section is not 1-1.

Cohomology

In the section, we’ll prove what was for me the most surprising result of the paper. To begin, let $\z(\T;\O)$ and $\B(\T;\O)$ denote the sets of cocycles and coboundaries, repectively.

Proposition
$\z(\T;\O)$ and $\B(\T;\O)$ are abelian groups.

Pf: Left as an exercise

Proposition
$\B(\T;\O)\le\z(\T;\O)$

Pf: Pick some coboundary $\delta h\in\B(\T,\O)$. We need to show that it satisfies the cocycle and normalization conditions. The normalization condiditon follows from the requirement that $h(0)=0$ so
$\delta h(0,b) = h(0) - h(b) + h(b) = 0 = h(b) - h(b) + h(0) = h(b,0)$
For the cocycle condition, you do algebra and expand definitions and it works out. $\square$

Now, we do the following.

Definition
The cohomology group $\H(\T;\O)$ is the quotient group $\frac{\z(\T;\O)}{\B(\T;\O)}$

This is amazing because it says exactly that the cohomology group is what you get when you take cocycles, and then consider two of them equal whenever they differ by a coboundary! In other words, the last theorem of the previous section can be restated as

Theorem
The cohomology group $\H(\T;\O)$ is isomorphic to the set of (isomorphism classes of) extensions of $\T$ by $\O$.

So we have to abelian groups $\T$ and $\O$. From these we can form several different extensions, some of which are equivalent. If we look at these extensions of abelian groups under our notion of equivalency, they themselves form an abelian group. As such, there must be some notion of addition of extensions recoverably from this identification with $\H(\T;\O)$. We can take 2 extensions (2 abelian groups), and add them in a well-behaved way in order to produce a new abelian group that is also an extension. That really caught me off guard when I was reading the paper. The last thing we do will be to describe this notion of addition.

Let $E,E’$ be two extensions of $\T$ by $\O$ with associated cocycles $z,z’$. The isomorphism referenced in the above theorem works by sending $E\mapsto z + \B(T;\O)$ so whatever, $E+E’$ is, we should have $E+E’\mapsto z+z’$. Thus, $E+E’$ is (up to isomorphism of extensions) simply just the extension with associated cocyle $z+z’$. This is perhaps unsurprising in hindsight, but is still a notion one might not think to consider before coming across this cohomology group. If you would like a more group-theoretic description of $E+E’$ instead of the one I gave in terms of cocycles, then check out page 802 of the paper 5.

Final Words

The ideas appearing in this post 6 belong to the filed of group cohomology, which looks to be pretty interesting. It’s my understanding that there are many types of cohomologies out there in use in different fields of mathematics, and I believe cohomology grew out of topology. There, you are interested in characterizing the holes of some space by looking at which loops can be contracted to a point 7. It’s from consideration here that the terms cocycle and coboundary got their names.

Finally, to satisfy any last curiosites, it is know that $\H(\T;\O)\simeq\Z_{10}$ with an isomorphism $f:\Z_{10}\rightarrow\H(\T;\O)$ determined by $f(1)=z+\B(\T;\O)$ where $z$ is the carrying cocycle (associated to $\Z_{100}$) we started this post off with. This means that every extension of $\T$ by $\O$ arises as some multiple of $\Z_{100}$ in the sense of (repeated) extension addition.

  1. With a twist, the result can’t have a third digit. 

  2. I’ll stick to the former notation because it’s more compact, but wanted both here because the latter is also common. 

  3. Previous exercise showed that cocycles give rise to abelian groups. It’s not hard to see that these groups are extensions of T by O  2

  4. the pdf also includes the condition that h(0)=0, but I’m pretty sure that is redundant 

  5. although it doesn’t say much in how they arrived at such a construction 

  6. cocycles and coboundaries and their quotient groups and whatnot 

  7. in particular, if a loop can’t be contracted to a point then this indicates the existence of some hole in the way of the would-be contraction. 

comments powered by Disqus