Numerical Analysis · Cross-listed from cs.DC
The 2M Multiplication Algorithm for Complex Matrices
Peter Caday
Complex
matrix multiplication is typically computed using 4 real
matrix multiplications (GEMMs) of the same size. The well-known 3M multiplication
algorithm reduces this cost to 3 real GEMMs, together with quadratic time pre- and post-processing steps. In this paper, we reduce 3M to 2M for
matrices with integer real and imaginary parts, performing complex GEMM with only 2 real GEMMs of the same size, along with quadratic time pre- and post-processing. For floating-point
matrices, 2M multiplication combines naturally with the Ozaki-II scheme, yielding a practical, high-performance
algorithm for computing a complex floating-point GEMM in roughly twice the time of a real GEMM of the same size. As corollaries, we derive new
algorithms for symmetric rank-$k$ updates (SYRK/HERK) that internally use full rectangular GEMMs.
Read the full abstract ▾
Geometric Topology
The unknotting number of 11n102 is 2
Tye Lidman
We prove that the unknotting number of the
knot 11n102 is 2.
Algebraic Geometry
Autoequivalences of Derived Categories of Moduli Spaces of Vector Bundles
Haotian Zuo
Let \(C\) be a smooth projective curve over an algebraically closed field of characteristic zero. For the
moduli space \(N(r,L)\) of stable vector bundles on \(C\) of rank \(r\) with fixed determinant \(L\), we study the group of exact autoequivalences of its bounded derived category. Combining the Bondal–Orlov reconstruction
theorem with the descriptions of \(\operatorname{Aut}(N(r,L))\) due to Kouvidakis–Pantev and Newstead, we obtain an explicit description of \(\operatorname{Aut}\mathrm{D^b}(N(r,L))\). We also construct extension correspondences between
moduli spaces of vector bundles of different ranks and use them to define natural
Fourier–Mukai type exact functors between their bounded derived categories.
Read the full abstract ▾
Combinatorics · Cross-listed from cs.GT
The Geometry of Cooperative Game Solutions: Stratified Egalitarian Shapley Values
Frank M. V. Feys
The space L of linear value maps on a finite-player cooperative game G^N is finite-dimensional, and admits a canonical inner product induced by the Harsanyi-dividend decomposition of G^N. We show that this inner product is intrinsic: the same value arises from any orthonormal basis of G^N with respect to the Harsanyi inner product. Within this geometry, the subspace L^{ESL} of efficient, symmetric, linear value maps admits a clean structure
theorem. The induced orthogonal stratification of L by coalition size yields a canonical linear isomorphism L^{ESL} = R^{n-1}, under which every efficient symmetric linear value map decomposes uniquely into n-1 stratified epsilons, one per coalition size. The classical egalitarian Shapley family of Joosten (1996) is precisely the diagonal slice of this R^{n-1}. The orthogonal projection of any Psi in L^{ESL} onto this diagonal yields an optimal parameter eps*(Psi) equal to the weighted mean of the stratified epsilons under an explicit probability distribution {w_a} over coalition sizes, and the goodness-of-fit R^2(Psi) equals one minus the relative weighted variance of those epsilons. The framework is a literal regression-statistics analogue of the coefficient of determination. At n=4 it produces a clean three-way classification of the standard alternatives to the Shapley value: the Banzhaf value is nearly orthogonal to the egalitarian Shapley axis (R^2 ~ 1%); the equal-surplus-division value is moderately aligned (R^2 ~ 38%); the solidarity value is almost entirely aligned (R^2 ~ 99.6%). Asymptotically R^2(ESD) -> 1, R^2(So) -> 1, and R^2(Bz) -> 1/2, the last reflecting a structural identity between the efficiency defect and the egalitarian-Shapley deviation of the Banzhaf value at every coalition size.
Read the full abstract ▾
Combinatorics · Cross-listed from cs.GT
An Axiomatic Theory of Tie-Breaking: Impossibility, Characterization, and Decomposition
Frank M. V. Feys
We develop an abstract axiomatic theory of tie-breaking. A tie-breaking input consists of a finite set N of players, a weak order on N representing the standings to be refined, and an auxiliary information item drawn from a set on which the symmetric group Sym(N) acts. Within this minimal framework we prove three
theorems. First, no tie-breaking rule producing a strict linear order can be anonymous, provided the input space contains even one intrinsically symmetric situation, a condition met in essentially every realistic application. Second, when we allow the rule to output a partition of N (rather than a strict ranking), there is a unique rule satisfying two natural axioms: it is the partition of N into orbits of the joint stabilizer of the input. Third, every reasonable strict tie-breaking rule decomposes uniquely as the canonical orbit partition followed by an arbitrary completion. The decomposition makes precise the informal observation that real tie-breaking systems are honest until forced to be arbitrary. The framework is broad enough to capture chess tournament tie-breakers, sports league regulations, voting tie-breakers, tie-breaking among symmetric players in cooperative games, and ranking by network centrality measures, all within a single uniform formalism.
Read the full abstract ▾
Information Theory · Cross-listed from cs.SI
Conditional Entropy of Heat Diffusion on Temporal Networks
Samuel Koovely and Alexandre Bovet
Diffusion-based information-theoretic approaches provide new theoretical and practical tools to study complex networks. So far, they have not been generalized to temporal networks. In this work, we show that common entropic measures based on modeling
diffusion on graphs, such as the
entropy rate and the spectral
entropy, do not generalize straightforwardly to temporal networks due to the process's non-stationarity and temporal asymmetries. Instead, we propose the conditional
entropy of heat
diffusion as an entropic measure for continuous-time temporal networks and study its properties. We show that this quantity is monotone in time, yielding an information-theoretic analog of the second law of thermodynamics for inhomogeneous
diffusion on temporal networks. We provide an upper bound and suggest a lower bound on its
evolution and explain how discrepancies from it arise due to asymmetric temporal paths. We then introduce a local version of conditional
entropy, designed to probe
diffusion over finite temporal windows, and show that it provides an informative signal for change-point detection in continuous-time temporal networks. We evaluate the proposed methodology on synthetic
benchmarks, including comparative experiments with existing nonparametric baselines in the snapshot setting, and then apply it to a real-world temporal contact network. Finally, we show how to use detected change points to guide community detection on targeted sub-intervals, improving the quality and interpretability of the clustering results.
Read the full abstract ▾
Number Theory
On the Natural Density of Monic Integer Polynomials with Roots in a Fixed Number Field
Amirali Fatehizadeh
In this article, we investigate the statistical distribution and asymptotic behavior of the family of monic integer
polynomials of degree $n$ having at least one root in a fixed number field $K$. Although the framework of thin sets implies that the natural density of this family in the parameter space of bounded height is zero, explicitly quantifying this vanishing rate is a central challenge in arithmetic statistics. Employing a hybrid approach that integrates the Mahler measure, Dirichlet's unit
theorem, and residue analysis of the Dedekind
zeta function, we demonstrate that the rate of convergence of this density to zero is strictly dependent on the degree $n$. Specifically, we prove that the degrees of the factors induce a phase transition in the asymptotic behavior; for
polynomials of degree $n = 2$, the decay rate is bounded by $O(H^{-1} \log H)$, whereas for higher degrees, the asymptotic behavior is dominated by the contribution of rational roots, yielding a bound of $O(H^{-1})$. Beyond deriving these asymptotic estimates, we apply principles from the geometry of numbers to establish explicit combinatorial bounds for counting both the reducible and irreducible components of these
polynomials. These explicit bounds provide practical tools for computational evaluations within this domain.
Read the full abstract ▾
Optimization and Control · Cross-listed from physics.bio-ph
Universal Extremum Seeking Mechanism for Lift Variation in Soaring Birds Flight: A New Paradigm in Computational Physics and Biology
Simone Martini, Dipesh Kunwar and Sameh A. Eisa
In this letter, we reveal a universal, very simple extremum seeking natural feedback law and mechanism that governs, adapts, and generates in real-time, optimized lift variations for successful energy gain flight in presence of wind shear. The introduced law/mechanism, which is computationally minimal and needs only sensory information of the wind or local energy rate (i.e., model-free and data-driven) is able to characterize and replicate dynamic soaring optimized flight physics of windward climb in real-time for a variety of soaring birds species, namely wandering albatross, black-browed albatross and grey-headed albatross. We confirm the effectiveness of this new simple, real-time law by successful comparisons with sophisticated non-real-time optimal control solver and reported biological data. Our results establish the proposed mechanism as a new paradigm in soaring flight physics. That is, our results substantially advance the computational physics/biology aspects of the problem while providing a biologically plausible theory for avian soaring behavior.
Read the full abstract ▾
General Mathematics
A Maxwell Quadratic-Form Representation of the Parallel-Plate Casimir Trace from Codimension-Three Riesz Reduction
Irshadullah Khan and Bilal Khan
We formulate a Maxwell version of the codimension-three Riesz/Gaussian quadratic-form representation for perfectly conducting parallel plates. This paper is the Maxwell follow-up to the scalar codimension-three Riesz/Gaussian representation
theorem presented earlier in arXiv:2605.06693(2026): the same transverse Riesz reduction and prescribed-covariance quadratic-form mechanism are carried over here to the physical parallel-plate Maxwell operator. The construction is carried out in finite lateral volume $\Omega_{L,a}=T_L^2\times[0,a]$, using the physical electric-field
Hilbert space of divergence-free fields satisfying the perfect-conductor tangential condition $n\times E=0$, with the static normal zero mode removed. The Maxwell curl-curl operator is defined by its closed quadratic form, and an explicit
Fourier-domain analysis proves the finite-volume spectral gap, compact resolvent, and heat-trace admissibility needed for the
stochastic construction. For this reduced Maxwell operator $\mathcal L_{\mathrm{Mx}}$, the codimension-three Riesz integral gives the transversely reduced Riesz mediator $g\mathcal L_{\mathrm{Mx}}^{-1}$. A prescribed heat-regularized Gaussian source with covariance $(\hbar c/g)\mathcal L_{\mathrm{Mx}}^{3/2}e^{-\tau\mathcal L_{\mathrm{Mx}}}$ then has expected quadratic Green energy equal to the heat-regularized physical Maxwell trace. The finite-volume trace is shown to be spectrally equivalent to a scalar Dirichlet channel plus a scalar Neumann channel with its constant zero mode removed. Under the standard parallel-plate interaction finite-part prescription, the large-area energy density is $$ -\frac{\pi^2\hbar c}{720a^3}. $$ The result is a representation
theorem for the Maxwell parallel-plate trace under a prescribed covariance in the flat-plate geometry considered here.
Read the full abstract ▾
General Mathematics
The Arithmetic of Chess Piece Strength on the n x n Board
Frank M. V. Feys
On the n x n chessboard, the move totals of distinct pieces satisfy a small number of striking arithmetic identities. The total diagonal mobility of the bishop and the total 8-neighbor mobility of the king are exactly proportional, with constant n/12, valid for every n. Among nontrivial boards, the strengths of two distinct pieces drawn from a natural thirteen-piece alphabet coincide only for n in {6, 8, 12}. We define the strength of a piece P on the n x n board as the probability that a uniformly random ordered pair of distinct squares forms a legal P-move on the empty board, and prove four main results. (1) An asymptotic dichotomy classifies pieces into riders (Theta(1/n) strength) and leapers (Theta(1/n^2) strength), with explicit rational leading constants. (2) A stable-ordering
theorem identifies the threshold n* = 24 beyond which the strength order becomes fixed, with a complete tabulation of every transition for 4 <= n <= 24. (3) A complete classification of strength coincidences shows they occur only at the three magic boards n in {6, 8, 12}, accompanied by the closed-form identity str(K) - str(N) = 12/(n^2(n+1)), the unique near-coincidence between bishop and knight at n = 10 (gap 0.0606%), and the bishop-king proportionality str(B)/str(K) = n/12. (4) A Strength
Algebra Theorem expresses the strength of any compound army as a linear functional of a four-dimensional atomic vector, and confines strength coincidences between distinct single pieces to the three magic boards. As immediate consequences we obtain explicit strength-preserving single-piece substitution rules on each magic board, and a characterization of the 8 x 8 board as the unique nontrivial board on which the rook attains a strength matched by another piece in the alphabet (the archbishop).
Read the full abstract ▾
General Mathematics
A Limit-Free Algebraic-Geometric Construction of Derivatives for Elementary Functions
Davit Kapanadze
This paper continues the author's previous work on a limit-free algebraic-
geometric construction of the derivative in the class of
polynomial functions and extends the proposed framework to elementary functions. Derivatives of rational power, exponential, logarithmic, trigonometric, and inverse trigonometric functions are constructed through the
geometric interpretation of the tangent line, inverse
symmetry, and local linear structure, without treating the limit as the initial defining mechanism. Within the proposed approach, the derivative is introduced from the outset as a functional correspondence assigning to each point the slope coefficient of the tangent line. The paper demonstrates that the classical differentiation formulas arise naturally from interconnected
geometric and algebraic structures and are subsequently consistent with standard limit-based analysis. From a methodological perspective, the study proposes the logical sequence: Tangent, Local Linear Structure, Limit formalisation. Thus, the paper presents a conceptual bridge between
geometric intuition, algebraic construction, and classical differential calculus.
Read the full abstract ▾
Combinatorics · Cross-listed from cs.FL
On the transversals of Latin squares generated by nonlinear bipermutive cellular automata
Alberto Dennunzio, Maximilien Gadouleau and Luca Mariot
In this short paper, we begin to investigate the conditions under which a generic Bipermutive Cellular Automaton (BCA) with no-boundary conditions of diameter $d$ generates a Latin square of order $N=2^{d-1}$ admitting an orthogonal mate, without relying on the linearity of the local rule. Since an orthogonal mate exists if and only if the Latin square can be partitioned into $N$ disjoint transversals, we start by characterizing the subclass of BCA whose Latin squares have a transversal on the main diagonal. In particular, we prove that the main diagonal forms a transversal if and only if the generating function of the bipermutive local rule induces an invertible CA with periodic boundary conditions on a configuration of size $d-1$. We then perform exhaustive search experiments, showing that $d=6$ is the smallest diameter for which there exist nonlinear bipermutive CA that generate Latin squares with a transversal on the main diagonal.
Read the full abstract ▾
Analysis of PDEs · Cross-listed from cs.LG
Multi-Headed Transformer Architectures as Time-dependent Wasserstein Gradient Flows
Alex Massucco, Leonardo Del Grande, Marcello Carioni et al. (+2 more)
In recent years,
transformer architectures have revolutionized the field of
language processing, opening the door to previously unforeseen possibilities. However, from a theoretical point of view, the mathematical models proposed in the literature often lack direct contact with the actual architectures and depend on strong simplifying assumptions. In this paper, we reduce this gap by modelling the data flow in multi-headed
transformer architectures as time-dependent gradient flows for a suitable interaction energy capturing the design of the
attention mechanism. The explicit dependence on time allows us to consider different weights for each head and for each layer, without imposing constraints on the initialization method. Moreover, we prove that, under a suitable integrability assumption on the
evolution of the weights, each element of the $\omega$-limit set of the gradient flows is a stationary point of the interaction energy at a limiting weight distribution. Finally, we analyse the stability of the gradient flows considering perturbations of both the initial data and the weights. Specifically, on the one hand, we study the robustness of the proposed models with respect to noisy inputs, establishing a continuous dependence of the gradient flows on the initial data and uniqueness of the flows. On the other hand, we prove the $\Gamma$-convergence of the perturbed interaction energy to the unperturbed one, leading to the convergence of the corresponding gradient flows. We complement these theoretical results with numerical experiments that confirm the predicted energy-dissipation identity and clarify the asymptotic behavior of the dynamics in both the autonomous-like (Ornstein–Uhlenbeck) and the genuinely non-autonomous (oscillating-weights) regimes.
Read the full abstract ▾
All authors Alex Massucco, Leonardo Del Grande, Marcello Carioni, Christoph Brune, Carola-Bibiane Schönlieb
Combinatorics
Brick Wall Excursions: Combinatorial Interpretation of Random Flight Moments
Sergey Kirgizov, Khaydar Nurligareev and Michael Wallner
We study the expected distance of short uniform random walks in arbitrary dimensions with unit steps in random directions. It is known that for dimensions $d=2$ and $d=4$, all the moments of an $m$-step walk are integer. While for $d=2$, the $n$th moment can be interpreted as the number of abelian squares of length $2n$ over an alphabet with $m$ letters, for $d=4$ no interpretation was known. The goal of this paper is to provide such an interpretation, both for $d=2$ and $d=4$, in terms of $2n$-step
lattice paths in dimension $m-1$. Our construction relies on a bijection between Dyck paths with a prescribed number of peaks and words of a certain type. In addition, this bijection allows us to derive closed formulas for the number of
lattice paths provided with certain statistics.
Read the full abstract ▾
Information Theory
Covert Multi-bit LLM Watermarking: An Information Theory and Coding Approach
Sidong Guo, Tyler Kann, Teodora Baluta et al. (+1 more)
We study the problem of multi-bit watermarking for non-autoregressive large
language models (LLMs). We introduce an information-theoretic model inspired by
diffusion language models (DLM), in which the encoder has limited non-causal access to
token distributions within each
token block. This formulation enables an information-theoretic characterization of the non-causal watermarking capacity, in which knowledge of LLM cover statistics is leveraged to enable a multi-bit covert
embedding. We study the information-theoretic limits of the model by combining Gelfand–Pinsker and channel synthesis coding techniques and obtain an exact characterization of the capacity. The
embedding strategy is further optimized across blocks using a constrained Markov decision process (CMDP) and we develop an explicit
algorithm based on polar codes following the information-theoretic principles. We simulate the error performance on LLaDA, and provide empirical total variation (TV) analysis as a function of key randomness.
Read the full abstract ▾
All authors Sidong Guo, Tyler Kann, Teodora Baluta, Matthieu R. Bloch
Combinatorics
On the geodesic midrange crossing constant
Saba Lepsveridze and Oriol Solé-Pi
We introduce an analytic framework for studying the number of crossings in planar straight-line and spherical geodesic drawings; we begin by analyzing drawings in a continuous setting and then pass to finite graphs. We use this approach to derive multiple results. First, we show that the midrange crossing constant is strictly smaller than $8/(9\pi^2)$, improving the best known upper bound of Pach and Tóth from nearly thirty years ago. Second, we prove sharp lower bounds for some restricted drawing classes. For spherical geodesic drawings with uniformly distributed vertices, we determine the minimum number of crossings at every edge density. We also prove lower bounds for planar straight line drawings in compact convex domains with uniform vertex sets. Consequently, we determine the restricted midrange crossing constant to be $8/(9\pi^2)$ in both of these settings. Finally, for two-layer bipartite drawings, with straight edges between two parallel lines, we determine the midrange crossing constant to be $2/3$.
Read the full abstract ▾
Probability · Cross-listed from q-bio.PE
Branching under First-Passage Resetting
Aanjaneya Kumar and James Holehouse
Many biological processes, from
cell division to viral lysis, are triggered when an internal
stochastic variable reaches a threshold. Here we introduce Branching under First-Passage Resetting, a general framework in which replication events arise endogenously from first-passage dynamics rather than from externally imposed lifetime clocks. We show that the resulting population dynamics obey an exact renewal equation linking single-trajectory first-passage statistics to the population growth rate. This mapping shows that, for fixed offspring number and fixed mean replication time,
stochastic timing fluctuations necessarily enhance growth relative to a deterministic clock. When offspring yield depends on the first-passage time, however, fluctuations have non-trivial effects and expose a fundamental yield-delay trade-off: waiting longer can increase the number of descendants, but delays all future lineages. Our framework allows us to address this optimization problem analytically, and upon application to bacteriophage lysis, gives an optimal lysis time and growth rate consistent with empirical data.
Read the full abstract ▾
Analysis of PDEs
A Unified Integral Equation Approach to Conservation Laws for Nonlinear Schrödinger Equations
Shuji Machihara, Hayato Miyazaki and Tohru Ozawa
We present a unified framework for the rigorous derivation of conservation laws and related identities for nonlinear Schrödinger equations with power-type nonlinearities. This approach treats the equation in its Duhamel form and uses the space-time integrability provided by Strichartz estimates, without relying on smooth approximations or regularization procedures. It was first introduced by the third author in [20] and subsequently developed in [7, 13]. In this paper, we establish a single integral identity from which all of the laws and identities considered here follow systematically. These include the conservation of charge (mass), energy, and momentum, the pseudo-conformal conservation law, and virial-type identities.
Read the full abstract ▾