On puncturing of codes from Norm–Trace curves

Constructing new codes from existing ones by puncturing is in this paper viewed in the context of order domains R where puncturing can be seen as redefinition of the evaluation map $\varphi :R\to {\mathbb{F}}_q^n$. The order domains considered here are of the form $R=\mathbb{F}[x_1,x_2,\dots ,x_m]/I$ where redefining $\varphi$ can be done by adding one or more polynomials to the basis of the defining ideal I to form a new ideal J in such a way that the number of points in the variety $\mathbb{V}(I)$ is reduced by t to form $\mathbb{V}(J)$ and puncturing in t coordinates is achieved. An explicit construction of such polynomials is given in the case of codes defined by Norm–Trace curves and examples are given of both evaluation codes and dual codes. Finally, it is demonstrated that the improvement in minimum distance can be significant when compared to the lower bound obtained by ordinary puncturing.     

On the Geil–Matsumoto bound and the length of AG codes

The Geil–Matsumoto bound conditions the number of rational places of a function field in terms of the Weierstrass semigroup of any of the places. Lewittes’ bound preceded the Geil–Matsumoto bound and it only considers the smallest generator of the numerical semigroup. It can be derived from the Geil–Matsumoto bound and so it is weaker. However, for general semigroups the Geil–Matsumoto bound does not have a closed formula and it may be hard to compute, while Lewittes’ bound is very simple. We give a closed formula for the Geil–Matsumoto bound for the case when the Weierstrass semigroup has two generators. We first find a solution to the membership problem for semigroups generated by two integers and then apply it to find the above formula. We also study the semigroups for which Lewittes’s bound and the Geil–Matsumoto bound coincide. We finally investigate on some simplifications for the computation of the Geil–Matsumoto bound.     

On low weight codewords of generalized affine and projective Reed–Muller codes

We propose new results on low weight codewords of affine and projective generalized Reed–Muller (GRM) codes. In the affine case we prove that if the cardinality of the ground field is large compared to the degree of the code, the low weight codewords are products of affine functions. Then, without this assumption on the cardinality of the field, we study codewords associated to an irreducible but not absolutely irreducible polynomial, and prove that they cannot be second, third or fourth weight depending on the hypothesis. In the projective case the second distance of GRM codes is estimated, namely a lower bound and an upper bound on this weight are given.     

Weighted Reed–Muller codes revisited

We consider weighted Reed–Muller codes over point ensemble S ₁ × · · · × S _m where S _i needs not be of the same size as S _j . For m = 2 we determine optimal weights and analyze in detail what is the impact of the ratio |S ₁|/|S ₂| on the minimum distance. In conclusion the weighted Reed–Muller code construction is much better than its reputation. For a class of affine variety codes that contains the weighted Reed–Muller codes we then present two list decoding algorithms. With a small modification one of these algorithms is able to correct up to 31 errors of the [49,11,28] Joyner code.     

On the Kählerization of the Moduli Space of Bohr–Sommerfeld Lagrangian Submanifolds

Mathematical Notes -     

Extensions between Cohen–Macaulay modules of Grassmannian cluster categories

In this paper we study extensions between Cohen–Macaulay modules for algebras arising in the categorifications of Grassmannian cluster algebras. We prove that rank 1 modules are periodic, and we give explicit formulas for the computation of the period based solely on the rim of the rank 1 module in question. We determine \(\mathrm{Ext}^i(L_I, L_J)\) for arbitrary rank 1 modules \(L_I\) and \(L_J\). An explicit combinatorial algorithm is given for the computation of \(\mathrm{Ext}^i(L_I, L_J)\) when i is odd, and when i even, we show that \(\mathrm{Ext}^i(L_I, L_J)\) is cyclic over the centre, and we give an explicit formula for its computation. At the end of the paper we give a vanishing condition of \(\mathrm{Ext}^i(L_I, L_J)\) for any \(i>0\).     

Feng–Rao decoding of primary codes

