Peer Revenue Publish or profit

Papers

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

Mathematics

math Watch Mathematics (sign in to use)

Sunday 27 September

Differential Geometry

Yet Another Family of Complex Structures on $S^6$

Following a similar path as the recent construction of a complex structure on $S^6$ we construct another such family, disjoint from the known ones.

Optimization and Control

Accelerated Consensus and Decentralized Optimization over Slowly Varying Networks

We study average consensus over slowly time-varying networks and its application to decentralized optimization. We introduce WAVE, a windowed Chebyshev method that limits the accumulated effect of network variation by restarting the recurrence after finite windows. If $\chi$ bounds the network condition number and successive communication operators satisfy $\|L_{k+1}-L_k\|\leq\beta$, WAVE reaches $\epsilon$-consensus in $O((\sqrt{\chi}+\min\lbrace\beta\chi^2,\chi\rbrace)\ln(e/\epsilon))$ communication rounds. This rate matches the fixed-network $\sqrt{\chi}$ dependence when $\beta=O(\chi^{-3/2})$ and smoothly interpolates across the full range of network variation. For piecewise-constant networks where each change is detected when it occurs and consecutive changes are at least $\tau$ rounds apart, WAVE reaches $\epsilon$-consensus in $O((\sqrt{\chi}+\chi/\tau)\ln(e/\epsilon))$ communication rounds. Finally, we use WAVE as the consensus step in an accelerated decentralized optimization method for $\alpha$-smooth convex local objectives with a $\mu$-strongly convex average. For sufficiently slow network variation, every agent obtains an $\epsilon$-solution to the global optimization problem after $\widetilde O(\sqrt{\alpha/\mu}\,\sqrt{\chi})$ communication rounds, matching the fixed-network dependence.
Read the full abstract

All authors Darina Dvinskikh, Anton Novitskii, Demyan Yarmoshik, Alexander Rogozin, Vladislav Matyukhin, Alexander Gasnikov

Number Theory

Omega bound for the Piltz divisor problem

We obtain improved omega bounds for the error term in the Piltz divisor problem over number fields. Our proof combines Lamzouri's resonance argument with a counting theorem for nonnegative multiplicative functions. The counting theorem gives the estimates needed for the divisor coefficients over a number field and allows us to remove the factor involving the third iterated logarithm from the earlier bounds.
Read the full abstract

Combinatorics

Orthogonal and unitary signings of cube-like graphs

A unitary signing of a $d$-regular graph is a Hermitian adjacency matrix $M$ whose nonzero entries lie in $\{\pm1,\pm i\}$ and satisfies $M^2=dI$. Motivated by the work of Alon and Zheng on orthogonal and unitary signings of cube-like graphs, we introduce the $\Theta$-property for a generating set $S\subseteq\mathbb Z_2^n$: whenever three pairwise disjoint subsets of $S$ have the same sum, at least two of them have even size. We prove that every zero-free generating set with the $\Theta$-property gives a cube-like graph $Q_S$ admitting a unitary signing, and we give an explicit local formula for such a signing. For Sidon sets, the $\Theta$-property is also necessary, yielding a characterization of the Sidon cube-like graphs that admit unitary signings. In this setting there are exactly $2^{|S|-n}$ switching-equivalence classes of unitary signings, and we characterize when a unitary signing can be chosen to be orthogonal. The $\Theta$-property admits a linear-algebraic description in terms of the dependency space $\mathcal D$ of $S$: \[ |D_1\cap D_2| \equiv |D_1||D_2| \pmod2 \qquad (D_1,D_2\in\mathcal D). \] Equivalently, the map \[ D\longmapsto \binom{|D|}{2}\pmod2 \] is linear on $\mathcal D$. For the corresponding extremal set problem, in which zero is permitted, this formulation yields the sharp bound $|S|\leq 2n+1$ for generating sets with the $\Theta$-property. We give elementary constructions attaining this bound for every $n\geq3$. Under the additional Sidon condition, the same extremal value is attained for every $n\geq10$ using binary self-dual codes. The exact Sidon maximum is also determined for $3\leq n\leq9$.
Read the full abstract

Mathematical Physics · Cross-listed from quant-ph

Quantum data processing equality

