16
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ At least for your (2), note that, even in the cyclic case, you're choosing a cocycle. There happens to be an obvious one in the cyclic case, but, even in the Abelian but non-cyclic case, there'll be at least several equally natural choices. $\endgroup$ – LSpice Jan 23 at 21:11
  • 1
    $\begingroup$ Related question: mathoverflow.net/q/218604/7709 $\endgroup$ – Mark Wildon Jan 25 at 13:20
  • $\begingroup$ @MarkWildon thanks. that looks interesting $\endgroup$ – user6671 Jan 25 at 13:22
22
$\begingroup$

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)

| cite | improve this answer | |
$\endgroup$
  • 6
    $\begingroup$ ... $\Bbb Z$ sit inside this as the subgroup of "finite words" ... This is perhaps slightly wrong, as negative integers are words whose digits are eventually $1$. $\endgroup$ – WhatsUp Jan 23 at 21:43
  • 3
    $\begingroup$ @WhatsUp good catch, edited! $\endgroup$ – Kevin Casto Jan 23 at 21:50
  • $\begingroup$ thanks for your answer $\endgroup$ – user6671 Jan 24 at 1:03
3
$\begingroup$

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:

enter image description here

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Your group structure on $\mathbb Z\times G$ is isomorphic to the usual one via $f:(n,a)\mapsto (n + |a|,a)$: You defined it as the central extension corresponding to the cocycle $\phi$ which by definition is the coboundary of $a\mapsto |a|$. $\endgroup$ – Bertram Arnold Jan 27 at 20:33
  • $\begingroup$ @BertramArnold thanks for yout comment. $\endgroup$ – user6671 Jan 28 at 0:49
  • $\begingroup$ @BertramArnold yes, they are isomorphic as groups, but the norm is not additive at the natural numbers. $\endgroup$ – user6671 Jan 28 at 15:08
  • $\begingroup$ @SebastienPalcoux I am not sure which functor you mean $\endgroup$ – user6671 Jan 29 at 4:12
  • $\begingroup$ @SebastienPalcoux the question is open in the sense that for cyclic groups we should get the usual addition, so if you have an idea how to extend this to other finite groups, that would be great. $\endgroup$ – user6671 Jan 29 at 4:54
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ It is not related to elementary addition: it is related to elementary multiplication. Modulo 8, there are 4 invertible remainders: 1,3,5,7. Their multiplication group is $K_4$. $\endgroup$ – Bugs Bunny Jan 24 at 11:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy