Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. The answer to Problem 97 is no: there is a convex polygon each of whose vertices has at least four other vertices at distance exactly 11 from it, so every vertex has four other vertices equidistant from it and no vertex is of the kind the question asks for. More generally, for every integer k≥2k\ge2 there is a convex polygon each of whose vertices has at least kk other vertices at distance 11, which refutes the general form of the question, in which some fixed kk replaces four. The claim is a deduction made in this corpus from the accepted disproof of Problem 96 by Liam Kruer and Jensen Kohlmeyer, whose explanation states no consequence for this problem. The polygon's vertices are a subset of their set with d=13d=13, so by their Theorem 1.1 it has at most N13=2⋅1313 21314N_{13}=2\cdot13^{13}\,2^{13^{14}} vertices; the proof gives no coordinates.

Scope. Full: the polygon has no vertex of the kind the question asks for.

Depends on. The accepted claim on Problem 96, where Theorem 1.1 of Kruer and Kohlmeyer supplies, with d=13d=13, a finite set in strictly convex position with more than three unit pairs per point; the negation of the bound O(n)O(n) accepted there, applied with the constant 33, supplies such a set as well. The deletion step and the passage to a polygon are proved below and use nothing else.

Proof. For a finite planar set SS, write u(S)u(S) for the number of unordered pairs of points of SS at distance exactly 11, and deg⁡S(p)\deg_S(p) for the number of points of SS at distance 11 from a point p∈Sp\in S. Call SS in strictly convex position when no point of SS lies in the convex hull of the other points of SS.

  1. The input. Theorem 1.1 of Kruer and Kohlmeyer, as the claim page on Problem 96 records it, gives for every integer d≥2d\ge2 a set VdV_d in strictly convex position with ∣Vd∣=Nd=2dd 2dd+1|V_d|=N_d=2d^d\,2^{d^{d+1}} and u(Vd)≥d4Ndu(V_d)\ge\frac d4N_d. With d=13d=13 the set V=V13V=V_{13} satisfies u(V)≥134∣V∣>3∣V∣u(V)\ge\frac{13}4|V|>3|V|.

  2. Deletion. Set V0=VV_0=V. While the current set ViV_i has a point pp with deg⁡Vi(p)≤3\deg_{V_i}(p)\le3, choose one such point and set Vi+1=Vi∖{p}V_{i+1}=V_i\setminus\{p\}. Removing pp removes exactly the deg⁡Vi(p)\deg_{V_i}(p) unit pairs that contain pp and leaves every other pair, so u(Vi+1)=u(Vi)−deg⁡Vi(p)≥u(Vi)−3u(V_{i+1})=u(V_i)-\deg_{V_i}(p)\ge u(V_i)-3, while ∣Vi+1∣=∣Vi∣−1|V_{i+1}|=|V_i|-1. Hence φ(S)=u(S)−3∣S∣\varphi(S)=u(S)-3|S| satisfies φ(Vi+1)≥φ(Vi)\varphi(V_{i+1})\ge\varphi(V_i), and since φ(V0)>0\varphi(V_0)>0, every ViV_i has φ(Vi)>0\varphi(V_i)>0. Each step removes a point, so the process stops after at most ∣V∣|V| steps, at a set WW. Then u(W)>3∣W∣≥0u(W)>3|W|\ge0, so WW is nonempty, and by the stopping rule every point of WW has at least four other points of WW at distance 11; in particular ∣W∣≥5|W|\ge5.

  3. Convex position. WW is a subset of VV. If a point p∈Wp\in W lay in the convex hull of W∖{p}W\setminus\{p\}, it would lie in the convex hull of the larger set V∖{p}V\setminus\{p\}, against the strictly convex position of VV. So WW is in strictly convex position. In particular no three points of WW are collinear, since the middle one would lie in the segment joining the other two, so the convex hull PP of WW is a convex polygon with nonempty interior. Every vertex of PP is a point of WW, and every point of WW is a vertex of PP: if a point of WW were not a vertex, it would be a convex combination of the vertices, which are other points of WW. So the vertices of PP are exactly the points of WW.

  4. Conclusion. Every vertex of PP has at least four other vertices at the common distance 11, so no vertex of PP has no four other vertices equidistant from it, and PP refutes the question. The common distance is 11 at every vertex, which the question does not require.

  5. The general form. For an integer k≥2k\ge2, take d=4k−3≥5d=4k-3\ge5 in Theorem 1.1, so that u(Vd)≥4k−34∣Vd∣>(k−1)∣Vd∣u(V_d)\ge\frac{4k-3}4|V_d|>(k-1)|V_d|, and delete points with at most k−1k-1 others at distance 11, with φ(S)=u(S)−(k−1)∣S∣\varphi(S)=u(S)-(k-1)|S|. The same argument leaves a set of at least k+1≥3k+1\ge3 points in strictly convex position, the vertex set of a convex polygon each of whose vertices has at least kk other vertices at distance 11. The case k=4k=4 is the polygon above.

The negation of the bound O(n)O(n) that the accepted Lean proof establishes gives the input of step 1 directly: applied with the constant 33, it gives some nn for which the most unit pairs among nn points in strictly convex position exceeds 3n3n, and since that maximum is taken over counts at most (n2)\binom n2, some nn-point set in strictly convex position has more than 3n3n unit pairs; steps 2 to 4 then apply unchanged.

Relation to the sources. The erdosproblems.com remarks on Problems 96 and 97 note that a positive answer to this problem, for four equidistant vertices, would give by induction at most 3n3n unit pairs among nn points in convex position. The deduction here is the contrapositive of that remark, applied to the accepted theorem of Problem 96, with the induction written out as the deletion step above. The converse fails: a counterexample to this problem need not have many unit pairs, since this problem lets the common distance vary with the vertex. Kruer and Kohlmeyer's explanation of their disproof of Problem 96 does not apply the remark to their theorem, so the claim is the project's: that application, written out in full, with the polygon a subset of their set with d=13d=13 and the common distance 11 at every vertex. The same deduction is recorded in brief on the claim page on Problem 96. The deletion step is also stated in general form in the manuscript of Kruer, Kohlmeyer and Price of 13 September 2026, in its Lemma 4.1 and Remark 4.5, as its claim page records. That manuscript is unrefereed and a pending claim here, and it derives its own disproof of this problem from its own construction; this page relies neither on its lemma nor on its construction.

Standing. The deduction is the project's own and awaits the project's review, so the claim is claimed and lists no evidence, and the problem's standing is claimed through it and through the manuscript of Kruer, Kohlmeyer and Price. No Lean proof checks it: the accepted Lean proof of Problem 96, linked above as the input's formalization, proves only the negation of the bound O(n)O(n), and the deletion step and the passage to a polygon are not formalized. The deduction was not submitted to erdosproblems.com, which labeled the problem falsifiable.