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?

  • 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