Perfect codes from the dual point of view I

The two concepts dual code and parity check matrix for a linear perfect 1-error correcting binary code are generalized to the case of non-linear perfect codes. We show how this generalization can be used to enumerate some particular classes of perfect 1-error correcting binary codes. We also use it to give an answer to a problem of Avgustinovich: whether or not the kernel of every perfect 1-error correcting binary code is always contained in some Hamming code.     

The non-existence of some perfect codes over non-prime power alphabets

Let denote the number of times the prime number p appears in the prime factorization of the integer q. The following result is proved: If there is a perfect 1-error correcting code of length n over an alphabet with q symbols then, for every prime number .This condition is stronger than both the packing condition and the necessary condition given by the Lloyd theorem, as it for example excludes the existence of a perfect code with the parameters (n,q,e)=(19,6,1).     

Maximal partial packings of $${Z_2^n}$$ with perfect codes

A maximal partial Hamming packing of is a family of mutually disjoint translates of Hamming codes of length n, such that any translate of any Hamming code of length n intersects at least one of the translates of Hamming codes in . The number of translates of Hamming codes in is the packing number, and a partial Hamming packing is strictly partial if the family does not constitute a partition of . A simple and useful condition describing when two translates of Hamming codes are disjoint or not disjoint is proved. This condition depends on the dual codes of the corresponding Hamming codes. Partly, by using this condition, it is shown that the packing number p, for any maximal strictly partial Hamming packing of , n = 2 ^m −1, satisfies . It is also proved that for any n equal to 2 ^m −1, , there exist maximal strictly partial Hamming packings of with packing numbers n−10,n−9,n−8,...,n−1. This implies that the upper bound is tight for any n = 2 ^m −1, . All packing numbers for maximal strictly partial Hamming packings of , n = 7 and 15, are found by a computer search. In the case n = 7 the packing number is 5, and in the case n = 15 the possible packing numbers are 5,6,7,...,13 and 14.      

On transitive one-factorizations of arc-transitive graphs

It is shown that transitive 1-factorizations of arc-transitive graphs exist if and only if certain factorizations of their automorphism groups exist. This relation provides a method for constructing and characterizing transitive 1-factorizations for certain classes of arc-transitive graphs. Then a characterization is given of 2-arc-transitive graphs which have transitive 1-factorizations. In this characterization, some 2-arc transitive graphs and their transitive 1-factorizations are constructed.     

On Intersection Problem for Perfect Binary Codes

The main result is that to any even integer q in the interval 0 ≤ q ≤ 2^{n+1-2log(n+1)}, there are two perfect codes C₁ and C₂ of length n = 2^m − 1, m ≥ 4, such that |C₁ ∩ C₂| = q.     

On diameter perfect constant-weight ternary codes

From cosets of binary Hamming codes we construct diameter perfect constant-weight ternary codes with weight n-1 (where n is the code length) and distances 3 and 5. The class of distance 5 codes has parameters unknown before.     

A number theoretic formula and asymptotic optimality of cardinalities of BAD correcting codes

This paper presents a formula for the cardinality of a class of non-linear error correcting codes for Balanced Adjacent Deletions that are provided as an extension of standard deletion from the point of the view of Weyl groups. Furthermore, we show that the cardinality is approximately optimal over any single BAD correcting codes. In other words, the ratio of the cardinality of the code and that of maximum cardinality BAD correcting code converges to 1 for sufficiently large length.     

On the classification of perfect codes: side class structures

The side class structure of a perfect 1-error correcting binary code (hereafter referred to as a perfect code) C describes the linear relations between the coset representatives of the kernel of C. Two perfect codes C and C′ are linearly equivalent if there exists a non-singular matrix A such that AC = C′ where C and C′ are matrices with the code words of C and C′ as columns. Hessler proved that the perfect codes C and C′ are linearly equivalent if and only if they have isomorphic side class structures. The aim of this paper is to describe all side class structures. It is shown that the transpose of any side class structure is the dual of a subspace of the kernel of some perfect code and vice versa; any dual of a subspace of a kernel of some perfect code is the transpose of the side class structure of some perfect code. The conclusion is that for classification purposes of perfect codes it is sufficient to find the family of all kernels of perfect codes.     

