Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Independent investigation of Erdős Problem 132
The companion file small_sets.md that Section 4 names for its expanded vertex-degree checks was not retained with this record.
1. Status and scope
For a set of distinct planar points, write
Every multiplicity in this record counts unordered pairs.
Neither unrestricted assertion was proved or disproved in this investigation. The results established here are:
- If are the distinct distances and is the number of points in the first convex layers, then
Consequently, with the largest convex-layer cardinality,
In particular, implies . 2. Writing for the largest and smallest distances, also implies . 3. for every . 4. whenever at least points are vertices of the convex hull. 5. when there are exactly two nonvertices and all the hull vertices are cocircular. 6. Every twelve-point five-distance set has exactly three rare distances. This does not settle arbitrary twelve-point sets.
Items 1–2 have self-contained elementary proofs below. Items 3–6 use specified classification statements from the supplied papers, together with additional arguments given below. No claim of historical novelty is made.
Only the supplied problem page and papers were used; there was no browsing. No earlier research notes were accessed or used. Source statements were read in the full supplied source files before use. Expanded versions of the proofs were written in companion files that are not retained.
2. A large-distance graph bound
2.1. A balanced point on a circle
Lemma. Among distinct points on a circle, some point has at least other points in each of the two closed semicircles from to its antipode. An antipodal point, if present, is counted in both semicircles.
Proof. First exclude antipodal pairs. In circular order , let count the points strictly clockwise between and its antipode. Each unordered pair contributes once, so
Moreover : shifting the initial endpoint to the next point removes at most that point, while the final endpoint advances. Set . The average of the 's is , so some value is at most and some is at least . A cyclic transition downward cannot skip . Thus some ; the other semicircle contains points.
For antipodal configurations, perturb the angular positions to remove antipodal pairs and take a sequence of perturbations tending to zero. The same selected label occurs on a subsequence. The limiting closed semicircles retain the required counts. This is why closed, rather than open, semicircles are used.
2.2. The 2-core argument
Proposition. Suppose an occurring distance has at most distinct distances larger than it. Its distance graph has a 2-core of maximum degree at most . Consequently, on any -point set,
Proof. Delete vertices of current degree at most one until the 2-core remains. At a core vertex , let be its degree; its neighbors lie on . Choose a balanced neighbor by the lemma. Since belongs to the core, it has an -neighbor .
The intersection of with the closed disk is an arc of angular length strictly less than , with as an endpoint, or is the singleton . Indeed, with , its polar description about , with direction toward as angle zero, is
One of the two closed semicircles based at , apart from , therefore lies strictly outside this disk. At least neighbors of satisfy .
There are at most possible larger lengths . For each, its circle about intersects in at most two points, since . Hence
If the core has vertices, it has at most edges. Deleting the other vertices discarded at most edges. Thus
This also handles an empty core.
For , this proves the diameter bound without importing a separate theorem.
3. Localization by convex depth
Define by repeatedly removing the vertices of the convex hull of the residual set. Nonvertex points on hull edges are not removed until a later layer. For a collinear residual set, the vertices are its two endpoints, or its sole remaining point. Put
Empty later layers contribute zero.
Depth lemma. If , then
Proof. If , , then is a nonvertex in . Write it as a nontrivial convex combination of vertices of . For fixed ,
Some is strictly farther from . Move the first endpoint outward one layer at a time, then move the second endpoint outward while keeping the new first endpoint fixed. For depths , this produces successive strict increases in distance. There are only larger distinct distances, proving (3.1). Strict increases also ensure that the chosen endpoints never coincide.
All occurrences of are thus supported on . Applying (2.1) to , which still has at most lengths larger than , gives
Therefore
The required distances exist: if , the premise gives , so a point deeper than , paired with a first-layer point, has distance rank greater than by (3.1). For , existence follows from .
Since , any integer satisfying
is a lower bound for . Solving this quadratic gives the bound in Section 1. In particular, implies divergence.
3.1. Aspect ratio
Let . Each layer has at most points. For a layer of vertices and perimeter , . The second inequality follows by integrating widths: the sum of absolute projections of the polygon's edges in direction is twice its width , and
Consequently . Layers of size at most two also satisfy the bound. Thus
This proves divergence whenever . For a integer grid, , , and , giving . This is a lower bound, not an assertion of the optimal grid order.
3.2. Necessary structure of bounded- sequences
The contrapositive of (3.3) is particularly useful. If , then
Some one of these layers therefore contains more than
points. Thus a sequence violating the asymptotic conjecture must have a positive-density convex layer among a bounded number of its outer layers. The argument does not control that remaining situation.
4. Pair counting and the small-order result
Write for the number of distances. For arbitrary ,
In particular, if , the unique rare distance is the diameter, and
For even , if , equality holds because
Thus
For odd and , the analogous calculation gives only ; it does not give a unique diameter.
4.1. Classification inputs actually used
The supplied Erdős–Fishburn 1996 source, Theorem 1 and Sections 2–4, states:
- , where is the maximum cardinality of a planar -distance set.
- The only five-point two-distance set is the regular pentagon.
- The seven-point three-distance sets are the regular heptagon and the regular hexagon together with its center.
- There are at most four similarity types of nine-point four-distance sets: the regular nonagon and three displayed configurations.
The last classification is also stated in the supplied Shinohara 2008 source, Theorem 1.1(a). The classification proofs are imported results, not independently reconstructed here.
The figures are not needed for the nine-point multiplicity check: four mutually nonsimilar examples below realize the four possible types, and hence exhaust the classification.
4.2. Exact nine-point calculations
In triangular-lattice coordinates , the squared norm is . Take
Direct substitution for all unordered pairs gives
The rows sum to . Expanded vertex-degree checks appear in small_sets.md; these integer calculations were also independently checked by a short exact enumeration.
For the third nonregular example, identify the plane with , put , and set
For two signed radii , corresponding vertices have squared distance , three times; noncorresponding vertices have squared distance , six times. The internal squared side length is , three times. Hence
The regular nonagon has spectrum . All four multiplicity multisets differ, so these examples are nonsimilar and exhaust the classification. Each has at least two rare distances; each nonregular example has a multiplicity at least fifteen.
4.3. A regular-polygon extension obstruction
Lemma. For a regular -gon , , no added point has distances to consisting of each of the polygon distances twice, and one additional distance once.
Normalize its circumcircle to the unit circle. The added point is not the center. Each equal-distance pair of vertices is interchanged by reflection in the line . The sum of all vertices is zero, so the remaining unpaired vertex also lies on . Rotate it to , and write . With , the two sets of squared distances are
Their ranges imply . Their sums, using , imply
Thus , making the unpaired vertex itself, a contradiction.
4.4. Proof for
Assume . For , (4.2) and the bounds reduce to the maximum configurations above. Their spectra are, respectively,
and the four nine-point spectra (4.4)–(4.5) and . Every one has at least two rare distances.
For , the same bounds force , so (4.3) applies. Delete one endpoint of the unique diameter. Every other distance survives, since its pairs cannot all be among the deleted pairs. The resulting -point set has exactly distances and is classified above.
If it is nonregular, it has a multiplicity when , or at least when , contradicting (4.3). Otherwise it is the regular -gon. Each old multiplicity must rise from to , and exactly one new diameter pair is added. This is precisely the impossible extension in the lemma. Therefore throughout .
4.5. Twelve points with five distances
Shinohara 2008, Theorem 1.2(b), states uniqueness up to similarity. An explicit representative is
in triangular-lattice coordinates. At squared distances , its multiplicities are
These sum to , and give . At squared distance four every vertex has degree two. Deleting one point leaves ten pairs at that distance. The three diameter pairs are the disjoint pairs
At least two survive, so every eleven-point subset of also has two rare distances.
This does not classify arbitrary eleven-point five-distance sets. Nor does it settle twelve-point six-distance sets; see Section 7.
5. A proved extension beyond convex sets
The supplied Fishburn 1995 source, Section 1, Theorems 1–2, gives the following inputs: a convex -gon has at least distances; for odd , equality forces regularity; for even , equality forces a regular -gon or a regular -gon with one vertex deleted. In particular, both even equality cases are cocircular.
5.1. One extra point inside a cocircular hull
Let be points on a circle and . For every ,
This follows from the same strict convexity identity as in Section 3 by expressing as a nontrivial convex combination of points of . It includes points in the relative interior of a hull edge.
If is not the circumcenter, circles centered at meet the circumcircle in at most two points. Thus sees at least distances, none the diameter. Consequently
excluding .
If is the circumcenter, each distance graph on has maximum degree two, hence at most edges. Adding changes just the circumradius class. For , there are at least three old classes, leaving two rare ones. For , either there are at least three old classes, or is a regular pentagon; its circumradius is a new distance and is rare. The case is already settled. Thus a cocircular hull plus one nonvertex always satisfies .
5.2. At most one nonvertex, without the circle assumption
Theorem. If at least points are hull vertices, then .
The fully convex case is the supplied Clemen–Dumitrescu–Liu Theorem 1.2, whose proof in Section 2.1 was read. Suppose instead that is the set of hull vertices and is the single nonvertex. Small orders through eight are settled above. Assume and .
If is odd, the bounds
force equality for the even polygon . Fishburn's classification makes cocircular, contradicting Section 5.1.
If is even, . If , the odd equality theorem makes regular. Otherwise , and (4.3) gives a unique diameter . Its endpoints lie in , by (5.1).
Both and are convex -point sets from which the diameter has disappeared. Thus each has exactly distances. Since , both are cocircular by the even equality classification. Their circles share hull vertices, including three noncollinear points, and hence coincide. Therefore all of is cocircular, again contradicting Section 5.1.
This endpoint-deletion step closed an initially unresolved even-order branch. It avoids needing a classification of odd polygons with one more than the minimum number of distances.
5.3. Two nonvertices with a cocircular hull
Let be hull vertices on a circle and let be the two nonvertices. For the result is already known; the following argument in fact needs only the small cases . Assume .
At least one of is not the center. If is odd, that point sees at least non-diameter lengths on . Together with the diameter this contradicts (4.2).
Let , so . An off-center point sees at least non-diameter lengths; hence , and (4.3) applies. Each off-center added point therefore sees every one of the non-diameter lengths exactly twice on .
Normalize the circle to radius one and center zero. If one added point, say , is the center, then for any non-diameter ,
a contradiction. There are distinct non-diameter lengths, so such an exists.
Otherwise both are off-center. The equal-distance pairs show that reflection in each of and permutes , with no fixed vertex. Both reflections must exchange the endpoints of the unique diameter, so their axes coincide with its perpendicular bisector. Take this common axis to be the -axis, and write , with . Write the hull vertices in reflected pairs
The two sets of squared distances to these pairs are identical:
The 's are not all equal, so comparing ranges gives . Since , . The same equality of sets then gives . Together with reflection in the -axis, this makes centrally symmetric. It has antipodal diameter pairs, contradicting uniqueness. Thus .
6. Other bounds retained, and source cautions
Two weaker elementary approaches preceded the 2-core bound. They remain valid, but are superseded for the main asymptotic purpose.
- On points a fixed-distance graph has at most two common neighbors for each pair of vertices. Thus
Combining this with support in would prove divergence under the stronger restriction .
- From (3.1), if , a -edge can only join layers with indices summing to at most . Hence
This direct count gives weaker layer-width conditions than (3.2).
The supplied Clemen–Dumitrescu–Liu source, Theorem 1.3 and Section 2.2, states
The digest miscopies the second and third expressions; the full source is the authority here. There is also an intermediate arithmetic typo in the source proof:
when , not . The next display uses the correct expression. No stronger theorem is inferred from the typo.
Equation (6.1) implies that any counterexample to must, in particular, have . This sharper two-distance source bound is separate from the elementary all-rank estimate (3.2). The detailed inherited geometric degree assertions in the source's proof were not independently reproved here; the source theorem is being used as a stated result. The new proof of (3.2) does not depend on them.
7. Failed extensions and precise remaining gaps
Counting alone
Equation (4.1) is useful only when the total number of distinct distances is sufficiently close to or above . It does not force two rare classes for arbitrary sets. Bounds on the total number of distances that grow more slowly than cannot repair this argument. A putative multiplicity sequence is not ruled out merely because the total number of distances grows.
The second-largest distance is not always rare
The supplied Vesztergombi 1987 source, main theorem and final construction, gives the sharp upper bound , with examples exceeding . Therefore one cannot universally select the two largest lengths. Those examples are not counterexamples to this problem: their other distance multiplicities would also need to be checked.
Passing from a subset to the original set
A rare distance in a convex subset or a diameter-free subset need not be rare in . Restoring the removed points can add many pairs of that same length. In particular, the supplied diameter-graph independent-set methods do not on their own transfer a rare-distance bound back to . The one-nonvertex result above avoids this gap through equality classifications and the two endpoint deletions, not through a general monotonicity assertion.
Large convex layers
The main asymptotic estimate becomes ineffective when an early convex layer contains a positive proportion of all points. This is a real unresolved branch, not a technicality. Even an arbitrary number of layers does not help if an early one is sufficiently large. Equation (3.5) precisely states what a bounded- sequence would have to satisfy; no contradiction has been obtained from it.
For convex sets, pair counting implies that a bounded- sequence would have only a bounded additive excess of distinct distances over . The supplied Fishburn paper classifies the exact minimum and discusses a conjectural wider stability phenomenon. The necessary general near-minimum classification is not established in the supplied material and was not proved here. It cannot be assumed to conclude divergence, even for all convex sets.
The first unhandled small-order branch
For , a putative counterexample has exactly five distances: four classes of size at least twelve and a diameter class of size at most seven. The supplied results do not classify all eleven-point five-distance sets, and there is no justification for assuming they extend to the unique twelve-point example .
For , the five-distance case is settled by (4.6). The remaining counterexample pattern has six distances, with multiplicities
where the singleton is the diameter. Deleting one diameter endpoint leaves an eleven-point five-distance set, bringing back the same unresolved classification branch.
Scope of the near-convex results
The theorem with at most one nonvertex is proved for every . The two-nonvertex theorem still assumes a cocircular hull. There is no proved extension here to an arbitrary hull with two or more nonvertices. Neither theorem supplies a uniform unbounded lower bound for in near-convex sets.
8. Checks and status
The main geometric argument was checked independently for antipodal neighbors, tangent circle intersections, empty 2-cores, collinear layers, nonvertex hull-edge points, and existence of all distance ranks used. The small lattice spectra were checked by exact integer arithmetic; the exceptional nine-point spectrum follows from the displayed symbolic triangle formulas. These computations verify explicit configurations only; exhaustiveness comes from the stated source classifications.
The restriction has been retained. For comparison, the four points
have five unit pairs and one pair of length , so . This is not a counterexample in the requested range.
The established results above are retained as proofs and source-dependent deductions; the large-layer branch and the unrestricted conjectures remain open within this record.