Open AccessArticle

A Topological View of Reed–Solomon Codes

Alberto Besana

and

Cristina Martínez

Department of Physics and Mathematics, University of Alcalá, 28871 Madrid, Spain

Author to whom correspondence should be addressed.

Mathematics 2021, 9(5), 578; https://doi.org/10.3390/math9050578

Submission received: 28 January 2021 / Revised: 21 February 2021 / Accepted: 28 February 2021 / Published: 9 March 2021

(This article belongs to the Special Issue New Trends in Algebraic Geometry and Its Applications)

Download Versions Notes

Abstract

We studied a particular class of well known error-correcting codes known as Reed–Solomon codes. We constructed RS codes as algebraic-geometric codes from the normal rational curve. This approach allowed us to study some algebraic representations of RS codes through the study of the general linear group

G L (n, q)

. We characterized the coefficients that appear in the decompostion of an irreducible representation of the special linear group in terms of Gromov–Witten invariants of the Hilbert scheme of points in the plane. In addition, we classified all the algebraic codes defined over the normal rational curve, thereby providing an algorithm to compute a set of generators of the ideal associated with any algebraic code constructed on the rational normal curve (NRC) over an extension

F_{q^{n}}

F_{q}

Keywords:

2000 mathematics subject classification; 05E10 (primary); 05A15 (secondary); algebraic code; symmetric group; partitions

1. Introduction

Let us denote by

F_{q}

the finite field of q elements with q a power of prime number p. One can consider field extensions

F_{q}

F_{p}

as q varies through powers of the prime p. Any

F_{p^{n}}

field extension of

F_{p}

is a vector space over

F_{p}

of dimension n and an

(n - 1) -

dimensional projective space

P G (n - 1, p)

Let V be an

n + 1

dimensional vector space over the field

F_{q}

; we denote by

P G (n, q)

P (V)

the n-dimensional projective space over V and by

P^{1}

, the projective line. The set of all subspaces of dimension r in V is a Grassmannian, and it is denoted by

G_{r, n} (F_{q})

or by

P G^{r} (n, q)

. The dual of an

r -

space in

P G (n, q)

is an

(n - r - 1) -

space.

Consider the

F_{q} -

rational points of

G_{r, n} (F_{q})

as a projective system; we obtain a q-ary linear code, called the Grassmann code, which we denote

{[n, r]}_{q}

code. The length l and the dimension k of

G (r, n)

are given by the q binomial coefficient

l = {[\begin{matrix} n \\ r \end{matrix}]}_{q} = \frac{(q^{n + 1} - 1) (q^{n + 1} - q) \dots (q^{n + 1} - q^{r})}{(q^{r + 1} - 1) (q^{r + 1} - q) \dots (q^{r + 1} - q^{r})}

, and

k = (\binom{n}{r})

, respectively.

We study the relation between codes constructed from vector bundles and the representation theory of the general linear group

G L (n, F_{q})

. Following [1], we consider the right action of the general linear group

G L (n, F_{q})

G_{k, n} (F_{q})

\begin{matrix} G_{k, n} (F_{q}) \times G L (n, F_{q}) & \to & G_{k, n} (F_{q}) \\ (U, A) & \to & U A . \end{matrix}

(1)

Observe that the action is defined independently of the choice of the representation matrix

U \in F_{q}^{k \times n}

Let

U \in G_{k, n} (F_{q})

and

G < G L (n, F_{q})

be a subgroup; then

C = {U A | A \in G}

is an orbit in

G_{k, n} (F_{q})

of the induced action.

In order to classify all the orbits, we need to classify all the conjugacy classes of subgroups of

G L (n, F_{q})

. In [2], we studied cyclic coverings of the projective line that correspond to orbits defined by a cyclic subgroup of order p as the multiplicative group of

p^{t h}

roots of unity or the additive group of integers modulo p for some prime number p. In particular, we showed that any irreducible cyclic plane cover of the projective line can be given by a prime ideal

(y^{m} - {(x - a_{1})}^{d_{1}} \dots {(x - a_{n})}^{d_{n}}) \subset F_{q} [x, y] .

This ideal defines an affine curve in

A^{2} (F_{q})

which has singularities, if

d_{k} > 1

for some

1 \leq k \leq n

. There exists a unique projective curve birationally equivalent to this affine curve obtained by homogenization of the polynomial. Here we study the connection between ideal sheaves on

F_{q} [x, y]

and its numerical invariants together with the combinatorics of partitions of n and the representation theory of the general linear group

G L (F_{q}, n)

. In other words, we want to understand which subspaces are invariant by the action of elements of the general linear group or finite subgroups of

G L (n, F_{q})

and how the

G L (n, F_{q})

group’s action on the Grassmannian changes the Grassmann code, as this action simply permutes basis elements of the Grassmann code.

When one considers as an alphabet a set

P = {P_{1}, \dots, P_{N}}

F_{q} -

rational points lying on a smooth projective curve defined over a finite field, algebraic codes are constructed by evaluation of the global sections of a line bundle or a vector bundle on the curve. Any cyclic cover of

P^{1}

which is simply ramified corresponds to an unordered tuple of n points on

P^{1}

. More generally, in Section 4 we consider configurations of n points in a

d -

dimensional projective space

P G (d, q)

which generically lies on a rational normal curve (NRC) and we study the algebraic codes defined on it, providing a complete classification in terms of divisors defined over the NRC; see Theorem 2. These are the so called Reed–Solomon codes. Moreover, in the last section as an application of the Horn problem, we provide a set of generators of the ideal associated with any algebraic code constructed on the NRC over an extension

F_{q}^{n}

F_{q}

From now on,

F_{q}

will be a field with

q = p^{n}

elements and

C

a non-singular, projective, irreducible curve defined over

F_{q}

with q elements.

Notation

For d a positive integer,

α = (α_{1}, \dots, α_{m})

is a partition of d into m parts if the

α_{i}

are positive and decreasing integers summing to n. We will denote as

P (d)

the set of all partitions of d. We set

l (α) = m

for the length of

α

, that is, the number of cycles in

α

, and

l_{i}

for the length of

α_{i}

. The notation

(a_{1}, \dots, a_{k})

stands for a permutation in

S_{d}

that sends

a_{i}

a_{i + 1}

. For

λ \in P (d)

, we write

[λ]

for the corresponding character of

S_{n}

. We write

P G L (2, k) = G L (2, k) / k^{*}

, where k is field of arbitrary characteristic and elements of

P G L (2, k)

, which will be represented by equivalence classes of matrices

(\begin{matrix} a & b \\ c & d \end{matrix})

, with

a d - b c \neq 0

. A

q -

ary constant weight code of length n, distance d and weight w will be denoted as an

{[n, d, w]}_{q}

code.

2. Horn Problem: An Application to Convolutional Codes

In this section we present a description of the Horn problem, i.e., the study of the eigenvalues of the sum

C = A + B

of two matrices, given the spectrum of A and B, in the context of polynomial matrices with polynomial entries associated with torsion modules or dually submodules of a polynomial ring with coefficients in a field. Next, we introduce some important matrices that define a linear error-correcting code.

Let R be any complete valued field R with a closed coefficient field k of an arbitrary characteristic, for example, a finite field or the ring

R = C {x}

of convergent power series. If

f \in R

is a nonzero divisor, then we define the encoder A as the matrix associated with the corresponding torsion module

R / f R

. The matrix A can be diagonalized by elementary row and column operations with diagonal entries

x^{α_{1}}, x^{α_{2}}, \dots, x^{α_{n}}

, for unique non-negative integers

α_{1} \geq \dots \geq α_{n}

. More precisely, these matrices are in correspondence with endomorphisms of

R^{n},

with cokernels being torsion modules with at most n generators. Such a module is isomorphic to a direct sum

R / x^{α_{1}} R \oplus R / x^{α_{2}} R \oplus \dots \oplus R / x^{α_{n}} R, α_{1} \geq \dots \geq α_{n} .

The set

(α_{1}, \dots, α_{n})

of invariant factors of A defines a partition

α

of size

d = | λ |

. Reciprocally, when

R = C {x}

is the ring of convergent power series, any partition

λ

defines a rank one torsion-free sheaf on

C

by setting

I_{λ} = (x^{λ_{1}}, x^{λ_{2}}, x^{λ_{3}}, \dots, x^{λ_{n}})

. In particular, the ideal sheaf corresponding to the identity partition

