Elimination Algorithms for Skew Polynomials with Applications in Cybersecurity

Abstract

It is evident that skew polynomials offer promising directions for developing cryptographic schemes. This paper focuses on exploring skew polynomials and studying their properties with the aim of exploring their potential applications in fields such as cryptography and combinatorics. We begin by deriving the concept of resultants for bivariate skew polynomials. Then, we employ the derived resultant to incrementally eliminate indeterminates in skew polynomial systems, utilising both direct and modular approaches. Finally, we discuss some applications of the derived resultant, including cryptographic schemes (such as Diffie–Hellman) and combinatorial identities (such as Pascal’s identity). We start by considering a bivariate skew polynomial system with two indeterminates; our intention is to isolate and eliminate one of the indeterminates to reduce the system to a simpler form (that is, relying only on one indeterminate in this case). The methodology is composed of two main techniques; in the first technique, we apply our definition of a (bivariate) resultant via a Sylvester-style matrix directly from the polynomials’ coefficients, while the second is based on modular methods where we compute the resultant by using evaluation and interpolation approaches. The idea of this second technique is that instead of computing the resultant directly from the coefficients, we propose to evaluate the polynomials at a set of valid points to compute its corresponding set of partial resultants first; then, we can deduce the original resultant by combining all these partial resultants using an interpolation technique by utilising a theorem we have established.

1. Introduction

Naturally, computations with polynomials in multivariate (commutative or noncommutative) polynomial rings are essential in computer algebra and have broad applications in both computer science and mathematics; some areas of interest include cryptography, combinatorics, and coding theory.

Skew polynomials represent a generalisation of ordinary polynomials, characterised by a (not necessarily commutative) multiplication rule.

This study focuses on bivariate skew polynomials and explores the feasibility of a novel resultant of multivariate skew polynomials, with the aim of exploring their potential applications in fields such as cryptography. Given the ongoing research in this field, it is evident (e.g., [1]) that skew polynomials offer a promising direction for developing new cryptographic schemes due to the increased complexity of computations involving skew polynomials as well as the limited availability of tools and techniques in noncommutative algebras that could be used by attackers to recover or decrypt the information.

Skew polynomials (or Ore polynomials) were first introduced by Ore in 1933 [2]. Chyzak and Salvy studied elimination through Gröbner bases in noncommutative algebra in 1996 [3]. Collins, in 1967 [4], used the Sylvester matrix to compute the determinant in the commutative case. The resultant of univariate skew polynomials was studied by Li in 1998 [5] and by Vesnik and Eric in 2008 [6]. Modular methods from commutative algebra were used for solving nonlinear polynomial systems through resultant by Rasheed in 2007 [7]. Evaluation and interpolation techniques for skew polynomial multiplication were considered by Caruso and Le Borgne in 2017 [8] and by Giesbrecht, Huang, and Schost in 2020 [9]. Fairly recently, Rasheed described resultant-based methods for skew elimination in 2021 [10]. Expanding upon the foundation established in [10], this study offers a comprehensive understanding of the entire process, including the new part of interpolation stage, which was not addressed in the earlier work [10], along with some potential applications enhancing the study’s applicability to relevant use cases.

At its core, this paper presents novel elimination methods for multivariate (initially bivariate) skew polynomial systems, transforming them into another that is simpler than the originals.

Working with skew polynomials (in noncommutative algebra) poses various challenges. Not only does the noncommutative nature of the algebra introduce its own challenges, but  essential tools for elimination (such as resultant) have also not been available for multivariate skew polynomials (not even for the bivariate case) until fairly recently, as described in [10]. Additionally, the evaluation map is not common in the noncommutative algebra as it does not preserve multiplication. A determinant is another challenge that does not have a standard formulation for computing a unique determinant. We need to discuss noncommutative analogs of these components to address the gaps. Section 4.2 and Section 4.3 will explore these challenges, as well as any additional ones encountered, along with the techniques we used to overcome each one.

What is new is that, in comparison to the previous study [10], the main improvements and additions in this new version are as follows.

First, the study derives the resultant formula and establishes a theorem (along with its proof) stating that the resultant of two operator polynomials annihilates any common solution of those polynomials.

Second, the interpolation part, which was briefly mentioned in the previous study [10] and left for future work, is now thoroughly examined by addressing and overcoming the challenges associated with it; this step is illustrated by examples.

Third, the feasibility of this research approach is studied and applied to some applications. An example is the use of one of the established theorems to identify new identities with fewer indeterminates, as demonstrated in a provided example. Furthermore, the techniques developed in this study can be used to establish a Diffie–Hellman key exchange between two users, a widely recognised cryptographic protocol for secure key exchange over a public channel.

2. Background

This part provides background information for this paper.

2.1. Ore Polynomial Rings

The use of Ore polynomial rings is a convenient way of unifying some classes of (noncommutative) polynomial rings; for example, it can analogously be applied to linear differential equations, linear difference equations, and other similar substances. A benefit of this model is that all the operations can be studied and implemented once, and then they can suitably be applied to all the substances. The following is the definition of an Ore polynomial ring [2].

Definition 1

(Ore polynomial ring). Let σ be a ring automorphism of a (skew) field $\mathcal{F}$, and let δ be a σ-derivation of $\mathcal{F}$. The Ore polynomial ring $\mathcal{F}[\theta ;\sigma ,\delta ]$ is the set of polynomials in indeterminate θ over $\mathcal{F}$ with the usual polynomial addition and noncommutative multiplication defined as

$$\theta a=\sigma \left(a\right)\theta +\delta \left(a\right),\forall a\in \mathcal{F}.$$

(1)

Elements of $\mathcal{F}[\theta ;\sigma ,\delta ]$ are called (univariate) Ore polynomials or Ore operators.

Table 1. Some examples of Ore operators in $\mathcal{K}\left(t\right)[\theta ;\sigma ,\delta ]$ for  some field $\mathcal{K}$.

$\mathcal{F}$	Operator	$\mathit{\sigma }\left(\mathit{a}\right(\mathit{t}\left)\right)$	$\mathit{\delta }\left(\mathit{a}\right(\mathit{t}\left)\right)$	Commutation Rule of $\mathit{\theta }\mathit{t}$
	Differential	$a\left(t\right)$	$a^{\prime }\left(t\right)={\displaystyle \frac{d}{dt}}\left(a\left(t\right)\right)$	$t\theta +1$
$\mathcal{K}\left(t\right)$	Difference	$a(t+1)$	$a(t+1)-a\left(t\right)$	$(t+1)\theta +1$
	Shift	$a(t+1)$	0	$(t+1)\theta$
	Eulerian	$a\left(t\right)$	$t{a}^{\prime }\left(t\right)$	$t\theta +t$
$\mathcal{K}(q,t)$	q-differential	$a\left(qt\right)$	${\displaystyle \frac{a\left(qt\right)-a\left(t\right)}{(q-1)t}}$	$qt\theta +1$
$q\in \mathbb{Q}\setminus \{0,1,-1\}$	q-difference	$a\left(qt\right)$	$a\left(qt\right)-a\left(t\right)$	$qt\theta +(q-1)t$
	q-shift	$a\left(qt\right)$	0	$qt\theta$

contains some examples of Ore operators with their commutation rules of $\theta t$ over a (skew) field $\mathcal{F}$; for more examples, please see [3].

Remark 1.

The case when $\delta =0$ in Definition 1 is called skew polynomial ring (the term skew polynomial ring may refer to a different ring in some references) and denoted by $\mathcal{F}[\theta ,\sigma ]$. The  ordinary commutative polynomial ring is a special case of Ore polynomial ring when σ is an identity map of a commutative ring $\mathcal{F}$ in addition to $\delta =0$, which means the results in this study can be applied to the commutative case as well.

We can construct a bivariate Ore polynomial ring by iterating the univariate case of Definition 1 to have a ring of Ore polynomials in two indeterminates with coefficients in the univariate Ore polynomial ring. This process can be extended to have multivariate Ore polynomials in general as defined below for the case when $\delta =0$, the specific case under consideration in this paper. The following definition is used in ([10], Definition 2); similar definitions can be found in ([11], Definition 46.13.1, p. 85) and ([12], Note 3.16, p. 28).

Definition 2.

A multivariate skew polynomial ring over $\mathcal{F}$ is the iterated skew polynomial ring $\mathcal{S}=\mathcal{F}[{\theta }_1;{\sigma }_1][{\theta }_2;{\sigma }_2]\cdots [{\theta }_n;{\sigma }_n]$ with commuting indeterminates ${\theta }_i$ and automorphisms ${\sigma }_i$ of $\mathcal{F}$ that satisfy the following relations;

$${\sigma }_j\left({\theta }_i\right)={\theta }_i(i\ne j),{\sigma }_j{\sigma }_i={\sigma }_i{\sigma }_{j}and{\theta }_{i}a={\sigma }_i\left(a\right){\theta }_i,forall1\le i,j\le nanda\in \mathcal{F}.$$

(2)

Note that a skew polynomial ring $\mathcal{F}[{\theta }_1;{\sigma }_1][{\theta }_2;{\sigma }_2]\cdots [{\theta }_n;{\sigma }_n]$ is sometimes written in a recursive form such that, for all $i=1,\dots ,n$, ${\mathcal{S}}_i=\left({\mathcal{S}}_{i-1}\right)[{\theta }_i;{\sigma }_i,{\delta }_i]$ where ${\mathcal{S}}_0=\mathcal{F}$. For example, we may write $\left(\mathcal{F}[{\theta }_1;{\sigma }_1]\right)[{\theta }_2;{\sigma }_2]$ instead of $\mathcal{F}[{\theta }_1;{\sigma }_1][{\theta }_2;{\sigma }_2]$, which is our primary initial focus. We assume that $\mathcal{F}[{\theta }_1;{\sigma }_1]$ is a domain, unless noted otherwise.

Also, in this study, all Ore polynomials are left Ore polynomials, which are in the form $f={\sum }_{i=0}^n{a}_i{\theta }^i$ in $\mathcal{F}[\theta ;\sigma ]$. Let $\mathcal{S}=\mathcal{F}[\theta ;\sigma ]$ and consider $\mathcal{V}$ to be an $\mathcal{S}$-module. Any pseudo linear map $\mathsf{\phi }:\mathcal{V}\to \mathcal{V}$ can create an action operation (denoted by · ) on a member $\mathbf{u}$ in $\mathcal{V}$ as follows:

$$·:\begin{array}{cc}& \mathcal{F}[\theta ;\sigma ]\times \mathcal{V}\to \mathcal{V}\hfill \\ {\displaystyle f\left(\theta \right)·\mathbf{u}=}\hfill & {\displaystyle \left(\sum _{i=0}^n{a}_i{\theta }^i\right)·\mathbf{u}\mapsto f\left(\mathsf{\phi }\right)\left(\mathbf{u}\right)=\sum _{i=0}^n{a}_i{\mathsf{\phi }}^i\left(\mathbf{u}\right).}\hfill \end{array}$$

(3)

Sometimes the dot $·$ is omitted for simplicity. If $f\left(\mathsf{\phi }\right)\left(a\right)=0$ for some $a\in \mathcal{F}$, then we say $\mathbf{u}=a$ is a solution of $f\left(\mathsf{\phi }\right)\left(\mathbf{u}\right)=0$. Similarly, for the bivariate case, when we have the map $f({\theta }_1,{\theta }_2)·\mathbf{u}\mapsto f({\mathsf{\phi }}_1,{\mathsf{\phi }}_2)\left(\mathbf{u}\right)$, for some pseudo linear maps ${\mathsf{\phi }}_1$ and ${\mathsf{\phi }}_2$, then $\mathbf{u}=a$ is a solution of f if $f({\mathsf{\phi }}_1,{\mathsf{\phi }}_2)\left(\mathbf{u}\right)=0$.

2.2. Euclidean Domain

In this section, we review the definition of a Euclidean domain and illustrate that bivariate skew polynomials, along with their multivariate extensions (involving two or more indeterminates) do not satisfy the properties of a Euclidean domain.

Definition 3.

A (not necessarily commutative) domain $\mathcal{R}$, endowed with a map

$$N:\mathcal{R}\setminus \left\{0\right\}\to {\mathbb{N}}_0,$$

is a right Euclidean domain with respect to N if the following properties hold for all $f,g\ne 0\in \mathcal{R}$

(i) There exist $q,r\in \mathcal{R}$ such that

$$f=gq+r,\mathrm{where}r=0\mathrm{or}N\left(r\right)<N\left(g\right),$$

(4)

(ii) $N\left(f\right)\le N\left(fg\right)$.

The elements q and r in (4) are called the right quotient (denoted by rquo) and right remainder (denoted by rrem), respectfully, of the right division of f by g. If $r=0$, then g is called a right divisor of f in $\mathcal{R}$. The left Euclidean domain uses analogous conventions and notations. A ring that is both left and right Euclidean domain is called a Euclidean domain.

In the context of a skew polynomial ring $\mathcal{R}=\mathcal{F}[\theta ;\sigma ]$, where N denotes the degree deg, if f and g are elements of $\mathcal{F}[\theta ;\sigma ]$, we can obtain a quotient q and a remainder r using the Euclidean division algorithm, which depends on the presence of invertible elements in $\mathcal{F}$. However, if the underlying ring of coefficients is not a division ring, the Euclidean division algorithm cannot be applied, as illustrated in the following example.

Example 1.

Let $\mathcal{R}=\left(\mathcal{F}[{\theta }_1;{\sigma }_1]\right)[{\theta }_2;{\sigma }_2]$ be a bivariate skew polynomial ring. Consider the attempt to divide $f={\theta }_2$ by $g={\theta }_1$, where we seek $q,r\in \mathcal{R}$ such that ${\theta }_2={\theta }_{1}q+r$ and ${deg}_{{\theta }_2}\left(r\right)<{deg}_{{\theta }_2}\left({\theta }_1\right)=0$. Since ${deg}_{{\theta }_2}\left({\theta }_2\right)=1$ and ${deg}_{{\theta }_2}\left({\theta }_1\right)=0$, the condition ${deg}_{{\theta }_2}\left(r\right)<0$ is impossible even if $\mathcal{F}$ is a field. Therefore, no such q and r exist, indicating that $\mathcal{R}$ is not a Euclidean domain.

Section 3.2 further examines this issue and presents a method for a key property related to relation (8).

3. Elimination

Many models of mathematical physics and engineering can be described in terms of extra indeterminates (or extra parameters), which are present usually in mixed forms; then, it becomes helpful to eliminate one or more of these extra indeterminates through an elimination method.

In this section, we will study how our approaches can be used to eliminate such extra indeterminates in a system of bivariate skew polynomial equations while retaining the original model’s behaviour, i.e., retaining the way the system acts. Furthermore, we show how to use a Euclidean relation to derive a formula that can compute the resultant directly from the polynomial’s coefficients, generalising the commutative case of Sylvester’s determinant and the noncommutative univariate case of [6]; then, we describe elimination methods of bivariate skew polynomials based on our resultant computations. Consequently, a suitable noncommutative formulation of a determinant is needed and for this, we use the Dieudonné determinant.

3.1. Dieudonné Determinant of Matrices with Skew Polynomial Entries

From the perspective of normal forms of matrices, one can think of diagonalising (or triangularising) an invertible $n\times n$ matrix A over $\mathcal{F}[\theta ;\sigma ]$ to obtain

$$D=UAV=\mathrm{diag}(d_1,\cdots ,d_n),$$

(5)

where U and V are unimodular matrices, D is a diagonal matrix with diagonal entries $d_i\in \mathcal{F}(\theta ;\sigma ),i=1,\cdots ,n$. Knowing that the Dieudonné determinant of a diagonal (or a triangular matrix) is the product of the diagonal entries (see, for example, [13] p. 822 or [14] p. 3 Example 2), we can obtain the Dieudonné determinant of D as

$$det\left(D\right)=[\prod d_i].$$

(6)

Please note that in general, the entries $d_i$ may become rational functions in $\mathcal{F}(\theta ;\sigma )$ rather than remaining polynomials in $\mathcal{F}[\theta ;\sigma ]$. However, for the purpose of this study, we need to perform the computations in such a way that the entries remain polynomials, especially the diagonal entries $d_i$. This ensures that their product $\prod d_i$, which is the determinant, also remains a polynomial in $\mathcal{F}[\theta ;\sigma ]$, and this can be achieved according to the following lemma (from [10], Lemma 11).

Lemma 1.

The Dieudonné determinant of a matrix $A\in \mathcal{F}{[\theta ;\sigma ]}^{n\times n}$ can be represented by a unique skew polynomial (modulo commutators).

Remark 2.

To compute the Dieudonné determinant in Lemma 1, one approach is to use elementary row operations by using the Ore condition in order to transform the matrix into a diagonal (or a triangular) form. Thus, the  determinant can be computed by simply multiplying the elements on the main diagonal. For more details, please see [10].

Another useful property of the Dieudonné determinant is that it does not depend on the choice of elementary row operations, neither on the order in the product of diagonal entries of the matrix, despite the noncommutative nature of the entries (see, for example, [13] p. 822). Furthermore, an important feature of Dieudonné determinant is that it preserves multiplication; that is,

$$det\left(AB\right)=det\left(A\right)det\left(B\right),$$

(7)

for any two invertible matrices $A,B$ over $\mathcal{F}[\theta ;\sigma ]$.

3.2. Deriving a Resultant Formula for Bivariate Skew Polynomials

It is evident that we can employ the extended Euclidean algorithm in its skew version (see Algorithm 1) to find the greatest common right divisor, denoted by gcrd. Additionally, the same algorithm can be used (by permitting $r_{i-1}=0$ in the algorithm) to derive the following relation for any two skew polynomials f and g in $\mathcal{F}[\theta ;\sigma ]$;

$$uf=vg,$$

(8)

for some non-zeros $u,v\in \mathcal{F}[\theta ;\sigma ]$ such that degrees of u and v are less than the degrees of g and f, respectively.

Algorithm 1: Skew extended euclidean algorithm
	Input: $f,g\in \mathcal{F}[\theta ;\sigma ]$, where $\mathcal{F}$ is a (skew) field
	Output: $d\in \mathcal{F}[\theta ;\sigma ]$, where d is a gcrd of f and g together with $s,t\in \mathcal{F}[\theta ;\sigma ]$ such that $sf+tg=d$
1	$r_0$ := f; $s_0$ := 1; $t_0$ := 0
2	$r_1$ := g; $s_1$ := 0; $t_1$ := 1
3	i := 2
4	while $r_{i-1}\ne 0$ repeat
5	$q_i$ := $r_{i-2}rquo{r}_{i-1}$       // rquo is the right quotient
6	$r_i$ := $r_{i-2}rrem{r}_{i-1}$       // rrem is the right remainder
7	$s_i$ := $s_{i-2}-q_i{s}_{i-1}$
8	$t_i$ := $t_{i-2}-q_i{t}_{i-1}$
9	i := $i+1$
10	return ($r_{i-2},s_{i-2},t_{i-2}$)

While effective for univariate cases, the algorithm fails for the bivariate cases in $\mathcal{F}[{\theta }_1;{\sigma }_1][{\theta }_2;{\sigma }_2]$ due to the domain not being a Euclidean domain anymore.

Now, let us examine the relation (8) more closely in the bivariate case $\mathcal{F}[{\theta }_1;{\sigma }_1][{\theta }_2;{\sigma }_2]$ as $f={\sum }_{j=0}^n{a}_j{\theta }_2^j,g={\sum }_{j=0}^m{b}_j{\theta }_2^j,u={\sum }_{i=0}^{m-1}{u}_i{\theta }_2^i$, and $v={\sum }_{i=0}^{n-1}{v}_i{\theta }_2^i,$ with polynomial coefficients $a_j,b_j,u_i,and{v}_i$ in $\mathcal{F}[{\theta }_1;{\sigma }_1]$, such that the relation $uf=vg$ then becomes

$$\sum _{i=0}^{m-1}\sum _{j=0}^n{u}_i{\sigma }^i\left(a_j\right){\theta }_2^{i+j}=\sum _{i=0}^{n-1}\sum _{j=0}^m{v}_i{\sigma }^i\left(b_j\right){\theta }_2^{i+j}.$$

(9)

Thus, by comparing the coefficients on both sides of (9), we can obtain a system of $n+m$ equations for the unknowns $u_i$ ($i=0,\dots ,m-1$) and $-v_i$ ($i=0,\dots ,n-1$) as follows:

