Non-Euclidean ErdH{o}s-Anning Theorems
Pith reviewed 2026-05-24 04:17 UTC · model grok-4.3
The pith
The Erdős-Anning theorem on finite or collinear integer-distance point sets extends to any strictly convex distance and to geodesic distances on bounded-genus Riemannian manifolds and convex surfaces.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
For any strictly convex distance function on the plane, every point set with integer distances is collinear or finite; the same holds for geodesic distance on every two-dimensional complete Riemannian manifold of bounded genus and on the boundary of every three-dimensional Euclidean convex set. Relative to any non-degenerate triangle of diameter delta, at most O(delta squared) additional points can have integer distances to all three vertices. The proofs rest on combinatorial and geometric properties of the additively weighted Voronoi diagrams induced by these distances.
What carries the argument
Additively weighted Voronoi diagrams, which assign each point in the space to the site minimizing distance plus an additive weight, used here to control the possible locations of points at integer distances from a fixed triangle.
If this is right
- The finiteness and O(delta squared) bound hold for every strictly convex distance function on the plane.
- The same conclusions apply to geodesic distance on every complete two-dimensional Riemannian manifold of bounded genus.
- The conclusions apply to geodesic distance on the boundary of every three-dimensional Euclidean convex body.
- The equilateral dimension of every such manifold or surface is finite.
Where Pith is reading between the lines
- If the Voronoi diagrams retain their required properties under small perturbations of the metric, the finiteness result could extend to nearby distance functions not covered by the stated theorems.
- The bounded equilateral dimension implies that no Riemannian manifold of bounded genus admits arbitrarily large regular simplices with equal geodesic edge lengths.
- Computational enumeration of integer-distance points on a given manifold could be organized by first fixing a triangle and then searching only within the O(delta squared) candidate cells of the weighted Voronoi diagram.
Load-bearing premise
The additively weighted Voronoi diagrams of the distances must possess the specific combinatorial and geometric properties needed to bound the number of integer-distance points relative to a fixed triangle.
What would settle it
An infinite non-collinear point set whose pairwise distances are all integers, lying on a torus or under a strictly convex non-Euclidean distance function, would show the claimed finiteness fails.
Figures
read the original abstract
The Erd\H{o}s-Anning theorem states that every point set in the Euclidean plane with integer distances must be either collinear or finite. More strongly, for any (non-degenerate) triangle of diameter~$\delta$, at most $O(\delta^2)$ points can have integer distances from all three triangle vertices. We prove the same results for any strictly convex distance function on the plane, and analogous results for every two-dimensional complete Riemannian manifold of bounded genus and for geodesic distance on the boundary of every three-dimensional Euclidean convex set. As a consequence, we resolve a 1983 question of Richard Guy on the equilateral dimension of Riemannian manifolds. Our proofs are based on the properties of additively weighted Voronoi diagrams of these distances.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript extends the classical Erdős-Anning theorem (point sets with all pairwise distances integers are collinear or finite; more strongly, at most O(δ²) points lie at integer distances from the three vertices of any non-degenerate triangle of diameter δ) to three broader settings: (i) any strictly convex distance function on the plane, (ii) geodesic distance on any complete 2-dimensional Riemannian manifold of bounded genus, and (iii) geodesic distance on the boundary of any 3-dimensional Euclidean convex body. As a corollary the equilateral dimension of every such manifold is at most 3, answering a 1983 question of Richard Guy. All proofs are said to rest on combinatorial and geometric properties of the associated additively weighted Voronoi diagrams.
Significance. If the central claims hold, the work supplies a unified geometric framework that lifts a foundational result of combinatorial geometry to a wide class of non-Euclidean metrics and manifolds, while simultaneously settling an explicit open question posed four decades ago. The Voronoi-diagram technique, if fully verified, would constitute a reusable tool for bounding integer-distance graphs in curved spaces.
major comments (2)
- [Proof strategy (abstract and §1)] The load-bearing step is the assertion that additively weighted Voronoi diagrams of the given distances possess the specific combinatorial and geometric properties needed to bound the number of integer-distance points relative to a fixed triangle. The manuscript must state these properties explicitly and verify them for the Riemannian and convex-body cases; without such verification the extension from the Euclidean plane remains conditional.
- [Riemannian case (presumably §4)] For the Riemannian-manifold statement, the argument invokes completeness, bounded genus, and the existence of a suitable Voronoi diagram, yet does not indicate where the genus bound is used to control the number of cells or the degree of the diagram. A concrete reference to the relevant lemma or proposition is required.
minor comments (2)
- [Abstract] The abstract states that the results hold for “every two-dimensional complete Riemannian manifold of bounded genus,” but the precise meaning of “bounded genus” (e.g., uniform bound independent of the manifold or a bound depending on the manifold) should be clarified in the introduction.
- Notation for the additively weighted Voronoi diagram (site weights, distance function, etc.) is introduced only informally; a short dedicated paragraph or figure illustrating the diagram for a strictly convex norm would improve readability.
Simulated Author's Rebuttal
We thank the referee for the careful reading and the constructive comments on our manuscript. The suggestions help clarify the presentation of the Voronoi-diagram arguments. We address each major comment below and will incorporate the requested clarifications in the revised version.
read point-by-point responses
-
Referee: [Proof strategy (abstract and §1)] The load-bearing step is the assertion that additively weighted Voronoi diagrams of the given distances possess the specific combinatorial and geometric properties needed to bound the number of integer-distance points relative to a fixed triangle. The manuscript must state these properties explicitly and verify them for the Riemannian and convex-body cases; without such verification the extension from the Euclidean plane remains conditional.
Authors: We agree that the central role of the combinatorial and geometric properties of the additively weighted Voronoi diagrams should be made fully explicit. In the revised manuscript we will add a dedicated subsection (placed after the abstract and before the main theorems) that enumerates the precise properties required: (i) each diagram has O(1) cells per site on average with bounded degree independent of the number of sites, (ii) the cells are convex with respect to the underlying distance, and (iii) the number of sites whose cells intersect a given bounded region is controlled by the diameter. We will then verify these properties separately for strictly convex planar distances (by direct comparison with the Euclidean case), for complete Riemannian manifolds of bounded genus (using the Gauss-Bonnet theorem and the resulting Euler-characteristic bound on cell complexity), and for geodesic distance on convex-body boundaries (via the supporting hyperplane structure). This will render the extensions unconditional. revision: yes
-
Referee: [Riemannian case (presumably §4)] For the Riemannian-manifold statement, the argument invokes completeness, bounded genus, and the existence of a suitable Voronoi diagram, yet does not indicate where the genus bound is used to control the number of cells or the degree of the diagram. A concrete reference to the relevant lemma or proposition is required.
Authors: The bounded-genus hypothesis is used precisely to obtain a uniform upper bound on the number of cells and their degrees via the Euler characteristic. In the revised manuscript we will insert an explicit pointer in §4 to the lemma that invokes this bound (a short argument combining the Gauss-Bonnet theorem with the standard complexity analysis of additively weighted Voronoi diagrams on surfaces). If the current draft leaves the citation implicit, we will add the reference to the relevant proposition on diagram complexity for genus-g Riemannian surfaces. revision: yes
Circularity Check
No significant circularity detected
full rationale
The derivation proceeds from the combinatorial and geometric properties of additively weighted Voronoi diagrams for strictly convex distances, Riemannian geodesic distances, and boundary geodesics; these properties are invoked as external inputs rather than being defined in terms of the target bound on integer-distance points. No equation reduces the claimed O(δ²) bound to a fitted parameter or prior self-citation by construction, and the resolution of Guy's equilateral-dimension question follows directly from the same diagram properties without renaming or smuggling an ansatz. The argument is therefore self-contained against the stated geometric assumptions.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Additively weighted Voronoi diagrams exhibit the required bounding properties for integer-distance constraints under strict convexity or bounded genus
Lean theorems connected to this paper
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
Our proofs are based on the properties of additively weighted Voronoi diagrams of these distances.
-
IndisputableMonolith/Foundation/RealityFromDistinction.leanreality_from_one_distinction unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
Lemma 9. ... Vi ∩ Vj ∩ Vk consists of at most two points.
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
Reference graph
Works this paper leans on
-
[1]
Norman H. Anning and Paul Erdős. Integral distances.Bulletin of the American Mathematical Society, 51(8):598–600, 1945.doi:10.1090/S0002-9904-1945-08407-9
-
[2]
Peter F. Ash and Ethan D. Bolker. Generalized Dirichlet tessellations.Geometriae Dedicata, 20(2):209–243, 1986.doi:10.1007/BF00164401
-
[3]
Jeffrey M. Augenbaum and Charles S. Peskin. On the construction of the Voronoi mesh on a sphere. Journal of Computational Physics, 59(2):177–192, 1985.doi:10.1016/0021-9991(85) 90140-8
-
[4]
Mikhail Bogdanov, Olivier Devillers, and Monique Teillaud. Hyperbolic Delaunay complexes and Voronoi diagrams made practical.Journal of Computational Geometry, 5(1):56–85, 2014. doi:10.20382/JOCG.V5I1A4
-
[5]
André Bouchet. Orientable and non orientable genus of the complete bipartite graph.Journal of Combinatorial Theory, Series B, 24:24–33, 1978.doi:10.1016/0095-8956(78)90073-4
-
[6]
L. Paul Chew and Robert L. (Scot) Drysdale, III. Generalization of Voronoi diagrams in the plane. SIAM Journal on Computing, 10(1):73–87, 1981.doi:10.1137/0210006
-
[7]
L. Paul Chew and Robert L. (Scot) Drysdale, III. Voronoi diagrams based on convex distance functions. In Joseph O’Rourke, editor,Proceedings of the First Annual Symposium on Compu- tational Geometry, Baltimore, Maryland, USA, June 5–7, 1985, pages 235–244. Association for Computing Machinery, 1985.doi:10.1145/323233.323264. 25
-
[8]
Robert Connelly. Convex Polyhedra by A. D. Alexandrov. SIAM Review , 48(1):157–160, March 2006. URL:https://www.jstor.org/stable/204537, doi:10.1137/ SIREAD000048000001000149000001
work page 2006
-
[9]
The space of spheres, a geometric tool to unify duality results on Voronoi diagrams
Olivier Devillers, Stefan Meiser, and Monique Teillaud. The space of spheres, a geometric tool to unify duality results on Voronoi diagrams. InProceedings of the 4th Canadian Conference on Computational Geometry (CCCG ’92), pages 263–268, 1992. URL: https://cccg.ca/ proceedings/1992/Paper43.pdf
work page 1992
-
[10]
David Eppstein.Forbidden Configurations in Discrete Geometry. Cambridge University Press,
-
[11]
doi:10.1017/9781108539180
-
[12]
Integral distances.Bulletin of the American Mathematical Society, 51:996, 1945
Paul Erdős. Integral distances.Bulletin of the American Mathematical Society, 51:996, 1945. doi:10.1090/S0002-9904-1945-08490-0
-
[13]
Fragmenta arithmetica ex Adversariis mathematicis deprompta, C: Analysis Diophantea
Leonhard Euler. Fragmenta arithmetica ex Adversariis mathematicis deprompta, C: Analysis Diophantea. InOpera postuma, volume I, pages 204–263. Eggers, Petropolis, 1862. Theorem 65, p. 229. URL: https://scholarlycommons.pacific.edu/euler-works/806/
-
[14]
Rachel Greenfeld, Marina Iliopoulou, and Sarah Peluse. On integer distance sets. Electronic preprint arxiv:2401.10821, 2024
-
[15]
Richard K. Guy. An olla-podrida of open problems, often oddly posed. The American Mathematical Monthly, 90(3):196–200, 1983.doi:10.2307/2975549
-
[16]
Integral distances in point sets
Heiko Harborth. Integral distances in point sets. InCharlemagne and his Heritage: 1200 Years of Civilization and Science in Europe, Vol. 2 (Aachen, 1995), pages 213–224. Brepols, Turnhout, Belgium, 1998. doi:10.1484/M.STHS-EB.4.2017040
-
[17]
H. Hopf and W. Rinow. Ueber den Begriff der vollständigen differentialgeometrischen Fläche. Commentarii Mathematici Helvetici, 3(1):209–225, 1931.doi:10.1007/BF01601813
-
[18]
Christian Icking, Rolf Klein, Ngo.c-Minh Lê, and Lihong Ma. Convex distance functions in 3-space are different.Fundamenta Informaticae, 22(4):331–352, 1995.doi:10.3233/FI-1995-2242
-
[19]
Menelaos I. Karavelas and Ioannis Z. Emiris. Root comparison techniques applied to computing the additively weighted Voronoi diagram. InProceedings of the Fourteenth Annual ACM–SIAM Symposium on Discrete Algorithms, January 12–14, 2003, Baltimore, Maryland, USA, pages 320–
work page 2003
-
[20]
URL:https://dl.acm.org/citation.cfm?id=644108.644161
ACM and SIAM, 2003. URL:https://dl.acm.org/citation.cfm?id=644108.644161
-
[21]
Michael Kleber. Encounter at far point. Mathematical Intelligencer, 1:50–53, 2008. doi: 10.1007/BF02985756
-
[22]
There are integral heptagons, no three points on a line, no four on a circle
Tobias Kreisel and Sascha Kurz. There are integral heptagons, no three points on a line, no four on a circle. Discrete & Computational Geometry, 39(4):786–790, 2008.doi:10.1007/ s00454-007-9038-6
work page 2008
-
[23]
Ngo.c-Minh Lê. On non-smooth convex distance functions.Information Processing Letters, 63(6):323–329, 1997.doi:10.1016/S0020-0190(97)00136-1
-
[24]
Delaunay triangulations and Voronoi diagrams for Riemannian manifolds
Greg Leibon and David Letscher. Delaunay triangulations and Voronoi diagrams for Riemannian manifolds. In Siu-Wing Cheng, Otfried Cheong, Pankaj K. Agarwal, and Steven Fortune, editors, Proceedings of the Sixteenth Annual Symposium on Computational Geometry, Clear Water Bay, 26 Hong Kong, China, June 12–14, 2000, pages 341–349. ACM, 2000.doi:10.1145/33615...
-
[25]
Jeremy Mann. Equilateral dimension of Riemannian manifolds with bounded curvature.Rose- Hulman Undergraduate Mathematics Journal, 14(1):Article 8, 2013. URL:https://scholar. rose-hulman.edu/rhumj/vol14/iss1/8/
work page 2013
-
[26]
M. Mazón and T. Recio. Voronoi diagrams on orbifolds.Computational Geometry: Theory & Applications, 8(5):219–230, 1997.doi:10.1016/S0925-7721(96)00017-X
- [27]
-
[28]
S. B. Myers. Arcs and geodesics in metric spaces.Transactions of the American Mathematical Society, 57:217–227, 1945.doi:10.1090/S0002-9947-1945-0011792-9
-
[29]
Hyeon-Suk Na, Chung-Nim Lee, and Otfried Cheong. Voronoi diagrams on the sphere.Computa- tional Geometry, Theory and Applications, 23(2):183–194, 2002.doi:10.1016/S0925-7721(02) 00077-9
-
[30]
John Nash. The imbedding problem for Riemannian manifolds.Annals of Mathematics, 2nd Ser., 63(1):20–63, 1956.doi:10.2307/1969989
-
[31]
Hyperbolic Voronoi diagrams made easy
Frank Nielsen and Richard Nock. Hyperbolic Voronoi diagrams made easy. In Bernady O. Apduhan, Osvaldo Gervasi, Andrés Iglesias, David Taniar, and Marina L. Gavrilova, editors, Proceedings of the 2010 International Conference on Computational Science and Its Applications, ICCSA 2010, Fukuoka, Japan, March 23–26, 2010, pages 74–80. IEEE Computer Society, 20...
-
[32]
Note on integral distances.Discrete & Computational Geometry, 30(2):337–342,
József Solymosi. Note on integral distances.Discrete & Computational Geometry, 30(2):337–342,
-
[33]
doi:10.1007/s00454-003-0014-7
-
[34]
Overcoming catastrophic forgetting in neural networks
Matthias Weber, David Hoffman, and Michael Wolf. An embedded genus-one helicoid.Pro- ceedings of the National Academy of Sciences, 102(46):16566–16568, 2005.doi:10.1073/pnas. 0508008102. 27
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.