The quantum data processing inequality asserts that quantum relative entropy is monotonically non-increasing under quantum channels. Here, we promote this fundamental inequality to an exact equality via boundary and surface Poisson integral representations across a complex strip. The relative-entropy loss is resolved into two independent, nonnegative physical mechanisms: an operational Petz recovery component governing state reconstructibility, and a boundary term measuring the mismatch of relative modular dynamics. We further express the loss as the measured relative entropy between the original state and its averaged Petz recovery state plus a nonnegative variational remainder. For the Belavkin–Staszewski (BS) loss, analogous integral representations yield a decomposition into negative log Uhlmann fidelity with an averaged reconstruction plus a nonnegative variational remainder. Furthermore, we establish recovery bounds at any prescribed modular parameter, including the canonical unrotated Petz map, with optimal square-root scaling in the relative entropy loss. The prefactors depend on distinct-eigenvalue counts or logarithmic spectral quantities, improving upon the inverse-power dependence on small eigenvalues in previous bounds.
Read the full abstract

Optimization and Control

Annealed Sinkhorn with Momentum: Certified Unregularized Optimal Transport in Linear Memory

We characterize Bregman Douglas-Rachford splitting (BDRS) for unregularized discrete optimal transport and develop an anytime primal-dual certificate in linear memory. We first establish that BDRS coincides with warm-started Inexact Proximal point method for exact Optimal Transport (IPOT) using a single inner Sinkhorn iteration. By eliminating the primal transport plan from the updates, we derive an equivalent dual formulation that reveals BDRS as annealed Sinkhorn under an implicit inverse-linear temperature schedule, with an additional log-scaling momentum term and a cooler kernel. While this explains the role of the temperature parameter in BDRS as an initial temperature, it also reduces the solver's memory requirement from quadratic to linear. Utilizing this annealing perspective, we introduce overrelaxed BDRS, which combines annealing and overrelaxed scaling within a single recursion. We derive a primal-dual certificate for both methods that can be evaluated in linear memory without transport plan construction, thus providing a computable stopping rule. On the DOTmark benchmark, combining momentum with the cooler kernel produces substantially smaller optimality gaps than annealed Sinkhorn under the same schedule. For pixel-level color transfer between $1024\times1024$ images, BDRS attains a lower repaired transport cost than MDOT-TNT with a 9$\times$ speed up, reaching a relative duality gap of $1.59\%$ in 24 minutes. We further demonstrate a color transfer with $4238\times2365$ images, yielding 10 million pixels per image and approximately one hundred trillion implicit transport entries, reaching a best relative duality gap of $2.41\%$ and $2.80\%$ within 35 hours in each direction on a single NVIDIA L40S GPU.
Read the full abstract

Algebraic Geometry

Perfectoidness of Proper Shimura Varieties With Limpid Integral Models

We prove that any proper Shimura variety admitting a limpid integral model in the sense of Madapusi Pera becomes a perfectoid space at infinite level at $p$. Our method provides a new geometric approach that circumvents the need for a universal abelian scheme, making it applicable beyond Shimura varieties of Hodge type. Inspired by Scholze's proof of the perfectoidness of the Siegel modular variety, we construct analogues of the canonical subgroup and the anticanonical tower within a strict neighborhood of the ordinary locus. To achieve this we utilize the geometry of the universal $G$-aperture over the limpid integral model. Because every Shimura variety admits a limpid integral model for sufficiently large primes, our result implies that all proper Shimura varieties are globally perfectoid at infinite level for big enough primes.
Read the full abstract

Analysis of PDEs

Logarithmic Bramson correction for Fisher–KPP equations on homogeneous trees

In this paper, we study the Fisher–KPP equation \[ \partial_t u = \alpha\Delta_{\TT_{q+1}}u+\beta u(1-u), \] on the homogeneous \((q+1)\)-regular tree \(\TT_{q+1}\), with \(q\geq2\), for nontrivial, compactly supported radial initial data. We first obtain an explicit representation of the fundamental solution of the corresponding linearized problem, together with sharp two-sided pointwise estimates. These estimates identify the propagation threshold \[ \beta>\alpha(\sqrt q-1)^2 \] and determine the associated critical speed \(c_\ast\) and decay rate \(\lambda_\ast\). In this regime, we prove that, for every fixed \(\theta\in(0,1)\), the outermost \(\theta\)-level set satisfies \[ \kappa_\theta(t) = c_\ast t-\frac{3}{2\lambda_\ast}\log t+O(1), \qquad t\to\infty. \] Therefore, while the branching geometry affects the threshold for propagation and the values of the critical parameters, the classical Bramson factor \(3/2\) persists. Our results therefore extend classical propagation and logarithmic-delay phenomena, previously known for one-dimensional continuous and discrete Fisher–KPP models, to homogeneous trees.
Read the full abstract

