Bounds on sphere sizes in the sum-rank metric and coordinate-additive metrics

Open Access
08.03.2025

Erschienen in:

Verfasst von: Hugo Sauerbier Couvée; Thomas Jerkovits; Jessica Bariffi
Erschienen in: Designs, Codes and Cryptography | Ausgabe 7/2025

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Patentsuche

Aus

Abstract

Der Artikel untersucht die Grenzen der Kugelgrößen in der Summe-Rang-Metrik und der Koordinaten-Additiv-Metrik, die für das Verständnis der Leistungsgrenzen von Codes unverzichtbar sind. Es führt neue obere und untere Grenzen ein, indem es informationstheoretische Argumente verwendet und Funktionen generiert, die bestehende Grenzen deutlich verbessern. Der Aufsatz vergleicht diese neuen Grenzen auch mit bestehenden und zeigt ihre Überlegenheit in verschiedenen Szenarien auf. Diese Arbeit ist besonders wertvoll für Forscher und Praktiker in der Verschlüsselungstheorie und Kryptographie und bietet neue Erkenntnisse und Werkzeuge für ein besseres Verständnis und die Gestaltung von Fehlerkorrekturcodes.

KI-Generiert

Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.

Hinweise

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

1 Introduction

Classically, the study of error-correcting codes focuses on codes in the Hamming metric [10] where the amount of errors happening depends on the number of entries that change during the transmission. With different applications, other coordinate-additive metrics were introduced and gained more attention. The sum-rank metric [19], Lee metric [14], and also the Hamming metric, are examples of coordinate-additive metrics. Codes with distance properties in such metrics are of particular interest in various applications, such as linear network coding [16], quantum-resistant cryptography [11, 21], coding for storage [17], space-time coding [22].

One crucial task is to understand the performance limits of codes endowed with a given coordinate-additive metric. Bounds like the sphere-packing bound or the Gilbert–Varshamov bound [7] play a crucial role in understanding these limits, and are derived using bounds on the size of an $\ell $-dimensional ball or sphere in the corresponding metrics. The exact value for the size of an $\ell $-dimensional sphere $\mathcal {S}_{t}^{\ell }$ of radius t in any coordinate-additive metric can be derived by computing all its (ordered) integer partitions, where each part of the partition has at most a part size of the maximal possible weight in the corresponding metric. These represent the decomposition of the nonzero entries of the elements in the sphere. To obtain the size of the sphere, we sum over all integer partitions, adding up the number of elements that have a weight decomposition corresponding to the integer partition. Although this procedure provides the exact value of $\left| {\mathcal {S}_t^{\ell }}\right| $, it often does not give an intuitive or practical understanding of the sphere size or how this size changes as the parameters change. For large parameters, it is even impractical to compute the size in this way. Hence, the derivation of closed-form bounds on the exact formula is of major interest. A current method of obtaining both upper and lower bounds on $\left| {\mathcal {S}_{t}^{\ell }}\right| $ is to consider only the partition attaining the maximum number of elements. This approach is utilized by [9, 20, 21]. Another method is to bound the size of an $\ell $-dimensional ball $\mathcal {B}_{t}^{\ell }$ of radius t, since every upper bound on $\left| {\mathcal {B}_{t}^{\ell }}\right| $ is also a valid upper bound on $\left| {\mathcal {S}_{t}^{\ell }}\right| $. On a complex analytic side, sizes of spheres and balls can be described using generating functions, whose coefficients can be computed using the saddle-point technique and other techniques from analytic combinatorics (see [5, 6]). In 1994, Löliger presented an information-theoretic approach for bounding the volume of an $\ell $-dimensional ball concerning any coordinate-additive metric, via the entropy of an auxiliary probability distribution [15]. Similar arguments have been used to derive bounds for Lee-metric codes [1, 2].

Specifically addressing the sum-rank metric, closed-form upper and lower bounds for the sphere size were introduced in [20, 21] and further discussed in [9]. However, these bounds are limited in their tightness, particularly noticeable in scenarios involving smaller sizes of the base field q and/or a larger number of blocks $\ell $.

In this paper we will discuss different approaches to bound sizes of spheres in a coordinate-additive metric. We derive novel improved lower and upper bounds on that size first in a general setting for any coordinate-additive metric and later explicitly focusing on the sum-rank metric. The paper is organized as follows. We start by introducing the basic notions and concepts needed throughout the paper in Sect. 2. In Sect. 3 we present bounds on the size of a sphere coming from an information-theoretic argument. We start the section by introducing the entropy function of a random variable, as well as the probability distribution of a typical sequence in an $\ell $-dimensional sphere endowed with a given coordinate-additive metric. Furthermore, we recap existing upper bounds given by the entropy of the typical sequences. In a next step, we give novel upper and lower bounds using the entropy of a typical sequence. The bounds derived hold for any coordinate-additive metric over a given alphabet. We then turn our attention to the sum-rank metric in Sect. 4 where we first recap the existing bounds on the size of an $\ell $-dimensional sphere in the sum-rank metric. Next, we present improved upper and lower bounds on the size of such a sphere using convolution arguments and ordinary generating functions, respectively. The new bounds presented in the Sects. 3 and 4 are then compared to already existing bounds in Sect. 5. Final conclusions are given in Sect. 6.

2 Preliminaries

In this section, we introduce the necessary definitions, notations, and concepts that are used throughout the paper. In the following, let q be a prime power and denote by $\mathbb {F}_q$ the finite field of q elements. The natural numbers $\mathbb {N}$ include 0.

2.1 Coordinate-additive metrics

Let $(\mathcal {A},+)$ be a finite abelian group with identity element 0 called the alphabet. We define a weight function ${{\,\textrm{wt}\,}}_{\mathcal {A}}: \mathcal {A}\rightarrow \mathbb {N}$ on $\mathcal {A}$ to be a function satisfying for all $a,b\in \mathcal {A}$:

${{\,\textrm{wt}\,}}_{\mathcal {A}}(a) = 0$ if and only if $a=0$,

${{\,\textrm{wt}\,}}_{\mathcal {A}}(a) = {{\,\textrm{wt}\,}}_{\mathcal {A}}(-a)$,

${{\,\textrm{wt}\,}}_{\mathcal {A}}(a+b) \le {{\,\textrm{wt}\,}}_{\mathcal {A}}(a) + {{\,\textrm{wt}\,}}_{\mathcal {A}}(b)$.

This function can be extended to a coordinate-additive weight function on the cartesian product $\mathcal {A}^{\ell }$ (with group structure inherited coordinate-wise from $\mathcal {A}$) by defining the weight of an $\ell $-tuple to be the sum of the weights of its coordinates, i.e.,

$$\begin{aligned} {{\,\textrm{wt}\,}}_{\Sigma \mathcal {A}}(a_1,\ldots ,a_\ell ) = \sum _{i=1}^{\ell }{{\,\textrm{wt}\,}}_{\mathcal {A}}(a_i). \end{aligned}$$

This coordinate-additive weight function naturally induces a metric

$$\begin{aligned} \begin{array}{cccc} {{\,\textrm{d}\,}}_{\Sigma \mathcal {A}}: & \mathcal {A}^{\ell } \times \mathcal {A}^{\ell } & \longrightarrow & \mathbb {N}\\ & (v, w) & \longmapsto & {{\,\textrm{wt}\,}}_{\Sigma \mathcal {A}}(v-w). \end{array} \end{aligned}$$

Examples of well-studied metrics induced by coordinate-additive weight functions are the Hamming metric with weight function

$$\begin{aligned} \begin{array}{cccc} {{\,\textrm{wt}\,}}_H: & \mathcal {A}^{\ell } & \longrightarrow & \mathbb {N}\\ & (a_1,\ldots ,a_\ell ) & \longmapsto & \sum _{i=1}^{\ell } [a_i \ne 0] \end{array} \end{aligned}$$

where $[\cdot ]$ denotes the Iverson bracket and the Lee metric with weight function

$$\begin{aligned} \begin{array}{cccc} {{\,\textrm{wt}\,}}_L : & (\mathbb {Z}/n\mathbb {Z})^{\ell } & \longrightarrow & \mathbb {N}\\ & (a_1,\ldots ,a_\ell ) & \longmapsto & \sum _{i=1}^{\ell } \min (a_i, n-a_i), \end{array} \end{aligned}$$

Of particular interest to this paper is the sum-rank metric on $\mathbb {F}_q^{m \times n}$, the space of $m \times n$ matrices over the finite field $\mathbb {F}_q$ with m and n positive integers. In this paper, we focus on the case where $n = \eta \ell $, for two positive integers $\eta $ and $\ell $. Then, under the isomorphism $\mathbb {F}_q^{m \times n} = \mathbb {F}_q^{m \times \eta \ell } \cong (\mathbb {F}_q^{m \times \eta })^{\ell }$, every matrix $M \in \mathbb {F}_q^{m \times n}$ can be represented as a sequence of $\ell $ blocks of $m \times \eta $ matrices $B_i \in \mathbb {F}_{q}^{m \times \eta }$, i.e. $M = (B_1 \mid B_2 \mid \ldots \mid B_\ell )$, and its sum-rank weight is given by the weight function

$$\begin{aligned} \begin{array}{cccc} {{\,\textrm{wt}\,}}_{\Sigma R}: & (\mathbb {F}_q^{m \times \eta })^{\ell } & \longrightarrow & \mathbb {N}\\ & (B_1 \mid B_2 \mid \ldots \mid B_\ell ) & \longmapsto & \sum _{i=1}^{\ell } {{\,\textrm{rk}\,}}_q(B_i). \end{array} \end{aligned}$$

Here ${{\,\textrm{rk}\,}}_q(B_i)$ denotes the rank of $B_i$ over $\mathbb {F}_q$. The special case of the sum-rank metric with $\ell = 1$ is called the rank-metric. Also note that the cases $m = 1$ or $\eta = 1$ are examples of the Hamming metric.

Given a coordinate-additive weight function ${{\,\textrm{wt}\,}}_{\Sigma \mathcal {A}}(\cdot )$ on $\mathcal {A}^{\ell }$, it is important to understand the size of an $\ell $-dimensional sphere and ball, respectively, of radius $t \in \mathbb {N}$ defined as

$$\begin{aligned} \mathcal {S}_t^{\ell }&:= \{v \in \mathcal {A}^{\ell } \ : \ {{\,\textrm{wt}\,}}_{\Sigma \mathcal {A}}(v) = t\} = {{\,\textrm{wt}\,}}_{\Sigma \mathcal {A}}^{-1}(t) \nonumber \\ \mathcal {B}_t^{\ell }&:= \{v \in \mathcal {A}^{\ell } \ : \ {{\,\textrm{wt}\,}}_{\Sigma \mathcal {A}}(v) \le t\} = {{\,\textrm{wt}\,}}_{\Sigma \mathcal {A}}^{-1}(\{0,1,\ldots ,t\}). \end{aligned}$$

(1)

Clearly, the following identities are satisfied

$$\begin{aligned} \mathcal {S}_i^{\ell } \cap \mathcal {S}_j^{\ell } = \emptyset \text { if } i \ne j, \quad \mathcal {B}_t^{\ell } = \bigcup _{i=0}^t \mathcal {S}_i^{\ell } \quad \text {and} \quad \mathcal {S}_t^{\ell } = \mathcal {B}_t^{\ell } \setminus \mathcal {B}_{t-1}^{\ell }. \end{aligned}$$

For the sum-rank metric we define

