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?

Improve this question
$\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$
    – Gerry Myerson
    Commented 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
    Commented Feb 28, 2011 at 23:09

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .