From:           rld@math.ohio-state.edu (Randall Dougherty)
Date:           6 Jun 1996 23:22:35 -0400
Newsgroups:     sci.math
Subject:        Re: Question from the classroom: Geometry

In article <steiner-0406961355200001@steiner.bgsu.edu>,
Ray Steiner <steiner@math.bgsu.edu> wrote:
>Greetings all,
>     I am teaching a course of mathematics for elementary teachers
>and a problem in the text recently asked about some of the possible number
>of distinct points in which 4,5,6,7,8 distinct lines could meet.
>I extended it a bit farther and we found the following results:
>For 4 distinct lines we could get 1,3,4,5 or 6 possible distinct points
>For 5, we could get all integers from 4 to 10.
>For 6, we could get all integers from 5 to 15.
>This led to the following questions:
>We know that n distinct lines can meet in at most n(n-1)/2 distinct
>points. For which n can we get all the integers from n-1 to n(n-1)/2
>as possible numbers of distinct points of intersection?
>How would one attack this problem for general n?

This pattern does not continue forever -- for large n, there is
no configuration of n lines which gives exactly n+1 intersection points.
(I think that this is so for all n > 10, but I have no proof of
this stronger statement.)

Here is a sketch of the proof; the full proof would be rather long.

Suppose we have a configuration of n lines giving n+1 intersection
points.  What is the largest number of lines in the configuration
which are concurrent or parallel?

These two cases will come up so often that it will be easier to move
to the projective plane, where there is no distinction between them.
Of course, this has a cost; instead of just counting intersection
points, we have to count the points and then see how many can
be removed by arranging to have them lie on the "line at infinity"
when converting back to the ordinary plane.  Note the restriction
that the line at infinity cannot be one of the n lines of the
configuration.

If all n lines are concurrent, we only get 1 projective
intersection point, which may be a finite point or a point
on the line at infinity, giving 0 or 1 ordinary intersection points.
If n-1 of them meet at one point but the n'th doesn't, then we get
n-1 additional points from the n'th line, for a total of n;
this gives either n-1 or n finite points.

If the largest number of lines at a point is n-2, then the
(n-1)'th line gives n-2 additional points, of which one may be infinite,
and the n'th line also meets the first n-2 in n-2 points, of which
one may be infinite and one may lie on the (n-1)'th line,
leaving at least n-4 new finite points.  Therefore, there are at least
(n-3)+(n-4) = 2n-7 finite points, which is too many.

Similarly, if the largest number of lines at a point is n-3,
then we get at least (n-4)+(n-5)+(n-6) = 3n-15 finite
intersection points.  Continuing this downward, we see
that, as long as k is large enough that (k-1)(k-2)/2 > n+1,
we will get too many finite intersection points if there
are k lines meeting at a point.  So, in the desired configuration,
the largest number of lines through a particular point is
at most about sqrt(2n).

Next, consider the case where two different points each have
at least d lines passing through them.  One of these lines
might pass through both points, but this still leaves d-1
other lines at each point, which produce (d-1)^2 intersection
points.  Since at most one of the points on each of the
first d-1 lines can be on the line at infinity, we get
at least (d-1)(d-2) finite intersection points.  Therefore,
in the desired configuration, the point with the second-largest
number of lines through it has at most about sqrt(n) such lines.

If one considers three points which each have at least d lines
through them, then, with a substantial amount of extra work,
one can show that there must be at least 3d^2/2 - 6d + 3
finite intersection points.  (This bound isn't quite sharp,
but the leading term is.)  Therefore, in the desired configuration,
every point with at most two exceptions lies on at most D lines,
where D is about sqrt(2n/3).

Now, the n lines give n(n-1)/2 pairs of lines, and each such
pair has an intersection point (finite or infinite).  A point
at which d lines meet takes care of d(d-1)/2 of these pairs.
There are only n+1 finite intersection points, and these
can take care of about (n+1)D(D-1)/2 ~ n^2/3 pairs.
(The two possible exceptionally large intersection points
would only yield about 5n/3 additional pairs.)
How about points on the line at infinity?  The sum of the degrees
(number of lines meeting there) of these points is at
most n, because each configuration line meets the line
at infinity only once.  And we still have the bound D on the
individual degrees.  So a simple optimization argument shows
that the number of pairs with intersection point on the
line at infinity is at most about (n/D)D(D-1)/2 ~ n^(3/2)/sqrt(6).
(Again the two exceptional points only change this bound
by O(n).)  Therefore, the total number of pairs of lines
in the configuration is n^2/3 + o(n^2); since this is
less than n(n-1)/2 for large n, we have a contradiction.
This completes the sketch of proof that no configuration of
n lines gives n+1 intersection points if n is large.

Actually, the argument shows that no configuration of n lines
gives between n+1 and cn intersection points, where c tends
to 3/2 for large n.  I conjecture that, in fact, for large n,
the first attainable number of intersection points
after 0, 1, n-1, and n is 2n-6.

Randall Dougherty                       rld@math.ohio-state.edu
Department of Mathematics,  Ohio State University,  Columbus, OH 43210  USA
"I have yet to see any problem, however complicated, that when looked at in the
right way didn't become still more complicated."  Poul Anderson, "Call Me Joe"

From:           kjellpe@math.uio.no (Kjell Fredrik Rogstad Pettersen)
Newsgroups:     sci.math
Subject:        Re: Question from the classroom: Geometry
Date:           7 Jun 1996 07:17:43 GMT
Organization:   University of Oslo, Norway

[Ray Steiner]

> Of course,they can never meet! Again, I want to know if all numbers
> of intersection points are possible between n-1 and n(n-1)/2 if 
> n>3. For example, 5 lines certainly can meet in 0 or 1 point.
> But they can also have 4,5,6,7,8,9 or 10 distinct intersection points.
> I'm not asking about all possible numbers of intersection points.
> I just want to know if all numbers between n-1 and n(n-1)/2
> are POSSIBLE. 
> Thanks 
> Ray Steiner

I've been looking at this a little bit. It is true for
n=3,4,5,6,7,8,9 while it seems as if it is impossible for 10 lines
to meet in 11 or in 12 points (but they may meet in 9,10,13,..,45
points). In general, I don't believe it is possible for n lines to
meet in n+1 points for n>10. (Which seems simple to proove by
induction if it is prooved for n=10).

Kjell Fredrik Pettersen

From:           Jeff Erickson <jeffe@cs.berkeley.edu>
Date:           Sun, 16 Jun 1996 18:45:26 -0700
Newsgroups:     sci.math
Subject:        Re: Question from the classroom: Geometry

Jerry Grossman wrote:

> Ray Steiner wants to know if all numbers of intersection points are possible
> between n-1 and n(n-1)/2 if  n>3 lines are arranged (in a plane or more
> generally?).

I think Erdos (or somebody else with Erdos number less than two) showed that
(n(n-1)/2) - 1 is impossible.

Some more information about this problem, at least for small n, can be found in
Grunbaum's classic treatise on convex polytopes.  According to the bibliography of
Ziegler's "Lecture Notes on Polytopes", a new edition is in the works.

Another relevant source is Grunbaum's monograph "Arrangements and Spreads".

> ...a friend of mine showed that you can't get 8 lines from 7 points...

A proof of this can be found in Grunbaum.

-- 
Jeff Erickson
jeffe@cs.berkeley.edu
http://www.cs.berkeley.edu/~jeffe