Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. For every sufficiently large nn, Salamon and Erdős [ErSa88] determine the set of integers mm for which some nn points in the plane determine exactly mm lines, which answers the corrected Statement of Problem 606. They sort configurations into bands by kk, the number of points off a largest collinear subset: k=0k=0 gives m=1m=1, and in the kk-th band mm lies between Mmin⁡(k)=k(n−k)−(k2)+1M_{\min}(k)=k(n-k)-\binom k2+1 (the Kelly–Moser lower bound) and Mmax⁡(k)=k(n−k)+(k2)+1M_{\max}(k)=k(n-k)+\binom k2+1. For (k2)≤n−k\binom k2\le n-k the lower bound is attained and every integer in that range occurs except Mmax⁡(k)−1M_{\max}(k)-1 and Mmax⁡(k)−3M_{\max}(k)-3; consecutive bands are disjoint while kk is small, so the spectrum is a union of separated bands there. From the first overlap, in the band k=⌊n+2⌋k=\lfloor\sqrt{n+2}\rfloor, the bands merge into a continuum containing every integer up to (n2)\binom n2 except (n2)−1\binom n2-1 and (n2)−3\binom n2-3, and the paper gives the exact lower end of that continuum, which fixes the best constant c=1c=1 in Erdős's earlier bound cn3/2cn^{3/2}. The paper displays the computed values for 22≤n≤2822\le n\le28 and says its figure may omit values at the lower ends of the high bands. The answer is complete for every n≥n∗n\ge n^*, a threshold the paper does not compute, and that is the limit of the statement: the paper says (p. 137) that its answer to Grünbaum's problem is complete for n≥n∗n\ge n^* and leaves n<n∗n<n^* open, and that the size of n∗n^* is unknown, though the authors expect it to be small. The digest is on the source card.

Acceptance. The site's curator, T. F. Bloom, labels the problem SOLVED and credits Salamon and Erdős [ErSa88] with the complete description (problem page accessed 2026-09-04), which is the reviewed evidence. The paper is refereed: P. Salamon and P. Erdős, The solution to a problem of Grünbaum, Canad. Math. Bull. 31 (1988), no. 2, 129–138, DOI 10.4153/CMB-1988-020-2. Issue no. 2 is the June 1988 issue, and the page's date is the first of that month. The second link is the copy on the Rényi Institute's Erdős page. No independent proof review and no formalization are recorded.