Browse

Combinatorics

math.CO — Combinatorics

math.CO RSS feed

Works in math.CO

269 works

math.CO — Combinatorics

Wills' (1981) conjecture holds if and only if the dimension is at most 4, and other miscellanea

Contributed by Dave Goel

Let PP be a lattice polytope in Rn\mathbb R^n that is symmetric about the origin and has the origin as its only interior lattice point. In 1981 Wills conjectured that each coefficient gi(P)g_i(P) of the Ehrhart polynomial of PP is at most the corresponding coefficient of the cube [−1,1]n[-1,1]^n, that is, gi(P)≤2i(ni)g_i(P)\le 2^i\binom ni. Wills proved this for n≤3n\le3, and Henze showed in 2014 that it fails for every n≥7n\ge7; the dimensions 44, 55 and 66 remained open. We settle them. In dimension 44 the conjecture holds; the new bounds are g1(P)≤8g_1(P)\le8 and g2(P)≤24g_2(P)\le24, and, up to unimodular equivalence, g1(P)=8g_1(P)=8 only for the cube, one explicit 2424-cell and one explicit cross-polytope. In dimension 55 we give a polytope with 5050 vertices in [−1,1]5[-1,1]^5 whose linear Ehrhart coefficient is 101/10>10101/10>10; products with segments then give counterexamples in every dimension n≥6n\ge6. Hence Wills' conjecture holds in Rn\mathbb R^n if and only if n≤4n\le4. The proof in dimension 44 combines Ehrhart reciprocity, the lower bound theorem for triangulated 33-spheres and an exhaustive computer enumeration of about three million sets of lattice points, listed up to symmetry. This expanded version also gives a second proof of the case in which the integer functionals bounded by 11 on PP do not span R4\mathbb R^4, determines the second largest value of g2g_2 in dimension 44, discusses a width-two approach, describes the computer search for the counterexample, and describes all computations used in the proofs.

Author comments: First version: November 3, 2026. This is the expanded version of the paper "Wills' (1981) conjecture holds if and only if the dimension is at most 4", which is at https://hexagonmath.org/2611.00540 on Hexagon.

A mix of human-written and AI-generated textHuman understanding: some partsEhrhart polynomialWills' conjecturecentrally symmetric polytopeinterior lattice pointlattice polytope
Nov 16, 202626 pages
PDFView work

math.CO — Combinatorics

Wills' (1981) conjecture holds if and only if the dimension is at most 4

Contributed by Dave Goel

Let PP be a lattice polytope in Rn\mathbb R^n that is symmetric about the origin and has the origin as its only interior lattice point. In 1981 Wills conjectured that each coefficient gi(P)g_i(P) of the Ehrhart polynomial of PP is at most the corresponding coefficient of the cube [−1,1]n[-1,1]^n, that is, gi(P)≤2i(ni)g_i(P)\le 2^i\binom ni. Wills proved this for n≤3n\le3, and Henze showed in 2014 that it fails for every n≥7n\ge7; the dimensions 44, 55 and 66 remained open. We settle them. In dimension 44 the conjecture holds; the new bounds are g1(P)≤8g_1(P)\le8 and g2(P)≤24g_2(P)\le24, and, up to unimodular equivalence, g1(P)=8g_1(P)=8 only for the cube, one explicit 2424-cell and one explicit cross-polytope. In dimension 55 we give a polytope with 5050 vertices in [−1,1]5[-1,1]^5 whose linear Ehrhart coefficient is 101/10>10101/10>10; products with segments then give counterexamples in every dimension n≥6n\ge6. Hence Wills' conjecture holds in Rn\mathbb R^n if and only if n≤4n\le4. The proof in dimension 44 combines Ehrhart reciprocity, the lower bound theorem for triangulated 33-spheres and an exhaustive computer enumeration of about three million sets of lattice points, listed up to symmetry.

Author comments: First version: November 3, 2026. The expanded version of this paper, "Wills' (1981) conjecture holds if and only if the dimension is at most 4, and other miscellanea", is at https://doi.org/10.5281/zenodo.23955454 on Zenodo.

A mix of human-written and AI-generated textHuman understanding: some partsEhrhart polynomialWills' conjecturecentrally symmetric polytopeinterior lattice pointlattice polytope
Nov 16, 202613 pages
PDFView work

math.CO — Combinatorics

The Zarankiewicz number z(13,15;3,4)

Contributed by Will Howe, Grant Huffman, Jensen Kohlmeyer, Liam Kruer

We establish z(13,15;3,4)=114z(13,15;3,4)=114: a 13×1513\times15 binary matrix with 115115 ones necessarily contains an all-one submatrix on three rows and four columns. The lower bound is attained by a previously published construction of Rosero. For the upper bound, we exclude dense eight-row column neighborhoods by a finite classification and a complete extension check. The resulting local inequality reduces a hypothetical counterexample to 6,0196{,}019 pairs of degree sequences. Each pair is excluded by an exact integer certificate for a system of neighborhood-type equations. The proof is computer-assisted; its mathematical reductions, finite search domains, classification representatives, and certificate conditions are given explicitly.

Author comments: Added a public, version-specific archive containing all 15 checked SAT refutations and CNF inputs, all 82 five-row extension inputs and outputs, and all 6,019 exact integer dual certificates, with generators and checking instructions. The manuscript now links release v1 and commit 10385847932cd2b61e25cb4e7d039633d108455b. The computational material was regenerated and independently checked on November 16, 2026.

Primarily AI-generated textHuman understanding: all partsZarankiewicz numbercomputer-assisted proofextremal bipartite graphforbidden submatrix
Nov 16, 202612 pages
PDFView work

math.NT — Number Theory

Three Properties of Markov–Hurwitz Equations

Contributed by Qiyue Tang

We prove Laurent positivity for pure Markov–Hurwitz mutations, density-one uniqueness by the largest coordinate for positive integral solutions of the symmetric generalized equation, and labelled Vieta connectivity for the pure equation on points with at most one zero coordinate over sufficiently large prime fields.

Author comments: The ideas behind this work came primarily from the author and were developed through discussions with ChatGPT.

Primarily AI-generated textHuman understanding: some parts
Nov 16, 202639 pages
PDFView work

math.CO — Combinatorics

The Lee (2026) conjecture on the diameters of order and chain polytopes fails in both directions, and other miscellanea

Contributed by Dave Goel

For a finite poset PP, Stanley's order polytope O(P)\mathcal O(P) and chain polytope C(P)\mathcal C(P) have the same number of vertices and, by a theorem of Hibi, Li, Sahara and Shikama, the same number of edges. J. Lee recently conjectured that for a connected poset the diameters of their graphs differ by at most 11. We show that this fails in both directions. For every k≥1k\ge1 we describe a connected poset BkB_k with 3k3k elements on three consecutive antidiagonals of the grid Z2\mathbb Z^2, for which the graph of O(Bk)\mathcal O(B_k) has diameter exactly kk, while the graph of C(Bk)\mathcal C(B_k) has diameter exactly ⌊2k/3⌋+1\lfloor2k/3\rfloor+1. Their difference is therefore ⌈k/3⌉−1\lceil k/3\rceil-1, and their ratio tends to 3/23/2. Hence no constant bounds diam⁡O(P)−diam⁡C(P)\operatorname{diam}\mathcal O(P)-\operatorname{diam}\mathcal C(P) on connected posets. In the other direction, for every n≥4n\ge4 we construct a connected poset PnP_n with 2n2+5n+12n^2+5n+1 elements such that diam⁡O(Pn)=2\operatorname{diam}\mathcal O(P_n)=2 and diam⁡C(Pn)=4\operatorname{diam}\mathcal C(P_n)=4. We also show that diam⁡O(P)≤2\operatorname{diam}\mathcal O(P)\le2 implies diam⁡C(P)≤4\operatorname{diam}\mathcal C(P)\le4 for every finite poset PP, so a difference of 22 is the largest possible at order diameter 22.

Author comments: First version: October 23, 2026. This is the expanded version of the paper "Diameters of the order and chain polytopes of a connected poset", which is at https://hexagonmath.org/2611.00523 on Hexagon.

