0
$\begingroup$

Let $S_1, \ldots, S_m \in \mathbb{Z}_2^n$ be elements forming a subgroup of $\mathbb{Z}_2^n$. How can I find a set of congruences (mod 2) over $x_1, \ldots, x_n$ satisfying exactly $x_1 = S_j[1], \ldots, x_n = S_j[n]$ for all $j \in [m]$.

For exemple, given $S_1 = 000$ and $S_2 = 111$, this is an associated set of congruences: $x_1 \equiv x_2 \, (\text{mod 2}) \text{ and } x_3 \equiv x_2 \, (\text{mod 2}).$

I've also post the question of MathOverflow.

  • 0
    @ndroock1, I think you've misunderstood the notation. $x_1$ is the first component of $S_j$. In the example, $x_1(S_1)=S_1[1]=0$, $x_1(S_2)=S_2[1]=1$. Also, elementary number theory seems OK to me for a question on congruences. Group Theory may be better, but I actually see it as Linear Algebra.2011-08-31

2 Answers 2

1

If I understand the question correctly, you're looking for the orthogonal complement of the subspace spanned by the vectors $S_1,\dotsc,S_m$ (considered as vectors in $\mathbb Z_2^n$ over $\mathbb Z_2$). Each congruence

$\sum_{i=1}^nc_ix_i\equiv0\pmod2$

is a constraint that all vectors $S_1,\dotsc,S_m$ are orthogonal to the vector $c$ with components $c_i$. So find a basis for the $S_1,\dotsc,S_m$, then find a basis for the orthogonal complement, and the set of all congruences satisfied by the $x_i$ corresponds to the subspace spanned by that basis. The $S_1,\dotsc,S_m$ forming a group (i.e. a subspace) isn't required for this; you just need to find a basis for the subspace they span.

  • 0
    ... Since $V\subseteq V^{\perp\perp}$ and $V$ can't be properly contained in a subspace of the same dimension, we must have $V= V^{\perp\perp}$. I think my answer remains valid, except, as I said, since you meant *only* the $S_j$, of course they do have to form a subgroup/subspace.2011-09-13
0

Here's a method which is most likely very impractical when $n$ is large. First, write a matrix $A$ whose rows are your subgroup elements. In the example, $A=\pmatrix{0&0&0\cr1&1&1\cr}$ Then write a matrix whose columns are all possible $n$-tuples of zeros and ones. For $n=3$, this is $B=\pmatrix{0&0&0&0&1&1&1&1\cr0&0&1&1&0&0&1&1\cr0&1&0&1&0&1&0&1\cr}$ The order of the columns of $B$ is immaterial. Each column of $B$ corresponds to a congruence, e.g., the column $(0,1,1)$ corresponds to $x_2+x_3\equiv0\pmod2$. Now form the product: $AB=\pmatrix{0&0&0&0&0&0&0&0\cr0&1&1&0&1&0&0&1\cr}$ Look at the all-zero columns of the product (namely, columns 1, 4, 6, and 7). The corresponding columns in $B$ give the congruences you want. The first column is the trivial congruence $0\equiv0\pmod2$, but the other columns give you $x_2+x_3\equiv0\pmod2$, $x_1+x_3\equiv0\pmod2$, and $x_2+x_3\equiv0\pmod2$.