# American Institute of Mathematical Sciences

ISSN:
1930-5346

eISSN:
1930-5338

All Issues

## Advances in Mathematics of Communications

May 2011 , Volume 5 , Issue 2

A special issue
ALCOMA'10

Select all articles

Export/Reference:

2011, 5(2): i-ii doi: 10.3934/amc.2011.5.2i +[Abstract](1410) +[PDF](127.0KB)
Abstract:
The present issue of the Advances in Mathematics of Communications has been dedicated to the conference

ALCOMA'10

(Algebraic Combinatorics and Applications, Designs and Codes)

which took place April 11-18, 2010 in the picturesque village of Thurnau near Bay\-reuth, Germany.
The purpose of this meeting was to bring together mathematicians from around the world to exchange recent results in all areas of Discrete Mathematics and Mathematics of Communications based on algebraic methods. Special emphasis was placed on the constructive theory of finite structures, in particular on combinatorial designs and codes. The conference was the third of its kind, after the inaugural meeting ALCOMA'99 in Gößweinstein, which was later followed by ALCOMA'05 at the same venue.

2011, 5(2): 149-156 doi: 10.3934/amc.2011.5.149 +[Abstract](1436) +[PDF](319.3KB)
Abstract:
The Krotov combining construction of perfect $1$-error-correcting binary codes from 2000 and a theorem of Heden saying that every non-full-rank perfect $1$-error-correcting binary code can be constructed by this combining construction is generalized to the $q$-ary case. Simply speaking, every non-full-rank perfect code $C$ is the union of a well-defined family of $\bar\mu$-components K$\bar\mu$, where $\bar\mu$ belongs to an “outer” perfect code C*, and these components are at distance three from each other. Components from distinct codes can thus freely be combined to obtain new perfect codes. The Phelps general product construction of perfect binary code from 1984 is generalized to obtain $\bar\mu$-components, and new lower bounds on the number of perfect $1$-error-correcting $q$-ary codes are presented.
2011, 5(2): 157-160 doi: 10.3934/amc.2011.5.157 +[Abstract](1208) +[PDF](284.4KB)
Abstract:
We give a geometric proof of the upper bound of q2n+1$+1$ on the size of partial spreads in the polar space $H(4n+1,$q2$)$. This bound is tight and has already been proved in an algebraic way. Our alternative proof also yields a characterization of the partial spreads of maximum size in $H(4n+1,$q2$)$.
2011, 5(2): 161-176 doi: 10.3934/amc.2011.5.161 +[Abstract](1604) +[PDF](447.7KB)
Abstract:
The $q$-analogs of covering designs, Steiner systems, and Turán designs are studied. It is shown that $q$-covering designs and $q$-Turán designs are dual notions. A strong necessary condition for the existence of Steiner structures (the $q$-analogs of Steiner systems) over $\mathbb F$2 is given. No Steiner structures of strength $2$ or more are currently known, and our condition shows that their existence would imply the existence of new Steiner systems of strength $3$. The exact values of the $q$-covering numbers $\mathcal C$q$(n,k,1)$ and $\mathcal C$q$(n,n-1,r)$ are determined for all $q,n,k,r$. Furthermore, recursive upper and lower bounds on the size of general $q$-covering designs and $q$-Turán designs are presented. Finally, it is proved that $\mathcal C$2$(5,3,2) = 27$ and $\mathcal C$2$(7,3,2) \leq 399$. Tables of upper and lower bounds on $\mathcal C$2$(n,k,r)$ are given for all $n \leq 8$.
2011, 5(2): 177-189 doi: 10.3934/amc.2011.5.177 +[Abstract](1320) +[PDF](349.6KB)
Abstract:
Constant dimension codes, with a prescribed minimum distance, have found recently an application in network coding. All the codewords in such a code are subspaces of $\mathbb F$qn with a given dimension. A computer search for large constant dimension codes is usually inefficient since the search space domain is extremely large. Even so, we found that some constant dimension lexicodes are larger than other known codes. We show how to make the computer search more efficient. In this context we present a formula for the computation of the distance between two subspaces, not necessarily of the same dimension.
2011, 5(2): 191-198 doi: 10.3934/amc.2011.5.191 +[Abstract](1312) +[PDF](291.5KB)
Abstract:
In the present work we study a class of singly-even self-dual codes with the special property that the minimum weight of their shadow is 1. Some of these codes support 1 and 2-designs. Using them, we describe two types of schemes based on codes, the first is an one-part secret sharing scheme and the second is a two-part sharing scheme. Similar schemes can be constructed from self-dual codes that support 3-designs.
2011, 5(2): 199-208 doi: 10.3934/amc.2011.5.199 +[Abstract](1482) +[PDF](272.3KB)
Abstract:
The main aim of this paper is to construct symmetric designs with trivial automorphism groups. Being aware of the fact that an exhaustive search for parameters $(36,15,6)$ and $(41,16,6)$ is still impossible, we assume that these designs admit a tactical decomposition which would correspond to an orbit structure achieved under an action of an automorphism of order $3$. This constraint proves to be fruitful and allows us to classify simultaneously those symmetric designs with mentioned parameters which admit an automorphism of order $3$ as well as to construct new designs with a trivial automorphism group.
2011, 5(2): 209-223 doi: 10.3934/amc.2011.5.209 +[Abstract](1455) +[PDF](373.2KB)
Abstract:
It is known that $42$ is the largest size of a $6$-arc in the Desarguesian projective plane of order $8$. In this paper, we classify these $(42,6)_8$ arcs. Equivalently, we classify the smallest $3$-fold blocking sets in PG$(2,8)$, which have size $31$.
2011, 5(2): 225-232 doi: 10.3934/amc.2011.5.225 +[Abstract](1537) +[PDF](375.5KB)
Abstract:
Network codes are sets of subspaces of a finite vectorspace over a finite field. Recently, this class of codes has found application in the error correction of message transmission within networks. Furthermore, binary codes can be represented as sets of subsets of a finite set. Hence, both kinds of codes can be regarded as substructures of lattices — in the first case it is the linear lattice and in the second case it is the power set lattice. This observation leads us to a more general investigation of similarities of both theories by means of lattice theory. In this paper we first examine general results of lattices in order to comprise basic considerations of network coding and binary vector coding theory. Afterwards we consider the issue of finding complements of subspaces.
2011, 5(2): 233-244 doi: 10.3934/amc.2011.5.233 +[Abstract](1734) +[PDF](404.9KB)
Abstract:
It has been widely known that complete decoding for binary linear codes can be regarded as a linear integer programming problem with binary arithmetic conditions. Conti and Traverso [9] have proposed an algorithm which uses Gröbner bases to solve integer programming with ordinary integer arithmetic conditions. Ikegami and Kaji [12] extended the Conti-Traverso algorithm to solve integer programming with modulo arithmetic conditions. It is natural to consider for those problems the Graver basis associated to them which turns out to be the minimal cycles of the matroid associated to the code, i.e. minimal support codewords in the binary case and its geometry. This provides us a universal test set for the programs considered.
2011, 5(2): 245-266 doi: 10.3934/amc.2011.5.245 +[Abstract](1870) +[PDF](509.6KB)
Abstract:
Two linear codes $C, C' \leq \mathbb Z$4n are equivalent if there is a permutation $\pi \in S_n$ of the coordinates and a vector $\varphi \in \{1,3\}^n$ of column multiplications such that $(\varphi; \pi) C = C'$. This generalizes the notion of code equivalence of linear codes over finite fields.
In a previous paper, the author has described an algorithm to compute the canonical form of a linear code over a finite field. In the present paper, an algorithm is presented to compute the canonical form as well as the automorphism group of a linear code over $\mathbb Z$4. This solves the isomorphism problem for $\mathbb Z$4-linear codes. An efficient implementation of this algorithm is described and some results on the classification of linear codes over $\mathbb Z$4 for small parameters are discussed.
2011, 5(2): 267-274 doi: 10.3934/amc.2011.5.267 +[Abstract](1556) +[PDF](283.8KB)
Abstract:
The decoding error probability of a code $C$ measures the quality of performance when $C$ is used for error correction in data transmission. In this note we compare different types of codes with regard to the decoding error probability.
2011, 5(2): 275-286 doi: 10.3934/amc.2011.5.275 +[Abstract](1784) +[PDF](356.1KB)
Abstract:
In this paper we present a new non-free $\mathbb Z$4-linear code of length $29$ and size $128$ whose minimum Lee distance is $28$. Its Gray image is a nonlinear binary code with parameters $(58,2^7,28)$, having twice as many codewords as the biggest linear binary codes of equal length and minimum distance. The code also improves the known lower bound on the maximal size of binary block codes of length $58$ and minimum distance $28$.
Originally the code was found by a heuristic computer search. We give a geometric construction based on a hyperoval in the projective Hjelmslev plane over $\mathbb Z$4 which allows an easy computation of the symmetrized weight enumerator and the automorphism group. Furthermore, a generalization of this construction to all Galois rings of characteristic $4$ is discussed.
2011, 5(2): 287-301 doi: 10.3934/amc.2011.5.287 +[Abstract](1624) +[PDF](427.0KB)
Abstract:
It is shown that the maximal size of a $2$-arc in the projective Hjelmslev plane over $\mathbb Z$25 is $21$, and the $(21,2)$-arc is unique up to isomorphism. Furthermore, all maximal $(20,2)$-arcs in the affine Hjelmslev plane over $\mathbb Z$25 are classified up to isomorphism.
2011, 5(2): 303-308 doi: 10.3934/amc.2011.5.303 +[Abstract](1868) +[PDF](251.1KB)
Abstract:
In this short note we present a simple combinatorial trick which can be effectively applied to show the non-existence of sharply transitive sets of permutations in certain finite permutation groups.
2011, 5(2): 309-315 doi: 10.3934/amc.2011.5.309 +[Abstract](1294) +[PDF](301.5KB)
Abstract:
One of the main goals of design theory is to classify, characterize and count various combinatorial objects with some prescribed properties. In most cases, however, one quickly encounters a combinatorial explosion and even if the complete enumeration of the objects is possible, there is no apparent way how to study them in details, store them efficiently, or generate a particular one rapidly. In this paper we propose a novel method to deal with these difficulties, and illustrate it by presenting the classification of quaternary complex Hadamard matrices up to order $8$. The obtained matrices are members of only a handful of parametric families, and each inequivalent matrix, up to transposition, can be identified through its fingerprint.
2011, 5(2): 317-331 doi: 10.3934/amc.2011.5.317 +[Abstract](1425) +[PDF](392.7KB)
Abstract:
In this paper, we prove the nonexistence of arcs with parameters $(398,101)$, $(464,117)$, and $(467,118)$ in PG$(4,4)$. The proof relies on the geometric characterization of $(117,30)$- and $(118,30)$-arcs in PG$(3,4)$. This settles the problem of finding the exact value of $n_4(5,d)$ for eight values of $d$: $297,298,347,348,349,...,352$.
2011, 5(2): 333-337 doi: 10.3934/amc.2011.5.333 +[Abstract](1357) +[PDF](263.3KB)
Abstract:
The study of minimal codewords in linear codes was motivated by Massey who described how minimal codewords of a linear code define access structures for secret sharing schemes. As a consequence of his article, Borissov, Manev, and Nikova initiated the study of minimal codewords in the binary Reed-Muller codes. They counted the number of non-minimal codewords of weight $2d$ in the binary Reed-Muller codes RM$(r,m)$, and also gave results on the non-minimality of codewords of large weight in the binary Reed-Muller codes RM$(r,m)$. The results of Borissov, Manev, and Nikova regarding the counting of the number of non-minimal codewords of small weight in RM$(r,m)$ were improved by Schillewaert, Storme, and Thas who counted the number of non-minimal codewords of weight smaller than $3d$ in RM$(r,m)$. This article now presents new results on the non-minimality of large weight codewords in RM$(r,m)$.
2011, 5(2): 339-350 doi: 10.3934/amc.2011.5.339 +[Abstract](1314) +[PDF](395.2KB)
Abstract:
The alternating group $A_8$, acts as a primitive rank-3 group of degree $35$ on the set of lines of $V_4(2)$ with line stabilizer isomorphic to $2^4:(S_3 \times S_3)$ and orbits of lengths 1, 16 and 18 respectively. This action defines the unique strongly regular $(35, 16, 6, 8)$ graph. The paper examines the binary (resp. ternary) codes spanned by the rows of this graph, and its complement. We establish some properties of the codes and use the geometry of the designs and graphs to give an account on the nature of some classes of codewords, in particular those of minimum weight. Further, we show that the codes with parameters $[35, 28, 4]_2,[35, 6, 16]_2,[35, 29, 3]_2,[28, 7, 12]_2,[28, 21,4]_2, [36, 7, 16]_2, [36,29,4]_2$ and $[64, 56, 4]_2$ are all optimal. In addition, we show that the codes with parameters $[35, 13, 12]_3, [35, 22, 5]_3,[35, 14, 11]_3, [35, 21, 6]_3$ are all near-optimal for the given length and dimension.
2011, 5(2): 351-371 doi: 10.3934/amc.2011.5.351 +[Abstract](1374) +[PDF](547.3KB)
Abstract:
It is proved that a numerical semigroup can be associated to the triangle-free $(r,k)$-configurations, and some results on existence are deduced. For example it is proved that for any $r,k\geq 2$ there exists infinitely many $(r,k)$-configurations. Most proofs are given from a graph theoretical point of view, in the sense that the configurations are represented by their incidence graphs. An application to private information retrieval is described.
2011, 5(2): 373-394 doi: 10.3934/amc.2011.5.373 +[Abstract](1470) +[PDF](518.6KB)
Abstract:
We examine the $p$-ary codes, for any prime $p$, that can be obtained from incidence matrices and line graphs of the Hamming graphs, $H^k(n,m)$, for $k \geq 2$. For $m=2$, we obtain the main parameters of the codes from the incidence matrices, including the minimum weight and the nature of the minimum words. We show that all the codes can be used for full permutation decoding.
2011, 5(2): 395-406 doi: 10.3934/amc.2011.5.395 +[Abstract](1533) +[PDF](400.1KB)
Abstract:
Let $R>S$ be finite Frobenius rings for which there exists a trace map $T:$ S$R \rightarrow$S$R$. Let $C$f,s$:=\{x \mapsto T(\alpha x + \beta f(x)) : \alpha, \beta \in R \}$. $C$f,s 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$f,s can be computed. In particular, we give constructions of codes over integer modular rings and commutative local Frobenius that have small spectra.
2011, 5(2): 407-416 doi: 10.3934/amc.2011.5.407 +[Abstract](1767) +[PDF](355.6KB)
Abstract:
Let $V$ be an $n$-dimensional vector space over the finite field $\mathbb F$q and $T$ a linear operator on $V$. For each $k\in\{1,\ldots,n\}$ we determine the number of $k$-dimensional $T$-invariant subspaces of $V$. Finally, this method is applied for the enumeration of all monomially nonisometric linear $(n,k)$-codes over $\mathbb F$q.

2018  Impact Factor: 0.879