The Constant of Proportionality in Lower Bound Constructions of Point-Line Incidences

Abstract

Let $I(n,l)$ denote the maximum possible number of incidences between $n$ points and $l$ lines. It is well known that $I(n,l)=\Theta (n^{2/3}{l}^{2/3}+n+l)$. Let $c_{\mathrm{SzTr}}$ denote the lower bound on the constant of proportionality of the $n^{2/3}{l}^{2/3}$ term. The known lower bound, due to Elekes, is $c_{\mathrm{SzTr}}\ge 2^{-2/3}=0.63$. With a slight modification of Elekes' construction, we show that it can give a better lower bound of $c_{\mathrm{SzTr}}\ge 1$, i.e., $I(n,l)\ge n^{2/3}{l}^{2/3}$. Furthermore, we analyze a different construction given by Erd{\H o}s, and show its constant of proportionality to be even better, $c_{\mathrm{SzTr}}\ge 3/(2^{1/3}{\pi }^{2/3})\approx 1.11$.