Question

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.

Answer 1

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