{(1)}^{n}

, defines a maximal ideal

I_{{(1)}^{n}} = (x, \overset{n t i m e s}{\overset{︷}{\dots}}, x)

C [x]

. The Horn problem is then equivalent to the following question: which partitions

α, β, γ

can be the invariant factors of matrices

A, B

and C if

C = A \cdot B

In the case of convergent power series, this problem was proposed by I. Gohberg and M.A. Kaashoek. By denoting the cokernels of

A, B

and C as

A, B

and

C

, respectively, one has a short exact sequence:

0 \to A \to B \to C \to 0,

i.e.,

B

is a submodule of

C

with

C / B ≅ A

; such an exact sequence corresponds to matrices

A, B

and C with

A \cdot B = C

If we specialize C to be the identity matrix I, by the correspondence between partitions and ideal sheaves above, the invariant factors of the identity matrix are defined by the partition

{(1)}^{n}

, then the question becomes: which partitions

α, β

can be the invariant factors of matrices A, B if

A \cdot B = I

? The case of interest for us will be the case in which R is an

F_{q} [x]

-module with q a prime power of p.

Duly, the code can be defined as an

R -

submodule of

R^{n}

, where

R = F [z]

is a polynomial ring with coefficients in a field

F

and z is a uniformizing parameter in R (see [3]). When

F

is a finite field, these are known as convolutional codes which have been very well studied; see, for example, [4]. A full row rank matrix

G (z) \in F {[z]}^{k \times n}

with the property that

C = {Im}_{F [z]} G (z) = {f (z) g (z) : f (z) \in [F^{k} (z)]}

is called a generator matrix. The degree d of a convolutional code

C

is the maximum of the degrees of the determinants of the

k \times k

submatrices of one, and hence any generator matrix of

C

. The main difference between block and convolutional codes is that at the encoder, in a convolutional code we may have different states. Linear block codes may be considered as a particular case of convolutional codes with only one state. In next section we describe an example of block codes known as Reed–Solomon codes.

Remark 1.

The set of convolutional codes of a fixed degree is parametrized by the Grothendieck Quot scheme of degree d, rank

n - k

coherent sheaf quotients of

O^{n}

on a curve X defined over

F

. If the degree is zero, these schemes describe a Grassmann variety and constitute the so called class of block codes of parameters

(n, k)

. Namely, the space of all matrix divisors

D_{k} (r, d)

of rank r and degree d can be identified with the set of rational points of

{Quot}_{O_{X} {(D)}^{n} / X / k}^{m}

parametrizing torsion quotients of

O_{X} {(D)}^{n}

and having degree

m = r \cdot deg D - d

, see [5].

An Example with Algebraic-Geometric Codes: Reed–Solomon Codes

Let X be a smooth projective curve defined over a finite field

F_{q}

with q elements. The classical algebraic-geometric (AG) code due to Goppa is defined by evaluating rational functions associated with a divisor D at a finite set of

F_{q}

-rational points. From another point of view, we are considering the evaluation of sections of the corresponding line bundle

O_{X} (D)

on X. Namely, let

P : = {P_{1}, \dots, P_{n}}

be a configuration of distinct

F_{q}

-rational points of X, the usual algebraic-geometric code is defined to be the image of the evaluation map:

\begin{matrix} φ_{D} : L (D) \to F_{q}^{n} \\ f \mapsto (f (P_{1}), \dots, f (P_{n})), \end{matrix}

(2)

where

L (D)

denotes the vector space of sections associated with the line bundle

O_{X}

. The parameters of these codes, the length n, the dimension k and the minimum distance d are determined by the theorem of Riemann-Roch and it is easy to see that they satisfy the following bound

k + d \geq n + 1 - g

, where g is the genus of the curve X. Using this definition, the notion of AG codes is easily generalized for varieties of higher dimension.

Namely, let E be a vector bundle of rank r on X defined over

F_{q}

. The Goppa code

C (X, D, G)

takes as input a divisor D supported on the finite set

P

F_{q}

-rational points and a divisor G associated with the vector bundle E and evaluates each section

σ \in L (G)

in the linear series attached to the divisor G:

C (X, D, G) = {{(σ (P_{i}))}_{i = 1}^{n} : σ \in L (G)} \subseteq F_{q}^{n} .

Observe that

C (X, P, E)

is an

F_{q}

-linear subspace of

F_{q^{r}}^{n}

and thus a point of the Grassmannian

G_{r, n} (F_{q})

. Moreover, for the same subset of evaluation points and any

r \leq k

, we have

G (r, n) \subseteq G (k, n) \subseteq F_{q}^{n}

, where

r \leq k

. Further, we get a partial flag of

F_{q} -

vector spaces

{0} = E^{k} \subset E^{k - 1} \subset \dots \subset E^{1} \subset E^{0} = F_{q}^{n}

such that

\dim (E^{i - 1} / E^{i}) = λ_{i}

, to which we associate the partition

λ = (λ_{1}, \dots, λ_{r})

of n. In this way, each partition

λ

of n determines a variety

F_{λ} = F_{λ} (F_{q})

of partial flags of

F_{q}

-vector spaces.

The representation theory of the special linear group

S L (n, F_{q})

can be viewed as a form of Gale duality first proven by Goppa in the context of algebraic coding theory.

Let D and G be effective divisors supported over a smooth projective curve X defined over

F_{q}

such that

Supp (G) \cap Supp (D) = \emptyset

, then the geometric Goppa code associated with the divisors D and G is defined by

C (D, G) = {(x (P_{1}), \dots, x (P_{n})), x \in L (G)} \subseteq F_{q}^{n},

where

L (G)

denotes the linear system associated with the divisor G.

Definition 1.

Let

C_{1}

and

C_{2}

be the corresponding codes obtained by evaluating non-constant rational functions

f (x)

and

g (x)

with non common roots on X over the support of the divisor D. We define the quotient code of

C_{1}

and

C_{2}

to be the code associated with the quotient rational function

φ = f / g

Since f and g take the value ∞, they are defined by non constant polynomials

f (x)

and

g (x)

\bar{F_{q}} [x]

. Here

\bar{F_{q}}

denotes the algebraic closure of

F_{q}

. The degree of

φ

is defined to be

deg (φ) = \max {deg (f), deg (g)}

φ

is a finite morphism, one may associate to each rational point

x \in X (F_{q})

a local degree or multiplicity

m_{φ} (x)

defined as:

m_{φ} (x) = o r d_{z = 0} ψ (z),

where

ψ = σ_{2} \circ φ \circ σ_{1}

y = φ (x)

, and

σ_{1}, σ_{2} \in P G L (2, F_{q})

such that

σ_{1} (0) = x

and

σ_{2} (y) = 0

With each non-constant rational function

φ

over X, one can associate a matrix A with entries in the ring

F_{q} [x]

. Namely, let us call

f_{0} : = f (x)

and call

f_{1}

the divisor polynomial

g (x)

, and

f_{2}

the remainder polynomial; then by repeated use of the Euclid’s algorithm, we construct a sequence of polynomials

f_{0}, f_{1}, \dots, f_{k}

, and quotients

q_{1}, \dots q_{k}

K \leq n

. Then the quotient matrix A is defined to be the diagonal matrix with entries

q_{1}, \dots, q_{k}

corresponding to the continued fraction expansion of the rational function

φ

Here we include a SAGE code [6] which implements the algorithm.

def euclid(f, g):

r = f % g

q = f // g

while r.degree() >= 0:

yield q

f = g

g = r

r = f % g

q = f // g

Let

λ_{i}

be the partition of the integer k, defining the degree multiplicities of the polynomial

q_{i}

. Then the Horn problem applied to this situation reads:

Which partitions

α, β

and

γ

can be the degree multiplicities of polynomials

q_{A}, q_{B}

and

q_{C}

such that the corresponding diagonal matrices

A, B

, and C satisfy

C = A \cdot B

Another important family of Goppa codes is obtained considering the normal rational curve

C^{n}

defined over

F_{q}

C^{n} : = {F_{q} (1, α, \dots, α^{n}) : α \in F_{q} \cup {\infty}} .

The points are distinct elements of

F_{q}

and L is the vector space of polynomials of degree at most

k - 1

and with coefficients in

F_{q}

. Such polynomials have at most

k - 1

zeros, so nonzero codewords have at least

n - k + 1

non-zeros. Hence, this is a

{[n, k, n - k + 1]}_{q}

code whenever

k \leq n

. Any codeword

(c_{0}, c_{1}, \dots, c_{n - 1})

can be expressed into a q-ary k-vector with respect to the basis

{1, α, \dots, α^{k - 1}}

.These codes are just generalized Reed–Solomon codes of parameters

{[n, k, d]}_{q}

over

F_{q}

with parity check polynomial

h (x) = \prod_{i = 1}^{k - 1} (x - α^{i})

where

α

is a primitive root of

F_{q}

such that

α^{k} = α + 1

. In other words, the GRS code is an ideal in the ring

F_{q} [x] / (x^{k} - x - 1)

generated by a polynomial

g (x)

with roots in the splitting field

F_{q}^{l}

x^{k} - x - 1

, where

k | q^{l} - 1

. Since the NRC is a genus 0 curve, it is easy to see that these codes satisfy the Singleton bound

d \geq n - k + 1

Construction of Reed–Solomon codes over

F_{q}

only employs elements of

F_{q}

, hence their lengths are at most q. In order to get longer codes, one can make use of elements of an extension of

F_{q}

, for instance considering subfield subcodes of Reed–Solomon codes.

As in [2], where we considered a variant of the Horn problem in the context of cyclic coverings of the projective line defined over an arbitrary field k, the problem is reduced to study the representation theory of the general linear group

G L (n, F_{q})

3. Representation Theory of $GL (n, F_{q})$

We focus on Grassman codes

G_{k, n} (F_{q})

that were described in the introduction as

{[n, k]}_{q} -

codes by considering an action (1) of the general linear group

G L (n, q)

on the Grassmannian. The study of the representation theory of

G L (n, q)

will allow us to understand better the orbits of this action that will be characterized in Section 5.

The multiplication in the finite field

F_{q^{n}}

is a bilinear map from

F_{q^{n}} \times F_{q^{n}}

into

F_{q^{n}}

. Thus it corresponds to a linear map from the tensor product

m : F_{q^{n}} \otimes F_{q^{n}} \to F_{q^{n}}

. The symmetric group

S_{n}

acts on

F_{q^{n}}

via the permutation matrix:

\begin{matrix} σ \cdot v_{i} = v_{σ (i)}, v_{i} \in F_{q^{n}} . \end{matrix}

(3)

The d-Veronese embedding of

P^{n} (F_{q})

maps the line spanned by the vector

v \in F_{q^{n}}

to the line spanned by

v^{\otimes d} = v \otimes \dots \otimes v

. Thus the symmetric group

S_{n}

acts diagonally on the basis of simple tensors of

F_{q^{n}}

\begin{matrix} σ \cdot (v_{i_{1}} \otimes \dots \otimes v_{i_{r}}) = v_{σ (i_{1})} \otimes \dots \otimes v_{σ (i_{r})} . \end{matrix}

(4)

For each partition

λ = (λ_{1}, \dots, λ_{k})

we consider its Young diagram. The diagram of

λ

is an array of boxes, lined up at the left, with

λ_{i}

boxes in the

i^{t h}

row, with rows arranged from top to botton. For example,

is the Young diagram of the partition

λ = (5, 3, 3, 1)

with

l (λ) = 4

and

| λ | = 12

. We define the Schur projection:

c_{λ} : ⨂^{d} F_{q^{n}} \to ⨂^{d} F_{q^{n}} .

Let

S_{n}

be the symmetric group of permutations over d elements. Any permutation

σ \in S_{n}

acts on a given Young diagram by permuting the boxes. Let

R_{λ} \subseteq S_{n}

be the subgroup of permutations preserving each row. Let

C_{λ} \subseteq S_{n}

be the subgroup of permutations preserving each column, let

c_{λ} = \sum_{σ \in R_{λ}} \sum_{τ \in C_{λ}} ϵ (τ) σ τ

The image of

c_{λ}

is an irreducible

G L (n, F_{q})

-module, which is nonzero iff the number of rows is less or equal than dim

V_{λ}

. All irreducible

G L (n, F_{q})

-modules can be obtained in this way. Every

G L (n, F_{q}) -

module is a sum of irreducible ones.

In terms of irreducible representations of

G L (n, F_{q})

, a partition

η

corresponds to a finite irreducible representation that we denote as

V (η)

. Since

G L (n, F_{q})

is reductive, any finite dimensional representation decomposes into a direct sum of irreducible representations, and the structure constant

c_{λ, μ}^{η}

is the number of times that a given irreducible representation

V (η)

appears in an irreducible decomposition of the tensor product of the representations

V (λ) \otimes V (μ)

. These are known as Littlewood–Richardson coefficients, since they were the first to give a combinatorial formula encoding these numbers (see [7]). In terms of the Hopf algebra

Λ

of Schur functions, let

s_{λ}

be the Schur function indexed by the partition

λ

, we have

s_{λ} \cdot s_{μ} = \sum_{ν} k_{λ μ}^{ν} s_{ν}

for the product and we get the coefficients

k_{λ μ}^{η}

as the structure constants of the dual Hopf algebra

Λ^{*}

. These are known as Kronecker coefficients (see [8,9]) since they appear as expansion coefficients in the Kronecker product

[λ] [μ] = \sum_{ν} k_{λ μ} [ν]

of characters of the symmetric group

S_{n}

, as the authors proved in Proposition 4.3 of [2]. Recall that the Schur function

s_{λ}

attached to the partition

λ = (λ_{1}, \dots, λ_{n})

of length less or equal than n is defined by the quotient:

s_{λ} (x_{1}, \dots, x_{n}) = \frac{d e t {(x_{i}^{λ_{i} + n - j})}_{1 \leq i, j, \leq n}}{d e t {(x_{i}^{n - j})}_{1 \leq i, j \leq 0}} .

It is a homogeneous polynomial of degree

| λ |

x_{1}, \dots, x_{n}

. It easily seen that

s_{λ} (x_{1}, \dots, x_{n}, 0) = s_{λ} (x_{1}, \dots, x_{n})

. Moreover we can define the Schur function

s_{λ}

as the unique symmetric function with this property for all

n \geq l (λ)

. It is well known that the Schur functions constitute a basis for the ring

Λ

of symmetric functions. In addition, there are at least other three well known bases for the ring

Λ

of symmetric functions. The basis

e_{k}

of k-elementary symmetric functions, the

h_{k}

complete homogeneous symmetric functions of degree k and the power sums

p_{k} = z_{1}^{k} + z_{2}^{k} + \dots

. This has been applied in Reed–Solomon coding, that is, for AG codes defined on the projective line

P^{1}

, as a way to encode information words. Namely, for each codeword

a = (a_{0}, a_{1}, \dots, a_{n})

a_{i} \in F_{q}

, let us define

a_{n + 1} = \sum_{i = 1}^{n} a_{i} \in F_{q}

which is nothing but the first elementary symmetric function

e_{1}

. If we consider the variables

x_{1}, \dots, x_{r}

as a fixed list of nonzero elements in

F_{q}

, then the information word a can be encoded into the codeword

d = (d_{1}, \dots, d_{r})

, where

d_{i} = \sum_{j = 1}^{n} a_{j} x_{i}^{j}

. The secret is

a_{0} = - \sum_{i = 1}^{r} d_{i}

, while the pieces of the secret are the

d_{i} s

3.1. Relation between Littlewood–Richardson Coefficients and Kronecker Coefficients

One can stack Littlewood–Richardson coefficients

c_{λ μ}^{ν}

in a 3D matrix or 3-dimensional matrix. Intuitively a 3D matrix is a stacking of boxes in the corner of a room. The elements of the principal diagonal are called rectangular coefficients and are indexed by triples

(λ, μ, ν) = ((i^{n}), (i^{n}), (i^{n}))

of partitions

(i^{n})

with all their parts equal to the same integer

1 \leq i \leq n

Consider

B

and

C

, two 3D matrices, then we define the product matrix

B \cdot C

as the 3D matrix

B \cdot C = \prod_{ν \in P (n), B^{ν}, C^{ν} \in M_{p (n) \times p (n)} (Q)} B^{ν} \cdot C^{ν} .

Namely, for each index

ν

fixed,

λ

and

μ

run over all partitions

P (n)

of n. Thus the coefficients

{(c_{λ, μ}^{ν})}_{λ, μ \in P (n)}

are encoded in a matrix of order

p (n) \times p (n)

, where

p (n)

