Error-correcting codes and Minkowski’s conjecture

Peter Horak

doi:10.2478/v10127-010-0004-y

.blurhash-client-img { display: none !important; }

Error-correcting codes and Minkowski’s conjecture

Tatra Mountains Mathematical Publications

Volume 45 (2010): Issue 1 (April 2010)

By: Peter Horak

Open Access

|Nov 2012

Abstract

The goal of this paper is twofold. The main one is to survey the latest results on the perfect and quasi-perfect Lee error correcting codes. The other goal is to show that the area of Lee error correcting codes, like many ideas in mathematics, can trace its roots to the Phytagorean theorem a2+b2 = c2. Thus to show that the area of the perfect Lee error correcting codes is an integral part of mathematics. It turns out that Minkowski’s conjecture, which is an interface of number theory, approximation theory, geometry, linear algebra, and group theory is one of the milestones on the route to Lee codes.

References

[1] ASTOLA, J.: On perfect codes in the Lee metric, Ann. Univ. Turku, Ser. A I 176 (1978), 56 p.
Search in Google Scholar
[2] AL-BDAIWI, B. F.-BOSE, B.: Quasi-perfect Lee distance codes, IEEE Tran. Inform. Theory 49 (2003), 1535-1539.10.1109/TIT.2003.811922
Search in Google Scholar
[3] AL-BDAIWI, B. F.-HORAK, P.-MILLAZO, L.: Perfect 1-error correcting Lee codes, Des. Codes Cryptogr. 52 (2009), 155-162.10.1007/s10623-009-9273-3
Search in Google Scholar
[4] GOLOMB, S.W.-WELSH, L. R.: Algebraic coding and the Lee metric, in: Error Correct. Codes, Wiley, New York, 1968, pp. 175-189.
Search in Google Scholar
[5] GRAVIER, S.-MOLLARD, M.-PAYAN, CH.: On the non-existence of 3-dimensionaltiling in the Lee metric, European J. Combin. 19 (1998), 567-572.10.1006/eujc.1998.0211
Search in Google Scholar
[6] GRAVIER, S.-MOLLARD, M.-PAYAN, CH.: On the nonexistence of three--dimensional tiling in the Lee metric. II. Discrete Math. 235 (2001), 151-157.
Search in Google Scholar
[7] HAJÓS, G.: ¨Uber eifache und merfache Bedeckung des n-dimensional Raumes mit einemW¨urfelgitter, Math. Zeit. 47 (1942), 427-467.10.1007/BF01180974
Search in Google Scholar
[8] HORAK, P.-AL-BDAIWI, B. F.: Fast decoding quasi-perfect Lee distance codes, Des. Codes Cryptogr. 40 (2006), 357-367.10.1007/s10623-006-0025-3
Search in Google Scholar
[9] HORAK, P.: Tiling in Lee metric, European J. Combin. 30 (2009) 480-489.10.1016/j.ejc.2008.04.007
Search in Google Scholar
[10] HORAK, P.: On perfect Lee codes, Discrete Math. 309 (2009), 5551-5561.10.1016/j.disc.2008.03.019
Search in Google Scholar
[11] HORAK, P.-AL-BDAIWI, B. F.: The number of tilings of Rn by crosses, submitted.
Search in Google Scholar
[12] KÁRTESZI, F.: Szemléletes geometria. Gondolat, Budapest, 1966.
Search in Google Scholar
[13] MOLNÁR, E.: Sui mosaici dello spazio di dimensione n, Atti Accad. Naz. Lincei, VIII. Ser., Rend., Cl. Sci. Fis. Mat. Nat. 51 (1971), 177-185.
Search in Google Scholar
[14] KELLER, O. H.: Über die lückenlose Einfüllung des Raumes mit Würfeln, J. Reine Angew. Math. 177 (1930), 231-248.10.1515/crll.1930.163.231
Search in Google Scholar
[15] LAGARIAS, J. F.-SHOR, P. W.: Keller’s cube-tiling conjecture is false in high dimensions, Bull. Amer. Math. Soc. 27 (1992), 279-283.10.1090/S0273-0979-1992-00318-X
Search in Google Scholar
[16] MACKEY, J.: A cube tiling of dimension eight with no facesharing, Discrete Comput. Geom. 28 (2002) 275-279.
Search in Google Scholar
[17] PERRON, O.: Modulartige lückenlose Ausfüllungdes Rn mit kongruenten Würfeln I, II, Math. Ann. 117 (1940), 415-447; 117 (1941), 609-658.
Search in Google Scholar
[18] POST, K. A.: Nonexistence theorem on perfect Lee codes over large alphabets, Inform. and Control 29 (1975), 369-380.10.1016/S0019-9958(75)80005-2
Search in Google Scholar
[19] STEIN, S. K.: Factoring by subsets, Pacific J. Math. 22 (1967), 523-541.10.2140/pjm.1967.22.523
Search in Google Scholar
[20] STEIN, S. K.-SZABÓ, S.: Algebra and Tilings: Homomorphisms in the Service of Geometry. Carus Mathematical Monographs, Vol. 25 Math. Assoc. Amer., Washington, DC, 1994.10.5948/UPO9781614440246
Search in Google Scholar
[21] SZABÓ, S.: On mosaics consisting of multidimensional crosses, Acta Math. Acad. Sci. Hung. 38 (1981), 191-203.10.1007/BF01917533
Search in Google Scholar
[22] SZABÓ, S.: A star polyhedron that tiles but not as fundamental domain, Colloq. Math. Soc. Janos Bolyai 48 (1985), 531-544.
Search in Google Scholar
[23] ŚPACAPAN, S.: Nonexistence of face-to-face four-dimensional tilings in the Lee metric, European. J. Combin. 28 (2007) 127-133.
Search in Google Scholar
[24] ULRICH,W.: Non-binary error-correction codes, Kibern. Sb. 7 (1963), 7-59; transl. from BEll System Tech. J. 36 (1957), 1341-1387.
Search in Google Scholar