# Finding a set of congruences from a set of solutions

Let $S_1, \ldots, S_m \in \mathbb{Z}_2^n$ be $n$-tuples 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 on math.stackexchange, sorry for the inconvenience.

-
In general, you can't. Consider 00, 01, 11. If your $n$-tuples form a translate of a vector subspace of ${\bf Z}_2^n$, then it should be possible to use the methods of linear algebra. –  Gerry Myerson Aug 31 '11 at 2:10
What if the elements form a group? I've edited the question. –  Carl Aug 31 '11 at 2:26
You've also posted it to math.stackexchange, without indicating on either site that you've posted it to the other one. This is a major breach of etiquette. Voting to close. –  Gerry Myerson Aug 31 '11 at 2:29
I wasn't aware of this politic, can I edit my post? –  Carl Aug 31 '11 at 2:31
You can do whatever you like. I think the question sits better at m.se than here, so you could 1) do nothing, and expect the problem to get closed here, or 2) delete the question from this site. Of course, you can edit your post here to include a link to the post at m.se, if you want to. –  Gerry Myerson Aug 31 '11 at 3:52