denotes the number of unrestricted partitions of n, that is, the number of ways of writing the integer n as a sum of positive integers without regard to order. Thus the product matrix

B^{ν} \cdot C^{ν}

is the standard product of square matrices in

M_{p (n) \times p (n)} (Q)

. In particular, the property of associativity follows easily from the associativity in the vector space

M_{p (n) \times p (n)} (Q)

Proposition 1.

Let

C

be the 3D matrix whose entries are the Littlewood–Richardson coefficients, and

K

the 3D matrix of Kronecker coefficients. Then the matrices are inverse one to each other.

Proof.

Since

c_{λ μ}^{ν}

and

k_{λ μ}^{ν}

correspond to the structure constants of the Hopf algebra of Schur functions and its dual one respectively (see Proposition 4.3 of [2]), and the Hopf algebra of Schur functions is self-dual (see [9]), one gets that the product matrix

C \cdot K

is the identity 3D matrix

I

, that is, the matrix whose rectangular coefficients are identically 1. Thus both matrices are inverse one to each other. □

3.2. The Polytope of Triples $(λ, μ, η)$ for Which $c_{λ, μ}^{η}$ Is Positive

The convex hull in

R^{3}

of all triples

(λ, μ, ν)

with

c_{λ, μ}^{ν} > 0

is the Newton polytope of

f (x, y, z) = \sum_{λ, μ, ν} c_{λ, μ}^{ν} x^{λ} y^{μ} z^{ν} \in C [x, y, z]

. Here

x^{λ}

denotes the monomial

x^{λ_{1}} \dots x^{λ_{n}}

of partition degree

λ

. In particular, when

λ = (1^{r})

, we have

x^{{(1)}^{r}} = e_{r} = \sum_{i_{1} < \dots < i_{r}} x_{i_{1}} \dots x_{i_{r}}

, the

r -

th elementary symmetric function. At the other extreme, when

λ = (r)

we have

x^{(r)} = p_{r} = \sum x_{i}^{r}

, the

r -

power sum. As we have seen in the previous section, it is clear that every symmetric function

f \in Λ

is uniquely expressible as a finite linear combination of the

{(x^{λ})}_{λ \in P}

. Moreover, the following theorem shows that f is the the generating series for the Gromov–Witten invariant

N_{d, g} (λ, μ, ν)

counting irreducible plane curves of given degree and genus g passing through a generic configuration of

3 d - 1 + g

points on

P^{2} (C)

with ramification type at

0, \infty

and 1 described by the partitions

λ, μ

and

ν

and simple ramification over other specified points with

| λ | + | μ | + | ν | = d,

and these have been computed by Fomin and Mikhalkin in [10].

Theorem 1.

The power series

f (x, y, z) = \sum_{λ, μ, ν} c_{λ, μ}^{ν} x^{λ} y^{μ} z^{ν} \in C [x, y, z],

is the generating series for the Gromov–Witten invariants

N_{d, g} (λ, μ, ν)

, counting irreducible plane curves of given degree d and genus g passing through a generic configuration of

3 d - 1 + g

points on

P^{2} (C)

with ramification type at

0, \infty

and 1 described by the partitions

λ, μ

and ν and simple ramification over other specified points with

| λ | + | μ | + | ν | = d

Proof.

Whenever the coefficient

c_{λ, μ}^{ν} > 0

is positive consider the corresponding ideal sheaves

I_{λ}

I_{μ}

and

I_{ν}

C [x, y, z]

associated with the partitions

λ, μ

and

ν

respectively. Each ideal sheaf determines a curve in

C [x, y]

via homogenization of the corresponding monomial ideals. Thus each coefficient represents the number of ideal sheaves on

C^{3}

of colength n and degree d equal to the size of the partition, that is the corresponding 3-point Gromov–Witten invariant

{〈 λ, μ, ν 〉}_{0, 3, d}

of the Hilbert scheme

{Hilb}_{n}

n = 2 d - 1 + | ν | + | μ | + | λ | + g

distinct points in the plane, or the relative Gromov–Witten invariant

N_{d, g} (λ, μ, ν)

counting irreducible plane curves of given degree d and genus g passing through a generic configuration of

3 d - 1 + g

points on

P^{2} (C)

with ramification type at

0, \infty

and 1 respectively, described by the partitions

λ, μ

and

ν

of n (see section 4 of [2]). □

Remark 2.

The Euler characteristic of each ideal sheaf is fixed and coincides with the Euler characteristic χ of the polyhedra described in

R^{3}

by the convex hull of all triples

(λ, μ, ν)

with

c_{λ, μ}^{ν} > 0

, that is, the Newton polytope of

f (x, y, z) = \sum_{λ, μ, ν} c_{λ, μ}^{ν} x^{λ} y^{μ} z^{ν} \in R [x, y, z] .

Thus each coefficient represents the number of ideal sheaves on

C^{3}

of fixed Euler characteristic

χ = n

and degree d equal to the size of the partition, that is the corresponding Donaldson-Thomas invariant of the blow-up of the plane

P^{1} \times (C^{2})

with discrete invariants

χ = n

and degree d.

Remark 3.

The Hilbert scheme

{Hilb}_{n}

of n points in the plane

C^{2}

parametrizing ideals

J \subset C [x, y]

of colength n contains an open dense set in the Zariski topology parametrizing ideals associated with configurations of n distinct points. Moreover there is an isomorphism

{Hilb}_{n} ≅ {(C^{2})}^{n} / S_{n}

. In particular, as we showed in [2], any conjugacy class in the symmetric group

S_{n}

determines a divisor class in the

T -

equivariant cohomology

H_{T}^{4 n} ({Hilb}_{n}, Q)

, for the standard action of the torus

T = {(C^{*})}^{2}

C^{2}

. The

T -

equivariant cohomology of

{Hilb}_{n}

has a canonical Nakajima basis indexed by

P (n)

. The map

λ \to J_{λ}

is a bijection between the set of partitions

P (n)

and the set of

T -

fixed points

{Hilb}_{n}^{T} \subset {Hilb}_{n}

Denote the series

{〈 λ, μ, ν 〉}^{{Hilb}_{n}}

of 3-point invariants by a sum over curve degrees:

{〈 λ, μ, ν 〉}^{{Hilb}_{n}} = \sum_{d \geq 0} q^{d} {〈 λ, μ, ν 〉}_{0, 3, d}^{{Hilb}_{n}} .

Corollary 1.

Let H be the divisor class in the Nakajima basis corresponding to the tautological rank n bundle

O / J \to {Hilb}_{n}

with fiber

C [x, y] / J

over

J \in {Hilb}_{n}

and ν the corresponding partition.Then we can recover inductively in the degree d, all the Littlewood–Richardson coefficients

{(c_{λ, μ}^{ν})}_{λ, μ \in P (n)}

Proof.

The non-negative degree of a curve class

β \in H_{2} ({Hilb}_{n}, Z)

is defined by

d = \int_{β} H

. Then via the identification of

c_{λ, μ}^{ν}

with the 3-point Gromov–Witten invariant

{〈 λ, H, μ 〉}_{0, 3, d}^{{Hilb}_{n}}

where

[λ], [μ]

are the corresponding classes in

H_{T}^{4 n} ({Hilb}_{n}, Q)

associated with the partitions

λ

and

μ

P (n)

, we proceed by induction on the degree d as in section 3.6 of [11]. □

Remark 4.

If we choose the partition ν to be the empty partition ∅, we recover the relative Gromov–Witten invariants

N_{d, g} (λ, μ)

studied by Fomin and Mikhalkin in [10], and by Caporaso and Harris in [12].

4. Configurations of Points over a Normal Rational Curve

In this section, we study codes defined from a linear series attached to a divisor on the normal rational curve NRC or equivalently Goppa codes on

P^{1}

and hence generalized Reed–Solomon codes. Assume V is a vector space of dimension

n + 1

over a field k equipped with a linear action, that is, G acts via a representation

G \to G L (V)

. We denote by

S^{d} V

the d-th symmetric power of V.

Consider the d-Veronese embedding of

P^{n}

\begin{matrix} P V^{*} \to P S^{d} V^{*} \\ v \mapsto v^{d}, \end{matrix}

(5)

mapping the line spanned by

v \in V^{*}

to the line spanned by

v^{d} \in S^{d} V^{*}

. In coordinates, if we choose bases

{α, β}

for V and

{[\frac{n!}{k! (n - k)!}] α^{k} β^{d - k}}