All authors Edagardo Álvarez, Marina Murillo-Arcila, Rodrigo Ponce, Juan C. Pozo

Analysis of PDEs

Maximal Regularity and Existence for Superquadratic Parabolic Hamilton–Jacobi Equations: The Endpoint case

We establish interior maximal $L^{q_c}$-regularity for bounded strong solutions of $u_t-\Delta u+|Du|^\gamma=f$ in $\mathbb{T}^d\times(0,T)$, where $d\geq 2$, $\gamma>2$, and $q_c=(d+2)(\gamma-1)/\gamma$. The estimates are uniform for uniformly bounded families of solutions whose source terms range over a bounded, uniformly equi-integrable subset of $L^{q_c}$. The main difficulty is the possible concentration of the critical gradient energy. We overcome it through a two-scale blow-up argument: the first scale produces a small Hamiltonian coefficient, while energy normalization at the second scale yields strong endpoint compactness, allowing a parabolic Liouville theorem to rule out concentration. The resulting uniform little-Hölder estimate, combined with critical Gagliardo–Nirenberg interpolation, permits absorption of the nonlinear term in the parabolic Calderón–Zygmund estimate. As an application, we construct bounded strong solutions for $f\in L^{q_c}$ and continuous initial data $u_0$, and prove subsequential strong interior convergence of smooth approximations in $W^{2,1}_{q_c}$.
Read the full abstract

Number Theory

Higher-order colossally abundant numbers

Colossally abundant numbers have large sums of divisors relative to their size. They also admit a geometric description using supporting lines of a planar convex hull. Starting from this description, we change coordinates to obtain nested subsets of these numbers, which we call colossally abundant numbers of higher order. Their definition does not depend on the Riemann hypothesis. We give conditions under which Robin's inequality holds on any one of these subsets if and only if the Riemann hypothesis is true. Some of the resulting families have infinite sets at every level but an empty intersection. For two classes of coordinates, we determine how fast the least members grow. We also prove that every fixed positive integer divides all members of sufficiently high order. Under a concavity assumption, the least members form a divisibility chain; for power abscissas, successive quotients have unbounded numbers of prime factors, with an explicit limsup growth rate. In a second class of families, every global maximum of the normalized divisor sum is retained, and the least members tend to infinity if and only if the Riemann hypothesis is true. We give numerical examples and explain how the Ramanujan–Nicolas bounds produce terminating chains.
Read the full abstract

Number Theory

Rank stability of elliptic curves over $\mathbb{F}_q(t)$ in residue classes

Fix a prime $\ell$. Let $K = \mathbb{F}_q(t)$ be a global function field such that $\gcd(q,6) = 1$ and $q \equiv 1 \pmod \ell$. Let $E$ be a non-isotrivial elliptic curve over $K$. Given a fixed monic polynomial $Q$ over $\mathbb{F}_q$, and assuming some mild conditions on $E$, we show that the rank of $E$ does not change with respect to a positive proportion of $\mathbb{Z}/\ell \mathbb{Z}$ extensions $K(\sqrt[\ell]{f})/K$, as $f$ varies over the set of monic polynomials over $\mathbb{F}_q$ such that $f \equiv A \pmod Q$ for any given polynomial $A$. We obtain this result by combining analytic and probabilistic techniques to study the distribution of certain prime Selmer groups of auxiliary abelian varieties constructed from these polynomials $f$.
Read the full abstract

Differential Geometry

Instability and Morse Index of Exponentially Subelliptic Harmonic Maps

Let $M$ be a closed manifold with a bracket-generating distribution $H$. We study the Morse index of exponentially subelliptic harmonic maps. After establishing finiteness, we estimate the index through two test spaces. The extrinsic one averages the index form over projected ambient parallel frames, reducing the estimate to a trace identity involving an extrinsic scalar with a quartic exponential term. The intrinsic one uses parallel sections of the pullback bundle, on which the index form descends to a coupled quadratic form that is exact when a global parallel frame exists. The bounds apply to round spheres, products of spheres, and convex hypersurfaces. On a closed Heisenberg nilmanifold, the intrinsic reduction yields a spectral formula for the index.
Read the full abstract

