CS Paper Radar

A new upper bound for $A(19,6,8)$

Jiang Chang

cs.IT math.CO ·submitted 2026-10-30 14:26 UTC · v1
theory

Abstract

We compute Polak's bound $A_4(19,6,8)$ for binary constant weight codes, obtaining the numerical value $673.04001$. An exact rational certificate gives $A_4(19,6,8)\le 673.0400143064802474039375132665301315202504$, and hence $A(19,6,8)\le 673$. This improves the upper bound $693$ listed in Brouwer's table. The certificate is verified by a separate program using exact rational arithmetic.

Comment
3 pages

Closest papers

Nearest neighbours by meaning across the whole index.

New lower bounds for binary constant-weight codes from prescribed-automorphism search, and two quantum codes meeting their upper bounds

cs.IT math.CO ·2026-10-16 ·Chris Dzoba
theory similarity 0.61
Abstract · 12 pages. Code word lists, group generators, orbit representatives, two independent checkers, verification outputs, quantum stabilizers and …

We give explicit binary constant-weight codes that raise the lower bounds on $A(n,6,w)$ in eight cells of Brouwer's table, all now listed there. The first round (9 October 2026) gave four values: $A(27,6,11)\ge 19305$, $A(27,6,12)\ge 24453$, $A(28,6,10)\ge 18642$ and $A(28,6,9)\ge 11154$, together with an explicit $A(24,6,12)$ code of 5566 words, now in the table's list of lost codes. The second round (14 October 2026) gave seven values, listed in the table since 15 October 2026: $A(29,6,10)\ge 27183$, $A(29,6,11)\ge 42042$, $A(29,6,9)\ge 14781$, $A(28,6,10)\ge 19110$, $A(27,6,12)\ge 24804$, $A(28,6,9)\ge 11388$ and $A(27,6,13)\ge 27783$, three of which replace first-round values. Every code is a union of orbits of the semilinear affine group $\mathrm{AΓL}(1,27)$, its index-2 subgroup, or $\mathrm{AGL}(1,23)$, acting on all but at most two coordinates. The orbits were chosen by maximum-weight independent set search on the orbit conflict graph: branch and bound in the first round, iterated local search in the second. Each code was checked by two separately written programs over all pairs of words and was regenerated from its generators and orbit representatives. We also report two qubit stabilizer codes, $[[20,11,4]]$ and $[[43,32,4]]$, which raise the lower bounds of 3 listed at codetables.de to the listed upper bound 4.

0.23

Exact rational certificates and a Lean formalization of the eleven-variable Vasc inequality

cs.SC ·2026-10-09 ·Dakai Guo, Ruichen Qiu, Yichuan Cao, Ruyong Feng, Xiao-Shan Gao
theorycode/data similarity 0.57
Abstract

We prove that the cyclic sum $\sum_{i=0}^{10}(x_i-x_{i+1})/(x_{i+1}+x_{i+2})$ is nonnegative for every strictly positive real eleven-tuple, with indices taken modulo eleven. Clearing denominators reduces the problem to a homogeneous polynomial. Subtracting the smallest coordinate then separates the proof into nonnegativity of a common-translation derivative and nonnegativity on a full boundary face. We supply exact rational polynomial certificates in Gram-matrix form for both statements. The derivative certificate uses a linear multiplier, centered monomials and cyclic averaging; the boundary certificate uses a strictly positive quadratic multiplier and uncentered monomials. Their verification requires 6,069 cyclic coefficient comparisons and 34,304 literal coefficient comparisons. All 606 certificate matrices are certified by integer congruences with strictly diagonally dominant images. A Lean 4 development formally verifies the certificate checks and their connection to the original inequality. The exact certificate data, replay programs, and formal sources are publicly available.

0.20

Sharp Degree Bounds for Putinar Certificates in Terms of the Positivity Margin via Analytic Sums of Squares

cs.CL ·2026-10-18 ·Yuxiang Zhao, Ting Gan
theory similarity 0.56
Abstract

We establish sharp degree bounds for Putinar sum-of-squares (SOS) certificates in terms of the positivity margin $δ$. For any fixed Archimedean quadratic module with prescribed generators and any fixed degree bound on the objective, normalized polynomial objectives admit a uniform certificate-degree upper bound of $O(δ^{-1/2}\log^2(2/δ))$. The bound is sharp: we construct a matching lower-bound example in three variables. We further show that the number of inequality generators affects the optimal degree bound. For quadratic modules with at most two inequality generators, the bound improves to $O(δ^{-1/2}\log(2/δ))$, which is also sharp. This improvement is obtained by directly converting two-generator Stengle refutations into certificates for the original quadratic module. We also establish sharp degree bounds for trigonometric SOS certificates on tori. In particular, for the full torus without additional constraints, the optimal worst-case order improves to $δ^{-1/4}$, whereas additional equality constraints can lead the order to $δ^{-1/2}\log(2/δ)$. These results also yield sharp worst-case convergence rates for the Lasserre hierarchy.

0.32

A Finite Certificate for the Positive $n=11$ Vasc Inequality

cs.SC ·2026-10-03 ·Tiancheng Xu, Wensheng Yu
theory similarity 0.55
Abstract

We establish the Vasc cyclic inequality for all strictly positive real eleven-tuples by a finite exact certificate. Cyclic rotation places a minimum at the first position, and rank words together with cumulative gaps reduce the problem to $10!=3{,}628{,}800$ homogeneous integer polynomials of degree eleven. Independent coefficient reconstruction proves $3{,}358{,}617$ roots directly. The remaining $270{,}183$ roots are covered by $267{,}952$ ordinary midpoint certificates, $2{,}195$ complete binary subdivision certificates, and $36$ complete certificates containing partial sorting nodes. Each nontrivial leaf is checked by subtracting weighted AM-GM midpoint circuits from a positive multiple of the transformed polynomial and verifying every residual coefficient. Explicit word-set comparisons certify disjointness and exact coverage. We prove the soundness of the leaves and both subdivision rules, then recover the rational inequality by positive denominator clearing and continuity. The resulting proof combines explicit mathematical reductions with independently checked exact integer certificates.

