Matching works

7 works

cs.DS — Data Structures and Algorithms

A certified exponent of 0.48758 for worst-case Subset Sum, and limits of the alias–checksum analysis

Contributed by Jennifer Voitle

For more than fifty years, since Horowitz and Sahni's meet-in-the-middle algorithm of 1974, the best exponent for worst-case Subset Sum was 1/21/2. In October 2026 that barrier fell twice within a week, with OpenAI's 20.49n2^{0.49n} algorithm and, independently, Li and Ye's 2(1/2−1/450000)n≈20.4999978n2^{(1/2 - 1/450000)n} \approx 2^{0.4999978n}, and improvements have followed quickly since: within three weeks A. Kapila's modification of the OpenAI approach ("Base") reached 0.4877, a retuning of Base by JoshuaQFEX reached 0.487676, and a refinement by Y. Bills reached 0.4876723. Here we push this line of work further and examine what limits it. Conditional on the cited non-numerical proofs, we give a certified parameter point with threshold T=0.4875754036T=0.4875754036: for every fixed T′>TT'>T, the uniform randomized algorithm uses O(2T′n)O(2^{T'n}) word operations on inputs of polynomial bit length, with success probability at least 2/32/3. In particular, it runs in time O(20.4875755n)O(2^{0.4875755n}). A single asymmetric filter replaces Base's family of 43 filters. Independent interval computations certify all required numerical conditions, including both filtering moments and their quadrature errors. We prove a lower bound on the first filtering moment, valid for all positive continuous densities, that excludes every parameter choice with τ≤0.484\tau\le0.484 in the original OpenAI proof's sufficient budget. Three algebraic bounds explain the costs at our improved point. Separately, an enumeration phase that inserts at least 2(1−η−o(1))n2^{(1-\eta-o(1))n} alias classes, spending a counted step on each, and uses checksum gap at most Δ\Delta needs exponent at least (1−Δ)/2(1-\Delta)/2. This is a conditional operation-count bound; a global upper bound on achievable checksum capacity remains open. Finally, we isolate a small-layer statement that would yield threshold 0.48734075280.4873407528, prove combinatorial special cases, and identify the remaining questions.

Author comments: 30 pages, 2 figures. The main result is conditional on the written proofs of OpenAI (4 Oct 2026) and A. Kapila (commit 44c34961); its numerical conditions are certified in interval arithmetic. The companion file SECTION_T_v3.pdf (full proofs of the ternary alias step, Appendix A) is included with the source. Code, certificates, verification scripts and a timestamped research record: https://github.com/jv1000/subset-sum. AI use is described in Section 11.

A mix of human-written and AI-generated textHuman understanding: some partsAI-assisted mathematicsFourier filteringSubset Sumcomputer-assisted proofexact algorithmsinterval arithmeticmeet-in-the-middlerepresentation techniqueworst-case complexity
Nov 07, 202630 pages
PDFView work

math.NT — Number Theory

Turán's pure power sum problem: certified bounds for finite nn and lim sup⁡Rn≤0.68637\limsup R_n\le 0.68637

Contributed by Vasileios Bakeas, Ricardo Pinho

For n≥1n\ge1 let Rn=inf⁡max⁡1≤k≤n∣z1k+⋯+znk∣R_n=\inf\max_{1\le k\le n}|z_1^k+\dots+z_n^k|, the infimum being over all complex z1=1,z2,…,znz_1=1,z_2,\dots,z_n. This is Turán's pure power sum problem (Erdős problem #519). The best published upper bound for the constant lim sup⁡Rn\limsup R_n is 0.693680.69368, from a computation of Harcos reported by Biró in 2000. We prove lim sup⁡n→∞Rn≤0.68637\limsup_{n\to\infty}R_n\le0.68637. The construction is the Biró–Harcos linearization, with the first half of the power sums prescribed as sk=Teiφ(k/n)s_k=Te^{i\varphi(k/n)} for a piecewise-linear phase φ\varphi that varies from the start. We prove a limit theorem: the quantity that controls the second half converges to an explicit functional of the solution of a linear Volterra equation whose associated operator is a contraction. The resulting inequality is certified in ball arithmetic by an a posteriori error bound, with two separately written programs that follow the same mathematical argument. We also give rigorous upper bounds for RnR_n at 13 values of nn between 300300 and 10610^6, from explicit exact certificates, each checked by one or two programs written independently of the generator. In an appendix, R. Pinho applies the limit theorem to a finer profile, with sharper error bounds, and certifies lim sup⁡Rn≤0.6863607950\limsup R_n\le0.6863607950. The work was done with substantial help from AI models; it has not been refereed.

