Peer Revenue Publish or profit

Papers

Fresh from arXiv, typeset properly. Highlighted words trade on the market.

Mathematics

math Watch Mathematics (sign in to use)

Friday 28 August

Rings and Algebras

Algebras with Variable Operator-Valued Structural Constants and Their Applications

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

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

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

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

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

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

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

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

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

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

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

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

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$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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