A mix of human-written and AI-generated textHuman understanding: some partsLee conjecturechain polytopediameterfinite posetgraph of a polytopeorder polytope
Nov 16, 202631 pages
PDFView work

math.CO — Combinatorics

Diameters of the order and chain polytopes of a connected poset

Contributed by Dave Goel

For a finite poset PP, Stanley's order polytope O(P)\mathcal O(P) and chain polytope C(P)\mathcal C(P) have the same number of vertices and, by a theorem of Hibi, Li, Sahara and Shikama, the same number of edges. On disconnected posets the diameters of their graphs can differ by any amount, since both diameters add over disjoint unions and already differ on small examples, but on connected posets a computer search of Lee found no difference larger than 11. We show that on connected posets, too, the two diameters can be far apart. For every k≥1k\ge1 we describe a connected poset BkB_k with 3k3k elements whose order polytope has graph diameter kk and whose chain polytope has graph diameter at most ⌊3(k+1)/4⌋\lfloor3(k+1)/4\rfloor; hence the first diameter can exceed the second by any amount. For every n≥4n\ge4 we construct a connected poset PnP_n with 2n2+5n+12n^2+5n+1 elements whose order polytope has graph diameter 22 and whose chain polytope has graph diameter 44. Finally, for every finite poset PP, if the graph of O(P)\mathcal O(P) has diameter at most 22, then the graph of C(P)\mathcal C(P) has diameter at most 44; so 22 is the largest possible difference when the order polytope has graph diameter 22.

Author comments: First version: October 28, 2026. The expanded version of this paper, "The Lee (2026) conjecture on the diameters of order and chain polytopes fails in both directions, and other miscellanea", is at https://doi.org/10.5281/zenodo.23351398 on Zenodo.

A mix of human-written and AI-generated textHuman understanding: some partschain polytopediameterfinite posetgraph of a polytopeorder polytope
Nov 16, 202619 pages
PDFView work

math.CO — Combinatorics

Flow reconfiguration with one modulus for all graphs, and Cereceda's conjecture for bipartite 2-degenerate graphs

Contributed by Dave Goel

This paper answers a question of Esperet, Hendrey, Lagoutte, Marseloo, Norin and Steiner on flow reconfiguration and makes inroads into Cereceda's recolouring conjecture for d=2d=2. Parts I and II are about flows. For a finite multigraph GG and an integer k≥2k\ge 2, let Mk(G)M_k(G) be the graph on the nowhere-zero Zk\mathbb{Z}_k-flows of GG, and Ik(G)I_k(G) the graph on the integer flows FF of GG with 1≤∣F(e)∣≤k−11\le|F(e)|\le k-1 on every edge; two flows are adjacent if the support of their difference is a cycle. We prove that Mk(G)M_k(G) and Ik(G)I_k(G) are connected for every finite bridgeless loopless multigraph GG if k=40k=40, if k=48k=48, or if kk is a multiple of 44 with k≥52k\ge 52. This answers their Problem 1.2. The same holds for k=66k=66, for every prime power pNp^N with N≥6N\ge 6, and for a set of moduli of natural density one; these results do not cover every k≥40k\ge 40. A master theorem for finite abelian groups gives the connectivity of the flow graph F(G,Γ)F(G,\Gamma) for every abelian group Γ\Gamma of order 4040, and a binary form of it for every abelian group of exponent dividing 44 and order at least 3232, in particular F25\mathbb{F}_2^5 (Esperet et al. proved F28\mathbb{F}_2^8). Part III is about colourings: two proper kk-colourings of a graph GG are adjacent if they differ at exactly one vertex. Cereceda conjectured that this graph has diameter O(n2)O(n^2) for every dd-degenerate graph on nn vertices and k=d+2k=d+2; the case d=2d=2 is open. For four colours we prove the diameter bound 2n(n+1)2n(n+1) for every bipartite graph of degeneracy at most 22, with the order n2n^2 sharp in this class, also at girth 66; the bound 5n(n+1)5n(n+1) when an independent set of vertices of degree at most 22 is added; and, with a computer-verified certificate, 4n(n+1)4n(n+1) for every graph of cone width at most 22, a class that contains all graphs of treewidth at most 22 and some graphs of treewidth 33 with triangles.

Author comments: First version: October 23, 2026. This is the expanded version, with many other results, of the paper "The Cereceda (2007) conjecture holds for bipartite 2-degenerate graphs", which is at https://hexagonmath.org/2611.00260 on Hexagon. The ancillary files of this paper (programs and data) are at https://doi.org/10.5281/zenodo.23603238 on Zenodo.

A mix of human-written and AI-generated textHuman understanding: some partsCereceda conjecturedegenerate graphsflow reconfigurationgraph recolouringnowhere-zero flow
Nov 16, 2026181 pages
PDFView work

math.CO — Combinatorics

Nowhere-zero flow reconfiguration in every finite abelian group of order at least 3024

Contributed by Dave Goel

For a finite multigraph GG and a finite abelian group Γ\Gamma, let F(G,Γ)F(G,\Gamma) be the graph on the nowhere-zero Γ\Gamma-flows of GG in which two flows are adjacent if the support of their difference is a cycle. We prove that F(G,Γ)F(G,\Gamma) is connected for every finite bridgeless multigraph GG and every finite abelian group Γ\Gamma of order at least 30243024. The previous bound for all finite abelian groups, due to Esperet, Hendrey, Lagoutte, Marseloo, Norin and Steiner, is a number with 694694 digits; for the cyclic groups of prime order pp their bound is p>2.26⋅1015p>2.26\cdot 10^{15}. A theorem of an earlier paper of the author covers every group that is not cyclic of prime-power order and whose order has a divisor dd with 4≤d≤∣Γ∣/104\le d\le|\Gamma|/10; from the order 100100 on, it leaves only the cyclic groups whose order is a prime power, twice a prime or three times a prime. For a cyclic factor Zn\mathbb{Z}_n we use units of Zn\mathbb{Z}_n as scales, and we average over a set of scales that is generated by good units. Counts of the bad units settle the orders from 39993999 on, and a finite arithmetic certificate with 230230 rows settles the orders from 30243024 to 39983998.

Author comments: First version: October 23, 2026. The ancillary files of this paper (a certificate checker) are at https://doi.org/10.5281/zenodo.23605837 on Zenodo.

A mix of human-written and AI-generated textHuman understanding: some partsfinite abelian groupflow reconfigurationgroup flownowhere-zero flow
Nov 16, 202632 pages
PDFView work

math.CO — Combinatorics

Integer and modular flow reconfiguration: the moduli up to six, chords, and large moduli

Contributed by Dave Goel

For a finite multigraph GG and an integer k≥2k\ge2, let Mk(G)\mathcal M_k(G) be the graph on the nowhere-zero Zk\mathbb Z_k-flows of GG, and Ik(G)\mathcal I_k(G) the graph on the integer flows FF of GG with 1≤∣F(e)∣≤k−11\le|F(e)|\le k-1 on every edge; a step adds a nonzero constant along one cycle. The Esperet–Hendrey–Lagoutte–Marseloo–Norin–Steiner (2025) lifting question asks for a proof that Ik(G)\mathcal I_k(G) is connected whenever Mk(G)\mathcal M_k(G) is connected; its authors write that they do not know how to prove this even for k=4k=4. We prove it for k=2,3,4,5,6k=2,3,4,5,6 and every graph, in a stronger form: reduction modulo kk induces a bijection between the components of Ik(G)\mathcal I_k(G) and of Mk(G)\mathcal M_k(G). We prove the same for every kk on the graphs in which every cycle with more than nine edges has a chord between two vertices that are not neighbors on the cycle. We also prove that Ik(G)\mathcal I_k(G) is connected for every bridgeless multigraph GG and every k≥mc⁡(G)+2k\ge\operatorname{mc}(G)+2, where mc⁡(G)\operatorname{mc}(G) is the largest number of edges of a cut of GG; and that scaling by mm carries the components of Mk(G)\mathcal M_k(G) into components of Imk(G)\mathcal I_{mk}(G). With a theorem of Esperet et al. on planar graphs, the first result settles the question for every planar graph and every kk. The bijection of the components for k≤6k\le6 holds more generally for the integer and modular kernel vectors of every totally unimodular matrix, with the circuit vectors as steps, and in this generality it fails at every prime p≥7p\ge7, for the tensions of a graph on 2p2p vertices; this does not answer the question for the flows of graphs. For the six moduli k=8,9,12,16,18,36k=8,9,12,16,18,36 we prove the bijection of the components for every graph also; this is a short deduction from a lemma on liftable steps of a companion paper. For the other k≥7k\ge7 this paper does not settle the question on arbitrary graphs.

