Euclidean and Hermitian LCD MDS codes

Linear codes with complementary duals (abbreviated LCD) are linear codes whose intersection with their dual is trivial. When they are binary, they play an important role in armoring implementations against side-channel attacks and fault injection attacks. Non-binary LCD codes in characteristic 2 can be transformed into binary LCD codes by expansion. On the other hand, being optimal codes, maximum distance separable codes (abbreviated MDS) are of much interest from many viewpoints due to their theoretical and practical properties. However, little work has been done on LCD MDS codes. In particular, determining the existence of q-ary [n, k] LCD MDS codes for various lengths n and dimensions k is a basic and interesting problem. In this paper, we firstly study the problem of the existence of q-ary [n, k] LCD MDS codes and solve it for the Euclidean case. More specifically, we show that for \(q>3\) there exists a q-ary [n, k] Euclidean LCD MDS code, where \(0\le k \le n\le q+1\), or, \(q=2^{m}\), \(n=q+2\) and \(k= 3 \text { or } q-1\). Secondly, we investigate several constructions of new Euclidean and Hermitian LCD MDS codes. Our main techniques in constructing Euclidean and Hermitian LCD MDS codes use some linear codes with small dimension or codimension, self-orthogonal codes and generalized Reed-Solomon codes.     

On deep holes of standard Reed-Solomon codes

Determining deep holes is an important open problem in decoding Reed-Solomon codes. It is well known that the received word is trivially a deep hole if the degree of its Lagrange interpolation polynomial equals the dimension of the Reed-Solomon code. For the standard Reed-Solomon codes [p-1, k]p with p a prime, Cheng and Murray conjectured in 2007 that there is no other deep holes except the trivial ones. In this paper, we show that this conjecture is not true. In fact, we find a new class of deep holes for standard Reed-Solomon codes [q-1, k]q with q a power of the prime p. Let q≥4 and 2≤k≤q-2. We show that the received word u is a deep hole if its Lagrange interpolation polynomial is the sum of monomial of degree q-2 and a polynomial of degree at most k-1. So there are at least 2(q-1)qk deep holes if k q-3.     

Some constructions of linearly optimal group codes

We continue here the research on (quasi)group codes over (quasi)group rings. We give some constructions of [n,n-3,3]_q-codes over F_q for n=2q and n=3q. These codes are linearly optimal, i.e. have maximal dimension among linear codes having a given length and distance. Although codes with such parameters are known, our main results state that we can construct such codes as (left) group codes. In the paper we use a construction of Reed-Solomon codes as ideals of the group ring F_qG where G is an elementary abelian group of order q.     

New linear codes over GF(8)

Let [n, k, d; q]-codes be linear codes of length n, dimension k and minimum Hamming distance d over GF(q). Let d₈(n, k) be the maximum possible minimum Hamming distance of a linear [n, k, d; 8]-code for given values of n and k. In this paper, eighteen new linear codes over GF(8) are constructed which improve the table of d₈(n, k) by Brouwer.     

广义Reed-Solomon 码的深洞

深洞在广义Reed-Solomon 码的译码中发挥重要的作用. 最近, Wu 和Hong 通过循环码对于标准Reed-Solomon 码发现了一类新的深洞. 本文给出一个简洁的方法, 对于一般广义Reed-Solomon 码给出新的一类深洞. 特别地, 对于标准Reed-Solomon 码, 我们得到了Wu 和Hong 给出的深洞. 对于广义Reed-Solomon 码GRS_k(F_q,D), Li 和Wan 研究和刻画了k+1 次多项式定义的深洞, 并且指出这个问题归结为在有限域中的子集和问题. 在偶特征的情形下, 利用他们的方法, 我们对于一些特殊的Reed-Solomon 码得到了更多一类新的深洞. 此外, 我们研究扩展Reed-Solomon 码(即赋值集合为D=F_q) k+2 次多项式定义的深洞, 并且证明没有k+2次多项式定义的深洞.     

Latin hypercubes and MDS codes

Maximum distance separable (MDS) codes have special properties that give them excellent error correcting capabilities. Counting the number of q-ary MDS codes of length n and distance d, denoted by D_q(n,d)_MDS, is a very hard problem. This paper shows that for d=2, it amounts to counting the number of (n-1)-dimensional Latin hypercubes of order q. Thus, D_q(3,2)_MDS is the number of Latin squares of order q, which is known only for a few values of q. This paper proves constructively that D₃(n,2)_MDS=6·2^n-2.     

