/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/modulepublicimportFormalConjecturesUtil
A sequence X is line-compatible for $n$ if there is a set P of $n$ points of
$\mathbb{R}^2$ and a finite set L of distinct lines, each containing at least two points of
P, such that X lists the numbers of points of P on the lines of L in nondecreasing
order.
Erdős's original count [Er81]: the sequences obtained from all the lines determined by a
set P of $n$ points, i.e. L is exactly the set of lines containing at least two points of
P. These form a subset of compatibleSequences n.
Call a sequence $1<X_1\leq\cdots\leq X_m\leq n$ line-compatible if there is a set of $n$ points in
$\mathbb{R}^2$ such that there are $m$ lines $\ell_1,\ldots,\ell_m$ containing at least two
points, and the number of points on $\ell_i$ is exactly $X_i$.
Prove that there are at most
$$\exp(O(n^{1/2}))$$
many line-compatible sequences.
Asked by Erdős [Er81] and proved by Szemerédi and Trotter [SzTr83]. We take the lines $\ell_i$ to
be distinct but not necessarily all the lines determined by the points, as on erdosproblems.com;
[Er81] uses all the determined lines (allLinesSequences), so this bound implies his. Finiteness
of the set is part of the statement, since Set.ncard of an infinite set is $0$.
Erdős [Er81] writes that it is 'easy' to prove there are at least
$$\exp(cn^{1/2})$$
many such sequences for some constant $c>0$, but expected proving the upper bound to be
difficult. Once it is done, he asked for the existence and value of
$$\lim_{n\to \infty}\frac{\log f(n)}{n^{1/2}},$$
where $f(n)$ counts the number of line-compatible sequences. Does this limit exist?
In [Er81], $f(n)$ counts the sequences of the numbers of points on all the lines determined by
$n$ points, i.e. (allLinesSequences n).ncard; this set is finite, as a subset of
compatibleSequences n.