## Automorphisms of subgroup of hamming cube under distance constraint

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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.

-

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 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 at 6:23

## 1 Answer

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

-

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 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 at 17:47
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 12, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9078010320663452, "perplexity_flag": "middle"}