A Hamada type characterization of the classical geometric designs

The dimension of a combinatorial design ${{\mathcal D}}$ over a finite field F = GF(q) was defined in (Tonchev, Des Codes Cryptogr 17:121–128, 1999) as the minimum dimension of a linear code over F that contains the blocks of ${{\mathcal D}}$ as supports of nonzero codewords. There it was proved that, for any prime power q and any integer n ≥ 2, the dimension over F of a design ${{\mathcal D}}$ that has the same parameters as the complement of a classical point-hyperplane design PG _n-1(n, q) or AG _n-1(n, q) is greater than or equal to n + 1, with equality if and only if ${{\mathcal D}}$ is isomorphic to the complement of the classical design. It is the aim of the present paper to generalize this Hamada type characterization of the classical point-hyperplane designs in terms of associated codes over F = GF(q) to a characterization of all classical geometric designs PG _d (n, q), where 1 ≤ d ≤ n ? 1, in terms of associated codes defined over some extension field E?=?GF(q ^t ) of F. In the affine case, we conjecture an analogous result and reduce this to a purely geometric conjecture concerning the embedding of simple designs with the parameters of AG _d (n, q) into PG(n, q). We settle this problem in the affirmative and thus obtain a Hamada type characterization of AG _d (n, q) for d = 1 and for d > (n ? 2)/2.     

Maximum distance separable codes and arcs in projective spaces

Given any linear code C over a finite field GF(q) we show how C can be described in a transparent and geometrical way by using the associated Bruen-Silverman code.Then, specializing to the case of MDS codes we use our new approach to offer improvements to the main results currently available concerning MDS extensions of linear MDS codes. We also sharply limit the possibilities for constructing long non-linear MDS codes. Our proofs make use of the connection between the work of Rédei [L. Rédei, Lacunary Polynomials over Finite Fields, North-Holland, Amsterdam, 1973. Translated from the German by I. Földes. [18]] and the Rédei blocking sets that was first pointed out over thirty years ago in [A.A. Bruen, B. Levinger, A theorem on permutations of a finite field, Canad. J. Math. 25 (1973) 1060-1065]. The main results of this paper significantly strengthen those in [A. Blokhuis, A.A. Bruen, J.A. Thas, Arcs in PG(n,q), MDS-codes and three fundamental problems of B. Segre—Some extensions, Geom. Dedicata 35 (1-3) (1990) 1-11; A.A. Bruen, J.A. Thas, A.Blokhuis, On M.D.S. codes, arcs in PG(n,q) with q even, and a solution of three fundamental problems of B. Segre, Invent. Math. 92 (3) (1988) 441-459].     

Intersection of Isomorphic Linear Codes

Given an (n, k) linear code over GF(q), the intersection of with a codeπ( ), whereπS_n, is an (n, k₁) code, where max{0, 2k−n}k₁k. The intersection problem is to determine which integers in this range are attainable for a given code . We show that, depending on the structure of the generator matrix of the code, some of the values in this range are attainable. As a consequence we give a complete solution to the intersection problem for most of the interesting linear codes, e.g. cyclic codes, Reed–Muller codes, and most MDS codes.     

Classes of optical orthogonal codes from arcs in root subspaces

We present new constructions for (n,w,λ) optical orthogonal codes (OOC) using techniques from finite projective geometry. In one case codewords correspond to (q-1)-arcs contained in Baer subspaces (and, in general, kth-root subspaces) of a projective space. In the other construction, we use sublines isomorphic to PG(2,q) lying in a projective plane isomorphic to PG(2,q^k), k>1. Our construction yields for each λ>1 an infinite family of OOCs which, in many cases, are asymptotically optimal with respect to the Johnson bound.     

The nonexistence of ternary [105,6,68] and [230,6,152] codes

Let [n,k,d]_q-codes be linear codes of length n, dimension k and minimum Hamming distance d over GF(q). In this paper, the nonexistence of [105,6,68]₃ and [230,6,152]₃ codes is proved.     

On construction of involutory MDS matrices from Vandermonde Matrices in GF(2 q )

Due to their remarkable application in many branches of applied mathematics such as combinatorics, coding theory, and cryptography, Vandermonde matrices have received a great amount of attention. Maximum distance separable (MDS) codes introduce MDS matrices which not only have applications in coding theory but also are of great importance in the design of block ciphers. Lacan and Fimes introduce a method for the construction of an MDS matrix from two Vandermonde matrices in the finite field. In this paper, we first suggest a method that makes an involutory MDS matrix from the Vandermonde matrices. Then we propose another method for the construction of 2 ⁿ × 2 ⁿ Hadamard MDS matrices in the finite field GF(2 ^q ). In addition to introducing this method, we present a direct method for the inversion of a special class of 2 ⁿ ?× 2 ⁿ Vandermonde matrices.     

