A Geometrical Realisation of Quasi-Cyclic Codes

Abstract

We study and enumerate cyclic codes which include generalised Reed-Solomon codes as function field codes. This geometrical approach allows to construct longer codes and to get more information on the parameters defining the codes. We provide a closed formula in terms of Stirling numbers for the number of irreducible polynomials and we relate it with other formulas existing in the literature. Further, we study quasi-cyclic codes as orbit codes in the Grassmannian parameterizing constant dimension codes. In addition, we review Horn’s algorithm and apply it to construct classical codes by their defining ideals.

1. Introduction

Function fields are used ubiquitously in algebraic coding theory for their flexibility in constructions and have produced excellent linear codes. Suitable families of function fields, for example good towers of function fields, have been used to construct families of codes with parameters bound better than the asymptotic bound.

Let $q$ a power of a prime number $p$. It is well known, that there exists exactly one finite field with $q$ elements which is isomorphic to the splitting field of the polynomial $x^q-x$ over the prime field ${\mathbb{F}}_p$. Any other field $F$ of characteristic $p$ contains a copy of ${\mathbb{F}}_p$. We denote respectively by ${\mathbb{A}}^n\left({\mathbb{F}}_q\right)$ and ${\mathbb{P}}^n\left({\mathbb{F}}_q\right)$ the affine space and the projective space over ${\mathbb{F}}_q$. Let ${\mathbb{F}}_q\left[x_1,x_2,\dots ,x_n\right]$ be the algebra of polynomials in $n$ variables over ${\mathbb{F}}_q$.

The encoding of an information word into a k-dimensional subspace is usually known as coding for errors and erasures in random network coding [1]. Namely, let $V$ be an $N-$dimensional vector space over ${\mathbb{F}}_q$, a code for an operator channel with ambient space $V$ is simply a non-empty collection of subspaces of $V$. The collection of subspaces is a code for error correcting errors that happen to send data through an operator channel. The matrix coding the information is parameterised by random variables $a_1,a_2,\dots ,a_n$ which constitute the letters of an alphabet. Here the operator channel is an abstraction of the operator encountered in random linear network coding, when neither transmitter nor receiver has knowledge of the channel transfer characteristics. The input and output alphabet for an operator channel is the projective geometry. A good code is capable of correcting error and erasures at the output of the operator channel. Thus in order to construct good codes one need to choose a metric consistent with channel errors and search of a set of vectors with given metric properties as a correcting code. The codes considered here are codes for channels whose errors are consistent with the weighted Hamming metric (WHM).

Let $\mathcal{C}$ be a non-singular, projective, irreducible curve defined over ${\mathbb{F}}_q$, as the vanishing locus of a polynomial $F\in {\mathbb{F}}_q\left[x_0,x_1,x_2\right]$. We define the number $N\left(q\right)$ of ${\mathbb{F}}_q-$rational points on the curve to be

$$N\left(q\right)=\mid \left\{\left(x_0,x_1,x_2\right)\in {\mathbb{P}}^2\left({\mathbb{F}}_q\right)|F\left(x_0,x_1,x_2\right)=0\right\}\mid .$$

It is a polynomial in $q$ with integer coefficients, whenever $q$ is a prime power.

The number of points $\overline{\mathcal{C}}\left({\mathbb{F}}_{q^r}\right)$ on $\mathcal{C}$ over the extensions ${\mathbb{F}}_{q^r}$ of ${\mathbb{F}}_q$ is encoded in an exponential generating series, called the zeta function of $\overline{\mathcal{C}}$:

$$Z\left(\mathcal{C},t\right)=\mathit{exp}\left(\sum _{r=1}^{\infty }\#\overline{\mathcal{C}}\left({\mathbb{F}}_{q^r}\right)\frac{t^r}{r}\right).$$

Garcia and Stichtenoth analysed the asymptotic behaviour of the number of rational places and the genus in towers of function fields, [2]. From Garcia-Stichtenoth’s second tower one obtains codes over any field ${\mathbb{F}}_q$ where $q$ is an even power of a prime [3].

One of the main problems in coding theory is to obtain non-trivial lower bounds of the number $N\left(F_i\right)$ of rational places of towers of function fields ${\left\{F_i/{\mathbb{F}}_q\right\}}_{i=1}^{\infty }$ such that $F_i⊊F_{i+1}$. Suitable families of function fields, for example good towers of function fields, have been used to construct families of codes that beat the Gilbert-Varshamov bound. This paper aims to explore this link for the study and construction of quasi-cyclic codes. For example good codes are obtained for curves of genus 0, they are in fact extended generalised Reed-Solomon codes.

Notation. Let ${\mathbb{F}}_q$ denote the Galois field of $q$ elements and let ${\left({\mathbb{F}}_q\right)}^n$ denote the vector spaces of all ordered n-tuples over ${\mathbb{F}}_q$. The Hamming weight of a vector $x$, denoted by $\mathit{wt}\left(x\right)$ is then number of non-zero entries in x. A linear code $C$ of length $n$ and dimension $k$ over ${\mathbb{F}}_q$ is a k-dimensional subspace of ${\left({\mathbb{F}}_q\right)}^n$. Such a code is called ${\left[n,k,d\right]}_q$ code if its minimum Hamming distance is $d$. For $d$ a positive integer, $\alpha =\left({\alpha }_1,\dots ,{\alpha }_m\right)$ is a partition of $d$ into $m$ parts if the ${\alpha }_i$ are positive and decreasing.

2. Algebraic geometric codes

Let ${\mathbb{F}}_q$ be a finite field of $q$ elements, where $q$ is a power of a prime. We consider as an alphabet a set $\mathcal{P}=\left\{P_1,\dots ,P_N\right\}$ of $N-{\mathbb{F}}_q$ rational points lying on a smooth projective curve $\mathcal{C}$ of genus $g$ and degree $d$ defined over the field ${\mathbb{F}}_q$. If $D$ is a divisor on the curve $\mathcal{C}$, $\mathcal{L}\left(D\right)$ is the linear series attached to this divisor with coefficients in the field.

Definition 2.1. Algebraic Geometric Codes (AGC) are constructed by evaluation of the global sections of a line bundle or a vector bundle on the curve$\mathcal{C}$over$N$$\left(N>g\right)$distinct rational places$P_1,\dots ,P_N$. Namely, let$F\mid {\mathbb{F}}_q$be the function field of the curve,$\mathcal{D}$the divisor$P_1+\cdots +P_N$and$G$a divisor of$F\mid {\mathbb{F}}_q$of degree$s\le N$such that$\text{Supp}\mathrm{G}\cap \text{Supp}\mathrm{D}=ø$. Then the geometric Goppa code associated with the divisors$D$and$G$is defined by

$$\mathbf{C}\left(D,G\right)=\left\{\left(x\left(P_1\right),\dots ,x\left(P_n\right)\right)|x\in \mathcal{L}\left(G\right)\right\}\subseteq {\mathbb{F}}_{q^n}.$$

Recall that ${\mathbb{F}}_{q^n}\mid {\mathbb{F}}_q$ is a cyclic Galois extension and it is finitely generated by unique element $\alpha \in {\mathbb{F}}_{q^n}\backslash {\mathbb{F}}_q$. $\alpha$ is a primitive element and $\left\{1,\alpha ,{\alpha }^2,\dots ,{\alpha }^{n-1}\right\}$ is a basis of the field extension ${\mathbb{F}}_q$ ↪ ${\mathbb{F}}_q\left(\alpha \right)$, that is, ${\mathbb{F}}_{q^n}\cong {\left({\mathbb{F}}_q\right)}^n$.

In the sequel, an ${\left[n,k\right]}_q$-code $C$ is a k-dimensional subspace of ${\left({\mathbb{F}}_q\right)}^n.$

2.1 Generalised Reed-Solomon codes as cyclic codes

Another important family of Goppa codes is obtained considering the normal rational curve (NRC) ${\mathcal{C}}^n$ defined over ${\mathbb{F}}_q$:

$${\mathcal{C}}^n≔\left\{{\mathbb{F}}_q\left(1,\alpha ,\dots ,{\alpha }^n\right):\alpha \in {\mathbb{F}}_q\cup \left\{\infty \right\}\right\}.$$

Assuming that $\left(n,p\right)=1$ are coprime, the set $\left\{1,\alpha ,{\alpha }^2,\dots ,{\alpha }^{n-1}\right\}$ forms a basis of ${\mathbb{F}}_{q^n}$ over ${\mathbb{F}}_q$, where $p$ is the characteristic of the field. Thus points in the NRC are in correspondence with ${\mathbb{F}}_q-$linear combinations of the base vectors up to collineation. The Goppa codes of dimension $n$ defined over ${\mathcal{C}}^n$ are constructed by evaluating non-zero polynomials of degree less than $n$ over a sequence ${\alpha }_1,\dots ,{\alpha }_n$ of $n$ distinct elements in ${\mathbb{F}}_q$, if $k\le n$, then the map

$$\mathrm{ϵ}:{\mathbb{F}}_q\left[x\right]\to {\mathbb{F}}_q^n,f\mapsto \left(f\left({\alpha }_1,\dots ,{\alpha }_n\right)\right)$$E1

is injective, since the existence of a non-zero polynomial of degree less than $k$ vanishing on all ${\alpha }_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 $\left[n,k,d\right]$ over a finite field ${\mathbb{F}}_q$, with parity check polynomial $h\left(x\right)={\prod }_{i=1}^q\left(x-{\alpha }^i\right)$, where $\alpha$ is a primitive root of ${\mathbb{F}}_q$ such that ${\alpha }^{k+1}=\alpha +1$. Any codeword $\left(c_0,c_1,\dots ,c_{n-1}\right)$ can be expanded into a $q$-ary $k$ vector with respect to the basis $\left\{1,\alpha ,\dots ,{\alpha }^{k-1}\right\}$. Construction of generalised Reed-Solomon codes over ${\mathbb{F}}_q$ only employ elements of ${\mathbb{F}}_q$, hence their lengths are at most $q+1$. In order to get longer codes, one can make use of elements of an extension of ${\mathbb{F}}_q$, 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 ${\mathbb{F}}_q\left[x\right]/\left(x^n-1\right)$ generated by a polynomial $g\left(x\right)$ with roots in the splitting field ${\mathbb{F}}_q^l$ of $x^n-1$, where $n\mid q^l-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 ${\mathbb{F}}_q\left[x\right]$. Next theorem expresses this number in terms of Stirling numbers.

Theorem 2.2. Assume that$\left(q,n\right)=1$, then the number of polynomials of degree$\left(n\ge 2\right)$decomposable into distinct linear factors over a finite field${\mathbb{F}}_q$of arbitrary characteristic a prime number$p$, is equal to${\sum }_{k=1}^n{\left(q\right)}_k$, where${\left(q\right)}_k$is the falling factorial polynomial$q\cdot \left(q-1\right)\dots \left(q-k\right)={\sum }_{k=0}^{n}s\left(n,k\right)q^k$, where$s\left(n,k\right)$is the Stirling number of the first kind (the number of ways to partition a set of$n$objects into$k$non-empty subsets), divided by the order of the affine transformation group of the affine line${\mathbb{A}}^1={\mathbb{P}}^1\backslash \infty$, that is$q^2-q$.

Proof. We need to count all the polynomials $f_n\left(x\right)$ in one variable of degree $n$ fixed. We assume that our polynomial $f_n\left(x\right)$ decomposes into linear factors, otherwise we work over ${\overline{\mathbb{F}}}_q\left[x\right]$, where ${\overline{\mathbb{F}}}_q$ denotes the algebraic closure of the finite field ${\mathbb{F}}_q$. 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 $q\left(q-1\right)\left(q-2\right)\dots \left(q-n+1\right)≔{\left(q-2\right)}_n$. 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 $q^2-q$. $\square$

Theorem 2.3. Given a set of integers$\left\{0,1,\dots ,n-1\right\}$module$n$, there is a set$J$of$k$integers which is a set of roots, that is, there is a polynomial$h\left(x\right)={\prod }_{j\in J}\left(x-{\alpha }^j\right)$, where$\alpha$is a generator of$\left({\mathbb{F}}_{p^m}\right)$for some prime number$p$and$m$is the least integer such that$n\mid p^m-1$. The ideal$h\left(x\right)$generates in${\mathbb{F}}_{p^m}\left[x\right]/\left(x^n-1\right)$is a cyclic linear code of parameters$\left(n,k,n-k+1\right)$.

Proof. Let $m$ be the least integer such that $n$ divides $p^m-1$, then $g.c.d\left(m,p\right)=1$. We define an equivalence relation on the set of integers $\left\{0,1,\dots ,n-1\right\}$, by declaring two integers $i$ and $j$ in the range $0\le i\le n-1$ to be conjugate module $n$ if $p^{s}i\equiv j\left(modn\right)$. This equivalence relation partition the set into cyclotomic cosets. The cyclotomic coset containing $j$, which we will denote by ${\mathrm{\Omega }}_j$, can be described explicitly as the set $\left\{j,\mathit{pj},\dots ,p^{k-1}j\right\}$, where $k$ is the least positive integer such that $p^{k}j\equiv j\left(modn\right)$ and $j$ is not necessarily the smallest integer in such coset. Denote by $I_n$ the set consisting of the smallest integers in each cyclotomic coset, then $I_n$ 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 ${\prod }_{i\in I_n}\left(x-{\alpha }^i\right)$ defines a cyclic code of parameters $\left(n,k,d\right)$. $\square$

As an application of Theorem 2.2, given an integer $n$, we can count the number of cyclic codes of parameters $\left[n,k\right]$ for each $0\le k\le n$ and set of roots ${\alpha }_1,\dots ,{\alpha }_k$ in the splitting field of $x^n-1$, the corresponding polynomial $g\left(x\right)={\prod }_{i=1}^k\left(x-{\alpha }_i\right)$ generates a linear cyclic code in the ring ${\mathbb{F}}_q\left[x\right]/\left(x^n-1\right)$. Thus for each $0\le k\le n$ there are exactly ${\left(q\right)}_k/\left(q^2-q\right)$ cyclic codes.

In the theory of error-correcting codes to a given code $C\subset {\mathbb{F}}_q^n$, one assigns another important parameter, the minimum distance $d$ which measures how good the decoding is.

Definition 2.4. The distance between vectors$a=\left(a_1,a_2,\dots ,a_n\right)$and$b=\left(b_1,b_2,\dots ,b_n\right)$in the Weighted Hamming metric (WHM) is defined by a function:

$$d_{\mathit{WH}}\left(a,b\right)=\sum _{i=1}^n{w}_i\overline{d\left(a_i,b_i\right)},$$

where $w_i>0$, $d\left(a_i,b_i\right)=1$ if $a_i\ne b_i$ and $d\left(a_i,b_i\right)=0$ if $a_i=b_i$. The weight of a vector $a$ in the WHM is ${\mathit{wt}}_{\mathit{WH}}\left(a\right)=d_{\mathit{WH}}\left(a,0\right)={\sum }_{i:a_i\ne 0}{w}_i$. The value $w_i$ and vector $w=\left(w_1,w_2,\dots ,w_n\right)$ are called a weight of position $i$ and a vector of weights of positions respectively.

Geometrically a binary vector $\left(a_1,\dots ,a_n\right)$ 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 function$g\left(x\right)=\frac{3x^2-5x+5}{x^3-2x^2+x}$which admits as decomposition into partial fractions the expression$G\left(x\right)≔\frac{5}{x}-\frac{2}{x-1}+\frac{3}{{\left(x-1\right)}^2}$. The presence of a double factor${\left(x-1\right)}^2$corresponds to the existence of an eigenspace$E$in the vector space${\mathbb{F}}_q^n$of multiplicity 2 and thus an$\alpha -$splitting subspace where the operator$\alpha$is just the linear operator$A-\mathit{\lambda I}$, with$\lambda$the eigenvalue associated to$E$and$A$is the generator matrix of the code. We recall that an$r-$dimensional$W$subspace is$\alpha -$splitting if${\alpha }^{i}W=W$is invariant under the action of any element${\alpha }^i$in the Galois group of the extension${\mathbb{F}}_q\rightarrowtail {\mathbb{F}}_q\left(\alpha \right)$.

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 $G_1$ and $G_2$ of an algebraic curve over ${\mathbb{F}}_q$ with $G_1\le G_2$. Then $\mathcal{L}\left(G_1\right)$ is a subspace of the vector space $\mathcal{L}\left(G_2\right)$ over ${\mathbb{F}}_q$. If we choose a basis of $\mathcal{L}\left(G_2\right)$, then the coordinate vectors of the elements of $\mathcal{L}\left(G_1\right)$ form a linear code over ${\mathbb{F}}_q$ of length $n=dim\left(\mathcal{L}\left(G_2\right)\right)$ and dimension $k=dim\left(\mathcal{L}\left(G_1\right)\right)$. 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$\chi$defined over${\mathbb{F}}_q$by the following equation$y^q-y=x^{q_0}\left(x^q-x\right)$with$q=2q_0^2\ge 8$and$q_0=2^r$. This curve has exactly$q^2+1-$rational places with a single place at infinity$P_{\infty }$and it is of genus$g_S=q_0\left(q-1\right).$ We construct a code out of the divisor $F={\mathit{mP}}_{\infty }$and$Q$where$Q=P_1+\dots +P_{q^2}$is the sum of the$q^2-$rational points and the parameter$m$satisfies the bound$m>2g-2$and$g$is the genus of the curve.

Observe that the geometric Goppa code $\mathbf{C}\left(F,Q\right)$ is an ${\mathbb{F}}_q$-subspace of ${\left({\mathbb{F}}_q\right)}^{q^2}$ and its dimension $k$ as an ${\mathbb{F}}_q-$vector space is the dimension of the code. Geometrically, it corresponds to a point in the Grassmannian ${\mathcal{G}}_{q^2,k}\left({\mathbb{F}}_q\right)$. The set of codewords recognised by the code $\mathbf{C}\left(F,Q\right)$ admits the following description in terms of monomial ideals in the variables $x,y,z,w$:

$$\left\{x^a{y}^b{z}^c{w}^{d^{\prime }}|a,b,c,d^{\prime }\ge 0,\mathit{aq}+b\left(q+q_0\right)+c\left(q+2q_0\right)+d^{\prime }\left(q+2q_0+1\right)\le d\right\},$$

where $z=x^{2q_0+1}$ and $w={\mathit{xy}}^{2q_0}-z^{2q_0}$ are elements in the function field $F_{\chi }≔{\mathbb{F}}_q\left(x,y\right)$ over ${\mathbb{F}}_q$. Moreover, it is a generating set for the linear series $\mathcal{L}\left({\mathit{dP}}_{\infty }\right)$ associated to the divisor ${\mathit{dP}}_{\infty }$.

Theorem 2.5. Cyclic codes are function field codes constructed over the curve${\mathcal{C}}_{n,m}$with affine equation$y^m+x^n=1$defined over a finite field${\mathbb{F}}_q$of$q$elements, where$q$is a power of a prime$p$and$n,m$are integer numbers greater or equal than 2.

Proof. Let us assume $n$ is an integer even number, thus $n=2^k\cdot s$, with $s$ an integer odd number. We recall that a linear cyclic code is an ideal in the ring ${\mathbb{F}}_q\left[x\right]/\left(x^n-1\right)$ generated by a polynomial $g\left(x\right)$ with roots in the splitting field ${\mathbb{F}}_q^l$ of $x^n-1$, where $n\mid q^l-1$. If we consider the factorisation of the polynomial $x^n-1$ over ${\mathbb{F}}_p\left[x\right]$, we get $\left(x^{n/2}-1\right)\left(x^{n/2}+1\right)=$$\left(x^{n/4}-1\right)\left(x^{n/4}+1\right)\left(x^{n/2}+1\right)=\left(x^{n/2^k}-1\right)\left(x^{n/2^k}+1\right)\left(x^{n/2^{\left(k-1\right)}}-1\right)\left(x^{n/2^{\left(k-1\right)}}+1\right)\dots \left(x^{n/2}+1\right)$. We see that the point $P_0=\left(\alpha ,0\right)\in \mathbb{P}\left({\mathbb{F}}_q^2\right)$ with ${\alpha }^{n/2}=p-1$ is an ${\mathbb{F}}_{q^2}-$rational place of the affine curve $y^m=\left(x^{n/2}+1\right)$. The other rational places are $P_k=\left(\beta ,0\right)$ with ${\beta }^{n/2^k}=p-1$,..., $P_2=\left({\beta }^2,0\right)$, $P_1=\left(1,0\right)$, $P_0=\left(-1,0\right)$ and the place $P_{\infty }=\left(0,\alpha \right)$ at $\infty$. The cyclic code is realised as the algebraic geometric code associated to the divisors $D=P_0+P_1+\dots +P_k$, $G=\mu P_{\infty }$ and the parameter $\mu$ satisfies the bound $\mu >2g-2$, where $g$ is the genus of the curve ${\mathcal{C}}_{n,m}$. Note that $m$ is the least integer such that $n\mid p^m-1$. In particular $\alpha$ is a generator of ${\left({\mathbb{F}}_p\right)}^m$.

If $n$ is an integer odd number, by Theorem 2.3, we know there is a set of roots ${\left\{{\alpha }^j\right\}}_{j\in J}$, such that $\alpha$ is a generator of $\left({\mathbb{F}}_{p^m}\right)$. Now we consider the points $P_j=\left({\alpha }^j,0\right)$ with $j\in J$ and the point $P$ at $P_{\infty }=\left(0,\alpha \right)=\infty$, and the cyclic code is realised as the function field code associated to the divisors $D={\sum }_{j\in J}{P}_j$ and $\mu P_{\infty }$. $\square$

Remark 2.6. The proof given in theorem gives a realisation of cyclic codes as AG codes constructed over the curve with affine model$y^m+x^n=1$. In particular when$m=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 $x^n-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 $\alpha$ be a primitive element of the underlying vector space over ${\mathbb{F}}_q$. Since the base field is of characteristic $p$, $x^n-1$ has $n$ different zeroes. Let ${\overline{\mathbb{F}}}_q\left[x\right]$ be the extension field containing the $n^{\mathit{th}}$ roots of unity $1,\alpha ,\dots ,{\alpha }^{n-1},$ where ${\alpha }^{n-1}+{\alpha }^{n-2}+\dots +\alpha +1=0$. Moreover the set $\left\{1,\alpha ,\dots ,{\alpha }^{n-1}\right\}$ constitutes a basis over the prime field ${\mathbb{F}}_p$, and the field extensions ${\mathbb{F}}_{p^n}\cong {\mathbb{F}}_p\left[x\right]/\left(x^{n-1}+\dots +x+1\right)$ are isomorphic.

Example 3. The polynomial$x^2+x+1$over${\mathbb{F}}_p\left[x\right]$is irreducible, thus the fields${\mathbb{F}}_{p^2}\cong {\mathbb{F}}_p\left[x\right]/\left(x^2+x+1\right)$are isomorphic, and the roots$w,w+1$correspond to one place of degree 2 in the extension field${\mathbb{F}}_p\left(w\right)$.

Example 4. We define the polynomials$f\left(x\right)=x^n+a_1{x}^{n-1}+\cdots +a_n$, with$a_i\in \mathbb{Q}$, and$f\left(x,t\right)=f\left(x\right)-t$. Then, if$f$is a separable polynomial, then the Galois group of$f\left(x,t\right)$over$\mathbb{Q}\left(t\right)$is a regular extension with Galois group$S_n$.

Observe that $\mathbb{Q}\left(x_1\dots ,x_n\right)$ is the function field of an $\left(n-1\right)-$dimensional projective space ${\mathbb{P}}^{n-1}\left(\mathbb{Q}\right)$ over $\mathbb{Q}$. Suppose that $z_1,\dots ,z_n$ are the roots of $f$ in a splitting field of $f$ over $\mathbb{Q}$. Each coefficient $a_i$ of $x^i$ in $f$ is symmetric in $z_1,\dots ,z_n$, thus by the theorem on symmetric functions, we can write $a_i$ as a symmetric polynomial in $z_1,\dots ,z_n$ with rational coefficients. On the other side, for a permutation $\sigma \in S_n$, set $E_{\sigma }=x_1{z}_{\left(\sigma \left(1\right)\right)}+\cdots +x_n{z}_{\left(\sigma \left(n\right)\right)}$ in $\mathbb{Q}\left(x_1\dots ,x_n\right)$ and $f\left(x\right)={\prod }_{\sigma }\left(x-E_{\sigma }\right)$, where $\sigma$ runs through all permutations in $S_n$.

Theorem 2.7. (Hilbert) Let$G=S_n$be acting on$\mathbb{Q}\left(x_1,\dots ,x_n\right)$. The field$E$of$S_n-$invariants is$\mathbb{Q}\left(t_1,\dots ,t_n\right)$, where$t_i$is the$i^{\mathit{th}}$symmetric polynomial in$x_1,\dots ,x_n$and$\mathbb{Q}\left(x_1,\dots ,x_n\right)$has Galois group$S_n$over$E$. It is the splitting field of the polynomial$f\left(x\right)=x^n-t_1{x}^{n-1}+\dots +{\left(-1\right)}^n{t}_n.$

Let $F$ be a finite field such that $\left(\mathit{char}F,n\right)=1$. A non-zero polynomial in $\overline{\mathbb{F}}\left[x,y\right]$ defines a curve on the plane ${\overline{\mathbb{F}}}^2$. The elliptic curves are curves of the form $y^2=f\left(x\right)$, where $f\left(x\right)$ is a polynomial of degree 3 with coefficients in $\overline{\mathbb{F}}$.

Proposition 2.8. Let$n=rs$be a factorisation of an integer positive number$n$into irreducible coprime factors and assume$r<s$, then there is a sequence of field extensions${\mathbb{F}}_{q^r}\subset {\mathbb{F}}_{q^s}\subset {\mathbb{F}}_{q^n}$.

Proof. Consider the map $T_n:F^n\mapsto F^n$

$$t_j={\left(-1\right)}^j{\sigma }_j\left(x_1,\dots ,x_n\right),$$

where ${\sigma }_j$ is the jth elementary symmetric function in the variables $x_i$. Thus $\left\{t_j,j=1,\cdots n\right\}$, are the coefficients of the equation:

$$f\left(z,t_1,\dots ,t_n\right)=z^n+\left(-1\right)t_1{z}^{n-1}+\cdots +{\left(-1\right)}^n{t}_n=\left(z-x_1\right)\left(z-x_2\right)\cdots \left(z-x_n\right).$$

If we apply Theorem 2.7 to the $i^{\mathit{th}}$ elementary symmetric polynomial in the symbols $\alpha ,{\alpha }^q,{\alpha }^{q^2},\dots ,{\alpha }^{q^n}$, we get that the field of $S_n$ invariants of the polynomial $f\left(z,t_1,\dots ,t_n\right)$ contains an extension ${\mathbb{F}}_{q^n}$ of ${\mathbb{F}}_q$. Moreover, for any divisor $r$ of $n$, one can consider the field of $S_r$ invariants, and apply Theorem 2.7 to the symbols $\alpha ,{\alpha }^{q^{2s}},\dots ,{\alpha }^{q^{\mathit{rs}}}$, where $n=\mathit{rs}$. Then we get an extension ${\mathbb{F}}_{q^s}$ of ${\mathbb{F}}_{q^r}$ and all its ${\mathbb{F}}_q$-subspaces are stable under $\mathit{Gal}\left({\mathbb{F}}_{q^s}/{\mathbb{F}}_{q^r}\right)$. $\square$

Example 5. Assume$n=q+1$and we study again the roots of the polynomial$x^q-1$in its splitting field. Let$\xi$be a non-trivial n-root of unity, for any divisor$r$of$n$, one can consider the symbols${\xi }^{q^r},\dots ,{\xi }^q,\xi$. The field of$S_r$invariants of the polynomial$f\left(z,t_1,\dots ,t_r\right)$is the set of solutions to the equation:

$$x^{q^r}+\dots +x^q+x=a\mathit{\text{in}}{\mathbb{F}}_{q^n}.$$E2

In ${\mathbb{F}}_{2^n}$, for any divisor $d$ of $n$, there are exactly $2^{d-1}$ solutions to Eq. (2) if $n/d$ is odd and $2^d$ 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\le k\le n$, we consider the partition $\left(k,n-k\right)$ of $n$. Fix two elements $g_1,g_2\in \mathit{GL}\left(n,q\right)$ of rank $k$ and rank $n-k$. These points correspond to linear transformations $T_{g_i}:{\mathbb{F}}_{q^n}\to {\mathbb{F}}_{q^n}$, $i\in 1,2$. It is well known that the corresponding points ${\mathbb{F}}_{q^k,q^n}\subset {\mathbb{F}}_{q^n}$ and ${\mathbb{F}}_{q^{n-k},q^n}\subset {\mathbb{F}}_{q^n}$ in the Grassmannians ${\mathcal{G}}_{k,n}\left({\mathbb{F}}_q\right)$ of $k-$dimensional subspaces and the Grassmannian ${\mathcal{G}}_{n-k}\left({\mathbb{F}}_q\right)$ of $n-k$ dimensional subspaces respectively are dual subspaces in the underlying vector space ${\left({\mathbb{F}}_q\right)}^n$ 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 $G_1$ and $G_2$ respectively are dual codes. Namely, given a linear $\left[n,k\right]$-code, a parity check matrix for $C$ is an $\left(n-k\right)\times n$ matrix $H$ of rank $n-k$ such that $C=\left\{x\in {\left({\mathbb{F}}_q\right)}^n:{\mathit{Hc}}^T=0\right\}$. Then the dual code $C^{\perp }$ is the linear $\left[n,n-k\right]$ code generated by the parity check matrix of $C$. There is a right action of the general linear group $\mathit{GL}\left(n,{\mathbb{F}}_q\right)$ on ${\mathcal{G}}_{k,n}\left({\mathbb{F}}_q\right)$:

$${\mathcal{G}}_{k,n}\left({\mathbb{F}}_q\right)\times \mathit{GL}\left(n,{\mathbb{F}}_q\right)\to {\mathcal{G}}_{k,n}\left({\mathbb{F}}_q\right)$$E3

$$\left(\mathcal{U},A\right)\to \mathcal{U}A.$$E4

One can study the orbits of ${\mathcal{G}}_{k,n}\left({\mathbb{F}}_q\right)$ by the action of any subgroup in the general linear group $\mathit{GL}\left(n,{\mathbb{F}}_q\right)$. For example we can study the orbit of any triangle group: the Klein group ${\mathrm{\mathbb{Z}}}_2\times {\mathrm{\mathbb{Z}}}_2$, the dihedral group, the alternated groups $A_4$ and $A_5$ or the symmetric group $S_n$. Take as $T$ the standard shift operator on ${\mathbb{F}}_q^n$, a linear code $C$ is said to be quasi-cyclic of index $l$ or $l-$quasi-cyclic if and only if is invariant under $T^l$. 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 $\left(c_0,c_1,\dots ,c_{n-1}\right)$ of $C$ as a polynomial $c_0+c_{1}x+\dots +c_{n-1}{x}^{n-1}\in {\mathbb{F}}_q\left[x\right]$, then $T\left(c\left(x\right)\right)=x\cdot c\left(x\right)mod\left(x^n-1\right)$.

Example 6. We study the action of a rotation element on the Grassmannian${\mathcal{G}}_{2,4}\left({\mathbb{F}}_q\right)$of lines in a 3-dimensional projective space$\mathit{PG}\left(3,q\right)$. We apply to any line$g$a rotation$\tau$of angle$\alpha =\frac{2\pi }{n}$, represented by the array of vectors$<\left(\mathrm{1,0,0}\right),\left(0,\mathit{cos}\left(\alpha \right),\mathit{sin}\left(\alpha \right)\right),\left(0,-\mathit{cos}\left(\alpha \right),\mathit{sin}\left(\alpha \right)\right)>$. It is easy to see that the orbit code by the composed action${\tau }^m$with$m$divisor of$n$is a quasi-cyclic code of index$\frac{m}{n}$.

In general, we study generalised Grassmannians or more commonly known as flag varieties. Fix a partition $\lambda =\left({\lambda }_1,\dots ,{\lambda }_r\right)$ of $n$ and let ${\mathcal{F}}_{\lambda }={\mathcal{F}}_{\lambda }\left({\mathbb{F}}_q\right)$ be the variety of partial flags of ${\mathbb{F}}_q-$vector spaces

$$\left\{0\right\}=E^r\subset E^{r-1}\subset \dots \subset E^1\subset E^0={\left({\mathbb{F}}_q\right)}^n$$

such that $dim\left(E^{i-1}/E^i\right)={\lambda }_i$. The group $\mathit{GL}\left(n,{\mathbb{F}}_q\right)$ acts on ${\mathcal{F}}_{\lambda }$ in the natural way. Fix an element $X_0\in {\mathcal{F}}_{\lambda }$ and denote by ${\mathcal{P}}_{\lambda }$ the stabilizer of $X_0$ in $G$ and by ${\mathcal{U}}_{\lambda }$ the subgroup of elements $g\in {\mathcal{P}}_{\lambda }$ which induces the identity on $E^i/E^{i+1}$ for all $i=0,1,\dots ,n-1$. Put ${\mathcal{L}}_{\lambda }={\mathit{GL}}_{{\lambda }_r}\left({\mathbb{F}}_q\right)\times \dots ,\times {\mathit{GL}}_{{\lambda }_1}\left({\mathbb{F}}_q\right)$, then we have ${\mathcal{P}}_{\lambda }={\mathcal{L}}_{\lambda }\times {\mathcal{U}}_{\lambda }$.

Proposition 2.9. Let us consider the factorisation of$n$into irreducible pairwise coprime factors$n=p_1^{e_1}{p}_2^{e_2}\cdots p_r^{e_r}$with$e_1<e_2<\dots <e_r$, and$\lambda =\left(e_1,\dots ,e_r\right)$be the partition of exponents. Then there is a flag variety${\mathcal{F}}_{\lambda }\left({\mathbb{F}}_q\right)$of partial flags of${\mathbb{F}}_q-$vector spaces:

$$\left\{0\right\}=E^r\subset E^{r-1}\subset \cdots \subset E^1\subset E^0={\left({\mathbb{F}}_q\right)}^n,$$

such that $\mathit{dim}\left(E^{i-1}/E^i\right)=e^i$.

Proof Observe that the result follows trivially for the case in which $n$ is a prime number $e_1=\cdots =e_r=1$. If $n=rs$ factorizes into two irreducible prime factors, the result follow as we have seen above, there is a flag $\left\{0\right\}=E^r\subset E^s\subset E^0={\left({\mathbb{F}}_q\right)}^n$ and then by induction in $r$ the result follows. $\square$

Given a cyclic code over $\overline{F}$ of length $n$, its defining set is given by the exponents occurring in $g\left(x\right)$, where $g\left(x\right)$ is the generator polynomial of the ideal of the code in $F\left[x\right]/\left(x^n-1\right)$.

Let $\alpha \in \overline{F}$ be an $n^{\mathit{th}}$ primitive root of unity. The $n^{\mathit{th}}$ cyclotomic polynomial ${\mathrm{\Phi }}_n\left(x\right)={\prod }_{1<j<n,\left(j,n\right)=1}\left(x-{\alpha }^j\right)\in \overline{F}\left[x\right]$ is the minimal polynomial of $\alpha$ over $F$. It is monic of degree of the Euler’s totient function $\phi \left(n\right)$. It has integer coefficients and it is irreducible over $\mathbb{Q}$. In $\mathbb{Q}\left[x\right]$, we have the factorization into irreducible polynomials:

$$x^n-1=\prod _{d\mid n}{\mathrm{\Phi }}_d\left(x\right).$$

By Möebius inversion:

$${\mathrm{\Phi }}_n\left(x\right)=\prod _{d\mid n}{\left(x^d-1\right)}^{\mu \left(n/d\right)}$$

In the case of binary codes where $q=2$, Bezzateev and Shekhunova [8] have obtained that the number of irreducible normalized polynomials $I_{2^m}\left(l\right)$ of degree $l$ over ${\mathbb{F}}_{2^m}$ satisfy the following equation:

$$I_{2^m}\left(l\right)=\frac{1}{l}\sum _{d/l}\mu \left(d\right)2^{m\frac{l}{d}}.$$E5

where $\mu \left(d\right)$ is the Möebius function:

$$\mu \left(d\right)=\left\{\begin{array}{r}1\mathit{\text{if}}d=1;\\ {\left(-1\right)}^r\mathit{\text{if}}d\mathit{\text{is}}a\mathit{\text{product}}\mathit{\text{of}}r\mathit{\text{different}}\mathit{\text{prime}}\mathit{\text{numbers}};\\ 0\mathit{\text{in}}\mathit{all}\mathit{\text{other}}\mathit{\text{cases}}.\end{array}\right.$$

Let $g\left(x\right)$ equals the least common multiple $\mathit{lcm}\left\{{\mathrm{\Phi }}_i\left(x\right):{\alpha }^i\in S\right\}$, then $S$ is a defining set for $C$. We will describe the defining set by the exponents occurring in $S$ with $S=\left\{i_1,i_2,\dots ,i_l\right\}$, where $i_1<\dots <i_l$. A parity check matrix for the code $C\left(S\right)$ is given by:

$$M\left(S\right)=\left(\begin{array}{cccc}{\left({\alpha }^{i_1}\right)}^0& {\left({\alpha }^{i_1}\right)}^1& \cdots & {\left({\alpha }^{i_1}\right)}^{n-1}\\ {\left({\alpha }^{i_2}\right)}^0& {\left({\alpha }^{i_2}\right)}^1& \cdots & {\left({\alpha }^{i_2}\right)}^{n-1}\\ ⋮& & ⋮& \\ {\left({\alpha }^{i_r}\right)}^0& {\left({\alpha }^{i_r}\right)}^1& \cdots & {\left({\alpha }^{i_r}\right)}^{n-1})\end{array}\right)$$

The code $C\subset F^n$ is obtained as the subfield subcode of $\overline{C}$:

$$C=\left\{c\in F^n:M\left(R\right)c^T=0\right\}.$$

Given a triple $\left(I,J,K\right)$ of subsets of $\left\{1,\dots ,n\right\}$ of the same cardinality $r$, we associate to them partitions $\lambda ,\mu$ and $\nu$ as follows. Let $I=\left\{i_1<\dots <i_r\right\}\subset \left\{1,\dots ,n\right\}$, then the corresponding partition is defined as $\lambda =\left(i_r-r,\dots ,r_1-1\right)$, and respectively for $J,K$. We call the triple $\left(I,J,K\right)$ admissible for the Horn problem, if the corresponding triple of partitions $\left(\lambda ,\mu ,\gamma \right)$ 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 $\left(I,J,K\right)\subset \left\{0,1,\dots ,n\right\}$.

$$U_r^n=\left\{\left(I,J,K\right)|\sum _{i\in I}i+\sum _{j\in J}j=\sum _{k\in K}k+r\left(r+1\right)/2\right\},$$

$$T_r^n=\{\left(I,J,K\right)\in U_r^n\mid \mathit{\text{for}}\mathit{all}p<r\mathit{\text{and}}\mathit{all}\left(F,G,H\right)\in T_p^r,$$

$$\sum _{f\in F}{i}_f+\sum _{g\in G}{j}_g\le \sum _{h\in H}{k}_h+p\left(p+1\right)/2\}.$$

Example 7. Let us consider the triple of subsets

$$\left(I,J,K\right)=\left(\left\{\mathrm{1,3,5}\right\},\left\{\mathrm{1,3,5}\right\},\left\{\mathrm{2,4,6}\right\}\right)$$

and the corresponding triple of partitions $\left(\lambda ,\mu ,\nu \right)=\left(\left(\mathrm{2,1,0}\right),\left(\mathrm{2,1,0}\right)\left(\mathrm{3,2,1}\right)\right)$ arises from the triple of diagonal 3 by 3 matrices with diagonal entries $\left(\mathrm{2,1,0}\right),\left(\mathrm{1,0,2}\right)$ and $\left(\mathrm{3,1,2}\right)$.

Lemma 2.10. For any triple$\left(I,J,K\right)$admissible for the Horn problem, the polynomials defined by$f\left(x\right)={\prod }_{i\in I}\left(x-{\alpha }^i\right),g\left(x\right)={\prod }_{j\in J}\left(x-{\alpha }^j\right),$and$h\left(x\right)={\prod }_{k\in K}\left(x-{\alpha }^k\right)$generate a cyclic code of length$n=i_r+j_r+k_r\mathit{mod}p$and$k=r$, where$r=\mid I\mid +\mid J\mid +\mid K\mid$and$p$is the characteristic of the field$F$.

Proof. The cyclic code generated by $f\left(x\right)$ coincides with the cyclic code generated by $\mathit{lcm}\left\{m_i\left(x\right):{\alpha }^i,i\in I\right\}$ and respectively for $g\left(x\right)$ and $h\left(x\right)$ the polynomials $\mathit{lcm}\left\{m_j\left(x\right):{\alpha }^j,j\in J\right\}$ and $\mathit{lcm}\left\{m_k\left(x\right):{\alpha }^k,k\in K\right\}.$ It is the cyclic code generated by the minimal polynomial of ${\alpha }^{i_r+j_r+k_r}$. $\square$

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 field${\mathbb{F}}_q$with$q=p^r$elements and$p$a prime number as in example (3).

Lemma 2.12. The family of cyclic codes obtained by considering the roots of the polynomial$x^n-1$over its splitting fields are indeed AG codes arising from genus 0 curves, and by Riemann-Roch theorem, their parameters satisfy the bound$d\ge n+1-k$, where$d$is the minimum distance.

Proof Let ${\overline{\mathbb{F}}}_q\left[x\right]$ be the extension field containing the $n^{\mathit{th}}$ roots of unity $1,\alpha ,\dots ,{\alpha }^{n-1},$ where ${\alpha }^{n-1}+{\alpha }^{n-2}+\dots +\alpha +1=0$. Moreover the set $\left\{1,\alpha ,\dots ,{\alpha }^{n-1}\right\}$ constitutes a basis over the prime field ${\mathbb{F}}_p$, and the field extensions ${\mathbb{F}}_{p^n}\cong {\mathbb{F}}_p\left[x\right]/\left(x^{n-1}+\dots +x+1\right)$ are isomorphic. $\square$

2.3 Generating functions of conjugacy classes in a group

The automorphism group of the projective line $\mathbb{P}\left({\mathbb{F}}_q\right)$ is the projective linear group $\mathit{PGL}\left(2,q\right)$. Any finite subgroup $A\subset \mathit{PGL}\left(2,q\right)$ defines a $k-$uniform Cayley (sum) hypergraph ${\mathrm{\Gamma }}^k\left(A\right)$ whose vertices are the generating $k-$tuples of $A$ and the edges are $k-$element sets $\left\{x_1,\dots ,x_k\right\}\in \left(\begin{array}{c}G\\ k\end{array}\right)$ represented by random variables $x_1,\dots ,x_k$. In particular, if $f\left(z\right)$ is the ordinary generating function that enumerates $A$, that is, number of conjugacy classes in $A$, then $\frac{1}{1-f\left(z\right)}$ is the ordinary generating function enumerating sequences of $k$ elements in $A$. If $G$ is an abelian group, then $x_1+\cdots +x_k\in A$. In general, we will consider $k$-arcs in $\mathrm{\Gamma }\left(A\right)$ which represent casual connections between the variables. Applications are known in statistics, for example the multinomial experiment consists of $n$ identical independent trials, and there are $k$ possible outcomes (classes, categories or cells) to each trial and the cell counts $n_1,n_2,\dots ,n_k$ are the random variables, the number of observations that fall into each of the $k-$categories.

Definition 2.13. In$\mathit{PG}\left(n-1,q\right)$a$\left(k;r\right)-$arc is a set of$k$points any$r$of which form a basis for${\mathbb{F}}_q^n$, or in other words,$r-1$of them but not$r$are collinear.

Consider the normal rational curve over ${\mathbb{F}}_q$:

$${\mathcal{V}}_1^n≔\left\{{\mathbb{F}}_q\left(1,x,x^2,\dots ,x^n\right)|x\in {\mathbb{F}}_q\cup \left\{\infty \right\}\right\}$$

is a (q + 1)-arc in the n-dimensional projective space $\mathit{PG}\left(n,q\right)$.

We see that if $q\le n$, the NRC is a basis of a q-dimensional projective subspace, that is, a ${\mathit{PG}}^q\left(n,q\right)$. So we can enumerate how many NRC’s are there in a $\mathit{PG}\left(n,q\right)$. The answer is $\varphi \left(q;n,q\right)$, the number of ways of choosing such a set of points in a particular q-space. If $q\ge n+2$, the NRC is an example of a (q + 1)-arc. It contains q + 1 points, and every set of $n+1$ points are linearly independent.

2.4 Conclusion

The problem of considering finite subgroups and conjugacy classes in $\mathit{PGL}\left(2,q\right)$ the automorphism group of the projective line can be generalised to that of finite subgroups in $\mathit{PGL}\left(n,q\right)$, the collineation group of the normal rational curve.

Acknowledgments

This research has been partially supported by the COST Action IC1104 and the project ARES (Team for Advanced Research on Information Security and Privacy. Funded by Ministry of Economy and Competitivity).