Dynamical Systems

Moments of the Cross-Sectional Siegel-Veech Transform

We study the Siegel–Veech transform on the Poincaré section for the horocycle flow consisting of lattice surfaces with a visible horizontal holonomy vector of length at most one. We compute its first moment and derive formulas for higher and factorial moments with respect to the section's induced ergodic invariant probability measure, which is not supported on a periodic orbit. We emphasize these formulas in the case of the square torus of unit area and, as an application, use its first-moment formula to recover the Boca–Zaharescu pair-correlation density for Farey fractions.
Read the full abstract

Algebraic Geometry

A two-parameter family of complex structures on $S^6$

We construct a two-parameter family of complex structures on the standard six-sphere, starting from a rational elliptic surface with singular fibers $III^*,I_1,I_1,I_1$. The resulting torus fibration over $\mathbb{P}^1$ has one multiple fiber of multiplicity four, one hexagonal fiber, and two rank-one degenerations. These complex structures are not biholomorphic to the original Alpöge–Claude examples.
Read the full abstract

Algebraic Geometry

Equivariant Riemann-Roch for Surfaces via Connections and Residues

Let $X$ be a smooth projective surface over $\mathbb{C}$ with an effective action of a finite group $G$, and let $L$ be a $G$-linearized line bundle. We develop a residue-theoretic and birational approach to computing the equivariant Euler characteristic $\chi_G(X,L)$. Every such $L$ admits an equivariant divisor presentation. Divisor peeling applies the divisor exact sequences one layer at a time, treating whole $G$-orbits of components together. It reduces the problem to the structure sheaf and lower-dimensional equivariant contributions. On a resolution of $X/G$, the natural extensions of the isotypic direct-image sheaves preserve Euler characteristics, but their induced connections need not be logarithmic, as an explicit $D_4$ calculation shows. Blowing up fixed points before taking the quotient reduces the local calculation to diagonal actions and cyclic Hirzebruch-Jung singularities. We obtain explicit correction class functions for the ADE singularities and a uniform procedure for general diagonal actions, including quasi-reflections. In the diagonal case, the natural extensions are logarithmic, and their residues are computed from monomial valuations on the Hirzebruch-Jung resolution. Combining these residue calculations with the branch-curve terms and divisor peeling gives a procedure for computing the equivariant Euler characteristic of every $G$-linearized line bundle. We compare the local classes with the holomorphic Lefschetz formula and the Kleinian coefficients of Lim and Rota, and give examples on $\mathbb{P}^2$, including one with fixed curves.
Read the full abstract

Analysis of PDEs

Scattering for Short-Range Mass-Subcritical Choquard Equations

We study scattering for the defocusing inhomogeneous generalized Choquard equation with data in the conformal energy space. In the full short-range mass-subcritical regime, a key estimate for the nonlinear term yields scattering in \(L^2\). A pseudoconformal argument in the compactified variables then gives scattering in \(H^1\). In the homogeneous case, estimates based on the Galilean vector field further imply scattering in \(\Sigma\) above the Strauss threshold. The method avoids the additional algebraic restrictions arising from intermediate Strichartz-Sobolev estimates.
Read the full abstract

Probability

Invariant Manifolds and Stability for Singular SPDEs

We study the long-time dynamics of a class of singular stochastic partial differential equations with multiplicative Gaussian noise. Using the theory of regularity structures, we construct the associated random dynamical system and establish an ergodic framework for the underlying random models. Combining pathwise estimates for the singular equation with a multiplicative ergodic theorem in Banach spaces, we analyse the Lyapunov spectrum of the linearized dynamics and establish the existence of local stable, unstable, and center invariant manifolds around stationary points. As a consequence, when the linearized equation is exponentially stable, we obtain a local exponential stability result for the nonlinear equation.
Read the full abstract

Number Theory

The two-block odd partition function

We investigate arithmetic and combinatorial properties of the function $a(n)$, which is the signed number of partitions of $n$ into exactly two distinct part sizes, each occurring an odd number of times. We prove that $a(n)\ge 0$ for all $n$, establishing a positivity phenomenon for a signed partition function arising from a double Lambert series. Furthermore, we show that $a(n)$ satisfies nontrivial divisibility properties modulo $3$. The results reveal unexpected arithmetic regularity in a family of partition functions defined by odd multiplicity constraints and restricted support.
Read the full abstract