Author comments: First version: October 23, 2026.

A mix of human-written and AI-generated textHuman understanding: some partsflow reconfigurationinteger flowmodular flownowhere-zero flowtotally unimodular matrix
Nov 16, 202623 pages
PDFView work

cs.FL — Formal Languages and Automata Theory

A uniform 7/48 cubic upper bound for reset thresholds

Contributed by SUNGBIN HONG

We prove that every complete synchronizing deterministic finite automaton AA with nn states satisfies rt⁡(A)≤748n3+o(n3)\operatorname{rt}(A)\le\frac{7}{48}n^3+o(n^3), uniformly over the automaton and its finite alphabet. The coefficient is the milestone proposed in Trahtman's 2011 half-rank approach. The argument fixes a short word whose kernel is stable over a dyadic length interval. Degree transport in the graphs of pairs mergeable by short words, combined with a simultaneous selection of times of small degree growth, gives a compression bound for every sufficiently large subset of states. The bound remains available after replacing the current word. We combine it with the cheap-gap construction and the Pin--Frankl rank upgrade: the cost of reaching half rank is paid by a saving in the subsequent rank reductions. The required scalar comparison has an elementary analytic proof over its entire parameter domain. An explicit two-parameter estimate proves uniformity and extends the result from strongly connected automata to arbitrary complete synchronizing automata. The full theorem, including the word constructions used as classical inputs, has also been formalized in Lean 4.

Author comments: 14 pages, including two appendices. Uniform asymptotic bound over all complete synchronizing DFAs and finite alphabets. A separate Lean 4 development and recorded verification artifact are described in the paper; code is not included in this Hexagon deposit.

Primarily AI-generated textHuman understanding: no partsCerny conjectureSynchronizing automatondegree transportformal verificationreset threshold
Nov 16, 202614 pages
PDFView work

math.CO — Combinatorics

An Irredundant Test for Circular Positivity

Contributed by Qiyue Tang

We give an inclusion-minimal circular-minor positivity test on five boundary vertices that is not weakly separated. This refutes the inclusion-minimal version of Conjecture 6.3.4 of Alman, Lian and Tran.

Author comments: I am posting this manuscript to share the mathematical results themselves. In doing so, I do not seek to assert ownership of the results or claim priority. I welcome anyone interested in checking the arguments or preparing a finished account, and I believe the eventual scholarly credit should go to those who undertake that work.

Primarily AI-generated textHuman understanding: some parts
Nov 15, 20263 pages
PDFView work

math.CO — Combinatorics

Schur Nonnegativity of Double-Wiring Cluster Variables

Contributed by Qiyue Tang

We prove Cuenca’s conjecture that every cluster variable of the matrix cluster algebra associated with a double wiring diagram evaluates to a Schur nonnegative symmetric function on every generalized Jacobi–Trudi matrix. The result extends to cluster monomials.

Author comments: I am posting this manuscript to share the mathematical results themselves. In doing so, I do not seek to assert ownership of the results or claim priority. I welcome anyone interested in checking the arguments or preparing a finished account, and I believe the eventual scholarly credit should go to those who undertake that work.

Primarily AI-generated textHuman understanding: some 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.CO — Combinatorics

An upper bound for the connective constant of the square lattice

Contributed by Tejasvi Singh Tomar

We prove that the connective constant μ\mu of the square lattice Z2\mathbb{Z}^2, the exponential growth rate of the number of nn-step self-avoiding walks, satisfies μ≤2.6586513\mu\le2.6586513. The previous best upper bound, μ≤2.662342426\mu\le2.662342426, is due to Couronné. Like the bounds of Pönitz and Tittmann and of Couronné, ours comes from a finite automaton that remembers a bounded part of the past of the walk. The new idea is to count bridges. Since they can all be preceded by the same infinite history, the automaton may treat as visited the unvisited cells that no infinite self-avoiding continuation can reach, and three tests on the current state and the next step recognize such cells. The bound is checked in exact integer arithmetic and proved in the Lean proof assistant.

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

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

math.CO — Combinatorics

Certified upper bounds for two sum-difference exponents

Contributed by Tejasvi Singh Tomar

For finite sets A,BA,B of real numbers and G⊆A×BG\subseteq A\times B, Katz and Tao proved in 1999 that {a−b:(a,b)∈G}\{a-b:(a,b)\in G\} has at most N11/6N^{11/6} elements whenever AA, BB and {a+b:(a,b)∈G}\{a+b:(a,b)\in G\} have at most NN elements; by an argument of Bourgain, bounds of this kind give lower bounds for the dimension of Kakeya sets. We lower the exponent 11/611/6 to 1.82731.8273, and to 1.82951.8295 in every abelian group. We also prove ∣X−Y∣≤∣X+Y∣1.4209|X-Y|\le|X+Y|^{1.4209} for all finite sets X,YX,Y of integers, improving the exponent 1.45431.4543 of Kleinwaks; through his transfer theorem, this lowers the upper bound for the sum-difference constant of Gyarmati, Hennecart and Ruzsa from 1.31241.3124 to 1.29621.2962. Both proofs add up entropy inequalities among integer combinations of coordinates of several copies of a random pair, with rational weights found by linear programming; all four bounds are also proved in Lean 4.

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

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

math.PR — Probability

Certified upper bounds for the Chvátal–Sankoff constant

Contributed by Tejasvi Singh Tomar

Let γ2\gamma_2 be the Chvátal–Sankoff constant, so that the expected length of a longest common subsequence of two independent uniformly random binary strings of length nn is γ2n+o(n)\gamma_2n+o(n). Lueker proved γ2≤0.826280\gamma_2\le0.826280 with a finite automaton that reads a pair of strings as a sequence of minimal match pairs and remembers the last hh symbols of each string, for h=8h=8. We carry out his method up to h=13h=13 and prove γ2≤0.821963\gamma_2\le0.821963. For h=13h=13 the certificate lists 165,695,219,469165{,}695{,}219{,}469 states of the automaton, reduced by a symmetry. The bound rests on an explicit positive vector for the weighted transition matrix of the automaton; a checker rebuilds every transition with its own code and verifies the required inequalities in exact integer arithmetic. We also give a complete proof that the automaton accepts the truncated canonical decomposition of every pair of strings, the property on which the method depends. The bound γ2≤0.821963\gamma_2\le0.821963 is also proved in the Lean 4 proof assistant, with a computation evaluated by compiled code, and the bounds γ2≤0.825101\gamma_2\le0.825101, γ2≤0.824120\gamma_2\le0.824120, γ2≤0.823290\gamma_2\le0.823290 and γ2≤0.822579\gamma_2\le0.822579 for h=9h=9, 1010, 1111 and 1212 by formal proofs that are checked entirely by the Lean kernel.

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

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

math.NT — Number Theory

Realizer Bounds and Repetition Constraints at the First Coefficient Crossing in the 3x + 1 Problem

Contributed by Elias De Jesús

Terras’s coefficient stopping time conjecture asks whether the shortcut Collatz orbit of every integer n ≥ 2 lies below n when its coefficient ρk = 3d/2k first falls below one. Here k counts shortcut steps and d counts their odd inputs. We prove that every eligible realizer descends when the first-crossing word has at most 75 maximal runs of odd inputs. Any counterexample requires at least 76 such runs, 10 439 860 591 steps and 6 586 818 670 odd inputs. The proof uses a lower bound on the seed from the length of its odd runs, rational approximations to log2 3, the verified range of Rozier and Terracol, and Rhin’s estimate for a linear form in logarithms. We also prove descent for a family with arbitrarily many odd runs. Two further restrictions narrow the remaining words. An initial square U U in a failing word satisfies |U | < 35 log2 k. For a counterexample of shortest crossing length, the reciprocal-sum estimate of Nikzad, Frinkle and Bagherzadeh gives a lower bound on ρk whose value begins 0.9441733669 . . .. The open inequality compares the least eligible starting value in each remaining parity class with an explicit threshold.

