On the Existence of Ordinary Triangles
Radoslav Fulek Hossein Nassajian Mojarrad Márton Naszódi József Solymosi Sebastian U. Stich May Szedlák


Let P be a finite point set in the plane.
A c-ordinary triangle in P is a subset of P consisting of three 
non-collinear points such that each of the three lines determined by the three 
points contains at most c points of P.
Motivated by a question of Erdős, and answering a question of de Zeeuw, we 
prove that there exists a constant c>0 such that  P contains a c-ordinary 
triangle, provided that P is not contained in the union of two lines. 
Furthermore, the number of c-ordinary triangles in P is Ω(|P|).

[NO \title GIVEN]
    [NO \author GIVEN]
    December 30, 2023
======================



§ INTRODUCTION


In 1893, Sylvester <cit.> asked whether, for any finite set of 
non-collinear points on the Euclidean plane, there exists a line incident 
with exactly two points.
The positive answer to this question, now known as the Sylvester–Gallai 
theorem, was first obtained almost half a century later in 1941 by 
Melchior <cit.> as a consequence of the positive answer to an analogous 
question in the projective dual.
Erdős <cit.>, unaware of these developments, posed the same 
problem in 1943, and it was solved by Gallai in 1944.
For more on the history of this and related problems, see <cit.>.

Given a finite set of points P on the Euclidean plane, a line ℓ⊂^2 is determined by P if ℓ contains at least two 
points of P. We say that ℓ is an ordinary line, if ℓ 
contains exactly two points of P.
























Erdős <cit.> considered the problem of finding an ordinary triangle, 
that is, three ordinary lines determined by three points of a finite planar 
point set. See <cit.> for details on the origin of this problem.
Motivated by this problem, and with an application in studying 
ordinary conics <cit.>, de Zeeuw asked a related question at the 13th 
Gremo's Workshop on Open Problems (GWOP 2015, Feldis, Switzerland), which we 
describe below.


Let c be a natural number and  let P be a point set in the plane. 
A c-ordinary triangle in P is 
a subset of P consisting of three non-collinear points such that each of the 
three lines determined by the three points contains at most c points of P.


It is easy to see that in order to be able to find a c-ordinary triangle 
for large n, we have to assume that P is not contained in the union of two 
lines.
Under this restriction one might suspect that there is a 2-ordinary triangle in 
P. However, this is not true as shown by Böröczky's 
construction <cit.>.
The following simple example also shows this. Let P_1 be a set of points 
that are not all collinear and let ℓ be some line. For each line ℓ_1 
determined by the point set P_1, we add the point at the intersection of 
ℓ and ℓ_1. Let us denote this new set of points by P_2. All points 
of P_2 are collinear, hence a 2-ordinary triangle must contain two points from 
P_1. However, by construction every line determined by P_1 contains a point 
of P_2. Hence there are no 2-ordinary triangles in this point set. 

De Zeeuw asked whether a c-ordinary triangle can be found in P. 
The aim of this manuscript is to give a positive answer to this question.

There is a natural number c such that the following holds. Assume P is a 
finite set of points on the Euclidean plane not contained in the union of two 
lines. Then P contains a c-ordinary triangle, that is three non-collinear 
points such that each of the three lines determined by these three points 
contains at most c points of P.  Moreover, the number of c-ordinary 
triangles in P is Ω(|P|).



The constant in the theorem above can be chosen as c=12000.

We see no reason to believe that this is the best constant.
Moreover, it remains open if the number of  c-ordinary 
triangles in P is superlinear (possibly even quadratic) in |P|.




§ TOOLS

To prove Theorem <ref>, we need the following lemmas. The first one is a 
corollary of the Szemerédi-Trotter Theorem. 

<cit.>
Let k,n ≥ 2 be natural numbers, P a set of n points in the plane, and 
let f(k) denote the number of lines in the plane containing at least k 
points of P. Then 

    f(k)≤
    c' n^2/k^3,  k ≤√(n),
    
    c' n/k,  k > √(n)

for a universal constant c'>0.
In fact, we may take c' = 125.



Clearly, the claimed bound holds for k=2,3, since f(2)≤n2 
and f(3)≤n2/32. To prove the statement for k > 
3, we rely on the following result by Pach, Radoičić, Tardos and 
Tóth <cit.>: for any given n points and m lines on 
the Euclidean plane, the number of incidences between them is at most 
2.5m^2/3 n^2/3 + m + n. Let m=f(k) denote the number of lines 
containing at least k points of P. Observe that the number of point-line 
incidences are thus at least mk. Hence, mk ≤ 2.5m^2/3 n^2/3 + 
m + n.

