<figure><img src="image_1.png" /></figure>

HAL
open science

# Selfdual skew cyclic codes

Xavier Caruso, Fabrice Drain

► To cite this version:

Xavier Caruso, Fabrice Drain. Selfdual skew cyclic codes. 2023. [hal-04127001](https://hal.science/hal-04127001)

HAL Id: hal-04127001

https://hal.science/hal-04127001

Preprint submitted on 13 Jun 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
<figure><img src="image_1.png" /></figure>

HAL
open science

Selfdual skew cyclic codes

Xavier Caruso, Fabrice Drain

► To cite this version:

Xavier Caruso, Fabrice Drain. Selfdual skew cyclic codes. 2024. hal-04127001v3

HAL Id: hal-04127001

https://hal.science/hal-04127001v3

Preprint submitted on 7 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Selfdual skew cyclic codes

Xavier Caruso & Fabrice Drain

June 13, 2023
# Selfdual skew cyclic codes

Xavier Caruso & Fabrice Drain

April 7, 2025

## Abstract

Given a finite extension $K/F$ of degree $r$ of a finite field $F$, we enumerate all selfdual skew cyclic codes in the Ore quotient ring $E_k := K[X; \text{Frob}]/(X^{rk} - 1)$ for any positive integer $k$ coprime to the characteristic $p$ (separable case). We also provide an enumeration algorithm when $k$ is a power of $p$ (purely inseparable case), at the cost of some redundancies. Our approach is based on an explicit bijection between skew cyclic codes, on the one hand, and certain families of $F$-linear subspaces of some extensions of $K$. Finally, we report on an implementation in SageMath.

## Contents

<table><tr><td>1</td><td>Introduction</td><td>2</td></tr><tr><td>2</td><td>From skew cyclic codes to finite geometry</td><td>5</td></tr><tr><td>2.1</td><td>Definition of skew cyclic codes</td><td>5</td></tr><tr><td>2.2</td><td>The evaluation isomorphism $\mathcal{E}_l$</td><td>5</td></tr><tr><td>2.3</td><td>Adjunctions on $E_k$ and related spaces</td><td>6</td></tr><tr><td>2.4</td><td>Vector space duality</td><td>10</td></tr><tr><td>3</td><td>Counting and generating selfdual skew cyclic codes</td><td>11</td></tr><tr><td>3.1</td><td>Existence criterion</td><td>12</td></tr><tr><td>3.2</td><td>Counting selfdual skew cyclic codes</td><td>13</td></tr><tr><td>3.3</td><td>Random generation of selfdual skew cyclic codes</td><td>16</td></tr><tr><td>3.4</td><td>Enumeration of selfdual skew cyclic codes</td><td>23</td></tr><tr><td>3.5</td><td>An implementation in SageMath</td><td>26</td></tr><tr><td>4</td><td>Enumeration of purely inseparable selfdual skew cyclic codes</td><td>27</td></tr><tr><td>4.1</td><td>Enumeration of purely inseparable selfdual skew cyclic codes</td><td>29</td></tr><tr><td>4.2</td><td>SageMath enumeration of inseparable selfdual skew cyclic codes</td><td>32</td></tr></table>
Abstract

Given a finite extension $K/F$ of degree $r$ of a finite field $F$ in characteristic $p$, we enumerate all selfdual skew cyclic codes in the Ore quotient ring $E_k := K[X^{\pm 1}; \theta]/(X^{kr} - 1)$ for any positive integer $k$ coprime to the characteristic $p$. We use a new approach based on vector space duality, which establishes an order reversing and orthogonality preserving bijection between skew codes and vector subspaces. Finally we implement this enumeration in SageMath.
# 1 Introduction

Among linear codes, cyclic codes enjoy a rich algebraic structure as they are defined as ideals of quotient polynomial rings. This structure endows them with good properties (encoding, decoding, duality, dimension, distance, length). In the paper of Boucher, Geiselmann and Ulmer from 2006 [BGU06], cyclic codes are generalized by considering left ideals in Ore polynomial rings rather than in polynomial rings, obtaining thus a much larger class of linear codes called skew cyclic codes. In the present article, following their work, we study the selfdual property of these codes.

Let $K/F$ be an extension of finite fields of degree $r$. Let $\theta: K \to K$ be the Frobenius $x \mapsto x^q$ where $q$ denotes the cardinality of $F$. We consider the Ore polynomial ring $K[X; \theta]$, defined as the set of classical polynomials equipped with the standard addition and the twisted multiplication derived from the law $X\kappa = \theta(\kappa)X$ where $\kappa$ is any element of $K$. Skew cyclic codes are by definition left ideals of a quotient of the form $E_k := K[X; \theta]/(X^{rk} - 1)$. We notice that cyclic codes correspond to the special case of skew cyclic codes when $r=1$.

The ambient space $E_k$ is equipped with a bilinear form coming from the coordinatewise bilinear form on the vector space $K^{rk}$, namely

$$ \left( \sum_{i=0}^{kr-1} a_i X^i, \sum_{i=0}^{kr-1} b_i X^i \right) \mapsto \sum_{0 \le i < rk} a_i b_i. $$

It thus makes sense to consider duality of skew cyclic codes. The topic was studied by Boucher among others [BU14, Bou15, Bou16, BBB20]. Notably, an existence criterion is given in [Bou15], while an enumeration of selfdual skew cyclic codes for $r=2$ and a prime field $F$ appears in [Bou16]. In the subsequent article [BBB20], the enumeration is extended to any nonnegative integer $r$, for $k=1$ and a prime field $F$. In their conclusion, the authors suggest to further count and enumerate all selfdual skew cyclic codes for any values of the order $r$ and of the degree $k$ and for any finite base field $F$. In the present paper, we give a complete answer to this question when the characteristic $p$ of $F$ is odd and $k$ is coprime to it (separable case). We also study the case when $k$ is a $p$-th power (purely inseparable case) and obtain partial result in this case, our enumeration algorithm suffering from some redundancy.

As we will show in Subsection 2.1, $r$ has to be even for selfdual skew cyclic codes to exist. We thus set $r=2s$. We first consider the separable case, i.e. we assume that $k$ is coprime with $p$. For the purpose of stating our main results, we write $F[Y]/(Y^k-1)$ as a product of field extensions of $F$, namely $F[Y]/(Y^k-1) = \prod_{1 \le l \le n} F_l$ where each $F_l$ corresponds to an irreducible factor of $Y^k-1$. We let $y_l$ denote the image of $Y$ in $F_l$ and we set $K_l := K \otimes_F F_l$. We also consider the function $\tau$ acting on the indices $l$ induced by the transformation $Y \mapsto \frac{1}{\tau}$ on the irreducible factors of $Y^k-1$.

Let $I$ be the subset of indexes $l \in \{1, \dots, n\}$ which are fixed by $\tau$ and let $I_{\text{eucl}}$ (resp. $I_{\text{herm}}$) be the subset of $I$ consisting of indexes $l$ such that $y_l = \pm 1$ (resp. $y_l \ne \pm 1$). Let also $J$ be the set consisting of all the pairs $\{l, \tau(l)\}$ when $l$ runs over the remaining indexes in $\{1, \dots, n\} \setminus I$. Finally, for each $l$, we denote by $\mathcal{V}(K_l/F_l)$ the set of $F_l$-vector subspaces of $K_l$. When $l \in I_{\text{eucl}}$ (resp. $l \in I_{\text{herm}}$), we shall further equip $K_l$ with a $F_l$-bilinear Euclidean (resp. Hermitian) form; we let $S_{\text{eucl}}(K_l/F_l)$ (resp. $S_{\text{herm}}(K_l/F_l)$) denote the set of isotropic subspaces of $K_l$ of dimension $s := r/2$. Our main theorem is as follows.
# Contents

<table><tr><td>1</td><td>Introduction</td><td>2</td></tr><tr><td>2</td><td>Insight for future work on the inseparable case</td><td>3</td></tr><tr><td>3</td><td>General definitions and notations</td><td>4</td></tr><tr><td>3.1</td><td>Definitions in finite geometry</td><td>4</td></tr><tr><td>3.2</td><td>Notations</td><td>5</td></tr><tr><td>4</td><td>Skew cyclic codes</td><td>6</td></tr><tr><td>5</td><td>On the semisimple algebra E<sub>k</sub></td><td>7</td></tr><tr><td>5.1</td><td>Semi-simplicity of the algebra E<sub>k</sub></td><td>7</td></tr><tr><td>5.2</td><td>The evaluation isomorphism J<sub>l</sub></td><td>8</td></tr><tr><td>5.3</td><td>Adjunction on E<sub>k</sub></td><td>10</td></tr><tr><td>6</td><td>Vector space duality</td><td>16</td></tr><tr><td>7</td><td>Enumeration of selfdual skew cyclic codes</td><td>18</td></tr><tr><td>7.1</td><td>Counting selfdual skew cyclic codes</td><td>18</td></tr><tr><td>7.2</td><td>Enumerating selfdual skew cyclic codes</td><td>26</td></tr><tr><td>8</td><td>SageMath enumeration of selfdual skew codes</td><td>34</td></tr><tr><td>8.1</td><td>SageMath computation of cyclic or negacyclic codes</td><td>35</td></tr><tr><td>8.2</td><td>SageMath iteration time for the enumeration of selfdual skew codes</td><td>36</td></tr><tr><td>A</td><td>Enumeration of inseparable selfdual skew cyclic codes</td><td>42</td></tr><tr><td>A.1</td><td>Counting selfdual skew separable twisted codes</td><td>42</td></tr><tr><td>A.2</td><td>Enumeration of inseparable selfdual skew cyclic codes</td><td>43</td></tr><tr><td>A.3</td><td>SageMath enumeration of inseparable selfdual skew cyclic codes</td><td>46</td></tr></table>
**Theorem 1.1** There exists an explicit bijection between the set of selfdual skew cyclic codes in $\mathbf{E}_k$ and the cartesian product of sets $W_{\text{pal}} \times W_{\text{nonpal}}$, where:

$$ W_{\text{pal}} = \prod_{l \in I_{\text{eucl}}} S_{\text{eucl}}(\mathbf{K}_l/\mathbf{F}_l) \times \prod_{l \in I_{\text{herm}}} S_{\text{herm}}(\mathbf{K}_l/\mathbf{F}_l) \\ W_{\text{nonpal}} = \prod_{\{l, \tau(l)\} \in J} \mathcal{V}(\mathbf{K}_l/\mathbf{F}_l) $$

As a byproduct, we get the following counting of selfdual skew cyclic codes of $\mathbf{E}_k$.

**Theorem 1.2** We assume that the characteristic of $\mathbf{F}$ is odd. Then there exist selfdual skew cyclic codes in $\mathbf{E}_k$ if and only if $k$ is odd, $s$ is odd and $q \equiv 3 \pmod 4$. Moreover, when selfdual codes exist, their number is given by

$$ \prod_{l \in I_{\text{eucl}}} \prod_{i=0}^{s-1} (q_l^i + 1) \times \prod_{l \in I_{\text{herm}}} \prod_{i=0}^{s-1} (q_l^{i+1/2} + 1) \times \prod_{\{l, \tau(l)\} \in J} \sum_{k=0}^{r} \frac{(q_l^r - 1) \dots (q_l^{r-k+1} - 1)}{(q_l^k - 1) \dots (q_l - 1)} $$

where $q_l$ denotes the cardinal of $\mathbf{F}_l$.

The existence criterion stated in the previous theorem was already known [Bou15]. Our approach, however, is new and allows for deriving other informations, including the above counting formula and explicit methods for generating self-dual codes that we discuss now. First of all, we describe algorithms, with polynomial complexity in $k$ and $r$, for generating randomly such a code, with uniform distribution. We then move to the question of complete enumeration. Since selfdual skew cyclic codes are quite numerous (their number grows exponentially with respect to $r$), it sounds not that interesting to design an algorithm that outputs the complete list of such codes in one shot. Instead, we describe a routine that outputs a new code each time it is called with the guarantee that all codes will show up-and show up only once-at the end of the day. The cost of each individual call to our algorithm is again polynomial in $k$ and $r$.

Our method looks robust in the sense that we are confident that it could be adapted to other situations, e.g. even characteristic or negacyclic (or more generally, constacyclic) codes instead of cyclic codes. However, addressing the inseparable case where $k$ is not coprime to $p$ using analogue methods seems more delicate (although probably doable). In the present paper, we outline a different method for enumerating all purely inseparable selfdual skew cyclic codes, for which $k$ is a power of the characteristic $p$, by multiplying properly generators of some twisted separable selfdual skew cyclic codes as described and illustrated by hand of SageMath computations in Section 4. This enumeration method could be used in combination with the enumeration method of the separable case to solve the general inseparable enumeration problem. However, it is not optimal as it comes with redundancies.

**Organization of the paper.** In Section 2, we define selfdual skew cyclic codes. Then, under the separability hypothesis that $k$ is coprime to $p$, we relate the skew algebra $\mathbf{E}_k$ to a product of matrix algebras, and we transport the bilinear structure of $\mathbf{E}_k$ onto matrices. In Section 3, we use this reinterpretation to count selfdual skew cyclic codes and to generate them efficiently. In Section 3.5, we
# 1 Introduction

Among linear codes, cyclic codes enjoy a rich algebraic structure as they are defined as ideals of quotient polynomial ring. It endows them with good properties (encoding, decoding, duality, dimension, distance, length). Coding theorists are searching for generalizations that preserve these good properties. In this paper, following the paper of D. Boucher, W. Geiselmann and F. Ulmer from 2006 [BGU06], we generalize cyclic codes by considering left ideals in Ore polynomial rings rather than in polynomial rings. We thus obtain a much larger class of linear codes called skew cyclic codes. In our study, we will focus on the selfdual property of these codes.

For a finite extension $K/F$ of finite field of degree $r$, we define the Ore Laurent polynomial ring $K[X^{\pm 1}; \theta]$ as the quotient of the free $K$-algebra $K\langle X\rangle$ by the noncommutative relation: $\forall k \in K$, $X.k = \theta(k).X$, where $\theta$ is the Frobenius automorphism of $K/F$. The center of this algebra being $F[X^{\pm r}]$, in particular, the ideal generated by the polynomial $X^{rk} - 1$ is two-sided. So we can define skew cyclic $(X^{rk} - 1, K/F)$-codes in Hamming metric as ideals of the quotient: $E_k := K[X^{\pm 1}; \theta]/(X^{rk} - 1)$. We notice that cyclic codes correspond to the special case of skew cyclic codes where $r=1$.

The duality of skew cyclic codes has been studied by D. Boucher among others. In her paper [Bou16], an enumeration of selfdual cyclic skew codes for $r=2$ and $q$ prime is given. In her subsequent article [BBB20], an enumeration of selfdual cyclic skew codes for $k=1, r=n$ and $q$ prime is provided. In both articles the duality considered is induced by the coordinatewise bilinear form on the vector space $K^{rk} : ((x_i)_{0 \le i < rk}, (y_i)_{0 \le i < rk}) \mapsto \sum_{0 \le i < rk} x_i y_i$. In their conclusions, the papers suggest to further enumerate all selfdual skew cyclic codes for any values of the order $r$, the degree $k$ and the finite base field $F$. In our paper, we give a complete answer to this question in the separable case, where $k$ is coprime to the characteristic of $F$.

For the purpose of stating our main results, we note $\prod_{1 \le l \le n} F_l$ the decomposition of $F[Y]/(Y^k - 1)$ as a product of field extensions of $F$ in an algebraic closure. We note $y_l$, a primitive element of $F_l$ such that: $F(y_l) = F_l$. We note $K_l := K \otimes_F F_l$. We also note $\tau$, the involution on the index $l$ induced by the aforementioned duality on $K^{rk}$. We get the following main result.

**Theorem 2** (Cf. theorem 43) There exists an explicit bijection between the set of selfdual skew cyclic codes of $E_k$ and the cartesian product of sets $W_{\text{palindromic}} \times W_{\text{nonpalindromic}}$, where:

$W_{\text{palindromic}}$ is the cartesian product over all indexes $l$ invariant by $\tau$ of the sets of maximal isotropic $F_l$-vector subspaces of $K_l$.
report on an implementation of our algorithms and provide some numerical experiments. The source code of the SageMath implementation is available at this location:

https://plmlab.math.cnrs.fr/caruso/selfdual-skew-cyclic-codes

In Section 4, we sketch an enumeration algorithm for purely inseparable selfdual skew cyclic codes, in the case where k is a power of p. Finally we provide computation results for the enumeration of purely inseparable skew cyclic codes.

**Conventions and notations.** Throughout this paper, we will use the following notation:

* $End_R(V)$ denotes, for any ring $R$ and $R$-module $V$, the endomorphism ring of $R$-linear endomorphisms of $V$.

* $Mat_{R,r \times r}$ denotes, for any ring $R$, the matrix ring of $r \times r$ square matrices with entries in $R$.

* $M^r$ denotes the transpose of the matrix $M$.

* id denotes the identity morphism.

* $GL_n(F)$ denotes the general linear group of the vector space $F^n$ over the finite field $F$.

* $L^\sigma$ denotes the subfield of $L$ fixed by the automorphism $\sigma$.

* $V^\perp$ denotes the orthogonal of the subvector space $V$ in some ambient space.

If $F$ is a finite field, equipped with an involutive automorphism $\sigma$ (i.e. an automorphism of order 2), we recall that a $\sigma$-sesquilinear form $\mathcal{B}$ of a $F$-vector space $V$ is an additive map $\mathcal{B}: V \times V \to F$ such that

$$ \mathcal{B}(\lambda u, \mu v) = \lambda \cdot \sigma(\mu) \cdot \mathcal{B}(u, v) \quad \forall u, v \in V, \quad \forall \lambda, \mu \in F $$

In this paper, we will consider four different types of sesquilinear forms:

* (Euclidean case) $\sigma = \text{id}$ and $\mathcal{B}$ is symmetric, i.e. $\mathcal{B}(u, v) = \mathcal{B}(v, u)$ for all $u, v \in V$,

* (skew-Euclidean case) $\sigma = \text{id}$ and $\mathcal{B}$ is antisymmetric, i.e. $\mathcal{B}(u, v) = -\mathcal{B}(v, u)$ for all $u, v \in V$,

* (Hermitian case) $\sigma \neq \text{id}$ and $\mathcal{B}$ is symmetric,

* (skew-Hermitian case) $\sigma \neq \text{id}$ and $\mathcal{B}$ is antisymmetric.

We recall that, when $\mathcal{B}$ is nondegenerate, the ring $End_F(V)$ of $F$-linear endomorphisms of $V$ is equipped with an involutive anti-automorphism $f \mapsto f^*$ characterized by

$$ \forall u, v \in V, \quad \mathcal{B}(u, f^*(v)) = \mathcal{B}(f(u), v) $$

It is called the *adjunction* relative to $\mathcal{B}$. We recall that $(f + g)^* = f^* + g^*$ and $(f \circ g)^* = g^* \circ f^*$ for $f, g \in \text{End}_F(V)$. Moreover, the adjoint of the scalar multiplication by an element $a \in F$ is the multiplication by $\sigma(a)$. The adjoint construction allows finally to endow $\text{End}_F(V)$ itself with a sesquilinear pairing, defined by $\langle f, g \rangle = \text{Trace}(f \circ g^*)$.

**Acknowledgments.** We warmly thank Delphine Boucher and the anonymous referee for pointing out several inconstancies in a former version of this article.

This research was supported by the grant ANR-21-CE39-0009-BARRACUDA.
$W_{\text{nonpalindromic}}$ is the cartesian product over all remaining unordered pairs of indexes $(l, \tau(l))$ (verifying $l \neq \tau(l)$) of the sets of $\mathbf{F}_l$-vector subspaces of $\mathbf{K}_l$.

As a byproduct, we get the following counting of selfdual skew cyclic codes of $\mathbf{E}_k$.

**Theorem 3** (Cf. theorem 58) The number of selfdual skew cyclic codes of $\mathbf{E}_k$ is given by:

$$ \left\{ \begin{array}{ll} \text{If } p = 2, & \prod_{\{l|l=\tau(l), y_l=\pm 1\}} \prod_{i=1}^{s} (q_l^i + 1) \prod_{\{l|l=\tau(l), y_l \neq \pm 1\}} \prod_{i=1}^{s} (q_l^{i+1/2} + 1) \prod_{\{\{l,\tau(l)\}|l \neq \tau(l)\}} \sum_{k=0}^{k=r} \frac{(q_l^r - 1) \cdots (q_l^{r-k+1}-1)}{(q_l^k - 1) \cdots (q_l - 1)} \\ \\ \text{If } p \neq 2, & \prod_{\{l|l=\tau(l), y_l=\pm 1\}} \prod_{i=0}^{s-1} (q_l^i + 1) \prod_{\{l|l=\tau(l), y_l \neq \pm 1\}} \prod_{i=0}^{s-1} (q_l^{i+1/2} + 1) \prod_{\{\{l,\tau(l)\}|l \neq \tau(l)\}} \sum_{k=0}^{k=r} \frac{(q_l^r - 1) \cdots (q_l^{r-k+1}-1)}{(q_l^k - 1) \cdots (q_l - 1)} \end{array} \right. \\ \text{where } q_l \text{ denotes the cardinal of } \mathbf{F}_l $$

## Organization of the paper

In section 2, we give an insight for future work on the inseparable case.

In section 3, we give general definitions and notations used in this paper.

In section 4, we define selfdual skew codes.

In section 5, we introduce the evaluation isomorphism $\mathcal{J}_l$. For each $x_l$ in $\mathbf{K}_l$ satisfying $\text{Norm}_{\mathbf{K}_l/\mathbf{F}_l}(x_l) = y_l$, The isomorphism $\mathcal{J}_l$ is the evaluation at $x_l\theta$ from the central simple $\mathbf{F}_l$-algebra $\mathbf{E}_k^{(l)} := \mathbf{K}_l[X^{\pm 1}; \theta]/(X^r - y_l)$ to the simple matrix algebra: $\text{End}_{\mathbf{F}_l}(\mathbf{K}_l)$.

In section 6, the duality between the left ideals of the endomorphism ring and the kernels of their generators being order reversing and orthogonality preserving, we deduce from it that selfdual skew cyclic codes correspond to maximal isotropic subspaces.

In section 7, we provide enumeration algorithms for separable selfdual skew cyclic codes of the Ore quotient ring: $\mathbf{K}[X^{\pm 1}; \theta]/(X^{rk} - 1)$.

In section 8, computation results are provided for skew cyclic $(X^{rk} - 1, \mathbf{K}/\mathbf{F})$-codes and skew negacyclic $(X^{rk} + 1, \mathbf{K}/\mathbf{F})$-codes for $|\mathbf{F}| \le 9$, $k \le 9$ and $r \in \{4, 6, 8\}$. The source code of the SageMath implementation is available at this location:

https://plmlab.math.cnrs.fr/caruso/selfdual-skew-cyclic-codes

In appendix A, we provided enumeration algorithms for inseparable selfdual skew cyclic codes of the Ore quotient ring: $\mathbf{K}[X^{\pm 1}; \theta]/(X^{rkp^m} - 1)$.

# 2 Insight for future work on the inseparable case

We intend, in a future paper, to address the inseparable case using analogue methods. However, several crucial elements of the theory have to be adapted in the inseparable case:

Isotropic spaces have to be enumerated on free modules over power series rings with coefficients in a finite field, and not on finite vector spaces anymore.
# 2 From skew cyclic codes to finite geometry

## 2.1 Definition of skew cyclic codes

Let $\mathbf{F}$ be a finite field of cardinality $q$ and characteristic $p$. Let $\mathbf{K}$ be a finite extension of $\mathbf{F}$ of degree $r$. Let $\theta: x \mapsto x^q$ be the Frobenius automorphism of $\mathbf{K}$. We build the quotient of the free $\mathbf{K}$-algebra $\mathbf{K}\langle X\rangle$ by the noncommutative relation: $\forall \kappa \in \mathbf{K}, X\kappa = \theta(\kappa)X$. We then localize it at the powers of $X$. This results in the Ore Laurent polynomial ring $\mathbf{K}[X^{\pm 1}; \theta]$. As shown in [Jac96, Theorem 1.1.22], its center is $\mathbf{F}[X] \cap \mathbf{K}[X^{\pm r}] = \mathbf{F}[X^{\pm r}]$. For any $f \in \mathbf{F}[X^{\pm r}]$, we can thus form the quotient $\mathbf{K}[X^{\pm 1}; \theta]/(f(X))$, which keeps a ring structure. We will call skew quotient algebra the algebra $\mathbf{K}[X^{\pm 1}; \theta]/(f(X))$.

**Remark 2.1** As a quotient ring of the left and right Euclidean domain of skew Laurent polynomials, $\mathbf{K}[X^{\pm 1}; \theta]$, any skew quotient algebra is a left and right principal ideal ring.

We now move to the definition of selfdual skew cyclic codes. For any nonnegative integer $k$, $X^{rk} - 1$ is in the center of $\mathbf{K}[X^{\pm 1}; \theta]$. We can thus form the quotient ring $\mathbf{E}_k := \mathbf{K}[X^{\pm 1}; \theta]/(X^{rk} - 1)$. Choosing for any element of $\mathbf{E}_k$ the unique lift in $\mathbf{K}[X; \theta] \subset \mathbf{K}[X^{\pm 1}; \theta]$ of degree strictly less than $kr$ defines an isomorphism of $\mathbf{K}$-vector spaces $\lambda: \mathbf{E}_k \to \mathbf{K}^{rk}$.

Using the classical Hamming distance $d$ on the $\mathbf{K}$-vector space $\mathbf{K}^{rk}$, we define the Hamming distance $D$ between two elements $f$ and $g$ of $\mathbf{E}_k$ by $D(f, g) = d(\lambda(f), \lambda(g))$.

**Definition 2.2** Given $\alpha \in \mathbf{F}^*$, a skew $\alpha$-constacyclic codes is a left ideal of $\mathbf{K}[X^{\pm 1}; \theta]/(X^{rk} - \alpha)$ endowed with the metric $D$. Skew cyclic codes (resp. skew negacyclic codes) are skew $\alpha$-constacyclic codes for $\alpha = 1$ (resp. $\alpha = -1$).

We are interested in the skew cyclic code duality for the coordinatewise bilinear form, defined on $\mathbf{K}^{rk}$ by

$$((x_i)_{0 \le i < rk}, (y_i)_{0 \le i < rk}) \mapsto \sum_{0 \le i < rk} x_i y_i$$

We note that this bilinear form is nondegenerate.

**Definition 2.3** A skew cyclic code is said self-orthogonal (resp. selfdual) if $\lambda(I) \subset \lambda(I)^\perp$ (resp. if $\lambda(I) = \lambda(I)^\perp$).

As we have $\dim(\lambda(I)) + \dim(\lambda(I)^\perp) = r$, a necessary condition for selfdual skew cyclic codes to exist is that $r$ is even.

## 2.2 The evaluation isomorphism $\mathcal{E}_l$

We now place ourselves in the separable case, where $k$ is coprime to $p$. It is then known that $\mathbf{E}_k$ is a semisimple algebra (see [Wis91, Proposition 20.7]). As $\mathbf{E}_k$ is finite-dimensional over $\mathbf{F}$, classical results imply that it is a cartesian product of matrix algebras over finite field extensions of $\mathbf{F}$. Hereunder, we describe an explicit isomorphism realizing this decomposition.

We note $Y := X^r$ and decompose $Y^k - 1$ as a product of irreducible polynomials $P_l(Y)$ over $\mathbf{F}$. We set $\mathbf{F}_l := \mathbf{F}[Y]/P_l(Y)$, $\mathbf{K}_l := \mathbf{K}[Y]/P_l(Y)$ and let $y_l$ denote the image of $Y$ in $\mathbf{K}_l$. We extend $\theta$ to an
The echelon matrix representation of vector spaces has to be replaced by the Iwasawa decomposition of free sub-modules over a power series ring.

Fortunately, we can easily enumerate all selfdual skew cyclic codes by multiplying properly twisted separable selfdual skew cyclic codes with each other as described and illustrated by hand of SageMath computations in the appendix A.

# 3 General definitions and notations

## 3.1 Definitions in finite geometry

Let $F$ be a finite field and let $\sigma$ be an involutive automorphism of $F$, we recall that a $F$-vector space $V$ can be equipped with a $\sigma$-sesquilinear form $\mathcal{B}$ satisfying:

$$ \mathcal{B}(xu, yv) = x\sigma(y)\mathcal{B}(u, v) \quad \forall u, v \in V, \forall x, y \in F $$

We will consider the four following main types of finite geometries.

$V$ equipped with $\mathcal{B}$ is said to be an *Euclidean* space if we have:

$$ \sigma = \mathrm{Id} \quad \text{and} \quad \mathcal{B}(u, v) = \mathcal{B}(v, u) \quad \forall u, v \in V $$

$V$ equipped with $\mathcal{B}$ is said to be a *skew-Euclidean* space if we have:

$$ \sigma = \mathrm{Id} \quad \text{and} \quad \mathcal{B}(u, v) = -\mathcal{B}(v, u) \quad \forall u, v \in V $$

$V$ equipped with $\mathcal{B}$ is said to be a *Hermitian* space if we have:

$$ \sigma^2 = \mathrm{Id}, \sigma \neq \mathrm{Id} \quad \text{and} \quad \mathcal{B}(u, v) = \rho(\mathcal{B}(v, u)) \quad \forall u, v \in V $$

$V$ equipped with $\mathcal{B}$ is said to be a *skew-Hermitian* space if we have:

$$ \sigma^2 = \mathrm{Id}, \sigma \neq \mathrm{Id} \quad \text{and} \quad \mathcal{B}(u, v) = -\rho(\mathcal{B}(v, u)) \quad \forall u, v \in V $$
automorphism of $\mathbf{K}_l$ by letting it act trivially on $y_l$. We have a first decomposition

$$ 
\begin{aligned}
\mathbf{E}_k &\approx \mathbf{K}[Y, X; \theta]/(Y^k - 1, X^r - Y) \\
&\approx \left( \frac{\mathbf{K}[Y, X; \theta]}{\prod_{1 \le l \le n} P_l(Y)} \right) / (X^r - Y) = \prod_{1 \le l \le n} \mathbf{K}_l[X^{\pm 1}; \theta] / (X^r - y_l).
\end{aligned} 
\quad (2.1) $$

We set $\tilde{\mathbf{E}}_k^{(l)} = \mathbf{K}_l[X^{\pm 1}; \theta]/(X^r - y_l)$ and now study each $\tilde{\mathbf{E}}_k^{(l)}$ separately. We observe that $\mathbf{K}_l$ is a finite étale extension of the finite field $\mathbf{F}_l$, i.e. a finite product of finite extensions of $\mathbf{F}_l$. As such, the norm map $\text{Norm}_{\mathbf{K}_l/\mathbf{F}_l}$ is surjective; hence, there exists an element $x_l$ in $\mathbf{K}_l$ satisfying $\text{Norm}_{\mathbf{K}_l/\mathbf{F}_l}(x_l) = y_l$. The change of variables $X \mapsto x_lX$ defines an isomorphism

$$ \text{Eval}_{x_l X} : \tilde{\mathbf{E}}_k^{(l)} \xrightarrow{\sim} \mathbf{E}_k^{(l)} := \mathbf{K}_l[X^{\pm 1}; \theta]/(X^r - 1). $$

On the other hand, we have an evaluation morphism $X \mapsto \theta$:

$$ \begin{array}{rcl} \text{Eval}_{\theta}: & \mathbf{E}_k^{(l)} & \to \text{End}_{\mathbf{F}_l}(\mathbf{K}_l) \\ & P(X) & \mapsto P(\theta) \end{array} $$

Composing both maps, we obtain a third morphism $\mathcal{E}_l : \tilde{\mathbf{E}}_k^{(l)} \to \text{End}_{\mathbf{F}_l}(\mathbf{K}_l)$. Applying it to each term $\tilde{\mathbf{E}}_k^{(l)}$ of the decomposition (2.1), we finally end up with a map relating $\mathbf{E}_k$ to a product of matrix algebras.

**Proposition 2.4** The map

$$ (\mathcal{E}_l)_{l \in \{1, \dots, n\}} : \mathbf{E}_k \to \prod_{1 \le l \le n} \text{End}_{\mathbf{F}_l}(\mathbf{K}_l) $$

is an isomorphism of $\mathbf{F}$-algebra.

*Proof.* (See also [Jac96, Theorem 1.3.12].) By Artin's lemma, the family $(\theta^i)_{0 \le i < r}$ is linearly independent. This proves the injectivity of $\mathcal{E}_l$. As the dimension (over $\mathbf{F}_l$) of its domain and the codomain are both $r^2$, surjectivity follows. The final evaluation map resulting from the composition of the chinese remainder isomorphism with the product of isomorphisms $\text{Eval}_{x_l \theta}$ is thus an isomorphism. $\square$

**Remark 2.5** To compute the evaluation isomorphism $\mathcal{E}_l$, a fast computation of preimages by the norm is needed. One possible method consists in finding an irreducible factor of the skew polynomial $X^r - y_l$ in $\mathbf{K}_l[X; \theta]$. An algorithm for this task is described in [CL17].

**Remark 2.6** By the Skolem-Noether theorem, the isomorphism $\mathcal{E}_l$ is uniquely defined up to conjugacy by an element of norm 1, i.e. up to another choice of $x_l$ as preimage of $y_l$ by the norm map.

## 2.3 Adjunctions on $\mathbf{E}_k$ and related spaces

In this subsection, we construct an alternative bilinear pairing on $\mathbf{E}_k$ and show that it induces the same orthogonals than the coordinatewise bilinear form considered previously. Our variant is interesting because it will in turn induce a pairing on the simpler spaces $\mathbf{E}_k^{(l)}$.
Moreover, the endomorphism ring of $F$-linear endomorphisms $End_F(V)$ is equipped with an
involutive anti-automorphism $f \mapsto f^*$ characterised by:

$$
\forall f \in \mathrm{End}_F(V), \forall u, v \in V, \mathcal{B}(u, f^*(v)) = \mathcal{B}(f(u), v)
$$

We call this involutive anti-automorphism the adjunction relative to the bilinear form $\mathcal{B}$.

We recall also that a totally isotropic subspace $W$ of $V$ is characterised by $W \subset W^{\perp}$ and that
such a subspace of (maximal) dimension, half the dimension of the ambiant space, is characterised
by $W = W^{\perp}$.

Finally a hyperbolic pair in $V$ equipped with $\mathcal{B}$ is a pair of vectors $\{u, v\}$ of $V$ satisfying
$\mathcal{B}(u, u) = 0$, $\mathcal{B}(v, v) = 0$ and $\mathcal{B}(u, v) = 1$.

The 2-dimensional subspace $\langle u, v \rangle$ of $V$ spanned by a hyperbolic pair $\{u, v\}$ is called a
*hyperbolic plane*.

3.2 Notations

In this paper, we will use the following notations:

• $\mathbb{F}_q$ will denote a finite field of cardinal $q$

• $\mathbf{F}_l$ will denote the finite field extension of $\mathbf{F}$ such that, $\prod_{1 \le l \le n} \mathbf{F}_l = \mathbf{F}[Y]/(Y^k - 1)$

• $y_l$ will denote a primitive element of the finite field extension $\mathbf{F}_l/\mathbf{F}$, so that we have:
$$
\mathbf{F}(y_l) := \mathbf{F}_l
$$

• $q_l$ will denote the cardinal of $\mathbf{F}_l$.

• $\mathbf{K}_l$ will denote the finite etale $\mathbf{F}_l$-algebra $\mathbf{K} \otimes_{\mathbf{F}} \mathbf{F}_l$.

• $\mathbf{E}_{k,l}$ will denote the central simple $\mathbf{F}_l$-algebra $\mathbf{K} \otimes_{\mathbf{F}} \mathbf{F}_l[X; \theta]/(X^r - 1)$.

• $End_R(V)$ will denote, for any ring $R$ and $R$-module $V$, the endomorphism ring of all $R$-linear endomorphisms of $V$.

• $Mat_{R,r \times r}$ will denote, for any ring $R$, the matrix ring of all $r \times r$ square matrices with entries in $R$.

• $M^{\mathrm{tr}}$ will denote the transpose of the matrix $M$.

• $\mathrm{Id}$ will denote the identity morphism.
We begin by defining an adjunction on $\mathbf{E}_k$. We start from the following $\mathbf{F}$-linear automorphism on $\mathbf{K}[X^{\pm 1}; \theta]$

$$ \mathbf{K}[X^{\pm 1}; \theta] \xrightarrow{*} \mathbf{K}[X^{\pm 1}; \theta] \\ f = \sum_i f_i X^i \mapsto f^* = \sum_i X^{-i} f_i $$

It is an involution, i.e. $f^{**} = f$ for all $f$. One moreover checks that it is an anti-morphism, i.e. it satisfies $(fg)^* = g^*f^*$ for all $f, g \in \mathbf{K}[X^{\pm 1}; \theta]$. Indeed, by linearity, it is enough to check the desired property when $f$ and $g$ are monomials, which is a direct computation. We observe that the adjoint $(X^{rk} - 1)^*$ is a multiple of $X^{rk} - 1$ itself. The adjunction thus preserves the two-sided ideal generated by $X^{rk} - 1$; therefore, it passes to the quotient to define an anti-automorphism of $\mathbf{E}_k$. In a slight abuse of notation, we continue to write $f^*$ when $f \in \mathbf{E}_k$. Since the adjunction is an anti-automorphism, we underline that it maps left ideals of $\mathbf{E}_k$ to right ideals.

We now define a nondegenerate bilinear form corresponding to this adjunction. We introduce to this end the notion of reduced trace of a skew polynomial: given $f = \sum_i f_i X^i \in \mathbf{K}[X^{\pm 1}; \theta]$, we set

$$ T_{\mathrm{rd}}(f) = \sum_{i} \mathrm{Trace}_{\mathbf{K}/\mathbf{F}}(f_{ir}) \cdot Y^i \in \mathbf{F}[Y]. $$

This definition passes to the quotient and defines a map $T_{\mathrm{rd}} : \mathbf{E}_k \to \mathbf{F}[Y]/(Y^k - 1)$. For $f, g \in \mathbf{E}_k$, we define

$$ \langle f, g \rangle := T_{\mathrm{rd}}(fg^*) \in \mathbf{F}[Y]/(Y^k - 1). $$

It is readily seen that $f \mapsto f^*$ satisfies the adjunction formula, in the sense that $\langle f, gh \rangle = \langle fh^*, g \rangle$ for any $f, g, h \in \mathbf{E}_k$. Denoting by $I^{\perp}$ the orthogonal of $I \subset \mathbf{E}_k$, we have the following compatibility property.

**Proposition 2.7** For any left ideal $I$ of $\mathbf{E}_k$, we have $\lambda(I^{\perp}) = \lambda(I)^{\perp}$.

*Proof.* Let $f \in I$, $g \in I^{\perp}$ and set $u = \sum_{0 \le i < kr} \lambda(f)_i \lambda(g)_i$. The condition $T_{\mathrm{rd}}(fg^*) = 0$ translates to $\mathrm{Trace}_{\mathbf{K}/\mathbf{F}}(u) = 0$. More generally, for all $\kappa \in \mathbf{K}$, we have $T_{\mathrm{rd}}(\kappa fg^*) = 0$ (since $\kappa f \in I$) and so $\mathrm{Trace}_{\mathbf{K}/\mathbf{F}}(\kappa u) = 0$. By nondegeneracy of $\mathrm{Trace}_{\mathbf{K}/\mathbf{F}}$, this implies that $u = 0$, i.e. $\lambda(f)$ is orthogonal to $\lambda(g)$. The inclusion $\lambda(I^{\perp}) \subset \lambda(I)^{\perp}$ follows.

Conversely, we consider $g \in \mathbf{E}_k$ such that $\lambda(g) \in \lambda(I)^{\perp}$. Let also $f \in I$. The orthogonality condition between $\lambda(f)$ and $\lambda(g)$ implies the vanishing of the constant coefficient of $fg^*$. More generally, using that $X^{-ir}f \in I$, we deduce that the coefficient in $X^{ir}$ of $fg^*$ vanishes as well. Therefore $T_{\mathrm{rd}}(fg^*) = 0$ and we conclude that $g \in I^{\perp}$. $\square$

In what follows, we prefer working with the pairing $\langle -, - \rangle$ because it corresponds to sesquilinear trace forms on the $\mathbf{F}_l$-algebras $\mathbf{E}_k^{(l)}$. We now describe them.

**Definition 2.8** We say that a polynomial is *palindromic* if the set of its roots in an algebraic closure of its base field does not contain zero and is stable under the inversion map $x \mapsto \frac{1}{x}$. Equivalently a polynomial $\sum_{i=0}^{n} p_i x^i$ (with $p_n \neq 0$) is *palindromic* if it is collinear to its reciprocal polynomial $\sum_{i=0}^{n} p_{n-i} x^i$.

We recall that we have the decomposition $F[Y]/(Y^k - 1) \simeq \prod_{1 \le l \le n} F[Y]/P_l(Y) \simeq \prod_{1 \le l \le n} \mathbf{F}_l$.
• $\mathcal{J}_l$ will denote the evaluation isomorphism

$$ \mathcal{J}_l: \left\{ \begin{array}{ll} \mathbf{K}_l[X^{\pm 1}; \theta] & \xrightarrow{\sim} \mathrm{End}_{\mathbf{F}_l}(\mathbf{K}_l) \\ X & \mapsto x_l \theta \end{array} \right. \qquad (3.1) $$

where $\mathrm{Norm}_{\mathbf{K}_l/\mathbf{F}_l}(x_l) = y_l$

• $f^*$ will denote the adjunction in $\mathbf{E}_k$ or $\mathbf{E}_k^{(l)}$.

• $f^*$ will denote the adjunction in $\mathbf{E}_{k,l}$ or $\mathrm{End}_{\mathbf{F}_l}(\mathbf{K}_l)$.

• $\mathrm{GL}_n(F)$ will denote the general linear group of the vector space $F^n$ over the finite field $F$.

• $L^\sigma$ will denote the subfield of the field $L$ fixed by the automorphism $\sigma$.

• $V^\perp$ will denote the orthogonal of a vector subspace $V$.

# 4 Skew cyclic codes

Let $\mathbf{F}$ be a finite field of cardinal $q$ and characteristic $p$. Let $\mathbf{K}/\mathbf{F}$ be a finite extension of $\mathbf{F}$ of degree $r$. Let $\theta$ be the Frobenius automorphism of $\mathbf{K}/\mathbf{F}$: $\mathbf{x} \mapsto \mathbf{x}^q$. Let $\mathbf{K}[X^{\pm 1}; \theta]$ be the corresponding Ore Laurent polynomial ring defined as the quotient of the free $\mathbf{K}$-algebra $\mathbf{K}\langle X \rangle$ by the noncommutative relation: $\forall k \in \mathbf{K}, X \cdot k = \theta(k) \cdot X$, localized by the powers of $X$. As shown in Theorem 1.1.22 in [Jac96], the center of the Ore Laurent polynomial ring $\mathbf{K}[X^{\pm 1}; \theta]$ is $\mathbf{F}[X] \cap \mathbf{K}[X^{\pm r}] = \mathbf{F}[X^{\pm r}]$.

**Definition 4** A skew quotient algebra is a quotient algebra $\mathbf{K}[X^{\pm 1}; \theta]/(f(X))$, where $f$ is taken in the center $\mathbf{F}[X^{\pm r}]$.

**Remark 5** As quotient ring of the left and right Euclidean domain of skew Laurent polynomials, $\mathbf{K}[X^{\pm 1}; \theta]$, it is a left and right principal ideal ring.

We now turn to the definition of selfdual skew cyclic codes.

**Definition 6** The Hamming distance on left ideals of any skew quotient algebra $\mathbf{K}[X^{\pm 1}; \theta]/(P(X))$ is defined as the Hamming distance of the underlying $\mathbf{K}$-vector spaces.

**Definition 7** The skew codes of a skew quotient algebra $\mathbf{K}[X^{\pm 1}; \theta]/(P(X))$ are its left ideals seen as vector subspaces over $\mathbf{K}$ and equipped with the Hamming metric.
**Definition 2.9** We define the map $\tau : \{1, \dots, n\} \to \{1, \dots, n\}$ by the relation $P_{\tau(l)}(\frac{1}{y_l}) = 0$.

As the polynomial $Y^k - 1$ is palindromic and separable, the index $\tau(l)$ exists, and $\tau$ is obviously involutive. Furthermore, we let $\sigma$ be the endomorphism of $F$-algebras of $F[Y]/(Y^k - 1)$ defined by $Y \mapsto \frac{1}{Y}$. It is also involutive and it induces isomorphisms $\sigma_l : F_l \to F_{\tau(l)}$ such that $\sigma_l(y_l) = y_{\tau(l)}$. The tensor product $\text{id} \otimes \sigma_l$ defines an involutive isomorphism $K_l \to K_{\tau(l)}$ extending $\sigma_l$. For simplicity, we will keep the notation $\sigma_l$ for id $\otimes \sigma_l$.

The next proposition shows that the adjunction behaves nicely with respect to the decomposition $E_k = \prod_{l=1}^n \tilde{E}_k^{(l)}$ we have established in Equation (2.1).

**Proposition 2.10** The adjunction $f \mapsto f^*$ induces “partial” adjunctions $\tilde{E}_k^{(l)} \to \tilde{E}_k^{(\tau(l))}$, which are explicitly given by the formula

$$ \sum_{i=0}^{\deg P_l - 1} f_i X^i \mapsto \sum_{i=0}^{\deg P_l - 1} X^{-i} \sigma_l(f_i), \quad \forall f_i \in \mathbf{K}_l. \qquad (2.2) $$

Moreover, the “global” adjunction can be recovered by taking the product of the partial ones.

*Proof.* Let $Q_l$ be the element of $F[Y]/(Y^k - 1) \subset E_k$ corresponding to the factor $F_l$, i.e. the element defined by the congruences $Q_l \equiv 1 \pmod{P_l}$ and $Q_l \equiv 0 \pmod{P_{l'}}$ whenever $l' \neq l$. As automorphisms respect congruences, we have $Q_l^* = \sigma(Q_l) = Q_{\tau(l)}$. Besides $\tilde{E}_k^{(l)} = Q_l E_k = E_k Q_l$. We thus have $\tilde{E}_k^{(l)*} = (Q_l E_k)^* = E_k Q_l^* = E_k Q_{\tau(l)} = \tilde{E}_k^{(\tau(l))}$. The explicit formula (2.2) is derived after noticing that $f_i^* = \sigma_l(f_i)$ for $f_i \in \mathbf{K}_l$. Finally, the last statement of the proposition is clear. $\square$

We now aim at describing how the adjunction is transformed by the evaluation isomorphisms $\mathcal{E}_l$. For this, the first step is to understand its effect on $E_k^{(l)}$ (without the tilde) which, we recall, is defined as $E_k^{(l)} = K_l[X; \theta]/(X^r - 1)$. The adjunction $f \mapsto f^*$ again passes to the quotient and determines a well-defined adjunction $E_k^{(l)} \to E_k^{(\tau(l))}$, that we continue to denote $f \mapsto f^*$. Unfortunately, the latter is not exactly what we need; we are now going to fix this issue by defining a twisting version of it. For this, we first define $z_l := x_l \cdot \sigma_{\tau(l)}(x_{\tau(l)}) \in \mathbf{K}_l$.

**Lemma 2.11** There exists a family of invertible elements $\zeta_l \in \mathbf{K}_l$ such that $\theta(\zeta_l) = z_l \zeta_l$ and $\sigma_l(\zeta_l) = \zeta_{\tau(l)}$ for all $l$.

*Proof.* Since $\sigma_l \circ \sigma_{\tau(l)} = \text{id}$, we have $\sigma_l(x_l \cdot \sigma_{\tau(l)}(x_{\tau(l)})) = x_{\tau(l)}\sigma_l(x_l)$, which ensures that $z_l$ is invariant under $\sigma_l$. Furthermore, we observe that $\text{Norm}_{K_l/F_l}(z_l) = y_l \cdot \sigma_{\tau(l)}(y_{\tau(l)}) = 1$. Hence, the Hilbert 90 Theorem guarantees the existence of an element $\zeta_l$ of $K_l^*$ such that $\theta(\zeta_l) = z_l \zeta_l$ and hence $z_l X = \zeta_l^{-1} X \zeta_l$. Moreover, as automorphisms of finite fields commute, $\sigma_l(\zeta_l)$ satisfies $\theta(\sigma_l(\zeta_l)) = z_l \sigma_l(\zeta_l)$. Set $\zeta'_l := \zeta_l + \sigma_{\tau(l)}(\zeta_{\tau(l)})$, so that we have $\sigma_l(\zeta'_l) = \zeta'_{\tau(l)}$. If $\zeta'_l$ is invertible, it satisfies $z_l X = \zeta_l'^{-1} X \zeta'_l$ as well. At the opposite side, if $\zeta'_l = 0$, we have $\sigma_{\tau(l)}(\zeta_{\tau(l)}) = -\zeta_l$. In this case, $\sigma_l$ is nontrivial and so $y_{\tau(l)} \neq \pm 1$. As $\frac{\zeta_l}{y_l}$ satisfies also $\theta(\frac{\zeta_l}{y_l}) = z_l \frac{\zeta_l}{y_l}$, the element $\zeta''_l := \frac{\zeta_l}{y_l} + \sigma_{\tau(l)}(\frac{\zeta_{\tau(l)}}{y_{\tau(l)}})$ does not vanish and it satisfies moreover $\zeta''_l z_l X = X \zeta''_l$ and $\sigma_l(\zeta''_l) = \zeta''_{\tau(l)}$. In full generality, we write $\mathbf{K}_l$ as a product of fields and apply the previous reasoning component by component. $\square$
The skew cyclic codes are skew codes of a skew quotient algebra of the form $K[X^{\pm 1}; \theta]/(X^{kr} - 1)$.

The skew negacyclic codes are skew codes of a skew quotient algebra of the form $K[X^{\pm 1}; \theta]/(X^{kr} + 1)$.

The skew constacyclic codes are skew codes of a skew quotient algebra of the form $K[X^{\pm 1}; \theta]/(X^{kr} + \alpha)$ with $\alpha \in F^*$.

**Definition 8** Choosing for any element of $E_k$ the unique lift in $K[X; \theta] \subset K[X^{\pm 1}; \theta]$ of degree strictly less than $kr$ defines an isomorphism of $K$-vector spaces.

$$ \lambda: \quad E_k \quad \rightarrow \quad K^{rk} \\ f \quad \mapsto \quad \lambda(f) \tag{4.1} $$

We are interested in the skew code duality for the following coordinatewise bilinear form.

**Definition 9** In the canonical base of $K^{rk}$, we define the coordinatewise bilinear form on $K^{rk}$ by: $((x_i)_{0 \le i < rk}, (y_i)_{0 \le i < rk}) \mapsto \sum_{0 \le i < rk} x_i y_i$.

We note that this bilinear form is nondegenerate.

**Definition 10** The self-orthogonal skew codes are the skew codes $I$ such that: $\lambda(I) \subset \lambda(I)^{\perp}$.

The selfdual skew codes are the skew codes $I$ such that: $\lambda(I) = \lambda(I)^{\perp}$.

As we have $\dim(\lambda(I)) + \dim(\lambda(I)^{\perp}) = r$, a necessary condition for selfdual skew codes to exist is that $r$ is even.

**Hypothesis 11** We restrict the study in this paper to even orders $2s := r$.

# 5 On the semisimple algebra $E_k$

## 5.1 Semi-simplicity of the algebra $E_k$

For any nonnegative integer $k$, $X^{rk} - 1$ is in the center. We can thus quotient the Ore Laurent polynomial ring by the two-sided ideal $(X^{rk} - 1)$ to build the skew cyclic quotient algebra $E_k := K[X^{\pm 1}; \theta]/(X^{rk} - 1)$.

**Proposition 12** The algebra $E_k$ is semisimple in the separable case where $k$ is coprime to $p$.
**Remark 2.12** The element $\zeta_l$ can be efficiently computed using the following formula from the proof of the Hilbert 90 Theorem: it can be chosen as the multiplicative inverse of any nonzero element in the image of the endomorphism $\sum_{0 \le i < r} \prod_{0 \le j < i} \theta^j(z_l)\theta^i$.

**Definition 2.13** For $f \in \mathbf{E}_k^{(l)}$, we set $f^\bullet := (\zeta_l f \zeta_l^{-1})^* = \zeta_{\tau(l)}^{-1} f^* \zeta_{\tau(l)} \in \mathbf{E}_k^{(\tau(l))}$.

**Lemma 2.14** For all $f \in \tilde{\mathbf{E}}_k^{(l)}$, we have $f^*(x_{\tau(l)}X) = f(x_l X)^\bullet$.

*Proof.* By additivity, it is enough to check the formula when $f$ is the monomial $\kappa X^i$. We thus have $f^* = X^{-i} \sigma_l(\kappa)$ and so

$$f^*(x_{\tau(l)}X) = X^{-i} \sigma_l(\kappa) \left( \prod_{t=0}^{i-1} \theta^t(x_{\tau(l)}) \right)^{-1} \\ f(x_l X)^\bullet = \left( \kappa \prod_{t=0}^{i-1} \theta^t(x_l) X^i \right)^\bullet = (z_{\tau(l)} X)^{-i} \sigma_l \left( \kappa \prod_{t=0}^{i-1} \theta^t(x_l) \right).$$

We conclude by noticing that $\prod_{t=0}^{i-1} \theta^t(z_{\tau(l)}) = \prod_{t=0}^{i-1} \theta^t(x_{\tau(l)}) \sigma_l(\prod_{t=0}^{i-1} \theta^t(x_l))$. $\square$

Following the isomorphism $\mathbf{E}_k^{(l)} \simeq \mathrm{End}_{\mathbf{F}_l}(\mathbf{K}_l)$ and its counterpart for $\tau(l)$, we find that the adjunction $f \mapsto f^\bullet$ induces another anti-isomorphism $\mathrm{End}_{\mathbf{F}_l}(\mathbf{K}_l) \xrightarrow{\bullet} \mathrm{End}_{\mathbf{F}_{\tau(l)}}(\mathbf{K}_{\tau(l)})$. We are now going to prove that the latter is the adjunction map associated to some explicit bilinear map. Precisely, we introduce the twisted bilinear trace form

$$\mathbf{K}_l \times \mathbf{K}_{\tau(l)} \to \mathbf{F}_l \qquad (2.3) \\ (\kappa, \rho) \mapsto (\kappa, \rho)_{\mathbf{F}_l} := \mathrm{Trace}_{\mathbf{K}_l/\mathbf{F}_l}(\zeta_l \cdot \kappa \cdot \sigma_{\tau(l)}(\rho))$$

In the palindromic case, we have $\mathbf{K}_{\tau(l)} = \mathbf{K}_l$ and we observe that the above pairing is Euclidean when $y_l = \pm 1$ and Hermitian otherwise. In all cases, the bilinear form $(-, -)_{\mathbf{F}_l}$ is nondegenerate and hence identifies $\mathbf{K}_l$ with the dual of $\mathbf{K}_{\tau(l)}$.

**Proposition 2.15** The involutive isomorphism $\bullet$ is the adjunction relative to $(-, -)_{\mathbf{F}_l}$, i.e.

$$(f(\kappa), \rho)_{\mathbf{F}_l} = (\kappa, f^{\bullet}(\rho))_{\mathbf{F}_l}, \quad \forall f \in \mathrm{End}_{\mathbf{F}_l}(\mathbf{K}_l), \quad \forall \kappa \in \mathbf{K}_l, \quad \forall \rho \in \mathbf{K}_{\tau(l)}.$$

*Proof.* We write $f = \sum_{0 \le i \le r-1} f_i \theta^i$ with $f_i \in \mathbf{K}_l$ and compute

$$(f(\kappa), \rho)_{\mathbf{F}_l} = \sum_{k=0}^{r-1} \theta^k \left( \zeta_l \cdot \sigma_{\tau(l)}(\rho) \cdot \sum_{i=0}^{r-1} f_i \theta^i(\kappa) \right) \\ = \sum_{i=0}^{r-1} \sum_{k=0}^{r-1} \theta^{k+i} \left( \zeta_l \cdot \theta^{-i}(f_i) \cdot \frac{\theta^{-i}(\zeta_l)}{\zeta_l} \cdot \theta^{-i}(\sigma_{\tau(l)}(\rho)) \cdot \kappa \right) \\ = \sum_{k=0}^{r-1} \theta^k \left( \sum_{i=0}^{r-1} \zeta_l \cdot \theta^{-i}(f_i) \cdot \theta^{-i}(\zeta_l \sigma_{\tau(l)}(\rho)) \cdot \zeta_l^{-1} \cdot \kappa \right) \\ = \mathrm{Trace}_{\mathbf{K}_l/\mathbf{F}_l}(\zeta_l \cdot \sigma_{\tau(l)}(f^{\bullet}(\rho)) \cdot \kappa) = (\kappa, f^{\bullet}(\rho))_{\mathbf{F}_l}$$

which is exactly what we want.

<figure><img src="image_3.png" /></figure>
*Proof.* The detail of the following proof can be found in Proposition 20.7 in [Wis91]. The quotient $\mathbf{E}_k$ is Artinian so its Jacobson radical must be nilpotent. As $k$ is coprime to $p$, $\mathbf{E}_k$ is separable and its Jacobson radical must thus be trivial. It follows that $\mathbf{E}_k$ is a semisimple algebra over $\mathbf{F}$. As it is finite-dimensional, it is a cartesian product of simple algebras over $\mathbf{F}$ which reduces by the Wedderburn theorem to a product of matrix algebras over finite, hence commutative, fields extensions of $\mathbf{F}$. $\square$

**Remark 13** In the inseparable case where $k$ is not coprime to the characteristic $p$, the Jacobson radical is equal to the nilradical generated by $(X^{rk} - 1)$, so $\mathbf{E}_k$ is not semisimple anymore. It is still a product of matrix algebras though, but over an Artinian $\mathbf{F}$-algebra, and not over a field $\mathbf{F}$ anymore.

**Hypothesis 14** We place ourselves in the separable case where $k$ is coprime to $p$, except in the appendix A where we treat the inseparable case

## 5.2 The evaluation isomorphism $\mathcal{J}_l$

We will show that the family of evaluation isomorphisms $(\mathcal{J}_l)_l$ where $\mathcal{J}_l$ is defined by:
$$ \left\{ \begin{array}{rcl} \mathbf{E}_k & \to & \mathrm{End}_{\mathbf{F}_l}(\mathbf{K}_l) \\ X & \mapsto & x_l \theta \end{array} \right. $$
with $\mathrm{Norm}_{\mathbf{K}_l/\mathbf{F}_l}(x_l) = y_l$, when applied to the chinese remainder decomposition of the central semi-simple $\mathbf{F}$-algebra $\mathbf{E}_k$, realizes an explicit isomorphism between $\mathbf{E}_k$ and a product of matrix algebras.

Indeed, expressing $\mathbf{E}_k$ as an $\mathbf{F}[Y]/(Y^k - 1)$-algebra and decomposing $Y^k - 1$ in a product of irreducible polynomials $P_l(Y)$ over $\mathbf{F}$, we obtain from the chinese remainder theorem:

$$ \mathbf{E}_k \simeq \mathbf{K}[Y, X; \theta]/((Y^k - 1), X^r - Y) \simeq (\mathbf{K}[Y, X; \theta]/(Y^k - 1))/(X^r - Y) \quad (5.1) $$

$$ \mathbf{E}_k \simeq \left( \mathbf{K}[Y, X; \theta] / \left( \prod_{1 \le l \le n} P_l(Y) \right) \right) / (X^r - Y) $$

Noting $\mathbf{F}_l := \mathbf{F}[Y]/(P_l(Y))$, $\mathbf{K}_l := \mathbf{K} \otimes_{\mathbf{F}} \mathbf{F}_l$, $\mathbf{E}_k^{(l)} := \mathbf{K}_l[X^{\pm 1}; \theta]/(X^r - y_l)$, we get the following lemma:
Finally, composing the morphisms $X \mapsto x_l X$ and $X \mapsto \theta$, we obtain the following commutative diagram:

$$ \begin{tikzcd} \begin{gathered} \tilde{\mathbf{E}}_k^{(l)} \arrow[r, "X \mapsto x_l X"] \arrow[d, "f \mapsto f^*"'] & \mathbf{E}_k^{(l)} \arrow[r, "X \mapsto \theta"] \arrow[d, "f \mapsto f^*"'] & \mathrm{End}_{\mathbf{F}_l}(\mathbf{K}_l) \\ \tilde{\mathbf{E}}_k^{(\tau(l))} \arrow[r, "X \mapsto x_{\tau(l)} X"] \arrow[d, "f \mapsto f^*"'] & \mathbf{E}_k^{(\tau(l))} \arrow[r, "X \mapsto \theta"] \arrow[d, "f \mapsto f^*"'] & \mathrm{End}_{\mathbf{F}_{\tau(l)}}(\mathbf{K}_{\tau(l)}) \end{tikzcd} \quad (2.4) $$

where we note that the composite of the horizontal maps is $\mathcal{E}_l$ on the top, and $\mathcal{E}_{\tau(l)}$ on the bottom.

## 2.4 Vector space duality

In the previous subsections, we reduced the problem of finding selfdual skew cyclic codes in $\mathbf{E}_k$ to that of finding selfdual skew cyclic codes in the product of the $\mathrm{End}_{\mathbf{F}_l}(\mathbf{K}_l)$. We will now further reduce this problem to that of finding maximal isotropic $\mathbf{F}_l$-vector spaces of $\mathbf{K}_l$ in the palindromic case and of $\mathbf{K}_l \times \mathbf{K}_{\tau(l)}$ in the nonpalindromic case.

To this end, we apply the classical duality between $\mathbf{F}_l$-vector subspaces of $\mathbf{K}_l$ and left ideals of $\mathrm{End}_{\mathbf{F}_l}(\mathbf{K}_l)$. Let us recall it briefly. Given a field $F$ and a finite dimensional $F$-vector space $W$, the *vector space duality* associates to every $F$-vector subspace $V$ of $W$, the left ideal $I_V$ of $\mathrm{End}_F(W)$ formed by the endomorphisms vanishing on $V$. Dually, it associates to every left ideal $I$ of $\mathrm{End}_F(W)$, the intersection of the kernels of the morphisms in $I$. With formulas, it can be expressed as

$$ \begin{gathered} I \mapsto V_I = \bigcap_{f \in I} \ker(f), \\ V \mapsto I_V = \{ f \in \mathrm{End}_F(W) \mid V \subset \ker(f) \}. \end{gathered} $$

This duality defines an order-reversing one-to-one correspondence between the set of left ideals of $\mathrm{End}_F(W)$ and the set of $F$-vector subspaces of $W$. Moreover, for all $V \subset W$, we have $\dim_F I_V = (\dim_F W - \dim_F V) \cdot \dim_F W$.

We now assume in addition that we are given an involution $\sigma: F \to F$ and that $W$ is endowed with a nondegenerate $\sigma$-sesquilinear form. We recall that this datum equips $\mathrm{End}_F(W)$ with a sesquilinear form as well. In particular, taking orthogonals over $W$ and $\mathrm{End}_F(W)$ makes sense.

**Proposition 2.16** For all subspace $V$ of $W$, we have $I_V^\perp = I_{V^\perp}$.

*Proof.* Given $f \in I_V$ and $g \in I_{V^\perp}$, we have $f \circ g^* = 0$ since $f$ vanishes on $V$ and $\mathrm{im} \, g^* = (\ker g)^\perp \subset V$. Therefore $f$ and $g$ are orthogonal in $\mathrm{End}_F(W)$. It follows that $I_V^\perp \subset I_{V^\perp}$. The equality follows by comparing dimensions. $\square$

We are now ready to apply what precedes to codes and prove the main theorem of this section.

**Theorem 2.17** There exists an explicit bijection between the set of selfdual skew cyclic codes of $\mathbf{E}_k$ and the cartesian product of sets $W_{\mathrm{pal}} \times W_{\mathrm{nonpal}}$, where:

* $W_{\mathrm{pal}}$ is the cartesian product, over the set $I$ of indexes invariant under $\tau$, of the sets of isotropic $\mathbf{F}_l$-vector subspaces of $\mathbf{K}_l$ of dimension $r/2$,
**Lemma 15** The map:

$$ \mathbf{E}_k \xrightarrow{\sim} \prod_{1 \le l \le n} \mathbf{E}_k^{(l)} \qquad (5.2) $$

$$ P \mapsto P \mod (X^r - y_l) $$

is an isomorphism of rings.

We will now study each $\mathbf{E}_k^{(l)}$. $\mathbf{K}_l$ is a finite etale extension of the finite field $\mathbf{F}_l$, i.e. a finite product of finite extensions of $\mathbf{F}_l$. As it has finite cardinality, its norm is surjective and there exists an element $x_l$ in $\mathbf{K}_l$ satisfying: $\mathrm{Norm}_{\mathbf{K}_l/\mathbf{F}_l}(x_l) = y_l$, so that the evaluation isomorphism at $x_l X$ from $\mathbf{E}_k^{(l)} := \mathbf{K}_l[X^{\pm 1}; \theta]/(X^r - \mathrm{Norm}_{\mathbf{K}_l/\mathbf{F}_l}(x_l))$ to $\mathbf{E}_{k,l} := \mathbf{K}_l[X^{\pm 1}; \theta]/(X^r - 1)$ is well defined:

$$ \mathbf{E}_k^{(l)} \xrightarrow{\overline{\mathrm{Eval}_{x_l X}}} \mathbf{E}_{k,l} \qquad (5.3) $$

$$ P(X) \mapsto P(x_l X) $$

Now we have the obvious evaluation isomorphism $X \mapsto \theta$, from $\mathbf{E}_{k,l}$ to $\mathrm{End}_{\mathbf{F}_l}(\mathbf{K}_l)$

$$ \mathbf{E}_{k,l} \xrightarrow{\mathrm{Eval}_{\theta}} \mathrm{End}_{\mathbf{F}_l}(\mathbf{K}_l) \qquad (5.4) $$

$$ P(X) \mapsto P(\theta) $$

Composing both evaluation isomorphisms and using lemma 15, we get:

**Proposition 16** (see theorem 1.3.12 in [Jac96]) The evaluation map:

$$ (\mathcal{J}_l)_l : \mathbf{E}_k \xrightarrow{(\mathrm{Eval}_{x_l \theta})_{1 \le l \le n}}} \prod_{1 \le l \le n} \mathrm{End}_{\mathbf{F}_l}(\mathbf{K}_l) \qquad (5.5) $$

$$ P(X) \xrightarrow{\sim} (P(x_l \theta))_{1 \le l \le n} $$

is an isomorphism of central simple algebra over $\mathbf{F}_l$.

*Proof.* The family $(b_i X^j)_{0 \le i < r, 0 \le j < r}$ for an $\mathbf{F}_l$ base $(b_i)_{0 \le i < r}$ of $\mathbf{K}_l$ is a free family of $\mathbf{E}_k^{(l)}$ seen as $\mathbf{F}_l$ vector space. It has cardinality $r^2$. Now the evaluation morphism $\mathrm{Eval}_{x_l \theta}$ is obviously injective on $\mathbf{E}_k^{(l)}$. So its image has dimension at least $r^2$. But the global dimension of $\mathrm{End}_{\mathbf{F}_l}(\mathbf{K}_l)$ over $\mathbf{F}_l$ is exactly $r^2$. So the evaluation morphism $\mathrm{Eval}_{x_l \theta}$ is surjective as well. $\square$
* $W_{\text{nonpal}}$ is the cartesian product, over the set $J$ of all remaining nontrivial orbits of $\tau$, of the sets of $\mathbf{F}_l$-vector subspaces of $\mathbf{K}_l$.

*Proof.* By what we have done in previous subsections, selfdual codes in $\mathbf{E}_k$ are in bijection with left ideals of the cartesian product

$$ \prod_{l=1}^{n} \mathrm{End}_{\mathbf{F}_l}(\mathbf{K}_l) $$

that are equal to their orthogonal. Besides, the orthogonal of an ideal can be taken component by component, with the care that the orthogonal of the $l$-th component lies in the $\tau(l)$-th component. Therefore, when $\tau(l) = l$, the $l$-th component must be selfdual itself whereas, when $\tau(l) \neq l$, the component at position $l$ can be anything but it determines the component at position $\tau(l)$. Using now the vector space duality, we can further replace ideals of $\mathrm{End}_{\mathbf{F}_l}(\mathbf{K}_l)$ by $\mathbf{F}_l$-subspaces of $\mathbf{K}_l$. This operation preserves the orthogonality condition as the vector space duality commutes with orthogonals.

We finally conclude by noticing that a subspace of $\mathbf{K}_l$ which is equal to its orthogonal is nothing else than an isotropic subspace of half dimension, that is of dimension $r/2$. □

## 3 Counting and generating selfdual skew cyclic codes

We keep the notation introduced before. In particular, we recall that $\mathbf{K}/\mathbf{F}$ is an extension of finite fields of degree $r$ and that $\mathbf{E}_k = \mathbf{K}[X; \theta]/(X^{kr} - 1)$ (where $\theta: x \mapsto x^q$ with $q = \text{Card } \mathbf{F}$). Besides, we set $Y = X^r$ and assume that $k$ is coprime with $r$. Under this hypothesis, the polynomial $Y^k - 1$ is separable and we write down its decomposition as a product of irreducible factors $Y^k - 1 = P_1(Y) \cdots P_n(Y)$. We recall also that we have introduced an involution $\tau: \{1, \dots, n\} \to \{1, \dots, n\}$ defined by the condition that the roots of $P_l$ are the inverses of the roots of $P_{\tau(l)}$. In Subsection 2.2, we proved that we have an isomorphism of the form

$$ \mathbf{E}_k \approx \prod_{l=1}^{s} \mathbf{K}_l[X; \theta]/(X^r - y_l) \approx \prod_{l=1}^{s} \mathrm{End}_{\mathbf{F}_l}(\mathbf{K}_l) $$

where $\mathbf{F}_l = \mathbf{F}[Y]/P_l(Y)$, $\mathbf{K}_l = \mathbf{K} \otimes_{\mathbf{F}} \mathbf{F}_l = \mathbf{K}[Y]/P_l(Y)$ and $y_l$ is the image of $Y$ in $\mathbf{K}_l$. In Subsection 2.3, we showed that this decomposition preserves orthogonality in some precise sense. This allowed us to conclude (see Theorem 2.17) that enumerating selfdual skew cyclic codes sitting in $\mathbf{E}_k$ boils down to enumerating maximal isotropic $\mathbf{F}_l$-vector subspaces of $\mathbf{K}_l$ when $\tau(l) = l$ (palindromic case), and to enumerating $\mathbf{F}_l$-vector subspaces of $\mathbf{K}_l$ otherwise.

In this section, we rely on this theoretical result, first, to count skew cyclic codes and, second, to construct them explicitely. More precisely, we shall address two different problems: that of random generation and that of complete enumeration.

Throughout this section, we assume that the characteristic of $\mathbf{F}$ is odd.
Moreover we get:

**Corollary 17** There is an isomorphism $\mathbf{E}_k \cong \prod_{1 \le l \le n} \mathrm{Mat}_{\mathbf{F}_l, r \times r}$.

**Remark 18** To realize the evaluation isomorphism $\mathcal{J}_l$, a fast computation of preimages of the norm is needed. One possible method consists in finding an irreducible factor of the skew polynomial $X^r - y_l$ in $K_l[X; \theta]$. It is described in [CL17].

**Remark 19** The evaluation isomorphism $\mathcal{J}_l$ is unique up to conjugation by an element of norm 1, i.e. up to another choice of $x_l$ as preimage for $y_l$.

## 5.3 Adjunction on $\mathbf{E}_k$

We will now equip $\mathbf{E}_k$ with a nondegenerate bilinear form for which orthogonal left-ideals are mapped via $\lambda$ to orthogonal vector spaces. We begin by defining the corresponding adjunction on $\mathbf{E}_k$. We start from the following $\mathbf{F}$-linear automorphism on $\mathbf{K}[X^{\pm 1}; \theta]$

$$ \mathbf{K}[X^{\pm 1}; \theta] \xrightarrow{\ast} \mathbf{K}[X^{\pm 1}; \theta] \qquad (5.6) \\ \sum_i f_i X^i \mapsto \sum_i X^{-i} f_i $$

By linearity one checks on monomials that it is an anti-automorphism:

$$ (f_i X^i g_j X^j)^* = (f_i \theta^i(g_j) X^{i+j})^* = X^{-(i+j)} f_i \theta^i(g_j) = X^{-j} g_j X^{-i} f_i = (g_j X^j)^* (f_i X^i)^* $$

**Definition 20** We define the *adjunction* on $\mathbf{E}_k$ as the automorphism of $\mathbf{E}_k$ induced by the composition of the adjunction on $\mathbf{K}[X^{\pm 1}; \theta]$ with the projection on $\mathbf{E}_k$.

$$ \mathbf{E}_k \xrightarrow{\ast} \mathbf{E}_k \qquad (5.7) \\ \sum_i f_i \overline{X^i} \mapsto \sum_i \overline{X^{-i}} f_i $$

This definition is licit because the adjunction maps the two-sided ideal $(X^{rk} - 1)$ on itself. Indeed $(X^{rk} - 1)^*$ is equal to the two-sided ideal $(X^{rk*} - 1)$ i.e. $-X^{-rk}(X^{rk} - 1)$ i.e. $(X^{rk} - 1)$. We also notice that the adjunction of $\mathbf{E}_k$, as quotient map of an anti-automorphism, is an anti-automorphism. So it maps the left ideals of $\mathbf{E}_k$ to its right ideals.
## 3.1 Existence criterion

By Theorem 2.17, there exist selfdual codes in $E_k$ if and only if for each $l$ such that $\tau(l) = l$, the space $K_l$ admits a totally isotropic subspace of dimension $s := r/2$. We then aim at providing simpler conditions for this property to hold. For this, we shall use Witt's decomposition theorem as a fundamental tool. Let us recall it briefly. Let $F$ be a field of odd characteristic, and let $\sigma: F \to F$ be a ring homomorphism which is an involution (possibly the identity). Let $V$ be a finite dimension vector space over $F$, endowed with a $\sigma$-sesquilinear form $\mathcal{B}: V \times V \to F$. We recall that a hyperbolic pair is a pair of vectors $(u, v)$ of $V$ satisfying $\mathcal{B}(u, u) = 0$, $\mathcal{B}(v, v) = 0$ and $\mathcal{B}(u, v) = 1$, and that the 2-dimensional subspace of $V$ spanned by a hyperbolic pair $(u, v)$ is called a hyperbolic plane.

**Theorem 3.1** Keeping the previous notation, there exists an invariant $d$ (called the Witt index of $V$) and hyperbolic planes $H_1, \dots, H_d$ such that one has the orthogonal decomposition

$$V \simeq \left( \bigoplus_{1 \le i \le d} H_i \right) \oplus W$$

where $W$ is a subspace that does not contain any nonzero isotropic vector.

Moreover, the dimension of any maximal isotropic space is equal to $d$.

*Proof.* See for instance [Art11, Theorem 3.11]. □

When $F$ is a finite field, more can be said. For simplicity, we assume that $\dim V = 2s$. If $\sigma \neq \text{id}$, the Witt index of $V$ is always $s$. On the contrary, when $\sigma = \text{id}$, it can be either $s$ or $s-1$ but we can decide between those two values by looking at the discriminant $\delta_V$ of $V$ (defined as the determinant of the matrix of $\mathcal{B}$ in some basis); precisely, the Witt index is $s$ if and only if $(-1)^s \delta_V$ is a square in $F^\times$. (See [Sch85, Theorem 3.3] for more details.)

In our case, Theorem 2.17 tells us that we are looking for isotropic vectors of dimension $s$ in $K_l$; we recall from Equation (2.3) that the latter is endowed with the sesquilinear form

$$(\kappa, \rho)_{F_l} = \mathrm{Trace}_{K_l/F_l}(\zeta_l \cdot \kappa \cdot \sigma_{\tau(l)}(\rho))$$

where $\sigma_{\tau(l)}: K_{\tau(l)} \to K_l$ is the map induced by $\sigma_{\tau(l)}(Y) = \frac{1}{Y}$ and $\zeta_l$ is an element of $K_l$ defined in Lemma 2.11. We then need to compute the discriminant $\delta_{\zeta_l}$ of this sesquilinear form.

**Lemma 3.2** We assume that $\sigma_l = \text{id}$ and we let $\delta_{K_l/F_l}$ be the discriminant of the extension $K_l/F_l$ (which is, by definition, the discriminant of the bilinear form $(\kappa, \rho) \mapsto \mathrm{Trace}_{K_l/F_l}(\kappa\rho)$). Then

1. the discriminant $\delta_{\zeta_l}$ is equal to $\mathrm{Norm}_{K_l/F_l}(\zeta_l) \cdot \delta_{K_l/F_l}$,

2. the discriminant $\delta_{K_l/F_l}$ is a square in $F_l$ if and only if the degree of the extension $[F_l : F]$ is even,

3. if $y_l = 1$ (resp. $y_l = -1$), $\mathrm{Norm}_{K_l/F_l}(\zeta_l)$ is a square (resp. is not a square) in $F_l$.

*Proof.* 1. We fix a basis of $K_l$ over $F_l$ and write $\mathrm{Mat}(\zeta_l)$ for the matrix representing the multiplication by $\zeta_l$ in this basis. Then $\delta_{\zeta_l} = \det(\mathrm{Mat}(\zeta_l)^{\mathrm{tr}}) \cdot \delta_{K_l/F_l} = \mathrm{Norm}_{K_l/F_l}(\zeta_l) \cdot \delta_{K_l/F_l}$.
We now define a nondegenerate bilinear form corresponding to this adjunction.

**Definition 21** The reduced trace bilinear form on $\mathbb{E}_k$ is the bilinear map sending $f$ and $g$ in $\mathbb{E}_k$ to $\text{Trace}_{K/F}((fg^*)(1))$ in $\mathbb{F}$.

The licitness of this definition is readily seen. It does not depend on the choice of representatives in $\mathbb{K}[X^{\pm 1}; \theta]$. It is readily seen that the adjunction $f \mapsto f^*$ satisfies the adjunction characterisation relative to the reduced trace bilinear form. Indeed for any $f,g,h$ in $\mathbb{E}_k$, we have:

$$ \text{Trace}_{K/F}((f(hg^*)(1)) = \text{Trace}_{K/F}((fg^*h^*)(1)) = \text{Trace}_{K/F}(((h^*f)g^*)(1)) $$

**Proposition 22** For a left ideal $I$ of $\mathbb{E}_k$, we have $\lambda(I^{\perp}) = \lambda(I)^{\perp}$.

*Proof.* Let $I$ be a left ideal of $\mathbb{E}_k$. An element $g$ of $\mathbb{E}_k$ is orthogonal to $I$ if and only if we have: $\text{Trace}_{K/F}((fg^*)(1)) = 0$ for all elements $f \in I$. By $K$-linearity, this holds if and only if we have $\text{Trace}_{K/F}((\kappa fg^*)(1)) = 0$ for all elements $\kappa \in K$ and all elements $f \in I$. By non-degeneration of $\text{Trace}_{K/F}$, the condition becomes $(fg^*)(1) = 0$ for all elements $f \in I$. This in turn is true if and only if: $(\sum_{0 \le i < kr} \lambda(f)_i X^i X^{kr-i} \lambda(g)_{(kr-(kr-i))})(1) = 0$ for all elements $f \in I$ since $g^* = \sum_{0 \le i < kr} X^i g_{kr-i}$. Finally we obtain the orthogonality condition for the coordinatewise bilinear form on $\mathbb{K}^{rk}: \sum_{0 \le i < kr} \lambda(f)_i \lambda(g)_i = 0$ for all elements $f \in I$. $\square$

We work with the reduced trace bilinear form rather than the coordinatewise bilinear form, so that we can induce corresponding reduced trace bilinear forms on the $\mathbb{F}_l$-algebras $\mathbb{E}_k^{(l)}$. We now describe them.

**Definition 23** We say that a polynomial is *palindromic* if the set of its roots in an algebraic closure does not contain zero and is stable under the inversion map $x \mapsto \frac{1}{x}$.

**Definition 24** Fixing $y_l$, a primitive element in $\mathbb{F}_l \simeq \mathbb{F}[Y]/(P_l(Y))$, we define the *involution* $\tau$ on the index set $\{1, \dots, n\}$ of the chinese remainder decomposition, $F[Y]/(Y^k - 1) \xrightarrow{\sim} \prod_{1 \le l \le n} F[Y]/(P_l(Y))$, by the relation $P_{\tau(l)}(\frac{1}{y_l}) = 0$.

As the polynomial $Y^k - 1$ is palindromic, the index $\tau(l)$ exists, and $\tau$ is obviously involutive. On the other hand, we can define an involutive $\mathbb{F}$-linear automorphism $\sigma$ on the ring
2. From $K_l = K \otimes_F F_l$, we deduce that $\delta_{K_l/F_l} = \delta_{K/F} \in F$. Moreover, we know that $\delta_{K/F}$ is a square in $F$ if and only if the Galois group of $K/F$ is a subgroup of the alternating group (see [Mil20, Corollary 4.2]), which never occurs in our situation given that Gal$(K/F)$ is a cyclic group of even cardinality. We conclude that $\delta_{K/F}$ is a square in $F_l$ if and only if the extension $F_l/F$ has even degree.

3. We assume that $y_l = \pm 1$ and compute

$$ \operatorname{Norm}_{K_l/F_l}(\zeta_l)^{\frac{q-1}{2}} = \left( \zeta_l^{\sum_{0 \le i < 2s} q^i} \right)^{\frac{q-1}{2}} \\ = (\zeta_l^{q-1})^{\frac{\sum_{0 \le i < 2s} q^i}{2}} = (x_l \sigma_l(x_l))^{\frac{\sum_{0 \le i < 2s} q^i}{2}} $$

As $y_l = \pm 1$, the automorphism $\sigma_l$ is the identity and so $\operatorname{Norm}_{K_l/F_l}(\zeta_l)^{\frac{q-1}{2}} = y_l$. We conclude by applying Euler's criterion. $\square$

**Corollary 3.3** We assume that the characteristic of $F$ is odd.

1. If $k$ is even, there are no selfdual skew cyclic codes in $E_k$.

2. If $k$ is odd, there exist selfdual skew cyclic codes in $E_k$ if and only if $(-1)^s$ is not a square in $F$, if and only if $s$ is odd and $q \equiv 3 \pmod 4$.

*Proof.* We first notice that, whenever $y_l \ne \pm 1$, there is no obstruction to the existence of an isotropic subspace of half dimension. On the contrary, when $y_l = 1$ (resp. $y_l = -1$), it follows from Lemma 3.2 that an isotropic subspace of $K$ of dimension $s$ exists if and only if $(-1)^s$ is a square (resp. is not a square) in $F$.

When $k$ is even, the decomposition of $E_k$ exhibits both factors $K[X; \theta]/(X^r+1)$ and $K[X; \theta]/(X^r-1)$. Since $(-1)^s$ cannot be simultaneously a square and a nonsquare, we conclude that selfdual skew cyclic codes cannot exist in this case. On the contrary, when $k$ is odd, the factor $K[X; \theta]/(X^r+1)$ does not show up and we are left to the condition corresponding to $y_l = 1$.

Finally, the fact that if $(-1)^s$ is not a square in $F$ if and only if $s$ is odd and $q \equiv 3 \pmod 4$ is a direct application of Euler's criterion. $\square$

## 3.2 Counting selfdual skew cyclic codes

We now aim at counting the number of selfdual codes sitting in $E_k$, when they exist. In what follows, we then assume that the existence criterion of Corollary 3.3 is fulfilled. It follows from Theorem 2.17 that out task reduces to finding the cardinality of $W_{\text{pal}}$ and $W_{\text{nonpal}}$.

### 3.2.1 The nonpalindromic case

We start by the nonpalindromic case, which is by far the easiest. For this counting, we will use $q$-analogues of integers. We recall briefly that the $q$-analogue of $n \in \mathbb{N}$ is, by definition, $[n]_q := 1 + q + q^2 + \dots + q^{n-1}$. The $q$-factorial of $n$ is defined by $[n]_q! = [1]_q[2]_q \dots [n]_q$ and we set

$$ \begin{bmatrix} n \\ k \end{bmatrix}_q := \frac{[n]_q!}{[k]_q![n-k]_q!} = \frac{(1-q^n)(1-q^{n-1})\dots(1-q^{n-k+1})}{(1-q)(1-q^2)\dots(1-q^k)} $$
where $n$ and $k$ are nonnegative integers with $k \le n$. It is a classical fact that the $q$-binomial coefficients count the number of $\mathbb{F}_q$-vector subspaces of dimension $k$ in the ambient $\mathbb{F}_q$-vector space $\mathbb{F}_q^n$.

Therefore, with the notation of Theorem 2.17, we have

$$ \mathrm{Card}(W_{\mathrm{nonpal}}) = \prod_{\{l, \tau(l)\} \in J} \left( \sum_{k=0}^{r} \begin{bmatrix} r \\ k \end{bmatrix}_{q_l} \right). \qquad (3.1) $$

### 3.2.2 The palindromic case

If $V$ is a finite dimensional vector space equipped with a sesquilinear form, we denote by $\mathrm{Iso}(V)$ the number of isotropic subspaces of $V$ of half dimension. It turns out that the behaviour of $\mathrm{Iso}(V)$ have been studied for a long time (see for instance [Seg59, Ple65, BBB20]) and that explicit formulas are known. Those are called Segre's formulas and are recalled in the following theorem.

**Theorem 3.4** Let $F$ be a finite field of odd characteristic and cardinality $q_F$ and let $\sigma: F \to F$ be an involutive ring automorphism. Let $V$ be a $F$-vector space of dimension $2s$ equipped with a nondegenerate $\sigma$-sesquilinear form, whose Witt index is $s$. Then:

1. if $\sigma = \mathrm{id}$ (Euclidean case), then $\mathrm{Iso}(V) = \prod_{i=0}^{s-1} (q_F^i + 1)$,

2. if $\sigma \neq \mathrm{id}$ (Hermitian case), then $\mathrm{Iso}(V) = \prod_{i=0}^{s-1} (q_F^{i+1/2} + 1)$.

*Proof.* We recall briefly the idea of the proof as it will be useful afterwards. Let $\mathrm{iso}(W)$ be the number of isotropic vectors in a Euclidean or Hermitian vector space $W$ over $F$. We claim that, if $W$ has dimension $2d$ and Witt index $d$, then

1. if $\sigma = \mathrm{id}$ (Euclidean case), then $\mathrm{iso}(W) = (q_F^d - 1)(q_F^{d-1} + 1)$,

2. if $\sigma \neq \mathrm{id}$ (Hermitian case), then $\mathrm{iso}(W) = (q_F^d - 1)(q_F^{d-1/2} + 1)$

Indeed, let us fix an isotropic basis $((u_i)_{0 \le i < s}, (v_i)_{0 \le i < s})$ corresponding to the Witt's decomposition of $W$ (see Theorem 3.1) and let $((a_i)_{0 \le i < s}, (b_i)_{0 \le i < s})$ be the coordinates in this basis of a vector. In the Euclidean case, the fact that this vector is isotropic reduces to the equation $\sum_{0 \le i < s} a_i b_i = 0$. Now, fixing a nonzero vector $(a_i)_{0 \le i < s} \in \mathbf{F}_l^s$, this occurs if and only if $(b_i)_{0 \le i < s}$ lies in some hyperplane. We thus have $(q_F^s - 1)q_F^{s-1}$ solutions corresponding to nonzero $(a_i)_{0 \le i < s}$, to which one should add $(q_F^s - 1)$ more solutions when all $a_i$ vanish. Finally, we get $\mathrm{iso}(W) = (q_F^d - 1)(q_F^{d-1} + 1)$ as claimed.

The Hermitian case is similar, expect that the equation to solve is now $\sum_{0 \le i < s} \sigma_l(a_i)b_i + \sum a_i\sigma_l(b_i) = 0$, which reduces to $\sum_{0 \le i < s} a_i\sigma_l(b_i) = \alpha$ where $\alpha$ satisfies $\sigma_l(\alpha) = -\alpha$. We conclude repeating the argument of the Euclidean case and using that there are exactly $q_F^{1/2}$ values for $\alpha$.

We are now ready to prove Segre's formula. We start by taking $W_1 = V$ and by picking an isotropic vector $u_1$ in $W$. This corresponds to $\mathrm{iso}(W_1)$ possibilities. Once this is achieved, we set $W_2 := (Fu_1)^\perp/Fu_1$. This is a space of dimension $2(s-1)$, whose Witt index is $s-1$. Therefore, we can apply again our claim and find that there are exactly $\mathrm{iso}(W_2)$ isotropic vectors in $W_2$. We choose one of them, that we denote by $u_2$. Now we repeat the argument until we reach $u_s$. This corresponds
algebra $\mathbf{E}_k^{(l)}$:

$$
\begin{tikzcd}
& & \sum_{0 \le i < r} \sum_{0 \le j_i < \deg P_l} f_i X^{i+rj_i} \arrow[r, "\cong"] & \sum_{0 \le i < r} \sum_{0 \le j_i < \deg P_l} X^{r(k-j_i)-i} f_i \\
& & \arrow[u, "\ell"] & \arrow[u, "\ell"] \\
& & \left( \sum_{0 \le i < r} \sum_{0 \le j_i < \deg P_l} f_i \otimes_{\mathbf{F}} 1 X^{i+rj_i} (P_l(X^r)) \right)_l & \left( \sum_{0 \le i < r} \sum_{0 \le j_i < \deg P_l} X^{-i} f_i \otimes_{\mathbf{F}} y_{\tau(l)}^{-j_i} (P_{\tau(l)}(X^r)) \right)_l \\
& & \arrow[dl, "\|"'] & \arrow[dl, "\|"'] \\
& & \left( \sum_{0 \le i < r} \sum_{0 \le j_i < \deg P_l} f_i \otimes_{\mathbf{F}} y_l^{j_i} X^i (P_l(X^r)) \right)_l & \left( \sum_{0 \le i < r} \sum_{0 \le j_i < \deg P_l} X^{-i} (Id \otimes \sigma_l)(f_i \otimes_{\mathbf{F}} y_l^{j_i}) (P_{\tau(l)}(X^r)) \right)_l
\arrow[r, "\cong"] & \arrow[dl, "\|"'] \arrow[dl, "\|"']
\end{tikzcd}
\qquad (5.10)
$$

□

Having defined the adjunction on $\mathbf{E}_k^{(l)}$, we now determine its transformation under the evaluation isomorphism $\mathcal{J}_l$. We define the automorphism $\mathcal{Z}_l$ by:

$$
\begin{equation} \tag{5.11}
\begin{split}
\mathcal{Z}_l : \quad \mathbf{E}_{k,l} &\xrightarrow{\sim} \mathbf{E}_{k,l} \\
X &\mapsto x_l.(\mathrm{Id} \otimes \sigma_{\tau(l)})(x_{\tau(l)}).X
\end{split}
\end{equation}
$$

In order to make the diagram 5.13 commutative, we have to twist the adjunction * on the target side into an adjunction $x \mapsto x^\bullet := \mathcal{Z}_l(x^\bullet)$ using the additional automorphism $\mathcal{Z}_l$, so that we have:

$$
\mathrm{Trace}(\mathcal{J}_l(\mathbf{E}_k^{(l)}) f) \mathcal{J}_{\tau(l)}((\mathbf{E}_k^{(\tau(l))}) g)^*(1)) = 0 \iff \mathrm{Trace}(\mathbf{E}_{k,l} \mathcal{J}_l(f)) (\mathbf{E}_{k,\tau(l)} \mathcal{J}_{\tau(l)}(g))^*(1) = 0
$$

where $\mathbf{E}_{k,l}$ denotes the central semi-simple algebra: $\mathbf{K}_l[X^{\pm 1}; \theta]/(X^r - 1)$

**Lemma 28** The automorphism of $\mathbf{E}_{k,l}$, $\mathcal{Z}_l: X \mapsto x_l.(\mathrm{Id} \otimes \sigma_{\tau(l)})(x_{\tau(l)}).X$, is the conjugation with respect to an explicit element $\zeta_l$ of $\mathbf{K}_l$

*Proof.* The norm of $x_l(\mathrm{Id} \otimes \sigma_{\tau(l)})(x_{\tau(l)})$ is equal to

$$
\mathrm{Norm}_{\mathbf{K}_l/\mathbf{F}_l}(x_l)(\mathrm{Id} \otimes \sigma_{\tau(l)})(\mathrm{Norm}_{\mathbf{K}_{\tau(l)}/\mathbf{F}_{\tau(l)}}(x_{\tau(l)})) = y_l(\mathrm{Id} \otimes \sigma_{\tau(l)})(y_{\tau(l)}) = 1
$$

Hence the automorphism of $\mathbf{K}[X^{\pm 1}; \theta]$: $X \mapsto x_l.(\mathrm{Id} \otimes \sigma_{\tau(l)})(x_{\tau(l)}).X$ is well defined in
to iso($W_1$) · iso($W_2$) · · · iso($W_s$) choices. However, each of them corresponds $q_F \cdot q_F^2 \cdot \dots \cdot q_F^{s-1} = q_F^{s(s-1)/2}$ choices of families of vecteurs of V since $u_i$ has $q^i$ preimages in V. We conclude that the number of bases of a maximal isotropic subspace of V is equal to $q_F^{s(s-1)/2} \cdot \text{iso}(W_1) \cdot \text{iso}(W_2) \cdots \text{iso}(W_s)$. We finally obtain $\text{Iso}(V)$ by dividing by the cardinality of $\text{GL}_s(F)$. □

**Remark 3.5** In the Euclidean case, one can alternatively prove Segre's formula by remarking that the orthogonal group of V acts transitively on the set of maximal isotropic subspaces and that the stabilizer of a given maximal isotropic subspace U can be presented as a semi-direct product of GL(U) and the group of antisymmetric linear applications from U to its dual Hom$_F(U, F)$. From this description we find that the number of maximal isotropic subspaces is

$$ \frac{\text{Card}(O_{2s}(F))}{q_F^{s(s-1)/2} \cdot \text{Card}(\text{GL}_s(F))} $$

a formula from which one can eventually derive Segre's theorem. A similar approach also works in the Hermitian case.

Keeping the notation of Theorem 2.17, it follows from Theorem 3.4 that

$$ \text{Card}(W_{\text{pal}}) = \prod_{l \in I} \prod_{i=0}^{s-1} (q_l^i + 1) \times \prod_{y_l \neq \pm 1} \prod_{l \in I} \prod_{i=0}^{s-1} (q_l^{i+1/2} + 1). \quad (3.2) $$

We notice moreover that there is always exactly one index $l$ for which $y_l = 1$, and there is at most one index $l$ such that $y_l = -1$ (such an index actually exists if and only if $k$ is even). In both cases, the corresponding field $\mathbb{F}_l$ is $\mathbb{F}$, and so $q_l = q$.

Now combining Equations (3.1) and (3.2), we get the number of selfdual skew cyclic codes sitting in $\mathbb{E}_k$, which proves Theorem 1.2.

**Example 3.6** For $\mathbb{K} = \mathbb{F}_{q^{2s}}$ and $\theta : x \mapsto x^q$, the number of selfdual skew cyclic codes is equivalent to $q^{\frac{s(s-1)}{2}}$ as $s$ grows to infinity, whereas the number of skew cyclic codes (number of $s$ dimensional $\mathbb{F}_q$-vector subspaces of $\mathbb{F}_{q^{2s}}$) is equivalent to $q^{s^2}$ as $s$ grows to infinity.

For example, for $\mathbb{K} = \mathbb{F}_{3^6}$ and $\theta : x \mapsto x^3$, the number of selfdual skew cyclic codes in $\mathbb{E}_1 = \mathbb{K}[X; \theta]/(X^6 - 1)$ is 80 among 33880 skew cyclic codes, whereas for $\mathbb{K} = \mathbb{F}_{3^{18}}$ and $\theta : x \mapsto x^3$, the number of selfdual skew cyclic codes in $\mathbb{E}_1 = \mathbb{K}[X; \theta]/(X^{18} - 1)$ is 469740602936729600 among 791614563787525746761491781638123230424 skew cyclic codes.

**Remark 3.7** As we noticed at the end of subsection 2.1, there exist no selfdual skew cyclic codes at all in the case $r$ odd. This is in particular the case for $r = 1$, when skew cyclic codes reduce to cyclic codes. On the contrary, for $s = 1$ and $q = 3$, we achieve the best ratio of selfdual skew cyclic codes over skew cyclic codes, which is $\frac{1}{2}$. Nevertheless, the proportion of selfdual skew cyclic codes over skew cyclic codes decreases as fast as $O(q^{-\frac{s^2+s}{2}})$ as $s$ grows larger.
$\mathbf{E}_{k,l}$. The Hilbert 90 theorem guarantees the existence of an element $\zeta_l$ of $\mathbf{K}_l$ such that:
$$ \theta(\zeta_l) = x_l(\mathrm{Id} \otimes \sigma_{\tau(l)})(x_{\tau(l)})\zeta_l. \text{ We have } x_l(\mathrm{Id} \otimes \sigma_{\tau(l)})(x_{\tau(l)}).X = \zeta_l^{-1}X\zeta_l. \quad \square $$

**Lemma 29** The element $\zeta_l$ can be chosen invariant by $(\mathrm{Id} \otimes \sigma_l)$ in the palindromic case $(\tau(l) = l)$.

*Proof.* As $(\mathrm{Id} \otimes \sigma_l)(\zeta_l)$ satisfies $\theta((\mathrm{Id} \otimes \sigma_l)(\zeta_l)) = x_l(\mathrm{Id} \otimes \sigma_l)(x_l)(\mathrm{Id} \otimes \sigma_l)(\zeta_l)$, we can take, $\zeta_l + (\mathrm{Id} \otimes \sigma_l)(\zeta_l)$. In the special case where $\zeta_l + (\mathrm{Id} \otimes \sigma_l)(\zeta_l)$ is equal to zero, obviously $\mathrm{Id} \otimes \sigma_l$ is not trivial and we are in the Hermitian case where $y_l \neq \pm 1$. As $\frac{\zeta_l}{y_l}$ satisfies also $\theta(\frac{\zeta_l}{y_l}) = x_l(\mathrm{Id} \otimes \sigma_{\tau(l)})(x_{\tau(l)})\frac{\zeta_l}{y_l}$, we can thus take $\frac{\zeta_l}{y_l} + (\mathrm{Id} \otimes \sigma_l)(\frac{\zeta_l}{y_l}) = \zeta_l(\frac{1}{y_l} - y_l)$, which is nonzero in this case. $\square$

**Remark 30** The element $\zeta_l$ can be efficiently computed using the cohomological formula in the proof of the Hilbert 90 theorem. It is the inverse of any nonzero element in the image of the endomorphism: $\sum_{0 \le i < r} \prod_{0 \le j < i} \theta^j(x_l(\mathrm{Id} \otimes \sigma_{\tau(l)})(x_{\tau(l)}))\theta^i$, as one can readily check.

**Definition 31** We define the *involutive anti-isomorphism* $\bullet$ from each $\mathbf{E}_{k,l}$ into $\mathbf{E}_{k,\tau(l)}$ by com-
posing $*$ with $\mathcal{Z}_l$.

$$
\begin{equation} \tag{5.12}
\begin{aligned}
\mathcal{Z}_l \circ * : \quad & \mathbf{E}_{k,l} \xrightarrow{\bullet} \mathbf{E}_{k,\tau(l)} \\
& f = \sum_i f_i X^i \quad \mapsto \quad f^* = \zeta_{\tau(l)}^{-1} \sum_i X^{-i} (\mathrm{Id} \otimes \sigma_l)(f_i) \zeta_{\tau(l)}
\end{aligned}
\end{equation}
$$

**Proposition 32** The following diagram commutes:

$$
\begin{tikzcd}[column sep=2.8em, row sep=2.8em]
    \bigcap_{1 \le l \le n} \mathbf{E}_k^{(l)} \arrow[r, "\cong", "\mathbf{E}_k"] & \mathbf{E}_k \arrow[r, "*", "\cong"] & \bigcap_{1 \le l \le n} \mathbf{E}_k^{(\tau(l))} \arrow[r, "\cong", "\mathbf{E}_k"] \\
    \bigcap_{1 \le l \le n} \mathbf{E}_k^{(l)} \arrow[r, "\bullet", "\cong"] & \bigcap_{1 \le l \le n} \mathbf{E}_{k,\tau(l)} \arrow[r, "\cong", "\mathbf{E}_{k,\tau(l)}"] & \bigcap_{1 \le l \le n} \mathbf{E}_k^{(\tau(l))} \arrow[r, "\cong", "\mathbf{E}_k"] \\
    \bigcap_{1 \le l \le n} \mathbf{E}_k^{(l)} \arrow[r, "\cong", "\mathbf{E}_k"] & \bigcap_{1 \le l \le n} \mathbf{E}_k^{(\tau(l))} \arrow[r, "\cong", "\mathbf{E}_k"] & \bigcap_{1 \le l \le n} \mathbf{E}_k^{(\tau(l))} \arrow[r, "\cong", "\mathbf{E}_k"] \\
    \bigcap_{1 \le l \le n} \mathbf{E}_k^{(l)} \arrow[r, "\cong", "\mathbf{E}_k"] & \bigcap_{1 \le l \le n} \mathbf{E}_k^{(\tau(l))} \arrow[r, "\cong", "\mathbf{E}_k"] & \bigcap_{1 \le l \le n} \mathbf{E}_k^{(\tau(l))} \arrow[r, "\cong", "\mathbf{E}_k"]
\end{tikzcd}
\qquad (5.13)
$$

*Proof.* By additivity, it suffices to check the commutativity on monomials $\kappa X^i$. On one hand, we have: $(\kappa X^i)^* = X^{-i}(\mathrm{Id} \otimes \sigma_{\tau(l)})(\kappa)$. The evaluation isomorphism $\mathcal{J}_l$ maps the right hand side to

$$
X^{-i}(\mathrm{Id} \otimes \sigma_{\tau(l)})(\kappa) \left( \prod_{0 \le t < i} \theta^t(x_l) \right)^{-1} \qquad (5.14)
$$
## 3.3 Random generation of selfdual skew cyclic codes

Since the number of selfdual skew cyclic codes grows exponentially fast with respect to the dimension $r$, an algorithm outputting in one shot the complete list of these codes would be necessarily very unefficient (the better we can expect is exponential complexity) and hence, probably not quite useful. Instead, in what follows, we address a different question, which is that of random generation: we aim at finding a fast algorithm that outputs a unique code in this huge list with the guarantee that the returned code is uniformly distributed among all of them. Such an algorithm could be very useful to generate typical selfdual skew cyclic codes and to check their properties.

### 3.3.1 From skew cyclic codes to finite geometry: explicit methods

Before designing our algorithms, we need to explain how we represent the objects on the computer. We recall that a skew cyclic code is, by definition, a left ideal of $E_k = K[X; \theta]/(X^{kr} - 1)$. Hence it necessarily has the form $E_k f$ for some $f \in K[X; \theta]$. We can further normalize this generator by requiring that it is monic and has minimal degree; concretely, normalizing the generator $f$ amounts to replacing it by $rgcd(f, X^{kr} - 1)$ (where $rgcd$ denotes the right gcd). The same discussion applies similarly to all quotients of a Ore polynomial ring by a two-sided ideal and so, in particular, to $K[X; \theta]/P_l(Y)$ and the algebras $\tilde{E}_k^{(l)} = K_l[X; \theta]/(X^r - y_l)$.

We recall further that we have the following sequence of isomorphisms:

$$ E_k \approx \prod_{l=1}^{n} K[X; \theta]/P_l(Y) \approx \prod_{l=1}^{n} \tilde{E}_k^{(l)} \approx \prod_{l=1}^{n} \mathrm{End}_{\mathbb{F}_l}(K_l) $$

and that the left ideals of $\mathrm{End}_{\mathbb{F}_l}(K_l)$ are in one-to-one correspondence with the $\mathbb{F}_l$-linear subspaces of $K_l$ (see Subsection 2.4). We aim at making explicit all these identifications.

Going back and forth between $E_k$ and $\prod_{l=1}^n \tilde{E}_k$ is not difficult. Indeed, if a code sitting in $E_k$ is generated by $f$, its image in $E_k$ will be generated by $f$ as well. Conversely, if one starts with a family of codes $(\tilde{E}_k^{(l)})_{1 \le l \le n}$, its preimage in $E_k$ is the code generated by a Ore polynomial $f$ satisfying the set of congruences

$$ f \equiv f_l \pmod{P_l(Y)} \quad (1 \le l \le n). \qquad (3.3) $$

We need to be careful however that $f_l$ has a priori coefficients in $K_l$; in order to view it as a Ore polynomial in $K[X; \theta]$, we have to replace each occurrence of $y_l$ by $Y = X^r$. The system of congruences (3.3) can then be solved using the Chinese Remainder Theorem; we underline that noncommutativity is not an issue here because all the moduli $P_l(Y)$ lie in the center. We also stress that the solution $f$ to (3.3) is in general not normalized, even if the $f_l$ are; if one wants to normalize it, one needs to compute an additional $rgcd$.

We now explain how to navigate between $\tilde{E}_k^{(l)}$ and $\mathrm{End}_{\mathbb{F}_l}(K_l)$. We first recall that the isomorphism between those two rings is given by $X \mapsto x_i\theta$. Hence the ideal of $\mathrm{End}_{\mathbb{F}_l}(K_l)$ that corresponds to the ideal $\tilde{E}_k^{(l)}f$ of $\tilde{E}_k^{(l)}$ is the ideal consisting on linear maps vanishing on the kernel of $f(x_i\theta)$. The associated $\mathbb{F}_l$-linear subspace of $K_l$ is then just $\ker f(x_i\theta)$. The correspondence in the other direction is also given
On the other hand, it maps the left hand side to $\kappa \prod_{0 \le t < i} \theta^t(x_t) X^i$, whose adjoint is:

$$ (x_l(\mathrm{Id} \otimes \sigma_{\tau(l)})(x_{\tau(l)})X)^{-i}(\mathrm{Id} \otimes \sigma_{\tau(l)})(\kappa \prod_{0 \le t < i} \theta^t(x_{\tau(l)})) \quad (5.15) $$

Both terms 5.15 and 5.14 coincide. □

**Definition 33** We define the involutive isomorphism $\bullet$ from $End_{\mathbb{F}_l}(\mathbf{K}_l)$ into $End_{\mathbb{F}_{\tau(l)}}(\mathbf{K}_{\tau(l)})$ by:

$$ \bullet: \quad \mathrm{End}_{\mathbb{F}_l}(\mathbf{K}_l) \xrightarrow{\bullet} \mathrm{End}_{\mathbb{F}_{\tau(l)}}(\mathbf{K}_{\tau(l)}) \quad (5.16) $$

$$ f = \sum_{0 \le i < r} f_i \theta^i \quad \mapsto \quad f^\bullet = \zeta_l^{-1} \sum_{0 \le i < r} \theta^{-i}((\mathrm{Id} \otimes \sigma_{\tau(l)})(f_i)) \theta^{-i} \zeta_l $$

**Definition 34** We define the corresponding trace form over the product of the $\mathbb{F}_l$-linear vector space $\mathbf{K}_l$ with the $\mathbb{F}_{\tau(l)}$-linear vector space $\mathbf{K}_{\tau(l)}$, by:

$$ (\kappa, \rho)_{\mathbb{F}_l} := \mathrm{Trace}_{\mathbb{K} \otimes_{\mathbb{F}} \mathbb{F}_l / \mathbb{F}_l} (\zeta_l \cdot \kappa \cdot (\mathrm{Id} \otimes \sigma_{\tau(l)})(\rho)) $$

**Remark 35** We notice that this trace form is bilinear in the nonpalindromic and in the Euclidean (for $y_l = \pm 1$) palindromic case and sesquilinear in the Hermitian (for $y_l \ne \pm 1$) palindromic case.

**Proposition 36** The involutive isomorphism $\bullet$ is the adjunction relative to the trace bilinear form defined in 34.

*Proof.* We have to check the adjunction characterisation. For any element $f := \sum_{0 \le i \le r-1} f_i \theta^i \in \mathrm{End}_{\mathbb{F}_l}(\mathbf{K}_l)$, we must have $(\kappa, f(\rho))_{\mathbb{F}_l} = (f^\bullet(\kappa), \rho)_{\mathbb{F}_l}$. By $r$-periodicity of $(\theta^i)_{0 \le i \le r-1}$ and re-indexation $k \mapsto k-i$, we get:

$$ \begin{align} (\kappa, f(\rho))_{\mathbb{F}_l} &= \sum_{0 \le k \le r-1} \theta^k (\zeta_l \kappa (\mathrm{Id} \otimes \sigma_{\tau(l)})(\sum_{0 \le i \le r-1} f_i \theta^i(\rho))) \nonumber \\ (\kappa, f(\rho))_{\mathbb{F}_l} &= \sum_{0 \le k \le r-1} \theta^k \left( \sum_{0 \le i \le r-1} \zeta_l \theta^{-i}((\mathrm{Id} \otimes \sigma_{\tau(l)})(f_i)) \frac{\theta^{-i}(\zeta_l)}{\zeta_l} \theta^{-i}(\kappa) \rho \right) \nonumber \\ (\kappa, f(\rho))_{\mathbb{F}_l} &= \mathrm{Trace}_{\mathbb{K} \otimes_{\mathbb{F}} \mathbb{F}_l / \mathbb{F}_l} (\zeta_l \cdot f^\bullet(\kappa) \rho) \tag{5.17} \end{align} $$

□
by an explicit formula: if $V$ is a $\mathbf{F}_l$-subvector space of $\mathbf{K}_l$ and $(v_1, \dots, v_d)$ is a basis of $V$, a generator of the ideal of $\tilde{\mathbf{E}}_k^{(l)}$ corresponding to $V$ is

$$ \mathrm{llcm} \left( X - \frac{x_l \theta(v_1)}{v_1}, \dots, X - \frac{x_l \theta(v_d)}{v_d} \right) $$

where llcm denotes the left lcm.

The discussion of this subsection is summarized by Algorithm 1 below which computes the normalized generator of the code sitting in $\mathbf{E}_k$ that corresponds to some element of $W_{\mathrm{nonpal}} \times W_{\mathrm{pal}}$ via the bijection of Theorem 2.17. The next subsections are devoted to explain how to produce a random element in (each component of) $W_{\mathrm{nonpal}} \times W_{\mathrm{pal}}$.

<caption>**Algorithm 1:** Explicit bijection with $W_{\mathrm{nonpal}} \times W_{\mathrm{pal}}$</caption>

**Input:** a family $((V_l)_{l \in I}, (V_l)_{\{l, \tau(l)\} \in J}) \in W_{\mathrm{nonpal}} \times W_{\mathrm{pal}}$
**Output:** the normalized generator of the corresponding selfdual skew cyclic code
1: **for** $l \in I$:
2: &nbsp;&nbsp;&nbsp;&nbsp;pick a basis $(v_1, \dots, v_s)$ of $V_l$
3: &nbsp;&nbsp;&nbsp;&nbsp;$f_l \leftarrow \mathrm{llcm}(X - x_l \theta(v_i)/v_i, 1 \le i \le s)$
4: &nbsp;&nbsp;&nbsp;&nbsp;do the substitution $y_l \to X^r$ in $f_l$ &nbsp;&nbsp;&nbsp;&nbsp;/* now $f_l \in \mathbf{K}[X; \theta]$ */
5: &nbsp;&nbsp;&nbsp;&nbsp;$f_l \leftarrow \mathrm{rgcd}(f_l, P_l(Y))$
6: **for** $\{l, \tau(l)\} \in J$:
7: &nbsp;&nbsp;&nbsp;&nbsp;pick a basis $(v_1, \dots, v_d)$ of $V_l$
8: &nbsp;&nbsp;&nbsp;&nbsp;$f_l \leftarrow \mathrm{llcm}(X - x_l \theta(v_i)/v_i, 1 \le i \le d)$
9: &nbsp;&nbsp;&nbsp;&nbsp;do the substitution $y_l \to X^r$ in $f_l$ &nbsp;&nbsp;&nbsp;&nbsp;/* now $f_l \in \mathbf{K}[X; \theta]$ */
10: &nbsp;&nbsp;&nbsp;&nbsp;$f_l \leftarrow \mathrm{rgcd}(f_l, P_l(Y))$
11: &nbsp;&nbsp;&nbsp;&nbsp;define $f_{\tau(l)}$ by the equality $f_l f_{\tau(l)}^* = P_l(Y)$
12: &nbsp;&nbsp;&nbsp;&nbsp;$f_{\tau(l)} \leftarrow \mathrm{rgcd}(f_{\tau(l)}, P_{\tau(l)}(Y))$
13: compute $f$ such that $f \equiv f_l \pmod{P_l(Y)}$ for $1 \le l \le n$
14: **return** $\mathrm{rgcd}(f, X^{rk} - 1)$

To conclude, we record the following proposition which elucidates how duality acts on our representations.

**Proposition 3.8** We set $E = E' = \mathbf{E}_k$ and $P = Y^k - 1$ (resp. $E = \mathbf{E}_k^{(l)}, E' = \mathbf{E}_k^{(\tau(l))}$ and $P = P_l$).

(a) Given $f, g \in K[X; \theta]$, the ideals $Ef$ and $E'g$ are orthogonal if and only if $fg^* = 0$ in $E$.

(b) Given $f \in K[X, \theta]$ dividing $P$, the orthogonal of $Ef$ is the ideal $E'g^*$ where $g$ is defined by $fg = P$.

*Proof.* (a) By nondegeneracy of sesquilinear form $\langle -, - \rangle$, the condition $fg^* = 0$ is equivalent to $gf^* = 0$ and then to $\langle E, gf^* \rangle = 0$. By adjunction relation, the condition becomes $\langle Ef, g \rangle = 0$. Since the adjunction is an isomorphism, the condition is further equivalent to $\langle (E')^* Ef, g \rangle = 0$ and finally to $\langle Ef, E'g \rangle = 0$.

(b) By what precedes, the ideals $Ef$ and $E'g^*$ are orthogonal. We conclude by noticing that $\dim Ef + \dim E'g^* = (\deg P - \deg f) + (\deg P - \deg g) = \deg P$. $\square$

**Remark 3.9** As a corollary, Proposition 3.8 provides a simple criterion to check that the code $\mathbf{E}_k f$ is selfdual: assuming that $f$ is normalized, it is the case if and only if $ff^* = 0$ in $\mathbf{E}_k$ and $\deg f = s$.
Composing both isomorphisms: $X \mapsto x_l X$ and $X \mapsto \theta$, we obtain the following commutative
diagram:

$$
\begin{tikzcd}[column sep=2.8em, row sep=2.8em]
\mathbf{E}_k^{(l)} \arrow[r, "\overline{\mathrm{Eval}}_{x_l X}"] \arrow[d, "f \mapsto f^*"'] & \mathbf{E}_{y_l} := \mathbf{K}_l[X^{\pm 1}; \theta]/(X^r - 1) \arrow[r, "\overline{\mathrm{Eval}}_{\theta}"] \arrow[d, "f \mapsto f^*"'] & \mathbf{K}_l[\theta] \simeq \mathrm{End}_{\mathbf{F}_l}(\mathbf{K}_l) \arrow[d, "f \mapsto f^*"'] \\
\mathbf{E}_{\mathbf{k}}^{(\tau(l))} \arrow[r, "\overline{\mathrm{Eval}}_{x_l X}"] \arrow[d, "f \mapsto f^*"'] & \mathbf{E}_{k, \tau(l)} := \mathbf{K}_{\tau(l)}[X; \theta]/(X^r - 1) \arrow[r, "\overline{\mathrm{Eval}}_{\theta}"] \arrow[d, "f \mapsto f^*"'] & \mathbf{K}_{\tau(l)}[\theta] \simeq \mathrm{End}_{\mathbf{F}_{\tau(l)}}(\mathbf{K}_{\tau(l)})
\end{tikzcd}
\qquad (5.18)
$$

Finally, we state and prove the following product criterion, that will be used first in the proof of the orthogonality preservation of vector space duality and secondly for checking the validity of our symbolic computation of selfdual skew codes in SageMath.

**Proposition 37** Let $E$ be either the algebra $\mathbf{E}_k \times \mathbf{E}_k$, $\mathbf{E}_k^{(l)} \times \mathbf{E}_k^{(\tau(l))}$, $\mathbf{E}_{k,l} \times \mathbf{E}_{k,\tau(l)}$ or $\mathrm{End}_{\mathbf{F}_l}(\mathbf{K}_l) \times \mathrm{End}_{\mathbf{F}_{\tau(l)}}(\mathbf{K}_{\tau(l)})$. Let $[\_, \_]$ be the corresponding trace bilinear form, and $f \mapsto f^*$ the corresponding adjunction. The skew codes generated by $f$ and $g$ in $E$ are orthogonal if and only if we have $fg^* = 0$ in $E$.

*Proof.* By nondegeneration of $[\_, \_]$, $fg^* = 0$ is equivalent to: $[E, fg^*] = 0$ By adjunction relation, the condition becomes: $[gE, f] = 0$ Since the adjunction is an isomorphism, we have: $[gEE^*, f] = 0$ And since $[\_, \_]$ is a trace form: $[gE, fE] = 0$ $\square$

**Corollary 38** With the same notations as in Proposition 37, a skew code of $E$ generated by an element $f \in E$, is selfdual if and only if we have $ff^* = 0$ and $\deg(f) = s$

**Remark 39** The product criterion $f^*g = 0$ is equivalent to $g^*f = 0$ by adjunction. It is also equivalent to $gf^* = 0$ and $fg^* = 0$. Indeed if we have $g^*f = 0$, $fg^*f$ is also equal to zero in $E$ and by left and right divisibility, taking lifts of $f$ and $g$, we obtain: $\tilde{f}\tilde{g}^*\tilde{f} = (X^{rk} - 1)\tilde{f}\tilde{h}\tilde{f}$, for some $\tilde{h}$. So by right Euclidean division by $\tilde{f}$, we get $\tilde{f}\tilde{g}^* = (X^{rk} - 1)\tilde{f}\tilde{h}$, which implies $fg^* = 0$ in $E$.

# 6 Vector space duality

In the preceding section we reduced the problem of finding selfdual skew cyclic codes in $\mathbf{E}_k$
to that of finding selfdual skew cyclic codes in $\mathrm{End}_{\mathbf{F}_l}(\mathbf{K}_l)$ for each index $l$. We will now further
reduce the problem to the enumeration of maximal isotropic spaces of $\mathbf{K}_l$ for each index $l$. To this
### 3.3.2 The nonpalindromic case

We first consider the indices $l$ such that $\tau(l) \neq l$. At those places, we simply need to generate a uniformly distributed random $\mathbf{F}_l$-subspace of $\mathbf{K}_l$. We proceed as follows. We first construct the dimension: we sample an integer $d \in \{0, \dots, r\}$ with distribution given by:

$$ \text{Prob}[d = i] \text{ proportionnal to } \begin{bmatrix} r \\ i \end{bmatrix}_{q_l}. $$

Once this is achieved, we sample $d$ random elements in $\mathbf{K}_l$ with uniform distribution. If they are linearly independent over $\mathbf{F}_l$, we output the vector space they generate. Otherwise, we throw them and start again with $d$ new elements. The probability of failure is

$$ \left(1 - \frac{1}{q_l^r}\right) \left(1 - \frac{1}{q_l^{r-1}}\right) \cdots \left(1 - \frac{1}{q_l^{r-d+1}}\right) \ge 1 - \left(\frac{1}{q_l^r} + \cdots + \frac{1}{q_l^{r-d+1}}\right) \ge 1 - \frac{1}{q_l - 1}, $$

proving that, in average, we will need to repeat our process only $O(1)$ times.

Up to a multiplicative constant, the mean complexity of the algorithm is then equal to the complexity of checking linearly independence of $d$ vectors in a space of dimension $r$, which is within $O(r^3)$ by Gaussian elimination.

### 3.3.3 The Hermitian case

We now move to the Hermitian case, i.e. we assume that $\tau(l) = l$ and $y_l \neq \pm 1$. We thus want to design an algorithm outputting a uniformly distributed random isotropic $\mathbf{F}_l$-subspace of $\mathbf{K}_l$ (endowed with the Hermitian pairing $(-, -)_{\mathbf{K}_l}$ defined in (2.3), assuming that the existence criterion of Corollary 3.3 is fulfilled. Our construction is inspired by the proof of Theorem 3.4, except that we will not work with the quotient $(Fu_1)^\perp/(Fu_1)$ but, instead, will embed $u_1$ is a hyperbolic plane $H_1$ and work with $H_1^\perp$.

We consider a finite field $F$ of cardinality $q_F$ equipped with a nontrivial involutive automorphism $\sigma: F \to F$. We also consider an Hermitian space $V$ of dimension $r$ and denote by $\langle-, -\rangle$ the bilinear form on it. We assume that $V$ has Witt index $s$ (i.e. that $V$ is isomorphic to the orthogonal direct sum of $s$ hyperbolic planes) and aim at sampling a random isotropic subspace of $V$ of dimension $s$.

For $u, v \in V$, we consider the following equation in $\lambda$:

$$ (\mathcal{E}_{u,v}) : \langle u + \lambda v, u + \lambda v \rangle = 0. $$

We briefly recall its resolution. If $\langle v, v \rangle = 0$, the equation reduces to $\text{Trace}_{F/F^\sigma}(\lambda \cdot \langle v, u \rangle) = -\langle u, u \rangle$ which, per surjectivity of the trace, can be solved as soon as $\langle v, u \rangle \neq 0$.

On the contrary, when $\langle v, v \rangle \neq 0$, we consider the discriminant of $(\mathcal{E}_{u,v})$ defined by $\Delta := \langle u, v \rangle \cdot \langle v, u \rangle - \langle u, u \rangle \cdot \langle v, v \rangle$. One readily checks that $\Delta$ is invariant under $\sigma$ and that the equation $(\mathcal{E}_{u,v})$ can be rewritten $\text{Norm}_{F/F^\sigma}(\langle u, v \rangle + \lambda \cdot \langle v, v \rangle) = \Delta$. The solutions of $(\mathcal{E}_{u,v})$ are then the elements of the form

$$ \lambda = \frac{\delta - \langle u, v \rangle}{\langle v, v \rangle} $$
end we apply the classical duality between $\mathbf{F}_l$-vector subspaces of $\mathbf{K}_l$ and left ideals of $End_{\mathbf{F}_l}(\mathbf{K}_l)$
[Ber] (Cf. definition of $\tau$ 24):

• In the palindromic case where $\tau(l) = l$

• In the nonpalindromic case where $\tau(l) \neq l$

**Definition 40** Given a field $L$ and any $L$-vector spaces $W$, the *vector space duality* associates to every $L$-vector subspace $V$ of $W$, the left ideal $I_V$ of $End_L(W)$ constituted by the endomorphisms vanishing on $V$. It associates dually to every left ideal $I$ of $End_L(W)$, the $L$-vector subspace intersection of the kernels of the morphisms in $I$. This correspondence can be expressed as:

$$ \left\{ \begin{array}{l} V_I = \bigcap_{f \in I} \ker(f) \\ I_V = \{ f \in \mathrm{End}_{\mathbf{F}_l}(\mathbf{K}_l) | V \subset \ker(f) \} \end{array} \right. \qquad (6.1) $$

This duality map is obviously order reversing. Moreover it is a bijective and involutive correspondence between the set of left ideals of $End_L(W)$ and the set of $L$-vector subspaces of $W$.

**Lemma 41** For a Hermitian bilinear form, the orthogonal vector space of the image of $f \in End_L(V)$ is equal to the kernel of its adjoint.

**Proposition 42** For any $L$-vector space $V$, and any nondegenerate bilinear form, along with its corresponding adjunction $\star$, and defined on $V \times V^*$, we have: $I_V^{\perp} = I_{V^*}$

*Proof.* For $g \in End_L(V^*)$, $C_g^{\perp}$ is a left-submodule of $End_L(V)$. We thus have $C_f = C_g^{\perp}$ for some $f \in End_L(V)$. By the product criterion 37, this corresponds to the condition: $fg^* = 0$. But $\{f \in End_L(V) | f \circ g^* = 0\} = \{f \in End_L(V) | f(g^*(L)) = 0\}$ is the left ideal vanishing on $Im(g^*)$, i.e. on $\ker(g)^{\perp}$ by lemma 41. We conclude: $C_g^{\perp} = C_f = I_{\ker(g)^{\perp}}$. $\square$

We can now prove the main Proposition 2.

**Theorem 43** There exists an explicit bijection between the set of selfdual skew cyclic codes of $\mathbf{E}_k$ and the cartesian product of sets $W_{\mathrm{palindromic}} \times W_{\mathrm{nonpalindromic}}$, where:

• $W_{\mathrm{palindromic}}$ is the cartesian product over all indexes $l$ invariant by $\tau$ of the sets of maximal isotropic $\mathbf{F}_l$-vector subspaces of $\mathbf{K}_l$.

• $W_{\mathrm{nonpalindromic}}$ is the cartesian product over all remaining unordered pairs of indexes $(l, \tau(l))$ (verifying $l \neq \tau(l)$) of the sets of $\mathbf{F}_l$-vector subspaces of $\mathbf{K}_l$.
where $\delta$ is a preimage of $\Delta$ by the norm map. Since the latter is surjective (because we are working over finite fields), a solution always exists.

We are now ready to present Algorithm 2: it computes a basis $(u_1, \dots, u_s, v_1, \dots, v_s)$ of $V$ such that each pair $(u_i, v_i)$ is hyperbolic and, writing $H_i \subset V$ for the hyperbolic plane they generate, we have the orthogonal decomposition $V = \bigoplus_{i=1}^s H_i$.

<caption>**Algorithm 2:** Decomposition as a direct sum of hyperbolic planes (Hermitian case)</caption>

**Input:** $V$: the ambient Hermitian vector space
**Output:** $u, v$: a basis of hyperbolic pairs
1: $u, v, W \leftarrow []$, $[]$, $0$
2: **while** $W \neq V$:
3: &nbsp;&nbsp;&nbsp;&nbsp;$u, v \leftarrow$ two random vectors in $W^{\perp}$
4: &nbsp;&nbsp;&nbsp;&nbsp;**if** $(u, v)$ are linearly independent and $\langle v, v \rangle \neq 0$:
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\lambda \leftarrow$ a random solution of the equation $(\mathcal{E}_{u,v})$
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$u \leftarrow u + \lambda v$ \quad /* now $\langle u, v \rangle = 0$ */
7: &nbsp;&nbsp;&nbsp;&nbsp;**if** $\langle u, v \rangle \neq 0$:
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\lambda \leftarrow$ a solution of the equation $(\mathcal{E}_{v,u})$
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$v \leftarrow v + \lambda u$ \quad /* now $\langle v, v \rangle = 0$ */
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$v \leftarrow v/\langle v, u \rangle$ \quad /* now $(u, v)$ is a hyperbolic pair */
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$u \leftarrow u + [u]$, $v \leftarrow v + [v]$
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$W \leftarrow W + Fu + Fv$

13: **return** $u, v$

**Proposition 3.10** Algorithm 2 is correct.

*Proof.* It follows from the construction that, after the first successful iteration of the loop, $(u, v)$ is a hyperbolic pair in $V$. Indeed, we notice that the subspace $H_1$ generated by $u$ and $v$ does not change throughout the loop, and so it is still a plane at the end. Moreover, each update successively ensures that $\langle u, u \rangle = 0$, then $\langle v, v \rangle = 0$ and finally $\langle u, v \rangle = 1$. We observe that $\langle v, u \rangle$ does not vanish on line 10 because the substitution of line 9 leaves it unchanged. After this, we update $W$ so that we continue to work in the orthogonal complement of $H_1$ which have dimension $2(s-1)$ and Witt index $s-1$ thanks to Witt's cancellation theorem. The induction then goes. □

**Lemma 3.11** The tests of lines 4 and 7 are successful if and only if the vectors $u, v$ picked on line 3 span a hyperbolic plane of $W^{\perp}$ and $v$ is not isotropic.

Moreover, this happens with probability at least $\frac{\sqrt{q_F-1}}{\sqrt{q_F+1}} \cdot \frac{q_F-1}{q_F} \ge \frac{4}{9}$.

*Proof.* It is clear that if $u$ and $v$ pass all tests, then they span a hyperbolic plane and that $v$ is nonisotropic. Conversely, we need to prove if $H \subset W^{\perp}$ is a hyperbolic plane and $u, v$ span $H$ with $\langle v, v \rangle \neq 0$, then all tests pass. It is obvious for the test of line 4. If, on line 7, we had $\langle u, v \rangle = 0$, then $u$ would be orthogonal to both $u$ and $v$, implying that the Hermitian form would be degenerated on $H$. This is a contradiction.

We now count to number of hyperbolic planes in $W^{\perp}$. For this, we write $\dim_F W^{\perp} = 2d$ and we
*Proof.* As we assumed dim $\mathbf{K} =: r$ to be even, selfdual skew cyclic codes correspond to isotropic spaces of maximal dimension $s := r/2$. We apply the duality to the $\mathbf{F}_l$-vector spaces $\mathbf{K}_l$ with the corresponding adjunction: $\mathbf{E}_{k,l} \stackrel{*}{\rightarrow} \mathbf{E}_{k,\tau(l)}$ and nondegenerate bilinear form on $\mathbf{K}_l \times \mathbf{K}_{\tau(l)}$. The duality being bijective, order reversing and preserving the orthogonality relation between skew codes in $\mathbf{E}_{k,l}$ and $\mathbf{F}_l$-vector subspaces, the diagrams 5.18 and 5.9 being commutative and thus preserving the product criterion 38 for selfdual codes, selfdual skew cyclic codes of $\mathbf{E}_k$ correspond to the product of the sets constituted by the cartesian product of the sets of maximal isotropic palindromic $\mathbf{F}_l$-vector subspaces of $\mathbf{K}_l$, and by the cartesian product of the sets of maximal isotropic nonpalindromic $\mathbf{F}_l$-vector subspaces of $\mathbf{K}_l \times \mathbf{K}_{\tau(l)}$. As in the nonpalindromic case, isotropic vector subspace of $\mathbf{K}_l \times \mathbf{K}_{\tau(l)}$ equal to their orthogonal are of the form $W \oplus W^{\perp}$ for some $\mathbf{F}_l$-vector subspace $W$ of $\mathbf{K}_l$, they correspond exactly to the $\mathbf{F}_l$-vector subspaces of $\mathbf{K}_l$. $\square$

# 7 Enumeration of selfdual skew cyclic codes

In the preceding sections we showed that enumerating selfdual skew cyclic codes boils down to enumerating maximal isotropic $\mathbf{F}_l$-vector subspaces of $\mathbf{K}_l$ in the palindromic case, and to enumerating $\mathbf{F}_l$-vector subspaces of $\mathbf{K}_l$ in the nonpalindromic case. We will now describe algorithms that fulfill this requirement.

## 7.1 Counting selfdual skew cyclic codes

In order to count selfdual skew cyclic codes, we introduce the $q$-binomial coefficients defined by:

$$ \binom{n}{k}_q = \frac{(1-q^n)(1-q^{n-1})\dots(1-q^{n-k+1})}{(1-q)(1-q^2)\dots(1-q^k)} $$

where $n$ and $k$ are nonnegative integers. If $k > n$, this evaluates to 0. For $r = 0$, the value is 1 since both the numerator and denominator are empty products.

All of the factors in numerator and denominator are divisible by $1-q$, and the quotient is the $q$-number ($q$-analog of an integer $k$):

$$ [k]_q = \sum_{0 \le i < k} q^i = 1 + q + q^2 + \dots + q^{k-1} = \begin{cases} \frac{1-q^k}{1-q} & \text{for } q \ne 1 \\ k & \text{for } q = 1 \end{cases} \quad (7.1) $$
consider the map

$$
\begin{array}{rcl}
S: & \left\{ \begin{array}{l} \text{pair of nonorthogonal} \\ \text{isotropic vectors in } W^{\perp} \end{array} \right\} & \to \left\{ \text{hyperbolic planes } \subset W^{\perp} \right\} \\
& & \\
& & \\
(x, y) & \mapsto & Fx + Fy.
\end{array}
$$

The cardinality of the domain of $\mathcal{S}$ is $\text{iso}(W^{\perp}) \cdot \text{iso}^*(W^{\perp})$ where $\text{iso}(W^{\perp})$ denotes the number of isotropic vectors in $W^{\perp}$ (as in the proof of Theorem 3.4) and $\text{iso}^*(W^{\perp})$ is the number of isotropic vectors in $W^{\perp}$ which are nonorthogonal to a given one. By the proof of Theorem 3.4, we know that $\text{iso}(W^{\perp}) = (q_F^d - 1)(q_F^{d-1/2} + 1)$. The computation of $\text{iso}^*(W^{\perp})$ can be handled similarly: reusing the notation of the proof of Theorem 3.4, it corresponds to count the tuples $((a_i)_{1 \le i \le d}, (b_i)_{1 \le i \le d}, \alpha)$ with $\sum_{i=1}^d a_i \sigma(b_i) = \alpha = -\sigma(\alpha)$ and $b_1 \ne 0$. There are then $\sqrt{q_F}$ choices for $\alpha$, $(q_F - 1)q_F^{d-1}$ choices for the $b_i$ and when all those are fixed, there remains $q_F^{d-1}$ choices for the $a_i$. Therefore $\text{iso}^*(W^{\perp}) = (q_F - 1)q_F^{2d-3/2}$ and we finally obtain:

$$
\mathrm{Card}(\text{domain of } \mathcal{S}) = (q_F^d - 1) \cdot (q_F - 1) \cdot (q_F^{3d-2} + q_F^{2d-\frac{3}{2}}).
$$

Similarly, given a hyperbolic plane $H \subset W^{\perp}$, we have:

$$
\mathrm{Card}(S^{-1}(H)) = \mathrm{iso}(H) \cdot \mathrm{iso}^{*}(H) = (q_F - 1)^2 \cdot (q_F + \sqrt{q_F}).
$$

We conclude that the number of hyperbolic planes in $W^{\perp}$ is

$$
A = \frac{(q_F^d - 1) \cdot (q_F^{3d-2} + q_F^{2d-\frac{3}{2}})}{(q_F - 1) \cdot (q_F + \sqrt{q_F})}.
$$

Now, once a hyperbolic place $H$ is fixed, the number of possibilities for $v$ is

$$
B = (q_F^2 - 1) - (1 + \sqrt{q_F})(q_F - 1) = (q_F - 1)(q_F - \sqrt{q_F})
$$

while the number of options for $u$ is $C = q_F^2 - q_F$. Finally, the probability we are looking for is $\frac{ABC}{q_F^{d/2}}$ and calculus shows that it is always greater than $\frac{\sqrt{q_F - 1}}{\sqrt{q_F + 1}} \cdot \frac{q_F - 1}{q_F}$ (which is the limit when $d$ goes to infinity). The fact that the latter is bounded from below by $\frac{4}{9}$ follows from the observation that $q_F$ is necessarily at least 9 because $F$ has odd characteristic and admits a subfield of index 2. $\square$

**Proposition 3.12** Algorithm 2 terminates almost surely and its average complexity is $O(r^3)$ operations in $F^\sigma$ and $O(r)$ computations of inner products.

*Proof.* Termination follows directly for Lemma 3.11. Regarding complexity, we claim that each successful iteration of the loop costs at most $O(r^2)$ operations in $F^\sigma$ and $O(1)$ computations of inner products. To achieve this, we first observe that solving the equation $(\mathcal{E}_{u,v})$ amounts to computing the attached discriminant (which corresponds to computing 4 inner products) and finding a uniformly distributed preimage of the discriminant by the norm map; the latter can be done using the algorithms of [CL17] for a constant cost. Similarly solving $(\mathcal{E}_{v,u})$ reduces to a linear system, which can be attacked by simple linear
Dividing out these factors gives the equivalent formula:

$$ \binom{m}{r}_q = \frac{[m]_q[m-1]_q \dots [m-r+1]_q}{[1]_q[2]_q \dots [r]_q} \quad (r \le m) $$

In terms of the q-factorial $[n]_q! = [1]_q[2]_q \dots [n]_q$, the formula can be stated as

$$ \binom{m}{r}_q = \frac{[m]_q!}{[r]_q! [m-r]_q!} \quad (r \le m) $$

We will use following lemmas on q-binomials.

**Lemma 44** The q-binomial coefficient $\binom{n}{k}_q$ counts the number of $\mathbb{F}_q$-vector subspaces of rank $k$ in the ambient $\mathbb{F}_q$-vector space $\mathbb{F}_q^n$.

*Proof.* The q-binomial coefficient is equal to the number of free families of rank $k$ on the numerator. As the denominator is equal to the number of bases for a given $\mathbb{F}_q$-vector subspace of dimension $k$, the quotient is the q-binomial number expected. $\square$

**Lemma 45** There is an analog of the binomial theorem for q-binomial coefficients, known as the q-binomial theorem:

$$ \prod_{k=0}^{n-1} (1 + q^k t) = \sum_{k=0}^{n} q^{k(k-1)/2} \binom{n}{k}_q t^k $$

*Proof.* See the article of Pólya [PA71]. $\square$

We also need the following classical theorem due to Witt.

**Proposition 46** (Witt decomposition) Let $F$ be a finite field, $V$ a 2s dimensional $F$-vector space. Let $\mathcal{B}$ be a nondegenerate $\sigma$-sesquilinear form on $V$, resp. bilinear form on $V$. Then there exist $H_i$ hyperbolic planes (Cf. the definition in 3), and an invariant, $d$, of $V$ called the Witt index and equal to $s$ or $s-1$, such that one has the orthogonal decomposition:

$$ V \simeq \perp_{1 \le i \le d} H_i \perp W $$

where $\dim(W) = s - 2d$ and $W$ does not contain any nonzero isotropic vector. The dimension of any maximal isotropic space is given by the Witt index $d$.

*Proof.* See the proof in Theorem 3.11 [Art11]. $\square$

**Remark 47** From the Witt decomposition theorem, we see that maximal isotropic spaces of dimension $s$ exist in $K_l$ if and only if the Witt index of $K_l$ is $s$.
algebra over $F^\sigma$ for a constant cost again. Regarding the computation of $W$, we may process as follows: we maintain a matrix $M$ in reduced row echelon form representing the subspace of $V^* = \operatorname{Hom}_F(V, F)$ generated by the forms $\langle-, w\rangle$ with $w \in W$. At each update of $W$ on line 11, we need to add two new lines to $M$ and re-echelon it; this has a cost of $O(r^2)$ operations in $F$ using standard Gaussian elimination. Moreover, knowing $M$, sampling $u$ and $v$ on line 3 amounts to finding two random solutions of the linear system $MX = 0$. Since $M$ is already row-echeloned, this can be done for a cost of $O(r^2)$ operations in $F$ as well. $\square$

Finally, the link between Algorithm 2 and the question we are interested in is established in the next proposition.

**Proposition 3.13** If $\mathbf{u}, \mathbf{v}$ is the output of Algorithm 2, then the space generated by $\mathbf{u}$ is a uniformly distributed random isotropic subspace of $V$ of dimension $s$.

*Proof.* The fact that the span of $\mathbf{u}$ is an isotropic subspace of dimension $s$ is clear. To prove that it is uniformly distributed, we notice that, after line 3, the plane $H := Fu+Fv$ is uniformly distributed among all planes in $W^\perp$. Since this plane stays unchained throughout the loop, the first part of Lemma 3.11 implies that, at the end of the loop, $H$ is uniformly distributed among all hyperbolic planes in $W^\perp$.

We now fix a hyperbolic plane $H \subset W^\perp$, together with a nonisotropic vector $v \in H$. We claim that, when $u$ varies in $H$, the vector $u$ one obtains after the replacement of line 6 is uniformly distributed in the set $\mathcal{I}_H$ of isotropic vectors in $H$. In order to prove this, for $u \in H$, we define $L(u) \subset H$ as the affine line passing through $u$ and directed by $v$. We also set $S(u) := L(u) \cap \mathcal{I}_H$. Clearly, for any fixed $u$ noncollinear to $v$, the $L(\alpha u)$ form a partition of $H \setminus Fv$ when $\alpha$ varies in $F^\times$. Since $v$ is itself nonisotropic, we conclude that

$$ \mathcal{I}_H = \bigsqcup_{\alpha \in F^\times} S(\alpha u). \qquad (3.4) $$

Moreover, the multiplication by $\alpha$ defines a bijection $S(u) \to S(\alpha u)$; hence, all the $S(\alpha u)$ have the same cardinality. Coming back now to the algorithm, we notice that the effect of lines 5 and 6 is to replace $u$ by a uniformly distributed random vector in $S(u)$. The decomposition (3.4), combined with the fact that all $S(\alpha u)$ have the same cardinality, then implies that the vector $u$ obtained after line 6 gets uniformly distributed in $\mathcal{I}_H$ when $u$ varies on any given line of $H$ that does not contain $v$. Since this holds for any line, our claim is proved.

Let $\mathcal{A}$ be the set of all $((H_1, u_1), \dots, (H_s, u_s))$ such that the $H_i$ are pairwise orthogonal hyperbolic planes in $V$ and, for all $i$, $u_i$ is an isotropic vector in $H_i$. It follows for what precedes that, if $\mathbf{u} = (u_1, \dots, v_s)$, $\mathbf{v} = (v_1, \dots, v_s)$ is the output of Algorithm 2, the tuple $((H_1, u_1), \dots, (H_s, u_s))$ with $H_i := Fu_i + Fv_i$ is uniformly distributed in $\mathcal{A}$. To conclude, it is then enough to prove that all the fibers of the map

$$ \begin{gathered} \mathcal{A} \to \mathcal{B} := \left\{ \begin{array}{l} \text{s-dimensional isotropic} \\ \text{subspaces of } V \end{array} \right\} \\ ((H_1, u_1), \dots, (H_s, u_s)) \mapsto Fu_1 + \dots + Fu_s \end{gathered} $$

have the same cardinality. For this, we use the fact that the unitary group $U(V)$ acts transitively of $\mathcal{B}$. In other words, given two $s$-dimensional isotropic subspaces $U, U' \subset V$, there exists a unitary transformation
### 7.1.1 Counting selfdual skew codes in the nonpalindromic case

**Proposition 48** Noting $q_l := |\mathbf{F}_l| = q^{\deg P_l}$, the number of maximal isotropic spaces in the nonpalindromic case is:

$$ \sum_{k=0}^{k=r} \binom{r}{k}_{q_l} = \sum_{k=0}^{k=r} \frac{(q_l^r - 1) \dots (q_l^{r-k+1} - 1)}{(q_l^k - 1) \dots (q_l - 1)} $$

*Proof.* Enumerating maximal selfdual ideals over $\mathbf{E}_{k,l} \times \mathbf{E}_{k,\tau(l)}$ boils down to enumerating all $\mathbf{F}_l$-vector subspaces of $\mathbf{K}_l$ by 43. The number of selfdual codes in such pairs $\mathbf{E}_{k,l} \times \mathbf{E}_{k,\tau(l)}$ is thus equal to the sum over all possible dimensions $k$ from 0 to $r$ of the numbers of vector subspaces of dimension $k$, which, by lemma 44, are given by the $q$-binomial coefficients. $\square$

### 7.1.2 Explicit existence criterion for selfdual skew codes in the palindromic case

As stated by the Witt decomposition theorem 46, computing the Witt index of $\mathbf{K}_l$ provides an explicit existence condition for selfdual skew codes. For this computation, we need to introduce the notion of discriminant of a finite etale algebra over its base field.

**Definition 49** We recall that the discriminant $\delta_{\mathbf{K}_l/\mathbf{F}_l}$ of the finite etale $\mathbf{F}_l$-algebra $\mathbf{K}_l$ is given by $\det(\mathrm{Trace}_{\mathbf{K}_l/\mathbf{F}_l}(e_i e_j))_{i,j}$ modulo squares in $\mathbf{F}_l^*$, where $(e_i)$ is a base of the $\mathbf{F}_l$-vector space $\mathbf{K}_l$.

We also define the discriminant $\delta_{\zeta_l}$ of the finite etale $\mathbf{F}_l$-algebra $\mathbf{K}_l$ for the trace bilinear form that we defined on $\mathbf{K}_l$ as $\det(\mathrm{Trace}_{\mathbf{K}_l/\mathbf{F}_l}(\zeta_l e_i e_j))_{i,j}$ modulo squares in $\mathbf{F}_l^*$.

This definition does not depend on the choice of the base $(e_i)$. Indeed, given any base change matrix $M$, we get:

$$ (\mathrm{Trace}_{\mathbf{K} \otimes \mathbf{F}}(y_l)/\mathbf{F}(y_l))(\zeta_l M(e_i)M(e_j))_{i,j} = \left(\sum_{l,m} M^{\mathrm{tr}}_{i,l} \mathrm{Trace}_{\mathbf{K} \otimes \mathbf{F}}(y_l)/\mathbf{F}(y_l)\right) (\zeta_l e_l e_m) \sum_{m,j} M_{m,j})_{i,j} $$

And on the other hand we have $\det(M) \det(M^{\mathrm{tr}}) = 1$ in $\mathbf{F}(y_l)^*/(\mathbf{F}(y_l))^2$.

We have the following classical existence criterion on (maximal) isotropic subspace of dimension $s$:

**Proposition 50** We assume $\sigma_l(y_l) = y_l$ and $p \neq 2$. Then there exists an isotropic subspace of dimension $s$ in $\mathbf{K}_l$ if and only if $(-1)^s \delta_{\zeta_l}$ is a square in $(\mathbf{F}_l)^*$.

*Proof.* For sake of completeness, we recall the proof. By Witt decomposition theorem 46 applied to our quadratic form, the maximal isotropic spaces of dimension $s$ exist if and only if the Witt
$f: V \to V$ such that $f(U) = U'$. Such an $f$ induces a bijection between the fibers above $U$ and $U'$, then proving that the cardinalities are equal. □

**Remark 3.14** Two important optimizations of Algorithm 2 needs to be mentioned. Firstly, the lines 8–10 are in fact not needed if we are only interested in the span of **u** (as we are here). We kept them because computing a full hyperbolic basis can be interested on its own, and will be actually used afterwards when we will come to enumeration. Secondly, if the picked vector **v** is not isotropic on line 4, instead of giving up immediately, we may try to swap **u** and **v** and redo the test. On the one hand, this increases the probability of success and, on the other hand, one can prove that this does not affect the fact that the span of **u** is uniformly distributed at the end.

### 3.3.4 The Euclidean case

We move to the Euclidean case, i.e. we consider the same setting as before expect that we now assume that $\sigma$ is the identity. The equation $(\mathcal{E}_{u,v})$ continues to make sense but its resolution is a bit different. Precisely, expanding the scalar product, we find that it is equivalent to

$$ \langle u, u \rangle + 2\lambda \cdot \langle u, v \rangle + \lambda^2 \cdot \langle v, v \rangle = 0. $$

If $\langle v, v \rangle = 0$, it is a linear equation that we can solve as soon as $\langle u, v \rangle \neq 0$. On the contrary, if $\langle v, v \rangle \neq 0$, it is a quadratic equation whose (reduced) discriminant is $\Delta := \langle u, v \rangle^2 - \langle u, u \rangle \cdot \langle v, v \rangle$ (this is in fact the same as before!). The equation $(\mathcal{E}_{u,v})$ has no solution when $\Delta$ is not a square and it has one or two solutions otherwise: if $\delta^2 = \Delta$, they are given by $\lambda = \frac{\delta - \langle u, v \rangle}{\langle v, v \rangle}$.

From here, we can write down Algorithm 3 (which is a direct translation of Algorithm 2).

<caption>**Algorithm 3:** Direct sum decomposition of hyperbolic planes in the Euclidean case</caption>

**Input:** $V$: the ambient Euclidean vector space
**Output:** $\mathbf{u}, \mathbf{v}$: a basis of hyperbolic pairs
1: $\mathbf{u}, \mathbf{v}, W \leftarrow []$, $[]$, $0$
2: **while** $W \neq V$:
3: &nbsp;&nbsp;&nbsp;&nbsp;`$u, v \leftarrow$ two random vectors in $W^{\perp}$`
4: &nbsp;&nbsp;&nbsp;&nbsp;**if** $(u, v)$ are linearly independent and $\langle v, v \rangle \neq 0$:
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`$\Delta \leftarrow \langle u, v \rangle^2 - \langle u, u \rangle \cdot \langle v, v \rangle$`
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $\Delta$ is a square in $F$:
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`$\lambda \leftarrow$ a random solution of the equation $(\mathcal{E}_{u,v})$`
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`$u \leftarrow u + \lambda v$`
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $\langle u, v \rangle \neq 0$:
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`$\lambda \leftarrow$ a solution of the equation $(\mathcal{E}_{v,u})$`
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`$v \leftarrow v + \lambda u$`
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`$v \leftarrow v/\langle v, u \rangle$` /* now $(u, v)$ is a hyperbolic pair */
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`$\mathbf{u} \leftarrow \mathbf{u} + [u]$, $\mathbf{v} \leftarrow \mathbf{v} + [v]$`
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`$W \leftarrow W + Fu + Fv$`

15: **return** $\mathbf{u}, \mathbf{v}$

**Proposition 3.15** Algorithm 3 is correct. It terminates almost surely and its average complexity is $O(r^3)$ operations in $F$ and $O(r)$ computations of inner products. Moreover, if $\mathbf{u}, \mathbf{v}$ is the output of
index is $s$. If this is the case, then obviously $\delta_{\zeta_l}$ is congruent to $(-1)^s$, as one can check by computing the discriminant of the matrix representing the bilinear form in a base constituted by hyperbolic pairs (Cf. 3):

$$ \begin{pmatrix} 0 & 1 & 0 & 0 & \cdots & 0 & 0 \\ 1 & 0 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 0 & 1 & \cdots & 0 & 0 \\ 0 & 0 & 1 & 0 & \cdots & 0 & 0 \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ 0 & 0 & 0 & 0 & \cdots & 0 & 1 \\ 0 & 0 & 0 & 0 & \cdots & 1 & 0 \end{pmatrix} $$

If this is not the case, then $\delta_{\zeta_l}$ cannot be congruent to $(-1)^s$. Indeed restricted to the last nonhyperbolic hyperplane of the Witt decomposition, the matrix representing the symmetric bilinear form in a suitable base has the form: $\begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$ if $\delta_{\zeta_l} \cong (-1)^s$. But it is readily seen that this defines a subspace having nontrivial isotropic vectors, which contradicts the assumption on the Witt index. $\square$

We can make this criterion explicit by effectively computing $-1$ and $\delta_{\zeta_l}$ in $\mathbf{F}_l^*/(\mathbf{F}_l^*)^2$.

**Lemma 51** $-1$ is a square in $\mathbf{F}_l^*$ if and only if $p \equiv 1(4)$ or $[\mathbf{F}_l : \mathbb{F}_p]$ is even.

*Proof.* If $p \equiv 1(4)$ or $[\mathbf{F}_l : \mathbb{F}_p]$ is even, $\mathbf{F}_l^*$ has an element of order 4, so there is an element different from 1 and $-1$ such that $x^4 = 1$, i.e, $(x^2 - 1)(x^2 + 1) = 0$, hence $x^2 + 1 = 0$. One checks the reciprocal assertion. $\square$

**Lemma 52** The discriminant $\delta_{\zeta_l}$ is equal to $\mathrm{Norm}_{\mathbf{K}_l/\mathbf{F}_l}(\zeta_l)\delta_{\mathbf{K}_l/\mathbf{F}_l}$.

*Proof.* Noting $\mathrm{Mat}(\zeta_l)$ the matrix representing the multiplication by $\zeta_l$ in the base $(e_i)$ and $\mathrm{Mat}(\zeta_l)^{\mathrm{tr}}$ its transpose, we get:

$$ \det \left( \sum_l \mathrm{Mat}(\zeta_l)^{\mathrm{tr}}_{i,l} \mathrm{Trace}_{\mathbf{K}_l/\mathbf{F}_l} (e_l e_j) \right)_{i,j} = \det(\mathrm{Mat}(\zeta_l)^{\mathrm{tr}}) \delta_{\mathbf{K}_l/\mathbf{F}_l} = \mathrm{Norm}_{\mathbf{K}_l/\mathbf{F}_l}(\zeta_l) \delta_{\mathbf{K}_l/\mathbf{F}_l} $$

<figure><img src="image_2.png" /></figure>

**Lemma 53** The discriminant $\delta_{\mathbf{K}_l/\mathbf{F}_l}$ is a square in $\mathbf{F}_l^*$ if and only if the Galois group of $\mathbf{F}_l/\mathbf{F}$ is a subgroup of the alternating group, i.e. if and only if the degree of the extension $[\mathbf{F}_l : \mathbb{F}_p]$ is odd.
Algorithm 3, then the space generated by **u** is a uniformly distributed random isotropic subspace of **V**
of dimension **s**.

*Proof.* It is a repetition of the proofs of Propositions 3.10, 3.12 and 3.13 (with the small difference that the probability of success in the analogue of Lemma 3.11 is now bounded from below by $\frac{(q_F-1)^2}{2q_F^2} \ge \frac{2}{9}$). $\square$

3.4 Enumeration of selfdual skew cyclic codes

We finally address the question of enumeration. As we already said earlier, an algorithm that outputs
in one shot the complete list of selfdual codes in E_k would only have a limited interest because the number
of such codes grows exponentially with respect to r.

Instead, we will work with iterators, that are, roughly speaking, procedures that produce a new
item each time they are called, without precomputing the entire list at the beginning. Concretely, we
model iterators by importing the keywords **yield** and **next** from the Python syntax. When a procedure
containing the keyword **yield** is called, it is not executed but instead returns an object called *iterator*,
which can be understood as a pointer to the current state of execution of the procedure. Now, each
time the iterator is called through the keyword **next**, the execution of the procedure continues until a
statement **yield** is encountered; at that point, the execution is interrupted and the iterator outputs the
attribute of the **yield** instruction.

In all what follows, we assume<fnref n="1" /> that we have at our disposal, for all integers $m \le n$ and any finite field $F$, an iterator producing the list of all matrices in reduced row echelon form with $m$ rows and $n$ columns. We note that such matrices are in one-to-one correspondence with $m$-dimensional $F$-linear subspaces of $F^n$ (the subspace being the span of the rows of the matrix). In a similar fashion, we also assume that, for any given linear system, we have at our disposal an iterator running over its solutions.

We now explain how to build iterators over each component of the product $W_{\text{nonpal}} \times W_{\text{pal}}$.

**3.4.1 The nonpalindromic case**

In this case, we have to construct an iterator running over all $\mathbf{F}_l$-linear subspaces of $\mathbf{K}_l$. In order to reduce this task to a matrix enumeration, we first pick a basis of $\mathbf{K}_l$ over $\mathbf{F}_l$ (this can be done easily; for example, a basis of $\mathbf{K}$ over $\mathbf{F}$ does the job). Once this is achieved, we take an iterator that runs over all matrices over $\mathbf{F}_l$ in reduced row echelon form with $r$ columns, which directly solves our problem.

**3.4.2 The Euclidean case**

As in Subsection 3.3.4, we work with a general $r$-dimensional Euclidean space $V$ over a finite field $F$ of cardinality $q_F$ and assume that $V$ has Witt index $s$. By the results of Subsection 3.3.4, we can further assume that we are given a hyperbolic basis of $V$, that is a basis $(u_1, \dots, u_s, v_1, \dots, v_s)$ such that $\langle u_i, v_i \rangle = 1$ and all other scalar products between elements in the basis vanish.

<footnote n="1">¹Such an iterator is available in many softwares, including SageMath. It is moreover easy to construct: we iterate over the subset of $I \subset \{1, \dots, n\}$ of cardinality $m$ and, for each such $I$, we run over all the matrices in reduced row echelon form with pivots at positions in $I$.</footnote>
*Proof.* The proof can be found in Corollary 4.2 from [Mil20]. □

In addition $Norm_{K_l/F_l}(\zeta_l)$ can also be computed.

**Lemma 54** The norm $Norm_{K_l/F_l}(\zeta_l)$ is a square in $F_l^*$ if and only if $y_l = 1$.

*Proof.* We have:

$$Norm_{K_l/F_l}(\zeta_l)^{\frac{q-1}{2}} = (\zeta_l^{\frac{\sum_{0 \le i < 2s} q_l^i}{2}})^{\frac{q-1}{2}}$$

Moreover, as $2s$ is even we have:

$$(\zeta_l^{\sum_{0 \le i < 2s} q_l^i})^{\frac{q-1}{2}} = (\zeta_l^{q-1})^{\frac{\sum_{0 \le i < 2s} q_l^i}{2}} = (x_l (Id \otimes \sigma_l)(x_l))^{\frac{\sum_{0 \le i < 2s} q_l^i}{2}}$$

Using the chinese remainder isomorphism between $K_l/F_l$ and a product of $F_l$-field extensions:

$$ \begin{array}{ccc} \mathbf{K}_l & \xrightarrow{\sim} & \prod_i \mathbf{L}_{l,i} \\ x_l & \mapsto & (x_{l,i})_i \end{array} \qquad (7.2) $$

The Frobenius automorphism generates the cyclic Galois group of each $L_{l,i}$. Thus for a palindromic index $i$ (satisfying $\tau(i) = i$), $Id \otimes \sigma_l$ induces the following involutive mapping: $Id \otimes \sigma_{l,i} : x_{l,i} \mapsto x_{l,i}^{q_l^{n_i}}$ for some positive integers $n_i$. For nonpalindromic indexes $i$ (satisfying $\tau(i) \neq i$), $Id \otimes \sigma_l$ induces the following involutive mapping: $Id \otimes \sigma_{l,i} : x_{l,i} \mapsto x_{l,\tau(i)}$ for some element $x_{l,\tau(i)} \in L_{l,\tau(i)}$. As these nonpalindromic terms can be grouped by products of identical pairs in $L_{l,i} \times L_{l,\tau(i)}$, we get

$$(x_l (Id \otimes \sigma_l)(x_l))^{\frac{\sum_{0 \le i < 2s} q_l^i}{2}} \mapsto ((x_{l,i}^{\frac{\sum_{0 \le i < 2s} q_l^i}{2} + \sum_{0 \le i < 2s} q_l^{n_i} q_l^{i}})_{\text{palindromic } i}, (x_{l,\tau(i)}^{\frac{2 \sum_{0 \le i < 2s} q_l^i}{2}}, x_{l,i}^{\frac{2 \sum_{0 \le i < 2s} q_l^i}{2}})_{\text{nonpalindromic } \{i, \tau(i)\}})$$

On the other hand, for palindromic indexes, by $2s$-periodicity of $\theta$, we have $x_{l,i}^{\sum_{0 \le i < 2s} q_l^i} = x_{l,i}^{\sum_{n_i \le i < 2s + n_i} q_l^i}$. So we get $x_{l,i}^{\frac{\sum_{0 \le i < 2s} q_l^i + \sum_{0 \le i < 2s} q_l^{n_i} q_l^{i}}{2}} = x_{l,i}^{\sum_{0 \le i < 2s} q_l^i}$. Since the chinese remainder isomorphism maps $y_l$ i.e. $Norm_{K_l/F_l}(x_l)$ to $(x_{l,i}^{\sum_{0 \le i < 2s} q_l^i})_i$, we get in the end $Norm_{K_l/F_l}(\zeta_l)^{\frac{q-1}{2}} = y_l$.

We deduce from this equality and Euler's criterion that the norm $Norm_{K_l/F_l}(\zeta_l)$ is a square in $F_l^*$, if and only if $y_l = 1$. □

**Corollary 55** When $k$ is even, there are no selfdual skew cyclic codes in $E_k$.
In order to take advantage of this basis, we will enumerate the s-dimensional subvector spaces of V in a slightly different manner. Those spaces are parametrized by the matrices M in reduced row echelon form of size s × (2s), but we shall further split M and write it as a block matrix as follows:

$$M = \begin{pmatrix} A & B \\ 0 & C \end{pmatrix}.$$

Here A, B and C all have s columns and the horizontal separation is positioned in such a way that the last line of A is not identically zero. The matrices A and C are then reduced row echelon matrices of size d × s and (s-d) × s respectively (for some d). Besides, the columns of B in front of the pivots of C all vanish. Conversely, if we choose A, B and C satisfying the above conditions, the resulting block matrix M will be in reduced row echelon form. In other words, there is a bijection between the matrices M, on the one hand, and the triples (A, B, C), on the other hand; in the sequel, we will constantly rely on it to enumerate the M.

**Remark 3.16** At the level of cardinalities, the above bijection leads to the (classical) formula

$$\begin{bmatrix} 2s \\ s \end{bmatrix}_{q_F} = \sum_{d=0}^{s} q_F^{d^2} \cdot \begin{bmatrix} s \\ d \end{bmatrix}_{q_F}^2.$$

The (A, B, C)-presentation is quite interesting for our purpose because the isotropy condition translates to the equations:

$$AB^{\mathrm{tr}} + BA^{\mathrm{tr}} = 0 \qquad (3.5)$$

$$AC^{\mathrm{tr}} = 0 \qquad (3.6)$$

Equation (3.6) means that the row-span of A should be orthogonal to the row-span of C for the standard scalar product on $F^s$. Since those two spaces have complementary dimension, we conclude that RowSpan(C) must be the orthogonal of RowSpan(A). Given that, in addition, C must also be in reduced row echelon form, we conclude that C is uniquely determined by A: it is the reduced row echelon basis of RowSpan(A)$^\perp$.

Once C is known, one also knows its pivots and the shape of B is determined. Equation (3.5) then appears as a linear equation on the entries of B, which can be easily solved using Gaussian elimination. All of this leads to Algorithm 4.

<caption>**Algorithm 4:** Iterator over maximal isotropic spaces (Euclidean case)</caption>

1: A ← iterator over reduced row echelon matrices over F with s columns

2: while A ← next(A):

3: C ← reduced row echelon basis of RowSpan(A)$^\perp$

4: B ← iterator over solutions of (3.5) with vanishing columns in front of pivots of C

5: while B ← next(B):

6: yield $\begin{pmatrix} A & B \\ 0 & C \end{pmatrix}$
*Proof.* If $k$ is even, $\mathbf{E}_k$ factors as follows:

$$ \mathbf{E}_k \approx \prod_{l, P_l(\pm 1) != 0} (\mathbf{K}[Y]/(P_l(Y))[X; \theta])/(X^r - Y) \times \mathbf{K}[X^{\pm 1}; \theta]/(X^r + 1) \times \mathbf{K}[X^{\pm 1}; \theta]/(X^r - 1) $$

So there are no selfdual skew codes in $\mathbf{K}[X^{\pm 1}; \theta]/(X^r + 1) \times \mathbf{K}[X^{\pm 1}; \theta]/(X^r - 1)$. Indeed, noting $l_{-1}$ the index corresponding to the root $-1$ of $Y^k - 1$, we have: $\delta_{l_{-1}} = \text{Norm}_{\mathbf{K}_{l_{-1}}/\mathbf{F}_{l_{-1}}}(\zeta_{l_{-1}})\delta_{\mathbf{K}_{l_{-1}}/\mathbf{F}_{l_{-1}}}$ where $\zeta_{l_{-1}}$ satisfies: $\theta(\zeta_{l_{-1}}) = x_{l_{-1}}(\text{Id} \otimes \sigma_l)(x_{l_{-1}})\zeta_{l_{-1}}$, $x_{l_{-1}}$ satisfies $\text{Norm}_{\mathbf{K}_{l_{-1}}/\mathbf{F}_{l_{-1}}}(x_{l_{-1}}) = -1$. As shown in the lemma 54: $\text{Norm}_{\mathbf{K}_{l_{-1}}/\mathbf{F}_{l_{-1}}} (\zeta_{l_{-1}})$ is not a square in $\mathbf{F}_{l_{-1}}^*$. So $\delta_{\mathbf{K}_{l_{-1}}/\mathbf{F}_{l_{-1}}}$ and $\delta_{l_{-1}}$ cannot be squares in $\mathbf{F}_{l_{-1}}^*$ simultaneously and we can conclude by proposition 50. □

The following tables summarize the results we can deduce from Proposition 50 and Lemmas 51, 52, 53, 54

In the Euclidean case, i.e. for $y_l = \pm 1$:

<table><thead><tr><th></th><th>[F : F<sub>p</sub>] even</th><th>[F : F<sub>p</sub>] odd</th></tr></thead><tbody><tr><td>s even</td><td>False</td><td>True</td></tr><tr><td>s odd</td><td>False</td><td>$p \equiv 3(4)$</td></tr></tbody></table>

In the Hermitian case, i.e. for $y_l \neq \pm 1$:

<table><thead><tr><th></th><th>[F : F<sub>p</sub>] even</th><th>[F : F<sub>p</sub>] odd</th></tr></thead><tbody><tr><td>s even</td><td>True</td><td>False</td></tr><tr><td>s odd</td><td>True</td><td>$p \equiv 1(4)$</td></tr></tbody></table>

In the Hermitian case:

<table><thead><tr><th></th><th>[F<sub>l</sub> : F<sub>p</sub>] always even</th></tr></thead><tbody><tr><td>s even or odd</td><td>True</td></tr></tbody></table>

### 7.1.3 Counting selfdual skew codes in the palindromic case

When maximal isotropic spaces exist in an ambient $\mathbb{F}_q$-vector space, their number is given by Segre's formulas [Seg59] [Ple65] [Ann09].

**Proposition 56** Number $\mathcal{I}so_d$ of maximal isotropic spaces of dimension $d$:

In the Euclidean case, i.e. for $y_l = \pm 1$:

$$ \left\{ \begin{array}{ll} \text{In even characteristic: } \mathcal{I}so_d = \prod_{i=1}^{d} (q^i + 1) & (7.3) \\ \text{In odd characteristic: } \mathcal{I}so_d = \prod_{i=0}^{d-1} (q^i + 1) & \end{array} \right. $$
Regarding complexity, it is clear that, in the worst case, an iteration of Algorithm 4 requires at most $O(r^6)$ operations in $F$ since it only involves Gaussian elimination in dimension at most $O(r^2)$. However, in most cases, an iteration only consists in going from one solution $B$ to the next one; once a basis of the space of solutions has been computed, this costs only $O(r^2)$ operations in $F$.

**Remark 3.17** Denoting by $d$ the number of rows of $A$, one can prove that the linear system (3.5) consists of $\frac{d(d+1)}{2}$ linearly independent equations. Therefore, the set of admissible $B$ is a $F$-vector space of dimension $\frac{d(d-1)}{2} = \binom{d}{2}$; hence it has cardinality $q_F^{\binom{d}{2}}$. From this, we derive that the number of isotropic subspaces of $V$ of dimension $s$ is equal to

$$ \sum_{d=0}^{s} q_F^{\binom{d}{2}} \begin{bmatrix} s \\ d \end{bmatrix}_{q_F} . $$

Comparing with Segre's formula (see Theorem 3.4), we find the identity

$$ \prod_{d=0}^{s-1} (1 + q_F^d) = \sum_{d=0}^{s} q_F^{\binom{d}{2}} \begin{bmatrix} s \\ d \end{bmatrix}_{q_F} $$

which is actually a special case of the well-known polynomial identity [PA71]:

$$ \prod_{k=0}^{n-1} (1 + q^k t) = \sum_{k=0}^{n} q^{\binom{k}{2}} \begin{bmatrix} n \\ k \end{bmatrix}_{q} t^k. \qquad (3.7) $$

As a byproduct, our approach then provides a bijective proof of this identity when $t = 1$ and $q$ is a power of a prime number.

### 3.4.3 The Hermitian case

We now equip $F$ with a nontrivial involution $\sigma: F \to F$ and assume that the pairing $\langle \cdot, \cdot \rangle$ on $V$ is $\sigma$-sesquilinear. In this new situation, all the discussion of Subsection 3.4.2 applies, except that the Equations (3.5) and (3.6) have to be replaced by the following ones:

$$ A\sigma(B^{\mathrm{tr}}) + B\sigma(A^{\mathrm{tr}}) = 0 \qquad (3.8) $$

$$ A\sigma(C^{\mathrm{tr}}) = 0 \qquad (3.9) $$

As in the Euclidean case, it turns out that Equation (3.9) fully determines $C$; precisely $C$ is the reduced row echelon basis of RowSpan($\sigma(A)$)$^\perp$. Similarly, Equation (3.8) provides a linear system on the entries on $B$ but we need to careful that it is $F^\sigma$-linearity and not $F$-linearity as before. Anyway, the system can equally be solved using Gaussian elimination.

Taking these remarks into account, we end up with Algorithm 5

**Remark 3.18** Similarly to the Euclidean case, our approach gives a bijective proof of the numerical identity

$$ \prod_{d=0}^{s-1} (1 + q_F^{d+1/2}) = \sum_{d=0}^{s} q_F^{d^2/2} \begin{bmatrix} s \\ d \end{bmatrix}_{q_F} $$
In the Hermitian case, i.e. for $y_l \neq \pm 1$:

$$ \left\{ \begin{array}{ll} \text{In even characteristic: } \mathcal{I}so_d = \prod_{i=1}^{d} (q^{i+1/2} + 1) & (7.4) \\ \text{In odd characteristic: } \mathcal{I}so_d = \prod_{i=0}^{d-1} (q^{i+1/2} + 1) & \end{array} \right. $$

For sake of completeness, we recall the proof in odd characteristic. We need the following lemma.

**Lemma 57** Number $\mathcal{I}soVect_d$ of isotropic vectors in an ambient $\mathbb{F}_q$-vector space in odd characteristic:

In the Euclidean case: $\mathcal{I}soVect_d = (q^d - 1)(q^{d-1} + 1)$

In the Hermitian case: $\mathcal{I}soVect_d = (q^d - 1)(q^{d-1+1/2} + 1)$

*Proof.* In odd characteristic, given an isotropic base $((u_i)_{0 \le i < d}, (v_i)_{0 \le i < d})$ corresponding to the Witt decomposition 46 of the ambient space of dimension $2d$, in $d$ hyperplanes $H_i :=< u_i, v_i >$ such that $\mathbf{F}_l^{2s} \simeq \oplus_{0 \le i < d} H_i$, an isotropic vector $((a_i)_{0 \le i < d}, (b_i)_{0 \le i < d})$ verifies:

In the Euclidean case: $\sum a_i b_j = 0$.

In the Hermitian case: $\sum \sigma_l(a_i)b_i + \sum a_i \sigma_l(b_i) = 0$. This corresponds to independent equations $\sum a_i \sigma_l(b_i) = \alpha$, for any anti-invariant $\alpha$, i.e. satisfying $\sigma_l(\alpha) = -\alpha$.

Hence we have the following counting.

In the Euclidean case, given a nonzero vector $y$, $x$ lies in a hyperplane of the vector space $\mathbf{F}_l^d$. We thus have $(q_l^d - 1)q_l^{d-1}$ solutions for $y$ nonzero and $(q_l^d - 1)$ additional non trivial solutions for $y$ equal to zero. Finally we get $\mathcal{I}soVect_d = (q_l^d - 1)(q_l^{d-1} + 1)$ nonzero isotropic vectors in the ambient space.

In the Hermitian case, a hyperplane over $\mathbf{F}_l$, has cardinal $q_l^{d-1}$, and the number of anti-invariant scalars in $\mathbf{F}_l$ is $q_l^{1/2}$ ($q_l$ is indeed a square because $P_l$ is palindromic and thus its roots can be counted pairwise in the Hermitian case). Hence given a nonzero vector $y$, we have $(q_l^d - 1)q_l^{d-1+1/2}$ solutions for $y$ nonzero and $(q_l^d - 1)$ additional non trivial solutions for $y$ equal to zero as in the Euclidean case. Finally we get $\mathcal{I}soVect_d = (q_l^d - 1)(q_l^{d-1+1/2} + 1)$ nonzero isotropic vectors. $\square$

*Proof.* (Segre's formulas) We start with an empty family $u$ of isotropic vectors of the ambient space. At each step $d$ from 0 to $s-1$ we pick an arbitrary isotropic vector among $\mathcal{I}soVect_{s-d}$ possibilities (as defined in 57) in the orthogonal complement of the isotropic space spanned by the family $u$ and append it to the family. It is readily seen that the family $u$ is free and totally
<caption>**Algorithm 5:** Iterator over maximal isotropic spaces (Hermitian case)</caption>

1: $\mathcal{A} \leftarrow$ iterator over reduced row echelon matrices over $F$ with $s$ columns
2: **while** $\mathcal{A} \leftarrow \text{next}(\mathcal{A})$:
3: &nbsp;&nbsp;&nbsp;&nbsp;3: $C \leftarrow$ reduced row echelon basis of $\text{RowSpan}(\sigma(\mathcal{A}))^{\perp}$
4: &nbsp;&nbsp;&nbsp;&nbsp;4: $\mathcal{B} \leftarrow$ iterator over solutions of (3.8) with vanishing columns in front of pivots of $C$
5: &nbsp;&nbsp;&nbsp;&nbsp;5: **while** $\mathcal{B} \leftarrow \text{next}(\mathcal{B})$:
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;6: $\text{yield} \begin{pmatrix} A & B \\ 0 & C \end{pmatrix}$

which is Equation (3.7) evaluated at $q = q_F$ and $t = \sqrt{q}$.

## 3.5 An implementation in SageMath

We implemented the algorithms of this section in SageMath. Our package is available at

https://plmlab.math.cnrs.fr/caruso/selfdual-skew-cyclic-codes

It consists in a main class instantiated with the extension $K/F$ of order $r$ and a palindromic polynomial of the center $P(X^r)$ in $F(X^{\pm r})$ of $K[X^{\pm 1}; \theta]$ as constructor parameters. It provides an iterator on all selfdual codes for the Ore algebra $K[X^{\pm 1}; \theta]/P(X^r)$. Hereunder, we present a bunch of examples covering all the encountered situations : palindromic Euclidean and palindromic Hermitian.

We start by loading our package and defining the relevant base rings.

```
sage: load("selforthogonal_codes.sage")
1

None
2

sage: q = s = 3; F = GF(q); Fy.<y> = F[]
3

sage: Q = F['z'].irreducibleElement(2*s, "adleman-lenstra")
4

sage: Q
5

z^6 + z^5 + z^4 + z^3 + z^2 + z + 1
6
```

**Case 3.19** Palindromic Euclidean: $q = 3$, $s = 3$ and $P(Y) = Y - 1$

```
sage: A = SelfDualCodes(y - 1, Q)
7

sage: iter = A.enumerate Selfdual codes()
8

sage: next(iter)
9

x^3 + (2*z^4 + 2*z^3 + z + 2)*x^2 + (2*z^5 + 2*z^3 + z + 1)*x + z^5 + z
10
  ^3 + z + 2

sage: next(iter)
11

x^3 + (2*z^3 + 2)*x^2 + (2*z^5 + 2*z^3 + z^2 + 1)*x + 2*z^5 + z^2
12
```

**Case 3.20** Palindromic Hermitian case: $q = 3$, $s = 3$ and $P(Y) = Y^2 + 1$

```
sage: A = SelfDualCodes(y^2 + 1, Q)
13

sage: iter = A.enumerate Selfdual codes()
14
```
isotropic. Once we have obtained a maximal isotropic family, Witt's decomposition theorem ensures that its rank, the Witt index, is an invariant equal to $s$. The number of maximal isotropic bases is thus equal to the product $\mathcal{P} : \prod_{1 \le d \le s} \mathrm{IsoVect}_d$ (as defined in 57). The general linear group of $GL_s(\mathbb{F}_q)$ acting freely and transitively on these maximal isotropic bases, the maximal isotropic spaces correspond exactly to its orbits. Dividing $\mathcal{P}$ by the cardinality of $GL_s(\mathbb{F}_q)$, we thus obtain Segre's formula stated above. $\square$

**Corollary 58** We apply Proposition 56 to our situation. The global number $\mathcal{N}$ of selfdual skew cyclic codes in $\mathbb{E}_k$ is equal to the product of the numbers of maximal isotropic spaces $V_l$ of dimension $s = r/2$ in palindromic $\mathbf{K}_l$, $\mathcal{N}_{V_l}$, times the product of the numbers of arbitrary subspaces $W_l$ over pairs of nonpalindromic spaces, $\mathcal{N}_{W_l}$.

$$ \mathcal{N} = |\{ \prod_{\{l|l=\tau(l)\}} \mathcal{N}_{V_l} \times \prod_{\{\{l,\tau(l)\}|l \neq \tau(l)\}} \mathcal{N}_{W_l} | W_l \text{ arbitrary, } V_l \text{ maximal isotropic} \}| $$

In a condensed form, we obtain the following number of selfdual skew cyclic codes in $\mathbb{E}_k$:

$$ \prod_{\{l|l=\tau(l), y_l=\pm 1\}} \prod_{i=0}^{s-1} (q_l^i + 1) \prod_{\{l|l=\tau(l), y_l \neq \pm 1\}} \prod_{i=0}^{s-1} (q_l^{i+1/2} + 1) \prod_{\{\{l,\tau(l)\}|l \neq \tau(l)\}} \sum_{k=0}^{k=r} \frac{(q_l^r - 1) \dots (q_l^{r-k+1} - 1)}{(q_l^k - 1) \dots (q_l - 1)} $$

**Example 59** For $\mathbf{K} = \mathbb{F}_{3^{2s}}$, $\theta: x \mapsto x^3$ and $\mathbf{K}^{\theta} = \mathbb{F}_3$, the number of selfdual skew cyclic codes grows as $O(q^{s(s-1)/2})$ as $s$ grows larger, whereas the number of skew cyclic codes (number of $s$ dimensional $\mathbb{F}_3$-vector subspaces of $\mathbb{F}_{3^{2s}}$) grows as $O(q^{s^2})$ as $s$ grows larger.

For $\mathbf{K} = \mathbb{F}_{3^6}$, $\theta: x \mapsto x^3$ and $\mathbf{K}^{\theta} = \mathbb{F}_3$, the number of selfdual skew cyclic codes in $\mathbb{E}_1 = \mathbf{K}[X; \theta]/(X^6 - 1)$ is: 80 among 33880 skew codes, whereas for $\mathbf{K} = \mathbb{F}_{3^{18}}$, $\theta: x \mapsto x^3$ and $\mathbf{K}^{\theta} = \mathbb{F}_3$, the number of selfdual skew cyclic codes in $\mathbb{E}_1 = \mathbf{K}[X; \theta]/(X^{18} - 1)$ is: 469740602936729600 among 791614563787525746761491781638123230424 skew codes.

**Remark 60** We recover also the number of selfdual cyclic codes from the case $r = 1$ in Segre's formula. We observe that, as we are in the separable case, $(X - 1)$ is always a palindromic factor of $(X^k - 1)$ of multiplicity 1. Thus there exist no selfdual cyclic codes at all in the separable case in $\mathbb{F}_p[X]/(X^k - 1)$. With regard to this fact, skew cyclic codes enjoy much more dual symmetries than cyclic codes. Nethertheless, the ratio of the number of skew cyclic codes over selfdual skew cyclic codes increases as fast as $O(q^{\frac{s^2+s}{2}})$ as $s$ grows larger. The best ratio is obtained for $s = 1$, and $q = 3$, in odd characteristic. In this case, half of the skew cyclic codes are selfdual skew cyclic codes.
<table><caption>Figure 1: Timings for the generation of one single code when $s = 2$</caption><thead><tr><th>P(Y)</th><th>q = 3</th><th>q = 5</th><th>q = 7</th><th>q = 3<sup>2</sup></th></tr></thead><tbody><tr><td>Y - 1</td><td>no codes.</td><td>no codes.</td><td>no codes.</td><td>no codes.</td></tr><tr><td>Y<sup>3</sup> - 1</td><td>inseparable</td><td>no codes.</td><td>no codes.</td><td>inseparable</td></tr><tr><td>Y<sup>5</sup> - 1</td><td>no codes.</td><td>inseparable</td><td>no codes.</td><td>no codes.</td></tr><tr><td>Y<sup>7</sup> - 1</td><td>no codes.</td><td>no codes.</td><td>inseparable</td><td>no codes.</td></tr><tr><td>Y<sup>9</sup> - 1</td><td>inseparable</td><td>no codes.</td><td>no codes.</td><td>inseparable</td></tr><tr><td>Y + 1</td><td>9 ms</td><td>9 ms</td><td>16 ms</td><td>21 ms</td></tr><tr><td>Y<sup>2</sup> + 1</td><td>16 ms</td><td>6 ms</td><td>15 ms</td><td>15 ms</td></tr><tr><td>Y<sup>3</sup> + 1</td><td>inseparable</td><td>26 ms</td><td>22 ms</td><td>inseparable</td></tr><tr><td>Y<sup>4</sup> + 1</td><td>18 ms</td><td>21 ms</td><td>35 ms</td><td>48 ms</td></tr><tr><td>Y<sup>5</sup> + 1</td><td>62 ms</td><td>inseparable</td><td>111 ms</td><td>128 ms</td></tr><tr><td>Y<sup>6</sup> + 1</td><td>inseparable</td><td>47 ms</td><td>59 ms</td><td>inseparable</td></tr><tr><td>Y<sup>7</sup> + 1</td><td>80 ms</td><td>300 ms</td><td>inseparable</td><td>250 ms</td></tr><tr><td>Y<sup>8</sup> + 1</td><td>463 ms</td><td>87 ms</td><td>113 ms.</td><td>108 ms</td></tr><tr><td>Y<sup>9</sup> + 1</td><td>inseparable</td><td>218 ms</td><td>125 ms</td><td>inseparable</td></tr></tbody></table>

```
sage: next(iter)

x^6 + (2*z^5 + 2*z + 1)*x^5 + (z^5 + z^4 + 2*z^2 + z + 1)*x^4 + (2*z^3 +
2)*x^3 + (2*z^5 + z^4 + z + 1)*x^2 + (2*z^5 + 2*z^4 + z^3 + 2*z)*x +
2*z^5 + z^4 + 2*z^3 + z^2 + 2*z
```

Benchmarks for a larger set of inputs are reported on Figures 1, 2 and 3; there were run on computer with Intel(R) Core(TM) i7-9750H CPU 2.60GHz processor x64 and 16 GB of RAM.

## 4 Enumeration of purely inseparable selfdual skew cyclic codes

We now address the case where $k$ is not coprime to the characteristic $p$. We aim at finding an enumeration algorithm of selfdual skew cyclic codes in this case too. If $k$ decomposes as $k'p^m$ with $k'$ coprime with $p$, it follows easily from the chinese remainder isomorphism

$$
\begin{align*}
\mathbf{E}_k &\approx \mathbf{K}[Y, X; \theta]/(Y^{k'} - 1, X^{rp^m} - Y) \\
&\approx (\mathbf{K}[Y, X; \theta]/(Y^{k'} - 1))/(X^r - Y^{\frac{1}{p^m}})^{p^m} \\
&\approx \left( \mathbf{K}[Y, X; \theta] / \prod_{1 \le l \le n} P_l(Y) \right) / (X^r - Y^{\frac{1}{p^m}})^{p^m} \\
&\approx \prod_{1 \le l \le n} (\mathbf{K}[Y, X; \theta]/P_l(Y)) / (X^r - Y^{\frac{1}{p^m}})^{p^m}
\end{align*}
$$
## 7.2 Enumerating selfdual skew cyclic codes

As we have to enumerate very large numbers of selfdual skew cyclic codes, we shall first ensure that our enumeration algorithms return uniformly distributed codes among all possible selfdual skew cyclic codes. Secondly we shall provide an iterative algorithm, that returns a new code at each iteration, with a low and constant complexity at each iteration. We use the keyword *next* to denote the operation which returns the next result on an iterator and *yield*, the operation that returns a generator object, to be iterated.

### 7.2.1 Enumeration in the nonpalindromic case

Let $W_0 \times W_0^\perp$ be the ambient Hermitian vector space. We want to enumerate all totally isotropic vector subspaces of $W_0 \times W_0^\perp$ of maximal dimension 2s.

**Algorithm 61** Enumeration of selfdual skew codes in the nonpalindromic case

**Input:** Iterator $I$ on all reduced echelon matrix $A$ of size $(s, 2s)$, Nonpalindromic polynomial $P_l$ generating the two-sided ideal in the skew cyclic algebra $E_{k,l}$, the skew cyclic algebra $E_k$

**Output:** $h$ is the next selfdual skew codes

1: $A \leftarrow \text{next } I$

2: $V \leftarrow \ker(A)$

3: $(e_i)_i \leftarrow \text{base of } V$

4: $f \leftarrow \text{leftlcm}((e_i)_i)$ in $K_l[X; \theta]/(P_l)$

5: $g \leftarrow P_l \cdot \text{right\_quo\_rem}(f)$

6: $g_{\text{star}} \leftarrow g^\bullet$

7: $\tilde{f} \leftarrow \text{lift of } f$ in $E_k$

8: $g_{\tilde{\text{star}}} \leftarrow \text{lift of } g_{\text{star}}$ in $E_k$

9: $h \leftarrow \text{leftlcm}(f, g_{\text{star}})$ in $E_k$

10: yield $h$

*Proof.* For any element $f$ in $E_{k,l}$, the elements $h$ in $E_{k,l}$ satisfying $f.h = 0$ constitute a right ideal generated by an element $g^\bullet$. It is clear from proposition 42 that selfdual skew codes are the codes $(I_f, I_g)$ for any $f$ in $E_{k,l}$. So the enumeration reduces to that of $F_l$-vector subspaces of $K_l$. We proceed to the latter enumeration using the bijection between $F_l$-vector subspaces of $K_l$, and reduced echelon matrices of dimension $s$ over $2s$ with entries in $F_l$. $\square$
<table><caption>Figure 2: Timings for the generation of one single code when $s = 3$</caption><thead><tr><th>P(Y)</th><th>q = 3</th><th>q = 5</th><th>q = 7</th><th>q = 3<sup>2</sup></th></tr></thead><tbody><tr><td>Y − 1</td><td>21 ms</td><td>no codes.</td><td>207 ms</td><td>no codes.</td></tr><tr><td>Y<sup>3</sup> − 1</td><td>inseparable</td><td>no codes.</td><td>42 ms</td><td>inseparable</td></tr><tr><td>Y<sup>5</sup> − 1</td><td>101 ms</td><td>inseparable</td><td>129 ms</td><td>no codes.</td></tr><tr><td>Y<sup>7</sup> − 1</td><td>195 ms</td><td>no codes.</td><td>inseparable</td><td>no codes.</td></tr><tr><td>Y<sup>9</sup> − 1</td><td>inseparable</td><td>no codes.</td><td>342 ms</td><td>inseparable</td></tr><tr><td>Y + 1</td><td>no codes.</td><td>21 ms</td><td>no codes.</td><td>56 ms</td></tr><tr><td>Y<sup>2</sup> + 1</td><td>152 ms</td><td>12 ms</td><td>36 ms</td><td>32 ms</td></tr><tr><td>Y<sup>3</sup> + 1</td><td>inseparable</td><td>57 ms</td><td>no codes.</td><td>inseparable</td></tr><tr><td>Y<sup>4</sup> + 1</td><td>38 ms</td><td>47 ms</td><td>74 ms</td><td>141 ms</td></tr><tr><td>Y<sup>5</sup> + 1</td><td>no codes.</td><td>inseparable</td><td>no codes.</td><td>317 ms</td></tr><tr><td>Y<sup>6</sup> + 1</td><td>inseparable</td><td>101 ms</td><td>139 ms</td><td>inseparable</td></tr><tr><td>Y<sup>7</sup> + 1</td><td>no codes.</td><td>398 ms</td><td>inseparable</td><td>601 ms.</td></tr><tr><td>Y<sup>8</sup> + 1</td><td>209 ms</td><td>270 ms</td><td>270 ms</td><td>280 ms</td></tr><tr><td>Y<sup>9</sup> + 1</td><td>inseparable</td><td>450 ms</td><td>no codes.</td><td>inseparable</td></tr></tbody></table>

<table><caption>Figure 3: Timings for the generation of one single code when $s = 4$</caption><thead><tr><th>P(Y)</th><th>q = 3</th><th>q = 5</th><th>q = 7</th><th>q = 3<sup>2</sup></th></tr></thead><tbody><tr><td>Y − 1</td><td>no codes.</td><td>no codes.</td><td>no codes.</td><td>no codes.</td></tr><tr><td>Y<sup>3</sup> − 1</td><td>inseparable</td><td>no codes.</td><td>no codes.</td><td>inseparable</td></tr><tr><td>Y<sup>5</sup> − 1</td><td>no codes.</td><td>inseparable</td><td>no codes.</td><td>no codes.</td></tr><tr><td>Y<sup>7</sup> − 1</td><td>no codes.</td><td>no codes.</td><td>inseparable</td><td>no codes.</td></tr><tr><td>Y<sup>9</sup> − 1</td><td>inseparable</td><td>no codes.</td><td>no codes.</td><td>inseparable</td></tr><tr><td>Y + 1</td><td>59 ms</td><td>49 ms</td><td>58 ms</td><td>177 ms</td></tr><tr><td>Y<sup>2</sup> + 1</td><td>78 ms</td><td>29 ms</td><td>89 ms</td><td>69 ms</td></tr><tr><td>Y<sup>3</sup> + 1</td><td>inseparable</td><td>128 ms</td><td>90 ms</td><td>inseparable</td></tr><tr><td>Y<sup>4</sup> + 1</td><td>88 ms</td><td>108 ms</td><td>174 ms</td><td>412 ms</td></tr><tr><td>Y<sup>5</sup> + 1</td><td>220 ms</td><td>inseparable</td><td>336 ms</td><td>723 ms</td></tr><tr><td>Y<sup>6</sup> + 1</td><td>inseparable</td><td>200 ms</td><td>388 ms</td><td>inseparable</td></tr><tr><td>Y<sup>7</sup> + 1</td><td>286 ms</td><td>387 ms</td><td>inseparable</td><td>1367 ms</td></tr><tr><td>Y<sup>8</sup> + 1</td><td>406 ms.</td><td>551 ms</td><td>586 ms</td><td>2159 ms</td></tr><tr><td>Y<sup>9</sup> + 1</td><td>inseparable</td><td>691 ms</td><td>784 ms</td><td>inseparable</td></tr></tbody></table>
### 7.2.2 Enumeration in the palindromic case in odd characteristic

Let $W_0$ be the ambient Hermitian vector space whose Witt decomposition 46 is given by:
$W_0 \cong \bigoplus_{1 \le i \le s} H_i$, where $H_i$ are hyperbolic planes (Cf. the definition in 3). We want to enumerate
all totally isotropic vector subspaces of $W_0$ of maximal dimension $s$.

**Algorithm 62** Direct sum decomposition of hyperbolic planes in the Hermitian case

**Input:** $W_0$: The ambient Hermitian vector space

**Output:** $U, V$ build a uniformly random direct sum decomposition of hyperbolic planes

1: $U, V, W \leftarrow []$, $[]$, $W_0$

2: **while** $W \neq 0$ **do**

3: Pick two random vectors $u$ and $v$ in $W$

4: **if** $<u, v> \neq 0$ and $(u, v)$ is free **then**

5: Solve the equation ($\mathcal{E}$) $<u + \lambda v, u + \lambda v> = 0$ for $\lambda$ (Hermitian quadratic equation)

6: $u \leftarrow u + \lambda v$

7: $u \leftarrow u - \lambda v$

8: Solve $<u, \nu v> = 1$ for $\nu$ (linear)

9: $v \leftarrow \nu v$, now $(u, v)$ is a hyperbolic pair

10: $U \leftarrow U + [u]$, $V \leftarrow V + [v]$

11: $W \leftarrow <U, V>^\perp \subset W_0$

12: **end if**

13: **end while**

**Proposition 63** The algorithm terminates with probability 1 and if it terminates, it is correct

We need the following lemmas to determine the probability for the quadratic equation at line
5 of the algorithm 62 to be solvable and to solve it when it is possible.

**Lemma 64** Picking then two random vectors $u$ and $v$ that are not collinear in $W$ of dimension $2d$
and such that $<u, v> \neq 0$ is an event of probability $\frac{(q_l^{2d}-1)(q_l^{2d}-q_l^{2d-1})}{q_l^{4d}}$. Moreover this probability
is always greater than $\frac{3}{8}$

*Proof.* This is the number of pairs of vectors with a first nonzero vector and another vector not contained in the hyperplane defined by the equation $<u, v> = 0$, divided by the number of pairs of vectors in $\mathbf{F}_l^{2d}$. Moreover, the probability increases with $q_l$ and $d$, and its value at $q_l = 2$ and $d = 1$ is $\frac{3}{8}$. $\square$
that we can recover an enumeration algorithm for any $k$ by combining the separable case and the case where $k = p^m$ (purely inseparable case).

## 4.1 Enumeration of purely inseparable selfdual skew cyclic codes

In order to solve the purely inseparable case, we follow a factorization approach, inspired by but slightly different from that of article [BU14]. We introduce twisted skew separable codes $E_{k,l}^{(\xi X^t)}$, that are slight generalizations of previously considered skew separable codes. They are defined as skew separable codes of $E_k^{(l)}$ corresponding to the usual adjunction on $E_k^{(l)}$ composed with the conjugation by $\xi X^t$ for $\xi \in K_l$ and $t \in \{0, s\}$. We will then obtain all inseparable selfdual codes as products of twisted skew separable selfdual codes.

**Definition 4.1** We fix parameters $t \in \{0, s\}$, $\xi \in K_l$. We denote by $E_{k,l}^{(\xi X^t)}$, the space $E_k^{(l)}$ equipped with the $\xi X^t$-twisted bilinear form $(\kappa, \rho) = \text{Trace}_{K_l/F_l}(\zeta \cdot \xi \kappa \theta^t(\sigma_l(\rho)))$.

The corresponding adjunction is $f^{\bullet X^t \xi^{-1}} = X^t \xi^{-1} \zeta^{-1} \sum_i X^{-i} \sigma_l(f_i) \zeta \xi X^{-t}$; we have

$$ (\kappa, f(\rho))_{\mathbf{F}_l}^{(\xi X^t)} = (f^{\bullet X^t \xi^{-1}}(\kappa), \rho)_{\mathbf{F}_l}^{(\xi X^t)}. $$

In the sequel, we will take $\sigma_l(\xi) = \xi$, and if $t = s \theta^t(\xi) = -\xi$, so that the $\xi X^t$-twisted bilinear form enjoys following symmetries:

* it is Euclidean if $y_l = \pm 1$ and $t = 0$,

* it is Hermitian if $y_l \neq \pm 1$ and $t = 0$,

* it is skew-Euclidean if $y_l = \pm 1$ and $t = s$,

* it is skew-Hermitian if $y_l \neq \pm 1$ and $t = s$.

**Remark 4.2** Reusing the method of Remark 3.5, we can compute the number of twisted codes when $k = 1$. For example, in the skew-Euclidean case, it is given by

$$ \frac{\text{Card}(\text{Sp}_{2s}(\mathbf{F}_l))}{q_l^{s(s+1)/2} \cdot \text{Card}(\text{GL}_s(\mathbf{F}_l))} = \prod_{d=1}^{s} (1 + q_l^d) $$

where $\text{Sp}_{2s}$ stands for the symplectic group. We refer to [Han05] for more details.

**Lemma 4.3** The set of $\xi$-twisted selfdual skew cyclic codes is in bijection with the set of nontwisted selfdual skew cyclic codes and their intersection is empty if $\theta^s(\xi) \neq \xi$.

*Proof.* We have for any monic skew polynomial $f$ of degree $s$ generating a selfdual code $C_f$ of $E_k^{(l)}$:

$$ f\xi f^{\bullet \xi^{-1}} \xi^{-1} = \frac{f f^{\bullet}}{X^s(X^r - 1)} X^s (X^r - 1) = f(0)X^s(X^r - 1) $$

where $f(0)$ denotes the constant term in $f$. As we assume $\xi$ to be $\sigma_l$-invariant, by Hilbert-90, we can solve the equation $\gamma\sigma_l(\gamma) = \xi$ for $\gamma$ in $K_l^{\theta^s}$. Noting then $g = \sigma_l(\gamma)f\gamma^{-1}$, we get a bijection $f \mapsto g$
**Lemma 65** (Cf. 5) The equation $(\mathcal{E}) < u + \lambda v, u + \lambda v > = 0$ has a solution in $\lambda$ for any vector $u$ and $v$ in the ambient Hermitian vector space. Denoting $\text{Norm}_{\mathbf{F}_l/\mathbf{F}_l^{\sigma_l}}^{-1}(x)$ a preimage by the norm map of the element $x$, a solution is given by the formula:

$$ \lambda = \frac{\text{Norm}_{\mathbf{F}_l/\mathbf{F}_l^{\sigma_l}}^{-1} \left( \frac{N(<u,v>)}{<v,v>} \left( \frac{N(<u,v>)}{<v,v>} - <u,u> \right) \right) - \frac{N(<u,v>)}{<v,v>}}{<v,u>} $$

*Proof.* $(\mathcal{E})$ can be rewritten as $<u, u> + \text{Trace}_{\mathbf{F}_l/\mathbf{F}_l^{\sigma_l}}(\lambda <v, u>) + \text{Norm}_{\mathbf{F}_l/\mathbf{F}_l^{\sigma_l}}(\lambda) <v, v> = 0$
Noting $\mu := \lambda <v, u>$, $N(x) := \text{Norm}_{\mathbf{F}_l/\mathbf{F}_l^{\sigma_l}}(x)$, $\text{Tr}(x) := \text{Trace}_{\mathbf{F}_l/\mathbf{F}_l^{\sigma_l}}(x)$ and $\alpha := \mu + \frac{N(<u,v>)}{<v,v>}$, it follows:

$$ \begin{align*} N(\mu) &= (\alpha - \frac{N(<u,v>)}{<v,v>})(\sigma_l(\alpha) - \frac{N(<u,v>)}{<v,v>}) \\ N(\mu) &= N(\alpha) - \frac{N(<u,v>)}{<v,v>} \text{Tr}(\alpha) + \left( \frac{N(<u,v>)}{<v,v>} \right)^2 \\ \text{Tr}(\mu) &= \text{Tr}(\alpha) - 2 \frac{N(<u,v>)}{<v,v>} \end{align*} $$

Injecting the trace and norm of $\mu$ in $(\mathcal{E})$, we obtain:

$$ (\mathcal{E}) \iff <u, u> + \text{Tr}(\alpha) - 2 \frac{N(<u,v>)}{<v,v>} + (N(\alpha) - \frac{N(<u,v>)}{<v,v>} \text{Tr}(\alpha) + \left( \frac{N(<u,v>)}{<v,v>} \right)^2) \frac{<v,v>}{N(<u,v>)} = 0 $$

$$ (\mathcal{E}) \iff N(\alpha) = \frac{N(<u,v>)}{<v,v>} \left( \frac{N(<u,v>)}{<v,v>} - <u, u> \right) $$

One can solve this last equation for $\alpha$ per surjectivity of the norm. $\square$

*Proof.* (of Proposition 63) We initialize $W$ to $W_0 := K_l$. We pick two random vectors $u$ and $v$ that are not collinear in $W$ of dimension $2d$ and such that $<u, v> \neq 0$.

Either $u$ and $v$ are both isotropic and they can be renormalized into a hyperbolic pair (Cf. 3). Indeed by surjectivity of the norm, there exist an element $\alpha \in \mathbf{F}_l$ such that $<u, v> = \alpha\sigma_l(\alpha)$, so that $(\frac{u}{\alpha}, \frac{v}{\alpha})$ is a hyperbolic pair.

Or one of them is not isotropic, say $v$ (wlog), so that $<v, v> \neq 0$. In this latter case we solve the equation $(\mathcal{E})$ for $\lambda$ and replace $u$ by $u + \lambda v$ and $v$ by $u - \lambda v$, building as previously a hyperbolic pair.

We then append the hyperbolic plane $<u, v>$ to the growing direct sum of hyperbolic planes $<U, V>$ and take its orthogonal $W'$ in $W_0$. Using Witt decomposition 46, we get $W' \simeq \bigoplus_{1 \le i \le d-1} H_i$, so we can reset $W$ to $W'$ and repeat the process until $W$ is equal to zero. Witt decomposition theorem 46, guarantees that this process ends properly and that we end up with a direct sum of hyperbolic planes. Finally at each step the hyperbolic plane picked is uniformly distributed among all available hyperbolic planes, the set of available hyperbolic planes has a constant cardinal and it is itself uniformly distributed relatively to the last picked
between nontwisted and $\xi$-twisted selfdual skew cyclic codes:

$$gg^{\bullet, \xi} = \sigma_l(\gamma) ff^{\bullet} \frac{1}{\sigma_l(\gamma)} = f(0) X^s (X^r - 1)$$

Moreover, if we assume $\theta^s(\xi) \neq \xi$ and $ff^{\bullet} = ff^{\bullet, \xi} = f\xi^{-1}f^{\bullet, \xi} = 0$ in $E_k^{(l)}$, then by evaluating lifts at 0, we get $f(0) = f(0)^{\frac{\theta^s(\xi)}{\xi}}$, and so $f(0) = 0$ and thus $f = 0$, which contradicts the hypothesis. □

Algorithm 6 is an iterator that enumerates selfdual skew cyclic codes sitting in $E_k$. It is exhaustive, in the sense that it lists every selfdual code at least once, but it is slightly redundant.

<caption>**Algorithm 6:** Enumeration of purely inseparable selfdual skew cyclic codes</caption>

1: $C \leftarrow$ array of length $p^m$ of maps of iterators on all twisted codes indexed by all possible twists $\xi X^s(\frac{\deg(f)}{s}) \% 2$ where $\xi$ can be chosen among all representatives of $\mathbb{P}_{\mathbb{F}_l}^r$ in $K_l$ if $\frac{\deg(f)}{s}$ is even and otherwise among all representatives of $\mathbb{P}_{\mathbb{F}_l}^r$ in $K_l$ that are antisymmetric relatively to $\theta^s$.
2: **procedure** RUNTHROUGHREMAININGCODES($f$)
3:     $i \leftarrow \frac{\deg(f)}{s}$
4:     **if** $i = p^m$ **then**
5:         **yield** $f$
6:     **else**
7:         **while** $f_i \leftarrow \text{next}(C[i][f(0)X^{s(i\%2)}])$ **do**
8:             **RunThroughRemainingCodes**($f_if$)
9:     **RunThroughRemainingCodes**($1$)

**Theorem 4.4** Algorithm 6 is correct and exhaustive

*Proof.* In order to enumerate all inseparable selfdual skew cyclic codes, at the cost of some redundancy, we can assume without loss of generality (See the last part of the proof, hereunder) that the general solution is a product of twisted selfdual skew cyclic codes $f_1 \dots f_n$, where the $f_i$ are left monic. We start by solving the equation $f_n f_n^{\bullet} \equiv 0 \mod (X^r - 1)$. This has been done in the preceding section. Now we obtain a scalar $\kappa_n = \frac{f_n f_n^{\bullet}}{X^s(X^r - 1)}$ which is equal to $f_n(0)$. Let $\bullet_{\kappa_n}$ be defined by $f_i^{\bullet_{\kappa_n}} = \sigma_l(\kappa_n) f_i^{\bullet_{\kappa_n}} \equiv 1$. The equation becomes $f_{n-1} X^s f_{n-1}^{\bullet_{\kappa_n}} = 0(X^r - 1)$. Solving it, we now obtain a scalar $\kappa_{n-1} = \frac{f_{n-1} X^s f_{n-1}^{\bullet_{\kappa_n}}}{X^{r+s}(X^r - 1)}$. At the next step, the monomials $X^s$ cancel, and we are back in the Hermitian case: $f_{n-2} f_{n-2}^{\bullet_{\kappa_{n-1} \kappa_n}} = 0(X^r - 1)$. And so on so forth, getting alternatively a skew Hermitian (resp. skew Euclidean) and a Hermitian (resp. Euclidean) bilinear form. We have to check that the $\kappa_i$ satisfy the required symmetry for the selfdual skew cyclic codes to exist. A monic polynomial $f$ satisfying the product criterion: $ff^{\bullet_{\kappa_n} X^t} = 0$ in $E_{k,l}^{(\kappa_n X^t)}$ has a constant term $f(0)$ satisfying:

$$(X^s + \dots + f(0)) \kappa_n X^t (X^r f(0) + \dots + X^s) = \theta^s(\kappa_n) \theta^{s+t}(f(0)) X^s X^t X^r + f(0) \kappa_n X^t X^s \\ \propto X^{r+s+t} - X^{s+t}.$$
hyperbolic plane (by Witt decomposition 46), so the final direct sum of hyperbolic planes obtained
is uniformly distributed as well. □

**Mean complexity 66** The mean complexity $\mathcal{C}$ in $s$ of the algorithm is less than a constant
times the complexity of taking the orthogonal at each step, as the random event at each
step is uniformly distributed and has a nonzero minimal probability (greater than $\frac{3}{8}$). Thus
$\mathcal{C} = \mathcal{O}(\sum_{1 \le i \le s} s^3) = \mathcal{O}(s^4)$

**Algorithm 67** Direct sum decomposition of hyperbolic planes in the Euclidean case

**Input:** $W_0$: The ambient Euclidean vector space

**Output:** $U, V$ build a uniformly random direct sum decomposition of hyperbolic planes

1: $U, V, W \leftarrow []$, [], $W_0$

2: **while** $W \neq 0$ **do**

3: Pick two random vectors $u$ and $v$

4: **if** $<u, v> \neq 0$ and $(u, v)$ is free **then**

5: Solve $<u + \lambda v, u + \lambda v> = 0$ for $\lambda$ (Euclidean quadratic equation)

6: **if** The discriminant is a square in $\mathbf{F}_l^*$ **then**

7: $u \leftarrow u + \lambda v$

8: $u \leftarrow u - \lambda v$

9: Solve $<u, \nu v> = 1$ for $\nu$ (linear)

10: $v \leftarrow \nu v$, now $(u, v)$ is a hyperbolic pair

11: $U \leftarrow U + [u]$, $V \leftarrow V + [v]$

12: $W \leftarrow \langle u, v \rangle^{\perp}$

13: **end if**

14: **end if**

15: **end while**

**Proposition 68** The algorithm terminates with probability 1 and if it terminates, it is correct

We need the following lemmas to determine the probability for the quadratic equation at line
5 of the algorithm 67 to be solvable and to solve it when it is possible.

**Lemma 69** If $-1$ is a square in $\mathbf{F}_l^*$, The probability $\mathcal{P}_{q_l, s}$ for the discriminant of the equation to be square at each step $i \in \{1, \dots, s\}$ is equal to $\mathcal{P}_{q_l, i} = \frac{(q_l^{i-1}+1)(q_l^{2i-1}+q_l^i-q_l^{i-1}-q_l)(q_l+1)}{2(q_l^i+1)(q_l^{2i-1}-1)}$. Moreover this probability decreases with $i$ and $q_l$ and we have $\lim_{s \to \infty, q_l \to \infty} \mathcal{P}_{q_l, s} = \frac{1}{2}$
Thus we have:

$$ \theta^s(f(0)) = -f(0) \quad \text{for } \theta^s(\kappa) = \kappa, t = 0 \qquad (4.1) $$

$$ \theta^s(\kappa) = -\kappa \quad \text{for } t = s \text{ (symplectic case)} \qquad (4.2) $$

$$ -f(0)\kappa = \theta^s(\kappa f(0)) \quad \text{for } t = 0 \qquad (4.3) $$

If we start with $\kappa = 1$, we get the symplectic case from (4.1) and (4.2) with $\kappa$ satisfying $\theta^s(\kappa) = -\kappa$, at the next step. We have then an orthogonal case, then again alternatively a symplectic case with $\kappa$ satisfying $\theta^s(\kappa) = -\kappa$ from (4.3), etc.

We now prove that the algorithm is exhaustive. We observe that the projection

$$ \mathbf{E}_k^{(l)} = \mathbf{K}_l[X^{\pm 1}; \theta]/(X^r - 1)^{p^m} \longrightarrow \mathbf{K}_l[X^{\pm 1}; \theta]/(X^r - 1) = \mathbf{E}_1^{(l)} \\ f \longmapsto \bar{f} $$

preserves the selforthogonality property. Noting $f_{p^m} := \bar{f}$ the unique lift of $\bar{f}$ on the basis $(X^i)_{0 \le i < r}$, we have a factorization $f_{p^m} = r_{p^m} g_{p^m}$ for a skew polynomial $r_{p^m}$ of degree strictly less than $s$ and a selfdual skew cyclic code $g_{p^m}$ in $E_1$. Indeed any selforthogonal subspace of $\mathbf{E}_1^{(l)}$ of dimension strictly less than $r$, corresponding to a monic skew polynomial $f$ can be extended, by Witt's decomposition, to a maximal isotropic space corresponding to a selfdual monic skew polynomial $g$ of degree $s$. Now this vector space inclusion corresponds by duality to a factorization $\bar{f} = rg$ for a skew polynomial $r$ of degree strictly less than $s$. Expressing $(X^r - 1)$ as a product of the selfdual codes $g_{p^m}$, $\frac{g_{p^m}^* g_{p^m}}{g_{p^m}(0)X^s}$ we get that any selforthogonal skew cyclic code $f \in \mathbf{E}_k^{(l)}$ can be written in the form

$$ f = h(X^r - 1) + f_{p^m} = \left( h \frac{g_{p^m}^*}{g_{p^m}(0)X^s} + r_{p^m} \right) g_{p^m} $$

where $\deg h = (p^m - 2)s$ and $\frac{1}{X^s g_{p^m}(0)} g_{p^m}^* \in \mathbf{K}_l[X; \theta]$ is of degree $s$. Let us note $f' = g \frac{1}{X^s g_{p^m}(0)} g_{p^m}^* + r_{p^m}$. We have $\deg f' = (p^m - 1)s$ and $f' g_{p^m} (f' g_{p^m})^* = f' g(0) X^s f'^* (X^r - 1) \equiv 0 \mod (X^r - 1)^{p^m}$ and hence $f' f'^* X^s g_{p^m}(0) \equiv 0 \mod (X^r - 1)^{p^m - 1}$. With the same reasoning, replacing $f$ by $f'$ and the adjunction $*$ by $\bullet_{X^s g_{p^m}(0)}$, we get yet another twisted separable selfdual skew cyclic code $f_{p^m - 1}$ and another skew polynomial $f''$ such that $f'' f''^* g_{p^m - 1}^{(0)} g_{p^m}(0) \equiv 0 \mod (X^r - 1)^{p^m - 2}$. In turn replacing $f'$ by $f''$ and the adjunction $\bullet_{X^s g_{p^m}(0)}$ by $\bullet_{g_{p^m - 1}(0) g_{p^m}(0)}$, we get yet another twisted separable selfdual skew cyclic code $g_{p^m - 2}$ and another skew polynomial $f''$ such that $f'' f''^* X^s g_{p^m - 2}^{(0)} g_{p^m - 1}^{(0)} g_{p^m}(0) \equiv 0 \mod (X^r - 1)^{p^m - 3}$. Per induction we thus a factorization $g_0 g_1 \cdots g_{p^m - 1} g_{p^m}$ of $f$ into twisted separable selfdual skew cyclic codes as claimed. $\square$

**Remark 4.5** We notice the reason for the redundancy in the enumeration algorithm from the above proof of the exhaustivity. Indeed the many different factorizations $f_i = r_i g_i$ for selforthogonal $f_i$ at each step lead to as many redundant enumerations of the same inseparable selfdual skew cyclic code $f$.
**Proof.** The equation is solvable exactly when the plane spanned by $u$ and $v$ is a hyperbolic plane. For any step $i \in \{1, \dots, s\}$ the application mapping the pairs of noncollinear isotropic vectors in $W \simeq \mathbf{F}_l^{2i}$ to their span is surjective on the set of hyperbolic planes. The cardinal of its preimage for any hyperbolic plane is the number of pairs of noncollinear vectors in the hyperbolic plane.
Hence it is:

$$ \frac{(q_l^i - 1)(q_l^{i-1} + 1)((q_l^i - 1)(q_l^{i-1} + 1) - (q_l - 1))}{2(q_l - 1)^2} $$

The number of arbitrary planes is on the other side: $\frac{(q_l^{2s-1})(q_l^{2s}-q_l)}{(q_l^2-1)(q_l^2-q_l)}$. Finally we get the probability:

$$ \mathcal{P}_{q_l, i} = \frac{(q_l^i - 1)(q_l^{i-1} + 1)((q_l^i - 1)(q_l^{i-1} + 1) - (q_l - 1))(q_l^2 - 1)(q_l^2 - q_l)}{2(q_l^{2s} - 1)(q_l^{2s} - q_l)(q_l - 1)^2} $$

$$ \mathcal{P}_{q_l, i} = \frac{(q_l^{i-1} + 1)(q_l^{2s-1} + q_l^i - q_l^{i-1} - q_l)(q_l + 1)}{2(q_l^i + 1)(q_l^{2s-1} - 1)} $$

We observe

$$ \frac{(q_l^{i-1} + 1)(q_l^{2s-1} + q_l^i - q_l^{i-1} - q_l)(q_l + 1)}{2(q_l^i + 1)(q_l^{2s-1} - 1)} \underset{i \to \infty}{\sim} \frac{q_l^{i-1} q_l^{2s-1} (q_l + 1)}{2 q^i q_l^{2s-1}} \underset{i \to \infty}{\sim} \frac{q_l + 1}{2 q} \underset{q_l \to \infty}{\sim} \frac{1}{2} $$

□

**Remark 70** For $i = 1$, we check: $\frac{(q_l^{i-1}+1)(q_l^{2s-1}+q_l^i-q_l^{i-1}-q_l)(q_l+1)}{2(q_l^i+1)(q_l^{2s-1}-1)} = 1$

**Lemma 71** Solving $< u + \lambda v, u + \lambda v > = 0$ for $\lambda$ is equivalent to solving $< u, u > + 2\lambda < u, v > + \lambda^2 < v, v > = 0$ for $\lambda$. Noting $\Delta$ the discriminant: $\Delta := <u, v>^2 - <u, u><v, v>$. If $\Delta$ is a square in $\mathbf{F}_l^*$, we find two solutions, $\lambda = \frac{-<u, v> \pm \sqrt{\Delta}}{<v, v>}$, else there are no solutions.

**Proof.** (of Proposition 68) As in the Hermitian case, we start by taking two non-collinear random elements $u$ and $v$ in $\mathbf{K}_l$. If $u$ is isotropic, the equation: $< u + \lambda v, u + \lambda v > = 0$ is linear in $\lambda$ and has always a solution $\lambda_0$. We can thus make the base change $u \leftarrow u, v \leftarrow u - \lambda_0 v$. If $u$ isn't isotropic we have to solve the quadratic equation: $< u + \lambda v, u + \lambda v > = 0$ for $\lambda$ using lemma 71. If there are solutions, we make the base change $u \leftarrow u + \lambda v, v \leftarrow u - \lambda v$. If there are no solutions, we pick two random vectors again. Asymptotically in $s$ and $q_l$, this operation thus increase the mean complexity of a factor 2, as the lemma 69 shows. As in the Hermitian case, Witt decomposition theorem 46 produces a direct sum of hyperbolic plane, provided the existence criterion on the discriminant is fulfilled. Finally as the discriminant of the bilinear form
## 4.2 SageMath enumeration of inseparable selfdual skew cyclic codes

For $F = GF(3)$, $K = GF(3^6)$ and $k = 3$, the upper bound on the number of generated inseparable selfdual skew cyclic codes is numerically equal to $80 \times 1120 \times 80$, where 80 is the number of orthogonal isotropic spaces and 1120 the number of symplectic isotropic spaces (see Remark 4.2). A SageMath enumeration based on this algorithm provides a number $n$ of maximal isotropic codes equal to $n = 2360960$. We have not many redundancies since $80 \times 1120 \times 80 \approx 3 \times 2360960$. For the purpose of this heavy computation we implemented the PARI/GP optimization for finite field extensions in a dedicated branch of our code, which is only valid for prime base fields. The computation takes place in less than 10 minutes on the aforementioned computer.

## References

[Art11] M. Artin. *Algebra*. Pearson Education, 2011.

[BBB20] Aicha Batoul, Delphine Boucher, and Ranya Boulanouar. A construction of selfdual skew cyclic and negacyclic codes of length $n$ over $\mathbb{F}_{p^n}$. In *WAIFI 2020: Arithmetic of Finite Fields*, volume 12542 of *Lecture Notes in Computer Science*, RENNES, France, July 2020.

[BGU06] Delphine Boucher, Willi Geiselmann, and Félix Ulmer. Skew-cyclic codes, 2006.

[Bou15] Delphine Boucher. A note on the existence of self-dual skew codes over finite fields. In *Codes, cryptology, and information security. First international conference, C2SI 2015, Rabat, Morocco, May 26-28, 2015. Proceedings – in honor of Thierry Berger*, pages 228-239. Cham: Springer, 2015.

[Bou16] Delphine Boucher. Construction and number of selfdual skew codes over $F_{p^2}$. *Advances in Mathematics of Communications*, Volume 10(Issue 4):765-795, November 2016.

[BU14] Delphine Boucher and Felix Ulmer. Self-dual skew codes and factorization of skew polynomials. *Journal of Symbolic Computation*, 60:47-61, 01 2014.

[CL17] Xavier Caruso and Jérémy Le Borgne. A new faster algorithm for factoring skew polynomials over finite fields. *Journal of Symbolic Computation*, 79:411-443, 2017.

[Han05] Genevieve Hanlon. Counting points in sp(2n, fq) maximal parabolic subgroup. 04 2005.

[Jac96] Nathan Jacobson. Finite dimensional division algebras over fields. 1996.

[Mil20] J.S. Milne. *Fields and Galois theory*. 2020.

[PA71] G. Pólya and G.L. Alexanderson. Gaussian binomial coefficients. *Elemente der Mathematik*, 26:102-109, 1971.

[Ple65] V. Pless. The number of isotropic subspaces in a finite geometry. *Atti Accad. Naz. Lincei, VIII. Ser., Rend., Cl. Sci. Fis. Mat. Nat.*, 39:418-421, 1965.

[Sch85] W. Scharlau. *Quadratic and Hermitian Forms*. Grundlehren der mathematischen Wissenschaften. World Publishing Corporation, 1985.
restricted to the remaining direct sum of hyperbolic planes does not depend on the hyperbolic plane chosen, the algorithm's returned value remains uniformly distributed. □

**Mean complexity 72** The mean complexity $\mathcal{C}$ in $s$ of the algorithm is a less than a constant times the complexity of taking the orthogonal at each step, as the random event at each step is uniformly distributed and has a nonzero minimal probability (greater than $\frac{3}{16}$). Thus
$$ \mathcal{C} = \mathcal{O}(\sum_{1 \le i \le s} s^3) = \mathcal{O}(s^4) $$

The random direct sum of hyperbolic planes obtained, can now be used to enumerate all maximal isotropic spaces.

**Algorithm 73** Enumeration of maximal isotropic spaces in the Euclidean case

**Input:** Iterator $I$ on all reduced echelon matrix $A$ of growing size $(i, s)$, $U, V$, bases of supplementary maximal isotropic building pairwise hyperbolic pairs
**Output:** $W$ is the next maximal isotropic space

1. $A \leftarrow$ next $I$

2. $B \leftarrow$ next solution of the orthogonality system given by $A$ among $q_l^{i(i-1)/2}$ solutions.

3. $(0, C) \leftarrow$ single reduced echelon matrix, whose image is the totally isotropic orthogonal to $(A, B)$ in the vector space spanned by the $(v_i)_{0 \le i \le s}$

4. $W \leftarrow \mathrm{Im}((A, B)) \oplus \mathrm{Im}((0, C))$

5. yield $W$

**Proposition 74** The algorithm is correct

*Proof.* We enumerate all maximal isotropic spaces in an analogue fashion as for the enumeration of subspaces of dimension $s$ in an ambient space of dimension $2s$ using the formula:
$$ \binom{2s}{s}_{q_l} = \sum_{i=0}^{s} q_l^{2} \binom{s}{i}_{q_l}. $$

The algorithm for subspaces enumeration in general is the following. Given a base of the ambient vector space, we use the bijection between its vector subspaces and the reduced echelon matrices in this base, whose image correspond to the vector subspaces, to reduce the problem to the enumeration of all $(s, 2s)$-sized reduced echelon matrices.

We enumerate these $\binom{2s}{s}_{q_l}$ different reduced echelon matrices $M$ of size $(s, 2s)$ by decomposing the matrix $M$ in $s$ types of reduced echelon matrices of the form $\begin{pmatrix} A & B \\ 0 & C \end{pmatrix}$ for block matrices $A$ of the size $(i, s)$ for each index $i$ between 0 and $s$. There are thus for each index $i$, $\binom{s}{i}_{q_l}$ possibilities
[Seg59] Beniamino Segre. Le geometrie di galois. *Annali di Matematica Pura ed Applicata*, 48:1-96, 1959.

[Wis91] R. Wisbauer. *Foundations of Module and Ring Theory: A Handbook for Study and Research (1st ed.)*. 1991.
for choosing A, $\binom{s}{s-i}_{q_l} = \binom{s}{i}_{q_l}$ possibilities for choosing C and $q_l^{i^2}$ possibilities for choosing the matrix B as its entries can be choosen arbitrarily once the pivots of C have been deleted.

Summing over all indices, and for each index, multiplying all independent possibilities for A, B and C, we obtain the expected formula $\binom{2s}{s}_{q_l} = \sum_{i=0}^{s} q_l^{i^2} \binom{s}{i}_{q_l}^2$.

$$ \binom{2s}{s}_{q_l} = |M_{\text{echelon}}| = \left| \left[ \frac{A_{\text{echelon}}(i, s)}{0} \mid \frac{B_{\text{pivot deletion}}(i, s)}{C_{\text{echelon}}(s-i, s)} \right] \middle| 0 \le i \le s \right| = \sum_{i=0}^{s} q_l^{i^2} \binom{s}{i}_{q_l}^2 $$

Now we adapt this strategy to the case of isotropic spaces. Starting with a base $(u_i)_{0 \le i \le s}$ and $(v_i)_{0 \le i \le s}$ of supplementary maximal isotropic spaces such that (Witt decomposition 46) the bilinear form is represented in this base by the matrix: $\begin{pmatrix} 0 & Id \\ Id & 0 \end{pmatrix}$, as it is obtained by the algorithm previously described, we express the global $(s, 2s)$ sized matrix as a generator matrix $M$ for a maximal isotropic space expressed in this base. For each reduced echelon matrix $A$ in the upper left corner of $M$ generating a subspace of $\langle U \rangle$ of dimension $i$, we get as in the previous enumeration corresponding matrices $B$ and $C$. But now the additional orthogonality relations on the rows expressed in the base of the $(u_i)_{0 \le i \le s}$ and $(v_i)_{0 \le i \le s}$ leads to $i(i+1)/2$ (number of unordered pairs of orthogonal rows of $(A, B)$) independent additional equations for $B$. Noting $A = (a_{i,j})_{1 \le i \le d, 1 \le j \le s}$ $B = (b_{i,j})_{1 \le i \le d, 1 \le j \le s}$, this set of equations is explicitly the following:

$$ \sum_{1 \le j \le s} a_{1,j} b_{1,j} + b_{1,j} a_{1,j} = 0 $$

...

...

$$ \sum_{1 \le j \le s} a_{1,j} b_{d,j} + b_{1,j} a_{d,j} = 0 $$

$$ \sum_{1 \le j \le s} a_{k,j} b_{k,j} + b_{k,j} a_{k,j} = 0 $$

...

$$ \sum_{1 \le j \le s} a_{k,j} b_{d,j} + b_{k,j} a_{d,j} = 0 \quad (7.5) $$

$$ \sum_{1 \le j \le s} a_{d,j} b_{d,j} + b_{d,j} a_{d,j} = 0 $$

or matricially:

$$ AB^{\text{tr}} + BA^{\text{tr}} = 0 $$

Let us note $\alpha$, $\beta$ and $\gamma$ the endomorphisms induced by the matrices $A$, $B$, and $C$ in the base $((u_i)_{0 \le i \le s}, (v_i)_{0 \le i \le s})$. From the system of equations we get: $\alpha \circ \beta^{\bullet} + \beta \circ \alpha^{\bullet} = 0$ and we have also $\alpha \circ \gamma^{\bullet} = 0$, which implies $\ker(\alpha) \supset \text{Im}(\gamma^{\bullet})$. By checking both dimensions equal to $s-i$, we deduce $\ker(\alpha) = \text{Im}(\gamma^{\bullet})$. Moreover, as we made the pivot with $C$ in $B$, we have: $\text{Im}(\beta^{\bullet}) \cap \text{Im}(\gamma^{\bullet}) = 0$.
We get $Im(\beta^{\bullet}) \cap ker(\alpha) = 0$. This means that $\alpha$ restricted to $Im(\beta^{\bullet})$ is injective. Noting $\mu = \alpha \circ \beta^{\bullet}$, the system of equations reduces to assert that $\mu$ is antisymmetric. We thus have to solve: $\beta^{\bullet} = \alpha|_{Im(\beta^{\bullet})}\mu$ for any antisymmetric endomorphism $\mu$ represented by an antisymmetric matrix $M$ of dimension $d \times d$ in the chosen base. This gives $q_l^{i(i-1)/2}$ solutions for $B$.

On the other hand, for $(0, C)$, there is no choice but to take the reduced echelon matrix corresponding to the right kernel of $A$: the single totally isotropic space spanned by the $(v_i)_{0 \le i \le s}$ and orthogonal to $(A, B)$. $\square$

**Mean complexity 75** The mean complexity $C$ in $s$ of one iteration of the algorithm is a less than a constant times the complexity of taking the orthogonal at each step. Thus $C = O(\sum_{1 \le i \le s} s^3) = O(s^4)$

**Remark 76** As a byproduct of Proposition 74, we obtain a bijective proof of the $q$-binomial formula stated in 45 for the evaluation at 1:

$$ \prod_{i=0}^{s-1} (1 + xq_l^i)|_{x=1} = \sum_{i=0}^{s} x^i q_l^{\binom{i}{2}} \binom{s}{i} |_{x=1} \\ \prod_{i=0}^{s-1} (1 + q_l^i) = \sum_{i=0}^{s} q_l^{\binom{i}{2}} \binom{s}{i} q_l $$

**Algorithm 77** Enumeration of maximal isotropic spaces in the Hermitian case

**Input:** Iterator $I$ on all reduced echelon matrix $A$ of growing size $(i, s)$, $U, V$, bases of supplementary maximal isotropic building pairwise hyperbolic pairs

**Output:** $W$ is the next maximal isotropic space

1. $A \leftarrow$ next $I$

2. $B \leftarrow$ next solution of the orthogonality system given by $A$ among $q_l^{i^2/2}$ solutions.

3. $(0, C) \leftarrow$ single reduced echelon matrix, whose image is the totally isotropic orthogonal of $(A, B)$ in the vector space spanned by the $(v_i)_{0 \le i \le s}$

4. $W \leftarrow Im((A, B)) \oplus Im((0, C))$

5. yield $W$

**Proposition 78** The algorithm is correct

*Proof.* We use the same algorithm as in the Euclidean case but the orthogonality equations are
now put in the Hermitian setting. This set of equations is explicitly the following:

$$ \sum_{1 \le j \le s} a_{1,j} \sigma_l(b_{1,j}) + b_{1,j} \sigma_l(a_{1,j}) = 0 $$

...

...

$$ \sum_{1 \le j \le js} a_{1,j} \sigma_l(b_{d,j}) + b_{1,j} \sigma_l(a_{d,j}) = 0 $$

...

...

$$ \sum_{1 \le j \le s} a_{k,j} \sigma_l(b_{k,j}) + b_{k,j} \sigma_l(a_{k,j}) = 0 $$

...

$$ \sum_{1 \le j \le js} a_{k,j} \sigma_l(b_{d,j}) + b_{k,j} \sigma_l(a_{d,j}) = 0 $$

...

...

$$ \sum_{1 \le j \le js} a_{d,j} \sigma_l(b_{d,j}) + b_{d,j} \sigma_l(a_{d,j}) = 0 \qquad (7.6) $$

or matricially:

$$ A\sigma_l(B^{\mathrm{tr}}) + B\sigma_l(A^{\mathrm{tr}}) = 0 $$

We follow the proof of 74, we now have that $M = \alpha \circ \beta^\bullet$ is Hermitian antisymmetric. And we have thus for fixed entries in the upper triangular part of $B$, $\sqrt{q_l^i}$ additional solutions on the diagonal of $B$. This gives $q_l^{i(i-1)/2+i/2} = q_l^{i/2}$ possibilities for $B$. □

**Mean complexity 79** The mean complexity $C$ in $s$ of one iteration of the algorithm is a less than a constant times the complexity of taking the orthogonal at each step. $C = O(\sum_{1 \le i \le s} s^3) = O(s^4)$

**Remark 80** As a byproduct of Proposition 74, we obtain a bijective proof of the $q$-binomial formula stated in 45 for the evaluation at $x = \sqrt{q_l}$:

$$ \prod_{i=0}^{s-1} (1 + xq_l^i) |_{x=\sqrt{q_l}} = \sum_{i=0}^{s} x^i q_l^{\binom{i}{2}} \binom{s}{i} |_{x=\sqrt{q_l}} $$

$$ \prod_{i=0}^{s-1} (1 + q_l^{i+\frac{1}{2}}) = \sum_{i=0}^{s} q_l^{\binom{i}{2}} \binom{s}{i} q_l $$

# 8 SageMath enumeration of selfdual skew codes

We implemented the algorithms of section 7 in SageMath. Our package is available at

https://plmlab.math.cnrs.fr/caruso/selfdual-skew-cyclic-codes

It consists in a main class instantiated with the extension $K/F$ of order $r$ and a palindromic polynomial of the center $P(X^r)$ in $F(X^{\pm r})$ of $K[X^{\pm 1}; \theta]$ as parameters. It provides an iterator on all selfdual codes for the Ore algebra $K[X^{\pm 1}; \theta]/P(X^r)$. Hereunder, a simple use case of the library to compute the first iteration of $E_1$ for $p = 3$ and $s = 3$:
```
sage:load("selforthogonal codes.sage")
```

```
sage:p,s,P = 3,3,[1,-1]
```

```
sage:A = SelfDualCodes(GF(p) ["y"] (P), GF(p) ["z"]).irreducibleElement(2*s))
```

```
sage:iter = A.enumerate selfdual codes (True)
```

```
sage:next(iter)
```

$$x^3 + (z^5 + z^4 + 2z^3 + z^2 + z + 1)x^2 + (z^4 + z^3 + 2z^2 + z + 1)x + 2z^4 + z^3 + 2z^2 + 2z + 1$$

## 8.1 SageMath computation of cyclic or negacyclic codes

Hereunder, we provide computations for the palindromic Euclidean, Hermitian, skew-Euclidean and skew-Hermitian cases and nonpalindromic case. (see the four types of geometries 3) Skew-Euclidean and skew-Hermitian cases are described in appendix A.

**Case 81** Palindromic Euclidean:

$$q = 3, s = 3 \text{ and } P(Y) = Y - 1$$

```
sage:A = SelfDualCodes(PolynomialRing(GF(3), y)([1, 2]), 3)
```

```
sage:iter = A.enumerate selfdual codes (True)
```

H90 preimage of $x\bar{x}$ with $norm(x) = y: zeta = 1$

Enumerating the 80 selfdual codes ...

```
selfdual code in E: x^3 + (2z_6^3 + z_6 + 1)x^2 + (z_6^5 + z_6^3 + 2)x + 2z_6^4 + z_6^3 + 2z_6^2 + 2z_6 + 1
```

Total time (ms): 35.42

```
sage:next(iter)
```

```
selfdual code in E: x^3 + (2z_6^5 + z_6^4 + 2z_6^3 + z_6^2 + 2)x^2 + (2z_6^5 + z_6^4 + 2z_6^3 + 2z_6 + 1)x + z_6^5 + 2z_6^4 + z_6^2 + 2z_6
```

Total time (ms): 31.98

**Case 82** Palindromic Hermitian case:

$$q = 3, s = 3 \text{ and } P(Y) = Y^2 + 1$$

```
sage:A = SelfDualCodes(PolynomialRing(GF(3), y)([1, 0, 1]), 3)
```

```
sage:iter = A.enumerate selfdual codes (True); next(iter)
```

H90 preimage of $x\bar{x}$ with $norm(x) = y: zeta = z_6^4 + z_6^3 + 2z_6^2 + 2z_6 + 1$

Enumerating the 1640 selfdual codes ...

```
selfdual code in E: x^6 + (z_6^4 + 2z_6 + 2)x^5 + (2z_6^5 + 2z_6^4 + z_6 + 1)x^4 + (2z_6^5 + z_6^4 + z_6^3 + z_6^2)x^3 + (z_6^5 + z_6^4 + 2z_6^2)x^2 + (2z_6^4 + z_6^3 + z_6^2 + z_6)x + z_6^5 + 2z_6^4 + 2z_6^3 + z_6^2 + 1
```

Total time (ms): 36.35

```
sage:next(iter)
```
selfdual code in E: $x^6 + (2z_6^4 + 2z_6^3 + 2z_6)x^5 + (2z_6^5 + 2z_6^4 + 2z_6^3 + 2z_6^2 + z_6 + 2)x^4 + (2z_6^5 + 2z_6^2 + z_6)x^3 + (z_6^5 + 2z_6^4 + z_6^2 + 1)x^2 + (z_6^3 + 2z_6^2)x + z_6^4 + 2z_6^3 + z_6^2 + z_6 + 2$

Total time (ms): 37.64

Case 83 Palindromic Skew-Euclidean case:

$$
q = 3, s = 3, t = -\theta^s(iota) \in GF(3^6) \text{ and } P(Y) = Y - 1
$$

sage:A = SelfDualCodes(PolynomialRing(GF(3), y)([1, 2]), 3, iota, True)

sage:iter = A.enumerate selfdual codes (True); next(iter)

H90 preimage of $x\bar{x}$ with $norm(x) = y$: $zeta = 2z_6^5 + z_6^4 + z_6^3 + 2z_6^2 + 2$

Enumerating the 1120 selfdual codes . . .

$$
\text{selfdual code in E: } x^3 + (z_6^5 + z_6^4 + z_6 + 2)x^2 + (z_6^4 + z_6^3 + 2z_6^2 + z_6 + 1)x + 2z_6^4 + 2z_6^3 + 1
$$

Total time (ms): 41.50

sage:next(iter)

$$
\text{selfdual code in E: } x^3 + (z_6^5 + z_6^4 + 2z_6^3 + z_6^2 + 2z_6 + 1)x^2 + (z_6^5 + z_6^3 + z_6 + 2)x + 2z_6^5 + 2z_6^3 + z_6 + 2
$$

Total time (ms): 42.02

Case 84 Palindromic Skew-Hermitian case:

$$
q = 3, s = 3, t = -\theta^s(iota) \in GF(3^6) \text{ and } P(Y) = Y^2 + 1
$$

sage:A = SelfDualCodes(PolynomialRing(GF(3), y)([1, 0, 1]), 3, iota, True)

sage:iter = A.enumerate selfdual codes (True); next(iter)

H90 preimage of $x\bar{x}$ with $norm(x) = y$: $zeta = (2z_6^5 + 2z_6^3 + 1)y + 2z_6^4 + z_6^3 + 2z_6^2 + 2z_6 + 1$

Enumerating the 14948416 selfdual codes . . .

$$
\text{selfdual code in E: } x^6 + (z_6^5 + z_6)x^5 + (z_6^3 + z_6^2 + 2z_6)x^4 + (z_6^5 + z_6^3 + z_6^2 + 1)x^3 + (z_6^5 + 2z_6^4 + z_6^3 + z_6^2 + 2)x^2 + (z_6^4 + z_6^2 + 2z_6 + 2)x + z_6^5 + z_6^4
$$

Total time (ms): 44.15

sage:next(iter)

$$
\text{selfdual code in E: } x^6 + (2z_6^5 + 2z_6^4 + z_6 + 1)x^5 + (2z_6^5 + z_6^2)x^4 + (2z_6^4 + 2z_6^2)x^3 + (z_6^5 + z_6^3 + 2z_6^2 + z_6 + 2)x^2 + (z_6^5 + z_6^3 + 2z_6^2 + z_6)x + 1
$$

Total time (ms): 45.33

8.2 SageMath iteration time for the enumeration of selfdual skew codes

We provide computation results for skew cyclic ($X^{rk} - 1, \mathbf{K}/\mathbf{F}$)-codes and skew negacyclic ($X^{rk} + 1, \mathbf{K}/\mathbf{F}$)-codes for $|\mathbf{F}| \le 9$, $k \le 9$ and $r \in \{4, 6, 8\}$ on a computer with following charac-
teristics:
* processeur x64: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz 2.59 GHz

* mémoire RAM: 16,0 Go

Case 85 s = 2:

<table><thead><tr><th>P(Y)</th><th>p = 3</th><th>p = 5</th><th>p = 7</th><th>p = 3<sup>2</sup></th></tr></thead><tbody><tr><td>Y - 1</td><td>no codes.</td><td>no codes.</td><td>no codes.</td><td>no codes.</td></tr><tr><td>Y<sup>3</sup> - 1</td><td>inseparable</td><td>no codes.</td><td>no codes.</td><td>inseparable</td></tr><tr><td>Y<sup>5</sup> - 1</td><td>no codes.</td><td>inseparable</td><td>no codes.</td><td>no codes.</td></tr><tr><td>Y<sup>7</sup> - 1</td><td>no codes.</td><td>no codes.</td><td>inseparable</td><td>no codes.</td></tr><tr><td>Y<sup>9</sup> - 1</td><td>inseparable</td><td>no codes.</td><td>no codes.</td><td>inseparable</td></tr><tr><td>Y + 1</td><td>9 ms<br>8 codes.</td><td>9 ms<br>12 codes.</td><td>16 ms<br>16 codes.</td><td>21 ms<br>20 codes.</td></tr><tr><td>Y<sup>2</sup> + 1</td><td>16 ms<br>112 codes.</td><td>6 ms<br>1120 codes.</td><td>15 ms<br>2752 codes.</td><td>15 ms<br>9104 codes.</td></tr><tr><td>Y<sup>3</sup> + 1</td><td>inseparable</td><td>26 ms<br>9072 codes.</td><td>22 ms<br>58432 codes.</td><td>inseparable</td></tr><tr><td>Y<sup>4</sup> + 1</td><td>18 ms<br>9104 codes.</td><td>21 ms<br>440080 codes.</td><td>35 ms<br>7573504 codes.</td><td>48 ms<br>82882816 codes.</td></tr><tr><td>Y<sup>5</sup> + 1</td><td>62 ms<br>58400 codes.</td><td>inseparable</td><td>111 ms<br>94120000 codes.</td><td>128 ms<br>1065800000 codes.</td></tr><tr><td>Y<sup>6</sup> + 1</td><td>inseparable</td><td>47 ms<br>492889600 codes.</td><td>59 ms<br>16862891008 codes.</td><td>inseparable</td></tr><tr><td>Y<sup>7</sup> + 1</td><td>80 ms<br>4409216 codes.</td><td>300 ms<br>2953126512 codes.</td><td>inseparable</td><td>250 ms<br>5671878518080 codes.</td></tr><tr><td>Y<sup>8</sup> + 1</td><td>463 ms<br>155747211899539264 codes.</td><td>87 ms<br>44667536 codes.</td><td>113 ms<br>153321876880 codes.</td><td>108 ms<br>37546305270016 codes.</td></tr><tr><td>Y<sup>9</sup> + 1</td><td>inseparable</td><td>218 ms<br>2232563643072 codes.</td><td>125 ms<br>815875477905664 codes.</td><td>inseparable</td></tr></tbody></table>

(8.1)
Case 86 s = 3:

<table><thead><tr><th>P(Y)</th><th>p = 3</th><th>p = 5</th></tr></thead><tbody><tr><td>Y - 1</td><td>21 ms<br>80 codes.</td><td>no codes.</td></tr><tr><td>Y<sup>3</sup> - 1</td><td>inseparable</td><td>no codes.</td></tr><tr><td>Y<sup>5</sup> - 1</td><td>101 ms<br>34485200000 codes.</td><td>inseparable</td></tr><tr><td>Y<sup>7</sup> - 1</td><td>195 ms<br>632674347361280 codes.</td><td>no codes.</td></tr><tr><td>Y<sup>9</sup> - 1</td><td>inseparable</td><td>no codes.</td></tr><tr><td>Y + 1</td><td>no codes.</td><td>21 ms<br>312 codes.</td></tr><tr><td>Y<sup>2</sup> + 1</td><td>152 ms<br>27328 codes.</td><td>12 ms<br>3583232 codes.</td></tr><tr><td>Y<sup>3</sup> + 1</td><td>inseparable</td><td>57 ms<br>737335872 codes.</td></tr><tr><td>Y<sup>4</sup> + 1</td><td>38 ms<br>540023488 codes.</td><td>47 ms<br>4298676317632 codes.</td></tr><tr><td>Y<sup>5</sup> + 1</td><td>no codes.</td><td>inseparable</td></tr><tr><td>Y<sup>6</sup> + 1</td><td>inseparable</td><td>101 ms<br>15403154538981146624 codes.</td></tr><tr><td>Y<sup>7</sup> + 1</td><td>no codes.</td><td>398 ms<br>2343178995193968789312 codes.</td></tr><tr><td>Y<sup>8</sup> + 1</td><td>209 ms<br>155747211899539264 codes.</td><td>270 ms<br>14621913851167452151565632 codes.</td></tr><tr><td>Y<sup>9</sup> + 1</td><td>inseparable</td><td>450 ms<br>5537531819466117905154319872 codes.</td></tr></tbody></table>

(8.2)
<table><thead><tr><th>P(Y)</th><th>p = 7</th><th>p = 3<sup>2</sup></th></tr></thead><tbody><tr><td>Y - 1</td><td>207 ms<br>800 codes.</td><td>no codes.</td></tr><tr><td>Y<sup>3</sup> - 1</td><td>42 ms<br>49557536000 codes.</td><td>inseparable</td></tr><tr><td>Y<sup>5</sup> - 1</td><td>129 ms<br>132932852650000000 codes.</td><td>no codes.</td></tr><tr><td>Y<sup>7</sup> - 1</td><td>inseparable</td><td>no codes.</td></tr><tr><td>Y<sup>9</sup> - 1</td><td>342 ms<br>3285136932442382207872260115712000 codes.</td><td>inseparable</td></tr><tr><td>Y + 1</td><td>no codes.</td><td>56 ms<br>1640 codes.</td></tr><tr><td>Y<sup>2</sup> + 1</td><td>36 ms<br>46255616 codes.</td><td>32 ms<br>540023488 codes.</td></tr><tr><td>Y<sup>3</sup> + 1</td><td>no codes.</td><td>inseparable</td></tr><tr><td>Y<sup>4</sup> + 1</td><td>74 ms<br>2139582011539456 codes.</td><td>141 ms<br>291625367591686144 codes.</td></tr><tr><td>Y<sup>5</sup> + 1</td><td>no codes.</td><td>317 ms<br>30473993612900000000 codes.</td></tr><tr><td>Y<sup>6</sup> + 1</td><td>139 ms<br>80064991841686623715328 codes.</td><td>inseparable</td></tr><tr><td>Y<sup>7</sup> + 1</td><td>inseparable</td><td>601 ms<br>95758739099623080435253982720 codes.</td></tr><tr><td>Y<sup>8</sup> + 1</td><td>270 ms<br>14621913851167452151565632 codes.</td><td>280 ms<br>2996100586019126506799315390464 codes.</td></tr><tr><td>Y<sup>9</sup> + 1</td><td>no codes.</td><td>inseparable</td></tr></tbody></table>

(8.3)
Case 87 s = 4:

<table><thead><tr><th>P(Y)</th><th>p = 3</th><th>p = 5</th></tr></thead><tbody><tr><td>Y - 1</td><td>no codes.</td><td>no codes.</td></tr><tr><td>Y<sup>3</sup> - 1</td><td>inseparable</td><td>no codes.</td></tr><tr><td>Y<sup>5</sup> - 1</td><td>no codes.</td><td>inseparable</td></tr><tr><td>Y<sup>7</sup> - 1</td><td>no codes.</td><td>no codes.</td></tr><tr><td>Y<sup>9</sup> - 1</td><td>inseparable</td><td>no codes.</td></tr><tr><td>Y + 1</td><td>59 ms<br>2240 codes.</td><td>49 ms<br>39312 codes.</td></tr><tr><td>Y<sup>2</sup> + 1</td><td>78 ms<br>59793664 codes.</td><td>29 ms<br>281268665344 codes.</td></tr><tr><td>Y<sup>3</sup> + 1</td><td>inseparable</td><td>128 ms<br>7258242894319872 codes.</td></tr><tr><td>Y<sup>4</sup> + 1</td><td>88 ms<br>2584219514040576 codes.</td><td>108 ms<br>26237287231770008445184 codes.</td></tr><tr><td>Y<sup>5</sup> + 1</td><td>220 ms<br>4618366957232000000 codes.</td><td>inseparable</td></tr><tr><td>Y<sup>6</sup> + 1</td><td>inseparable</td><td>200 ms<br>7379726761927122670144512264503296 codes.</td></tr><tr><td>Y<sup>7</sup> + 1</td><td>286 ms<br>185303919822256877419151360 codes.</td><td>387 ms<br>140781666466923087414564624908817453312 codes.</td></tr><tr><td>Y<sup>8</sup> + 1</td><td>406 ms<br>3562996965217630611881373225216 codes.</td><td>551 ms<br>544708738161233632462123485150149692387504384 codes.</td></tr><tr><td>Y<sup>9</sup> + 1</td><td>inseparable</td><td>691 ms<br>25992763794364435757209303588361601906385684303872 codes.</td></tr></tbody></table>

(8.4)