for

S^{d} V^{*}

and expanding out

{(x α + y β)}^{d}

, we see that in coordinates this map may be given as

[x, y] \to [x^{d}, x^{d - 1} y, x^{d - 2} y^{2}, \dots, x y^{d - 1}, y^{d}] .

In particular, the homogeneous coordinate ring for the natural projective embedding of the geometric invariant theory (GIT) quotient

{(P^{d})}^{n} / / S L_{d + 1}

is the ring of invariants for n ordered points in the projective space up to, projectivity, i.e, if one considers the function field

k (x_{1}, \dots, x_{d})

of the projective space

{(P)}^{d}

, the ring of invariants is defined by:

{f \in k (x_{1}, \dots, x_{d}) | \forall σ \in S L_{d + 1}, σ \cdot f = f} .

Generators for this ring are given by tableau functions, which appear in many areas of mathematics, particularly representation theory and Schubert calculus. Consider the hypersimplex:

▵ (d + 1, n) = {(c_{1}, \dots, c_{n}) \in Q^{n} | 0 \leq c_{i} \leq 1, \sum c_{i} = d + 1},

for any

1 \leq d \leq n - 3

and choose a linearization

c \in ▵ (d + 1, n)

, there is a morphism

φ : {\bar{M}}_{0, n} \to {(P^{d})}^{n} / /_{c} S L_{d + 1},

sending a configuration of distinct points on

P^{1}

to the corresponding configuration under the

d^{t h}

Veronese map.

The symmetric power

{Sym}^{n} C_{d}

of the curve

C_{d}

is the quotient of the configuration space

C_{d}^{n}

of n unordered tuples of points on the normal rational curve

C_{d}

by the symmetric group

S_{n}

. Furthermore, we can identify the set of effective divisors of degree d on

C_{d}

with the set of k-rational points of the symmetric power

{Sym}^{n} C

, that is,

{Sym}^{n} C

represents the functor of families of effective divisors of degree n on C.

Lee-Sullivan List-Decoding Algorithm of Reed–Solomon Codes

By definition, the rational normal curve

C_{d}

is the image by the

d -

Veronese embedding of

P V^{*} = P^{1}

where V is a 2-dimensional vector space, therefore it is isomorphic to any curve of genus 0. The action of

P G L (2, k)

P^{d}

preserves the rational normal curve

C_{d}

. Conversely, any automorphism of

P^{d}

fixing

C_{d}

pointwise is the identity. It follows that the group of automorphisms of

P^{d}

that preserves

C_{d}

is precisely

P G L (2, k)

. These codes are just generalized RS codes and they come with efficient decoding algorithms once we choose a metric consistent with channel errors and search of a set of vectors with given metric properties as a correcting code. In particular, these codes are consistent with the Hamming metric ([13,14]). Recall that given two vectors of length n, say U and V, the Hamming distance

d_{H} (U, V)

between U and V is the number of coordinates in which they differ.

Given a

[n, k]

RS code C of length n and dimension k, we call d the minimum (Hamming distance) which attains the Singleton bound

n - k + 1

. We shall identify the code with the set of its codewords. A codeword of C is viewed as a polynomial

c_{0} + c_{1} x + \dots + c_{n - 1} x^{n - 1}

in the

F -

vector space

F [x],

where

F

is a finite field. In the communication process, when a codeword is transmitted, it can be affected by errors and erasures. An error occurs when one codeword component is changed into another field element and an erasure occurs when the received component has an unknown value. The problem of minimum distance decoding is to find, for any given vector v, the set

C_{v}

of all codewords

c \in C

at minimum distance from v. If

C_{v}

contains just one element c, then the sent codeword coincides with the received codeword and no decoding is needed. The codewords of minimum weight are the points lying in the intersection of any line and the curve. K. Lee and M.E. O’Sullivan in [15] describe a list decoding algorithm consisting of two steps: the interpolation step and the root-finding step. Starting with a set of generators of the module induced from the ideal for the n points

{P_{1}, \dots, P_{n}}

, they convert the generators to a Gröbner basis of the module in which the minimal polynomial is found. This results in an efficient algorithm solving the interpolation problem.

Let v be the received vector, and fix n distinct points

α_{1}, \dots, α_{n}

from

F

, for each

1 \leq i \leq n

, let

P_{i}

denote the point

(α_{i}, v_{i})

by Lagrange interpolation we get the polynomial

h_{v} = \sum_{i = 1}^{n} v_{i} h_{i} \in F {[x]}_{n}

, where

h_{i} = \prod_{j = 1}^{n} (x - α_{j})

j \neq i

so that

h_{i} (α_{j}) = 1

j = 1

, and 0 otherwise. Now for

m \geq 1

, we define the ideal

I_{v, m} = {f \in F [x, y] | m u l t_{P_{i}} (f) \geq m for 1 \leq i \leq n} \cup {0} .

For

f \in F [x, y]

and

u \geq 1

, denoted by

d e g_{u} (f)

, the

(1, u) -

weighted degree of f, that is, the variables x and y, are assigned weights 1 and u, respectively, and for a monomial

x^{i} y^{j}

, we define

d e g_{u} (x^{i} y^{j}) = i + u j

The goal of the interpolation step is to find a polynomial in

I_{v, m}

having the smallest

(1, k - 1) -

weighted degree. The codewords of minimum weight are the points lying in the intersection of any line and the curve. Moreover if

w t (v - c) < n - \frac{w}{m}

, where

w = d e g_{k - 1} (f)

and f is the polynomial representing the word c, then the polynomial

h_{c}

is a root of f as a polynomial in y over

F [x]

. Moreover the set of polynomials

{(y - h_{c})}^{i} η^{m - i}, 0 \leq i \leq m

, where

η = \prod_{j = 1}^{n} (x - α_{j})

is a set of generators of

I_{v, m}

Let Q be the minimal polynomial of

I_{v, m}

with respect to the monomial order

>_{k - 1}

F [x, y]

. We can find Q by computing a Gröbner basis of

I_{v, m}

with respect to

>_{k - 1}

. In Appendix A, we provide Horn’s algorithm to compute sets of indices which are admissible for the Horn problem. As a result, we provide a set of generators for the algebraic code induced on the NRC.

Proposition 2.

If we consider the set of orbits of

C_{d}^{n}

by the action of finite subgroups of the symmetric group

S_{n}

, we get all possible divisor classes in the group

{Div}^{n} (C_{d})

of degree n divisors on

C_{d}

Proof.

Since the symmetric group

S_{n}

is generated by 3 elements, a reflection of order 2, a symmetry of order 3 and a rotation of order n, we get all the divisor classes by quotienting the configuration space

C_{d}^{n}

of n points on the normal rational curve, by the cyclic group generated by the rotation, or one of the triangle groups, the dihedral group

D_{n}

, the alternated groups

A_{4}

A_{5}

or the symmetric group

S_{4}

. □

5. Notion of Collinearity on the Normal Rational Curve

A permutation matrix

σ \in G L (n, F_{q})

acts on the Grassmannian by multiplication on the right of the corresponding representation matrix. In particular, we are interested in understanding the orbits by the action of any permutation matrix of

G L (n, F_{q})

and moreover of any subgroup G contained in

G L (n, F_{q})

. Further, it is possible to count the orbits of the action in several cases and this is established by the correspondence given in Theorem 2 between sets of points satisfying certain geometrical conditions and partitions.

Definition 2.

An incidence structure

S

on V is a triple

(P, B, I)

, where

P

is a set whose elements are smooth, reduced points in V,

B

is a set whose elements are subsets of points called blocks (or lines in several specific cases) endowed with a relation of collinearity, and an incidence relation

I \subset P \times B

. If

(P, L) \in I

, then we say that P is incident with L or L is incident with P, or P lies in L or L contains P.

When the collinearity relation is a symmetric ternary relation defined on triples

(p, q, r) \in P \times P \times P

by the geometric condition

(p, q, r) \in B

if either

p + q + r

is the full intersection cycle of

C_{d}

with a k-line

l \subset P^{n} (k)

with the right multiplicities, or else if there exists a k-line

l \subset V

such that,

p, q, r \in l

, then the triple

(p, q, r)

is called a plane section.