Number Theory

Necessary and sufficient condition for reciprocal polynomials to be monogenic

Let $\mathbb{Z}_K$ denote the ring of integers of the number field $K=\mathbb{Q}(\theta)$, where $\theta$ is a root of a monic irreducible polynomial $f(x)\in\mathbb{Z}[x]$. We say that $f(x)$ is monogenic if $\mathbb{Z}_K=\mathbb{Z}[\theta]$. A polynomial $f(x)\in\mathbb{Z}[x]$ is called reciprocal if $f(x)=x^{\deg(f)}f(1/x)$. In this article, we establish necessary and sufficient conditions for the monogeneity of reciprocal polynomials. As an application, we obtain an alternative and much simpler proof that the maximal real subfields of cyclotomic fields are monogenic.
Read the full abstract

Group Theory

Analytic, geometric and measured aspects of lamplighter-like groups

In this thesis, we study finitely generated groups close to wreath products, all defined as semi-direct products, from various perspectives. The first main result is a quasi-isometric classification of some permutational wreath products. The strategy we follow relies on recent work of Genevois and Tessera, but yields a stronger rigidity phenomenon: under suitable assumptions, a quasi-isometry between two permutational lamplighters always induces a quasi-isometry of pairs between the base groups equipped with the corresponding normal subgroups. We also show that, in some specific cases, being quasi-isometric is equivalent to being bijectively quasi-isometric. A chapter is also dedicated to the study of standard wreath products whose lamp groups have polynomial growth. We establish a rigidity result for quasi-isometries between such wreath products: they must all be {\guillemotleft}measure-scaling{\guillemotright}. In particular, self-quasi-isometries of such wreath products all lie at bounded distance from bijections. We also prove that this class of lamplighters provides examples of amenable quasi-isometric groups that are not bijectively quasi-isometric. The second part of this thesis relies on joint works with Corentin Correia, in which we study halo products of Genevois and Tessera from a measured point of view. We construct orbit equivalence couplings between two halo products of the same kind and, using the recent technology of Folner tilings, we exhibit couplings between halo products and free abelian groups. We also establish several asymptotic estimates of the isoperimetric profiles of these groups, improving previous results of Erschler-Zheng and Saloff-Coste-Zheng. These computations allow us to prove that, in many cases, the orbit equivalence couplings thus obtained are quantitatively optimal.
Read the full abstract

Information Theory

Concurrent Coded Signal-Multiplexing Ranging for Half-Duplex Asynchronous Networks

Signal-multiplexing network ranging (SM-NR) shares broadcasts across node pairs, but its sequential operation leads to a ranging cycle that grows linearly with network size. This paper proposes a concurrent coded SM-NR (CC-SM-NR) framework for asynchronous half-duplex networks. Firstly, the CC-SM-NR protocol coordinates concurrent transmissions through binary transmit-listen codewords. The transmit-listen schedule defined by these codewords ensures reciprocal observations subject to a finite concurrency limit. Then, we derive the exact minimum number of transmit-listen rounds without a concurrency limit, which reveals that the minimum grows logarithmically with network size. To account for practical scenarios, we establish the necessary and sufficient conditions for the constant-weight feasibility of codewords under a finite concurrency limit. Subsequently, we propose a low-complexity scheduling algorithm that achieves the minimum round count within the constant-weight codeword class. To support higher observation redundancy, this scheduling design is extended through a greedy construction. Finally, simulation results demonstrate the effectiveness of the proposed schemes for network ranging.
Read the full abstract

Combinatorics

The Fibonacci numbers are not 3-accessible

A $D$-diffsequence is a sequence of integers $x_1 < \dots < x_k$ such that $x_{i+1} -x_i \in D$ for $1 \le i \le k-1$. The set $D$ is called $r$-accessible if every $r$-coloring of the positive integers contains arbitrarily long monochromatic $D$-diffsequences. This note proves that the set of Fibonacci numbers is not 3-accessible, resolving an open problem of Landman and Robertson from 2007.
Read the full abstract

Combinatorics

A quasipolynomial inverse theorem for the $\mathsf{U}^k(\mathbb{F}_p^n)$ norm in the high characteristic

