On the order bound of one-point algebraic geometry codes

Let S={s_i}_i∈N⊆N be a numerical semigroup. For each i∈N, let ν(s_i) denote the number of pairs (s_i−s_j,s_j)∈S²: it is well-known that there exists an integer m such that the sequence {ν(s_i)}_i∈N is non-decreasing for i>m. The problem of finding m is solved only in special cases. By way of a suitable parameter t, we improve the known bounds for m and in several cases we determine m explicitly. In particular we give the value of m when the Cohen-Macaulay type of the semigroup is three or when the multiplicity is less than or equal to six. When S is the Weierstrass semigroup of a family {C_i}_i∈N of one-point algebraic geometry codes, these results give better estimates for the order bound on the minimum distance of the codes {C_i}.     

Testing algebraic geometric codes

Property testing was initially studied from various motivations in 1990’s. A code C  GF (r)n is locally testable if there is a randomized algorithm which can distinguish with high possibility the codewords from a vector essentially far from the code by only accessing a very small (typically constant) number of the vector’s coordinates. The problem of testing codes was firstly studied by Blum, Luby and Rubinfeld and closely related to probabilistically checkable proofs (PCPs). How to characterize locally te...     

Coset bounds for algebraic geometric codes

We develop new coset bounds for algebraic geometric codes. The bounds have a natural interpretation as an adversary threshold for algebraic geometric secret sharing schemes and lead to improved bounds for the minimum distance of an AG code. Our bounds improve both floor bounds and order bounds and provide for the first time a connection between the two types of bounds.     

Distance bounds for algebraic geometric codes

Various methods have been used to obtain improvements of the Goppa lower bound for the minimum distance of an algebraic geometric code. The main methods divide into two categories, and all but a few of the known bounds are special cases of either the Lundell-McCullough floor bound or the Beelen order bound. The exceptions are recent improvements of the floor bound by Güneri, Stichtenoth, and Taskin, and by Duursma and Park, and of the order bound by Duursma and Park, and by Duursma and Kirov. In this paper, we provide short proofs for all floor bounds and most order bounds in the setting of the van Lint and Wilson AB method. Moreover, we formulate unifying theorems for order bounds and formulate the DP and DK order bounds as natural but different generalizations of the Feng-Rao bound for one-point codes.     

Exponents of polar codes using algebraic geometric code kernels

Reed–Solomon and BCH codes were considered as kernels of polar codes by Mori and Tanaka (IEEE Information Theory Workshop, 2010, pp 1–5) and Korada et al. (IEEE Trans Inform Theory 56(12):6253–6264, 2010) to create polar codes with large exponents. Mori and Tanaka showed that Reed–Solomon codes over the finite field \(\mathbb {F}_q\) with \(q\) elements give the best possible exponent among all codes of length \(l \le q\) . They also stated that a Hermitian code over \(\mathbb {F}_{2^r}\) with \(r \ge 4\) , a simple algebraic geometric code, gives a larger exponent than the Reed–Solomon matrix over the same field. In this paper, we expand on these ideas by employing more general algebraic geometric (AG) codes to produce kernels of polar codes. Lower bounds on the exponents are given for kernels from general AG codes, Hermitian codes, and Suzuki codes. We demonstrate that both Hermitian and Suzuki kernels have larger exponents than Reed–Solomon codes over the same field, for \(q \ge 3\) ; however, the larger exponents are at the expense of larger kernel matrices. Comparing kernels of the same size, though over different fields, we see that Reed–Solomon kernels have larger exponents than both Hermitian and Suzuki kernels. These results indicate a tradeoff between the exponent, kernel matrix size, and field size.     

A generalized floor bound for the minimum distance of geometric Goppa codes

We prove a new bound for the minimum distance of geometric Goppa codes that generalizes two previous improved bounds. We include examples of the bound applied to one- and two-point codes over certain Suzuki and Hermitian curves.     

On the general excess bound for binary codes with covering radius one

Let K(n,1)$K(n,1)$ denote the minimal cardinality of a binary code of length n$n$ and covering radius one. Fundamental for the theory of lower bounds for K(n,1)$K(n,1)$ is the covering excess method introduced by Johnson and van Wee. Let _δi${\delta }_i$ denote the covering excess on a sphere of radius i$i$, 0≤i≤n$0\le i\le n$. Generalizing an earlier result of van Wee, Habsieger and Honkala showed _δp−1≥p−1${\delta }_{p-1}\ge p-1$ whenever n≡−1$n\equiv -1$ (mod p$p$) for an odd prime p$p$ and _δ0=_δ1=?=_δp−2=0${\delta }_0={\delta }_1=?={\delta }_{p-2}=0$ holds. In the present paper we give the new estimation _δp−1≥(p−2)p−1${\delta }_{p-1}\ge (p-2)p-1$ instead. This answers a question of Habsieger and yields a “general improvement of the general excess bound” for binary codes with covering radius one. The proof uses a classification theorem for certain subset systems as well as new congruence properties for the δ$\delta$-function, which were conjectured by Habsieger.     

