Peer Revenue Play credits. Real papers.

Papers

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

Mathematics

math Watch Mathematics (sign in to use)

Wednesday 23 September

Spectral Theory

Microlocal analysis and spectral gap for complex hyperbolic manifolds

We prove the existence of an essential spectral gap for convex cocompact complex hyperbolic manifolds under the hypothesis that the limit set does not contain a complex circle. We apply an extension to complex hyperbolic manifolds due to Quan of the approach of Vasy to meromorphic continuation of the resolvent. This allows us to adapt the method of Dyatlov-Zahl to prove fine microlocal properties of resonant states. Following recent work of Athreya-Dyatlov-Miller and Dyatlov-Jezequel, we then take advantage of the different expansion rates in different directions for the geodesic flow, and apply the one dimensional fractal uncertainty principle of Bourgain-Dyatlov along the fast expanding direction. Combining these techniques provides a new resolvent bound from which the essential spectral gap follows.
Read the full abstract

Probability

Recurrence and transience of random walks in monotonically changing environments

Let $(c_t)_{t\geq 0}$ be a deterministic family of edge conductances on a countable vertex set, monotone in $t$, and let $(X_t)$ be the random walk that takes its $t$-th step using the conductances $c_t$. We prove that if $c_t\uparrow c_\infty$ and $c_\infty$ is recurrent (respectively, $c_0$ is transient), then $(X_t)$ is almost surely recurrent (respectively, transient), i.e., visits every vertex infinitely (respectively, finitely) often. We also establish the analogous results in continuous time. This proves conjectures of Amir, Benjamini, Gurel-Gurevich, and Kozma, and the special case of $\{ 0, 1 \}$-valued conductances corresponds to simple random walk on a growing graph, and in this special case our results prove a conjecture of Dembo, Huang, and Sidoravicius. In addition, we provide counterexamples to the corresponding conjectures when $(c_t)$ is monotone non-increasing: if $c_t\downarrow c_\infty$ and $c_\infty$ is transient, $(X_t)$ need not be transient, and similarly if $c_0$ is recurrent, $(X_t)$ need not be recurrent, even if $c_\infty\geq\alpha c_0$ for some $\alpha>0$.
Read the full abstract

Functional Analysis

The Dunford-Pettis property for Lipschitz-free spaces over $\mathbb{R}^n$

We show that for every $n\in \mathbb{N}$, the Lipschitz-free space $\mathcal{F}(\mathbb{R}^n)$ has the Dunford-Pettis property. As a consequence, for every $n\in \mathbb{N}$ and every nonempty $M\subset \mathbb{R}^n$, the space $\mathcal{F}(M)$ has the Dunford-Pettis property. This implies that $\mathcal{F}(M)$ is not isomorphic to $\mathcal{F}(X)$ for any separable Banach space $X$ that fails the Dunford-Pettis property. In particular, this applies to $X=\ell_2$, and more generally to every infinite-dimensional separable reflexive space. We also deduce that if $1<p<\infty$, then $\mathcal{F}(\ell_p)$ is not isomorphic to $\left(\bigoplus\limits_{n=1}^\infty \mathcal{F}(\ell_p^n) \right)_{\ell_1}$.
Read the full abstract

Statistics Theory · Cross-listed from stat.ME

Reduced-Rank Autoregressive Models for Matrix Time Series

Matrix time series is a series of matrix data observed over time. Analytical tools for such time series is needed in many applications in finance, economics, engineering and many other fields. To avoid the use of vectorization of the matrices which loses the column and row information, and the vector autoregression framework in traditional time series analysis, \cite{chen2021autoregressive} proposed the Matrix Autoregressive (MAR) Model. The model maintains and utilizes the matrix structure, leading to a substantial dimensional reduction and admitting explicit interpretations, comparing with the vector autoregressive model on the vectorized data. However, the MAR model still encounters difficulties in dealing with large dimensional matrix time series as the coefficient matrices in MAR models are also large. In this paper we propose to achieve further dimension reduction through reduced-rank constraints of the coefficient matrices in the MAR model. Estimation and rank determination procedures are studied. Theoretical investigation and empirical examples show that the reduced-rank constraint can achieve higher statistical efficiency than the MAR model.
Read the full abstract

All authors Han Xiao, Yuefeng Han, Rong Chen, Ama Ampadu-Kissi

Dynamical Systems

Effect of Parity in Cyclically Competing Communities

Communities exhibiting cyclic (i.e., “winnerless”) competition occur throughout nature. These systems can exhibit qualitatively different long-term behavior depending on the strength of inter-species competition and a specific property of the number of interacting species: parity. We consider how ecological communities can adapt to and transition between an odd and an even number of cyclically competing species. Previous studies have shown that, for strong inter-species competition, odd parity communities are dynamically unstable, while species in even parity communities form stable alliances of maximal noncompeting sets. We trace a homotopy between two May-Leonard type models: the odd parity N=3 model and the even parity N=4 system. We identify all physical steady states and analyze their stabilities. We show the existence of stable transitional states that are unique to our symmetric model. We then use a piecewise linear approximation technique to characterize the stability of heteroclinic cycles. We use numerical simulations to map distinct regimes in parameter space. Our computations confirm our analytical results and also reveal a window in parameter space where limit cycles occur. We illustrate that parity transitions can be complex and characterized by diverse parameter-dependent pathways.
Read the full abstract

All authors T.M. Murdie, D.M. Abrams, A. Bayliss, V.A. Volpert

Optimization and Control · Cross-listed from eess.SY

Comparison of Multisine Peak Factor Minimization Algorithms for Aircraft System Identification

Two phase-optimized multisine peak factor minimization algorithms are presented and evaluated. The first algorithm minimizes peak factor by iteratively clipping the peaks of generated multisine signals. The second algorithm optimizes peak factor indirectly through minimization of an approximation of the infinity norm of the multisine. Algorithm performance was evaluated as a function of different signal properties, including the number of harmonics, harmonic spacing, and number of snow harmonics (extra harmonics included for further reduction of the peak factor). The two algorithms are compared against results obtained by minimizing peak factor directly using a simplex algorithm, which has been a common approach when designing phase-optimized multisines for system identification flight tests. Sample results show that the clipping and infinity norm algorithms produced multisine signals with comparable peak factors that were lower than that of the simplex algorithm. However, the clipping algorithm runs an order of magnitude faster than the other two algorithms, which also makes it practical to repeat the algorithm multiple times to achieve even lower peak factors.
Read the full abstract

Commutative Algebra

Matrix factorization of quotient singularities of type A and D

In this article, we extend the classical relationship between ADE singularities and their maximal Cohen-Macaulay modules to quotient singularities of types A and D. We identify projected hypersurfaces which allow us to construct explicit matrix factorizations, and in return, families of maximal Cohen-Macaulay modules. These hypersurfaces also yield the dual resolution graphs of the corresponding quotient singularities via Oka's method. Finally, we show that all special Cohen-Macaulay modules over the original quotient singularity can be recovered from those over the projected hypersurfaces.
Read the full abstract

Dynamical Systems

Reflective projective billiards in the plane: odd periods, period five, and metric rigidity

We study polygonal projective billiards whose reflection law is constant on each side. We give a single explicit family with an open set of periodic trajectories for every period at least three, including every odd period, and identify the previously known centrally projective examples as a special parameter value. For period five we describe the full scalar-monodromy variety, prove its irreducibility, and show that every configuration preserves a nonzero quadratic form. Under the stated distinct-centre and non-collinearity hypotheses that form is nondegenerate; this yields an explicit unirational classification of the convex five-reflective locus. We also relate the definite members to spherical billiards and prove that, among analytic simply connected constant-curvature surfaces with geodesic walls, only the sphere can carry an open family of periodic trajectories. For general complete analytic ambients with global wall reflections we prove compactness and a common period for the geodesic flow. The arguments reduce the billiard return map to products of harmonic homologies and separate the algebraic closure condition from the strict first-impact inequalities.
Read the full abstract

Complex Variables

Wiman-Valiron inequalities in the unit disk outside sets of finite logarithmic measure

We give affirmative answers to both parts of Question 2.6 posed by Grosse-Erdmann (2025) concerning Wiman-Valiron inequalities in the unit disk. For every unbounded analytic function in the disk, we establish the proposed iterated-logarithm inequalities outside exceptional sets of finite logarithmic measure. The corresponding power estimate is a corollary. Both conclusions follow from a variance bound for Khinchin families and a classical estimate for their largest atom. The multiplicative constants in the main inequalities can be chosen absolute. We also obtain a disk analogue of Rosenbloom's composition estimate, with an explicit boundary prefactor. The key step combines a boundary change of variable with a monotone auxiliary function whose derivative is exactly the variance of a rescaled member of the Khinchin family. A classical example shows that the leading logarithmic exponent $1/2$ cannot be decreased.
Read the full abstract

Combinatorics

Cyclic Latin Eulerian Numbers

We introduce the directed cyclic difference inventory $D_n(\mathbf{m})$ to study Latin Eulerian numbers restricted to row-reorderings of the cyclic Latin square, offering an orientation-sensitive refinement of the prescribed-edge-length Hamiltonian path problem. We establish exact enumeration formulas, symmetries, and realizability obstructions for this inventory. Furthermore, we reduce the cyclic total-ascent statistic directly to endpoint-refined Eulerian statistics via the identity $\Sigma(L_\pi) = n \operatorname{asc}(\pi) + \pi(1) - \pi(n)$, yielding a closed-form expression for the cyclic Latin-Eulerian polynomial.
Read the full abstract

General Mathematics

Parallel Searching Method for Verifying Finiteness of Prime Numbers Presented as Specific Linear Combinations of Factorials

As a new approach to search a counterexample of variants of Kurepa's conjecture, we investigate a parallel searching method of prime numbers $p$ satisfying \begin{eqnarray*} \sum_{k=0}^{p-1} c_k k! \equiv 0 \pmod{p} \end{eqnarray*} for a given integer sequence $(c_k)_{k=0}^{\infty}$. As an application, we prove that there are only finitely may prime numbers of the form $\sum_{k=0}^{n} (1+dk)!$ with $(d,n) \in (\mathbb{N}_{\leq 25} \setminus \{0,8,18,20,23,25\}) \times \mathbb{N}$.
Read the full abstract

Algebraic Topology

On the cobordism groups of $O\langle n\rangle$-manifolds

Given a smooth manifold, a tangential $O\langle n \rangle$-structure is a lift of the classifying map of its tangent bundle to $BO\langle n \rangle$. An $O\langle n \rangle$-manifold is a manifold equipped with an equivalence class of tangential $O\langle n \rangle$-structures. The cases $n=2$ and $n=4$ recover the familiar notions of oriented and spin manifolds. Larger values of $n$ furnish higher analogs of these with additional geometric properties. In this thesis, we calculate the 2-primary component of the cobordism groups of compact $O\langle n\rangle $-manifolds in a range of degrees, for $n$ between 9 and 17. We derive various consequences for the boundaries of almost-closed manifolds.
Read the full abstract

Functional Analysis

New Generalized Dual Banach Frames

This paper presents a comprehensive formulation and a systematic investigation of g-dual Banach frames in a Banach space X and its dual space X?. We study the fundamental structural properties of these frames and establish sufficient conditions for their existence. Furthermore, we explore their relationships with other generalized notions of duality in Banach frame theory. Finally, we investigate the stability of g- dual Banach frames under bounded perturbations, demonstrating their robustness and potential applications in functional analysis.
Read the full abstract

Numerical Analysis

Two-Dimensional Shallow Water Linearized Moment Equations: Hyperbolicity and Well-Balanced Schemes

We study rotational invariance, hyperbolicity, and well-balanced discretization of shallow water linearized moment equations in two horizontal dimensions. Although the direct extension has real characteristic speeds, its directional matrices can lack a complete eigenbasis. We construct a rotationally invariant modification and prove its global hyperbolicity for all states with positive water depth. For quasi-two-dimensional flows over non-flat topography with Navier-slip friction, we develop first- and second-order path-conservative finite-volume schemes that exactly preserve a discrete moving equilibrium constructed by midpoint collocation. Numerical tests confirm equilibrium preservation to roundoff, second-order approximation of smooth stationary branches, and near-second-order accuracy of the second-order scheme for the tested perturbations. Comparisons with three-dimensional two-phase OpenFOAM simulations illustrate the invariant shallow-water limit and show that retaining moments improves the reconstruction of curved rotational velocity profiles, while differences remain in radial motion.
Read the full abstract

Dynamical Systems

Unique ergodicity of hedgehogs

We prove that the dynamics on a non-linearizable hedgehog is uniquely ergodic. This solves a conjecture of the author formulated in 1995. Its unique invariant probability measure is the Dirac mass at the indifferent fixed point. The proof relies on the techniques of quasi-invariant curves and the hyperbolic form of the Denjoy-Yoccoz lemma developed by the author.
Read the full abstract

Optimization and Control

On the Minimum Number of Linear Pieces Required to Approximate Nonlinear Functions under an Accuracy Constraint

The approximation of nonlinear functions by piecewise linear functions is a tool commonly used when dealing with mixed-integer nonlinear problems. Typically, by replacing nonlinearities by piecewise linear functions one can transform the problem into a mixed-integer linear problem, which may be substantially easier to solve. However, using approximate functions can produce solutions that are infeasible for the original problem or far from optimal. To control these errors it is useful to bound the error created during the function approximation process. Moreover, obtaining a piecewise linear function with few pieces usually results in an easier to solve mixed-integer linear problem. This leads us to study the Corridor Fitting Problem. It consists in building a piecewise linear function with the minimum number of pieces which approximates a nonlinear function given a bound on the approximation error on each point of the domain. The Corridor Fitting Problem has primarily been addressed for univariate functions or via heuristic approaches for multivariate functions. Notably, for the latter setting, no exact algorithms or established relaxations are currently known. In this work, we explore this aspect and propose exploitable relaxations of the Corridor Fitting Problem in Rm based on a discretization of the domain. We show that a structure of hypergraph coloring problem is induced by the discretization of the domain. We define four relaxations making use of this hypergraph coloring problem. We provide new best upper bounds for the classical instance set in R2 and we derive the first lower bounds for these instances, closing more than a third of the instances from the literature.
Read the full abstract

Combinatorics · Cross-listed from cs.DM

Packing Tails of Reciprocal Rectangles into Squares of Equal Area

The Meir–Moser rectangle-packing problem asks whether all rectangles with side lengths \(1/n\) and \(1/(n+1)\), for \(n\ge1\), can be packed into the unit square with pairwise disjoint interiors. We establish a tail version of this problem. Let \(R_n\) denote the rectangle with these side lengths. We prove that there exists an integer \(m_0\) such that, for every \(m\ge m_0\), the family \(\{R_n:n\ge m\}\) admits a packing, by translations and right-angle rotations, into a square of side length \(m^{-1/2}\), with pairwise disjoint interiors. The area of the square equals the sum of the areas of all the rectangles. The geometric construction recursively decomposes rectangular gaps, while local randomized quotas and random permutations assign subsequent integer indices. We separately control the total area of waiting gaps and the assignment load at each index. The proof is organized in six steps: a finite-prefix reduction, geometric row decompositions, an area bootstrap, a sharp source-load estimate, control of the actual adaptive construction, and a compactness limit. For every finite time horizon, the probability of failure has a bound that is independent of the horizon and can be made arbitrarily small. The adaptive step uses a permanent load ledger, actual fresh height queries, and a one-sided comparison with a frozen source experiment. Compactness then yields an infinite packing. The final packing statements have been checked in Lean 4. A sufficient threshold is \(m_0=10^{1000}\). This result applies only to sufficiently late tails and does not resolve the original Meir–Moser rectangle-packing problem for the full sequence starting at \(n=1\), which remains open.
Read the full abstract

Probability

Eigenvalue and Eigenvector Approximation for Random Matrices Using Low-Degree Polynomials

We initiate the study of approximating the top eigenvalue and eigenvector of a random symmetric matrix $ A \in \mathbb{R}^{n\times n} $ using $ q(A)b $ where $q$ is a degree-$d$ polynomial and $b$ is a standard Gaussian vector independent of $A$. For spiked GOE $ Y = \lambda vv^\top + X $, we identify $ d_\star = \frac{\log(n)}{2\log(\lambda)} $ to be the critical degree threshold above which accurate approximation of the top eigenvalue and eigenvector is possible. This sharpens the common belief that spectral methods can be implemented by $ O(\log(n)) $-step power iterations and offers a precise connection between spectral methods and low-degree polynomial algorithms, a popular proxy for all polynomial-time algorithms. For GOE $X$, we identify $ d_\star = n^{1/3+o(1)} $ to be the critical degree threshold for top eigenvector approximation, whereas constant degree suffices for top eigenvalue approximation. Moreover, in the limit where $ d/n^{1/3} $ converges to a positive finite constant, we compute the exact asymptotic eigenvector approximation accuracy in terms of the expected squared overlap. These results significantly improve upon predictions made in randomized numerical linear algebra for deterministic data matrices that the iteration count of power methods with random initialization is governed by the inverse spectral gap. Technically, our analyses leverage extremal properties of Chebyshev polynomials and draw upon the rich literature of random matrix theory.
Read the full abstract

General Topology

Primeless proofs of the Menger and Rothberger games

We continue the study of the Menger and Rothberger games on lattices carried out in "Pointless proofs of the Menger and Rothberger games" (Topology Appl. 300 (2021), 107774). This time, we extend the earlier results by dropping some hypotheses that turned out to be unnecessary, and use Stone duality to recover known game characterizations for dense open families. We also give a formulation of $\mathsf U_{\mathrm{fin}}$ for partially ordered sets and prove its game characterization without any lattice assumption. Finally, almost disjoint families give complete distributive lattices on which the selection principles and the corresponding games differ. Dias's results give the lower bounds $\operatorname{cov}(\mathcal M)$ and $\mathfrak d$ for the least sizes of such counterexamples.
Read the full abstract

Group Theory

Heat kernels on Cayley graphs of free products of finite groups

We obtain explicit formulas for heat kernels of the normalized Laplacians for two infinite families of Cayley graphs. The first family corresponds to free products of finite groups $G=G_1*\dots*G_r$, with $r\ge2$, and where all factors $G_i$ have the same order $L\ge2$. The second family corresponds to free products of two arbitrary nontrivial finite groups $G*H$ of unequal order. In both families, the generating set consists of all non-identity elements in each factor. Extending the approach of Chung–Yau, we show that the Cayley graph in each family strongly and regularly covers a weighted half-line and a weighted line, respectively. We solve the spectral problems on the half-line and the line, and then apply spectral transfer principles for strong and regular coverings to derive formulas for the heat kernels on the Cayley graphs. For the first family, the spectrum of the Laplacian consists of a single interval together with, when $L>r$, one additional isolated eigenvalue. When $L=2$, we recover the well-known results for regular trees. For the second family, the spectrum of the Laplacian consists of two intervals and two eigenvalues.
Read the full abstract

Analysis of PDEs

Duality for Garding operators and a new inequality of GM/AM type

This article concerns Garding Dirichlet operators, and also the theory of Garding polynomials. Garding Dirichlet operators are those which arise from homogeneous polynomials on the space S(n) of symmetric $n \times n$ polynomials, which are hyperbolic with respect to any positive definite matrix. (In particular, any polynomial on ${\mathbb R}^n$, which is hyperbolic with respect to elements in $({\mathbb R_+})^n$, gives rise to a Garding operator on S(n), in many ways.) Here a new duality theorem is developed with many special cases and examples. The dual $g^*$ of a Garding operator $g$ is used to prove a new basic inequality for $g$. An important Lemma of Guo-Phong-Tong is improved upon as a final application.
Read the full abstract

Spectral Theory

Transmutation operators for the Sturm–Liouville equation in impedance form with an integrable potential

In this work, we study a family of transmutation operators for the Sturm–Liouville operator in impedance form with an integrable potential satisfying a smallness condition. Specifically, we consider transmutations associated with the pair \[\textbf{L}_r=\frac{1}{r^2 (x)}\frac{d}{dx}r^2 (x)\frac{d}{dx} \quad \text{and} \quad \textbf{M}=\frac{d^2}{dx^2}. \] We extend existing results by showing that a particular transmutation operator on $W^{3,1} (-a,a)$ can be represented in integral form, where the kernel function satisfies a corresponding Goursat problem. We establish the existence of this kernel using two distinct approaches: the classical method of successive approximations and an application of Picard's theorem.
Read the full abstract

Analysis of PDEs

Global solvability of the heat equations in two unbounded domains and the interface

This paper considers the existence of a unique global-in-time strong solution to the heat equations in two unbounded domains $\Omega_A$, $\Omega_B$ and the interface $\Gamma (= \partial \Omega_A \cap \partial \Omega_B)$. We introduce and study some function spaces in the two unbounded domains and the interface. We apply our function spaces and maximal $L^p$-regularity for Hilbert space-valued functions to show the existence of a local-in-time strong solution to our heat equations. By using an energy equality of our heat system, we prove the existence of a unique global-in-time strong solution to the system with large initial data when the slope of the interface is gentle and our parameters are limited. The key ideas for showing the existence of our strong solutions are to transform our system into a system of equations in two half spaces $\mathbb{R}^3_+, \mathbb{R}^3_-$ and the whole space $\mathbb{R}^2$, and to make use of nice properties of the heat semigroups and kernels for $\mathbb{R}^3_+$, $\mathbb{R}^3_-$, and $\mathbb{R}^2$. In Appendix (I), we derive our heat equations in the two unbounded domains and the interface from an energetic point of view. In Appendix (II), we study representation formulas for differential operators on unbounded domains and surfaces.
Read the full abstract

Statistics Theory

Proper scoring rules for survival times

This note presents a general form for a proper scoring rule that can be used for possibly right-censored survival data without requiring any knowledge or assumptions about the censoring process, so long as it is independent of survival time.

2609.28762 · 23 Sep · This is an edited version of an old unpublished 5 page note giving the proof of a result announced, without proof, in Section 3.5 of the paper: A. P. Dawid & M. Musio, Theory and applications of proper scoring rules, Metron, Volume 72, pages 169-183, 2014. It is uploaded to arXiv following several requests that it be made publicly available

Optimization and Control

Fuel-optimal Boost-Back Guidance via Successive Convexification with a Terminal Constraint for ReusableLaunch Vehicles

This paper proposes a fuel-optimal boost-back guidance algorithm for reusable launch vehicles using successive convexification (SCvx). The guidance problem is formulated as a free-final-time optimal control problem with a terminal instantaneous impact point (IIP) constraint. This constraint depends only on the burnout position and velocity and enforces that the predicted ballistic impact point coincides with the target under a spherical-Earth, central-gravity model. By handling the coast analytically, the formulation confines trajectory discretization to the powered phase, reduces the problem size, and explicitly represents the bang-off structure. It also avoids the accumulation of discretization defects over the long coast and the need to resolve the burn-coast transition on a single-phase grid. Two terminal constraint formulations are considered: the closed-form Keplerian IIP and the eccentric-anomaly-based F&G solution. Their Jacobians are evaluated using complex-step differentiation. The algorithm is validated in a return-to-launch-site case study based on the Falcon 9 CRS-10 mission. Comparisons with a single-phase full-trajectory formulation, a closed-form guidance law incorporating the flight path angle rate, and an offline trajectory optimization benchmark assess the trade-off between computational cost and optimality. The results demonstrate near-optimal propellant consumption with reduced computational cost.
Read the full abstract

All authors Mingyeom Kim, Changhyun Kang, Dohyun Lee, Byeong-Un Jo

Combinatorics

Pendant paths and integral generalized sun graphs

A graph is integral if the spectrum of its adjacency matrix consists entirely of integers. We prove that every simple graph having a pendant path with at least three edges has an eigenvalue in $(1,2\cos(\pi/9)]$ and one in $[-2\cos(\pi/9),-1)$, and hence is not integral. This settles a conjecture of Braga, Del-Vecchio and Rodrigues (2021) on integral generalized sun graphs. The argument is matrix-theoretic: adjoining a terminal path on three new coordinates to an arbitrary real symmetric matrix produces the same spectral obstruction, and the positive interval above is optimal in this generality. We then disprove a second conjecture of the same authors, which asserts that the cycle of an integral generalized sun graph other than a cycle has length divisible by four. The graph obtained from a hexagon by attaching $6,6,12,6,6$ pendant vertices to five of its six vertices is integral and has $42$ vertices. We show that it is the smallest member of an infinite family governed by the Pell equation $x^{2}-2k^{2}=-7$, and we compute in closed form the characteristic polynomial of the analogous graphs on an arbitrary even cycle. Integrality within this family forces the cycle to be a square or a hexagon, and the square case yields a second infinite family governed by the Pell equation $k^{2}-2c^{2}=1$.
Read the full abstract

Combinatorics · Cross-listed from cs.CC

Strong NP-Hardness and Approximation Algorithm for Weighted Tardiness with Release Dates and Identical Processing Times

