# On the structure of pointsets with many collinear triples

József Solymosi Department of Mathematics, University of British Columbia,
Vancouver, Canada and Obuda University, Budapest, Hungary. Email:
<EMAIL_ADDRESS>
###### Abstract

It is conjectured that if a finite set of points in the plane contains many
collinear triples then there is some structure in the set. We are going to
show that under some combinatorial conditions such pointsets contain special
configurations of triples, proving a case of Elekes’ conjecture. Using the
techniques applied in the proof we show a density version of Jamison’s
theorem. If the number of distinct directions between many pairs of points of
a pointset in convex position is small, then many points are on a conic.

##  1 Introduction

It is a classical and important problem in discrete geometry to understand the
structure of finite planar pointsets defining many lines containing at least
three points of this set of points. A nice survey article of many related
problems is by written by Borwein and Moser [5] and several open problems are
mentioned in the problem book of Brass, Moser, and Pach (Chapter 7 in [6]).
Solving a famous conjecture of Dirac and Motzkin, the following statement was
proved by Green and Tao in 2013 [20].

###### Theorem 1

Suppose that $P$ is a set of $n$ points in the plane. Then there are at most
$\lfloor\frac{n(n-3)}{6}\rfloor+1$ lines that contain at least three points of
$P,$ provided $n$ is large enough.

For a given set of points, $P,$ a line is determined by $P$ if it contains at
least two points of $P.$ If such a line contains exactly two points then it is
called an ordinary line. Green and Tao proved a strong structure theorem which
states that if $P$ has at most $Kn$ ordinary lines then all but $O(K)$ points
of $P$ lie on a cubic curve, if $n$ is sufficiently large depending on $K$ (in
this result $K$ is a constant or a very slowly growing function of $n$).
Unfortunately almost nothing is known about the structure of $P$ when there
are $cn^{2}$ lines with at least three points of $P,$ where $0<c<1/6.$ Elekes
conjectured that here, under this weaker condition, ten or more points of $P$
lie on a (possibly degenerate) cubic, provided that $n\geq n_{0}(c)$ (see e.g.
Conjecture 2.1 in [15]). There are some structural results for $n$-element
pointsets with $cn^{2}$ collinear triples, like in [32] and [11], but Elekes’
conjecture on “ten points on a cubic” seems to be still out of reach. There is
another related conjecture (problem) of Elekes (see in [42] and in [30]) which
was the main inspiration of this work.

######  Problem 2 (Elekes [42])

For fixed $c>0,$ suppose that the edges of a graph $G$ with $n$ vertices and
$cn^{2}$ edges are well-coloured using $n$ colours (i.e., no two edges of the
same colour are incident upon a common vertex). If $n$ is sufficiently large,
must $G$ contain a six-cycle with opposite edges having the same colour?

Elekes gave another formulation of the problem in [42]. If the colours of the
edges are represented by extra vertices, each added to the edges with its
colour, then we can state the problem (now stated as a conjecture) in terms of
3-uniform hypergraphs. A 3-uniform hypergraph is linear if any two edges have
at most one vertex common. In a 3-uniform hypergraph, six edges will be called
a tic-tac-toe if they intersect each other like the rows and columns of a
$(3\times 3)$ tic-tac-toe board. In a tic-tac-toe configuration of collinear
triples in the plane, if three pairwise independent111Two vertices are
independent if there is no edge containing both. points are collinear then the
remaining six points are on a conic (Figure 1). A 3-uniform linear hypergraph
on $n$ vertices has at most $\lfloor\frac{n(n-1)}{6}\rfloor$ edges. Elekes
conjectured, that if it contains no tic-tac-toe then it should be sparse.

###### Conjecture 3

If a 3-uniform linear hypergraph on $n$ vertices contains no tic-tac-toe then
it is sparse, it has $o(n^{2})$ edges. (For any $\varepsilon>0$ there is an
$n_{0}=n_{0}(\varepsilon)$ such that if $n\geq n_{0}$ then the number of edges
is at most $\varepsilon n^{2}.$)

This conjecture was refuted by Gishboliner and Shapira giving a nice
construction for 3-uniform hypergraphs on $n$ vertices with
$\sim\frac{n^{2}}{16}$ edges without a tic-tac-toe [19]. Earlier, Füredi and
Ruszinkó conjectured that there are 3-uniform hypergraphs on $n$ vertices with
$\sim\frac{n^{2}}{6}$ edges (almost Steiner triple systems) without a tic-tac-
toe [17]. The Füredi-Ruszinkó conjecture is still open, but Gishboliner and
Shapira already disproved Elekes’ conjecture which was more ambitious than the
famous Brown-Erdős-Sós conjecture for 9-vertex configurations.

######  Conjecture 4 (Brown-Erdős-Sós [7])

Fix $m\geq 6$. For every $c>0$, there exists a threshold $N=N(c)$ such that if
$H_{n}^{(3)}$ is a 3-uniform hypergraph on $n$ vertices with $|S|\geq cn^{2}$,
edges there exists a subset of $m$ vertices of $H_{n}^{(3)}$ which spans at
least $m-3$ edges.

About 50 years later the only known case of Conjecture 4 is when $m=6$ due to
Ruzsa and Szemerédi [31]. For some estimates and reviews of related works we
refer to [35] and [9]. In its general form Conjecture 4 has resisted all proof
attempts, however there are some special cases when even stronger statements
can be proven. When the edges of the hypergraph are defined by a finite group
with edges of the form $(a,b,a+b)$, then the underlying structure helps to
find vertices spanning many edges. There are several recent works proving such
results like in [33],[36],[24],[41], and [26].

Conjecture 3 would have implied the $m=9$ case in the Brown-Erdős-Sós
conjecture. In the tic-tac-toe configuration there are 6 edges on 9 vertices.
Elekes’ problem was motivated by the configuration illustrated in Figure 1. If
three vertices, $A,B,C,$ are collinear then the remaining six are points on a
conic. It is a special case of Elekes’ conjecture on ten points on a cubic in
the sense that it is also an over-determined system (three points on a line
and six on a conic). This configuration is also building block of Böröczky’s
example in the Green Tao paper [20].

Figure 1: If $A,B,C$ are collinear then the other six points are on a conic

While Conjecture 3 is out of reach, there is hope that for special triple
systems one can prove it, as it happened for triples from finite groups. In
this paper we are going to prove it when the edges are collinear triples in
some pointsets. We show that if the edges of a 3-uniform hypergraph are
defined by collinear triples from three sets of points, then there are
vertices spanning many edges, more than what would follow from the Brown-
Erdős-Sós conjecture. In the last section we prove that under some
combinatorial conditions, if one of the three sets consists of collinear
points, then a large fraction of the other two sets are on a conic. As noted
in [13], without extra conditions this statement would not hold. For example,
taking an affine image of an integer
$\lfloor\sqrt{n}\rfloor\times\lfloor\sqrt{n}\rfloor$ square grid with the line
of infinity, there are $cn^{2}$ collinear triples with two points in the grid
and one on the line at infinity (the points of the directions), while the grid
contains at most $n^{1/4}$ points of a parabola and $n^{o(1)}$ points of other
conics (Figure 2).

Figure 2: $A,B,C,$ and $M$ are some of the points of directions on the line at
infinity determined by the $5\times 5$ integer grid

Many collinear triples of points in a finite pointset define an over-
determined algebraic system. One would expect that such arrangements are only
possible if there is a strong algebraic structure behind the point set. It was
proved in [8, 10] that in the Euclidean space if there are $cn^{2}$ collinear
triples among $n$ points then a positive fraction of the points is in a small
dimensional affine subspace. If the points are in the plane, then there is a
structural rigidity to the setting where we bound the number of degrees of
freedom in perturbing a set of points under collinearity constraints [11].
Elekes and Szabó proved strong results in the very special case when the
points are on a small degree algebraic curve [15] . Beyond that, we only know
the structure in cases close to the extremal density of triples, by the Green-
Tao theorem [20]. The main motivation of searching dense local arrangements
(much denser than what would follow from the B-E-S conjecture) in collinear
triple systems is to find building blocks for from-local-to-global arguments,
similar to what was used by Green and Tao.

In the last section of the paper we prove a strong structural result for some
pointsets where many pairs determine few distinct directions. Using the
combinatorial model for analysing sets with few direction due to Eli Goodman
and Ricky Pollack [21], Jamison proved the following structural result.

######  Theorem 5 (Jamison [22])

If an $n$-element pointset contains no three collinear points and determines
$n$ directions then it is affinely equivalent to the vertices of a regular
$n$-gon, i.e. the points are on a conic.

The Goodman-Pollack method is nicely explained in Chapter 12 of the Proofs
from the BOOK, by Aigner and Ziegler [1] where they proved Ungar’s theorem
[39] on the minimum number of distinct directions determined by $n$ non-
collinear points in the plane.

