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...     

A Gap in GRM Code Weight Distributions

The weight distribution of GRM (generalized Reed-Muller) codes is unknown in general. This article describes and applies some new techniques to the codes over F3. Specifically, we decompose GRM codewords into words from smaller codes and use this decomposition, along with a projective geometry technique, to relate weights occurring in one code with weights occurring in simpler codes. In doing so, we discover a new gap in the weight distribution of many codes. In particular, we show there is no word of weight 3^m–2 in GRM₃(4,m) for m>6, and for even-order codes over the ternary field, we show that under certain conditions, there is no word of weight d+, where d is the minimum distance and is the largest integer dividing all weights occurring in the code.     

Quasi-cyclic codes with cyclic constituent codes

Ling and Solé [S. Ling, P. Solé, On the algebraic structure of quasi-cyclic codes I: Finite fields, IEEE Trans. Inform. Theory 47 (2001) 2751–2760] showed that every quasi-cyclic code C is constructed from shorter linear codes which are called the constituent codes of C. Given a quasi-cyclic code C of length ℓm and index ℓ with m being pairwise coprime to ℓ and the order of the field C is over, if all its constituent codes are cyclic with their zeroes having full multiplicity, C is then shown to be equivalent to a cyclic code whose zeroes with their multiplicities are fully described in terms of the nonzeroes of the cyclic constituent codes. The general transformation to obtain the above-mentioned equivalent cyclic code is also explicitly given. The approach adopted here follows the approach used by A.M.A. Natividad [A.M.A. Natividad, PhD thesis, Department of Mathematics, University of Philippines Diliman, The Philippines, 2004] and uses the generalized discrete Fourier transform on the algebraic structure of the class of quasi-cyclic codes developed by Ling and Solé [S. Ling, P. Solé, On the algebraic structure of quasi-cyclic codes I: Finite fields, IEEE Trans. Inform. Theory 47 (2001) 2751–2760].     

Polycyclic codes as invariant subspaces

Polycyclic codes are a powerful generalization of cyclic and constacyclic codes. Their algebraic structure is studied here by the theory of invariant subspaces from linear algebra. As an application, a bound on the minimum distance of these codes is derived which outperforms, in some cases, the natural analogue of the BCH bound.     

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.     

Forms and Baer ordered *-fields

It is well known that for a quaternion algegra, the anisotropy of its norm form determines if the quaternion algebra is a division algebra. In case of biquaternio algebra, the anisotropy of the associated Albert form (as defined in [LLT]) determines if the biquaternion algebra is a division ring. In these situations, the norm forms and the Albert forms are quadratic forms over the center of the quaternion algebras; and they are strongly related to the algebraic structure of the algebras. As it turns out, there is a natural way to associate a tensor product of quaternion algebras with a form such that when the involution is orthogonal, the algebra is a Baer ordered *-field iff the associated form is anisotropic.     

On differential modular forms and some analytic relations between Eisenstein series

In the present article we define the algebra of differential modular forms and we prove that it is generated by Eisenstein series of weight 2, 4 and 6. We define Hecke operators on them, find some analytic relations between these Eisenstein series and obtain them in a natural way as coefficients of a family of elliptic curves. The fact that a complex manifold over the moduli of polarized Hodge structures in the case h ¹⁰=h ⁰¹=1 has an algebraic structure with an action of an algebraic group plays a basic role in all of the proofs.      

Quasi-cyclic codes as cyclic codes over a family of local rings

We give an algebraic structure for a large family of binary quasi-cyclic codes. We construct a family of commutative rings and a canonical Gray map such that cyclic codes over this family of rings produce quasi-cyclic codes of arbitrary index in the Hamming space via the Gray map. We use the Gray map to produce optimal linear codes that are quasi-cyclic.     

Group-valued measures on coarse-grained quantum logics

In [3] it was shown that a (real) signed measure on a cyclic coarse-grained quantum logic can be extended, as a signed measure, over the entire power algebra. Later ([9]) this result was re-proved (and further improved on) and, moreover, the non-negative measures were shown to allow for extensions as non-negative measures. In both cases the proof technique used was the technique of linear algebra. In this paper we further generalize the results cited by extending group-valued measures on cyclic coarse-grained quantum logics (or non-negative group-valued measures for lattice-ordered groups). Obviously, the proof technique is entirely different from that of the preceding papers. In addition, we provide a new combinatorial argument for describing all atoms of cyclic coarse-grained quantum logics.     

The Brauer group of a curve over a strictly local discrete valuation ring

LetK be the field of fractions of a curve overR whereR is the henselization of a regular local ring on an algebraic curve over a field which is algebraically closed and has characteristic 0. ThenK has the exponent=degree property for division algebras. In fact every central finite dimensionalK-division algebra with exponentn is a cyclic algebra of degreen. In memory of Professor S. A. Amitsur     

A Decomposition of the Descent Algebra of a Finite Coxeter Group

The purpose of this paper is twofold. First we aim to unify previous work by the first two authors, A. Garsia, and C. Reutenauer (see [2], [3], [4], [5] and [10]) on the structure of the descent algebras of the Coxeter groups of type A _n and B _n. But we shall also extend these results to the descent algebra of an arbitrary finite Coxeter group W. The descent algebra, introduced by Solomon in [14], is a subalgebra of the group algebra of W. It is closely related to the subring of the Burnside ring B(W) spanned by the permutation representations W/W _J, where the W _J are the parabolic subgroups of W. Specifically, our purpose is to lift a basis of primitive idempotents of the parabolic Burnside algebra to a basis of idempotents of the descent algebra.     

Algebraic density property of homogeneous spaces

Let X be an affine algebraic variety with a transitive action of the algebraic automorphism group. Suppose that X is equipped with several fixed point free nondegenerate SL₂-actions satisfying some mild additional assumption. Then we prove that the Lie algebra generated by completely integrable algebraic vector fields on X coincides with the space of all algebraic vector fields. In particular, we show that apart from a few exceptions this fact is true for any homogeneous space of form G/R where G is a linear algebraic group and R is a closed proper reductive subgroup of G.     

Subcodes of the Projective Generalized Reed-Muller Codes Spanned by Minimum-Weight Vectors

We use methods of Mortimer [19] to examine the subcodes spanned by minimum-weight vectors of the projective generalized Reed-Muller codes and their duals. These methods provide a proof, alternative to a dimension argument, that neither the projective generalized Reed-Muller code of order r and of length over the finite field F _q of prime-power order q, nor its dual, is spanned by its minimum-weight vectors for 0<r<m–1 unless q is prime. The methods of proof are the projective analogue of those developed in [17], and show that the codes spanned by the minimum-weight vectors are spanned over F _q by monomial functions in the m variables. We examine the same question for the subfield subcodes and their duals, and make a conjecture for the generators of the dual of the binary subfield subcode when the order r of the code is 1.     

On algebras admitting a complete set of near weights,evaluation codes,and Goppa codes

In 1998 Høholdt, van Lint and Pellikaan introduced the concept of a “weight function” defined on a \({\mathbb{F}_q}\)-algebra and used it to construct linear codes, obtaining among them the algebraic geometry (AG) codes supported on one point. Later, in 1999, it was proved by Matsumoto that all codes produced using a weight function are actually AG codes supported on one point. Recently, “near weight functions” (a generalization of weight functions), also defined on a \({\mathbb{F}_q}\)-algebra, were introduced to study codes supported on two points. In this paper we show that an algebra admits a set of m near weight functions having a compatibility property, namely, the set is a “complete set”, if and only if it is the ring of regular functions of an affine geometrically irreducible algebraic curve defined over \({\mathbb{F}_q}\) whose points at infinity have a total of m rational branches. Then the codes produced using the near weight functions are exactly the AG codes supported on m points. A bound for the minimum distance of these codes is presented with examples which show that in some situations it compares better than the usual Goppa bound.     

