# The covering radius of Euclidean codes

Minjia Shi, Xingxing Xu, Patrick Solé

► To cite this version:

Minjia Shi, Xingxing Xu, Patrick Solé. The covering radius of Euclidean codes. Journal of Applied Mathematics and Computing, 2025, 10.1007/s12190-025-02574-1. hal-05145929

HAL Id: hal-05145929

https://hal.science/hal-05145929v1

Submitted on 5 Jul 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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The covering radius of Euclidean codes*

Minjia Shi, Xingxing Xu†, Patrick Solé‡

## Abstract

The Euclidean metric for block codes is an important parameter to consider when building Euclidean lattices by Construction A and spherical codes by the Yaglom map. The covering radius of Euclidean codes over the ring $Z_q$ with $q$ an integer $> 1$, is explored here in analogy with covering codes for the Hamming metric over finite fields. The three classical upper bounds: Delsarte, Norse and redundancy are generalized in this new set up. The sphere covering bound is derived and some non-existence results for perfect codes are given. The covering radii of free repetition codes are determined exactly. The covering radii of zero divisor repetition codes are given upper and lower estimates. A construction for spherical covering codes based on covering Euclidean codes over the ring $Z_q$ via the Yaglom map is studied.

**Keywords:** Euclidean metric, spherical codes, covering radius

**MSC(2020):** Primary 94B25, Secondary 51M04

## 1 Introduction

The Euclidean metric over the ring $Z_q$ with $q$ an integer $> 1$, has been instrumental to the construction of Euclidean lattices in the 1990's [2, 13], using a generalized Construction A. The covering radius of codes for that metric was considered for $q = 4$ in [1], giving information on the covering radius of the lattices so constructed. More recently, this metric enters the construction of spherical codes from codes over $Z_q$, via the Yaglom map [22], with a performance close to the Shannon bound. In the present paper we will revisit this mapping technique to construct covering spherical codes. While the covering radius of codes over finite fields has been a topic of intense activity since the 1980's [5, 6, 7], as witnessed by the extensive bibliography collated

<footnote>*This research is supported in part by National Natural Science Foundation of China (12471490)</footnote>

<footnote>†Minjia Shi and Xingxing Xu are with the Key Laboratory of Intelligent Computing Signal Processing, Ministry of Education, School of Mathematical Sciences, Anhui University, Hefei 230601, China. Email: smjwcl.good@163.com, xuxingxing03@163.com</footnote>

<footnote>‡Institut de Mathématiques de Marseille (CNRS, Aix-Marseille University), Marseilles, France. Email: sole@enst.fr</footnote>
by A. Lobstein [16], the covering radius of codes for the Euclidean metric has been hardly touched upon apart from [1].

In this paper, motivated by the above two applications, we will study that topic, while keeping in mind the approaches and problems of [5]. In particular, we extend the three main upper bounds of [5, 6]. The *Norse bounds* (called that way by Skip Mattson to honor the Norwegian authors of [14]) involving the strength of the code as an orthogonal array are generalized here by a method based on orthogonal polynomials in the spirit of [21]. We use the notion of self-complementary codes (introduced in [15] to bound above the covering radius of the first order GRM codes), in the case of codes of strength 2. This extends naturally the notion of binary self-complementary codes in [14]. The *Delsarte bound* of [9], bounds the covering radius above by the number of dual Hamming weights (an alternative proof is in [17, Chap. 6, Th. 21]). It is extended here by considering the relation between the Euclidean and Hamming distance. The *redundancy bound* states that the covering radius of a linear code over a finite field is bounded above by its codimension [6, Proposition 2]. This elementary fact is extended here to a complex bound based on the type of a code as a module over a chain ring in the case $q = p^r$ [18, 19]. The special case $p = r = 2$ of that bound figures in [1].

For lower bounds, the sphere covering bound is derived, generalizing [1]. Two non-existence results for perfect codes are given. One for $q = 4$ which does not appear in [1], and another for an infinite class of alphabets.

The covering radius of certain repetition codes that were investigated for the Lee metric in [8] are considered here, and determined exactly for free repetition codes. For zero divisor repetition codes we obtain upper and lower estimates that are close to each other.

Spherical codes $X = \{x_i, x_2, \dots, x_N\}$, are finite sets of points on the unit sphere $S(n)$ of $\mathbb{R}^n$ [10]. They can be used as codebooks in *vector quantization of Gaussian sources* [12]. The covering radius of $X$ is

$$R = \sup\{d(x, X) \mid x \in S(n)\},$$

where $d(x, X) = \min\{d(x, y) \mid y \in X\}$, and $d(\cdot, \cdot)$ denotes the Euclidean distance in $\mathbb{R}^n$. In the source coding application this quantity would be the worst possible distorsion from the source. The best sphere coverings in the sense of minimizing the covering radius for a given $N$ are recorded in [20] for $n = 3$. Spherical designs with small covering radius are constructed in [24]. Upper bounds on the covering radius of spherical $t$-designs as a function of $t$ are given in [11, 21]. In [22] the Yaglom map was used to construct spherical codes in the sense of [10], that is to say packing of caps on the sphere from Euclidean codes over $\mathbb{Z}_q$. In the present paper, we use the same map to construct covering spherical codes in the sense of [11, 20, 21]. The covering radius of the Euclidean code is used to bound above the covering radius of the spherical code.

The material is arranged as follows. The next section collects the notions and notations needed to read and understand the rest of the paper. Section 3 studies
upper and lower bounds. Section 4 examines the covering radii of repetition codes. Section 5 controls the parameters of spherical covering codes that the Yaglom map constructs from the Euclidean codes $\mathbb{Z}_q$. Section 6 concludes the article and provides open problems for future research.

# 2 Preliminaries

## 2.1 Background on linear codes

A linear code $C$ of length $n$ over $\mathbb{Z}_q$ is an additive subgroup of $\mathbb{Z}_q^n$. An element of $C$ is called a codeword of $C$. The Hamming weight $wt_H(\mathbf{x})$ of a vector $\mathbf{x}$ is the number of its nonzero components. The Euclidean weight of $x \in \mathbb{Z}_q$ is defined by

$$wt_E(x) = \min\{x^2, (q-x)^2\}, x \in \mathbb{Z}_q,$$

and the Euclidean weight $wt_E(\mathbf{x})$ of $\mathbf{x}$ is just the rational sum of the Euclidean weights of its components. The Hamming and Euclidean distances $d_H(\mathbf{x}, \mathbf{y})$ and $d_E(\mathbf{x}, \mathbf{y})$ between two vectors $\mathbf{x}$ and $\mathbf{y}$ are $wt_H(\mathbf{x} - \mathbf{y})$ and $wt_E(\mathbf{x} - \mathbf{y})$ respectively. The minimum Hamming and Euclidean distances, $d_H$ and $d_E$ of $C$ are the smallest Hamming and Euclidean weights among all nonzero codewords of $C$, respectively. A code of length $n$, size $M$, minimum Hamming distance $d_H$, minimum Euclidean distance $d_E$ over $\mathbb{Z}_q$ is a $(n, M, d_H, d_E)$ code.

Let $\mathbf{x} = (x_1, \dots, x_n)$ and $\mathbf{y} = (y_1, \dots, y_n)$ be two elements of $\mathbb{Z}_q^n$. Define the inner product of $\mathbf{x}$ and $\mathbf{y}$ in $\mathbb{Z}_q^n$ by $\mathbf{x} \cdot \mathbf{y} = x_1y_1 + \dots + x_ny_n \pmod{q}$. The dual code $C^\perp$ of $C$ is defined as $C^\perp = \{\mathbf{x} \in \mathbb{Z}_q^n | \mathbf{x} \cdot \mathbf{y} = 0, \text{ for all } \mathbf{y} \in C\}$.

Two codes are said to be equivalent if one can be obtained from the other by permuting the coordinates, or multiplying by a non-zero element a given coordinate. Codes differing by only a permutation of coordinates are called permutation-equivalent.

When $q = p^m$, for a prime $p$ and $m \ge 1$, the ring is a chain ring with maximal ideal $(p)$. (Recall that a ring is a chain ring if its lattice of ideals is a chain [19]). By the characterization in [18] any linear code $C$ over $\mathbb{Z}_q$, is permutation-equivalent to a code with a generator matrix $G$ of the form