In the problem of characterising pointsets determining few directions, we show
that if two $n$-element sets, $A$ and $B$ contain $cn^{2}$ distinct $(a,b)\in
A\times B$ pairs determining at most $n$ directions, then – under some
combinatorial assumptions – a positive fraction of the points of $A\cup B$ is
on a conic.

##  2 Elekes’ conjecture for collinear triples

While in general Conjecture 3 was disproved, we show that it holds for certain
sets of collinear triples. Given three pointsets in the plane, $P,Q,$ and $S,$
we say that the three sets are mutually avoiding set if no line determined by
two points in a set intersects the two convex hulls of the other two
pointsets. The concept of mutually avoiding sets are often used in discrete
and computational geometry, like in [2], [40], [25] and [27]. It was proved in
[2] that any planar $n$-element pointset in general position contains two
mutually avoiding subsets of size at least $\sqrt{n/12}.$

Figure 3: The three sets are mutually avoiding

###### Theorem 6

For any $\delta>0$ constant there is a threshold $n_{0}=n_{0}(\delta)$ so the
following holds. Let $A,B,C$ be mutually avoiding $n$-element pointsets in the
plane. Let us suppose that there are $\delta n^{2}$ collinear $(a,b,c)$
triples, where $a\in A,b\in B,$ and $c\in C.$ If $n\geq n_{0},$ then there is
a tic-tac-toe configuration among the collinear triples.

We are going to show an even stronger statement, that if we select a set of
collinear triples of size at least $\delta n^{2}$ then among these triples
there will be a tic-tac-toe configuration. During the proofs in this paper
when we refer to collinear triples (or simply triples or edges), then these
are triples in our selected subset of the geometrically collinear triples. We
can remove them in the proofs, even if the three points remain to be a
collinear triple in the geometric sense. In the proof we are going to use the
geometric properties of the triples and the $(6,3)$ theorem of Ruzsa and
Szemerédi twice. Because of the use of the Ruzsa-Szemerédi theorem our bound
on $n_{0}=n_{0}(\delta)$ is rather weak (the current best bound on the
triangle removal lemma is due to Jacob Fox [18]). On the other hand it is
possible that tic-tac-toe configurations are unavoidable even with $n^{2-c}$
triples for some $c>0.$222There is no $n^{2-o(1)}$ type lower bound known for
the $(9,6)$ case of the Brown-Erdős-Sós conjecture.

It follows from Pascal’s theorem that if in Theorem 6 set $C$ is a set of
collinear points, then there are three points in $A$ and three in $B$ that are
lying on the same conic (Figure 1). We will analyse this case in the last
section of the paper.

###  2.1 Proof of Theorem 6

Since the three sets $A,B,$ and $C$ are mutually avoiding, there is a natural
ordering (labeling) of the points in all three sets,
$A=\\{a_{1},\ldots,a_{n}\\},B=\\{b_{1},\ldots,b_{n}\\},C=\\{c_{1},\ldots,c_{n}\\}$
so the following conditions hold:

  * •

If $a_{i},b_{j_{1}},c_{k_{1}}$ and $a_{i},b_{j_{2}},c_{k_{2}}$ are collinear
triples and $j_{1}<j_{2}$ then $k_{1}<k_{2}$

  * •

If $a_{i_{1}},b_{j},c_{k_{1}}$ and $a_{i_{2}},b_{j},c_{k_{2}}$ are collinear
triples and $i_{1}>i_{2}$ then $k_{1}<k_{2}$

  * •

If $a_{i_{1}},b_{j_{1}},c_{k}$ and $a_{i_{2}},b_{j_{2}},c_{k}$ are collinear
triples and $i_{1}<i_{2}$ then $j_{1}<j_{2}.$

This ordering will be crucial in the proof, since we will search for $(6,3)$
configurations where the vertices in the same set are close to each other. We
will see that in this ordered geometric settings $\delta n^{2}$ collinear
triples determine some $\delta^{\prime}n^{2}$ $(6,3)$ configurations on not
too many, $\Delta n,$ close point-pairs ($\delta^{\prime}$ and $\Delta$ are
constants depending on $\delta$ only). Then we can apply the Ruzsa-Szemerédi
theorem once again to find a $(12,9)$ configuration. This configuration
contains a tic-tac-toe (Figure 4) .

Figure 4: From triples to tic-tac-toe (points $A,B,C,D,E,F,G,H,I$)

####  2.1.1 Finding many skinny (6,3) configurations

We begin this subsection with stating the theorem of Ruzsa and Szemerédi.

######  Theorem 7 (Ruzsa-Szemerédi [31])

For any $\epsilon>0$ there is a threshold, $\nu(\epsilon),$ such that if a
3-uniform hypergraph has $n\geq\nu(\epsilon)$ vertices and at least $\epsilon
n^{2}$ edges, then there are six vertices spanning at least three edges of the
hypergraph.

In our application the hypergraph is a linear three-partite 3-uniform
hypergraph, since the edges are defined by collinear triples with one vertex
in each sets. The only $(6,3)$ configuration which is possible is isomorphic
to the second figure (b,) in Figure 4.

###### Definition 8

A $(6,3)$ configuration in the sets
$A=\\{a_{1},\ldots,a_{n}\\},B=\\{b_{1},\ldots,b_{n}\\},C=\\{c_{1},\ldots,c_{n}\\}$
is called $N$-skinny if the spanning vertices are
$a_{i},a_{j},b_{k},b_{\ell},c_{u},c_{v}$ and
$\max\\{|i-j|,|k-\ell|,|u-v|\\}\leq N.$

###### Lemma 9

For any $\delta>0$ there is a $\delta^{\prime}>0$ and natural number $N$ such
that $\delta n^{2}$ collinear $a,b,c$ triples ($a\in A,b\in B,c\in C$)
determine at least $\delta^{\prime}n^{2}$ $N$-skinny $(6,3)$ configurations
provided $n$ is large enough. Moreover one can assume that the $(6,3)$
configurations are edge-disjoint, they don’t share collinear triples.

P r o o f. Let us choose a large constant $M.$ We will determine the value of
$M$ during the proof. It is a constant, so for the sake of simplicity we can
assume that $M$ divides $n.$ Let us partition the vertices of $A$ and $C$ into
$n/M$ classes such that each partition class contains consecutive elements.
$P_{1}=\\{a_{1},\ldots,a_{M}\\},P_{2}=\\{a_{M+1},\dots,a_{2M}\\},\ldots$ etc.
and $Q_{1}=\\{c_{1},\ldots,c_{M}\\},Q_{2}=\\{c_{M+1},\dots,c_{2M}\\},\ldots$
etc.

###### Definition 10

For an $(i,j)$ pair, $b\in B$ is said to be $\varepsilon$-good if there are at
least $\varepsilon M$ collinear triples $(a,b,c)$ where $a\in P_{i}$ and $c\in
Q_{j}.$ By saying that an $(a,b,c)$ triple is $\varepsilon$-good we mean that
$b$ is $\varepsilon$-good for the $(i,j)$ pair, where $a\in P_{i}$ and $c\in
Q_{j}.$

Let us count the number of $(b,i,j)$ triples where $b$ is $\varepsilon$-good
for $(i,j)$.

For every $b\in B$ let us complete the following pruning process:

  1. 1.

If the vertices of a $P_{i}$ contributes to less than $\frac{\delta}{4}M$
triples with $b$ and any $c\in C$ then let’s remove these triples ($1\leq
i\leq n/M$). Then we repeat the process with $Q_{i}$-s, if there are less than
$\frac{\delta}{4}M$ vertices in a $Q_{i}$ forming a collinear triple with $b$
and some vertices of $A$ then remove the triples. Next we check $P_{i}$-s
again, removing triples if there are less than $\frac{\delta}{4}M$ triples
with the vertices in this partition class. Then we check $Q_{i}$-s again and
repeat this alternating process as long as we can. The total number of removed
triples is less than $2\frac{n}{M}\frac{\delta}{4}M=\frac{\delta}{2}n$.

  2. 2.

Let us call triples $(a,b,c)$ $a\in P_{i}$ and $c\in Q_{j}$ with point $b\in
B$ to be weak if the total number of collinear triples
$(a^{\prime},b,c^{\prime})$ $a^{\prime}\in P_{i}$ and $c^{\prime}\in Q_{j}$ is
less than $\frac{\delta}{8}M,$ or, equivalently, $b$ is not
$\frac{\delta}{8}$-good for $(i,j).$ Remove all weak triples.

We have to show that after the second step we still have many triples, if
there were many triples through $b$. At this point we have to use the
geometric properties of sets $A$ and $C.$ If there is a collinear triple
$(a,b,c),$ $a\in P_{i}$ and $c\in Q_{j}$ with point $b\in B$ then we can’t
conclude that there are many triples between $P_{i}$ and $Q_{j}$ through $b$
even in this geometric setting (see Figure 5).