0.47

Quantum bivariate bicycle codes with weight-8 checks surpassing the BB benchmark

cs.IT quant-ph ·2026-09-06 ·Liangdong Lu, Ruipan Yang, Guanmin Guo
benchmarktheory similarity 0.54
Abstract

Bivariate bicycle (BB) codes of Bravyi \emph{et al.}~\cite{Bravyi2024} are quantum low-density parity-check codes with weight-$6$ checks, exemplified by $[[144,12,12]]$ with $kd^2/n=12$. We develop the algebraic structure theory of BB-type codes with weight-$8$ checks (weight-$4$ generator polynomials) and use it, together with an exactly validated search pipeline, to construct and certify new codes. We prove an exact dimension formula $k=2\dim R/(A,B)$ (forcing even $k$), a $4\ell m$-element symmetry group on generator pairs, an $X/Z$ distance equality $d_X=d_Z$, and a family of subgroup-coset kernel vectors giving rigorous distance upper bounds and a design rule for high-distance constructions; all distances are computed exhaustively by a cross-validated bit-mask verifier. At $n=144$ the pipeline returns a census of $53$ codes whose strongest members surpass the BB benchmark: $[[144,6,d\ge 15]]$ exceeds the benchmark distance $12$ (certified $d\ge 15$), $[[144,10,12]]$ reaches it with weight-$8$ checks, and $[[144,16,10]]$ encodes a third more logical qubits at $kd^2/n=11.11$ ($7.4\%$ below benchmark) while decoding no worse. At $n=72$, $[[72,14,8]]$ attains $kd^2/n=12.44$---more than twice the same-length BB code---and decodes better; a circuit-level memory experiment places our weight-$8$ codes at $\approx 0.1\%$ pseudo-threshold versus $\approx 0.4\%$ for the BB reference under an identical model, quantifying the threshold cost of the heavier checks. All structural statements are verified numerically on the whole census.

0.16

More lower bounds for Hales--Jewett and van der Waerden numbers

cs.DM math.CO ·2026-11-17 ·Younes Mouhib
code/data similarity 0.54
Abstract · 6 pages. Explicit certificates, search algorithms, and verification code are available at https://github.com/ysmouhib/hj-vdw-reproducibility…

We give explicit colourings improving the comparison lower bounds assembled here for several Hales--Jewett and van der Waerden numbers. The main algebraic tool generalises Rabung's power-residue colouring from arithmetic progressions to arbitrary sets. If every translate of a t-element set S in F_p meets at least two classes of the r-th power character, and the integer weights have both parities, then a period-2p one-weight colouring of [t]^p has no monochromatic combinatorial line. The 19 displayed algebraic certificates comprise 18 improvements and one closed-form reproduction; they include HJ(4,3)>=164, HJ(5,4)>=7418, and HJ(5,6)>=34034. The underlying period-p construction also proves kappa_ow(t,r)>=p-1 for the one-weight bracket ceiling, in particular kappa_ow(5,4)>=7416 and kappa_ow(5,6)>=34032. Warm breakout-weighted tabu search on the type simplex gives HJ(3,4)>=51. Whole-colouring local search gives W(8,3)>522, W(11,3)>1193, and W(17,3)>3620. All accepted certificates are available separately and are checked by direct enumeration; unresolved searches are reported as UNKNOWN, not UNSAT.

0.57

Improved Bounds on the Ingleton Score of Four Random Variables

cs.IT ·2026-10-04 ·Jiang Chang
theory similarity 0.51
Abstract · 5 pages. Ancillary files contain the parsed inequality catalogues, exact rational certificates for the bounds 5/32 and 19/124, exact extensi…

For four finite discrete random variables, we prove that the negative of the Ingleton expression, divided by the joint entropy, is at most $19/124 \approx 0.15323$, improving the previously reported upper bound $3/19$ by $11/2356$. The proof uses a copy program with four copy steps and six auxiliary variables, certified by exact rational linear-programming certificates. We also show that two published information inequalities, due to Dougherty-Freiling-Zeger and Csirmaz, imply the bound $5/32$ by an explicit nonnegative combination with Shannon inequalities, and that $5/32$ is the exact optimum both of the union of the three published inequality catalogues considered here and of the full copy-lemma extensions of all 213 distinct copy programs occurring in them. The new program is not among these programs, and the bound $19/124$ remains optimal when all of them and all catalogue inequalities are added. Ancillary files provide the parsed catalogues, exact primal and dual certificates, exact extension certificates, and verifiers that use only the Python standard library.

0.27

A Uniform Upper Bound on the Length of MDS Codes from Genus-Two Curves

cs.IT math.AGmath.NT ·2026-10-29 ·Haojie Chen
theory similarity 0.51
Abstract

We study the maximal length of MDS algebraic geometry codes from genus-two curves over finite fields. Let $C_\mathcal{ L}(D,G)$ be such a code over $\mathbb F_q$, with length $n$ and dimension $k$. Assume that $3\leq k\leq n-3$. We prove that $n<(2q+10\sqrt q+16)/3$. This bound holds for every prime power $q$ and for both parities of $k$. It gives a uniform upper bound of $2q/3+O(\sqrt q)$ for the maximal length. The explicit bound is strictly smaller than $q+1$ when $q\geq125$.

0.17