$$G = \begin{pmatrix}
I_{k_0} & A_{01} & A_{02} & \cdots & A_{0,m-1} & A_{0,m} \\
0 & pI_{k_1} & pA_{12} & \cdots & pA_{1,m-1} & pA_{1,m} \\
0 & 0 & p^2I_{k_2} & \cdots & p^2A_{2,m-1} & p^2A_{2,m} \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & 0 & \cdots & p^{m-1}I_{k_{m-1}} & p^{m-1}A_{m-1,m}
\end{pmatrix},$$

where $A_{i,j}$ are matrices with entries 0 or 1 and $I_{k_i}$ is the identity matrix of order $k_i$ for $0 \le i \le m-1, 1 \le j \le m$. The vector $(k_0, k_1, \dots, k_{m-1})$ is called the type of $C$. The above form of the generator matrix can be regarded as the analogue for chain rings of the row reduced echelon form for finite fields.
For simplicity, $d$ and $wt$ in the following text represent Euclidean distance and Euclidean weight, respectively.

## 2.2 The concept of covering radius

The covering radius of a block code of length $n$ is defined as the smallest integer $\rho$ such that all vectors in the ambient space are within Euclidean distance $\rho$ of some codewords. Thus, for the $q$-ary case, the covering radius $r(C)$ of $C$ is

$$r(C) = \max\{\min\{d(\boldsymbol{x}, \boldsymbol{c}) \mid \boldsymbol{c} \in C\} \mid \boldsymbol{x} \in \mathbb{Z}_q^n\}.$$

We now relate the covering radius with respect to the Euclidean distance to the weights of cosets. The translate

$$\boldsymbol{u} + C = \{\boldsymbol{u} + \boldsymbol{c} \mid \boldsymbol{c} \in C\}$$

is called a coset of $C$ where $\boldsymbol{u}$ is a vector of $\mathbb{Z}_q^n$. A vector of minimum weight in a coset is called a *coset leader*. The following proposition is immediate but useful. The proof is omitted.

**Proposition 1** *The covering radius of $C$ with respect to the Euclidean distance is the largest minimum Euclidean weight among all cosets.*

# 3 Upper and lower bounds

In this section, we give several upper and lower bounds on the covering radius of codes over $\mathbb{Z}_q^n$.

## 3.1 Lower bounds

The following theorem extends the sphere covering bound on the covering radius of codes over $\mathbb{Z}_4$ in [1] to codes over $\mathbb{Z}_q$ for any integer $q > 1$.

**Theorem 1** (The Sphere-Covering Bound) For any code $C$ of length $n$ over $\mathbb{Z}_q$,

$$\sum_{i=0}^{r(C)} V_i \geq \frac{q^n}{|C|},$$

where

$$\sum_{i=0}^{nt^2} V_i z^i = \left(1 + 2 \sum_{j=1}^{t} z^{j^2}\right)^n$$

for $t = \lfloor q/2 \rfloor$.
**Proof.** The upper bound on $q^n$ is obtained, as usual, by considering a covering of the ambient space by spheres of radius $r(C)$ centered on the codewords. The generating series for the size $V_i$ of the set of elements of weight $i$ is obtained by noticing that

$$ \sum_{c=(c_1, \dots, c_n) \in \mathbb{Z}_q^n} z^{wt(c)} = \prod_{k=1}^{n} \left( \sum_{c_k \in \mathbb{Z}_q} z^{wt(c_k)} \right), $$

where $wt(c_k)$ denotes the Euclidean weight of an element $c_k$ of $\mathbb{Z}_q$, the inner factor is independent of $k$ and equal to $1 + 2 \sum_{j=1}^t z^{j^2}$ for $t = \lfloor q/2 \rfloor$. ■

We say that $C$ is a perfect code if it meets the previous bound with equality. We derive now two non-existence results for perfect codes.

**Theorem 2** Let $C$ be a code of length $n$ and covering radius $r$ over $\mathbb{Z}_4$.

(1) If $r = 1, 2, 3$, there is no perfect code.

(2) If $r = 4$ and $n$ is even, there is no perfect code.

**Proof.** For $q = 4$, $t = \lfloor q/2 \rfloor = 2$, expand the polynomial

$$ (1 + 2x + x^4)^n = 1 + 2nx + 2(n-1)nx^2 + \frac{4}{3}(n-2)(n-1)nx^3 + \left(\frac{2}{3}(n-3)(n-2)(n-1)n + n\right)x^4 + \dots $$

Write $V_i$ as the coefficient of $x^i$.

(1) It can be seen that when $r = 1, 2, 3$, $\sum_{i=0}^r V_i$ is odd, which means that it cannot be a power of 4, i.e.,

$$ \sum_{i=0}^{r} V_i \neq 4^a, a \in \mathbb{N} $$

for $r = 1, 2, 3$. That means there is no perfect code.

(2) Similarly, when $r = 4$ and $n$ is even, there is no perfect code. ■

**Theorem 3** There is no perfect code with covering radius 2 over $\mathbb{Z}_{p^m}$ in the Euclidean metric for $p \equiv \pm 3 \pmod 8$.

**Proof.** Still using the coefficients of the expansion in the previous theorem, when the covering radius $r$ of a code is 2, we want to see whether

$$ \sum_{i=0}^{2} V_i = 1 + 2n^2 = p^x $$
has a solution with $(n, x)$ integers.

Reducing modulo $p$, and multiplying both sides by $2$, we see that this condition is equivalent to $-2 \equiv 4n^2 \pmod p$. Recall that $-1$ is a quadratic residue modulo $p$ if $p \equiv 1 \pmod 4$, and that $2$ is a quadratic residue modulo $p$ iff $p \equiv \pm 1 \pmod 4$ [17, chap. 16]. Thus if $p \equiv \pm 3 \pmod 8$ we see that $-1$ is a quadratic residue and $2$ is not. Contradiction. ■

## 3.2 Upper bounds

Let $C$ be a code over $\mathbb{Z}_q$ and

$$s(C^{\perp}) = |\{i \mid A_i(C^{\perp}) \neq 0, i \neq 0\}|,$$

where $A_i(C^{\perp})$ is the number of codes of Hamming weight $i$ in $C^{\perp}$. Then we derive the analogue of the Delsarte bound [9] for the Euclidean distance.

**Theorem 4 (Delsarte-like Bound)** Let $C$ be a code over $\mathbb{Z}_q$, then

$$r(C) \leq t^2 \cdot s(C^{\perp})$$

for $t = \lfloor q/2 \rfloor$.

**Proof.** For a code $C$, we have $d_H(C) \leq d(C) \leq t^2 \cdot d_H(C)$ with $t = \lfloor q/2 \rfloor$. Therefore, the upper bound follows from the Delsarte bound on the covering radius for the Hamming distance [5]. ■

**Remark 1** This bound is not very tight in general. See Examples 2 and 3 in Sections 4.1 and 4.2 below.

We extend here the Norse bounds on the covering radius for the Hamming distance of binary codes [14] to codes for the Euclidean distance over $\mathbb{Z}_q$. To do this we need to recall what the strength of a code is.

**Definition 1** A code has strength $s$ if each $s$-subset of the coordinates of the code contains all $s$-tuples a constant number of times.

We proceed to derive bounds of precision increasing with the strength. We begin with strength one.

**Lemma 1** Let $C$ be a code of length $n$ over $\mathbb{Z}_q$, and let $v \in \mathbb{Z}_q^n$. If $C$ has strength 1, then for $t = \lfloor q/2 \rfloor$,

$$\sum_{\mathbf{u} \in \mathbf{v} + C} wt(\mathbf{u}) = \begin{cases} \frac{n}{q} |C| \left( 2 \sum_{i=0}^{t} i^2 \right) & \text{if } q \text{ is odd,} \\ \frac{n}{q} |C| \left( 2 \sum_{i=0}^{t-1} i^2 + t^2 \right) & \text{if } q \text{ is even.} \end{cases}$$
**Proof.** Since $|v + C| = |C|$ and $v + C$ has strength $s$ if and only if $C$ has strength $s$, it is enough to prove the lemma for $v = 0$. Since $C$ has strength 1, we only have to notice that each position has an equal number of elements in $\mathbb{Z}_q = \{0, 1, \dots, q-1\}$, and so each position contributes $|C|/q$ to the sum. ■

**Theorem 5** Let $C$ be a code of length $n$ over $\mathbb{Z}_q$ and strength 1, then for $t = \lfloor q/2 \rfloor$,

