Combinatorics
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Sunday 11 October
For a $k$-uniform hypergraph $L$, let $h_L(n,q)$ be the minimum number of copies of $L$ in an $n$-vertex $k$-graph with $\mathrm{ex}(n,L)+q$ edges. Let $t_L(n,q)$ be the minimum number of copies obtained by adding $q$ edges to an extremal $L$-free $k$-graph. A graph is color-critical if deleting a suitable edge decreases its chromatic number. Let $\mathcal K_k(F)$ be the expanded graph obtained by adding $k-2$ new vertices to each edge of $F$, with disjoint sets of new vertices for distinct edges. Mubayi proved that, for every clique $K_r$ with $r\ge4$ and fixed $ q>0$, $ h_{\mathcal K_3(K_r)}(n,q)\ge qt_{\mathcal K_3(K_r)}(n,1)$ for every sufficiently large $n$. Pikhurko and Yilma later proved that, for every color-critical graph $F$, there is a constant $\epsilon_F>0$ such that $h_{F}(n,q)=t_{F}(n,q)$ for every sufficiently large $n$ and $1\le q\le\epsilon_F n$. We extend this equality to expanded color-critical graphs. Let $d>k\ge3$. For every color-critical graph $F$ with $\chi(F)=d+1$, there is a constant $\epsilon>0$ such that $ h_{\mathcal K_k(F)}(n,q)=t_{\mathcal K_k(F)}(n,q)$ for every sufficiently large $n$ and $1\le q\le\epsilon n^{k-1}$. Let $q_L(n)$ be the largest integer $q$ such that $h_L(n,s)=t_L(n,s)$ for every integer $1\le s\le q$. We give a sufficient condition for $q_L(n)=\Theta_L(n^{k-1})$ and an explicit family satisfying it. We also give a different sufficient condition under which $q_L(n)=\Omega_L(n^{k-1/2})$. \noindent Keywords. Supersaturation; extremal graph; color-critical graph; chromatic number; expanded graph; hypergraph.
Category Theory
A categorical approach to the set-theoretic Yang-Baxter equation
We investigate set-theoretic solutions of the Yang–Baxter equation from a categorical perspective. The paper has two main objectives. On the one hand, several existing constructions and classification results in the literature are recast in categorical terms, thereby showing that certain hypotheses previously imposed on such solutions are in fact superfluous. On the other hand, the categorical approach leads naturally to new classes of Yang-Baxter solutions. Our approach consists in identifying suitable subcategories of the category $\mathcal{YB}$ of Yang-Baxter solutions and providing categorical characterisations of the solutions they encode. As an application, we prove that the category of Płonka bi-magmas is isomorphic to the subcategory of $\mathcal{YB}$ consisting of solutions of the Baaj-Long-Skandalis equation. Along the way, we introduce and study a new class of Lyubashenko type solutions and examine the extent to which non-degenerate bijective solutions of the braid equation arise from skew left braces.
Read the full abstract
Quantum Algebra
Type $B$- and $C$- trigonometric weight functions
We introduce and study trigonometric weight functions of type $B$ and type $C$ arising from integrable lattice models. These functions give $q$-deformations of the factorial $K$-theoretic Schur $P$- and $Q$-functions of Ikeda and Naruse, with the $P$-functions specialized to the type $B$ case. We realize them as specializations of partition functions of a six-vertex model with triangular boundary conditions and derive their algebraic properties using the Yang-Baxter equation and properties of the $R$- and $K$-matrices. We introduce normalized weight functions and establish diagonal evaluation formulas, divisibility properties, and bounds on Newton polytopes analogous to those in type $A$, together with recursive relations and stability. We further derive branching formulas relating these functions to type $A$ weight functions, and prove equal-cardinality orthogonality and all-cardinality biorthogonality relations.
Read the full abstract
Group Theory
Three-point orbits of 2-transitive groups and their combinatorial applications
Let $G$ be a finite $2$-transitive permutation group. We determine the orbits of $G$ on the unordered triples of its point set, together with the three-point stabilizer and its image inside $S_3$, for every affine and almost simple family in the finite $2$-transitive classification. These data classify the $G$-invariant triple systems and the simple $2$-\mbox{$(v,3,\lambda)$} designs admitting $G$, and yield in a uniform way the standard objects attached to them: the incidence and block graphs (with arc-transitivity and strong regularity in the Steiner case), the constant-weight and design codes, and the Schurian coherent configurations on triples.
Read the full abstract
Optimization and Control
Cyclic steepest descent is $R$-superlinearly convergent for almost every initialization on two-spectrum quadratics
We completely classify cyclic steepest descent (CSD) on strictly convex quadratics whose Hessian has exactly two distinct eigenvalues. At the beginning of each cycle CSD recomputes an exact steepest-descent stepsize and reuses it for $m$ updates. For every $m\ge2$, write $A=aP+bQ$ with $0<a<b$ and spectral projectors $P,Q$. For nonzero spectral blocks, let $r=\|Pg\|_2/\|Qg\|_2$ at a cycle boundary. The exact projective dynamics is $r^+=r^{1-2m}$. Hence the nonzero equal-norm cone $\|Pg_0\|_2=\|Qg_0\|_2>0$ is precisely the nonterminating exceptional set: there the convergence is $R$-linear with factor $(b-a)/(b+a)$, whereas every other nonterminating initialization is $R$-superlinear and one-eigenspace initializations terminate in one step. The exceptional cone has Lebesgue measure zero, so $R$-superlinear convergence holds almost everywhere in this two-spectrum class. The main results of this paper were obtained through a generative-AI workflow using OpenAI GPT-5.6 Sol, Anthropic Claude Fable 5, and OpenAI GPT-6 Astra. Further details appear in the disclosure at the end of the paper.
Read the full abstract
Information Theory
New Minimum Storage Regenerating Codes With Small Sub-packetization Levels for All Admissible Repair Degrees
In this paper, {we propose a new family of $(n, k)$ Minimum Storage Regenerating (MSR) codes} for distributed storage systems. By structuring the parity-check matrix as a block Vandermonde matrix composed of diagonal matrices and generalized permutation matrices, the proposed code achieves a sub-packetization level of $N = (d-k+1)^{\lceil\frac{n}{2}\rceil}$ and supports any repair degree $k+1\le d<n$. A key innovation of the new construction lies in relaxing the strict commutativity condition previously required for the building blocks in the parity-check matrices of Ye-Barg codes. We introduce a novel proof technique to establish the MDS property without relying on full commutativity, thereby generalizing the applicability of block Vandermonde matrices and enriching the family of Ye-Barg codes. Additionally, the sparsity of the parity-check matrix enhances encoding and decoding efficiency by reducing computational complexity. This work provides new insights into the construction of MSR codes.
Read the full abstract
Differential Geometry
A note on the Chern-Yamabe flow on compact Hermitian manifolds with negative Gauduchon degree
In this note, we prove that on a compact Hermitian manifold with negative Gauduchon degree, the Chern-Yamabe flow introduced in our recent work [13] converges to the solution of prescribed Chern scalar curvature problem, provided that the candidate curvature function is nonpositive and not identically zero.
Read the full abstract
Operator Algebras
Quadratic polynomials preserving free infinite divisibility
We characterize non-commutative polynomials of degree 2 which preserve free infinite divisibility as self-adjoint Lie polynomials of degree 2. This extends previous results which characterized homogeneous quadratic forms only. The proof is based on an involution of colored noncrossing partitions cancelling many terms; positive definiteness of the remaining terms is established by an explicit operator model on Fock space. Examples show that higher order Lie polynomials do not preserve free infinite divisibility.
Read the full abstract
Number Theory
Non-vanishing of primitive cubic, quartic and sextic L-functions
We establish lower bounds for the non-vanishing proportions of primitive cubic, quartic and sextic Dirichlet $L$-functions over $\F_q[T]$ in the non-Kummer setting. Adapting the truncated-exponential method of Gao and Zhao, we improve the cubic lower bound of David, Florea and Lalín and obtain positive lower bounds for quartic and sextic families in which every ramified local character has full order. For each family, the lower limit of the non-vanishing proportion exceeds $e^{-e^{66}}$ as the conductor degree tends to infinity with $q$ fixed. We also establish uniform twisted first moments in the quartic and sextic cases, yielding an asymptotic formula for the sextic first moment. All results are unconditional.
Read the full abstract
Number Theory
Counting Rational Points on a Certain Bihomogeneous Threefold
Let $V\subset\mathbb P^2\times\mathbb P^2$ be the threefold $x_0y_0^2+x_1y_1^2+x_2y_2^2=0$, and let $U$ be the complement of its coordinate hyperplane sections. For the anticanonical height $H([\mathbf x],[\mathbf y])=|\mathbf x|^2|\mathbf y|$, evaluated on primitive integral representatives, we prove \[ N_U(B)=\frac{12\pi-14}{\zeta(2)\zeta(3)}B\log B+o(B\log B). \] The two projections combine lattice counting with uniform conic estimates. The main arithmetic step is an average of the fiber singular series, whose two main terms are related by Hilbert reciprocity. A moment estimate controls the full bad-prime part, and shape estimates permit the errors to be summed over the height region. We also check the leading constant with Peyre's constant.
Read the full abstract
Analysis of PDEs
Global solutions to the fully nonlinear obstacle problem
In this paper, we investigate global solutions to the fully nonlinear obstacle problem. We prove that, after factoring out invariant directions, the coincidence set of any global solution belongs to one of the following four types: a single point, a compact convex set with nonempty interior, a ray for $n=1$, or a slender body for $n\geq 2$, where $n$ denotes the spatial dimension. Furthermore, we establish a bijection between the collection of all global solutions with compact coincidence sets and a family of functions describing the asymptotic behavior of such solutions at infinity.
Read the full abstract
Differential Geometry
Alexandrov–Fenchel inequalities for closed axisymmetric hypersurfaces
We establish sharp Alexandrov–Fenchel inequalities for closed, embedded, axisymmetric hypersurfaces Sigma in n+1 dimensional Euclidean space R^{n+1}, the dimension n > or = 2, with admissible C^{1,1} profiles. Let H_j be the j-th normalized mean curvature. If Sigma is axiconvex, i.e., every hyperplane orthogonal to the symmetry axis meets the enclosed domain in an n-dimensional ball or empty, then \[\left(\frac{\int_\Sigma H_\ell\,dA}{|\mathbb S^n|}\right)^{1/(n-\ell)} \le \left(\frac{\int_\Sigma H_k\,dA}{|\mathbb S^n|}\right)^{1/(n-k)}, \qquad 0\le\ell<k\le n-1. \] Without axiconvexity, the inequalities hold for sign-corrected integrals \[\int_\Sigma\varepsilon_\theta^{\,j}H_j\,dA,\] where varepsilon_{theta}= {sgn}(sin {theta}) denotes the sign of the azimuthal principal curvatures. As applications, the Alexandrov–Fenchel inequalities remain valid whenever both l and k are even. Equality in each of the above inequalities holds if and only if Sigma is a round sphere. The proof adapts the rearrangement and tangent angle folding approach of Dalphin-Henrot-Masnou-Takahashi from surfaces of revolution in R^3 to n-dimensional axisymmetric hypersurfaces in R^{n+1}. The higher-dimensional construction uses weighted monotone rearrangement to produce convex comparison bodies with C^{1,1} boundaries.
Read the full abstract
Information Theory
Rydberg Atomic Quantum Receivers for OFDM Systems: An Atomic-Comb Design
Rydberg atomic quantum receivers (RAQR) exhibit exceptional sensitivity to radio-frequency (RF) signals, positioning them as promising candidates for next-generation wireless systems. Extending their capabilities to orthogonal frequency-division multiplexing (OFDM), however, requires atomic responses that go beyond broadband reception and are tailored to the structured interference of multicarrier signals. To bridge this gap, we develop an atomic-comb Rydberg receiver based on six-wave mixing (SWM) transduction. In particular, injecting a multi-tone local oscillator (LO) into the RAQR generates frequency-shifted replicas of the intrinsic SWM response. By subtly tuning the amplitude and phase of each LO tone, constructive and destructive interference can be selectively induced to preserve desired response components while attenuating harmful frequency offsets. Furthermore, we harness the response-reshaping capability of the proposed atomic comb to proactively mitigate OFDM interference. More explicitly, by exploiting the discrete difference-frequency structure of both carrier-frequency-offset (CFO)-induced and phase-noise (PN)-induced inter-carrier interference (ICI), we optimize the atomic-comb response to suppress dominant ICI components directly. We further reveal an intrinsic coupling between spectral shaping and the time-domain effective channel memory, motivating a joint optimization of both ICI and inter-symbol interference (ISI), which simultaneously suppresses inter-carrier leakage and post-cyclic-prefix (CP) tail energy. Extensive simulation results validate our atomic-comb design, unveiling that the proposed atomic comb can effectively reshape the receiver response over the OFDM, while mitigating ICI, shortening the effective channel memory, and substantially lowering CP overhead.
Read the full abstract
Complex Variables
Quaternionic Elasticity Theory with Local Fractional Derivatives
We develop a quaternionic formulation of linear elasticity in which the classical derivative is replaced by Yang's local fractional derivative and the classical Cauchy–Riemann operator by a fractal Cauchy–Riemann operator. We formulate fractal kinematics, a constitutive law with a material length scale and the equilibrium equation, and show that, for displacement fields with polynomial components, the resulting homogeneous fractal Lamé system is equivalent to the monogenicity of an explicit quaternionic field. On the polynomial sector, that is, for finite combinations of normalized fractal monomials, we prove a fractal Kolosov–Muskhelishvili representation of the displacement field in terms of two monogenic quaternionic potentials, together with its completeness, by a direct construction that uses neither the Galerkin nor the Papkovich–Neuber potentials. The position term of the classical formula has to be replaced by a corrected position operator, which satisfies the exact Weyl relation with the partial local fractional derivatives. Finally a fractal Papkovich-Neuber representation is derived.
Read the full abstract
Combinatorics
A note on the logarithmic exponent of Ramsey number $r(4,t)$
In this short note, we point out that the recent lower bounds for off-diagonal Ramsey numbers $r(s,t)$ with fixed $s\ge 5$, together with the recent proof of the Ajtai–Erdős–Komlós–Szemerédi independence conjecture, imply \[ r(4,t)=\frac{t^3}{(\log t)^{2+o(1)}}. \] This note is solely for informal circulation and will not be submitted for publication.
Read the full abstract
Number Theory
Amplified moments and a refinement of the quasi-Riemann hypothesis
Recently, OpenAI announced a uniform $7/8$ zero-free half-plane for finite-order Hecke $L$-functions over $\mathbb{Q}(\sqrt{-3})$, together with its transfer to Dirichlet $L$-functions. Assuming the analytic inputs of that work, we improve the boundary from $7/8=0.875$ to $8748867/10000000=0.8748867$ for the same families. The improvement combines a relaxed direct estimate with an amplified first moment of the reflected numerator, obtained from the existing fourth-moment estimate. A two-stage parameter argument yields the stated boundary without strengthening the inverse-moment estimate.
Read the full abstract
Number Theory
The Norm Spectrum of Barnes-Wall Lattices Below Twice the Minimum
Let $\Lambda_m$ be the Barnes-Wall lattice of dimension $2^m$, normalized to have minimum squared norm $d_m:=2^{m-1}$. We determine its complete norm spectrum strictly between $d_m$ and $2d_m$, proving that, for every integer $m\ge1$, $\{\|x\|^2:x\in\Lambda_m,\ d_m<\|x\|^2<2d_m\}=\{2d_m-2^j:j\in\mathbb Z,\ \lceil m/2\rceil\le j\le m-2\}$. In particular, the norm spectrum in this interval is nonempty for $m\ge4$. The proof uses a Gaussian-integer model in which lattice automorphisms arising from Clifford unitaries transform a vector into a pair of coordinate subvectors in a lower-dimensional lattice. Divisibility of the differences of their squared norms and a matrix Parseval identity provide the arithmetic and averaging constraints needed for induction on $m$. Every listed norm is realized explicitly by a sum of two minimal vectors of the lattice.
Read the full abstract
Differential Geometry
On the Structure of the Cut Locus in Certain Classes of Warped Product Manifolds
In this paper, we determine the structure of the cut locus for a class of complete warped product manifolds $M=(R^1\times S^1,dt^2+m(t)^2d\theta^2)$, where the warping function $m(t)$ is positive and even, under the assumption that there exists a positive number $t_1$ such that the Gaussian curvature is nonpositive on the domain $t^{-1}\left((t_1,\infty) \right)$ and is decreasing along the subarc $t^{-1}([0,t_1])\cap\theta^{-1}(0)$ of the upper half meridian.
Read the full abstract
Representation Theory
Unipotent quotients in compactified Coxeter varieties
In this paper, we extend Lusztig's description of quotients of Coxeter varieties by unipotent radicals of parabolic subgroups, to quotients of certain open neighbourhoods in the smooth compactification of Coxeter varieties. These quotients are products of an affine space with a Coxeter variety for an associated Levi quotient, and this result holds uniformly for any connected reductive group over a finite field. As an application, we prove a conjecture of Wang computing the invariants, under the action of unipotent subgroups, of the cohomology of the Deligne-Lusztig coverings of Coxeter varieties. We also prove that derived Alvis-Curtis duality sends the compactly supported cohomology of these coverings to their ordinary cohomology.
Read the full abstract
Algebraic Geometry
A note on stability conditions on product-quotient surfaces
Let $X$ be a product-quotient surface, which is by definition a minimal resolution of $(C_1\times C_2)/G$, where $C_i$ are smooth curves of genus $\geq 2$ and $G$ is a finite group. When $G$ acts freely, we show that every product Bridgeland stability condition on $C_1\times C_2$ induces a tilt stability condition on $X$, and that, if $p_g(X)=q(X)=0$, every tilt stability condition on $X$ arises this way. When $(C_1\times C_2)/G$ has only $A_1$-singularities, we use induction \cite{MMS} and derived McKay correspondence \cite{BKR} to produce non-geometric stability conditions $\sigma_X$ on $X$, which satisfy the full support property and lie in the closure of the geometric chamber. Whether $\sigma_X$ also lies in the closure of the $\widetilde{\mathrm{GL}}^+(2,\mathbb{R})$-orbit of the tilt stability conditions depends on a single inequality, $\omega_X^2 \ge n/8$, where $n$ is the number of $A_1$-singularities. When it fails, the geometric chamber is strictly larger than this orbit.
Read the full abstract
Analysis of PDEs
Nonexistence of Stable Solutions to Lane–Emden Equations on Graphs with Polynomial Volume Growth
We study stable solutions of the Lane–Emden equation $$-\Delta u=|u|^{p-1}u$$ on graphs with polynomial volume growth. Due to the lack of a chain rule in the discrete setting, we establish suitable algebraic inequalities which serve as substitutes for the usual differential identities. Combining these inequalities with the stability condition and cutoff arguments, we obtain nonexistence results for stable solutions in a range of exponents analogous to the Joseph–Lundgren range. As an application, we derive a lower bound for the Sobolev best constant in the discrete setting.
Read the full abstract
Probability
Weighted moments and sharp convergence rates for supercritical multitype branching processes
Let $Z_n^i=(Z_n^i(1),\cdots,Z_n^i(d)), n\geqslant0$, be a supercritical $d$-type branching process starting from a single particle of type $i\in\{1,\cdots,d\}$, where $d$ is a positive integer. The Kesten-Stigum theorem states that if the mean matrix $M$ of the offspring distribution has spectral radius $\rho>1$ with the associated positive left and right eigenvectors $u$ and $v$, then for all $1\leqslant i \leqslant d$, the sequence $W_n^i=\langle Z_n^i,u\rangle/\rho^n u(i)$ forms a non-negative martingale, and hence converges almost surely to a random variable $W^i$ as $n\rightarrow\infty$. In this paper, we investigate the asymptotic properties of the martingale $\{W_n^i\}$, focusing on weighted moments and sharp rates of convergence. We establish necessary and sufficient conditions for the finiteness of $\phi$-moments of $W^i$, where $\phi(x)=x^{\alpha}\ell(x)$ with $\alpha\geqslant1$ and $\ell$ is a positive function slowly varying at infinity. We also determine the sharp exponential rate of convergence of $W_n^i$ to $W^i$ in the $\phi$-moment sense, identify a phase transition at the critical rate $\rho^{1/2},$ and characterize the behavior at the critical value. Our proofs rely on the double martingale structure of the fundamental martingale and on convex inequalities for martingales.
Read the full abstract
Statistics Theory
Optimal detection of geometry in random graphs and kernel matrices at critical thresholds
Detection of geometry in random graphs and matrices has been extensively studied in recent years. For testing a dense random geometric graph on $n$ vertices with latent points in dimension $d$ against an Erdős–Rényi graph, the detection threshold $d\asymp n^3$ is well known since Bubeck, Ding, Eldan, and Rácz (2016). We sharpen this result by establishing the optimal asymptotic testing error in the critical regime $d/n^3\to\lambda\in(0,\infty)$. The log-likelihood ratio is shown to be asymptotically normal and dominated by the signed triangle count. Moreover, we consider testing the rank statistics of inner products between latent points against uniformly random ranks. We show that ranks preserve all asymptotic testing information available in the full matrix models, and a cubic statistic based on rank statistics attains the optimal asymptotic error. This then yields an asymptotically optimal test for random kernel matrices with a possibly unknown, strictly monotone kernel. The proofs combine the classical framework of Davies (1985) and Le Cam and Yang (1988) for asymptotic normality under information loss with conditional limit theorems for the models in consideration.
Read the full abstract
Differential Geometry
Holomorphic Bisectional Curvature on Total Spaces of Holomorphic Vector Bundles
We study complete K$\"a$hler metrics with prescribed signs of holomorphic bisectional curvature on total spaces of holomorphic vector bundles over compact complex manifolds. We establish necessary and sufficient conditions in the nonnegative and strictly negative cases, characterized respectively by unitary flatness and Griffiths negativity of the bundle, together with the corresponding curvature conditions on the base. We also obtain a global metric splitting in the nonnegative case, rule out strictly positive curvature over positive-dimensional bases, and construct counterexamples to the converse in the nonpositive case.
Read the full abstract
Combinatorics
Tuza's Conjecture for Graphs of Maximum Degree at Most 10
For a finite simple graph $G$, let $\nu(G)$ be the maximum number of pairwise edge disjoint triangles and $\tau(G)$ the minimum number of edges meeting every triangle. Tuza conjectured in 1981 that every such $G$ satisfies $\tau(G) \le 2 \nu(G).$ We prove the conjecture for the class of graphs with $\Delta\le10.$
Read the full abstract
Statistics Theory · Cross-listed from stat.ME
Moment-Calibrated Conformal Prediction with Side Information
For a fixed conformal score function, standard split conformal prediction calibrates a prediction set using the empirical distribution of the conformal scores, without using available side information about the data. We propose a moment-calibrated approach that uses such information to reduce variability across calibration data sets. Side information involving the covariates, the response, or both is expressed as moment restrictions, which are enforced through empirical likelihood weights on the calibration data points. The resulting weighted empirical distribution of the scores determines the weighted empirical quantile without changing the score function. We establish finite-sample bounds on training-conditional and marginal coverage of the moment-calibrated prediction set. We derive asymptotic distributions for training-conditional coverage and average prediction-set size, show that their asymptotic variances are no larger than the corresponding variances under standard split conformal prediction, and characterize when the reductions are strict. In the semi-supervised setting, we identify an optimal moment function of a given covariate representation, develop implementations using prespecified moment functions or a function learned by cross-fitting, and quantify the effect of the unlabeled sample size. We also extend the method to coverage conditions indexed by a class of functions of the covariates through weighted quantile regression. Numerical studies demonstrate the effectiveness of the proposed methods.
Read the full abstract
Algebraic Geometry
The a-number of the Serre-type maximal curves of Abdón-Bezerra-Quoos
For every prime power $q$, we determine the $a$-number of the Serre-type maximal curves $X(q,n)$: $y^{q^2}-y=x^{(q^n+1)/(q+1)}$ over $\mathbb{F}_{q^{2n}}$, $n\ge 3$ odd, introduced by Abdón, Bezerra and Quoos as a generalization of Serre's curve $y^4+y=x^3$ over $\mathbb{F}_{64}$. The Weierstrass semigroup at the unique point at infinity gives an explicit basis of holomorphic differentials, on which the Cartier operator acts by monomials; this reduces the $a$-number to a lattice-point count, which we evaluate in closed form.
Read the full abstract
Combinatorics · Cross-listed from cs.CR
Asymptotics of Random-Lattice Enumeration: Beyond HKZ via Dense Sublattices
To bridge the gap between worst-case and heuristic analyses of lattice enumeration, we study the sizes of (unpruned) enumeration trees on $n$-dimensional Haar-random lattices. Writing $n^{cn+o(n)}$ for the tree size at the shortest vector radius, we investigate the asymptotic scaling of $c$, and which bases minimize it. For quasi-HKZ bases, we rigorously analyze the random-lattice HKZ geometry and establish $c=1/(2e)\approx 0.1839$. This matches the worst-case enumeration exponent of Hanrot-Stehlé and confirms earlier predictions for the geometry of HKZ bases on random lattices. Searching beyond quasi-HKZ bases, we prove that with high probability, the minimum achievable tree size exponent $c$ over all bases of a random lattice satisfies: \begin{align} 0.1464 \approx \frac{2-\sqrt{2}}{4}\leq c<0.1474. \end{align} For the lower bound, we use Kim's mean-value formula for nested chains of primitive sublattices to rule out bases with small prefix determinants. This strengthens the earlier Rankin-based heuristic lower bound exponent $c \geq 1/8$, discussed by Nguyen and Hanrot-Stehlé, and rules out the existence of random-lattice bases with trees as small as predicted by the geometric series assumption. For the upper bound, we show that with high probability a dense primitive half-rank sublattice exists with determinant at most $n^{n/8 + o(n)}$. Combining dual HKZ on this sublattice with HKZ on its quotient gives a basis with $c \leq 1/(4\sqrt{e}) \approx 0.1516$. Recursively splitting each half lowers the upper bound below $0.1474$, and under a natural heuristic assumption we prove that the lower bound is tight. Combined with the collision search of Feng-Gao-Liu, our two-block construction gives a polynomial-space algorithm solving the closest vector problem with preprocessing (CVPP) on random lattices in query time $n^{0.0892 n + o(n)}$ for arbitrary targets.
Read the full abstract
Number Theory
Bernoulli numbers and the integer group determinants of $C_p \times C_p$
For a prime $p\ge7$, let $S(C_p\times C_p)$ be the set of integer group determinants and $e(p)$ the least exponent for which $p^{e(p)}\mathbf Z\subseteq S(C_p\times C_p)$. Let $r_p$ be the least integer $r\ge1$ satisfying $(2r+1)i>r(p-1)$ for every irregular pair $(p,2i)$ with $r\mid i$. We prove the unconditional inclusion $p^{p+3+2r_p}\mathbf Z\subseteq S(C_p\times C_p)$. Equality $e(p)=p+3+2r_p$ holds when Vandiver's conjecture holds for $p$ and $r_p\le(p-5)/2$, hence for every prime $7\le p<2^{31}$. The first exception to $e(p)=p+5$ is $p=103$, where $e(103)=116$. A polynomial obstruction from Bernoulli numbers supplies the lower bound, and circular units give the construction. For regular primes, we characterize the entire determinant set through explicit affine systems over $\mathbf F_p$ and principality conditions in $\mathbf Z[\zeta_p]$. For regular $p\ge11$, prime cofactors cannot occur at valuation $p+3$; at valuation $p+4$ they have natural density $(p+1)/(hp^{(p-3)/2})$, where $h$ is the class number of $\mathbf Q(\zeta_p)$. We also show that $p^{p+5}$ is the least absolute value of a nonzero $p$-divisible determinant for these regular primes.
Read the full abstract
Commutative Algebra
Some Remarks on Regular Sequences and Complete Intersections
We give an ideal in a polynomial ring in three variables, generated by three elements and having height equal to three, but for which no permutation of its generators is a regular sequence. We prove that in a polynomial ring over an infinite field, an ideal of height n generated by n polynomials, always admits a set of n generators, for which any permutation is a regular sequence.