On the rigidity of binary codes
by
Sergey Avgustinovich
Sobolev Institute of Mathematics
Coauthors: Faina Solov'eva (Sobolev Institute of Mathematics)

A binary code C of length n is a subset of the vector space Eⁿ of dimension n over GF(2). The Hamming distance d(x, y) between vectors x, y +AFw-in Eⁿ is the number of coordinates in which x and y differ. The Hamming weight of x +AFw-in Eⁿ is given by wt(x)=d(x, +AFw-bf 0), where +AFw-bf 0 is the all-zero vector. A code distance is given by d = min +AFw-, d(x, y) for all different codewords x, y +AFw-in C.

A mapping +AFw-phi : C+AFw-rightarrow Eⁿ is called an isometry from the code C to the code +AFw-phi (C) if d(x, y) = d(+AFw-phi(x), +AFw-phi(y)) for all codewords x, y +AFw-in C. A code C in Eⁿ is called metrically rigid if every isometry +AFw-phi : C+AFw-rightarrow Eⁿ with respect to the Hamming metric is extendable to an isometry of the whole space Eⁿ, see [1].

Let N=+AFw-1, 2, +AFw-ldots, n+AFw-. A subset D+AFw-subset Eⁿ of weight k vectors is called an 2-(n, k, +AFw-lambda)-design if the number of vectors in D with ones in i'th and j'th coordinates is equal exactly +AFw-lambda for all different i, j +AFw-in N. We define an (n, k, +AFw-lambda)-gomogenious code as the code containing an 2-(n, k, +AFw-lambda)-design. Let for a subset S_i in a code C and some k+AFw-le n be true:

1. wt(v)=k for every v+AFw-in S_i;

2. d(v, u)=2k-2 for all different v, u+AFw-in S_i;

3. |S_i| > k²-k+-1.+AFwAXA- We call S_i the fluffy i-star of the code C.

Theorem 1. For every n+AFw-ge k⁴ an (n, k, +AFw-lambda)-gomogenious code contains a fluffy i-star for all i+AFw-in N.

Theorem 2. If for all i+AFw-in N a code C contains a fluffy i-star and +AFw-bf 0+AFw-in C then C is metrically rigid.

As a consequence from Theorems 1 and 2 one can get that for n large enough all (n, k, +AFw-lambda)-gomogenious codes are metrically rigid. Moreover it is known [2] that for all natural k, +AFw-lambda and large enough n such that +AFw-lambda (n-1)/(k-1) and +AFw-lambda n(n-1)/k(k-1) are integers there exists an 2-(n, k, +AFw-lambda)-design.

References

[1] Solov'eva F.I., Avgustinovich S.V., Honold T., Heise W., On the extendability of code isometries, J. of Geometry, 61 (1998) 3-16.

[2] Wilson R.M., An existence theory for pairwise balanced designs: III - Proof of the existence conjectures, J. Comb. Theory, 18A (1975) 71-79.

The work of Avgustinovich was partially supported by the RFBR 97-01-01075 and by INTAS 97-1001 grants. The work of Solov'eva was partially supported by the RFBR 97-01-01104 gran

Date received: February 21, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cadw-33.