American Institute of Mathematical Sciences

Advanced
May  2016, 10(2): 393-399. doi: 10.3934/amc.2016013

Non-existence of a ternary constant weight $(16,5,15;2048)$ diameter perfect code

Denis S. Krotov 1, , Patric R. J.  Östergård 2, and  Olli Pottonen 3,

1. 

Sobolev Institute of Mathematics, Mechanics and Mathematics Department, Novosibirsk State University, Novosibirsk, Russian Federation
2. 

Department of Communications and Networking, School of Electrical Engineering, Aalto University, P.O. Box 13000, 00076 Aalto, Finland
3. 

School of Mathematics and Physics, The University of Queensland, Brisbane, Australia

Received  August 2014 Revised  December 2014 Published  April 2016

Ternary constant weight codes of length $n=2^m$, weight $n-1$, cardinality $2^n$ and distance $5$ are known to exist for every $m$ for which there exists an APN permutation of order $2^m$, that is, at least for all odd $m \geq 3$ and for $m=6$. We show the non-existence of such codes for $m=4$ and prove that any codes with the parameters above are diameter perfect.
Keywords: diameter perfect code., Constant weight code.
Mathematics Subject Classification: Primary: 94B2.
Citation: Denis S. Krotov, Patric R. J.  Östergård, Olli Pottonen. Non-existence of a ternary constant weight $(16,5,15;2048)$ diameter perfect code. Advances in Mathematics of Communications, 2016, 10 (2) : 393-399. doi: 10.3934/amc.2016013
References:
[1]

R. Ahlswede, H. K. Aydinian and L. H. Khachatrian, On perfect codes and related concepts, Des. Codes Crypt., 22 (2001), 221-237. doi: 10.1023/A:1008394205999.  Google Scholar

[2]

R. Ahlswede and L. H. Khachatrian, The complete intersection theorem for systems of finite sets, Eur. J. Combin., 18 (1997), 125-136. doi: 10.1006/eujc.1995.0092.  Google Scholar

[3]

R. Ahlswede and L. H. Khachatrian, The diametric theorem in Hamming spaces-optimal anticodes, Adv. Appl. Math., 20 (1998), 429-449. doi: 10.1006/aama.1998.0588.  Google Scholar

[4]

K. A. Browning, J. F. Dillon, M. T. McQuistan and A. J. Wolfe, An APN permutation in dimension six, in Finite Fields: Theory and Applications, Amer. Math. Soc., Providence, 2010, 33-42. doi: 10.1090/conm/518/10194.  Google Scholar

[5]

M. Deza, Une propriété extrémale des plans projectifs finis dans une classe de codes équidistants, Discrete Math., 6 (1973), 343-352.  Google Scholar

[6]

T. Junttila and P. Kaski, Engineering an efficient canonical labeling tool for large and sparse graphs, in Proc. 9th Workshop Algor. Engin. Exper., Soc. Industr. Appl. Math., Philadelphia, 2007, 135-149. Google Scholar

[7]

P. Kaski and O. Pottonen, libexact user's guide, version 1.0, HIIT Technical Reports 2008-1, Helsinki, 2008. Google Scholar

[8]

D. S. Krotov, On diameter perfect constant-weight ternary codes, Discrete Math., 308 (2008), 3104-3114. doi: 10.1016/j.disc.2007.08.037.  Google Scholar

[9]

P. R. J. Östergård and O. Pottonen, The perfect binary one-error-correcting codes of length 15: Part I-classification, IEEE Trans. Inf. Theory, 55 (2009), 4657-4660. doi: 10.1109/TIT.2009.2027525.  Google Scholar

[10]

P. R. J. Östergård and M. Svanström, Ternary constant weight codes, Electr. J. Combin., 9(1) (2002), #R41.  Google Scholar

[11]

M. Svanström, A class of perfect ternary constant-weight codes, Des. Codes Crypt., 18 (1999), 223-229. doi: 10.1023/A:1008361925021.  Google Scholar

