2.1 Generalised Reed-Solomon codes as cyclic codes
Another important family of Goppa codes is obtained considering the normal rational curve (NRC) Cn defined over Fq:
Cn≔Fq1α…αn:α∈Fq∪∞.
Assuming that np=1 are coprime, the set 1αα2…αn−1 forms a basis of Fqn over Fq, where p is the characteristic of the field. Thus points in the NRC are in correspondence with Fq−linear combinations of the base vectors up to collineation. The Goppa codes of dimension n defined over Cn are constructed by evaluating non-zero polynomials of degree less than n over a sequence α1,…,αn of n distinct elements in Fq, if k≤n, then the map
ϵ:Fqx→Fqn,f↦fα1…αnE1
is injective, since the existence of a non-zero polynomial of degree less than k vanishing on all αi implies n<k by the fundamental theorem of algebra (a non-zero polynomial of degree r with coefficients in a field can have at most r roots). These are just Reed-Solomon codes of parameters nkd over a finite field Fq, with parity check polynomial hx=∏i=1qx−αi, where α is a primitive root of Fq such that αk+1=α+1. Any codeword c0c1…cn−1 can be expanded into a q-ary k vector with respect to the basis 1α…αk−1. Construction of generalised Reed-Solomon codes over Fq only employ elements of Fq, hence their lengths are at most q+1. In order to get longer codes, one can make use of elements of an extension of Fq, for instance considering subfield subcodes of Reed-Solomon codes. In this way, one gets cyclic codes. Recall that a linear cyclic code is an ideal in the ring Fqx/xn−1 generated by a polynomial gx with roots in the splitting field Fql of xn−1, where n∣ql−1, ([4]). We shall identify the code with the set of its codewords. A natural question then to ask is how many irreducible polynomials of degree at least 2 are there over the algebraic closure of Fqx. Next theorem expresses this number in terms of Stirling numbers.
Theorem 2.2. Assume thatqn=1, then the number of polynomials of degreen≥2decomposable into distinct linear factors over a finite fieldFqof arbitrary characteristic a prime numberp, is equal to∑k=1nqk, whereqkis the falling factorial polynomialq⋅q−1…q−k=∑k=0nsnkqk, wheresnkis the Stirling number of the first kind (the number of ways to partition a set ofnobjects intoknon-empty subsets), divided by the order of the affine transformation group of the affine lineA1=P1\∞, that isq2−q.
Proof. We need to count all the polynomials fnx in one variable of degree n fixed. We assume that our polynomial fnx decomposes into linear factors, otherwise we work over F¯qx, where F¯q denotes the algebraic closure of the finite field Fq. Since the number of ordered sequences on q symbols is q! and each root is counted with its multiplicity, it follows that the number of monic polynomials with n−1 different roots is qq−1q−2…q−n+1≔q−2n. Now we observe that polynomials are invariant by the action of automorphisms of the affine line, so we must divide this number by the order of this group which is q2−q. □
Theorem 2.3. Given a set of integers01…n−1modulen, there is a setJofkintegers which is a set of roots, that is, there is a polynomialhx=∏j∈Jx−αj, whereαis a generator ofFpmfor some prime numberpandmis the least integer such thatn∣pm−1. The idealhxgenerates inFpmx/xn−1is a cyclic linear code of parametersnkn−k+1.
Proof. Let m be the least integer such that n divides pm−1, then g.c.dmp=1. We define an equivalence relation on the set of integers 01…n−1, by declaring two integers i and j in the range 0≤i≤n−1 to be conjugate module n if psi≡jmodn. This equivalence relation partition the set into cyclotomic cosets. The cyclotomic coset containing j, which we will denote by Ωj, can be described explicitly as the set jpj…pk−1j, where k is the least positive integer such that pkj≡jmodn and j is not necessarily the smallest integer in such coset. Denote by In the set consisting of the smallest integers in each cyclotomic coset, then In is a set root, that is, it is a set of k integers in arithmetic progression modulo n whose increment is relatively prime to n. Let d=n−k+1, then the polynomial ∏i∈Inx−αi defines a cyclic code of parameters nkd. □
As an application of Theorem 2.2, given an integer n, we can count the number of cyclic codes of parameters nk for each 0≤k≤n and set of roots α1,…,αk in the splitting field of xn−1, the corresponding polynomial gx=∏i=1kx−αi generates a linear cyclic code in the ring Fqx/xn−1. Thus for each 0≤k≤n there are exactly qk/q2−q cyclic codes.
In the theory of error-correcting codes to a given code C⊂Fqn, one assigns another important parameter, the minimum distance d which measures how good the decoding is.
Definition 2.4. The distance between vectorsa=a1a2…anandb=b1b2…bnin the Weighted Hamming metric (WHM) is defined by a function:
dWHab=∑i=1nwidaibi¯,
where wi>0, daibi=1 if ai≠bi and daibi=0 if ai=bi. The weight of a vector a in the WHM is wtWHa=dWHa0=∑i:ai≠0wi. The value wi and vector w=w1w2…wn are called a weight of position i and a vector of weights of positions respectively.
Geometrically a binary vector a1…an of length n gives the coordinates of a vertex of a unit cube in n dimensions.
Example 1. Consider the Goppa code defined by the rational functiongx=3x2−5x+5x3−2x2+xwhich admits as decomposition into partial fractions the expressionGx≔5x−2x−1+3x−12. The presence of a double factorx−12corresponds to the existence of an eigenspaceEin the vector spaceFqnof multiplicity 2 and thus anα−splitting subspace where the operatorαis just the linear operatorA−λI, withλthe eigenvalue associated toEandAis the generator matrix of the code. We recall that anr−dimensionalWsubspace isα−splitting ifαiW=Wis invariant under the action of any elementαiin the Galois group of the extensionFq↣Fqα.
2.2 Algebraic function field codes
A much greater variety of linear codes is obtained if one uses places of arbitrary degree rather than just places of degree 1. These codes are more naturally described through function field codes. A general viewpoint is that function field codes are certain finite dimensional linear subspaces of an algebraic function field over a finite field as in Goppa’s construction.
In the paper [5], the authors introduce another construction where places of arbitrary degree are allowed. The method consists of choosing two divisors G1 and G2 of an algebraic curve over Fq with G1≤G2. Then LG1 is a subspace of the vector space LG2 over Fq. If we choose a basis of LG2, then the coordinate vectors of the elements of LG1 form a linear code over Fq of length n=dimLG2 and dimension k=dimLG1. These are known as function field codes and they provide a general perspective on the construction of algebraic-geometry codes [6].
Example 2. We consider as in [7] the Suzuki curveχdefined overFqby the following equationyq−y=xq0xq−xwithq=2q02≥8andq0=2r. This curve has exactlyq2+1−rational places with a single place at infinityP∞and it is of genusgS=q0q−1. We construct a code out of the divisor F=mP∞andQwhereQ=P1+…+Pq2is the sum of theq2−rational points and the parametermsatisfies the boundm>2g−2andgis the genus of the curve.
Observe that the geometric Goppa code CFQ is an Fq-subspace of Fqq2 and its dimension k as an Fq−vector space is the dimension of the code. Geometrically, it corresponds to a point in the Grassmannian Gq2,kFq. The set of codewords recognised by the code CFQ admits the following description in terms of monomial ideals in the variables x,y,z,w:
xaybzcwd′abcd′≥0aq+bq+q0+cq+2q0+d′q+2q0+1≤d,
where z=x2q0+1 and w=xy2q0−z2q0 are elements in the function field Fχ≔Fqxy over Fq. Moreover, it is a generating set for the linear series LdP∞ associated to the divisor dP∞.
Theorem 2.5. Cyclic codes are function field codes constructed over the curveCn,mwith affine equationym+xn=1defined over a finite fieldFqofqelements, whereqis a power of a primepandn,mare integer numbers greater or equal than 2.
Proof. Let us assume n is an integer even number, thus n=2k⋅s, with s an integer odd number. We recall that a linear cyclic code is an ideal in the ring Fqx/xn−1 generated by a polynomial gx with roots in the splitting field Fql of xn−1, where n∣ql−1. If we consider the factorisation of the polynomial xn−1 over Fpx, we get xn/2−1xn/2+1=xn/4−1xn/4+1xn/2+1=xn/2k−1xn/2k+1xn/2k−1−1xn/2k−1+1…xn/2+1. We see that the point P0=α0∈PFq2 with αn/2=p−1 is an Fq2−rational place of the affine curve ym=xn/2+1. The other rational places are Pk=β0 with βn/2k=p−1,..., P2=β20, P1=10, P0=−10 and the place P∞=0α at ∞. The cyclic code is realised as the algebraic geometric code associated to the divisors D=P0+P1+…+Pk, G=μP∞ and the parameter μ satisfies the bound μ>2g−2, where g is the genus of the curve Cn,m. Note that m is the least integer such that n∣pm−1. In particular α is a generator of Fpm.
If n is an integer odd number, by Theorem 2.3, we know there is a set of roots αjj∈J, such that α is a generator of Fpm. Now we consider the points Pj=αj0 with j∈J and the point P at P∞=0α=∞, and the cyclic code is realised as the function field code associated to the divisors D=∑j∈JPj and μP∞. □
Remark 2.6. The proof given in theorem gives a realisation of cyclic codes as AG codes constructed over the curve with affine modelym+xn=1. In particular whenm=n=q+1, we cover the codes defined over the Hermitian curve.
Another important family of cyclic codes is obtained considering the roots of the polynomial xn−1 over its splitting field. These codes are of great importance in ADN-computing and as they are linear codes, they can be described as function fields. Let α be a primitive element of the underlying vector space over Fq. Since the base field is of characteristic p, xn−1 has n different zeroes. Let F¯qx be the extension field containing the nth roots of unity 1,α,…,αn−1, where αn−1+αn−2+…+α+1=0. Moreover the set 1α…αn−1 constitutes a basis over the prime field Fp, and the field extensions Fpn≅Fpx/xn−1+…+x+1 are isomorphic.
Example 3. The polynomialx2+x+1overFpxis irreducible, thus the fieldsFp2≅Fpx/x2+x+1are isomorphic, and the rootsw,w+1correspond to one place of degree 2 in the extension fieldFpw.
Example 4. We define the polynomialsfx=xn+a1xn−1+⋯+an, withai∈Q, andfxt=fx−t. Then, iffis a separable polynomial, then the Galois group offxtoverQtis a regular extension with Galois groupSn.
Observe that Qx1…xn is the function field of an n−1−dimensional projective space Pn−1Q over Q. Suppose that z1,…,zn are the roots of f in a splitting field of f over Q. Each coefficient ai of xi in f is symmetric in z1,…,zn, thus by the theorem on symmetric functions, we can write ai as a symmetric polynomial in z1,…,zn with rational coefficients. On the other side, for a permutation σ∈Sn, set Eσ=x1zσ1+⋯+xnzσn in Qx1…xn and fx=∏σx−Eσ, where σ runs through all permutations in Sn.
Theorem 2.7. (Hilbert) LetG=Snbe acting onQx1…xn. The fieldEofSn−invariants isQt1…tn, wheretiis theithsymmetric polynomial inx1,…,xnandQx1…xnhas Galois groupSnoverE. It is the splitting field of the polynomialfx=xn−t1xn−1+…+−1ntn.
Let F be a finite field such that charFn=1. A non-zero polynomial in F¯xy defines a curve on the plane F¯2. The elliptic curves are curves of the form y2=fx, where fx is a polynomial of degree 3 with coefficients in F¯.
Proposition 2.8. Letn=rsbe a factorisation of an integer positive numberninto irreducible coprime factors and assumer<s, then there is a sequence of field extensionsFqr⊂Fqs⊂Fqn.
Proof. Consider the map Tn:Fn↦Fn
tj=−1jσjx1…xn,
where σj is the jth elementary symmetric function in the variables xi. Thus tjj=1⋯n, are the coefficients of the equation:
fzt1…tn=zn+−1t1zn−1+⋯+−1ntn=z−x1z−x2⋯z−xn.
If we apply Theorem 2.7 to the ith elementary symmetric polynomial in the symbols α,αq,αq2,…,αqn, we get that the field of Sn invariants of the polynomial fzt1…tn contains an extension Fqn of Fq. Moreover, for any divisor r of n, one can consider the field of Sr invariants, and apply Theorem 2.7 to the symbols α,αq2s,…,αqrs, where n=rs. Then we get an extension Fqs of Fqr and all its Fq-subspaces are stable under GalFqs/Fqr. □
Example 5. Assumen=q+1and we study again the roots of the polynomialxq−1in its splitting field. Letξbe a non-trivial n-root of unity, for any divisorrofn, one can consider the symbolsξqr,…,ξq,ξ. The field ofSrinvariants of the polynomialfzt1…tris the set of solutions to the equation:
xqr+…+xq+x=ainFqn.E2
In F2n, for any divisor d of n, there are exactly 2d−1 solutions to Eq. (2) if n/d is odd and 2d solutions if n/d is even.
Instead of considering r,s divisors of n, we can consider a partition of n into two parts. For example for an integer 0≤k≤n, we consider the partition kn−k of n. Fix two elements g1,g2∈GLnq of rank k and rank n−k. These points correspond to linear transformations Tgi:Fqn→Fqn, i∈1,2. It is well known that the corresponding points Fqk,qn⊂Fqn and Fqn−k,qn⊂Fqn in the Grassmannians Gk,nFq of k−dimensional subspaces and the Grassmannian Gn−kFq of n−k dimensional subspaces respectively are dual subspaces in the underlying vector space Fqn for the Euclidean inner product. Note that the Hamming weight is preserved under invertible linear transformation. This case is of great interest for applications in coding theory, since the corresponding codes with generator matrices G1 and G2 respectively are dual codes. Namely, given a linear nk-code, a parity check matrix for C is an n−k×n matrix H of rank n−k such that C=x∈Fqn:HcT=0. Then the dual code C⊥ is the linear nn−k code generated by the parity check matrix of C. There is a right action of the general linear group GLnFq on Gk,nFq:
Gk,nFq×GLnFq→Gk,nFqE3
UA→UA.E4
One can study the orbits of Gk,nFq by the action of any subgroup in the general linear group GLnFq. For example we can study the orbit of any triangle group: the Klein group ℤ2×ℤ2, the dihedral group, the alternated groups A4 and A5 or the symmetric group Sn. Take as T the standard shift operator on Fqn, a linear code C is said to be quasi-cyclic of index l or l−quasi-cyclic if and only if is invariant under Tl. If l=1, it is just a cyclic code. The quantity m≔n/l is called the co-index of C. Namely, if we view a codeword c0c1…cn−1 of C as a polynomial c0+c1x+…+cn−1xn−1∈Fqx, then Tcx=x⋅cxmodxn−1.
Example 6. We study the action of a rotation element on the GrassmannianG2,4Fqof lines in a 3-dimensional projective spacePG3q. We apply to any linega rotationτof angleα=2πn, represented by the array of vectors<1,0,0,0cosαsinα,0−cosαsinα>. It is easy to see that the orbit code by the composed actionτmwithmdivisor ofnis a quasi-cyclic code of indexmn.
In general, we study generalised Grassmannians or more commonly known as flag varieties. Fix a partition λ=λ1…λr of n and let Fλ=FλFq be the variety of partial flags of Fq−vector spaces
0=Er⊂Er−1⊂…⊂E1⊂E0=Fqn
such that dimEi−1/Ei=λi. The group GLnFq acts on Fλ in the natural way. Fix an element X0∈Fλ and denote by Pλ the stabilizer of X0 in G and by Uλ the subgroup of elements g∈Pλ which induces the identity on Ei/Ei+1 for all i=0,1,…,n−1. Put Lλ=GLλrFq×…,×GLλ1Fq, then we have Pλ=Lλ×Uλ.
Proposition 2.9. Let us consider the factorisation ofninto irreducible pairwise coprime factorsn=p1e1p2e2⋯prerwithe1<e2<…<er, andλ=e1…erbe the partition of exponents. Then there is a flag varietyFλFqof partial flags ofFq−vector spaces:
0=Er⊂Er−1⊂⋯⊂E1⊂E0=Fqn,
such that dimEi−1/Ei=ei.
Proof Observe that the result follows trivially for the case in which n is a prime number e1=⋯=er=1. If n=rs factorizes into two irreducible prime factors, the result follow as we have seen above, there is a flag 0=Er⊂Es⊂E0=Fqn and then by induction in r the result follows. □
Given a cyclic code over F¯ of length n, its defining set is given by the exponents occurring in gx, where gx is the generator polynomial of the ideal of the code in Fx/xn−1.
Let α∈F¯ be an nth primitive root of unity. The nth cyclotomic polynomial Φnx=∏1<j<n,jn=1x−αj∈F¯x is the minimal polynomial of α over F. It is monic of degree of the Euler’s totient function φn. It has integer coefficients and it is irreducible over Q. In Qx, we have the factorization into irreducible polynomials:
xn−1=∏d∣nΦdx.
By Möebius inversion:
Φnx=∏d∣nxd−1μn/d
In the case of binary codes where q=2, Bezzateev and Shekhunova [8] have obtained that the number of irreducible normalized polynomials I2ml of degree l over F2m satisfy the following equation:
I2ml=1l∑d/lμd2mld.E5
where μd is the Möebius function:
μd=1ifd=1;−1rifdisaproductofrdifferentprimenumbers;0inallothercases.
Let gx equals the least common multiple lcmΦix:αi∈S, then S is a defining set for C. We will describe the defining set by the exponents occurring in S with S=i1i2…il, where i1<…<il. A parity check matrix for the code CS is given by:
MS=αi10αi11⋯αi1n−1αi20αi21⋯αi2n−1⋮⋮αir0αir1⋯αirn−1)
The code C⊂Fn is obtained as the subfield subcode of C¯:
C=c∈Fn:MRcT=0.
Given a triple IJK of subsets of 1…n of the same cardinality r, we associate to them partitions λ,μ and ν as follows. Let I=i1<…<ir⊂1…n, then the corresponding partition is defined as λ=ir−r…r1−1, and respectively for J,K. We call the triple IJK admissible for the Horn problem, if the corresponding triple of partitions λμγ occurs as eigenvalues of a triple of Hermitian r by r matrices, with the third one the sum of the first two.
We describe Horn’s inductive procedure to produce set of triples IJK⊂01…n.
Urn=IJK∑i∈Ii+∑j∈Jj=∑k∈Kk+rr+1/2,
Trn={IJK∈Urn∣forallp<randallFGH∈Tpr,
∑f∈Fif+∑g∈Gjg≤∑h∈Hkh+pp+1/2}.
Example 7. Let us consider the triple of subsets
IJK=1,3,51,3,52,4,6
and the corresponding triple of partitions λμν=2,1,02,1,03,2,1 arises from the triple of diagonal 3 by 3 matrices with diagonal entries 2,1,0,1,0,2 and 3,1,2.
Lemma 2.10. For any tripleIJKadmissible for the Horn problem, the polynomials defined byfx=∏i∈Ix−αi,gx=∏j∈Jx−αj,andhx=∏k∈Kx−αkgenerate a cyclic code of lengthn=ir+jr+krmodpandk=r, wherer=∣I∣+∣J∣+∣K∣andpis the characteristic of the fieldF.
Proof. The cyclic code generated by fx coincides with the cyclic code generated by lcmmix:αii∈I and respectively for gx and hx the polynomials lcmmjx:αjj∈J and lcmmkx:αkk∈K. It is the cyclic code generated by the minimal polynomial of αir+jr+kr. □
Remark 2.11. We see that Horn’s algorithm is relevant since some classical code constructions can be seen as ideals in a finite dimensional commutative semi simple algebra over a finite fieldFqwithq=prelements andpa prime number as in example (3).
Lemma 2.12. The family of cyclic codes obtained by considering the roots of the polynomialxn−1over its splitting fields are indeed AG codes arising from genus 0 curves, and by Riemann-Roch theorem, their parameters satisfy the boundd≥n+1−k, wheredis the minimum distance.
Proof Let F¯qx be the extension field containing the nth roots of unity 1,α,…,αn−1, where αn−1+αn−2+…+α+1=0. Moreover the set 1α…αn−1 constitutes a basis over the prime field Fp, and the field extensions Fpn≅Fpx/xn−1+…+x+1 are isomorphic. □