First, consider the case m ≥ n. Observe that for k>3, we have mk/2 ≤ 
m(k-2) ≤ 2.5m^2/3 n^2/3.


It follows that m ≤ 125 n^2/k^3, and specifically, m ≤ 125 
n/k if k > √(n).

Next, consider the case m < n. We have mk ≤ 2.5m^2/3 n^2/3 + m + n 
≤ 2.5m^2/3 n^2/3 +  2.5 n, and therefore mk ≤max{5 m^2/3 
n^2/3,5n}. Hence, m ≤max{ 125 n^2/k^3, 5n/k}. For 
k ≤ 5√(n), the maximum is attained at the first term, whereas for k > 
√(n), we trivially have n^2/k^3 < n/k,
establishing the claim for c'=125.


The following Turán–type lemma (related to Mantel's theorem) from extremal 
graph theory provides a lower bound for the number of triangles (subgraphs 
isomorphic to K_3) in a graph.  It can be found with a proof as Problem 10.33 
in <cit.>.

Consider a graph G=(V(G), E(G)) with |V(G)|=n and |E(G)|=m. Let 
t_3(G) denote the number of triangles in G. Then we have

    t_3(G) ≥m/3n(4m-n^2).
















§ PROOF OF THEOREM <REF>


In this section, we prove Theorem <ref>. 
Our proof is closely related to the standard proof of Beck's Theorem, where the 
number of pairs of points on medium-rich lines is bounded using the 
Szemerédi-Trotter theorem, and then it is concluded that either there is a 
very rich line, or there are many pairs of points on poor lines, see the proof 
of Theorem 18.8 in <cit.>.

The constant c will be chosen at the end of the proof. Assume P is a set of 
n ≥ c points in the plane and let ℒ={L_1,L_2,…,L_m} 
denote the set of lines determined by P. Define l_i=|L_i ∩ P|, for  
i=1,2,…,m. 
 Set α=4/c+1. We split the proof into two 
cases:


  (i) There is a line L_i ∈ℒ such that l_i > α n;

  (ii) For all i=1,2,…,m we have l_i ≤α n.
 

Consider the first case. Since the point set P∖ L_i is non-collinear 
by the assumption, by applying the Sylvester-Gallai theorem, we can 
find an 
ordinary line L ∈ℒ for P∖ L_i, i.e. L contains 
exactly two points q,r ∈ P∖ L_i. Note that L may contain at most 
one point of P ∩ L_i. Next, we show that there are many points on L_i 
which 
together with q,r form c-ordinary triangles. For this, we define the set 
P_q ⊂ P as

    P_q={ p ∈ L_i∩ P : |pq∩ P| > c},

where pq denotes the line passing through p,q. We define P_r 
in 
a similar way. Note that for any point p∈ P_q, the line pq 
contains at least c-1 points of P∖ ( L_i∪{q}), moreover, these 
sets of c-1 points are disjoint for different p∈ P_q. So we 
get

    (c-1)· |P_q| ≤ n-l_i,

which implies that

    |P_q| ≤n-l_i/c-1 < 
    l_i/α-l_i/c-1=(c+1)/4-1/c-1· l_i<l_i/4.

Similarly, |P_r| < l_i/4. So there are at 
least l_i/2 points 
s∈ P∩ L_i such that s ∉ P_q∪ P_r. Furthermore, s,q,r are 
non-collinear. This implies that the lines sq,sr 
contain 
at most c points of P. Therefore every triangle determined by s,q,r, 
where s ∉ P_q∪ P_r, is a 
c-ordinary triangle for P. 
The number of these triangles is at least
l_i/2>α n/2=2n/c+1, 
completing the proof of case (i). Note that, so far, c may be chosen as any 
integer greater than 2.

Next, we consider case (ii). So we assume that no line of ℒ 
contains more than α n points of P. First we bound ∑_c < l_i ≤α nl_i2 from above. With the notation of Lemma <ref>, we 
have


    ∑_i : c < l_i ≤√(n)l_i2   ≤∑_j=⌊log (c+1)⌋^⌈log√(n)⌉   ∑_i: 2^j ≤ l_i ≤ 2^j+1l_i2≤∑_j=⌊log (c+1)⌋^⌈log√(n)⌉ f(2^j) 2^j+12
       *≤∑_j=⌊log (c+1)⌋^⌈log√(n)⌉ c' n^2/2^3j2^j+12≤∑_j=⌊log (c+1)⌋^⌈log√(n)⌉ c' 
    n^2/2^j-1
       ≤∑_j=⌊log (c+1)⌋^∞ c' n^2/2^j-1≤8c'n^2/c+1,

where logarithms are base 2, and the inequality with star follows 
from Lemma <ref>. 

On the other hand, by the same lemma, we have

    ∑_i : √(n) < l_i ≤α nl_i2   ≤∑_j=0^⌈log(α√(n))⌉-1∑_2^j√(n) < l_i ≤ 
    2^j+1√(n)l_i2≤∑_j=0^⌈log(α√(n))⌉-1 f(2^j√(n)) 
    2^j+1√(n)2
       *≤∑_j=0^⌈log(α√(n))⌉-1 c' 
    n/2^j√(n)2^j+1√(n)2
       ≤∑_j=0^⌈log(α√(n))⌉-1 c'n^3/2 2^j+1≤ 4c'n^3/2·α√(n)=16c'n^2/c+1.


As a result, we obtain

    ∑_i : c < l_i ≤α nl_i2= ∑_i : c < l_i ≤√(n)l_i2+∑_i : √(n) < l_i ≤α nl_i2≤24c'n^2/c+1.



Let G be the graph with vertex set V(G)=P, such that two points p,p' 
∈ P are adjacent in G if the line pp' spanned by p,p' 
satisfies |pp'∩ P| ≤ c.

By the following identity

    ∑_i : 2 ≤ l_i ≤α nl_i2=n2,

we obtain for the number of edges of G, 

    |E(G)| =∑_i : 2 ≤ l_i ≤ cl_i2≥n2- 
    24c'n^2/c+1.


Now we choose c large enough such that 

    4(n2-  24c'n^2/c+1)-n^2=Ω(n^2).
 Combining 
it with (<ref>) yields 
    4|E(G)|-n^2=4(∑_i: 2 ≤ l_i ≤ cl_i2)-n^2=Ω(n^2).
 Therefore, by Lemma <ref> we have 

    t_3(G) ≥|E(G)|/3n(4|E(G)|-n^2)=Ω(n^2)/n·Ω(n^2)=Ω(n^3).

This implies that G has Ω(n^3) triangles. Let T be the set of those 
triangles in G whose three vertices are non-collinear. It is easy to see that these 
triangles correspond to c-ordinary triangles in P. 

Note that the number of triangles with collinear vertices is at most

    ∑_i : 2 ≤ l_i ≤ cl_i3≤∑_i : 2 ≤ l_i ≤ 
    cc3≤n2·c3=O(n^2).

So we get
 
    |T|=Ω(n^3)-O(n^2)=Ω(n^3).

As a result, P has Ω(n^3) c-ordinary 
triangles, provided that c satisfies (<ref>). 


Equation (<ref>) yields that we may choose c = 96 c', where 
c' is from Lemma <ref>.




§ ACKNOWLEDGEMENTS

We thank Emo Welzl for providing the venue, his GWOP workshop, where our 
research initially started. We also thank Frank de Zeeuw for his many remarks 
on earlier versions of the manuscript.
We are grateful to both referees, whose comments made the presentation much 
cleaner. 

R. Fulek was partially supported by the People Programme (Marie Curie Actions) 
of the European Union's Seventh Framework Programme (FP7/2007-2013) under REA 
grant agreement no [291734].
H. N. Mojarrad and M. Naszódi were members of János Pach's Chair of DCG 
at EPFL, Lausanne, supported by the Swiss National Science 
Foundation (SNSF) Grants 200020-162884 and 200021-165977.
M. Naszódi was also partially supported by the National Research, 
Development and Innovation Office grant K119670, and by the 
János Bolyai Research Scholarship of the Hungarian 
Academy of Sciences.
J. Solymosi was supported by NSERC, by ERC Advanced Research Grant no 267165 
(DISCONV) and by the National Research, Development and Innovation Office 
(NKFIH) grant NK 104183.
S. U. Stich acknowledges support from SNSF and grant “ARC 14/19-060” from the 
“Direction de la recherche scientifique - Communauté française de 
Belgique”. M. Szedlák's research was supported by the SNSF Project 
200021_150055/1.


amsalpha
 