Perfect codes as isomorphic spaces

Linear equivalence between perfect codes is defined. This definition gives the concept of general perfect 1-error correcting binary codes. These are defined as 1-error correcting perfect binary codes, with the difference that the set of errors is not the set of weight one words, instead any set with cardinality n and full rank is allowed. The side class structure defines the restrictions on the subspace of any general 1-error correcting perfect binary code. Every linear equivalence class will contain all codes with the same length, rank and dimension of kernel and all codes in the linear equivalence class will have isomorphic side class structures.     

Generalized Covering Groups

Let v and be two varieties of groups defined by the sets of laws V and W, respectively. In this paper we construct a -v-covering group of a finite v-perfect group G, and show that every automorphism of G may be lifted to its -v-covering group. These generalize the previous work of the first two authors (1999). We also characterize the -v-irreducible extensions in some sense.AMS Mathematics Subject Classification (2000) Primary 20E34 20E36 Secondary 20E10     

Perfect codes in direct products of cycles—a complete characterization

Let be a direct product of cycles. It is known that for any r1, and any n2, each connected component of G contains a so-called canonical r-perfect code provided that each ℓ_i is a multiple of rⁿ+(r+1)ⁿ. Here we prove that up to a reasonably defined equivalence, these are the only perfect codes that exist.     

On perfect <Emphasis Type=Italic>p</Emphasis>-ary codes of length <Emphasis Type=Italic>p</Emphasis> + 1

Let p be a prime number and assume p ≥ 5. We will use a result of L. Redéi to prove, that every perfect 1-error correcting code C of length p + 1 over an alphabet of cardinality p, such that C has a rank equal to p and a kernel of dimension p − 2, will be equivalent to some Hamming code H. Further, C can be obtained from H, by the permutation of the symbols, in just one coordinate position.      

On the size of the symmetry group of a perfect code

It is shown that for every nonlinear perfect code C of length n and rank r with n−log(n+1)+1≤r≤n−1, where denotes the group of symmetries of C. This bound considerably improves a bound of Malyugin.     

Explicit combinatorial interpretation of Kerov character polynomials as numbers of permutation factorizations

We find an explicit combinatorial interpretation of the coefficients of Kerov character polynomials which express the value of normalized irreducible characters of the symmetric groups S(n) in terms of free cumulants R₂,R₃,… of the corresponding Young diagram. Our interpretation is based on counting certain factorizations of a given permutation.     

On the classification of perfect codes: Extended side class structures

The two 1-error correcting perfect binary codes, C and C^′ are said to be equivalent if there exists a permutation π of the set of the n coordinate positions and a word such that . Hessler defined C and C^′ to be linearly equivalent if there exists a non-singular linear map φ such that C^′=φ(C). Two perfect codes C and C^′ of length n will be defined to be extended equivalent if there exists a non-singular linear map φ and a word such that

     

On the length of the tail of a vector space partition

A vector space partition of a finite dimensional vector space V=V(n,q) of dimension n over a finite field with q elements, is a collection of subspaces U₁,U₂,…,U_t with the property that every non zero vector of V is contained in exactly one of these subspaces. The tail of consists of the subspaces of least dimension d₁ in , and the length n₁ of the tail is the number of subspaces in the tail. Let d₂ denote the second least dimension in .Two cases are considered: the integer q^d₂−d₁ does not divide respective divides n₁. In the first case it is proved that if 2d₁>d₂ then n₁≥q^d₁+1 and if 2d₁≤d₂ then either n₁=(q^d₂−1)/(q^d₁−1) or n₁>2q^d₂−d₁. These lower bounds are shown to be tight and the elements in the subspaces in tails of minimal length will constitute a subspace of V of dimension 2d₁ respectively d₂.In case q^d₂−d₁ divides n₁ it is shown that if d₂<2d₁ then n₁≥q^d₂−q^d₁+q^d₂−d₁ and if 2d₁≤d₂ then n₁≥q^d₂. The last bound is also shown to be tight.The results considerably improve earlier found lower bounds on the length of the tail.