$$\begin{aligned} \mu _{\Sigma R}:= \min \{m,\eta \} \, \text { and }\, n:= \eta \ell , \end{aligned}$$

and denote for every $0 \le t \le \mu _{\Sigma R}\ell $ the sum-rank sphere and sum-rank ball, respectively, of radius t by

$$\begin{aligned} \mathcal {S}^{m,\eta ,\ell ,q}_t&:= \{M \in \mathbb {F}_q^{m \times \eta \ell } \ : \ {{\,\textrm{wt}\,}}_{\Sigma R}(M) = t\} \\ \mathcal {B}^{m,\eta ,\ell ,q}_t&:= \{M \in \mathbb {F}_q^{m \times \eta \ell } \ : \ {{\,\textrm{wt}\,}}_{\Sigma R}(M) \le t\}. \end{aligned}$$

For fixed m,$\eta $,q,$\ell $, the sum-rank sphere sizes $\big |\mathcal {S}^{m,\eta ,\ell ,q}_t\big |$ can be computed with a dynamic program described in [21] or a closed-form described in Sect. 2.2. However, this formula is generally not practical to work with when an intuitive understanding of the approximate size is needed, such as theorems involving sphere-packings or sphere-coverings. Therefore, easy-to-work-with approximations or lower/upper bounds for the sphere sizes for all m,$\eta $,q,$\ell $ are of value to research on the sum-rank metric.

2.2 Sizes of spheres

Consider an alphabet $\mathcal {A}$ and a coordinate-additive weight ${{\,\textrm{wt}\,}}_{\mathcal {A}}$. Let $\ell $ and t be positive integers and $\mathcal {S}^{\ell }_{t}$ be the $\ell $-dimensional sphere of radius t with respect to the weight ${{\,\textrm{wt}\,}}_{\mathcal {A}}$ as introduced in (1). The exact size of $\mathcal {S}^{\ell }_{t}$ can be obtained by computing all the (ordered) integer partitions of t, where each part size is at most the maximum possible weight in the corresponding metric. More explicitly, let us define the set of all possible weights in $\mathcal {A}$ by

$$\begin{aligned} W_\mathcal {A}= \{{{\,\textrm{wt}\,}}_{\mathcal {A}}(a) \, \ a \in \mathcal {A}\} \subset \mathbb {N}. \end{aligned}$$

Let us denote the maximum possible weight in $W_\mathcal {A}$ by $\mu := \max _{a\in \mathcal {A}}\left\{ { {{\,\textrm{wt}\,}}_{\mathcal {A}}(a)}\right\} $. We denote by $A_j$ the number of elements $a \in \mathcal {A}$ of weight $j \in W_\mathcal {A}$, i.e.,

$$\begin{aligned} A_j = \left| {\{a \in \mathcal {A}\, \ {{\,\textrm{wt}\,}}_{\mathcal {A}}(a) = j\}}\right| . \end{aligned}$$

Furthermore, for $t,\ell \in \mathbb {N}$, let $\mathcal {T}^{\ell }_{t}$ denote the set of all (ordered) integer partitions of t of length $\ell $ with part sizes not exceeding $\mu $, i.e.,

$$\begin{aligned} \mathcal {T}_t^\ell := \{(t_1,t_2,\ldots ,t_\ell ) \in W_\mathcal {A}^{\, \ell } \ : \ t_1 + t_2 + \ldots + t_\ell = t \}. \end{aligned}$$

Then, the size of the $\ell $-dimensional sphere of radius t can be computed as

$$\begin{aligned} \left| {\mathcal {S}_t^{\ell }}\right| = \sum _{\begin{array}{c} (t_1,\ldots , t_\ell ) \in \mathcal {T}_t^\ell \end{array}} \, \prod _{i=1}^\ell A_{t_i} . \end{aligned}$$

(2)

This formula can further be reduced depending on the metrics considered. For instance, in the Hamming metric, since tuples of Hamming weight t consist of t nonzero positions, we compute the number of ways to choose t positions among a total number of positions $\ell $ and multiply by the number of options we have to choose the nonzero element from, i.e.,

$$\begin{aligned} \left| {\mathcal {S}^{\ell }_{t, \textsf{H}}}\right| = \left( {\begin{array}{c}\ell \\ t\end{array}}\right) (\left| {\mathcal {A}}\right| - 1)^{t}. \end{aligned}$$

Hence, in the Hamming metric we obtain a compact closed form expression for $\left| {\mathcal {S}^{\ell }_{t}}\right| $. However, when changing the metric this task can get more involved, as the set $\mathcal {T}^{\ell }_t$ might grow rapidly and, thus, summing over all its elements would be an exhaustive task. Therefore, finding simpler upper and lower bounds on the sum or the single summands is an important task.

For a fixed weight function ${{\,\textrm{wt}\,}}_{\mathcal {A}}$ and fixed integers t, $\ell $ the sphere sizes $\left| \mathcal {S}^{\ell }_t\right| $ can be computed efficiently if the values of $A_j$ are known with a dynamic program that uses formula (2). This is demonstrated in [21, Algorithm 1] for specifically the sum-rank metric, but the used algorithm can easily be adjusted for other coordinate-additive metrics. Similar to (2), we can calculate the size $\left| {\mathcal {S}^{\ell }_{t}}\right| $ by summing over all weight decompositions of the weight t and adding the number of tuples with that weight decomposition. From an information-theoretic point of view we use the notion of a type of a tuple $x \in \mathcal {A}^{\ell }$. For any positive integers $\ell $ and t, the type of $x \in \mathcal {A}^{\ell }$ is a tuple $\theta (x) = (\theta _0(x), \ldots , \theta _{\mu }(x))$ where each $\theta _i(x)$ is the relative fraction of occurrences of a weight $i \in W_{\mathcal {A}}$ in x, i.e.,

$$\begin{aligned} \theta _i(x) = \frac{1}{\ell }\left| {\left\{ {k \in \left\{ {1, \ldots , \ell }\right\} \, : \,{{\,\textrm{wt}\,}}_{\mathcal {A}}(x_k) = i}\right\} }\right| . \end{aligned}$$

Notice that the weight decomposition of $x \in \mathcal {A}^{\ell }$ is immediately derived from its type $\theta (x)$ by $\ell \theta (x) = (\ell \theta _0(x), \ldots , \ell \theta _{\mu }(x))$ and indeed ${{\,\textrm{wt}\,}}_{\mathcal {A}}(x) = \ell \sum _{i = 0}^{\mu } \theta _i(x)$. Furthermore, if ${{\,\textrm{wt}\,}}(x) = t$ then $ \left\{ {0}\right\} ^{\ell \theta _0} \times \ldots \times \left\{ {\mu }\right\} ^{\ell \theta _{\mu }} \in \mathcal {T}^{\ell }_t$. Hence, to calculate $\left| {\mathcal {S}_t^{\ell }}\right| $, instead of summing over all partitions in $\mathcal {T}_t^{\ell }$ we can sum over all types in $\mathcal {A}^{\ell }$ yielding weight t. We will denote this set by $\Theta _t^{\ell }$. The number of tuples $x \in \mathcal {A}^{\ell }$ of type $\theta $ is given by the multinomial coefficient

$$\begin{aligned} \left( {\begin{array}{c}\ell \\ \ell \theta \end{array}}\right) = \frac{\ell !}{(\ell \theta _0)! \cdot \ldots \cdot (\ell \theta _{\mu })!}. \end{aligned}$$

Hence, the size of the $\ell $-dimensional sphere of radius t can be expressed as

$$\begin{aligned} \left| {\mathcal {S}_{t}^{\ell }}\right| = \sum _{\ell \theta \in \Theta ^{\ell }_{t}} \left( {\begin{array}{c}\ell \\ \ell \theta \end{array}}\right) {.} \end{aligned}$$

This value, however, is hard to manipulate wherefore we might use the following upper and lower bounds (see [4, Theorem 11.1.3])

$$\begin{aligned} \frac{1}{(\ell + 1)^{{\left| {\mathcal {A}}\right| - 1}}} 2^{\ell H(\theta )} \le \left( {\begin{array}{c}\ell \\ \ell \theta \end{array}}\right) \le 2^{\ell H(\theta )}, \end{aligned}$$

(3)

where $H(\theta ):= -\sum _{i: \theta _i \ne 0} \theta _i \log _2(\theta _i)$ is the entropy of $\theta $. With this we immediately obtain upper and lower bounds on $\left| {\mathcal {S}_{t}^{\ell }}\right| $. Regarding the upper bound, further improvements can be achieved which we will discuss in Sect. 3.

2.3 Ordinary generating functions

The theory of ordinary generating functions (OGFs) is an important branch of mathematics that lays connections between combinatorics, analysis, number theory, probability theory and other fields. In this paper we restrict ourselves to OGFs corresponding to weights in coordinate-additive metrics, which are polynomials with non-negative coefficients. Consider a finite abelian group $\mathcal {A}$ with weight function ${{\,\textrm{wt}\,}}_{\mathcal {A}}$ and induced coordinate-additive weight function ${{\,\textrm{wt}\,}}_{\Sigma \mathcal {A}}$ on $\mathcal {A}^{\ell }$. The OGF corresponding to ${{\,\textrm{wt}\,}}_{\Sigma \mathcal {A}}$ is defined as the polynomial

$$\begin{aligned} \textstyle F_{\mathcal {A}^{\ell }}(z):= \sum _{v \in \mathcal {A}^{\ell }} z^{{{\,\textrm{wt}\,}}_{\Sigma \mathcal {A}}(v)} = \sum _{i=0}^{\mu \ell } |\mathcal {S}_i^{\ell }| \ z^i. \end{aligned}$$

For a polynomial $F(z) = F_0 + F_1 z + \ldots + F_d z^d$ we use the notation $[z^i]F(z)$ to refer to the i-th coefficient $F_i$ of F(z), with $[z^i]F(z) = 0$ for $i > \deg (F)$. The OGF for the sum-rank metric on $\mathbb {F}_q^{m \times \eta \ell }$ is denoted by

$$\begin{aligned} \mathcal {S}^{m,\eta ,\ell ,q}(z) = \sum _{i=0}^{\mu \ell } \left| {\mathcal {S}_i^{m,\eta ,\ell ,q}}\right| \, z^i. \end{aligned}$$

Definition 1

(Partial order on polynomials) Let $F(z), G(z) \in \mathbb {R}[z]$ be two real polynomials. If $[z^i]F(z) \le [z^i]G(z)$ for all $i \in \mathbb {N}$, we say F(z) is coefficient-wise less-than-or-equal to G(z), denoted as $F(z) \preccurlyeq _c G(z).$

Proposition 1

([5, Theorem I.1]) Let $\mathcal {A}_1$, $\mathcal {A}_2$ be two finite alphabets with weight functions ${{\,\textrm{wt}\,}}_{\mathcal {A}_1},{{\,\textrm{wt}\,}}_{\mathcal {A}_2}$ respectively. Then ${{\,\textrm{wt}\,}}_{\mathcal {A}_1\times \mathcal {A}_2}(a,b):= {{\,\textrm{wt}\,}}_{\mathcal {A}_1}(a)+{{\,\textrm{wt}\,}}_{\mathcal {A}_2}(b)$ is a weight function on $\mathcal {A}_1 \times \mathcal {A}_2$ and

$$\begin{aligned} F_{\mathcal {A}_1 \times \mathcal {A}_2}(z) = F_{\mathcal {A}_1}(z) F_{\mathcal {A}_2}(z). \end{aligned}$$

In particular, we have

