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

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.

share|improve this question
    
Such a set would be a 2-error correcting binary code. You might search for constructions and see if some provide good lower bounds. –  Aaron Meyerowitz Oct 14 '12 at 22:00
    
Thanks for the comment. Haven't found anything yet that I've gotten to work, but I'll post here if I do. –  rishig Oct 19 '12 at 6:23
1  
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. –  Jyrki Lahtonen Jun 10 '13 at 8:57
add comment

2 Answers

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$.

share|improve this answer
add comment

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

share|improve this answer
    
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 –  rishig Oct 19 '12 at 4:44
    
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 –  David Bernier Oct 20 '12 at 17:47
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.