MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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 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, if you want to. – Gerry Myerson Aug 31 '11 at 3:52

Your Answer


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

Browse other questions tagged or ask your own question.