A mix of human-written and AI-generated textHuman understanding: some parts2-adic congruencesCollatz conjectureDiophantine approximationTerras conjecturecoefficient stopping timefirst coefficient crossingleast positive realizersodd-run decompositionparity vectorsreciprocal sums
Nov 15, 202612 pages
PDFView work

math.CO — Combinatorics

Constructions and explicit power savings for point--unit-circle incidences

Contributed by Yuda Chen, Yifei Wang

Let U(n,m)\mathcal U(n,m) be the maximum number of incidences between nn distinct points and mm distinct unit circles in the plane. We give two constructions and an explicit upper bound for this function. Writing s=min⁡(n,m)s=\min(n,m) and M=max⁡(n,m)M=\max(n,m), the first construction gives a four-piece monomial lower bound for all cardinalities, with balanced exponent 1.0411699201.041169920. The second gives balanced configurations along an unbounded sequence with exponent 1.04317223055397011.0431722305539701, and further unbalanced configurations. The upper bound is U(n,m)≪M+s2/3−2δM2/3+δ\mathcal U(n,m)\ll M+s^{2/3-2\delta}M^{2/3+\delta}, where δ=2−2664/514560000000>2−2665\delta=2^{-2^{664}}/514560000000>2^{-2^{665}}. The constructions use two windows in a relative-norm-one number-field lattice, strengthened arithmetic estimates, and interpolation between local profiles. The upper bound uses finite incidence regularization, prediction, arithmetic heights, and a six-by-five rigidity obstruction. The resulting bounds for the unit-distance problem follow as corollaries.

Primarily AI-generated textHuman understanding: some partsPoint--unit-circle incidencesarithmetic heightsclass field towersincidence boundsnumber-field latticespolynomial partitioningunit distances
Nov 15, 2026178 pages
PDFView work

math.CO — Combinatorics

Vector Packing and Sharp Bounds for Matrices of Bounded Rank

Contributed by Yair Lavi

We prove a packing theorem in real and complex normed spaces. Given a possibly infinite family of vectors (vj)(v_j) whose span has finite dimension r≥1r\ge1, let MM be the supremum of the norms of its finite linear combinations with coefficients of modulus at most one. If MM is finite, the family splits into rr nonempty sets, each with sum of norms at most MM. The same partition works for every norm on the span, using that norm's value of MM. We also determine exactly which finite lists of nonnegative numbers can be realized as the norms of a family of capacity one in some normed space of dimension at most kk. We also obtain sharp rank-dependent bounds for products of the moduli of the entries on generalized diagonals and the permanent of the entrywise modulus, extending the known nonnegative-matrix bounds to real and complex matrices. The packing theorem also gives sharp support and entropy bounds for doubly stochastic matrices of bounded rank.

A mix of human-written and AI-generated textHuman understanding: all partsStochastic matrixVector packingentropymajorizationmatrix rankpermanent
Nov 15, 202624 pages
PDFView work

cs.CC — Computational Complexity

An edge comparison with constant 3/2 and the coefficient 6/sqrt(2 pi) for the average sensitivity of polynomial threshold functions

Contributed by David Niedbala Giraudin

For every real polynomial threshold function f of degree at most d on the uniform cube {-1,1}^n we prove AS(f) <= min{n, 6 d b_n (n+d)/(n+2d)} <= (6/sqrt(2 pi)) d sqrt(n) < 2.394 d sqrt(n), where b_n = E|B_n - n/2| for B_n ~ Bin(n,1/2). The previous coefficient was 8/sqrt(2 pi) = 3.1915... The new ingredient is an edge comparison with constant 3/2 in place of 2 in OpenAI's weighted-grading argument: for every positive weight and every sign function h, the number of ordered equal-sign edges of h is at most (3/2)||MH+HM||_HS^2. The proof rests on the exact identity (Z_i M Z_i - M)^2 = I - A_i^2, where A_i is the grade-diagonal part of the multiplication by x_i. Combined with OpenAI's original coupling estimate alone, the lemma already gives AS(f) <= 6 d sqrt(n).

Primarily AI-generated textHuman understanding: no partsBoolean functionsaverage sensitivitycoupling inequalitypolynomial threshold functionstotal influenceweighted grading
Nov 15, 20264 pages
PDFView work

math.NT — Number Theory

Aigner's Three Monotonicities from Fibonacci Matrices and Six Snake Pieces

Contributed by Elleard Felix Webster Heffern

Starting from the established fact that Markov numbers count perfect matchings of their Markov snake graphs, we give a self-contained proof of the fixed-sum, fixed-numerator, and fixed-denominator orderings proposed by Aigner. The author's Fibonacci-matrix normalization begins with (AC)11−(B2)11=2(AC)_{11}-(B^2)_{11}=2 for consecutive odd-indexed Fibonacci blocks. Fibonacci matrices prove normalization and fixed-numerator monotonicity. The author's six-piece decomposition proves the remaining fixed-sum comparison and fixed-denominator monotonicity. We credit the matching correspondence to its original 2002–2003 REACH development and distinguish that history from the later ordering theorems.

Author comments: Standalone v4, 6 pages, 2 figures. The normalization and three ordering proofs also appear in Section 5 of Meridians; this standalone presentation makes them easier to find and cite. Earlier proofs of the orderings and the 2002–2003 matching correspondence retain their citations. The general Markov uniqueness conjecture remains open. Linked chronology: 8 November 2026: standalone v3: https://zenodo.org/records/24053747 11 November 2026: standalone v4, source, figures and finite-check reports: https://zenodo.org/records/24146546 12 November 2026: v4 PDF mirrored on ResearchGate: https://www.researchgate.net/publication/417809122_Aigner's_Three_Monotonicities_from_Fibonacci_Matrices_and_Six_Snake_Pieces 12 November 2026: corrected Meridians v22: https://zenodo.org/records/24167894 ; its Aigner arguments and figures are unchanged. The v4 source's version note records its original synchronization with v21. 13 November 2026: Meridians published on Hexagon: https://hexagonmath.org/2611.00410 Related computational supplements (2 November 2026): https://zenodo.org/records/23874075 ; current trillion-verification evidence accompanies the corrected Meridians archive above. Earlier project announcements, not announcements of this standalone proof: 21 October 2026, 15:18:25 UTC: X, earlier billion-scale verification: https://x.com/webystar/status/2112926487091282350 23 October 2026, 14:54:57.771 UTC: LinkedIn, earlier 9.3-billion verification: https://www.linkedin.com/posts/elleard-felix-webster-heffern-joseph-by-confirmation-2953a3104_markovnumbers-activity-7519411048115003392-4NaJ No separate social announcement for this paper has been independently verified.

A mix of human-written and AI-generated textHuman understanding: all partsAigner's conjecturesFibonacci matricesMarkoff numbersMarkov numberscombinatorial number theoryfixed-denominator monotonicityfixed-numerator monotonicityfixed-sum monotonicityperfect matchingssnake graphs
Nov 15, 20266 pages
PDFView work

math.RT — Representation Theory

A proof of Lusztig's connectedness conjecture in finite type

Contributed by Qiyue Tang

We prove that every equal-parameter Kazhdan–Lusztig left cell in a finite Weyl group is connected by simple left multiplications.

Author comments: I am posting this manuscript to share the mathematical results themselves. In doing so, I do not seek to assert ownership of the results or claim priority. I welcome anyone interested in checking the arguments or preparing a finished account, and I believe the eventual scholarly credit should go to those who undertake that work.

Primarily AI-generated textHuman understanding: no parts
Nov 13, 202630 pages
PDFView work

math.RT — Representation Theory

