Universal bounds for cardinalities and energy of codes in Hamming spaces
Keywords:
Hamming space, Levenshtein bounds, potential functions, energy of a code, errorcorrecting codes, τ-designs, signed measuresAbstract
We survey recent results on universal bounds on the energy of codes in Hamming spaces. The universality means, in particular, that the bounds hold for a large class of potential functions (the most important bounds – for absolutely monotone interactions). Furthermore, we employ signed measures that are positive definite up to certain degrees to establish Levenshtein-type upper bounds on the cardinality of codes with given minimum and maximum distance, and universal lower bounds on the potential energy for codes with given maximum distance and cardinality. In particular, the results extend the Levenshtein framework.
References
M. Abramowitz, I. A. Stegun. Handbook of Mathematical Functions with formulas, graphs, and mathematical tables. Applied Mathematics Series, No. 55. U. S. Government Printing Office, Washington, D.C., 1964.
A. Ashikhmin, A. Barg. Binomial moments of the distance distribution: bounds and applications. IEEE Trans. Inform. Theory 45, no. 2 (1999), 438–452.
A. Ashikhmin, A. Barg, S. Litsyn. Estimates of the distance distribution of codes and designs. IEEE Trans. Inform. Theory 47, No. 3 (2001), 1050–1061.
S. Borodachov, D. Hardin, E. Saff. Minimal Discrete Energy on the Sphere and other Manifolds. New York, Springer, 2019.
P. Boyvalenkov, S. Boumova, D. Danev. Necessary conditions for existence of some designs in polynomial metric spaces. Europ. J. Combin. 20, no. 3 (1999), 213–225.
P. Boyvalenkov, D. Danev. On linear programming bounds for codes in polynomial metric spaces. Problemy Peredachi Informatsii 34, no. 2 (1998), 16–31 (in Russian); English translation in: Problems Inform. Transmission 34, no. 2 (1998), 108–120.
P. Boyvalenkov, D. Danev. On maximal codes in polynomial metric spaces. Applied algebra, algebraic algorithms and error-correcting codes (Toulouse, 1997), 29–38, Lecture Notes in Comput. Sci., vol. 1255. Berlin, Springer, 1997.
P. Boyvalenkov, P. Dragnev, D. Hardin, E. Saff, M. Stoyanova. On spherical codes with inner products in a prescribed interval. Des. Codes Cryptogr. 87, no. 2–3 (2019), 299–315.
P. Boyvalenkov, P. Dragnev, D. Hardin, E. Saff, M. Stoyanova. Universal bounds for size and energy of codes of given minimum and maximum distances. IEEE Trans. Inform. Theory 67, no. 6, part 1 (2021), 3569–3584.
P. Boyvalenkov. Dragnev, D. Hardin, E. Saff, M. Stoyanova. Bounds for spherical codes: the Levenshtein framework lifted. Math. Comp. 90, no. 329 (2021), 1323–1356.
H. Cohn, Y. Zhao. Energy-minimizing error-correcting codes. IEEE Trans. Inform. Theory 60, no. 12 (2014), 7442–7450.
P. Delsarte. An algebraic approach to the association schemes in coding theory. Philips Res. Rep. Suppl. no. 10 (1973).
P. Delsarte, V. I. Levenshtein. Association schemes and coding theory. IEEE Trans. Inform. Theory, 44, no. 6 (1998), 2477–2504.
P. D. Dragnev, E. B. Saff. Constrained energy problems with applications to orthogonal polynomials of a discrete variable. J. Anal. Math. 72 (1997), 223–259.
A. Hedayat, N. J. A Sloane, J. Stufken. Orthogonal Arrays: Theory and Applications. Springer Series in Statistics. New York, Springer-Verlag, 1999.
V. I. Levenshtein. Bounds for packings in metric spaces and certain applications. Problemy Kibernet. 40 (1983), 43–110 (in Russian).
V. I. Levenshte˘ın. Designs as maximum codes in polynomial metric spaces. Interactions between algebra and combinatorics. Acta Appl. Math., 29, no. 1–2 (1992), 1–82.
V. I. Levenshtein. Krawtchouk polynomials and universal bounds for codes and designs in Hamming spaces. IEEE Trans. Infor. Theory, 41, no. 5 (1995), 1303–1321.
V. I. Levenshtein. Universal bounds for codes and designs, In: Handbook of Coding Theory, vol. I, II (Eds, V. S. Pless and W. C. Huffman), 499–648. Amsterdam, NorthHolland, 1998.
F. J. MacWilliams, N. J. A. Sloane. The theory of error-correcting codes, I. North Holland Math. Library, vol. 16. Amsterdam-New York-Oxford,North-Holland Publishing Co., 1977.
R. J. McElliece. The Theory of Information and Coding. Reading MA, AddisonWesley, 1977. 2nd ed. Cambridge Univ. Press, 2002, https://doi.org/10.1017/CBO9780511606267.
C. R. Rao. Factorial experiments derivable from combinatorial arrangements of arrays. Suppl. J. Roy. Statist. Soc. 9 (1947), 128–139.
G. Szego. ˝ Orthogonal Polynomials. American Mathematical Society Colloquium Publications, Vol. 23. New York, AMS, 1939.
V. A. Yudin. Minimum potential energy of a point system of charges. Discret. Mat., 4 (1992), 115–121, (in Russian); English translation in : Discrete Math. Appl., 3, no. 1 (1993), 75–81.
