pith. sign in

arxiv: 2401.06328 · v3 · submitted 2024-01-12 · 🧮 math.MG · cs.CG

Non-Euclidean ErdH{o}s-Anning Theorems

Pith reviewed 2026-05-24 04:17 UTC · model grok-4.3

classification 🧮 math.MG cs.CG
keywords Erdős-Anning theoreminteger distancesstrictly convex distancesRiemannian manifoldsgeodesic distancesadditively weighted Voronoi diagramsequilateral dimensionpoint sets
0
0 comments X

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.

The paper establishes that point sets with all pairwise distances integers remain either collinear or finite when the underlying distance is any strictly convex function on the plane. The same finiteness holds for geodesic distance on any complete two-dimensional Riemannian manifold of bounded genus and on the boundary of any three-dimensional Euclidean convex body. A reader would care because the result shows the integer-distance restriction is not an artifact of flat Euclidean geometry but persists across many curved settings. The work also settles an open question from 1983 on the largest possible equilateral point sets in these spaces.

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

These are editorial extensions of the paper, not claims the author makes directly.

  • 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

Figures reproduced from arXiv: 2401.06328 by David Eppstein.

Figure 1
Figure 1. Figure 1: Note that, according to this definition, star-shaped sets are not required to form topological [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Integer L1 (left) and L∞ distances in the integer grid (Example 1). The yellow shaded regions are the unit balls for these two distances. 1 1 3 3 3 3 1 1 3 3 3 3 K [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Construction for an infinite non-geodesic set with integer distances for a convex but not [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The points on the unit sphere whose angles are even multiples of the angles of a 3-4-5 [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: An additively weighted Voronoi diagram with two degenerate sites (red and green) and [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Figure for the proof of Lemma 6: a site si , a segment L within Voronoi cell Vi , and a point p in the relative interior of L that is not interior to Vi . The lemma proves that this situation cannot exist by considering cases for the location of sj , another site with the same distance to p as si . Note that Corollary 4 would not be true if we allowed infinite sets of sites. Instead of defining degeneracy … view at source ↗
Figure 7
Figure 7. Figure 7: Figure for the proof of Lemma 7: if a point [PITH_FULL_IMAGE:figures/full_fig_p009_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Figure for the proof of Lemma 9: Three non-degenerate sites [PITH_FULL_IMAGE:figures/full_fig_p010_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Figure for the proof of Theorem 3: After enclosing the given points in a bounding box [PITH_FULL_IMAGE:figures/full_fig_p012_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Five small spheres connected in pairs by cylindrical tubes. Smoothing the sphere-cube [PITH_FULL_IMAGE:figures/full_fig_p014_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: An embedding of K3,6 with shortest-curve edges on a hexagonal torus (Example 8). The colors indicate the Voronoi diagram of the points on the three-vertex side of the bipartition. the Erdős–Anning theorem to complete Riemannian 2-manifolds of bounded genus also provides a bound on the equilateral dimension of these manifolds, as a function of their genus (Corollary 20). Our proof of the Erdős–Anning theor… view at source ↗
Figure 12
Figure 12. Figure 12: A solid cone in the limit. The apex of the cone, however, is not Euclidean, even in the limit: it has a positive angular deficiency that can be measured by comparing the radius and circumference of small metric disks around it. The total curvature of this surface is 4π, by the Gauss–Bonnet theorem, but in this case this curvature is concentrated at the cone point (where it equals the angular deficit of th… view at source ↗
Figure 13
Figure 13. Figure 13: Lemma 31: a short path connecting two of three points separated by a convex set [PITH_FULL_IMAGE:figures/full_fig_p023_13.png] view at source ↗
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.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

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)
  1. [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.
  2. [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)
  1. [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.
  2. 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

2 responses · 0 unresolved

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
  1. 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

  2. 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

0 steps flagged

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

0 free parameters · 1 axioms · 0 invented entities

Paper is a pure proof extending a known theorem; relies on standard properties of Voronoi diagrams in the stated geometries rather than new postulates or fitted values.

axioms (1)
  • domain assumption Additively weighted Voronoi diagrams exhibit the required bounding properties for integer-distance constraints under strict convexity or bounded genus
    Central to the proof strategy outlined in the abstract.

pith-pipeline@v0.9.0 · 5645 in / 1210 out tokens · 25916 ms · 2026-05-24T04:17:55.797070+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

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

34 extracted references · 34 canonical work pages

  1. [1]

    Anning and Paul Erdős

    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. [2]

    Ash and Ethan D

    Peter F. Ash and Ethan D. Bolker. Generalized Dirichlet tessellations.Geometriae Dedicata, 20(2):209–243, 1986.doi:10.1007/BF00164401

  3. [3]

    Augenbaum and Charles S

    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. [4]

    Hyperbolic Delaunay complexes and Voronoi diagrams made practical.Journal of Computational Geometry, 5(1):56–85, 2014

    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. [5]

    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

    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. [6]

    Paul Chew and Robert L

    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. [7]

    Paul Chew and Robert L

    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. [8]

    Convex Polyhedra by A

    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

  9. [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

  10. [10]

    Cambridge University Press,

    David Eppstein.Forbidden Configurations in Discrete Geometry. Cambridge University Press,

  11. [11]

    doi:10.1017/9781108539180

  12. [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. [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. [14]

    On integer distance sets

    Rachel Greenfeld, Marina Iliopoulou, and Sarah Peluse. On integer distance sets. Electronic preprint arxiv:2401.10821, 2024

  15. [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. [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. [17]

    Hopf and W

    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. [18]

    Convex distance functions in 3-space are different.Fundamenta Informaticae, 22(4):331–352, 1995.doi:10.3233/FI-1995-2242

    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. [19]

    Karavelas and Ioannis Z

    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–

  20. [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. [21]

    Encounter at far point

    Michael Kleber. Encounter at far point. Mathematical Intelligencer, 1:50–53, 2008. doi: 10.1007/BF02985756

  22. [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

  23. [23]

    On non-smooth convex distance functions.Information Processing Letters, 63(6):323–329, 1997.doi:10.1016/S0020-0190(97)00136-1

    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. [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. [25]

    Equilateral dimension of Riemannian manifolds with bounded curvature.Rose- Hulman Undergraduate Mathematics Journal, 14(1):Article 8, 2013

    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/

  26. [26]

    Mazón and T

    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. [27]

    R. E. Miles. Random points, sets and tessellations on the surface of a sphere.Sankhy¯ a, Series A, 33:145–174, 1971. URL:https://www.jstor.org/stable/25049720

  28. [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. [29]

    Voronoi diagrams on the sphere.Computa- tional Geometry, Theory and Applications, 23(2):183–194, 2002.doi:10.1016/S0925-7721(02) 00077-9

    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. [30]

    The imbedding problem for Riemannian manifolds.Annals of Mathematics, 2nd Ser., 63(1):20–63, 1956.doi:10.2307/1969989

    John Nash. The imbedding problem for Riemannian manifolds.Annals of Mathematics, 2nd Ser., 63(1):20–63, 1956.doi:10.2307/1969989

  31. [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. [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. [33]

    doi:10.1007/s00454-003-0014-7

  34. [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