Status
On this page
Status
Topics
Status
On this page
Status
Topics
Given any points in , the number of -rich lines (lines which contain of the points) is, provided ,
Given any points in , the number of -rich lines (lines which contain of the points) is, provided ,
Source: erdosproblems.com/1069
An accepted solution exists. The statement is true.
The site labels the problem SOLVED and credits Szemerédi and Trotter (1983); the label and the commentary describe the corrected Statement. Proved: Theorem 2 of Szemerédi and Trotter (Combinatorica 3 (1983), 381--392, refereed) gives fewer than lines with at least of the points for every ; see the claim page (Szemerédi and Trotter, 1983).
The site's wording (page last edited 2 October 2025) fails at , which its range admits for every : every line through one of the points is -rich, so there are infinitely many -rich lines and no bound holds. The failure is this page's own elementary check, and it is the only one: at each -rich line is determined by two of the points, so there are at most of them. The change inserts "" before ""; the upper end is Erdős's print and stays. The defect is already in the poser's text: Erdős [Er87b, Section 2, p. 169] states the conjecture of Croft, Purdy and Erdős "for ", with no lower end, and in the next sentence reports it "proved by Szemerédi and Trotter". Szemerédi and Trotter state their Theorem 2 for (p. 382) and restate and prove it for (p. 389), the form inserted here. That range is used because two sources corroborate it as the problem's form: Erdős's own report that the theorem settles the conjecture, and the site's curator, whose label SOLVED and commentary ("This is true, and was proved by Szemerédi and Trotter [SzTr83]") read the statement as the theorem proves it. The same range is also exactly the exclusion of the one value, , at which no finite count is possible. The form was fixed from Erdős's report, the site's reading and the exclusion of , not from the theorem's hypothesis range alone. No result concerns the site's wording alone.