Figure 5: There is only one collinear triple between $P_{i}$ and $Q_{j}$

On the other hand a collinear triple guaranties that there are many triples
either between $P_{i}$ and $Q_{j}$ or in their neighbourhood. If there is a
collinear triple between $P_{i}$ and $Q_{j}$ via $b\in B$ then let
$V_{b}=\\{a_{i_{1}},\ldots,a_{i_{m}}\\}\subset P_{i},$
(${i_{1}}<\ldots<{i_{m}}$) denote the set of points in $P_{i}$ where there is
another point in $C$ forming a triple with $b.$ Similarly,
$W_{b}=\\{c_{j_{1}},\ldots,c_{j_{\ell}}\\}\subset Q_{j},$
(${j_{1}}<\ldots<{j_{\ell}}$) denote the set of points in $Q_{j}$ where there
is another point in $A$ forming a triple with $b.$ Because of the first step,
we know that both $m$ and $\ell$ are at least $\frac{\delta}{4}M.$

For any triple, $(a_{i_{s}},b,c_{j_{t}}),$ at least
$\min\left(s,\frac{\delta}{4}M\right)$ triples $(a_{i_{u}},b,x),$ where $x\in
C$ and $u\leq s,$ are triples between $P_{i}$ and $Q_{j}\cup Q_{j+1}.$ 333Let
us suppose that $P_{0}=Q_{0}=P_{\frac{n}{m}+1}=Q_{\frac{n}{m}+1}=\emptyset$
Similarly, when $u\geq s$ then at least
$\min\left(m-s,\frac{\delta}{4}M\right)$ triples are between $P_{i}$ and
$Q_{j}\cup Q_{j-1}.$ Out of the $y$ elements of $A,$ when $(y,b,c_{j_{v}})$ is
a collinear triple and $v\leq t,$ at least
$\min\left(v,\frac{\delta}{4}M\right)$ are in $P_{i}\cup P_{i+1},$ and when
$v\geq t$ then for at least $\min\left(\ell-v,\frac{\delta}{4}M\right)$
$y\in\\{P_{i}\cup P_{i-1}\\}.$ If $(a_{i_{s}},b,c_{j_{t}})$ is weak then both
$a_{i_{s}}$ and $c_{j_{t}}$ should be among the first $\frac{\delta}{8}M$
points or both are among the last $\frac{\delta}{8}M$ points of $V_{b}$ and
$W_{b}.$ More precisely

$\min(s+t,(m+\ell-s-t))\leq\frac{\delta}{8}M.$

After the first step of the pruning process let’s check the triples
$(a_{\alpha},b,c_{\beta}),$ $a_{\alpha}\in A,c_{\beta}\in C,$ starting with
the least index $\alpha$ in increasing order. By the previous observations the
longest sequence of weak triples is less than $\frac{\delta}{8}M$ always
followed by at least $\frac{\delta}{8}M$ many $\frac{\delta}{8}$-good triples
(if there are triples left). If the number of triples through $b$ after the
first step is denoted by $\Gamma_{b}$ ($\geq\frac{\delta}{2}n$) then the
number of weak triples is at most

$\left\lceil\frac{\Gamma_{b}}{2\cdot\frac{\delta}{8}M}\right\rceil\cdot\frac{\delta}{8}M<\frac{\Gamma_{b}}{2}+\frac{\delta}{8}M.$
(1)

After the pruning process is finished for all $b\in B,$ the total number of
removed triples is less than

$\sum_{b\in
B}\frac{\delta}{2}n+\frac{\Gamma_{b}}{2}+\frac{\delta}{8}M\leq\frac{3\delta}{4}n^{2}+\frac{\delta}{8}Mn.$
(2)

We still have about the quarter of the original triples,
$\frac{\delta}{4}n^{2}-O(n),$ and now every triple is $\frac{\delta}{8}$-good
for the relevant $(i,j)$ pair. For reference in later applications we record
the partial result we have in the following claim.

###### Claim 11

Under the conditions of Theorem 6 at least
$\frac{\delta}{4}n^{2}-\frac{\delta}{8}Mn$ triples are
$\frac{\delta}{8}$-good.

Note that up to this point the only property we used for the pointset $B$ is
that no line determined by the points of $A$ or by the points of $C$
intersects the convex hull of $B,$ so Claim 11 holds under the weaker
conditions that $A$ and $C$ are mutually avoiding and $A$ and $C$ are avoiding
$B.$

In the remaining part of the proof of Theorem 6 we ignore the linear error
term, it has no effect in the arguments. As the last step of pruning we check
the number of the remaining collinear triples between the $P_{i},Q_{j}$ pairs
for all $1\leq i,j\leq n/M.$ If the number of triples is less than
$\frac{\delta}{8}M^{2}$ then remove all triples between $P_{i}$ and $Q_{j}.$
After this we left with at least $\frac{\delta}{8}n^{2}$ triples, and whenever
there is a triple between two partition classes $P_{i}$ and $Q_{j}$ if is
$\frac{\delta}{8}$-good for $(i,j),$ and there are at least
$\frac{\delta}{8}M^{2}$ triples between $P_{i}$ and $Q_{j}.$

We can apply the Ruzsa-Szemerédi theorem for triple systems between all
$P_{i},Q_{j}$ pairs where we have at least one triple left between them. As we
noted before, there are at least $\frac{\delta}{8}M^{2}$ triples between them,
and the number of points from $B$ forming the triples is at most

$\frac{M^{2}}{\frac{\delta}{8}M}=\frac{8}{\delta}M$

By Theorem 7 we can set $M$ large enough such that if the number of triples is
at least $\frac{\delta}{8}M^{2}$ on $\left(\frac{8}{\delta}+2\right)M$
vertices then it contains a $(6,3)$ configuration. It is satisfied is we
choose $M=\nu(\delta^{3}/128).$ We continue to work with this parameter $M.$
The number of triples is at least $\frac{\delta}{8}n^{2}$, so there are at
least $\frac{\delta}{8M^{2}}n^{2}$ distinct $(i,j)$ pairs so that there is a
$(6,3)$ configurations spanned by the triples between $P_{i}$ and $Q_{j}.$ For
every $1\leq i\leq n/M$ we select two points from $P_{i}$ and two points from
$Q_{i}$ such that the selected pairs span many $(6,3)$ configurations
(together with the points of $B.$) Let’s choose the pairs independently at
random. The probability that both pairs of points of a $(6,3)$ configuration
from $A$ and $C$ have been selected is $\binom{M}{2}^{-2}.$ So, there is a way
to select $4n/M$ points, two from every partition class of $A$ and $C,$ such
that the selected pairs span at least $\frac{\delta}{4M^{4}}n^{2}$ distinct
$(6,3)$ configurations. If the spanning vertices of such a configuration are
denoted by $a_{i},a_{j},b_{k},b_{\ell},c_{u},c_{v}$ then
$\max\\{|i-j|,|u-v|\\}\leq M.$

What is left in the proof of Lemma 9 is to show that there is a constant $N,$
such that many of the selected configurations satisfy $|k-\ell|\leq N.$ For
this we are going to use the ordering (labeling) of $B.$ In a $(6,3)$
configuration there is one point in $B$ which is in two collinear triples and
the other is in one triple. In at least half of the configurations the order
of the two types of points are the same. Let us suppose that the double point
has the smaller subscript in most of the earlier selected triples and keep
these configurations only. We have at least $\frac{\delta}{8M^{4}}n^{2}$
configurations left. Every $(6,3)$ configuration has its pair of points in $C$
in one of the $M$ pairs selected in the random process. If the number of
configurations on a selected pair is less than half of the average, when it is
less than $\frac{\delta}{16M^{3}}n,$ then throw them away. We have at least
$\frac{\delta}{8M^{4}}n^{2}$ configurations left. Note that in any two
configurations with the same pair of points in $C,$ where the vertices are
denoted by $a_{i},a_{j},b_{k},b_{\ell},c_{u},c_{v}$ and
$a_{i^{\prime}},a_{j^{\prime}},b_{k^{\prime}},b_{\ell^{\prime}},c_{u},c_{v},$
the intervals $[k,\ell]$ and $[k^{\prime},\ell^{\prime}]$ are disjoint, since
the pairs $a_{i},a_{j}$ and $a_{i^{\prime}},a_{j^{\prime}}$ are in different
partition classes. (Figure 6 ).

Figure 6: The intervals $[k,\ell]$ and $[k^{\prime},\ell^{\prime}]$ are
disjoint

Since these intervals of indices are disjoint, no pair in $C$ can hold more
than $\frac{\delta}{32M^{3}}n,$ configurations where the two points
$b_{k},b_{\ell}\in B$ are far, when $|k-\ell|\geq\frac{32M^{3}}{\delta}.$ This
proves the lemma with parameters $N=\frac{32M^{3}}{\delta}$ and
$\delta^{\prime}=\frac{\delta}{16M^{4}}n^{2},$ where $M=\nu(\delta^{3}/128).$
$\Box$