$$r(C) \le \begin{cases} \lfloor \frac{n(q^2 - 1)}{12} \rfloor & \text{if } q \text{ is odd,} \\ \lfloor \frac{n(q^2 + 2)}{12} \rfloor & \text{if } q \text{ is even.} \end{cases}$$

**Proof.** Let $v \in \mathbb{Z}_q^n$. By Lemma 1, the average distance between $v$ and a codeword is

$$\bar{d} = \begin{cases} \frac{n}{q} \left( 2 \sum_{i=0}^{t} i^2 \right) & \text{if } q \text{ is odd,} \\ \frac{n}{q} \left( 2 \sum_{i=0}^{t-1} i^2 + t^2 \right) & \text{if } q \text{ is even,} \end{cases}$$

where $t = \lfloor q/2 \rfloor$. Hence at least one codeword is within distance $\lfloor \bar{d} \rfloor$ of $v$. ■

Let us introduce the discrete random variable $X_v := wt(\mathbf{u})$, with sample space the translate $-v + C$. Denote by $\mu$ the expectation $E$ of $X_v$, then

$$\mu = E(X_v) = \sum_{\mathbf{u} \in v+C} wt(\mathbf{u}) = \bar{d},$$

in the notation of the above proof. We need to consider the family of monic polynomials orthogonal for the inner product $\langle P, Q \rangle = E(PQ(X_v))$.

To treat the cases of codes two and three we will require two lemmas and a theorem.

**Lemma 2** Let $C$ be a code of length $n$ over $\mathbb{Z}_q$, and let $v \in \mathbb{Z}_q^n$. If $C$ has strength 2, then

$$\sum_{\mathbf{u} \in -v + C} wt(\mathbf{u})^2 = \binom{n}{2} \frac{|C|}{q^2} \left( \sum_{\mathbf{u} \in -v + C} wt(\mathbf{u}) \right)^2 = \binom{n}{2} \frac{|C|}{q^2} \mu^2.$$

**Proof.** We only prove the lemma for $v = 0$. Since $C$ has strength 2, we first note that $(a, b)$ occurs $|C|/q^2$ times in two fixed positions for $a, b \in \mathbb{Z}_q$. Summing over all
pairs of positions, we have

$$ 
\begin{aligned}
\sum_{\mathbf{u} \in C} wt(\mathbf{u})^2 &= \sum_{\mathbf{u} \in C} \left( \sum_{i} wt(u_i) \sum_{j} wt(u_j) \right) \\
&= \sum_{\mathbf{u} \in C} \left( \sum_{a,b \in \mathbb{Z}_q} A_{a,b} wt(a) wt(b) \right) = \binom{n}{2} \frac{|C|}{q^2} \left( \sum_{\mathbf{u} \in -\mathbf{v}+C} wt(\mathbf{u}) \right)^2,
\end{aligned}
$$

where $A_{a,b}$ represents the number of the codewords whose $i$-th position is $a$ and $j$-th position is $b$. ■

The proof of the following lemma is similar to Lemma 2 and is omitted.

**Lemma 3** Let $C$ be a code of length $n$ over $\mathbb{Z}_q$, and let $\mathbf{v} \in \mathbb{Z}_q^n$. If $C$ has strength 3, then

$$ \sum_{\mathbf{u} \in \mathbf{v}+C} wt(\mathbf{u})^3 = \binom{n}{3} \frac{|C|}{q^3} \left( \sum_{\mathbf{u} \in \mathbf{v}+C} wt(\mathbf{u}) \right)^3 = \binom{n}{3} \frac{|C|}{q^3} \mu^3. $$

**Theorem 6** Let $C$ be a code of strength 3. Then the orthogonal polynomial of degree 2 is

$$ O_2(x) = x^2 + \frac{\binom{n}{3} \frac{|C|}{q^3} - \binom{n}{2} \frac{|C|}{q^2}}{1 - \binom{n}{2} \frac{|C|}{q^2}} \mu x - \frac{\binom{n}{3} \frac{|C|}{q^3} - \left(\binom{n}{2} \frac{|C|}{q^2}\right)^2}{1 - \binom{n}{2} \frac{|C|}{q^2}} \mu^2. $$

**Proof.** It is trivial that the orthogonal polynomial of degree one is $x - \mu$, where $\mu = E(X)$. Write the orthogonal polynomial of degree 2 as $x^2 + bx + c$ with indeterminate coefficients $b, c$. Combining its orthogonality with constant polynomials and linear polynomials, we obtain the following system in unknowns $b$ and $c$.

$$ 
\begin{cases}
\mu b + c + \mu_2 = 0, \\
(\mu_2 - \mu^2)b + \mu_3 - \mu\mu_2 = 0,
\end{cases}
$$

where $\mu_2 = \binom{n}{2} \frac{|C|}{q^2} \mu^2$ and $\mu_3 = \binom{n}{3} \frac{|C|}{q^3} \mu^3$. Thus,

$$ b = \frac{\binom{n}{3} \frac{|C|}{q^3} - \binom{n}{2} \frac{|C|}{q^2}}{1 - \binom{n}{2} \frac{|C|}{q^2}} \mu \quad \text{and} \quad c = - \frac{\binom{n}{3} \frac{|C|}{q^3} - \left(\binom{n}{2} \frac{|C|}{q^2}\right)^2}{1 - \binom{n}{2} \frac{|C|}{q^2}} \mu^2. $$

This completes the proof. ■
**Theorem 7** Let C be a code of strength 3. Then

$$r(C) \leq \frac{\binom{n}{2} \frac{|C|}{q^2} - \binom{n}{3} \frac{|C|}{q^3} - \sqrt{\Delta}}{2 \left(1 - \binom{n}{2} \frac{|C|}{q^2}\right)} \mu,$$

where

$$\Delta = \left( \binom{n}{2} \frac{|C|}{q^2} - \binom{n}{3} \frac{|C|}{q^3} \right)^2 + 4 \left[ \binom{n}{3} \frac{|C|}{q^3} - \left( \binom{n}{2} \frac{|C|}{q^2} \right)^2 \right] \left( 1 - \binom{n}{2} \frac{|C|}{q^2} \right).$$

**Proof.** Let $x_0$ denote the smallest zero of the orthogonal polynomial of degree 2. According to the result of [23], we have $r(C) \leq x_0$. It follows from Theorem 6 that

$$x_0 = \frac{\binom{n}{2} \frac{|C|}{q^2} - \binom{n}{3} \frac{|C|}{q^3} - \sqrt{\Delta}}{2 \left(1 - \binom{n}{2} \frac{|C|}{q^2}\right)} \mu,$$

$$\text{where } \Delta = \left( \binom{n}{2} \frac{|C|}{q^2} - \binom{n}{3} \frac{|C|}{q^3} \right)^2 + 4 \left[ \binom{n}{3} \frac{|C|}{q^3} - \left( \binom{n}{2} \frac{|C|}{q^2} \right)^2 \right] \left( 1 - \binom{n}{2} \frac{|C|}{q^2} \right). \blacksquare$$

**Remark 2** Since the value of $|C|$ depends on $n$ and $q$, we could not manage to derive an asymptotic version of that bound.

Since strength 3 is needed to determine the first three moments of the variable $X_v$, we need to assume an extra property for codes of strength 2 but possibly not three.

**Definition 2** [15] A code C over $\mathbb{Z}_q$ is self-complementary if

$$\forall \mathbf{c} \in C, \forall \omega \in \mathbb{Z}_q, \bar{c}^{\omega} = (\omega, \dots, \omega) + \mathbf{c} \in C.$$

**Theorem 8** If C is a self-complementary code over $\mathbb{Z}_q$ of length $n$ and strength 2, then

$$r(C) \leq \frac{q-1}{q} nT - \frac{nT}{q} \sqrt{(q-1)\left(\binom{n}{2} \frac{|C|^2}{q^2} - 1\right)},$$

$$\text{where } T = \frac{q^3 + 2q}{12(q - 1)}.$$
**Proof.** Let $\mathbf{v} \in \mathbb{Z}_q^n$ such that its distance to any codeword is at least $r$, i.e. $\forall \mathbf{u} \in \mathbf{v} + C, wt(\mathbf{u}) \ge r$. Since $C$ is self-complementary, then $\bar{\mathbf{u}}^\omega \in \mathbf{v} + C$ and $wt(\bar{\mathbf{u}}^\omega) \ge r$. We have

$$ \sum_{\omega \in \mathbb{Z}_q} wt(\bar{\mathbf{u}}^\omega) = n \left( \sum_{\omega \in \mathbb{Z}_q} wt(\omega) \right), $$

