# How can I identify all congruence classes of a vector under shifting?

I'm trying to think of the right way to tackle this situation and will welcome any suggestion.

I'm working with bit vectors, that is, vectors where each element is either 0 or 1. At the moment, I'm interested in 4 dimensions, thus vectors of the form:

$(b{_0},b{_1},b{_2},b{_3})$

with each $b{_i}$ in (0,1)

In my problem, two vectors are equivalent if one can be shifted to become the other. So for instance:

$(1,1,1,0)$ $\cong$ $(0,1,1,1)$

but

$(1,1,0,0)$ !$\cong$ $(1,0,1,0)$

My question is: what is a good way to give this an algebraic structure so I can reason about the different congruence classes within this space? For instance, given a vector, how many other vectors are congruent to it, and other questions like that?

• If you know about group actions, you can let $\mathbb Z_4$ act on your set of vectors, where the element $k \in \mathbb{Z}_4$ maps $(b_0,b_1,b_2,b_3)$ to $(b_k, b_{k+1}, b_{k+2}, b_{k+3})$ (where the indexing is taken mod 4). Then your equivalence classes are precisely the orbits of the action, and there are nice things like the orbit-stabilizer theorem which will give you insight. – Bungo Nov 11 '15 at 2:19

## 1 Answer

To expand my comment a bit, this sort of problem is well suited to analysis by means of group actions. In case this notion is unfamiliar, I'll give a brief tutorial and apply it to this problem.

Consider the group $G = \mathbb Z_4$, the set of integers modulo 4, under addition. So the elements of $G$ are simply $0,1,2,3$ with the addition rule that $i+j$ is computed modulo $4$, e.g. $2 + 3 = 1$.

Let $\Omega$ be your set of vectors of the form $(b_1,b_2,b_3,b_4)$ where each $b_i$ is $0$ or $1$. Then $\mathbb Z_4$ acts on $\Omega$ via the rule $k \cdot (b_1,b_2,b_3,b_4) = (b_{k+1},b_{k+2},b_{k+3},b_{k+4})$, where the indexing is computed mod $4$. So for example, $2 \cdot (b_1,b_2,b_3,b_4) = (b_3,b_4,b_1,b_2)$. It's easy to check that this rule satisfies the conditions of a group action.

This action, like any group action, partitions $\Omega$ into a disjoint set of equivalence classes, called orbits. The orbit of the vector $v = (b_1,b_2,b_3,b_4)$ is simply the set of all vectors that can be achieved by applying the group action to $v$, in this case shifting $v$ cyclically.

An element $k\in G$ stabilizes a vector $v$ if $k \cdot v = v$, meaning in this case that $v$ shifted by $k$ is just $v$ itself. For example, if $v = (1,0,1,0)$, then both $k=0$ and $k=2$ stabilize $v$, whereas $k=1$ and $k=3$ do not.

Some elementary facts about orbits and stabilizers: the stabilizer of an element $v$, usually denoted $G_v$, is a subgroup of $G$, and therefore its order $|G_v|$ (the number of elements in $G_v$) must be a divisor of $|G|$, the order of the group. Since in your case, $G = \mathbb Z_4$ has $4$ elements, every stabilizer must have order $1$, $2$, or $4$.

The size of any orbit is equal to $|G|/|G_v|$ for any $v$ in the orbit. This means in your case that each orbit will have size $1$, $2$, or $4$.

Your set of vectors $\Omega$ contains $2^4 = 16$ elements total, and each vector in $\Omega$ lies in exactly one orbit, so $|\Omega| = 16$ must equal the sums of the sizes of the orbits.

It's easy to check that there are exactly two orbits which contain one vector each, namely $(0,0,0,0)$ and $(1,1,1,1)$.

What about orbits of size $2$? The only vectors which can be in such an orbit are those which satisfy $(a,b,c,d) = (c,d,a,b)$, or equivalently, $a=c$ and $b=d$. We can choose $a$ and $b$ freely, then $b$ and $d$ are automatically assigned. This means there are $4$ vectors satisfying this condition. They are $(0,0,0,0)$, $(0,1,0,1)$, $(1,0,1,0)$, and $(1,1,1,1)$. Since $(0,0,0,0)$ and $(1,1,1,1)$ lie in their own size-one orbits, the only orbit of size $2$ is the one consisting of $(0,1,0,1)$ and $(1,0,1,0)$.

So far, we have two orbits of size $1$ and one orbit of size $2$, which accounts for $4$ elements of $\Omega$. All other elements of $\Omega$ must be grouped in orbits of size $4$ (the only other possibility). Since there are $12$ remaining elements to divide among these orbits, this means that there are exactly three orbits of size $4$.

To summarize, your group action induces:

• Two orbits of size $1$
• One orbit of size $2$
• Three orbits of size $4$

Of course, it's a bit overkill to apply the theory of group actions to this example; you could just as easily analyze it by brute force. But group actions allow this sort of reasoning to generalize to a wide range of situations which can be difficult to analyze in other ways.

• Wow, this is perfect. It's going to take me a while to digest, but it sounds like exactly what I was looking for. Thanks for the detailed explanation! – Joshua Frank Nov 11 '15 at 14:04