Search

We consider properties of the class of $\mathcal{L}$-polymatroids, especially those that are defined on a finite modular complemented lattice $\mathcal{L}$. We give a set of cover-weight axioms and hence give a cryptomorphism between these axioms and the rank axioms of an $\mathcal{L}$-polymatroid. We introduce the notion of a cyclic flat of an $\mathcal{L}$-polymatroid and study properties of its lattice of cyclic flats. We show that the weighted lattice of cyclic flats of an $\mathcal{L}$-polymatroid along with its atomic weights are sufficient to define its rank function on $\mathcal{L}$. In our main result, we characterise those lattices $\mathcal{Z} \subseteq \mathcal{L}$ such that $\mathcal{Z}$ is the collection of cyclic flats of an $\mathcal{L}$-polymatroid., Comment: 31 pages, 8 figures

The Critical Theorem, due to Henry Crapo and Gian-Carlo Rota, has been extended and generalised in many ways. In this paper, we describe properties of the characteristic polynomial of a weighted lattice and show that it has a recursive description, which we use to obtain results on the critical exponent of $q$-polymatroids. We prove a Critical Theorem for representable $q$-polymatroids and we provide a lower bound on the critical exponent. We show that $q$-polymatroids arising from certain families of rank-metric codes attain this lower bound.

We describe a construction of the Tutte polynomial for both matroids and $q$-matroids based on an appropriate partition of the underlying support lattice into intervals that correspond to prime-free minors, which we call a Tutte partition. We show that such partitions in the matroid case include the class of partitions arising in Crapo's definition of the Tutte polynomial, while not representing a direct $q$-analogue of such partitions. We propose axioms of $q$-Tutte-Grothendiek invariance and show that this yields a $q$-analogue of Tutte-Grothendiek invariance. We establish the connection between the rank polynomial and the Tutte polynomial, showing that one can be obtained from the other by convolution.

We introduce the concept of a rank saturating system and outline its correspondence to a rank-metric code with a given covering radius. We consider the problem of finding the value of $s_{q^m/q}(k,\rho)$, which is the minimum $\mathbb{F}_q$-dimension of a $q$-system in $\mathbb{F}_{q^m}^k$ which is rank $\rho$-saturating. This is equivalent to the covering problem in the rank metric. We obtain upper and lower bounds on $s_{q^m/q}(k,\rho)$ and evaluate it for certain values of $k$ and $\rho$. We give constructions of rank $\rho$-saturating systems suggested from geometry., Comment: 26 pages, to appear in Journal of Algebraic Combinatorics

In this paper we develop the theory of cyclic flats of $q$-matroids. We show that the lattice of cyclic flats, together with their ranks, uniquely determines a $q$-matroid and hence derive a new $q$-cryptomorphism. We introduce the notion of $\mathbb{F}_{q^m}$-independence of an $\mathbb{F}_q$-subspace of $\mathbb{F}_q^n$ and we show that $q$-matroids generalize this concept, in the same way that matroids generalize the notion of linear independence of vectors over a given field.

In 1991, Roth introduced a natural generalization of rank metric codes, namely tensor codes. The latter are defined to be subspaces of $r$-tensors where the ambient space is endowed with the tensor rank as a distance function. In this work, we describe the general class of tensor codes and we study their invariants that correspond to different families of anticodes. In our context, an anticode is a perfect space that has some additional properties. A perfect space is one that is spanned by tensors of rank 1. Our use of the anticode concept is motivated by an interest in capturing structural properties of tensor codes. In particular, we indentify four different classes of tensor anticodes and show how these gives different information on the codes they describe. We also define the generalized tensor binomial moments and the generalized tensor weight distribution of a code and establish a bijection between these invariants. We use the generalized tensor binomial moments to define the concept of an $i$-tensor BMD code, which is an extremal code in relation to an inequality arising from them. Finally, we give MacWilliams identities for generalized tensor binomial moments., Comment: 25 pages

In this paper we investigate known Singleton-like bounds in the Lee metric and characterize optimal codes, which turn out to be very few. We then focus on Plotkin-like bounds in the Lee metric and present a new bound that extends and refines a previously known, and out-performs it in the case of non-free codes. We then compute the density of optimal codes with regard to the new bound. Finally we fill a gap in the characterization of Lee-equidistant codes.

In this paper we focus on modules over a finite chain ring $\mathcal{R}$ of size $q^s$. We compute the density of free modules of $\mathcal{R}^n$, where we separately treat the asymptotics in $n,q$ and $s$. In particular, we focus on two cases: one where we fix the length of the module and one where we fix the rank of the module. In both cases, the density results can be bounded by the Andrews-Gordon identities. We also study the asymptotic behaviour of modules generated by random matrices over $\mathcal{R}$. Since linear codes over $\mathcal{R}$ are submodules of $\mathcal{R}^n$ we get direct implications for coding theory. For example, we show that random codes achieve the Gilbert-Varshamov bound with high probability.

The Assmus-Mattson theorem gives a way to identify block designs arising from codes. This result was broadened to matroids and weighted designs. In this work we present a further two-fold generalisation: first from matroids to polymatroids and also from sets to vector spaces. To achieve this, we introduce the characteristic polynomial of a $q$-polymatroid and outline several of its properties.

In the theory of classical matroids, there are several known equivalent axiomatic systems that define a matroid, which are described as matroid cryptomorphisms. A q-matroid is a q-analogue of a matroid where subspaces play the role of the subsets in the classical theory. In this article we establish cryptomorphisms of q-matroids. In doing so we highlight the difference between classical theory and its q-analogue. We introduce a comprehensive set of q-matroid axiom systems and show cryptomorphisms between them and existing axiom systems of a q-matroid. These axioms are described as the rank, closure, basis, independence, dependence, circuit, hyperplane, flat, open space, spanning space, non-spanning space, and bi-colouring axioms.

A well studied problem in algebraic complexity theory is the determination of the complexity of problems relying on evaluations of bilinear maps. One measure of the complexity of a bilinear map (or 3-tensor) is the optimal number of non-scalar multiplications required to evaluate it. This quantity is also described as its tensor rank, which is the smallest number of rank one matrices whose span contains its first slice space. In this paper we derive upper bounds on the tensor ranks of certain classes of $3$-tensors and give explicit constructions of sets of rank one matrices containing their first slice spaces. We also show how these results can be applied in coding theory to derive upper bounds on the tensor rank of some rank-metric codes. In particular, we compute the tensor rank of some families of $\mathbb{F}_{q^m}$-linear codes and we show that they are extremal with respect to Kruskal's tensor rank bound., Comment: 24 pages

We study the structure of anticodes in the sum-rank metric for arbitrary fields and matrix blocks of arbitrary sizes. Our main result is a complete classification of optimal linear anticodes. We also compare the cardinality of the ball in the sum-rank metric with that of an optimal linear anticode, showing that the latter is strictly larger over sufficiently large finite fields. Finally, we give examples of parameters for which the largest anticode is neither a ball nor a linear anticode

This paper investigates the theory of sum-rank metric codes for which the individual matrix blocks may have different sizes. Various bounds on the cardinality of a code are derived, along with their asymptotic extensions. The duality theory of sum-rank metric codes is also explored, showing that MSRD codes (the sum-rank analogue of MDS codes) dualize to MSRD codes only if all matrix blocks have the same number of columns. In the latter case, duality considerations lead to an upper bound on the number of blocks for MSRD codes. The paper also contains various constructions of sum-rank metric codes for variable block sizes, illustrating the possible behaviours of these objects with respect to bounds, existence, and duality properties.

A perfect matroid design (PMD) is a matroid whose flats of the same rank all have the same size. In this paper we introduce the q-analogue of a PMD and its properties. In order to do so, we first establish a new cryptomorphic definition for q-matroids. We show that q-Steiner systems are examples of q-PMD's and we use this q-matroid structure to construct subspace designs from q-Steiner systems. We apply this construction to the only known q-Steiner system, which has parameters S(2,3,13;2), and hence establish the existence of a new subspace design with parameters 2-(13,4,5115;2).

In this paper we introduce a new class of extremal codes, namely the $i$-BMD codes. We show that for this family several of the invariants are determined by the parameters of the underlying code. We refine and extend the notion of an $i$-MRD code and show that the $i$-BMD codes form a proper subclass of the $i$-MRD codes. Using the class of $i$-BMD codes we then obtain a relation between the generalized rank weight enumerator and its corresponding generalized zeta function. We also establish a MacWilliams identity for generalized rank weight distributions., Comment: 27 pages

We present the theory of rank-metric codes with respect to the 3-tensors that generate them. We define the generator tensor and the parity check tensor of a matrix code, and describe the properties of a code through these objects. We define the tensor rank of a code to be the tensor rank of its generating tensors, and propose that this quantity is a significant coding theoretic parameter. By a result on the tensor rank of Kruskal from the 1970s, the tensor rank of a rank-metric code of dimension $k$ and minimum rank distance $d$ is at least $k+d-1$. We call codes that meet this bound minimal tensor rank (MTR) codes. It is known from results in algebraic complexity theory that an MTR code implies the existence of an MDS code. In this paper, we also address the converse problem, that of the existence of an MTR code, given an MDS code. We identify several parameters for which the converse holds and give explicit constructions of MTR codes using MDS codes. We furthermore define generalized tensor ranks, which give a refinement of the tensor rank as a code invariant. Moreover, we use these to distinguish inequivalent rank-metric codes.

