Incidence Lower Bounds for Dense Points and Lines

Definitions and mathematical statement

Let $n\geq 2$ be an integer and let $P\subset{\mathbb{R}}^2$ satisfy \[ |P|=n,\qquad \min_{\substack{p,q\in P\\p\neq q}}\|p-q\|_2=1. \] Write $K=\operatorname{conv}(P)$ and $\operatorname{diam}(P)=\max_{p,q\in P}\|p-q\|_2$. The supplied density hypothesis is $\operatorname{diam}(P)=O(\sqrt n)$. Let $L$ be a set of $n$ affine lines in ${\mathbb{R}}^2$. For a point $p$ and a line $\ell$, put \[ \operatorname{dist}(p,\ell)=\inf_{x\in\ell}\|p-x\|_2, \qquad I_n(P,L)=\left|\left\{(p,\ell)\in P\times L:\operatorname{dist}(p,\ell)\leq n^{-1/2}\right\}\right|. \] The source requires the lines to be pairwise essentially different, described as angular separation $1/n$ or disjoint $1/\sqrt n$-neighborhoods inside $K$. Denote this intended pairwise relation by $E_n(\ell,\ell';K)$. This notation is a placeholder: the supplied record does not give an unambiguous complete definition of that relation. In particular, it does not specify the angular convention, the precise threshold inequality, whether the neighborhoods are open or closed, or how lines whose neighborhoods miss $K$ are treated.

Source question. Under these hypotheses, must \[ I_n(P,L)=\Omega(n^{4/3}) \] hold?

A possible uniform interpretation of the asymptotic quantifiers is the following: for every fixed $C>0$, do there exist $c(C)>0$ and an integer $n_0(C)\geq2$ such that, for every integer $n\geq n_0(C)$, every such $P$ with $\operatorname{diam}(P)\leq C\sqrt n$, and every such $L$ with $E_n(\ell,\ell';K)$ for all distinct $\ell,\ell'\in L$, one has \[ I_n(P,L)\geq c(C)n^{4/3}? \] This quantifier convention is explicit but provisional; the record does not specify the dependence of the asymptotic constants. No condition requiring a line or its neighborhood to meet $K$ is supplied. The exact intended question therefore remains unresolved until the essential-difference relation and any missing line-location hypotheses are recovered. The supplied literature assessment concerns a different nerve question and does not substantiate this incidence question.

Short English statement

The supplied question asks whether $n$ separated planar points of diameter $O(\sqrt n)$, together with $n$ suitably distinct lines, must determine $\Omega(n^{4/3})$ point--line pairs at distance at most $n^{-1/2}$. The precise distinction condition for lines and possible line-location assumptions are incomplete. The supplied open-status assessment discusses a different problem.

Sources

• Local UnsolvedMath registry: supplied record with permanent ID $30003476$, title Incidence Lower Bounds for Dense Points and Lines, source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. No individual proposer is named; the supplied proposed year is 2017.
• Supplied report citation: Discrete Geometry (2018), Oberwolfach Reports, pp. 1135--1205, DOI 10.4171/owr/2017/19. Supplied source URL and literature-source link labeled "original OWR report": https://doi.org/10.4171/owr/2017/19. The background describes these reports as documenting mathematical workshops and their open-problem discussions. The report title's year 2018 and the supplied 2017 provenance require bibliographic clarification.
• Supplied literature assessment, checked on 2026-08-21: status "open"; the assessment says that a nerve question is proved only for covers with four members in the cited source, and that no general proof or counterexample for arbitrary $m$ was located. This is supplied dated curation, not independently verified. Its subject does not match the incidence statement, so it cannot establish the literature status of this question. The background itself requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and reports that the official Oberwolfach report was checked directly, with definitions restored and source-dependent wording removed. These are supplied verification claims, not verification performed for this draft. The original statement begins "Let P be as above", leaving its preceding context absent from the supplied original excerpt.