The number of multiplicity sets of n-point plane line collections grows as exp(Theta(sqrt(n)))

A mix of human-written and AI-generated textHuman understanding: all partsmath.CO — Combinatoricsmath.MG — Metric Geometry

Contributed by Raphael DUCAY ↗

Version 1 / Oct 09, 2026 / CC BY 4.0

Abstract

For a set P of n points in the plane R^2, let A(P) be the set of multiplicities of P, i.e. the sizes |ell cap P| >= 2 of the subsets of P lying on a common line ell, and let F(n) be the number of distinct multiplicity sets A(P) as P ranges over all n-point sets. Erdos problem 607 (erdosproblems.com/607) asks whether F(n) <= exp(O(sqrt n)), remarking that the sqrt(n) scale is easy to see to be best possible. We prove the upper bound F(n) <= exp(c sqrt n) for an absolute constant c > 0. The proof is a three-step reduction to a published result of Colbourn-Phelps-Rodl, "Block sizes in pairwise balanced designs" (Canad. Math. Bull. 27(3), 375-380, 1984): (1) the lines determined by P, restricted to P, form a pairwise balanced design (PBD) of order n - every unordered pair of points lies in exactly one such block; (2) the profile set of block sizes of this PBD is exactly A(P); (3) Theorem 2.4 of Colbourn-Phelps-Rodl bounds the number g(n) of profile sets of order-n PBDs by exp(c2 sqrt n), hence F(n) <= g(n) < exp(c2 sqrt n). Combined with the grid construction of Szemeredi-Trotter (1983) this settles the order of magnitude exactly: F(n) = exp(Theta(sqrt n)). The essential observation is that plane line collections are precisely PBDs, so the published design-theoretic bound applies to multiplicity sets directly. A Lean 4 machine-checked formalization of the reduction is in progress for the Palomar registry and will be linked from this deposit upon acceptance.

Provenance statement

AI-assisted preparation, per Hexagon deposit terms: the note was drafted with substantial assistance from a locally hosted LLM (Qwen 3.8 27B) under the direction of the author, who independently: read the full statement of Erdos 607 and confirmed 0 existing proof claims and 0 expositions as of 2026-10-08; read the full text of Colbourn-Phelps-Rodl (1984) from the primary PDF (mathdoc.fr) and verified Theorem 2.4 verbatim; and inspected the full proof line-by-line. Reproducible CPU cross-checks (16 test families of point sets verifying the PBD structure and the equality of block-size sets with A(P); an independent Erdos-Davenport-Trotter-based upper bound) are described in the supplementary note (anc/supplementary.md). A machine-checked Lean 4 formalization is in progress for the Palomar registry.

Tools used

Local LLM (llama-swap)
Qwen 3.8 27BVersion 27B local inference

References

  1. C. J. Colbourn, K. T. Phelps and V. Rődl, Block sizes in pairwise balanced designs, Canad.\ Math.\ Bull. 27(3), 375--380 (1984). doi:10.4153/CMB-1984-057-0.DOI
  2. E. Szemerédi and W. T. Trotter, Extremal problems in discrete geometry, Combinatorica 3(4), 381--392 (1983).

Version history

  1. v1Submitted by Raphael DUCAYInitial depositCurrentOct 09, 2026