May 07, 2026
We introduce Generalized Skew Multivariate Goppa codes relying on the theory of multivariate Ore polynomials. These codes contain Generalized Skew Goppa codes as a special case. By providing a new parity-check matrix for the latter, we show that, under some hypotheses, they are subfield subcodes of Generalized Skew Reed–Solomon codes. This result turns out to be helpful to study the parameters of Skew Multivariate Goppa codes, for which we provide bounds on their dimension and minimum distance.
Among linear codes in the Hamming metric, Goppa codes [1], [2] stand out for their many interesting properties: they can be efficiently decoded, their dimension can often be increased without decreasing the minimum distance, and they are so far the only linear codes for which the McEliece cryptosystem stays partially unbroken. Goppa codes have many different, though equivalent, characterizations, all involving the use of a polynomial \(g\in\mathbb{F}_q[x]\). To name some, Goppa codes are alternant, that is, subfield subcodes of some Generalized Reed–Solomon codes. As such, they can also be defined through residues of differentials over the projective line. Furthermore, they also have a concrete description in terms of their parity-check matrix.
Because of their features, Goppa codes and their generalizations have been studied extensively. In the Hamming metric, multivariate Goppa codes were introduced by replacing \(g\) with a multivariate polynomial [3]. Successively, with the rising interest in the rank metric, Skew and Generalized Skew Goppa codes were defined respectively in [4], [5] by replacing \(g\) with an Ore polynomial. Finally, let us mention that Goppa codes in the sum-rank metric, called linearized Goppa codes, were introduced in [6], using skew residues.
The first aim of this paper is to define Generalized Skew Multivariate Goppa codes and study their parameters, which are the multivariate version of Generalized Skew Goppa (GSG) codes, as introduced in [5]. To this end, we also propose a new form of the parity-check matrix of GSG codes, which, under some minor hypotheses, allows us to show that these codes are subfield subcodes of Generalized Skew Reed–Solomon codes [7], thus providing a characterization which is well-known for classical Goppa codes but was missing in the skew case.
The paper is organized as follows. After some preliminaries on coding theory, in 2, we recall Goppa codes in the Hamming metric and their multivariate version. In 3 we propose a systematic study of Generalized Skew Goppa codes and relate their construction with that of Generalized Skew Reed–Solomon codes. Finally, in 4, we exploit the theory of multivariate Ore polynomials recently developed in [8] to introduce the multivariate version of GSG codes, and study their parameters.
After recalling some preliminaries on coding theory, this section introduces the original construction of Goppa codes in the Hamming metric [1], [2] and its multivariate version, introduced in [3].
Throughout the paper, we fix \(\mathbb{F}_{q^t}\) an extension of degree \(t\) of the finite field \(\mathbb{F}_q\), and \(n\) a positive integer. A linear code is a subspace \(C \subseteq \mathbb{F}_{q^t}^n\). We often say that \(C\) is an \([n,k,d]\) linear code where \(n\) is the block length, \(k = \dim_{\mathbb{F}_{q^t}} C\) and \(d\) is the minimum Hamming distance defined as \[d = \min_{c \in C, c \neq 0} \mathrm{wt}(c)=\min_{c \in C, c \neq 0} \mid \{i\in\{1,\dots,n\}\,:\, c_i\neq 0\}\mid.\] Given a subfield \(\mathbb{F}_{q^r}\) of \(\mathbb{F}_{q^t}\), one can consider \(C\vert_{\mathbb{F}_{q^r}} = C \cap \mathbb{F}_{q^r}^n\) which is called a subfield subcode. It is the restriction of \(C\) to the codewords which have entries only in \(\mathbb{F}_{q^r}\).
Attached to a finite field extension, we also have the trace map \[\require{physics} \Tr: \mathbb{F}_{q^t}\to \mathbb{F}_{q^r}\] given by \[\require{physics} \Tr(a) = \sum_{i=0}^{\frac{t}{r}-1} a^{(q^r)^i}\] which allows us to define the trace code.
Definition 1. Given a linear code \(C \subseteq \mathbb{F}_{q^t}^n\), for \(c = (c_1,\ldots, c_n)\), we define \(\require{physics} \Tr(c) = (\Tr(c_1),\ldots, \Tr(c_n)) \in \mathbb{F}_{q^r}^n\). We define the trace code of \(C\) to be \(\require{physics} \Tr(C) = \{\Tr(c)\,:\, c \in C\}\).
The following is a well-known result due to Delsarte, relating subfield subcodes and trace codes. For a proof, we refer the reader to [9].
Theorem 1 (Delsarte). For a code \(C \subseteq \mathbb{F}_{q^t}^n\), we have \[\require{physics} (C\vert_{\mathbb{F}_{q^r}})^\perp = \Tr(C^\perp).\]
Finally, we recall the following known result on the minimum distance of the dual of the tensor product of codes, which we shall use in the rest of the paper. A proof of this result can be found, for instance, in [10].
Lemma 1. Let \(C_i \subseteq \mathbb{F}^{n_i}\) be linear codes for \(i = 1,2\) and let \(d_i = d(C_i)\). Then \[(C_1^\perp\otimes C_2^\perp)^\perp = C_1 \otimes \mathbb{F}^{n_2} + \mathbb{F}^{n_1} \otimes C_2\] and its minimum distance is \(\min(d_1,d_2)\).
We now proceed to describe Goppa codes and their nature as subfield subcodes of particular Generalized Reed–Solomon codes.
For \(k\) a positive integer, a Generalized Reed–Solomon (GRS) code over \(\mathbb{F}_{q^t}\) is defined as \[\mathrm{GRS}_k(S, v) := \{(v_1\cdot f(s_1),\ldots, v_n\cdot f(s_n)): f \in \mathbb{F}_{q^t}[X]_{< k}\},\] where \(S = \{s_1,\ldots, s_n\}\) is a set of distinct elements of \(\mathbb{F}_{q^t}\) and \(v = \{v_1,\ldots, v_n\}\) a set of not necessarily distinct elements of \(\mathbb{F}_{q^t}^*\). When \(v_i=1\) for all \(i\), we recover classical Reed–Solomon codes. Taking \(k\leq n\), Generalized Reed–Solomon codes have parameters \([n,k,n+1-k]\), thus attaining the Singleton bound.
Let \(g \in \mathbb{F}_{q^t}[X]\) be a polynomial that does not vanish at any entries in \(S\). Throughout the paper, we consider an integer \(r\) such that \(r\mid t\), so that \(\mathbb{F}_{q^r}\) is a subfield of \(\mathbb{F}_{q^t}\). The classical Goppa code associated to \((S, g, \mathbb{F}_{q^r})\) [11] is defined as \[\Gamma(S, g, \mathbb{F}_{q^r}) := \left\{c = (c_1,\ldots, c_n) \in \mathbb{F}_{q^r}^n \, : \, \sum_{i=1}^n \frac{c_i}{X - s_i}\equiv 0 \mod g\right\}.\] Goppa codes have length \(n\), dimension \(k\geq n-\deg g\cdot (t/r)\) and minimum distance \(d\geq \deg g +1\).
When in the definition of GRS codes we take \(v_i=g(s_i)^{-1}\) for some polynomial \(g\in\mathbb{F}_{q^t}[X]\) of degree \(k\) which does not vanish at any of the \(s_i\)’s, we obtain so-called GRS codes via a Goppa code: \[\mathrm{GRS}_{\deg g} (S, g) := \{(g(s_1)^{-1}f(s_1),\ldots, g(s_n)^{-1}f(s_n)): f \in \mathbb{F}_{q^t}[X]_{< \deg g}\}.\]
It is well known that the generator matrix for \(\mathrm{GRS}_{\deg g}(S,g)\) is \[\begin{align} G &= \begin{bmatrix} g(s_1)^{-1} & g(s_2)^{-1} & \cdots & g(s_n)^{-1}\\ g(s_1)^{-1}s_1 & g(s_2)^{-1}s_2 & \cdots & g(s_n)^{-1}s_n\\ \vdots & \vdots & \ddots & \vdots\\ g(s_1)^{-1}s_1^{\deg g - 1} &g(s_2)^{-1}s_2^{\deg g - 1} &\cdots &g(s_n)^{-1}s_n^{\deg g - 1}\\ \end{bmatrix}\\ &= \begin{bmatrix} 1 & 1 & \cdots & 1\\ s_1 & s_2 & \cdots & s_n\\ \vdots & \vdots & \ddots & \vdots\\ s_1^{\deg g - 1} &s_2^{\deg g - 1} &\cdots &s_n^{\deg g - 1}\end{bmatrix}\begin{bmatrix} g(s_1)^{-1} & 0 & \cdots & 0\\ 0 & g(s_2)^{-1} & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 &\cdots & g(s_n)^{-1}\\ \end{bmatrix} \end{align}\] and it is a parity-check matrix for \(\Gamma(S,g, \mathbb{F}_{q^r})\) [11]. Moreover, the dual of a GRS is another GRS. In the above case, the dual of \(\mathrm{GRS}_{\deg g}(S,g)\) is given by \(\mathrm{GRS}_{n-\deg g}(S, y)\) where for \(i = 1,\ldots, n\) \[y_i = \frac{g(s_i)}{\prod_{j\neq i}(s_i - s_j)}.\] The generator matrix \(G\) is a parity-check matrix for \(\mathrm{GRS}_{n-\deg g}(S,y)\) so naturally \(\Gamma(S,g,\mathbb{F}_{q^r})\) is a subfield subcode of \(\mathrm{GRS}_{n-\deg g}(S,y)\). We note that the dual of a GRS code via a Goppa code is not necessarily a GRS code via a Goppa code.
The construction of Goppa codes was extended to the multivariate case in [3]. We recall here their construction and offer an alternative, shorter proof of the parameters of the so-called multivariate Goppa codes. The approach we take here will then be of inspiration for the study of the skew version of multivariate Goppa codes we shall perform in 4.
Definition 2. Fix nonempty subsets \(S_1,\ldots, S_m \subseteq \mathbb{F}_{q^t}\). Let \(\mathcal{S} := S_1 \times \cdots \times S_m \subseteq \mathbb{F}_{q^t}^m.\) Enumerate the elements of \(\mathcal{S} = \{\boldsymbol{s}_1,\ldots, \boldsymbol{s}_n\}.\) Choose \(g \in \mathbb{F}_{q^t}[\boldsymbol{x}] = \mathbb{F}_{q^t}[x_1,\ldots, x_m]\) such that \(g(\boldsymbol{s}_i) \neq 0\) for all \(i\). Further, we assume \(g = g_1\cdots g_m\) where \(g_i \in \mathbb{F}_{q^t}[x_i]\) and define \(\deg g = \prod_{i=1}^m \deg g_i\). Let \(r\mid t\) be an integer. The multivariate Goppa code is defined as \[\label{eq:multGoppa} \Gamma(\mathcal{S}, g,\mathbb{F}_{q^r}):= \left\{(c_1,\ldots, c_n) \in \mathbb{F}_{q^r}^n\, : \, \sum_{i=1}^n \frac{c_i}{\prod_{j= 1}^m (x_j-s_{ij})}\equiv 0 \mod g\right\},\tag{1}\] where \(\boldsymbol{s}_i = (s_{i1},\ldots, s_{im}) \in \mathcal{S}\).
We will often denote \(\Gamma(\mathcal{S}, g, \mathbb{F}_{q^r})\) by \(\Gamma(\mathcal{S},g)\) when the subfield is understood from the context. Notice, when \(m = 1\), \(\Gamma(\mathcal{S},g)\) reduces to a classical Goppa code. In general, it was shown in [3] that the generator matrix for \[\bigotimes_{i = 1}^m \mathrm{GRS}_{\deg g_i}(S_i, g_i)=:T(\mathcal{S}, g)\] is a parity-check matrix for \(\Gamma(\mathcal{S}, g)\). In other words, \(\Gamma(\mathcal{S}, g)\) is a subfield subcode of the dual of the code denoted \(T(\mathcal{S}, g)\), that is, \(\Gamma(\mathcal{S}, g)=(T(\mathcal{S}, g)^\perp\cap \mathbb{F}_{q^r}^n)\). We point out that the dual of \(T(\mathcal{S},g)\) can be expressed as follows \[\begin{align} (T(\mathcal{S},g))^\perp &= \left(\bigotimes_{i = 1}^m \mathrm{GRS}_{\deg g_i}(S_i, g_i)\right)^\perp\\ &=\sum_{i = 1}^m \mathbb{F}_{q^t}^{n_1} \otimes \cdots \otimes \mathrm{GRS}_{\deg g_i}(S_i, g_i)^\perp \otimes \cdots \otimes \mathbb{F}_{q^t}^{n_m}\\ &=\sum_{i = 1}^m \mathbb{F}_{q^t}^{n_1} \otimes \cdots \otimes \mathrm{GRS}_{n_i-\deg g_i}(S_i, y_i) \otimes \cdots \otimes \mathbb{F}_{q^t}^{n_m}, \end{align}\] where \(n_i = |S_i|\). The chain of equalities follows from observing and inducting on the fact that \((C_1 \otimes C_2)^\perp = C_1^\perp \otimes \mathbb{F}_{q^t}^{n_2} + \mathbb{F}_{q^t}^{n_1} \otimes C_2^\perp\) and then applying the fact that the dual of a GRS code is another GRS code.
We know \(\Gamma(\mathcal{S},g)\) is the subfield subcode of \((T(\mathcal{S},g))^\perp\) so we obtain the following result, which matches [3].
Theorem 2. The multivariate Goppa code \(\Gamma(\mathcal{S},g)\) has parameters:
Length \(n = |\mathcal{S}|\),
Dimension \(k\) satisfying \(n - \frac{t}{r}\deg g\leq k \leq n -\deg g\),
Minimum distance \(d \geq \min_{i\in [m]}\{\deg g_i + 1\}\).
Proof. The length is obvious. Let \(k = \dim \Gamma(\mathcal{S}, g)\). Since \(T(\mathcal{S},g)\) has dimension \(\deg g\), its dual \((T(\mathcal{S},g))^\perp\) has dimension \(n - \deg g\) and \(\Gamma(\mathcal{S},g)\) is a subfield subcode of \((T(\mathcal{S},g))^\perp\) so \(\dim \Gamma(\mathcal{S},g) \leq n - \deg g\). By Delsarte’s Theorem (1), we have that for a code \(C\) over \(\mathbb{F}_{q^t}\), \[\require{physics} \left(C \cap \mathbb{F}_{q^r}^n\right)^\perp = \Tr(C^\perp),\] and \(\require{physics} \Tr: C \to \Tr(C)\) is a surjective \(\mathbb{F}_{q^r}\) linear mapping so the dimension of \(C\) regarded as a \(\mathbb{F}_{q^r}\) vector space is \(\frac{t}{r}\cdot \dim C\). Applying this result to \[\require{physics} \Gamma(\mathcal{S},g) = (\Tr(T(\mathcal{S},g)))^\perp\] we have \[\require{physics} \dim \Tr(T(\mathcal{S},g)) \leq \frac{t}{r}\deg g\] from which we obtain \[\dim \Gamma(\mathcal{S},g) \geq n - \frac{t}{r}\deg g.\] Finally, by 1, the minimum distance of \((T(\mathcal{S},g))^\perp\) is \(\min_{j\in [m]}\{\deg g_j + 1\}\) and the bound on the minimum distance of \(\Gamma(\mathcal{S},g)\) follows. ◻
In [3], the authors introduced Augmented Cartesian codes to prove the minimum distance of \(\Gamma(\mathcal{S},g)\). We showed that our proof of dimension and distance of \(\Gamma(\mathcal{S},g)\) follows directly from the tensor product of GRS codes characterization and manipulating the dual of tensor product codes. We now show how our method leads to an alternative distance proof for Augmented Cartesian codes. We recall that for \(g\) and \(S\) as above, Augmented Cartesian codes are defined as \[ACar(\mathcal{S}, g)=\left\{\left(\frac{g}{L}(s_i)f(s_i)\right)_i \,:\, s_i\in S, f\in L(A_g)\right\},\] where \(A_g=\prod_{j=1}^m \{0,\dots,n_j-1\}\setminus\prod_{j=1}^m \{n_j-\deg_{x_j}(g),\dots,n_j-1\}\) and \(L(A_g)=\mathrm{Span}_{\mathbb{F}_{q^t}} \{\boldsymbol{x}^a\,:\, a\in A_g\}\). Note that by [3], we have \[ACar(\mathcal{S},g) = (T(\mathcal{S},g))^\perp,\] hence \(\Gamma(\mathcal{S}, g)\) is the subfield subcode of \(ACar(\mathcal{S}, g)\), that is, \(\Gamma(\mathcal{S}, g)=ACar(\mathcal{S},g)\cap \mathbb{F}_{q^r}^n\). Since \[ACar(\mathcal{S}, g) = \sum_{j = 1}^m \mathbb{F}_{q^t}^{n_1} \otimes \cdots \otimes \mathrm{GRS}_{n_j-\deg g_j}(S_j, y_j) \otimes \cdots \otimes \mathbb{F}_{q^t}^{n_m},\] it follows from 1 that the minimum distance is \(\min_{j\in [m]}\{\deg g_j + 1\}\). Indeed, this gives rise to a proof of the minimum distance of \(ACar(\mathcal{S}, g)\), which differs from the one presented in [3].
In this section, we transpose the construction of Goppa codes to the skew case, following the construction of Generalized Skew Goppa (GSG) codes from [5]. In particular, in 3.2, we give a new description of the parity-check matrix of GSG codes, which will allow us to show in 3.3 that GSG codes are subfield subcodes of the dual of so-called Generalized Skew Reed–Solomon codes (introduced in [7] and recalled later in this section). We shall use this result in 4 to study the multivariate version of GSG codes.
Let \(\theta\) be the Frobenius automorphism for the finite field \(\mathbb{F}_{q^t}\) and let \(R = \mathbb{F}_{q^t}[X;\theta]\). This is an Ore polynomial ring in one variable \(X\) over the finite field \(\mathbb{F}_{q^t}\). On this ring, we have the usual sum while the multiplication is twisted by the rule \(X\cdot a =\theta(a) \cdot X\) for all \(a\in\mathbb{F}_{q^t}\). It is well-known that \(R\) is a left and right Euclidean domain, and has left and right divisors and multiples. We refer to [12] for the theory of Ore polynomial rings.
Distinctness and linear independence do not carry over in the noncommutative setting of Ore polynomial rings. For an equivalent notion, the concept of P-independence was introduced. In this section, we present the results necessary for this work, and refer the reader to [5], [13]–[16] for a more comprehensive treatment.
Definition 3. A set of \(n\) points \(S = \{s_1,\ldots, s_n\} \subseteq \mathbb{F}_{q^t}\) is said to be P-independent if the degree of the least common left multiple of \(\{X - s_i\mid 1 \leq i \leq n\}\) is \(n\).
A polynomial \(0 \neq g \in R\) is called invariant if \(gR = Rg\). If \(g\in R\) is an invariant polynomial, then \(R/Rg\) is a ring.
Suppose \(gh = h'g\) for some \(h,h' \in R\). If \(fh = g\) then \(gh = h'fh\) so \(g = h'f\). On the other hand, if \(g = h'f\) then \(h'fh = h'g\) so \(fh = g\). This shows that \(f\mid_r g\) if, and only if, \(f \mid_l g\), where \(\mid_r\) and \(\mid_l\) denote the right and left division, respectively. It follows that, given the monomial \(X - s\) for \(s \in \mathbb{F}_{q^t}\), \((X-s, g)_r = 1\) if, and only if, \((X-s, g)_l = 1\), where \((\cdot,\cdot)_r\) and \((\cdot,\cdot)_l\) denote the right and left gcd, respectively.
If \((X-s,g)_r = 1\), then there is some \(h\in R\) such that \(h(X-s) -1 \in Rg = gR\). In \(R/Rg\), \(h(X-s) - 1 = 0\), hence \(X - s + Rg\) is a unit in \(R/Rg\). This implies that \(h\) is unique, with \(\deg h < \deg g\), and such that \(h(X-s) -1 \in Rg\).
We are now ready to define Generalized Skew Goppa codes [5].
Definition 4. Let \(0 \neq g \in R\) be invariant. Let \(S=\{s_1,\ldots,s_n\} \subseteq \mathbb{F}_{q^t}\) be P-independent elements such that \((X-s_j, g)_r = 1\) for \(j = 1,\ldots,n\). Let \(h_j \in R\) be the unique element such that \(\deg h_j < \deg g\) and \(h_j(X-s_j) - 1 \in Rg\). Let \(\eta=\{\eta_1,\ldots,\eta_n\} \subseteq \mathbb{F}_{q^t}^*\). Let \(r\mid t\) be an integer. The Generalized Skew Goppa (GSG) code \(\widetilde{\Gamma}\subseteq \mathbb{F}_{q^r}^n\) is \[\begin{align} \widetilde{\Gamma}(S, \eta, g, \mathbb{F}_{q^r}) &\mathrel{\vcenter{:}}= \left\{c=(c_1,\ldots, c_n)\in \mathbb{F}_{q^r}^n \, : \, \sum_{j=1}^n c_j\eta_jh_j = 0\right\}\\ &=\left\{c=(c_1,\ldots, c_n)\in \mathbb{F}_{q^r}^n \, : \, \sum_{j=1}^n c_j\eta_jh_j \in Rg\right\}. \end{align}\]
If \(\eta_j = 1\) for \(j = 1,\ldots, n\), then we call \(\widetilde{\Gamma}\) a Skew Goppa code. It is isomorphic to the linearized Goppa codes introduced in [4]. Additionally, if \(\theta = \mathrm{id}\), \(\widetilde{\Gamma}\) recovers the classical Goppa code.
We now proceed to a study of GSG codes and their parity-check matrix. From [4], we know that linearized Goppa codes have dimension \(k\geq n - \frac{t}{r}\deg g\) and minimum distance \(d\geq \deg g + 1\). A decoding algorithm for GSG codes was provided in [5], from which one can deduce that their minimum distance is at least \(\deg g+1\). In our coming study, we will have a slightly different approach than the aforementioned papers. In particular, we will make explicit the form of invariant polynomials in \(R\), and successively rewrite the parity-check matrix of GSG codes in a way which will be convenient for us, as explained at the beginning of this section. In order to do so, we first need to recall some results on partial norms and P-independent sets.
To proceed in analyzing the parity-check matrix of the GSG code, the following results about partial norms will be useful. For \(i \in \mathbb{N}\), let \(N_i: \mathbb{F}_{q^t}\to \mathbb{F}_{q^t}\) be defined as \(N_0(a) = 1\) and \(N_i(a) = \prod_{s=0}^{i-1}\theta^s(a)\) for \(i > 0\). One can easily check that \(N_{i+1}(a) = \theta(N_{i}(a))\cdot a = \theta^i(a)N_i(a)\). Note that \(N_t\) is the classical field norm and if \(\theta = \mathrm{id}\) then \(N_i(a) = a^i\).
For any ratio of norms we have the identity \[\label{eqn:ratio46of46norms}\frac{N_{i+1}(a)}{N_{j+1}(a)} = \theta\left(\frac{N_{i}(a)}{N_{j}(a)}\right)\tag{2}\] for all \(0 \leq i,j \leq t\) and all \(a \neq 0\). Additionally, \[\label{eqn:inverse46of46norm46equals46norm46of46inverse}\frac{1}{N_i(a)} = \frac{1}{\prod_{s=0}^{i-1}\theta^s(a)} = \prod_{s=0}^{i-1}\frac{1}{\theta^s(a)} = \prod_{s=0}^{i-1}\theta^s(a^{-1}) = N_i(a^{-1}).\tag{3}\] These norms often show up in the context of polynomial evaluation and, consequently, Vandermonde matrices (see e.g., [7]). Consider a skew polynomial \(g(X) = g_\rho X^\rho + g_{\rho-1}X^{\rho-1} + \cdots + g_0\), then the evaluation of \(g\) at a point \(a\) is well known [17] to be \[g(a) = \sum_{i=0}^\rho g_i N_i(a).\] We present some easy lemmas which will be used to prove the rank of the parity-check matrix of \(\widetilde{\Gamma}\).
Lemma 2. Let \(M\) be an \(m \times n\) matrix over \(\mathbb{F}_{q^t}\) and let \(\theta\) be the \(q\)-Frobenius automorphism. Then, \(\mathrm{rk}(M) = \mathrm{rk}(\theta(M))\) where \(\theta(M)\) is the matrix obtained by applying \(\theta\) to every entry of \(M\).
Proof. Let \(v_1,\ldots, v_n\) be the columns of \(M\). Then \(\theta(v_1),\ldots, \theta(v_n)\) are the columns of \(\theta(M)\) where \(\theta(v_j)\) is the vector obtained by applying \(\theta\) to each entry of \(v_j\) for \(j = 1,\ldots, n\). Suppose there is an \(\mathbb{F}_{q^t}\)-linear relation among the \(v_j\)’s: \[\sum_{j=1}^n \beta_j v_j = 0, \quad \beta_j \in \mathbb{F}_{q^t}.\] Applying \(\theta\) componentwise leads to \[0 = \theta(0) = \theta\left(\sum_{j=1}^n \beta_j v_j\right) = \sum_{j=1}^n \theta(\beta_j)\theta(v_j).\] Since \(\beta_j \neq 0 \iff \theta(\beta_j) \neq 0\), we get the \(v_j\)s are dependent if and only if \(\theta(v_j)\)s are dependent. Hence, the maximum number of independent columns is preserved so \(\mathrm{rk}(M) = \mathrm{rk}(\theta(M))\). ◻
We recall the following two results from [5], which we state without proof. For \(a\in \mathbb{F}_{q^t},b\in\mathbb{F}_{q^t}^*\), we write \(^ba=\theta(b)ab^{-1}\) and denote by \([a]_\theta=\{^ba\mid b\in\mathbb{F}_{q^t}^*\}\) the conjugacy class of \(a\) under \(\theta\). The first lemma relates the notion of P-independent subsets of a conjugacy class to the linear independence of the element by which we are conjugating.
Lemma 3. Given \(a \in \mathbb{F}_{q^t}^*\), the P-independent subsets of \([a]_\theta\) are those of the form \(\{\prescript{b_1}{}{a},\ldots, \prescript{b_m}{}{a}\}\) where \(m \leq t\) and \(\{b_1,\ldots, b_m\}\) is an \(\mathbb{F}_q\)-independent set. Additionally, \(m = t\) if, and only if, the least common left multiple of \(\{X-\prescript{b_i}{}{a}\mid 1 \leq i \leq m\}\) is \(X^t - N_t(a)\).
The next lemma describes how P-independent sets can be partitioned by norms.
Lemma 4. A subset \(A \subseteq \mathbb{F}_{q^t}^*\) is P-independent if, and only if, \(A = A_1 \cup \cdots \cup A_s\), where \(A_i \subseteq [a_i]_\theta\) is P-independent for all \(i = 1,\ldots, s\), and \(a_1,\ldots, a_s \in \mathbb{F}_{q^t}^*\) have distinct norms.
This leads to the following sufficient condition for building P-independent sets which remain P-independent under inversion.
Lemma 5. Suppose \(S = \{s_1,\ldots, s_n\} \subseteq \mathbb{F}_{q^t}^*\) is P-independent and at most two elements from each \(\theta\)-conjugacy class belong to \(S\). Then \(S^{-1} = \{s_1^{-1},\ldots, s_n^{-1}\}\) is P-independent.
Proof. It suffices to prove the statement for P-independent elements within a conjugacy class since norms stay distinct after inversion by 3 . To that end, split \(S\) by conjugacy classes (which all have distinct norms) and consider one such conjugacy class \(A = \{\prescript{b_1}{}{a},\ldots, \prescript{b_m}{}{a}\} \subseteq [a]_\theta \cap S\) with \(1 \leq m \leq \min (2,t)\). Note that \(b_j \neq 0\) for \(j = 1,\ldots, m\). Since \(S\) is P-independent, \(A\) is P-independent. Furthermore, \(A\) is P-independent if, and only if, \(b_1,\ldots, b_m\) are \(\mathbb{F}_q\)-linearly independent. If \(|A| \leq 1\), then obviously \(A^{-1}\) is P-independent. Suppose \(|A| = 2\). Notice that \[(\prescript{b_j}{}{a})^{-1} = (\theta(b_j)ab_j^{-1})^{-1} = \theta(b_j^{-1})a^{-1}(b_j^{-1})^{-1} = \prescript{b_j^{-1}}{}{a^{-1}}\] for \(j = 1,2\). Hence, we need to show that if \(b_1,b_2\) are \(\mathbb{F}_q\)-linearly independent, then \(b_1^{-1},b_2^{-1}\) are \(\mathbb{F}_q\)-linearly independent.
Suppose there exist some \(u_1,u_2 \in \mathbb{F}_q\) such that \(u_1b_1^{-1} + u_2b_2^{-1} = 0\). Multiplying by \(b_1b_2\), we obtain \(u_1b_2 + u_2b_1 = 0\). This contradicts the \(\mathbb{F}_q\)-linear independence of \(b_1,b_2\). Therefore, \(b_1^{-1},b_2^{-1}\) are \(\mathbb{F}_q\)-independent and thus \(A^{-1}\) is P-independent. The claim follows. ◻
Remark 3. If the automorphism is trivial, i.e., \(\theta = \mathrm{id}\), then every \(\theta\)-conjugacy class is a singleton and P-independence is equivalent to distinctness, so the P-independence of the inverse as in 5 holds without any hypothesis. In particular, the classical Goppa code is still a special case of the GSG code with the restriction of P-independent sets as in 5.
Example 1. We want to show how P-independence can be preserved and fail under inversion if we allow more than \(2\) elements per conjugacy class. Consider \(\mathbb{F}_8 = \mathbb{F}_2[\omega]/[\omega^3 + \omega + 1]\) and let \(\theta:\mathbb{F}_8 \to \mathbb{F}_8\) be the usual Frobenius automorphism \(\theta(a) = a^2\). Let \(\{1,\omega,\omega^2\}\) be a basis of \(\mathbb{F}_8\) over \(\mathbb{F}_2\). It is not too difficult to check that the roots of \(X^3 + X^2 + 1\) are \[\omega + 1, \omega^2 + 1, \omega^2 + \omega + 1.\] Expanding the roots with respect to the basis, we obtain the matrix \[\begin{bmatrix} 1&1&1\\1&0&1\\0&1&1 \end{bmatrix}\] which has full rank so the roots are \(\mathbb{F}_2\)-linearly independent. The inverses of these roots are \[\omega^2 + \omega, \omega,\omega^2,\] respectively, but they are not \(\mathbb{F}_2\)-linearly independent. Hence, if the first set of roots is used as conjugating elements, then the second set of roots would be the corresponding conjugating elements for the inverted elements. Since the second set of roots fails to be \(\mathbb{F}_2\)-linearly independent, the inverted elements cannot be P-independent.
Now take the basis elements \(1,\omega,\omega^2\). They are clearly \(\mathbb{F}_2\)-linearly independent. Inverting these elements, we obtain \[1, \omega^2 + 1, \omega^2 + \omega + 1.\] Expanding these three elements with respect to the basis, we obtain the matrix \[\begin{bmatrix} 1&1&1\\0&0&1\\0&1&1 \end{bmatrix}\] which has full rank so the roots are \(\mathbb{F}_2\)-linearly independent. Therefore, this gives rise to \(3\) elements within the same conjugacy class which are P-independent, and their inverses are also P-independent.
5 is a sufficient condition for \(S^{-1}\) to be a P-independent set, when \(S\) is P-independent and is useful for checking and building such P-independent sets. However, as 1 shows, it is not a necessary condition.
The length of the GSG code is bounded by the size of the P-independent set on which it is evaluated. Since there are \(q-1\) nonzero \(\theta\)-conjugacy classes, P-independent sets have size at most \(t(q-1) + 1\). P-independent sets such that their inverted set is also P-independent have size at most \(t(q-1)\) and P-independent sets built using 5 have size at most \(2(q-1)\).
A parity-check matrix for the Generalized Skew Goppa codes was studied in [5]. In this subsection, we rewrite it in a way which will be convenient for us later on in 4.
To this end, it will be convenient to characterize elements \(g \in R\) that are invariant as required in 4. A more general version of 4 below is proven in [18], but we provide a self-contained characterization for completeness. In the following, we will use the well-known result that the center of \(R\), that is, the set of all elements of \(R\) that commute with every element of \(R\), is \(Z(R)=\mathbb{F}_q[X^t]\).
Theorem 4. Let \(R = \mathbb{F}_{q^t}[X; \theta]\). Then a nonzero element \(g \in R\) satisfies \(gR = Rg\) (i.e., \(g\) is invariant) if, and only if, \[g = a\cdot v \cdot X^l,\] for some \(v(X) \in Z(R)\), \(a \in \mathbb{F}_{q^t}\), and \(l \in \mathbb{N}\).
Proof. Clearly \(0 \in \mathbb{F}_{q^t}\) is invariant. Any nonzero element \(a \in \mathbb{F}_{q^t}\) is invariant because for any \(f = \sum_{i=0}^k f_i X^i \in R\), \[Ra \ni f \cdot a = \sum_{i=0}^k f_i \theta^i(a) X^i = a \cdot \sum_{i=0}^k f_i \frac{\theta^i(a)}{a} X^i \in aR.\]
For any \(l \in \mathbb{N}\), \(X^l\) is invariant because \[RX^l \ni f \cdot X^l = \sum_{i=0}^k f_iX^{i+l} = X^l \sum_{i=0}^k \theta^{-l}(f_i)X^i \in X^lR.\]
Hence, any invariant element of \(R\) has the form \(a \cdot v(X) \cdot X^j\) where \(a \in \mathbb{F}_{q^t}\) and \[v(X) = 1 + v_1X + \cdots + v_mX^m,\quad v_i \in \mathbb{F}_{q^t}, v_m \neq 0\] is invariant. For \(v(X)\) to be invariant, we must satisfy that for every \(b \in \mathbb{F}_{q^t}\) there exists \(b' \in R\) such that \(v \cdot b = b' \cdot v\) and there exists \(r(X) \in R\) such that \(v(X) \cdot X = r(X) \cdot v(X)\). By degree considerations, it follows that \(b' \in \mathbb{F}_{q^t}\) and \(\deg r = 1\) so \(r(X) = r_1X + r_0\) for \(r_0, r_1 \in \mathbb{F}_{q^t}\).
Suppose \(b \neq 0\) (otherwise, invariance is trivially satisfied). From \(v \cdot b =b' \cdot v\), we have \[\begin{align} v\cdot b &= (1 + v_1X + \cdots + v_mX^m)b\\ &= b + v_1 \theta(b)X + \cdots + v_m\theta^m(b) X^m\\ &=b' + b'v_1X + \cdots + b'v_mX^m\\ &= b'\cdot v \end{align}\] which implies \(b = b'\) and \(\theta^i(b) = b' = b\) so \(t \mid i\). Furthermore, because \(v(X) \cdot X = r(X) \cdot v(X)\), we have \[\begin{align} v(X) \cdot X &= X + v_1X^2 + \cdots + v_mX^{m+1}\\ &= r_0 + (r_1 + r_0v_1)X + \cdots r_1\theta(v_m)X^{m+1}\\ &= (r_1 X + r_0)(1 + v_1X + \cdots + v_mX^m)\\ &= r(X) \cdot v(X) \end{align}\] which forces \(r_0 = 0\), \(r_1 = 1\), and \(\theta(v_i) = v_i\) so \(v_i \in \mathbb{F}_q\). Hence, \(r(X) = X\) and \(v(X) \in \mathbb{F}_q[X^t] = Z(R)\), as desired. ◻
We are now ready to construct the parity-check matrix of GSG codes. We choose to divide \(g\) by \(X - s_j\) on the right. Let \[g(X) = a\cdot v(X) \cdot X^l = a(v_0 + v_1X^t + \cdots + v_mX^{tm})X^l\] as described in 4. Without loss of generality, we assume that \(a, v_m \neq 0\) and \(v_0 = 1\), and define \(\rho:= tm + l\). For convenience, let us write \[g(X) = g_\rho X^\rho + g_{\rho-1}X^{\rho-1} + \cdots + g_0,\] where \[g_u = \begin{cases} av_{m-b} & \text{for } u = \rho-bt, b = 0,\ldots, m\\ 0 & \text{otherwise} \end{cases}.\] Let \(q_j(X) = q_{\rho-1,j}X^{\rho-1} + \cdots + q_{1,j}X + q_{0,j}\) and suppose \(g(X) = q_j(X)(X-s_j) + r_j\), \(r_j\in \mathbb{F}_{q^t}\), for all \(j=1,\dots, n\). Then \[\begin{align} g(X) &= av_mX^{tm+l} + av_{m-1}X^{t(m-1)+l} + \cdots + aX^l\\ &= q_{\rho-1,j}X^\rho + (q_{\rho-2,j} - q_{\rho-1,j}\theta^{\rho-1}(s_j))X^{\rho-1} +\\&\qquad \cdots + (q_{0,j} - q_{1,j}\theta(s_j))X - q_{0,j}s_j + r_j. \end{align}\] Equating coefficients, we get: \[\begin{align} \label{eq:h95structure95skew} q_{i,j} &= \sum_{b=0}^{\left\lfloor\frac{\rho-i-1}{t}\right\rfloor}av_{m-b}\prod_{s=bt+1}^{\rho-i-1}\theta^{\rho-s}(s_j)\nonumber\\ &= \sum_{b=0}^{\left\lfloor\frac{\rho-i-1}{t}\right\rfloor}av_{m-b}\prod_{s=i+1}^{\rho-(bt+1)}\theta^{s}(s_j)\nonumber\\ &= \sum_{b=0}^{\left\lfloor\frac{\rho-i-1}{t}\right\rfloor}av_{m-b}\frac{N_{\rho-bt}(s_j)}{N_{i+1}(s_j)}\nonumber\\ &= \sum_{b=0}^{\left\lfloor\frac{\rho-i-1}{t}\right\rfloor}g_{\rho-bt}\frac{N_{\rho-bt}(s_j)}{N_{i+1}(s_j)} \end{align}\tag{4}\] for \(0 \leq i \leq \rho-1, 1 \leq j \leq n\), and \[\begin{align} r_j = g_0 + q_{0,j} s_j &= g_0 + \left(\sum_{b=0}^{\left\lfloor\frac{\rho-1}{t}\right\rfloor}g_{\rho-bt}\frac{N_{\rho-bt}(s_j)}{N_{1}(s_j)}\right)\cdot s_j\\ &= g_0 + \sum_{b=0}^{\left\lfloor\frac{\rho-1}{t}\right\rfloor}g_{\rho-bt}N_{\rho-bt}(s_j)\\ & = \sum_{i=0}^\rho g_iN_i(s_j)= g(s_j) \neq 0 \end{align}\] otherwise \(s_j\) would be a root of \(g\). Multiplying by \(-r_j^{-1}\) on the left we obtain \(-r_j^{-1}g(X) = -r_j^{-1}q_j(X)(X-s_j) - 1\). Let \(h_j(X) = -r_j^{-1}q_j(X)\); this is the desired polynomial.
Clearly, a parity-check matrix is \(-H = (-r_j^{-1} q_{i,j}\eta_j)_{0 \leq i \leq \rho-1, 1 \leq j\leq n}\) and an equivalent parity-check matrix is \(H = (g(s_j)^{-1} q_{i,j}\eta_j)_{0 \leq i \leq \rho-1, 1 \leq j\leq n}\). We can see that \[\label{eq:HHRE} \begin{align} H = \underbrace{\begin{bmatrix} q_{0,1} & \cdots & q_{0,n}\\ \vdots & \ddots & \vdots\\ q_{\rho-1,1}& \cdots & q_{\rho-1,n} \end{bmatrix}}_{H'}\underbrace{\begin{bmatrix} g(s_1)^{-1}\\ &\ddots\\ &&g(s_n)^{-1} \end{bmatrix}}_{R}\underbrace{\begin{bmatrix} \eta_1\\ &\ddots\\ &&\eta_n \end{bmatrix}}_{E} \end{align}\tag{5}\] and using 4 we have \[\begin{align} H'&=\begin{bmatrix} q_{0,1} & \cdots & q_{0,n}\\ \vdots & \ddots & \vdots\\ q_{\rho-1,1}& \cdots & q_{\rho-1,n} \end{bmatrix}\\ &= \begin{bmatrix} \sum_{b=0}^{\left\lfloor\frac{\rho-1}{t}\right\rfloor}g_{\rho-bt}\frac{N_{\rho-bt}(s_1)}{N_{1}(s_1)} & \cdots & \sum_{b=0}^{\left\lfloor\frac{\rho-1}{t}\right\rfloor}g_{\rho-bt}\frac{N_{\rho-bt}(s_n)}{N_{1}(s_n)}\\ \sum_{b=0}^{\left\lfloor\frac{\rho-2}{t}\right\rfloor}g_{\rho-bt}\frac{N_{\rho-bt}(s_1)}{N_{2}(s_1)} & \cdots & \sum_{b=0}^{\left\lfloor\frac{\rho-2}{t}\right\rfloor}g_{\rho-bt}\frac{N_{\rho-bt}(s_n)}{N_{2}(s_n)}\\ \vdots & \ddots & \vdots\\ \sum_{b=0}^{\left\lfloor\frac{\rho-(\rho-1)-1}{t}\right\rfloor}g_{\rho-bt}\frac{N_{\rho-bt}(s_1)}{N_{\rho}(s_1)}& \cdots & \sum_{b=0}^{\left\lfloor\frac{\rho-(\rho-1)-1}{t}\right\rfloor}g_{\rho-bt}\frac{N_{\rho-bt}(s_n)}{N_{\rho}(s_n)} \end{bmatrix}\\&= \begin{bmatrix} \sum_{b=0}^{\left\lfloor\frac{\rho-1}{t}\right\rfloor}g_{\rho-bt}\frac{N_{\rho-bt}(s_1)}{N_{1}(s_1)} & \cdots & \sum_{b=0}^{\left\lfloor\frac{\rho-1}{t}\right\rfloor}g_{\rho-bt}\frac{N_{\rho-bt}(s_n)}{N_{1}(s_n)}\\ \sum_{b=0}^{\left\lfloor\frac{\rho-2}{t}\right\rfloor}g_{\rho-bt}\frac{N_{\rho-bt}(s_1)}{N_{2}(s_1)} & \cdots & \sum_{b=0}^{\left\lfloor\frac{\rho-2}{t}\right\rfloor}g_{\rho-bt}\frac{N_{\rho-bt}(s_n)}{N_{2}(s_n)}\\ \vdots & \ddots & \vdots\\ g_\rho& \cdots & g_\rho \end{bmatrix}. \end{align}\]
Notice that for fixed \(i\) and for every \(j\), the term in position \((i,j)\) \[g_{\rho-bt}\frac{N_{\rho-bt}(s_j)}{N_{i+1}(s_j)}\] and the term in position \((i-t,j)\) \[g_{\rho-(b+1)t}\frac{N_{\rho-(b+1)t}(s_j)}{N_{i-t+1}(s_j)} =g_{\rho-(b+1)t}\theta^t\left(\frac{N_{\rho-(b+1)t}(s_j)}{N_{i-t+1}(s_j)}\right) \stackrel{\eqref{eqn:ratio46of46norms}}{=} g_{\rho-(b+1)t}\frac{N_{\rho-bt}(s_j)}{N_{i+1}(s_j)}\] only differ by the coefficient. In particular, we can systematically row reduce \(H'\) such that it can be transformed, by multiplying by an invertible matrix \(T\), into the matrix \[\begin{align} H'' &= \begin{bmatrix} g_\rho\frac{N_\rho(s_1)}{N_1(s_1)} & \cdots & g_\rho\frac{N_\rho(s_n)}{N_1(s_n)}\\ g_\rho\frac{N_\rho(s_1)}{N_2(s_1)} & \cdots & g_\rho\frac{N_\rho(s_n)}{N_2(s_n)}\\ \vdots & \ddots & \vdots\\ g_\rho\frac{N_\rho(s_1)}{N_\rho(s_1)} & \cdots & g_\rho\frac{N_\rho(s_n)}{N_\rho(s_n)} \end{bmatrix}\\ &= \begin{bmatrix} 1 & \cdots & 1\\ \frac{N_1(s_1)}{N_2(s_1)} & \cdots & \frac{N_1(s_n)}{N_2(s_n)}\\ \vdots & \ddots & \vdots\\ \frac{N_1(s_1)}{N_\rho(s_1)} & \cdots & \frac{N_1(s_n)}{N_\rho(s_n)}\end{bmatrix} \begin{bmatrix}g_\rho \frac{N_\rho(s_1)}{N_1(s_1)}\\&g_\rho\frac{N_\rho(s_2)}{N_1(s_2)}\\&&\ddots\\&&&g_\rho \frac{N_\rho(s_n)}{N_1(s_n)} \end{bmatrix}\\ &\stackrel{\eqref{eqn:inverse46of46norm46equals46norm46of46inverse}}{=} \begin{bmatrix} 1 & \cdots & 1\\ \theta(N_1(s_1^{-1})) & \cdots & \theta(N_1(s_n^{-1}))\\ \vdots & \ddots & \vdots\\ \theta(N_{\rho-1}(s_1^{-1})) & \cdots & \theta(N_{\rho-1}(s_n^{-1}))\end{bmatrix}\\&\qquad \times \underbrace{\begin{bmatrix}g_\rho\theta(N_{\rho-1}(s_1))\\&g_\rho\theta(N_{\rho-1}(s_2))\\&&\ddots\\&&&g_\rho\theta(N_{\rho-1}(s_n)) \end{bmatrix}}_{D} \stepcounter{equation}\label{eq:matrixD}. \end{align}\tag{6}\] Finally, we have shown the following.
Theorem 5. The Generalized Skew Goppa code \(\widetilde{\Gamma}(S,\eta,g,\mathbb{F}_{q^r})\) has a parity-check matrix of the form \[\begin{bmatrix} 1 & \cdots & 1\\ \theta(N_1(s_1^{-1})) & \cdots & \theta(N_1(s_n^{-1}))\\ \vdots & \ddots & \vdots\\ \theta(N_{\rho-1}(s_1^{-1})) & \cdots & \theta(N_{\rho-1}(s_n^{-1}))\end{bmatrix} \cdot DRE,\] where \(D\) is given in 6 and \(R\) and \(E\) are given in 5 , respectively.
We can now compute, under some hypothesis, the rank of the parity-check matrix for \(\widetilde{\Gamma}(S,\eta,g,\mathbb{F}_{q^r})\) using the theorem above.
Theorem 6. Consider the parity-check matrix \(H\) of the Generalized Skew Goppa code \(\widetilde{\Gamma}(S,\eta,g,\mathbb{F}_{q^r})\) and suppose \(S\) is such that \(S^{-1} = \{s_1^{-1},\ldots, s_n^{-1}\}\) is also P-independent. If \(\deg g \leq n\), then \(H\) has rank \(\deg g\).
Proof. Given the reductions of \(H\) to the matrix in 5, we have the following chain of equalities: \[\begin{align} \label{eqn:rank46of46H} \mathrm{rk}(H) &= \mathrm{rk}\begin{bmatrix} 1 & \cdots & 1\\ \theta(N_1(s_1^{-1})) & \cdots & \theta(N_1(s_n^{-1}))\\ \vdots & \ddots & \vdots\\ \theta(N_{\rho-1}(s_1^{-1})) & \cdots & \theta(N_{\rho-1}(s_n^{-1}))\end{bmatrix}\nonumber\\ &= \mathrm{rk}\begin{bmatrix} 1 & \cdots & 1\\ N_1(s_1^{-1}) & \cdots & N_1(s_n^{-1})\\ \vdots & \ddots & \vdots\\ N_{\rho-1}(s_1^{-1}) & \cdots & N_{\rho-1}(s_n^{-1})\end{bmatrix}\nonumber\\ &= \rho = \deg g. \end{align}\tag{7}\] The second equality follows by applying 2 and the last equality follows from the assumption that \(S^{-1}\) is P-independent and [13]. ◻
As an immediate corollary, we obtain the dimension and distance of \(\widetilde{\Gamma}(S,\eta,g,\mathbb{F}_{q^r})\). As mentioned before, those were already known in the literature, hence we skip the proof here.
Corollary 1. Let \(\widetilde{\Gamma}(S, \eta, g, \mathbb{F}_{q^r})\) be a Generalized Skew Goppa code and suppose \(S^{-1}\) is also P-independent. Then \(\widetilde{\Gamma}\) has length \(n\), dimension \(k\) satisfying \[n - \frac{t}{r}\deg g \leq k \leq n - \deg g\] and minimum distance \(d \geq \deg g + 1\).
Remark 7. When \(\theta = \mathrm{id}\), we have \[q_{i,j} = \sum_{l=1}^{\rho-i}g_{i+l}\theta^{i+1}(N_{l-1}(s_j)) = \sum_{l=1}^{\rho-i}g_{i+l}s_j^{l-1}.\] Combined with \(\eta_i =1\) for all \(i =1, \ldots, n\), \(H = H'RE\) (see 5 ) reduces to the usual Goppa code parity-check matrix [11] as expected: \[\begin{align} H'RE = \begin{bmatrix} g_1 & \cdots & g_\rho\\ \vdots & \iddots\\ g_\rho \end{bmatrix}\begin{bmatrix} 1 & \cdots & 1\\ s_1 & \cdots & s_n\\ \vdots & \ddots & \vdots\\ s_1^{\rho-1} & \cdots & s_n^{\rho-1} \end{bmatrix}\begin{bmatrix} g(s_1)^{-1}\\ &\ddots\\ &&g(s_n)^{-1} \end{bmatrix}. \end{align}\]
Remark 8. In [5], the distance of \(\widetilde{\Gamma}\) is proved to be at least \(\deg g + 1\) by providing a decoding algorithm rather than analyzing a parity-check matrix. To argue the rank of \(H\), we needed the additional assumption that \(S^{-1}\) is P-independent. It is an open question if we can derive a parity-check matrix which does not need to resort to \(S^{-1}\) to determine its rank and match the distance bound in [5] in full generality. Also, we note \(\mathrm{rk}_{\mathbb{F}_{q^t}}(H) = \deg g\) is only necessary to establish the upper bound on the dimension, \(k\). The lower bound follows simply from \(\mathrm{rk}_{\mathbb{F}_{q^t}}(H) \leq \deg g\), which is true without any additional assumptions.
Generalized Skew Evaluation (GSE) codes and, specifically, Generalized Skew Reed–Solomon (GSRS) codes have been studied in [7], [19], [20]. Goppa codes in the Hamming metric are known to be subfield subcodes of (duals of) Generalized Reed–Solomon codes. Up to now, this characterization was missing in the skew case. In this subsection, we will use the form of the parity-check matrix constructed so far in this section to show that a Generalized Skew Goppa code is a subfield subcode of the dual of a Generalized Skew Reed–Solomon code (up to automorphism).
Definition 5. Let \(S = \{s_1,\ldots, s_n\} \subseteq \mathbb{F}_{q^t}\) such that \(\mathrm{rk}(V_\theta(s_1,\ldots, s_n)) \geq k\), where \[V_\theta(s_1,\ldots, s_n) := \begin{bmatrix} 1 & \cdots & 1\\ N_1(s_1) & \cdots & N_1(s_n)\\ \vdots & \ddots & \vdots\\ N_{n-1}(s_1) & \cdots & N_{n-1}(s_n) \end{bmatrix}.\] Additionally, choose \(v = \{v_1,\ldots, v_n\} \subseteq \mathbb{F}_{q^t}^*\). The Generalized Skew Evaluation (GSE) code of length \(n\), dimension \(k\), and with evaluation points \(S\) and multiplier weights \(v\) is given by \[\mathrm{GSE}_{k}(S,v) = \{(v_1f(s_1),\ldots, v_nf(s_n)) \, :\, f \in \mathbb{F}_{q^t}[X;\theta], \deg f < k\}.\] If \(\mathrm{rk}(V_\theta(s_1,\ldots, s_n)) = n\), then we call \(\mathrm{GSE}_{k}(S,v)\) a Generalized Skew Reed–Solomon code and denote the code as \(\mathrm{GSRS}_{k}(S,v)\).
The evaluation points \(S\) of a GSRS are P-independent, so any degree \(k-1\) polynomial can vanish on at most \(k-1\) points of \(S\). Therefore, the weight of any codeword is at least \(n-k+1\), but by the Singleton bound, the distance must be exactly \(n-k+1\). Hence, the GSRS codes are MDS. Furthermore, the generator matrix \(G\) for \(\mathrm{GSRS}_{k}(S,v)\) as defined in 5 has the form \[G = \begin{bmatrix}1 & \cdots & 1\\ N_1(s_1) & \cdots & N_1(s_n)\\ \vdots & \ddots & \vdots\\ N_{k-1}(s_1) & \cdots & N_{k-1}(s_n)\end{bmatrix}\begin{bmatrix}v_1\\&v_2\\&&\ddots\\&&&v_n\end{bmatrix}.\] Before proceeding with the main result, we prove the following easy lemma.
Lemma 6. Given a linear code \(C \subseteq \mathbb{F}_{q^t}^n\) and the Frobenius automorphism \(\theta\), we have that \[\theta(C^\perp) = \theta(C)^\perp.\]
Proof. Let \(z \in C^\perp\). Then \(z \cdot c = 0\) for all \(c \in C\). Applying \(\theta\), \[\theta(z\cdot c) = \theta(z)\cdot \theta(c) = 0\] so \(\theta(z) \in \theta(C)^\perp\). This implies \(\theta(C^\perp) \subseteq \theta(C)^\perp\) and by dimension counting, equality follows. ◻
Theorem 9. Let \(\widetilde{\Gamma}(S, \eta, g, \mathbb{F}_{q^r})\) be a Generalized Skew Goppa code and assume \(S^{-1}\) is also P-independent. Let \(u_i = g_\rho\theta(N_{\rho-1}(s_i))g(s_i)^{-1}\eta_i\) for \(i = 1,\ldots, n\). Then \(\widetilde{\Gamma}(S, \eta, g, \mathbb{F}_{q^r})\) is a subfield subcode of \[(\theta(\mathrm{GSRS}_\rho(S^{-1},\theta^{-1}(u))))^\perp = \theta(\mathrm{GSRS}_\rho(S^{-1},\theta^{-1}(u))^\perp).\]
Proof. Consider \(u_i\) as in the theorem statement. Then, we can write the parity-check matrix from 5 as \[TH=\begin{bmatrix} 1 & \cdots & 1\\ \theta(N_1(s_1^{-1})) & \cdots & \theta(N_1(s_n^{-1}))\\ \vdots & \ddots & \vdots\\ \theta(N_{\rho-1}(s_1^{-1})) & \cdots & \theta(N_{\rho-1}(s_n^{-1}))\end{bmatrix} \begin{bmatrix} u_1\\&u_2\\&&\ddots\\&&&u_n \end{bmatrix}.\] Consider the GSRS code of length \(n\), dimension \(\rho = \deg g\), and distance \(n - \rho + 1\) with evaluation points \(S^{-1} = (s_1^{-1},\ldots, s_n^{-1})\) and multiplier weights \(\theta^{-1}(u) := \{\theta^{-1}(u_1),\ldots, \theta^{-1}(u_n)\}\). A generator matrix for \(\mathrm{GSRS}_{\rho}(S^{-1}, \theta^{-1}(u))\) is \[G = \begin{bmatrix}1 & \cdots & 1\\ N_1(s_1^{-1}) & \cdots & N_1(s_n^{-1})\\ \vdots & \ddots & \vdots\\ N_{\rho -1}(s_1^{-1}) & \cdots & N_{\rho -1}(s_n^{-1})\end{bmatrix}\begin{bmatrix}\theta^{-1}(u_1)\\& \theta^{-1}(u_2)\\&&\ddots\\&&& \theta^{-1}(u_n)\end{bmatrix}.\] Notice that \(TH = \theta(G)\) and since the row space of \(G\) is \(\mathrm{GSRS}_\rho(S^{-1},\theta^{-1}(u))\), the row space of \(TH\) is \(\theta(\mathrm{GSRS}_\rho(S^{-1},\theta^{-1}(u)))\) which applies \(\theta\) to each codeword in \(\mathrm{GSRS}_\rho(S^{-1},\theta^{-1}(u))\). Therefore,\[\widetilde{\Gamma}(S, \eta, g, \mathbb{F}_{q^r}) = (\ker_{\mathbb{F}_{q^t}} \theta(G)) \cap \mathbb{F}_{q^r}^n = (\theta(\mathrm{GSRS}_\rho(S^{-1},\theta^{-1}(u))))^\perp \cap \mathbb{F}_{q^r}^n,\] as desired. The commutativity of \(\theta\) with taking duals follows from 6. ◻
Remark 10. Since \(\mathrm{GSRS}_\rho(S^{-1},\theta^{-1}(u))\) is MDS, applying \(\theta\) does not change its dimension or distance. Noting that the dual of an MDS code is MDS (see [21]), we obtain an alternative proof of 1 immediately from the subfield subcode characterization of \(\widetilde{\Gamma}(S,\eta, g, \mathbb{F}_{q^r})\).
The theory we recalled and developed in the previous section will now be extended to multiple variables, in order to construct the multivariate version of Generalized Skew Goppa codes.
To start with, we recall the theory of multivariate Ore polynomial rings as developed in [8], limited here to the “almost commutative" case, that is, when only one variable is non-commutative.
Consider the ring \(\mathbb{F}_{q^t}[X_1,\ldots, X_m;\theta]\) of multivariate Ore polynomials with the usual sum and multiplication given by
\(X_i \cdot X_j = X_j \cdot X_i\)
\(X_i \cdot a = a\cdot X_i, \forall a \in \mathbb{F}_{q^t}\) and \(i = 1,\ldots, m-1\)
\(X_m \cdot a = \theta(a) \cdot X_m, \forall a \in \mathbb{F}_{q^t}\)
where \(\theta\) is the usual \(q\)-Frobenius map. Let \[R = \mathbb{F}_{q^t}[\mathbf{X};\theta] = \mathbb{F}_{q^t}[X_1,\ldots, X_m;\theta].\] The ring \(R\) is “almost" commutative because the only variable which is noncommutative is \(X_m\). Let \[L = \{u = (u_1,\ldots, u_m) \in \mathbb{N}^{m-1} \times t\mathbb{N}\}.\] By [8], the center of \(R\) is \[Z:=\mathbb{F}_q[\mathbf{X}^L] = \left\{\sum_{u\in L}a_uX^u \text{(finite sum)}\, : \, a_u \in \mathbb{F}_q\right\}.\] It follows from 4 that the invariant polynomials of \(R\) are in \(\mathbb{F}_{q^t}\cdot Z \cdot \mathbf{X}^l\), where \(l\in\mathbb{N}^m\).
We now proceed with the definition of Generalized Skew Multivariate Goppa codes. Fix nonempty subsets \(S_1,\ldots, S_m \subseteq \mathbb{F}_{q^t}\) such that the elements in \(S_i\) are distinct for \(i = 1, \ldots, m-1\) and the elements of \(S_m\) are P-independent and \(S_m\) stays P-independent upon inverting each element. Let \(\mathcal{S} = S_1\times\cdots\times S_m \subseteq \mathbb{F}_{q^t}^m\) and let \(n_i = |S_i|\) so \(n:= |\mathcal{S}| = \prod_{i=1}^m n_i\). Enumerate the elements of \(\mathcal{S} = \{\boldsymbol{s}_1,\ldots, \boldsymbol{s}_n\}\) so that \(\boldsymbol{s}_{j} = ({s}_{1j_1},\ldots, {s}_{mj_m})\) for \(j = (j_1,\ldots, j_m)\). For \(i = 1,\ldots, m-1\), let \(g_i \in \mathbb{F}_{q^t}[X_i]\) be an (invariant) polynomial such that \(g_i({s}_{ij_i}) \neq 0\) for each \(j = (j_1,\ldots, j_m) \in \mathcal{S}\). Let \(g_m \in \mathbb{F}_{q^t}[X_m;\theta]\) be an invariant polynomial such that \((X_m -{s}_{mj_m}, g_m)_r = 1\) for each \(j = (j_1,\ldots, j_m) \in \mathcal{S}\). Lastly, let \(g = g_1\cdots g_m\) and define \(\deg g = \prod_{i=1}^m \deg g_i\).
For each \(i = 1,\ldots, m\) and each \(j_i = 1,\ldots, n_i\), let \(h_{ij_i}\) be the unique polynomial such that \(\deg h_{ij_i} < \deg g_i\) and \[h_{ij_i}(X_i - {s}_{ij_i}) - 1 \in Rg_i.\] In particular, dividing \(g_i\) on the right by \(X_i - s_{ij_i}\), we obtain \[g_i = q_{ij_i}(X_i - s_{ij_i}) + r_{ij_i} = q_{ij_i}(X_i - s_{ij_i}) + g_i(s_{ij_i}).\] Hence, setting \(h_{ij_i} = -g_i(s_{ij_i})^{-1} q_{ij_i}\), gives the desired polynomial (just as in 3.2). Let \(h_j = h_{1j_1}\cdots h_{mj_m}\) for \(j = (j_1,\ldots, j_m) \in \mathcal{S}\). Lastly, choose \(\eta_1,\ldots, \eta_{n_m} \in \mathbb{F}_{q^t}^*\), and for \(j = (j_1,\ldots, j_m) \in \mathcal{S}\), define \(\eta_j = \eta_{j_m}\).
Definition 6. Let \(\mathcal{S}, \eta,g\) and \(h_j\) for \(j = (j_1,\ldots, j_m) \in \mathcal{S}\) be as above. Let \(r\mid t\) be an integer. The Generalized Skew Multivariate Goppa (GSMG) code \(\widetilde{\Gamma}(\mathcal{S}, \eta,g,\mathbb{F}_{q^r})\subseteq \mathbb{F}_{q^r}^n\) is defined as \[\begin{align} \widetilde{\Gamma}(\mathcal{S}, \eta,g,\mathbb{F}_{q^r}) &= \left\{c= (c_j)_{j \in \mathcal{S}} \in \mathbb{F}_{q^r}^{\mathcal{S}} \, : \, \sum_{j \in \mathcal{S}} c_j\eta_jh_j = 0 \right\}\\ &= \left\{c= (c_j)_{j \in \mathcal{S}} \in \mathbb{F}_{q^r}^{\mathcal{S}} \, : \, \sum_{j \in \mathcal{S}} c_j\eta_jh_j \in Rg \right\}. \end{align}\]
Note that we are fixing a particular enumeration of \(\mathcal{S}\) which gives a bijection between elements of \(\mathcal{S}\) and integers \(\{1,\ldots, n\}\).
6 admits the Multivariate Goppa code ([3], see 2) as a special case, which we recover when \(\eta_j = 1\) for all \(j\) and \(\theta = \mathrm{id}\). It also recovers the Generalized Skew Goppa code ([5], see 4) as a special case when \(m = 1\).
We start by constructing a parity-check matrix in order to deduce the dimension and distance of the GSMG code.
Fix an element \(\boldsymbol{s}_j\). We will determine \(h_{ij_i}\) for each \(i = 1,\ldots, m\). Let \(\deg g_i = \rho_i\). We already showed the structure of \(h_{mj_m}\) in 4 and by specializing to \(\theta = \mathrm{id}\), we obtain \[\begin{align} q_{ij_i} = \sum_{b=0}^{\rho_i-1}q_{ij_i,b}X_i^b = \sum_{b=0}^{\rho_i-1}\sum_{l = b+1}^{\rho_i}s_{ij_i}^{l-b-1}g_{i,l}X_i^b. \end{align}\] Additionally, \[g(\boldsymbol{s}_j) = g_1({s}_{1j_1})\cdots g_m({s}_{mj_m}).\] We defined \(h_j = h_{1j_1}\cdots h_{mj_m}\) so writing \[\begin{align} H_i &= \begin{bmatrix} q_{i1,0} &\cdots &q_{in_i,0}\\ \vdots &\ddots &\vdots\\ q_{i1,\rho_i-1} &\cdots & q_{in_i,\rho_i-1} \end{bmatrix},\\ R_i &= \begin{bmatrix} g_i({s}_{i1})^{-1}\\ &\ddots\\ && g_i({s}_{in_i})^{-1} \end{bmatrix},\\ \text{ and } E &= \begin{bmatrix} \eta_1\\&\ddots \\&&\eta_n \end{bmatrix} \end{align}\] a parity-check matrix for GSMG is \[H:=\left(\bigotimes_{i=1}^m H_iR_i\right)E.\] Equivalently, \(\widetilde{\Gamma}(\mathcal{S}, \eta,g,\mathbb{F}_{q^r})\) is a subfield subcode of the dual of the tensor product code \[\widetilde{T}(\mathcal{S},g) := \left(\bigotimes_{i=1}^{m-1} \mathrm{GRS}_{\rho_i}(S_i,g_i)\right)\otimes \theta(\mathrm{GSRS}_{\rho_m}(S_m^{-1}, \theta^{-1}(u)))\] where \(u = (u_1,\ldots, u_{n_m})\) and \(u_{j_m} = g_{m,\rho_m}\theta(N_{\rho_m-1}({s}_{mj_m}))g_m({s}_{mj_m})^{-1}\eta_{j_m}\) for \(j_m = 1,\ldots n_m\).
Utilizing the expression of \(\widetilde{\Gamma}(\mathcal{S}, \eta,g,\mathbb{F}_{q^r})\) as a subfield subcode of the dual of the tensor product code \(\widetilde{T}(\mathcal{S},g)\), we obtain the following result.
Theorem 11. The Generalized Skew Multivariate Goppa code \(\widetilde{\Gamma}(\mathcal{S},\eta, g, \mathbb{F}_{q^r})\) has parameters:
Length \(n = |\mathcal{S}|\),
Dimension \(k\) satisfying \(n - \frac{t}{r}\deg g\leq k \leq n -\deg g\),
Minimum distance \(d \geq \min_{i\in [m]}\{\deg g_i + 1\}\).
Proof. The length is obvious. Let \(k = \dim \widetilde{\Gamma}(\mathcal{S},\eta, g, \mathbb{F}_{q^r})\). Since \(\widetilde{T}(\mathcal{S},g)\) has dimension \(\deg g\), its dual \((\widetilde{T}(\mathcal{S},g))^\perp\) has dimension \(n - \deg g\) and \(\widetilde{\Gamma}(\mathcal{S}, \eta,g,\mathbb{F}_{q^r})\) is a subfield subcode of \((\widetilde{T}(\mathcal{S},g))^\perp\) so \(\dim \widetilde{\Gamma}(\mathcal{S},\eta, g, \mathbb{F}_{q^r}) \leq n - \deg g\). We now show the lower bound on the dimension.
By Delsarte’s Theorem (1), we have that for a code \(C\) over \(\mathbb{F}_{q^t}\), \[\require{physics} \left(C \cap \mathbb{F}_{q^r}^n\right)^\perp = \Tr(C^\perp),\] and \(\require{physics} \Tr: C \to \Tr(C)\) is a surjective \(\mathbb{F}_{q^r}\)-linear mapping, so the dimension of \(C\) regarded as a \(\mathbb{F}_{q^r}\) vector space is \(\frac{t}{r}\cdot \dim C\). Applying this result to \[\require{physics} \widetilde{\Gamma}(\mathcal{S}, \eta,g,\mathbb{F}_{q^r}) = \left(\Tr(\widetilde{T}(\mathcal{S},g))\right)^\perp\] we have \[\require{physics} \dim \Tr(\widetilde{T}(\mathcal{S},g)) \leq \frac{t}{r}\deg g\] which implies \[\dim \widetilde{\Gamma}(\mathcal{S}, \eta,g,\mathbb{F}_{q^r}) \geq n - \frac{t}{r}\deg g.\]
By 1, the minimum distance of \((\widetilde{T}(\mathcal{S},g))^\perp\) is \(\min_{i\in [m]}\{\deg g_i + 1\}\) and the minimum distance of \(\widetilde{\Gamma}(\mathcal{S}, \eta,g,\mathbb{F}_{q^r})\) follows. ◻
Remark 12. The hypothesis on \(S_m\) preserving P-independence under inversion is used only to argue the subfield subcode property of the GSMG code. The distance bound still holds because [5] shows the distance of a GSG code is at least \(\deg g_m + 1\). Hence, there must be some parity-check matrix \(H_m\) such that every set of \(\deg g_m\) columns is independent. For further details see 8.
In this paper, we constructed a multivariate version of Skew Goppa codes by using the multivariate Ore polynomial ring \(\mathbb{F}_{q^t}[X_1,\ldots, X_m;\theta]\), where the only noncommutative variable is the last one. For the sake of completeness, one could study a more general multivariate construction from the ring \(\mathbb{F}_{q^t}[X_1,\ldots, X_m;\theta_1,\dots,\theta_m]\). However, note that even for the linearized Reed–Muller codes of [8], the “almost commutative" case is the one giving the best parameters.
We also showed that Generalized Skew Goppa codes are subfield subcodes of Generalized Skew Reed–Solomon codes. We were able to prove this result under the condition that the inverse set \(S^{-1}\) of the P-independent set \(S\) is itself P-independent. It is an open question if we can derive a parity-check matrix which does not need to resort to \(S^{-1}\) to match the one of GSRS codes.
Finally, we believe it would be interesting to study the relation between GSG codes and the linearized Goppa codes introduced in [6] using skew residues.