CS Paper Radar

Asymptotic Dimension of Persistence Modules of Bounded Presentation

Sushovan Majhi, Atish Mitra, Žiga Virk

cs.CG math.MGmath.AT ·submitted 2026-11-12 15:36 UTC · v2
unusual

Abstract

We compute the asymptotic dimension of spaces of multiparameter persistence modules of bounded presentation under the interleaving distance. The $d$-parameter modules with at most $n$ generators and $m$ relations have asymptotic dimension, and Assouad-Nagata dimension, exactly $d(n+m)$, the number of coordinates of their generator and relation grades, over every field; for two parameters this is $2(n+m)$. The space has continuous moduli, already for two parameters and $n,m\ge2$: over an infinite field it contains, at every scale, infinite uniformly separated families of pairwise non-isomorphic modules with one fibered barcode, so it is not doubling even at a fixed fibered barcode; already for $m\ge1$ it is not coarsely equivalent to a proper metric space. The proof is an induction on the number of distinct grade coordinates: an interleaving small compared with the gaps between these coordinates moves each of them by at most twice its size and preserves the induced grid representation, so the continuous moduli are invisible at large scale. Each class of modules at finite distance therefore embeds coarsely into Hilbert space; for two parameters, $n,m\ge2$ and an uncountable field, a class containing such a family admits no coarse embedding into a separable Hilbert space. Under the two-parameter matching distance, on the space of rank invariants, the asymptotic dimension and the Assouad-Nagata dimension are again $2(n+m)$: slope-one slices pin the grid of grades, and over a grid only finitely many rank invariants occur; on a finite net of $S$ slices the asymptotic dimension is at most $2nS$.

Comment
22 pages. Companion paper: arXiv:2611.12866. v2: new Section 9 proves the position count under the matching distance; revised introduction and discussion

Closest papers

Nearest neighbours by meaning across the whole index.

A General Construction of Codes from Drinfeld Modules

cs.IT math.NTmath.CO ·2026-09-01 ·Alessandro Giannoni, Giacomo Micheli, Mihran Papikian
theory similarity 0.55
Abstract

We construct additive rank-metric and sum-rank-metric codes from Drinfeld modules by restricting bounded-degree morphisms to prime-to-characteristic torsion. For supersingular Drinfeld modules of rank $r$ in characteristic $\mathfrak{p}$ of degree $d$, the stabilization formula for morphism spaces yields rank-metric codes of $\mathbb{F}_q$-dimension $mrt-c$ and minimum distance $r-t+1$, where $c=r(r-1)(d-1)/2$. Simultaneous restriction to $\ell$ distinct degree-$m$ torsion modules gives additive sum-rank codes of the same dimension and minimum distance at least $\ell r-t+1$. Their normalized Singleton defects tend to zero, while in characteristic $(T)$ the module $φ_T=τ^r$ makes the defect vanish and produces an explicit MSRD family. We identify this family with a skew Chinese remainder theorem code supported on central skew polynomials and prove that its poly-skew weight is exactly $m$ times its sum-rank weight. This gives a specialized Singleton-type bound and a polynomial-time unique decoder up to the full sum-rank unique-decoding radius. We also derive a Welch-Berlekamp-type filter equation for the general supersingular sum-rank construction; it becomes an effective decoder whenever bases of the relevant morphism spaces and the restriction maps are computable.

0.31

Projected and Reflected Sliced Wasserstein Kernels for Persistence Diagrams

cs.CG math.AT ·2026-11-04 ·Julián Uribe Castañeda, Mircea Petrache
benchmark similarity 0.54
Abstract · 50 pages, 7 figures, 10 tables

Persistence diagrams do not naturally live in a Hilbert space. Carrière, Cuturi, and Oudot embedded them in kernel methods through the Sliced Wasserstein kernel, built from the Sliced Wasserstein distance $\mathrm{SW}_1$, which is conditionally negative definite (CND). We study the projected ($\mathrm{SW}_p$) and reflected ($\mathrm{RW}_p$) Sliced Wasserstein distances for every order $p\ge1$, and compare them with the $p$-Wasserstein distance $d_p$ and with a reflected variant $d_p^r$, in which projection onto the diagonal is replaced by reflection across it. We show that $2^{1/p}d_p\le d_p^r\le 2d_p$ with sharp constants, so that $d_1^r=2d_1$ and $d_p^r$ inherits the stability of $d_p$, although it is a metric only for $p=1$. The distances $\mathrm{SW}_1$ and $\mathrm{RW}_1$ are CND metrics, and $\mathrm{RW}_1$ gives rise to a new positive definite kernel, stable with respect to $d_1$. For $p>1$, neither $\mathrm{SW}_p$ nor $\mathrm{RW}_p$ satisfies the triangle inequality, and rigorous interval-arithmetic certificates prove that $\mathrm{SW}_2$ and $\mathrm{RW}_2$ are not CND; numerical experiments suggest that the CND property fails for every $p$ above some $p^*\in(1,1.2]$. On diagrams with at most $N$ points, $\mathrm{SW}_p$ and $\mathrm{RW}_p$ are metrically equivalent to $d_p$ and $d_p^r$, with sharp upper constants. On an orbit recognition benchmark, the kernels built from $\mathrm{SW}_1$ and $\mathrm{RW}_1$ reach about 85% accuracy, outperform the persistence scale space kernel, perform on par with the persistence weighted Gaussian kernel, and are about one percentage point below the kernel built from $\mathrm{SW}_2$, which is not positive definite.

