Matching works

6 works

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

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

A composite modulus and Frobenius digits in the Heilbronn triangle construction

Contributed by David Niedbala Giraudin

OpenAI proved that for every sufficiently large n there are n points in the unit square all of whose triangles have area at least c n^(-2+eta), with an explicit but extremely small eta (of order 10^(-235)). Subsequent public work lowered the cost of the construction, the latest claimed exponent being eta = 2/100866719, about 1.98*10^(-8). We introduce two changes. First, the digit base is taken to be a multiple of the label prime r and the main modulus is h = r B^(k-1) instead of B^k; this reduces the ratio h/tau between the modulus and the excluded determinant window from about B to about r, which allows the extension degree d = 3. Second, the norm polynomial is placed in the digits by a digit-wise convolution along the Frobenius expansion of the exponents, with a trace digit in a polynomial basis, giving k = 1440 positions. The result is Delta(n) >= c n^(-2+eta) with eta = 1/177022 > 5.64*10^(-6), for every sufficiently large n. The finite identities are checked by exact computation in the ancillary files.

Primarily AI-generated textHuman understanding: no partsHeilbronn triangle problemfield normfinite fieldslattice point countingprobabilistic method
Nov 04, 202611 pages
PDFView work

math.MG — Metric Geometry

Separated distances in fixed dimension

Contributed by John Tripodo

A finite Euclidean point set is distance-separated if the lengths of any two distinct unordered edges differ by at least one. Counting gives a diameter lower bound of binom(n,2), whereas Erdős asked for a lower bound with leading term n^2. We give two constructions in fixed dimension. For every 0 < epsilon <= 1/2, put m0 = ceil(8192/epsilon). For every n >= 4m0 there is a distance-separated n-point set in dimension 10m0-1 with diameter < (1/2+epsilon)n^2. A six-cluster construction gives arbitrarily large configurations in R^29 with diameter < 0.998n^2, and an explicit prime-interval bound gives diameter < 0.999n^2 for every n >= 400000. The constructions use two orthogonal circle families to control distances within and between clusters separately. Their common geometric argument reduces to a uniform operator estimate for the first result and three rational positive-definiteness certificates for the second. Lean 4 formalizations accompany the tolerance family and the dimension-29 result for arbitrarily large sizes; the all-size corollary is a written consequence.

Primarily AI-generated textHuman understanding: no partsErdős Problem 670Lean 4fixed dimensionseparated Euclidean distances
Oct 15, 202620 pages
PDFView work

math.CO — Combinatorics

Measurable Independence Density Equals the Finite Independence-Ratio Infimum in the Euclidean Plane

Contributed by Ákos Dúcz

Let m1(R^2) be the supremum of upper densities of Lebesgue-measurable subsets of the plane containing no pair of points at distance one. We show, using the spectral rigidity theorem in OpenAI's recent proof that the plane is not five-colorable, that m1(R^2) = inf_G alpha(G)/|V(G)|, where G ranges over nonempty finite unit-distance graphs in the plane. The argument constructs an isometry-invariant law on independent subsets of the countable algebraic plane, projects the occupancy indicator onto the continuous spectral factor without changing its expectation, and extracts a measurable independent set with arbitrarily small density loss. As a consequence, if f(n) is the least independence number among unit-distance graphs on n vertices, then f(n)/n converges to m1(R^2). The proof is nonquantitative and uses the cited spectral rigidity result as a black box.

Primarily AI-generated textHuman understanding: some partsSpectral RigidityUnit-distance graphsindependence ratioinvariant random independent setsmeasurable sets
Oct 09, 20266 pages
PDFView work

math.CO — Combinatorics

An Exponent of 1.043 for the Unit Distance Problem

Contributed by Eric Naslund

Let u(U)u(U) count the unordered pairs at distance one in a finite planar set UU. We construct finite sets UjU_j with ∣Uj∣→∞|U_j|\to\infty and u(Uj)/∣Uj∣1.043171→∞u(U_j)/|U_j|^{1.043171}\to\infty. The largest exponent previously claimed, apart from preliminary versions of the present work, is 1.03581.0358, in the author's unpublished manuscript. The method is the number-field construction of OpenAI and Sawin. Here unit distances come from elements of relative norm one in quadratic extensions K/FK/F in which FF has both real and complex places, and the fields come from an infinite pro-22 tower over $\Q(\sqrt{241})$, ramified only above 22, 33 and 55, with Frobenius conditions at the two primes above 2929 and at one prime above 4141. The relative zeta value is bounded through the dihedral quotients of the tower group: the tower group has 2727 quotients isomorphic to the dihedral group of order~88; fifteen of them detect, by a census, the residue degree of the primes that split completely in the Kummer field up to norm 4⋅10134\cdot10^{13}, and seven of them generate a field EW′′E_{W''} of degree 81928192 contained in every field of the tower. We write ζEW′′\zeta_{E_{W''}} as a product of LL-functions of degrees 22, 44 and~88, evaluate the 576576 of degrees 44 and 88 rigorously at 2121 real points near~11, and combine the values through a kernel inequality with coefficients of both signs. Finite facts and numerical inequalities are certified by exact computation and interval arithmetic. Partial formalization PALOMAR-2026-10-01-000018 v2

Primarily AI-generated textHuman understanding: some parts
Oct 02, 2026101 pages
PDFView work

Advanced search

Text
Human understanding
Linked formalizations