$$\left\{\begin{array}{cccc}{u}_{m-1}{a}_n^{[m-1]}\hfill & \hfill =& v_{n-1}{b}_m^{[n-1]}\hfill & \\ u_{m-1}{a}_{n-1}^{[m-1]}+u_{m-2}{a}_n^{[m-2]}\hfill & \hfill =& v_{n-1}{b}_{m-1}^{[n-1]}+v_{n-2}{b}_m^{[n-2]}\hfill & \\ u_{m-1}{a}_{n-2}^{[m-1]}+u_{m-2}{a}_{n-1}^{[m-2]}+u_{m-3}{a}_n^{[m-3]}\hfill & \hfill =& v_{n-1}{b}_{m-2}^{[n-1]}+v_{n-2}{b}_{m-1}^{[n-2]}+v_{n-3}{b}_m^{[n-3]}\hfill & \\ ⋮⋮\hfill & \hfill ⋮& ⋮\hfill & \\ u_1{a}_0^{\left[1\right]}+u_0{a}_1^{\left[0\right]}\hfill & \hfill =& v_1{b}_0^{\left[1\right]}+v_0{b}_1^{\left[0\right]}\hfill & \\ u_0{a}_0^{\left[0\right]}\hfill & \hfill =& v_0{b}_0^{\left[0\right]}\hfill & \end{array}\right.$$

(10)

where, for each $i=1,\dots ,m$, the sequence $a_j^{[\mathrm{m}-\mathrm{i}]}$ ($j=n,\dots ,0$) represents the coefficients of the multiplication ${\theta }_2^{m-i}f$, while for each $i=1,\dots ,n$, the sequence $b_j^{[\mathrm{n}-\mathrm{i}]}$ ($j=m,\dots ,0$) represents the coefficients of the multiplication ${\theta }_2^{n-i}g$. It is worth noting that they are free of the indeterminate ${\theta }_2$. Accordingly, an associate determinant for the system (10) can be formulated as follows:

$$\left|\begin{array}{cccccccc}{a}_n^{[m-1]}& a_{n-1}^{[m-1]}& \cdots & \cdots & a_0^{[m-1]}& & & \\ & a_n^{[m-2]}& a_{n-1}^{[m-2]}& \cdots & \cdots & a_0^{[m-2]}& & \\ & & & & \ddots & & & \\ & & & a_n^{\left[0\right]}& a_{n-1}^{\left[0\right]}& \cdots & \cdots & a_0^{\left[0\right]}\\ b_m^{[n-1]}& b_{m-1}^{[n-1]}& \cdots & b_0^{[n-1]}& & & & \\ & b_m^{[n-2]}& b_{m-1}^{[n-2]}& \cdots & b_0^{[n-2]}& & & \\ & & & & \ddots & & & \\ & & & b_m^{\left[1\right]}& b_{m-1}^{\left[1\right]}& \cdots & b_0^{\left[1\right]}& \\ & & & & b_m^{\left[0\right]}& b_{m-1}^{\left[0\right]}& \cdots & b_0^{\left[0\right]}\end{array}\right|.$$

This is a determinant of a matrix whose entries are univariate skew polynomials of ${\theta }_1$ that are noncommutative in $\mathcal{F}[{\theta }_1;{\sigma }_1]$, and for this, we use the Dieudonné determinant.

Remark 3.

In order to have a nontrivial solution for the above system, we need to ensure that the determinant is equal to zero.

We now have a definition of resultant [10] for bivariate skew polynomials based on the Dieudonné determinant as formally described below.

Definition 4.

Consider two bivariate skew polynomials $f={\sum }_{i=0}^n{a}_i\left({\theta }_1\right){\theta }_2^i$ and $g={\sum }_{j=0}^m{b}_j\left({\theta }_1\right){{\theta }_2}^j$ in $\left(\mathcal{F}[{\theta }_1;{\sigma }_1]\right)[{\theta }_2;{\sigma }_2]$ where $a_i\left({\theta }_1\right),b_j\left({\theta }_1\right)\in \mathcal{F}[{\theta }_1;{\sigma }_1]\subset \mathcal{F}({\theta }_1;{\sigma }_1)$. We define the resultant of f and g with respect to ${\theta }_2$ over $\mathcal{F}({\theta }_1;{\sigma }_1)$ (denoted by ${\mathrm{res}}_{{\theta }_2}(f,g)$) by the following Dieudonné determinant

$${\mathrm{res}}_{{\theta }_2}(f,g)=\begin{array}{c}\hfill {\theta }_2^{m-1}f\\ \hfill {\theta }_2^{m-2}f\\ \hfill ⋮\\ \hfill f& \\ \hfill {\theta }_2^{n-1}g\\ \hfill {\theta }_2^{n-2}g\\ \hfill ⋮\\ \hfill {\theta }_{2}g\\ \hfill g\end{array}\left|\begin{array}{cccccccc}{a}_n^{[\mathrm{m}-1]}\left({\theta }_1\right)& a_{n-1}^{[\mathrm{m}-1]}\left({\theta }_1\right)& \cdots & \cdots & a_0^{[\mathrm{m}-1]}\left({\theta }_1\right)& & & \\ & a_n^{[\mathrm{m}-2]}\left({\theta }_1\right)& a_{n-1}^{[\mathrm{m}-2]}\left({\theta }_1\right)& \cdots & \cdots & a_0^{[\mathrm{m}-2]}\left({\theta }_1\right)& & \\ & & & & \ddots & & & \\ & & & a_n^{\left[0\right]}\left({\theta }_1\right)& a_{n-1}^{\left[0\right]}\left({\theta }_1\right)& \cdots & \cdots & a_0^{\left[0\right]}\left({\theta }_1\right)\\ b_m^{[\mathrm{n}-1]}\left({\theta }_1\right)& b_{m-1}^{[\mathrm{n}-1]}\left({\theta }_1\right)& \cdots & b_0^{[\mathrm{n}-1]}\left({\theta }_1\right)& & & & \\ & b_m^{[\mathrm{n}-2]}\left({\theta }_1\right)& b_{m-1}^{[\mathrm{n}-2]}\left({\theta }_1\right)& \cdots & b_0^{[\mathrm{n}-2]}\left({\theta }_1\right)& & & \\ & & & & \ddots & & & \\ & & & b_m^{\left[1\right]}\left({\theta }_1\right)& b_{m-1}^{\left[1\right]}\left({\theta }_1\right)& \cdots & b_0^{\left[1\right]}\left({\theta }_1\right)& \\ & & & & b_m^{\left[0\right]}\left({\theta }_1\right)& b_{m-1}^{\left[0\right]}\left({\theta }_1\right)& \cdots & b_0^{\left[0\right]}\left({\theta }_1\right)\end{array}\right|,$$

where the i-th row ($i=1,\dots ,m$) contains the coefficient sequence of the multiplication ${\theta }_2^{m-i}f$ and the coefficients of this multiplication are denoted by $a_j^{[\mathrm{m}-\mathrm{i}]}\left({\theta }_1\right)$ ($j=n,\dots ,0$). Similarly, the $(m+i)$-th row ($i=1,\dots ,n$), contains the coefficients of ${\theta }_2^{n-i}g$, these coefficients are denoted by $b_j^{[\mathrm{n}-\mathrm{i}]}\left({\theta }_1\right)$ ($j=m,\dots ,0$). Thus, for notational simplicity, we can write the resultant ${\mathrm{res}}_{{\theta }_2}(f,g)$ in the form

$${\mathrm{res}}_{{\theta }_2}(f,g)=det({\theta }_2^{m-1}f,\dots ,{\theta }_{2}f,f,{\theta }_2^{n-1}g,\dots ,{\theta }_{2}g,g).$$

(11)

Recall that the indeterminates ${\theta }_1$ and ${\theta }_2$ do not commute with the coefficients but rather act according to the ring automorphisms ${\sigma }_1$ and ${\sigma }_2$ such that for each $a\in \mathcal{F}$,

$${\theta }_{1}a={\sigma }_1\left(a\right){\theta }_1\mathrm{and}{\theta }_{2}a={\sigma }_2\left(a\right){\theta }_2,$$

(12)

which means the noncommutative properties in the determinants’ entries are properly performed as the rows are multiplied on the left by ${\theta }_2$ to some power.

The difference between this definition (Definition 4) and the definition used in [6] is that we consider the case of bivariate skew polynomials with two commuting indeterminates which is particularly suitable for Ore algebra (the framework of this research). This is a new combination from [6] that allows the elimination of indeterminates in the general case (with $n>1$ indeterminates) including an elimination method using an operator evaluation map, which is the aim of this study.

Remark 4.

The determinant described in Definition 4 requires entries to be in a (skew) field; this can be obtained by embedding $\mathcal{F}[{\theta }_1,{\sigma }_1]$ in a (skew) field ([15], Corollary 0.7.2), written as $\mathcal{F}({\theta }_1,{\sigma }_1)$, and its elements can be in the form of $g^{-1}f$ where $f,g\in \mathcal{F}$, in which case the degree is defined as

$$deg\left(g^{-1}f\right)=deg\left(f\right)-deg\left(g\right).$$

(13)

While the Dieudonné determinant is only unique up to a multiple of some commutators, its degree is well defined and is always the same value; this was pointed out by Taelman [16] as the degree is always zero on commutators.

Note that the involvement of commutator factors will be encountered when dealing with the elimination process in the noncommutative case only. Let us illustrate this phenomenon with the following simple system of two polynomial equations of the first degree with respect to the indeterminate $\theta$ as

$$\left\{\begin{array}{ccc}\hfill a_1\theta +a_0& =& 0\hfill \\ \hfill b_1\theta +b_0& =& 0\hfill \end{array}\right.$$

(14)

where $a_0,a_1,b_0,$ and $b_1$ are elements in a (skew) field that they do not commute with $\theta$. Assume $a_1,b_1\ne 0$ (otherwise, the case is straightforward).

Now, multiply the first equation by $-b_1{a}_1^{-1}$ and add it to the second equation to obtain

$$b_0-b_1{a}_1^{-1}{a}_0=0,$$

and multiply by $a_1\ne 0$;

$$a_1(b_0-b_1{a}_1^{-1}{a}_0)=0.$$

(15)

Similarly, multiply the second equation of system (14) by $-a_1{b}_1^{-1}$ and add it to the first equation to obtain

$$a_0-a_1{b}_1^{-1}{b}_0=0,$$

which can be written as

$$b_1(a_1{b}_1^{-1}{b}_0-a_0)=0,b_1\ne 0.$$

(16)

Below, we show that the left sides of the two obtained Equations (15) and (16) are different by a factor of type commutators; i.e., they become the same mod commutators, denoted by $\mathrm{mod}\mathcal{C}$.

$$\begin{array}{cc}\hfill l.s.ofEquation\left(16\right)& =b_1{a}_1{b}_1^{-1}{b}_0-b_1{a}_0\hfill \\ \hfill & =b_1{a}_1{b}_1^{-1}{a}_1^{-1}{a}_1{b}_0-b_1{a}_0\hfill \\ \hfill & ={\mathbf{c}}^{-1}(a_1{b}_0-\mathbf{c}{b}_1{a}_0),where\mathbf{c}=a_1{b}_1{a}_1^{-1}{b}_1^{-1}\hfill \\ \hfill & =a_1{b}_0-\mathbf{c}{b}_1{a}_0\left(\mathrm{mod}\mathcal{C}\right)\hfill \\ \hfill & =a_1{b}_0-a_1{b}_1{a}_1^{-1}{b}_1^{-1}{b}_1{a}_0\left(\mathrm{mod}\mathcal{C}\right)\hfill \\ \hfill & =a_1{b}_0-a_1{b}_1{a}_1^{-1}{a}_0\left(\mathrm{mod}\mathcal{C}\right)\hfill \\ \hfill & =a_1(b_0-b_1{a}_1^{-1}{a}_0)\left(\mathrm{mod}\mathcal{C}\right)\hfill \\ \hfill & =l.s.ofEquation\left(15\right)\left(\mathrm{mod}\mathcal{C}\right).\hfill \end{array}$$

This is also true for the general $n\times n$ case. Note that in the commutative case, the commutator factor $\mathbf{c}=a_1{b}_1{a}_1^{-1}{b}_1^{-1}$ is always 1, and hence, in the commutative case there is no need to involve commutators. Essentially, a similar phenomenon happens for the determinant used in this study (Dieudonné determinant) which is unique up to commutators (as mentioned).

In the following section, we consider computations in almost commutative rings where the Dieudonné determinant becomes well defined (i.e., it becomes unique).

3.3. Uniqueness of the Resultant

As noted, our resultant relies on the Dieudonné determinant, and as we have seen, the Dieudonné determinant can be computed by multiplying its diagonal entries in any order, which is only unique up to an undesirable factor of products of commutators. However, in some rings, this factor does not change its effect on the determinant value.

In the context of graded rings (which will be described shortly), we show that a computation that satisfies a property within the graded ring can be sufficient to prove that the same computation holds that property in the original ring. In the following, we discuss a suitable graded ring to obtain a well-defined determinant (i.e., to assign a unique value to it), and for this, we need the following two definitions.

Definition 5.

A not necessarily commutative ring $\mathcal{S}$ is called filtered if for an indexed family of additive subgroups $S_i$ we have

$$\bigcup _i{\mathcal{S}}_i=\mathcal{S},{\mathcal{S}}_i\subseteq {\mathcal{S}}_{i+1},{\mathcal{S}}_i{\mathcal{S}}_j\subseteq {\mathcal{S}}_{i+j},and1\in {\mathcal{S}}_0,$$

for any $i,j\in \mathbb{Z}$, or its special case $i,j\in {\mathbb{Z}}_{\ge 0}$ when ${\mathcal{S}}_{-1}=0$.

Definition 6.

Let $\mathcal{S}=\bigcup _i{\mathcal{S}}_i$ be a filtered ring. The associated graded ring is denoted by $\mathrm{gr}\left(\mathcal{S}\right)$ and defined as

$$\underset{i}{⨁}{\mathcal{S}}_i/{\mathcal{S}}_{i-1},$$

such that for all $r\in {\mathcal{S}}_i$ and $s\in {\mathcal{S}}_j,$

$$(r+{\mathcal{S}}_{i-1})(s+{\mathcal{S}}_{j-1})=(rs+{\mathcal{S}}_{i+j-1}).$$

For each $r\in {\mathcal{S}}_i$, let us denote the image of r in ${\mathcal{S}}_i/{\mathcal{S}}_{i-1}$ by ${\tilde{\sigma }}_i\left(r\right)$, or simply by $\tilde{\sigma }\left(r\right)$ when $r\in {\mathcal{S}}_i\setminus {\mathcal{S}}_{i-1}$ (i.e., if r is in ${\mathcal{S}}_i$ but not in ${\mathcal{S}}_{i-1}$) also when it is clear from the context. Note that if $\tilde{\sigma }\left(r\right)\tilde{\sigma }\left(s\right)\ne 0$, then

$$\tilde{\sigma }\left(rs\right)=\tilde{\sigma }\left(r\right)\tilde{\sigma }\left(s\right),\forall r,s\in \mathcal{S}.$$

(17)

For details about filtration and graded rings, see, for example, [17] (Chapter 1, §6). In the following two subsections, we discuss the uniqueness of our resultant.

3.3.1. Almost Commutative Rings

Following a similar concept in terms of differential operators, we call a not necessarily commutative ring $\mathcal{S}$ an almost commutative ring if the associated graded ring $\mathrm{gr}\left(\mathcal{S}\right)$ is commutative (see, for example, [18] (§3.3)). Under this assumption, we will have a rather well-defined representation for the resultant of a matrix M with entries in $\mathcal{S}$ by considering computations in $\mathrm{gr}\left(\mathcal{S}\right)$ [10], assuming that $\mathrm{gr}\left(\mathcal{S}\right)$ is a unique factorisation domain and $\mathcal{S}$ can be embedded in a (skew) field.

Essentially, we compute the resultant as before, by transforming its matrix, let us call it M, to a diagonal (or a triangular) form and then multiplying the diagonal elements (in any order) and fixing the obtained value by denoting it as $\widetilde{det}\left(M\right)$. Note that multiplying these elements in any other order will result in a value that only differs by a multiplication of a factor of the type $fg{f}^{-1}{g}^{-1}$ ($f,g\in \mathcal{S}\setminus \left\{0\right\}$), but since $\mathcal{S}$ is assumed to be almost commutative, all those other values will be the same when written as $\tilde{\sigma }\left(\widetilde{det}\left(M\right)\right)$. Hence, in this case, the determinant has a well-defined value, which in turn means that $\tilde{\sigma }\left(\widetilde{det}\left(M\right)\right)$ has equivalent properties to the corresponding one of the usual commutative case. By applying this concept to our resultant, we can observe that all the values of the resultant are the same in almost commutative rings.

Considering that computations in associated graded rings is particularly useful for homogeneous polynomials or with polynomials when their highest-degree components are the only important parts (similar to the use of the principal symbol in the context of differential operators).

3.3.2. Hermite Form

The Hermite form for invertible matrices is a canonical matrix representation whose entries reside within either commutative or noncommutative rings [19]. It satisfies the following properties:

(i)

It is an upper triangular matrix, serving as a normal form of the original matrix;

(ii)

The diagonal entries are monic; that is, the leading coefficient is 1 for each of them;

(iii)

The degrees of the off-diagonal entries are strictly less than the corresponding degree of the diagonal entry in the same column.

This normal form offers two main advantages; it provides a unique representation for the original matrix, and it can be computed efficiently [19]. The uniqueness property of this form is particularly valuable for our purpose, as it ensures a unique representation of a Sylvester matrix upon transformation, thus ensuring a consistent value for our resultant.

Next, we turn our attention towards operator elimination techniques using our proposed resultant.

3.4. Operator Elimination

The focus of this section is to study a process that will allow us to reduce an operator system to a more manageable and tractable alternative to the original system, that, is to exclude selected indeterminates that are perhaps deemed irrelevant, while retaining those that are of interest. Let us illustrate what we mean by looking at the following well-known parametric families of functions called orthogonal polynomials [20], such as Chebyshev and Legendre polynomials.

Example 2.

Consider the Chebyshev polynomial

$$\begin{array}{cc}\hfill T_n\left(t\right)& =\sum _{k=0}^{⌊{\displaystyle \frac{n}{2}}⌋}\left({\displaystyle \genfrac{}{}{0pt}{}{n}{2k}}\right){\left(t^2-1\right)}^k{t}^{n-2k},\hfill \end{array}$$

with variable t and parameters n and k, which satisfy the relations

$$\begin{array}{cc}\hfill & (1-t^2)T_{n+1}^{\prime }\left(t\right)-(n+1)t{T}_{n+1}\left(t\right)-(n+1)T_n\left(t\right)=0,\hfill \\ \hfill & T_{n+2}\left(t\right)-2t{T}_{n+1}\left(t\right)+T_n\left(t\right)=0,\hfill \\ \hfill & (1-t^2)T_n^{\prime \prime }\left(t\right)-t{T}_n^{\prime }\left(t\right)+n^2{T}_n\left(t\right)=0,\hfill \end{array}$$

and they can be translated to the operators language of differential ($D_t$) and difference ($S_n$) in $\mathbb{Q}[n,t][D_t;1,D_t][S_n;S_n,0]$ as follows.

(i)

With a mix of differential and difference operators

$$(1-t^2)D_t{S}_n-(n+1)t{S}_n-(n+1),$$

(18)

(ii)

With only a difference operator

$$S_n^2-2t{S}_n+1,$$

(19)

(iii)

With only a differential operator

$$(1-t^2)D_t^2-t{D}_t+n^2,$$

(20)

where each of the above relations (18), (19), and (20) annihilate $T_n\left(t\right)$, assuming

$$\begin{array}{cc}\hfill & D_t\left(T_n\left(t\right)\right)=T_n^{\prime }\left(t\right),\hfill \\ \hfill & S_n\left(T_n\left(t\right)\right)=T_{n+1}\left(t\right).\hfill \end{array}$$

Let us consider only (18) and (19) as the following operator system:

$$\left\{\begin{array}{ccc}\hfill F& =& (1-t^2)D_t{S}_n-(n+1)t{S}_n-(n+1)\hfill \\ \hfill G& =& S_n^2-2t{S}_n+1.\hfill \end{array}\right.$$

(21)

Now, it will be convenient to have a method to eliminate the indeterminate $S_n$ from F and G in order to obtain the relation (20), that is, to have a relation with a pure operator of $D_t$.

Additionally, if we have a system consisting of the operator relations (18) and (20), then we can think of eliminating $D_t$ in order to have a relation with only $S_n$.

In a similar manner, other orthogonal polynomials can also be expressed in the language of (mixed) operators; for example, the Legendre polynomial

$$\begin{array}{cc}\hfill P_n\left(t\right)& ={\displaystyle \frac{1}{2^n}}\sum _{k=0}^n{\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)}^2{\left(t-1\right)}^{n-k}{(t+1)}^k,\hfill \end{array}$$

satisfies the following different forms of operator relations:

$$\begin{array}{cc}\hfill & (1-t^2)D_t+(n+1)S_n-(n+1)t,\hfill \\ \hfill & (n+2)S_n^2-(2n+3)t{S}_n+(n+1),\hfill \\ \hfill & (t^2-1)D_t^2+2t{D}_t-n(n+1).\hfill \end{array}$$

In other instances, they may appear as multiple parameters with the same operator type, as we will see in Example 3 (for more details on the orthogonal polynomials and other types of special polynomials with their relations, see, for example, [20]).

Therefore, a method that would allow us to simplify an operator system by excluding unwanted indeterminates would be beneficial. The next theorem will look at how the resultant (Definition 4) can help with this, where our resultant can annihilate the same solution that one can obtain from solving the operator system in general.

Before we can state and prove the theorem, we need to establish a property that relates the resultant to the original polynomials. In the commutative case, such a property exists, where the resultant of two polynomials can be expressed as the sum of the products of the original polynomials each multiplied by a suitable polynomial. The conventional method (e.g., [21,22]) for proving this property involves rewriting the original polynomials in terms of matrix representations; this allows the utilisation of determinant computations using Cramer’s rule, where the proof proceeds by expanding the determinant along a selected row (or column) of the matrix. Unfortunately, the Dieudonné determinant can not be expanded by cofactors. For instance, consider a $2\times 2$ matrix $\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)$, over a skew field, where the matrix elements do not commute. In this scenario, an attempt to obtain the determinant by cofactor expansion would be $adet\left(d\right)-bdet\left(c\right)$, that is, $ad-bc$. However, we know that the Dieudonné determinant of the same matrix is $ad-ac{a}^{-1}b$, and the two results are not the same in general. Another option that some authors use is a permutation-based method, where the determinant is given by the alternating sum of products along all the possible permutations. Unfortunately, the same example can also be used to show that the permutation-based method to compute Dieudonné determinant does not make sense because the order of the factors becomes crucial when computing the products, and thus, this method cannot be utilised here either. Instead, we adopt a distinct method, presented in ([23], [Proposition 5, p. 164]). While this different method was also used for the commutative case, it does not rely on cofactor expansions or permutations; rather, it involves applying a specific equation and subsequently using Cramer’s rule to perform a coefficient comparison. This method turns out to be applicable for the noncommutative setting as well, with some modifications, namely, that the computation needs to follow the commutation rule and to be performed with modulo commutators when determining the Dieudonné determinant, in addition to using the result which states that the Dieudonné determinant can be represented by a polynomial (Lemma 1), as shown in the proof of the following proposition.

Proposition 1.

Let $f={\sum }_{i=0}^n{a}_i\left({\theta }_1\right){\theta }_2^i$ and $g={\sum }_{j=0}^m{b}_j\left({\theta }_1\right){{\theta }_2}^j$ be two bivariate skew polynomials in $\mathcal{S}=\mathcal{F}[{\theta }_1;{\sigma }_1][{\theta }_2;{\sigma }_2]$ of positive degrees, where $a_i\left({\theta }_1\right),b_j\left({\theta }_1\right)\in \mathcal{F}[{\theta }_1;{\sigma }_1]\subset \mathcal{F}({\theta }_1;{\sigma }_1)$. Then, there exist two polynomials p and q in $\mathcal{S}$ with polynomial coefficients $\left(\mathrm{mod}\mathcal{C}\right)$ in $\mathcal{F}[{\theta }_1;{\sigma }_1]$ such that

$$pf+qg={\mathrm{res}}_{{\theta }_2}(f,g).$$

(22)

Proof. 

To initiate the proof, first, we aim to identify two polynomials $u={\sum }_{i=0}^{m-1}{u}_i{\theta }_2^i$ and $v={\sum }_{j=0}^{n-1}{v}_j{\theta }_2^j$ satisfying

$$uf+vg=1.$$

(23)

Similar to Equations (10), we can express Equation (23) as

$$\left\{\begin{array}{ccccc}{u}_{m-1}{a}_n^{[m-1]}\hfill & \hfill +& v_{n-1}{b}_m^{[n-1]}\hfill & \hfill =& 0\hfill \\ u_{m-1}{a}_{n-1}^{[m-1]}+u_{m-2}{a}_n^{[m-2]}\hfill & \hfill +& v_{n-1}{b}_{m-1}^{[n-1]}+v_{n-2}{b}_m^{[n-2]}\hfill & \hfill =& 0\hfill \\ u_{m-1}{a}_{n-2}^{[m-1]}+u_{m-2}{a}_{n-1}^{[m-2]}+u_{m-3}{a}_n^{[m-3]}\hfill & \hfill +& v_{n-1}{b}_{m-2}^{[n-1]}+v_{n-2}{b}_{m-1}^{[n-2]}+v_{n-3}{b}_m^{[n-3]}\hfill & \hfill =& 0\hfill \\ ⋮⋮\hfill & \hfill ⋮& ⋮\hfill & \\ u_1{a}_0^{\left[1\right]}+u_0{a}_1^{\left[0\right]}\hfill & \hfill +& v_1{b}_0^{\left[1\right]}+v_0{b}_1^{\left[0\right]}\hfill & \hfill =& 0\hfill \\ u_0{a}_0^{\left[0\right]}\hfill & \hfill +& v_0{b}_0^{\left[0\right]}\hfill & \hfill =& 1\hfill \end{array}\right.$$

and this can be rewritten as follows:

$$\left(\begin{array}{c}{u}_{m-1},\cdots ,u_0,v_{n-1},\cdots ,v_0\end{array}\right)\left(\begin{array}{cccccc}{a}_n^{[\mathrm{m}-1]}\left({\theta }_1\right)& \cdots & a_0^{[\mathrm{m}-1]}\left({\theta }_1\right)& & & \\ & a_n^{[\mathrm{m}-2]}\left({\theta }_1\right)& \cdots & a_0^{[\mathrm{m}-2]}\left({\theta }_1\right)& & \\ & & & \ddots & & & \\ & & & a_n^{\left[0\right]}\left({\theta }_1\right)& \cdots & a_0^{\left[0\right]}\left({\theta }_1\right)\\ b_m^{[\mathrm{n}-1]}\left({\theta }_1\right)& \cdots & b_0^{[\mathrm{n}-1]}\left({\theta }_1\right)& & & & \\ & b_m^{[\mathrm{n}-2]}\left({\theta }_1\right)& \cdots & b_0^{[\mathrm{n}-2]}\left({\theta }_1\right)& & & \\ & & & \ddots & & & \\ & & b_m^{\left[1\right]}\left({\theta }_1\right)& \cdots & b_0^{\left[1\right]}\left({\theta }_1\right)& \\ & & & b_m^{\left[0\right]}\left({\theta }_1\right)& \cdots & b_0^{\left[0\right]}\left({\theta }_1\right)\end{array}\right)=\left(\begin{array}{c}0,\cdots ,0,1\end{array}\right).$$

Note that the Dieudonné determinant of the middle matrix is the resultant ${\mathrm{res}}_{{\theta }_2}(f,g)$ whose entries are independent of ${\theta }_2$.

Assuming ${\mathrm{res}}_{{\theta }_2}(f,g)\ne 0$—otherwise the Formula (22) is immediately satisfied by $p=q=0$—we can use Cramer’s rule (the row version) to obtain all the $u_i$’s and $v_j$’s; for instance, $v_0$ can be written as

$$v_0·{\mathrm{res}}_{{\theta }_2}(f,g)=det\left(\begin{array}{cccccc}{a}_n^{[\mathrm{m}-1]}\left({\theta }_1\right)& \cdots & a_0^{[\mathrm{m}-1]}\left({\theta }_1\right)& & & \\ & a_n^{[\mathrm{m}-2]}\left({\theta }_1\right)& \cdots & a_0^{[\mathrm{m}-2]}\left({\theta }_1\right)& & \\ & & & \ddots & & & \\ & & & a_n^{\left[0\right]}\left({\theta }_1\right)& \cdots & a_0^{\left[0\right]}\left({\theta }_1\right)\\ b_m^{[\mathrm{n}-1]}\left({\theta }_1\right)& \cdots & b_0^{[\mathrm{n}-1]}\left({\theta }_1\right)& & & & \\ & b_m^{[\mathrm{n}-2]}\left({\theta }_1\right)& \cdots & b_0^{[\mathrm{n}-2]}\left({\theta }_1\right)& & & \\ & & & \ddots & & & \\ & & b_m^{\left[1\right]}\left({\theta }_1\right)& \cdots & b_0^{\left[1\right]}\left({\theta }_1\right)& \\ 0& & & \cdots & 0& 1\end{array}\right).$$

(24)

It is worth noting that the Dieudonné determinant value $v_0$ commutes with the other Dieudonné determinant value ${\mathrm{res}}_{{\theta }_2}(f,g)$; that is,

$$v_0·{\mathrm{res}}_{{\theta }_2}(f,g)={\mathrm{res}}_{{\theta }_2}(f,g)·v_0,$$

this follows from the fact that Dieudonné determinants commute with each other (see, for example, ([10], [Definition 7])). By Lemma 1, the determinant on the right side of relation (24) can be expressed as a polynomial $q_0$ in $\mathcal{F}[{\theta }_1;{\sigma }_1]$. Additionally, for all j, we have

$$v_j={\left({\mathrm{res}}_{{\theta }_2}(f,g)\right)}^{-1}·q_j,\mathrm{for}\mathrm{some}\mathrm{polynomial}{q}_j\in \mathcal{F}[{\theta }_1;{\sigma }_1].$$

Similarly,

$$u_i={\left({\mathrm{res}}_{{\theta }_2}(f,g)\right)}^{-1}·p_i,\mathrm{for}\mathrm{some}\mathrm{polynomial}{p}_i\in \mathcal{F}[{\theta }_1;{\sigma }_1].$$

Therefore, $v={\sum }_{j=0}^{n-1}{v}_j{\theta }_2^j$ can be written in the form

$$v={\left({\mathrm{res}}_{{\theta }_2}(f,g)\right)}^{-1}·q,\mathrm{where}q=\sum _{j=0}^{n-1}{q}_j{\theta }_2^j\in \mathcal{F}[{\theta }_1;{\sigma }_1][{\theta }_2;{\sigma }_2].$$

Similarly,

$$u={\left({\mathrm{res}}_{{\theta }_2}(f,g)\right)}^{-1}·p,\mathrm{where}p=\sum _{i=0}^{m-1}{p}_i{\theta }_2^i\in \mathcal{F}[{\theta }_1;{\sigma }_1][{\theta }_2;{\sigma }_2].$$

Substituting these expressions into Equation (23), we obtain

$$pf+qg={\mathrm{res}}_{{\theta }_2}(f,g).$$

□

Before introducing and proving the theorem that we will shortly discuss, it is helpful to review the following definition of the annihilating ideal of a polynomial, which will be mentioned in the proof of the theorem.

Definition 7.

Let $\mathcal{V}$ be an algebra of functions with $\mathbf{u}$ being an element in $\mathcal{V}$. Additionally, let $\mathcal{S}$ be a skew polynomial ring. The annihilating ideal of $\mathbf{u}$ (denoted by $\mathrm{Ann}\mathbf{u}$) consists of all skew polynomials f in $\mathcal{S}$ that annihilate $\mathbf{u}$, that is

$$\mathrm{Ann}\mathbf{u}=\{f\in \mathcal{S}\mid f·\mathbf{u}=0\}.$$

(25)

Now we are ready to prove the following theorem regarding the belonging of the resultant to the annihilating ideal $\mathrm{Ann}\mathbf{u}$, when $\mathbf{u}$ is annihilated by the resultant’s input polynomials.

Theorem 1.

The resultant of a system of two bivariate skew polynomials annihilates the solution of the system.

Proof. 

Let $r={\mathrm{res}}_{{\theta }_2}(f,g)$ be the resultant of bivariate skew polynomials f and g in a skew polynomial ring $\mathcal{S}$. From Proposition 1 we now know that there are polynomials p and q in $\mathcal{S}$ such that

$$pf+qg=r.$$

(26)

Let $\mathbf{u}$ be the solution of the system, that is, $f·\mathbf{u}=0$ and $g·\mathbf{u}=0$. When applying this to Equation (26), it yields

$$\begin{array}{cc}\hfill r·\mathbf{u}& =(pf+qg)·\mathbf{u}\hfill \\ \hfill & =\left(pf\right)·\mathbf{u}+\left(qg\right)·\mathbf{u}\hfill \\ \hfill & =p·\left(f·\mathbf{u}\right)+q·\left(g·\mathbf{u}\right)\hfill \\ \hfill & =p·0+q·0\hfill \\ \hfill & =0.\hfill \end{array}$$

Therefore, $r={\mathrm{res}}_{{\theta }_2}(f,g)$ belongs to $\mathrm{Ann}\mathbf{u}$. □

The following example illustrates the theorem.

Example 3.

Consider the binomial coefficient

$$\mathrm{C}(n,k)=\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)$$

which satisfies the Pascal identity

$$\begin{array}{cc}\hfill \left({\displaystyle \genfrac{}{}{0pt}{}{n+1}{k+1}}\right)-\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k+1}}\right)-\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)& =0,\hfill \end{array}$$