A proof of Lusztig’s conjectures for extended affine Weyl groups

Contributed by Qiyue Tang

We prove Lusztig’s conjectures P1–P15 for extended affine Weyl groups with positive integer-valued weight functions.

Author comments: I am posting this manuscript to share the mathematical results themselves. In doing so, I do not seek to assert ownership of the results or claim priority. I welcome anyone interested in checking the arguments or preparing a finished account, and I believe the eventual scholarly credit should go to those who undertake that work.

Primarily AI-generated textHuman understanding: no parts
Nov 13, 202657 pages
PDFView work

math.CO — Combinatorics

An Upper Bound Exponent of 0.9999873 for Square-Difference-Free Sets

Contributed by Eric Naslund

Let A⊆{1,…,N}A\subseteq\{1,\ldots,N\} contain no two distinct elements whose difference is a nonzero square, and let s(N)s(N) be the largest possible size of such a set. We prove \[ s(N)\le CN^{0.9999873} \] with an absolute constant CC. A recent preprint of OpenAI proves $s(N)\le CN^{1-\eps}$ for some absolute $\eps>0$. Their proof utilizes a certain average of the Fourier transform over (24!)161(24!)^{161} points, and for the parameter choices displayed there we calculate that they obtained $\eps\approx \exp_{10}(-\exp_{10}(\exp_{10}(5782.77)))$, in the sense that $\log_{10}\log_{10}\log_{10}(1/\eps)\approx5782.77$. We follow the same overall strategy, with new work at almost every quantitative step. The largest gain is the use of 7272 slots (positions at which the Fourier transform is evaluated) in place of (24!)161(24!)^{161}: the exponent is roughly a fixed constant divided by the number of slots, so this alone gains many orders of magnitude, but leaves far less room for loss elsewhere. Other savings come from the local construction at each prime. Small primes are handled jointly rather than one by one; and errors are measured in the actual half-distributions of the laws being compared, not bounded term by term against a product model. Where sums over the primes of a block of Weil-type error terms of size O(p−1/2)O(p^{-1/2}) would be too weak, we prove bounds of order O(p−1)O(p^{-1}) for the same error terms using \'etale cohomology over finite fields (Deligne's theorems and Katz--Sarnak monodromy for families of curves), the representation theory of GL2(Fp)\mathrm{GL}_2(\mathbf F_p), exact counts at p≡3(mod4)p\equiv3\pmod4, and a modular evaluation of Ahlgren and Ono. Dependence in our distributions is controlled by the correlation inequalities of Peyre and Kassabov. The remaining finitely many numerical inequalities are verified by exact computer arithmetic, listed in the appendices; all analytic steps are proved in the text. The companion repository \cite{NaslundUpperRepository2026} contains a partial Lean 4 formalization, totaling over 600,000 lines of lean. It establishes s(N)≤CN0.99999s(N)\le C N^{0.99999}, conditional on five named analytic inputs and explicit numerical hypotheses. This formalizes the most critical parts of the proof.

Primarily AI-generated textHuman understanding: some parts
Nov 13, 2026603 pages
PDFView work

math.CO — Combinatorics

The Sharp Exponential Constant for 6-Regular Circulant Matrices

Contributed by Yair Lavi

We prove that, for every integer n≥6n\ge6 and six-element set S⊆ZnS\subseteq\mathbb Z_n, the binary circulant Cn(S)=(1{j−i∈S})i,j∈ZnC_n(S)=(1_{\{j-i\in S\}})_{i,j\in\mathbb Z_n} satisfies per⁡Cn(S)≥((3125/1296)e7/250000)n\operatorname{per}C_n(S)\ge((3125/1296)e^{7/250000})^n. For every integer d≥2d\ge2, we identify the optimal uniform base as inf⁡n≥dinf⁡∣S∣=dper⁡Cn(S)1/n=lim⁡q→∞per⁡Cqd−1({0,1,q,…,qd−2})1/qd−1\inf_{n\ge d}\inf_{|S|=d}\operatorname{per}C_n(S)^{1/n}=\lim_{q\to\infty}\operatorname{per}C_{q^{d-1}}(\{0,1,q,\ldots,q^{d-2}\})^{1/q^{d-1}}, where S⊆ZnS\subseteq\mathbb Z_n and qq runs through integers at least 22. In degree six this base is at most 1638128736631981/35163812873663198^{1/35}, while the lower bound strictly exceeds the sharp unrestricted base 3125/12963125/1296. This resolves the surviving circulant lower-bound question in Minc's Problem 10; its proposed full upper bound fails even for circulants.

Author comments: The supplement cited in the text (supplement-v7.tar.gz) is in the Zenodo record https://doi.org/10.5281/zenodo.23044484.

A mix of human-written and AI-generated textHuman understanding: all partsBinary circulantMatching entropyMatching measureMinc's Problem 10Regular bipartite graphpermanent
Nov 13, 202615 pages
PDFView work

math.CO — Combinatorics

A Conjecture on the Permanent of Positive Semidefinite Matrices

Contributed by Yair Lavi

We state the following conjecture of the author and prove it for n≤5n\leq5. Let A=(aij)A=(a_{ij}) be a complex positive semidefinite n×nn\times n matrix with n≥1n\geq1, and let χλ\chi_\lambda be an irreducible character of SnS_n of degree dλd_\lambda. For σ∈Sn\sigma\in S_n, put aσ=∏i=1nai,σ(i)a_\sigma=\prod_{i=1}^n a_{i,\sigma(i)}. The conjecture asserts that ∑σ,τ∈Snχλ(στ)aσaτ≤dλ(per⁡A)2.\sum_{\sigma,\tau\in S_n}\chi_\lambda(\sigma\tau)a_\sigma a_\tau \leq d_\lambda(\operatorname{per}A)^2. We show that Soules' permanent-on-top conjecture implies this inequality, and that it in turn implies both Lieb's immanant dominance and Chollet's permanent inequality. We also settle the previously unresolved order-four case of Soules' conjecture.

Author comments: The supplement cited in the text (exact certificates, order-four proof inputs and checking programs; ZIP, 176.5 MB) is in the Zenodo record https://doi.org/10.5281/zenodo.22976216.

A mix of human-written and AI-generated textHuman understanding: all partsChollet conjecturePositive semidefinite matrixSchur power matriximmanantpermanent
Nov 13, 20268 pages
PDFView work

math.CO — Combinatorics

An order-eleven counterexample to triangular realization of sign matrix permanents

Contributed by Weiming Zhang

We construct an 11×1111\times11 sign matrix with permanent P=2 029 568P=2\,029\,568. An exhaustive enumeration shows that \(\lvert\per B\rvert\ne P\) for every sign matrix BB of order eleven whose entries below the diagonal are all +1+1. This gives a negative answer to a question of Ingram and Razborov.

Primarily AI-generated textHuman understanding: all parts
Nov 13, 202612 pages
PDFView work

math.NT — Number Theory

Verification of the Markov Uniqueness Conjecture for the First One Trillion Markov Values: Meridians on the Markov Surface and Farey Addresses

Contributed by Elleard Felix Webster Heffern

The Markov unicity problem asks whether the largest entry of a positive integer solution determines the other two. We organize the triples into families called Meridians, with compact addresses and explicit evaluation rules. The construction starts with catenary profiles: a fixed host sets the curve, and two heights one unit apart solve the Markov equation with that host. Selected positions give integer triples. Reversing geometric descent gives an exact indexing of these triples. Remainder patterns, growth bounds, corridor paths, and Fibonacci-matrix and snake-graph arguments then restrict possible collisions. The Meridian description of starting scales and logarithmic spacing guided the organization of a large verification into magnitude bands. The implementation uses Farey addresses and certified matrix bounds to select each band; its correctness does not require the Meridian collision theorems. Production finished on 10 November 2026 at 03:54:13 UTC (9 November, 21:54:13 CST). The combined computation compared 1,101,388,071,945 configurations and certified uniqueness of the first one trillion Markov values in numerical order. The trillionth value has 1,021,609 decimal digits. All 12 repeated 64-bit residue groups were resolved by exact arithmetic, with no equal maxima. On eight workers, retained active band processing took 23 h 57 min 23.146 s, including the inherited 500-billion certificate; the maximum recorded temporary key-file footprint was 1,065,664,392 bytes (0.992 GiB). This elapsed processing time is distinct from summed CPU time and the calendar span. Both final replays passed. A separate computer-checked certificate covers all 5,067,077 Meridians of degree at most 10,000, at every integer phase. The general unicity problem remains open.

