7
$\begingroup$

Let $S$ be a subset of $\{0,1\}^n$ such that any two elements of $S$ are at least (Hamming) distance 5 apart. I'm looking for an upper bound on the size of the automorphism group of $S$.

There's a trivial upper bound of $2^nn!$ (the number of automorphisms of $\{0,1\}^n$), and an easy lower bound of $2^{n/5}(n/5)!$ (take S to be all elements of the form $xxxxx$, where $x$ is a bitstring of length $n/5$).

Any bound of the form $n!/n^{cn}$ for any $c>0$ would be helpful.

$\endgroup$
3
  • $\begingroup$ Such a set would be a 2-error correcting binary code. You might search for constructions and see if some provide good lower bounds. $\endgroup$ Oct 14, 2012 at 22:00
  • $\begingroup$ Thanks for the comment. Haven't found anything yet that I've gotten to work, but I'll post here if I do. $\endgroup$
    – rishig
    Oct 19, 2012 at 6:23
  • 1
    $\begingroup$ You seem to allow translations as well as permutations of coordinates, don't you? Do you treat the automorphism group as a subgroup of the isometries of the entire Hamming space? Or do you treat it as a subgroup of $Sym(S)$? The former is IMHO standard in coding theory (usually translations aren't allowed though). I am asking because the choice $S=\{111110^{n-5},0^n\}$ leads to a very large group with the "standard" interpretation: any permutation of the last $n-5$ coordinates $\times$ any permutation of the first five coordinates $\times$ two translations = $240(n-5)!$ automorphisms. $\endgroup$ Jun 10, 2013 at 8:57

2 Answers 2

1
$\begingroup$

There's a better easy lower bound of $2^{n/3-1}(n/3)!$ and minimum distance six: start with the parity code of all $n/3$-bit words with an even number of ones, and replace the bits of each code word with $000$ or $111$.

$\endgroup$
0
$\begingroup$

For the additive group {0, 1}^n , it seems to me that every non-singular binary nxn matrix provides one F_2 linear bijective map from {0, 1}^n to itself . As I recall, asymptotically the number of these bijective linear maps is at least C 2^(n^2), for some C>0 . In other words, a strictly positive proportion of random nxn matrices over F_2 has non-zero determinant, and an nxn matrix over F_2 has nxn entries, each being 0 or 1. When you say automorphism, are you referring to automorphisms of the additive group (F_2)^n ? Thanks. David Bernier

$\endgroup$
2
  • $\begingroup$ Thanks for your response. I'm referring to automorphisms of the hypercube [1], which are substantially more restricted than $F_2^n$. For instance the linear map [[1 1] [1 0]] is an automorphism of $F_2^2$ but not of the square. [1] en.wikipedia.org/wiki/Hyperoctahedral_group $\endgroup$
    – rishig
    Oct 19, 2012 at 4:44
  • $\begingroup$ I might be mistaken. But perhaps the autmorphism group is the same as the hroups that preserve the Hamming distance on the metric space {0,1}^n with the Hamming distance metric? Noam Elkies wrote a survey article on linear error-correcting codes that was published in the Notices of the AMS: Elkies, Noam; "Lattices, Linear Codes, and Invariants, Part II", Notices of the AMS, Volume 47 number 11, December 2000. ams.org/notices/200011/index.html $\endgroup$ Oct 20, 2012 at 17:47

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.