(27)

in addition to

$$\begin{array}{cc}\hfill (k+1)\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k+1}}\right)-(n-k)\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)& =0.\hfill \end{array}$$

(28)

The above relations (27) and (28) can be rewritten in the shift operator notations $S_n$ and $S_k$ to form the following operator system:

$$\left\{\begin{array}{ccc}\hfill F& =& S_n{S}_k-S_k-1\hfill \\ \hfill G& =& (k+1)S_k-(n-k).\hfill \end{array}\right.$$

(29)

Now, to obtain another relation relying on just $S_n$, we can employ our resultant (Definition 4) to eliminate ${\mathcal{S}}_k$ from the system (29), and to achieve that, we can view the system as a bivariate skew polynomial system in $\mathbb{Q}(\alpha ,\beta )[{\theta }_1;{\sigma }_1][{\theta }_2;{\sigma }_2]$ as follows:

$$\left\{\begin{array}{ccc}\hfill f& =& {\theta }_1{\theta }_2-{\theta }_2-1\hfill \\ \hfill g& =& (\beta +1){\theta }_2-(\alpha -\beta ),\hfill \end{array}\right.$$

(30)

where ${\sigma }_1$ and ${\sigma }_2$ are the shift operators $S_n$ and $S_k$, respectively. Also, ${\theta }_1,{\theta }_2,\alpha$ and β are $S_n,S_k,n$ and k, respectively. Accordingly, we can use the resultant method through the Dieudonné determinant to compute ${\mathrm{res}}_{{\theta }_2}(f,g)$ as follows:

$$\begin{array}{cc}\hfill {\mathrm{res}}_{{\theta }_2}(f,g)=& \left|\begin{array}{cc}{\theta }_1-1& -1\\ \beta +1& -(\alpha -\beta )\end{array}\right|\hfill \\ \hfill \stackrel{ro{w}_1\leftrightarrows ro{w}_2}{\to }& \left|\begin{array}{cc}\beta +1& -(\alpha -\beta )\\ {\theta }_1-1& -1\end{array}\right|\hfill \\ \hfill \stackrel{-({\theta }_1-1){(\beta +1)}^{-1}ro{w}_1+ro{w}_2}{\to }& \left|\begin{array}{cc}\beta +1& -(\alpha -\beta )\\ 0& ({\theta }_1-1){(\beta +1)}^{-1}(\alpha -\beta )-1\end{array}\right|\hfill \\ \hfill =& \left|\begin{array}{cc}\beta +1& -(\alpha -\beta )\\ 0& ({\theta }_1{(\beta +1)}^{-1}-{(\beta +1)}^{-1})(\alpha -\beta )-1\end{array}\right|\hfill \\ \hfill =& \left|\begin{array}{cc}\beta +1& -(\alpha -\beta )\\ 0& ({\sigma }_1\left({(\beta +1)}^{-1}\right){\theta }_1-{(\beta +1)}^{-1})(\alpha -\beta )-1\end{array}\right|\hfill \\ \hfill =& \left|\begin{array}{cc}\beta +1& -(\alpha -\beta )\\ 0& ({(\beta +1)}^{-1}{\theta }_1-{(\beta +1)}^{-1})(\alpha -\beta )-1\end{array}\right|\hfill \\ \hfill =& \left|\begin{array}{cc}\beta +1& -(\alpha -\beta )\\ 0& {(\beta +1)}^{-1}({\theta }_1-1)(\alpha -\beta )-1\end{array}\right|\hfill \\ \hfill =& \left[(\beta +1)({(\beta +1)}^{-1}({\theta }_1-1)(\alpha -\beta )-1)\right]\hfill \\ \hfill =& [({\theta }_1-1)(\alpha -\beta )-(\beta +1)]\hfill \\ \hfill =& [{\theta }_1(\alpha -\beta )-(\alpha -\beta )-(\beta +1)]\hfill \\ \hfill =& [{\theta }_1\alpha -{\theta }_1\beta -\alpha -1]\hfill \\ \hfill =& [{\sigma }_1\left(\alpha \right){\theta }_1-{\sigma }_1\left(\beta \right){\theta }_1-\alpha -1]\hfill \\ \hfill =& [(\alpha +1){\theta }_1-\beta {\theta }_1-\alpha -1]\hfill \\ \hfill =& [(\alpha -\beta +1){\theta }_1-(\alpha +1)].\hfill \end{array}$$

(31)

Finally, we can substitute back for the chosen quantities in (31) to obtain

$$(n-k+1)S_n-(n+1),$$

(32)

and this is another desired operator relation, relying only on the operator $S_n$, annihilating $\mathrm{C}(n,k)$, in which its validity can easily be confirmed by applying it to the binomial coefficient $\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)$.

Therefore, Theorem 1 enables us to identify a new relation, which is the resultant, annihilating the same function that is annihilated by the original input polynomials. Our primary focus, thus far, has been on the bivariate case of finding resultants of skew polynomials. However, moving forward to the trivariate case, and ultimately generalising to the multivariate case with n indeterminants, things become more complicated. This is because the coefficient matrix will contain polynomials with two indeterminants (or more for multivariate cases), which means the matrix entries are no longer over a field, and thus, we cannot use the direct technique we used for the previous case. To overcome this difficulty, we introduce an alternative method by utilising a suitable noncommutative evaluation and interpolation technique. This proposed method not only enables elimination for the multivariate case but also improves the processing speed of the algorithms, as detailed in the following section.

4. Efficient Computing Through Evaluation and Interpolation

In this section, we describe another method to compute the resultant of matrices with skew polynomial entries by using evaluation and interpolation techniques. First, we need to identify a suitable evaluation map from the available valid noncommutative versions of evaluation maps that best suit our purpose. Second, we state a theorem that shows how bivariate resultants and evaluation maps are connected; then, we demonstrate the crucial role this theorem plays in the elimination process. Consequently, we will describe our evaluation and interpolation method, generalising the commutative case presented in [7]. However, both of the evaluation and interpolation processes present several challenges, arising from the significant differences in evaluation maps between skew and ordinary polynomials and from the need to maintain the noncommutative product rule during the computations. Recall from the previous methods in the commutative case [7] that the resultant’s input polynomials were evaluated at some scalar values for the evaluation stage, where the computations proceeded consistently and smoothly. However, the direct scalar evaluation for skew polynomials leads to inconsistency here; for example, consider $\theta t$ for $\theta$ be a derivative operator D with respect to t, which, in this case, is equivalent to $t\theta +1$ (the derivative operator D satisfies $D\mathbf{u}=\mathbf{u}D+{\displaystyle \frac{d}{dt}}\mathbf{u}$, for any function $\mathbf{u}$ with respect to t. Thus, we have $Dt=tD+1$, when $\mathbf{u}=t$), and an attempt to evaluate $t\theta +1$ with $\theta$ set to a scalar value say 2 results in $t2+1=2t+1$, while an attempt to evaluate the original $\theta t$ with the same value of $\theta =2$ yields $2t$, and the two obtained results are not the same. This inconsistency illustrates the need for a valid evaluation map from several available formulations of noncommutative evaluation maps in the literature (e.g., the remainder theorem [24], the product formula ([24], [Lemma 8.6.4]), the operator evaluation [25], and the recursive relation formula ([26], [§2]), etc.); the choice of evaluation method is crucial and depends on the specific study at hand, and we will discuss this in more detail in the following section.

4.1. Skew Polynomial Evaluation

When it comes to evaluations in noncommutative rings, one of the main differences compared to the commutative case (where one can simply substitute values for the variables) is that the noncommutative evaluation maps generally do not preserve the products, as observed in the previous example.

In this section, we are searching for a suitable evaluation map that not only preserves the product rule but is also a ring homomorphism.

Here, we are working with skew polynomials in $\mathcal{F}[{\theta }_1;{\sigma }_1][{\theta }_2;{\sigma }_2]$, and a key aspect of this algebra is the presence of operators, such as ${\sigma }_1$ or ${\sigma }_2$. In fact, all the elements of Ore polynomial rings can be viewed as operators, which naturally suggests considering an evaluation map that deals with evaluating at operators. Thus, an interesting option would be evaluating at ${\sigma }_1$ or ${\sigma }_2$, especially if we know that, in our study, these maps are ring homomorphisms, and this property will be a significant desired factor in the evaluation process. Therefore, we adapt the operator evaluation [25] with some adjustments in order to make it compatible with the bivariate case.

Applying the operator evaluation techniques can also improve the efficiency of the polynomial multiplications during the computation of the resultant, as shown in [8,9], but we proceed slightly differently as we are working in $\mathcal{F}[{\theta }_1;{\sigma }_1][{\theta }_2;{\sigma }_2]$; we consider one of the operators, namely ${\sigma }_1$ itself, as an element of the base field $\mathcal{F}$ in a valid manner, that is, ensuring its compatibility with the field $\mathcal{F}$. For convenience, we introduce the notion $\tilde{\mathcal{F}}$ to denote the field of rational maps of operators $\mathcal{F}({\sigma }_1,\circ$)  ([10], [Remark 14]); this approach of considering σ₁ in $\tilde{\mathcal{F}}$ offers a more efficient and convenient way to process our elimination technique, which is the main focus of this study.

Next, we discuss the definition of operator evaluation for bivariate skew polynomials (which will be a ring homomorphism) as in [10].

Definition 8.

Let $\tilde{\mathcal{F}}[{\theta }_1;{\sigma }_1][{\theta }_2;{\sigma }_2]$ be a bivariate skew polynomial ring. Since we have commuting indeterminates ${\theta }_1$ and ${\theta }_2$, we can consider $\mathcal{S}=E[{\theta }_1;{\sigma }_1]$, where $E=\tilde{\mathcal{F}}[{\theta }_2;{\sigma }_2]$, that is, polynomials are regarded with respect to ${\theta }_1$. Then, for each polynomial $f={\sum }_{i=0}^n{\alpha }_i{\theta }_1^i$, ${\alpha }_i\in E$, we define the evaluation map ${\mathrm{eval}}_{({\theta }_1-{\sigma }_1)}\left(f\right)$ as

$${\mathrm{eval}}_{({\theta }_1-{\sigma }_1)}:\begin{array}{ccc}& E[{\theta }_1;{\sigma }_1]\hfill & \to E\hfill \\ f=& {\displaystyle \sum _{i=0}^n{\alpha }_i{\theta }_1^i}\hfill & {\displaystyle \mapsto f({\theta }_2,{\sigma }_1)=\sum _{i=0}^n{\alpha }_i{\sigma }_1^i.}\hfill \end{array}$$

The following Lemma ([10], Lemma 16) shows that the map ${eval}_{({\theta }_1-{\sigma }_1)}$ is a ring homomorphism for bivariate Ore polynomials.

Lemma 2.

The map ${eval}_{({\theta }_1-{\sigma }_1)}$ is a ring homomorphism.

In the following, we define the evaluation map when the polynomials are regarded as modulo commutators [10].

Definition 9.

Let $\tilde{\mathcal{F}}(\theta ;\sigma )$ be a (skew) field, and let ${\tilde{\mathcal{F}}}^{\times }(\theta ;\sigma )$ denote multiplicative group of $\tilde{\mathcal{F}}(\theta ;\sigma )$ containing non-zero elements of $\tilde{\mathcal{F}}(\theta ;\sigma )$. Let $f=g^{-1}f$ be an element in

$${\tilde{\mathcal{F}}}^{\times }(\theta ;\sigma )/[{\tilde{\mathcal{F}}}^{\times }(\theta ;\sigma ),{\tilde{\mathcal{F}}}^{\times }(\theta ;\sigma )].$$

The modular evaluation map ${\mathrm{eval}}_{\left(\theta -\sigma \right)}\left(f\right)$ is defined as

$${\mathrm{eval}}_{\left(\theta -\sigma \right)}:\begin{array}{ccc}\hfill {\tilde{\mathcal{F}}}^{\times }(\theta ;\sigma )/[{\tilde{\mathcal{F}}}^{\times }(\theta ;\sigma ),{\tilde{\mathcal{F}}}^{\times }(\theta ;\sigma )]& \hfill \to & {\tilde{\mathcal{F}}}^{\times }/[{\tilde{\mathcal{F}}}^{\times },{\tilde{\mathcal{F}}}^{\times }]\hfill \\ \hfill f=g^{-1}f\mathrm{mod}\mathcal{C}& \hfill \mapsto & \hfill f\left(\sigma \right)={\left(g\left(\sigma \right)\right)}^{-1}f\left(\sigma \right)\mathrm{mod}{\mathcal{C}}^{\prime },g\left(\sigma \right)\ne 0.\end{array}$$

In particular, if $f={\sum }_{i=0}^n{a}_i{\theta }^i$ is an Ore polynomial in ${\tilde{\mathcal{F}}}^{\times }(\theta ;\sigma )/[{\tilde{\mathcal{F}}}^{\times }(\theta ;\sigma ),{\tilde{\mathcal{F}}}^{\times }(\theta ;\sigma )]$ then

$${\mathrm{eval}}_{\left(\theta -\sigma \right)}:f={\sum }_{i=0}^n{a}_i{\theta }^i\mathrm{mod}\mathcal{C}\mapsto f\left(\sigma \right)={\sum }_{i=0}^n{a}_i{\sigma }^i\mathrm{mod}{\mathcal{C}}^{\prime }.$$

Remark 5.

Note that in this study, we assume the evaluation map $\mathrm{eval}$ becomes modular (by default) as in Definition 9, when the input argument computed modulo commutators.

We can now describe the behaviour of resultant under specialisations from applying $\mathrm{eval}$ to polynomials with indeterminate coefficients [10].

Theorem 2.

Let $\mathcal{S}=\tilde{\mathcal{F}}[{\theta }_1;{\sigma }_1][{\theta }_2;{\sigma }_2]$. For all polynomials $f,g\in \mathcal{S}$, if ${deg}_{{\theta }_2}\left(f\right)={deg}_{{\theta }_2}\left({\mathrm{eval}}_{\left({\theta }_1-{\sigma }_1\right)}\left(f\right)\right)$ and ${deg}_{{\theta }_2}\left(g\right)={deg}_{{\theta }_2}\left({\mathrm{eval}}_{\left({\theta }_1-{\sigma }_1\right)}\left(g\right)\right)$ then the following formula holds:

$${eval}_{({\theta }_1-{\sigma }_1)}\left({\mathrm{res}}_{{\theta }_2}(f,g)\right)={\mathrm{res}}_{{\theta }_2}({\mathrm{eval}}_{\left({\theta }_1-{\sigma }_1\right)}\left(f\right),{\mathrm{eval}}_{\left({\theta }_1-{\sigma }_1\right)}\left(g\right)).$$

(33)

By Theorem 2, we can conclude that the two methods ${\mathrm{eval}}_{\left({\theta }_1-{\sigma }_1\right)}\left({\mathrm{res}}_{{\theta }_2}(f,g)\right)$ and ${\mathrm{res}}_{{\theta }_2}({\mathrm{eval}}_{\left({\theta }_1-{\sigma }_1\right)}\left(f\right),{\mathrm{eval}}_{\left({\theta }_1-{\sigma }_1\right)}\left(g\right))$ are the same (viewed as operators). Thus, for all a in $\mathcal{F}$, we have

$${eval}_{({\theta }_1-{\sigma }_1)}\left({\mathrm{res}}_{{\theta }_2}(f,g)\right)\left(a\right)={\mathrm{res}}_{{\theta }_2}({\mathrm{eval}}_{\left({\theta }_1-{\sigma }_1\right)}\left(f\right),{\mathrm{eval}}_{\left({\theta }_1-{\sigma }_1\right)}\left(g\right))\left(a\right).$$

(34)

The left side of Equation (34) describes the operator evaluation of direct resultant of two bivariate skew polynomials f and g at a value a in $\mathcal{F}$, while the right side provides a way to obtain the resultant through operator evaluation of its entries, which follows by applying evaluation at a. This ultimately means reducing the computation of the resultant to the base ring, which then can efficiently and more easily be computed.

Remark 6.

An advantage of using the Dieudonné determinant in Theorem 2 is that the case can be reduced to a triangular determinant with diagonal entries of polynomials $d_i^{\prime }\left({\theta }_1\right)$ ($i=1,\dots ,k;k=n+m$) for the direct method of the left side of Equation (34), while the right side will be in the form $d_i\left({\sigma }_1\right)$ ($i=1,\dots ,k;k=n+m$), which can be computed by the following product:

$$\begin{array}{cc}\hfill {\mathrm{res}}_{{\theta }_2}({\mathrm{eval}}_{\left({\theta }_1-{\sigma }_1\right)}\left(f\right),{\mathrm{eval}}_{\left({\theta }_1-{\sigma }_1\right)}\left(g\right))\left(a\right)& =\left(\prod _{i=1}^k{d}_i\left({\sigma }_1\right)\right)\left(a\right)\hfill \\ \hfill & =(d_1\left({\sigma }_1\right)d_2\left({\sigma }_1\right)\cdots d_k\left({\sigma }_1\right))\left(a\right)\hfill \\ \hfill & =d_1^{*}\left(d_2^{*}(\cdots d_k^{*}\left(a\right))\right),\hfill \end{array}$$

(35)

where $d_i^{*}=d_i\left({\sigma }_1\right)$ for all $i=1,\dots ,k$.

Our method of evaluation and interpolation offers the benefit of enabling elimination for multivariate skew polynomials, which would have been difficult to process otherwise. Additionally, our prior observations show that evaluation and interpolation techniques offer a significant asymptotic advantage over the direct method in the commutative case [7]. We have also observed substantial speed improvements in computing skew polynomial products using the evaluation and interpolation method, as applied over finite fields [8,9]. Consequently, we can expect an asymptotic improvement in the computational speed of computing the product in (35) using evaluation and interpolation techniques. Thus, the resultant can be computed more efficiently, and it obtains the same result as directly computing the resultant. In the bivariate case, for instance, it achieves the same result as directly computing the resultant of two bivariate skew polynomials, $f({\theta }_1,{\theta }_2)$ and $g({\theta }_1,{\theta }_2)$, with respect to ${\theta }_2$.

While achieving more efficient computation is highly desirable, it often comes with challenges that require investigation and resolutions. The following sections will detail the main steps used in our study and the challenges encountered during the development.

4.2. Efficiency Steps and Challenges Encountered

The efficiency of this method is achieved by breaking down the computation into three main stages, as proven by Theorem 2;

(i)

Evaluation: Choose distinct values $a_i$ ($i=1,\dots ,k$), and then compute the evaluation of f and g at $a_i$ with respect to ${\theta }_1$. These become univariate polynomials in ${\theta }_2$.

(ii)

Partial resultants: Obtain the partial resultants of these evaluated polynomials f and g (step i) with respect to ${\theta }_2$.

(iii)

Interpolation: Combine these partial resultants using a suitable interpolation technique to recover the complete resultant of the original f and g.

However, applying these steps to skew polynomials presents several challenges compared to the commutative case. These challenges include the following.

(i)

Evaluation values: Since there are several evaluation maps to choose from, evaluating a polynomial using a specific evaluation map (in this case operator evaluation at ${\sigma }_1$ and then applying it to a value a) may not be the actual evaluation value that is expected by the chosen interpolation method (such as a Lagrange or Newton interpolation technique). A suitable interpolation method should be used to match the chosen evaluation map.

(ii)

Validity of the evaluation map: The evaluation map needs to be a ring homomorphism to preserve the product.

(iii)

Distinct conjugacy classes: All chosen evaluation values must belong to pairwise distinct conjugacy classes for the evaluation and interpolation techniques to function correctly. We can achieve this by choosing primitive elements in which they inherently belong to different conjugacy classes.

(iv)

Unlucky evaluations: To avoid unlucky evaluations, where a chosen value eliminates the leading coefficient and alters the original polynomial’s degree, we need to identify and exclude such unconstructive values. This can be determined by examining the leading term status at the time of evaluation; if it is unlucky, then skip to the next value, and continue only if the evaluation is valid/lucky.

(v)

Insufficient evaluation values: In some cases, we may not have enough valid values for the evaluation stage. To address this, we can extend the domain by including additional valid values. Then, these new values can be utilised by the evaluation map as long as they belong to distinct conjugacy classes (as in Section 4.2).

The following sections address these challenges in more detail and illustrate potential solutions with examples.

4.3. Skew Polynomial Interpolation

This part describes the interpolation stage on a normal basis. The first subsection is definitions and notations; then, we provide some technical details on how to compute the resultant of bivariate skew polynomials through evaluation and interpolation techniques, including how to overcome the challenges encountered, followed by an example to illustrate the idea.

4.3.1. Galois Theory (Finite and Infinite Field Extensions)

For clarity and convenience, we recall some definitions and notations used in the remainder of this study regarding Galois field extensions for both finite and infinite field extensions.

Recall that a field $\mathcal{F}$ is a field extension of a field $\mathcal{K}$ if $\mathcal{K}\subset \mathcal{F}$, denoted by $\mathcal{F}/\mathcal{K}$. In this study, $\mathcal{F}$ is always a field extension of $\mathcal{K}$ unless otherwise specified. In Section 4.3.3, we study a particular case when $\mathcal{K}=\mathbb{Q}$, the field of rational numbers, and $\mathcal{F}=\mathbb{C}$, the field of complex numbers, or $\mathcal{F}$ may be a subfield of $\mathbb{C}$.

Let $X\subset \mathcal{F}$; we type $\mathcal{K}\left(X\right)$ for the smallest subfield generated by X in $\mathcal{F}$ (that is, the smallest subfield of $\mathcal{F}$ that contains both $\mathcal{K}$ and X). A field extension $\mathcal{F}/\mathcal{K}$ is called finitely generated if there is a finite set $X\subset \mathcal{F}$ such that $\mathcal{F}=\mathcal{K}\left(X\right)$; furthermore, it is called simple if there exists a single element $\alpha \in \mathcal{F}$ such that $\mathcal{F}=\mathcal{K}\left(\alpha \right)$; it is common to write $\mathcal{K}\left(\alpha \right)$ instead of $\mathcal{K}\left(\right\{\alpha \left\}\right)$.

An element $\alpha \in \mathcal{F}$ is called an algebraic over $\mathcal{K}$ if there exists a non-zero polynomial $m_{\alpha }$ over $\mathcal{K}$ such that $m_{\alpha }\left(\alpha \right)=0$. The minimal polynomial of an algebraic element $\alpha \in \mathcal{F}$ over $\mathcal{K}$ is a monic irreducible polynomial $m_{\alpha }$ over $\mathcal{K}$ such that $m_{\alpha }\left(\alpha \right)=0$; furthermore, if $\alpha$ is a root of any other polynomial $m_{\alpha }^{\prime }$ over $\mathcal{K}$, then $m_{\alpha }$ divides $m_{\alpha }^{\prime }$ (that is $m_{\alpha }$ is of minimal degree).

Viewing $\mathcal{F}$ as a vector space over $\mathcal{K}$, the dimension of $\mathcal{F}$ over $\mathcal{K}$ is the degree of the extension $\mathcal{F}/\mathcal{K}$ and is denoted by $[F:K]$. We say $\mathcal{F}$ is finite extension or finite dimensional if $[F:K]<\infty$, and in this case, we denote the dimension by ${dim}_{\mathcal{K}}\left(\mathcal{F}\right)=[\mathcal{F}:\mathcal{K}]$.

Consider the finite extension $\mathcal{K}\left(\alpha \right)/\mathcal{K}$ for an algebraic element $\alpha$ over $\mathcal{K}$ defined as

$$\mathcal{F}=\mathcal{K}\left(\alpha \right)=\left\{\sum _{i=0}^{r-1}{a}_i{\alpha }^i:a_i\in \mathcal{K}\right\},$$

(36)

where $r=deg\left(m_{\alpha }\right)$ for some minimal polynomial $m_{\alpha }$ over $\mathcal{K}$. This is the set of all the finite linear combinations of basis elements $\{1,\alpha ,{\alpha }^2,\dots ,{\alpha }^{r-1}\}$ over $\mathcal{K}$. Let $\sigma$ be an automorphism of $\mathcal{F}$ that fixes $\mathcal{K}$ (called $\mathcal{K}$-automorphism), which satisfies $\sigma \left({\sum }_{i=0}^{r-1}{a}_i{\alpha }^i\right)={\sum }_{i=0}^{r-1}{a}_i\sigma {\left(\alpha \right)}^i$. Note that $\sigma$ is determined by the image $\sigma \left(\alpha \right)$, where $\sigma \left(\alpha \right)$ represents a root of $m_{\alpha }$ which yields a one-to-one correspondence between the $\mathcal{K}$-automorphisms of $\mathcal{K}\left(\alpha \right)$ and the roots of $m_{\alpha }$ (since these automorphisms send a root to another root of the same minimal polynomial $m_{\alpha }$). Moreover, this also yields an isomorphism between $\mathcal{K}\left(\alpha \right)$ and $\mathcal{K}\left(\sigma \right(\alpha \left)\right)$.

We call a monic irreducible polynomial over $\mathcal{K}$ separable if it has no double roots in any field extension of $\mathcal{K}$ (i.e., all its roots are distinct). An extension $\mathcal{F}/\mathcal{K}$ is separable if for every element $\alpha \in \mathcal{F}$, its minimal polynomial $m_{\alpha }$ over $\mathcal{K}$ is separable. A well-known theorem (primitive element theorem) states that any separable finite field extension is simple.

An extension $\mathcal{F}/\mathcal{K}$ is called normal if every irreducible polynomial over $\mathcal{K}$ that has at least one root in $\mathcal{F}$ has all its roots in $\mathcal{F}$ (i.e., the polynomial splits completely in $\mathcal{F}$).

A finite extension $\mathcal{F}/\mathcal{K}$ is called Galois extension if it is both separable and normal. Additionally, the Galois group of a Galois extension is defined as the group (under composition) of all the automorphisms $\sigma$ of $\mathcal{F}$ that fix $\mathcal{K}$, and this group is denoted by $\mathrm{Gal}(\mathcal{F}/\mathcal{K})$.

The Fundamental Theorem of Galois Theory establishes a fundamental relation between the structure of a Galois field extension and its Galois group. It states that there is a one-to-one correspondence between the intermediate subfields of $\mathcal{F}$ containing $\mathcal{K}$ and the subgroups of $\mathrm{Gal}(\mathcal{F}/\mathcal{K})$.

Extending Galois theory to the case of infinite field extensions, where the Galois group $\mathrm{Gal}(\mathcal{F}/\mathcal{K})$ can be infinite, the fundamental theorem requires a more careful examination. While the concepts of separability and normality remain relevant for infinite extensions, the one-to-one correspondence between subgroups and subfields, as established in the finite case, no longer holds [27]. To address this issue, we can define a topology, known as the Krull topology [27], on the Galois group $\mathrm{Gal}(\mathcal{F}/\mathcal{K})$. While the precise definition of this topology and the corresponding closed subgroups is not essential for our current study, it is important to recognise that this topological structure enables us to restrict our consideration to the closed subgroups of $\mathrm{Gal}(\mathcal{F}/\mathcal{K})$. This restriction approach effectively resolves the issue at hand, where the fundamental theorem can be restated as there beubg a one-to-one correspondence between intermediate subfields and closed subgroups of the Galois group $\mathrm{Gal}(\mathcal{F}/\mathcal{K})$. Readers interested in more details on Krull topology can refer, for example, to [27].

A number field is a field extension of $\mathbb{Q}$ that is finite dimensional when viewed as a vector space over $\mathbb{Q}$. An algebraic number that has its minimal polynomial with integer coefficients is called an algebraic integer. An interesting fact is that any number field is generated by a single algebraic integer (for example see Theorem 2.2 and Corollary 2.12 in [28]).

Next, we briefly describe a normal basis [29], which is a particular basis for finite Galois extensions when viewed as a vector space over the base field. It has also been described for the infinite case [30], as we will discuss in the following subsection.

4.3.2. Normal Basis (Finite and Infinite Cases)

Let $\mathcal{F}/\mathcal{K}$ be a finite Galois extension. The Galois $\mathcal{K}$-conjugates of an element $\alpha \in \mathcal{F}$ is the set of all elements $\sigma \left(\alpha \right)\in \mathcal{F}$ where $\sigma \in \mathrm{Gal}(\mathcal{F}/\mathcal{K})$; this set represents the action of the Galois group on the element $\alpha$, which is the reason it is sometimes denoted by $\mathrm{Gal}(\mathcal{F}/\mathcal{K})·\alpha$ or simply by $\mathrm{G}·\alpha$, where $G=\mathrm{Gal}(\mathcal{F}/\mathcal{K})$.

An element $\alpha \in \mathcal{F}$ is called normal if the Galois conjugates set $\mathrm{G}·\alpha =\left\{\sigma \right(\alpha )\mid \sigma \in \mathrm{Gal}(\mathcal{F}/\mathcal{K}\left)\right\}$ forms a basis for $\mathcal{F}$ when viewed as a vector space over $\mathcal{K}$, which is characterised by the group action that forms a single orbit, that is, its elements lie on the same $\mathrm{Gal}(\mathcal{F}/\mathcal{K})$-orbit (see Figure 1). Such a basis is called normal [29], as defined below.

Definition 10.

Let $\mathcal{F}/\mathcal{K}$ be a finite Galois extension of degree n with the Galois group $\mathrm{Gal}(\mathcal{F}/\mathcal{K})=\{{\sigma }_0,{\sigma }_1,\dots ,{\sigma }_{n-1}\}$. A basis that consists of all the $\mathcal{K}$-conjugate elements

$$G·\alpha =\{{\sigma }_0\left(\alpha \right),{\sigma }_1\left(\alpha \right),\dots ,{\sigma }_{n-1}\left(\alpha \right)\}$$

is called normal basis and denoted by $\mathcal{N}\left(\alpha \right)$.

One of the simplest examples of constructing normal basis for finite Galois extensions is when we have the field extension $\mathbb{Q}\left(i\right)$ over $\mathbb{Q}$ with its Galois group $\mathrm{Gal}(\mathbb{Q}\left(i\right)/\mathbb{Q})=\{{\sigma }_0,{\sigma }_1\}$ defined as

$${\sigma }_0\left(i\right)=i\mathrm{and}{\sigma }_1\left(i\right)=-i.$$

A normal basis can be defined by the Galois group action on the element $\alpha =1+i\in \mathbb{Q}\left(i\right)$ as

$${\sigma }_0\left(\alpha \right)=1+i\mathrm{and}{\sigma }_1\left(\alpha \right)=1-i.$$

Thus, the normal basis in this case is $\mathcal{N}\left(\alpha \right)=\{1+i,1-i\}$.

Note that although the field extension is in the form $\mathbb{Q}\left(i\right)/\mathbb{Q}$, the element $\alpha =i$ does not consturnct a normal basis since the set of its conjugates $\{{\sigma }_0\left(i\right),{\sigma }_1\left(i\right)\}=\{i,-i\}$ is not linearly independent.

In the case of an infinite Galois extension $\mathcal{F}/\mathcal{K}$, the original definition of a normal basis (as in Definition 10) does not make sense anymore. This is because the set of K-conjugates of an element in $\mathcal{F}$ remains finite in which it can not be a $\mathcal{K}$-basis when $\mathcal{F}/\mathcal{K}$ is infinite. To address this limitation, Lenstra [30] described a reformulation of the normal basis definition that allows the concept to be applicable in the infinite case as well; the idea is based on the compression between $\mathcal{F}$ and $C(G,\mathcal{K})$ and the set of all continuous maps from the Galois group G to the field $\mathcal{K}$, assuming that G is equipped with the Krull topology and $\mathcal{K}$ has the discrete topology. This reformulated definition of the normal basis reduces to the original one when the Galois extension $\mathcal{F}/\mathcal{K}$ is finite.

Other more sophisticated examples of a normal basis can be constructed by adjoining roots of unity to a number field, as we will see in the following section.

4.3.3. Cyclotomic Extension

Cyclotomic fields are essential for various applications involving roots of unity, such as representation theory, Kummer theory, and the discrete Fourier transform. In the area of cryptography, certain elliptic curves defined over cyclotomic fields are utilised in modern cryptography.

In this section, we provide a quick overview of the cyclotomic field extension, which will be needed in the next subsection.

It is easy to check that the polynomial ${\theta }^n-1$ is a separable polynomial over $\mathcal{K}$ (since ${\theta }^n-1$ is relatively prime to its derivative, which is the non-zero polynomial $n{\theta }^{n-1}$), where ${\theta }^n-1$ has n distinct roots in its splitting field over $\mathcal{K}$. In $\mathbb{C}$, the set of these roots is in the form

$${\mu }_n=\{e^{2\pi ik/n}\mid k=0,\dots ,n-1\}=\left(\alpha \right),\mathrm{where}\alpha =e^{2\pi i/n},$$

which is a multiplicative cyclic group of order n generated by $\alpha$. In general, this $\alpha$ is not the only generator for ${\mu }_n$ . Any element of the cyclic group ${\mu }_n$ that generates ${\mu }_n$ is called primitive n-th roots of unity. The term cyclotomic refers to circle-cutting, where the n-th roots of unity divide a circle into n equal parts on the complex plane (see Figure 2 when $n=7$). For any integer k, primitive n-th roots of unity can be identified through $gcd(k,n)$, since we know that the order of ${\alpha }^k$ in ${\mu }_n$ is $n/gcd(n,k)$, which means any ${\alpha }^k$ is a primitive n-th root of unity iff $gcd(k,n)=1$.

As ${\mu }_n$ is a cyclic group, the mapping $\alpha \mapsto {\alpha }^k$ sends a generator to another generator iff $gcd(k,n)=1$, and as a consequence, this mapping is an automorphism iff $gcd(k,n)=1$.

Note that the primitive elements in ${\mu }_n$ are powers of each other; therefore, the extension $\mathcal{K}\left(\alpha \right)$ is irrelevant to the choice of $\alpha$ in ${\mu }_n$. In the case when $\mathcal{K}=\mathbb{Q}$ is the field of rational numbers, then the field extension $\mathcal{K}\left(\alpha \right)$ is called cyclotomic field of n-th roots of unity for a positive integer n. In particular, if $n=p$ is a prime, then a basis can be constructed, which acts as a normal basis (compare Figure 1 and Figure 2) by simply taking the basis that starts with ${\alpha }_0=e^{2\pi i/n}$.

An advantage of utilising cyclotomic extensions is that it works for any arbitrary base field by simply adjoining the n-th roots of unity for a fixed integer $n\ne 0$ in $\mathcal{K}$ (i.e., if $\mathcal{K}$ is not of characteristic 0, then n should not be divisible by the characteristic of the field $\mathcal{K}$). For the modular algorithms, we can choose a large prime number p for the value n in the examples. This is to make sure we can generate enough values to be available for the interpolation stage, which is the topic of the next subsection.

4.3.4. Interpolation

In this subsection, we apply our theorem to obtain an evaluation and interpolation method for computing the resultant of bivariate skew polynomials over number fields, in particular over $\mathbb{Q}\left(\alpha \right)$, where $\alpha$ is a complex root of unity, followed by examples to illustrate the idea.

Recall that in the theorem, we use operator evaluation to evaluate the polynomials, which are then applied to selected evaluation values. However, the properties of this evaluation are different from the other evaluation maps for noncommutative polynomials. For instance when using operator evaluation ${\mathrm{eval}}_{(\theta -\sigma )\left(a\right)}$ for evaluating $f={\theta }^2$ in a skew polynomial ring $\mathcal{F}[\theta ;\sigma ]$ for a value $a\in \mathcal{F}$, we first obtain ${\sigma }^2$ and then apply it to the value a to find ${\sigma }^2\left(a\right)$; this image is not an actual evaluation of the value a in the typical noncommutative evaluation manner, which should be $\sigma \left(a\right)a$; nor is it an evaluation of the form ${\left(\sigma \left(a\right)\right)}^2$ because ${\left(\sigma \left(a\right)\right)}^2=\sigma \left(a^2\right)$, which is different from ${\sigma }^2\left(a\right)$, and it is certainly not a naive substitution in the form $a^2$. So the main question from an interpolation point of view would be at which specific value the indeterminate of the original polynomial is evaluated. For this, we need a suitable interpolation method in order to be able to properly recover the original polynomial, which is the topic of the following subsection.

4.4. Evaluation and Interpolation Technique

In this section, we describe a modular method that can compute the resultant through an evaluation and interpolation technique by applying our resultant formula in the Theorem 2.

The method uses coefficient compression, that is, by equating the coefficients (of both sides of the formula) at enough evaluation values, and then solving its corresponding linear system. A similar method is also used in [8,9] for the multiplication of univariate skew polynomials.

Let $\mathcal{F}/\mathcal{K}$ be a finite Galois extension of degree r. We consider the computation of the resultant of two bivariate skew polynomials f and g in $\mathcal{F}[{\theta }_1;{\sigma }_1][{\theta }_2;{\sigma }_2]$. The particular case we have in mind is that when $\mathcal{K}=\mathbb{Q}$ and $\mathcal{F}=\mathbb{Q}\left(\alpha \right)$ for some fixed choice of a complex root of unity $\alpha$.

Let $\mathcal{N}$ be the normal basis of $\mathcal{F}/\mathcal{K}$ given as

$$\mathcal{N}=\{{\alpha }_0,{\alpha }_1,\dots ,{\alpha }_{r-1}\}$$

such that ${\alpha }_i={\sigma }_1^i\left({\alpha }_0\right)$ for $i=0,\dots ,r-1$.

As with any modular setup, the method requires a bound s for the number of needed evaluation values for the interpolation stage. For this purpose, we can use the total sum of the degrees of the factors plus one, which is the degree of the product plus one, as in the commutative case (since in Ore algebra, $deg\left(fg\right)=deg\left(f\right)+deg\left(g\right)$ for any two Ore polynomials f and g), we may encounter a case where we do not have enough distinct evaluation values (i.e., enough elements in the base field belonging to different conjugacy classes). In this case, we can extend the base field to include additional elements as needed. However, for our purposes, we can typically select a sufficiently large value that ensures there are enough elements for the evaluation map.

Recall that our resultant formula for two bivariate skew polynomials f and g in $\mathcal{F}[{\theta }_1;{\sigma }_1][{\theta }_2;{\sigma }_2]$ of degrees n and m, respectively, is in the form

$${\mathrm{eval}}_{\left({\theta }_1-{\sigma }_1\right)}\left({\mathrm{res}}_{{\theta }_2}(f,g)\right)={\mathrm{res}}_{{\theta }_2}({\mathrm{eval}}_{\left({\theta }_1-{\sigma }_1\right)}\left(f\right),{\mathrm{eval}}_{\left({\theta }_1-{\sigma }_1\right)}\left(g\right)).$$

(37)

Let us assume that the original resultant R is in the generic form with coefficients $c_i$ as

$$R=\sum _{i=0}^{s-1}{c}_i{\theta }_1^i,$$

(38)

and then our aim is to find these unknown coefficients $c_i$ of R.

We fix the normal element ${\alpha }_0$ and evaluate the right side of (37) at the values ${\alpha }_0^j$$(j=0,1,\dots ,s-1)$ as in

$$\begin{array}{cc}\hfill {\mathrm{res}}_{{\theta }_2}({\mathrm{eval}}_{\left({\theta }_1-{\sigma }_1\right)}\left(f\right),{\mathrm{eval}}_{\left({\theta }_1-{\sigma }_1\right)}\left(g\right))\left({\alpha }_0^j\right)& =\left(\prod _{i=1}^k{d}_i\left({\sigma }_1\right)\right)\left({\alpha }_0^j\right)\hfill \\ \hfill & =(d_1\left({\sigma }_1\right)d_2\left({\sigma }_1\right)\cdots d_k\left({\sigma }_1\right))\left({\alpha }_0^j\right)\hfill \\ \hfill & =d_1^{*}\left(d_2^{*}(\cdots d_k^{*}\left({\alpha }_0^j\right))\right).\hfill \end{array}$$

(39)

Note that computing (39) provides a single value for each evaluation point ${\alpha }_0^j$; let us denote this value by $R^{*}\left({\alpha }_0^j\right)$.

On the other hand, if we evaluate the generic resultant R at the same values ${\alpha }_0^j$$(j=0,1,\dots ,s-1)$ in the operator evaluation manner as

$$\begin{array}{cc}\hfill {\mathrm{eval}}_{\left({\theta }_1-{\sigma }_1\right)\left({\alpha }_0^j\right)}\left(R\right)=R^{*}\left({\alpha }_0^j\right)& =\sum _{i=0}^{s-1}{c}_i{\sigma }_1^i\left({\alpha }_0^j\right)\hfill \\ \hfill & =\sum _{i=0}^{s-1}{c}_i{\alpha }_i^j,\mathrm{since}{\alpha }_i={\sigma }_1^i\left({\alpha }_0\right).\hfill \end{array}$$

(40)

Equalities (39) and (40) allow us to solve the following system for unknowns $c_i$ as

$$\left(\begin{array}{cccc}1& 1& \cdots & 1\\ {\alpha }_0& {\alpha }_1& \cdots & {\alpha }_{s-1}\\ ⋮& ⋮& \ddots & ⋮\\ {\alpha }_0^{s-1}& {\alpha }_1^{s-1}& \cdots & {\alpha }_{s-1}^{s-1}\end{array}\right)\left(\begin{array}{c}{c}_0\\ c_1\\ ⋮\\ c_{s-1}\end{array}\right)=\left(\begin{array}{c}{R}^{*}\left({\alpha }_0^0\right)\\ R^{*}\left({\alpha }_0^1\right)\\ ⋮\\ R^{*}\left({\alpha }_0^{s-1}\right)\end{array}\right)$$

(41)

Thus, we have found the Formula (38) that we were looking for.

4.5. Examples

In the following example, we compute the resultant of two bivariate skew polynomials over a number field $\mathbb{Q}\left(\alpha \right)$ using both methods; the direct as well as the evaluation and interpolation methods as described in the previous sections.

Example 4.

Let $\mathbb{Q}\left(\alpha \right)[{\theta }_1;{\sigma }_1][{\theta }_2;{\sigma }_2]$ be a bivariate skew polynomial ring where $\alpha =e^{2\pi i/p}$ and $p=101$, endowed with two $\mathbb{Q}$-automorphisms ${\sigma }_1,{\sigma }_2$ of $\mathbb{Q}\left(\alpha \right)$ such that

$${\sigma }_1\left(\alpha \right)={\alpha }^2,{\sigma }_2\left(\alpha \right)={\alpha }^3.$$

Consider the problem of computing the resultant of the following two bivariate skew polynomials over $\mathbb{Q}\left(\alpha \right)$ w.r.t. ${\theta }_2$ :

$$\left\{\begin{array}{cc}\hfill f& =\alpha {\theta }_1{\theta }_2^2+\alpha {\theta }_1-1\hfill \\ \hfill g& ={\alpha }^2{\theta }_1^2{\theta }_2-\alpha \hfill \end{array}\right.$$

(42)

Let the matrix ${\mathrm{M}=\mathrm{Sylv}}_{{\theta }_2}(f,g)$ be the Sylvester matrix of f and g in its general form as follows:

$$\begin{array}{cccc}det\left(M\right)=det\left({\mathrm{Sylv}}_{{\theta }_2}(f,g)\right)& =\hfill & \begin{array}{c}\hfill f\\ \hfill {\theta }_{2}g\\ \hfill g\end{array}& \left|\begin{array}{ccc}{a}_2^{\left[0\right]}& a_1^{\left[0\right]}& a_0^{\left[0\right]}\\ b_1^{\left[1\right]}& b_0^{\left[1\right]}& \\ & b_1^{\left[0\right]}& b_0^{\left[0\right]}\end{array}\right|\hfill \\ & =\hfill & & \left|\begin{array}{ccc}{a}_2& a_1& a_0\\ {\sigma }_2\left(b_1\right)& {\sigma }_2\left(b_0\right)& \\ & b_1& b_0\end{array}\right|,\end{array}$$

applying it to our example, it becomes

$$=\left|\begin{array}{ccc}\alpha {\theta }_1& 0& \alpha {\theta }_1-1\\ {\alpha }^6{\theta }_1^2& -{\alpha }^3& \\ & {\alpha }^2{\theta }_1^2& -\alpha \end{array}\right|.$$

Now, we can use row operations to transform the above matrix to an upper triangular form (following Lemma 1 and Remark 2):

$$det\left(M\right)=\left|\begin{array}{ccc}\alpha {\theta }_1& 0& \alpha {\theta }_1-1\\ 0& -{\alpha }^3& -{\alpha }^6{\theta }_1^2+{\alpha }^4{\theta }_1\\ 0& 0& -{\alpha }^{14}{\theta }_1^4+{\alpha }^6{\theta }_1^3-\alpha \end{array}\right|.$$

Thus, the direct resultant can be computed by multiplying the diagonal elements $d_i$

$$\begin{array}{ccc}\hfill det\left(M\right)={\prod }_{i=1}^3{d}_i& =& \alpha {\theta }_1(-{\alpha }^3)(-{\alpha }^{14}{\theta }_1^4+{\alpha }^6{\theta }_1^3-\alpha )\hfill \\ & =& \alpha {\theta }_1({\alpha }^{17}{\theta }_1^4-{\alpha }^9{\theta }_1^3+{\alpha }^4)\hfill \end{array}$$

(43)

$$\begin{array}{ccc}& =& {\alpha }^{35}{\theta }_1^5-{\alpha }^{19}{\theta }_1^4+{\alpha }^9{\theta }_1.\hfill \end{array}$$

(44)

Next, we use another method to compute (43) through an evaluation and interpolation method (by applying Theorem 2) as follows:

1.

From the right side of the resultant formula (37) we compute the composition product (39)

$$d_1^{*}\left(d_2^{*}\left(d_3^{*}\left(w\right)\right)\right)$$

(45)

for some p-th roots of unity w (in this example, w can be $\alpha$ to any integer power greater than 0 and less than the prime p). Let us first compute $d_3^{*}\left(w\right)$ as

$$\begin{array}{cc}\hfill d_3^{*}\left(w\right)& =(-{\alpha }^{14}{\sigma }_1^4+{\alpha }^6{\sigma }_1^3-\alpha )\left(w\right)\hfill \\ \hfill & =-{\alpha }^{14}{\sigma }_1^4\left(w\right)+{\alpha }^6{\sigma }_1^3\left(w\right)-\alpha w\hfill \\ \hfill & =-{\alpha }^{14}{w}^{16}+{\alpha }^6{w}^8-\alpha w,\hfill \end{array}$$

Then, we apply it to (45):

$$\begin{array}{cc}\hfill d_1^{*}\left(d_2^{*}\left(d_3^{*}\left(w\right)\right)\right)& =\alpha {\sigma }_1(-{\alpha }^3(-{\alpha }^{14}{w}^{16}+{\alpha }^6{w}^8-\alpha w))\hfill \\ \hfill & =\alpha {\sigma }_1({\alpha }^{17}{w}^{16}-{\alpha }^9{w}^8+{\alpha }^{4}w)\hfill \\ \hfill & =\alpha {\sigma }_1\left({\alpha }^{17}{w}^{16}\right)-\alpha {\sigma }_1\left({\alpha }^9{w}^8\right)+\alpha {\sigma }_1\left({\alpha }^{4}w\right)\hfill \\ \hfill & ={\alpha }^{35}{w}^{32}-{\alpha }^{19}{w}^{16}+{\alpha }^9{w}^2.\hfill \end{array}$$

We call this result the evaluated resultant polynomial (denoted by $R\left(w\right)$), which in this case is

$$R\left(w\right)={\alpha }^{35}{w}^{32}-{\alpha }^{19}{w}^{16}+{\alpha }^9{w}^2.$$

(46)

2.

We select evaluation values from the following normal basis that starts with the normal element $\alpha$:

$$\mathcal{N}=\{{\sigma }_1^i\left(\alpha \right)\mid i=0,\dots ,p-1\}.$$

3.

To perform our actual evaluations, we need a bound on the number of evaluations required to recover the original resultant, which is the sum of the degrees of $d_i$ plus one (that is 6). Therefore, we compute (46) at the first six values in the normal basis $\mathcal{N}$ as

$$w_i={\sigma }_1^i\left(\alpha \right),i=0,\dots ,5$$

which are the values $w_0=\alpha$, $w_1={\alpha }^2$, $w_2={\alpha }^4$, $w_3={\alpha }^8$, $w_4={\alpha }^{16}$ and $w_5={\alpha }^{32}$ (since ${\sigma }_1\left(\alpha \right)={\alpha }^2$). Note that these values satisfy $w_{i+1}={\sigma }_1\left(w_i\right)$ for $i=0,\dots ,p-1$.

4.

Let V be a vector whose entries are given by the actual evaluation of the evaluated resultant polynomial (46) at the corresponding values $w_i$, as mentioned in the previous step. For example, the first evaluation

$$\begin{array}{cc}\hfill R\left(w_0\right)& =R\left(\alpha \right)={\alpha }^{67}-{\alpha }^{35}+{\alpha }^{11},\hfill \end{array}$$

stored in the vector’s first entry, and so on for the other evaluations $R\left(w_i\right)$ for $i=0,\dots ,5$.

5.

For the left side of the resultant Formula (37), let us assume that the original resultant R is in the generic form as in (38)

$$R=c_5{\theta }^5+c_4{\theta }^4+c_3{\theta }^3+c_2{\theta }^2+c_1\theta +c_0$$

(47)

and our aim is to find those coefficients $c_i,i=0,\dots ,5$. By applying our theorem, each evaluation $R^{*}\left(w_i\right)$ is the same as the corresponding values that we have obtained in the previous step (i.e., the entries in V). For example, the evaluation $R^{*}\left(w_i\right)$ at the first value $w_0=\alpha$ is

$$\begin{array}{cc}\hfill R^{*}\left(\alpha \right)& =c_5{\sigma }_1^5\left(\alpha \right)+c_4{\sigma }_1^4\left(\alpha \right)+c_3{\sigma }_1^3\left(\alpha \right)+c_2{\sigma }_1^2\left(\alpha \right)+c_1{\sigma }_1\left(\alpha \right)+c_0\alpha \hfill \end{array}$$

which is equal to the first entry in the vector V, and so on for the other evaluations. This will allow us to solve a linear system (e.g., by using a software such as Maple 2024) in the form

$$Mx=V,$$

(48)

where x is a vector of the unknowns $c_i$ and M is a matrix of the form:

$$\left(\begin{array}{ccccccc}\alpha & {\alpha }^2& {\alpha }^4& {\alpha }^8& {\alpha }^{16}& {\alpha }^{32}& \\ {\alpha }^2& {\alpha }^4& {\alpha }^8& {\alpha }^{16}& {\alpha }^{32}& {\alpha }^{64}& \\ {\alpha }^4& {\alpha }^8& {\alpha }^{16}& {\alpha }^{32}& {\alpha }^{64}& {\alpha }^{27}& \\ {\alpha }^8& {\alpha }^{16}& {\alpha }^{32}& {\alpha }^{64}& {\alpha }^{27}& {\alpha }^{54}& \\ {\alpha }^{16}& {\alpha }^{32}& {\alpha }^{64}& {\alpha }^{27}& {\alpha }^{54}& {\alpha }^7& \\ {\alpha }^{32}& {\alpha }^{64}& {\alpha }^{27}& {\alpha }^{54}& {\alpha }^7& {\alpha }^{14}& \end{array}\right).$$

From solving the linear system (48), we obtain all the coefficients $c_i$ of the original resultant (47) as follows:

$$\left(\begin{array}{c}0\\ {\alpha }^9\\ 0\\ 0\\ -{\alpha }^{19}\\ {\alpha }^{35}\end{array}\right),$$

which is the same as the polynomial obtained by the direct method (44).

Note that as variables are eliminated, we have reduced the computations to computing only with the elements (numbers) in the base field $\mathbb{Q}\left(\alpha \right)$, which is the key idea behind the method of evaluation and interpolation to improve the efficiency of the method.

Now, let us describe an example for the infinite-dimensional case. For this purpose, we can consider

$$\mathcal{F}=\bigcup _{n\ge 1}\mathbb{Q}\left({\alpha }_n\right),$$

where ${\alpha }_n$ is a primitive $p^n$ for a fixed (odd) prime p, wihch is the union of all p-th power cyclotomic extensions of $\mathbb{Q}$ where each of $\mathbb{Q}\left({\alpha }_n\right)$ is of finite extension, meaning its Galois extension $G=\mathrm{Gal}(\mathcal{F}/\mathcal{K})$, where $\mathcal{K}=\mathbb{Q}$, is a composite of finite Galois extensions. An element in G can be determined by indicating how it acts on each $\mathbb{Q}\left({\alpha }_n\right)$. In finite Galois theory, we know an automorphism ${\sigma }_n$ in G is acting by

$${\sigma }_n\left({\alpha }_n\right)={\alpha }_n^{a_n},$$

(49)

for some integer $a_n\mathrm{mod}{p}^n$ where $(a_n,p)=1$ ([27], [Example 3.7]), with the property ${\alpha }_{n+1}^p={\alpha }_n$ and

$${\sigma }_n{|}_{\mathbb{Q}\left({\alpha }_{n-1}\right)}={\sigma }_{n-1},$$

which enables an extension of ${\sigma }_n$ to an automorphism, say ${\sigma }^{*}$, of $\mathcal{F}$ in G. Let us specify, for instance, $a_n=2$ such that

$${\sigma }^{*}\left({\alpha }_n\right)={\alpha }_n^2.$$

Let $m_n$ be the order of ${\sigma }_n$, that is,

$${\sigma }_n^{m_n}\left({\alpha }_n\right)=1,$$

then, combined with the definition of ${\sigma }_n$ (Formula (49)) and with $a_n=2$, we can conclude

$${\sigma }_n^{m_n}\left({\alpha }_n\right)={\alpha }_n^d,\mathrm{where}d=2^{m_n},$$

and $d=1\mathrm{mod}{p}^n,\mathrm{since}{m}_n\mathrm{is}\mathrm{the}\mathrm{order}\mathrm{of}{\sigma }_n.$

Consequently, as n approaches infinity, the order $m_n$ also approaches infinity, meaning our automorphism ${\sigma }^{*}$ is of infinite order. Next, we consider our example with two infinite order automorphisms ${\sigma }_1^{*}$ and ${\sigma }_2^{*}$.

Example 5.

Consider the problem of eliminating an indeterminant, namely ${\theta }_1$, from the algebra $\mathcal{F}[{\theta }_1;{\sigma }_1^{*}][{\theta }_2;{\sigma }_2^{*}]$.

In the literature, Hachenberger’s work [31], in the field of number theory provides an explicit formulation for constructing normal elements (including those that are completely normal, meaning the element is simultaneously normal over every intermediate field extension [31]) within cyclotomic fields of prime power order over the rational field.

Consequently, we can now follow similar steps as in Example 4 to derive the elimination process for Example 5. Note that for the evaluation and interpolation stage, it is convenient to fix a (large) n and work in a sub-algebra over ${\mathcal{F}}^{\prime }$, where ${\mathcal{F}}^{\prime }$ is a finite extension of $\mathcal{K}$; then, the rest will follow in the same manner as in the previous example.

5. Conclusions and Future Work

In this study, we have successfully derived the concept of the resultant for bivariate skew polynomials and applied it to eliminate indeterminates in skew polynomial systems. Our methodology covers two primary techniques; the first utilises a Sylvester-style matrix constructed from the coefficients of the polynomials, allowing for direct computation of the resultant. The second technique introduces a modular approach that utilises evaluation and interpolation methods to derive partial resultants, which are then combined to yield the original resultant.

The study’s focus on the bivariate case is essential due to its role in a recursive evaluation and interpolation technique, in which this technique enables the reduction of a general $n\times n$ system to an $(n-1)\times (n-1)$ system by evaluating one indeterminate. This recursive process can be repeated until a bivariate system is reached. Subsequently, the study’s specialised bivariate techniques can be applied to solve the original system.

The contributions of this research extend beyond theoretical exploration. We have demonstrated the practical applicability of the derived resultant in combinatorial contexts, proving (or deriving) combinatorial identities, simplifying skew polynomial systems, and determining the existence of solutions by assessing the vanishing of the resultant. Our work not only contributes to the existing literature but also opens new avenues for future research in both algebraic and computational fields.

In future work, we aim to explore applications related to cryptographic schemes, including the Diffie–Hellman protocol and secret sharing among any number of participants. Prior research has already examined the use of skew polynomials, and our upcoming research intends to build on this by leveraging the resultant introduced in this paper and by properties of the Dieudonné determinant. Moreover, additional optimisation techniques can be employed, particularly by leveraging the properties of roots of unity during the evaluation stage. This approach presents opportunities for parallel computation and incorporates established techniques for handling this type of data, resulting in more efficient resource utilisation.

The techniques developed in this study provide a promising framework for tackling multivariate skew polynomial systems, thus opening avenues for further innovations in related applications.