2
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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). $\endgroup$ Feb 28, 2011 at 22:54
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Peter Shor
    Feb 28, 2011 at 23:09

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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