Browse

Optimization and Control

math.OC — Optimization and Control

math.OC RSS feed

Works in math.OC

37 works

math.MG — Metric Geometry

An upper bound of 2√2 for the three-dimensional sofa problem in a snake-shaped corridor

Contributed by Tejasvi Singh Tomar

The moving sofa problem in a snake-shaped corridor, posed by O'Rourke and by Georgiev, Gómez-Serrano, Tao and Wagner, asks for the largest volume of a connected body that can be moved through a corridor of unit-square cross-section with two turns that are far apart, one in the xx–yy plane and one in the yy–zz plane. The largest reported body has volume at least 1.85584041.8558404, and Tang obtained upper bounds for this problem, the best of which is 3.40833.4083. We prove by hand that the largest volume is at most 222\sqrt2 whenever the straight section between the turns is longer than 2+22+\sqrt2. The main new tool is a sharp bound: two infinite tubes of unit-square cross-section whose axes make an angle θ\theta meet in volume at most 1/sin⁡θ1/\sin\theta. With it, Hammersley's argument for the planar moving sofa problem carries over to three dimensions. The same argument gives explicit bounds for shorter straight sections; these and the main bound have also been proved in Lean 4 with Mathlib.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23716059

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 15, 202610 pages
PDFView work

math.PR — Probability

A certified upper bound for the beat the average game

Contributed by Tejasvi Singh Tomar

Let CC be the supremum of P[X1+X2+X3<2X4]\mathbb{P}[X_1+X_2+X_3<2X_4] over all probability measures on [0,∞)[0,\infty), where X1,…,X4X_1,\dots,X_4 are independent with the given law. Determining CC is Problem 6.39, the beat the average game, in the list of Georgiev, Gómez-Serrano, Tao and Wagner. Bellec and Fritz proved 0.4006953≤C≤673/16150.4006953\le C\le 673/1615 and conjectured that the lower bound, 0.4006953723…0.4006953723\ldots, is the exact value. We prove C≤0.40069634C\le0.40069634, less than 10−610^{-6} above the conjectured value. The proof applies Razborov's flag algebra method to samples of nine points. Since the points are independent, the positivity constraints of flag algebras hold for every single measure, so that no limit objects are needed. An exact certificate is checked in rational arithmetic, and the bound is also proved in the Lean 4 proof assistant, with Lean's kernel checking the certificate.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23715999

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 15, 202612 pages
PDFView work

math.NT — Number Theory

New lower bounds for Romanoff's constant

Contributed by Tejasvi Singh Tomar

Romanoff proved in 1934 that the integers of the form p+2ap+2^a, with pp prime and a≥1a\ge1, have positive lower density dd. We prove that d≥0.110825d\ge0.110825 and, conditionally on an upper bound for prime pairs that Johnston and Trudgian derive from Lichtman's work on primes in arithmetic progressions, that d≥0.119178d\ge0.119178; the best lower bound so far was 0.107880.10788. The proof refines the method of Elsholtz and Schlage-Puchta, which bounds the second moment of the number of representations in each residue class modulo a fixed integer. Both bounds are certified by computer and also proved in the Lean proof assistant, with the analytic inputs as hypotheses.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23715954

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 15, 202613 pages
PDFView work

math.NT — Number Theory

Upper and lower bounds for the Schur–Siegel–Smyth trace problem

Contributed by Tejasvi Singh Tomar

The Schur–Siegel–Smyth trace constant C86C_{86} is the lower limit of tr⁡(α)/deg⁡(α)\operatorname{tr}(\alpha)/\deg(\alpha) over totally positive algebraic integers α\alpha. We prove 1.8022225<C86<1.80708091.8022225<C_{86}<1.8070809. For the upper bound we exhibit a measure on [0,6][0,6] that satisfies the hypotheses of Smith's theorem on limits of distributions of conjugates, which we check with the help of 2121 integer polynomials. This improves the upper bounds 1.82161.8216 of Orloski and Talebizadeh Sardari and 1.81172511.8117251 of Pinho. The lower bound comes from the method of Orloski, Talebizadeh Sardari and Smith with fifteen polynomials, three of them of degree 1010 found by McKee and Smyth. It is larger than the bound 1.802201.80220 reported by Giraudin, whose verification evaluates its bounds in floating-point arithmetic with fixed safety margins; ours encloses every rounding error. For each bound, two separately written programs check the certificate in ball arithmetic. Both bounds are also proved in Lean 4, the upper bound under the assumption of Smith's theorem, also in a version in which all checks on the certificates are carried out by Lean's kernel. We also give evidence that certificates of this kind cannot lower the upper bound much further without integer polynomials of high degree.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23563968

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 15, 202615 pages
PDFView work

quant-ph — Quantum Physics

Equality cases and every-copy results for the Werner endpoint inequality

Contributed by Tejasvi Singh Tomar

Whether every entangled state with a non-positive partial transpose (NPT) can be distilled is open. For the Werner states ρ(d,α)\rho(d,\alpha), a criterion of Costa Rico reduces kk-copy undistillability to an inequality for matrices of rank at most two: an alternating sum of the squared norms of their partial traces must be nonnegative. At α=−1/2\alpha=-1/2 we call it the endpoint inequality. It is known for two and three copies, and if it held for every kk in some dimension d≥3d\ge3, NPT bound entanglement would exist. For two copies we show that every equality case has rank two, with its range and that of its adjoint in products of two-dimensional subspaces. We also show that a first failure would produce, at some α>−1/2\alpha>-1/2, an equality case whose range has reduced states of rank at least three on every copy, unlike all known equality cases at α=−1/2\alpha=-1/2. For every kk we prove the endpoint inequality on an explicit class of matrices whose ranges generically have such reduced states. For four copies we give a computer-assisted proof of it in every dimension for all matrices CC such that the ranges of CC and of its adjoint lie in one two-dimensional subspace, as they do for all normal matrices of rank two.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23992370

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 15, 202626 pages
PDFView work

