Browse › Convex and metric geometry › 092 The optimal order of convex-body covering density
A single-lattice covering bound of order n log n
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
Every convex body in ℝn, n ≥ 2, admits a covering by translates along one full-rank lattice with density at most $Cn\log n$, for an absolute constant C. No symmetry or boundary regularity is assumed.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Follow-up works
- Hexagon deposit contributed by Scott Kominers, Multi-coverings by lattice translates of convex bodies (hexagon:2610.00165v1, October 2026). Uses translates along a single lattice to prove multi-covering versions (mean multiplicity exactly a prescribed density of order at least $A_\varepsilon n\log n$, every point covered at least $(1-\varepsilon)$ times that density), extending this paper's horizontal–vertical construction; the source calls the work "heavily LLM-assisted", and Hexagon labels it as mixed human/AI authorship.
Formalization
- OpenAI math release, Lean scope note 092: The optimal order of convex-body covering density (lean/docs/092.md, 2026-10-06). The release's own scope note: it formalizes the single-lattice bound $|K|/\mathrm{covol}(L)\le Cn\log n$ for every convex body, $n\ge2$, and points to the comparator file
SingleLatticeCovering.lean. [family-level] - OpenAI, lean/OAI/Geometry/LatticeCovering/Main.lean (openai/math, commit adc7f12). Contains the Lean theorem
OAI.SingleLatticeCovering.single_lattice_covering, which states this paper's Theorem 1.1. - OpenAI, lean/OAI/Geometry/CoveringDensity/Main.lean (openai/math, commit adc7f12). Contains
OAI.CoveringOrder.optimal_order, which combines this paper's upper bound with the lower bounds into $\Theta(n\log n)$ for the lattice and translative suprema. [family-level]
Related prior literature mentioned by others
- M. Naszódi, Flavors of Translative Coverings (arXiv:1603.04481, Bolyai Soc. Math. Stud. 27, 2018). The VibeMathed entry for this family gives Section 3 of this survey as the source of the linear-bound question; this paper does not cite it, but its companion translative paper does. [family-level]
- Or Ordentlich, Oded Regev and Barak Weiss, New bounds on the density of lattice coverings (arXiv:2006.00340, 2020-05-30). Kalai's October 2026 discussion identifies this earlier work on lattice covering densities as background to the family's two announced results. [family-level]
Possibly relevant literature (found by the agent, not checked)
- J. Gao, X. Liu, O. Pikhurko, S. Sun, New upper bound for lattice covering by spheres (arXiv:2508.06446, August 2025). Gives lattice coverings by Euclidean balls of density $O(n\ln^{\beta}n)$ with $\beta\approx1.858$; for the ball, Theorem 1.1's uniform $Cn\log n$ bound would be a further improvement.
- M. Schymura, J. Wang, F. Xue, On lattice coverings by locally anti-blocking bodies and polytopes with few vertices (arXiv:2505.07369, May 2025). Proves bounds comparable to Rogers' ball bound for lattice coverings by some non-symmetric classes; this relates to the paper's claim that no symmetry is needed.
News and blogs
- Gil Kalai, Updates: Sharing AI progress on mathematics (amazing!); and my lecture plans (Combinatorics and more, 2026-10-07). Item 7, "Covering density of convex bodies", links both papers of this family and ties the universal $O(n\log n)$ lattice-covering bound to Kalai's earlier post on Ordentlich–Regev–Weiss. [family-level]
Elsewhere
- Hexagon: Multi-coverings by lattice translates of convex bodies (human and AI; human understanding: all)
- Emergent Mind: family 092
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:A-single-lattice-covering-bound-of-order-n-log-n-September-23-2026,
author = {{OpenAI}},
title = {{A single-lattice covering bound of order $n\log n$}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/A-single-lattice-covering-bound-of-order-n-log-n-September-23-2026/paper.pdf}{OAI:A-single-lattice-covering-bound-of-order-n-log-n-September-23-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/092.md. The Lean statements have not been checked by people against the paper's claims.
Family 092: The optimal order of convex-body covering density
Determines the optimal worst-case covering density as $\Theta(n\log n)$, for both lattice and unrestricted translative coverings. Every convex body in ℝn, n ≥ 2, admits a lattice covering of density at most $Cn\log n$; centrally symmetric examples in every sufficiently large dimension require at least $cn\log n$ even without the lattice restriction, for absolute $c,C\gt 0$.
Other papers in this family:
- Translative covering densities of order n log n · September 23, 2026