Steiner quadruple systems of small rank embedded into extended perfect binary codes

D. I. Kovalevskaya ; F. I. Solov'eva

Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 5, pp. 47-62.

Résumé

It is known that the set of all vectors of weight 4 in an arbitrary extended perfect binary code of length $N$ containing the all-zero vector defines a Steiner quadruple system of order $N$. In this paper, we give a modification of the known Lindner construction for the Steiner quadruple system of order $N=2^r$ that can be represented by some special switchings from the Hamming system of Steiner quadruples. It is proved that any of such Steiner quadruple systems is embedded into some extended perfect binary code constructed by switchings of $ijkl$-components from the binary extended Hamming code. We present the lower bound for the number of different Steiner quadruple systems of order $N$ of rank less than or equal to $N-\log N+1$ such that the systems are embedded into extended perfect binary codes of length $N$. Tab. 4, bibliogr. 19.

Détail

Keywords: Steiner quadruple system, extended perfect binary code, switching, $ijkl$-component, $il$-component.

Bibliographie

[1] Avgustinovich S. V., Soloveva F. I., “Postroenie sovershennykh dvoichnykh kodov posledovatelnymi sdvigami $\tilde\alpha$-komponent”, Problemy peredachi informatsii, 33:3 (1997), 15–21 | MR | Zbl

[2] Aliev I. Sh. o., “Kombinatornye skhemy i algebry”, Sib. mat. zhurn., 13:3 (1972), 499–509 | MR | Zbl

[3] Vasilev Yu. L., “O negruppovykh plotno upakovannykh kodakh”, Problemy kibernetiki, 8, 1962, 337–339 | MR

[4] Glukhikh E. S., Vlozhimost sistem troek Shteinera v sovershennye kody, Magisterskaya dissertatsiya, Novosibirsk. gos. un-t, Novosibirsk, 2005, 18 pp.

[5] Zinovev V. A., Zinovev D. V., “O razreshimosti sistem Shteinera $S(v=2^m,4,3)$ ranga $r\leq v-m+1$ nad $\mathbb F^2$”, Problemy peredachi informatsii, 43:1 (2007), 39–55 | MR

[6] Zinovev V. A., Zinovev D. V., “Sistemy Shteinera $S(v,k,k-1)$: komponenty i rang”, Problemy peredachi informatsii, 47:2 (2011), 52–71 | MR

[7] Mak-Vilyams F. Dzh., Sloen N. Dzh., Teoriya kodov, ispravlyayuschikh oshibki, Svyaz, M., 1979, 744 pp.

[8] Petrenyuk A. Ya., “Priznaki neizomorfnosti sistem troek Shteinera”, Ukr. mat. zhurn., 24:6 (1972), 772–780

[9] Soloveva F. I., Vvedenie v teoriyu kodirovaniya, Ucheb. posobie, Novosibirsk. gos. un-t, Novosibirsk, 2006, 124 pp.

[10] Kholl M., Kombinatorika, Mir, M., 1970, 424 pp. | MR

[11] Doyen J., Hubaut X., Vandensavel M., “Ranks of incidence matrices of Steiner triple systems”, Math. Z., 163:3 (1978), 251–259 | DOI | MR | Zbl

[12] Doyen J., Vandensavel M., “Nonisomorphic Steiner quadruple systems”, Bull. Soc. Math. Belg., 23 (1971), 393–410 | MR | Zbl

[13] Hanani H., “The existence and construction of balanced incomplete block designs”, Ann. Math. Stat., 32:2 (1961), 361–386 | DOI | MR | Zbl

[14] Lenz H., “On the number of Steiner quadruple systems”, Mitt. Math. Seminar Giessen, 169 (1985), 55–71 | MR | Zbl

[15] Lindner C. C., “On the construction of nonisomorphic Steiner quadruple systems”, Colloq. Math., 29 (1974), 303–306 | MR | Zbl

[16] Östergård P. R., Pottonen O., “The perfect binary one-error-correcting codes of length 15. Part 1. Classification”, IEEE Trans. Inform. Theory, 55 (2009), 4657–4660 | DOI | MR

[17] Teirlinck L., “On projective and affine hyperplanes”, J. Comb. Theory Ser. A, 28:3 (1980), 290–306 | DOI | MR | Zbl

[18] Tonchev V. D., “A formula for the number of Steiner quadruple systems on $2^n$ points of $2$-rank $2^n-n$”, J. Comb. Des., 11:4 (2003), 260–274 | DOI | MR | Zbl

[19] Tonchev V. D., “A mass formula for Steiner triple systems $\mathrm{STS}(2^n-1)$ of $2$-rank $2^n-n$”, J. Comb. Theory Ser. A, 95:2 (2001), 197–208 | DOI | MR | Zbl