Author comments: Version 22 (12 November 2026), 44 pages: revised title and abstract, including the 1,021,609-digit trillionth value; added Arthur Baragar's 1996 benchmark (M < 10^140). The proofs, figures and verification evidence are unchanged. Chronology (distinct announcements and deposits): 21 October 2026, 15:18:25 UTC: X announcement of an earlier search exceeding one billion values: https://x.com/webystar/status/2112926487091282350 23 October 2026, 14:54:57.771 UTC: LinkedIn announcement of the earlier 9.3-billion search in 24 minutes: https://www.linkedin.com/posts/elleard-felix-webster-heffern-joseph-by-confirmation-2953a3104_markovnumbers-activity-7519411048115003392-4NaJ 2 November 2026: 50-billion verification and degree-10,000 computational supplements: https://zenodo.org/records/23874075 9 November 2026: selected full decimal expansions first deposited: https://zenodo.org/records/24093257 10 November 2026: v21 trillion-verification deposit (publication-date field: 9 November): https://zenodo.org/records/24096109 12 November 2026: corrected v22 manuscript; Zenodo DOI reserved (deposit pending): https://doi.org/10.5281/zenodo.24167894 12 November 2026: ResearchGate full-text mirroring began: https://www.researchgate.net/publication/417066856_Meridians_on_the_Markov_Surface_Growth_Structure_and_Verification_of_One_Trillion_Markov_Values_Using_Farey_Addresses The earlier X and LinkedIn announcements are not announcements of the trillion result. The source releases preserve the original verification timestamps and separate software licenses. The general unicity conjecture remains open.

A mix of human-written and AI-generated textHuman understanding: all partsFarey fractionsFrobenius conjectureMarkoff numbersMarkov numbersMarkov treeMarkov uniqueness conjectureMeridianscertified computationcomputational number theorysnake graphs
Nov 13, 202644 pages
PDFView work

math.AG — Algebraic Geometry

The Shapiro–Shapiro conjecture for ordered positive flags

Contributed by Qiyue Tang

We prove the Shapiro–Shapiro conjecture for ordered totally positive flags in Grassmannians.

Author comments: I am posting this manuscript to share the mathematical results themselves. In doing so, I do not seek to assert ownership of the results or claim priority. I welcome anyone interested in checking the arguments or preparing a finished account, and I believe the eventual scholarly credit should go to those who undertake that work.

Primarily AI-generated textHuman understanding: no parts
Nov 13, 202615 pages
PDFView work

math.RT — Representation Theory

Domino insertion and cells in type B

Contributed by Qiyue Tang

We prove Conjectures A, A+^{+}, and B of Bonnafé, Geck, Iancu, and Lam on Kazhdan–Lusztig cells in type BB.

Author comments: I am posting this manuscript to share the mathematical results themselves. In doing so, I do not seek to assert ownership of the results or claim priority. I welcome anyone interested in checking the arguments or preparing a finished account, and I believe the eventual scholarly credit should go to those who undertake that work.

Primarily AI-generated textHuman understanding: no parts
Nov 12, 202614 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

cs.DS — Data Structures and Algorithms

Sorting networks on 13 inputs need at least 44 comparators

Contributed by Tejasvi Singh Tomar

Let S(N)S(N) be the least number of comparators in a sorting network on NN inputs. We prove S(13)≥44S(13)\ge44, one more than the previously best proved lower bound. We also prove P(2,N)=⌈log⁡2F(N)⌉P(2,N)=\lceil \log_2 F(N)\rceil for 3≤N≤323\le N\le32, where P(2,N)P(2,N) is the least worst-case number of comparators met by the two largest inputs in a network that delivers them to fixed outputs and FF is an explicit function of Van Voorhis; the lower bound comes from a finite search based on the structure of the paths of these two values. Starting from Harder's S(11)=35S(11)=35 and S(12)=39S(12)=39, these values of P(2,N)P(2,N), the two-value bound S(N)≥S(N−2)+P(2,N)S(N)\ge S(N-2)+P(2,N) and the one-value bound S(N)≥S(N−1)+⌈log⁡2N⌉S(N)\ge S(N-1)+\lceil \log_2 N\rceil give the twenty lower bounds on S(N)S(N) for 13≤N≤3213\le N\le32 in Dobbelaere's table; these bounds rested on Van Voorhis's inequality P(2,N)≥⌈log⁡2F(N)⌉P(2,N)\ge\lceil \log_2 F(N)\rceil, whose published proof is invalid. The bound S(13)≥44S(13)\ge44 is also proved in Lean 4, with every step checked by Lean's kernel.

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

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

math.CO — Combinatorics

Subplanes of order 3 and maximal arcs in projective planes of order 12

Contributed by Tejasvi Singh Tomar

Whether a projective plane of order 12 exists is open. A subplane of order 3 of such a plane is a case of equality in Bruck's bound n≥m2+mn\ge m^2+m; the 27 points on no line of the subplane then form a maximal arc of degree 3, and together with the subplane a maximal arc KK of degree 4. We show that every line of a subplane of order 3 contained in KK lies in at most two such subplanes, whereas in PG(3,3)\mathrm{PG}(3,3), which like KK has 40 points, a line lies in four planes; the proof uses Egan and Wanless's classification of triples of mutually orthogonal Latin squares of order 9. We also show that AG(3,3)\mathrm{AG}(3,3) is not the design of any maximal arc of degree 3 in a plane of order 12, and that a permutation of the points that maps a subplane of order 3 onto itself and each line meeting it onto a line cannot have prime order other than 3. The proofs are computer-assisted, and their SAT refutations are certified.

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

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

cs.CC — Computational Complexity

Which Fine-Grained Lower Bounds Survive the Refutation of 3SUM and APSP?

Contributed by Tejasvi Singh Tomar

Alman and Vassilevska Williams have refuted the 3SUM and APSP hypotheses. Their algorithms rest on counting the triangles through prescribed edges of lopsided tripartite graphs, whose middle part has nεn^{\varepsilon} vertices for a small ε\varepsilon. Majdoddin extended the method to every ε<ln⁡4/(5ln⁡5)≈0.172\varepsilon<\ln4/(5\ln5)\approx0.172. We determine which of the main conditional lower bounds derived from the refuted hypotheses survive. We also prove that the method extends to every ε<0.17843\varepsilon<0.17843 when the prescribed edges are known in advance and there are at most n2−ε/2n^{2-\varepsilon/2} of them, which confirms Majdoddin's numerical estimate. Whether a bound survives depends mostly on the instances that its reduction produces. The reductions behind most bounds produce instances outside the range of the new algorithms: balanced graphs, or lopsided graphs with a larger middle part. Most of the set-disjointness, dynamic-graph and triangle bounds therefore follow from hypotheses that no known algorithm contradicts. These hypotheses, however, concern mainly such instances, and for several bounds the hypothesis is the bound itself, stated for these instances. Their evidence came largely from the refuted hypotheses. A few bounds are false, among them a lower bound of Goldstein, Lewenstein and Porat for Set Disjointness over small universes; the Strong SetDisjointness Conjecture also fails at small polynomial query times. Other bounds have lost their support, such as the Set Disjointness trade-offs of Kopelowitz, Pettie and Porat over small universes apart from constant query time. Finally, we collect the known obstacles to a larger closed-form range with a different base identity and use border-rank lower bounds to exclude several natural candidates.

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

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

math.PR — Probability

The L¹ Poincaré constant of the Hamming cube

Contributed by Tejasvi Singh Tomar

