# Finding a set of congruences from a set of solutions

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.

-
Also posted to MathOverflow. In the example you give, you don't have a subgroup; you have a coset of a subgroup. –  Gerry Myerson Aug 31 '11 at 2:31
Sorry, I've edited the question. –  Thomas Aug 31 '11 at 2:36
If x1 = S1= 000, x2 = S2 = 111 in your example, then what is x3 ? –  ndroock1 Aug 31 '11 at 5:35
You might tag this problem under Group Theory, this problem does not belong in elementary-number-theory or algorithms. Willy Wong may do this anyway. –  ndroock1 Aug 31 '11 at 5:38
@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. –  Gerry Myerson Aug 31 '11 at 7:15

## 2 Answers

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.

-
You seem to use the fact that $\langle S_1, \ldots, S_m \rangle^{\perp \perp} = \langle S_1, \ldots, S_m \rangle$. Is it actually the case? –  Thomas Sep 13 '11 at 1:11
@Thomas: I don't seem how I'm using that, unless by "satisfying exactly" you mean that only the $S_j$ should satisfy the congruences. (In this latter case also the requirement that they form a subgroup/subspace would be necessary after all.) However, for finite dimension indeed $V^{\perp\perp}=V$; see e.g. here. –  joriki Sep 13 '11 at 3:09
I meant only the $S_j$. The link you've gave states "For a finite dimensional inner product space", but as far as I know, this isn't an "inner product space". –  Thomas Sep 13 '11 at 17:04
@Thomas: You're right, sorry, I didn't notice that. An inner product space has a notion of positivity, but we don't need that here; all we need is orthogonality. To see that $V^{\perp\perp}=V$, note that forming the orthogonal complement of a $k$-dimensional subspace of an $n$-dimensional space imposes $k$ linearly independent linear constraints and thus yields a subspace of dimension $n-k$; forming the orthogonal complement again imposes $n-k$ linearly independent linear constraints and thus yields a subspace of dimension $k$... –  joriki Sep 13 '11 at 17:37
... 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. –  joriki Sep 13 '11 at 17:37

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$.

-