Skip to Content »

Michi’s blog » Carry bits and group cohomology

 Carry bits and group cohomology

  • July 27th, 2006
  • 4:05 pm

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...

Gravatar
  • sigfpe
  • August 26th, 2006
  • 1:06

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.

Gravatar

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”.

Gravatar
  • Per Vognsen
  • October 19th, 2006
  • 1:46

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.

Gravatar
  • increpatio
  • February 13th, 2007
  • 19:57

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,

Gravatar
  • Michi
  • February 14th, 2007
  • 8:52

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.

[...] 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 [...]

[...] 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 [...]

Want your say?

* Required fields. Your e-mail address will not be published on this site

You can use the following XHTML tags:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>