find this polynomial by interpolation. The starting observation is that the degree $r-2$ Veronese embedding takes $r$-collinear points to $r$ linearly dependent images. Hence, each collinear $r$-tuple of points, gives us a dependent $r$-tuple of images. We then use the design-matrix method of [@BDWY12] to convert these ‘local’ linear dependencies into a global one, showing that all the images lie in a hyperplane. This then translates into a low degree polynomial vanishing on the original set.
author:
- 'Zeev Dvir[^1]'
- 'Sivakanth Gopi[^2]'
bibliography:
- 'richlines.bib'
title: On the number of rich lines in truly high dimensional sets
---

Introduction
============

The Szemerédi-Trotter theorem gives a tight upper bound on the number of incidences between a collection of points and lines in the real plane. We write $A\lesssim B$ to denote $A\le C\cdot B$ for some absolute constant $C$ and $A \approx B$ if we have both $A \lesssim B$ and $B \lesssim A$.

\[thm-Szemeredi-Trotter\] Given a set of points $V$ and a set of lines $\L$ in $\R^2$, let $I(V,\L)$ be the set of incidences between $V$ and $\L$. Then, $$I(V,\L)\lesssim |V|^{2/3}|\L|^{2/3}+|V|+|\L|.$$

This fundamental theorem has found many applications in various areas (see [@Dvir-survey] for some examples) and is 