For any $(p, q) \in P^{2} (V^{*})$ , there exists an $r \in P (S^{d} V^{*})$ such that $(p, q, r) \in l$ . The triple $(p, q, r)$ is strictly collinear if r is unique with this property, and $p, q, r$ are pairwise distinct. The subset of strictly collinear triples is a symmetric ternary relation. When k is a field algebraically closed of characteristic 0, then r is unique with this property, and we recover the euclidean axioms.
Assume that $p \neq q$ and that there are two distinct $r_{1}, r_{2} \in P$ with $(p, q, r_{1}) \in B$ and $(p, q, r_{2}) \in B$ . Denote by $l = l (p, q)$ the set of all such $r s$ , then $l^{3} \in B$ —that, is any triple $(r_{1}, r_{2}, r_{3})$ of points in which l is collinear. Such sets l are called lines in $B$ .

If V is a 3-dimensional vector space defined over the finite field

F_{p}

, then the projective plane

P^{2} (F_{p})

on V is defined by the incidence structure

P G (2, p) = (P (V), L (V), I)

Definition 3.

A $(k; r)$ -arc $K$ in $P G (2, p)$ is a set of k points such that some r, but not $r + 1$ of them are collinear. In other words, some line of the plane meets $K$ in r points and no more than r points. A $(k; r) -$ arc is complete if there is no $(k + 1; r)$ arc containing it.
A k-arc is a set of k points, such that, every subset of s points with $s \leq n$ points is linearly independent.

Let q denote some power of the prime p and

P G (n, p)

be the n-dimensional projective space

{(F_{p})}^{n + 1} ≅ F_{q}

, where

n \geq 2

. The normal rational curve C is defined as:

V_{1}^{n} : = \{F_{q} (1, x, x^{2}, \dots, x^{n}) | x \in F_{q} ⋃ {\infty}\} .

q \geq n + 2

, the NRC is an example of a

(q + 1) -

arc. It contains

q + 1

rational points, and every set of

n + 1

points are linearly independent. For each

a \in {(F_{p})}^{n + 1}

, the mapping:

F_{p} (x_{0}, \dots, x_{n}) \to F_{p} (a^{0} x_{0}, \dots, a^{n} x_{n}),

describes an automorphic collineation of the NRC.

All invariant subspaces form a lattice with the operations of “join” and “meet”.

For

j \in N

, let

Ω (j) = {m \in N | 0 \leq m \leq n, (\binom{m}{j}) \neq 0 m o d p}

. Given

J \subset {0, 1, \dots, n}

, put

Ω (J) = ⋃_{j \in J} Ω (j), Ψ (J) : = ⋃_{j \in J} {j, n - j}

Both

Ω

and

Ψ

are closure operators on

{0, 1, \dots, n}

. Likewise the projective collineation

F_{p} (x_{0}, x_{1}, \dots, x_{n}) \to F_{p} (x_{n}, x_{n - 1}, \dots, x_{0})

leaves the NRC invariant whence

Λ

has to be closed with respect to

Ψ

. Any algebraic-geometric code constructed by evaluation of a function over the NRC with values in

F_{q}

is a generalized Reed–Solomon code of length at most q. In order to get longer codes, one needs to use elements from any finite extension

F_{q}^{r}

F_{q}

Proposition 3.

Each subspace invariant under collineation of the NRC is indexed by a partition in

P (t)

. If the ground field k is sufficiently large, then every subspace which is invariant under all collineations of the NRC is spanned by base points

k c_{λ}

, where

λ \in P (t)

Proof.

Let

E_{n}^{t} : = {(e_{0}, e_{1}, \dots, e_{n}) \in N^{n + 1} | e_{0} + e_{1} + \dots + e_{n} = t},

be the set of partitions of t of n parts and let Y be the

(\binom{n}{t}) -

dimensional vector space over

F_{p}

with basis

{c_{e_{0}, e_{1}, \dots, e_{n}} \in F_{q} : (e_{0}, e_{1}, \dots, e_{n}) \in E_{n}^{t}} .

Let us call

V_{n}^{t}

the Veronese image under the Veronese mapping given by:

F_{p} (\sum_{i = 0}^{n} x_{i} b_{i}) \to F_{p} (\sum_{E_{n}^{t}} c_{e_{0}, \dots, e_{n}} x^{e_{0}} x_{1}^{e_{1}} \dots c_{n}^{e_{n}}), x_{i} \in F_{p} .

The Veronese image of each r-dimensional subspace of

P G (n, p)

is a sub-Veronesean variety

V_{r}^{t}

V_{n}^{t}

, and all those subspaces are indexed by partitions in

P (t)

. Thus by a Theorem due to Gmainer are invariant under the collineation group of the normal rational curve (see [16]).

The k-rational points

(p_{0}, p_{1}, \dots, p_{n})

of the normal rational curve C correspond to collinear points on C that are defined over some Galois extension l of k and permuted by

Gal (l / k)

. □

5.1. An Application: Three-Point Codes on the Normal Rational Curve

As we showed in Proposition 3, each subspace invariant under collineation of the NRC is indexed by a partition

λ \in P (d)

. Let us call the base point associated with the partition

λ

P_{λ}

. As we are considering that the ground field is

F_{q}

, the

F_{q}

-points might be defined over a finite extension

F_{q^{r}}

F_{q}

. Observe that for any divisor r of n, one easily obtains a extension field of

F_{q}

of degree r. Namely, let

ξ

a non-trivial

r -

root of unity, one can consider the symbols

ξ^{q^{r}}, \dots, ξ^{q}, ξ

and the polynomial which has them as roots,

q (x) = \prod_{i = 0}^{i = r} (1 - ξ^{q^{i}})

gives an extension field of

F_{q}

of degree r.

Theorem 2.

Let

σ_{1}, σ_{2}, σ_{3}

be three generators for the symmetric group

S_{d}

and let

λ_{1}, λ_{2}

and

λ_{3}

be the partitions of d indexing the corresponding irreducible representations in the special linear group

S L (n, F_{q})

. Then any algebraic code defined over the NRC is covered by a divisor defined as linear combination of the base points

{(P_{λ_{i}})}_{1 \leq i \leq 3}

on the NRC, where the

λ_{i}

are LR coefficients.

Proof.

Consider the divisors associated with the rational maps

f (x, y, z) = n x + m y + l z

defined over the normal rational curve

C_{d}

defined over

F_{q}

, with

n, m

and l integer numbers. In particular, if

d | q^{2} - 1

, the points

P = (α, 0, 0)

Q = (0, β, 0)

and

R = (0, 0, γ)

with

α^{d} = 1

β^{d} = 1

and

γ^{d} = 1

, are

F_{q^{2}} -

rational points on

C_{d}

, and the divisors

n P

m Q

and

l R

define codes on it. Reciprocally, given a code on the NRC, by Proposition 2, the corresponding divisor defining the code is defined by a finite subgroup in the symmetric group. Since the symmetric group is generated by the 3 elements

σ_{1}, σ_{2}

and

σ_{3}

, the divisor is a linear combination of the base points

{(P_{λ_{i}})}_{1 \leq i \leq 3}

on the NRC. □

5.2. Conclusions

In [17], the authors considered a particular class of block codes known as quasi-cyclic codes as orbit codes in the Grassmannian parameterizing constant dimension codes. In the present paper we have focused on RS codes that can also be viewed as orbit codes in the Grassmannian through the action of

P G L (n, q)

, the collineation group of the NRC. This approach could be extended to study a wide class of codes, including convolutional codes with two states known as 2D finite support convolutional codes of rate

\frac{k}{n}

, which are defined as free

F [z_{1}, z_{2}] -

submodules of

F {[z_{1} . z_{2}]}^{n}

with rank k.

Author Contributions

Writing—original draft, C.M.; Writing–review—editing, A.B. All authors have read and agreed to the published version of the manuscript.

Funding

This research received external funding from University of Alcalá.

Acknowledgments

We thank Diego Napp for very useful comments during the preparation of this manuscript and the referee for valuable observations.

Conflicts of Interest

The authors declare no conflict of interest.

Appendix A. Explicit Presentation of 3-Point Codes

In this section, we provide Horn’s algorithm to compute sets of indices which are admissible for the Horn problem. As a result, we provide a set of generators for the algebraic code induced on the NRC. Given sets

I, J, K \subset {0, 1, \dots, n}

, of cardinality r, we can associate to them partitions

λ, μ

and

ν

as follows. Let

I = {i_{1} < \dots, < i_{r}} \subset {1, \dots, n}

; then the corresponding partition is defined as