[12]

M. Svanström, Ternary Codes with Weight Constraints, Ph.D thesis, Linköping Univ., 1999. Google Scholar

[13]

H. Tanaka, Classification of subsets with minimal width and dual width in Grassmann, bilinear forms and dual polar graphs, J. Combin. Theory Ser. A, 113 (2006), 903-910. doi: 10.1016/j.jcta.2005.08.006.  Google Scholar

[14]

J. van Lint and L. Tolhuizen, On perfect ternary constant weight codes, Des. Codes Crypt., 18 (1999), 231-234. doi: 10.1023/A:1008314009092.  Google Scholar

show all references

References:
[1]

R. Ahlswede, H. K. Aydinian and L. H. Khachatrian, On perfect codes and related concepts, Des. Codes Crypt., 22 (2001), 221-237. doi: 10.1023/A:1008394205999.  Google Scholar

[2]

R. Ahlswede and L. H. Khachatrian, The complete intersection theorem for systems of finite sets, Eur. J. Combin., 18 (1997), 125-136. doi: 10.1006/eujc.1995.0092.  Google Scholar

[3]

R. Ahlswede and L. H. Khachatrian, The diametric theorem in Hamming spaces-optimal anticodes, Adv. Appl. Math., 20 (1998), 429-449. doi: 10.1006/aama.1998.0588.  Google Scholar

[4]

K. A. Browning, J. F. Dillon, M. T. McQuistan and A. J. Wolfe, An APN permutation in dimension six, in Finite Fields: Theory and Applications, Amer. Math. Soc., Providence, 2010, 33-42. doi: 10.1090/conm/518/10194.  Google Scholar

[5]

M. Deza, Une propriété extrémale des plans projectifs finis dans une classe de codes équidistants, Discrete Math., 6 (1973), 343-352.  Google Scholar

[6]

T. Junttila and P. Kaski, Engineering an efficient canonical labeling tool for large and sparse graphs, in Proc. 9th Workshop Algor. Engin. Exper., Soc. Industr. Appl. Math., Philadelphia, 2007, 135-149. Google Scholar

[7]

P. Kaski and O. Pottonen, libexact user's guide, version 1.0, HIIT Technical Reports 2008-1, Helsinki, 2008. Google Scholar

[8]

D. S. Krotov, On diameter perfect constant-weight ternary codes, Discrete Math., 308 (2008), 3104-3114. doi: 10.1016/j.disc.2007.08.037.  Google Scholar

[9]

P. R. J. Östergård and O. Pottonen, The perfect binary one-error-correcting codes of length 15: Part I-classification, IEEE Trans. Inf. Theory, 55 (2009), 4657-4660. doi: 10.1109/TIT.2009.2027525.  Google Scholar

[10]

P. R. J. Östergård and M. Svanström, Ternary constant weight codes, Electr. J. Combin., 9(1) (2002), #R41.  Google Scholar

[11]

M. Svanström, A class of perfect ternary constant-weight codes, Des. Codes Crypt., 18 (1999), 223-229. doi: 10.1023/A:1008361925021.  Google Scholar

[12]

M. Svanström, Ternary Codes with Weight Constraints, Ph.D thesis, Linköping Univ., 1999. Google Scholar

[13]

H. Tanaka, Classification of subsets with minimal width and dual width in Grassmann, bilinear forms and dual polar graphs, J. Combin. Theory Ser. A, 113 (2006), 903-910. doi: 10.1016/j.jcta.2005.08.006.  Google Scholar

[14]

J. van Lint and L. Tolhuizen, On perfect ternary constant weight codes, Des. Codes Crypt., 18 (1999), 231-234. doi: 10.1023/A:1008314009092.  Google Scholar

[1]

Olof Heden. The partial order of perfect codes associated to a perfect code. Advances in Mathematics of Communications, 2007, 1 (4) : 399-412. doi: 10.3934/amc.2007.1.399
[2]