$$\begin{aligned} F_{\mathcal {A}^{\ell }}(z) = F_{\mathcal {A}}(z)^{\ell }, \end{aligned}$$

for $\ell \in \mathbb {N}$. Furthermore, the product of real polynomials with non-negative coefficients preserves the partial order: If $F(z) \preccurlyeq _c G(z)$ and $K(z) \preccurlyeq _c L(z)$, then $F(z)K(z) \preccurlyeq _c G(z)L(z)$.

Lemma 2

Let F(z) be a real polynomial of degree $d > 0$ with non-negative coefficients $F_i \ge 0$ and first derivative $F'(z)$. If F(z) is not a monomial, then the function $G(z) = z F'(z)/F(z)$ is a strictly increasing smooth function on the positive reals $\mathbb {R}_{> 0}$. In particular if $F(0) > 0$, which is the case with OGFs of finite alphabets with weight functions, G(z) is a bijection from $[0,\infty )$ to [0, d).

Proof

Smoothness follows directly from smoothness of F(z) and 1/z on $\mathbb {R}_{>0}$. To show that G(z) is strictly increasing, consider two positive integers $0< a < b$ and let $K(a,b):= bF'(b)F(a) - aF'(a)F(b)$. Then,

$$\begin{aligned} K(a,b)&= \sum _{i=0}^{d} i F_i b^i \sum _{j=0}^{d} F_j a^j - \sum _{i=0}^{d} i F_i a^i \sum _{j=0}^{d} F_j b^j\\&= \sum _{0 \le i< j \le d} i F_i F_j b^i a^j + j F_j F_i b^j a^i\ - i F_i F_j a^i b^j - j F_j F_i a^j b^i\\&= \sum _{0 \le i < j \le d} F_i F_j (j-i)( b^j a^i - a^j b^i) > 0 \end{aligned}$$

where the last inequality follows from assuming that F(z) is not a monomial, so there exist $i < j$ such that $F_i F_j > 0$. The proof now follows since $G(b) - G(a) = \frac{K(a,b)}{F(a)F(b)} > 0.$ Lastly, we have that $\lim _{z \rightarrow \infty } F'(z)/z^{d-1} = d F_d$ and $\lim _{z \rightarrow \infty } F(z)/z^{d} = F_d$, hence we get $\lim _{z \rightarrow \infty } G(z) = d$. $\square $

3 Information-theoretic bounds on spheres

In [15] an asymptotically tight upper bound on the volume of an $\ell $-dimensional ball $\left| {\mathcal {B}_{t}^{\ell }}\right| $ of radius t was introduced. The author used information theoretic tools, as described in Sect. 2.2, and bounded the size of the sphere via the type maximizing the entropy, and showed that this bound is asymptotically tight. Furthermore, this bound is valid for any arbitrary additive weight function ${{\,\textrm{wt}\,}}_{\mathcal {A}}$ (see Sect. 2.1 for the definition) with respect to some finite abelian group $\mathcal {A}$. The bound was proved to hold for normalized weights $\rho $ with $\rho := t/\ell $ up to the average weight

$$\begin{aligned} \overline{w}:= |\mathcal {A}|^{-1} \sum _{a \in \mathcal {A}} {{\,\textrm{wt}\,}}_{\mathcal {A}}(a) \end{aligned}$$

at which the volume of the ball is saturated. We extend the result from [15] to the size of spheres and also prove that the bound holds for $\rho \ge \overline{w}$ up to the maximum possible weight, i.e., for $0< \rho < \mu = \max _{a\in \mathcal {A}}\left\{ { {{\,\textrm{wt}\,}}_{\mathcal {A}}(a)}\right\} $.

Given a random variable X over a finite alphabet $\mathcal {A}$ with probability distribution P, we define $P(a):= \operatorname {Prob}(X=a)$ with $a \in \mathcal {A}$. The entropy H(P) of P with respect to the base q is defined as

$$\begin{aligned} H(P) := -\sum _{a \in \mathcal {A}, P(a) \ne 0} P(a)\log _{q} P(a). \end{aligned}$$

Example 1

Consider an alphabet $\mathcal {A}= \mathbb {F}_q$, a probability $\rho \in (0,1)$, and a probability distribution

