Functional Analysis
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Saturday 3 October
Let \(X\in M_n(\mathbb C)\), \(n\geq2\), and let \[ \delta_2(X) = \sup_{\dim S=2}\delta(X_S), \] where \(X_S\) denotes the compression of \(X\) to \(S\), and \(\delta(X_S)\) is the diameter of the largest disk contained in the numerical range \(W(X_S)\). Bourin and Lee proved that every positive block matrix \[ M= \begin{pmatrix} A&X X^*&B \end{pmatrix} \] satisfies \[ \norm{M}\leq\norm{A+B}+\delta_2(X). \] In the same work, they conjectured that the inequality \[ \norm{M}\leq\norm{A+B} \] for every positive block matrix with prescribed off-diagonal block \(X\) characterizes essentially Hermitian matrices. We resolve this conjecture by proving the stronger exact formula \[ \sup_{\left(\begin{smallmatrix}A&X\\X^*&B\end{smallmatrix}\right)\geq0} \left\{ \norm{\begin{pmatrix}A&X\\X^*&B\end{pmatrix}} -\norm{A+B} \right\} = \delta_2(X). \] Thus the elliptical width is precisely the optimal norm defect associated with a fixed off-diagonal block. The reverse inequality is obtained by lifting an arbitrary two-dimensional compression of \(X\) to an explicit family of positive block matrices, yielding quantitative two-sided estimates with error of order \(t^{-1}\). As a consequence, the norm inequality above holds universally if and only if \(X\) is essentially Hermitian, proving Conjecture 3.3 of Bourin and Lee. We also construct an explicit \(3\times3\) normal example showing that the radius constant in their normal-off-diagonal eigenvalue estimate is optimal at the leading eigenvalue level. By direct-sum amplification of this construction, we further prove that the same radius constant is sharp at every eigenvalue level \(j\geq0\), thereby resolving their corresponding sharpness question.
Statistics Theory
Optimal Community Recovery by Spectrally Initialized Variational EM in General Stochastic Block Models
We prove a Chernoff-exponent guarantee for the output of spectrally initialized batch variational EM after a prescribed iteration budget, without assuming global maximization of its variational objective. The iteration repeatedly estimates the entire block probability matrix and community proportions from the same sparse graph. We consider a fixed number of communities with proportions bounded away from zero and fixed, positive, distinct connectivity profiles; neither assortativity nor full rank is required. The algorithm uses simultaneous softmax updates without sample splitting or posterior thresholding. Its analysis must control the feedback between estimated parameters, soft labels and reused edges at an exponentially small risk scale. We establish a uniform one-step bound over data-dependent soft assignments whose random remainder has exponentially small expectation. Combined with an exponentially reliable regularized spectral initializer, this yields an unconditional expected misclassification rate bounded by $\exp\{-(1-o(1))J_n\}$ throughout the sparse, diverging-degree regime, where $J_n$ is the minimum nodewise Chernoff information. Matching lower bounds establish first-order logarithmic minimax optimality on local parameter spaces allowing unknown connectivity and varying community counts. The algorithm also attains the sharp first-order exact-recovery threshold. Numerical experiments illustrate refinement gains and sensitivity to initialization and imbalance.
Read the full abstract
Algebraic Topology
Geometric Realizations of Capability Spaces of Large Models and Zigzag Persistent Homology
We propose a topological model for capability changes during large-model training. The model represents knowledge states and preregistered capability probes as subcomplexes of a finite regular CW complex. We prove that attaching a single $n$-cell can only create a class in $\mathrm H_n$ or kill a class in $\mathrm H_{n-1}$. With the reliability threshold and the training checkpoint as two parameter axes, capability gains and losses make the spaces along the training axis nonnested. Union or intersection bridges produce zigzag persistence modules, and we distinguish checkpoint, transition, and bridge-sensitive classes. A finite four-stage example is computed by boundary matrices. The framework records algebraic changes under a chosen encoding, and a homological change is called a candidate capability emergence only after robustness tests, null-model comparisons, and independent behavioral validation.
Read the full abstract
Algebraic Geometry
Core Coordinates and Negative Support in A-Hypergeometric Systems
For a homogeneous $A$-hypergeometric system, let $K_v$ be the intersection of the negative support family for a fake exponent $v$, and let $C_w$ be the set of indices of variables that do not occur in any minimal monomial generator of $\operatorname{in}_w(I_A)$. We prove that $K_v=\operatorname{nsupp}(v)\cap C_w$ holds for every parameter and every fake exponent if and only if $\operatorname{Cone}(A_{C_w})$ meets the interior of $\operatorname{Cone}(A)$. We give equivalent criteria using the reduced Gröbner basis and the associated regular triangulation. When the condition fails, we construct an infinite family of fake exponents for which the equality fails.
Read the full abstract
Probability
Classification of commutation relation for multi-chordal SLE
We classify the linear solution spaces of the chordal Belavin–Polyakov–Zamolodchikov (BPZ) equations, which arise in Dubédat's commutation relations for multiple Schramm–Loewner evolutions (SLE). Without imposing growth conditions, we determine the subspaces selected by successive conformal Ward identities and their exact dimensions. For every $\kappa>0$ and BPZ spectral parameter $\lambda\in\mathbb{R}$, we determine the spectrum and Jordan structure of the translation operator. When $\lambda=0$ and $\kappa\in(0,8)$, we further determine all admissible scaling exponents and the dimensions of the corresponding translation-invariant solution spaces. A triangular change of derivative coordinates yields a first-order system of rational Knizhnik–Zamolodchikov type, allowing us to represent the Ward operators explicitly and reduce the classification to finite-dimensional linear algebra. For $2N$ boundary points and $\kappa\in(0,8)$, translation-invariant BPZ solutions with $\lambda=0$ and the homogeneity required by Möbius covariance automatically satisfy the third Ward identity and the usual power-law bound. This recovers, under weaker assumptions, the Catalan dimension formula previously established by Flores and Kleban. At $\kappa=8$, the third Ward identity imposes an additional constraint when $N\ge2$, but the full Möbius-covariant solution space still has Catalan dimension, establishing completeness of the partition functions constructed from uniform spanning trees. Finally, at $\kappa=4$ and $\lambda>0$, we construct an explicit basis of positive BPZ solutions and identify its elements as partition functions for level lines of a Gaussian free field with suitable harmonic means.
Read the full abstract
Mathematical Physics · Cross-listed from astro-ph.EP
How dust particles orbiting white dwarfs can reveal undetected co-orbiting exoplanets II. Exoplanets on elliptic orbits
Abridged. We aim to extend Paper I to the eccentric secondary orbit case and now analyse the elliptic restricted three-body problem (ERTBP). Our secondary masses include Ceres, Mercury, Earth, and Neptune so that we can help infer the presence of both large asteroids and planets through our analysis. We study dust particles on both planar (2D-ERTBP) and non-coplanar (3D-ERTBP) orbits. We computed families of 1/1 resonant symmetric and asymmetric periodic orbits in the 2D-ERTBP and 3D-ERTBP. Doing so produces novel results in their own right and diagnostic tools for precise guidance for our next steps. Based on them, we generated detailed phase portraits. Finally, we run suitably seeded $N$-body simulations to compare with the periodic orbits, and to provide observational links with debris close to WDs. New families of asymmetric periodic orbits, called $E^A_{41}$, $E^A_{42}$, and $E^A_{43}$ in the high-eccentricity 2D-ERTBP regime were discovered. They are generated by the new bifurcation point, $B_T^4$, along the new $A_2$ family, showcased in Paper I. Moreover, new isolated families of asymmetric periodic orbits, namely $E^A_{44}$, $E^A_{45}$, and $E^A_{46}$ were discovered. Families of short- and long- period asymmetric orbits starting from $L_4$, called $E^A_S$ and $E^A_L$, were also computed. In both the 2D- and 3D-ERTBP regimes, highly eccentric motion is exhibited for the dust particles in the majority of the families of either symmetric or asymmetric periodic orbits. The $N$-body simulations reveal that over ten years, the orbital period deviations of the dust are higher than in the circular restricted three-body problem (Paper I); in some architectures, Mercury-mass planets can regularly generate deviations exceeding $\sim$100 s, which potentially aids observational inferences of hidden asteroids or planets orbiting WDs.
Read the full abstract
Numerical Analysis · Cross-listed from cs.LG
Checkable NTK Positivity and Finite-Width Gradient Descent for Scalar- and Vector-Valued PINNs with Strong-Form, Weak-Form, and Nonlocal Linear Constraints
We give checkable positive-definiteness criteria for the limiting neural tangent kernel (NTK) and high-probability finite-width gradient-descent guarantees for scalar- or vector-valued physics-informed neural networks (PINNs) with linear constraints. The constraints may be strong-form differential rows of any fixed finite order, including coupled systems, with any linear initial or boundary conditions; weak-form residual and boundary functionals; or finite-measure nonlocal observations such as integral, nonlocal-diffusion, and Dirac-data rows, all in any dimension. For each class, positive definiteness of the limiting NTK is equivalent to a rank condition on a finite coefficient, functional, or moment matrix of the fixed design: a certificate computed before training that detects structural zero modes. The model hypotheses are those of an ordinary two-layer PINN, a smooth nonpolynomial activation with bounded symmetric initialization, and are met by standard choices such as $\tanh$ with uniform initialization. Given a certificate, explicit width and step-size conditions ensure, with high probability, that the empirical NTK retains at least half the limiting gap and that full-batch gradient descent decreases the training loss geometrically at every iteration. Controlled experiments check the certificates and the finite-width mechanism.
Read the full abstract
Numerical Analysis
Operator splitting methods for non-autonomous evolution equations comprising three parts, with application to the Bloch-Torrey equation of MRI
In this paper we devise and analyze Lie Trotter splitting schemes for non-autonomous evolution equations, following two approaches: 1) A fully non-autonomous scheme, motivated by the potential use of explicit solutions of some subproblems. 2) A splitting scheme relying on the concept of Magnus integrators, where we freeze the operators at the beginning of each time interval as this suffices for first order convergence of the Lie-Trotter integrator. We derive first order convergence in a general setting and apply the analysis to the Bloch-Torrey equation of magnetic resonance imaging, where a decomposition into three subproblems is well-motivated by the physical role of the underlying operators. Numerical tests, complementing the time stepping scheme by a finite element space discretization, illustrate the theoretical findings.
Read the full abstract
Numerical Analysis
Inference of Hamiltonian and Lie-Poisson structures from vector field samples
We present a method for the data-driven inference of Hamiltonian and Lie-Poisson dynamical systems from vector-field samples, in which the Hamiltonian and the underlying Poisson tensor are estimated jointly rather than assuming the structure is known. The Hamiltonian is represented as a linear combination of random feature maps with fixed random internal weights, so its estimation is a linear regression problem for any given Poisson structure. We treat three cases of increasing generality: a known Poisson tensor, an unknown constant invertible (symplectic) structure matrix, and Lie-Poisson and affine Poisson structures, with structure matrix linear in the state. In the constant case, the Hamiltonian and structure matrix are recovered jointly from an eigenvalue problem that avoids the trivial zero solution due to the scaling symmetry of Hamiltonian systems. For Lie-Poisson and affine Poisson systems we alternate between an initial Hamiltonian estimate from a generalized eigenvalue problem for an approximate first integral, and a constrained nonlinear least-squares fit of the structure constants that enforces the Jacobi identity and, for affine structures, the cocycle condition, via continuation in a penalty parameter. Orthogonal matching pursuit selects a compact, well-conditioned subset of random features. Because the learned Hamiltonian is a sum of single-feature terms, the model admits an explicit Poisson/symplectic splitting integrator, which we use to validate the learned systems via long-time Poincare sections. We demonstrate the approach on the four- and five-dimensional Lorenz-86 model and a six-dimensional Kirchhoff rigid-body system, recovering Hamiltonians, structure constants and Casimir invariants to high accuracy, and showing the inferred Poincare sections converge to the correct invariant-tori topology as the number of random features increases.
Read the full abstract
Numerical Analysis
On the involution preserving properties of semi-discrete Active Flux methods on simplex
We study the involution-preserving properties of the Active Flux method on unstructured triangular meshes. Two model problems are considered: the two-dimensional linear acoustic system, which satisfies a curl involution on the velocity field, and the two-dimensional Maxwell equations with an in-plane magnetic field, which satisfy a divergence involution. Both systems can be written in conservative form. The question we address is how a single discretization can satisfy the conservative form and the involution at the same time. Within a discrete Active Flux framework on simplices, we derive explicit formulas for a discrete curl operator that is exactly preserved by the scheme for acoustics, and for a discrete divergence operator preserved for the Maxwell system. The analysis applies to general simplex meshes and to any polynomial degree, including extensions of the method beyond third order. Numerical experiments with the third-order scheme confirm the theoretical results. Highlights: 1-Active Flux on unstructured triangular meshes preserves discrete involutions, 2-Explicit discrete curl operator preserved by the scheme for linear acoustics, 3- Explicit discrete divergence operator preserved for 2D Maxwell equations, 4- Results hold on general simplex meshes,% and for any polynomial degree 5- Third-order numerical experiments confirm the theoretical results. \end{itemize}
Read the full abstract
Dynamical Systems · Cross-listed from eess.SY
A KKL Observer Perspective on Reservoir Computing
Reservoir computing (RC) is a machine learning technique for data-driven modeling of dynamics for forecasting and control, primarily studied in computer science and physics literature with promising applications in neural network learning, physical computing, and neuroscience. Why reservoirs learn and how to choose good reservoir architectures are considered important open questions. We show that the RC problem is mathematically an extension of a classic problem in systems and control theory, the Kazantzis-Kravaris-Luenberger (KKL) observer design problem. As a consequence, many of the questions considered open for RC stand to benefit from a large body of theory in the mature KKL literature, non-exhaustively including on questions of embedding, transverse stability, local and global uniqueness guarantees, and effective data-driven solution constructions. Elaborating on this connection, we show that the surprising forecasting ability of reservoirs is in fact a direct consequence of the well-known observer internal model principle, derive an upper bound on the prediction error over a fixed forecast horizon, and provide a partial explanation for why linear readout training in RC works reasonably well. This work illustrates how classical ideas from systems and control can provide strong theoretical backing and open new questions for modern machine learning methods.
Read the full abstract
Optimization and Control
Intrinsic Path Following on $\mathsf{SO}(3)$
This paper studies intrinsic path following for fully actuated rigid-body attitude dynamics over a broad class of attitude paths, namely arbitrary smooth embedded closed curves on $\mathsf{SO}(3)$. We construct a tangential–transverse state decomposition on a tubular neighborhood using normal and pullback bundle geometry. The resulting second-order dynamics admit a smooth feedback transformation that independently assigns tangential and transverse covariant accelerations. A transverse proportional–derivative law renders the path-following manifold invariant and locally uniformly exponentially stable on an explicit forward-invariant neighborhood, while leaving the tangential dynamics freely assignable. This allows independent regulation of progression along the path, stabilization of a selected attitude on the path, or tracking of a time-varying motion. For a representative fiber path, the tubular coordinates are obtained in closed form up to the natural cut-locus obstruction, and simulations illustrate point stabilization and trajectory tracking.
Read the full abstract
Group Theory
Asymptotic Schur orthogonality for lattices
Let $\pi:G\to \mathcal{U}(L^{2}(G/P,\nu))$ be the boundary representation of a non-compact connected semisimple Lie group $G$ with finite center on its Furstenberg-Poisson boundary $(G/P,\nu)$. Let $\Gamma\subset G$ be a lattice in $G$ (uniform or not). We show that for any continuous functions $\varphi,\psi,\varphi',\psi'$ on $G/P$, $$ \lim_{n\to\infty}\frac{1}{|\Gamma_{n}|}\sum_{\gamma\in \Gamma_{n}}\frac{\langle\pi(\gamma)\varphi,\psi\rangle\overline{\langle\pi(\gamma)\varphi',\psi'\rangle}}{\Xi^{2}(\gamma)}=\langle \varphi,\varphi'\rangle\overline{\langle\psi,\psi'\rangle}, $$ where $\Gamma_{n}$ is a ball in $\Gamma$ with radius $n$ relative to a natural length function and with center the identity element of $G$, and $\Xi$ is the restriction to $\Gamma$ of the Harish-Chandra function of $G$. As a corollary, we deduce that when the real rank of $G$ is one, then the analogous convergence holds for any $\varphi,\psi,\varphi',\psi'$ in $L^{2}(G/P,\nu)$ if and only if the lattice $\Gamma$ is uniform.
Read the full abstract
Representation Theory
Chromatic characters and root multiplicities for Borcherds–Kac–Moody algebras
The main aim of this article is to obtain explicit formulas for the root multiplicities of a class of finite-rank symmetrizable Borcherds-Kac-Moody algebras g(A) whose real part is of type A. The Dynkin diagram of each such algebra is obtained from the disjoint union of a Dynkin diagram of type A and a finite simple graph G_im, whose vertices correspond to imaginary simple roots, by choosing one vertex in each and joining the chosen vertices by a single edge of multiplicity c>0. More generally, we consider the same construction with the type A diagram replaced by the Dynkin diagram of an arbitrary finite-rank symmetrizable Kac-Moody algebra g_re. The resulting symmetrizable Borcherds-Kac-Moody algebra g(A) has real part g_re and imaginary part represented by G_im. Our starting point is a graph-theoretic description of the quotient of the denominator products of g(A) and g_re. This quotient is a multivariate independence polynomial of G_im, with the variable corresponding to the attachment vertex weighted by normalized highest-weight characters of g_re. We prove that the coefficients of powers of this quotient factor into a generalized chromatic polynomial and a tensor-power weight multiplicity. Using this, we obtain explicit formulas for all root multiplicities with nonzero imaginary component in terms of generalized chromatic polynomials of G_im and weight multiplicities in tensor products of highest-weight modules of g_re. When G_im is chordal, these formulas specialize to finite divisor sums involving products of binomial coefficients; paths and complete graphs provide particular examples. In particular, we obtain explicit formulas for the root multiplicities of g(A) when its real part g_re is of type A.
Read the full abstract
Probability
The contact process with social clusters and asymptomatic states
This paper is concerned with a natural variant of the contact process that places a social cluster of individuals, rather than a single individual, at each lattice point, and distinguishes between symptomatic and asymptomatic individuals. In particular, the epidemic model depends on four infection parameters: the external (inter-cluster) and internal (intra-cluster) infection rates for both symptomatic and asymptomatic individuals. Newly infected individuals begin as asymptomatic before transitioning to the symptomatic state at a spontaneous mutation rate, and infected individuals recover at a baseline rate of one. We study the phase structure of the deterministic nonspatial mean-field model when each cluster reduces to a pair of individuals, and prove that the stochastic spatial model exhibits the same phase transitions with respect to the four infection rates for all cluster sizes. We also prove the existence of a phase transition driven by the cluster size itself for the spatial model.
Read the full abstract
Rings and Algebras
Characterization of the centrally finite Amitsur-Small division rings
In 1978, Amitsur and Small asked whether, for every division ring $D$, maximal left ideals of $D[x_1,\ldots,x_n]$ contract to maximal left ideals in smaller polynomial subrings. Chapman and the author showed that the answer is negative in general and called $D$ an Amitsur-Small ring when this contraction property always holds. Earlier work showed that Hamilton's real quaternion algebra is Amitsur-Small, that division algebras of degree three are not Amitsur-Small, and that degree-two examples are restricted to a specific quaternionic form; subsequent work excluded cyclic division algebras of odd prime degree. We give a complete resolution in the centrally finite case. If $D$ has finite dimension over its center $F$, then $D$ is an Amitsur-Small ring if and only if either $D=F$, or $F$ is real closed and $D$ is the Hamilton quaternion algebra $(-1,-1)_F$. In every other noncommutative centrally finite case, failure already occurs in two variables: there is a maximal left ideal $M\subseteq D[x,y]$ such that $M\cap D[x]$ is not maximal in $D[x]$.
Read the full abstract
Algebraic Geometry
The topology of Kähler manifolds and 1-forms without zeros
We study how the topology and geometry of a compact Kähler manifold relate to the zeros of its one-forms. We determine all implications among several closely related conditions. In particular, we construct a smooth projective variety for which the Aomoto complex is exact for every nonzero holomorphic one-form and every semisimple local system, although every closed real one-form, and hence every holomorphic one-form, has a zero.
Read the full abstract
Number Theory
Cubic Progressions on Smooth Plane Curves
Let $C \subset \Pbb^2_k$ be a smooth projective plane curve of degree $d \ge 5$ over a number field $k$. We prove that any cubic arithmetic or geometric progression sequence on $C$ is finite. The proof rests on a prime-$p$ tower of cyclic Kummer covers controlled by the divisor of a linear-form quotient on $C$, combined with the Kadets–Vogt classification of curves with infinitely many cubic points, the Abramovich–Harris gonality descent, a Castelnuovo–Severi factorization for the elliptic maps supplied by Kadets–Vogt independently at consecutive levels of the tower, and a deck-transformation obstruction. We also obtain a conditional quartic result under a cyclotomic non-splitting hypothesis. The case $d = 4$ with $C(k) \neq \emptyset$ admits infinite cubic progressions, so no analogue of the main theorem can hold there.
Read the full abstract
Algebraic Topology
Torsion of every finite order in the homology of graph braid groups
We determine the torsion subgroup of $H_{m-1}(\mathbb{B}_mK_{m+1,m+r-1};\mathbb{Z})$ for $m\ge2$ and $r\ge0$: top homology with arbitrary coefficients is the kernel of an unsigned subset-inclusion matrix, and its integral diagonal form determines all primary summands. Every finite order occurs, with explicit representatives. Generalized theta classes span an embedded copy of the cokernel of the inclusion matrix, containing all torsion; for $r\ge m$ they generate the torsion, each of order $\operatorname{lcm}(1,\ldots,m)$. For every prime power $q$ and $m\ge q$, the graph $K_{m+1,m+q-1}$ is minimal in the minor order for order-$q$ torsion in $H_{m-1}(\mathbb{B}_m)$. In particular, odd torsion first appears in $H_2(\mathbb{B}_3K_{4,5})\cong\mathbb{Z}^{155}\oplus(\mathbb{Z}/2)^4\oplus\mathbb{Z}/3$, and no proper minor of $K_{4,5}$ has odd torsion in $H_2(\mathbb{B}_3)$. For arbitrary part sizes, we give a multiplicity-free decomposition of $H_m(\mathbb{B}_mK_{a,b};\mathbb{Q})$ under vertex permutations and prove that $H_{m-1}(\mathbb{B}_mK_{a,b};\mathbb{Z})$ has no $p$-primary torsion when $a,b\ge2m-1$ and $p\ge m$ is an odd prime. The explicit order-$q$ class retains its order under every enlargement of the second part of the graph, while for $m=q=p$ an odd prime it is killed by a specified enlargement of the first part.
Read the full abstract
Optimization and Control
Amortized Score-Hamiltonian Policy Iteration: A Grid-Free Scheme for Relaxed Stochastic Control Problems
We develop an amortized, grid-free implementation of continuous Langevin dynamics based policy-value iteration for entropy-regularized, infinite-horizon relaxed stochastic control problems. The improvement rate of the exact iteration is a discounted aggregate of relative Fisher information between the policy and the Gibbs law of its Hamiltonian. The associated score residual is the velocity with which the control's Langevin dynamics transport its law. We project this velocity onto a conditional sampler shared across states, instead of one Langevin dynamics per state, and the value dynamics onto a parametric critic, estimating both projections at sampled states to obtain coupled actor–critic flows. The score loss measures the actor's agreement with the current critic, while the policy-evaluation residual measures the critic's agreement with the actor. We also derive gradient and Hessian residuals, including a Feynman–Kac representation for the gradient equation, to control errors not detected by the projected value iteration. An exact decomposition of the HJB residual combines these errors into a policy-suboptimality bound under verification and logarithmic Sobolev assumptions. In the linear-quadratic class, both projections are exact and recover the pointwise iteration, and we provide numerical experiments on general models to demonstrate the coupled actor–critic learning in high-dimensions.
Read the full abstract
Optimization and Control
Computing Equilibria in Integer Programming Games with Shared Constraints
We develop a cutting-plane algorithm for computing pure Nash equilibria in finite integer games with shared constraints, where a deviation may be feasible against one opponent profile and infeasible against another. Conditional equilibrium inequalities capture this dependence through an explicit activation term. We give affine encodings of costs and activation conditions and prove that the resulting inequalities characterize the equilibrium set exactly. Embedded as lazy constraints in branch-and-cut, they yield the Generalized Zero-Regret algorithm for optimizing a linear objective over exact or approximate equilibria; a bisection procedure maintains certified bounds on the smallest achievable approximation factor. We also prove that, when the conditional polytopes have integral vertices, a concave cost is constant on the minimal face containing an equilibrium strategy, so strict concavity forces vertex strategies; for uniform integer-splittable bin packing, a cost-preserving transformation yields vertex equilibria even without strict concavity. We give formulations for bin packing, network formation, and knapsack games with shared capacities and evaluate the algorithm on 3,300 instances, computing a socially optimal equilibrium on all but 43, certifying nonexistence on 16, and certifying approximation factors within a few percent where no exact equilibrium exists.
Read the full abstract
Group Theory
Groups of Class Transpositions with Prescribed Prime Divisors of the Moduli
For a set $\mathcal P$ of odd primes, let $\operatorname{CT}_{\mathcal P}(\mathbb{Z})$ denote the group generated by all class transpositions whose moduli have no odd prime divisors outside $\mathcal P$. We prove that \[ \bigl\langle \operatorname{CT}_{\mathcal P_1}(\mathbb{Z}),\operatorname{CT}_{\mathcal P_2}(\mathbb{Z}) \bigr\rangle = \operatorname{CT}_{\mathcal P_1\cup\mathcal P_2}(\mathbb{Z}) \] for any sets $\mathcal P_1$ and $\mathcal P_2$ of odd primes. This gives a negative answer to Question 21.75 in the Kourovka Notebook.
Read the full abstract
Group Theory · Cross-listed from quant-ph
Amenable groups with nearly exponential sofic profile, and quantum channels that need nearly linear memory
How far from finite can an amenable group be? Every finite piece of an amenable group can be imitated by permutations of a finite set, and Cornulier's sofic profile counts how many points such an imitation needs at accuracy $1/r$. We build a finitely presented elementary amenable group with a finite piece whose profile is $\exp(r^{1+o(1)})$, close to the most our counting method can ever detect. The construction is a lamplighter with its lamps on configurations rather than on points. Houghton's group moves the points of three rays, finitely supported affine maps act on their binary configurations, and a copy of $S_3$ sits on every configuration. Then $N$ points carry $2^N$ lamps, yet any two lamps can be brought together by moves that each involve at most three points. The group embeds in Brin's group $3V$, so $3V$ too has a finite piece of nearly exponential profile. The group also gives an explicit quantum channel on $\mathbb C^{873}$ that is cheap to use once and expensive to use many times. A device that applies it $n$ times, releasing each output before the next input arrives, needs about $n/B$ qubits of memory when it may spend $B$ bits of purity, and exact devices achieve this up to polylogarithmic factors. With exchange at the optimal rate, the least memory is about $\sqrt n$, attained with purity of the same order. The channel is factorizable and lies in the closure of channels with finite maximally mixed baths, yet any such bath that imitates it to accuracy $u$ needs dimension $\exp(u^{-1+o(1)})$, although its minimal Stinespring dilation implements it exactly with a pure environment of dimension $130$. The engine is a one-round theorem: after a single use, the memory of any such device carries an approximate representation of the group.
Read the full abstract
Combinatorics
The complete nontrivial-intersection theorem for vector spaces
A family of $k$-subspaces of an $n$-dimensional vector space over a finite field is $t$-intersecting if any two members intersect in a subspace of dimension at least $t$. A $t$-intersecting family is nontrivial if no $t$-subspace is contained in all its members. In this paper, we determine the largest nontrivial $t$-intersecting families for $k\geq t+2$ and $n\geq 2k+1$. As a result, the complete nontrivial-intersection theorem for vector spaces is established.
Read the full abstract
Optimization and Control
An inverse-stochastic-control Galerkin estimator for drift potentials
We consider the ill-posed inverse problem of recovering the drift potential of an overdamped Langevin diffusion from discrete, possibly irregular position observations. Specializing the suboptimality gap for inverse stochastic control to drift-potential recovery, we parametrize the associated value function in a finite basis. Under a basis nondegeneracy condition, the resulting Galerkin estimator is obtained from one positive-definite linear system whose entries are smooth functionals of the empirical time marginals; no transition density is required. The gap equals one half of the squared energy distance to the true potential, yielding a best-approximation identity and energy-seminorm consistency as the basis becomes complete. At a fixed basis, we separate the sample fluctuation from the time-quadrature error, thereby avoiding the Euler–Maruyama $O(\Delta t)$ drift-discretization bias. We also analyze the finite basis as regularization, give a dimension-dependent convergence rate for a concrete basis family, and bound observation-noise bias. One- and two-dimensional experiments verify the predicted sampling-interval behavior. An application to irregular animal telemetry illustrates the method on a single long trajectory.
Read the full abstract
Optimization and Control · Cross-listed from cs.LG
Adaptive Bregman Alternating Projections for Feasible Gromov-Wasserstein Learning
The Gromov-Wasserstein (GW) problem compares structured distributions without requiring a shared feature space or known correspondences, but its nonconvex objective and coupled marginal constraints make computation challenging. Bregman alternating projected gradient (BAPG) uses inexpensive alternating row and column updates, yet its fixed-penalty relaxation leaves a persistent feasibility gap. We propose Adaptive KL-BAPG (A-KL-BAPG), which combines a finite fixed-penalty burn-in with a guarded increasing-penalty phase. At each tail iteration, the method reuses BAPG's alternating updates and backtracks a delayed-power step until a Sinkhorn-inspired projective-diameter safeguard is satisfied. We prove finite termination of the backtracking at each iteration and show that the feasibility gap vanishes asymptotically. We further establish a best-iterate $O(1/\log N)$ bound for the weighted squared corrected residual and, under a support regularity condition, the existence of a stationary accumulation point for the original GW problem. This distinguishes A-KL-BAPG from fixed-penalty BAPG, whose stationarity guarantees are given for the relaxed problem. Experiments show that A-KL-BAPG achieves a favorable balance of accuracy, objective value, feasibility, and stationarity relative to BAPG variants, projection-based methods, and task-specific baselines. For synthetic and real graph alignment problems, it closely matches the accuracy and objective value of fixed-penalty KL-BAPG while reducing the marginal feasibility gap by 62-99% and the projected stationarity residual by 28-98%. Heterogeneous domain adaptation experiments show a similar pattern: A-KL-BAPG maintains comparable target accuracy and objective values while achieving better feasibility and stationarity than fixed-penalty KL-BAPG.
Read the full abstract
Analysis of PDEs
Sharp Truncated Difference Estimates for Nonlocal Nonconvex Functionals Defined by Superlevel Sets
Let $N\in\mathbb N$ and $p\in[1,\infty)$. In this article, we consider a family $\{\Phi_{\lambda,p}^{\gamma}\}_{\lambda\in(0,\infty)}$ of nonlocal nonconvex functionals with a real parameter $\gamma$ and establish two truncated difference estimates bounded by these functionals with the sharp range of $\gamma$; that is, for any $\gamma\in(-\infty,-1]$, any $\lambda\in(0,\infty)$, any cube $Q\subset\mathbb R^N$, and any measurable function $g:Q\to\mathbb R$, \begin{align*} &\int_Q\int_Q\left[\frac{|g(x)-g(y)|-\lambda|x-y|^{1+\gamma/p}}{\ell(Q)^{1+\gamma/p}}\right]_+^p\,dx\,dy\\ &\quad\lesssim \lambda^p\mathop{\int_Q\int_Q}\limits_{\frac{|g(x)-g(y)|}{|x-y|^{1+\gamma/p}}>\lambda}\left[\frac{|x-y|}{\ell(Q)}\right]^{\gamma-N}\,dx\,dy=:\frac{\Phi_{\lambda,p}^{\gamma}(g;Q)}{\ell(Q)^{\gamma-N}}, \end{align*} where the implicit positive constant depends only on $N$, $p$, and $\gamma$. For $\gamma\in(0,\infty)$, the above estimate holds with the left-most integrand replaced by $\frac{\min\{|g(x)-g(y)|^p,\lambda^p|x-y|^{p+\gamma}\}}{\ell(Q)^{p+\gamma}}$. As applications, these estimates yield related nonlocal Poincaré inequalities with the sharp range of $\gamma$, and also recover the known $\Gamma$-liminf lower bounds and characterizations of Sobolev and BV spaces in terms of the liminf of the functionals $\{\Phi^\gamma_{\lambda,p}\}_{\lambda\in(0,\infty)}$ for all $\gamma\in\mathbb{R}\setminus(-1,0]$. We investigate further applications to compactness and variational problems as well as a new VMO criterion. Inspired by a recent work of R. L. Frank, we develop an elementary approach based on dyadic iteration of truncated differences along line segments, which allows us to treat the aforementioned problems in a unified way.
Read the full abstract
Analysis of PDEs
Existence and stability of shock profiles for a one-dimensional full compressible Navier–Stokes–Poisson equations
This paper studies the existence and asymptotic stability of traveling shock waves for the one-dimensional full compressible Navier–Stokes–Poisson equations, which model viscous heat-conducting ions in a self-consistent electrostatic field. We first prove the existence and uniqueness of a smooth shock profile of small amplitude by the center manifold theorem, and then establish its large-time asymptotic stability under suitably small smooth perturbations. The proof is based on an energy estimate for a specially constructed integrated system derived from the full compressible Navier–Stokes–Poisson equations. To carry out this estimate, we introduce suitable anti-derivative variables that incorporate the effects of the self-consistent electrostatic potential and heat conduction, thereby reformulating the original system as a dissipative integrated one. The subsequent energy estimates are completed by carefully handling the induced couplings.
Read the full abstract
Number Theory
Prescribed Ideal Classes in Ennola Cubic Fields and Rational Points on Associated Elliptic Curves
For every prime $\ell\geq5$ and integer $n\geq2$, we construct an Ennola cubic field with a specified prime ideal above $\ell$ whose class has exact order $2^n$. For parameters satisfying two square conditions and explicit congruences, the same squareclass obstructions give four independent rational points on the associated elliptic curves. A Pell equation describes all such parameters. A genus-one base change gives five independent sections that generate a subgroup saturated at two. It also yields infinitely many elliptic curves over $\mathbb Q$, pairwise nonisomorphic over $\overline{\mathbb Q}$, with rank at least five.
Read the full abstract
Algebraic Geometry
From wall structures to closed mirror symmetry. The case of $K_{\mathbb{P}^2}$: Renormalized periods over the positive real locus, closed Gromov-Witten invariants from wall functions, and tropical enumeration
We recover closed Gromov-Witten invariants and renormalized mirror periods for $K_{\mathbb{P}^2}$ by the same operation on a wall function. This gives a direct passage from the Gross-Siebert construction of intrinsic mirror pairs to classical enumerative mirror symmetry. The link is a polynomiality theorem for punctured invariants. Assuming the expected identification with the normalized slab function, we also obtain a finite tree sum for closed Gromov-Witten invariants in terms of types of plane tropical curves. The mechanism is expected to extend to more general Calabi-Yau mirror pairs.