The weak conjecture on spherical classes

Let be the mod 2 Steenrod algebra. We construct a chain-level representation of the dual of Singer's algebraic transfer, which maps Singer's invariant-theoretic model of the dual of the Lambda algebra, , to and is the inclusion of the Dickson algebra, , into . This chain-level representation allows us to confirm the weak conjecture on spherical classes (see [9]), assuming the truth of (1) either the conjecture that the Dickson invariants of at least k = 3 variables are homologically zero in }, (2) or a conjecture on ${\mathcal{A}}$ -decomposability of the Dickson algebra in $\Gamma_k^{\wedge}$. We prove the conjecture in item (1) for k = 3 and also show a weak form of the conjecture in item (2). Received November 27, 1996; in final form March 6, 1998     

Some elements of Lie-differential algebra and a uniform companion for large Lie-differential fields

In this paper, we develop the beginning of Lie-differential algebra, in the sense of Kolchin (see [E.R. Kolchin, Differential algebra and algebraic groups, in: Pure and Applied Mathematics, vol. 54, Academic Press, 1973]) by using tools introduced by Hubert in [E. Hubert, Differential algebra for derivations with nontrivial commutation rules, J. Pure Appl. Algebra 200 (2005) 163–190].

In particular it allows us to adapt the results of Tressl (see [M. Tressl, A uniform companion for large differential fields of characteristic zero, Trans. Amer. Math. Soc. 357 (10) (2005) 3933–3951]) by showing the existence of a theory of Lie-differential fields of characteristic zero. This theory will serve as a model companion for every theory of large and Lie-differential fields extending a model complete theory of pure fields. As an application, we introduce the Lie counterpart of classical theories of differential fields in several commuting derivations.     

Weyl Groups are Finite — and Other Finiteness Properties of Cartan Subalgebras

For each pair (??,??) consisting of a real Lie algebra ?? and a subalgebra a of some Cartan subalgebra ?? of ?? such that [??, ??]∪ [??, ??] we define a Weyl group W(??, ??) and show that it is finite. In particular, W(??, ??,) is finite for any Cartan subalgebra h. The proof involves the embedding of 0 into the Lie algebra of a complex algebraic linear Lie group to which the structure theory of Lie algebras and algebraic groups is applied. If G is a real connected Lie group with Lie algebra ??, the normalizer N(??, G) acts on the finite set Λ of roots of the complexification ??c with respect to hc, giving a representation π : N(??, G)→ S(Λ) into the symmetric group on the set Λ. We call the kernel of this map the Cartan subgroup C(??) of G with respect to h; the image is isomorphic to W(??, ??), and C(??)= {g G : Ad(g)(h)— h ε [h,h] for all h ε h }. All concepts introduced and discussed reduce in special situations to the familiar ones. The information on the finiteness of the Weyl groups is applied to show that under very general circumstance, for b ∪ ?? the set ??? ?(b) remains finite as ? ranges through the full group of inner automorphisms of ??.     

Reed-Muller codes and Barnes-Wall lattices: Generalized multilevel constructions and representation over GF(2<Superscript><Emphasis Type="Italic">q</Emphasis></Superscript>)

Generalized multilevel constructions for binary RM(r,m) codes using projections onto GF(2 ^q ) are presented. These constructions exploit component codes over GF(2), GF(4),..., GF(2 ^q ) that are based on shorter Reed-Muller codes and set partitioning using partition chains of length-2 ^l codes. Using these constructions we derive multilevel constructions for the Barnes-Wall Λ(r,m) family of lattices which also use component codes over GF(2), GF(4),..., GF(2 ^q ) and set partitioning based on partition chains of length-2 ^l lattices. These constructions of Reed-Muller codes and Barnes-Wall lattices are readily applicable for their efficient decoding.