where

$$ \sum_{\omega \in \mathbb{Z}_q} wt(\omega) = \begin{cases} 2 \sum_{i=0}^{t} i^2 & \text{if } q \text{ is odd,} \\ 2 \sum_{i=0}^{t-1} i^2 + t^2 & \text{if } q \text{ is even,} \end{cases} $$

for $t = \lfloor q/2 \rfloor$, which means $\sum_{\omega \in \mathbb{Z}_q} wt(\omega) \le \frac{q^3 + 2q}{12}$.

Write $T = \frac{q^3 + 2q}{12(q-1)}$, and assume $r > \frac{q-1}{q}nT$, then

$$ \frac{q-1}{q}nT < r \le wt(\mathbf{u}) = n\left(\sum_{\omega \in \mathbb{Z}_q} wt(\omega)\right) - \sum_{\omega \in \mathbb{Z}_q^*} wt(\bar{\mathbf{u}}^\omega) \\ \le n(q-1)T - (q-1)r < \frac{q-1}{q}nT. $$

It leads to a contradiction. Write $r = \frac{q-1}{q}nT - \rho$ with $\rho \ge 0$ and we have

$$ \begin{aligned} \sum_{\omega \in \mathbb{Z}_q} wt(\bar{\mathbf{u}}^\omega)^2 &= \sum_{\omega \in \mathbb{Z}_q^*} wt(\bar{\mathbf{u}}^\omega)^2 + wt(\mathbf{u})^2 \\ &= \sum_{\omega \in \mathbb{Z}_q^*} wt(\bar{\mathbf{u}}^\omega)^2 + \left( n \left( \sum_{\omega \in \mathbb{Z}_q} wt(\omega) \right) - \sum_{\omega \in \mathbb{Z}_q^*} wt(\bar{\mathbf{u}}^\omega) \right)^2 \\ &\le (q-1)r^2 + (q-1)^2(nT-r)^2 \\ &= (q-1) \left( \frac{q-1}{q}nT - \rho \right)^2 + (q-1)^2 \left( \frac{nT}{q} + \rho \right)^2 \\ &= q \left( \frac{(q-1)^2}{q^2}n^2T^2 + (q-1)\rho^2 \right). \end{aligned} $$

Decomposing $C$ into cosets of the repetition code $\{(\omega, \dots, \omega) \mid \omega \in \mathbb{Z}_q\}$, we derive

$$ \sum_{\mathbf{u} \in \mathbf{v} + C} wt(\mathbf{u})^2 \le |C| \left( \frac{(q-1)^2}{q^2} n^2 T^2 + (q-1)\rho^2 \right). $$
Then

$$ \left(\binom{n}{2}\right) \frac{|C|}{q^2} \left(\frac{n}{q}|C|(q-1)T\right)^2 \leq |C| \left(\frac{(q-1)^2}{q^2} n^2 T^2 + (q-1)\rho^2\right). $$

Hence

$$ \rho^2 \geq \frac{q-1}{q^2} n^2 T^2 \left( \binom{n}{2} \frac{|C|^2}{q^2} - 1 \right). $$

Since $\rho \geq 0$,

$$ r \leq \frac{q-1}{q} nT - \frac{nT}{q} \sqrt{(q-1) \left( \binom{n}{2} \frac{|C|^2}{q^2} - 1 \right)}. $$

This completes the proof.

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

To ensure that the upper bound is positive, we have $\frac{n(n+1)|C|^2}{2q^3} < 1$, thus

**Remark 3** We could not drive an asymptotic result of that bound due to mutual control between $n$ and $q$.

We give the analogue of the redundancy bound for codes over $\mathbb{Z}_q = \mathbb{Z}_{p^m}$, where $p$ is a prime and $m \geq 1$. The type of the dual code (as defined in Section 2.1) plays here the role of the codimension in the classical case. The special case of codes over $\mathbb{Z}_4$ is in [1].

**Theorem 9** (Cotype Bound) Let $C$ be a code of length $n$ over $\mathbb{Z}_{p^m}$ for some prime $p$ of type $(p^m)^{k_0}(p^{m-1})^{k_1}\dots p^{k_{m-1}}$, then

$$ r(C) \leq (|p^m/2|)^2 \left( n - \sum_{i=0}^{m-1} k_i \right) + \sum_{j=1}^{m-1} (|p^j/2|)^2 k_j. $$

**Proof.** If $C$ is of type $(p^m)^{k_0}(p^{m-1})^{k_1}\dots p^{k_{m-1}}$, then the dual code $C^\perp$ is of type $(p^m)^{n-l}(p^{m-1})^{k_{m-1}}\dots p^{k_1}$, where $l = \sum_{i=0}^{m-1} k_i$. We may assume that, up to permutation, the dual code $C^\perp$ has a generator matrix of the form

$$ H = \begin{pmatrix} I_{n-l} & B_{01} & B_{02} & \cdots & B_{0,m-1} & B_{0,m} \\ 0 & pI_{k_{m-1}} & pB_{12} & \cdots & pB_{1,m-1} & pB_{1,m} \\ 0 & 0 & p^2I_{k_{m-2}} & \cdots & p^2B_{2,m-1} & p^2B_{2,m} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & p^{m-1}I_{k_1} & p^{m-1}B_{m-1,m} \end{pmatrix} $$

for $0 \le i \le j \le m$, $B_{i,j} = - \sum_{k=i+1}^{j-1} B_{i,k} A_{m-j,m-k}^T - A_{m-j,m-i}^T$.

By analogy with the $p$-ary case for some prime $p$, the set of syndromes associated, up to permutation, to the code $C$ is the set

$$ \begin{aligned} S &= \{H \boldsymbol{x}^T | \boldsymbol{x} \in \mathbb{Z}_{p^m}^n\} \\ &= \{(c_{01}, \dots, c_{0,n-l}, pc_{11}, \dots, pc_{1,k_{m-1}}, \dots, p^{m-1}c_{m-1,1}, \dots, p^{m-1}c_{m-1,k_1}); \\ & \phantom{=} c_{0,i} \in \mathbb{Z}_{p^m}, c_{1,j} \in \mathbb{Z}_{p^{m-1}}, \dots, c_{m-1,k} \in \mathbb{Z}_p \}. \end{aligned} $$
For matter of convenience, we write the vector $(c_{01}, \dots, c_{0,n-l})$ of length $(n-l)$ by $c_0$, the vector $(c_{11}, \dots, c_{1,k_{m-1}})$ of length $k_{m-1}$ by $c_1, \dots$, the vector $(c_{m-1,1}, \dots, c_{m-1,k_1})$ of length $k_1$ by $c_{m-1}$. As in the $p$-ary case for prime $p$, each syndrome is associated to a coset in a unique way. Let $\mathbf{s} = (c_0, pc_1, \dots, p^{m-1}c_{m-1})$ be a given syndrome, and let $\mathbf{x} = (c_0, c_1, \dots, c_{m-1}, 0, \dots, 0)$. Then the syndrome associated to $\mathbf{x}$ is

$$ \mathbf{s} + (t_0, t_1, \dots, t_{m-2}, 0), $$

where $t_i$ is given by $t_i = p^i \sum_{j=i+1}^{m-1} B_{i,j} c_j^T$.

Therefore, the syndrome of the vector $\mathbf{x} = (c_0 - t_0, \dots, c_{m-2} - t_{m-2}, c_{m-1}, 0, \dots, 0)$ is $\mathbf{s}$ and the $(p^m)^{n-l}(p^{m-1})^{k_{m-1}} \dots (p^2)^{k_2}$ vectors

$$ (d_0, \dots, d_{m-2}, c_{m-1}, 0, \dots, 0) $$

have distinct syndromes of $S$ with fixed $c_{m-1}$, where $d_0 \in \mathbb{Z}_{p^m}^{n-l}$, $d_j \in \mathbb{Z}_{p^{m-j}}^{k_{m-j}}$ for $j = 1, \dots, m-2$ and $c_{m-1} \in \mathbb{Z}_p^{k_1}$.

In such a way we have constructed an element of each possible coset. The bound now follows from the covering radius of $C$, with respect to a given distance, which is the largest minimum weight among all the different cosets. This gives for the Euclidean distance

$$ r(C) \leq \max\{wt(c_0, c_1, \dots, c_{m-1}, 0, \dots, 0)\} = (\lfloor p^m/2 \rfloor)^2(n-l) + \sum_{j=1}^{m-1} (\lfloor p^j/2 \rfloor)^2 k_j, $$

$$ \text{where } c_0 \in \mathbb{Z}_{p^m}^{n-l}, c_1 \in \mathbb{Z}_{p^{m-1}}^{k_{m-1}}, \dots, c_{m-1} \in \mathbb{Z}_p^{k_1}. \quad \blacksquare $$

**Remark 4** It is easy to see that that bound is tight for codes with generator matrices

$$ H = \begin{pmatrix} I_{n-\sum_{i=0}^{m-1} k_i} & 0 & 0 & \cdots & 0 & 0 \\ 0 & pI_{k_{m-1}} & 0 & \cdots & 0 & 0 \\ 0 & 0 & p^2 I_{k_{m-2}} & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & p^{m-1} I_{k_1} & 0 \end{pmatrix}. $$

**Example 1** We shall compute the redundancy bounds on some self-orthogonal codes of small lengths (see Table 1 for results), where the covering radius of codes has been provided in [1].

# 4 Repetition codes

Let $\mathbb{F}_q$ be a finite field, where $q$ is a prime power. A $q$-ary repetition code $C = \{\alpha = (\alpha, \dots, \alpha) | \alpha \in \mathbb{F}_q\}$ is an $[n, 1, n]_q$ code over $\mathbb{F}_q$. The covering radius for the Hamming distance of the repetition code $C$ over $\mathbb{F}_q$ is given by $\lfloor n(q-1)/q \rfloor$ [3]. Here we have considered two types of repetition codes over $\mathbb{Z}_{p^m}$ for some prime $p$ that were studied in [8] in relation with their covering properties for the Lee metric.
<table><caption>**Table 1:** Bounds on Self-orthogonal Codes over $\mathbb{Z}_4$</caption><thead><tr><th>Code</th><th>Type</th><th>r(C)</th><th>Bound</th></tr></thead><tbody><tr><td>D<sub>4</sub></td><td>4<sup>1</sup></td><td>6</td><td>12</td></tr><tr><td>D<sub>6</sub></td><td>4<sup>2</sup></td><td>8</td><td>16</td></tr><tr><td>D<sub>8</sub></td><td>4<sup>3</sup></td><td>10</td><td>20</td></tr><tr><td>D<sub>10</sub></td><td>4<sup>4</sup></td><td>12</td><td>24</td></tr><tr><td>D<sub>12</sub></td><td>4<sup>5</sup></td><td>16</td><td>28</td></tr><tr><td>D<sub>4</sub><sup>o</sup></td><td>4<sup>1</sup>2<sup>1</sup></td><td>4</td><td>13</td></tr><tr><td>D<sub>6</sub><sup>o</sup></td><td>4<sup>2</sup>2<sup>1</sup></td><td>7</td><td>17</td></tr><tr><td>E<sub>7</sub></td><td>4<sup>3</sup></td><td>8</td><td>16</td></tr><tr><td>A<sub>1</sub> (self-dual)</td><td>2<sup>1</sup></td><td>1</td><td>5</td></tr><tr><td>D<sub>4</sub><sup>⊕</sup> (Type II)</td><td>4<sup>1</sup>2<sup>2</sup></td><td>4</td><td>14</td></tr><tr><td>E<sub>7</sub><sup>+</sup> (self-dual)</td><td>4<sup>3</sup>2<sup>1</sup></td><td>7</td><td>17</td></tr><tr><td>E<sub>8</sub> (self-dual)</td><td>4<sup>4</sup></td><td>8</td><td>16</td></tr></tbody></table>

## 4.1 Unit repetition codes

Let $u$ be a unit in the ring $\mathbb{Z}_{p^m}$. The code $C_u$ generated by the matrix $G_u = [\underbrace{uu\cdots u}_{n}]$ is called a unit repetition code. Clearly $C_u$ is a $(n, p^m, n, n)$ code over $\mathbb{Z}_{p^m}$.

**Theorem 10** Let $u$ be a unit in $\mathbb{Z}_{p^m}$, then

$$r(C_u) = \begin{cases} \frac{1}{12}n(p^m - 1)(p^m + 1) & \text{if } p \text{ is odd,} \\ \frac{1}{6}n(2^{2m-1} + 1) & \text{if } p = 2. \end{cases}$$

**Proof.** Let $\mathbf{x} \in \mathbb{Z}_{p^m}^n$ and let $w_i$ be the number of $i$ coordinates in $\mathbf{x}$ for $0 \le i \le p^m - 1$. Then $\sum_{i=0}^{p^m-1} w_i = n$. When $p$ is odd,

$$d(\mathbf{x}, \mathbf{i}) = 1 \cdot (w_{i+1} + w_{i-1}) + 2^2 \cdot (w_{i+2} + w_{i-2}) + \cdots + [(p^m - 1)/2]^2 \\ \cdot (w_{i+(p^m-1)/2} + w_{i-(p^m-1)/2}),$$

where $\mathbf{i} = (i, i, \dots, i) \in \mathbb{Z}_{p^m}^n$, $i = 0, 1, \dots, p^m - 1$. Then

$$r(C_u) \le \frac{\sum_{i=0}^{p^m-1} d(\mathbf{x}, \mathbf{i})}{p^m} = \frac{2(1 + 2^2 + \cdots + [(p^m - 1)/2]^2) \sum_{i=0}^{p^m-1} w_i}{p^m} = \frac{n(p^m - 1)(p^m + 1)}{12}.$$
Thus $r(C_u) \le \frac{1}{12}n(p^m - 1)(p^m + 1)$.

Conversely, let $\boldsymbol{x} = (\overline{0}, \overline{1}, \dots, \overline{p^m - 2}, \overline{p^m - 1}) \in \mathbb{Z}_{p^m}^n$, where $\bar{i} = ii \cdots i$ are the duplicate strings of length $l$, $i = 0, 1, \dots, p^m - 2$, $l = \lceil n/p^m \rceil$ and the remaining coordinates are all $p^m - 1$, also denoted by $\overline{p^m - 1}$. Then

$$d(\boldsymbol{x}, \boldsymbol{i}) = \left( \sum_{a \in \mathbb{Z}_{p^m}} wt(a) - wt(p^m - 1 - i) \right) l + wt(p^m - 1 - i)(n - (p^m - 1)l) \\ = n \cdot wt(p^m - 1 - i) + p^m \left( \frac{(p^m - 1)(p^m + 1)}{12} - wt(p^m - 1 - i) \right) l,$$

where $\boldsymbol{i} = (i, i, \dots, i) \in \mathbb{Z}_{p^m}^n, i = 0, 1, \dots, p^m - 1$. Thus the covering radius $r(C_u)$ is given by

$$r(C_u) \ge d(\boldsymbol{x}, C_u) = \min_{0 \le i \le p^m - 1} d(\boldsymbol{x}, \boldsymbol{i}) \ge p^m \left( \frac{(p^m - 1)(p^m + 1)}{12} \right) l \ge \frac{n(p^m - 1)(p^m + 1)}{12}.$$

Finally, when $p$ is odd, $r(C_u) = \frac{1}{12}n(p^m - 1)(p^m + 1)$.

Especially when $p = 2$,

$$d(\boldsymbol{x}, \boldsymbol{i}) = 1 \cdot (w_{i+1} + w_{i-1}) + 2^2 \cdot (w_{i+2} + w_{i-2}) + \dots + (2^{m-1})^2 \cdot w_{i+2^{m-1}},$$

where $\boldsymbol{i} = (i, i, \dots, i) \in \mathbb{Z}_{2^m}^n, i = 0, 1, \dots, 2^m - 1$. Then

$$r(C_u) \le \frac{\sum_{i=0}^{2^m-1} d(\boldsymbol{x}, \boldsymbol{i})}{p^m} = \frac{[2(1 + \cdots + (2^{m-1} - 1)^2) + (2^{m-1})^2] \sum_{i=0}^{2^m-1} w_i}{2^m} = \frac{n(2^{2m-1} + 1)}{6}.$$

It shows that $r(C_u) \le \frac{1}{6}n(2^{2m-1} + 1)$.

Conversely, let $\boldsymbol{x} = (\overline{0}, \overline{1}, \dots, \overline{2^m - 2}, \overline{2^m - 1}) \in \mathbb{Z}_{2^m}^n$, where $\bar{i} = ii \cdots i$ are the duplicate strings of length $l$, $i = 0, 1, \dots, 2^m - 2$, $l = \lceil n/2^m \rceil$ and the remaining coordinates are all $2^m - 1$, also denoted by $\overline{2^m - 1}$. Similarly, we derive $r(C_u) \ge \frac{1}{6}n(2^{2m-1} + 1)$. ■

