Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Semidefinite programming bounds for binary codes from a split Terwilliger algebra

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

We study the upper bounds for A(n, d), the maximum size of codewords with length n and Hamming distance at least d. Schrijver studied the Terwilliger algebra of the Hamming scheme and proposed a semidefinite program to bound A(n, d). We derive more sophisticated matrix inequalities based on a split Terwilliger algebra to improve Schrijver’s semidefinite programming bounds on A(n, d). In particular, we improve the semidefinite programming bounds on A(18, 4) to 6551.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ashikhmin A., Lai C.-Y., Brun T.A.: Quantum data-syndrome codes. IEEE J. Sel. Areas Commun. 38(3), 449–462 (2020). https://doi.org/10.1109/JSAC.2020.2968997.

    Article  Google Scholar 

  2. Bachoc, C.: Applications of semidefinite programming to coding theory. In: Proceedings of the 2010 IEEE Information Theory Workshop (ITW), pp. 1–5 (2010). https://doi.org/10.1109/CIG.2010.5592938

  3. Bannai, E., Bannai, E., Ito, T., Tanaka, R.: Algebraic combinatorics. De Gruyter Series in Discrete Mathematics and Applications. Walter de Gruyter GmbH, Co KG, Berlin, Boston (2021)

  4. Best M., Brouwer A., MacWilliams F., Odlyzko A., Sloane N.: Bounds for binary codes of length less than 25. IEEE Trans. Inf. Theory 24(1), 81–93 (1978). https://doi.org/10.1109/TIT.1978.1055827.

    Article  MathSciNet  MATH  Google Scholar 

  5. Best M.: Binary codes with a minimum distance of four. IEEE Trans. Inf. Theory 26(6), 738–742 (1980). https://doi.org/10.1109/TIT.1980.1056269.

    Article  MathSciNet  MATH  Google Scholar 

  6. Barg A., Musin O.R.: Bounds on sets with few distances. J. Comb. Theory Ser. A 118(4), 1465–1474 (2011). https://doi.org/10.1016/j.jcta.2011.01.002.

    Article  MathSciNet  MATH  Google Scholar 

  7. Brouwer, A.: Table of general binary codes. https://www.win.tue.nl/ aeb/codes/binary-1.html (2022). Accessed 14 Feb

  8. Bachoc C., Vallentin F.: New upper bounds for kissing numbers from semidefinite programming. J. Am. Math. Soc. 21(3), 909–924 (2008). https://doi.org/10.1090/S0894-0347-07-00589-9.

    Article  MathSciNet  MATH  Google Scholar 

  9. Barg A., Yu W.-H.: New bounds for equiangular lines. Discret. Geom. Algebr. Comb. 625, 111–121 (2013).

    MathSciNet  MATH  Google Scholar 

  10. Barg A., Yu W.-H.: New bounds for spherical two-distance sets. Exp. Math. 22(2), 187–194 (2013). https://doi.org/10.1080/10586458.2013.767725.

    Article  MathSciNet  MATH  Google Scholar 

  11. Delsarte P.: An algebraic approach to the association schemes of coding theory. Philips Res. 10, 880–886 (1973).

    MATH  Google Scholar 

  12. Grant M., Boyd S.: Graph implementations for nonsmooth convex programs. In: Blondel V., Boyd S., Kimura H. (eds.) Recent Advances in Learning and Control, pp. 95–110. Lecture notes in control and information Sciences. Springer-Verlag, Berlin Heidelberg (2008).

    Chapter  Google Scholar 

  13. Grant, M., Boyd, S.: CVX: MATLAB software for disciplined convex programming, version 2.1. http://cvxr.com/cvx (2014)

  14. Gijswijt, D.: Matrix algebras and semidefinite programming techniques for codes. PhD thesis, University of Amsterdam (2005)

  15. Gijswijt, D.: Block diagonalization for algebra’s associated with block codes. https://arxiv.org/0910.4515 (2009)

  16. Gijswijt D., Mittelmann H., Schrijver A.: Semidefinite code bounds based on quadruple distances. IEEE Trans. Inf. Theory 58(5), 2697–2705 (2012). https://doi.org/10.1109/TIT.2012.2184845.

    Article  MathSciNet  MATH  Google Scholar 

  17. Gijswijt D., Schrijver A., Tanaka H.: New upper bounds for nonbinary codes based on the Terwilliger algebra and semidefinite programming. J. Comb. Theory Ser. A 113(8), 1719–1731 (2006). https://doi.org/10.1016/j.jcta.2006.03.010.

    Article  MathSciNet  MATH  Google Scholar 

  18. Hou L., Hou B., Gao S., Yu W.-H.: New code upper bounds for the folded n-cube. J. Comb. Theory Ser. A 172, 105182 (2020). https://doi.org/10.1016/j.jcta.2019.105182.

    Article  MathSciNet  MATH  Google Scholar 

  19. Kim H.-K., Toan P.-T.: Improved semidefinite programming bound on sizes of codes. IEEE Trans. Inf. Theory 59(11), 7337–7345 (2013). https://doi.org/10.1109/TIT.2013.2277714.

    Article  MathSciNet  MATH  Google Scholar 

  20. Lai C.-Y., Ashikhmin A.: Linear programming bounds for entanglement-assisted quantum error-correcting codes by split weight enumerators. IEEE Trans. Inf. Theory 64(1), 622–639 (2018). https://doi.org/10.1109/TIT.2017.2711601.

    Article  MathSciNet  MATH  Google Scholar 

  21. Laurent M.: Strengthened semidefinite programming bounds for codes. Math. Program. 109, 239–261 (2007). https://doi.org/10.1007/s10107-006-0030-3.

    Article  MathSciNet  MATH  Google Scholar 

  22. Lai C.-Y., Hsieh M.-H., Lu H.-F.: On the MacWilliams identity for classical and quantum convolutional codes. IEEE Trans. Commun. 64(8), 3148–3159 (2016). https://doi.org/10.1109/TCOMM.2016.2585641.

    Article  Google Scholar 

  23. Litjens B., Polak S., Schrijver A.: Semidefinite bounds for nonbinary codes based on quadruples. Des. Codes Cryptogr. 84, 87–100 (2017). https://doi.org/10.1007/s10623-016-0216-5.

    Article  MathSciNet  MATH  Google Scholar 

  24. Machado F.C., de Oliveira Filho F.M.: Improving the semidefinite programming bound for the kissing number by exploiting polynomial symmetry. Exp. Math. 27(3), 362–369 (2018). https://doi.org/10.1080/10586458.2017.1286273.

    Article  MathSciNet  MATH  Google Scholar 

  25. Mounits B., Etzion T., Litsyn S.: Improved upper bounds on sizes of codes. IEEE Trans. Inf. Theory 48(4), 880–886 (2002). https://doi.org/10.1109/18.992776.

    Article  MathSciNet  MATH  Google Scholar 

  26. Musin O.R., Nozaki H.: Bounds on three- and higher-distance sets. Eur. J. Comb. 32(8), 1182–1190 (2011). https://doi.org/10.1016/j.ejc.2011.03.003.

    Article  MathSciNet  MATH  Google Scholar 

  27. MacWilliams F.J., Sloane N.J.A.: The Theory of Error Correcting Codes. North Holland Publishing Co., North Holland (1977).

    MATH  Google Scholar 

  28. Östergård P.R.J.: The sextuply shortened binary golay code is optimal. Des. Codes Cryptogr. 87(2), 341–347 (2019). https://doi.org/10.1007/s10623-018-0532-z.

    Article  MathSciNet  MATH  Google Scholar 

  29. Polak, S.C.: New methods in coding theory: Error-correcting codes and the Shannon capacity. PhD thesis, University of Amsterdam (2019)

  30. Polak S.C.: Semidefinite programming bounds for constant-weight codes. IEEE Trans. Inf. Theory 65(1), 28–38 (2019). https://doi.org/10.1109/TIT.2018.2854800.

    Article  MathSciNet  MATH  Google Scholar 

  31. Schrijver A.: A comparison of the Delsarte and Lovász bounds. IEEE Trans. Inf. Theory 25(4), 425–429 (1979). https://doi.org/10.1109/TIT.1979.1056072.

    Article  MATH  Google Scholar 

  32. Schrijver A.: New code upper bounds from the Terwilliger algebra and semidefinite programming. IEEE Trans. Inf. Theory 51(8), 2859–2866 (2005). https://doi.org/10.1109/TIT.2005.851748.

    Article  MathSciNet  MATH  Google Scholar 

  33. Simonis J.: MacWilliams identities and coordinate partitions. Linear Algebra Appl. 216, 81–91 (1995). https://doi.org/10.1016/0024-3795(93)00106-A.

    Article  MathSciNet  MATH  Google Scholar 

  34. Terwilliger P.: The subconstituent algebra of an association scheme, (part I). J. Algebr. Comb. 1, 363–388 (1992). https://doi.org/10.1023/A:1022494701663.

    Article  MATH  Google Scholar 

  35. Terwilliger P.: The subconstituent algebra of an association scheme, (part II). J. Algebr. Comb. 2, 73–103 (1993). https://doi.org/10.1023/A:1022480715311.

    Article  MATH  Google Scholar 

  36. Tseng, P.-C., Lai, C.-Y., Yu, W.-H.: Improved semidefinite programming bounds for binary codes by split distance enumerations. In: Proceedings of the 2022 IEEE International Symposium on Information Theory (ISIT), pp. 3073–3078 (2022). https://doi.org/10.1109/ISIT50566.2022.9834515