quant-ph — Quantum Physics

Undistillability of Werner states from three, four and five copies

Contributed by Tejasvi Singh Tomar

Whether every entangled state with a non-positive partial transpose (NPT) can be distilled is a long-standing open problem of entanglement theory. It reduces to the Werner states ρ(d,α)\rho(d,\alpha), which for d≥3d\ge3 and −1/2≤α<−1/d-1/2\le\alpha<-1/d are NPT but cannot be distilled from one copy; if one of them stays undistillable from every number of copies, NPT bound entanglement exists. We prove that for every d≥3d\ge3 the state ρ(d,α)\rho(d,\alpha) is three-copy distillable if and only if α<−1/2\alpha<-1/2, the threshold known for one and two copies, so a third copy does not help. In every dimension we also prove four-copy undistillability for α≥−79/160\alpha\ge-79/160 and five-copy undistillability for α≥−9/20\alpha\ge-9/20, and improved bounds of order 1/k1/k for k≥6k\ge6 copies. The proofs use a criterion of Costa Rico and computer-verified certificates for quartic moment relaxations that hold for all large dimensions at once; for many copies they combine the resulting inequalities with known partial-trace inequalities. Whether −1/2-1/2 remains the threshold from four copies on is open.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23992387

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 15, 202615 pages
PDFView work

math.AG — Algebraic Geometry

An explicit determinantal formula for Sinkhorn limits of matrices and tensors

Contributed by Shankar Sivarajan

