Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let's consider the abelian group $\mathbb{Z}^N_2$ equipped with the Hamming metric (the hypercube).

Suppose I have a subgroup of this hypercube (not necessarily a subcube) which is generated by a set of elements all of which are at least distance $d$ from the identity, i.e. it has a set of generators all of which are large.

How many elements of this subgroup can be within $R$ of the identity?

share|improve this question
1  
Question seems a little vague to me. With $N$ generators of the form $(1,1,\dots,1,0,1,\dots,1,1)$ you get the whole group (if $N$ is even). –  Gerry Myerson Feb 28 '11 at 22:54
1  
Do you want a lower bound on $R$ or an upper bound on $R$. If you want to find subgroups with $R$ small, this is basically the theory of binary linear error-correcting codes, which has been extensively studied (for this case, the constraint that the group is generated by a set of large Hamming weight elements is completely superfluous). If you want to find subgroups with $R$ big, you should look at the MacWilliams identities (also from the theory of error correcting codes) and see what those tell you about $R$. –  Peter Shor Feb 28 '11 at 23:09
add comment

1 Answer 1

You can get half of the elements small. Let $e_k$ be the element $(0,0,\ldots,0,1,0, \ldots 0)$ with a single $1$ in the $k$th position. Let $v$ be the element $(1,1,1,1,1,\ldots,1)$. Now, consider the $t+1$ generators $v$ and $v+e_k$, $k = 1 \ldots t$. The subgroup generated contains the subgroup with $1$'s in any subset of the first $t$ positions, all of whose elements have Hamming weight at most $t$. The subgroup has order $2^{t+1}$, and there are $2^t$ small elements.

Unless $R$ is fairly big, you can't do better, because if you add an element with large Hamming weight to one with small Hamming weight, the result has large Hamming weight.

share|improve this answer
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.