**Example 2** We shall compute the Delsarte bounds for some repetition codes of small lengths, where the covering radius of codes are obtained from Theorem 10. All these computations were done in [4].

(1) If $C_1$ is a unit repetition code of length 4 over $\mathbb{Z}_4$, then the Delsarte bound equals 12.

(2) If $C_2$ is a unit repetition code of length 6 over $\mathbb{Z}_9$, then the Delsarte bound equals 80.
**Proof.** (1) Let $C_1$ be a unit repetition code of length 4 over $\mathbb{Z}_4$, generated by $G_1 = [1, 1, 1, 1]$. The generator matrix of the dual code $C_1^\perp$ is

$$H_1 = \begin{bmatrix} 1 & 0 & 0 & 3 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & 3 \end{bmatrix}.$$

According to the weight distribution of $C_1^\perp$, the Delsarte bound of $C_1$ is 12, where the covering radius equals 6.

(2) Let $C_2$ be a unit repetition code of length 6 over $\mathbb{Z}_9$ generated by $G_2 = [1, 1, 1, 1, 1, 1]$. The generator matrix of the dual code $C_2^\perp$ is

$$H_2 = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 8 \\ 0 & 1 & 0 & 0 & 0 & 8 \\ 0 & 0 & 1 & 0 & 0 & 8 \\ 0 & 0 & 0 & 1 & 0 & 8 \\ 0 & 0 & 0 & 0 & 1 & 8 \end{bmatrix}.$$

According to the weight distribution of $C_2^\perp$, the Delsarte bound of $C_2$ is 80, where the covering radius equals 40. ■

## 4.2 Zero divisor repetition codes

Let $z$ be a zero divisor of $\mathbb{Z}_{p^m}$. The code generated by the generator matrix $[\underbrace{zz\cdots z}_{n}]$, is called a zero divisor repetition code. The $p^{m-1}-1$ zero divisors of $\mathbb{Z}_{p^m}$ are given by $\alpha_1 p^{m-1} + \alpha_2 p^{m-2} + \cdots + \alpha_{m-2} p^2 + \alpha_{m-1} p, \alpha_i \in \{0, 1, \dots, p-1\}, 1 \le i \le m-1$, but not all $\alpha_i$ will be zero. The additive order of the zero divisors is $p, p^2, \dots, p^{m-1}$.

We first consider the zero divisors of order $p$. There are $p-1$ zero divisors of order $p$, namely $\alpha_1 p^{m-1}, \alpha_1 \in \{1, 2, \dots, p-1\}$. Let $C_p$ be the code generated by the generator matrix $G_p = [\underbrace{p^{m-1} p^{m-1} \cdots p^{m-1}}_n]$. Then $C_p = (0, \mathbf{p}^{m-1}, 2\mathbf{p}^{m-1}, \dots, (p-1)\mathbf{p}^{m-1}) \subset \mathbb{Z}_{p^m}^n$, where $\alpha = (\alpha, \dots, \alpha) \in \mathbb{Z}_{p^m}^n$, is a $(n, p, n, np^{2m-2})$ code over $\mathbb{Z}_{p^m}$.

**Theorem 11** If $p$ is odd, then

$$\frac{n(p^{2m} - p^{2m-2})}{12} \le r(C_p) \le \frac{n}{p}W_1,$$

where $W_1 = \frac{1}{12}p^{2m+1} + \frac{1}{6}p^{2m-1} - \frac{1}{2}p^m + \frac{1}{4}p$. In particular, when $p=2$, then $r(C_2) = n \cdot 2^{2m-3}$.
**Proof.** Let $\mathbf{x} \in \mathbb{Z}_{p^m}^n$ and let $w_i$ be the number of $i$ coordinates in $\mathbf{x}$ for $0 \le i \le p^m - 1$. Then $\sum_{i=0}^{p^m-1} w_i = n$. When $p$ is odd,

$$d(\mathbf{x}, \mathbf{i}) = 1 \cdot (w_{i+1} + w_{i-1}) + 2^2 \cdot (w_{i+2} + w_{i-2}) + \cdots + [(p^m - 1)/2]^2 \\ \cdot (w_{i+(p^m-1)/2} + w_{i-(p^m-1)/2}),$$

where $\mathbf{i} \in C_p$. Then

$$r(C_p) \le \frac{\sum_{\mathbf{i} \in C_p} d(\mathbf{x}, \mathbf{i})}{p} \le \frac{W_1 \cdot \sum_{i=0}^{p^m-1} w_i}{p} = \frac{n}{p} W_1,$$

where

$$W_1 = [(p^m - 1)/2]^2 + \sum_{i=1,3,5,\dots,p-2} \{[(i \cdot p^{m-1} - 1)/2]^2 + [(i \cdot p^{m-1} + 1)/2]^2\} \\ = \frac{1}{12} p^{2m+1} + \frac{1}{6} p^{2m-1} - \frac{1}{2} p^m + \frac{1}{4} p.$$

Conversely, let $\mathbf{x} = (\overline{0}, \overline{p^{m-1}}, \dots, \overline{p^m - 2p^{m-1}}, \overline{p^m - p^{m-1}}) \in \mathbb{Z}_{p^m}^n$, where $\overline{i} = ii \dots i$ are the duplicate strings of length $l$, $i = 0, p^{m-1}, \dots, p^m - 2p^{m-1}$, $l = \lceil n/p \rceil$ and the remaining coordinates are all $p^m - p^{m-1}$, also denoted by $\overline{p^m - p^{m-1}}$. Consider

$$d(\mathbf{x}, \mathbf{i}) = \left( \sum_{j=1}^{p-1} wt(jp^{m-1}) - wt(p^m - p^{m-1} - i) \right) l + wt(p^m - p^{m-1} - i)(n - (p-1)l) \\ = n \cdot wt(p^m - p^{m-1} - i) + p \left( \frac{p^{2m} - p^{2m-2}}{12} - wt(p^m - p^{m-1} - i) \right) l,$$

where $\mathbf{i} \in C_p$. Then the covering radius $r(C_p)$ is given by

$$r(C_p) \ge d(\mathbf{x}, C_p) = \min_{\mathbf{i} \in C_p} d(\mathbf{x}, \mathbf{i}) \ge p \left( \frac{p^{2m} - p^{2m-2}}{12} \right) l \ge \frac{n(p^{2m} - p^{2m-2})}{12}.$$

In particular, when $p = 2$,

$$d(\mathbf{x}, \mathbf{0}) = 1 \cdot (w_1 + w_{2^{m-1}}) + 2^2 \cdot (w_2 + w_{2^{m-2}}) + \cdots + (2^{m-1})^2 \cdot w_{2^{m-1}}, \\ d(\mathbf{x}, \mathbf{2^{m-1}}) = 1 \cdot (w_{2^{m-1}+1} + w_{2^{m-1}-1}) + 2^2 \cdot (w_{2^{m-1}+2} + w_{2^{m-1}-2}) + \cdots + (2^{m-1})^2 \cdot w_0.$$

Then

$$r(C_2) \le \frac{d(\mathbf{x}, \mathbf{0}) + d(\mathbf{x}, \mathbf{2^{m-1}})}{2} \le n \cdot 2^{2m-3}.$$

Conversely, let $\mathbf{x} = (\overbrace{0, \dots, 0}^{n/2}, \overbrace{2^{m-1}, \dots, 2^{m-1}}^{n/2}) \in \mathbb{Z}_{p^m}^n$, then

$$r(C_2) \ge \min\{d(\mathbf{x}, \mathbf{0}), d(\mathbf{x}, \mathbf{2^{m-1}})\} = \frac{n}{2}(2^{m-1})^2 = n \cdot 2^{2m-3}.$$
It shows that $r(C_2) = n \cdot 2^{2m-3}$.

**Corollary 1** Assume that odd $p$ and $n$ are fixed and $m \to \infty$, then $r(C_p) \sim \frac{np^{2m}}{12}$.