Download references

Acknowledgements

We would like to thank Dion Gijswijt, Alexander Schrijver, and Hajime Tanaka for helpful discussions. We would also like to thank the anonymous referees for their valuable comments. PCT and CYL were supported by the Ministry of Science and Technology (MOST) in Taiwan under Grant MOST110-2628-E-A49-007. WHY was supported by MOST under Grant109-2628-M-008-002-MY4.

Author information

Authors and Affiliations

  1. Institute of Communications Engineering, National Yang Ming Chiao Tung University, Hsinchu, 30010, Taiwan

    Pin-Chieh Tseng & Ching-Yi Lai

  2. Department of Applied Mathematics, National Yang Ming Chiao Tung University, Hsinchu, 30010, Taiwan

    Pin-Chieh Tseng

  3. Department of Mathematics, National Central University, Taoyüan, 32001, Taiwan

    Wei-Hsuan Yu

Authors
  1. Pin-Chieh Tseng
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ching-Yi Lai
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Wei-Hsuan Yu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pin-Chieh Tseng.

Additional information

Communicated by G. Korchmaros.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This article was presented in part at ISIT 2022 [36].

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Tseng, PC., Lai, CY. & Yu, WH. Semidefinite programming bounds for binary codes from a split Terwilliger algebra. Des. Codes Cryptogr. 91, 3241–3262 (2023). https://doi.org/10.1007/s10623-023-01250-4

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-023-01250-4

Keywords

Mathematics Subject Classification

Search

Navigation