Improving the high order nonlinearity lower bound for Boolean functions with given algebraic immunity

Algebraic immunity is a recently introduced cryptographic parameter for Boolean functions used in stream ciphers. If pAI(f) and pAI(f⊕1) are the minimum degree of all annihilators of f and f⊕1 respectively, the algebraic immunity AI(f) is defined as the minimum of the two values. Several relations between the new parameter and old ones, like the degree, the r-th order nonlinearity and the weight of the Boolean function, have been proposed over the last few years.In this paper, we improve the existing lower bounds of the r-th order nonlinearity of a Boolean function f with given algebraic immunity. More precisely, we introduce the notion of complementary algebraic immunity defined as the maximum of pAI(f) and pAI(f⊕1). The value of can be computed as part of the calculation of AI(f), with no extra computational cost. We show that by taking advantage of all the available information from the computation of AI(f), that is both AI(f) and , the bound is tighter than all known lower bounds, where only the algebraic immunity AI(f) is used.     

Twisting geometric codes

The aim of this paper is to explain how, starting from a Goppa code C(X,G,P₁,…,P_n) and a cyclic covering π:Y→X of degree m, one can twist the initial code to another one C(X,G+D_χ,P₁,…,P_n), where D_χ is a non-principal degree 0 divisor on X associated to a character χ of Gal(Y/X), in the hope that ℓ_X(G+D_χ)>ℓ_X(G). We give, using a MAGMA program, several examples where this occurs, and where both the initial and twisted codes have same minimum distance, so that initial codes have been improved.     

The algebraic degree of geometric optimization problems

In this paper we apply Galois methods to certain fundamentalgeometric optimization problems whose exact computational complexity has been an open problem for a long time. In particular we show that the classic Weber problem, along with theline-restricted Weber problem and itsthree-dimensional version are in general not solvable by radicals over the field of rationals. One direct consequence of these results is that for these geometric optimization problems there existsno exact algorithm under models of computation where the root of an algebraic equation is obtained using arithmetic operations and the extraction ofkth roots. This leaves only numerical or symbolic approximations to the solutions, where the complexity of the approximations is shown to be primarily a function of the algebraic degree of the optimum solution point.     

The algebraic and geometric classification of Zinbiel algebras

This paper is devoted to the complete algebraic and geometric classification of complex 5-dimensional Zinbiel algebras. In particular, we proved that the variety of complex 5-dimensional Zinbiel algebras has dimension 24, it is defined by 16 irreducible components and it has 11 rigid algebras.     

The linear programming bound for codes over finite Frobenius rings

In traditional algebraic coding theory the linear-programming bound is one of the most powerful and restrictive bounds for the existence of both linear and non-linear codes. This article develops a linear-programming bound for block codes on finite Frobenius rings. An erratum to this article can be found at     

The Tietäväinen bound for spherical codes

It is shown that an analog of the Tietäväinen bound for binary codes holds also for spherical codes.     

A symmetric Roos bound for linear codes

The van Lint-Wilson AB-method yields a short proof of the Roos bound for the minimum distance of a cyclic code. We use the AB-method to obtain a different bound for the weights of a linear code. In contrast to the Roos bound, the role of the codes A and B in our bound is symmetric. We use the bound to prove the actual minimum distance for a class of dual BCH codes of length q²−1 over Fq. We give cyclic codes [63,38,16] and [65,40,16] over F₈ that are better than the known [63,38,15] and [65,40,15] codes.     

The algebraic and geometric classification of nilpotent terminal algebras

We give algebraic and geometric classifications of 4-dimensional complex nilpotent terminal algebras. Specifically, we find that, up to isomorphism, there are 41 one-parameter families of 4-dimensional nilpotent terminal (non-Leibniz) algebras, 18 two-parameter families of 4-dimensional nilpotent terminal (non-Leibniz) algebras, 2 three-parameter families of 4-dimensional nilpotent terminal (non-Leibniz) algebras, complemented by 21 additional isomorphism classes (see Theorem 13). The corresponding geometric variety has dimension 17 and decomposes into 3 irreducible components determined by the Zariski closures of a one-parameter family of algebras, a two-parameter family of algebras and a three-parameter family of algebras (see Theorem 15). In particular, there are no rigid 4-dimensional complex nilpotent terminal algebras.     

Near-MDS codes arising from algebraic curves

Every elliptic quartic Γ₄ of PG(3,q) with nGF(q)-rational points provides a near-MDS code C of length n and dimension 4 such that the collineation group of Γ₄ is isomorphic to the automorphism group of C. In this paper we assume that GF(q) has characteristic p>3. We classify the linear collineation groups of PG(3,q) which can preserve an elliptic quartic of PG(3,q). Also, we prove for q?113 that if the j-invariant of Γ₄ does not disappear, then C cannot be extended in a natural way by adding a point of PG(3,q) to Γ₄.