Note that for each $i, 1 \le i \le m-1$, the number of zero divisors of order $p^i$ is $p^{i-1}(p-1)$ which are given by $\alpha_1p^{m-1} + \alpha_2p^{m-2} + \dots + \alpha_ip^{m-i}$, $\alpha_j \in \{0, 1, \dots, p-1\}$, $1 \le j \le i-1$ and $\alpha_i \in \{1, 2, \dots, p-1\}$. Let $C_{p^i}$ be the code generated by the generator matrix $G_{p^i} = [p^{m-i} p^{m-i} \cdots p^{m-i}]^n$. Then $C_{p^i}$ is a $(n, p^i, n, np^{2m-2i})$ code over $\mathbb{Z}_{p^m}$. As we sum up the above ideas, we derive

**Theorem 12** For $1 \le i \le m-1$, if $p$ is odd, then

$$ \frac{n(p^{2m} - p^{2m-2i})}{12} \le r(C_{p^i}) \le \frac{n}{p^i}W_2, $$

where $W_2 = \frac{1}{12}p^{2m+i} + \frac{1}{6}p^{2m-i} - \frac{1}{2}p^m + \frac{1}{4}p^i$. Especially when $p=2$, then $r(C_{2i}) = \frac{1}{3}n(2^{2m-2} + 2^{2m-2i-1})$.

**Proof.** Let $\boldsymbol{x} \in \mathbb{Z}_{p^m}^n$ and let $w_j$ be the number of $i$ coordinates in $\boldsymbol{x}$ for $0 \le m \le p^m - 1$. Then $\sum_{j=0}^{p^m-1} w_j = n$. For $1 \le i \le m-1$, when $p$ is odd,

$$ d(\boldsymbol{x}, \boldsymbol{j}) = 1 \cdot (w_{j+1} + w_{j-1}) + 2^2 \cdot (w_{j+2} + w_{j-2}) + \dots + [(p^m - 1)/2]^2 \\ \cdot (w_{j+(p^m-1)/2} + w_{j-(p^m-1)/2}), $$

where $\boldsymbol{j} \in C_{p^i}$. Then

$$ r(C_{p^i}) \le \frac{\sum_{j \in C_{p^i}} d(\boldsymbol{x}, \boldsymbol{j})}{p^i} \le \frac{W_2 \cdot \sum_{j=0}^{p^m-1} w_j}{p^i} = \frac{n}{p^i}W_2, $$

where

$$ W_2 = [(p^m - 1)/2]^2 + \sum_{j=1,3,5,\dots,p^i-2} \{[(jp^{m-i} - 1)/2]^2 + [(jp^{m-i} + 1)/2]^2\} \\ = \frac{1}{12}p^{2m+1} + \frac{1}{6}p^{2m-i} - \frac{1}{2}p^m + \frac{1}{4}p^i. $$

Conversely, let $\boldsymbol{x} = (\overline{0}, \overline{p^{m-i}}, \dots, \overline{p^m - p^{m-1} - p^{m-i}}, \overline{p^m - p^{m-i}}) \in \mathbb{Z}_{p^m}^n$, where $\overline{j} = jj \dots j$ are the duplicate strings of length $l$, $j = 0, p^{m-i}, \dots, p^m - p^{m-1} - p^{m-i}, l =$
$[n/p^i]$ and the remaining coordinates are all $p^m - p^{m-i}$, also denoted by $\overline{p^m - p^{m-i}}$. For $j \in C_{p^i}$, consider

$$
\begin{align*}
d(\mathbf{x}, \mathbf{j}) &= (W_3 - wt(p^m - p^{m-i} - j))l + wt(p^m - p^{m-i} - j)(n - (p^i - 1)l) \\
&= n \cdot wt(p^m - p^{m-i} - j) + p^i \left( \frac{p^{2m} - p^{2m-2i}}{12} - wt(p^m - p^{m-i} - j) \right)l,
\end{align*}
$$

where

$$
\begin{align*}
W_3 &= \sum_{\alpha_{m-i}, \dots, \alpha_{m-2}, \alpha_{m-1} \in \{0, 1, \dots, p-1\}} wt(p^{m-i}\alpha_{m-i} + \dots + p^{m-2}\alpha_{m-2} + p^{m-1}\alpha_{m-1}) \\
&= 2(p^{m-i})^2 (1 + 2^2 + \dots + [(p^i - 1)/2]^2) = \frac{1}{12}(p^{2m+i} - p^{2m-i}).
\end{align*}
$$

Then the covering radius $r(C_{p^i})$ is given by

$$
r(C_{p^i}) \ge d(\mathbf{x}, C_{p^i}) = \min_{\mathbf{j} \in C_{p^i}} d(\mathbf{x}, \mathbf{j}) \ge p^i \left( \frac{p^{2m} - p^{2m-2i}}{12} \right) l \ge \frac{n(p^{2m} - p^{2m-2i})}{12}.
$$

Especially when $p=2$,

$$
d(\mathbf{x}, \mathbf{j}) = 1 \cdot (w_{j+1} + w_{j-1}) + 2^2 \cdot (w_{j+2} + w_{j-2}) + \dots + (2^{m-1})^2 \cdot w_{j+2^{m-1}},
$$

where $j \in C_{2i}$. Similarly, we derive

$$
r(C_{2^i}) \le \frac{\sum_{j \in C_{2^i}} d(\mathbf{x}, j)}{2^i} \le \frac{W_4 \cdot \sum_{i=0}^{p^{m-1}} w_i}{2^i} = \frac{1}{3} n(2^{2m-2} + 2^{2m-2i-1}),
$$

where

$$
\begin{align*}
W_4 &= \sum_{\alpha_{m-i}, \dots, \alpha_{m-2}, \alpha_{m-1} \in \{0,1\}} wt(2^{m-i}\alpha_{m-i} + \dots + 2^{m-2}\alpha_{m-2} + 2^{m-1}\alpha_{m-1}) \\
&= 2(2^{m-i})^2 [1 + 2^2 + \dots + (2^{i-1} - 1)^2] + (2^{m-1})^2 = \frac{1}{3}(2^{2m+i-2} + 2^{2m-i-1}).
\end{align*}
$$

Conversely, let $\mathbf{x} = (\overline{0}, \overline{2^{m-i}}, \dots, \overline{2^m - 2^{m-1} - 2^{m-i}}, \overline{2^m - 2^{m-i}}) \in \mathbb{Z}_{2^m}^n$, where $\overline{j = jj \dots j}$ are the duplicate strings of length $l$, $j = 0, 2^{m-i}, \dots, 2^m - 2^{m-1} - 2^{m-i}$, $l = \lceil n/2^i \rceil$ and the remaining coordinates are all $2^m - 2^{m-i}$, also denoted by $\overline{2^m - 2^{m-i}}$. Consider

$$
\begin{align*}
d(\mathbf{x}, \mathbf{j}) &= (W_4 - wt(2^m - 2^{m-i} - j))l + wt(2^m - 2^{m-i} - j)(n - (2^i - 1)l) \\
&= n \cdot wt(2^m - 2^{m-i} - j) + 2^i \left( \frac{2^{2m-2} + 2^{2m-2i-1}}{3} - wt(2^m - 2^{m-i} - j) \right)l,
\end{align*}
$$
where $j \in C_{2i}$, $W_4$ is still as indicated in the previous text. Then the covering radius $r(C_{2i})$ is given by

$$r(C_{2i}) \ge d(\mathbf{x}, C_{2i}) = \min_{j \in C_{2i}} d(\mathbf{x}, j) \ge 2^i \left( \frac{2^{2m-2} + 2^{2m-2i-1}}{3} \right) l \ge \frac{1}{3} n(2^{2m-2} + 2^{2m-2i-1}).$$

It shows that $r(C_{2i}) = \frac{1}{3}n(2^{2m-2} + 2^{2m-2i-1})$. ■

**Corollary 2** For $1 \le i \le m-1$, assume that odd $p$ and $n$ are fixed and $m \to \infty$, then $r(C_{p^i}) \sim \frac{np^{2m}}{12}$.

**Example 3** We shall compute the Delsarte bounds on some repetition codes of small lengths by using the algorithm in [4], where the covering radius of codes are obtained from Theorems 11 and 12.

(1) If $C_3$ is a zero divisor repetition code of order $2^2$ and length 4 over $\mathbb{Z}_8$, then the Delsarte bound equals 64.

(2) If $C_4$ is a zero divisor repetition code of order 2 and length 3 over $\mathbb{Z}_8$, then the Delsarte bound equals 48.

**Proof.** (1) If $C_3$ is a zero divisor repetition code of order $2^2$ and length 4 over $\mathbb{Z}_8$, generated by $G_3 = [4, 4, 4, 4]$ then the generator matrix of the dual code $C_3^\perp$ is

