1
$\begingroup$

I know $(\{0, 1\}, \oplus)$ (where $\oplus$ is the XOR operator) is a well-known abelian group.

But what if i "extend" the underlying set?

For example, i can get $(\{0, 1, 2, 3\}, \oplus)$, or in general $(\{0, 1, ... , 2^n-1\}, \oplus)$ and they are groups as well.

Have these groups been studied? Have they any application in CS?

  • 6
    If I understand you correctly, your groups should be isomorphic to an $n$-fold product of $C_2$, where $C_2$ is the cyclic group with 2 elements (the one you mentioned in the first sentence of your answer). I don't know how much there is to study about those groups, as they don't look too mysterious to me. I don't know about applications in CS either...2011-01-30
  • 0
    Also, they are just the vector spaces over $\mathbb{Z}/2\mathbb{Z}$.2011-01-30
  • 0
    Since $a\oplus a = 0$ for all a, the group consists of involutions only. The only such groups are indeed the ones sebastian suggests, the elementary abelian groups of order $2^n$. (This follows from the fact that $x\mapsto x^{-1}$ is an automorphism and the structure of (finite) abelian groups.)2011-01-30
  • 0
    The magic words are "elementary abelian $2$-groups". They show up all over the place.2011-01-30

1 Answers 1

3

As Sebastian mentioned, the groups are not mysterious at all. In fact, they are quite "boring" since they're Abelian.

Here are some example applications, most of them practical, and some theoretical.

CPUs

Your CPU supports an operation called XOR (Exclusive OR) which views the registers as members of the group $\mathbb{Z}_2^n$ (where $n=32$ or $n=64$ for modern CPUs), and applies the operation of the group. The CPU also supports addition in the group $\mathbb{Z}_{2^n}$, i.e. addition modulo $2^n$, as well as multiplication modulo $2^n$.

Coding Theory

Lots of codes are defined using these groups. CRCs are linear, so they can be viewed as a linear mapping from $\mathbb{Z}_2^n$ to $\mathbb{Z}_2^m$ (where $m=16$ or $m=32$). All error-correcting codes used in practice are also linear.

Walsh-Hadamard Transform

According to Wikipedia, the Walsh-Hadamard transform, which is just the Fourier transform on your groups, has some applications to encryption and encoding (usually real Fourier transforms are used).

This transform is very important in complexity theory (see also the next section), where it is used to construct and analyze PCPs, and to prove important results such as the parallel repetition theorem.

Complexity Theory

These groups are used to prove lower bounds on constant-depth circuits using the polynomials method in its finite field variety (the so-called Razborov-Smolensky method). The idea is to associate with each gate in the circuit a low-degree polynomial approximating the function computed by the gate (with a small error), and then proving that the target function doesn't have such nice approximations.

  • 2
    They also show up in combinatorial game theory, where the operation is better-known as 'nim-addition' because it's the key to correctly playing the (impartial) game of Nim! Check out Winning Ways For Your Mathematical Plays or some of John Conway's work for more details.2011-01-30