####  2.1.2 Using Ruzsa-Szemerédi again

To complete the proof of Theorem 6 we define a 3-uniform hypergraph, where the
edges are the skinny $(6,3)$ configurations we left with after the last step
in the previous section. From the pointsets $A$ and $B$ the vertices of the
new hypergraph are the $2n/M$ pairs we selected in the random process. In
pointset $B$ let’s consider all pairs $b_{k},b_{\ell}\in B,$ where
$|k-\ell|\leq N.$ For each such pair we can assign an integer, the number of
$(6,3)$ configurations containing this pair of points. We follow a greedy
algorithm to select vertex disjoint pairs contributing in many skinny $(6,3)$
configurations.

  1. 1.

Select a pair $b_{k},b_{\ell}$ with the highest assigned value, say $v$.

  2. 2.

Remove all pairs $b_{k^{\prime}},b_{\ell^{\prime}}$ where the $k=k^{\prime}$
or $\ell=\ell^{\prime}.$ There are less than $4N$ such pairs, and all removed
pair had value less than $v.$

  3. 3.

If there are pairs left, then go back to step one.

The selected pairs will be the middle vertices of the triples (edges). All
together we have at least $\frac{\delta^{\prime}}{4N}n^{2}$ edges (triples) on
at most $2n/M+n/2$ vertices. We can apply Theorem 7 to conclude that if
$n\geq\nu(\frac{\delta^{\prime}}{4N})$ then it contains the $(12,9)$
configuration we were looking for (picture $c,$ in Figure 4).

##  3 The Brown-Erdős-Sós conjecture for collinear triples

We proved the existence of $(12,9)$ configurations in large dense systems of
collinear triples between three mutually avoiding pointsets. Removing points
from this arrangement we have $(11,8),(10,7),(9,6)$ configurations, matching
the numbers of the B-E-S conjecture. For larger values we can get denser
configurations, similar to the case of triples from finite groups mentioned in
the introduction. One way to prove such results is to iterate the method we
used it the proof of Theorem 6. We can find many skinny $(12,9)$
configurations, and consider them as edges of a 3-uniform graph on some four-
tuples of points as vertices, and then apply Ruzsa-Szemerédi again. This way
we would get $3\cdot 9$ edges on $2\cdot 12$ vertices, a $(24,27)$
configuration. By further iterations one would get $(3^{k+1},2^{k}3)$
configurations. But this method involves the iteration of the Ruzsa-Szemerédi
theorem, which gives a very poor bound. On the other hand, one can use some
elements of the previous proof to get better bounds than what would follow
from the B-E-S conjecture even in sparse systems.

###### Definition 12

A $k$-complete collinear triple arrangement (or $k$-system in short) consists
of $k$ disjoint $k$-element pointsets in $A,$ denoted by
$A_{1}=\\{a_{1}^{(1)},\ldots,a_{k}^{(1)}\\},\ldots,A_{k}=\\{a_{1}^{(k)},\ldots,a_{k}^{(k)}\\}$
and $k$ disjoint $k$-element pointsets in $C,$ denoted by
$C_{1}=\\{c_{1}^{(1)},\ldots,c_{k}^{(1)}\\},\ldots,C_{k}=\\{c_{1}^{(k)},\ldots,c_{k}^{(k)}\\}$
such that for every $1\leq i,j\leq k$ there is a point $b_{i,j}\in B$ such
that for every $1\leq\ell\leq k$ the points $a_{\ell}^{(i)},$ $b_{i,j}$ and
$c_{k-\ell+1}^{(j)}$ form a collinear triple.

Figure 7: This is a $3$-complete collinear triple arrangement (a 3-system)

A $k$-system has at most $3k^{2}$ points (some $b_{i,j}$ points might be the
same) and $k^{3}$ edges.

###### Theorem 13

For any $k\in\mathbb{N}$ there are positive constants $\gamma_{k}>0,\mu_{k}>0$
and a threshold $n_{0}(k)$ such that the following holds. Let $A$ and $C$ be
mutually avoiding $n$-element pointsets in the plane such that no line
determined by $A$ or determined by $C$ intersects the convex hull of the
$n$-element pointset $B$. Let us suppose that that there are at least
$\mu_{k}n^{2-\gamma_{k}}$ collinear $(a,b,c)$ triples, where $a\in A,b\in B,$
and $c\in C.$ If $n\geq n_{0},$ then there is a $k$-system among the collinear
triples.

P r o o f. We are going to use the calculations and notations leading to Claim
11 in the proof of Theorem 6. There are at least
$\frac{\delta}{4}n^{2}-\frac{\delta}{8}Mn$ triples that are
$\frac{\delta}{8}$-good among $\delta n^{2}$ triples. Set
$\frac{\delta}{8}M=k,\mu_{k}=8k$ and $M=n^{\gamma_{k}}$. If $\gamma$ is small
enough then we can still assume that $M$ divides $n.$ (If the number of
triples in the arrangement was $T,$ then we can throw away a few points and
less than $2T/n^{1-\gamma}$ triples adjacent to them before starting the
proof) With this setup $\delta=\frac{8k}{n^{\gamma_{k}}}$ and at least
$2kn^{2-\gamma_{k}}-kn^{1+\gamma_{k}}$ triples are $\frac{k}{M}$-good since
$\mu_{k}n^{2-\gamma_{k}}=\delta n^{2}.$

We now estimate the number of $k$-branches, the building blocks of
$k$-systems. The $k$-branches are spanned by the $P_{i},Q_{j}$ partition
classes for some $1\leq i,j\leq n^{1-\gamma_{k}}.$ They are formed by $k$
triples, $a,b,c,$ sharing the same $b\in B$ where $a\in P_{i}$ and $c\in
Q_{j}.$ There are at least $2n^{2-\gamma_{k}}-n^{1+\gamma_{k}}$ such branches.
Let’s choose $k$ points from each $P_{i}$ and $Q_{j}$ independently at random.
If the number of $k$-branches between $P_{i}$ and $Q_{j}$ is denoted by
$K_{ij}$ then the probability of selecting the $2k$ points of a $k$-branch in
$A$ and $B$ is $K_{ij}\binom{M}{k}^{-2},$ so there is a selection of
$k$-tuples where the number of $k$-branches is at least