$$\begin{aligned} P(x) = {\left\{ \begin{array}{ll} 1 - \rho & x = 0\\ \rho /(q-1) & x \ne 0 \end{array}\right. }. \end{aligned}$$

Then the entropy H(X) reduces to the q-ary entropy function defined as

$$\begin{aligned} h_{q}(\rho ):= - \rho \log _{q} (\rho /(q-1)) - (1-\rho )\log _{q} (1-\rho ). \end{aligned}$$

Definition 2

For any $a \in \mathcal {A}$ and $0< \rho < \mu $, we define the probability distribution

$$\begin{aligned} P_{\beta }(a) := \frac{q^{-\beta {{\,\textrm{wt}\,}}_{\mathcal {A}}(a)}}{\mathcal {Z}(\beta )} \end{aligned}$$

(4)

where $\beta $ is the unique solution to the weight constraint

$$\begin{aligned} {\mathbb {E}}[{{\,\textrm{wt}\,}}_{\mathcal {A}}(a) ] = \sum _{a \in \mathcal {A}} P_{\beta }(a){{\,\textrm{wt}\,}}_{\mathcal {A}}(a) = \rho \end{aligned}$$

(5)

and $\mathcal {Z}(\beta )$ is chosen s.t. $\sum _{a \in \mathcal {A}} P_{\beta }(a)=1$, i.e. $\mathcal {Z}(\beta ) = \sum _{a \in \mathcal {A}} q^{-\beta {{\,\textrm{wt}\,}}_{\mathcal {A}}(a)}.$

Later, in Proposition 7, we show that for any $0< \rho < \mu $, a solution $\beta $ to the equation $\sum _{a \in \mathcal {A}} P_{\beta }(a){{\,\textrm{wt}\,}}_{\mathcal {A}}(a) = \rho $ always exists and is unique. This establishes a one-to-one correspondence between $\rho $ and $\beta $, i.e. every $\beta \in {\mathbb {R}}$ determines a $\rho \in (0,\mu )$ via the function

$$\begin{aligned} \rho (\beta ):= \sum _{a \in \mathcal {A}} P_{\beta }(a){{\,\textrm{wt}\,}}_{\mathcal {A}}(a) \end{aligned}$$

(6)

and vice versa. Hence we will use $\rho $ and $\rho (\beta )$ interchangeably. Let us denote by

$$\begin{aligned} H_{\rho }:= H(P_{\beta }) \end{aligned}$$

the entropy of the distribution in (4). Then, the following bound was proven in [15].

Theorem 3

[15] For any $0 < \rho \le \overline{w}$ and $\ell \in {\mathbb {N}}$ we have

$$\begin{aligned} \frac{1}{\ell } \log _q \left| {\mathcal {B}_{\rho \ell }^{\ell }}\right| \le H_{\rho }. \end{aligned}$$

The following is an immediate consequence of Theorem 3 above.

Corollary 4

For any $0< \rho < \overline{w}$ and $\ell \in {\mathbb {N}}$ we have

$$\begin{aligned} \frac{1}{\ell } \log _q \left| {\mathcal {S}_{\rho \ell }^{\ell }}\right| \le H_{\rho }. \end{aligned}$$

By a simple cutting argument, the bound in Theorem 3 can be extended to any normalized weight $0 \le \rho \le \max _{x\in \mathcal {A}}\left\{ { {{\,\textrm{wt}\,}}_{\mathcal {A}}(x)}\right\} =: \mu $ as follows.

Theorem 5

For any $0 < \rho \le \mu $ we have

$$\begin{aligned} \frac{1}{\ell } \log _q \left| {\mathcal {B}_{\rho \ell }^{\ell }}\right| \le {\left\{ \begin{array}{ll} H_{\rho } & \text {if } 0< \rho \le \overline{w}\\ \log _q(\left| {\mathcal {A}}\right| ) & \text {if } \overline{w} < \rho \le \mu \end{array}\right. }. \end{aligned}$$

3.1 Upper bound

In this subsection, we show that Corollary 4 also holds for normalized weights $0< \rho < \mu $. Recall the OGFs for the alphabets $\mathcal {A}$ and $\mathcal {A}^{\ell }$, respectively,

$$\begin{aligned} F_\mathcal {A}(z) = \sum _{a \in \mathcal {A}} z^{{{\,\textrm{wt}\,}}_{\mathcal {A}}(a)}\quad \text {and } \quad F_{\mathcal {A}^\ell } (z) = \sum _{v \in \mathcal {A}^\ell } z^{{{\,\textrm{wt}\,}}_{\Sigma \mathcal {A}}(v)} = F_\mathcal {A}(z)^\ell . \end{aligned}$$

We now can express $\mathcal {Z}(\beta )$, $\rho (\beta )$ and $H_{\rho }$ in terms of $F_\mathcal {A}(z)$.

Lemma 6

Let $\beta \in \mathbb {R}$ and $\rho = \rho (\beta )$. Then

$$\begin{aligned} \mathcal {Z}(\beta ) = F_\mathcal {A}\left( q^{-\beta }\right) , \quad \rho (\beta ) = q^{-\beta } \frac{F'_\mathcal {A}\left( q^{-\beta }\right) }{F_\mathcal {A}\left( q^{-\beta }\right) }, \quad H_{\rho } = \log _q\left( \frac{F_\mathcal {A}(q^{-\beta })}{q^{-\beta \rho (\beta )}}\right) . \end{aligned}$$

(7)

Proof

The first equality immediately follows from the fact that $\mathcal {Z}(\beta )$ is the normalization constant of the distribution $P_\beta (\cdot )$: $\mathcal {Z}(\beta ) = \sum _{a \in \mathcal {A}} \left( q^{-\beta }\right) ^{{{\,\textrm{wt}\,}}_{\mathcal {A}}(a)} = F_{\mathcal {A}}(q^{-\beta })$.

For the second equality, we rewrite the weight constraint (5) defining $\rho (\beta )$ to obtain

$$\begin{aligned} \rho (\beta )&= \sum _{a \in \mathcal {A}} P_{\beta }(a) {{\,\textrm{wt}\,}}_{\mathcal {A}}(a)= \sum _{a \in \mathcal {A}} \frac{q^{-\beta {{\,\textrm{wt}\,}}_{\mathcal {A}}(a)}}{\mathcal {Z}(\beta )} {{\,\textrm{wt}\,}}_{\mathcal {A}}(a)\\&= \sum _{a \in \mathcal {A}} \frac{q^{-\beta ({{\,\textrm{wt}\,}}_{\mathcal {A}}(a) - 1)} q^{-\beta } {{\,\textrm{wt}\,}}_{\mathcal {A}}(a)}{F_{\mathcal {A}}(q^{-\beta })} \end{aligned}$$

Noticing that $F'_\mathcal {A}\left( q^{-\beta }\right) = \sum _{a \in \mathcal {A}} q^{-\beta ({{\,\textrm{wt}\,}}_{\mathcal {A}}(a) - 1)}{{\,\textrm{wt}\,}}_{\mathcal {A}}(a)$ yields the result.

To show the last equality we use Eqs. (4), (6) and the previous equalities for $\mathcal {Z}(\beta )$. Rewriting the definition of the entropy $H_{\rho }$ gives

$$\begin{aligned} H_{\rho }&= -\sum _{a \in \mathcal {A}} P_{\beta }(a) \log _q \left( P_{\beta }(a) \right) = -\sum _{a \in \mathcal {A}} P_{\beta }(a) \log _q \left( \frac{q^{-\beta {{\,\textrm{wt}\,}}_{\mathcal {A}}(a)}}{F_{\mathcal {A}}(q^{-\beta })} \right) \\&= \sum _{a \in \mathcal {A}} P_{\beta }(a)\left( \beta {{\,\textrm{wt}\,}}_{\mathcal {A}}(a) + \log _q\left( F_{\mathcal {A}}(q^{-\beta }) \right) \right) \\&= \beta \sum _{a \in \mathcal {A}} P_{\beta }(a) {{\,\textrm{wt}\,}}_{\mathcal {A}}(a) \ + \ \log _q\left( F_{\mathcal {A}}(q^{-\beta }) \right) \sum _{a \in \mathcal {A}} P_{\beta }(a)\\&= \beta \rho (\beta ) + \log _q\left( F_{\mathcal {A}}(q^{-\beta })\right) \\&= \log _q\left( \frac{F_\mathcal {A}(q^{-\beta })}{q^{-\beta \rho (\beta )}} \right) . \end{aligned}$$

$\square $

Proposition 7

Let $\mathcal {A}$ be an alphabet with weight function ${{\,\textrm{wt}\,}}_{\mathcal {A}}$. Then the function $\rho (\beta )$ given in (6) is a strictly decreasing smooth bijection from ${\mathbb {R}}$ to $(0,\mu )$.

Proof

By Lemma 2, the function $G(z):= z \frac{F'_\mathcal {A}\left( z\right) }{F_\mathcal {A}\left( z\right) }$ is a strictly increasing bijection from $[0,\infty )$ to $[0,\mu )$. The proof now follows since $\rho (\beta ) = G(q^{-\beta })$. $\square $

We will now use the technique of bounding the coefficients of an OGF by evaluating it at points y. For any real valued $y > 0$ we have

$$\begin{aligned} |\mathcal {S}_t^\ell | y^t&= \left( [z^t]F_{\mathcal {A}^\ell }(z)\right) y^t \le F_{\mathcal {A}^\ell }(y) = F_\mathcal {A}(y)^\ell . \end{aligned}$$

We can further rewrite this expression and take the infimum on the right-hand side and obtain

$$\begin{aligned} \frac{1}{\ell } \log _q |\mathcal {S}_t^\ell |&\le \inf _{y > 0}\ \log _q\left( \frac{F_\mathcal {A}(y)}{y^\rho }\right) . \end{aligned}$$

(8)

Moreover, we can show that a global minimum of $F_\mathcal {A}(y)/y^\rho $ exists and therefore the infimum is a minimum: by setting the derivative of $F_\mathcal {A}(y)/y^\rho $ to zero and using (7) for $\rho $, we obtain a local minimum for $y = q^{-\beta }$. Then, using Lemma 2, we can show that the derivative of $F_\mathcal {A}(y)/y^\rho $ is negative for $0< y < q^{-\beta }$ and positive for $y > q^{-\beta }$. Therefore, the local minimum is also the global minimum, where the function $\log _q\left( \frac{F_\mathcal {A}(y)}{y^\rho }\right) $ takes the value $H_\rho $ (cf. (7)).

This technique is similar to the more general saddle-point bound explained in [5, Sect. VIII.2]. To summarize, the saddle-point-like bound (8) coincides with the entropy bound (see also [8, Theorem 4.1], [3, Theorem IV.9]), but extends the range of $\rho $ to $(0,\mu )$, as stated in Theorem 8. Finally, we have

$$\begin{aligned} \frac{1}{\ell } \log _q |\mathcal {S}_t^\ell |&\le \log _q\left( \frac{F_\mathcal {A}(q^{-\beta })}{(q^{-\beta })^\rho }\right) . \end{aligned}$$

Theorem 8

For any $0< \rho < \mu $ and $\ell \in {\mathbb {N}}$ we have

$$\begin{aligned} \frac{1}{\ell } \log _q |\mathcal {S}_{\rho \ell }^\ell | \, \le \, H_{\rho } \, = \, \inf _{y > 0}\ \log _q\left( \frac{F_\mathcal {A}(y)}{y^\rho }\right) , \end{aligned}$$

where the infimum (in this case a minimum) on the right-hand side is attained at $y = q^{-\beta }$, with $\beta $ defined by $\rho (\beta ) = \rho $.

3.2 Lower bounds

Observe that (3) gives us the lower bound

$$\begin{aligned} \frac{1}{\ell } \log _q |\mathcal {S}_{\rho \ell }^\ell | \ge H_\rho - (\left| {\mathcal {A}}\right| -1)\frac{1}{\ell }\log _q(\ell +1). \end{aligned}$$

(9)

Although this bound is asymptotically tight as $\ell \rightarrow \infty $, it can be improved for some ranges of $\ell $ when the alphabet size $\left| {\mathcal {A}}\right| $ is large (e.g. for the sum-rank metric where $\left| {\mathcal {A}}\right| = q^{mn}$). In this section we derive a different lower bound that does not depend on $\left| {\mathcal {A}}\right| $ but instead on ${{\,\textrm{wt}\,}}_{\mathcal {A}}$. Specifically for the sum-rank metric this new bound is tighter than (9) for a large range of $\ell $.

Let $X_{\beta }, X_{\beta ,1}, X_{\beta ,2},X_{\beta ,3},\ldots $ be independent and identically distributed random variables taking values in $\mathcal {A}$ with probability distribution $P_{\beta }$ given in (4). For $a \in \mathcal {A}$, define the function

$$\begin{aligned} \varphi _\beta (a) := -\log _q\left( P_{\beta }(a)\right) \ = \beta {{\,\textrm{wt}\,}}_{\mathcal {A}}(a) + \log _q\left( F_{\mathcal {A}}(q^{-\beta }) \right) . \end{aligned}$$

(10)

Note that $H_{\rho } = {\mathbb {E}}[\varphi _\beta (X_{\beta ,i})]$ with $\rho = \rho (\beta )$ for each $i \in \mathbb {N}$. As a consequence of Chebyshev’s inequality [23], for any $\gamma > 0$ it holds

$$\begin{aligned} \operatorname {Prob}\left( \left| \frac{1}{\ell }\sum _{i=1}^\ell \varphi _\beta (X_{\beta ,i}) - H_{\rho } \right| \ge \gamma \right) \le \frac{{{\,\textrm{Var}\,}}(\varphi _\beta (X_{\beta }))}{\ell \gamma ^2} = \frac{\beta ^2 {{\,\textrm{Var}\,}}({{\,\textrm{wt}\,}}_{\mathcal {A}}(X_{\beta }))}{\ell \gamma ^2}. \end{aligned}$$

(11)

By choosing $\gamma $ appropriately and by following similar techniques as used in [15], a lower bound for a sum of sphere sizes is derived in Theorem 9.

Theorem 9

Given $t = \rho \ell $ and $0< \varepsilon < 1$, let $\beta $ be defined by the weight constraint (5). Furthermore, let $\delta = \left( \frac{\ell {{\,\textrm{Var}\,}}( {{\,\textrm{wt}\,}}_{\mathcal {A}}(X_{\beta }))}{(1-\varepsilon )}\right) ^{1/2}$. Then

$$\begin{aligned} \sum _{\begin{array}{c} -\delta< j < \delta \\ j \in \mathbb {Z} \end{array}} |\mathcal {S}_{t + j}^\ell | \ > \ \varepsilon \ q^{\ell H_\rho - |\beta | \delta }. \end{aligned}$$

Proof

First, let us define a probability distribution on $\mathcal {A}^\ell $ naturally by $P_\beta (v):= \prod _{i=1}^\ell P_\beta (v_i)$ for $v = (v_1,\ldots ,v_\ell ) \in \mathcal {A}^\ell $. Let $Y_\beta $ denote a random variable taking values in $\mathcal {A}^\ell $ with this probability distribution. Note that $Y_\beta $ is identically distributed as the tuple $(X_{\beta ,1},\ldots ,X_{\beta ,\ell })$.

Next, for any $v \in \mathcal {A}^\ell $, the expression $\left| {{{\,\textrm{wt}\,}}_{\Sigma \mathcal {A}}(v) - \rho \ell }\right| < \delta $ is equivalent to

$$\begin{aligned} \left| {\frac{1}{\ell }\beta {{\,\textrm{wt}\,}}_{\Sigma \mathcal {A}}(v) - \beta \rho }\right| < \frac{|\beta | \delta }{\ell }. \end{aligned}$$

Note that, using Lemma 6 and (10), we rewrite the left hand side of the inequality as

$$\begin{aligned} \left| {\frac{1}{\ell }\beta {{\,\textrm{wt}\,}}_{\Sigma \mathcal {A}}(v) - \beta \rho }\right| = \left| {\frac{1}{\ell }\sum _{i=1}^{\ell }\varphi _\beta (v_i) - H_\rho }\right| . \end{aligned}$$

Hence, we have

$$\begin{aligned} \operatorname {Prob}\left( \left| {{{\,\textrm{wt}\,}}_{\Sigma \mathcal {A}}(Y_\beta ) - \rho \ell }\right|< \delta \right) = \operatorname {Prob}\left( \left| \frac{1}{\ell }\sum _{i=1}^\ell \varphi _\beta (X_{\beta ,i}) - H_{\rho } \right| < \frac{|\beta | \delta }{\ell } \right) . \end{aligned}$$

Applying Chebyshev’s inequality (see (11)), we obtain a lower bound

$$\begin{aligned} \operatorname {Prob}\left( \left| {{{\,\textrm{wt}\,}}_{\Sigma \mathcal {A}}(Y_\beta ) - \rho \ell }\right| < \delta \right) \ge 1 - \frac{\ell {{\,\textrm{Var}\,}}({{\,\textrm{wt}\,}}_{\mathcal {A}}(X_{\beta }))}{ \delta ^2} = \varepsilon . \end{aligned}$$

Now, let us denote $U:={\bigcup _{\begin{array}{c} -\delta< j < \delta \\ j \in \mathbb {Z} \end{array}} } \mathcal {S}_{\rho \ell +j}^\ell $ and note that we can write

$$\begin{aligned} \operatorname {Prob}\left( \left| {{{\,\textrm{wt}\,}}_{\Sigma \mathcal {A}}(Y_\beta ) - \rho \ell }\right| < \delta \right) = \operatorname {Prob}\left( Y_\beta \in U \right) = \sum _{v \in U} P_\beta (v). \end{aligned}$$

Furthermore, note that the inequality $\left| {\frac{1}{\ell }\sum _{i=1}^{\ell }\varphi _\beta (v_i) - H_\rho }\right| < \frac{|\beta | \delta }{\ell }$ implies that $q^{-\ell H_{\rho } + |\beta |\delta } > P_\beta (v) $. The proof is completed observing that

$$\begin{aligned} \sum _{\begin{array}{c} -\delta< j < \delta \\ j \in \mathbb {Z} \end{array}} \left| {\mathcal {S}_{\rho \ell +j}^\ell }\right| q^{-\ell H_{\rho } + |\beta |\delta } = \ \left| {U}\right| q^{-\ell H_{\rho } + |\beta |\delta } > \sum _{v \in U} P_\beta (v) \ge \varepsilon . \hspace{17mm} \end{aligned}$$

$\square $

Using the inequality $ {\displaystyle { \max _{\begin{array}{c} -\delta< j< \delta \\ j \in \mathbb {Z} \end{array}} }}|\mathcal {S}_{t + j}^\ell | \ \ge \ \frac{1}{2\lceil \delta \rceil - 1}{\displaystyle { \sum _{\begin{array}{c} -\delta< j < \delta \\ j \in \mathbb {Z} \end{array}} }} |\mathcal {S}_{t + j}^\ell | $ we get an alternative bound in Theorem 10.

Theorem 10

Given $t = \ell \rho $ and $0< \varepsilon < 1$, let $\beta $ be defined by the weight constraint (5) and $\delta = \left( \frac{\ell {{\,\textrm{Var}\,}}( {{\,\textrm{wt}\,}}_{\mathcal {A}}(X_{\beta }))}{(1-\varepsilon )}\right) ^{1/2}$. Then

$$\begin{aligned} \max _{\begin{array}{c} -\delta< j < \delta \\ j \in \mathbb {Z} \end{array}} \ \frac{1}{\ell } \log _q |\mathcal {S}_{t + j}^\ell | \ > \ H_{\rho } - \frac{|\beta | \delta }{\ell } - \frac{1}{\ell } \log _q \left( \frac{2\lceil \delta \rceil - 1}{\varepsilon }\right) . \end{aligned}$$

Empirically, good bounds seem to be obtained for $\varepsilon $ close to 0 (this corresponds to a relatively small $\delta $ close to $\ell ^{1/2} {{\,\textrm{Var}\,}}({{\,\textrm{wt}\,}}_{\mathcal {A}}(X_{\beta }))^{1/2}$). There exists a number $ 0< \varepsilon _0 < 1$ such that setting $\varepsilon = \varepsilon _0$ implies $\delta = \lfloor \ell ^{1/2} {{\,\textrm{Var}\,}}({{\,\textrm{wt}\,}}_{\mathcal {A}}(X_{\beta }))^{1/2} \rfloor + 1$; we suspect that the best bounds are obtained for $\varepsilon $ close to this $\varepsilon _0$.

Moreover, for constant $\varepsilon $ and $\rho $, this bound coincides asymptotically with the bound from Theorem 8 as $\ell \rightarrow \infty $ and is therefore asymptotically tight.

4 Bounds on spheres in the sum-rank metric

In this section we derive improved closed-form upper and lower bounds on the size of a sphere in the sum-rank metric. Hence we fix m, $\eta $ and q and we use $\operatorname {NM}_q(m,\eta , t)$ to denote the number of matrices of rank t over $\mathbb {F}_q^{m \times \eta }$. Following (2), an exact formula for the size of the $\ell $-dimensional sphere of radius t in the sum-rank metric is given by

$$\begin{aligned} \left| {\mathcal {S}^{m,\eta ,\ell ,q}_t}\right| = \sum _{\begin{array}{c} (t_1,\ldots , t_\ell ) \in \mathcal {T}_t^\ell \end{array}} \, \prod _{i=1}^\ell \operatorname {NM}_q(m,\eta , t_{i}), \end{aligned}$$

(12)

with $\mathcal {T}^{\ell }_{t}$ the set of all (ordered) integer partitions of t of length $\ell $ with part sizes not exceeding $\mu = \mu _{\Sigma R} = \min \{m,\eta \}$, i.e.,

$$\begin{aligned} \mathcal {T}_t^\ell := \left\{ (t_1,t_2,\ldots ,t_\ell ) \in \{0,1,\ldots ,\mu \}^\ell \ : \ t_1 + t_2 + \ldots + t_\ell = t \right\} . \end{aligned}$$

A current method of obtaining both closed-form upper and lower bounds on $\left| {\mathcal {S}^{m,\eta ,\ell ,q}_t}\right| $ uses the following steps:

Derive a closed-form upper bound $b^{\text {up}}_q(m,\eta , t)$ and lower bound $b^{\text {low}}_q(m,\eta , t)$ on $\operatorname {NM}_q(m,\eta , t)$;

Find a partition $t^{\text {up}} = (t_1^{\text {up}},\ldots ,t_\ell ^{\text {up}}) \in \mathcal {T}_t^\ell $ that maximizes $\prod _{i=1}^\ell b^{\text {up}}_q(m,\eta , t_{i}^{\text {up}})$ and a partition $t^{\text {low}} = (t_1^{\text {low}},\ldots ,t_\ell ^{\text {low}}) \in \mathcal {T}_t^\ell $ that maximizes $\prod _{i=1}^\ell b^{\text {low}}_q(m,\eta , t_{i}^{\text {low}})$, for example with the use of Lagrange multipliers;

Derive a closed-form upper bound $N_t^\ell $ on $\left| {\mathcal {T}_t^{\ell }}\right| $.

This strategy yields the following general bounds on the size of a sphere:

$$\begin{aligned} \prod _{i=1}^\ell b^{\text {low}}_q(m,\eta , t_{i}^{\text {low}}) \, \le \, \left| {\mathcal {S}^{m,\eta ,\ell ,q}_t}\right| \,\le \, N_t^\ell \prod _{i=1}^\ell b^{\text {up}}_q(m,\eta , t_{i}^{\text {up}}). \end{aligned}$$

(13)

In [20], and further discussed in [9], the authors used $b^{\text {low}}_q(m,\eta , t) = \gamma _q^{-1} q^{t(m+\eta -t)}$ to obtain the closed-form lower bounds

$$\begin{aligned} \gamma _q^{-\ell } q^{t(m+\eta -\frac{t}{\ell }) - \frac{\ell }{4}} \, \le \, \gamma _q^{-\ell } \left( {\begin{array}{c}\ell \\ r\end{array}}\right) q^{t(m+\eta - \frac{t}{\ell })+\frac{r^2}{\ell }-r} \le \left| {\mathcal {S}^{m,\eta ,\ell ,q}_t}\right| , \end{aligned}$$

(14)

where r satisfies $t \equiv r \mod \ell $ with $0 \le r < \ell $ and $\gamma _q$ is a special instance of the $\varvec{q}$-Pochhammer symbol defined as

$$\begin{aligned} (a;x)_k := \prod _{i=0}^{k-1} (1-a x^i), \quad (a;x)_\infty := \prod _{i=0}^\infty (1-a x^i), \quad \gamma _q := \left( \frac{1}{q};\frac{1}{q}\right) _{\infty }^{-1} = \prod _{i=1}^\infty (1-q^{-i})^{-1}. \end{aligned}$$

Likewise in [21] this strategy is used with $b^{\text {up}}_q(m,\eta , t) = \gamma _q q^{t(m+\eta -t)}$ and $N_t^\ell = \left( {\begin{array}{c}\ell + t - 1\\ \ell -1\end{array}}\right) $ to obtain the closed-form upper bounds

$$\begin{aligned} \left| {\mathcal {S}^{m,\eta ,\ell ,q}_t}\right| { \le \gamma _q^\ell \left( {\begin{array}{c}\ell + t - 1\\ \ell - 1\end{array}}\right) q^{t(m+\eta -\frac{t}{\ell })+\frac{r^2}{\ell }-r}} \le \gamma _q^\ell \left( {\begin{array}{c}\ell + t - 1\\ \ell - 1\end{array}}\right) q^{t(m+\eta -\frac{t}{\ell })}. \end{aligned}$$

(15)

where r satisfies $t \equiv r \mod \ell $ with $0 \le r < \ell $. Note that as $\ell $ increases, the discrepancy between the lower bounds of (14) and upper bounds of (15) also greatly increases. Hence in the regime of large $\ell $ better bounds can be obtained.

First, we reuse the current strategy (13) with a different upper bound $b^{\text {up}}_q(m,\eta , t)$ on $\operatorname {NM}_q(m,\eta , t)$ that works better for large $\ell $ and small t in Sect. 4.1. We also derive an improved lower bound that we will use later in Sect. 4.3.

Secondly, in Sect. 4.2, we investigate a different strategy where, instead of estimating the sum in (12) directly, we exploit the nature of the sum-rank sphere size as an $\ell $-fold discrete convolution, and bound it with continuous convolutions for which closed-form expression exist.

Lastly, in Sect. 4.3, we utilize $\mathcal {S}^{m,\eta , \ell , q}(z) = \left( \mathcal {S}^{m,\eta , 1, q}(z)\right) ^\ell $, where we derive an alternative function that serves as a coefficient-wise lower bound for $\mathcal {S}^{m,\eta , 1, q}(z)$. The $\ell $-th power of this function is calculated more efficiently, since its roots are expressed easily.

4.1 Bounds on the number of matrices of fixed rank

For $a, b \in \mathbb {N}$ we define the $\varvec{q}$-binomial coefficient as

$$\begin{aligned} \begin{bmatrix}a \\ b \end{bmatrix}_{q} = \prod _{i = 1}^{b}\frac{1-q^{a-b+i}}{1-q^{i}} = \prod _{j = 0}^{b-1}\frac{q^a-q^{j}}{q^b-q^{j}}. \end{aligned}$$

Then, by [18], the number of matrices of rank t over $\mathbb {F}_q^{m \times \eta }$ is computed as

$$\begin{aligned} \operatorname {NM}_q(m,\eta , t) = \begin{bmatrix}m\\ t\end{bmatrix}_q \ \prod _{i=0}^{t-1} (q^\eta - q^i). \end{aligned}$$

Let $q \ge 2$, $\mu = \mu _{\Sigma R} = \min \{m,\eta \}$ and $\mathfrak {M}:= \max \{m,\eta \}$. We will lower-bound $\operatorname {NM}_q(m,\eta , t)$ in two steps, eventually leading to Proposition 12 below; first, the q-binomial coefficients satisfy a useful lower bound that follows from elementary arguments (see [12, Lemma 2.2]):

$$\begin{aligned} \begin{bmatrix} \mu \\ i\end{bmatrix}_q&\ge {\left\{ \begin{array}{ll} (1+\frac{1}{q})q^{i(\mu -i)} & \text {if}\, 0< i < \mu \\ 1 & \text {if}\, i \in \{0,\mu \}\\ \end{array}\right. }. \end{aligned}$$

(16)

Lemma 11

Let $0< i < \mu $ and $q \ge 2$. Then

$$\begin{aligned} \begin{bmatrix} \mu \\ i\end{bmatrix}_{1/q^2} \le \left( \frac{1}{q^2};\frac{1}{q^2}\right) _\infty ^{-1} \le 1+\frac{1}{q}. \end{aligned}$$

Proof

By Euler’s pentagonal number theorem [24, Thm 15.5] we can rewrite and bound the q-Pochhammer symbol as follows:

$$\begin{aligned} \left( \frac{1}{q^2};\frac{1}{q^2}\right) _\infty&= 1 + \sum _{n=1}^{\infty } (-1)^n\left[ \left( \frac{1}{q}\right) ^{3n^2-n}+\left( \frac{1}{q}\right) ^{3n^2+n}\right] \\&= 1 - \left( \frac{1}{q}\right) ^{2} - \left( \frac{1}{q}\right) ^{4} + \left( \frac{1}{q}\right) ^{10} + \left( \frac{1}{q}\right) ^{14} - \cdots \\&\ge 1 - \left( \frac{1}{q}\right) ^{2} - \left( \frac{1}{q}\right) ^{4}\\&\quad {\mathop {\ge }\limits ^{\text {(for}\,q \ge 2\text {)}}} 1 - \frac{1}{q^2 - 1} \ge 1 - \frac{1}{q+1} = \frac{q}{q+1} . \end{aligned}$$

So for $0< i < \mu $ we have

$$\begin{aligned} \begin{bmatrix} \mu \\ i\end{bmatrix}_{1/q^2} = \frac{ \left( \frac{1}{q^2};\frac{1}{q^2}\right) _\mu }{\left( \frac{1}{q^2};\frac{1}{q^2}\right) _i \left( \frac{1}{q^2};\frac{1}{q^2}\right) _{\mu -i}} \le \frac{1}{\left( \frac{1}{q^2};\frac{1}{q^2}\right) _i} \le \frac{1}{\left( \frac{1}{q^2};\frac{1}{q^2}\right) _\infty } \le 1+\frac{1}{q}.\hspace{10mm} \end{aligned}$$

$\square $

As direct corollary of (16) and Lemma 11 we obtain for all $0 \le i \le \mu $ the inequality

$$\begin{aligned} \begin{bmatrix}\mu \\ i\end{bmatrix}_{1/q^2} q^{i(\mu - i)} \le \begin{bmatrix}\mu \\ i\end{bmatrix}_{q}. \end{aligned}$$

(17)

For $i\in \{0,\mu \}$ this follows trivially as the q-binomial coefficients equal 1 then.

Secondly, for $a,b,c \in {\mathbb {N}}$ with $0 \le a< b < c$ we have

$$\begin{aligned} \left( \prod _{j=0}^{b-1} (q^c - q^j) \right) ^{a}&= \left( \prod _{j=0}^{a-1} (q^c - q^j) \right) ^{a} \prod _{k=a}^{b-1} (q^c - q^k)^a \\&\le \left( \prod _{j=0}^{a-1} (q^c - q^j) \right) ^{a} \prod _{k=a}^{b-1} (q^c - q^a)^a \\&< \left( \prod _{j=0}^{a-1} (q^c - q^j) \right) ^{a} \prod _{k=a}^{b-1} \left( \prod _{j=0}^{a-1} (q^c - q^j) \right) = \left( \prod _{j=0}^{a-1} (q^c - q^j) \right) ^{b}. \end{aligned}$$

Hence, we observe that

$$\begin{aligned} \prod _{j=0}^{i-1} (q^\mathfrak {M} - q^j) > \left( \prod _{j=0}^{\mu -1} (q^\mathfrak {M} - q^j) \right) ^{i/\mu } = q^{i \, \mathfrak {M}} \left( {\gamma _{q,m,\eta }}^{-1}\right) ^{i/\mu } , \end{aligned}$$

(18)

where we introduce the notation

$$\begin{aligned} {\gamma _{q,m,\eta }}:= \prod _{j=\mathfrak {M}-\mu +1}^{\mathfrak {M}} \left( 1 - q^{-j}\right) ^{-1} \end{aligned}$$

(19)

(with $\mu = \mu _{\Sigma R} = \min \{m,\eta \}$ and $\mathfrak {M}:= \max \{m,\eta \}$). Combining (17) and (18) leads to a new lower bound on the number of matrices of rank i.

Proposition 12

For $m, \eta , i \in \mathbb {N}$ with $0 \le i \le \mu $, we have the lower bound

$$\begin{aligned} \left( {\gamma _{q,m,\eta }}^{-1/\mu }\right) ^i \begin{bmatrix}\mu \\ i\end{bmatrix}_{1/q^2} q^{i(m + \eta - i)}\le \operatorname {NM}_q(m,\eta , i). \end{aligned}$$

Proof

Let $\mathfrak {M} = \max \{m,\eta \}$. Then

$$\begin{aligned} \begin{bmatrix}\mu \\ i\end{bmatrix}_{1/q^2} q^{i(m + \eta - i)} \left( {\gamma _{q,m,\eta }}^{-1/\mu }\right) ^i&= \begin{bmatrix}\mu \\ i\end{bmatrix}_{1/q^2} q^{i(\mu - i)} q^{i\mathfrak {M}} \left( {\gamma _{q,m,\eta }}^{-1/\mu }\right) ^i \\&\le \begin{bmatrix}\mu \\ i\end{bmatrix}_{q} q^{i\mathfrak {M}} \left( {\gamma _{q,m,\eta }}^{-1}\right) ^{i/\mu }\\&< \begin{bmatrix}\mu \\ i\end{bmatrix}_{q} \prod _{j=0}^{i-1} \left( q^\mathfrak {M}-q^{j}\right) = \operatorname {NM}_q(m,\eta , i) \hspace{11mm} \end{aligned}$$

$\square $

Next, we observe that

$$\begin{aligned} \operatorname {NM}_q(m,\eta , t) = \left( \prod _{i=1}^{t}\frac{(1-q^{-m+i-1})(1-q^{-\eta +i-1})}{(1-q^{-i})}\right) q^{t(m+\eta -t)}. \end{aligned}$$

Let us now introduce the function

$$\begin{aligned} \kappa _{q, m, \eta }(t):= \left( \frac{(1-q^{-m})(1-q^{-\eta })}{(1-q^{-1})}\right) ^{t}. \end{aligned}$$

Noticing that $\kappa _{q, m, \eta }(t) \le \prod _{i=1}^{t}\frac{(1-q^{-m+i-1})(1-q^{-\eta +i-1})}{(1-q^{-i})}$, we derive the following upper bound on $\operatorname {NM}_q(m,\eta , t)$.

Proposition 13

For $m, \eta , t \in \mathbb {N}$ we have the upper bound

$$\begin{aligned} \operatorname {NM}_q(m,\eta , t) \ \le \ \kappa _{q, m, \eta }(t) q^{t(m+\eta -t)}. \end{aligned}$$

With the property $\kappa _{q, m, \eta }(t_1)\kappa _{q, m, \eta }(t_2) = \kappa _{q, m, \eta }(t_1+t_2)$, we perform the same steps of the proof of bounds (15) in [21] with $\kappa _{q, m, \eta }(t)$ instead of $\gamma _q$ and obtain Theorem 14 as a new upper bound on sum-rank sphere sizes.

Theorem 14

Given positive integers $m, \eta , \ell , t$ and a prime power q, we have

$$\begin{aligned} \left| {\mathcal {S}^{m,\eta ,\ell ,q}_t}\right| { \le \kappa _{q, m, \eta }(t) \left( {\begin{array}{c}\ell + t - 1\\ \ell - 1\end{array}}\right) q^{t(m+\eta -\frac{t}{\ell })+\frac{r^2}{\ell }-r}} \le \kappa _{q, m, \eta }(t) \left( {\begin{array}{c}\ell + t - 1\\ \ell - 1\end{array}}\right) q^{t(m+\eta -\frac{t}{\ell })} \end{aligned}$$

where r satisfies $t \equiv r \mod \ell $ with $0 \le r < \ell $. Importantly, for sufficiently small t the coefficient $\kappa _{q, m, \eta }(t)$ is smaller than $\gamma _q$. In this case the bounds of Theorem 14 are tighter than [21, Theorem 5] (see (15)).

4.2 Convolution upper bound

Let f(x) and g(x) be two real-valued functions defined on the natural numbers (or on a larger domain). For $t \in \mathbb {N}$, we define the discrete convolution by

$$\begin{aligned} {[}f * g](t) := \sum _{i = 0}^t f(i)g(t-i). \end{aligned}$$

The $\ell $-fold discrete convolution $[f * f * \cdots * f]$ (well-defined by associativity of $*$) is denoted as $f^{*\ell }$. The strategy in this subsection comes from the observation that (12) is equivalent to

$$\begin{aligned} \left| {\mathcal {S}^{m,\eta ,\ell ,q}_t}\right| = \operatorname {NM}_q(m,\eta ,x)^{*\ell }(t). \end{aligned}$$

Let C(t) be a real-valued function depending on the parameters $m,\eta ,q$ and satisfying

$$\begin{aligned} \operatorname {NM}_q(m,\eta ,t) \le C(t) q^{t(m + \eta - t)} \quad \text {and} \quad C(t_1) C(t_2) = C(t_3) C(t_4) \end{aligned}$$

whenever $t_1 + t_2 = t_3 + t_4$. By Proposition 13, examples of such functions are $\gamma _q$ and $\kappa _{q, m, \eta }(t)$. The reason for looking at these functions is because they work well with discrete convolutions, i.e., $\left[ C(x)f(x) * C(x)g(x)\right] (t) = C(0)C(t)[f * g](t).$ Therefore, we can upper bound the sphere sizes as follows

$$\begin{aligned} \left| {\mathcal {S}^{m,\eta ,\ell ,q}_t}\right| \le \left( C(x)q^{x(m + \eta - x)}\right) ^{*\ell }(t) = C(0)^{\ell -1}C(t)\left( q^{x(m + \eta - x)}\right) ^{*\ell }(t). \end{aligned}$$

(20)

Proposition 15 provides a formula to easily bound convolutions.

Proposition 15

Consider $f_\ell (x):= q^{x(m+\eta - x/\ell )}$ for $x \in \mathbb {R}$ and $\ell \in \mathbb {N}$. Functions of this form satisfy the convolution inequality

$$\begin{aligned} {[}f_{\ell _1} * f_{\ell _2}](t) \le \left( 1 + \sqrt{\frac{\ell _1 \ell _2\pi }{(\ell _1 + \ell _2) \ln {q}}}\right) f_{\ell _1 + \ell _2}(t). \end{aligned}$$

Proof

First of all, note that

$$\begin{aligned} {[}f_{\ell _1} * f_{\ell _2}](t)&= \sum _{i=0}^{t} q^{t(m+\eta - \frac{t}{\ell _1+\ell _2}) - \frac{1}{\ell _1}i^2 - \frac{1}{\ell _2}(t-i)^2 + \frac{t^2}{\ell _1+\ell _2} } \\&= f_{\ell _1 + \ell _2}(t) \sum _{i=0}^{t}q^{-\left( \frac{1}{\ell _1} + \frac{1}{\ell _2}\right) \left( i - \frac{\ell _1}{\ell _1 + \ell _2}t\right) ^2} {< f_{\ell _1 + \ell _2}(t)\!\!\! \sum _{i=-\infty }^{\infty } \!\!q^{-\left( \frac{1}{\ell _1} + \frac{1}{\ell _2}\right) \left( i - \frac{\ell _1}{\ell _1 + \ell _2}t\right) ^2}\!\!.} \end{aligned}$$

Next, we will apply the technique of bounding summations with integrals, bounding the discrete convolution with a continuous one. To make the notation more compact, let $g(x):= q^{-\left( \frac{1}{\ell _1} + \frac{1}{\ell _2}\right) \left( x - \frac{\ell _1}{\ell _1 + \ell _2}t\right) ^2}$. Then, using unimodality of g(x) with its mode/peak at $x_{\text {p}}:= \frac{\ell _1}{\ell _1 + \ell _2}t$ where g attains $g(x_{\text {p}}) = 1$, we bound different parts of the summation as follows:

$$\begin{aligned} \sum _{i=-\infty }^{\lfloor x_{\text {p}}\rfloor -1} g(i)&\le \int _{-\infty }^{\lfloor x_{\text {p}}\rfloor } g(x) \ dx,&\quad \sum _{i = \lceil x_{\text {p}}\rceil -1}^\infty g(i) \; \le \; \int _{\lceil x_{\text {p}}\rceil }^\infty g(x) \ dx, \\ \sum _{i=\lfloor x_{\text {p}}\rfloor }^{\lceil x_{\text {p}}\rceil } g(i)&\le 1 + \int _{\lfloor x_{\text {p}}\rfloor }^{\lceil x_{\text {p}}\rceil } g(x) \ dx. \end{aligned}$$

Note that these bounds hold both if $x_{\text {p}} \in \mathbb {N}$ and $x_{\text {p}} \notin \mathbb {N}$. Hence,

$$\begin{aligned} \sum _{i=-\infty }^{\infty }q^{-\left( \frac{1}{\ell _1} + \frac{1}{\ell _2}\right) \left( i - \frac{\ell _1}{\ell _1 + \ell _2}t\right) ^2}&\le 1 + \int _{-\infty }^{\infty }q^{-\left( \frac{1}{\ell _1} + \frac{1}{\ell _2}\right) \left( x - \frac{\ell _1}{\ell _1 + \ell _2}t\right) ^2} dx \\&= 1 + \int _{-\infty }^{\infty }q^{-\left( \frac{1}{\ell _1} + \frac{1}{\ell _2}\right) x^2} dx = 1+\sqrt{\frac{\pi }{\left( \frac{1}{\ell _1} + \frac{1}{\ell _2}\right) \ln {q}}} \end{aligned}$$

and thus the proposition follows.$\square $

A tighter bound could possibly be obtained by examining the summation $\sum _{i=-\infty }^{\infty }q^{-\left( \frac{1}{\ell _1} + \frac{1}{\ell _2}\right) \left( i - \frac{\ell _1}{\ell _1 + \ell _2}t\right) ^2}$ more closely, which is a special case of a (Jacobi) theta function. Studying theta functions lies outside of the scope of this paper, but could be a promising direction for further improvements on Proposition 15.

Setting $\ell _1 = 1$ and applying Proposition 15 inductively for $\ell _2 = 1,\ldots ,\ell -1$, we obtain new upper bounds on the sum-rank sphere sizes using (20) with C(t) of our choice.

Theorem 16

Let $m, \eta , \ell , q, t$ be positive integers. Choosing C(t) equal to $\gamma _q$ or $\kappa _{q, m, \eta }(t)$, we observe the following bounds, respectively

$$\begin{aligned} \left| {\mathcal {S}^{m,\eta ,\ell ,q}_t}\right|&\le \gamma _q^\ell \ \prod _{k=1}^{\ell -1}\left( 1 + \sqrt{\frac{k\pi }{(k+1) \ln {q}}}\right) q^{t(m+\eta - t/\ell )}\\ \left| {\mathcal {S}^{m,\eta ,\ell ,q}_t}\right|&\le \kappa _{q, m, \eta }(t) \prod _{k=1}^{\ell -1}\left( 1 + \sqrt{\frac{k\pi }{(k+1) \ln {q}}}\right) q^{t(m+\eta - t/\ell )} \end{aligned}$$

where the further simplifications

$$\begin{aligned} \prod _{k=1}^{\ell -1}\left( 1 + \sqrt{\frac{k\pi }{(k+1) \ln {q}}}\right) \le \left( 1 + \sqrt{\frac{(\ell -1)\pi }{\ell \ln {q}}} \right) ^{\ell -1} < \left( 1 + \sqrt{\frac{\pi }{ \ln {q}}} \right) ^{\ell -1} \end{aligned}$$

can be made.

4.3 Lower bound via ordinary generating functions

Recall that the OGF of sum-rank sphere sizes is given by

$$\begin{aligned} \mathcal {S}^{m,\eta ,\ell ,q}(z) = \sum _{t=0}^{\mu \ell } \left| {\mathcal {S}_t^{m,\eta ,\ell ,q}}\right| \ z^t = \mathcal {S}^{m,\eta ,1,q}(z)^\ell . \end{aligned}$$

(21)

Note that finding a closed-form bound for $\left| {\mathcal {S}_t^{m,\eta ,\ell ,q}}\right| $ is equal to finding such a bound for the coefficients of the $\ell $-th power on the right-hand side of (21). The approach that we thus take is, to bound the function $\mathcal {S}^{m,\eta ,1,q}(z) = \sum _{i=0}^\mu \operatorname {NM}_q(m,\eta ,i) \, z^i$ coefficient-wise using another polynomial $\mathcal {F}(z)$ whose $\ell $-th power can be computed more easily, as we will see later. We consider the polynomial

$$\begin{aligned} \mathcal {F}(z):=\sum _{i=0}^{\mu } q^{i(m+\eta -i) } \begin{bmatrix}\mu \\ i\end{bmatrix}_{1/q^2} z^i. \end{aligned}$$

This polynomial satisfies the following chain of coefficient-wise inequalities:

$$\begin{aligned} \sum _{i=0}^{\mu } \gamma _q^{-1} q^{i(m+\eta -i)}z^i \ \preccurlyeq _c \ \gamma _q^{-1} \mathcal {F}(z) \ \preccurlyeq _c \ \mathcal {F}({\gamma _{q,m,\eta }}^{-1/\mu } z) \ \preccurlyeq _c \ \mathcal {S}^{m,\eta , 1, q}(z). \end{aligned}$$

The first inequality follows from $ 1 \le \begin{bmatrix}\mu \\ i\end{bmatrix}_{1/q^2}$, the second inequality follows from $\gamma _q^{-1} \le {\gamma _{q,m,\eta }}^{-1} \le {\gamma _{q,m,\eta }}^{-i/\mu } \le 1$ for $0 \le i \le \mu $ and the third from Proposition 12. Since these coefficient-wise inequalities are preserved under $\ell $-th powers, we obtain

$$\begin{aligned} \left( \sum _{i=0}^{\mu } \gamma _q^{-1} q^{i(m+\eta -i)}z^i\right) ^\ell \ \preccurlyeq _c \ \mathcal {F}({\gamma _{q,m,\eta }}^{-1/\mu } z)^\ell \ \preccurlyeq _c \ \mathcal {S}^{m,\eta , \ell , q}(z). \end{aligned}$$

(22)

Note that the left-most polynomial is used in deriving the lower bound [20, Lemma 2] (see (14)). Since the middle polynomial is coefficient-wise greater, estimating its coefficients can potentially lead to improved lower bounds. Let us thus focus on estimating the $\ell $-th power of $\mathcal {F}({\gamma _{q,m,\eta }}^{-1/\mu } z)$.

To our advantage, the polynomial $\mathcal {F}(z)$ (and hence also $\mathcal {F}({\gamma _{q,m,\eta }}^{-1/\mu } z)$) can be factored nicely into linear parts, as the following proposition shows.

Proposition 17

Let $m,\eta \in \mathbb {N}$ and $\mu = \min \{m,\eta \}$. Then

$$\begin{aligned} \mathcal {F}(z) =\sum _{i=0}^{\mu } q^{i(m+\eta -i) } \begin{bmatrix}\mu \\ i\end{bmatrix}_{1/q^2} z^i = \prod _{i=1}^{\mu } (1 + q^{m+\eta -2i + 1} z). \end{aligned}$$

The proof follows directly from the q-binomial theorem, also known as the Cauchy binomial theorem or Gaussian binomial theorem (see [13, Chapter 5]).

Let us now consider

$$\begin{aligned} \mathcal {F}(z)^\ell&= \prod _{i=1}^{\mu } \left( 1 + q^{-2i} \left( q^{m+\eta + 1} z\right) \right) ^\ell \\&= \prod _{i=1}^{\mu } \, \sum _{j = 0}^\ell \left( {\begin{array}{c}\ell \\ j\end{array}}\right) q^{-2ij} \left( q^{m+\eta + 1} z\right) ^j \\&= \sum _{t=0}^{\mu \ell } \left( \sum _{\begin{array}{c} j_1 + \ldots + j_{\mu } = t \\ 0 \le j_i \le \ell \end{array}} \; \prod _{i=1}^{\mu }\left( {\begin{array}{c}\ell \\ j_i\end{array}}\right) q^{-2i j_i} \right) \left( q^{m+\eta + 1} z\right) ^t. \end{aligned}$$

At first, bounding these sums seems as difficult as those in (12). However, unlike (12), the factors $\left( {\begin{array}{c}\ell \\ j_i\end{array}}\right) q^{-2ij_i}$ are also strongly dependent on i (not only on $j_i$) and increase as i decreases. This implies that there is a unique optimal tuple $(j_1,\ldots ,j_\mu )$ that maximizes $\prod _{i=1}^{\mu }\left( {\begin{array}{c}\ell \\ j_i\end{array}}\right) q^{-2ij_i}$, in contrast to (12) where every tuple $(t_1,\ldots , t_\ell )$ contributes the same term $ \prod _{i=1}^\ell \operatorname {NM}_q(m,\eta , t_{i})$ to the sum as any of its permutations.

For each t we will simply bound the sum by only one term $\prod _{i=1}^{\mu }\left( {\begin{array}{c}\ell \\ j_i\end{array}}\right) q^{-2ij_i}$ with the near-optimal choice

$$\begin{aligned} j_i = {\left\{ \begin{array}{ll} \ell & \text {for }\ 1 \le i \le t_* \\ r & \text {for }\ i = t_*+1 \\ 0 & \text {for }\ t_*+2 \le i \le \mu \end{array}\right. } \end{aligned}$$

(23)

where $t = t_* \ell + r$ for some $t_* \in \mathbb {N}$ and $0 \le r < \ell $. This yields the bound

$$\begin{aligned} \mathcal {F}(z)^\ell \succcurlyeq _c \sum _{t=0}^{\mu \ell } \left( \left( {\begin{array}{c}\ell \\ r\end{array}}\right) q^{- 2r(t_* + 1)}\prod _{i=1}^{t_*} q^{-2i\ell }\right) \left( q^{m+\eta + 1} z\right) ^t = \sum _{t=0}^{\mu \ell } \left( {\begin{array}{c}\ell \\ r\end{array}}\right) q^{t(m+\eta - \frac{t}{\ell })+\frac{r^2}{\ell }-r} z^t. \end{aligned}$$

Finally, by substituting ${\gamma _{q,m,\eta }}^{-1/\mu } z$ for z in this inequality and applying (22) we obtain the following result.

Theorem 18

Let $m,\eta \in \mathbb {N}$, $\mu = \min \{m,\eta \}$ and q a prime power. Let $t = t_* \ell + r \le \mu \ell $ with $t_* \in \mathbb {N}$ and $0 \le r < \ell $. Then

$$\begin{aligned} \left( {\gamma _{q,m,\eta }}^{-1}\right) ^{t/\mu } \left( {\begin{array}{c}\ell \\ r\end{array}}\right) q^{t(m+\eta - \frac{t}{\ell })+\frac{r^2}{\ell }-r} \le \left| {\mathcal {S}_t^{m,\eta ,\ell ,q}}\right| , \end{aligned}$$

with $\gamma _{q,m,\eta }$ given in (19).

Notice that remarkably, aside for the improved coefficients in front, we have obtained the same lower bound as [20, Lemma 2] (see (14)) via a completely different method. However, by choosing $j_i$ differently in (23) there is still room for future optimization.

In addition, for $0< i < \mu $ we have

$$\begin{aligned} \frac{\operatorname {NM}_q(m,\eta , i)^2}{\operatorname {NM}_q(m,\eta , i-1)\operatorname {NM}_q(m,\eta , i+1)}&= \frac{(q^m-q^{i-1})}{(q^m-q^i)}\frac{(q^\eta -q^{i-1})}{(q^\eta -q^i)}\frac{q^{i}(q^{i+1}-1)}{q^{i-1}(q^i-1)}\ge q^2 > 1 \end{aligned}$$

and thus $(\operatorname {NM}_q(m,\eta , i))_{i=0}^{\mu }$ is a logarithmically concave sequence (log-concave for short). Moreover, since convolution preserves log-concavity, it holds that for all $\ell $ the sequence $\left( \left| {\mathcal {S}_i^{m,\eta ,\ell ,q}}\right| \right) _{i=0}^{\mu \ell }$ is log-concave. Hence we can take the convex hull of the logarithm of the bound in Theorem 18 to obtain a slight improvement. In this context, the convex hull of a sequence $(a_i)_{i=0}^{\mu \ell }$ is the sequence $(b_i)_{i=0}^{\mu \ell }$ with

$$\begin{aligned} b_i = \max _{x,y > 0}\left\{ a_i, \, \frac{y}{x+y}a_{i-x} + \frac{x}{x+y}a_{i+y}\right\} , \end{aligned}$$

and as a consequence of Carathéodory’s theorem on convex hulls this is the lowest-valued concave sequence that is coefficient-wise greater or equal to $(a_i)_{i=0}^{\mu \ell }$.

Theorem 19

The convex hull of the sequence

$$\begin{aligned} \left( \log _q\left( \left( {\gamma _{q,m,\eta }}^{-1}\right) ^{i/\mu } \left( {\begin{array}{c}\ell \\ r\end{array}}\right) q^{i(m+\eta - \frac{i}{\ell })+\frac{r^2}{\ell }-r}\right) \right) _{i=0}^{\mu \ell } \end{aligned}$$

is a lower bound on $\log _q\left| {\mathcal {S}_t^{m,\eta ,\ell ,q}}\right| $.

5 Comparison of bounds

In this section, we compare the new bounds presented in this paper with the existing bounds related to the sphere size in the sum-rank metric. In Fig. 1 the relationship between the growth rate $\frac{1}{\ell }\log _q \left| { \mathcal {S}_{t}^{m, \eta , \ell , q}}\right| $ of the sphere size and the normalized radius $\rho $ is shown. We observe that the upper bound using Theorem 8 and the lower bound using Theorem 10 are the tightest bounds and very close to the exact values. The computation of these bounds necessitates the evaluation of the entropy $H_\rho $. Computing $H_\rho $ is straightforward for a specified $\beta $, whereas determining $\beta $ for a given $\rho $ cannot in general be achieved in a closed-form manner, as outlined in (5).

For scenarios where prioritizing closed-form expressions dependent on $\rho $ is essential, the derived alternative bounds may better suit the intended use-cases. In Fig. 1, the upper bounds from Theorem 16 using $\kappa _{q, m, \eta }$, Theorem 16 using $\gamma _q$ and Theorem 14 are consolidated into a single piece-wise function by selecting the minimum value among these bounds. The transition points are indicated by circles.

We observe that for the new closed-form upper and lower bounds we improve significantly in comparison to the already existing closed-form bounds given in [21, Theorem 5] and [20, Lemma 2]. Furthermore, the new bounds are potentially useful tools for obtaining improved closed-form Gilbert–Varshamov or sphere-packing bounds, as introduced in [3] and [20].

Fig. 1

Comparison of upper and lower bounds for the sphere $\mathcal {S}_{\rho \ell }^{m, \eta , \ell , q}$ as function of $\rho $ with parameters $q=2$, $m=5$, $\eta =5$, $\ell =100$

Bild vergrößern

In Fig. 2 we show the tightness of the improved bounds for different numbers of blocks. We choose the same values for the parameters q, m, t and n as for the bounds given in [21]. Notably, the bounds proposed in [21] exhibit considerable looseness in scenarios where $\ell $ becomes substantially large (i.e., when the sum-rank metric converges to the Hamming metric). While superior bounds are already established for the Hamming metric (i.e., $\ell =n$), our analysis illustrates substantial enhancements for $\ell < n$ compared to existing bounds.

Fig. 2

Comparison of upper and lower bounds for the sphere $\mathcal {S}_{t}^{m, \eta , \ell , q}$ as function of $\ell $ with parameters $q=2$, $m=40$, $t=10$ and keeping $n= \eta \ell =60$ constant

Bild vergrößern

6 Conclusions

In this paper, we derive novel upper and lower bounds on the size of an $\ell $-dimensional sphere. First, we consider a general setting for any coordinate-additive metric, and then we focus specifically on spheres in the sum-rank metric. In the general setting, we employ techniques from information theory and typical sequences to bound the logarithmic growth rate of the sphere’s size, utilizing the entropy of a Boltzmann-like distribution representing the marginal distribution of a typical sequence. Although these bounds apply to any coordinate-additive metric, we also derive new bounds specifically for the sum-rank metric, using convolution arguments for the upper bounds and ordinary generating functions for the lower bounds. Finally, we compare our bounds to existing ones in the sum-rank metric and observe that, when choosing the most suitable bound for each regime, our bounds outperform the existing closed-form bounds.

Acknowledgements

H. Sauerbier Couvée is supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 801434) and the Bavarian State Ministry of Science and Arts via the project EQAP. T. Jerkovits and J. Bariffi acknowledge the financial support by the Federal Ministry of Education and Research of Germany in the program of “Souverän. Digital. Vernetzt.” Joint project 6 G-RIC, project identification number: 16KISK022. J. Bariffi is funded by the European Union (DiDAX, 101115134). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. The authors thank H. Bartz, A. Baumeister, G. Liva, and A. Wachter-Zeh for their insights and discussions.

Declarations

Conflict of interest

The authors declare no conflict of interest.

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Vorheriger Artikel How to lose some weight: a practical template syndrome decoding attack

Nächster Artikel Nonexistence of generalized bent functions and the quadratic norm form equations

Metadaten
Literatur

Titel: Bounds on sphere sizes in the sum-rank metric and coordinate-additive metrics
Verfasst von: Hugo Sauerbier Couvée
Thomas Jerkovits
Jessica Bariffi
Publikationsdatum: 08.03.2025
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 7/2025
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-025-01604-0

Bariffi J., Bartz H., Liva G., Rosenthal J.: Error-correction performance of regular ring-linear LDPC codes over lee channels. IEEE Trans. Inf. Theory 70(11), 7820–7839 (2024).MathSciNetCrossRef

Bhattacharya S., Banerjee A.: A method to find the volume of a sphere in the lee metric, and its applications. In: 2019 IEEE International Symposium on Information Theory (ISIT), pp. 872–876. IEEE (2019).

Byrne E., Gluesing-Luerssen H., Ravagnani A.: Fundamental properties of sum-rank-metric codes. IEEE Trans. Inf. Theory 67(10), 6456–6475 (2021). https://doi.org/10.1109/TIT.2021.3074190.MathSciNetCrossRef

Cover T.M., Thomas J.A.: Elements of Information Theory, 2nd edn Wiley, New York (2006).

Flajolet P., Sedgewick R.: Analytic Combinatorics. Cambridge University Press, New York (2009).CrossRef

Gardy D., Solé P.: Saddle point techniques in asymptotic coding theory. In: Workshop on Algebraic Coding, pp. 75–81. Springer, Berlin (1991).

Gilbert E.N.: A comparison of signalling alphabets. Bell Syst. Tech. J. 31(3), 504–522 (1952).CrossRef

Greferath M., O’Sullivan M.E.: On bounds for codes over Frobenius rings under homogeneous weights. Discret. Math. 289(1), 11–24 (2004). https://doi.org/10.1016/j.disc.2004.10.002.MathSciNetCrossRef

Gruica A., Horlemann A.-L., Ravagnani A., Willenborg N.: Densities of codes of various linearity degrees in translation-invariant metric spaces. Des. Codes Cryptogr. 92, 609–637 (2023).MathSciNetCrossRef

10.

Hamming R.W.: Error detecting and error correcting codes. Bell Syst. Tech. J. 29(2), 147–160 (1950).MathSciNetCrossRef

11.

Horlemann-Trautmann A.L., Weger V.: Information set decoding in the Lee metric with applications to cryptography. Adv. Math. Commun. (2021). https://doi.org/10.3934/amc.2020089.MathSciNetCrossRef

12.

Ihringer F.: Finite geometry intersecting algebraic combinatorics : an investigation of intersection problems related to Erdös–Ko–Rado theorems on Galois geometries with help from algebraic combinatorics. PhD thesis, Justus-Liebig-Universität Gießen (2015). https://doi.org/10.22029/JLUPUB-9701.

13.

Kac V.G., Cheung P.: Quantum Calculus, vol. 113. Springer, New York (2002).CrossRef

14.

Lee C.: Some properties of nonbinary error-correcting codes. IRE Trans. Inf. Theory 4(2), 77–82 (1958).MathSciNetCrossRef

15.

Loeliger H.-A.: An upper bound on the volume of discrete spheres. IEEE Trans. Inf. Theory 40(6), 2071–2073 (1994).MathSciNetCrossRef

16.

Lu H.F., Kumar P.V.: A unified construction of space-time codes with optimal rate-diversity tradeoff. IEEE Trans. Inf. Theory (2005). https://doi.org/10.1109/TIT.2005.846403.MathSciNetCrossRef

17.

Martínez-Peñas U., Kschischang F.R.: Universal and dynamic locally repairable codes with maximal recoverability via sum-rank codes. IEEE Trans. Inf. Theory 65(12), 7790–7805 (2019). https://doi.org/10.1109/TIT.2019.2924888.MathSciNetCrossRef

18.

Migler T., Morrison K.E., Ogle M.: Weight and rank of matrices over finite fields. arXiv Preprint (2004). arXiv:math/0403314.

19.

Nóbrega R.W., Filho B.F.U.: Multishot codes for network coding using rank-metric codes. In: 2010 Third IEEE International Workshop on Wireless Network Coding, pp. 1–6 (2010).

20.

Ott C., Puchinger S., Bossert M.: Bounds and genericity of sum-rank-metric codes. In: 2021 17th International Symposium Problems of Redundancy in Information and Control Systems, REDUNDANCY 2021 (2021). https://doi.org/10.1109/REDUNDANCY52534.2021.9606442.

21.

Puchinger S., Renner J., Rosenkilde J.: Generic decoding in the sum-rank metric. IEEE Trans. Inf. Theory 68(8), 5075–5097 (2022).MathSciNetCrossRef

22.

Shehadeh M., Kschischang F.R.: Space–time codes from sum-rank codes. IEEE Trans. Inf. Theory 68(3), 1614–1637 (2021).MathSciNetCrossRef

23.

Tchebichef P.: Sur les valeurs limites des intégrales. J. Math. Pures Appl. 19, 157–160 (1874).

24.

Van Lint J.H., Wilson R.M.: A Course in Combinatorics. Cambridge University Press, New York (2001).CrossRef

Erweiterte Suche

Suchoperatoren:

Springer Professional

Bounds on sphere sizes in the sum-rank metric and coordinate-additive metrics

Abstract

Abstract

Publisher's Note

1 Introduction

2 Preliminaries

2.1 Coordinate-additive metrics

2.2 Sizes of spheres

2.3 Ordinary generating functions

3 Information-theoretic bounds on spheres

3.1 Upper bound

3.2 Lower bounds

4 Bounds on spheres in the sum-rank metric

4.1 Bounds on the number of matrices of fixed rank

4.2 Convolution upper bound

4.3 Lower bound via ordinary generating functions

5 Comparison of bounds

6 Conclusions

Acknowledgements

Declarations

Conflict of interest

Publisher's Note

Weitere Artikel der Ausgabe 7/2025

Galois subcovers of the Hermitian curve in characteristic p with respect to subgroups of order dp with prime

The weight hierarchy of decreasing norm-trace codes

An attack on p-adic lattice public-key encryption cryptosystems and signature schemes

Universal partial tori

Admissible parameters for the Crossbred algorithm and semi-regular sequences over finite fields

Correction: The classifications of o-monomials and of 2-to-1 binomials are equivalent

Premium Partner