Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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... –  Sebastian Jan 30 '11 at 13:28
    
Also, they are just the vector spaces over $\mathbb{Z}/2\mathbb{Z}$. –  George Lowther Jan 30 '11 at 13:43
    
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.) –  Myself Jan 30 '11 at 14:22
    
The magic words are "elementary abelian $2$-groups". They show up all over the place. –  Arturo Magidin Jan 30 '11 at 19:19
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
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. –  Steven Stadnicki Jan 30 '11 at 20:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.