Question

Hello,

I don't know if this question has already been posted, I have made a little search with keywords and did not found it, sorry if I missed anything.

Is it possible to characterize the set of pairs of integers ($l$,$i$) such that one can draw $l$ lines on the euclidean plane with exactly $i$ intersection points?

It is quite trivial to see is that given $l$, an upper bound for $i$ is $l(l+1)/2$. More generally, given $l$, any additive decomposition of $l$ of the form $\underset{j=1}{\overset{k}{\sum}} l_i$ provides a value for $i$ which is $\underset{i=1}{\overset{k}{\sum}} $ $\underset{j>i}{\overset{k}{\sum}} l_i l_j$ if we fix for any $i \in [1,k]$ exactly $l_i$ parallel lines such that there is no intersection of three or more lines at the same point.

It is not difficult to see that there are pairs ($l$,$i$) that are not of this form. For instance, if you try all decompositions of 6, you may draw 6 lines with 5, 8, 9, 11, 12, 13, 14 or 15 intersection points with this method, but 7 and 10 are missing (they can be obtained with intersection points of three lines).

Here is a link containing some observations (http://www.ics.uci.edu/~eppstein/junkyard/how-many-intersects.html). As far as I know, this is the only place where this problem has been seriously considered, but it is quite old and maybe lacks of results. So any additional comment will be welcomed :)

Just a final remark, thanks to some projective properties, this question is the same as finding $c$ circles sharing a common point with exactly $i+1$ intersection points. Don't know if this can help.

Answer 1

I asked Jon Lenchner, an expert on point-line incidences, and he told me the question (in dual form) was posed in Grünbaum's 1971 book Arrangements and Spreads, and fully answered in a paper by Peter Salamon and Paul Erdős: "The solution to a problem of Grünbaum," Canad. Math. Bull. 31: 129-138 (1988). Here are its first two sentences:

In the paper below we characterize for large $n$ the possible values of the number of connecting lines determined by a set of $P_n$ points in the plane, where a connecting line is any straight line containing at least two points of $P_n$. This solves a problem posed by Grünbaum [5,6] which asks for the sequence of all integers $m$ with the property that some configuration of $n$ points determine exactly $m$ lines.

([6] is Arrangements and Spreads; [5] is Erdős's earlier partial solution.) They obtain exact expressions "for the lower end of the continuum of values leading down from $\binom{n}{2}-4$." "The possible values...can be seen to bear a strong resemblance to physical spectra." The lower end of the continuum grows as $n^{3/2}$ (with constant 1). Here are two figures from the paper: