Rings and Algebras
Algebras with Variable Operator-Valued Structural Constants and Their Applications
Vitalii Shpakivskyi
We introduce a new class of
algebras with variable operator-valued structural constants and develop elements of the theory of monogenic functions in such
algebras. Compatibility conditions for the structural operators are established. It is shown that the components of monogenic functions satisfy second-order operator-differential equations with variable coefficients, and converse results are proved. The proposed approach provides a constructive method for obtaining solutions of various differential, integro-differential, and functional-differential equations. Several illustrative examples are presented.
Read the full abstract ▾
Rings and Algebras
Algebras with Variable Structural Constants and Their Applications
Vitalii Shpakivskyi
We introduce a new class of
algebras with variable structural constants and develop elements of the theory of monogenic functions in such
algebras. Compatibility conditions for the structural functions are established. It is shown that the components of monogenic functions satisfy certain second-order partial differential equations with variable coefficients, and converse results are proved. This approach provides a constructive method for obtaining explicit solutions of such equations. Several illustrative examples are presented.
Read the full abstract ▾
Combinatorics
Resolutions of two conjectures on the spectral diameter
Irena M. Jovanović, Jelena Sedlar and Riste Škrekovski
Let $\lambda_1(G) \geq \dots \geq \lambda_n(G)$ be the adjacency spectrum of a graph $G$ on $n$ vertices. The spectral distance $\sigma(G,H)$ between $n$-vertex graphs $G$ and $H$ is the Manhattan distance between their spectra, i.e. $\sigma(G,H) = \sum_{i=1}^n |\lambda_i(G) - \lambda_i(H)|$. Given a set $\mathcal{G}$ of pairwise non-isomorphic graphs of order $n$, the spectral diameter of $\mathcal{G}$ is defined as $\mathrm{sdiam}(\mathcal{G}) = \max\{\mathrm{secc}_{\mathcal{G}}(G) : G \in \mathcal{G}\}$, where $\mathrm{secc}_{\mathcal{G}}(G) = \max\{\sigma(G,H) : H \in \mathcal{G}\}$ is the spectral eccentricity of $G \in \mathcal{G}$. Among six
conjectures on spectral distances posed by Z. Stanić in 2012, two
conjectures related to the spectral diameter of certain graph classes remained open. One of them concerns the spectral diameter of the set $\mathcal{B}_n$ of all connected bipartite graphs of order $n$, while the other, of the set $\mathcal{T}_n$ of all trees of order $n$. More precisely, Stanić conjectured that $\mathrm{sdiam}(\mathcal{T}_n) = \sigma(P_n, K_{1,n-1})$, where $P_n$ is the path graph, while $K_{1,n-1}$ is the
star, and that $\mathrm{sdiam}(\mathcal{B}_n) = \mathrm{secc}_{\mathcal{B}_n}(K_{\lceil n/2 \rceil, \lfloor n/2 \rfloor})$, where $K_{\lceil n/2 \rceil, \lfloor n/2 \rfloor}$ is the complete bipartite graph. In this paper, both of these
conjectures are disproved.
Read the full abstract ▾
Number Theory
On murmurations
Timothy Nelson, Erick Ross, Maya Wassercug et al. (+1 more)
In the recent paper “Murmurations", Zubrilina showed that the
Fourier coefficients of modular forms follow a certain murmuration pattern. The proof given in “Murmurations" proceeded by estimating the terms of the Skoruppa-Zagier trace formula. However, a few technical issues arise in the proof, including an omission of certain Chebyshev factors that arise in summations from the Skoruppa-Zagier trace formula. In this work, we address these issues to solidify the proof.
Read the full abstract ▾
All authors Timothy Nelson, Erick Ross, Maya Wassercug, Hui Xue
Dynamical Systems
Mathematical modelling of a multicluster open system: transfer-operator recovery from aggregate data under a least-action prior
A. P. Nevecheria
Many open systems are observed only through aggregate snapshots, while the rule that moves objects between states stays hidden. This paper studies the inverse problem of recovering the transfer operator of a multicluster open system from two adjacent snapshots. The consistent operators fill an affine
manifold: the data fix the aggregate flows and leave the internal routing free, so every recovery method commits to a prior that selects one operator. Tikhonov regularisation with a zero reference gives the uniform
outflow on each source simplex, which underestimates retention in an inertial system. We propose least action on the operator trajectory, under which the rule changes as little as the data permit. In discrete time this is exact as a probability statement: the action prices a trajectory by its likelihood under a Gaussian reference drawn toward full retention, so least action selects the most probable trajectory consistent with the balance. A causal construction keeps the balance exact by moving the operator only inside the null space of the constraints, and we relate it to optimal transport, to Perron-Frobenius coarse-graining, and to the Schrödinger bridge. Two instantiations carry it: the Russian labour
market and a radiation-damped relativistic electron ensemble. The construction holds the balance to machine precision where temporal smoothing corrupts it by twelve percent on the labour series and sixty percent in the physical one. The spectral gap is non-identifiable from aggregate snapshots but available from micro-trajectories, where Ulam's method reproduces the Landau-Lifshitz rate to within six percent. On the short labour series no method beats the naive forecast in point accuracy at conventional significance levels. The value is structural: an interpretable operator, an exactly preserved balance, and an explicit information limit of aggregate observation.
Read the full abstract ▾
Combinatorics
On Alon's problem concerning the difference between connected domination number and domination number
Chengli Li and Bo Zhou
For a connected graph $G$, let $\gamma(G)$ and $\gamma_c(G)$ denote its domination number and connected domination number, respectively. Let $M(n,k)$ be the maximum of $\gamma_c(G)-\gamma(G)$ over all connected $n$-vertex graphs of minimum degree at least $k$. Alon proved that \[ 2\left\lfloor\frac{n}{k+1}\right\rfloor-O(1)\le M(n,k)<\frac{n}{k+1} \bigl(\log\lceil\log(k+1)\rceil+3\bigr). \] He proposed a problem to determine or estimate $M(n,k)$ for $n-1\ge k\ge 3$, and particularly remarked that it would be interesting to close the $\log\log(k+1)$ gap between the upper and lower bounds and decide whether or not $M(n,k)=\Theta\bigl(\frac{n}{k+1}\bigr)$. We give an asymptotic answer to Alon's problem for sufficiently large $k$. More precisely, $M(k+1,k)=0$. For $n>k+1$, let \[ \nu=\frac{n}{k+1} \text{ and } \Phi(x)= \frac{1}{x\log\!\frac{x}{x-1}} \ (\text{for }x>1). \] As $k\to\infty$, uniformly over all integers $n>k+1$, \[ M(n,k)= \big(\Phi(\nu)+o(1)\big) \nu\log\log(k+1). \]
Read the full abstract ▾
Numerical Analysis
Closure complexity of Bänsch-type algorithms for tetrahedral mesh refinement
Yuwen Li and Zhiyuan Yang
We prove, to our knowledge, the first unconditional cumulative closure estimates for the Arnold–Mukherjee–Pouly (AMP) refinement
algorithm and the original face-marked tetrahedral
algorithm of Bänsch on arbitrary conforming initial tetrahedral meshes. Let $T_0,\ldots,T_L$ be an adaptive mesh sequence generated by either
algorithm, with $M_\ell\subseteq T_\ell$ denoting the marking set at step $\ell$. Then $$\#T_L-\#T_0\leq C_{\mathrm{clos}}(T_0)\sum_{\ell=0}^{L-1}\#M_\ell.$$ The proof is intrinsic to the physical three-dimensional mesh and requires neither an initial compatibility condition nor a higher-dimensional
embedding. It organizes conformity refinements into a causal forest and combines a uniform horizontal-propagation estimate with a weighted packing argument to obtain an explicit closure constant. For the original Bänsch
algorithm, every history-dependent resolution of the initial two-edge ambiguity is represented by one of finitely many AMP histories. The estimate therefore holds uniformly for arbitrary deterministic or nondeterministic choices. This resolves a long-standing complexity question for the Bänsch–AMP family.
Read the full abstract ▾
Numerical Analysis
Semidiscrete Modeling of Dislocation-Disclination Systems: Finite Element Formulation
Pierluigi Cesana, Edoardo Fabbrini, Andrés A. León Baldelli et al. (+1 more)
We present a numerical formulation for the resolution of finite systems of interacting edge dislocations and wedge disclinations. The approach is based on a finite element discretization of a fourth-order
elliptic boundary value problem arising from the mechanical
equilibrium equations of plane-strain linear elasticity in the presence of kinematic incompatibilities. The numerical implementation follows a continuous interior penalty discontinuous Galerkin framework and relies on the solution of a finite set of local
cell problems. Our method is validated against analytical
benchmarks and used to explore several non-trivial dislocation-disclination configurations, illustrating how translational and rotational incompatibilities shape the stress state of the body.
Read the full abstract ▾
All authors Pierluigi Cesana, Edoardo Fabbrini, Andrés A. León Baldelli, Marco Morandotti
Numerical Analysis
Uniform Stability of Scott-Vogelius Elements on Three-Dimensional Freudenthal Meshes in Degrees Four and Five: Resolving the Farrell-Mitchell-Scott Conjecture
Hanbing Liang and Fujun Liu
We establish a uniform inf-sup stability estimate for the Scott-Vogelius finite element spaces on uniform Freudenthal tetrahedralizations of the unit cube for
polynomial degrees k >= 4. This result completely settles the first
conjecture of Farrell, Mitchell, and Scott for the critical degrees k = 4 and k = 5, complementing the known stability range for higher
polynomial degrees. The main mathematical difficulties stem from the complex topological compatibility required at the singular vertices and the corresponding mean-value constraints across adjacent elements. We tackle these challenges by developing a unified barycentric skeleton-bubble calculus that explicitly constructs vertex jets, edge modes, and face transfers to globally route element means. The accompanying exact computations independently verify these finite-dimensional identities and provide reproducibility data.
Read the full abstract ▾
Mathematical Physics · Cross-listed from cond-mat.stat-mech
A summation rule for the four-coupling beta function of four-dimensional nonplanar Euclidean scalar $\varphi^{4}$ theory under factorial coefficient bounds, and a domain on which the summed beta function is well defined
Puyu Zeng
Let $\mathbf{c}=(\lambda,\alpha,\mu,\nu)\in\mathbb{R}^{4}$ denote the four running couplings of four-dimensional nonplanar Euclidean scalar $\varphi^{4}$ theory, and let $B(\mathbf{c})=\sum_{p\ge2}\sum_{|\mathbf{m}|=p}\beta(\mathbf{m})\mathbf{c}^{\mathbf{m}}$ be its formal beta-function series. Assuming the factorial coefficient bounds $|\beta(\mathbf{m})|\le (p-1)!C^{p-1}$ for $|\mathbf{m}|=p$, we construct an explicit summation rule $\mathcal{S}$, given by a cut Borel–Laplace transform whose cut is placed by a scale-covariant real-analytic gauge. We prove that it assigns a well-defined real value to $B$ on an explicit nonempty open domain, in fact on all of $\mathbb{R}^{4}$. The summed function $\mathcal{S}B$ is linear and real, real-analytic on $\mathbb{R}^{4}\setminus\{0\}$, $C^\infty$ on $\mathbb{R}^{4}$ with Taylor series $B$ at the origin, and Gevrey-$1$ asymptotic to $B$ to all orders with an explicit remainder bound. At optimal truncation the remainder is $O(e^{-\eta/(C\|\mathbf{c}\|_\infty)})$ for any $\eta<1$. We show that $\mathcal{S}B$ reproduces the classical Borel sum and the ordinary sum of a convergent series up to errors of the same exponentially small order. Exact reproduction is impossible for any linear rule defined on the whole admissible class: regularity forces all weights to equal $1$, leading to divergence. Finally, we prove optimality under the stated hypothesis. Admissible series may diverge at every $\mathbf{c}\ne0$, and their Borel transforms may have the circle $|\tau|=1/(C\|\mathbf{c}\|_\infty)$ as a natural boundary, so classical Borel-type summation need not be available on the class. Moreover, there exist two functions indistinguishable at the level of the coefficient bounds yet differing by exactly $(2\pi/C)e^{-1/(C\|\mathbf{c}\|_\infty)}$. All constants are explicit and all arguments are self-contained.
Read the full abstract ▾
Numerical Analysis
Accelerating Multiple-Precision LU Decomposition with Ozaki Scheme II
Tomonori Kouya
Solving ill-conditioned linear systems needs LU decomposition in precisions beyond binary64. The standard approaches – GMP/MPFR, or multi-component arithmetic such as double-double – leave every scalar multiply-add inside the O(n^3) update in multiple precision, and so cannot exploit the low-precision
matrix engines that dominate current hardware. We build a blocked, partially pivoted LU decomposition on Ozaki scheme II, which replaces the multiple-precision GEMM by exact integer modular products followed by an explicit CRT reconstruction, and implement it for multi-component (DD/TD/QD) and arbitrary precision, on CPUs and GPUs. Two contributions make this practical: a direct conversion between the non-overlapping expansion format and the internal fixed-point representation, which removes the MPFR round trip and is worth a factor of 2.4–4.7; and new FP16, FP8 and binary64 GPU back-ends, the FP8 one using a balanced base-17 two-digit encoding that keeps the full 362.8-bit CRT capacity of INT8. On an Arm/GB10 and an x86/H100 the fastest back-end changes with the machine: INT8 wins on GB10, whereas on H100 binary64 is fastest for QD, beating both the native implementation and INT8. The essential point of Ozaki scheme II is thus not to use a low-precision engine but to choose the format maximising bits-per-modulus times engine throughput. For the Lotkin
matrix at p ~ 1.2 log2 cond(A) we reach relative errors of 10^-645 at n=2048, up to 2.84x faster than a fully OpenMP-parallel multiple-precision LU. We also show by measurement that the O(p) advantage of scheme II over scheme I applies only to the GEMM term: modular reduction and CRT grow as O(p^2) and dominate the runtime at the
matrix sizes considered here. The implementation is released as open source.
Read the full abstract ▾
Number Theory
Infinitely Many Binomial Coefficients of Deficiency One
Xu Zhang
A binomial coefficient $\binom{n}{k}$ is good if all its
prime divisors exceed $k$, and its deficiency is the number of $k$-smooth integers in $(n-k,n]$. A short constructive proof of the existence of infinitely many good binomial coefficients with deficiency exactly one is given, which provides an answer to a problem of Erdős, Lacampagne, and Selfridge.
Read the full abstract ▾
Combinatorics
A square-root law for equitable coloring
Mohammad F. Marashdeh
An equitable $k$-coloring of a graph partitions its vertex set into $k$ independent sets whose sizes differ by at most one; the least such $k$ is the equitable chromatic number $\chie(G)$. Every known bound on $\chie$ valid for all graphs, beginning with the Hajnal–Szemerédi
theorem, is linear in the maximum degree $\Delta$, and the
star $K_{1,\Delta}$, for which $\chie=\ceil{\Delta/2}+1$, shows that no general bound below $\Delta/2$ exists. We prove that this obstruction is a shortage of vertices rather than an effect of the degree: every graph with $|V(G)|\ge3\chi(G)\Delta$ satisfies $\chie(G)=O\bigl(\chi(G)^{3/2}\sqrt{\Delta/\ln\Delta}\bigr)$ throughout the range $\chi(G)\le(\Delta/\ln\Delta)^{1/3}$, so that for graphs of large order the degree enters only through $\sqrt{\Delta/\ln\Delta}$, with the chromatic number governing the rest. For each fixed $\ell$, $\ell$-colorable graphs of sufficiently large order satisfy $\chie\le\bigl(2\sqrt2\,\ell\sqrt{\ell-1}+o(1)\bigr)\sqrt{\Delta/\ln\Delta}$, while a probabilistic construction supplies graphs of arbitrarily large order, bipartite when $\ell=2$, with $\chie\ge\tfrac13\sqrt{(\ell-1)\Delta/\ln\Delta}$: the order of growth $\Theta\bigl(\sqrt{\Delta/\ln\Delta}\bigr)$ is exact for every fixed chromatic number, and the extremal constant is determined up to a factor $O(\chi(G))$. All upper bounds are constructive, and a prescribed-anchor variant of the construction produces equitable colorings of bipartite graphs with $O(\sqrt\Delta)$ colors in optimal linear time.
Read the full abstract ▾
General Mathematics
A Complex Structure on $S^2\times S^4$
Shengtao Guo, Ethan X. Fang and Junwei Lu
We show that $S^2\times S^4$ admits a complex structure. Starting from a modular family of complex two-
tori associated with the $(3,4,\infty)$ triangle group and the compactification constructed in [Alpöge 2026], we replace the period
lattice by its unique monodromy-invariant index-two superlattice and compactify the resulting family. In the integral Mayer–Vietoris calculation, a primitive local class whose double is the class of a cusp component and the unique nonzero torsion class contributed by the multiplicity-four fibre restrict to the same class of order two on the common boundary. We then prove that the resulting compact complex threefold is diffeomorphic to $S^2\times S^4$. The proof is discovered by the Odin Automatic AI Research
Agent.
Read the full abstract ▾
General Mathematics
Optimal Practice Allocation Under Learning Saturation
Shrisha Rao
A saying attributed to Bruce Lee unfavorably contrasts a martial artist who has practiced ten thousand kicks once each with another who has practiced a single kick ten thousand times. We read the saying as implicitly raising a question about how to allocate a fixed practice budget among several skills, and we show that the answer is governed by two ingredients: the shape of the learning curve that converts practice into skill, and the rule by which separate skills are aggregated into overall effectiveness. Neither ingredient alone settles the matter. Our central result reduces the multivariable allocation problem to the maximization of a single scalar efficiency function \(\eff(x)=f(x)^{p}/x\); under a simple uniqueness and divisibility condition, every optimal practice schedule is balanced, dividing the budget equally among a definite number of skills. The optimal number of skills is then determined by a transparent criterion equating the elasticity of the learning curve to the reciprocal of the aggregation parameter. Hard-saturation models, heterogeneous learning rates, a sharp specialization threshold, and a genuinely intermediate optimal repertoire all follow as consequences.
Read the full abstract ▾
Combinatorics · Cross-listed from physics.chem-ph
Enumerating Chemical Structures, Stereoisomers, and Stereogenic Units with Analytic Combinatorics
Casper Asbjørn Eriksen and Daniel Merkle
The enumeration of chemical structures traditionally relies on graph- and group-theoretic techniques, including Pólya theory, in order to account for stereochemical
symmetries. These methods require bespoke derivations and methods for each molecular family of interest, and quickly become very intricate for nontrivial classes. In this work, we demonstrate that analytic combinatorics provides a unifying, highly extensible, and relatively simple framework for enumeration problems. Using the symbolic method, we show that classical counting problems, such as the enumeration of acyclic alkanes and other hydrocarbon families, can be naturally solved via concise combinatorial specifications of the class of interest. We first demonstrate the simplicity of this approach by replicating existing results in this framework, requiring significantly less work than previously necessary, and then extend these ideas to more complex problems, counting broader classes of molecules accounting for both tetrahedral and E/Z stereoisomerism, counting the distribution of stereogenic units, and enumerating achiral and meso compounds. All results are made reproducible through CombOL, our open-source software package which automates the translation of combinatorial specifications into generating functions using the symbolic method, and performs both univariate and multivariate enumeration.
Read the full abstract ▾
Probability · Cross-listed from physics.data-an
A Probability Model for Pentagonal Prism Dice Rolls
Paul R. Hurst and J. Naleo Hyde
In the realm of probability theory and game design, the study of dice probabilities plays a crucial role. The featured dice are usually fair, so their probabilities can be predicted without rolling the dice. Pentagonal prismatic dice are not fair. Hence, the probabilities are more complicated. Our mathematical model is naturally derived from both the
geometric properties of the dice and empirical evidence. Dice of varying sizes but with constant volume were designed. Using a 3D printer with 100 percent infill, the dice were printed and prepared. A machine that simulates dropping dice through a dice tower onto a hard surface was used to obtain about 41,000 results. From these data, a statistical model was constructed that gives probabilities of dice with varying height-to-radius ratios. The formula for the model is based on the centroid solid angle, but with two adjustment parameters due to varying energy and other requirements to transition between different resting aspects. Within the range of height-to-radius ratios tested, the data are within reasonable statistical error of the model.
Read the full abstract ▾
Analysis of PDEs
Analysis validation of a new continuum model for the evolution of grain boundaries in polycrystalline materials
Peicheng Zhu, Xiaoxue Qin and Yang Xiang
To describe the
evolution of grain boundaries based on the underlying microscopic mechanisms of line defects (disconnections) and the integrated effects of a diverse range of thermodynamic driving forces, Zhang, et al. in 2017 formulated a continuum equation. We prove the global-in-time existence, uniqueness, and regularity of the weak solution to an initial-boundary value problem for this model. The existence, uniqueness of the stationary solution are also established. Finally, we investigate the large-time behavior of the weak solution of the
evolution problem, and show that the solution converges to the stationary solution in a suitable sense. Numerical simulations are carried out to validate the analysis results. The main difficulties in the proof of main
theorems are due to a non-local term with singularity, a non-smooth coefficient of the highest derivative associated with the gradient of the unknown, and the special form of free energy which is not uniformly bounded from below. The key ingredients in the proof are the energy method, an estimate for a singular integral of the
Hilbert type,
Fourier transform of
Hilbert transformations, and an estimate with a weight, for time-derivative of the unknown.
Read the full abstract ▾
Numerical Analysis
Minimizing the Arithmetic and Communication Complexity of Jacobi's Method for Eigenvalues and Singular Values: Part Two – Parallel Algorithms
James Demmel, Hengrui Luo, Ryan Schneider et al. (+1 more)
This paper presents several parallel versions of Jacobi's method for the symmetric
eigenvalue problem and the SVD. A continuation of [Demmel, Luo, Schneider, & Wang 2025], we develop parallel Jacobi
algorithms whose arithmetic cost is optimal and whose bandwidth or latency can match the corresponding lower bounds of parallel
matrix multiplication. Our focus is a standard distributed-
memory setting with variable processor layouts, including both 2D and 2.5D processor grids. In the 2D case, we demonstrate that a standard implementation of parallel Jacobi achieves a perfect speedup in arithmetic cost – i.e., complexity $O(n^3/P)$ when done with $P$ processors – while hitting the 2D
matrix-multiplication lower bound for bandwidth and (nearly) the lower bound for latency. By employing a 2.5D processor grid and leveraging 2.5D
matrix multiplication, equivalently by increasing the
memory per processor, we demonstrate that parallel Jacobi can achieve even lower bandwidth/latency, though we also prove that these costs cannot simultaneously match the best-known bounds for parallel
matrix multiplication in any Jacobi
algorithm. Finally, we extend our results to one-sided Jacobi SVD.
Read the full abstract ▾
All authors James Demmel, Hengrui Luo, Ryan Schneider, Yifu Wang
Statistics Theory · Cross-listed from stat.ML
The information geometry of product-reference discrete diffusion: Interaction growth complexity and optimal scheduling
Martin J. Wainwright
We study a class of product-reference
diffusion algorithms for sampling from a discrete distribution. We show that their sampling performance can be characterized using a path-based measure of data geometry that we call the interaction growth complexity (IGC). We show that a bivariate IGC kernel gives an exact representation of both the KL discretization error and a simple one-step upper bound. The simpler univariate IGC density can be used to study the effect of stepsize choices on the iteration complexity required to obtain $\epsilon$-accurate samples in KL divergence. Samplers that traverse the path with equi-spaced steps in log-squared-reliability-odds have performance that depends on the aggregate IGC mass, whereas refined choices of stepsizes have a lower complexity depending on a square-root functional. In the fine-grid limit, both of these characterizations become sharp. We also allow general product reference distributions and show that the reference law can substantially reshape the IGC profile and the resulting sampling complexity; in particular, references far from both the uniform and the data marginals can yield dimension-dependent improvements. Finally, the aggregate IGC mass admits bounds in terms of total correlation and dual total correlation, thereby connecting the pathwise geometry to classical measures of multivariate dependence.
Read the full abstract ▾
Mathematical Physics · Cross-listed from hep-th
Action-angle variables and phase space formulation of Hermitian matrix models
Arghya Chattopadhyay
We develop a phase space description of large $N$ Hermitian one
matrix models directly from the recursions satisfied by the orthogonal
polynomials. In the one-cut phase, the recursion
lattice naturally gives rise to a semiclassical action-angle pair, which can be mapped canonically to
eigenvalue and momentum variables. We show that the resulting momentum profile is determined by the density of zeros of the orthogonal
polynomials, and that the same phase space structure is reproduced from the Wigner transform of the Christoffel-Darboux projector and from the planar spectral curve. The Gaussian model provides a simple consistency check of the proposal. We then extend the construction to the symmetric quartic two-cut phase, where a period-two Jacobi recursion produces two Bloch bands and two disconnected phase space components with actions given by the partial 't Hooft couplings. Finally, we outline the finite-gap generalization appropriate to multicut phases.
Read the full abstract ▾
Numerical Analysis
A GPU-Accelerated Blocked Adaptive Randomized Range Finder Based on an Implicit Householder QR Decomposition
Carolin Penke and Andreas Herten
Low-rank methods can reduce the
memory and computational requirements of deep neural network training in approaches such as GaLore. Randomized range finders offer an attractive alternative to singular value decompositions, particularly when the required rank is determined adaptively from a prescribed approximation tolerance. We introduce a blocked adaptive randomized range finder based on a Householder QR decomposition and an optimized hybrid CPU–GPU implementation. Numerical experiments show that it preserves orthogonality and approximation accuracy in regimes where block Gram–Schmidt without reorthogonalization becomes unstable. The blocked formulation exposes
matrix–
matrix operations and enables overlap of CPU panel factorization with GPU updates. On an NVIDIA GH200, the overlapped implementation reduces the runtime for the largest tested
matrix from 9.91 s on the CPU to 0.407 s. The method provides a stable and efficient building block for low-rank approximation on heterogeneous systems with applications in computational science and engineering.
Read the full abstract ▾
Information Theory
Authentication over Arbitrarily Varying Channels with Causal Adversaries
Mayank Bakshi, Vinod M. Prabhakaran, Bikash Kumar Dey et al. (+1 more)
We study authentication over a discrete memoryless arbitrarily varying channel (AVC) in which the adversary selects the channel state causally based on past channel outputs. We prove that the authentication capacity is positive exactly when the channel is not distribution-overwritable under
stochastic encoding, and not I-overwritable under deterministic encoding. In the
stochastic case, whenever the authentication capacity is positive, it coincides with the no-adversary Shannon capacity. Both converses follow from a novel wait-and-overwrite attack: the adversary tracks the no-adversary posterior over the message via the posterior guessing probability, and once it concentrates past a threshold, it samples a guess and a decoy from the posterior and overwrites the channel to mimic a no-adversary transmission of the decoy. The positivity results are obtained by constructing positive-rate codes with controlled overlap between codewords, together with a martingale concentration argument that handles adaptive
adversarial strategies. For
stochastic encoding, the full-capacity achievability further combines a capacity-achieving channel code with an authentication tag. These characterizations separate the causal
stochastic-code and causal deterministic-code settings from each other and from the oblivious-adversary setting studied by Kosut and Kliewer.
Read the full abstract ▾
All authors Mayank Bakshi, Vinod M. Prabhakaran, Bikash Kumar Dey, Oliver Kosut
Combinatorics
Braess' Paradox in Uniform Affine Grid Networks
Andy Lu and Steven J. Miller
Braess' Paradox is the phenomenon in which adding an edge to a congestion network increases total travel time. We study the paradox in directed rectangular grids where every edge shares the latency function $\ell(x)=ax+b$ and an added chord has latency $\ell_{*}(x) = cx+d$, where $a > 0$ and $b,c,d \ge 0$. Using an analogy with electrical networks, we bound the change in total travel time. We then give a necessary and sufficient condition for a chord to induce the paradox for some choice of nonnegative coefficients and compute the exact proportion of such chords in all grids with dimensions at most $100$. Such chords are scarce, and the fraction is maximized near an aspect ratio of $2:1$. We then improve the established $4/3$ upper bound on the Braess Ratio to one depending only on the grid dimensions, approaching $1.207$ on squares and $4/3$ on thin grids. Finally, we prove any ratio-maximizing chord must have zero latency.
Read the full abstract ▾
Mathematical Physics
Pseudorandomness and Diffraction
David Damanik and Nicolae Strungaru
Pseudorandom structures are structures that behave like random ones, without necessarily being random themselves. It is a prominent, and evidently very difficult,
conjecture that $$ V(n) = \lambda \cos \Big( 2 \pi \Big( x_1 + n x_2 + \frac{n(n-1)}{2} \alpha \Big) \Big) $$ is pseudorandom from a Schrödinger operator perspective in that the Schrödinger operator in $\ell^2(\mathbb{Z})$ with potential $V$ displays Anderson localization, that is, pure point spectrum with exponentially decaying eigenfunctions for almost all parameter values — the same spectral features as those produced by random potentials. We show that $V$ is pseudorandom in terms of its diffraction properties, that is, the associated diffraction measure is purely absolutely continuous for all $\lambda \not= 0$, all irrational $\alpha$, and all $x_1,x_2$ — which is the case as well for the random case. Our result gives further evidence for the
conjecture in the Schrödinger case and it elucidates the apparent dual behavior of Schrödinger spectral measures and diffraction measures.
Read the full abstract ▾
Mathematical Physics · Cross-listed from quant-ph
Exact Haar Statistics of Planar $k$-Purity in Multipartite Quantum Systems
Kourosh Mirsohi
Planar $k$-uniform states have maximally mixed reductions on every $k$-site interval of a ring. We introduce planar $k$-purity—the mean purity of those intervals—as a faithful cost function for this simultaneous constraint. For a Haar-random pure state of $n$ parties with local dimension $p$, the joint purity of two intervals depends only on their overlap. An exhaustive four-replica calculation therefore yields the complete cyclic covariance kernel and a closed variance for every $1\le k\le\lfloor n/2\rfloor$. In the balanced
qubit case, $k=\lfloor n/2\rfloor$ and $N=2^n$, the variance is asymptotic to $20/(3nN^2)$ for even $n$ and $6/(nN^2)$ for odd $n$. A site-factorized permutation representation gives all raw moments and permits exact finite-sum evaluation of the skewness. Fixed-seed simulations validate nonbalanced
qubit and qutrit cases, while balanced-
qubit simulations through $n=10$ validate the parity formulas and finite-size skewness. Balanced planar and absolute balanced purity have the same Haar mean but different fluctuations; the planar variance is approximately $2.83$ times larger at $n=10$. Thus subsystem incidence, although invisible to every one-cut marginal distribution, controls the collective fluctuations of geometrically related cuts. Together with universal attainability and a linear number of interval constraints at balance, this provides a geometry-aware
benchmark for multipartite
entanglement beyond AME existence regimes.
Read the full abstract ▾
Information Theory · Cross-listed from cs.LG
SemKV: Semantic Mixed-Precision KV Cache Quantization Guided by the Quality Cliff for Long-Context LLM Inference
Daeha Lee, Do-Hyung Kim and Jae-Hong Kim
The key-value (KV) cache is the dominant
memory bottleneck of long-context large
language model (LLM) inference, growing linearly with context length. We show that uniform KV quantization on a fractional-bit grid does not degrade gracefully: under a prespecified multi-seed statistical protocol, Llama-3.1-8B-Instruct with an affine quantizer is statistically indistinguishable from FP16 KV down to 2.322 code bits/value and collapses at 2.0 bits - a quality cliff in (2.0, 2.322] that reappears in generation-time quantization and multi-turn dialogue and transfers to Mistral-7B. The cliff reframes importance-aware mixed precision: above it, eight model-internal importance indicators are statistically interchangeable, so the benefit of mixing is grid interpolation, reaching average precisions uniform quantization cannot realize. SemKV preserves every
token, ranks
tokens by a model-internal score, and assigns two adjacent above-cliff precisions, achieving a measured 6.0x storage reduction with no statistically detectable quality difference from full KV (n=900, three seeds), and outperforming FP16
token pruning granted a 1.5x larger
memory budget. Replacing the affine base with a distortion-optimized quantizer (TurboQuant-MSE) lowers the cliff in every protocol tested, raising the no-detectable-loss operating point to 7.9x. The recipe: measure the cliff for the target deployment setting, then interpolate above it.
Read the full abstract ▾
Functional Analysis
Transfinite Schreier families and cardinal invariants
Kevin Beanland and Christian Rosendal
We study the dependence of the transfinite Schreier hierarchy on the choice of fundamental sequences for the countable limit ordinals. With each Schreier family we associate an interval endpoint function. We prove that the bounding number is equal to $\omega_1$ exactly when the fundamental sequences may be chosen so that these endpoint functions form an unbounded family in the eventual domination order. Equivalently, the hierarchy then satisfies the tail-covering property isolated by Shiliaev, or every infinite compact interval family has infinite intersection with some member of the hierarchy. We also prove that the dominating number is equal to $\omega_1$ exactly when the fundamental sequences may be chosen so that every compact family of finite subsets of $\{2,3,\ldots\}$ is contained in one Schreier family. The latter equivalence combines Fremlin's cofinality
theorem for compact subsets of the rationals with an absorption construction for compact families.
Read the full abstract ▾
Optimization and Control
Differentiating Minimal-Norm Solutions to Parametric Optimization Problems
Baptiste Plaquevent-Jourdain, Jalal Fadili and Antonio Silveti-Falls
Differentiating through parametric optimization problems is central to bilevel programming and meta-learning, often accomplished using approximate implicit differentiation. The implicit function
theorem requires inverting a partial Jacobian of the optimality condition, which fails when there are many solutions. Nonetheless, in such cases it is possible to relax invertibility to a strictly weaker uniform range condition, under which it is shown that the minimal-norm solution mapping admits generalized derivatives by using a limiting Tikhonov regularization argument and conservative set-valued field theory. With additional control on the
eigenvalues of the generalized Hessians, a pseudoinverse formula is justified. This is established for a class of smooth convex objectives and extended to nonsmooth composite problems. These assumptions are verified for Least-Squares, Huber regression and LASSO. The resulting extension of nonsmooth implicit differentiation to ill-posed settings is examined experimentally on data poisoning and data hypercleaning problems.
Read the full abstract ▾
Information Theory · Cross-listed from quant-ph
Rényi Entanglement of Purification Is Non-additive
Amir-Reza Negari and Zahra Baghali Khanian
Entanglement of purification is a fundamental measure of total correlations whose additivity remains unresolved. We study its additivity for classical states on two
qubits at different Rényi orders. For every $\alpha\in[0,1)$, we prove nonadditivity within this family, witnessed by two copies of a single state. We first solve the one-copy optimization exactly for the entire family at every Rényi order. We then restrict the two-copy optimization to a natural finite set of purifications and exhibit one whose
entropy is strictly below the product value. In contrast, for $\alpha\in[2,\infty]$ we prove additivity under tensor products within this family. The interval $\alpha\in[1,2)$, including the von Neumann case $\alpha=1$, remains open, and we
conjecture additivity there throughout the same family.
Read the full abstract ▾