On the existence of extended perfect binary codes with trivial symmetry group (Q2268258): Difference between revisions

Two binary codes are said to be equivalent if there is a permutation of the coordinates and permutations of the coordinate values that map the words of one of the codes onto those of the other. The permutations of the coordinate values can also be viewed via the addition of a binary word. A transformation of the described form that maps a code onto itself is called an automorphism of the code; all automorphisms form the automorphism group of the code. The question regarding existence of objects with trivial automorphism group is central in combinatorics. A perfect binary one-error-correcting code is always self-complementary (meaning that the complement of a codeword is always a codeword) and cannot therefore have a trivial automorphism group. Other similar questions may then be asked instead. For example, if one restricts the transformation to only permutations of the coordinates, one gets the definition of the symmetry group of a code, and one may ask about existence of perfect binary one-error-correcting codes with trivial symmetry group. The authors extend work by the first author [J. Comb. Math. Comb. Comput. 52, 109--115 (2005; Zbl 1073.94022)] and prove that for all \(n = 2^m-1\), \(m \geq 4\), and all \(r\) satisfying \(n-\log(n+1)+3 \leq r \leq n-1\), there are perfect binary one-error-correcting codes with length \(n\), rank \(r\), and trivial symmetry group. An analogous result holds for extended perfect codes. The all-zero vector is assumed to belong to the code when computing the rank, that is, the dimension of the space spanned by the codewords.