We prove an inverse theorem for the Gowers uniformity norm $\mathsf{U}^k(\mathbb{F}_p^n)$ with quasipolynomial bounds in the case when $p \geq k$. The inverse theorem follows from a quasipolynomial structure theorem for Freiman multihomomorphisms, which are a natural generalization of Freiman homomorphisms to maps of several variables. The proof of the structure theorem for Freiman multihomomorphisms is the central result of the paper and rests on three main ingredients: algebraic regularity method, abstract Balog-Szemerédi-Gowers theorem and the theory of multilinear maps defined on multilinear varieties. The last ingredient originates from an earlier work of Gowers and the author, and is significantly expanded in this paper. In particular, once the theory of such maps is in place, the proof of the structure theorem for Freiman multihomomorphisms is relatively short, especially compared to the previous quantitative results in the inverse theory of Gowers norms.
Read the full abstract

Combinatorics

Strong $q$-log-convexity of the $d$-Hoggatt polynomials

In this paper, three ($q$-)log-convexity or concavity properties related to the $d$-Hoggatt numbers are investigated. First, we show that the $d$-Hoggatt transformation preserves the log-convexity of a sequence. We then establish the strong $q$-log-concavity of a $q$-analog of $d$-Hoggatt numbers. Finally, we prove the core result of this work, namely, the sequence of $d$-Hoggatt polynomials is strongly $q$-log-convex, based on the theory of Schur functions.
Read the full abstract

Information Theory

A proof of the Braun-Etzion-Vardy bound for binary subspace codes

The notion of a linear subspace code in a projective space was introduced by Braun, Etzion and Vardy (2013), who conjectured that a linear subspace code in the projective space has at most 2^n codewords. We resolve this conjecture. A novel character-theoretic argument is used to prove the conjecture and the proof is self-contained.
Read the full abstract

Combinatorics

A note on three-quarters circulant digraphs

We introduce and study a new family of circulant digraphs associated with the cyclic group $\Z_N$, obtained by restricting admissible combinations of two generators $a$ and $b$ to three coordinate sectors. The resulting distance-like function differs from the standard directed distance in circulant digraphs and gives rise to new geometric and combinatorial phenomena. Using planar lattice representations and periodic tessellations, we analyze the growth of reachable sets and derive Moore-type upper bounds for the corresponding order/diameter problem. We construct explicit infinite families of three-quarters circulant structures with the prescribed diameter and provide lattice-based methods for determining admissible generator pairs. Separate constructions are obtained for even and odd diameters. In addition, computational experiments for small and moderate orders suggest improved families for even diameters and motivate a conjectural asymptotic formula for the maximum attainable order. The paper highlights the interplay between constrained lattice representations, periodic tilings, and extremal problems for circulant networks.
Read the full abstract

Algebraic Geometry

Obstructions to the ampleness of invariant jet differentials on complete intersections

We introduce the analogue, for invariant jet differentials, of the principal symbol of a differential operator: the component of maximal degree in the highest derivative. The top symbol identifies a canonical quotient bundle of the Demailly–Semple bundle $E_{k,m}T^*_X$, with values in jet differentials of lower order, and together with the Brückmann–Rackwitz vanishing theorem it gives a non-ampleness criterion for $E_{k,m}T^*_Z$ on complete intersections $Z\subset\PP^N$. On the Demailly–Semple tower the top symbol is the restriction to a thickening of the vertical divisor, inside the singular jets. The criterion applies in orders $3$ and $4$: $E_{3,5q}T^*_X$ is not ample on any smooth hypersurface $X\subset\PP^4$, and $E_{4,m}T^*_X$ is not ample for $m\ge7$ with $m\equiv0,1,2\pmod 7$ on any smooth hypersurface $X\subset\PP^5$ of degree at least $2$. This contradicts the Diverio–Trapani conjecture at its own threshold.
Read the full abstract

2609.33710 · 27 Sep · v2: 36 pages (14 more than v1!). Substantially revised. The Genesis (Section 1), which some readers seem to have enjoyed, now ends on a more optimistic note. New Section 3: the principal symbol of a jet differential and a general non-ampleness criterion (Thm 3.8) of which the main theorems are instances; new Prop 9.2 (E_{3,8} not ample); corrections throughout. Comments very welcome!

Combinatorics · Cross-listed from cs.LO

Flip-packability: uniform characterisations of tame graph classes