We give an explicit formula, as a single determinant, for the polynomial satisfied by any entry of the limit obtained by scaling a positive tensor of format n1×⋯×nrn_1\times\dots\times n_r to arbitrary prescribed one-dimensional margins (Sinkhorn--Knopp scaling, Kruithof's method, iterative proportional fitting). The polynomial is the multilinear resultant, on the Segre variety $\PP^{n_1-1}\times\dots\times\PP^{n_r-1}$, of the linear forms expressing the margin conditions. Its degree is the multinomial coefficient N=(dn1−1,…,nr−1)N=\binom{d}{n_1-1,\dots,n_r-1} with d=∑k(nk−1)d=\sum_k(n_k-1), and for generic tensors its roots are the corresponding entries of all complex solutions of the scaling equations. A Sylvester matrix turns it into an explicit N×NN\times N generalized eigenvalue problem, whose null vector recovers the whole limit. The leading coefficient is the principal AA-determinant of the product of simplices, that is, the product of the hyperdeterminants of all faces of the tensor. The constant term is likewise a product of face hyperdeterminants, and the faces avoiding the chosen entry split off as a factor independent of that entry. For matrices we also give a short proof, in Pl\"ucker coordinates, of a diagonal form of the eliminant. For every positive tensor, the limit is the unique root for which the Sylvester matrix has a positive null vector of monomials. Generically, the other roots are the corner entries of the solutions of the same scaling equations with complex scaling factors.

Primarily AI-generated textHuman understanding: all partsSinkhorn scaling
Nov 15, 202612 pages
PDFView work

math.OC — Optimization and Control

Quadratic Strictly Positive Real Factors of Stable Transfer Functions

Contributed by Jinlin Wang, Zhenyu Sun

We characterize factorizations G=G0∘HG=G_0\circ H in which GG and G0G_0 are stable, minimum-phase, biproper real-rational functions with simple poles and zeros and positive gains at infinity, and HH is a quadratic strictly positive real function. Classical rational decomposition identifies the quadratic right-factor classes with real Möbius involutions fixing GG. Within each class, we parameterize all normalized representatives and eliminate the scaling parameter and the frequency variable. The resulting sign conditions involve univariate polynomials of degree at most four. They determine all feasible denominator intervals and all factorizations in the class; for real-algebraic input, they give an exact decision procedure. We also give a scaling that maximizes the smaller of the inner positive-real margin and the outer spectral margin for a fixed denominator. For quadratic input, existence is equivalent to strict positive realness of GG and to an explicit coefficient inequality. Examples exhibit a disconnected feasible parameter set, separate algebraic and analytic obstructions, and a quartic input with exactly three admissible classes.

Primarily human-written textHuman understanding: all partsHurwitz polynomialsMöbius involutionsRational decompositionstrictly positive real functionstransfer function substitution
Nov 12, 202618 pages
PDFView work

math.CA — Classical Analysis and ODEs

Certified lower bounds for the first and the signed third autocorrelation constants

Contributed by Tejasvi Singh Tomar

Let C1C_1 be the largest constant such that sup⁡∣t∣≤1/2∫f(t−x)f(x) dx≥C1(∫−1/41/4f)2\sup_{|t|\le 1/2}\int f(t-x)f(x)\,dx\ge C_1\bigl(\int_{-1/4}^{1/4}f\bigr)^2 for every nonnegative function ff on the real line. We prove C1≥1.337C_1\ge 1.337, improving the bound 1.29371.2937 of Kim and Pilanci, by a spatial branch-and-bound over the masses of ff on equal bins. Consequently, for every large gg, every gg-Sidon set in {1,…,N}\{1,\dots,N\} has fewer than 1.2231gN1.2231\sqrt{gN} elements once NN is large enough in terms of gg. For real-valued ff supported in [−1/4,1/4][-1/4,1/4], let C3C_3 and C3′C_3' be the analogous constants for the essential suprema of ∣f∗f∣|f*f| and of f∗ff*f; no lower bound better than the trivial bound 11 was recorded for them. We prove C3≥C3′≥4/3C_3\ge C_3'\ge 4/3 with the argument principle. Both proofs are computer-assisted, and both theorems are also proved in Lean 4.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23715655

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202619 pages
PDFView work

math.MG — Metric Geometry

The 24-cell conjecture in the all-contact case and near D4

Contributed by Tejasvi Singh Tomar

The 24-cell conjecture states that every Voronoi cell of a packing of unit balls in R4\mathbb{R}^4 has volume at least 88, the volume of the regular 24-cell. It implies that no packing of equal balls in R4\mathbb{R}^4 is denser than the lattice packing D4D_4. We prove the conjecture for two classes of cells; in each class, equality holds only for the D4D_4 root configuration. The first consists of the cells whose ball touches every ball centred at distance less than 222\sqrt2 from its centre, and its proof uses a certificate at the second level of the Lasserre hierarchy. The second consists of the cells whose 2424 nearest centres lie in an explicit neighbourhood of the D4D_4 configuration, whatever the other centres are. For them the volume is at least 88 plus a fixed multiple of the total outward displacement of the 2424 centres, which we prove by a quantitative rigidity estimate and a second-order expansion of the volume about D4D_4. Our proofs for both classes are computer-assisted and partly formalised in Lean.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23720963

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202624 pages
PDFView work

math.PR — Probability

Lower bounds for the Beardwood–Halton–Hammersley constant

Contributed by Tejasvi Singh Tomar

Let β\beta be the Beardwood–Halton–Hammersley constant: the shortest tour through nn independent uniform random points in the unit square has length asymptotic to βn\beta\sqrt n almost surely. Dong and Cao proved β≥0.6421\beta\ge0.6421 from an inequality β≥5/8+∑k=3KCk\beta\ge5/8+\sum_{k=3}^{K}C_k, where CkC_k is an integral over configurations of kk points in the plane that form a connected graph when points at distance at most 11 are joined. For C3C_3, C4C_4 and C5C_5, sharper bounds come from a first-order expansion of the area of the union of the unit disks on boxes of configurations. For C6+⋯+C22C_6+\dots+C_{22}, which Dong and Cao did not use, a lower bound comes from comparing each point only with the three points before it in the order of their first coordinates. We obtain β≥0.6496\beta\ge0.6496, and β≥0.6508\beta\ge0.6508 if the exponential function of the C library used to evaluate the bound for C6+⋯+C22C_6+\dots+C_{22} has a relative error below 10−910^{-9}. The proofs are computer-assisted; the bound 0.64960.6496 is proved in Lean 4, with finite checks evaluated by compiled code, from the inequality of Dong and Cao and two statements about unions of disks that we prove but do not formalize.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23716094

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202621 pages
PDFView work

math.CO — Combinatorics

The Steiner ratio is at least 0.8564

Contributed by Tejasvi Singh Tomar

The Steiner ratio is the infimum, over finite sets of points in the Euclidean plane, of the length of a Steiner minimal tree divided by the length of a minimum spanning tree. Gilbert and Pollak conjectured in 1968 that it equals 3/2≈0.8660\sqrt3/2\approx0.8660, and the conjecture is open. We prove that it is at least 2141/2500=0.85642141/2500=0.8564, improving the bound 0.85590.8559 of Ke, Huang, Shu, He, Gai and Wang. Their method reduces the induction step of Du and Hwang's 1983 proof of the bound 0.80.8 to finitely many inequalities on boxes in a space of local configurations of a Steiner minimal tree, which are checked by computer. These inequalities use estimates for the positions of terminals outside the local configuration. We prove all the geometric lemmas that our certificate uses, filling gaps in two proofs of Ke et al., and we add two such estimates that hold for more parameter values than the published ones. Within this method some new estimate is necessary: with the published estimates, no certificate of this kind reaches 0.8560.856, whatever the boxes. The computer-assisted part is also verified in Lean 4, by a proof whose checks all run in Lean's kernel; the rest of the argument enters the formal proof as hypotheses.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23716009

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202619 pages
PDFView work

math.MG — Metric Geometry

The kissing numbers in dimensions five and seven are at most 43 and 132

Contributed by Tejasvi Singh Tomar

The kissing number τn\tau_n is the largest number of non-overlapping unit balls in Rn\mathbb{R}^n that can touch a common unit ball. The best bounds so far were 40≤τ5≤4440\le\tau_5\le44 and 126≤τ7≤134126\le\tau_7\le134; both upper bounds come from high-precision floating-point computations of the three-point bound by Mittelmann and Vallentin. We prove τ5≤43\tau_5\le 43 and τ7≤132\tau_7\le132. Each proof is an exact rational solution of the second level of the Lasserre hierarchy for spherical codes at degrees (d1,d2,δ)=(14,20,20)(d_1,d_2,\delta)=(14,20,20). We use the formulation of de Laat, Leijenhorst and de Muinck Keizer and check the solutions with their verification program. Each certificate is obtained by rounding a convex combination of two dual iterates of the interior-point method, one on each side of the target value. Exact certificates for the same hierarchy also give A(4,arccos⁡13)≤14A(4,\arccos\frac13)\le14, A(5,arccos⁡13)≤22A(5,\arccos\frac13)\le22 and A(6,arccos⁡13)≤34A(6,\arccos\frac13)\le34 for spherical codes, improving the previous bounds 1515, 2323 and 3535; with a known code, A(4,arccos⁡13)=14A(4,\arccos\frac13)=14. The largest number of points at angle π/3\pi/3 from a point of a kissing configuration in Rn\mathbb{R}^n equals A(n−1,arccos⁡13)A(n-1,\arccos\frac13), so in R5\mathbb{R}^5 this number is 1414. We also prove the five bounds in the Lean proof assistant, assuming only the positivity of the zonal kernels given by the zonal polynomial files: once by checking the exact certificates with compiled code, and once, with every computation done by Lean's kernel, from the certificates rounded to 3030 decimal places.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23992400

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 20268 pages
PDFView work

math.CO — Combinatorics

A linear gap for the maximal cp-rank

Contributed by Yair Lavi

We prove that the maximal cp-rank pnp_n satisfies pn≥n(n−3)/2p_n\ge n(n-3)/2 for odd n≥5n\ge5 and pn≥n(n−3)/2−1p_n\ge n(n-3)/2-1 for even n≥6n\ge6. Together with the known upper bound pn≤(n+12)−4p_n\le\binom{n+1}{2}-4, this gives pn=n2/2+O(n)p_n=n^2/2+O(n).

A mix of human-written and AI-generated textHuman understanding: all partsCompletely positive matrixCopositive matrixCyclic incidence matrixExposed facecp-rank
Nov 11, 20268 pages
PDFView work

math.LO — Logic

The Logical Anatomy of Optimization: Reverse Mathematics, Proof Mining, and the Price of Convergence

Contributed by Xiaoyu Li

Optimization theory proves three kinds of theorems: that optimal points exist, that algorithms converge to them, and that optimality can be certified by duality. We measure how much mathematics each kind needs, using reverse mathematics, Weihrauch complexity and proof mining, and assemble the answers, old and new, into one map stated in the language of optimization. Compactness makes existence cost weak Kőnig's lemma, but convexity (and, format by format, tameness) makes it cheap: we show that RCA0\mathsf{RCA}_0 proves that convex functions on [0,1][0,1] attain their minima (and on [0,1]n[0,1]^n, for each fixed nn, given a modulus of uniform continuity), and that RCA0\mathsf{RCA}_0 proves linear programming duality and the minimax theorem for real data of every size. Convergence costs more: it follows from results of Kohlenbach and Neumann that convergence of gradient descent for convex smooth functions on R\mathbb{R} is equivalent to ACA0\mathsf{ACA}_0. We explain this by a selection principle: what costs is the particular minimizer the algorithm selects, and uniqueness or an error bound removes the cost. Below convergence lies finitary information. Gradient descent in Rd\mathbb{R}^d has at most 2CdD/ε2C_dD/\varepsilon fluctuations of size ε\varepsilon, with CdC_d depending only on dd, which yields rates of metastability; no such bound is dimension-free, by the span-restriction argument behind performance estimation; and the limits of gradient descent on computable instances have d.c.e. coordinates, a proper subclass of the limit-computable reals. The map also covers Ekeland's variational principle (up to Π11-CA0\Pi^1_1\text{-}\mathsf{CA}_0), separation theorems, Kőnig duality (ATR0\mathsf{ATR}_0), proof-mined rates for fixed-point iterations, and the feasible world, where local search captures the NP\mathsf{NP} search problems provably total in T21T^1_2 and approximate stationary points of smooth functions are complete for CLS=PPAD∩PLS\mathsf{CLS}=\mathsf{PPAD}\cap\mathsf{PLS}. We close with five principles and open problems.

Primarily AI-generated textHuman understanding: some partsTFNPWeihrauch complexitybounded arithmeticconvex optimizationgradient descentlinear programming dualitymetastabilityminimax theoremproof miningreverse mathematics
Nov 10, 202646 pages
PDFView work

cs.LO — Logic in Computer Science

Formalization of Robust Strictly Positive Real Synthesis for Fourth-Order Interval Polynomial Families

Contributed by Tiancheng Xu, Wensheng Yu

That every robustly Hurwitz-stable fourth-order interval polynomial family admits a common strictly positive real (SPR) numerator was conjectured by Anderson et al. and proved by Yu and Wang. In this paper, we present a complete formalization of this classical synthesis theorem in the Lean~4 interactive theorem prover.

Primarily AI-generated textHuman understanding: all partsHurwitz stabilityLean 4formal verificationinterval polynomial familyproof reconstructionstrictly positive real synthesis
Nov 06, 202613 pages
PDFView work

math.OC — Optimization and Control

A Sixth-Order Hurwitz Interval Polynomial Family Without Degree-Five Weak Strictly Positive Real Numerator

Contributed by Tiancheng Xu, Zhengtai Xiong, Wensheng Yu

We construct an explicit sixth-order Hurwitz-stable interval polynomial family with independent closed coefficient intervals that admits a common strictly positive real (SPR) numerator of degree six, yet admits no common weak strictly positive real (WSPR) numerator of degree five. More strongly, no nonzero real polynomial of degree at most five makes the real part of the associated transfer functions nonnegative across the family at all real frequencies. This counterexample shows that, for sixth-order interval polynomial families, robust Hurwitz stability does not guarantee the existence of a strictly proper common SPR or WSPR numerator of degree five, and equal numerator degree six is necessary in general.

Primarily AI-generated textHuman understanding: some partsstrictly positive real synthesis
Nov 05, 202610 pages
PDFView work

math.CO — Combinatorics

Finite Field Grothendieck Inequality, Finite Field Johnson-Lindenstrauss Flattening and Finite Field Bourgain-Tzafriri Restricted Invertibility Problems

Contributed by K. MAHESH KRISHNA

We ask for finite field versions of following three: (1) Grothendieck Inequality, (2) Johnson-Lindenstrauss Flattening Lemma, (3) Bourgain-Tzafriri Restricted Invertibility Theorem.

Primarily human-written textHuman understanding: all partsBourgain-Tzafriri Restricted InvertibilityFinite Field.Grothendieck InequalityJohnson-Lindenstrauss Lemma
Nov 05, 20265 pages
PDFView work

math.OC — Optimization and Control

The generalized Lax conjecture holds for mixed determinants

Contributed by Suvrit Sra

We prove that the mixed determinant η(⋅)\eta(\cdot) of Borcea and Brändén has a spectrahedral hyperbolicity cone. More precisely, for Hermitian matrices A1,…,AmA_1,\ldots,A_m of order dd, the hyperbolicity cone of η(A1,…,Am)\eta(A_1,\ldots,A_m) is cut out by ∑jΦj(Aj)⪰0\sum_j\Phi_j(A_j)\succeq0, where Φ1,…,Φm\Phi_1,\ldots,\Phi_m are explicit unital completely positive maps. We argue by induction on dd, adding one row and one column to every argument and expressing the logarithmic derivatives of η\eta as extremal eigenvalues. By compressing along polynomial boundary kernels, we reduce the order of the pencil ∑jΦj(Aj)\sum_j\Phi_j(A_j) to exp⁡(O(md3log⁡m))\exp(O(md^3\log m)); for one fixed positive semidefinite n×nn\times n matrix AA a separate pencil yields the order exp⁡(O(n2log⁡n))\exp(O(n^2\log n)). We also answer four problems of Borcea and Brändén negatively.

A mix of human-written and AI-generated textHuman understanding: some partsCompletely positive mapsJohnson's conjecturesSchur positivitygeneralized Lax conjecturehyperbolic polynomialsimmanantsmixed determinantprincipal minorsspectrahedral cones
Nov 05, 202631 pages
PDFView work

cs.DS — Data Structures and Algorithms

The Exact One-Half Threshold for Arbitrary-Capacity Bottleneck Multiple Subset Sum

Contributed by Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník

In bottleneck multiple subset sum, items with weights are packed into knapsacks with capacities, possibly leaving items unpacked, so as to maximize the minimum load. For identical capacities the best possible approximation ratio is 2/32/3, and Chen et al.\ asked whether 2/32/3 is also achievable for arbitrary capacities. We show that it is not: for arbitrary capacities we give a 1/21/2-approximation using O(nlog⁡(n+1)+mlog⁡(m+1))O(n\log(n+1)+m\log(m+1)) arithmetic and comparison operations for nn items and mm knapsacks, and prove that no fixed ratio above 1/21/2 is achievable unless P=NP\mathsf P=\mathsf{NP}. We also give a short proof of the classical 1/21/2 guarantee of Friesen and Langston for unit profits.

Primarily AI-generated textHuman understanding: some partsapproximation thresholdbipartite matchingbottleneck multiple subset sumknapsacknumerical matching
Nov 04, 20269 pages
PDFView work

math.FA — Functional Analysis

The pp-Bures–Wasserstein distance via 3×33\times3 block matrices (with application to pp-Bures–Wasserstein barycenters)

Contributed by Suvrit Sra

We study the pp-Bures–Wasserstein distance Dp(A,B)=(tr Ap+tr Bp−2∥A1/2B1/2∥pp)1/2D_p(A,B)=(\mathrm{tr}\,A^p+\mathrm{tr}\,B^p-2\|A^{1/2}B^{1/2}\|_p^p)^{1/2} on positive semidefinite matrices; it equals the Bures–Wasserstein distance for p=1p=1, and the Hilbert–Schmidt distance for p=2p=2. We prove that DpD_p is a metric for every 1≤p≤21\le p\le2, by proving a stronger 2014 conjecture of Lin and van den Driessche on 3×33\times3 block matrices. Our main tool is a partition inequality for Schatten norms, proved by complex interpolation. We also characterize Fréchet means for DpD_p by a fixed-point equation and prove geometric convergence of the associated iteration.

A mix of human-written and AI-generated textHuman understanding: all partsBures-Wasserstein distanceLin-van den Driessche conjectureSchatten normbarycenterscomplex interpolationpartition inequalitypositive semidefinite block matrices
Nov 02, 202620 pages
PDFView work

math.OC — Optimization and Control

Lower bounds for the quantum permanent

Contributed by Suvrit Sra

Griffiths's 1969 conjecture on the positivity of Schur forms reduces to the positivity of the quantum permanent Φn\Phi_n on positive bistochastic maps. This conjecture was refuted by Du with a map for which Φ9<0\Phi_9<0. Therefore, we ask: how negative can Φn\Phi_n be? We prove a lower bound Φn≥−3n/(3n2+20n+103)\Phi_n\ge-3n/(3n^2+20n+103) (for n≥8n\ge 8), and an asymptotically stronger bound Φn≥−1/n+(3e2−7−o(1))log⁡n/n2\Phi_n\ge-1/n+(3e^2-7-o(1))\log n/n^2. The key to our bounds is the orbital polynomial of the map, which turns Φn\Phi_n into a linear function of a distribution on partitions and positivity into linear constraints. We also construct explicit maps for n=8,9n=8, 9 that improve on Du's example. Finally, if d∗∈{4,…,8}d_*\in\{4,\ldots,8\} is the first dimension for which Φn<0\Phi_n<0, the minimum μn\mu_n of Φn\Phi_n over positive bistochastic maps satisfies −μn=Ω(n−d∗)-\mu_n=\Omega(n^{-d_*}); we conjecture the matching order −μn=O(n−d∗)-\mu_n=O(n^{-d_*}).

A mix of human-written and AI-generated textHuman understanding: some partsGriffiths positivitybistochasticlower boundspositive mapsquantum permanentsemidefinite programming
Nov 02, 202630 pages
PDFView work

math-ph — Mathematical Physics

Density functionals for the Pauli-Fierz Hamiltonian

Contributed by Mihaly A. Csirik, Andre Laestadius, Markus Penz, Erik I. Tellgren

We develop a density-functional theory for the Pauli-Fierz Hamiltonian of nonrelativistic quantum electrodynamics in the spirit of the convex-analytic formulation of Lieb. We consider finitely many electrons, subject to external scalar and vector potentials, coupled to the full continuum of massless transverse photons with an ultraviolet cutoff. The natural basic variables are the standard electron density and a combined current density, the sum of the paramagnetic current density and a field-induced current density generated by the quantized vector potential. We prove representability results for these density-current pairs and show that the mixed-state constrained-search functional attains its infimum and coincides with the Lieb functional obtained by convex conjugation. Since arbitrarily soft photons purify mixed states at a negligible energy cost without changing their density and combined current density, the pure-state Levy-Lieb functional equals the Lieb functional and is therefore convex, even though its infimum need not be attained. In addition, we establish the zero-coupling limit, which recovers the mixed-state Vignale-Rasolt functional of current-density-functional theory. Finally, we consider the long-wavelength (dipole) limit and show that the limiting functional can be written as a constrained search for the well-known length-gauge dipole Hamiltonian.

Primarily AI-generated textHuman understanding: all parts
Nov 02, 2026121 pages
PDFView work

math.MG — Metric Geometry

Symmetric Volume Descent from U4 and a Four-Dimensional Lower Bound

Contributed by Hangang Wang

We explain a symmetric deformation that decreases the volume of the four-dimensional constant-width body U4U_4. The emphasis is on why the deformation works, rather than the size of the decrease. Oddness preserves width; convexity requires control of the curvature radii. A positive cap on one support branch is coupled to a negative correction on the adjacent branch. Their first-order volume contributions have different orders in the localization parameter, so the favorable contribution dominates. A small motion towards the ball makes the direction feasible for positive time. In a separate part we give a spectral lower bound for all four-dimensional bodies of constant width one, including an explicit positive refinement. A short projection argument using a three-dimensional theorem of Jiang gives the stronger lower bound 0.178722030.17872203. A substantial gap between the lower and upper bounds remains.

A mix of human-written and AI-generated textHuman understanding: all partsconstant widthspectral lower boundsvolume descent
Oct 29, 202616 pages
PDFView work

math.OC — Optimization and Control

Risk Aversion and Information in Robust Contracting

Contributed by Ruixue Yuan, Zhenyu Sun

We study hidden-action contracting with a risk-averse agent and partial knowledge of actions in a compact convex envelope of distribution--cost pairs. With finitely many outcomes and bounded deterministic wages, the principal's worst-case payoff admits an exact dual representation with an endogenous ff-divergence governed by transfer utility and an incentive multiplier. Under strictly concave utility, finite-multiplier branch optima follow a truncated likelihood-ratio rule, including at zero-probability outcomes. To address nonattainment induced by adversarial tie-breaking, we characterize the infinite-multiplier limit as a restricted zero-sum game. For polyhedral envelopes, we establish two-sided O(1/λ)O(1/\lambda) convergence when inverse utility is Lipschitz. Positive tolerance for suboptimal agent responses restores existence and confines the multiplier search to an explicit compact interval. A finite optimal multiplier gives a linear upper bound on tolerance loss; an optimal infinite-multiplier endpoint in a polyhedral envelope gives a square-root upper bound. A two-action example attains the square-root rate asymptotically. Restricting contracts to a coarse performance statistic contracts the endogenous divergence. We characterize equality in data processing under wage bounds, bracket the value of finer contractible information using fine and coarse dual minimizers, and derive quantitative bounds for approximately sufficient statistics. Numerical experiments demonstrate strict gains over utility-affine contracts and distinguish technological knowledge from the richness of contractible performance signals.

Primarily human-written textHuman understanding: all partsapproximate best responsesconvex dualityrisk aversionrobust contractssufficient statisticsunknown actions
Oct 26, 202625 pages
PDFView work

math.DS — Dynamical Systems

Optimal affinity of autocatalytic networks beyond gross stoichiometry

Contributed by Michael Mislan

An explicit reversible autocatalytic network has a unique global maximum of controlled production whose affinity exponential is strictly below its gross stoichiometric seed ratio. This refutes the proposed general lower bound. We identify a response-profile capacity that retains the missing kinetic information, analyze a literal recycling family approaching the source boundary and give a zero-diagonal counterexample. Under the stated rooted accessibility and response hypotheses, a local mass-action realization theorem makes the capacity sharp; an explicit power family supplies global maxima, while interacting cores delimit broader claims. The registered Lean project verifies the original refutation and checks the explicit witness against the literature conventions. Broader historical formal evidence and conventional arguments are distinguished in the manuscript and supporting claim map.

Primarily AI-generated textHuman understanding: some partsLean formalizationautocatalytic networkscounterexamplemass-action kineticsoptimal affinityresponse-profile capacity
Oct 21, 202625 pages
PDFView work

math.NT — Number Theory

An explicit upper-bound certificate for the essential minimum of the Zhang–Zagier height

Contributed by Ricardo Pinho

We give an exact certificate proving C82<0.2534449C_{82}<0.2534449 for the essential minimum of h(α)+h(1−α)h(\alpha)+h(1-\alpha), where hh is the absolute logarithmic Weil height. We use Doche's limit-point method, building on Grinsztajn's factor library and, in particular, Épi's unequal-multiplicity construction. We retain Épi's denominator factors, add Doche's P7P_7, and add 25 numerator factors found by LP-dual-weighted evaluation lattices with LLL. Joint linear-program re-optimisation is followed by exact rational rounding. Two separately written ball-arithmetic checkers certify the bound; a further adversarial computational audit accepts the certificate.

Primarily AI-generated textHuman understanding: some partsDoche limit-point methodLLLWeil heightZhang-Zagier heightcomputer-assisted proofessential minimumlinear programming
Oct 21, 20265 pages
PDFView work

math.NT — Number Theory

An explicit upper-bound certificate for the Schur–Siegel–Smyth trace constant

Contributed by Ricardo Pinho

We document an explicit certificate proving C86<1.8117251C_{86}<1.8117251 for the smallest limiting trace-to-degree ratio of totally positive algebraic integers. The construction uses the primal problem of Orloski and Talebizadeh Sardari, with their four-polynomial set enlarged to eleven. A discretised solution is rounded to a rational step density, then normalised to a probability measure. Exact rational calculations and rigorous ball-arithmetic inequalities verify Smith's sufficient criterion for an arithmetic measure. An independently written agent checker accepts the certificate and rejects four corrupted controls. This note records the proof, data provenance, reproduction results and limitations of the previously released certificate; it makes no optimality claim.

Primarily AI-generated textHuman understanding: some partsSchur-Siegel-Smyth trace problemball arithmeticcomputer-assisted prooflinear programmingtotally positive algebraic integers
Oct 21, 20266 pages
PDFView work

math.OC — Optimization and Control

Classical regularity and attainment in portfolio choice with nonhomothetic utility

Contributed by Yuanhong Wei, Zhenyu Sun

We study classical regularity and attainment in terminal-utility portfolio choice with unspanned factors, nonnegative wealth, and exposures that are square-integrable in expectation. A joint estimate for logarithmic marginal utility controls relative risk aversion and factor sensitivity. In several dimensions, a risk-price component uniformly separated from the factor-hedging span gives classical solvability and a unique strong optimal portfolio on every finite horizon. A scalar comparison equation treats correlated single-factor markets. For state-independent C4C^4 utility, the preference assumptions reduce to positive lower and upper bounds on relative risk aversion. In an orthogonal single-factor market, a uniform finite-order condition allows the risk price to vanish and change sign. Subelliptic gradient estimates and a parabolic equation in the factor variable yield a classical value; verification and strict concavity give strong existence for its continuous feedback. In both settings, the optimal dual coefficient has a deterministic bound uniform over initial states and multipliers. Attainment has a separate integrability boundary. For deterministic opportunities with a finite static optimum, the prescribed strategy class attains the value exactly when the optimal payoff lies in L2L^2 under the physical probability. An explicit nonhomothetic utility gives a horizon and wealth classification with smooth finite values and nonattainment. Further results identify wealth-dependent purchasing-power hedges and a strict increase in the dual value under factor-information restrictions.

Primarily human-written textHuman understanding: all partsNonhomothetic utilityclassical regularityconvex dualitydegenerate HJB equationssquare-integrable strategiesstochastic factors
Oct 20, 202641 pages
PDFView work

math.OC — Optimization and Control

Additive Rounding for LP-Tight Three-Item Bin Packing

Contributed by Ruixue Yuan, Da Teng, Zhenyu Sun

We consider bin-packing instances with 3m3m items of sizes in (1/4,1/2)(1/4,1/2), total size mm, and configuration linear programming value mm. Let dd be the relative dimension of the polytope of zero-sum multiplicity patterns obtained by centering sizes at 1/31/3. We determine the maximum additive integrality gap for every d≤10d\le10. It is zero for d≤4d\le4 and one for 5≤d≤105\le d\le10. More generally, a representation of the multiplicity vector by at most five zero-sum patterns admits an integral packing, and a representation by at most eleven patterns requires at most one additional bin. The integral-packing result has a structural proof; the additive-one result combines structural restrictions with exact finite enumeration. For arbitrary dd, we construct an LP-tight subinstance with at most 6d+36d+3 items and no smaller additive gap. An integer representation preserving the signs of triple sums then yields a finite rational family attaining the worst gap, which is computable in time 2O((d+1)2)2^{O((d+1)^2)}. Finally, we construct a sharp family with simplex pattern polytopes and a linearly growing zero-sum matching deficit. Its eleven-dimensional member violates the zero-sum remainder condition used in the ten-dimensional proof. Thus the bound of eleven fractional patterns in that condition is sharp.

Primarily human-written textHuman understanding: all partsbin packingconfiguration linear programminghypergraph matchinglattice polytopeszero-sum patterns
Oct 20, 202618 pages
PDFView work

math.OC — Optimization and Control

Exact interfaces for modular autocatalytic networks

Contributed by Michael Mislan

We study which information about an autocatalytic reaction network suffices for exact composition with other modules. For the maximum amplification factor, threshold-indexed species-price cones compose by exact set operations, while scalar optima do not. Autocatalytic child-selection cores are reconstructed from complete, uniquely matched ordinary-core anchors using alternating exchange paths and certified rational semipositivity tests. For irreducible unary diluted source networks, positive-composition certificates characterize growth, criticality and extinction under arbitrary species degradation; a related certificate identifies partial-actuation stabilizability. Further manuscript results treat factor interactions, exact boundary traces, contextual indistinguishability and junction-tree composition under running intersection and scope extensionality. Separator width bounds message arity, without a runtime claim. Eleven foundation statements are Palomar registered in Lean 4; the broader historical formalization and conventional extensions retain their separately documented scope. Thermodynamic and passive-tail examples illustrate exact interfaces and information loss. Structural amplification and linear onset conclusions are distinguished from nonlinear kinetic dynamics.

Primarily AI-generated textHuman understanding: some partsLean formalizationautocatalytic networksboundary traceschild-selection coresdegradationmaximum amplification factormodular composition
Oct 20, 202624 pages
PDFView work

math.NT — Number Theory

Cubic augmentation of a two-moment model: an exact finite absorption theorem and its limits

Contributed by Kunal Tyagi

We study adjoining a half-bandwidth signed cubic trace and a spectral count ladder to a bandwidth-one trace/Frobenius model motivated by zeta-zero certificates. In a finite circle model with mass N = 64, flat windows, and explicit budget centers, we prove exact absorption over the full atom-only class: the augmented and baseline optima agree for both the distinct-count and simple-fraction objectives. Three explicitly specified integer-marked grid columns attain the lower bounds. Their mixing weights are defined algebraically, and an Arb certificate proves all strict feasibility and inertia inequalities. The witness satisfies the ladder at every positive threshold, not just on a finite threshold grid. We also give the exact conjugate-pair spectrum, the isolated-block cubic identity, grid Parseval, and the sharp conditional spectral-capacity constant 2 sqrt(2). The result is a finite model theorem, not an unconditional statement about zeta zeros. Version 2 corrects an infeasible witness, a cubic-tolerance mismatch, and an incorrect rationality claim in version 1. Global absorption in the pair-containing or pinned classes remains unproved; equality on a searched column dictionary and heuristic pricing do not establish it.

Primarily AI-generated textHuman understanding: some parts
Oct 15, 20268 pages
PDFView work

math.OC — Optimization and Control

Continuity of solutions to abstract linear control systems

Contributed by Frédéric Marbach

It has long been known that the solutions to abstract linear control systems are continuous in time for controls in LpL^p with 1≤p<∞1 \le p < \infty. We prove that the same property remains valid for the endpoint case p=∞p = \infty, giving a positive answer to Weiss' 1989 Problem 2.4. The proof relies on a direct semigroup argument based on Phillips' lemma, does not require the input map to have an integral representation (which is not always the case for p=∞p = \infty), and actually entails that such systems are all of the zero-class (which fails for 1≤p<∞1 \le p < \infty).

Primarily AI-generated textHuman understanding: all partsabstract linear control systems
Oct 03, 20269 pages
PDFView work

math.OC — Optimization and Control

A Finite Coordinate Reduction for Approachability Loss in Lean

Contributed by Arthur, David Barros Hulak, Ruy J. G. B. de Queiroz

We explain a Lean 4 development of a finite-coordinate loss-preserving construction motivated by Theorem 4 of Dann, Mansour, Mohri, Schneider, and Sivan. Nonempty finite constraint and action index sets give a joint probability simplex with a canonical action marginal. For each mixed constraint, a linear comparator adds its outer product with that marginal. The comparator has mass two and leaves the legal action set. A one-step pairing identity yields exact equality of finite-horizon approachability and comparator-regret objectives, with explicit anchored lifts and marginal decoders. The development also proves a row-wise decomposition with at most one rank-one term per constraint index. We describe the twelve declarations registered in Palomar and their historical verification provenance. The scope is deliberately narrow: the constraint simplex parametrizes coordinate functions, both causal strategy translations observe original loss histories, and the comparators have no fixed point in the joint simplex. Thus the checked statements establish finite algebraic loss preservation; they do not certify the full published reduction, its fixed-point-defined improper class, reduced-loss-only feedback, or asymptotic rate theory. No mathematical novelty or formalization priority is claimed.

Primarily AI-generated textHuman understanding: some parts
Oct 01, 20269 pages
PDFView work

math.OC — Optimization and Control

A Lean Formalization of Roberts Theorem on Unrestricted Valuations

Contributed by Arthur, David Barros Hulak, Ruy J. G. B. de Queiroz

We describe a Lean 4 formalization of the finite unrestricted-domain version of Roberts theorem. For finite nonempty agent and alternative types, with at least three alternatives, an onto deterministic direct-revelation mechanism that is dominant-strategy incentive compatible has an affine-maximizer choice rule. Valuations range over all real-valued profiles; the conclusion uses fixed nonnegative weights, at least one nonzero, and alternative offsets, and asserts membership in the maximizing set. The development follows the modular proof route: taxation and weak monotonicity, perturbation-based tie-breaking to strong monotonicity, no-veto range analysis, affine prices for two agents, and induction through fixed-report slices. We explain the proved tie-set transport lemma, the construction of fresh payments for the tie-broken rule, and the transfer back to arbitrary ties. A version-pinned account distinguishes the proved library from statement-only comparator placeholders and separates source inspection from executable checks. This is an exposition of a classical result and its formal artifact, with no claim of mathematical novelty or formalization priority.

Primarily AI-generated textHuman understanding: some partsLean 4Roberts theoremaffine maximizersdominant strategiesformalizationmechanism design
Sep 30, 20268 pages
PDFView work

math.OC — Optimization and Control

Finite VCG and Groves Payments in Lean

Contributed by Arthur, David Barros Hulak, Ruy J. G. B. de Queiroz

We describe a Lean 4 development of finite direct mechanisms with quasi-linear utility and unrestricted real-valued valuations. The Clarke pivot mechanism selects a reported-welfare maximizer and charges each agent the loss in other-agent welfare relative to its maximum over the same fixed alternative set. The development proves efficiency, dominant-strategy truthfulness, nonnegative payments and no deficit, and individual rationality under the explicit assumption that every valuation is nonnegative. It also proves that every efficient, dominant-strategy incentive-compatible mechanism on the full valuation domain has Groves-form payments, with a term independent of the paying agent's report. We explain the finite-maximization interface, the report-update invariants, and the characterization argument using outcome-forcing reports and positive perturbations. The exposition is tied to a specific source revision and separates proved implementations from statement-only comparator placeholders. These are classical mechanism-design results; no new mathematical theorem or formalization-priority claim is made.

Primarily AI-generated textHuman understanding: some partsClarke pivot paymentsGroves characterizationLean 4VCG mechanismdominant strategiesformal verification
Sep 30, 20266 pages
PDFView work

math.OC — Optimization and Control

A Lean Formalization of Finite Zero Sum Minimax via Sion's Theorem

Contributed by Arthur, David Barros Hulak, Ruy J. G. B. de Queiroz

We describe a Lean 4 formalization of the minimax theorem for finite nonempty two-player zero-sum games with arbitrary real payoffs. Mixed strategies are probability vectors, and the two game values are defined using real indexed suprema and infima. An explicit payoff bound supplies the boundedness obligations required by these conditional extrema. The reverse minimax inequality follows by applying Mathlib's proved Sion saddle-point theorem to compact convex coordinate simplices, with the minimizing player placed in its first argument. We explain the representation bridge, the proof obligations, and the passage from a saddle point to equality. The accompanying version-pinned artifact separates a reusable library from a statement-only challenge and its proved solution. This is an exposition of a finite-game specialization of existing formal analysis, with no claim of a new mathematical proof or formalization priority.

Primarily AI-generated textHuman understanding: some partsLeanSion's theoremformalizationminimax theoremzero-sum games
Sep 30, 20267 pages
PDFView work