María Chara, Ricardo A. Podestá, Ricardo Toledano. The conorm code of an AG-code. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021018
[3]

Masaaki Harada, Ethan Novak, Vladimir D. Tonchev. The weight distribution of the self-dual $[128,64]$ polarity design code. Advances in Mathematics of Communications, 2016, 10 (3) : 643-648. doi: 10.3934/amc.2016032
[4]

Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1
[5]

Irene Márquez-Corbella, Edgar Martínez-Moro, Emilio Suárez-Canedo. On the ideal associated to a linear code. Advances in Mathematics of Communications, 2016, 10 (2) : 229-254. doi: 10.3934/amc.2016003
[6]

Serhii Dyshko. On extendability of additive code isometries. Advances in Mathematics of Communications, 2016, 10 (1) : 45-52. doi: 10.3934/amc.2016.10.45
[7]

Sascha Kurz. The $[46, 9, 20]_2$ code is unique. Advances in Mathematics of Communications, 2021, 15 (3) : 415-422. doi: 10.3934/amc.2020074
[8]

Selim Esedoḡlu, Fadil Santosa. Error estimates for a bar code reconstruction method. Discrete & Continuous Dynamical Systems - B, 2012, 17 (6) : 1889-1902. doi: 10.3934/dcdsb.2012.17.1889
[9]

M. Delgado Pineda, E. A. Galperin, P. Jiménez Guerra. MAPLE code of the cubic algorithm for multiobjective optimization with box constraints. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407
[10]

Jorge P. Arpasi. On the non-Abelian group code capacity of memoryless channels. Advances in Mathematics of Communications, 2020, 14 (3) : 423-436. doi: 10.3934/amc.2020058
[11]

Andrew Klapper, Andrew Mertz. The two covering radius of the two error correcting BCH code. Advances in Mathematics of Communications, 2009, 3 (1) : 83-95. doi: 10.3934/amc.2009.3.83
[12]

Masaaki Harada, Takuji Nishimura. An extremal singly even self-dual code of length 88. Advances in Mathematics of Communications, 2007, 1 (2) : 261-267. doi: 10.3934/amc.2007.1.261
[13]

José Gómez-Torrecillas, F. J. Lobillo, Gabriel Navarro. Information--bit error rate and false positives in an MDS code. Advances in Mathematics of Communications, 2015, 9 (2) : 149-168. doi: 10.3934/amc.2015.9.149
[14]

M. De Boeck, P. Vandendriessche. On the dual code of points and generators on the Hermitian variety $\mathcal{H}(2n+1,q^{2})$. Advances in Mathematics of Communications, 2014, 8 (3) : 281-296. doi: 10.3934/amc.2014.8.281
[15]

Sihuang Hu, Gabriele Nebe. There is no $[24,12,9]$ doubly-even self-dual code over $\mathbb F_4$. Advances in Mathematics of Communications, 2016, 10 (3) : 583-588. doi: 10.3934/amc.2016027
[16]

Michael Kiermaier, Johannes Zwanzger. A $\mathbb Z$4-linear code of high minimum Lee distance derived from a hyperoval. Advances in Mathematics of Communications, 2011, 5 (2) : 275-286. doi: 10.3934/amc.2011.5.275
[17]

Anna-Lena Horlemann-Trautmann, Kyle Marshall. New criteria for MRD and Gabidulin codes and some Rank-Metric code constructions. Advances in Mathematics of Communications, 2017, 11 (3) : 533-548. doi: 10.3934/amc.2017042
[18]

Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2021, 15 (1) : 113-130. doi: 10.3934/amc.2020046
[19]

Terry Shue Chien Lau, Chik How Tan. Polynomial-time plaintext recovery attacks on the IKKR code-based cryptosystems. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020132
[20]

Jianying Fang. 5-SEEDs from the lifted Golay code of length 24 over Z4. Advances in Mathematics of Communications, 2017, 11 (1) : 259-266. doi: 10.3934/amc.2017017

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (95)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences