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)

Tuesday 7 April

Information Theory · Cross-listed from cs.LG

Expectation Maximization (EM) Converges for General Agnostic Mixtures

Mixture of linear regression is well studied in statistics and machine learning, where the data points are generated probabilistically using $k$ linear models. Algorithms like Expectation Maximization (EM) may be used to recover the ground truth regressors for this problem. Recently, in \cite{pal2022learning,ghosh_agnostic} the mixed linear regression problem is studied in the agnostic setting, where no generative model on data is assumed. Rather, given a set of data points, the objective is fit $k$ lines by minimizing a suitable loss function. It is shown that a modification of EM, namely gradient EM converges exponentially to appropriately defined loss minimizer even in the agnostic setting. In this paper, we study the problem of fitting $k$ parametric functions to given set of data points. We adhere to the agnostic setup. However, instead of fitting lines equipped with quadratic loss, we consider any arbitrary parametric function fitting equipped with a strongly convex and smooth loss. This framework encompasses a large class of problems including mixed linear regression (regularized), mixed linear classifiers (mixed logistic regression, mixed Support Vector Machines) and mixed generalized linear regression. We propose and analyze gradient EM for this problem and show that with proper initialization and separation condition, the iterates of gradient EM converge exponentially to appropriately defined population loss minimizers with high probability. This shows the effectiveness of EM type algorithm which converges to optimal solution in the non-generative setup beyond mixture of linear regression.
Read the full abstract

Algebraic Geometry

The Cone Conjecture for Enriques Surfaces in any Characteristic

We give a proof of the Morrison-Kawamata cone conjecture for Enriques surfaces independent of their characteristic. It is based on the analysis of certain generically finite morphisms of degree two.

Algebraic Geometry

Derived Hodge-to-de Rham Degeneration and Quasihomogeneous Curve Singularities

We study the Hodge-completed derived Hodge-to-de Rham spectral sequence of integral projective complex curves. We prove E2-degeneration whenever every singularity is analytically quasihomogeneous, without a local complete intersection (lci) hypothesis. An explicit lci counterexample shows that the converse fails in general. For lci curves, E2-degeneration bounds the total Milnor-Tjurina defect by the dimension of the space of global Kahler one-forms modulo torsion, and hence by the genus of the normalization. This yields a converse for lci curves whose global Kahler one-forms are all torsion, including those with rational normalization. We also establish the converse for locally planar curves. An example with elliptic normalization shows that the numerical defect bound alone is not sufficient for E2-degeneration, even when equality holds.
Read the full abstract

2604.05825 · 7 Apr · 43 pages. Substantially revised. A counterexample disproves the general lci converse claimed in v1; corrected converse statements are established under additional hypotheses. The locally planar characterization remains valid, with a revised proof. The Hochschild-to-cyclic claims have been removed. Junxiao Wang has joined as coauthor, and the title and abstract have been revised

Numerical Analysis

Linear convergence of Gearhart-Koshy accelerated Kaczmarz methods for tensor linear systems

The generalized Gearhart-Koshy acceleration is a recent exact affine search technique designed for the method of cyclic projections onto hyperplanes, i.e., the Kaczmarz method. However, its convergence properties, particularly the linear convergence rate, have not been thoroughly established. In this paper, we systematically establish the linear convergence of the generalized Gearhart-Koshy accelerated Kaczmarz method for tensor linear systems, proving that it converges linearly to the unique least-norm solution. Our analysis is general and applies to several popular Kaczmarz variants, including incremental, shuffle-once, and random-reshuffling schemes, and demonstrates that this acceleration approach yields a better convergence upper bound compared to the plain Kaczmarz method. We also propose an efficient Gram-Schmidt-based implementation that computes the next iterate in linear time. Building on this implementation, we establish a connection between this acceleration framework and Arnoldi-type Krylov subspace methods, further highlighting its efficiency and potential. Our theoretical results are supported by numerical experiments.
Read the full abstract

All authors Yijie Wang, Yonghan Sun, Deren Han, Jiaxin Xie

General Topology

Topological size of the set of universal and ultrahomogeneous retractions on the Urysohn space