We show that the Feng–Rao bound for dual codes and a similar bound by Andersen and Geil (2008) [1] for primary codes are consequences of each other. This implies that the Feng–Rao decoding algorithm can be applied to decode primary codes up to half their designed minimum distance. The technique applies to any linear code for which information on well-behaving pairs is available. Consequently we are able to decode efficiently a large class of codes for which no non-trivial decoding algorithm was previously known. Among those are important families of multivariate polynomial codes. Matsumoto and Miura (2000) [30] (see also Beelen and Høholdt, 2008 [3]) derived from the Feng–Rao bound a bound for primary one-point algebraic geometric codes and showed how to decode up to what is guaranteed by their bound. The exposition in Matsumoto and Miura (2000) [30] requires the use of differentials which was not needed in Andersen and Geil (2008) [1]. Nevertheless we demonstrate a very strong connection between Matsumoto and Miuraʼs bound and Andersen and Geilʼs bound when applied to primary one-point algebraic geometric codes.     

On Classes of Generalized Convex Functions, Gordan–Farkas Type Theorems, and Lagrangian Duality

In this paper, we introduce several classes of generalized convex functions already discussed in the literature and show the relation between these classes. Moreover, a Gordan–Farkas type theorem is proved for all these classes and it is shown how these theorems can be used to verify strong Lagrangian duality results in finite-dimensional optimization.     

Peterson–Gorenstein–Zierler algorithm for skew RS codes

We design a non-commutative version of the Peterson–Gorenstein–Zierler decoding algorithm for a class of codes that we call skew RS codes. These codes are left ideals of a quotient of a skew polynomial ring, which endow them of a sort of non-commutative cyclic structure. Since we work over an arbitrary field, our techniques may be applied both to linear block codes and convolutional codes. In particular, our decoding algorithm applies for block codes beyond the classical cyclic case.     

Minimal codewords in Reed–Muller codes

Minimal codewords were introduced by Massey (Proceedings of the 6th Joint Swedish-Russian International Workshop on Information Theory, pp 276–279, 1993) for cryptographical purposes. They are used in particular secret sharing schemes, to model the access structures. We study minimal codewords of weight smaller than 3 · 2 ^m−r in binary Reed–Muller codes RM(r, m) and translate our problem into a geometrical one, using a classification result of Kasami and Tokura (IEEE Trans Inf Theory 16:752–759, 1970) and Kasami et al. (Inf Control 30(4):380–395, 1976) on Boolean functions. In this geometrical setting, we calculate numbers of non-minimal codewords. So we obtain the number of minimal codewords in the cases where we have information about the weight distribution of the code RM(r, m). The presented results improve previous results obtained theoretically by Borissov et al. (Discrete Appl Math 128(1), 65–74, 2003), and computer aided results of Borissov and Manev (Serdica Math J 30(2-3), 303–324, 2004). This paper is in fact an extended abstract. Full proofs can be found on the arXiv.     

Association schemes related to Delsarte–Goethals codes

In this paper, we construct an infinite series of 9-class association schemes from a refinement of the partition of Delsarte–Goethals codes by their Lee weights. The explicit expressions of the dual schemes are determined through direct manipulations of complicated exponential sums. As a byproduct, another three infinite families of association schemes are also obtained as fusion schemes and quotient schemes.     

Hasse–Weil bound for additive cyclic codes

We obtain a bound on the minimum distance of additive cyclic codes via the number of rational points on certain algebraic curves over finite fields. This is an extension of the analogous bound in the case of classical cyclic codes. Our result is the only general bound on such codes aside from Bierbrauer’s BCH bound. We compare our bounds’ performance against the BCH bound for additive cyclic codes in a special case and provide examples where it yields better results.     

On Hamiltonian stationary Lagrangian spheres in non-Einstein K?hler surfaces

Hamiltonian stationary Lagrangian spheres in K?hler-Einstein surfaces are minimal. We prove that in the family of non-Einstein K?hler surfaces given by the product Σ₁?×?Σ₂ of two complete orientable Riemannian surfaces of different constant Gauss curvatures, there is only a (non minimal) Hamiltonian stationary Lagrangian sphere. This example, defined when the surfaces Σ₁ and Σ₂ are spheres, is unstable.