Optimization and Control
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Sunday 20 September
This paper studies path-following control for a kinematic unicycle evolving on a smooth manifold embedded in \(\mathbb{R}^3\). The objective is to stabilize a one-dimensional path on the manifold without imposing a temporal parameterization, thereby distinguishing the problem from trajectory tracking. Working in a geometric framework, we propose two feedback laws: a static controller for prescribed nonzero translational speed and a dynamic controller based on a dynamic extension of the translational speed. By lifting the path to the unit tangent bundle of the surface, we characterize the corresponding path-following manifold and establish its control invariance. We then show that the proposed controllers render the path-following manifold locally exponentially stable under suitable regularity conditions. A numerical simulation illustrates the proposed controller. Code and animations are publicly available at https://gradslab.github.io/UnicycleOnManifolds/.
Differential Geometry
Orientable minimal submanifolds of low index in the sphere
In this short note we prove a rigidity result for orientable minimal submanifolds in the round sphere of the lowest non-trivial Morse index. In particular, we show that the only closed and connected $(2m-2)$-dimensional orientable minimal submanifolds in $\mathbb{S}^{2m}$ of index less than or equal to $2m+1$ are the totally geodesic spheres.
Read the full abstract
Analysis of PDEs
On rigidity of stationary black holes under a nontrapping assumption
We prove that a smooth, regular, asymptotically flat stationary vacuum black hole has a nonextremal Kerr exterior if no null geodesic orthogonal to its stationary Killing field is trapped, establishing the rigidity conjecture of Alexakis, Ionescu, and Klainerman. In the rotating case, we start with the rotational Killing field constructed near the bifurcation sphere and study a maximal domain carrying its complete circle action. The main difficulty is to recover boundary regularity and the curvature condition needed for local Killing extension. We derive uniform estimates along complete rotational orbits from nontrapping and combine them with convexity along short null geodesics. These estimates show that a nonempty remaining boundary in the ergoregion is a timelike photon surface for the stationary quotient metric. Its null geodesics lift to spacetime null geodesics orthogonal to the stationary field. The vacuum circularity identities give their continuation through contact with the ergosurface, keeping their stationary projections in a compact set. This contradicts nontrapping and yields the global rotational symmetry required by black hole uniqueness.
Read the full abstract
Group Theory
Computing Bogomolov multipliers and finitary Bogomolov multipliers of infinite groups
We study homological Bogomolov multipliers and finitary Bogomolov multipliers of infinite groups, with emphasis on polycyclic groups. We obtain structural descriptions for torsion-free nilpotent groups of class two, semidirect products, wreath products, and infinite simple groups. The class-two case reveals a connection with rational points on linear sections of Grassmannians, explaining an arithmetic obstruction to a general algorithm. On the positive side, we give a deterministic algorithm for virtually abelian polycyclic groups and an algorithm for finitary Bogomolov multipliers of arbitrary polycyclic groups, both implemented in GAP.
Read the full abstract
Information Theory
Envelopes of upper bounds for nonbinary constant-weight and constant-composition codes
Deriving upper bounds on code size from existing bounds is a classical approach in coding theory, dating back to the seminal results of Elias, Bassalygo, and Levenshtein. We study a framework encompassing the Bassalygo–Elias and Levenshtein inequalities for binary and nonbinary (constant-weight) codes and provides certain generalizations. The asymptotic cost of transferring a bound between different symbol compositions is expressed in terms of mutual information, yielding an information-theoretic optimal transport formulation. We determine the optimal permutation-transport cost between arbitrary compositions in terms of their least common majorant in the majorization order. Specializing to symmetric constant-weight compositions yields explicit transport profiles. As a byproduct, we establish unimodality of the asymptotic constant-weight rate as a function of the relative weight. We prove that the resulting closure operators are idempotent and that applying transport before outer Bassalygo–Elias averaging leaves the unrestricted bound obtained from the same input unchanged. We also establish necessary and sufficient conditions for an upper bound to be a fixed point of the closure operator. Since the asymptotic rate function is an upper bound for itself and it is a fixed point, we conclude the Schur concavity of the constant-composition rate function. Finally, we survey existing upper bounds for binary and nonbinary constant-weight and constant-composition codes, combine them into optimized envelopes within the transport framework, and obtain improved theoretical and numerical bounds.
Read the full abstract
Mathematical Physics · Cross-listed from physics.flu-dyn
The Positive Defect Problem: Target and Admissibility Criteria for a Programmatic Search for Unforced Navier-Stokes Blowup
On 7 and 8 September 2026 programmatic search produced singularities: a forced Navier-Stokes singularity at every fixed viscosity, statements (C) and (D) of the Clay problem, and two Euler singularities. The unforced problem, statements (A) and (B), stands open, and a search for it needs a target. This paper fixes one: the positive defect problem, that a Leray-Hopf solution from smooth data on the periodic cube loses energy on a finite window, at fixed viscosity, beyond what viscosity removes. A positive defect implies blowup and so a negative answer to statement (B); the converse is not known. The paper proves the target equivalent to a floor on the energy flux through the Littlewood-Paley shells, the Fourier-side form of the coarse-grained flux of the Onsager theory of turbulence, averaged over the window; states necessary conditions on a candidate: a singular time of Type II in velocity, energy concentrating on a set of zero length, a pressure outside L^2, a velocity outside the Onsager-critical class L^3_t B^{1/3}_{3,c_0}, an obstruction to collapse onto a fixed steady Euler profile; and states what cannot certify one: no finite computation witnesses a Galerkin-uniform ceiling, and selection and forcing return the question to a positive defect. A pseudo-spectral search at 128^3 and 256^3 shows which condition of the reduction binds: the fine-shell flux floor holds to within 1 to 6 percent of the ceiling for a third of a turnover time, and fails in scale at the Kolmogorov wavenumber, so a candidate must differ from generic turbulence in the depth of its cascade, not in its timing. Every implication not marked otherwise is a theorem in Lean 4 over Mathlib; the library contains no Navier-Stokes object, and the equation enters only through hypotheses.
Read the full abstract
Metric Geometry
Optimal-diameter partitions into regions of the prescribed measure
In this paper we find a sufficient condition on an Ahlfors–David regular metric measure space under which it admits a partition into parts of prescribed measures and optimal (up to a constant) diameters. The proof uses the construction of dyadic cubes. The process is algorithmic: the pieces are cut out one by one via a filling procedure on the tree of dyadic cubes. We introduce the notion of spaces which admit a connected dyadic cube decomposition and prove that they admit a partition of the kind described above. We then develop several techniques to obtain such spaces and show some natural examples of this type.
Read the full abstract
Representation Theory
A bar operation on the double affine Hecke algebra
We construct a bar-type operation for the affine Hecke algebra $\Ha$ attached to a symmetrizable Kac–Moody group. Our main tool is a geometric bimodule defined using the equivariant $K$-theory of a suitable version of the Steinberg variety for this Kac–Moody group. Using elements of this bimodule corresponding to standard and costandard Hodge $D$-modules on the Kashiwara flag variety, we define a bar involution on $\mathcal{H}_{W}^a$ by relating the left and right actions of $\mathcal{H}_{W}^a$ on this bimodule. A central issue is that the resulting formulas for the bar operation do not preserve the algebra itself and naturally produce infinite expansions. To address this, we introduce certain completions of $\mathcal{H}_{W}^a$ on which the bar operation is well-defined. For this construction, we prove a number of combinatorial finiteness results for products in $\mathcal{H}_{W}^a$. In affine type, we further analyze the level-zero part of the algebra and obtain an explicit combinatorial formula for a bar operation on a suitable localization of Cherednik's double affine Hecke algebra. In this case the bar operation itself is not an involution but we also show that this bar operation becomes an involution when the lattice parameter $q$ is set to $1$.
Read the full abstract
Mathematical Physics
Quantum modularity in refined topological recursion
In this paper we study the Borel summability and quantum modularity of the free energy computed by refined topological recursion on the Weber-type refined spectral curve. On the one hand, we verify expected properties, namely, Stokes rays come in a pair and the Borel-Laplace sum of the free energy coincides with the Barnes double gamma function. Somewhat unexpectedly, on the other hand, we prove that the generating function of the Stokes constants along each ray is a Jacobi quantum modular function. Our proof suggests that quantum modularity may be a general feature of refined topological recursion, applicable beyond the Weber-type refined spectral curve.
Read the full abstract
Probability
Linear Independence of Random Boolean Tensor Powers at the Dimension Threshold
Let $d \geq 1$ be fixed and let \[ D(n,d) := \sum_{j=0}^{d} \binom{n-1}{j}. \] We show that if $x^{(1)}, \dots, x^{(m)}$ are independent uniform points of $\{\pm 1\}^n$ then uniformly for $m \leq D(n,d)$, there exists a constant $C_d > 0$ such that \[ \mathbb{P}((x^{(1)})^{\otimes d}, \dots, (x^{(m)})^{\otimes d} \text{ are linearly independent}) = 1 - O_d\left(\frac{\log^{C_d} n}{n^{1/2}} \right). \] This achieves the exact dimensional threshold and answers a question asked by Baldi and Vershynin. We discuss applications of the result to the semidefinite relaxation of the cut-polytope and to matrix factorization.
Read the full abstract
Combinatorics · Cross-listed from cs.DS
Kadison–Singer partitions and Bilu–Linial graph signings in polynomial time
We prove two main algorithmic results in spectral discrepancy. First, we give a deterministic polynomial-time rounding theorem for rational positive semidefinite matrices of arbitrary rank. The algorithm starts from any rational fractional signing and assigns one sign per original matrix. Its discrepancy is less than $3.37\,\|\sum_i \mathrm{Tr}(A_i)A_i\|^{1/2}$. This yields Kadison–Singer half-partitions with error below $1.69\sqrt{\varepsilon}$, as well as deterministic graph signings that control signed adjacency and signed degrees simultaneously. The proof builds on the spectral-potential method of Ezeunala and Jiang (2026) and introduces a new way to choose rounding directions. We prove polynomial bit complexity for the rounding procedure. Second, we give a Las Vegas algorithm for the Bilu–Linial signing problem on an arbitrary prescribed graph. If $G$ has $n$ vertices and maximum degree $\Delta\ge3$, the algorithm terminates almost surely. It uses fewer than $100n^3$ insertion attempts in expectation and returns a signing with $\|A_s\|<2\sqrt{2(\Delta-1)}$. For bipartite graphs its one-sided form gives the sharp universal bound $\|A_s\|<2\sqrt{\Delta-1}$. The algorithm builds the signing by inserting vertices and recursively deleting and restoring neighbors after rejected insertions. In the analysis, the $\sqrt2$ gap to the Bilu–Linial conjecture comes from a factor of two in the bound for vertex deletions in the two-sided case. On a $d$-regular bipartite Ramanujan base the same signing produces a Ramanujan $2$-lift of that prescribed base.
Read the full abstract
Dynamical Systems · Cross-listed from eess.SY
Stability of Slow-Fast Nonlinear Dynamics: Moving Equilibrium Case
We study the stability of nonlinear systems subject to both slow and fast time variations. Both can have discontinuities, covering switched systems as a special case. The fast variation is assumed to be periodic; thus, we rely on averaging to construct an average system. Importantly, the equilibrium of the average system depends on the slow variation and is assumed to be exponentially stable when this slow input is frozen. Using perturbation and Lyapunov analyses, we establish a practical stability result showing that the system state remains within a neighborhood of the moving equilibrium when the total variation (flows and jumps) of the slow variation is appropriately bounded and the fast input varies sufficiently fast. The result is illustrated via a nonlinear switched system with slow-fast switching and a mode-dependent equilibrium.
Read the full abstract
Optimization and Control
Anytime-Feasible Gradient Descent for Constrained Optimization Under Gradient Uncertainty
Constrained optimization is central to many engineering systems in which decisions must satisfy strict safety and operational requirements, especially in real-time settings with limited computational budgets. In such scenarios, optimization algorithms are often terminated before full convergence, making *anytime feasibility* essential for safe deployment. Existing methods that guarantee feasibility at every iterate typically rely on exact gradient information, an assumption that is often violated in practice due to measurement noise, stochastic approximations, or model mismatch. We develop an anytime-feasible first-order method for nonlinear constrained optimization under norm-bounded errors in the objective and constraint gradients. The method computes a robust search direction by solving a second-order cone program and selects a step size through safeguarded backtracking. Assuming exact function evaluations and a strictly feasible initialization, the method preserves strict feasibility and guarantees sufficient objective decrease whenever the computed search direction is nonzero. We establish a uniform positive lower bound on the accepted step sizes, an O(1/K) bound on the average squared search direction norm, and convergence of the search directions to zero. We also show that a zero search direction at a strictly feasible point certifies approximate first-order stationarity. We validate the proposed method on a multi-agent navigation task in cluttered environments and show that it maintains collision-free trajectories despite noisy gradient information.
Read the full abstract
Number Theory
Selmer groups of CM-twists of elliptic curves
Let $F$ be a totally real Galois number field of degree $g\leq5$ and let $\ell$ be an odd prime. Let $E/F$ be an elliptic curve with an $F$-rational point of order $\ell$. Under explicit arithmetic and local hypotheses, together with an explicit non-vanishing condition modulo $\ell$, we prove that there are $\gg_{F,E,\ell}\frac{X^{1/(2g)}}{\log X}$ totally negative square classes $d\in F^\times/(F^\times)^2$ with $\left|\mathrm{N}_{F/\mathbb{Q}}\bigl(D(F(\sqrt{d})/F)\bigr)\right|<X $ for which $\operatorname{Sel}_\ell(E^d,F)$ is trivial. Such twists have rank zero and trivial $\ell$-part of the Shafarevich–Tate group. The condition is verifiable by a finite computation, which we carry out in an example. We lift the method of James and Ono from $\mathbb{Q}$ to the totally real setting, combining a theorem of Morrow, which relates the Selmer group of such a twist to the class group of the CM extension $F(\sqrt{d})$, with an indivisibility theorem of Takai for relative class numbers. Takai twists only by quadratic Hecke characters, whereas Morrow's conditions are local; we extend the twisting argument to primitive quadratic residue-class characters to make the two results compatible.
Read the full abstract
Combinatorics
Edge complexity of weighted graphs: involutory symmetries and NP-hardness
The edge complexity of a weighted graph is the smallest ratio of the Fourier $\ell^1$ and $\ell^2$ norms of its adjacency matrix over all vertex labelings. We study the difficulty of finding this minimum by relating it to a graph symmetry. Adding a universal vertex with sufficiently large incident weight produces an explicit Fourier $\ell^1$ lower bound. We show that equality holds exactly when the source graph has a fixed-point-free involutory automorphism. Two-sided estimates compare the excess above this bound with the squared Frobenius distance to the nearest weighted graph having such a symmetry. For sources of constant weighted degree, these estimates determine the exact leading term as the added weight tends to infinity. A stronger separation for simple source graphs proves that additive $\frac{1}{256N^{\frac{7}{2}}}$ approximation of weighted edge complexity is NP-hard, even on connected graphs of odd order $N$ with at most two distinct positive integer weights, each at most $N^2$. We also prove that recognizing a simple graph with a real Fourier labeling is NP-complete. A seven-vertex example shows that every minimizing labeling can have nonreal Fourier coefficients even when real Fourier labelings exist. An exact rational certificate for this example is included in the appendix.
Read the full abstract
Optimization and Control
Accelerated Plug-and-Play Davis-Yin Splitting for Nonconvex Image Reconstruction
In this work, we study a class of structured non-convex and non-smooth optimization problems arising in imaging applications, where the objective is the sum of three functions. We consider the Davis-Yin splitting method, a FISTA-type accelerated variant, along with a quasi-Newton line-search method and a plug-and-play (PnP) extension to solve the problem. We develop a unified convergence analysis based on the Davis-Yin envelope under mild assumptions, including the Kurdyka-Łojasiewicz property. Within this framework, we establish subsequential and global convergence of the iterates to stationary points, together with residual convergence rates. We demonstrate the performance of the proposed methods on image restoration and low-rank matrix completion problems. For low-rank matrix completion, we perform experiments on both synthetic data and public datasets to evaluate recovery accuracy and efficiency. In imaging tasks, including image deblurring, we compare the convergence behaviour and reconstruction quality of several algorithmic variants using peak signal-to-noise ratio (PSNR). The results show that FISTA-acceleration and line-search methods improve convergence, while PnP denoisers enhance image quality, and the proposed methods remain competitive on matrix completion tasks.
Read the full abstract
Optimization and Control
The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization
We study the complexity of finding $(\delta,\epsilon)$-Goldstein stationary points of nonsmooth nonconvex Lipschitz functions. By now, it is known that randomized first-order algorithms can solve this task with a dimension-free oracle complexity [Zhang et al., 2020], whereas deterministic algorithms cannot, as their complexity must scale at least linearly with the dimension $d$ [Jordan et al., 2023, Tian and So, 2024]. This leaves open whether deterministic algorithms can nevertheless solve the problem with oracle complexity polynomial in $d$. We answer this question negatively by proving a lower bound of order $(1/\epsilon)^{\Omega(d)}$ for deterministic algorithm, closing the exponential gap between the previously known lower and upper bounds and resolving an open problem posed by Jordan et al. [2023]. We further discuss several extensions and implications of this result to weaker stationarity notions, finding a descent direction and deterministic smoothing. Overall, our results establish an exponential computational advantage in nonsmooth nonconvex optimization offered by randomization.
Read the full abstract
Statistics Theory · Cross-listed from eess.SY
Minimax-Optimal Robust Identification of Continuous-Time Systems: Handling Narrow-Band Disturbances in the Frequency Domain
The high-frequency spectral roll-off of continuous-time ARMA (CARMA) models can magnify the effect of narrow-band disturbances when aliasing is weak, making standard maximum-likelihood Whittle estimation sensitive to affected ordinates. We show that a logarithmic transformation $r_k = \log \rho_k$ converts the Whittle scale problem into a Gumbel location problem, connecting robust spectral estimation to the classical minimax theory of Huber and Rieder. A piecewise centering correction—closed-form for small $b$, implicit closed-form for the practitioner range—preserves Fisher consistency for any clipping level without numerical optimisation. Clipping the Gumbel score symmetrically and transforming back yields a two-sided clipped Gumbel score (the standard Rieder–Hampel bounded-influence form) whose normalised influence curve is proved locally asymptotically minimax under shrinking gross-error contamination. The efficiency loss is quantified by a single scalar $K(b)$: at $b = 1.5$, only $16\%$ nominal asymptotic variance overhead. In the stated AR(2) Monte Carlo design, the sample-size trends are compatible with the asymptotic rate, and at $b=1.5$ the bias reductions are about $40\%$, $90\%$, and $96\%$ for $a_1$, $a_2$, and $\lambda$, respectively.
Read the full abstract
Dynamical Systems
Hyperbolic area of Fatou components and new proofs of no-wandering-domain theorems
We give a new elementary proof of Sullivan's no-wandering-domain theorem for rational maps of degree at least two using hyperbolic area. We then develop this method further to prove that a transcendental entire function has no wandering Fatou components if its set of singular values is compact and all accumulation points of that set lie in the Fatou set. Neither proof uses quasiconformal techniques.
Read the full abstract
Numerical Analysis
Numerical differentiation of functions on the half-line in a weighted uniform metric
We consider the problem of numerical differentiation of functions defined on the half-line: the derivative $f^{(r)}$, $ r=1,2,\ldots$, is recovered from a finite set of perturbed Fourier–Laguerre coefficients of a function $f$, whose error is measured in $\ell_p$, while the accuracy of approximation is measured in the uniform metric with the weight $t^{\alpha}e^{-t}$. It is established that the Wiener class $W^{\mu}_{s}$ admits such a setting for $\mu>r+1-1/s$. A class of methods $\mathcal{S}^{\theta}$ is constructed that realize the optimal order of accuracy of numerical differentiation on $W^{\mu}_{s}$ and use the smallest amount of input information in order.
Read the full abstract
Functional Analysis
Sewing on Thin Groupoids, Knitting, and Based Holonomy for Lipschitz Paths
An approximate action of the pair groupoid of a metric space determines an action of its Lipschitz-thin groupoid on complete extended metric fibers, uniquely characterized by its local sewing estimate. We prove this assertion under a superlinear three-point defect estimate and a Lipschitz bound for finite products. As a result, we obtain a positive proof of Curry and Manchon's sewing conjecture [2], with the necessary path-scaling correction to its estimate. Further restriction to isotropy constructs the based holonomy anticipated in their Remark 4.15 as a representation of based Lipschitz loops modulo thin equivalence. Rectangular comparison estimates give full relative Lipschitz-homotopy descent, in particular under their strong knitting hypothesis and under any three point estimate of total order greater than two. We prove the corresponding flatness and basepoint-covariance statements. An area model shows that the order threshold is sharp. We also separate the exponential estimate from the general knitting assumptions and exhibit a compact disk metric for which strong knitting does not imply invariance under merely continuous homotopy. As an application, for controlled fields on a metric space, we prove that the classical rough integral descends to the thin groupoid and admits substitution with a common rough controller.
Read the full abstract
Differential Geometry
Blaschke Conjecture and Complex Geometry
We provide a complex-geometric approach to the Blaschke conjecture, i.e., that a manifold whose injectivity radius equals its diameter is isometric to a compact rank-one symmetric space (CROSS). In particular, we introduce the great quadric fibration, a complex analogue of the great sphere fibration. Requiring its total space to be a complex submanifold simultaneously explains many properties that a Blaschke manifold is expected to possess, including its Clifford structure, Hopf fibration, and diffeomorphism class. Furthermore, the great quadric bundle coincides with the variety of minimal rational tangents (VMRT) of the ambient Fano variety in the standard CROSS cases, and we explain this through a bend-and-break argument in the setting of the Blaschke conjecture under a suitable complexification assumption. Combining this with Hwang-Mok VMRT recognition, we prove the Blaschke conjecture for manifolds admitting an adapted complex structure on their entire tangent bundles.
Read the full abstract
Probability
Multiradial Regular Variation
We introduce and study multiradial regular variation of random fields, allowing componentwise thresholds to diverge at unrelated rates. The limit measures are homogeneous in each component and finite on events where every component exceeds a positive level in absolute value somewhere on a compact window. We characterise convergence by anchor exceedance masses and conditional whole-path laws, together with a compact-window mass bound in the continuous-parameter setting. For fields indexed by a countable discrete abelian group or by R^m every shift-invariant tail measure in this class admits a strictly stationary realisation. Finite moving averages with shared volatility show that scalar row-tail measures and simultaneous-exceedance tail masses on every consecutive finite window can coincide while relative-lag tail masses differ.
Read the full abstract
Probability
Using the Blackwell-Cover Guessing Strategy to Separate Unobserved Bernoulli Trials
Blackwell and Cover both proposed the same method for guessing the larger of a pair of two numbers when one can only observe one and the other of the two numbers remains unobserved. As originally stated, the procedure ended with a computation showing that the probability of correctly guessing the larger number was greater than one-half. In this paper, we investigate what we can say when about the number in the pair that was not observed we employ the Blackwell/Cover procedure. Let {\alpha}1 and {\alpha}2 be two different numbers in (0,1]. Let G be the uniform distribution on [0, {\alpha}1] and H be the uniform distribution on [0, {\alpha}2]. We think of G and H as being represented by the heads probabilities of coins. We use a variant of the Blackwell-Cover strategy ro take pairs of coins chosen from distributions created from G and H such that one of the coins is flipped, and as a result of that flip the unobserved (unflipped) coin is placed in one of two sets A and B. We show that there are situations in which this can be done so that the mean of the heads probabilities of the unobserved coins in A is less than the mean of the heads probabilities of the unobserved coins in B. We show that there are situations in which recursive application of this process results in a set consisting almost completely of coins from one of the two distributions G and H, and another set consisting almost completely of coins from the other distribution.
Read the full abstract
Probability · Cross-listed from cs.LG
Iterative Atom Refinement: A Monotonicity Principle for Dictionary Learning
Dictionary learning seeks to recover an unknown dictionary $A$ from observations ${\bf y}_i = A{\bf x}_i$ with sparse coefficient vectors ${\bf x}_i$. We introduce the Iterative Atom Refinement (IAR) algorithm, a simple procedure for recovering individual dictionary atoms. Starting from a random direction, IAR repeatedly selects the observations most strongly correlated with the current iterate and updates the direction by averaging the selected data. Our main contribution is a rigorous convergence theory of IAR. Using high-dimensional probabilistic estimates and a novel monotonicity principle for atom-selection probabilities, we show that a small initial advantage of one atom is amplified until that atom is isolated. Under our model assumptions, IAR identifies a generating atom after only three refinement steps. Numerical experiments support the theory and show that the resulting dynamics accurately capture the behavior observed in dictionary refinement.
Read the full abstract
Numerical Analysis
Blind error estimation for CUR approximation
Low-rank approximation is a fundamental tool for scalable matrix computations. While such approximations have classically been formed via the truncated SVD, recent advances in randomized numerical linear algebra have produced methods of comparable accuracy at a fraction of the cost. A key advantage of these approaches is their ability to operate with limited access to the full matrix. A prominent example is the CUR decomposition, which builds an approximation from only a subset of columns and rows, making it particularly well-suited to settings where global matrix access is unavailable, such as in the design of spectro-microscopy experiments where even matrix-vector products cannot be computed. However, the randomness inherent to these methods introduces a key challenge: efficiently assessing approximation accuracy under the stringent constraint that only a subset of matrix entries can be observed. We derive a "blind" estimator of the Frobenius error of a CUR decomposition. For this estimator, we derive a worst-case lower bound on the number of required column queries, and provide techniques for quantifying its uncertainty. Finally, we demonstrate the performance of the estimator and the uncertainty sets on a mix of synthetic problems and real spectro-microscopy examples.
Read the full abstract
Functional Analysis
Normalized Orbit Frames and Essential Spectrum
We characterize the essential spectra of normal operators admitting normalized orbit frames. These are exactly closed subsets of the unit circle with positive Haar measure.
Combinatorics
On the majority game chromatic number of forests and other graphs
A majority coloring of a graph $G$ is a vertex coloring of $G$ in which no vertex has more than half of its neighbors colored with its own color. The least number of colors required for a majority coloring of $G$ is the majority chromatic number $\mu(G)$. The majority coloring game, introduced by Bosek et al. (2019), is a two-player Maker-Breaker-type game where the players alternately color vertices while maintaining the majority condition at each vertex; the least number of colors required for the first player to have a winning strategy on $G$ is the majority game chromatic number $\mu_g(G)$. In contrast with the static case, Bosek et al. show that $\mu_g(G)$ is unbounded in general, while $\mu_g(G)\le col_g(G)$, where $col_g(G)$ is the game coloring number of $G$. It is known (cf. Faigle et al. (1993)) that, for any acyclic graph $G$, $col_g(G) \leq 4$, so $\mu_g(G) \leq 4$ as well. We improve this bound by showing that $\mu_g(G) \leq 3$ for any acyclic graph $G$ of maximum degree at most $4$. We also show that $\mu_g(G) = 2$ if $G$ is a nonempty path, star, or complete graph, or a disjoint union of such graphs. These improve the results of Bosek et al. We also initiate the study of the computational complexity of the pre-coloring extension problem for the static and game versions of majority coloring. We show that the Majority $k$-precoloring Extension problem is NP-complete for each $k \geq 2$. When $k = 2$, it remains NP-complete on the class of bipartite graphs where maximum degrees of each part are $5$ and $6$, and when $k = 3$ it remains NP-complete on the class of $12$-regular planar graphs. We show that the game version is PSPACE-complete, even when the number of colors $k=\chi(G)$, and even when $k=2$ and $G$ is a bipartite graph in which one part has maximum degree equal to $9$. The results on the game versions also hold for the variation where Bob starts the game.
Read the full abstract
Probability
Distance and resistance on random series-parallel graphs: logarithmic speeds and near-critical asymptotics
We study the graph distance $D_n(p)$ and effective resistance $R_n(p)$ between the boundary vertices of a depth-$n$ random series–parallel graph, obtained by recursively joining two independent copies in series with probability $p$ and in parallel with probability $1-p$. We prove the existence of deterministic logarithmic speeds: for every $p\in[0,1]$, $n^{-1}\log D_n(p)$ and $n^{-1}\log R_n(p)$ converge to deterministic limits $v_D(p)$ and $v_R(p)$, respectively, almost surely and in $L^1$. The limiting speeds agree with the corresponding first-moment logarithmic rates for every $p\in[0,1]$ in the distance case and for $p\in[1/2,1]$ in the resistance case. We further determine the near-critical behavior of the resistance speed: $v_R(\frac12+\delta)\sim 2\zeta(3)^{1/3}\lambda_*\delta^{2/3}$ as $\delta\downarrow0$, where $\lambda_*>0$ is characterized by an explicit nonlinear boundary-value problem. This exponent $2/3$ contrasts with the exponent $1/2$ for distance obtained by Chen, Derrida, Duquesne, and Shi (2026). The main idea of this work was proposed by ChatGPT 5.6 Sol, and the authors take full responsibility for the mathematical content. The three main theorems and their supporting proof dependencies have been formalized in Lean 4, relative to two explicitly documented external mathematical inputs.
Read the full abstract
Mathematical Physics
Sum of Three Squares and Particle in a Cubic Box - Degeneracies
We address the problem of determining the degeneracy of a particular energy eigenvalue corresponding to a quantum particle trapped in a cubic box. In other words, we aim to find the number of ways a specific positive integer can be written as the sum of three natural number squares. This is a classic problem in number theory. We provide a closed-form, exact solution to the problem. We do not claim to provide proofs, as we have none; instead, we build up the formulae starting from simple cases where the answer could be deduced by studying the list of degeneracies. We present ample examples that could be verified against the degeneracy calculated numerically via the brute-force method. We arrived at the solution by meticulously studying the list of degeneracies for the first five million numbers, generated by Mathematica$^{\circledR}$.