Let CC be the smallest constant such that E∣f−Ef∣≤C E∣∇f∣\mathbb{E}|f-\mathbb{E} f|\le C\,\mathbb{E}|\nabla f| for every real-valued function ff on every Hamming cube {−1,1}n\{-1,1\}^n, where ∣∇f∣|\nabla f| is the Euclidean length of (D1f,…,Dnf)(D_1f,\dots,D_nf) and Djf(x)=(f(x)−f(x(j)))/2D_jf(x)=(f(x)-f(x^{(j)}))/2. Ben Efraim and Lust-Piquard proved C≤π/2C\le\pi/2, the Gaussian case gives C≥π/2C\ge\sqrt{\pi/2}, and Ivanisvili, Li, van Handel and Volberg asked whether C=π/2C=\sqrt{\pi/2}. We prove that it is, with an explicit constant cn<π/2c_n<\sqrt{\pi/2} in dimension nn. The proof turns on an integral of first absolute moments of sums of independent biased random signs: we compute it exactly when the coefficients are nonnegative, and show, with a sampled Fejér kernel, that it can only grow when the coefficients are replaced by their absolute values. The equality C=π/2C=\sqrt{\pi/2} is also proved in Lean 4 with Mathlib.

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

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

math.CO — Combinatorics

A thrackle on n vertices has fewer than 4n/3 edges

Contributed by Tejasvi Singh Tomar

A thrackle is a drawing of a graph in the plane in which every two edges meet exactly once, either at a common endpoint or at a proper crossing. Conway conjectured that a thrackle with nn vertices has at most nn edges. We prove that a thrackle with n≥4n\ge4 vertices has at most 43(n−1)\frac43(n-1) edges, improving the bound 1813(n−1)\frac{18}{13}(n-1) obtained by Tóth and, independently, by Scoppetto. The proof combines Xu's discharging argument with two computer searches, by the method of Fulek and Pach, showing that two generalized dumbbells in the sense of Fulek and Pach are not thrackleable: DB(6,8,−1)\mathrm{DB}(6,8,-1) is a 66-cycle and an 88-cycle sharing one edge; DB(6,10,−3)\mathrm{DB}(6,10,-3) is a 66-cycle and a 1010-cycle sharing a path of three edges. A formal proof in Lean 4 derives the bound from five properties of thrackles and checks the computational facts it uses; Section 6 states what this proof trusts.

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

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

cs.IT — Information Theory

The automorphism group of an extremal [72,36,16] code is trivial

Contributed by Tejasvi Singh Tomar

Whether a binary doubly-even self-dual [72,36,16][72,36,16] code exists is a question raised by Sloane in 1973. A series of papers, surveyed by Borello, shows that the automorphism group of such a code is trivial or isomorphic to C2C_2, C3C_3, C2×C2C_2\times C_2 or C5C_5. We prove that such a code has no automorphism of order 22, 33 or 55, and hence no nontrivial automorphism. Each such automorphism reduces the problem to a finite computer search. For order 22 the search runs over symmetric bilinear forms on the 4141 self-dual [36,18,8][36,18,8] codes. An automorphism of order 33 leads to a search over labellings of the Hermitian self-dual [24,12,8][24,12,8] codes over F4\mathbb{F}_4 by the extended Golay code. Order 55 reduces to 7×77\times7 unitary matrices over F16\mathbb{F}_{16}. Along the way we classify the Hermitian self-dual [24,12,8][24,12,8] codes over F4\mathbb{F}_4: there are 26 924 93126\,924\,931 of them up to monomial equivalence.

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

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202622 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

cs.DS — Data Structures and Algorithms

Exact sizes of networks that select the three or four largest of n elements

Contributed by Tejasvi Singh Tomar

We study (t,n)(t,n)-selection networks, which move the tt largest of nn inputs to tt given lines in any order, and the least number U^t(n)\hat U_t(n) of comparators in such a network. Alekseev showed that U^t(n)≥(n−t)⌈lg⁡(t+1)⌉\hat U_t(n)\ge(n-t)\lceil\lg(t+1)\rceil. For t=2k≥4t=2^k\ge 4 we raise this bound by k−1k-1 for every n>tn>t, and by 2k−52k-5 when t≥32t\ge 32; as far as we know, these are the first improvements at powers of two. The proofs follow the weights of the lines, and a pruning step of Yao extends the gain to every t≥3t\ge 3. For t=3t=3, Yao's upper bound 2n−5+⌊lg⁡(n−3)⌋2n-5+\lfloor\lg(n-3)\rfloor is exact for 4≤n≤184\le n\le 18. For t=4t=4 the new bound is 3n−113n-11 for all n≥5n\ge 5, and the value 3n−103n-10 that Knuth expected is exact for 6≤n≤126\le n\le 12. Their lower bounds rest on exhaustive searches at a few sizes and on the fact that one more input costs at least two more comparators. Most of the results are also proved in Lean 4, some through compiled checks.

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

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

math.CO — Combinatorics

The Cranston–Li–Su–Wang–Xu (2026) conjecture is true

Contributed by Dave Goel

Let A be a finite abelian group. A nowhere-zero A-flow of a graph can be changed along a cycle: going around the cycle, add a fixed non-zero element of A to the value of every edge that points forward and subtract it from the value of every edge that points backward. The Cranston–Li–Su–Wang–Xu (2026) conjecture on the reconfiguration of nowhere-zero flows states that if A has at least four elements, then in every graph in which all degrees are even, any two nowhere-zero A-flows are joined by a chain of such changes through nowhere-zero A-flows. It also states that, for every integer k ≥ 4, the same holds for integer flows whose values are between 1 and k − 1 in absolute value, where each change adds a non-zero integer. We prove this conjecture. The proof is by induction on the number of edges. If a flow enters a vertex along one edge and leaves it along another edge with the same value, the two edges can be replaced by a single edge; this gives a smaller graph. The main step is to change every flow into a flow with such a pair of edges. For A-flows we do this when all degrees are at most 4; repeatedly replacing a vertex of degree at least 6 by a triangle, following Cranston et al., reduces the general case to this one. For integer flows, we show that, in a graph in which all degrees are even, any two nowhere-zero flows with values in the cyclic group Z_k, k ≥ 4, are joined by changes that add only 1, −1, 2 or −2, and that such changes lift to integer flows. All theorems of this paper are also proved in the Lean 4 proof assistant.

Author comments: An expanded version of this paper is posted on Zenodo: https://doi.org/10.5281/zenodo.23605838

A mix of human-written and AI-generated textHuman understanding: some partsEulerian graphflow-connected graphgroup flownowhere-zero flowreconfiguration
Nov 12, 202615 pages
PDFView work

math.CO — Combinatorics

Optimal Packing of Eleven Unit Squares: The Formalized Voronoi-Cell Proof

Contributed by Manasseh Ahmed

We explain the computer-assisted proof that eleven independently rotated unit squares require a square container of side at least T = 3.8770835900228141773 . . ., the side attained by the known construction attributed to Walter Trump. The proof reduces arbitrary packings to 2,184 patterns of occupied closed Voronoi cells. Exact geometric certificates exclude 2,180 patterns, a square-symmetry argument reduces the remaining four to one, and a complete subdivision of that case places every possible smaller packing inside an explicitly certified isolation neighborhood. We give the geometric definitions, prove the continuous soundness rules underlying the finite calculations, and explain the common-cone local isolation argument used in the Lean development. The large certificate instances are identified by pinned source references; they are not replaced by numerical experiments. The reported formal verification uses Lean’s kernel together with its native compiler for specified numerical certificates.

Primarily AI-generated textHuman understanding: some parts
Nov 12, 202628 pages
PDFView work

math.CO — Combinatorics

The independence number of the generalized Johnson graph J(13,5,3)J(13,5,3)

Contributed by Mustafa Stanikzai