$\sum_{1\leq i,j\leq
n^{1-\gamma}}K_{ij}\binom{M}{k}^{-2}\geq\left(2n^{2-\gamma_{k}}+n^{1+\gamma_{k}}\right)\binom{M}{k}^{-2}\geq\frac{k!}{e}\left(2n^{2-(k+1)\gamma_{k}}-n^{(1+(k-1)\gamma_{k}}\right)\geq\frac{k!}{e}n^{2-(k+1)\gamma_{k}}.$

For the last inequality we assumed that $\gamma_{k}<\frac{1}{2k}.$ Let us
define an auxiliary bipartite graph where the vertices are the selected
$k$-tuples of points and there is an edge between two if there was a
$k$-branch selected on the $2k$ points. This graph has $n^{1-\gamma_{k}}$
vertices in each vertex class and at least $\frac{k!}{e}n^{2-(k+1)\gamma_{k}}$
edges. By the Kővári-Sós-Turán theorem [23] if

$(1-\gamma_{k})\left(2-\frac{1}{k}\right)\leq 2-(k+1)\gamma_{k}\quad\text{i.e.
when}\quad\gamma_{k}\leq\frac{1}{k^{2}-k+1,}$

then the graph contains a complete bipartite graph $K_{k,k}$ which proves the
existence of a $k$-system among the triples. $\Box$

With the same $\gamma_{k}$ exponent, by increasing the constant multiplier,
$\mu_{k},$ a larger bipartite graph, $K_{k,t}$ will appear in the bipartite
graph. Using a larger $t$ one can guarantee a $k$-system where all $b\in B$
vertices are distinct, so the system contains exactly $3k^{2}$ points. It is a
particular $(3k^{2},k^{3})$ configuration, which is an unavoidable collinear
triple configuration even in sparse systems.

##  4 When one set of points is collinear

In this section we assume that set $C$ consists of $n$ collinear points, the
convex hulls of $A$ and $B$ are not intersected by the line of $C$ and no line
determined by the points of $A$ intersects the convex hull of $B$. Let us
suppose that that there are $\delta n^{2}$ collinear $(a,b,c)$ triples, where
$a\in A,b\in B,$ and $c\in C.$ In the case when $A$ is also a set of collinear
points Elekes proved that a positive fraction of the points of $B$ should be
also collinear [12]. Elekes and Szabó proved the stronger statement that if
the points of $A\cup C$ are on a conic then a positive fraction of the points
of $B$ is collinear (Theorem 5.2 in [15]). Our main result in this section is
to show that if $C$ is collinear, then—under some additional conditions—many
points of $A$ and $B$ are on a conic. Let’s recall another conjecture of
Elekes, similar to the earlier ones:

######  Conjecture 14 (Elekes [14])

For every $C>0$ there is an $n_{0}=n_{0}(C)$ with the following property. If
$A\subset\mathbb{R}^{2},$ $|A|\geq n_{0}$ and the number of directions
determined by $A$ is at most $C|A|$ then $A$ contains six points of a
(possibly degenerate) conic. (As usual, a pair of lines is considered a
degenerate conic.)

In his classical paper Sums vs Products [13] Elekes writes the following about
his conjecture:

“It is very likely that Conjecture 14 holds for any number in place of six,
for $|A|$ large enough. It was pointed out by M. Simonovits, that one cannot
expect $c^{*}|A|$ conconic points in general (as shown by a square lattice.)
However, some $|A|^{\alpha}$ such points may exist, for a suitable
$\alpha=\alpha(C)$. Perhaps even $c^{*}|A|$ can be found, provided that $A$ is
the vertex set of a convex polygon.”

We will show a stronger, density version of this later statement.

###### Theorem 15

For any $D>0$ and $c>0$ there is a constant, $\delta>0,$ and a threshold
$n_{0}=n_{0}(c,D)$ so the following holds. Let $A$ be a set of $n$ points in
the plane in convex position (the vertex set of a convex polygon) such that at
least $cn^{2}$ pointpairs determine at most $Dn$ distinct directions. If
$|A|\geq n_{0}$ then at least $\delta n$ points of $A$ are on a conic.

Theorem 15 is a direct corollary of Lemma 17 below. Before proving Elekes’
conjecture, we need a somewhat technical definition.

###### Definition 16

For a given line $L,$ two triangles $(p,q,r)$ and
$(p^{\prime},q^{\prime},r^{\prime})$ are similar relative to $L,$ if the three
intersection points of the lines through the corresponding sides are on $L.$
Two triples of points are said to be similar, if they are vertices of two
similar triangles.

Figure 8:  $(p,q,r)$ and $(p^{\prime},q^{\prime},r^{\prime})$ are similar
relative to $L$

Note that there are no similar triples in a convex set of points. In the first
section we proved Theorem 6, which implies that if $C$ is a set of collinear
points then many 6-tuples of points from $A\cup B$ are on a conic. Now we have
all the tools needed to show that under some additional conditions a positive
fraction of the points in $A\cup B$ are on a conic.

###### Lemma 17

For any $\delta>0$ constant there is a threshold $n_{0}=n_{0}(\delta)$ and
$\gamma=\gamma(\delta)$ so the following holds. Let $A,B,C$ be $n$-element
pointsets in the plane. Assume that $n>n_{0}$ and

  1. 1.

$C$ is a set of collinear points,

  2. 2.

no three points are collinear and no two triples are similar respect to the
line of $C$ in $A$,

  3. 3.

the convex hulls of $A$ and $B$ are not intersected by the line of $C,$

  4. 4.

no line determined by the points of $A$ intersects the convex hull of $B,$

  5. 5.

there are at least $\delta n^{2}$ collinear $(a,b,c)$ triples, where $a\in
A,b\in B,$ and $c\in C.$

Then at least $\gamma n$ points of $B$ are on a conic.

###  4.1 The proof of Lemma 17

In the proof we refer to the calculations preceding Claim 11. Based on the
collinear triples we will define a bipartite graph formed by 3-branches in a
similar way as we did in the proof of Theorem 13. This bipartite graph is
dense, so we will find a $K_{2,\ell}$ subgraph where $A$ contains two vertices
(quadruples) and $C$ contains $\ell\sim cn$ vertices. We will show then that
the points of the corresponding $b\in B$ points are on a low degree algebraic
curve. We will follow the exponents of $\delta$ during the calculations in
case one is interested about conclusions similar to Lemma 17 when
$\delta=n^{\varepsilon}$ for some $\varepsilon>0.$

####  4.1.1 The auxiliary bipartite graph

We are going to use the same parameters we had in the previous sections. By
Claim 11 at least

$\frac{\delta}{4}n^{2}-\frac{\delta}{8}Mn$ (3)

triples are $\frac{\delta}{8}$-good for the relevant $(i,j)$ pairs. We choose
the parameter $M$ to be the least integer such that $\lfloor\frac{\delta
M}{8}\rfloor\geq 3,$ so if there is a triple between a $P_{i},Q_{j}$ pair
after the pruning process before Claim 11, then there is at least one 3-branch
between $P_{i}$ and $Q_{j}.$ We choose independently at random a triple of
points is each $P_{i}$ and $Q_{j}$ ($1\leq i,j\leq n/M$). Since
$M\leq\frac{24}{\delta}+1,$ a constant nicely depending on $\delta$, we can
ignore the linear term in (3) which is at most about $3n$. There are at least
$\frac{\delta}{12}n^{2}$ distinct (but not necessarily vertex disjoint)
3-branches. The expected number of selected 3-branches - when both the top and
bottom triples were selected - is at least

$\binom{M}{3}^{-2}\frac{\delta}{12}n^{2}>c_{1}\delta^{7}n^{2},$ (4)

with a universal constant $c_{1}>0.$ Now we are ready to define the auxiliary
bipartite graph, $G(P,Q)$. The vertices are the selected triples in $P_{i}$-s
and $Q_{j}$-s. There are $2\times n/M$ such triples, so both vertex classes of
the bipartite graph $G(P,Q)$ have size about $\frac{\delta n}{24},$ denoted by
$N.$ There is a choice of triples such that the number of edges in $G(P,Q)$ is
at least the expected number of edges in the random selection, it is at least
$c_{2}\delta^{6}N^{2}.$ If $n$ is large enough then there are two vertices in
$P$ with at least $c_{3}\delta^{12}N$ common neighbours in $Q.$

Let us denote the corresponding two triples of points in $A$ by
$(\alpha_{1},\beta_{1}),(\alpha_{2},\beta_{2}),(\alpha_{3},\beta_{3})$
and
$(a^{\prime}_{1},b^{\prime}_{1}),(a^{\prime}_{2},b^{\prime}_{2}),(a^{\prime}_{3},b^{\prime}_{3}).$
The corresponding triples in $Q$ are denoted by
$(s^{\prime}_{1},t^{\prime}_{1},u^{\prime}_{1}),\ldots,(s^{\prime}_{m},t^{\prime}_{m},u^{\prime}_{m})$
where $m\geq c_{3}\delta^{12}N.$

####  4.1.2 Finding the algebraic curve in $B$

To simplify the remaining calculations let us apply a homothety transformation
which sends the first three points,
$(\alpha_{1},\beta_{1}),(\alpha_{2},\beta_{2}),(\alpha_{3},\beta_{3}),$ to
some pre-set coordinates. Depending on the position of the points we apply one
of the transformations below. In both transformations the line of $C$ is the
$x$-axis.

$T_{1}:(\alpha_{1},\beta_{1}),(\alpha_{2},\beta_{2}),(\alpha_{3},\beta_{3})\Longrightarrow(1,1),(0,1),(0,2)\quad\text{(Figure
\ref{fig:masodik})}$

and the other possible transformation is

$T_{2}:(\alpha_{1},\beta_{1}),(\alpha_{2},\beta_{2}),(\alpha_{3},\beta_{3})\Longrightarrow(0,.5),(0,1),(1,1)\quad\text{(Figure
\ref{fig:elso})}.$

In the figures the images of the other three points and the set $B$ are just
illustrations, they could be anywhere satisfying the conditions of Lemma 17.

|
---|---
Figure 9: The vertices of triangle $A$ are mapped to $(1,1),(0,1),(0,2)$ |
---|---
Figure 10: The vertices of triangle $A$ are mapped to $(0,.5),(0,1),(1,1)$

Let’s complete the calculations for the first case, applying $T_{1}.$ The
other case is similar, we will discuss it after completing the first case.

Figure 11: With the right selection of points, $(x,y)$ moves along an
algebraic curve

We denote the image of
$(a^{\prime}_{1},b^{\prime}_{1}),(a^{\prime}_{2},b^{\prime}_{2}),(a^{\prime}_{3},b^{\prime}_{3})$
by $(a_{1},b_{1}),(a_{2},b_{2}),(a_{3},b_{3}),$

$T_{1}:(a^{\prime}_{1},b^{\prime}_{1}),(a^{\prime}_{2},b^{\prime}_{2}),(a^{\prime}_{3},b^{\prime}_{3})\Longrightarrow(a_{1},b_{1}),(a_{2},b_{2}),(a_{3},b_{3}),$

and

$T_{1}:(s^{\prime}_{i},t^{\prime}_{i},u^{\prime}_{i})\Longrightarrow(s_{i},t_{i},u_{i})\quad(1\leq
i\leq m).$

For a point $(x,y),$ where $y\neq 1,2$ the lines through $(x,y)$ and the
points $(0,1),(0,2),(1,1)$ will intersect the $x$ axis in coordinates
$u=\frac{x}{1-y},$ $t=\frac{2x}{2-y}$ and $s=\frac{x-y}{1-y}$ (Figure 11). If
$(x,y)$ is in $T_{1}(B)$ as a midpoint of a 3-branch connecting
$(0,1),(0,2),(1,1)$ to $(s_{i},t_{i},u_{i})$ for some $1\leq i\leq m,$ then
there is also a 3-branch between $(a_{1},b_{1}),(a_{2},b_{2}),(a_{3},b_{3})$
and $(s_{i},t_{i},u_{i}).$ Since the three lines of this 3-branch

  1. 1.

$\ell_{1}:$ $-b_{1}X+(a_{1}-u_{i})Y+u_{i}b_{1}=0,$

  2. 2.

$\ell_{2}:$ $-b_{2}X+(a_{2}-t_{i})Y+t_{i}b_{2}=0,$

  3. 3.

$\ell_{3}:$ $-b_{3}X+(a_{1}-s_{i})Y+s_{i}b_{3}=0,$

are concurrent we have the following identity for many $i$

$\begin{vmatrix}b_{1}&a_{1}-u_{i}&b_{1}u_{i}\\\
b_{2}&a_{2}-t_{i}&b_{2}t_{i}\\\ b_{3}&a_{3}-s_{i}&b_{3}s_{i}\end{vmatrix}=0.$

We want to show that the $(x,y)$ solutions, the zero set of the polynomial
below, in equation (5) – the two-variable polynomial given by the determinant
– is a one dimensional algebraic set, it is an algebraic curve.

$\begin{vmatrix}(1-y)b_{1}&(1-y)a_{1}-x&b_{1}x\\\
(2-y)b_{2}&(2-y)a_{2}-2x&2b_{2}x\\\
(1-y)b_{3}&(1-y)a_{3}-(x-y)&b_{3}(x-y)\end{vmatrix}=0.$ (5)

Even from the geometric way we defined the equations we see that the $y=0$
line is part of the zero set, but we will show that if $y\neq 0,1,2$ then for
any given $y$ value, $x$ has at most two possible values. For a fixed $y,$
equation (5) is a quadratic equation in $x.$ If it takes three or more
different values then all three coefficients of the quadratic equation should
be zero. The constant term is

$-b_{3}y\begin{vmatrix}(1-y)b_{1}&(1-y)a_{1}\\\
(2-y)b_{2}&(2-y)a_{2}\end{vmatrix}$

which is zero only if $b_{1}a_{2}=a_{1}b_{2}.$ The two points, $(a_{1},b_{1})$
and $(a_{2},b_{2})$ are on a line through the origin, i.e. there is a $c>0$
such that $(a_{1},b_{1})=(ca_{2},cb_{2}).$

The coefficient of the quadratic term is

$b_{1}\begin{vmatrix}(2-y)b_{2}&-2\\\
(1-y)b_{3}&-1\end{vmatrix}-2b_{2}\begin{vmatrix}(1-y)b_{1}&-1\\\
(1-y)b_{3}&-1\end{vmatrix}+b_{3}\begin{vmatrix}(1-y)b_{1}&-1\\\
(2-y)b_{2}&-2\end{vmatrix}=yb_{2}(b_{1}-b_{3})$

which is zero only if $b_{1}=b_{3}.$

If we just want to see the proof of Theorem 15, then at this point we are
done, since our selection of the two triples of points from the convex
pointset doesn’t allow such accidents. For the proof of Lemma 17 let’s
complete the calculations of coefficients. We will see that there are pairs of
triples where the zero set of the polynomial in (5) is a two-dimensional set.

The coefficient of the linear term is a bit harder to calculate, it is

$y^{2}b_{1}b_{2}-ya_{3}b_{1}b_{2}(y-1)-2yb_{1}b_{3}(y-1)-2yb_{2}b_{3}+y^{2}b_{2}b_{3}+ya_{1}b_{2}b_{3}(y-1).$

Assuming that the other two coefficients are zero, i.e. $b_{1}=b_{3}$ and
$b_{1}a_{2}=a_{1}b_{2},$ this coefficient is

$y(y-1)b_{2}b_{3}(a_{1}-a_{3}-2c+2),$

which is zero only if $a_{3}=a_{1}-2c+2.$

If the coordinates of the three points satisfy the equations

$(a_{1},b_{1})=(ca_{2},cb_{2}),\quad b_{1}=b_{3},\quad a_{3}=a_{1}-2c+2$ (6)

then, and only then, the zero set of the polynomial in (5) is a two-
dimensional set. See for example Figure 12, where we set the three points as
$(2.5,1.5),(5,3)$ and $(3.5,1.5).$

Figure 12: With the selected coordinates the three intervals
$\overline{EK},\overline{GI}$ and $\overline{FJ}$ are concurrent for any
position of $H.$

If all three conditions of (6) are satisfied then $(0,1),(0,2),(1,1)$ and
$(a_{1},b_{1}),(a_{2},b_{2}),(a_{3},b_{3})$ are similar triples relative to
the $x$-axis. Two common intersection points on the $x$-axis are easy to find
from the first two conditions, these are $x=0$ and $x=\infty$. The line of
$(0,2)$ and $(1,1)$ intersects at the point $(2,0).$ The equation of the line
through $(a_{2},b_{2}),(a_{3},b_{3})$ is

$Y-b_{2}=\frac{b_{2}-b_{3}}{a_{2}-a_{3}}(X-a_{2}).$

After substituting the values from (6) one can check that this line intersects
the $x$ axis at $x=2$ as well. For completeness we include the simple
calculation. Setting $Y=0$ and using the identities in (6) we have

$\displaystyle b_{2}(a_{3}-a_{2})$ $\displaystyle=(b_{2}-b_{3})(X-a_{2}),$
$\displaystyle b_{2}a_{3}-b_{3}a_{3}$ $\displaystyle=(b_{2}-b_{3})X,$
$\displaystyle b_{2}a_{3}-b_{1}a_{2}$ $\displaystyle=(b_{2}-b_{1})X,$
$\displaystyle b_{2}a_{3}-b_{2}a_{1}$ $\displaystyle=b_{2}(1-c)X,$
$\displaystyle a_{3}-a_{1}$ $\displaystyle=(1-c)X,$ $\displaystyle
a_{1}-2c+2-a_{1}$ $\displaystyle=(1-c)X,$ $\displaystyle 2$ $\displaystyle=X.$

By the assumptions of Lemma 17, $A$ doesn’t contain triples similar relative
to the line of $C,$ so the equation in (5) defines an algebraic curve. After
factoring out the $y=0$ line we left with a degree two polynomial in two
variables

$\displaystyle
x^{2}b_{2}(b_{3}-b_{2})+x\big{(}yb_{1}b_{2}-a_{3}b_{1}b_{2}(y-1)-2b_{1}b_{3}(y-1)-2b_{2}b_{3}+yb_{2}b_{3}+a_{1}b_{2}b_{3}(y-1)\big{)}$
$\displaystyle+\frac{b_{3}}{4}(a_{1}b_{2}-a_{2}b_{1})\big{(}(2y-3)^{2}-1\big{)}=0,$

which defines a (possibly degenerate) conic, so at least $c_{3}\delta^{12}N$
points of $B$ are on a conic.

The calculations in case of transformation $T_{2}$ goes in a similar way.
Referring to the notations we used for $T_{1},$ assuming $y\neq 1,2,$ now
$u=\frac{x}{1-2y},$ $t=\frac{x}{1-y},$ and $s=\frac{x-y}{1-y}.$ The polynomial
is given by

$\begin{vmatrix}b_{1}&a_{1}-u&b_{1}u\\\ b_{2}&a_{2}-t&b_{2}t\\\
b_{3}&a_{3}-s&b_{3}s\end{vmatrix}=0,$

which is equivalent to

$\begin{vmatrix}(1-2y)b_{1}&(1-2y)a_{1}-x&b_{1}x\\\
(1-y)b_{2}&(1-y)a_{2}-x&b_{2}x\\\
(1-y)b_{3}&(1-y)a_{3}-(x-y)&b_{3}(x-y)\end{vmatrix}=0.$ (7)

After dividing the terms of the polynomial by $y,$ it gives the quadratic
equation

$b_{1}(b_{3}-b_{2})x^{2}+Ex+(y-1)(2y-1)(a_{2}b_{1}-a_{1}b_{2})b_{3}=0,$ (8)

where the coefficient of the linear term is

$E=yb_{1}b_{2}+a_{3}b_{1}b_{2}(1-y)+b_{1}b_{3}-2yb_{1}b_{3}-a_{2}b_{1}b_{3}(1-y)-b_{2}b_{3}(1-y).$

As earlier, assuming that the constant term and the coefficient of the
quadratic term are both zero, i.e. $a_{2}b_{1}=a_{1}b_{2}$ and $b_{3}=b_{2},$
the coefficient of the linear term is

$E=(1-y)b_{1}b_{2}\left(a_{3}-a_{2}-\frac{a_{2}}{a_{1}}+1\right).$

Equation (8) defines a conic (or line(s)) unless the coordinates of the three
points satisfy all three identities

$a_{1}b_{2}=a_{2}b_{1},\quad b_{2}=b_{3},\quad
a_{3}=a_{2}+\frac{a_{2}}{a_{1}}-1.$ (9)

What is left is to check that the lines between $(1,1)$ and $(0,0.5)$ and
between $(a_{1},b_{1})$ and $(a_{3},b_{3})$ intersect on the $x$-axis. The
formal one intersects at $x=-1.$ The equation of the second line is

$Y-b_{1}=\frac{b_{3}-b_{1}}{a_{3}-a_{1}}(X-a_{1}).$

A simple calculation – similar to the one we performed in the $T_{1}$ case –
shows that this line also intersects the $x$-axis in the $x=-1$ point. Since
$A$ contains no two similar triples, equation (8) defines a conic or a line or
two lines. This completes the proof of Lemma 17, that at least
$c_{3}\delta^{12}N$ points of $B$ are on a conic. $\Box$

###  4.2 Few directions in a convex pointset

Let’s prove Theorem 15 first and then we prove a stronger statement.

P r o o f. [of Theorem 15]: The convex pointset can be separated into two sets
$A^{\prime}$ and $A^{\prime\prime}$ by a line $\ell$ such that out of the
$cn^{2}$ pointpairs at least $\frac{c^{2}}{2}n^{2}=c_{1}n^{2}$ have one point
in $A^{\prime}$ and the other one in $A^{\prime\prime}.$ Let’s apply a
projective transformation which moves the line of infinity to the real plane,
to a line $\ell^{\prime}$ parallel to $\ell,$ which keeps the points of $A$ in
convex position on the same halfplane determined by $\ell^{\prime}$. The set
$C$ is defined by the points of directions of the $c_{1}n^{2}$ pointpairs in
$A,$ one point in $A^{\prime}$ and the other in $A^{\prime\prime}.$ From the
conditions of the theorem we have $|C|\leq Dn.$ If, say, $A^{\prime\prime}$ is
closer to $\ell^{\prime}$ then applying Lemma 17 with $B:=A^{\prime\prime}$
and $A:=A^{\prime},$ shows that at least $c_{2}n$ points of $A^{\prime\prime}$
are on a conic, where $c_{2}>0$ depends on $c$ only. $\Box$

After choosing the separating line $\ell,$ we can choose the projective
transformation such that either $A^{\prime}$ or $A^{\prime\prime}$ are the
pointsets closer to $\ell^{\prime}.$ Because of that we know that both
$A^{\prime}$ and $A^{\prime\prime}$ contain many points from conics, however
we don’t know whether the two conics are the same or not. The following
theorem, which is one of our main results addresses this question.

###### Theorem 18

For any $D>0$ and $c>0$ there is a constant, $\delta>0$ and a threshold
$n_{0}=n_{0}(c,D)$ so the following holds. Let $A$ be a set of $n$ points in
the plane in convex position, and $E\subset A\times A$ is a set of pointpairs,
which determine at most $Dn$ distinct directions. If $|A|\geq n_{0}$ and
$|E|\geq cn^{2}$ then there is an $H\subset E$ such that $|H|\geq\delta n^{2}$
and the points of $H$ are on a conic.

P r o o f. We follow the previous proof first with the additional step that
before applying Lemma 17 we remove points from $A^{\prime\prime}$ (let’s
assume that $A^{\prime\prime}$ is closer to $\ell^{\prime}$) which contribute
in few directions with $A^{\prime}$ in $E$. The set $E^{\prime}\subset E$ is
defined as $E^{\prime}=E\cap A^{\prime}\times A^{\prime\prime}.$ By the
previous calculations $|E^{\prime}|\geq c_{1}n^{2}.$ We can consider
$E^{\prime}$ as the edge set of the bipartite graph
$G(A^{\prime},A^{\prime\prime}).$ Let’s remove the vertices from
$A^{\prime\prime}$ which have degree less than $\frac{c_{1}}{2}n.$ This
reduced set is denoted by $A^{\prime\prime\prime},$ and
$E^{\prime\prime}=E\cap A^{\prime}\times A^{\prime\prime\prime}.$ We apply
Lemma 17 with parameters $A:=A^{\prime},$ $B:=A^{\prime\prime\prime},$ and $C$
as the points of directions on $\ell^{\prime}$ (also denoted by $C$). Now we
have a set $A^{*}\subset A^{\prime\prime\prime},$ which is large, $|A^{*}|\geq
c_{3}n,$ its points are on a conic, $H_{1},$ and

$|E\cap A^{\prime}\times A^{*}|\geq\frac{c_{1}}{2}n|A^{*}|=c_{4}n^{2}$

for some constants $c_{3},c_{4}>0$ depending on $c$ and $D$ only. We keep the
points of $A^{\prime}$ and $A^{*},$ and move back $\ell^{\prime}$ to the
infinity and back on the ”other side“ so now $\ell^{\prime\prime}$ is closer
to $A".$ Let’s apply Lemma 17 again, now with $A:=A^{*},$ $B:=A^{\prime}$ and
$C$ is the set of direction points on the new $\ell^{\prime\prime}.$ It
follows that there is a $c_{5}>0$ such that there is a set of points,
$A^{**}\subset A^{\prime}$ which is on a conic, $H_{2},$ and $|E\cap
A^{*}\times A^{**}|\geq c_{5}n^{2}.$ Now we have two conics and a line
containing many collinear triples. To show that $H_{1}$ and $H_{2}$ are the
same conics, we use the following theorem which completes our proof.

######  Theorem 19 (Elekes-Szabó [15])

For every $c>0$ and positive integer $d$ there exist $\rho=\rho(c,d)$ and
$n_{0}=n_{0}(c,d)$ with the following property. Let
$\Gamma_{1},\Gamma_{2},\Gamma_{3}$ be (not necessarily distinct) irreducible
algebraic curves of degree at most $d$ in the plane $R^{2}.$ Assume that
$n>n_{0}$ and

  1. 1.

no two $\Gamma_{i}$ are identical straight lines;

  2. 2.

$H_{i}\subset\Gamma_{i}$ with $|H_{i}|\leq n\quad(i=1,2,3)$;

  3. 3.

The number of collinear triples $a,b,c$ with $a\in H_{1},b\in H_{2},c\in
H_{3}$ is at least $cn^{2}.$

Then $\Gamma_{1}\cup\Gamma_{2}\cup\Gamma_{3}$ is a cubic.

In the theorem it is required that the three curves, in our case $H_{1},H_{2}$
and $\ell^{\prime\prime},$ are irreducible. We can suppose that, because if
$H_{1}$ or $H_{2}$ contains a linear component, then by the result of Elekes
we mentioned earlier in the introduction of this section, we had three lines
with some $c^{*}n^{2}$ collinear triples proving Theorem 18 (Elekes’ result is
in [12]).

$\Box$

##  5 Open problems

Most of the related conjectures of Erdős and Elekes remain open. Here we list
a few questions where the tools we used in this paper might be useful.

  1. 1.

In the proofs we heavily used the fact that the pointsets had a natural
ordering. What happens if we consider arbitrary sets in the plane? Do the
statements of Theorem 6 and 13 still hold?

  2. 2.

If the $cn^{2}$ collinear triples among $n$ points are 3-term arithmetic
progressions, i.e. when in the $(a,b,c)$ triples $b$ is the halving point of
the $(a,c)$ segment, one can use standard tools from additive combinatorics to
find an arithmetic structure among the points. In particular, there are many
collinear points in the set. It is expected that with the right choice of
parameter $\varepsilon,$ if in all the $cn^{2}$ $(a,b,c)$ triples $b=\lambda
a+(1-\lambda)c$ where $1/2-\varepsilon\leq\lambda\leq 1/2+\varepsilon$ then
many points are collinear.

  3. 3.

Sets with few directions were investigated extensively in affine Galois planes
([4, 29, 37, 38, 3]). Under what conditions can we conclude that Conjecture 14
holds in planes over finite fields?

  4. 4.

Scott’s problem on the minimum number of directions was solved in 3-space by
Pach, Pinchasi, and Sharir in [28]. What are the structural results one can
guarantee if the number of directions determined by two sets in space is very
small?

  5. 5.

Let us suppose that four mutually avoiding $n$-elements pointsets $A,B,C$ and
$D$ have $cn^{2}$ collinear four-tuples $(a,b,c,d)$ where $a\in A,b\in B,c\in
C$ and $d\in D.$ Can we conclude that then at least 5 points are collinear in
$A$? (or in any other set). This problem is closely related to a question of
Erdős [16]; is it true that if $n$ points contain $cn^{2}$ collinear 4-tuples,
then it should contain 5 collinear points? For some lower bounds, and related
results see [34].

  6. 6.

Given an $n^{2}$-element pointset such that there is a point in every unit
square of an $n\times n$ integer grid. Prove that if the number of collinear
triples is $cn^{2},$ then many points are collinear, provided $n$ is large
enough.

  7. 7.

Are there better bounds for the Brown-Erdős-Sós conjecture for collinear
triples than what we had in Theorem 13? Maybe – similar to the case with
triples from finite groups – there is a constant, $c>0,$ such that the
following holds. For any $k\in\mathbb{N}$ and $\delta>0$ there is a threshold,
$n_{0}=n_{0}(k,\delta)$ such that if $n\geq n_{0}$ and there are at least
$\delta n^{2}$ collinear triples among $n$ points then there is a $(k,ck^{2})$
configuration among the triples.

##  6 Acknowledgments

The research of J.S. was supported in part by an NSERC Discovery grant and
OTKA K 119528 grant. The author is thankful to Lior Gishboliner for pointing
out the crucial reference [19].

## References

  * [1] M. Aigner, G.M. Ziegler, Proofs from THE BOOK, Springer-Verlag Berlin Heidelberg 2014
  * [2] B. Aronov, P. Erdős, W. Goddard, D. Kleitman, M. Klugerman, J. Pach, L. Schulman, Crossing families, Combinatorica 14 (1994), 127–134.
  * [3] Daniel Di Benedetto, Jozsef Solymosi, Ethan P. White, On the directions determined by a Cartesian product in an affine Galois plane, Combinatorica, to appear, (2022)
  * [4] A. Blokhuis, S. Ball, A. E. Brouwer, L. Storme, T. Szőnyi, On the slopes of the graph of a function defined on a finite field, _J. Combin. Theory_ , Ser. A 86 (1999), no. 1, 187-196.
  * [5] Borwein, P., Moser, W.O.J. A survey of Sylvester’s problem and its generalizations. Aeq. Math. 40, 111–135 (1990).
  * [6] Peter Brass, William O. J. Moser, János Pach, Research Problems in Discrete Geometry, Springer–Verlag, 2004.
  * [7] W. G. Brown, P. Erdős, and V. T. Sós.  On the existence of triangulated spheres in $3$-graphs, and related problems.  Period. Math. Hungar., 3(3-4):221–228, 1973.
  * [8] Boaz Barak, Zeev Dvir, Avi Wigderson, and Amir Yehudayoff. Fractional Sylvester-Gallai theorems. Proceedings of the National Academy of Sciences, 2012.
  * [9] D. Conlon, L. Gishboliner, Y. Levanzov and A. Shapira, A New Bound for the Brown-Erdős-Sós Problem, arXiv:1912.08834 [math.CO] (2019)
  * [10] Zeev Dvir, Shubhangi Saraf, and Avi Wigderson. Improved rank bounds for design matrices and a new proof of Kelly’s theorem. Forum of Mathematics, Sigma, 2:24, 2014.
  * [11] Zeev Dvir, Ankit Garg, Rafael Oliveira, and Jozsef Solymosi, Rank bounds for design matrices with block entries and geometric applications, Discrete Analysis 2018:5, 24 pp.
  * [12] György Elekes, On linear combinatorics I, Combinatorica, 17(4) (1997), 447–458.
  * [13] György Elekes. SUMS versus PRODUCTS in number theory, algebra and Erdős geometry. In Paul Erdős and His Mathematics, II. Edited by G. Halász, L. Lovász, M. Simonovits, and V. T. Sós. Vol 11. Bolyai Society Mathematical Studies, Berlin, Germany: Springer-Verlag, 2002, pp. 241–290.
  * [14] György Elekes. On linear combinatorics III. Combinatorica, 19 (1):43–53, 1999.
  * [15] Elekes, Gy., Szabó, E. On Triple Lines and Cubic Curves – the Orchard Problem revisited, arXiv:1302.5777 [math.CO] (2014).
  * [16] Erdős, P. On some problems of elementary and combinatorial geometry. Annali di Matematica 103, 99–108 (1975).
  * [17] Z. Füredi and M. Ruszinkó, Uniform hypergraphs containing no grids, Advances in Mathematics, Volume 240, 2013, 302–324.
  * [18] Fox, Jacob , A new proof of the graph removal lemma, Annals of Mathematics, Second Series, 174 (1): 561–579 (2011).
  * [19] Lior Gishboliner and Asaf Shapira, Constructing dense grid-free linear 3-graphs, Proc. Amer. Math. Soc. 150 (2022), 69–74
  * [20] Green, B., Tao, T. On Sets Defining Few Ordinary Lines. Discrete Comput Geom 50, 409–468 (2013).
  * [21] Goodman, J. E. and Pollack, R. A Combinatorial Perspective on some Problems in Geometry. Congressus Num. 32 (Proc. XIIth S.E. Conf.), 1981, pp. 383–394.
  * [22] Jamison, R.E. Planar configurations which determine few slopes. Geom Dedicata 16, 17–34 (1984).
  * [23] T. Kővári, V. Sós, P. Turán, Colloquium Mathematicum 3 (1954), 50–57.
  * [24] Long, J. (2020). A note on the Brown–Erdős–Sós conjecture in groups. Combinatorics, Probability and Computing, 29(4), 633–640.
  * [25] Mozhgan Mirzaei and Andrew Suk, A positive fraction mutually avoiding sets theorem. Discrete Math. 343, 3 (Mar 2020).
  * [26] Nnadov, R., Sudakov, B., and Tyomkyn, M. (2020). Proof of the Brown–Erdős–Sós conjecture in groups. Mathematical Proceedings of the Cambridge Philosophical Society, 169(2), 323–333.
  * [27] J. Pach, N. Rubin, G. Tardos, Planar point sets determine many pairwise crossing segments. STOC 2019: 1158–1166.
  * [28] Pach, J., Pinchasi, R. and Sharir, M. Solution of Scott’s Problem on the Number of Directions Determined by a Point Set in 3-Space. Discrete Comput Geom 38, 399–441 (2007).
  * [29] L. Rédei, “Lückenhafte Polynome über endlichen Körperrn,” Birkhäuser, Basel, 1970 (Engl. trans. Lacunary Polynomials over Finite Fields, North Holland, Amsterdam, 1973).
  * [30] Rosta, Vera, Note on Gy. Elekes’s conjectures concerning unavoidable patterns in proper colorings, The Electronic Journal of Combinatorics [electronic only] 7.1 (2000): Research paper N3, 3 p.
  * [31] I. Z. Ruzsa and E. Szemerédi.  Triple systems with no six points carrying three triangles.  In Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, volume 18 of Colloq. Math. Soc. János Bolyai, pages 939–945. North-Holland, Amsterdam-New York, 1978.
  * [32] Jozsef Solymosi, Dense Arrangements are Locally Very Dense. I. SIAM J. Discrete Math. 20, 3 (2006), 623–627.
  * [33] J. Solymosi.  The $(7,4)$-conjecture in finite groups.  Combin. Probab. Comput., 24(4):680–686, 2015.
  * [34] David Solymosi, Jozsef Solymosi, Small cores in 3-uniform hypergraphs, Journal of Combinatorial Theory, Series B, Volume 122, 2017, 897–910.
  * [35] Solymosi, J., Stojaković, M. Many Collinear $k$-Tuples with no $k+1$ Collinear Points. Discrete Comput Geom 50, 811–820 (2013).
  * [36] Jozsef Solymosi, Ching Wong, The Brown–Erdős–Sós conjecture in finite abelian groups, Discrete Applied Mathematics, Volume 276, 2020, 155–160,
  * [37] T. Szőnyi, On the Number of Directions Determined by a Set of Points in an Affine Galois Place, _J. Combin. Theory_ , Ser. A 74 (1996), no. 1, 141-146.
  * [38] T. Szőnyi, Around Rédei’s theorem, _Discrete Math._ , 208/209 (1999), 557-575.
  * [39] P. Ungar, $2N$ noncollinear points determine at least $2N$ directions, J. Combinatorial Theory, Ser. A 33 (1982), 343–347.
  * [40] P. Valtr, On mutually avoiding sets, The Mathematics of Paul Erdős II. Springer Berlin Heidelberg, 1997. 324–328.
  * [41] Ching Wong, On the existence of dense substructures in finite groups, Discrete Mathematics, Volume 343, Issue 10, 2020,
  * [42] Problem Collection of the DIMANET Mátraháza Workshop, 22–28 October 1995. (1999). Combinatorics, Probability and Computing, 8(1–2), 185–192.