In this paper, we investigate the set $\mathcal{U}(\mathbb{U})$ of universal and ultrahomogeneous $1$-Lipschitz retractions acting on the Urysohn space as the subspace of the space $\mathcal{R}(\mathbb{U})$ of all $1-$Lipschitz retractions defined on the Urysohn space. Especially, we study Borel complexity and density $\mathcal{U}(\mathbb{U})$ in $\mathcal{R}(\mathbb{U}).$ In order to do that, we introduce a new extension property $(UR^*)$ that is equivalent to the universality and ultrahomogeneity of a retraction, and a new pointwise retract topology.
Read the full abstract

Optimization and Control

A Posteriori Second-Order Guarantees for Bolza Problems via Collocation

Direct collocation for Bolza optimal control yields discrete Karush-Kuhn-Tucker (KKT) points, while practical solvers expose only discrete quantities such as primal-dual iterates, reduced Hessians, and Jacobians. This creates a gap between continuous second-order optimality theory and what can be certified from solver output. We develop an a posteriori certification framework that bridges this gap. Starting from a discrete KKT solution, we reconstruct piecewise polynomial state, control, and costate trajectories, evaluate residuals of the dynamics, boundary, and stationarity conditions, and derive a computable lower bound for the continuous second variation. The bound is expressed as the discrete reduced curvature minus explicit residual-dependent correction terms. A positive bound yields a sufficient certificate for continuous second-order sufficiency and provides quantitative information relevant to local growth and trust-region sizing. The constants entering the certification inequality are conservatively estimable from reconstructed discrete data. The resulting test is operationally verifiable from collocation outputs and naturally supports adaptive mesh refinement through residual decomposition. We also outline an extension to path inequalities with isolated transversal switches.
Read the full abstract

Geometric Topology

Non-isotopic surfaces in $T^4\#(S^2\times S^2)$: an example

We prove that there exist infinitely many embedded tori with a common geometric dual in $T^4\#(S^2\times S^2)$ that are homotopic, diffeomorphic, but not isotopic to each other, even after arbitrary many external stabilizations. These surfaces are obtained by applying the Norman trick to a fixed immersed surface, using non-homotopic tubing arcs. The isotopy classes of these surfaces are distinguished by homotopy classes of the 2-handles (relative to the boundary) in the complement of the image of the $0$- and $1$-handles.
Read the full abstract

Functional Analysis

Oscillation Functionals and Embeddings in Rearrangement-Invariant Spaces

We study embeddings associated with oscillation functionals in rearrangement-invariant spaces. More precisely, given a positive function \(\psi\), we analyze how the interaction between the geometry of the underlying space and the growth of \(\psi\) determines the behaviour of these embeddings, leading to a natural classification into subcritical, supercritical and critical regimes. We prove that in the critical regime logarithmic refinements of Hansson type appear, governed by a deviation function associated with the quotient \(\psi/\varphi_X\), where \(\varphi_X\) is the fundamental function of the underlying space. This leads to explicit Hansson-type targets and, in the bounded case of the deviation function, to Trudinger-type consequences. The results recover and extend several classical endpoint embeddings.
Read the full abstract

Information Theory

Near-Field Integrated Sensing, Computing and Semantic Communication in Digital Twin-Assisted Vehicular Networks

Digital twin (DT) technology offers transformative potential for vehicular networks, enabling high-fidelity virtual representations for enhanced safety and automation. However, seamless DT synchronization in dynamic environments faces challenges such as massive data transmission, precision sensing, and strict computational constraints. This paper proposes an integrated sensing, computing, and semantic communication (ISCSC) framework tailored for DT-assisted vehicular networks in the near-field (NF) regime. Leveraging a multi-user multiple-input multiple-output (MU-MIMO) configuration, each roadside unit (RSU) employs semantic communication to serve vehicles while simultaneously utilizing millimeter-wave (mmWave) radar for environmental mapping. We implement particle filtering at RSUs to achieve high-precision vehicle tracking. To optimize performance, we formulate a joint optimization problem balancing semantic communication rates and sensing accuracy under limited computational resources and power budget. Our solution includes a hybrid heuristic algorithm for vehicle-to-RSU assignment and an alternating optimization approach for determining semantic extraction ratios and beamforming matrices. Performance is extensively evaluated via the Cramér-Rao bound (CRB) for angle and distance estimation, semantic transmission rates, and resource utilization. Numerical results demonstrate that the proposed ISCSC framework achieves a 20% improvement in transmission rate while maintaining the sensing accuracy of existing integrated sensing and communication (ISAC) schemes under constrained resource conditions.
Read the full abstract

All authors Yinchao Yang, Yahao Ding, Jiaxiang Wang, Zhaohui Yang, Chen Zhu, Zhaoyang Zhang, Dusit Niyato, Mohammad Shikh-Bahaei

Analysis of PDEs

The Navier-Stokes equations in $\mathbb R^2_+$ with point vortex initial data: Zero-viscosity limit

This is the second of two papers devoted to the asymptotic behavior of solutions to the incompressible Navier-Stokes equations in a half-space with point vortex initial data. A major difficulty stems from the interaction between the point vortex initial data and the boundary, which complicates the derivation of a valid asymptotic expansion. To overcome this, we carry out a precise matching between the point vortex and boundary-layer profiles to accurately capture the correct viscous behavior of the vortex in the half-plane. Based on this matched asymptotic analysis, we decompose the vorticity into three components: vorticity near the point vortex, vorticity near the boundary, and vorticity in the transition layer. A key point is that each component must be analyzed in its own distinct region. On this basis, we establish refined estimates and thereby achieve the inviscid limit for the point vortex. Finally, we rigorously prove that solutions to the Navier-Stokes equations converge to the Lamb-Oseen vortex away from the boundary, while approaching the Prandtl boundary-layer system in the near-boundary region.
Read the full abstract

Dynamical Systems

Effective Dynamics and Transition Pathways from Koopman-Inspired Neural Learning of Collective Variables

The ISOKANN (Invariant Subspaces of Koopman Operators Learned by Artificial Neural Networks) framework provides a data-driven route to extract collective variables (CVs) and effective dynamics from complex molecular systems. In this work, we integrate the theoretical foundation of Koopman operators with Krylov-like subspace algorithms, and reduced dynamical modeling to build a coherent picture of how to describe metastable transitions in high-dimensional systems based on CVs. Starting from the identification of CVs based on dominant invariant subspaces, we derive the corresponding effective dynamics on the latent space and connect these to transition rates and times, committor functions, and transition pathways. The combination of Koopman-based learning and reduced-dimensional effective dynamics yields a principled framework for computing transition rates and pathways from simulation data. Numerical experiments on one-, two-, and three-dimensional benchmark potentials illustrate the ability of ISOKANN to reconstruct the coarse-grained kinetics and reproduce transition times across enthalpic and entropic barriers.
Read the full abstract

All authors Alexander Sikorski, Luca Donati, Marcus Weber, Christof Schütte

Dynamical Systems

On the Furstenberg-Katznelson constant for the IP Szemeredi theorem over finite fields

Bergelson et al. observed that Furstenberg's proof of Szemeredi's theorem provides a positive lower bound on the density of arithmetic progressions in sets of positive density in the integers. Namely, for every $\delta\in(0,1]$ and every $k\in \mathbb{N}$, there exists a positive constant $c=c(k,\delta)>0$ such that $$\{n\in \mathbb{N} : d(E\cap (E-n)\cap\dots\cap (E-(k-1)n))>c(k,\delta)\} \neq \emptyset$$ whenever $d(E)\ge \delta$. Similarly, Furstenberg and Katznelson proved the IP Szemeredi theorem, establishing in particular the existence of a constant $c_{\mathrm{IP}}=c_{\mathrm{IP}}(k,\delta)>0$ such that $$\{n\in \mathbb{N} : d(E\cap (E-n)\cap\dots\cap (E-(k-1)n))>c_{\mathrm{IP}}(k,\delta)\}$$ is $\mathrm{IP}^*$ whenever $d(E)\ge \delta$. In this paper, we study analogues of $c$ and $c_{\mathrm{IP}}$ and their ergodic-theoretic counterparts, $c^{\mathrm{rec}}$ and $c_{\mathrm{IP}}^{\mathrm{rec}}$, for vector spaces over finite fields. We provide a qualitative result and in special cases such as Roth's theorem and the IP-Roth theorem, we also provide strong quantitative bounds for these constants. Our tools are primarily ergodic theoretic; we study the characteristic factors and limit of multiple ergodic averages along $\mathrm{IP}$s in vector spaces over finite fields.
Read the full abstract