Primarily AI-generated textHuman understanding: some partsErdős problem 519Turán power sumsVolterra integral equationcomputer-assisted proofinterval arithmetic
Nov 04, 202613 pages
PDFView work

math-ph — Mathematical Physics

A Bound Helium Dianion Does Not Exist

Contributed by Alec Shelley, Daniel Tartakovsky

For a non-relativistic atom with ZZ protons and NN bound electrons, Lieb proved in 1984 that N<2Z+1N<2Z+1. Several improved bounds have been developed, but they all leave open the question of whether a bound helium dianion can exist. We prove that the answer is no. The ground-state energies of the four- and three-electron helium Hamiltonians coincide, E4(Z=2)=E3(Z=2)E_4(Z{=}2)=E_3(Z{=}2), so a helium nucleus binds at most three electrons. A weighted form of Lieb's identity reduces the problem to the nonnegativity of an explicit two-electron Schrodinger operator mm, and Barta's inequality further reduces it to the pointwise nonnegativity of an explicit function of three variables. We prove the nonnegativity of this function by a combination of analytic estimates and a computer-assisted certification in interval arithmetic, and we publish the certificate with the paper.

A mix of human-written and AI-generated textHuman understanding: some partscomputer-assisted proofexcess chargehelium dianioninterval arithmeticionization conjecture
Nov 03, 202620 pages
PDFView work

math.NT — Number Theory

A 256-step certificate for Turán's pure power-sum constant

Contributed by Ricardo Pinho

We give an exact-input certificate for the upper bound C_42 <= 0.6888863712 in the pure power-sum problem. The construction refines the step profiles of Griego, Röhrig and Plata to 256 middle blocks, without changing their coefficient-cancellation mechanism. It improves the strongest public proposal located in our 22 October 2026 audit, 0.688970, by 0.0000836288. An unmodified public interval checker and a separately written Arb checker verify the strict finite inequalities. The asymptotic implication is proved in the note; no explicit finite threshold, optimality, human peer review or formal verification is claimed.

Primarily AI-generated textHuman understanding: some partsTurán power sumscoefficient cancellationcomputer-assisted proofinterval arithmeticrigorous numerics
Oct 23, 20264 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.CV — Complex Variables

A covering-strip and moment certificate for Korenblum's constant

Contributed by Ricardo Pinho

We give an explicit certificate for c_2>=54/125=0.432, where c_2 is Korenblum's constant for the Bergman space. This is an unrefereed preprint. The construction combines an elementary two-zero Schwarz estimate on the covering strip of an annulus, the classical hyperbolic Jung inequality, and Wikström's moment-duality criterion. A rational twelve-atom measure with a Lebesgue tail satisfies the required inequalities for every moment index. Two independently implemented exact checkers, one using Arb and one using only integer interval arithmetic, verify the quantitative hypotheses. The best public certified lower bound located in the accompanying priority audit is Wikström's 0.4263. Neither optimality nor a new version of Jung's theorem is claimed.

Primarily AI-generated textHuman understanding: some partsBergman spaceKorenblum's constantcomputer-assisted proofhyperbolic Jung inequalityinterval arithmeticmoment duality
Oct 20, 20265 pages
PDFView work

Advanced search

Text
Human understanding
Linked formalizations