Michi’s blog » Blog Archive » Carry bits and group cohomology

Carry bits and group cohomology

July 27th, 2006

Got treated today to a really nice workout in group cohomology; most of which is well worth sharing, since seeing it done once gave me a lot of insight.

So, if we pick $\mathbb Z/10$ and view it as the set 0,1,2,3,4,5,6,7,8,9 and with the group operation given by a*b = a+b % 10, then one standard 2-cocycle is the function
$f(a,b) = \begin{cases}1&a+b\geq10\\0&\text{else}\end{cases}$
That this actually does form a cocycle would be the same as requiring
f(b,c)-f(a*b,c)+f(a,b*c)-f(a,b)=0
or regrouped
f(a*b,c)+f(a,b)=f(a,b*c)+f(b,c)
which is to say that the number of carry bits generated when adding three digits does not depend on associativity.

This cocycle classifies the group extension
$0 \to \mathbb Z/10 \to \mathbb Z/100 \to \mathbb Z/10 \to 0$
with the first map taking $a+10\mathbb Z\mapsto 10a+100\mathbb Z$ and the second taking $b+100\mathbb Z\mapsto b+10\mathbb Z$

Now, this is a nontrivial extension – which is equivalent to it not being a coboundary – by the following calculation:
Suppose f=dg. Then f(a,b)=g(a)+g(b)-g(a*b). So, since f(0,0)=0, we get g(0)-g(0)+g(0)=0, so g(0)=0. For any b≤8, we also get 0=f(1,b)=g(b)-g(b+1)+g(1), so g(b+1)=g(b)+g(1) and thus by induction, g(b)=bg(1) for all 0≤b≤9.
But, now, 1=f(1,9)=g(9)-g(0)+g(1)=10g(1)=0, which is a contradiction.

Thus f is not a coboundary, and thus has a nontrivial cohomology class associated to it.

One further useful observation is that f(a,b)=(a+b-a*b)/10.

Note, that if we started out with addition in base B for some arbitrary B, not one single line of the above would have had anything but the most trivial updates needed. Thus, this argument holds for any base, and not only for base 10.

Now, suppose we pick ourselves some g in $H^1(\mathbb Z/B,\mathbb Z/B)=\operator{Hom}(\mathbb Z/B,\mathbb Z/B)$ – let’s even decide to take the identity. So ga=a for any a in our $\mathbb Z/B$ . Then the Bockstein of this is the image under the connecting homomorphism under the long exact sequence in cohomology induced by the short exact sequence
$0 \to \mathbb Z/B \to \mathbb Z/B^2 \to \mathbb Z/B \to 0$
with $a+B\mathbb Z\mapsto Ba+B^2\mathbb Z$ and $b+B^2\mathbb Z\mapsto b+B\mathbb Z$ as above.

So the class [g] maps first to some set map $\hat g\colon\mathbb Z/B\to\mathbb Z/B^2$ , which we choose to be the one we create by identifying $\mathbb Z/B$ with the integers 0,1,…,B-1. Thus the images of g end up living in $\mathbb Z/B^2$ without us having to do any extra work for it. This map, then, we can throw along the differential, and then we get a cocycle; so that we know that it takes values in $B\mathbb Z/B^2\mathbb Z$ , so we can “just” divide by B to get something in the right universe for our Bockstein image.

Applied to our specific g, note that
$d\hat g(a,b)=\hat g(a)-\hat g(a*b)+\hat g(b)=a+b-a*b$
and so
$\beta g(a,b)=\frac{a+b-a*b}B$
which is our carry bit map all over again.

If we happen to have a generic g, then we get a similar result; only without being able to use $\hat ga=ga=a$ as comfortably. We get, in the end, for a 1-cocycle g:
$\beta g(a,b)=\frac{ga+gb-g(a*b)}B$

I wanted to talk about Bocksteins and the d_2 differential in the LHS spectral sequence at this point, but I’m no longer certain of what these, if anything, have to do with each other, so I won’t.

7 People had this to say...

sigfpe Said...

Part of this was originally presented to me as a joke. You can only tell it to someone who’s a good enough mathematician to understand basic group cohohmology but who hasn’t actually studied it yet. (This must count as the smallest demographic for a joke – but I was roughly in it at the time.) You say “I bet you’ve been doing group cohomology since you were a kid” and when they deny it you start describing the 2-cycle above and wait for them to get it. While not particularly funny, it does have the unique virtue of being a joke, not about mathematics, or mathematicians, but completely *in* mathematics.

August 26th, 2006 at 1:06

Alexandre Borovik Said...

A nice one. It is one of those observations which deserve to be much wider known. I have no Knuth on hands, it would be interesting to check whether he mentions this property of carries in his “Art of computer programming”.

August 28th, 2006 at 15:49

Per Vognsen Said...

Good stuff. If you go to Google Groups and search for old posts by James Dolan you’ll find a handful of posts where he talks about this connection in quite some detail.

October 19th, 2006 at 1:46

increpatio Said...

By comparison with the planetmath and wikipedia entries on group cohomology, should the cocycle condition

f(b,c)-f(a*b,c)+f(a,b*c)-f(a,b)=0

have the first term multiplied by a?

Of course, then it’s wrong; unless you’re defining some sort of trivial action I’m not seeing.

(I would like to get the example clear in my head; I don’t know enough group cohomology : ( )

Thanks,

February 13th, 2007 at 19:57

Michi Said...

increpation: You are, of course right, in general. For the full Hochschild cocycle condition, you’ll want the last term to be right multiplied by c as well.

The clou here is that in the group cohomology ring
H(G,Z/10)
in which we’re doing all of this, we end up actually viewing Z/10 as a trivial module; thus vanishing all the left and right actions outside the f.

February 14th, 2007 at 8:52

More math education « The Unapologetic Mathematician Said...

[...] manipulations for any student to understand why before how. I only just recently found out (via Michi’s blog) that place-value addition “really” arises from group cohomology. Did my not knowing [...]

April 14th, 2007 at 15:36

Primary School Arithmetic and Group Cohomology « Mathematics under the Microscope Said...

[...] that he had been speaking prose all his life. I was recently reminded (by Mikael Johanssons’ blog) tha tall my life I was calculating 2-cocycles.Indeed, a carry in elementary arithmetic, a digit [...]

December 25th, 2008 at 10:36

Want your say?

post navigation

about: Michi is a recent PhD working in homological algebra and applied algebraic topology. This blog is his outlet for texts with some manner of thought put into them. Over at his LiveJournal intimate details and streams of consciousness might be found.
Not all here is mathematics. All here, though, are my personal thoughts and opinions. Please read the about page (linked above) for more details.
This blog uses statcounter.com for logging and traffic analysis. In order to identify return visitors, this site will issue a cookie on viewing the blog.

Travel plans