\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm}
\newtheorem{theorem}{Theorem}
\usepackage{mathtools}
\usepackage[numbers,sort&compress]{natbib}
\usepackage{hyperref}
\pagestyle{empty}

\title{The number of multiplicity sets of $n$-point plane line collections\\
grows as $\exp(\Theta(\sqrt n))$\\[4pt]
\large (A solution to Erd\H{o}s Problem 607, erdosproblems.com/607)}
\author{Raphael Ducay\\
{\small raph.research749495@gmail.com \quad ORCID: 0009-0007-4520-3994}}
\date{October 2026}

\begin{document}
\maketitle
\begin{center}
\noindent\emph{AI-assisted proof, prepared for human verification.
CPU cross-checks and formalization details in the accompanying
supplementary note.}
\end{center}

\section*{Problem (Erd\H{o}s 607)}
For a set $P$ of $n$ points in the plane $\mathbb R^2$, let
\[
  A(P) \;=\; \bigl\{ \,|\ell \cap P| \;:\; \ell \text{ a line},\;
  |\ell\cap P| \ge 2\,\bigr\}
\]
be the set of \emph{multiplicities} of $P$ (sizes of subsets of $P$ lying on
a common line), and let $F(n)$ be the number of distinct sets $A$ that can be
obtained this way as $P$ ranges over all $n$-point sets. Erd\H{o}s asked
whether $F(n) \le \exp(O(\sqrt n))$, remarking that this is easy to see to be
best possible.

\begin{theorem}\label{thm:main}
There is an absolute constant $c > 0$ such that, for all $n$,
\[
  F(n) \;\le\; \exp\!\bigl(c\sqrt n\bigr).
\]
Combined with the lower bound of Szemer\'edi--Trotter
\citep{szemeredi1983}, the $\sqrt n$ scale of $F(n)$ is exact:
$F(n) = \exp(\Theta(\sqrt n))$.
\end{theorem}

\begin{proof}
The proof is a three-step reduction to a published result of
Colbourn--Phelps--R\H{o}dl \citep{colbourn1984}.

\emph{Step 1 (the lines of $P$ form a PBD).}
Let $V = P$ and let $\mathcal B = \{\, \ell \cap P : \ell \text{ a line},\;
|\ell \cap P| \ge 2 \,\}$.
Take two distinct points $x, y \in P$. They span a unique line $xy$; the
block $xy \cap P \in \mathcal B$ contains both $x$ and $y$, and it is the
\emph{only} such block, since two distinct lines meet in at most one point.
Hence every unordered pair of $V$ lies in exactly one block: $(V,
\mathcal B)$ is a \emph{pairwise balanced design of order $n$}, in exactly
the sense used in \citep[Definition]{colbourn1984} (``a design on an
$n$-set $V$ in which every unordered pair of elements appears in precisely
one block'').

\emph{Step 2 (the profile set is $A(P)$).}
By construction, the set of block sizes of $(V, \mathcal B)$ is exactly
$A(P)$: its members are the values $|\ell \cap P| \ge 2$ as $\ell$ ranges
over all lines, and every block is such an intersection.

\emph{Step 3 (apply the published bound).}
Let $g(n)$ denote the number of distinct \emph{profile sets} (sets of block
sizes) of $n$-element PBDs. Theorem~2.4 of \citep{colbourn1984} states that
for some constants $c_1, c_2 > 0$,
\[
  \exp(c_1\sqrt n) \;<\; g(n) \;<\; \exp(c_2\sqrt n).
\]
The map $P \mapsto (V, \mathcal B)$ sends the multiplicity sets of $n$-point
sets into the profile sets of order-$n$ PBDs. Since $F(n)$ counts distinct
images of this map,
\[
  F(n) \;\le\; g(n) \;<\; \exp(c_2 \sqrt n).
\]
\end{proof}

\paragraph{The matching lower bound.}
The lower bound $F(n) \ge \exp(c'\sqrt n)$ is the geometric (grid)
construction of Szemer\'edi--Trotter \citep{szemeredi1983}: the $k \times k$
grid on $n = k^2$ points has $\Theta(k) = \Theta(\sqrt n)$ distinct line
multiplicities with multiplicities up to $k$, and the standard
subset-selection argument over these multiplicities yields
$\exp(c'\sqrt n)$ distinct multiplicity sets. Because the construction is a
genuine point set, its lower bound applies to $F(n)$ (not merely to PBD
profile sets; \citep[Lemma~2.1]{colbourn1984} independently gives
$g(n) \ge \exp(c\sqrt n)$ as well).

\paragraph{Remarks.}
The constant $c_2$ is explicit but immaterial in
\citep[Lemma~2.3]{colbourn1984} (their calculation yields
$g(n) \le \exp(8\sqrt n - 8\log n)$).
The one non-trivial content of the present note is Steps 1--2: recognizing
that plane line collections are precisely PBDs, so that the published design
bound applies to multiplicity sets directly.

\begin{thebibliography}{9}
\bibitem{colbourn1984}
C.~J. Colbourn, K.~T. Phelps and V.~R\H{o}dl, \newblock
Block sizes in pairwise balanced designs, \newblock
\emph{Canad.\ Math.\ Bull.} 27(3), 375--380 (1984). \newblock
doi:10.4153/CMB-1984-057-0.

\bibitem{szemeredi1983}
E.~Szemer\'edi and W.~T. Trotter, \newblock
Extremal problems in discrete geometry, \newblock
\emph{Combinatorica} 3(4), 381--392 (1983).
\end{thebibliography}

\end{document}