Non-orientable fundamental surfaces in lens spaces

We give a concrete example of an infinite sequence of (pn,qn)-lens spaces L(pn,qn) with natural triangulations T(pn,qn) with pn tetrahedra such that L(pn,qn) contains a certain non-orientable closed surface which is fundamental with respect to T(pn,qn) and of minimal crosscap number among all closed non-orientable surfaces in L(pn,qn) and has n−2 parallel sheets of normal disks of a quadrilateral type disjoint from the pair of core circles of L(pn,qn). Actually, we can set p₀=0, q₀=1, pk+1=3pk+2qk and qk+1=pk+qk.     

The non-existence of Griesmer codes with parameters close to codes of Belov type

Hill and Kolev give a large class of q-ary linear codes meeting the Griesmer bound, which are called codes of Belov type (Hill and Kolev, Chapman Hall/CRC Research Notes in Mathematics 403, pp. 127–152, 1999). In this article, we prove that there are no linear codes meeting the Griesmer bound for values of d close to those for codes of Belov type. So we conclude that the lower bounds of d of codes of Belov type are sharp. We give a large class of length optimal codes with n _q (k, d) = g _q (k, d) + 1.     

Codes and Anticodes in the Grassman Graph

Perfect codes and optimal anticodes in the Grassman graph G_q(n, k) are examined. It is shown that the vertices of the Grassman graph cannot be partitioned into optimal anticodes, with a possible exception when n=2k. We further examine properties of diameter perfect codes in the graph. These codes are known to be similar to Steiner systems. We discuss the connection between these systems and “real” Steiner systems.     

On the diophantine equation y2 = 4qn + 4q + 1

It is known that a certain class of [n, k] codes over GF(q) is related to the diophantine equation y² = 4qⁿ + 4q + 1 (1). In Parts I and II of this paper, two different, and in a certain sense complementary, methods of approach to (1) are discussed and some results concerning (1) are given as applications. A typical result is that the only solutions to (1) are (y, n) = (5, 1), (7, 2), (11, 3) when q = 3 and (y, n) = (2q + 1, 2) when q = 3^f, f >- 2.     

A Note on MDS Codes, <Emphasis Type="Italic">n</Emphasis>-Arcs and Complete Designs

A generalized incidence matrix of a design over GF(q) is any matrix obtained from the (0, 1)-incidence matrix by replacing ones with nonzero elements from GF(q). The dimension d _q of a design D over GF(q) is defined as the minimum value of the q-rank of a generalized incidence matrix of D. It is proved that the dimension d _q of the complete design on n points having as blocks all w-subsets, is greater that or equal to n ? w + 1, and the equality d _q = n ? w + 1 holds if and only if there exists an [n, n ? w + 1, w] MDS code over GF(q), or equivalently, an n-arc in PG(w ? 2, q).     

Equalities on the number of conjugacy classes of the Sylow p-subgroups of GL(n,q)

We denote by Gn the group of the upper unitriangular matrices over F_q, the finite field with q = p^t elements, and r(G_n) the number of conjugacy classes of G_n. In this paper, we obtain the value of r(G_n) modulo (q² -1)(q -1). We prove the following equalities     

On the Existence of Absolutely Simple Abelian Varieties of a Given Dimension over an Arbitrary Field

We prove that for every field k and every positive integer n there exists an absolutely simple n-dimensional abelian variety over k. We also prove an asymptotic result for finite fields: For every finite field k and positive integer n, we let S(k, n) denote the fraction of the isogeny classes of n-dimensional abelian varieties over k that consist of absolutely simple ordinary abelian varieties. Then for every n we have S(F_q, n)→1 as q→∞ over the prime powers.     

The Erdös-Kac theorem for additive arithmetical semigroups

We show that the Erdös-Kac theorem for additive arithmetical semigroups can be proved under the condition that the counting function of elements has the asymptotics G(n) = q ⁿ (A + O(1/(lnn)^k) as n → ∞ with A > 0, q > 1, and arbitrary k ∈ ? and that P(n) = O(q ⁿ /n) for the number of prime elements of degree n. This improves a result of Zhang.