Analysis of PDEs

The Navier-Stokes equations in $\mathbb R^2_+$ with point vortex initial data: construction of the solution

This is the first of two papers concerning the asymptotic behavior of the incompressible Navier-Stokes equations in a half-space at high Reynolds numbers, with initial data given by a point vortex. In the present work, we establish the existence and uniqueness of solutions subject to the non-slip boundary condition. This result was established in \cite{Ken} under the condition that the total mass is sufficiently small. Here, we eliminate the smallness assumption by analyzing the linearized operator near the point vortex and constructing a tailored functional framework-one designed to capture the distinct behaviors of the solution in the vicinity of the point vortex and the boundary, respectively.
Read the full abstract

Probability

The volume of hyperbolic Poisson zero cells: critical divergence and exact second moment

We investigate the second volume moment of the zero cell $Z_o$ of a Poisson hyperplane tessellation with intensity $\gamma$ in the $d$-dimensional hyperbolic space. We focus on the phase transition at the critical intensity $\gamma_c^{(d)}$, the minimum value for which $Z_o$ is almost surely bounded. In the critical regime $\gamma=\gamma_c^{(d)}$, we show that the second volume moment of the restricted zero cell $Z_o \cap B_R$, where $B_R$ is a hyperbolic ball of radius $R$ centred at $o$, diverges in any dimension at the universal rate $R^3$ as $R \to \infty$. In the supercritical case $\gamma > \gamma_c^{(d)}$, we prove that the full second volume moment is finite. Using tools from harmonic analysis in hyperbolic space, we derive an exact expression for this moment in terms of the Meijer $G$-function. Furthermore, we determine the asymptotic behaviour of the second moment as $\gamma \to \infty$ and as $\gamma \downarrow \gamma_c^{(d)}$, facilitating a direct comparison with the corresponding Euclidean values as well as the mean-field universality class of percolation theory.
Read the full abstract

Group Theory

Universal Fibonacci sequences and UFS-groupoids

In a binary groupoid $(G, *)$, a Fibonacci sequence is a recurrent sequence defined by $f_1 = a, f_2 = b, \ldots, f_n = f_{n - 2} * f_{n - 1}$. A universal Fibonacci sequence (UFS) is a singly or doubly infinite sequence whose set of suffixes coincides precisely with the set of all Fibonacci sequences in the groupoid. This paper studies UFS-groupoids, i.e., groupoids that admit a universal Fibonacci sequence. It is shown that every nontrivial UFS-groupoid is at most countable, locally cyclic, and non-power-associative; that the right cancellation property and the right quasigroup property hold for all pairs of elements except possibly one and two, respectively; that no neutral element or zero element exists; and that there is at most one idempotent element. It is proved that any UFS-groupoid whose universal Fibonacci sequence is not doubly infinite strictly preperiodic is cyclic. It has also been proved that the class of UFS-groupoids is closed under taking subgroupoids and homomorphic images, but is not closed under finite direct products. The structure of subgroupoids of UFS-groupoids is described. A complete classification of UFS-groupoids is given in terms of the cardinality of $G$ and the periodicity of the universal Fibonacci sequences. Finite UFS-groupoids are described combinatorially via de Bruijn sequences. The number of distinct UFS-groupoids on a finite set is determined, and explicit constructions are provided for both finite and infinite cases across all periodicity classes, including embeddings of UFS-groupoids as subgroupoids into other UFS-groupoids and infinitely generated UFS-groupoids.
Read the full abstract

Classical Analysis and ODEs

From curvature to Kovacic: a geometric approach to integrability of scalar ODEs

We study first-order ordinary differential equations such that the intrinsic Gauss curvature of the associated surface depends only on the independent variable: $\mathcal{K}(x,u)=\kappa(x)$, showing that this geometrically motivated class of equations admits a threefold connection to the second-order linear operator $L=d^2/dx^2+\kappa(x)$: the divergence along every solution satisfies a Riccati equation that linearizes to $L(y)=0$; every solution of the first-order equation satisfies the non-homogeneous equation $L(u)=c(x)$; and solutions of $L(y)=0$ give rise to integrating factors for the original nonlinear equation. By means of differential Galois theory, we prove that the nonlinear equation is integrable by quadratures if and only if $L$ admits a non-zero Liouvillian solution; when $\kappa$ is rational, Kovacic's algorithm provides a complete decision procedure.
Read the full abstract