0.20

Asymptotic dimension of graphs excluding an induced or fat minor

cs.DM math.CO ·2026-10-15 ·Robert Hickingbotham, Freddie Illingworth, Piotr Micek, Bartosz Walczak
theory similarity 0.53
Abstract

Asymptotic dimension is a large-scale invariant of metric spaces that was introduced by Gromov (1993). A major open problem in coarse graph theory asks whether, for every fixed graph $H$, the class of graphs excluding $H$ as a fat minor has bounded asymptotic dimension. A weaker conjecture asserts the same conclusion for graphs excluding $H$ as an induced minor. We substantially expand the range of graphs $H$ for which these conjectures are known to hold. Specifically, we prove bounded asymptotic dimension for the following classes of graphs: graphs excluding a fixed planar graph as a fat minor; and graphs excluding a fixed string graph as an induced minor. All of our results also hold for the stronger notion of Assouad--Nagata dimension, a refinement of asymptotic dimension. These results have a number of applications, two of which we mention here. First they imply that an induced minor-closed class is $χ$-bounded if and only if it does not contain some Burling graph. Second they imply that, in graph classes excluding a fixed planar graph as an induced minor, treewidth is polynomial in maximum degree.

0.24

Covering radius of rank-metric codes via covering lifts and clubs

cs.IT math.CO ·2026-10-08 ·Giuseppe Marino, Alessandro Neri, Alessia Vallefuoco
theory similarity 0.53
Abstract

We introduce a generator-matrix-based geometric approach to the covering radius of $\mathbb F_{q^m}$-linear rank-metric codes. Starting from the $q$-system associated with the code, we define the notion of covering lift and show that the covering radius can be recovered from the hyperplane weights of such lifts. This yields an exact criterion, in terms of the length and effective length of the code, for the covering radius to attain its largest possible value, together with the upper bound $ρ(\mathcal{C})\le \min\{m,n\}-1$ in all remaining cases. We then specialize our approach to $1$-dimensional codes, for which the effective length coincides with the minimum rank distance. In this setting, codes attaining $ρ(\mathcal{C})= \min\{m,n\}-1$ are related to covering lifts that are clubs. More generally, we characterize this case through linear maps into suitable quotient spaces, obtaining equivalent interpretations in terms of generalised evasive subspaces and auxiliary matrix rank-metric codes. These results determine the covering radius for several boundary values of the minimum distance and for all $1$-dimensional codes with extension degree $m\in\{3,4,5\}$. For $m=6$ and every $q$ we provide constructions and, for $q\in\{2,3\}$, computational results showing that $1$-dimensional rank-metric codes with the same length and minimum distance can have different covering radii.

0.05

Guillotine and Tiling Cofiniteness in Unary Picture Languages

cs.FL ·2026-08-25 ·Pierluigi San Pietro, Stefano Crespi Reghizzi, Antonio Restivo
publishedtheory similarity 0.53
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

Motivated by the study of closure operations on picture languages, we ask when a set of unary tiles can generate all sufficiently large pictures either via repeated horizontal and vertical concatenations or via tiling operations. In one dimension, the lengths of words in the concatenation closure of a unary language form an additive subsemigroup of positive natural numbers; hence, they are finitely generated. Cofiniteness is characterized by the gcd of these generators being one. Since ordinary cofiniteness in two dimensions is too restrictive and essentially reduces to degenerate one-dimensional conditions on strips, we introduce and study asymptotic cofiniteness: all sufficiently large rectangular pictures are generated. A direct extension of the one-dimensional criterion, requiring the gcd of the tile heights and of the tile widths to be one, is not sufficient, because local congruence obstructions may persist in two dimensions. We give an exact arithmetic characterization of asymptotic cofiniteness for arbitrary, possibly infinite, sets of unary rectangular tiles. The characterization is the same for the guillotine closure, obtained by horizontal and vertical concatenation, and for the full tiling closure. For finite tile sets, the proof combines semigroup arguments and an explicit least-common-multiple stacking construction for sufficiency, while necessity is obtained by a roots-of-unity argument applying also to nonsliceable tilings. The extension to infinite tile sets follows from the finite-basis theorem for Klarner systems.

0.36

Code distances of matrix rank-metric codes under Add-and-Remove transformations

cs.IT ·2026-10-02 ·Gianira N. Alfarano, Rakhi Pratihar, Adrien Vinçotte
theory similarity 0.52
Abstract

For a matrix rank-metric code $\mathcal{C}$ and an integer $i$, the $i$-th subcode distance of $\mathcal{C}$ is the largest minimum rank distance of an $i$-dimensional subcode of $\mathcal{C}$. We study how subcode distances change under the Add-and-Remove construction, in which a subcode of codimension $\ell_s$ is kept and a space of dimension $\ell_a$ is added; this construction is used, with Gabidulin codes, in the $\mathsf{MIRANDA}$ signature scheme. For arbitrary matrix codes, we give inequalities between the subcode distances of the original and of the new code, and we show that Delsarte duality interchanges $\ell_s$ and $\ell_a$. For matrix Gabidulin codes, whose subcode distances are given by an explicit formula, we show that, if $\ell_s<\max\{m,n\}$, then within each block of indices $(a-1)\max\{m,n\}+1,\ldots,a\max\{m,n\}$ not exceeding $\dim_{\mathbb{F}_q}(\mathcal{C}_s)$, all but the last $\ell_s$ subcode distances are the same as for the Gabidulin code, and the remaining ones decrease by at most one; a small example shows that such a decrease can occur. We also express the minimum distance of the new code in terms of the rank distance between the added space and the common subcode. For $\mathsf{MIRANDA}$, the lower bound on the minimum distance of the dual public code used by the known distinguisher when $\ell_s=0$ is a special case of these results; for the proposed parameters, where $\ell_s>0$, the same bound holds for a subcode of codimension $\ell_s$ of the dual public code.

0.05

Asymptotic Bounds for Codes in Toroidal Distance

cs.IT ·2026-11-19 ·Pengjie Zhong, Jinquan Luo
theory similarity 0.52
Abstract

The toroidal distance naturally describes the geometry of codes over \(\mathbb Z_q\), where distances are measured modulo \(q\). In this paper, we study asymptotic bounds for codes in \(\mathbb Z_q^n\) under the toroidal metric. We first derive an explicit asymptotic lower bound from the classical Gilbert--Varshamov bounds for the Hamming and Lee metrics, which serves as a baseline for comparison. We then develop a saddle-point approach for the toroidal metric, which yields an asymptotic Gilbert--Varshamov lower bound and an asymptotic Hamming-type upper bound. For \(3\mid q\), we embed ternary Hamming codes into \(\mathbb Z_q^n\) and obtain another asymptotic lower bound for the toroidal metric. In addition, we derive an asymptotic lower bound for Maximum Toroidal Distance (MTD) codes. We compare these lower bounds with the baseline and prove that they are nontrivial in the corresponding parameter ranges. Finally, we compare the asymptotic bounds numerically.

0.15

Sierpiński--Knopp Wasserstein Distance for Persistence Diagrams and Applications to 2-Wasserstein Approximation

cs.CG cs.LG ·2026-09-01 ·Sebastien Tchitchek, Julien Tierny
benchmarkcode/data similarity 0.51
Abstract · 49 pages, 11 figures, 6 tables. Code and reproducibility package: https://github.com/sebastien-tchitchek/SK-Wasserstein-Reproducibility

This paper introduces the Sierpiński-Knopp (SK) Wasserstein distance, a fast metric between persistence diagrams. The SK-Wasserstein distance, denoted $d_{\mathrm{SK}}$, maps diagram points and their diagonal projections to the unit interval via the Sierpiński-Knopp space-filling curve on the upper diagonal triangle. The encoded point sets are then efficiently matched via one-dimensional optimal assignment, in \(O(N\log N)\) steps, yielding an explicit diagonal-aware point assignment between the two input persistence diagrams. We show that the SK-Wasserstein distance controls the classical \(2\)-Wasserstein distance between diagrams, admits an explicit isometric embedding into a Hilbert space, and induces a positive-definite Gaussian kernel, making the resulting geometry directly compatible with Euclidean and kernel-based learning methods. A tighter surrogate dissimilarity, noted \(W_Γ\), is also introduced based on the point assignments along the curve. Experiments on 12 scientific collections comprising 227 diagrams show median per-collection speedup of \(d_{\mathrm{SK}}\) over state-of-the-art approximations of \(W_2\) is \(626\times\), while the aggregate speedup over the full benchmark is \(2100\times\). Average-linkage partitions obtained from \(d_{\mathrm{SK}}\) and \(W_Γ\) each exactly match the corresponding \(W_2\) partition on 8 of the 12 collections. Hilbert \(k\)-means and Gaussian spectral clustering, both based on \(d_{\mathrm{SK}}\), achieve mean adjusted Rand indices (ARI) of \(0.756\) and \(0.800\), respectively, with respect to the benchmark reference partitions, compared to \(0.750\) obtained by average linkage on \(W_2\). The Gaussian \(d_{\mathrm{SK}}\) kernel supports other kernel-based analysis tasks, as illustrated by its use for contiguous segmentation of ordered diagram collections in our experiments.

0.49