Paper Info
Title
Duality of codes supported on regular lattices, with an application to enumerative combinatorics
Abstract
We introduce a general class of regular weight functions on finite abelian groups, and study the combinatorics, the duality theory, and the metric properties of codes endowed with such functions. The weights are obtained by composing a suitable support map with the rank function of a graded lattice satisfying certain regularity properties. A regular weight on a group canonically induces a regular weight on the character group, and invertible MacWilliams identities always hold for such a pair of weights. Moreover, the Krawtchouk coefficients of the corresponding MacWilliams transformation have a precise combinatorial significance, and can be expressed in terms of the invariants of the underlying lattice. In particular, they are easy to compute in many examples. Several weight functions traditionally studied in Coding Theory belong to the class of weights introduced in this paper. Our lattice-theory approach also offers a control on metric structures that a regular weight induces on the underlying group. In particular, it allows to show that every finite abelian group admits weight functions that, simultaneously, give rise to MacWilliams identities, and endow the underlying group with a metric space structure. We propose a general notion of extremality for (not necessarily additive) codes in groups endowed with semi-regular supports, and establish a Singleton-type bound. We then investigate the combinatorics and duality theory of extremal codes, extending classical results on the weight and distance distribution of error-correcting codes. Finally, we apply the theory of MacWilliams identities to enumerative combinatorics problems, obtaining closed formulae for the number of rectangular matrices over a finite having prescribed rank and satisfying some linear conditions.
Year
DOI
Venue
2015
https://doi.org/10.1007/s10623-017-0436-3
Designs, Codes and Cryptography
Keywords
Field
DocType
Additive code (finite abelian group),Poset lattice,Support map,Weight function,MacWilliams identity,Extremal code,Weight distribution,Distance distribution,Enumerative combinatorics,11T71,05A15,06B05,20K01
Discrete mathematics,Abelian group,Combinatorics,Duality (mathematics),Enumerative combinatorics,Duality (optimization),Coding theory,Invariant (mathematics),Metric space,Mathematics,Character group
Journal
Volume
Issue
ISSN
abs/1510.02383
9
0925-1022
Citations 
PageRank 
References 
0
0.34
13
Authors
1
Name
Order
Citations
PageRank
Alberto Ravagnani1329.46