A $t$-$(n,d,\lambda)$ design over ${\mathbb F}_q$, or a subspace design, is a collection of $d$-dimensional subspaces of ${\mathbb F}_q^n$, called blocks, with the property that every $t$-dimensional subspace of ${\mathbb F}_q^n$ is contained in the same number $\lambda$ of blocks. A collection of matrices in over ${\mathbb F}_q$ is said to hold a subspace design if the set of column spaces of its elements forms the blocks of a subspace design. We use notions of puncturing and shortening of rank metric codes and the rank-metric MacWilliams identities to establish conditions under which the words of a given rank in a linear rank metric code hold a subspace design.

We introduce the class of partition-balanced families of codes, and show how to exploit their combinatorial invariants to obtain upper and lower bounds on the number of codes that have a prescribed property. In particular, we derive precise asymptotic estimates on the density functions of several classes of codes that are extremal with respect to minimum distance, covering radius, and maximality. The techniques developed in this paper apply to various distance functions, including the Hamming and the rank metric distances. Applications of our results show that, unlike the $\mathbb{F}_{q^m}$-linear MRD codes, the $\mathbb{F}_q$-linear MRD codes are not dense in the family of codes of the same dimension. More precisely, we show that the density of $\mathbb{F}_q$-linear MRD codes in $\mathbb{F}_q^{n \times m}$ in the set of all matrix codes of the same dimension is asymptotically at most $1/2$, both as $q \to +\infty$ and as $m \to +\infty$. We also prove that MDS and $\mathbb{F}_{q^m}$-linear MRD codes are dense in the family of maximal codes. Although there does not exist a direct analogue of the redundancy bound for the covering radius of $\mathbb{F}_q$-linear rank metric codes, we show that a similar bound is satisfied by a uniformly random matrix code with high probability. In particular, we prove that codes meeting this bound are dense. Finally, we compute the average weight distribution of linear codes in the rank metric, and other parameters that generalize the total weight of a linear code.

We consider distance functions on a quotient module $M/K$ induced by distance functions on a module $M$. We define error-correction for codes in $M/K$ with respect to induced distance functions. For the case that the metric is induced by a homogeneous weight, we derive analogues of the Plotkin and Elias-Bassalygo bounds and give their asymptotic versions. These results have applications to coherent network error-correction in the presence of adversarial errors. We outline this connection, extending the linear network coding scheme introduced by Yang et al.

In this paper we study properties and invariants of matrix codes endowed with the rank metric, and relate them to the covering radius. We introduce new tools for the analysis of rank-metric codes, such as puncturing and shortening constructions. We give upper bounds on the covering radius of a code by applying different combinatorial methods. We apply the various bounds to the classes of maximal rank distance and quasi maximal rank distance codes.

Coding schemes with extremely low computational complexity are required for particular applications, such as wireless body area networks, in which case both very high data accuracy and very low power-consumption are required features. In this paper, coding schemes arising from incidence matrices of graphs are proposed. An analysis of the resilience of such codes to erasures is given using graph theoretical arguments; decodability of a graph is characterized in terms of the rank of its incidence matrix. Bounds are given on the number of decodable subgraphs of a graph and the number of edges that must be deleted in order to arrive at an undecodable subgraph. Algorithms to construct codes that are optimal with respect to these bounds are presented.

In this work we study both the index coding with side information (ICSI) problem introduced by Birk and Kol in 1998 and the more general problem of index coding with coded side information (ICCSI), described by Shum et al in 2012. We estimate the optimal rate of an instance of the index coding problem. In the ICSI problem case, we characterize those digraphs having min-rank one less than their order and we give an upper bound on the min-rank of a hypergraph whose incidence matrix can be associated with that of a 2-design. Security aspects are discussed in the particular case when the design is a projective plane. For the coded side information case, we extend the graph theoretic upper bounds given by Shanmugam et al in 2014 on the optimal rate of index code.

Index coding is a source coding problem in which a broadcaster seeks to meet the different demands of several users, each of whom is assumed to have some prior information on the data held by the sender. If the sender knows its clients' requests and their side-information sets, then the number of packet transmissions required to satisfy all users' demands can be greatly reduced if the data is encoded before sending. The collection of side-information indices as well as the indices of the requested data is described as an instance of the index coding with side-information (ICSI) problem. The encoding function is called the index code of the instance, and the number of transmissions employed by the code is referred to as its length. The main ICSI problem is to determine the optimal length of an index code for and instance. As this number is hard to compute, bounds approximating it are sought, as are algorithms to compute efficient index codes. Two interesting generalizations of the problem that have appeared in the literature are the subject of this work. The first of these is the case of index coding with coded side information, in which linear combinations of the source data are both requested by and held as users' side-information. The second is the introduction of error-correction in the problem, in which the broadcast channel is subject to noise. In this paper we characterize the optimal length of a scalar or vector linear index code with coded side information (ICCSI) over a finite field in terms of a generalized min-rank and give bounds on this number based on constructions of random codes for an arbitrary instance. We furthermore consider the length of an optimal error correcting code for an instance of the ICCSI problem and obtain bounds on this number, both for the Hamming metric and for rank-metric errors. We describe decoding algorithms for both categories of errors.