We study nonpreemptive scheduling on a single machine with release dates, due dates, positive job weights, and a common processing time. The objective is to minimize total weighted tardiness. Although closely related equal-processing-time problems admit polynomial-time algorithms, the complexity of this problem has remained open in the literature since 2010. We prove that its decision version is strongly NP-complete, even when every job can meet its due date if processed immediately upon release. The reduction is from unweighted MAX-CUT and uses a quadratic number of jobs with polynomially bounded numerical data. Its main ingredient is a constructive normalization theorem that converts every sufficiently inexpensive feasible schedule into a binary choice for each graph vertex; after normalization, total weighted tardiness equals a constant minus a scaled cut value. We also give a deterministic polynomial-time phase-grid assignment algorithm for the shifted objective $\Phi=F+p\sum_jw_j$, where $F$ is total weighted tardiness. The algorithm enumerates at most $N$ release-date residues modulo $p$, solves one minimum-cost assignment problem for each residue, and returns the best phase-grid schedule. It runs in $O(N^5)$ arithmetic operations and achieves the tight ratio $3/2-1/(2N)$ for this algorithm. Because the added term $p\sum_jw_j$ is independent of how the jobs are scheduled, the shifted and original objectives have exactly the same optimal schedules. However, the approximation guarantee applies to the shifted objective; for the original objective, the analysis provides an additive bound. Thus, the paper both resolves the long-standing complexity question and provides a complementary worst-case guarantee for the phase-grid assignment algorithm.
Read the full abstract

Dynamical Systems

Sterile Insect Technique in a Metapopulation Model. Impact of Network Structure, Male Annihilation Technique and Entomopathogenic Fungi on the Release Strategies

The sterile insect technique (SIT) is a biological control method that reduces insect pest and disease vector populations through the release of sterile insects (in general only males). In this work, spatial aspects are accounted for through an explicit metapopulation model of $n$ interconnected patches. Each patch includes a non-adult stage and adult stages divided into females and males, with distinct dispersal networks for females, wild males, and sterile males. This framework allows to adopt an area-wide integrated pest management perspective. Focusing on the oriental fruit fly, Bactrocera dorsalis, we consider two types of additional control methods, with life stage and sex specificities. These correspond to entomopathogenic fungi soil treatment (EPFST), with a differentiated effect at every life stage; and to the male annihilation technique (MAT), which attracts and kills wild and sterile males. We derive a sufficient condition ensuring elimination of the wild population in all patches, considering either continuous or impulsive periodic release strategies. Under constraints such as the impossibility of releasing sterile males in some patches, we then study an optimisation problem to minimise a weighted sum of the release rates over all release patches to eliminate the wild population. For illustrative purposes, numerical simulations are used to investigate how dispersal network configurations, local conditions, and the simultaneous use of SIT with EPFST or MAT affect optimal release strategies. The main contribution of this work is to identify efficient spatial release strategies for population elimination under practical constraints, in combination with other control methods.
Read the full abstract

Logic

A Randomness Test Formalism for Neutral Measures and Beyond

We discuss in detail Neutral Measures, which are measures which believably generate any real in Cantor space. We intuitively build up the classical notions of randomness, and show that neutral measures do exist, using the language of continuous semimeasures. Finally, we construct some specific randomness tests which allow us to enforce de- sirable properties on neutral measures. As an application, we show the existence of Gibbs measures for a large class of finite range Hamilto- nians on lattice models, and establish their relationship with neutral measures.
Read the full abstract

Information Theory · Cross-listed from cs.LG

Policy Complexity, Reaction Time, and Bounded Rationality in Reinforcement Learning

Biological agents do not learn under conditions of unlimited computation. For humans, learning and choice are shaped by constraints on perception, attention, and working memory, which limit how much state information guides behavior and therefore bound policy complexity. Standard reinforcement learning models typically optimize reward without explicitly representing these internal costs, making them less suitable as models of biological intelligence. We derive MI-SARSA, an on-policy temporal-difference algorithm that incorporates mutual-information regularization through a learned marginal action prior and a penalty on state-specific deviations from that prior. This yields a sequential learning model in which state information is used selectively when its expected return benefit justifies the added informational cost. Critically, the same state-specific information cost that governs policy compression also generates trial-level predictions for reaction time, distinguishing MI-SARSA from most reinforcement learning models, which predict choices or returns but not latency. Empirically, MI-SARSA produces a reward-complexity tradeoff, and stronger information penalties produce simpler policies with lower control costs and faster reaction times. Under environment shift, increasing regularization reduces post-switch performance degradation but also lowers asymptotic return, revealing a robustness-capacity tradeoff. Together, these results position MI-SARSA as a model of bounded sequential learning under cognitive constraints.
Read the full abstract