Cornelia Ott: Bounds on Codes in the Sum-Rank Metric

The sum-rank metric, which generalizes both the Hamming and rank metric, first appeared in 2005 in the context of space-time codes and later in 2010 for multi-shot network coding. It has since become a key tool with significant theoretical and practical relevance.

We investigate three classical bounds on the cardinality of sum-rank metric codes: the Singleton, Gilbert--Varshamov, and sphere-packing bound. Although these bounds and their asymptotic forms for the case of bounded block sizes with a growing number of blocks are known, their evaluation relies on computing the size of sum-rank metric balls, a task that is super-polynomial using existing closed formulas.

To address this, we revisit the Gilbert--Varshamov and sphere-packing bounds for linear codes, connect them to a known polynomial-time algorithm for computing sum-rank sphere sizes, and thereby obtain efficient polynomial-time methods for evaluating these bounds.

Moreover, by incorporating upper and lower estimates on sum-rank metric ball sizes, we derive simplified variants that further reduce computational complexity. These simplified bounds also yield new asymptotic versions of the Gilbert--Varshamov and the sphere-packing bound that apply not only when the number of blocks grows but also when block sizes grow and thereby extending previously established asymptotic results.