λ = (i_{r} - r, \dots, i_{1} - 1)

. We consider the corresponding codes defined by the base points

c_{λ}

c_{μ}

and

c_{ν}

, whenever the corresponding Littlewood–Richardson coefficient

c_{λ, μ}^{ν}

is positive. Next, we give an algorithm to compute the Littlewood–Richardson coefficients

c_{λ, μ}^{ν}

. Horn defined sets of triples

(I, J, K)

by the following inductive procedure (see [7]):

U_{r}^{n} = {(I, J, K) | \sum_{i \in I} + \sum_{j \in J} = \sum_{k \in K} k + r (r + 1) / 2},

T_{r}^{n} = {(I, J, K) \in U_{r}^{n} | f o r a l l p < r a n d a l l (F, G, H) \in T_{p}^{r},

\sum_{f \in F} i_{f} + \sum_{g \in G} j_{g} \leq \sum_{h \in H} k_{h} + p (p + 1) / 2} .

Note that Horn’s algorithm produces all the triples from the lowest values. Even if it is possible to start with a random generator set I, you need first to compute the lower values. As a consequence of the classification Theorem 2, for any triple

(I, J, K)

of indices admissible for the Horn problem the polynomials defined by

f (x) = \prod_{j \in J} (x - α^{j}), g (x) = \prod_{i \in I} (x - α^{i})

, and

h (x) = \prod_{k \in K} (x - α^{k})

where

α

is a primitive element of

F_{q^{m}}

and m is the least integer such that

n + 1 | p^{m} - 1

constitute a set of generators for the ideal of the corresponding algebraic code in the module of

n + 1

F_{q^{m}}

-rational points lying on the NRC.

Here we present a Sage [6] code calculating the

U_{r}^{n}

and

T_{r}^{n}

index sets, followed by a table containing all the cases till

n = 4

and

r = 3

. The algorithm is implemented using Python: this involves calculate and iterate through

r -

combination of

n -

element. The running time is

O ({(\binom{n}{r})}^{3})

from sage.combinat.subset import Subsets

def simple_cache(func):

cache = dict()

def cached_func(*args):

if args not in cache:

cache[args] = func(*args)

return cache[args]

cached_func.cache = cache

return cached_func

@simple_cache

def getUnr(n, r):

if r >= n:

raise ValueError(“r must be less than n: (n, r) =

(%d, %d)” %(n, r))

s = Subsets(range(1, n + 1), r)

candidates = [(x, y, z) for x in s for y in s for z in s]

return [tuple(map(sorted, (x, y, z))) for (x, y, z) in candidates if (

sum(x) + sum(y)) == (sum(z) + r * (r + 1)/2)]

def index_filter(sub_index, index):

if max(sub_index) > len(index):

raise ValueError(“%s must be valid indexes for %s”

% (sub_index, index))

# our indexes lists start at 1

return [index[i - 1] for i in sub_index]

def condition((f, g, h), (i, j, k)):

p = len(f)

return sum(index_filter(f, i)) + sum(index_filter(g, j)) <= sum(

index_filter(h, k)) + p*(p + 1)/2

def genTillR(r):

return [getTnr(r, p) for p in range(1, r)]

@simple_cache

def getTnr(n, r):

if r == 1:

return getUnr(n, 1)

else:

return [(i, j, k) for (i, j, k) in getUnr(n, r) if all(

all(condition((f, g, h), (i, j, k)) for (f, g, h) in triplets)

for triplets in genTillR(r))]

Here we list code’s remarks

The sorted() mapping function in getUnr() is necessary because the order of elements in Subsets is unknown;
There is a 1-offset between index in Python lists and index sets we use;
The recursion in getTnr() is factored out in getTillR() call;
The cache decorator mitigates the perils of performing the same calculation several times in a function that is already heavily recursive;
Results are limited by constraints Python has on recursive function calls;
The filtering performed on $U_{r}^{n}$ to get $T_{r}^{n}$ is implemented by two nested calls to all().

$(n, r)$	$U_{r}^{n}$	$T_{r}^{n}$
(2, 1)	$({1}, {1}, {1})$ , $({1}, {2}, {2})$ , $({2}, {1}, {2})$	$({1}, {1}, {1})$ , $({1}, {2}, {2})$ , $({2}, {1}, {2})$
(3, 1)	$({1}, {1}, {1})$ , $({1}, {2}, {2})$ , $({1}, {3}, {3})$ , $({2}, {1}, {2})$ , $({2}, {2}, {3})$ , $({3}, {1}, {3})$	$({1}, {1}, {1})$ , $({1}, {2}, {2})$ , $({1}, {3}, {3})$ , $({2}, {1}, {2})$ , $({2}, {2}, {3})$ , $({3}, {1}, {3})$
(3, 2)	$({1, 2}, {1, 2}, {1, 2})$ , $({1, 2}, {1, 3}, {1, 3})$ , $({1, 2}, {2, 3}, {2, 3})$ , $({1, 3}, {1, 2}, {1, 3})$ , $({1, 3}, {1, 3}, {2, 3})$ , $({2, 3}, {1, 2}, {2, 3})$	$({1, 2}, {1, 2}, {1, 2})$ , $({1, 2}, {1, 3}, {1, 3})$ , $({1, 2}, {2, 3}, {2, 3})$ , $({1, 3}, {1, 2}, {1, 3})$ , $({1, 3}, {1, 3}, {2, 3})$ , $({2, 3}, {1, 2}, {2, 3})$
(4, 1)	$({1}, {1}, {1})$ , $({1}, {2}, {2})$ , $({1}, {3}, {3})$ , $({1}, {4}, {4})$ , $({2}, {1}, {2})$ , $({2}, {2}, {3})$ , $({2}, {3}, {4})$ , $({3}, {1}, {3})$ , $({3}, {2}, {4})$ , $({4}, {1}, {4})$	$({1}, {1}, {1})$ , $({1}, {2}, {2})$ , $({1}, {3}, {3})$ , $({1}, {4}, {4})$ , $({2}, {1}, {2})$ , $({2}, {2}, {3})$ , $({2}, {3}, {4})$ , $({3}, {1}, {3})$ , $({3}, {2}, {4})$ , $({4}, {1}, {4})$
(4, 2)	$({1, 2}, {1, 2}, {1, 2})$ , $({1, 2}, {1, 3}, {1, 3})$ , $({1, 2}, {1, 4}, {1, 4})$ , $({1, 2}, {1, 4}, {2, 3})$ , $({1, 2}, {2, 3}, {1, 4})$ , $({1, 2}, {2, 3}, {2, 3})$ , $({1, 2}, {2, 4}, {2, 4})$ , $({1, 2}, {3, 4}, {3, 4})$ , $({1, 3}, {1, 2}, {1, 3})$ , $({1, 3}, {1, 3}, {1, 4})$ , $({1, 3}, {1, 3}, {2, 3})$ , $({1, 3}, {1, 4}, {2, 4})$ , $({1, 3}, {2, 3}, {2, 4})$ , $({1, 3}, {2, 4}, {3, 4})$ , $({1, 4}, {1, 2}, {1, 4})$ , $({1, 4}, {1, 2}, {2, 3})$ , $({1, 4}, {1, 3}, {2, 4})$ , $({1, 4}, {1, 4}, {3, 4})$ , $({1, 4}, {2, 3}, {3, 4})$ , $({2, 3}, {1, 2}, {1, 4})$ , $({2, 3}, {1, 2}, {2, 3})$ , $({2, 3}, {1, 3}, {2, 4})$ , $({2, 3}, {1, 4}, {3, 4})$ , $({2, 3}, {2, 3}, {3, 4})$ , $({2, 4}, {1, 2}, {2, 4})$ , $({2, 4}, {1, 3}, {3, 4})$ , $({3, 4}, {1, 2}, {3, 4})$	$({1, 2}, {1, 2}, {1, 2})$ , $({1, 2}, {1, 3}, {1, 3})$ , $({1, 2}, {1, 4}, {1, 4})$ , $({1, 2}, {2, 3}, {2, 3})$ , $({1, 2}, {2, 4}, {2, 4})$ , $({1, 2}, {3, 4}, {3, 4})$ , $({1, 3}, {1, 2}, {1, 3})$ , $({1, 3}, {1, 3}, {1, 4})$ , $({1, 3}, {1, 3}, {2, 3})$ , $({1, 3}, {1, 4}, {2, 4})$ , $({1, 3}, {2, 3}, {2, 4})$ , $({1, 3}, {2, 4}, {3, 4})$ , $({1, 4}, {1, 2}, {1, 4})$ , $({1, 4}, {1, 3}, {2, 4})$ , $({1, 4}, {1, 4}, {3, 4})$ , $({2, 3}, {1, 2}, {2, 3})$ , $({2, 3}, {1, 3}, {2, 4})$ , $({2, 3}, {2, 3}, {3, 4})$ , $({2, 4}, {1, 2}, {2, 4})$ , $({2, 4}, {1, 3}, {3, 4})$ , $({3, 4}, {1, 2}, {3, 4})$
(4, 3)	$({1, 2, 3}, {1, 2, 3}, {1, 2, 3})$ , $({1, 2, 3}, {1, 2, 4}, {1, 2, 4})$ , $({1, 2, 3}, {1, 3, 4}, {1, 3, 4})$ , $({1, 2, 3}, {2, 3, 4}, {2, 3, 4})$ , $({1, 2, 4}, {1, 2, 3}, {1, 2, 4})$ , $({1, 2, 4}, {1, 2, 4}, {1, 3, 4})$ , $({1, 2, 4}, {1, 3, 4}, {2, 3, 4})$ , $({1, 3, 4}, {1, 2, 3}, {1, 3, 4})$ , $({1, 3, 4}, {1, 2, 4}, {2, 3, 4})$ , $({2, 3, 4}, {1, 2, 3}, {2, 3, 4})$	$({1, 2, 3}, {1, 2, 3}, {1, 2, 3})$ , $({1, 2, 3}, {1, 2, 4}, {1, 2, 4})$ , $({1, 2, 3}, {1, 3, 4}, {1, 3, 4})$ , $({1, 2, 3}, {2, 3, 4}, {2, 3, 4})$ , $({1, 2, 4}, {1, 2, 3}, {1, 2, 4})$ , $({1, 2, 4}, {1, 2, 4}, {1, 3, 4})$ , $({1, 2, 4}, {1, 3, 4}, {2, 3, 4})$ , $({1, 3, 4}, {1, 2, 3}, {1, 3, 4})$ , $({1, 3, 4}, {1, 2, 4}, {2, 3, 4})$ , $({2, 3, 4}, {1, 2, 3}, {2, 3, 4})$