Mathematical Physics

Analytic exact solutions to the nonlinear Dirac equation

We present analytic exact solutions to the nonlinear Dirac equation: they display a ring singularity for the Nambu–Jona-Lasinio nonlinearity and a shell singularity for the Soler nonlinearity. For both cases, the size of the singular region is of the order of the Compton length. General comments about square-integrability will be addressed in terms of a solution to the linearized system.
Read the full abstract

Category Theory

On the decomposition of a strong epimorphism into regular epimorphisms

Strong epimorphisms and regular epimorphisms are two important classes of morphisms, and they do not coincide in general. Yet, in a locally presentable category, it is known that any strong epimorphism can be decomposed into a transfinite composite of regular epimorphisms. In this paper, we provide two syntactic methods to determine how many regular epimorphisms are needed in such a decomposition, using partial Horn theory and generalized algebraic theory. We start by discussing a general problem of decomposing a morphism into a transfinite composite of morphisms in a given class, which also covers the decomposition of an adjoint functor into monadic functors.
Read the full abstract

Algebraic Geometry

Stability of syzygy bundles of Ulrich bundles

Let X be either a smooth K3 surface or a smooth Fano variety (i.e. $-K_X$ is ample) of dimension $n$ and index $i_X> n-3$ and let E be an initialized Ulrich bundle on X. In this paper, we show that the syzygy bundle $S(E)$, defined as the kernel of the evaluation map $H^0(X,E)\otimes O_{X}\rightarrow E$, is semistable.
Read the full abstract

Number Theory

On Iwasawa theory of abelian varieties over $\mathbb{Z}_p^2$-extension with applications to Diophantine stability and integally Diophantine extensions

We present certain results on the Iwasawa theory of an abelian variety with potentially good ordinary reduction at all primes above $p$. These are then applied to study Diophantine stability and integally Diophantine extensions. Along the way, we also obtain some results pertaining to Mazur growth conjecture which refine previous results of Gajek-Leonard, Hatley, Kundu and Lei. Finally, we extend our investigation to the case of an elliptic curve with good supersingular reduction at the prime $p$ and make a similar analysis.
Read the full abstract

Number Theory

Small gaps between consecutive zeros of the Riemann zeta-function

In this paper, we introduce the resonance-correlation method to study small gaps between consecutive zeros of the Riemann zeta-function. Our method is based on a synthesis of Montgomery's pair correlation approach and the Montgomery-Odlyzko method. As an application, we break the persistent practical barrier around $0.515$ and prove $\mu < 0.50895$ under the Riemann Hypothesis.
Read the full abstract

Group Theory

An improved characterisation of inner automorphisms of groups

We show that every group $G$ embeds malnormally into a simple, complete co-Hopfian group $H$. This implies that a non-trivial endomorphism of $G$ extends to $H$ if and only if it is an inner automorphism, strengthening a theorem of Schupp and answering a question of Bergman.

Numerical Analysis

On convergence of residual-based extended randomized Kaczmarz methods for matrix equations

In this paper, for solving inconsistent matrix equations we propose a dual-space residual-based randomized extended Kaczmarz method and its version with Nesterov momentum. Without the full column rank assumptions on coefficient matrices, we provide a thorough convergence analysis, and derive upper bounds for the convergence rates of the new methods. A feasible range for the momentum parameters is determined. Numerical experiments demonstrate that the proposed methods are much more effective than the existing ones, especially the method with momentum.
Read the full abstract

All authors Wendi Bao, Jing Li, Lili Xing, Weiguo Li, Jichao Wang

Dynamical Systems · Cross-listed from q-bio.PE

Mathematical Models of Evolution and Replicator Systems Dynamics

