How to add two numbers from a group theoretic perspective?

Question

It is known that adding two numbers and looking at the carrying operation has a link with cocycles in group theory. (https://www.jstor.org/stable/3072368?origin=crossref) When we add two numbers by elementary addition, we choose a basis $b$ for example $b=2$ which corresponds to the cyclic group $C_2$.

Suppose we have words $w_1,w_2$ of (possibly different) lengths from this group $C_2$, how do we add them to get a new word $w$ in elementary addition?

For example: $2=10_2=w_1$, $3=11_2=w_2$. Consider these as $w_1$ and $w_2$. Adding these numbers we get $5=101_2$ so the new word $w=101$.

(1) But how exactly is the process of adding these two "words" from $C_2 = \{0,1\}$ in group theoretic means?

(2) Is this "elementary addition" also possible for example for a non-cylcic group such as the Klein Four group?

(3) We also assign a number to such a word (b-adic expansion). Is this assignment also possible for the Klein Four group?

Thanks for your help.

Edit: In view of the plot given below, I decided to put the tag "fractals" to this question.

Answer 1

I think the point is that, forgetting the final carry, the group of $n$-digit binary words is isomorphic to $C_{2^n}$. In the simplest case, the group of 2-digit binary words is isomorphic to $C_4$, which is built as a nontrivial extension $$ 0 \to C_2 \to C_4 \to C_2 \to 0 $$ The 2-cocycle you mention is the one corresponding to this extension. In general, $C_{2^n}$ is built up as an iterated extension of $C_2$'s in the same way, with each carry being the associated 2-cocycle. If we want to avoid forgetting the final carry, we can take the limit of the whole system to get the 2-adics $\mathbb{Z}_2$. The natural numbers $\mathbb{N}$ sit inside this as the submonoid of "finite words" (words whose digits are eventually 0 as we read right to left)

Answer 2

I think I found a way how to mimic the elementary addition for arbitrary finite groups $G$:

Let $G$ be a finite group, $S \subset G$ a generating set, $|g|:=|g|_S=$ word-length with respect to $S$. Let $\phi(g,h)=|g|+|h|-|gh| \ge 0$ be the "defect-function" of $S$. The set $\mathbb{Z}\times G$ builds a group for the following operation:

$$(a,g) \oplus (b,h) = (a+b+\phi(g,h),gh)$$

On $\mathbb{N}\times G$ is the "norm": $|(a,g)| := |a|+|g|$ additive, which means that $|a \oplus b| = |a|+|b|$. Define the multiplication with $n \in \mathbb{N_0}$ to be:

$$ n \cdot a := a \oplus a \oplus \cdots \oplus a$$

(if $n=0$ then $n \cdot a := (0,1) \in \mathbb{Z} \times G$).

A word $w := w_{n-1} w_{n-2} \cdots w_0$ is mapped to an element of $\mathbb{Z} \times G$ as follows:

$$\zeta(w) := \oplus_{i=0}^{n-1} (m^i \cdot (0,w_i))$$

where $m := \min_{g,h\in G, \phi(g,h) \neq 0} \phi(g,h)$.

We let $|w|:=|\zeta(w)|$ and $w_1 \oplus w_2:=\zeta(w_1)\oplus \zeta(w_2)$

Then we have $|w_1 \oplus w_2| = |w_1|+|w_2|$.

For instance for the Klein four group $\{0,a,b,c=a+b\}$ generated by $S:=\{a,b\}$, we get sorting the words $w$ by their word-length:

$$0,a,b,c,a0,aa,ab,ac,b0,ba,bb,bc,c0,ca,cb,cc,a00,a0a,a0b,a0c$$

corresponding to the following $\mathbb{Z}\times K_4$ elements $\zeta(w)$:

$$(0,0),(0,a),(0,b),(0,c),(2,0),(2,a),(2,b),(2,c),(2,0),(2,a),(2,b),(2,c),(4,0),(4,a),(4,b),(4,c),(4,0),(4,a),(4,b),(4,c)$$

corresponding to the the following "norms" of words $|w| = |\zeta(w)|$:

$$0,1,1,2,2,3,3,4,2,3,3,4,4,5,5,6,4,5,5,6$$

It would be interesting to see what sequence one gets for the smallest non-abelian group $S_3$. If someone likes to write a computer program to compute this, that would be great.

Related questions: How is this group theoretic construct called?

Edit: Here is some python code for the cyclic groups and an example for $b=3$:

def add(a,b,n=2):
    x,y = a
    c,d = b
    return(x+c+(y%n+d%n-(y+d)%n),(y+d)%n)

def sumadd(l,n=2):
    x = (0,0)
    for y in l:
        x = add(x,y,n=n)
    return(x)

def norm(a):
    return(abs(a[0])+abs(a[1]))

def mult(x,a,n=2):
    return(sumadd([a for i in range(x)],n=n))

def zeta(w,n=2):
    return sumadd([mult(n**(len(w)-1-i),(0,w[i]),n=n) for i in range(len(w))],n=n)

def digits(n, b):
    if n == 0:
        return [0]
    digits = []
    while n:
        digits.append(int(n % b))
        n //= b
    return digits[::-1]

b = 3
for m in range(1,20):
    w = digits(m,b)
    print(m, norm(zeta(w,n=b)))

(1, 1)
(2, 2)
(3, 3)
(4, 4)
(5, 5)
(6, 6)
(7, 7)
(8, 8)
(9, 9)
(10, 10)
(11, 11)
(12, 12)
(13, 13)
(14, 14)
(15, 15)
(16, 16)
(17, 17)
(18, 18)
(19, 19)

Update Here is some Python Code, to do the computations for the Klein Four group:

K4_elements = {'0':0,"a":1,"b":2,"c":3}
K4_group_table = [
    ["0","a","b","c"],
    ["a","0","c","b"],
    ["b","c","0","a"],
    ["c","b","a","0"]
]
K4_lengths = {"0":0,"a":1,"b":1,"c":2}

def K4_add(g,h):
    i = K4_elements[g]    
    j = K4_elements[h]
    return(K4_group_table[i][j])

def K4_phi(g,h):
    return(K4_lengths[g]+K4_lengths[h]-K4_lengths[K4_add(g,h)])

def add_ZxK4(a,b):
    a0,a1=a
    b0,b1=b
    return((a0+b0+K4_phi(a1,b1),K4_add(a1,b1)))

def sumadd_ZxK4(l):
    x = (0,"0")
    for y in l:
        x = add_ZxK4(x,y)
    return(x)

def norm_ZxK4(a):
    return(abs(a[0])+K4_lengths[a[1]])

def mult_ZxK4(x,a):
    return(sumadd_ZxK4([a for i in range(x)]))

def zeta_ZxK4(w):
    m = min([K4_phi(g,h) for g in K4_elements.keys() for h in K4_elements.keys() if K4_phi(g,h)!=0])
    return sumadd_ZxK4([mult_ZxK4(m**(len(w)-1-i),(0,w[i])) for i in range(len(w))])

def operate_ZxK4(h,a):
    return(add_ZxK4((0,h),a))


from itertools import product
K4 = ['0',"a","b","c"]
words = []
words.extend(list(product(K4,K4,K4)))

for word in words:
    print(".".join(word), zeta_ZxK4(word),norm_ZxK4(zeta_ZxK4(word)))

0.0.0 (0, '0') 0
0.0.a (0, 'a') 1
0.0.b (0, 'b') 1
0.0.c (0, 'c') 2
0.a.0 (2, '0') 2
0.a.a (2, 'a') 3
0.a.b (2, 'b') 3
0.a.c (2, 'c') 4
0.b.0 (2, '0') 2
0.b.a (2, 'a') 3
0.b.b (2, 'b') 3
0.b.c (2, 'c') 4
0.c.0 (4, '0') 4
0.c.a (4, 'a') 5
0.c.b (4, 'b') 5
0.c.c (4, 'c') 6
a.0.0 (4, '0') 4
a.0.a (4, 'a') 5
a.0.b (4, 'b') 5
a.0.c (4, 'c') 6
a.a.0 (6, '0') 6
a.a.a (6, 'a') 7
a.a.b (6, 'b') 7
a.a.c (6, 'c') 8
a.b.0 (6, '0') 6
a.b.a (6, 'a') 7
a.b.b (6, 'b') 7
a.b.c (6, 'c') 8
a.c.0 (8, '0') 8
a.c.a (8, 'a') 9
a.c.b (8, 'b') 9
a.c.c (8, 'c') 10
b.0.0 (4, '0') 4
b.0.a (4, 'a') 5
b.0.b (4, 'b') 5
b.0.c (4, 'c') 6
b.a.0 (6, '0') 6
b.a.a (6, 'a') 7
b.a.b (6, 'b') 7
b.a.c (6, 'c') 8
b.b.0 (6, '0') 6
b.b.a (6, 'a') 7
b.b.b (6, 'b') 7
b.b.c (6, 'c') 8
b.c.0 (8, '0') 8
b.c.a (8, 'a') 9
b.c.b (8, 'b') 9
b.c.c (8, 'c') 10
c.0.0 (8, '0') 8
c.0.a (8, 'a') 9
c.0.b (8, 'b') 9
c.0.c (8, 'c') 10
c.a.0 (10, '0') 10
c.a.a (10, 'a') 11
c.a.b (10, 'b') 11
c.a.c (10, 'c') 12
c.b.0 (10, '0') 10
c.b.a (10, 'a') 11
c.b.b (10, 'b') 11
c.b.c (10, 'c') 12
c.c.0 (12, '0') 12
c.c.a (12, 'a') 13
c.c.b (12, 'b') 13
c.c.c (12, 'c') 14

Plotting this sequence one recognizes a fractal structure:

Answer 3

Doc, the proper place for the Klein-4 group in elementary arithmetic is multiplication, not addition. Namely, it is the group if invertible modulo 8 integers. Thus, they will represent in binary as words $(a,b,1)$ and you can work out the multiplication table, but it ain't gonna be a big surprise...