Let J(13,5,3)J(13,5,3) be the graph on the 5-element subsets of a 13-element set, two subsets being adjacent when they share exactly 3 elements. We prove that α(J(13,5,3))=33\alpha(J(13,5,3)) = 33. The graph is an explicit unit-distance graph in R12\mathbb{R}^{12}, so χ(R12)≥⌈1287/33⌉=39\chi(\mathbb{R}^{12}) \ge \lceil 1287/33 \rceil = 39; earlier bounds from explicit finite graphs give at most 38. A recent preprint of Davies gives much larger bounds, none from an explicit finite graph. An explicit independent set gives α≥33\alpha \ge 33. For the upper bound, a symmetry reduction splits the problem into 200 clique subproblems, and a certifying solver refutes each one with a proof log that the checker VeriPB accepts. An uncertified computation reproduces the value α(J(13,6,4))=46\alpha(J(13,6,4)) = 46 reported by Exoo and Ismailescu, which gives χ(R12)≥38\chi(\mathbb{R}^{12}) \ge 38.

Author comments: 16 pages. Programs, certificates and proof logs: https://doi.org/10.5281/zenodo.24145863 Changes from version 1: 28 cross-references to lemmas, propositions, claims, definitions and corollaries were printed with the word "Theorem" (for example "Theorem 2.4" for Lemma 2.4). They now carry the correct names. The reference numbers were already correct. Statements, proofs, results and bibliography are unchanged.

A mix of human-written and AI-generated textHuman understanding: all partschromatic number of Euclidean spacegeneralized Johnson graphindependence numbermaximum cliqueproof loggingunit-distance graph
Nov 12, 202616 pages
PDFView work

math.CO — Combinatorics

The Maximum of per⁡(I−A)\operatorname{per}(I-A) in Odd Order

Contributed by Yair Lavi

Let ΩnΩ_n denote the set of n×nn\times n doubly stochastic matrices. Kim and Roush conjectured in 1981 that, for n=2k+1>1n=2k+1>1, max⁡A∈Ω2k+1per⁡(I−A)=3⋅2k−2 \max_{A\inΩ_{2k+1}}\operatorname{per}(I-A)=3\cdot 2^{k-2}. They proposed the block construction A⋆=12(J3−I3)⊕P2⊕(k−1)A_\star=\frac12(J_3-I_3)\oplus P_2^{\oplus(k-1)}, where P2=(0110)P_2=\begin{pmatrix}0&1\\1&0\end{pmatrix}. Here J3J_3 is the 3×33\times3 all-ones matrix. They did not claim uniqueness. We fully prove their conjecture and classify equality: the maximizers are exactly the simultaneous-permutation conjugates of A⋆A_\star.

A mix of human-written and AI-generated textHuman understanding: all partsDoubly stochastic matrixFunctional digraphpermanent
Nov 12, 202611 pages
PDFView work

math.CO — Combinatorics

A counterexample to the Foregger-Sinkhorn tie-point conjecture

Contributed by Yair Lavi

The Foregger-Sinkhorn tie-point conjecture asserts that if a nearly decomposable doubly stochastic matrix minimizes the permanent on a face and the permanental cofactor at a prescribed zero is larger than its permanent, then that zero is a tie point. We give a counterexample in dimension eight.

A mix of human-written and AI-generated textHuman understanding: all partsDoubly stochastic matrixNearly decomposable matrixcounterexamplepermanent
Nov 12, 202610 pages
PDFView work

math.CO — Combinatorics

The Maximum Permanent of a Stochastic Matrix of Bounded Rank

Contributed by Yair Lavi

Let AA be a stochastic n×nn\times n matrix with rank⁡A≤k\operatorname{rank}A\leq k, where 1≤k≤n1\leq k\leq n. Write n=qk+sn=qk+s, where 0≤s<k0\leq s<k. The author conjectured in 2018 that per⁡A≤(q!/qq)k−s((q+1)!/(q+1)q+1)s\operatorname{per}A\leq (q!/q^q)^{k-s}((q+1)!/(q+1)^{q+1})^s, with equality if and only if A=P(Jq⊕(k−s)⊕Jq+1⊕s)QA=P(J_q^{\oplus(k-s)}\oplus J_{q+1}^{\oplus s})Q, where P,QP,Q are permutation matrices and JtJ_t is the t×tt\times t matrix with every entry 1/t1/t. We prove this conjecture in full.

A mix of human-written and AI-generated textHuman understanding: all partsBounded rankStochastic matrixpermanent
Nov 12, 202614 pages
PDFView work

math.CO — Combinatorics

The Marcus-Minc Transform Inequality

Contributed by Yair Lavi

We prove the Marcus-Minc conjecture: let n be any integer at least 2, and let A be a nonnegative n by n matrix whose row and column sums are all one. Form a new matrix by subtracting A from the n by n matrix of ones and dividing by n minus one. Then the permanent of A is at least the permanent of the new matrix. We also determine all equality cases.

A mix of human-written and AI-generated textHuman understanding: all partsDoubly stochastic matrixMarcus-MincMatrix inequalitypermanent
Nov 12, 202611 pages
PDFView work

quant-ph — Quantum Physics

Exact projector-rank thresholds for state-independent contextuality

Contributed by Sunay Venkat

For every integer r ≥ 1 we construct a finite exclusivity graph Fr with the following two properties. First, Fr has a projective representation by pairwise distinct projectors of rank r that exhibits state-independent contextuality. Second, no projective representation of Fr by projectors of any common rank s < r, in any finite dimension, exhibits state-independent contextuality; in every such representation the maximally mixed state is noncontextual. This establishes, for every r, the “rank efficient” scenarios sought by Hohn, Xu and Kleinmann, for which only numerical evidence at r = 2, 3 was available. The graph is the disjunctive product of an odd cycle C2r+1 with the orthogonality structure of a rank-one contextuality set whose fractional chromatic number exceeds its dimension by an arbitrarily small amount. Such sets are obtained from the infinite family of Kochen–Specker parity proofs in R^4 of Elford and Lisonek, together with a coning construction that raises the dimension by one.

Primarily AI-generated textHuman understanding: some partsprojector-rank thresholdsquantum contextualitystate-independent contextuality
Nov 12, 20266 pages
PDFView work

math.MG — Metric Geometry

On the local geometry of the tight 39-point code in the octonionic projective plane

Contributed by Robert R. MacGregor

Cohn, Kumar and Minton constructed a four-parameter family of tight 3939-point codes in the octonionic projective plane. We show that near each member outside a closed nowhere-dense set of resonant parameters, the labeled tight codes modulo F4F_4 form exactly four ten-dimensional families, any two meeting in the four-parameter family, although the first-order deformations of the member form a 2828-dimensional space modulo F4F_4. The originally constructed code is resonant, and we do not determine the tight codes near it; but every neighborhood of it in the space of unlabeled tight 3939-point codes modulo F4F_4 contains a nonempty open subset homeomorphic to an open subset of R10\mathbb R^{10}, so any neighborhood of it that is a manifold has dimension ten.

Author comments: 55 pages, 5 figures. Ancillary files: anc/native-data.json holds the exact coefficients of Appendix C, and anc/finite-identities.py replays the finite identities of Proposition 6.5 from it in exact arithmetic. Lean source: https://github.com/macgregor-sudo/tight-39-code at commit 46f01c1.

Primarily AI-generated textHuman understanding: no partsAlbert algebraF4Leandeformationmutually unbiased basesoctonionic projective planetight code
Nov 12, 202655 pages
PDFView work

math.CO — Combinatorics

The exact diameter of the symmetric group 𝑆𝑛 with LRX generators

Contributed by Sergei Uskov, Alexander Chervov, Fedor Levkovich-Maslyuk, Ivan Litvak, Andrei Smolensky, Alexander Soibelman, Dia Taha

We consider the undirected Cayley graph of the symmetric group 𝑆𝑛 with respect to the cyclic shift 𝐿, its inverse 𝑅, and the transposition 𝑋 of the first two positions. We prove that its diameter is given by 𝑛(𝑛 − 1)/2 for every 𝑛 ≥ 4, thus settling a conjecture open since at least 2011. This is done by separately establishing sharp upper and lower bounds, invoking a variety of combinatorial and group-theoretic arguments which leave a finite set of special cases that are verified in the accompanying C++ code. We also provide a Lean formalization of the results.

A mix of human-written and AI-generated textHuman understanding: some partsCayley graphsLean 4formal verificationsymmetric groups
Nov 12, 202643 pages
PDFView work