Constructing covering codes with given automorphisms

Let K(n, r) denote the minimum cardinality of a binary covering code of len gth n and covering radius r. Constructions of covering codes give upper bou nds on K(n, r). It is here shown how computer searches for covering codes c an be sped up by requiring that the code has a given (not necessarily full) automorphism group. Tabu search is used to find orbits of words that lead to a covering. In particular, a code D is found which proves K(13, 1) less than or equal to 704 a new record. A direct construction of D is given, and its full automorphism group is shown to be the general linear group GL(3, 3). It is proved that D is a perfect dominating set (each word not in D is covered by exactly one word in D) and is a counterexample to the recent Uni formity Conjecture of Weichsel.