A class of graphs is monadically dependent if one cannot encode all graphs in coloured graphs from the class using a fixed first-order formula, and monadically stable if one cannot even encode arbitrarily long linear orders. Bonnet et al. (ICALP 2025) characterised monadic dependence by flip-separability: for every vertex weighting, boundedly many flips - complementations of the adjacency relation within a vertex subset - make every ball of radius $r$ carry at most an $\varepsilon$-fraction of the weight, so that every set carrying an $\varepsilon$-fraction has two elements pulled apart. We introduce flip-packability: boundedly many graphs, each obtained from the input by boundedly many flips and all determined by the weighting before any set is presented, such that every set carrying an $\varepsilon$-fraction of the weight has $m$ elements pairwise far apart in one of them. The number of flips producing each graph depends on the radius alone; only the number of graphs depends on $\varepsilon$ and $m$. We prove that a class of graphs is flip-packable if and only if it is monadically stable, and $2$-flip-packable, that is, flip-packable with $m=2$, if and only if it is monadically dependent. The passage from two scattered elements to $m$ is thus exactly what separates the two notions. For monadically stable classes we show that the flipped graphs can be computed from the weighting in cubic time. Varying the three parameters of the definition - the sparsifying operation, the radius, and the number $m$ of elements scattered - produces eight known characterisations of sparse and dense graph classes from the same template. In each case $m$ separates a depth-like notion from its width-like relaxation: treedepth from treewidth, shrubdepth from cliquewidth, and monadic stability from monadic dependence.
Read the full abstract

Information Theory

Non-Adaptive Learning of Sparse Erdős–Rényi Graphs via Affine Splitting

Graph learning from edge-detecting queries concerns the reconstruction of an unknown edge set on a known vertex set. Each query reports whether a specified vertex subset contains at least one edge. We study non-adaptive schemes, in which all queries are fixed before any outcomes are observed, with the goal of achieving exact recovery using few queries and fast decoding. For general graphs on $n$ vertices with at most $k$ edges, non-adaptive recovery requires $\Omega(\min\{k^2\log n,n^2\})$ queries in the worst case, even when a small error probability is allowed. In this paper, we consider Erdős–Rényi ($\mathrm{ER}$) graphs $G\sim \mathrm{ER}(n,q)$, with expected edge count $\bar{k}=q\binom{n}{2}$. Our scheme uses $O(\bar{k}\log n)$ queries and achieves exact recovery in $O(\bar{k}\log n)$ decoding time with probability tending to one throughout the regime $\bar{k}\to\infty$ and $\bar{k}=o(n^2)$. This improves the previous $O(\bar{k}^{1+\delta}\log n)$ decoding guarantee for any fixed $\delta>0$, while maintaining the same query order. The guarantee also extends beyond the previously studied regime $\bar{k}=\Theta(n^{2\theta})$ with fixed $\theta\in(0,1)$. Our approach builds on the binary splitting method used in prior work, which organizes vertices into a hierarchy of successively smaller groups. We introduce three main changes: (i) we use random affine hash functions over a finite field to process each candidate pair in constant time; (ii) we apply the splitting procedure directly to the full graph, avoiding the need to combine solutions to multiple smaller graph-learning subproblems; and (iii) we bound the total decoding workload directly rather than deriving separate high-probability bounds on candidate counts at each level.
Read the full abstract

Number Theory

Cyclotomic factors and irreducibility of the denominators of $q$-deformed rational numbers

For $d\ge2$ the $q$-deformed modular group specialized at a primitive $d$-th root of unity is the triangle group of type $(2,3,d)$. Using this we determine the fractions $r/s$ for which the $d$-th cyclotomic polynomial divides the denominator $S_{r/s}(q)$ of the $q$-deformed rational number $[r/s]_q$. They form the orbit of $\infty$ under the normal closure of the translation $z\mapsto z+d$ in $\mathrm{PSL}(2,\mathbb{Z})$. This proves a conjecture of Byakuno, Ren and Yanagawa, and shows that the congruences $s\equiv0$ and $r\equiv\pm1$ modulo $d$ characterize the divisibility exactly for $d\le5$. For $a\in\{2,3,4,6\}$ and $n>5a^2$ prime to $a$ we show that $S_{a/n}(q)$ is irreducible up to cyclotomic factors. Together with a computer check for small primes, this confirms a conjecture of Kogiso, Ren, Wakui, Yanagawa and the author for every prime $p$ and every $r$ prime to $p$ with $r\equiv\pm a$ or $ar\equiv\pm1\pmod p$.
Read the full abstract