On some points-and-lines problems and configurations
- PDF / 227,531 Bytes
- 16 Pages / 595 x 842 pts (A4) Page_size
- 32 Downloads / 235 Views
SOME POINTS-AND-LINES PROBLEMS AND CONFIGURATIONS Noam D. Elkies (Cambridge) Department of Mathematics, Harvard University, Cambridge, MA 02138, USA E-mail: [email protected] (Received: October 17, 2005; Accepted: December 20, 2005)
Abstract We apply an old method for constructing points-and-lines configurations in the plane to study some recent questions in incidence geometry.
What are known as “Points and Lines” puzzles are found very interesting by many people. The most familiar example, here given, to plant nine trees so that they shall form ten straight rows with three trees in every row, is attributed to Sir Isaac Newton, but the earliest collection of such puzzles is, I believe, in a rare little book that I possess—published in 1821— Rational Amusement for Winter Evenings, by John Jackson. The author gives ten examples of “Trees planted in Rows.” These tree-planting puzzles have always been a matter of great perplexity. They are real “puzzles,” in the truest sense of the word, because nobody has yet succeeded in finding a direct and certain way of solving them. They demand the exercise of sagacity, ingenuity, and patience, and what we call “luck” is also sometimes of service. —H. E. Dudeney, Amusements in Mathematics (1917) [8, p. 56]
Mathematics subject classification number: 52C35 (52C10). Key words and phrases: points-and-lines configurations, points-and-lines problems, orchard problem, incidence geometry. 0031-5303/2006/$20.00 c Akad´ emiai Kiad´ o, Budapest
Akad´ emiai Kiad´ o, Budapest Springer, Dordrecht
134
n. d. elkies
Introduction Almost a century after Dudeney wrote these paragraphs, problems in incidence geometry continue to perplex both recreational and professional mathematicians, and the prospect of a uniform “direct and certain way of solving them” remains remote. Even for natural asymptotic questions, a wide gap often separates the best upper and lower bounds known. In this paper we construct some explicit point-and-line configurations that yield new lower bounds for two specific questions of this kind. Question 1, suggested by the recreational literature, asks: How many lines can meet n2 points in the plane in at least n points each? Question 2 arises in the research literature [3]: If on each of N horizontal lines we choose (at most) N points, how many additional lines can contain N of these N 2 points? It turns out that an arrangement of 16 points in 15 lines of 4 (Figure 1 below), which has been known at least since 1908, naturally generalizes to configurations that not only give lower bounds for Question 1 but also improve on the previous records for Question 2. We also find a variation of this construction that yields a partial answer to Question 1 and a further improvement for the cases N = 12m = 12, 24, 36, . . . and N = 12m − 1 = 11, 23, 35, . . . of Question 2. By the construction in [3], the new results for Question 2 yield, for each N ≥ 5, improved lower bounds on the exponent in the asymptotic “orchard-planting” problem with N -point lines. Each of these arrangements
Data Loading...
