Numerical Analysis
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Friday 22 May
Ensembles of variational data assimilations (EDA) require solving systems of linear equations with iterative methods. The solution process can be accelerated using a limited memory preconditioner constructed with approximations of the leading eigenpairs of the Hessian matrix. Randomized methods for low-rank matrix approximations provide a feasible approach for computing these eigenpairs. These methods use a random sketching matrix to obtain a low-rank representation of the Hessian matrix, which is then used for computing the eigendecomposition. The sketching matrix highly influences the quality of the approximation. In this paper, we show how the structure of the EDA can be exploited to construct a suitable sketching matrix, i.e., using the differences of the right-hand sides of the linear systems of equations. Idealised numerical experiments with the Lorenz-96 model show that the resulting preconditioner is able to accelerate the EDA solution process for all ensemble members, even if constructed from the control member only.
Combinatorics · Cross-listed from cs.LG
Is Dimensionality a Barrier for Retrieval Models?
Why does the low dimensionality of representations, typically $d\approx 1000$, not prevent modern embedding-based retrieval models from scaling to billions, or even trillions, of data points? To answer this question, we study maximal-margin embeddings in the following retrieval model, classically studied in communication complexity [PS86] and more recently in embedding-based retrieval [WBNL26]. Let $A\in \{0,1\}^{N\times n}$ be a matrix indicating whether each of $N$ queries is relevant to each of $n$ documents. We are interested in the largest margin $m>0,$ denoted by $\mathsf{m}^{\mathsf{rd}}(d, A),$ for which there exist unit norm embeddings of the queries and documents $\{U_j\}_{j = 1}^N, \{V_i\}_{i = 1}^n$ with the following property. $\langle U_j, V_i\rangle \ge m$ whenever $A_{ji} = 1$ and $\langle U_j, V_i\rangle \le -m$ otherwise. A large margin is a key proxy for representation quality: it controls both robustness to perturbations and compositional generalization across queries. Our main theorem establishes that the best possible margin without a restriction on the dimension, $\mathsf{m}^{\mathsf{rd}}(+\infty, A),$ can be nearly achieved in dimension $d = O(\mathsf{m}^{\mathsf{rd}}(+\infty, A)^{-2}\log n)$ which improves a theorem of [BDES02]. Together with a matching lower bound in Theorem 1.5, we conclude that when $A\in \{0,1\}^{\binom{n}{k}\times n}$ is the matrix containing all possible $k$-sparse rows once, dimension $d = O(k\log (n/k))$ is necessary and sufficient for the maximal possible margin $\mathsf{m}^{\mathsf{rd}}(+\infty, A) = \Theta(k^{-1/2})$ in this setting. This fully resolves the setup of [WBNL26]. We also give several constructions for large margins when $d = o(k\log (n/k)).$ Finally, we empirically test the InfoNCE and sigmoid losses for producing large margin embeddings and demonstrate a clear advantage of the sigmoid loss.
Read the full abstract
Combinatorics
The INIEP: Irreducible and Positive Realizations
Our focus is upon irreducible nonnegative $n$-by-$n$ matrix realizations of nonnegatively realizable spectra or, equivalently, characteristic polynomials. After giving some general background, we make some useful new observations and show the existence of irreducible nonnegative realizations in some general cases. Then, we focus on $n<5$, where the NIEP is solved. Finally, we focus on the trace 0 case and, using graph theoretic methods, characterize nonnegative irreducible realizability among realizable polynomials. The closely related problem of positive realizations, for trace positive spectra, is also discussed.
Read the full abstract
Optimization and Control
RA-DCA: A Randomized Active-Set DCA for Directional Stationarity in Max-Structured DC Programs
We study nonsmooth difference-of-convex programs whose subtracted convex term is a finite maximum of smooth convex functions. In this setting, standard DCA iterations may converge to critical points that are not directionally stationary, whereas exact active-vertex screening can be expensive when active sets are large or combinatorial. We propose RA-DCA, a vertex-first randomized active-set DCA that projects active gradients onto sampled directions, checks a sampled vertex residual, and uses a small linear program only as a low-residual convex-combination fallback. The method preserves the descent structure of DCA and reduces the randomized screening layer to matrix multiplications. Under the stated regularity, numerical active-set consistency, and random-embedding assumptions, every accumulation point generated by the safeguarded method is directionally stationary with probability one. MATLAB experiments first test the theorem on degenerate max-affine, max-quadratic, and sparse support-function models, where the safeguard avoids nonstationary critical points and closely tracks a full active-vertex scan. Block top-k tests then show that the same screening idea remains useful when exact aggregate enumeration is combinatorial. Trimmed-regression, complementarity, and QUBO diagnostics separate cases where active-set selection helps from cases dominated by multistart search, the DC split, or other problem-specific features.
Read the full abstract
Combinatorics
The number of Pfaffian orientations on punctured polygonally cellulated surfaces
In this paper, we introduce the notion of Pfaffian orientations on (punctured) polygonally cellulated orientable surfaces, and provide an expression for the number of such orientations. This generalizes the notion of Pfaffian orientations on planar graph, where a planar graph is seen as a punctured $2$-sphere, embedded in $\mathbb{R}^3$. So, as a direct corollary of our main theorem, we derive the number of Pfaffian orientations on a planar graph.
Read the full abstract
Combinatorics
Explicit Construction of Polytopes whose Ehrhart Polynomials Realize any Given Sign Pattern
In Ehrhart theory, the well-known sign pattern problem asks: given a positive integer $d\geq 3$ and integers $1 \leq i_1 < \cdots < i_k \leq d-2$, does there exist a $d$-dimensional integral polytope $\mathcal{P}$ such that in its Ehrhart polynomial $i(\mathcal{P}, t)$ the coefficients of $t^{i_1}, \ldots, t^{i_k}$ are negative, while all remaining coefficients are positive? This problem was proposed by Hibi, Higashitani, Tsuchiya, and Yoshida. In this paper, we first construct a class of simplices $\mathcal{S}_d(m)$ whose Ehrhart polynomial has leading coefficient $m$ and all other coefficients fixed positive constants. Then, using the Cartesian product of $\mathcal{S}_d(m)$ and the Reeve tetrahedron, we obtain the first complete solution to the sign pattern problem. Finally, while attacking the sign pattern problem, we discovered a fast algorithm for computing the $h^*$-polynomial of a class of simplices $\Delta(0,q)$. This algorithm is crucial for constructing the simplices $\mathcal{S}_d(m)$.
Read the full abstract
Spectral Theory
Randomly twisted transfer operators and singular values statistics
In this paper, we investigate the singular values of a natural family of transfer operators twisted by large random permutation matrices. In the large N limit, we obtain a Weyl law for its singular values, valid asymptotically almost surely with rapid decay. We also extend the so-called polynomial method to an infinite dimensional setting which implies a "smooth" probabilistic Weyl law for singular values.
Read the full abstract
Probability
Generalized Bessel-Dunkl diffusions
We develop a general theory of Bessel-Dunkl type diffusions in Weyl chambers associated with classical root systems. The class considered here allows time-dependent and configuration-dependent diffusion and drift coefficients, as well as state-dependent singular repulsion coefficients which may vanish on the walls of the chamber. This includes, in a unified framework, Dyson-type logarithmic particle systems, radial Dunkl processes, squared Bessel and Wishart particle systems, and non-colliding diffusion models. Using the geometry of the underlying root system and a symmetric-polynomial approach, we establish weak existence in both the strictly positive repulsion and the degenerate regimes. In the strictly positive regime, we prove that positive repulsion prevents positive-time multiple collisions. In the degenerate case, we identify geometric conditions which exclude boundary sticking and allow one to recover the genuine singular equation from its interior form. We also prove non-explosion under a radial linear-growth condition, obtain pathwise uniqueness and strong existence in the non-sticky class under natural Yamada-Watanabe type or locally Lipschitz assumptions, and establish a mean-field convergence theorem for systems of types $A_{N-1}$, $B_N$, and $D_N$. Together, these results build the structural foundations for a systematic theory of generalized Bessel-Dunkl diffusions with non-constant and possibly degenerate coefficients.
Read the full abstract
Algebraic Topology
Top-dimensional rational cohomology of the congruence subgroup $\Gamma_{0,n}^+(p)$
Let $\Gamma_{0,n}^+(p)\subset \mathrm{SL}_n(\mathbb{Z})$ be the congruence subgroup of level-$p$ whose first column is of the form $(*,0,\dots,0)^t\bmod p$. We prove that the top-dimensional cohomology group $H^{\binom{n}{2}}(\Gamma_{0,n}^+(p);\mathbb{Q})$ vanishes for $p\in\{2,3,5,7,13\}$ if $n \geq 3$, as well as for $p \leq 6n-14$. Additionally, we prove a non-vanishing result, showing that this cohomology group is nonzero for $n = 2$ for every prime $p$, and for $n=3$ for all primes $p \notin \{2,3,5,7,13\}$.
Read the full abstract
Optimization and Control
End-to-End Pseudo-Measurement Learning for State Estimation under Limited Observability
Distribution System State Estimation (DSSE) is becoming increasingly important with the integration of Distributed Energy Resources (DERs) and the active operation of distribution networks (DNs), but it remains challenging due to the limited and heterogeneous monitoring infrastructure available in these networks. To address this challenge, this paper proposes a novel DSSE framework that restores observability through data-driven pseudo-measurements generated by a Neural Network (NN), while preserving the exact non-linear AC power flow model within a classical Weighted Least Squares (WLS) estimator. Unlike conventional approaches that generate pseudo-measurements independently of the physical estimation process, the proposed method explicitly couples both components through an end-to-end learning formulation. Specifically, the WLS estimator is embedded as a layer within the NN architecture, enabling implicit differentiation to propagate the impact of pseudo-measurements on the final estimation error back to the NN parameters. Extensive numerical experiments on the IEEE 30-bus and IEEE 33-bus systems demonstrate that the proposed framework consistently outperforms state-of-the-art methods in state estimation (SE) accuracy under a wide range of loading conditions and measurement configurations.
Read the full abstract
Combinatorics
Finite-state enumeration of adjacency-constrained 132-avoiding permutations
For a fixed integer $m\ge 1$, let $\mathcal{A}_n^{(m)}$ be the set of permutations $\pi\in S_n$ that avoid the pattern $132$ and satisfy the adjacency bound $|\pi_{i+1}-\pi_i|\le m$ for all $i$. Here, a pattern $132$ means three indices $i<j<k$ such that $\pi_i<\pi_k<\pi_j$. A recent study initiated the enumeration of these constrained 132-avoiding permutations, treating the case $m=2$ by deriving a rational ordinary generating function and asking for finite-state decompositions, rational generating functions, and explicit rational formulas for larger fixed $m$. We introduce a two-sided endpoint-state decomposition that works uniformly for every fixed $m$. The state variables impose threshold bounds on the endpoint deficiencies $n-\pi_1$ and $n-\pi_n$, with thresholds in $\{0,1,\ldots,m-1,\infty\}$. This gives at most $(m+1)^2$ states and proves that, for every fixed $m$, the ordinary generating function $A^{(m)}(x)$ is rational and can be computed effectively by exact linear algebra. We also identify cyclic strongly connected components of the dependency graph in the finite-state system to give an explicit upper bound for the order of an eventual constant-coefficient recurrence satisfied by the sequence $a_n^{(m)}=|\mathcal{A}_n^{(m)}|$. We then recover the known case $m=2$ from this state system and work out the case $m=3$ explicitly. On the asymptotic side, we prove that the exponential growth constant exists for every $m$; for $m\ge2$ it is obtained from the spectral radii of the two cyclic components with more than one vertex in the state system. We determine the simple-pole asymptotics for $m=2$ and $m=3$, and we prove that the growth constants are nondecreasing in $m$, strictly smaller than the Catalan growth constant $4$ for every finite $m$, and converge to $4$ as $m\to\infty$.
Read the full abstract
Numerical Analysis
On the treatment of topology changes on 3D polyhedral moving meshes via 4D space-time hole-like elements in direct ALE ADER-DG methods
This work investigates a novel approach for the high order evolution of hyperbolic PDEs using ADER discontinuous Galerkin schemes within a direct Arbitrary-Lagrangian-Eulerian (ALE) framework on 3D moving polyhedral meshes with topology changes. Our direct ALE method is based on the PDE integration over 4D (3D+time) space-time control volumes connecting the elements of two subsequent tessellations, so to simultaneously evolve the solution both in time and between the two different meshes in an effective and high order manner. In this way, we also avoid any complex and expensive projection-reconstruction techniques and any mesh intersection operation typical of indirect ALE schemes. The crucial step consists in the strategy for building space-time control volumes that also connect elements with different shapes and neighborhoods due to a change in topology. In fact, simply linking existing elements by collapsing or expanding their edges would leave a "hole" in the space-time domain. To fill it, we introduce additional degenerate elements that we call hole-like elements. These are 4D objects with zero 3D volume at both the beginning and end of the timestep, but which possess a strictly non-zero 4D space-time volume. Given the uniqueness of this space-time approach in 3D+time and the necessity of characterizing the geometry of such elements, the main objective of this paper is the formal geometrical and numerical description of the method as well as the presentation of new and intuitive visualization strategies. In particular, we provide a detailed characterization of the hole-like elements arising in correspondence to 2-3, 3-2, and 4-4 flips on the underlying Delaunay tetrahedralization. Finally, we numerically show that the method is fully conservative, satisfies the GCL and maintains the correct order of convergence even in the presence of frequent topology changes.
Read the full abstract
Information Theory · Cross-listed from eess.SP
Distributed Two-Phase Processing for Modular XL-MIMO with Wireless Fronthaul under Hardware Impairments
Modular extremely large-scale MIMO (XL-MIMO) architectures combined with wireless fronthaul provide a scalable alternative to monolithic arrays, but their performance is sensitive to hardware impairments and resource allocation strategies. In this paper, we consider a distributed two-phase processing framework for modular XL-MIMO systems employing amplify-and-forward wireless fronthaul under practical hardware constraints. We jointly model access-side and fronthaul-side distortions and formulate a weighted minimum mean-square error (WMMSE)-based optimization problem that maximizes the uplink sum spectral efficiency (SE) by jointly adjusting UE transmit powers and fronthaul amplification levels. The resulting algorithm alternates between distortion-aware receiver design and convex power-control updates. Numerical results demonstrate that the proposed joint optimization significantly improves spectral efficiency compared to fixed transmission strategies, particularly when the CPU has a moderate number of antennas, while also quantifying the relative impact of access and fronthaul impairments.
Read the full abstract
Numerical Analysis
Spectral distribution of Jacobi weighted histopolation matrices via GLT theory
In this paper we study a weighted histopolation problem on $[-1,1]$ associated with Jacobi weights. In the first part of the present work we prove results in approximation theory, while in the second we analyze the resulting matrices from an asymptotic linear algebra perspective. More in detail, in the first part, given weighted cell averages, we construct a reconstruction operator based on weighted primitives of Jacobi polynomials and investigate the resulting discretization matrices. At any fixed discretization level, we derive an exact factorization of the histopolation matrix through a backward-difference operator and a sampling operator of Jacobi weighted primitives. Combining a sharp integration by parts identity with the three-term recurrence of Jacobi polynomials, we further show that the primitive sampling operator admits an explicit decomposition involving a tridiagonal coupling matrix in the Jacobi spectral index. This yields a tridiagonal factor representation of the histopolation matrix. In the second part, under standard mesh-regularity assumptions, we show that all the various induced matrix sequences belong to the Generalized Locally Toeplitz (GLT) class, by describing in detail the related GLT symbols. As a consequence, we provide the corresponding spectral distributions and discuss their implications for numerical stability when solving the associated linear systems.
Read the full abstract
Information Theory · Cross-listed from eess.SP
Constant-Envelope Quantized Precoding with Power Control for Cell-Free Massive MIMO-OFDM
Cell-free massive MIMO has matured into a key candidate technology for 6G and beyond, owing to its ability to provide nearly uniform service quality to many user equipments (UEs) over the same time-frequency resources. Unlike conventional cellular massive MIMO, the core idea is to distribute a large number of low-cost access points (APs) across the network and enable joint coherent transmission and reception. While early works largely assumed ideal hardware, hardware impairments become inevitable when APs are implemented with low-cost components. In this context, this paper investigates the adverse impact of low-resolution digital-to-analog converters (DACs) on the downlink performance of cell-free massive MIMO-OFDM systems. In contrast to prior studies that mainly quantify spectral-efficiency degradation under low-resolution DACs, we consider the design of quantized constant-envelope (CE) precoding, which additionally enables the use of highly power-efficient amplifiers. To the best of our knowledge, this is the first work on quantized CE precoding for cell-free massive MIMO-OFDM. Beyond adapting the classical maximum-antenna-power method, we propose a novel power-control strategy across APs that mitigates the detrimental effects of severely quantized transmitters by reducing the contribution of harmful APs. Simulation results demonstrate that the proposed power-control mechanism significantly improves the uncoded bit error rate performance.
Read the full abstract
Optimization and Control
A Stochastic Implicit Proximal Point Algorithm for Solving Linearly Constrained Stochastic Minimax Problems
This paper presents a novel approach to solving large-scale minimax problems with nonsmooth regularizers. We propose a stochastic implicit proximal point algorithm with variance reduction techniques where stochastic oracles are selected in two cases – with or without replacement. The semismooth Newton methods with Armijo line search is used to solve the implicit proximal point update subproblem in each iteration. The algorithm efficiently handles the strongly-convex-strongly-concave objective function with nonsmooth regularizers and coupling linear equations, which is proved to exhibit global q-linear convergence of the iterations to the saddle point and global r-linearly convergence of the multipliers to the multiplier set in expectation. Numerical experiments on machine learning problems demonstrate the superiority of the proposed method over state-of-the-art algorithms in terms of both computational efficiency and selection of the step sizes.
Read the full abstract
Dynamical Systems
Rate-induced tipping in a coral reef ecosystem: A slow increase in fishing effort can induce reef collapse
Critical transitions describe sudden changes in the state of an ecosystem. In classical bifurcation theory, such transitions occur when the value of a parameter exceeds a threshold (“bifurcation") value. More recently, critical transitions which are triggered by the rate of change of a parameter were described by Wieczorek et al. [Wieczorek, S., Ashwin, P., Luke, C.M., Cox, P.M., Proceedings of the Royal Society A 467(2129), 1243-1269, 2011]. In mathematical ecology, these rate-induced transitions correspond to environmental conditions that deteriorate too rapidly for the ecosystem to adapt, resulting in population collapse (“R-tipping"). In this article, we consider the potential for rate-induced tipping due to increased anthropogenic stress in a recently proposed behavioural-demographic model for herbivorous fish, algae, and coral in a coral reef ecosystem [Gil, M.A., Baskett, M.L., Munch, S.B., Hein, A.M., PNAS 117(41), 25580-25589, 2020]. We first show that the underlying demographic model can be reframed naturally as a singularly perturbed system with two fast variables and one slow variable in which bistability can occur in ecologically relevant parameter regimes. We explore the potential for canard-type dynamics in the model, complementing numerical results with an analytical description through the lens of geometric singular perturbation theory, and we describe R-tipping as a result of an increase in the fishing effort. We show that trajectories will undergo canard-induced tipping by passage through a folded node singularity, whereas a folded focus may give rise to tipping of jump type; in both scenarios, a catastrophic collapse occurs in the populations of herbivorous fish and coral, with the population of algae experiencing a “bloom". Alternatively, we may observe “tracking" of a sustainable coexistence state between the three populations in the presence of a folded focus.
Read the full abstract
Numerical Analysis
A high-order nodally bound-preserving and mass-conservative method for linear fourth-order elliptic problems and its applications to nonlinear parabolic equations
We propose a high-order finite element method for linear fourth-order elliptic problems that is both nodally bound-preserving and mass-conservative, based on a variational inequality formulation. The method admits an equivalent strictly convex minimization structure, which ensures well-posedness and enables an optimal error estimate in the $H^1$-seminorm, under suitable regularity assumptions. This framework is further extended to nonlinear fourth-order parabolic problems through space–time high-order discretizations that combine variational inequalities, BDF schemes, and scalar auxiliary variable (SAV) techniques. The fully discrete schemes preserve nodal bounds and mass, and a modified energy stability result is established for the first-order temporal scheme. We also apply the same framework to nonlinear second-order parabolic problems by introducing a consistent fourth-order regularization, leading to space–time high-order schemes with the same bound-preserving and mass-conservative properties. Extensive numerical results, including challenging tests with singularities and low regularity, demonstrate the stability, efficiency, and high-order accuracy of the proposed methods.
Read the full abstract
Differential Geometry
Magnitude of metric measure spaces and integrals over geodesics
We propose a definition of magnitude for a length space with a Borel measure, which involves integrals over the set of geodesics. This quantity agrees with the magnitude of finite metric spaces, up to re-scaling the metric to ensure the convergence, when we use the counting measure on them. We also prove a version of the homogeneous magnitude theorem, by showing that the new definition agrees with the volume when we use the weight measure on a compact homogeneous Riemannian manifold. We compute various examples, which suggest that this quantity can capture information of non-uniqueness of geodesics, such as the injectivity radius, corresponding to the generating degrees of the magnitude homology.
Read the full abstract
Optimization and Control · Cross-listed from cs.LG
Non-normal spectral signatures of instability in neural network training dynamics
Training instabilities in deep networks - loss spikes, oscillatory convergence, and gradient pathologies - are empirically prevalent but lack a rigorous operator-theoretic explanation. We show that the linearized update operators for practically used optimizers are generically non-normal: for Adam, non-normality is controlled by the commutator [H, M] between the Hessian and the diagonal adaptive preconditioner, while for SGD with momentum it arises from the augmented state-space structure of the update map. Applying non-normal stability theory to these operators, we derive a conservative pseudospectral precursor bound in which \kappa(V) serves as an early-warning indicator of transient amplification even when the spectral radius remains below one, and we establish that exceptional points of the update operator appear as the \kappa(V) -> \infty limiting case of this framework. Numerical experiments on two-layer networks confirm that the spectral radius \rho(J) provides no separation between stable and unstable training phases while \kappa(V) separates them by approximately one order of magnitude, complementing the classical sharpness criterion with a continuous severity measure of non-normal amplification. These results establish non-Hermitian operator theory as a useful and underexplored framework for neural network optimization stability, offering a diagnostic language and proof-of-concept benchmark for understanding adaptive optimization stability.
Read the full abstract
Logic
Definability via the tilting correspondence
We show that arithmetic definability of henselian valuations is preserved by the tilting correspondence. Moreover, we show that if a perfectoid valuation is arithmetically definable, then no parameters are needed. We also investigate whether these definitions can be chosen uniformly, and discuss the required quantifier complexity.
Read the full abstract
Probability
An almost sure invariance principle for the Takagi-van der Waerden class functions
The Takagi-van der Waerden functions are a well-known class of continuous but nowhere differentiable functions. In this paper, we study their weighted versions, the Takagi-van der Waerden class functions $f_{r,a}(x)$, from a probabilistic point of view. We prove that the local modulus of continuity of $f_{r,a}(x)$ is described by a standard Brownian motion under some regularity assumptions on the weights, as an application of a strong approximation for elephant random walks remembering the very recent past with variable step length.
Read the full abstract
Information Theory
Self-Orthogonal Twisted Generalized Reed-Solomon Codes and Their Application to Quantum Error-Correcting Codes
In this paper, two classes of twisted generalized Reed-Solomon (TGRS) codes with multi-twists are studied. Firstly, some sufficient and necessary conditions for these codes to be self-orthogonal and self-dual are established. Then several explicit constructions of self-orthogonal and self-dual codes are presented, from which quantum stabilizer codes are further derived. Finally, some corresponding examples are given, especially that some of these codes are MDS, AMDS or NMDS and that some of the resulting quantum stabilizer codes are optimal, achieving the quantum Singleton bound.
Read the full abstract
Algebraic Geometry · Cross-listed from cs.LG
Commutator-Induced Uncertainty in VAEs
Variational autoencoders (VAEs) often struggle to represent non-commutative structure in learned latent spaces. Symmetry-aware VAEs commonly address this issue by enforcing commutativity through algebraic regularization, which is appropriate for commutative transformation groups but can suppress meaningful non-commutative structure when it is intrinsic to the data. We argue that non-commutativity should instead be explicitly diagnosed and reflected in reconstruction behavior. We introduce a Lie Group VAE framework that combines geometric and algebraic perspectives on uncertainty while separating discrete generative factors from continuous geometric transformations. In a first phase, the model is trained without structural constraints while algebraic non-commutativity is measured through finite Baker-Campbell-Hausdorff deviations and decoder order sensitivity is measured through reconstruction order-swap tests. These diagnostics reveal a scale mismatch between latent non-commutativity and reconstruction behavior under unconstrained training. In a second phase, we introduce a deformation-stability constraint with a data-driven calibration constant that aligns decoder sensitivity with algebraic non-commutativity. We evaluate the framework on dSprites, 3DShapes, 3DCars, and CelebA against generic and symmetry-aware baselines, including beta-VAE, CLG-VAE, and CFASL. Across synthetic benchmarks, the method improves reconstruction quality and yields decoder-level behavior more consistent with latent non-commutative structure. Qualitative analyses show clearer order-dependent latent compositions and more stable reconstructions. On CelebA, the model yields more faithful reconstructions and factor-specific latent traversals than CFASL, while also exhibiting meaningful order-dependent interactions between learned latent directions.
Read the full abstract
Combinatorics
AMDS and quantum AMDS Constacyclic codes of length $4p^\varsigma $ over $\mathbb{F}_{{p}^{m}}$
This paper provides a comprehensive analysis of almost maximum distance separable (AMDS) constacyclic codes of length $4p^{\varsigma}$ over the finite field $\mathbb{F}_{p^m}$, where $p$ is an odd prime number. Furthermore, it introduces the construction of quantum AMDS (qAMDS) codes, drawing on the principles of the Calderbank-Shor-Steane (CSS) framework, which enhances their applicability in quantum error correction. This work aims to deepen the understanding of these codes and their potential uses in both classical and quantum computing environments.
Read the full abstract
Combinatorics · Cross-listed from cs.LG
Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them
Graphs with a simple spectrum admit cubic-time isomorphism testing, yet we prove that for every natural number $k$, the $k$-Weisfeiler-Leman ($k$-WL) test cannot distinguish all non-isomorphic graphs with a simple spectrum. As the WL hierarchy upper-bounds the distinguishing power of widely-used Graph Neural Networks (GNNs), this incompleteness applies to all such GNNs, ruling out completeness for every $k$-WL-aligned GNN family. To close this gap, we introduce PRiSM (Partition, Refine, Solve, Match), the first provably complete canonicalization of simple-spectrum eigendecompositions. PRiSM obtains the completeness guarantee that prior canonicalizations provably lack, and resolves the open problem of achieving complete expressivity on simple-spectrum graphs. When composed with DeepSets or a Transformer, PRiSM achieves universal approximation on simple-spectrum graphs, justifying the use of canonicalized Laplacian positional encodings. Empirically, PRiSM performs comparably to or outperforms existing spectral canonicalizations on graph regression, classification, and expressivity
Read the full abstract
General Topology
The separability embedding of $\sigma$-compact strongly topological gyrogroups
In this paper, it is shown that every right $\omega$-narrow strongly topological gyrogroup $G$ is right $\omega$-balanced by applying the gyrosemidirect product groups. Then we investigate the class of $\sigma$-compact strongly topological gyrogroups, and conclude that every $\sigma$-compact strongly topological gyrogroup is range-metrizable. By applying these results, we discuss the separability embedding of $\sigma$-compact strongly topological gyrogroups, and claim that the following three statements (a)-(c) are equivalent for any $\sigma$-compact strongly topological gyrogroup $G$: \smallskip (a) $G$ is homeomorphic to a subspace of a separable regular space; \smallskip (b) $G$ is topologically gyrogroup isomorphic to a subgyrogroup of a separable strongly topological gyrogroup; \smallskip (c) $G$ is topologically gyrogroup isomorphic to a closed subgyrogroup of a separable path-connected, locally path-connected strongly topological gyrogroup. The above results extend the classical results from topological groups to the class of strongly topological gyrogroups in the literature.
Read the full abstract
Combinatorics
A superlinear improvement on line-free sets in $\mathbb{F}_p^3$
Building on an earlier result of the author together with Elsholtz, Führer, Füredi, Pach, Simon and Velich, we present an improved construction for a line-free set in $\mathbb{F}_p^3$, showing that $r_p(\mathbb{F}_p^3)\ge (p-1)^3+\frac18 p^{3/2} - O(p)$ as $p\to \infty$. This results in the first superlinear-term improvement over the standard hypercube construction $\{0,1,\ldots,p-2\}^3$. Via complementation, a line-free set in $\mathbb{F}_p^3$ corresponds to a $2$-blocking set in the affine geometry $AG(3,p)$, hence we also obtain an upper bound of $3p^2-\frac18p^{3/2}+O(p)$ on the smallest size of such a $2$-blocking set.
Read the full abstract
Metric Geometry
A unified approach to Penner, Ptolemy, and Casey's theorems in several dimensions
We prove Penner's theorem on horocycles and theorems of Ptolemy and Casey, all with full converses, in hyperbolic space of several dimensions. Recently Waddle observed that the equations underpinning these three theorems are related, and it is this viewpoint that we advance, using the Lorentzian model of hyperbolic space. We show that all three theorems can be derived from a common Gram-matrix calculation applied to lightlike, timelike, and spacelike vectors. Remarkably, our approach gives a version of Casey's theorem in the plane with a full converse, involving three geometric alternatives, which to our knowledge has not previously been recorded.
Read the full abstract
Information Theory
Sparse In-Network Learning via Shortest-Path Backpropagation and Finite-Rate Gating
In-network learning (INL) trains distributed neural modules by exchanging latent activations and backpropagated errors over a communication graph. This letter proposes Dijkstra-pruned INL (D-INL), which removes non-tree links by retaining a capacity-aware shortest-path tree rooted at the fusion node. To balance sparsity and predictive information, local routing (or aggregation) is modeled as a finite-rate stochastic gate with rate $R_g=I(Z; T)$. We derive a rate-distortion-generalization bound and validate the method on a reproducible distributed-classification experiment, where D-INL reduces training exchange by $70.4\%$ while preserving accuracy within the standard deviation of dense INL. Adding finite-rate regularization further reduces the estimated latent rate by $45.7\%$ relative to unregularized Dijkstra INL.