\documentclass[12pt]{article} \usepackage{e-jc} \usepackage{latexsym,color,graphicx,amsmath,amssymb,caption} \usepackage{enumerate} \usepackage{lineno} \usepackage{dsfont} %\setlength{\textwidth}{6.0in} \setlength{\evensidemargin}{0.25in} %\setlength{\oddsidemargin}{0.25in} \setlength{\textheight}{9.0in} %\setlength{\topmargin}{-0.5in} \setlength{\parskip}{2mm} %\setlength{\baselineskip}{1.7\baselineskip} % \def\reals{{\mathbb R}} % \def\eps{{\varepsilon}} % \def\bd{{\partial}} % \def\marrow{\marginpar[\hfill$\longrightarrow$]{$\longleftarrow$}} % \def\micha#1{\textsc{(Micha says: }\marrow\textsf{#1})} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \def\R{{\mathbb R}} \newcommand{\RR}{\ensuremath{\mathbb R}} \def\sph{{\mathbb S}} \def\eps{{\varepsilon}} \def\bfxi{{\bf \xi}} \def\bfeta{{\bf \eta}} \def\bd{{\partial}} \def\dd{{d}} \def\A{{\cal A}} \def\C{{\mathcal C}} \def\D{{\cal D}} \def\E{{\cal E}} \def\F{{\cal F}} %\def\H{{\cal H}} \def\L{{\cal L}} \def\N{{\mathbb N}} \def\P{{\cal P}} \def\DD{\D_{B,A}} \DeclareMathOperator{\VD}{{\cal V}} \newcommand{\scalprod}[2]{\left\langle #1,#2 \right\rangle} \def\marrow{\marginpar[\hfill$\longrightarrow$]{$\longleftarrow$}} \def\micha#1{\textsc{(Micha says: }\marrow\textsf{#1})} \def\noam#1{\textsc{(Noam says: }\marrow\textsf{#1})} \pagestyle{plain} \begin{document} \def\reals{{\mathbb R}} \def\cplx{{\mathbb C}} \def\deg{{\mathsf{deg}}} \newcommand{\pts}{\mathcal P} \newcommand{\vrts}{\mathcal V} \newcommand{\curves}{\mathcal C} \newcommand{\lines}{\mathcal L} \newcommand{\motions}{\mathcal M} \newcommand{\planes}{\Pi} \newcommand{\flats}{\mathcal F} \newcommand{\DS}{\ensuremath{\mathbb S}} \newcommand{\dist}[1] {{\,{\mathrm{D}_3}\!\left(#1\right)}} \newcommand{\res}{\text{Res}} \newcommand{\Deg}{D} % degree \makeatletter \newcommand{\ProofEndBox}{{\ifhmode\unskip\nobreak\hfil\penalty50 \else \leavevmode\fi\quad\vadjust{}\nobreak\hfill$\Box$ \finalhyphendemerits=0 \par}} \makeatother \newcommand{\proofend}{\ProofEndBox\smallskip} % \title{Incidences with curves in $\RR^d$ \thanks{% Work on this paper was partially supported by Grant 2012/229 from the U.S.-Israel Binational Science Foundation, by Grant 892/13 from the Israel Science Foundation, by the Israeli Centers for Research Excellence (I-CORE) program (center no.~4/11), and by the Hermann Minkowski--MINERVA Center for Geometry at Tel Aviv University. % Part of this research was performed while the authors were visiting the Institute for Pure and Applied Mathematics (IPAM) at UCLA, which is supported by the National Science Foundation. A preliminary version of this paper appeared in {\it Proc. European Sympos. Algorithms}, 2015, pages 977--988.} } \author{ Micha Sharir\thanks{% Blavatnik School of Computer Science, Tel Aviv University, Tel~Aviv, Israel; \tt{michas@post.tau.ac.il} } \and Adam Sheffer\thanks{% Dept.~of Mathematics, California Institute of Technology, Pasadena, CA, USA; \tt{adamsh@gmail.com} } \and Noam Solomon\thanks{% Blavatnik School of Computer Science, Tel Aviv University, Tel~Aviv, Israel; \hfill \tt{noamsolomon@post.tau.ac.il} } } % \maketitle %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{abstract} We prove that the number of incidences between $m$ points and $n$ bounded-degree curves with $k$ degrees of freedom in $\RR^d$ is \[ O\left(m^{\frac{k}{dk-d+1}+\eps}n^{\frac{dk-d}{dk-d+1}}+ \sum_{j=2}^{d-1} m^{\frac{k}{jk-j+1}+\eps}n^{\frac{d(j-1)(k-1)}{(d-1)(jk-j+1)}} q_j^{\frac{(d-j)(k-1)}{(d-1)(jk-j+1)}}+m+n\right), \] % \[ I(\pts,\curves) =O\left(m^{\frac{k}{dk-d+1} +\eps}n^{\frac{dk-d}{dk-d+1}} + m^{\frac{k}{2k-1}+\eps}n^{\frac{dk-d}{(d-1)(2k-1)}}q^{\frac{(k-1)(d-2)}{(d-1)(2k-1)}}+m+n\right),\] for any $\eps>0$, where the constant of proportionality depends on $k, \eps$ and $d$, provided that no $j$-dimensional surface of degree $\le c_j(k,d,\eps)$, a constant parameter depending on $k$, $d$, $j$, and $\eps$, contains more than $q_j$ input curves, and that the $q_j$'s satisfy certain mild conditions. This bound % \noam{notice that this is not completely true, because of % the conditions on $q$ and $s$ but for the sake of selling perhaps it % is fine, but perhaps also do the same with Guth's result} generalizes the well-known planar incidence bound of Pach and Sharir to $\RR^d$. It generalizes a recent result of Sharir and Solomon~\cite{SS14} concerning point-line incidences in four dimensions (where $d=4$ and $k=2$), and partly generalizes a recent result of Guth~\cite{Gu14} (as well as the earlier bound of Guth and Katz~\cite{GK2}) in three dimensions (Guth's three-dimensional bound has a better dependency on $q_2$). It also improves a recent $d$-dimensional general incidence bound by Fox, Pach, Sheffer, Suk, and Zahl~\cite{FPSSZ14}, in the special case of incidences with algebraic curves. Our results are also related to recent works by Dvir and Gopi~\cite{DG15} and by Hablicsek and Scherr~\cite{HS14} concerning rich lines in high-dimensional spaces. Our bound is not known to be tight in most cases. \end{abstract} %\graphicspath{{./graphics/}}%helpful if your graphic files are in another directory \bibliographystyle{plain}% the recommended bibstyle % Author macros::begin %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} Let $\C$ be a set of curves in $\RR^d$. We say that $\C$ has $k$ \emph{degrees of freedom} with \emph{multiplicity} $s$ if (i) for every $k$ points in $\RR^d$ there are at most $s$ curves of $\cal C$ that are incident to all $k$ points, and (ii) every pair of curves of $\cal C$ intersect in at most $s$ points. The bounds that we derive depend more significantly on $k$ than on $s$---see below. In this paper we derive general upper bounds on the number of incidences between a set $\pts$ of $m$ points and a set $\C$ of $n$ bounded-degree algebraic curves that have $k$ degrees of freedom (with some constant multiplicity $s$). We denote the number of these incidences by $I(\pts,\C)$. Before stating our results, let us put them in context. The basic and most studied case involves incidences between points and lines. In two dimensions, writing $L$ for the given set of $n$ lines, the classical Szemer\'edi--Trotter theorem~\cite{SzT} yields the worst-case tight bound %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{equation} \label{inc2} I(\pts,L) = O\left(m^{2/3}n^{2/3} + m + n \right) . \end{equation} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In three dimensions, in the 2010 groundbreaking paper of Guth and Katz~\cite{GK2}, an improved bound has been derived for $I(\pts,L)$, for a set $\pts$ of $m$ points and a set $L$ of $n$ lines in $\reals^3$, provided that not too many lines of $L$ lie in a common plane. Specifically, they showed: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{theorem}[Guth and Katz~\cite{GK2}] \label {ttt} Let $\pts$ be a set of $m$ distinct points and $L$ a set of $n$ distinct lines in $\reals^3$, and let $q_2\le n$ be a parameter, such that no plane contains more than $q_2$ lines of $L$. Then $$ I(P,L) = O\left(m^{1/2}n^{3/4} + m^{2/3}n^{1/3}q_2^{1/3} + m + n\right). $$ \end{theorem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% This bound was a major step in the derivation of the main result of \cite{GK2}, an almost-linear lower bound on the number of distinct distances determined by any set of $n$ points in the plane, a classical problem posed by Erd{\H o}s in 1946~\cite{Er46}. Their proof uses several nontrivial tools from algebraic and differential geometry. This machinery comes on top of the main innovation of Guth and Katz, the introduction of the \emph{polynomial partitioning technique}; see below. In four dimensions, Sharir and Solomon~\cite{SS4d} have obtained the following sharp point-line incidence bound: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{theorem}[Sharir and Solomon~\cite{SS4d}] \label{th:ss4d} Let $\pts$ be a set of $m$ distinct points and $L$ a set of $n$ distinct lines in $\reals^4$, and let $q_2,q_3\le n$ be parameters, such that (i) no hyperplane or quadric contains more than $q_3$ lines of $L$, and (ii) no 2-flat contains more than $q_2$ lines of $L$. Then \begin {equation} \label {ma:in0} I(\pts,L) \le 2^{c\sqrt{\log m}} \left( m^{2/5}n^{4/5} + m \right) + A\left( m^{1/2}n^{1/2}q_3^{1/4} + m^{2/3}n^{1/3}q_2^{1/3} + n\right) , \end {equation} where $A$ and $c$ are suitable absolute constants. When $m\le n^{6/7}$ or $m\ge n^{5/3}$, we get the sharper bound \begin {equation} \label {ma:in0x} I(\pts,L) \le A \left( m^{2/5}n^{4/5} + m + m^{1/2}n^{1/2}q_3^{1/4} + m^{2/3}n^{1/3}q_2^{1/3} + n\right) . \end {equation} In general, except for the factor $2^{c\sqrt{\log m}}$, the bound is tight in the worst case, for any values of $m,n$, with corresponding suitable ranges of $q_2$ and $q_3$. \end{theorem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% This improves, in several aspects, an earlier treatment of this problem in Sharir and Solomon~\cite{SS14}. Another way to extend the Szemer\'edi--Trotter bound is for curves in the plane with $k$ degrees of freedom (for lines, $k=2$). This has been done by Pach and Sharir, who showed:\footnote{% Their result holds for more general families of curves, not necessarily algebraic, but, since algebraicity will be assumed in higher dimensions, we assume it also in the plane.} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{theorem}[Pach and Sharir \cite{PS98}] \label{th:PS} Let $\pts$ be a set of $m$ points in $\RR^2$ and let $\C$ be a set of bounded-degree algebraic curves in $\RR^2$ with $k$ degrees of freedom and with multiplicity $s$. Then $$ I(\pts,\C) = O\left(m^{\frac{k}{2k-1}}n^{\frac{2k-2}{2k-1}}+m+n\right) , $$ where the constant of proportionality depends on $k$ and $s$. \end{theorem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Several special cases of this result, such as the cases of unit circles and of arbitrary circles, have been considered separately~\cite{CEGSW,SST}. Unlike the Szemer\'edi-Trotter result (which arises as a special case of Theorem~\ref{th:PS} with $k=2$), the bound in Theorem~\ref{th:PS} is not known to be tight for any $k\ge 3$. In fact, it is known not to be tight for the case of arbitrary circles; see~\cite{ANP+}. Here too one can consider the extension of these bounds to higher dimensions. Excluding this paper, the following theorem states the current best bound for this case % \begin{theorem}[Fox et al.~\cite{FPSSZ14}] \label{th:IncFox} Let $\pts$ be a set of $m$ points and let $\vrts$ be a set of $n$ constant-degree algebraic varieties, both in $\RR^d$, such that the incidence graph of $\pts\times\vrts$ does not contain a copy of $K_{s,t}$ (here we think of $s,t,$ and $d$ as being fixed constants, and $m$ and $n$ as large). Then for every $\eps>0$, we have $$ I(\pts,\vrts) = O\left(m^{\frac{(d-1)s}{ds-1}+\eps}n^{\frac{d(s-1)}{ds-1}}+m+n\right), $$ where the constant of proportionality depends on $\eps$, $s$, $t$, $d$, and the maximum degree of the varieties. \end{theorem} While the bound of Theorem \ref{th:IncFox} holds for varieties of any dimension, in this paper we only consider the case of curves. Several better bounds are known for specific types of curves. The case of lines is studied in several papers, such as \cite{DG15,HS14}. It is also worth mentioning here the work of Sharir, Sheffer and Zahl~\cite{SSZ} on incidences between points and circles in three dimensions; an earlier study of this problem by Aronov et al.~\cite{AKS} gives a different, dimension-independent bound. A very recent result of Sharir and Zahl~\cite{SZ16} gives an improved bound (over the one in Theorem~\ref{th:PS}) for curves in the plane. %\micha{Any other REFS?} The bounds given in Theorem~\ref{ttt} and Theorem~\ref{th:ss4d} include a ``leading term'' that depends only on $m$ and $n$ (the terms $m^{1/2}n^{3/4}$ and $2^{c\sqrt{\log n}} m^{2/5}n^{4/5}$, respectively), and, except for the two-dimensional case, a series of ``lower-dimensional'' terms (like the term $m^{2/3}n^{1/3}q_2^{1/3}$ in Theorem~\ref{ttt} and the terms $m^{1/2}n^{1/2}q_3^{1/4}$ and $m^{2/3}n^{1/3}q_2^{1/3}$ in Theorem~\ref{th:ss4d}). The leading terms, in the case of lines, become smaller as $d$ increases (when $m$ is not too small and not too large with respect to $n$). Informally, by placing the lines in a higher-dimensional space, it should become harder to create many incidences on them. Nevertheless, this is true only if the setup is ``truly $d$-dimensional''. This means that not too many lines or curves are allowed to lie in a common lower-dimensional space. The lower-dimensional terms handle incidences within such lower-dimensional spaces. There is such a term for every dimension $j=2,\ldots,d-1$, and the ``$j$-dimensional'' term handles incidences within $j$-dimensional subspaces (which, as the quadrics in the case of lines in four dimensions in Theorem~\ref{th:ss4d}, are not necessarily linear and might be algebraic of low constant degree). Comparing the bounds for lines in two, three, and four dimensions, we see that the $j$-dimensional term in $d$ dimensions, for $jj$, is of the form $m^an^tq_j^{b-t}$, where $q_j$ is the maximum number of lines that can lie in a common $j$-dimensional flat or low-degree variety, % when one is allowed to take a generic % projection to a $j+1$-flat \noam{Is this notion clear?}, and $t$ depends on $j$ and $d$. \vspace{2mm} \noindent{\bf Our results.} In this paper we consider a generalization of these results, to the case where $\C$ is a family of bounded-degree algebraic curves with $k$ degrees of freedom (and some multiplicity $s$) in $\RR^d$. This is a very ambitious and difficult project, and the challenges that it faces seem to be enormous. Here we make the first step in this direction, and obtain the following bounds. As the exponents in the bounds are rather cumbersome expressions in $d$, $k$, and $j$, we first state the special case of $d=3$ (and prove it separately), % \noam{there is another reason: in three-dimension there is no % condition on $q_2$, and no need for conjectures}, and then give the general bound in $d$ dimensions. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{theorem}[Curves in $\RR^3$] \label{th:mainInc3} Let $k\ge 2$ be an integer, and let $\eps>0$. Then there exists a constant $c(k,\eps)$ that depends on $k$ and $\eps$, such that the following holds. Let $\pts$ be a set of $m$ points and $\C$ a set of $n$ irreducible algebraic curves of constant degree with $k$ degrees of freedom (and some multiplicity $s$) in $\RR^3$, such that every algebraic surface of degree at most $c(k,\eps)$ contains at most $q_2$ curves of $\C$. Then \[ I(\pts,\C) =O\left(m^{\frac{k}{3k-2}+\eps}n^{\frac{3k-3}{3k-2}}+ m^{\frac{k}{2k-1}+\eps}n^{\frac{3k-3}{4k-2}}q_2^{\frac{k-1}{4k-2}}+m+n\right), \] where the constant of proportionality depends on $k$, $s$, and $\eps$ (and on the degree of the curves). \end{theorem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% The corresponding result in $d$ dimensions is as follows. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{theorem}[Curves in $\RR^d$] \label{th:IncD} Let $d\ge 3$ and $k\ge 2$ be integers, and let $\eps>0$. Then there exist constants $c_j(k,d,\eps)$, for $j=2,\ldots,d-1$, that depend on $k$, $d$, $j$, and $\eps$, such that the following holds. Let $\pts$ be a set of $m$ points and $\C$ a set of $n$ irreducible algebraic curves of constant degree with $k$ degrees of freedom (and some multiplicity $s$) in $\RR^d$. Moreover, assume that, for $j=2,\ldots, d-1$, every $j$-dimensional algebraic variety of degree at most $c_j(k,d,\eps)$ contains at most $q_j$ curves of $\C$, for given parameters $q_2 \le \cdots \le q_{d-1}\le n$. Then we have \[ I(\pts,\C) =O\left(m^{\frac{k}{dk-d+1}+\eps}n^{\frac{dk-d}{dk-d+1}}+ \sum_{j=2}^{d-1} m^{\frac{k}{jk-j+1}+\eps}n^{\frac{d(j-1)(k-1)}{(d-1)(jk-j+1)}} q_j^{\frac{(d-j)(k-1)}{(d-1)(jk-j+1)}}+m+n\right), \] where the constant of proportionality depends on $k$, $s$, $d$, and $\eps$ (and on the degree of the curves), % \noam{and $s$. Do we actually use $k$ because of % Kovari-Sos-Turan? Check on which parameters the $O$-notation % actually depend}, provided that, for any $2\le j0$. Then there % exists a constant $c(k,d,\eps)$, that depends on $k$, $d$, and $\eps$, % such that the following holds. Let $\pts$ % be a set of $m$ points and let $\curves$ be a set of $n$ irreducible % algebraic curves of constant degree and with $k$ degrees of freedom, both in $\RR^d$. % Moreover, assume that every surface of degree at most $c(k,d,\eps)$ % contains at most $q$ curves of $\curves$. Then % \[ I(\pts,\curves) =O\left(m^{\frac{k}{dk-d+1} +\eps}n^{\frac{dk-d}{dk-d+1}} + % m^{\frac{k}{2k-1}+\eps}n^{\frac{dk-d}{(d-1)(2k-1)}}q^{\frac{(k-1)(d-2)}{(d-1)(2k-1)}}+m+n\right),\] % where the constant of proportionality depends on $k$, $d$, and $\eps$. % \end{theorem} % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \medskip \noindent{\bf Discussion.} The advantages of our results are obvious: They provide the first nontrivial bounds for the general case of curves with any number of degrees of freedom in any dimension (with the exception of one previous study of Fox et al.~\cite{FPSSZ14}, in which weaker bounds are obtained, albeit for arbitrary varieties instead of algebraic curves). Apart for the $\eps$ in the exponents, the leading term is ``best possible,'' in the sense that (i) the polynomial partitioning technique~\cite{GK2} that our analysis employs (and that has been used in essentially all recent works on incidences in higher dimensions) yields a recurrence that solves to this bound, and, moreover, (ii) it is (nearly) worst-case tight for \emph{lines} in two, three, and four dimensions (as shown in the respective works cited above), and in fact is likely to be tight for lines in higher dimensions too, using a suitable extension of a construction, due to Elekes and used in \cite{GK2,SS4d}. Nevertheless, our bounds are not perfect, and tightening them further is a major challenge for future research. Specifically: \vspace{2mm} \noindent{\bf (i)} While it seems likely that the leading terms in our bounds are tight for lines in $\RR^d$, they are probably not tight for most constant-degree algebraic curves. Sharir and Zahl \cite{SZ16} recently proved better bounds\footnote{% To be precise, it is assumed in \cite{SZ16} that the curves come from a ``$k$-dimensional family of curves'', which is a similar constraint, albeit not quite the same, as having $k$ degrees of freedom.} for the case of $d=2$ and $k\ge 3$, and it seems likely that better bounds also exist in higher dimensions. One common conjecture suggests that in $\RR^2$ the number of incidences between any $n$ points and any $n$ constant-degree curves (with no common components) should be $O(n^{4/3})$; the conjecture does not always hold when the number of points and the number of curves are significantly different. \vspace{2mm} \noindent{\bf (ii)} The bounds involve the factor $m^\eps$. As the existing works indicate, getting rid of this factor is no small feat. Although the factor does not show up in the cases of lines in two and three dimensions, it already shows up (sort of) in four dimensions (Theorem~\ref{th:ss4d}), as well as in the case of circles in three dimensions~\cite{SSZ}. (A recent study of Guth~\cite{Gu14} also pays this factor for the case of lines in three dimensions, in order to simplify the original analysis in the Guth--Katz paper~\cite{GK2}. Another recent simplified proof, due to Sharir and Solomon~\cite{SS3d}, manages to get rid of this factor, except for some narrow range of $m$ and $n$.) See the proofs and comments below for further elaboration of this issue. \vspace{2mm} \noindent{\bf (iii)} The condition that no surface of degree $c_j(k,d,\eps)$ contains too many curves of $\C$, for $j=2,\ldots,d-1$, is very restrictive, especially since the actual values of these constants that arise in the proofs can be quite large. Again, earlier works also ``suffer'' from this handicap, such as Guth's work~\cite{Gu14} mentioned above, as well as an earlier version of Sharir and Solomon's four-dimensional bound~\cite{SS14}. A recent interesting study of Guth and Zahl~\cite{GZ} may offer some tools for better controlling these parameters. \vspace{2mm} \noindent{\bf (iv)} Finally, the lower-dimensional terms that we obtain are not best possible. For example, the bound that we get in Theorem~\ref{th:mainInc3} for the case of lines in $\RR^3$ ($k=2$) is $O(m^{1/2+\eps}n^{3/4} + m^{2/3+\eps}n^{1/2}q_2^{1/6}+m+n)$. When $q_2 \ll n$, the two-dimensional term $m^{2/3+\eps}n^{1/2}q_2^{1/6}$ in that bound is worse than the corresponding term $m^{2/3}n^{1/3}q_2^{1/3}$ in Theorem~\ref{ttt} (even when ignoring the factor $m^\eps$). Since the statement of Theorem \ref{th:IncD} is rather involved, we also present two simplified versions thereof. The first is a straightforward corollary as a simpler case. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{corollary} Let $d\ge 3$, $k\ge 2$ be integers, and let $\eps>0$. Then there exists a constant $c(k,d,\eps)$ that depends on $k$, $d$, and $\eps$, such that the following holds. Let $\pts$ be a set of $m$ points and $\C$ a set of $n$ irreducible algebraic curves of some constant maximum degree with $k$ degrees of freedom (and some multiplicity $s$) in $\RR^d$, such that $m =O(n^{d/(d-1)})$. Moreover, assume that every algebraic variety of degree at most $c(k,d,\eps)$ contains a constant number of curves of $\C$, where this constant may depend on $d$, $k$, and $\eps$. Then we have \[ I(\pts,\C) =O\left(m^{\frac{k}{dk-d+1}+\eps}n^{\frac{dk-d}{dk-d+1}}+n\right), \] where the constant of proportionality depends on $k$, $s$, $d$, $\eps$, and the maximum degree of the curves. \end{corollary} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% The second simplification replaces the sequence of constraints on the number of curves in lower-dimensional varieties of constant degrees by a single constraint involving only $(d-1)$-dimensional varieties (hypersurfaces). Its proof is similar to that of Theorem~\ref{th:IncD}, and will be briefly discussed later. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{theorem} \label{th:IncDsimp} Let $d\ge 3$, $k\ge 2$ be integers, and let $\eps>0$. Then there exists a constant $c(k,d,\eps)$ that depends on $k$, $d$, and $\eps$, such that the following holds. Let $\pts$ be a set of $m$ points, let $\curves$ be a set of $n$ irreducible algebraic curves of some constant maximum degree and with $k$ degrees of freedom, both in $\RR^d$, and let $q\le n$ be another parameter, such that every hypersurface of degree at most $c(k,d,\eps)$ contains at most $q$ curves of $\curves$. Then \[ I(\pts,\curves) =O\left(m^{\frac{k}{dk-d+1} +\eps}n^{\frac{dk-d}{dk-d+1}} + m^{\frac{k}{2k-1}+\eps}n^{\frac{dk-d}{(d-1)(2k-1)}}q^{\frac{(k-1)(d-2)}{(d-1)(2k-1)}}+m+n\right), \] where the constant of proportionality depends on $\eps$, $k$, $d$, and the maximum degree of the curves. \end{theorem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Our results are also related to recent works by Dvir and Gopi~\cite{DG15} and by Hablicsek and Scherr~\cite{HS14}, that study rich lines in high dimensions. Specifically, let $\pts$ be a set of $n$ points in $\reals^d$ and let $L$ be a set of \emph{$r$-rich} lines (that is, each line of $L$ contains at least $r$ points of $\pts$). If $|L|=\Omega(n^2/r^{d+1})$ then there exists a hyperplane containing $\Omega(n/r^{d-1})$ points of $\pts$. Our bounds are relevant for extending this result to rich curves. Concretely, for a set $\pts$ of $n$ points in $\reals^d$ and a collection $\C$ of $r$-rich constant-degree algebraic curves with $k$ degrees of freedom, if $|\C|$ is too large then the incidence bound becomes larger than the ``leading term'' in Theorem~\ref{th:IncDsimp}, indicating that some hypersurface must contain many curves of $\C$, which would then imply that such a surface has to also contain many points of $\pts$. We omit the rather routine, albeit fairly tedious, calculations. As in the classical work of Guth and Katz~\cite{GK2}, and in the numerous follow-up studies of related problems, here too we use the polynomial partitioning method, as pioneered in \cite{GK2}. The reason why our bounds suffer from the aforementioned handicaps is that we use a partitioning polynomial of (large but) constant degree. (The idea of using constant-degree partitioning polynomials for problems of this kind is due to Solymosi and Tao~\cite{ST11}.) When using a polynomial of a larger, non-constant degree, we face the difficult task of bounding incidences between points and curves that are fully contained in the zero set of the polynomial, where the number of curves of this kind can be large, because the polynomial partitioning technique has no control over this value. We remark that for lines we have the classical Cayley--Salmon theorem (see, e.g., Guth and Katz~\cite{GK2}), which essentially bounds the number of lines that can be fully contained in an algebraic surface of a given degree, unless the surface is ruled by lines. However, such a property has not been known for more general curves. Nevertheless, Nilov and Skopenkov~\cite{NS12} have recently established such a result involving lines and circles in $\reals^3$, and, very recently, Guth and Zahl~\cite{GZ} have done the same for general algebraic curves in three dimensions. Handling these incidences requires heavy-duty machinery from algebraic geometry, and leads to profound new problems in that domain that need to be tackled. % \noam{I think the following section is a bit too apologetic in my opinion.} In contrast, using a polynomial of constant degree makes this part of the analysis much simpler, as can be seen below, but then handling incidences within the cells of the partition becomes non-trivial, and a naive approach yields a bound that is too large. To handle this part, one uses induction within each cell of the partitioning, and it is this induction process that is responsible for the weaker aspects of the lower-dimensional terms in the resulting bound, as well as the extra $m^\eps$ factor in the leading term. Nevertheless, with these ``sacrifices'' we are able to obtain a ``general purpose'' bound that holds for a broad spectrum of instances. It is our hope that this study will motivate further research on this problem that would improve our results along the ``handicaps'' mentioned above. %\micha{Anything new to mention here?} Recalling how inaccessible were these kinds of problems prior to Guth and Katz's breakthroughs eight and six years ago, it is quite gratifying that so much new ground can be gained in this area, including the progress made in this paper. \vspace{2mm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \noindent{\bf Background.} Incidence problems have been a major topic in combinatorial and computational geometry for the past thirty years, starting with the aforementioned Szemer\'edi-Trotter bound \cite{SzT} back in 1983 (and even earlier). Several techniques, interesting in their own right, have been developed, or adapted, for the analysis of incidences, including the crossing-lemma technique of Sz\'ekely~\cite{Sz}, and the use of cuttings as a divide-and-conquer mechanism (e.g., see~\cite{CEGSW}). Connections with range searching and related algorithmic problems in computational geometry have also been noted and exploited, and studies of the Kakeya problem (see, e.g., \cite{T}) indicate the connection between this problem and incidence problems. See Pach and Sharir~\cite{PS} for a comprehensive (albeit a bit outdated) survey of the topic. The landscape of incidence geometry has dramatically changed in the past eight years, due to the infusion, in two groundbreaking papers by Guth and Katz~\cite{GK,GK2}, of new tools and techniques drawn from algebraic geometry. Although their two direct goals have been to obtain a tight upper bound on the number of joints in a set of lines in three dimensions \cite{GK}, and a near-linear lower bound for the classical distinct distances problem of Erd{\H o}s \cite{GK2}, the new tools have quickly been recognized as useful for incidence bounds. See \cite{EKS,KMSS,KMS,SSZ,ST11,Za1,Za2} for a sample of recent works on incidence problems that use the new algebraic machinery. The present paper continues this line of research, and aims at extending the collection of instances where nontrivial incidence bounds in higher dimensions can be obtained. %\paragraph{The partitioning polynomial method.} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{The three-dimensional case} {\bf Proof of Theorem \ref{th:mainInc3}.} We fix $\eps > 0$, and prove by induction on $m+n$ that \begin{equation} \label{eqind} I(\pts,\C) \le \alpha_{1} \left( m^{\frac{k}{3k-2}+\eps}n^{\frac{3k-3}{3k-2}}+m^{\frac{k}{2k-1}+\eps}n^{\frac{3k-3}{4k-2}}q^{\frac{k-1}{4k-2}} \right) +\alpha_{2}(m+n), \end{equation} % where $\alpha_{1},\alpha_{2}$ are sufficiently large constants, $\alpha_1$ depends on $\eps$ and $k$ (and $s$), and $\alpha_2$ depends on $k$ (and $s$). % \noam{why does this not appear in the $O$ % notation (i.e., in the statement of the theorem)? it is not clear % why the dependency on $s$ is ``soft'' as you said at the beginning % of the paper. Notice that in the theorem of Pach and yourself, in % the $O$-notation you mention $O_{k,s}$ -- needs consistency.} For the induction basis, the case where $m,n$ are sufficiently small constants can be handled by choosing sufficiently large values of $\alpha_{1},\alpha_{2}$. Another base case is $m=O(n^{1/k})$. Since the incidence graph, as a subgraph of $\pts\times\C$, does not contain $K_{k,s+1}$ as a subgraph, the K\H ov\' ari-S\'os-Tur\'an theorem (e.g., see \cite[Section 4.5]{Mat02}) implies that $I(\pts,\C) = O(mn^{1-1/k} + n)$, where the constant of proportionality depends on $k$ (and $s$). When $m=O(n^{1/k})$, this implies the bound $I(\pts,\C) = O(n)$, which is subsumed in (\ref{eqind}) if we choose $\alpha_2$ sufficiently large. We may thus assume that $n\le cm^k$, for some absolute constant $c$, and that $m$ and $n$ are at least some sufficiently large constants. \vspace{2mm} \noindent {\bf Applying the polynomial partitioning technique.} We construct an \emph{$r$-partitioning polynomial} $f$ for $\pts$, for a sufficiently large constant $r$ (depending on $\eps$). That is, as established in Guth and Katz~\cite{GK2}, $f$ is of degree $O(r^{1/3})$ (the constant in the $O$ notation is an absolute constant), and the complement of its zero set $Z(f)$ is partitioned into $u=O(r)$ open connected cells, each containing at most $m/r$ points of $\pts$. % % \micha{Do we really need to say the next sentence? Propose to delete it.} % We impose the asymptotic relations % $2^{1/\eps} \ll r \ll \alpha_{2} \ll \alpha_{1}$ between the various constants. Denote the (open) cells of the partition as $\tau_1, \ldots, \tau_u$. For each $i=1,\ldots,u$, let $\C_i$ denote the set of curves of $\C$ that intersect $\tau_i$ and let $\pts_i$ denote the set of points that are contained in $\tau_i$. We set $m_i=|\pts_i|$ and $n_i=|\C_i|$, for $i=1,\ldots,u$, and $m' = \sum_i m_i$, and notice that $m_i\le m/r$ for each $i$ (and $m'\le m$). An obvious property (which is a consequence of B\'ezout's theorem, see, e.g., \cite[Theorem A.2]{ST11}) is that every curve of $\C$ intersects $O(r^{1/3})$ cells of $\RR^3\setminus Z(f)$. Therefore, $\sum_i n_i \le bnr^{1/3}$, for a suitable constant $b>1$ (that depends on the degree of the curves in $\C$). Using H\"older's inequality, we have \begin{align*} \sum_i n_i^{\frac{3k-3}{3k-2}} &\le \left(\sum_i n_i\right)^{\frac{3k-3}{3k-2}} \left(\sum_i 1\right)^{\frac{1}{3k-2}} \le b'\left(nr^{\frac{1}{3}}\right)^{\frac{3k-3}{3k-2}}r^{\frac{1}{3k-2}} = b'n^{\frac{3k-3}{3k-2}}r^{\frac{k}{3k-2}}, \\[2mm] \sum_i n_i^{\frac{3k-3}{4k-2}} &\le \left(\sum_i n_i\right)^{\frac{3k-3}{4k-2}} \left(\sum_i 1\right)^{\frac{k+1}{4k-2}} \le b'\left(nr^{\frac{1}{3}}\right)^{\frac{3k-3}{4k-2}}r^{\frac{k+1}{4k-2}} = b'n^{\frac{3k-3}{4k-2}}r^{\frac{k}{2k-1}}, \end{align*} for another absolute constant $b'$. Combining the above with the induction hypothesis, applied within each cell of the partition, implies $$ \sum_i I ( \pts_i,\C_i) \le \sum_i \left(\alpha_{1} \left( m_i^{\frac{k}{3k-2}+\eps}n_i^{\frac{3k-3}{3k-2}}+ m_i^{\frac{k}{2k-1}+\eps}n_i^{\frac{3k-3}{4k-2}}q_2^{\frac{k-1}{4k-2}}\right)+\alpha_{2}(m_i+n_i)\right) $$ $$ \le \alpha_{1}\left(\frac{m^{\frac{k}{3k-2}+\eps}}{r^{\frac{k}{3k-2}+\eps}} \sum_i n_i^{\frac{3k-3}{3k-2}} + \frac{m^{\frac{k}{2k-1}+\eps}q_2^{\frac{k-1}{4k-2}}}{r^{\frac{k}{2k-1}+\eps}} \sum_i n_i^{\frac{3k-3}{4k-2}}\right) + \sum_i\alpha_{2}(m_i+n_i) $$ $$ \le \alpha_{1}b'\left( \frac{m^{\frac{k}{3k-2}+\eps}n^{\frac{3k-3}{3k-2}}}{r^{\eps}} + \frac{m^{\frac{k}{2k-1}+\eps}n^{\frac{3k-3}{4k-2}}q_2^{\frac{k-1}{4k-2}}}{r^{\eps}}\right) + \alpha_{2}\left(m'+bnr^{1/3}\right). $$ Our assumption that $n=O(m^k)$ implies that $n=O\left(m^{\frac{k}{3k-2}}n^{\frac{3k-3}{3k-2}}\right)$ (with an absolute constant of proportionality). Thus, when $\alpha_{1}$ is sufficiently large with respect to $r,k$, and $\alpha_{2}$, we have \[ \sum_i I(\pts_i,\C_i) \le 2\alpha_{1}b'\left(\frac{m^{\frac{k}{3k-2}+\eps}n^{\frac{3k-3}{3k-2}}}{r^{\eps}} + \frac{m^{\frac{k}{2k-1}+\eps}n^{\frac{3k-3}{4k-2}}q_2^{\frac{k-1}{4k-2}}}{r^{\eps}} \right) + \alpha_{2}m'. \] When $r$ is sufficiently large, such that $r^\eps \ge 6b'$, we have \begin{equation}\label{eq:incCells} \sum_i I(\pts_i,\C_i) \le \frac{\alpha_{1}}{3} \left(m^{\frac{k}{3k-2}+\eps}n^{\frac{3k-3}{3k-2}} + m^{\frac{k}{2k-1}+\eps}n^{\frac{3k-3}{4k-2}}q_2^{\frac{k-1}{4k-2}} \right)+ \alpha_{2}m'. \end{equation} \noindent {\bf Incidences on the zero set $Z(f)$.} It remains to bound incidences with points that lie on $Z(f)$. Set $\pts_0:= \pts \cap Z(f)$ and $m_0=|\pts_0|=m-m'$. Let $\C_0$ denote the set of curves that are fully contained in $Z(f)$, and set $\C': = \C \setminus \C_0$, % \noam{I see that you chose not to mention the fact that $\C'$ is the union of the $\C'_i$.} $n_0 := |\C_0|$, and $n' := |\C'| =n-n_0$. Since every curve of $\C'$ intersects $Z(f)$ in $O(r^{1/3})$ points, we have, taking $\alpha_1$ to be sufficiently large, and arguing as above, \begin{equation} \label{eq:inc'} I(\pts_0,\C') = O(nr^{1/3}) \le \frac{\alpha_1}{3} m^{\frac{k}{3k-2}+\eps}n^{\frac{3k-3}{3k-2}} . \end{equation} Finally, we consider the number of incidences between points of $\pts_0$ and curves of $\C_0$. For this, we set $c(k,\eps)$ to be the degree of $f$, which is $O(r^{1/3})$, and can be taken to be $O((6b')^{1/(3\eps)})$. Then, by the assumption of the theorem, we have $|\C_0| \le q_2$. We consider a generic plane $\pi \subset \RR^3$ and project $\pts_0$ and $\C_0$ onto two respective sets $\pts^*$ and $\C^*$ on $\pi$. Since $\pi$ is chosen generically, we may assume that no two points of $\pts_0$ project to the same point in $\pi$, and that no pair of distinct curves in $\C_0$ have overlapping projections in $\pi$. Moreover, the projected curves still have $k$ degrees of freedom, in the sense that, given any $k$ points on the projection $\gamma^*$ of a curve $\gamma\in\C_0$, there are at most $s-1$ other projected curves that go through all these points. This is argued by lifting each point $p$ back to the point $\bar{p}$ on $\gamma$ in $\reals^3$, and by exploiting the facts that the original curves have $k$ degrees of freedom, and that, for a sufficiently generic % \noam{explain what we mean by generic projection} projection, any curve that does not pass through $\bar{p}$ does not contain any point that projects to $p$. The number of intersection points between a pair of projected curves may increase % \noam{why does this number may increase?? I see that you did % not relate to any of the comments I sent you about this paragraph. % In my opinion it is too sketchy, and I commented yesterday how % to improve it.} but it must remain a constant since these are intersection points between constant-degree algebraic curves with no common components. By applying Theorem \ref{th:PS}, we obtain % \begin{equation*} I(\pts_0,\C_0) = I(\pts^*,\C^*) = O(m_0^{\frac{k}{2k-1}}q_2^{\frac{2k-2}{2k-1}} + m_0 + q_2), \end{equation*} where the constant of proportionality depends on $k$ (and $s$). Since $q_2\le n$ and $m_0\le m$, we have ${\displaystyle m_0^{\frac{k}{2k-1}}q_2^{\frac{2k-2}{2k-1}} \le m^{\frac{k}{2k-1}}n^{\frac{3k-3}{4k-2}}q_2^{\frac{k-1}{4k-2}}}$. We thus get that $I(\pts_0,\C_0)$ is at most \begin{equation} \label{eq:inc0} O\left(m^{\frac{k}{2k-1}}n^{\frac{3k-3}{4k-2}}q_2^{\frac{k-1}{4k-2}} + n + m_0\right) \le \frac{\alpha_1}{3}m^{\frac{k}{2k-1}}n^{\frac{3k-3}{4k-2}}q_2^{\frac{k-1}{4k-2}} + b_2n + \alpha_2 m_0 , \end{equation} for sufficiently large $\alpha_1$ and $\alpha_2$; the constant $b_2$ comes from Theorem \ref{th:PS}, and is independent of $\eps$ and of the choices for $\alpha_1,\alpha_2$ made so far. By combining \eqref{eq:incCells}, \eqref{eq:inc'}, and \eqref{eq:inc0}, including the case $m=O(n^{1/k})$, and choosing $\alpha_2$ sufficiently large, we obtain \begin{equation*} I(\pts,\C) \le \alpha_{1} \left( m^{\frac{k}{3k-2}+\eps}n^{\frac{3k-3}{3k-2}}+m^{\frac{k}{2k-1}+\eps}n^{\frac{3k-3}{4k-2}}q_2^{\frac{k-1}{4k-2}} \right) +\alpha_{2}(m+n). \end{equation*} % This completes the induction step and thus the proof of the theorem. \proofend \vspace{2mm} \noindent{\bf Example 1: The case of lines.} Lines in $\reals^3$ have $k=2$ degrees of freedom, and we almost get the bound of Guth and Katz in Theorem~\ref{ttt}. There are three differences that make this derivation somewhat inferior to that in Guth and Katz~\cite{GK2}, as detailed in items (i)--(iii) in the discussion in the introduction. % % (already % noted earlier): (i) The requirement that no surface of degree at % most $c_\eps$ contains more than $q_2$ lines is more restrictive % than the one in \cite{GK2}, which only requires this property for % planes. % % (and reguli). % (ii) The bound that we get is weaker because of % the $m^\eps$ factors. (iii) The bound is also weaker because of its % second term, which, ignoring the factor $m^\eps$, is % $O(m^{2/3}n^{1/2}q_2^{1/6})$, which is weaker than the bound % $O(m^{2/3}n^{1/3}q_2^{1/3})$ derived in \cite{GK2}. We also recall the two follow-up studies of point-line incidences in $\RR^3$, of Guth~\cite{Gu14} and of Sharir and Solomon~\cite{SS3d}. Guth's bound suffers from weaknesses (i) and (ii), but avoids (iii), using a fairly sophisticated inductive argument. Sharir and Solomon's bound avoids (i) and (iii), and almost avoids (ii), in a sense that we do not make explicit here. In both cases, considerably more sophisticated machinery is needed to achieve these improvements. % The third issue % seems to be a delicate question. It is enforced to make the % induction step work. \vspace{2mm} \noindent{\bf Example 2: The case of circles.} Circles in $\reals^3$ have $k=3$ degrees of freedom, and we get the bound \[ I(\pts,\C) =O\left(m^{3/7+\eps}n^{6/7}+ m^{3/5+\eps}n^{3/5}q_2^{1/5}+m+n\right).\] The leading term is the same as in Sharir et al.~\cite{SSZ}, but the second term is weaker, because it relies on the general bound of Pach and Sharir (Theorem~\ref{th:PS}), whereas the bound in \cite{SSZ} exploits an improved bound for point-circle incidences, due to Aronov et al.~\cite{AKS}, which holds in any dimension. If we plug that bound into the above scheme, we obtain an exact reconstruction of the bound in \cite{SSZ}. In addition, considering the items (i)--(iii) discussed earlier, we note: (i) The requirements in \cite{SSZ} about the maximum number of circles on a surface are weaker, and are only for planes and spheres. (ii) The $m^\eps$ factors are present in both bounds. (iii) Even after the improvement noted above, the bounds still seem to be weak in terms of their dependence on $q_2$, and improving this aspect, both here and in \cite{SSZ}, is a challenging open problem. % \micha{Add another example, just to illustrate the potential of the whole scheme.} Theorem \ref{th:mainInc3} can easily be restated as bounding the number of \emph{rich points}. % \begin{corollary} \label{co:rich} For each $\eps>0$ there exists a parameter $c(k,\eps)$ that depends on $k$ and $\eps$, such that the following holds. Let $\C$ be a set of $n$ irreducible algebraic curves of constant degree and with $k$ degrees of freedom (with some multiplicity $s$) in $\RR^3$. Moreover, assume that every surface of degree at most $c(k,\eps)$ contains at most $q_2$ curves of $\C$. Then there exists some constant $r_0(k,\eps)$ depending on $\eps, k$ (and $s$), such that for any $r\ge r_0(k,\eps)$, the number of points that are incident to at least $r$ curves of $\C$ (so-called \emph{$r$-rich points}), is\\ % \noam{no $s$ in the $O$ notation? did you check % that the $\eps$ in the exponent should not be multiplied by some % constant as I asked in the email?} ${\displaystyle O\left( \frac{n^{3/2+\eps}}{r^{\frac{3k-2}{2k-2}+\eps}} + \frac{n^{3/2+\eps}q_2^{1/2+\eps}}{r^{\frac{2k-1}{k-1}+\eps}} + \frac{n}{r} \right)}$, where the constant of proportionality depends on $k$, $s$ and $\eps$. \end{corollary} \noindent{\bf Proof.} Denoting by $m_r$ the number of $r$-rich points, the corollary is obtained by combining the upper bound in Theorem~\ref{th:mainInc3} with the lower bound $rm_r$. \proofend %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Incidences in higher dimensions} % \noindent{\bf Proof of Theorem~\ref{th:IncD}.} Again, we fix $\eps>0$, and prove, by double induction, where the outer induction is on the dimension $d$ and the inner induction is on $m+n$, that $I(\pts,\C)$ is at most \begin{equation} \label{eq:indgend} \alpha_{1,d} \left(m^{\frac{k}{dk-d+1}+\eps}n^{\frac{dk-d}{dk-d+1}}+ \sum_{j=2}^{d-1} m^{\frac{k}{jk-j+1}+\eps}n^{\frac{d(j-1)(k-1)}{(d-1)(jk-j+1)}}q_j^{\frac{(d-j)(k-1)}{(d-1)(jk-j+1)}}\right) +\alpha_{2,d}(m+n), \end{equation} % where $\alpha_{1,d},\alpha_{2,d}$ are sufficiently large constants, $\alpha_{1,d}$ depends on $k$ (and $s$), $\eps$, $d$, and the maximum degree of the curves, and $\alpha_{2,d}$ depends only on $k$ (and $s$), $d$, and the maximum degree of the curves. % \micha{Check!} For the outer induction basis, the case $d=2$ follows by Theorem~\ref{th:PS}, and the case $d=3$ is just Theorem~\ref{th:mainInc3}, proved in the previous section. We assume therefore that the claim holds up to dimension $d-1$, and prove it in dimension $d\ge 4$. The base cases of the inner induction (that is, when $d$ is fixed, we induct over $m+n$) is when $m,n$ are sufficiently small constants, and when $m=O(n^{1/k})$. The bound in (\ref{eq:indgend}) can be enforced in the former case by choosing sufficiently large values of $\alpha_{1,d},\alpha_{2,d}$, and in the latter case exactly as for $d=3$, so we may assume, as before, that $n\le c m^k$ for some absolute constant $c$. \vspace{2mm} \noindent {\bf Applying the polynomial partitioning technique.} The analysis is somewhat repetitive and resembles the one in the previous section, although many details are different; it is given in detail for the convenience of the reader, and in the interest of completeness. Let $f$ be an $r$-partitioning polynomial, for a sufficiently large constant $r$. % \micha{Do we really need to say the next sentence? Propose to delete it.} % We impose the asymptotic relations $2^{1/\eps} \ll r % \ll \alpha_{2,d} \ll \alpha_{1,d}$ between the various constants. According to the polynomial partitioning theorem \cite{GK2}, we have $\deg f = O(r^{1/d})$. Denote the (open) cells of the partition as $\tau_1, \ldots, \tau_u$, where % according to Warren's theorem in $\RR^d$ \cite{Warren68}, $u=O(r)$. For each $i=1,\ldots,u$, let $\C_i$ denote the set of curves of $\C$ that intersect $\tau_i$ and let $\pts_i$ denote the set of points that are contained in $\tau_i$. We set $m_i=|\pts_i|$, and $n_i=|\C_i|$, for $i=1,\ldots,u,$ and $m' = \sum_i m_i$, and notice that $m_i\le m/r$ for each $i$ (and $m' \le m$). Arguing as before, every curve of $\C$ intersects at most $\deg(f) = O(r^{1/d})$ cells of $\RR^d\setminus Z(f)$. Therefore, $\sum_i n_i \le b_dnr^{1/d}$, for a suitable constant $b_d>1$ that depends on $d$ and the degree of the curves. Using H\"older's inequality, we have \begin{align*} \sum_i n_i^{\frac{dk-d}{dk-d+1}} &\le b'_d\left(nr^{\frac{1}{d}}\right)^{\frac{dk-d}{dk-d+1}}r^{\frac{1}{dk-d+1}} \le b'_dn^{\frac{dk-d}{dk-d+1}}r^{\frac{k}{dk-d+1}}, \quad \text{and} \\ \sum_i n_i^{\frac{d(j-1)(k-1)}{(d-1)(jk-j+1)}} &\le b'_d\left(nr^{\frac{1}{d}}\right)^{\frac{d(j-1)(k-1)}{(d-1)(jk-j+1)}}r^{\frac{dk-jk+j-1}{(d-1)(jk-j+1)}} \le b'_dn^{\frac{d(j-1)(k-1)}{(d-1)(jk-j+1)}}r^{\frac{k}{jk-j+1}} , \end{align*} for each $j=2,\ldots,d-1$, where $b'_d$ is another constant parameter that depends on $d$. Combining the above with the induction hypothesis implies that $\sum_i I ( \pts_i,\C_i)$ is at most $$ \sum_i \left(\alpha_{1,d} \left( m_i^{\frac{k}{dk-d+1}+\eps}n_i^{\frac{dk-d}{dk-d+1}}+\sum_{j=2}^{d-1} m_i^{\frac{k}{jk-j+1}+\eps} n_i^{\frac{d(j-1)(k-1)}{(d-1)(jk-j+1)}}q_j^{\frac{(d-j)(k-1)}{(d-1)(jk-j+1)}} \right) + \alpha_{2,d}(m_i+n_i)\right) $$ $$ \le \alpha_{1,d}\left(\frac{m^{\frac{k}{dk-d+1}+\eps}}{r^{\frac{k}{dk-d+1}+\eps}} \sum_i n_i^{\frac{dk-d}{dk-d+1}} + \sum_{j=2}^{d-1} \frac{m^{\frac{k}{jk-j+1}+\eps}q_j^{\frac{(d-j)(k-1)}{(d-1)(jk-j+1)}}}{r^{\frac{k}{jk-j+1}+\eps}} \sum_i n_i^{\frac{d(j-1)(k-1)}{(d-1)(jk-j+1)}}\right) $$ $$ \hspace{120mm} + \sum_i\alpha_{2,d}(m_i+n_i) $$ $$ \le \alpha_{1,d} b'_d\left( \frac{m^{\frac{k}{dk-d+1}+\eps}n^{\frac{dk-d}{dk-d+1}}}{r^{\eps}} + \frac{\sum_{j=2}^{d-1} m^{\frac{k}{jk-j+1}+\eps} n^{\frac{d(j-1)(k-1)}{(d-1)(jk-j+1)}} q_j^{\frac{(d-j)(k-1)}{(d-1)(jk-j+1)}}}{r^\eps} \right) $$ $$ \hspace{120mm} + \alpha_{2,d}\left(m'+b_dnr^{1/d}\right). $$ Since we assume that $n=O(m^k)$, we have $n=O\left(m^{\frac{k}{dk-d+1}}n^{\frac{dk-d}{dk-d+1}}\right)$, with a constant of proportionality that depends only on $d$. Thus, when $\alpha_{1,d}$ is sufficiently large with respect to $r,d$, and $\alpha_{2,d}$, we have \[ \sum_i I(\pts_i,\C_i) \le 2\alpha_{1,d} b\left(\frac{m^{\frac{k}{dk-d+1}+\eps}n^{\frac{dk-d}{dk-d+1}}}{r^{\eps}} + \frac{m^{\frac{k}{2k-1}+\eps}n^{\frac{dk-d}{(d-1)(2k-1)}}q^{\frac{(k-1)(d-2)}{(d-1)(2k-1)}}}{r^{\eps}} \right) + \alpha_{2,d}m'. \] When $r$ is sufficiently large, such that $r^\eps \ge 6b'$, the bound is at most \begin{equation}\label{eq:incCellsd} \frac{\alpha_{1,d}}{3} \left(m^{\frac{k}{dk-d+1}+\eps}n^{\frac{dk-d}{dk-d+1}} + \sum_{j=2}^{d-1} m^{\frac{k}{jk-j+1}+\eps} n^{\frac{d(j-1)(k-1)}{(d-1)(jk-j+1)}} q_j^{\frac{(d-j)(k-1)}{(d-1)(jk-j+1)}} \right) + \alpha_{2,d}m'. \end{equation} \noindent {\bf Incidences on the zero set $Z(f)$.} It remains to bound incidences with points that lie on $Z(f)$. Set $\pts_0= \pts \cap Z(f)$ and $m_0=|\pts_0|=m-m'$. Let $\C_0$ denote the set of curves that are fully contained in $Z(f)$, and set $\C' = \C \setminus \C_0$, $n_0 = |\C_0|$, and $n' = |\C'| =n-n_0$. Since every curve of $\C'$ intersects $Z(f)$ in $O(r^{1/d})$ points, we have, arguing as above, \begin{equation} \label{eq:inc'd} I(\pts_0,\C') \le b_dn'r^{1/d} = O(nr^{1/d}) \le \frac {\alpha_{1,d}}{3} m^{\frac{k}{dk-d+1}+\eps}n^{\frac{dk-d}{dk-d+1}} , \end{equation} provided that $\alpha_{1,d}$ is chosen sufficiently large. Finally, we consider the number of incidences between points of $\pts_0$ and curves of $\C_0$. For this, we set $c_{d-1}(k,d,\eps)$ to be the degree of $f$, which is $O(r^{1/d})=O((6b')^{1/(\eps d)})$. Then, by the assumption of the theorem, we have $|\C_0| \le q_{d-1}$. We consider a generic hyperplane $H \subset \RR^d$ and project $\pts_0$ and $\C_0$ onto two respective sets $\pts^*$ and $\C^*$ on $H$. Arguing as in the three-dimensional case, we can enforce that $I(\pts_0,\C_0) = I(\pts^*,\C^*)$, that the projected curves have $k$ degrees of freedom, % % Since $H$ is chosen generically, we may assume that % no two points of $\pts_0$ project to the same point in $H$, and that % no pair of distinct curves in $\C_0$ have overlapping projections in % $H$. Moreover, the projected curves still have $k$ degrees of % freedom, in the sense that, given any $k$ points on a projected % curve, there are at most $s-1$ other projected curves that go % through all these points. This is argued, as before, by lifting each % point $p$ back to the point $\bar{p}$ on the original curve in % $\reals^d$, and by exploiting the facts that the original curves % have $k$ degrees of freedom, and that, for a sufficiently generic % projection, any curve that does not pass through $\bar{p}$ does not % contain any point that projects to $p$. % % Since the projected curves do not overlap, we can apply B\'ezout's % theorem in the plane (say, by projecting them further onto some % generic 2-plane) and conclude that the number of intersection % points between them is at most the product of their degrees. Moreover, % By Harris~\cite{Har}, the degrees of the curves do not change under % a generic projection (in the complex projective setting), so the % number of intersection points (counted with multiplicity) of the % projections of any pair of curves is at most the product of their % degrees and thus a constant. That is, by changing $s$ if needed, % the projected curves still have $k$ degrees of freedom. % and that, for $j0$, there exists an integer $c_\eps$, so that the following holds. Let $P$ be a set of $m$ distinct points and $L$ a set of $n$ distinct lines in $\reals^4$, and let $q, s\le n$ be parameters, such that % (i) each point of $P$ is incident to at least $XX$ lines of $L$, (i) for any polynomial $f \in \reals[x,y,z,w]$ of degree $\le c_\eps$, its zero set $Z(f)$ does not contain more than $q$ lines of $L$, and (ii) no 2-plane contains more than $s$ lines of $L$. Then, $$ \label {ma:in} I(P,L) \le A_{\eps} \left(m^{2/5+\eps}n^{4/5}+ m^{1/2+\eps}n^{2/3}q^{1/12} + m^{2/3+\eps}n^{4/9}s^{2/9} \right) + A(m + n) , $$ where $A_{\eps}$ depends on $\eps$, and $A$ is an absolute constant. \end{theorem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% This result follows from our main Theorem~\ref{th:IncD}, if we impose Equation~\eqref{eq:ontheq} on $q_2=s$, $q_3=q$, and $n$, which in this case is equivalent to $s\le q \le n$ and $\frac {q^9} {n^8} 3$ (see~\cite[Conjecture 3.4]{BS14} for an exact formulation); for completeness we refer also to ~\cite[Theorem 4.1]{FPSSZ14}, where a weaker version of this conjecture is proved. Building upon the work of Basu and Sombra~\cite{BS14}, the proof of Sharir and Solomon~\cite{SS4d} is likely to extend and yield the same bound as in our main Theorem~\ref{th:IncD}, for the more general case of incidences between points and bounded degree algebraic curves in dimensions at most five, and, if Conjecture 3.4 of~\cite{BS14} holds, in every dimension, without any conditions on the $q_j$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{thebibliography}{99} % \bibitem{ANP+} P. K. Agarwal, E. Nevo, J. Pach, R. Pinchasi, M. Sharir and S. Smorodinsky, Lenses in arrangements of pseudocircles and their applications, {\it J. ACM} 51 (2004), 139--186. \bibitem{AKS} B.\ Aronov, V.\ Koltun, and M.\ Sharir, Incidences between points and circles in three and higher dimensions, {\it Discrete Comput. Geom.} 33 (2005), 185--206. \bibitem{BS14} S. Basu and M. Sombra, Polynomial partitioning on varieties of codimension two and point-hypersurface incidences in four dimensions, {\it Discrete Comput. Geom.} 55 (2016), 158--184. \bibitem{CEGSW} K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir and E. Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, {\it Discrete Comput. Geom.} 5 (1990), 99--160. \bibitem{DG15} Z. Dvir and S. Gopi, On the number of rich lines in truly high dimensional sets, {\it Proc. 31st Annu. Sympos. Comput. Geom.}, 2015, 584--598. \bibitem{EKS} G. Elekes, H. Kaplan and M. Sharir, On lines, joints, and incidences in three dimensions, {\it J. Combinat. Theory, Ser. A} 118 (2011), 962--977. Also in arXiv:0905.1583. \bibitem{Er46} P. Erd{\H o}s, On sets of distances of $n$ points, {\it Amer. Math. Monthly} 53 (1946), 248--250. % \bibitem{FPSSZ14} J.\ Fox, J.\ Pach, A.\ Sheffer, A.\ Suk, and J.\ Zahl, A semi-algebraic version of Zarankiewicz's problem, {\it J. European Math. Soc.}, to appear. % \bibitem{Gu14} L.\ Guth, Distinct distance estimates and low-degree polynomial partitioning, {\it Discrete Comput. Geom.} 53 (2015), 428--444. Also in arXiv:1404.2321. \bibitem{GK} L. Guth and N. H. Katz, Algebraic methods in discrete analogs of the Kakeya problem, {\it Advances Math.} 225 (2010), 2828--2839. Also in arXiv:0812.1043. \bibitem{GK2} L.\ Guth and N.\ H.\ Katz, On the Erd{\H o}s distinct distances problem in the plane, {\it Annals Math.} 181 (2015), 155--190. Also in arXiv:1011.4105. \bibitem{GZ} L.\ Guth and J.\ Zahl, Algebraic curves, rich points, and doubly ruled surfaces, in arXiv:1503.02173. \bibitem{HS14} M. Hablicsek and Z. Scherr, On the number of rich lines in high dimensional real vector spaces, {\it Discrete Comput. Geom.} 55 (2016), 955--962. % \bibitem{Har} % J.\ Harris, % {\it Algebraic Geometry: A First Course}, % Vol. 133. Springer-Verlag, New York, 1992. \bibitem{KMSS} H. Kaplan, J. Matou\v{s}ek, Z. Safernov\'a and M. Sharir, Unit distances in three dimensions, {\it Combinat. Probab. Comput.} 21 (2012), 597--610. Also in arXiv:1107.1077. \bibitem{KMS} H. Kaplan, J. Matou\v{s}ek and M. Sharir, Simple proofs of classical theorems in discrete geometry via the Guth--Katz polynomial partitioning technique, {\it Discrete Comput. Geom.} 48 (2012), 499--517. Also in arXiv:1102.5391. % \bibitem{Mat02} J.\ Matou\v sek, {\it Lectures on Discrete Geometry}, Springer Verlag, Heidelberg, 2002. % \bibitem{NS12} F. Nilov and M. Skopenkov, A surface containing a line and a circle through each point is a quadric, {\it Geometria Dedicata} 163.1 (2013), 301--310. % \bibitem{PS98} J.\ Pach and M.\ Sharir, On the number of incidences between points and curves, {\it Combinat.\ Probab.\ Comput.} 7 (1998), 121--127. % \bibitem{PS} J. Pach and M. Sharir, Geometric incidences, in {\it Towards a Theory of Geometric Graphs} (J. Pach, ed.), {\it Contemporary Mathematics}, Vol. 342, Amer. Math. Soc., Providence, RI, 2004, pp. 185--223. \bibitem{SSZ} M. Sharir, A. Sheffer, and J. Zahl, Improved bounds for incidences between points and circles, {\it Combinat. Probab. Comput.} 24 (2015), 490--520. Also in {\it Proc. 29th ACM Symp. on Computational Geometry} (2013), 97--106, and in arXiv:1208.0053. % \bibitem{SS14} M.\ Sharir and N.\ Solomon, Incidences between points and lines in four dimensions, {\it Proc.\ 30th ACM Sympos.\ on Computational Geometry} (2014), 189--197. % \bibitem{SS4d} M.\ Sharir and N.\ Solomon, Incidences between points and lines in $\reals^4$, {\it Proc. 56th IEEE Symp. on Foundations of Computer Science} (2015), 1378--1394. Also in arXiv:1411.0777. \bibitem{SS3d} M.\ Sharir and N.\ Solomon, Incidences between points and lines in three dimensions, in {\it Intuitive Geometry} (J. Pach, Ed.), to appear. Also in {\it Proc.\ 31st ACM Sympos.\ on Computational Geometry} (2015), 553--568, and in arXiv:1501.02544. \bibitem{SZ16} M.\ Sharir and J.\ Zahl, Cutting algebraic curves into pseudo-segments and applications, in arXiv:1604.07877. % \bibitem{SS3dv} % M. Sharir and N. Solomon, % Incidences between points and lines on a two-dimensional variety in three dimensions, % {\it Combinatorica}, submitted, and in arXiv:1501.01670. % \bibitem{ST11} J.\ Solymosi and T.\ Tao, An incidence theorem in higher dimensions, {\it Discrete Comput. Geom.} 48 (2012), 255--280. \bibitem{SST} J. Spencer, E. Szemer\'edi and W.T. Trotter, Unit distances in the Euclidean plane, In: \emph{Graph Theory and Combinatorics} (B. Bollob\'as, ed.), Academic Press, New York, 1984, 293--303. \bibitem{Sz} L.~Sz{\'e}kely, Crossing numbers and hard Erd{\H o}s problems in discrete geometry, {\it Combinat. Probab. Comput.} 6 (1997), 353--358. \bibitem{SzT} E. Szemer\'edi and W.T. Trotter, Extremal problems in discrete geometry, {\it Combinatorica} 3 (1983), 381--392. \bibitem{T} T. Tao, From rotating needles to stability of waves: Emerging connections between combinatorics, analysis, and PDE, {\it Notices AMS} 48(3) (2001), 294--303. % % \bibitem{Warren68} % H.\ E.\ Warren, % Lower bound for approximation by nonlinear manifolds, % {\it Trans. Amer. Math. Soc.} 133 (1968), 167--178. % \bibitem{Za1} J.\ Zahl, An improved bound on the number of point-surface incidences in three dimensions, \emph{Contrib. Discrete Math.} 8(1) (2013), 100--121. Also in arXiv:1104.4987. \bibitem{Za2} J.\ Zahl, A Szemer\'edi-Trotter type theorem in $\reals^4$, {\it Discrete Comput. Geom.} 54 (2015), 513--572. Also in arXiv:1203.4600. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \bibitem{CLO} % D. Cox, J. Little and D. O'Shea, % {\it Ideals, Varieties, and Algorithms: % An Introduction to Computational Algebraic Geometry and Commutative Algebra,} % Springer Verlag, Heidelberg, 2007. % % \bibitem{CLO2} % D. Cox, J. Little and D. O'Shea, % {\it Using Algebraic Geometry}, % Springer Verlag, Heidelberg, 2005. % % \bibitem{El} % G. Elekes, % Sums versus products in number theory, algebra and Erd{\H o}s geometry--A survey, % in {\it Paul Erd{\H o}s and his Mathematics} II, % Bolyai Math. Soc., Stud. 11, Budapest, 2002, pp.~241--290. % \bibitem{Fu84} % W.~Fulton, % {\it Introduction to Intersection Theory in Algebraic Geometry}, % Expository Lectures from the CBMS Regional Conference Held at % George Mason University, June 27--July 1, 1983, Vol. 54. AMS Bookstore, 1984. \end{thebibliography} \end{document}