This is an edited English version of the authors' monograph "Mathematical Models of Evolution and Replicator Systems Dynamics", posted on arXiv as a single document to which chapters are added as they are completed; the present version contains Chapters 1-4. The book develops a unified mathematical framework for evolutionary processes in the spirit of generalised Darwinism, built on replicator systems. It covers the derivation and asymptotic analysis of replicator equations, hypercycles and other canonical replicator systems, the Eigen and Crow-Kimura quasispecies models and the error threshold, the geometry of the fitness surface and its relation to trajectory dynamics and evolutionarily stable states, and a model of evolutionary adaptation in which the fitness landscape itself evolves on a slow time scale, including the incorporation of new species arriving at random moments. Analytical results are complemented by numerical experiments on hypercyclic, bi-hypercyclic, anthill and RNA network systems.
Read the full abstract

2604.05720 · 7 Apr · Consolidated English edition of the authors' monograph, posted as a single growing document. This version contains Chapters 1-4 with a cover page and table of contents; it supersedes the separately posted chapter preprints arXiv:2605.05385 (Chapter 2) and arXiv:2607.04456 (Chapter 3), which are being withdrawn

Numerical Analysis

Robust H(curl)-based finite element methods for the incompressible MHD system

We propose and analyze a class of finite element methods for the time-dependent incompressible magnetohydrodynamics system based on $H(\mathrm{curl})$-conforming discretizations for both the velocity and the magnetic field. This choice is guided by the aim of developing methods that are also suitable for the types of solutions arising in problems posed on nonconvex domains. Within this framework, we introduce three stabilized formulations, and study how the stabilization mechanisms employed influence their structural properties. In particular, we focus on suitability for nonconvex polyhedral domains, the need for Lagrange multipliers for the magnetic field, pressure-robustness, and quasi-robustness with respect to both the fluid and magnetic Reynolds numbers. The proposed formulations are further assessed through numerical experiments, highlighting their practical performance.
Read the full abstract

All authors Lourenço Beirão da Veiga, Sergio Gómez, Ilaria Perugia, Enrico Zampa

Dynamical Systems

Bohr chaoticity, semi-horseshoes and full-entropy abundance

Bohr chaoticity is a topological notion of dynamical complexity defined through non-orthogonality to all non-trivial weights. It is strictly stronger than positivity of topological entropy and also has strong consequences for the invariant-measure structure. In this paper, we show that every dynamical system having a semi-horseshoe, including every positive-entropy graph map and every $C^1$ partially hyperbolic diffeomorphism, is Bohr chaotic; furthermore, the set of points correlated with any given non-trivial weight has positive topological entropy. Moreover, for positive-entropy dynamical systems with either the shadowing property or the modified almost specification property, such set can has full topological entropy. Our results also yield applications in several classical algebraic and smooth settings, as well as in the $C^0$-generic setting of topological dynamics.
Read the full abstract

Information Theory

Foundations of Future Communication Systems: Innovations in Communication - A Report

The Foundations of Future Communication Systems (FFCS) conference brought together leading researchers from information theory, quantum communication, molecular communication, semantic communication, and secure network design to explore the fundamental principles shaping next-generation communication systems. The event serves as a platform for interdisciplinary exchange, bridging classical Shannon theory, post-Shannon paradigms, quantum information science, and emerging physically grounded communication models. This report compiles the abstracts of all invited talks, contributed presentations, and poster contributions presented at FFCS. The collected works reflect the breadth of contemporary research directions, including identification-based communication, entanglement-assisted networks, semantic and goal-oriented communication, coding for molecular and nanoscale systems, secure authentication mechanisms, and information-theoretic limits of novel physical-layer architectures. A central theme of the conference was the re-examination of foundational limits under realistic physical, architectural, and security constraints. Many contributions move beyond traditional rate-centric perspectives and instead investigate reliability, identification, semantics, resource efficiency, and trust in complex and heterogeneous networks. The inclusion of poster abstracts further highlights emerging ideas, early-stage research results, and innovative cross-disciplinary approaches that contribute to shaping future communication paradigms. By documenting the intellectual landscape presented at FFCS, this report aims to provide a structured overview of current research frontiers and to stimulate continued collaboration across theoretical and experimental domains.
Read the full abstract

All authors Christian Deppe, Eduard Jorswieck, Pin-Hsun Lin, Vida Gholamian, Marcel A. Mross

Information Theory

The Incidence-Multiplicity Bound for Linear Exact Repair in MDS Array Codes