$$H_3 = \begin{bmatrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 2 \end{bmatrix}.$$

According to the weight distribution of $C_3^\perp$, the Delsarte bound of $C_3$ is 64, where the covering radius equals 32.

(2) If $C_4$ is a zero divisor repetition code of order 2 and length 3 over $\mathbb{Z}_8$, generated by $G_4 = [2, 2, 2]$ then the generator matrix of the dual code $C_4^\perp$ is

$$H_4 = \begin{bmatrix} 1 & 0 & 3 \\ 0 & 1 & 3 \\ 0 & 0 & 4 \end{bmatrix}.$$

According to the weight distribution of $C_4^\perp$, the Delsarte bound of $C_4$ is 48, where the covering radius equals 18. ■
# 5 Covering spherical codes

We inject $\mathbb{R}^n$ into $\mathbb{R}^{n+1}$ by the Yaglom map

$$Y: \boldsymbol{x} \mapsto (\boldsymbol{x}, \sqrt{R^2 - \boldsymbol{x} \cdot \boldsymbol{x}}),$$

which sends the ball $B(n, R)$ of radius $R$ in $\mathbb{R}^n$

$$B(n, R) := \{\boldsymbol{x} \in \mathbb{R}^n \mid \boldsymbol{x} \cdot \boldsymbol{x} \leq R^2\}$$

into the sphere $S(n, R)$ of radius $R$ in $\mathbb{R}^{n+1}$

$$S(n, R) := \{\boldsymbol{x} \in \mathbb{R}^{n+1} \mid \boldsymbol{x} \cdot \boldsymbol{x} = R^2\}.$$

The following proposition for spherical codes is given in [22].

**Proposition 2** If $C$ is a code of length $n$ over $\mathbb{Z}_q$, then $Y(C)$ is a spherical code of $S(n, t\sqrt{n})$ for $t = \lfloor q/2 \rfloor$.

Building on that result, we give a bound on the covering radius of a spherical code, Yaglom map image of a code over $\mathbb{Z}_q$ with a given covering radius for the Euclidean distance.

**Theorem 13** Let $C$ be a code of length $n$ over $\mathbb{Z}_q$, of covering radius $r(C)$ for the Euclidean distance. Let $Z$ be a point of the unit sphere in $n+1$ dimensions. Then

$$d(Z, Y(C)) \leq n/4t^2 + r(C) + 1.$$

**Proof.** Write $Z = (\boldsymbol{z}, Z_{n+1})$, where $\boldsymbol{z}$ represents the first $n$-dimensional vector of $Z$ and $\|Z_i\| \leq 1$ for $i = 1, \dots, n+1$. For any $\boldsymbol{c} \in C$, we have $\|\boldsymbol{c}\|^2 \leq nt^2$ for $t = \lfloor q/2 \rfloor$. Now $\boldsymbol{z}$ can be approximated by $\boldsymbol{y}$ in $\mathbb{Z}_q^n$ with $y_i = [tz_i]$, where $[x]$ is the closest integer to the real of $x$. Then

$$d(\boldsymbol{z}, \boldsymbol{y}/t) \leq n/4t^2.$$

It is easily seen that $d(\boldsymbol{y}/t, C) \leq r(C)$, hence $d(Z, Y(C)) \leq n/4t^2 + r(C) + 1$, where the last one comes from the contribution of $Z_{n+1}$. ■

# 6 Conclusion and open problems

In this paper, we have considered the covering radius of Euclidean codes from the standpoint of upper and lower bounds, and we have determined explicitly the covering radii of free repetition codes. The sphere covering bound and perfect codes have been considered. A classification of perfect codes by the parameters is a very remote goal at this point. In the domain of lower bounds, a linear programming
bound on the size of covering codes of given length, alphabet and covering radius is a worthy project. We have determined the covering radius of free repetition codes. There are many other families of codes to consider like Simplex, BCH, geometric codes and so on. We have constructed covering spherical codes by use of the Yaglom map. Deriving a decoding algorithm of spherical codes built in that way based on the complete decoding of Euclidean codes is a fruitful avenue of research.

**Declarations**

**Data availability** No data.

**Conflict of Interest** The authors declare no conflict of interest.

**References**

[1] T. Aoki, P. Gaborit, M. Harada, M. Ozeki and P. Solé, On the covering radius of $\mathbb{Z}_4$-codes and their lattices, *IEEE Trans. Inf. Theory*, vol. 45, no. 6, pp. 2162-2168, Sep. 1999.

[2] E. Bannai, S. T. Dougherty, M. Harada and M. Oura, Type II codes, even unimodular lattices, and invariant rings, *IEEE Trans. Inf. Theory*, vol. 45, no. 4, pp. 1194-1205, May 1999.

[3] M. C. Bhandari and C. Durairajan, On the covering radius of Simplex codes, *J. Discret. Math. Sci. Cryptogr.*, vol. 6, no. 1, pp. 59-69, Jun. 2003.

[4] W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I: The user language, *J. Symb. Comput.*, vol. 24, pp. 235-265, Sep. 1997.

[5] G. D. Cohen, I. S. Honkala, S. Litsyn and A. Lobstein, *Covering Codes*, North Holland, Amsterdam, 1997.

[6] G. D. Cohen, M. G. Karpovsky, H. F. Mattson and J. R. Schatz, Covering radius-survey and recent results, *IEEE Trans. Inf. Theory*, vol. 31, no. 3, pp. 328-343, May 1985.

[7] G. D. Cohen, S. Litsyn, A. C. Lobstein and H. F. Mattson, Covering radius 1985-1994, *Appl. Algebra Eng. Commun. Comput.*, vol. 8, no. 3, pp. 173-239, Feb. 1997.

[8] M. Cruz, C. Durairajan and P. Solé, On the covering radius over $\mathbb{Z}_{p^k}$, *Mathematics*, vol. 8, no. 3, p. 328, Mar. 2020.
[9] P. Delsarte, Four fundamental parameters of a code and their combinatorial significance, *Inf. Control*, vol. 23, no. 5, pp. 407-438, Dec. 1973.

[10] T. Ericson and V. Zinoviev, *Codes on Euclidean spheres*, North Holland, 2001.

[11] G. Fazekas and V. I. Levenshtein, On upper bounds for code distance and covering radius of designs in polynomial metric spaces, *J. Comb. Theory Ser. A*, vol. 70, no. 2, pp. 267-288, May 1995.

[12] J. Hamkins and K. Zeger, Structured spherical codes for Gaussian quantization, *Proceedings of IEEE International Symposium on Information Theory*, p. 62, Jul. 1997.

[13] M. Harada and M. Kitazume, $Z_4$-Code Constructions for the Niemeier Lattices and their Embeddings in the Leech Lattice, *Eur. J. Comb.*, vol. 21, no. 4, pp. 473-485, May 2000.

[14] T. Helleseth, T. Kløve and J. Mykkelveit, On the covering radius of binary codes, *IEEE Trans. Inf. Theory*, vol. 24, no. 5, pp. 627-628, Sep. 1978.

[15] E. Leducq, On the covering radius of first-order generalized Reed Muller codes, *IEEE Trans. Inf. Theory*, vol. 59, no. 3, pp. 1590-1596, Mar. 2013.

[16] https://www.lri.fr/~lobstein/bib-a-jour.pdf

[17] F. J. MacWilliams and N. J. A. Sloane, *The theory of Error Correcting codes*, North Holland, Amsterdam, 1977.

[18] G. Norton and A. Salagean, On the structure of linear and cyclic Codes over a finite chain ring, *Appl. Algebra Eng. Commun. Comput.*, vol. 10, pp. 489-506, Jul. 2000.

[19] M. Shi, A. Alahmadi and P. Solé, *Codes and Rings: Theory and Practice*, Academic Press, an imprint of Elsevier, Amsterdam, 2017.

[20] http://neilsloane.com/coverings/index.html

[21] P. Solé, The covering radius of spherical designs, *Eur. J. Comb.*, vol. 12, no. 5, pp. 423-431, Sep. 1991.

[22] P. Solé and J.-C. Belfiore, Constructive spherical codes near the Shannon bound, *Des. Codes Cryptogr.*, vol. 66, pp. 17-26, Jan. 2013.

[23] P. Solé, Packing radius, covering radius, and dual distance, *IEEE Trans. Inf. Theory*, vol. 41, no. 1, pp. 268-272, Jan. 1995.

[24] https://arxiv.org/abs/1709.01624