References

Manganiello, F.; Trautmann, A.L.; Rosenthal, J. On conjugacy classes of subgroups of the general linear group and cyclic orbit codes. In Proceedings of the IEEE International Symposium on Information Theory proceedings (ISIT), St. Petersburg, Russia, 31 July–5 August 2011. [Google Scholar]
Besana, A.; Martínez, C. Combinatorial enumeration of cyclic covers of $P_{1}$ . Turk. J. Math. 2018, 42, 2018–2034. [Google Scholar] [CrossRef]
Martínez, C. On the cohomology of Brill-Noether loci over Quot schemes. J. Algebra 2008, 319, 391–403. [Google Scholar] [CrossRef] [Green Version]
Climent, J.; Napp, D.; Pinto, R.; Simoes, R. Decoding of 2D convolutional codes over an erasure Channel. Adv. Math. Commun. 2016, 10, 179–193. [Google Scholar] [CrossRef] [Green Version]
Bifet, E.; Ghione, F.; Leticia, M. On the Abel-Jacobi map for divisors of higher rank on a curve. Math. Ann. 1994, 299, 641–672. [Google Scholar] [CrossRef] [Green Version]
SageMath. Available online: http://www.sagemath.org/ (accessed on 20 October 2020).
Fulton, W. Eigenvalues, invariant factors, highest weights and Schubert calculus. Bull. Am. Math. Soc. 2000, 37, 209–249. [Google Scholar] [CrossRef] [Green Version]
Manivel, L. On rectangular Kronecker coefficients. J. Algebr. Comb. 2011, 33, 153–162. [Google Scholar] [CrossRef] [Green Version]
Sottile, F.; Lam, T.; Lauve, A. A skew Littlewood-Richardson rule from Hopf algebras. Int. Math. Res. Not. 2011, 2011, 1205–1219. [Google Scholar]
Fomin, S.; Milkhalkin, G. Label floor diagrams for plane curves. J. Eur. Math. Soc. 2009, 12, 1453–1496. [Google Scholar]
Okounkov, A.; Pandharipande, P. Quantum cohomology of the Hilbert scheme of points in the plane. Invent. Math. 2010, 179, 523–557. [Google Scholar] [CrossRef] [Green Version]
Caporaso, L.; Harris, J. Counting plane curves of any genus. Invent. Math. 1998, 131, 345–392. [Google Scholar] [CrossRef]
Bezzateev, S.V.; Shekhunova, N. Class of generalized Goppa codes perfect in weighted Hamming metric. Des. Codes Criptogr. 2013, 66, 391–399. [Google Scholar] [CrossRef]
Bezzateev, S.V.; Shekhunova, N.A. Subclass of cyclic Goppa codes. IEEE Trans. Inf. Theory 2013, 59, 11. [Google Scholar] [CrossRef]
Lee, K.; O’Sullivan, M.E. List decoding of RS codes from a Gröbner basis perspective. J. Symb. Comput. 2008, 43, 645–658. [Google Scholar] [CrossRef] [Green Version]
Gmainer, J. Pascal’s Triangle, Normal Rational Curves, and their Invariant Subspaces. Eur. J. Comb. 2001, 22, 37–49. [Google Scholar] [CrossRef] [Green Version]
Besana, A.; Martínez, C. A Geometrical Realisation of Quasi-Cyclic Codes. In Combinatorics, Probability and Control; IntechOpen: London, UK, 2020; pp. 259–271. [Google Scholar]

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

© 2021 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Besana, A.; Martínez, C. A Topological View of Reed–Solomon Codes. Mathematics 2021, 9, 578. https://doi.org/10.3390/math9050578

AMA Style

Besana A, Martínez C. A Topological View of Reed–Solomon Codes. Mathematics. 2021; 9(5):578. https://doi.org/10.3390/math9050578

Chicago/Turabian Style

Besana, Alberto, and Cristina Martínez. 2021. "A Topological View of Reed–Solomon Codes" Mathematics 9, no. 5: 578. https://doi.org/10.3390/math9050578

APA Style

Besana, A., & Martínez, C. (2021). A Topological View of Reed–Solomon Codes. Mathematics, 9(5), 578. https://doi.org/10.3390/math9050578

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

A Topological View of Reed–Solomon Codes

Abstract

1. Introduction

Notation

2. Horn Problem: An Application to Convolutional Codes

An Example with Algebraic-Geometric Codes: Reed–Solomon Codes

3. Representation Theory of $GL (n, F_{q})$

3.1. Relation between Littlewood–Richardson Coefficients and Kronecker Coefficients

3.2. The Polytope of Triples $(λ, μ, η)$ for Which $c_{λ, μ}^{η}$ Is Positive

4. Configurations of Points over a Normal Rational Curve

Lee-Sullivan List-Decoding Algorithm of Reed–Solomon Codes

5. Notion of Collinearity on the Normal Rational Curve

5.1. An Application: Three-Point Codes on the Normal Rational Curve

5.2. Conclusions

Author Contributions

Funding

Acknowledgments

Conflicts of Interest

Appendix A. Explicit Presentation of 3-Point Codes

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

Article Menu

A Topological View of Reed–Solomon Codes

Abstract

1. Introduction

Notation

2. Horn Problem: An Application to Convolutional Codes

An Example with Algebraic-Geometric Codes: Reed–Solomon Codes

3. Representation Theory of GL ( n , F q )

3.1. Relation between Littlewood–Richardson Coefficients and Kronecker Coefficients

3.2. The Polytope of Triples ( λ , μ , η ) for Which c λ , μ η Is Positive

4. Configurations of Points over a Normal Rational Curve

Lee-Sullivan List-Decoding Algorithm of Reed–Solomon Codes

5. Notion of Collinearity on the Normal Rational Curve

5.1. An Application: Three-Point Codes on the Normal Rational Curve

5.2. Conclusions

Author Contributions

Funding

Acknowledgments

Conflicts of Interest

Appendix A. Explicit Presentation of 3-Point Codes

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

3. Representation Theory of $GL (n, F_{q})$

3.2. The Polytope of Triples $(λ, μ, η)$ for Which $c_{λ, μ}^{η}$ Is Positive