We study linear exact repair for $(n,k,\ell)$ MDS array codes over $\mathbb{F}_q$, with redundancy $r=n-k$, in the regime where $q$, $r$, and $\ell$ are fixed and the code length $n$ varies. A recent projective counting argument gives a general lower bound on repair bandwidth and repair I/O in this setting. While this bound is attained over a broad interval of code lengths in the two-parity case, it is not attained once $r\ge 3$ and $\ell\ge 2$. In this paper, we refine the counting argument behind this bound and establish a sharper lower bound, which we call the incidence-multiplicity bound. We prove that for every $(n,k,\ell)$ MDS array code over $\mathbb{F}_q$ with $r\ge 2$, both the average and worst-case repair bandwidth, as well as the average and worst-case repair I/O, are at least $$\ell(n-1)-(r-1)\frac{q^\ell-1}{q-1}.$$This bound agrees with the earlier projective counting bound when $r=2$, and is strictly stronger for every $r\ge 3$. We also show that the incidence-multiplicity bound is sharp in a broad parameter range. Assume that $\ell\ge 2$, $r\ge 2$, $(r-1)\mid(q-1)$, and $(q-1)/(r-1)\ge 2$. Then for every integer $n$ satisfying $$2(r-1)\frac{q^\ell-1}{q-1}\le n\le q^\ell+1,$$ there exists an $(n,n-r,\ell)$ MDS array code over $\mathbb{F}_q$ that attains the incidence-multiplicity bound simultaneously for both repair bandwidth and repair I/O. These codes arise from field reduction of a normal rational curve. Together, these results reveal incidence multiplicity as the governing geometric principle for linear exact repair in MDS array codes beyond the two-parity case.
Read the full abstract

Combinatorics

Tree-partitions and small-spread tree-decompositions

Tree-decompositions and treewidth are of fundamental importance in structural and algorithmic graph theory. The "spread" of a tree-decomposition is the minimum integer $s$ such that every vertex lies in at most $s$ bags. A tree-decomposition is "domino" if it has spread 2, which is the smallest interesting value of spread. So that spread 1 becomes interesting, one can relax the definition of tree-decomposition to "tree-partition", which allows the endpoints of each edge to be in the same bag or adjacent bags, while demanding that each vertex appears in exactly one bag. Ding and Oporowski [1995] showed that every graph $G$ with treewidth $k$ and maximum degree $\Delta$ has a tree-partition with width $O(k\Delta)$. We prove the same result with an improved constant, and with the extra property that the underlying tree has maximum degree $O(\Delta)$ and $O(|V(G)|/k\Delta)$ vertices. This result implies (with an improved constant) the best known upper bound on the domino treewidth of $O(k\Delta^2)$, due to Bodlaender [1999]. Moreover, solving an open problem of Bodlaender, we show this upper bound is best possible, by exhibiting graphs with domino treewidth $\Omega(k\Delta^2)$ for $k\geqslant 2$. On the other hand, allowing the spread to be a function of $k$, we show that width $O(k\Delta)$ can be achieved. This result exploits a connection to chordal completions, which we show is best possible, a result of independent interest.
Read the full abstract

All authors Marc Distel, Neel Kaul, Raj Kaul, David R. Wood

Numerical Analysis

Discrete Mean Field Games on Finite Graphs as Initial Value Optimization

In this paper, we propose an initial value fomulation of the discrete mean field games on finite graphs (Graph MFG), and design a neural network based approach to solve it. Graph MFG describes infinite, non-cooperative and interactive homogeneous agents move on node states through the edges to optimize their own goals. Nash Equilibrium of the Graph MFG is characterized by a coupled ordinary differential equations (ODE) system, including the discrete forward continuity equation and the discrete backward Hamilton-Jacobi equation. In this paper, we mainly focus on the potential mean field games (Potential MFG) on finite graphs, which has an infinite-dimensional constrained optimization structure. We reformulate Potential MFG as an initial value finite-dimentional optimization problem with dynamics constrains, names Graph MFG-IV. Specifically, the initial condition of the Hamilton-Jacobi equation is regarded as the unique variable, constrained by the coupled Hamilton-Jacobi and continuity equation system as the ODE integrator. This formulation is a reduced-order model, which avoids time-discretization of the infinite-dimensional path and has a much smaller searching space than the general path-wise problem setting. We design a neural network-based approach to solve the Graph MFG-IV problem.
Read the full abstract