In this article we investigate Berlekamp's negacyclic codes and discover that these codes, when considered over the integers modulo 4, do not suffer any of the restrictions on the minimum distance observed in Berlekamp's original papers. The codes considered here have minimim Lee distance at least 2t+1, where the generator polynomial of the code has roots z,z^3,...,z^{2t+1} for a primitive 2nth root of unity z in a Galois extension of Z4. No restriction on t is imposed. We present an algebraic decoding algorithm for this class of codes that corrects any error pattern of Lee weight at most t. Our treatment uses Grobner bases and the decoding complexity is quadratic in t., Comment: 17 pages

Modern medical wireless systems, such as wireless body area networks (WBANs), are applications of wireless networks that can be used as a tool of data transmission between patients and doctors. Accuracy of data transmission is an important requirement for such systems. In this paper, we will propose a WBAN which is robust against erasures and describe its properties using graph theoretic techniques.

Delsarte showed that for any projective linear code over a finite field of characteristic p with two nonzero Hamming weights w1 < w2 there exist positive integers u and s such that w1 = (p^s)u and w2 = (p^s)(u+1). Moreover, he showed that the additive group of such a code has a strongly regular Cayley graph. Here we show that for any proper regular projective linear code C over a finite Frobenius ring with two integral nonzero homogeneous weights w1 < w2, there is a positive integer d, a divisor of the order of C, and positive integer u such that w1 = du and w2 = d(u+1). In doing so, we give a new proof of the known result that any proper regular projective two-weight code code yields a strongly regular graph. We apply these results to existence questions on two-weight codes.

Establishing the CCZ-equivalence of a pair of APN functions is generally quite difficult. In some cases, when seeking to show that a putative new infinite family of APN functions is CCZ inequivalent to an already known family, we rely on computer calculation for small values of n. In this paper we present a method to prove the inequivalence of quadratic APN functions with the Gold functions. Our main result is that a quadratic function is CCZ-equivalent to an APN Gold function if and only if it is EA-equivalent to that Gold function. As an application of this result, we prove that a trinomial family of APN functions that exist on finite fields of order 2^n where n = 2 mod 4 are CCZ inequivalent to the Gold functions. The proof relies on some knowledge of the automorphism group of a code associated with such a function., Comment: 13 pg

Let R > S be finite Frobenius rings for which there exists a trace map T from R onto S as left S modules. Let C:= {x -> T(ax + bf(x)) : a,b in R}. Then C is an S-linear subring-subcode of a left linear code over R. We consider functions f for which the homogeneous weight distribution of C can be computed. In particular, we give constructions of codes over integer modular rings and commutative local Frobenius that have small spectra., Comment: 18 pg

We give results on the question of code optimality for linear codes over finite Frobenius rings for the homogeneous weight. This article improves on the existing Plotkin bound derived in an earlier paper, and suggests a version of a Singleton bound. We also present some families of codes meeting these new bounds.

We present two infinite families of APN functions where the degree of the field is divisible by 3 but not 9. Our families contain two already known families as special cases. We also discuss the inequivalence proof (by computation) which shows that these functions are new., Comment: 12 pages, submitted to Cryptography and Communications

A framework for linear-programming (LP) decoding of nonbinary linear codes over rings is developed. This framework facilitates linear-programming based reception for coded modulation systems which use direct modulation mapping of coded symbols. It is proved that the resulting LP decoder has the 'maximum-likelihood certificate' property. It is also shown that the decoder output is the lowest cost pseudocodeword. Equivalence between pseudocodewords of the linear program and pseudocodewords of graph covers is proved. It is also proved that if the modulator-channel combination satisfies a particular symmetry condition, the codeword error rate performance is independent of the transmitted codeword. Two alternative polytopes for use with linear-programming decoding are studied, and it is shown that for many classes of codes these polytopes yield a complexity advantage for decoding. These polytope representations lead to polynomial-time decoders for a wide variety of classical nonbinary linear codes. LP decoding performance is illustrated for the [11,6] ternary Golay code with ternary PSK modulation over AWGN, and in this case it is shown that the performance of the LP decoder is comparable to codeword-error-rate-optimum hard-decision based decoding. LP decoding is also simulated for medium-length ternary and quaternary LDPC codes with corresponding PSK modulations over AWGN., Comment: To appear in the IEEE Transactions on Information Theory. 54 pages, 5 figures