On a projective plane , there are points and lines . Points may or may not lie on lines. Given any two points on the plane, there exists a unique line passing through them. Any two lines intersect at exactly one point; that is, for any two lines on the plane, there is a unique point that lie on both of them.
Suppose P is a set of points and L is a set of lines on a projective plane. A pair ( p , l ) with p ∈ P , l ∈ L is called an incidence if p lies on l . Let I ( n ) be the maximum number of incidences among all P , L such that ∣ P ∣ = ∣ L ∣ = n .
For example, I ( 4 ) = 9 , achieved by having P = { p 1 , p 2 , p 3 , p 4 } , L = { l 1 , l 2 , l 3 , l 4 } , and having the set of incidences
{ ( p 2 , l 1 ) , ( p 3 , l 1 ) , ( p 4 , l 1 ) , ( p 1 , l 2 ) , ( p 2 , l 2 ) , ( p 1 , l 3 ) , ( p 3 , l 3 ) , ( p 1 , l 4 ) , ( p 4 , l 4 ) } .
It can be proven that no configuration can reach more than 9 incidences. Geometrically, the above example can be represented in the following diagram:
However, remember that despite the objects being called points and lines, there is no requirement that they can actually be represented on the standard Euclidean plane.
As it turns out, I ( n ) = Θ ( n c ) for some exponent c ; in other words, there exist constants c , N , C 1 , C 2 > 0 such that for all n > N , we have C 1 ⋅ n c ≤ I ( n ) ≤ C 2 ⋅ n c .
What is the value of ⌊ 1 0 0 0 0 c ⌋ ?
Notation:
⌊
⋅
⌋
denotes the
floor function
.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
The upper bound can be proved much more easily. For every line i , define its n -dimensional incidence vector x i , such that its j th component x i j = 1 if the point j lies on the line i and x i j = 0 otherwise. Now, the constraint that two distinct lines i , k can meet at only one point may be written as j = 1 ∑ n x i j x k j ≤ 1 , ∀ i = k , which in vector notation simply reads x i ⋅ x k ≤ 1 , ∀ i = k . Now compute, ∣ ∣ i ∑ x i ∣ ∣ 2 = i ∑ ∣ ∣ x i ∣ ∣ 2 + i = k ∑ x i ⋅ x k ≤ n 2 + ( n 2 − n ) ≤ 2 n 2 , where the first term in the upper bound follows simply from the fact that there can be at most n points on a line. If we denote the total number of incidences by I ( n ) , then denoting the n dimensional all-1 vector by e n , we have I ( n ) = i ∑ x i ⋅ e n = ( i ∑ x i ) ⋅ e n . Using the Cauchy-Schwartz inequality, I ( n ) 2 = ∣ ( i ∑ x i ) ⋅ e n ∣ 2 ≤ ∣ ∣ i ∑ x i ∣ ∣ 2 ∣ ∣ e n ∣ ∣ 2 ≤ 2 n 2 × n = 2 n 3 . This immediately proves that I ( n ) ≤ 2 n 1 . 5 .
Log in to reply
I wouldn't call that "much easier", but it's another way to put it. It's pretty similar to my method, actually, since x i ⋅ x j ≤ 1 corresponds to line i and line j intersecting only at one point; if I instead considered triples of line, line, point, then I would also get the same condition. And there's also a use of Cauchy-Schwarz, the same as mine. But yes, that's also a way to prove the upper bound.
Problem Loading...
Note Loading...
Set Loading...
To give an idea of some bounds, let's quickly sketch some simple ones:
As it turns out, the answer is c = 2 3 , precisely in the middle. We will give a proof.
First, we show c ≤ 2 3 . Surprisingly, this is not very difficult, although the ideas might not come easily. The idea is to double-count the number of pairs of points incident to the same line, putting an upper bound on it and converting it to an upper bound on the number of incidences.
Let d i be the number of points of P incident to the i -th line. Note that the total number of incidences S is then ∑ d i . Thus if we can bound ∑ d i from above, we also obtain the same bound for I ( n ) .
Let's consider triples { p 1 , p 2 , l } where p 1 , p 2 ∈ P and l ∈ L , such that p 1 , p 2 lie on l (that is, they are incident to l ). We will count the number of such triples, call it N .
On one hand, it's easy to do this: for each line l i , it has d i points lying on it. We can pick any two points to obtain a triple, so line l i contributes ( 2 d i ) triples. In total, N = ∑ ( 2 d i ) .
On the other hand, we can put an upper bound on this number of triples. We claim that for any two points p 1 , p 2 , they may only appear together in one triple. Indeed, suppose there are two triples { p 1 , p 2 , l 1 } , { p 1 , p 2 , l 2 } containing them. Then line l 1 passes p 1 , p 2 , and line l 2 also passes the same points, contradicting that through any two points there exists a unique line (or otherwise any two lines can only intersect at one point). Thus the claim is proven, which means N ≤ ( 2 n ) .
Together, this means ∑ ( 2 d i ) ≤ ( 2 n ) . Multiplying both sides by 2 and collecting terms, we obtain ∑ d i 2 − ∑ d i ≤ n ( n − 1 ) . Using QM-AM inequality (note that d i ≥ 0 for all i ), we know ∑ d i 2 ≥ n 1 ( ∑ d i ) 2 , thus we have
∑ d i 2 − ∑ d i n 1 ( ∑ d i ) 2 − ∑ d i n 1 S 2 − S S 2 − n S ≤ n ( n − 1 ) ≤ n ( n − 1 ) ≤ n ( n − 1 ) ≤ n 3 − n 2
If you're familiar with Big O notation, you can immediately tell that S 2 = O ( n 3 ) and so S = O ( n 3 / 2 ) , giving c ≤ 2 3 . If not, we can also spell it out. Suppose S ≤ C 2 ⋅ n c , as in the statement. Then S 2 − n S ≤ n 3 − n 2 , or S 2 − n S − ( n 3 − n 2 ) ≤ 0 . We can solve the quadratic inequality to obtain that
S ≤ 2 n + n 2 + 4 ( n 3 − n 2 ) = 2 n ⋅ ( 1 + 4 n − 3 )
Now, to obtain a concrete (if weak) C 2 , we can weaken the inequality:
S ≤ 2 n ⋅ ( 1 + 4 n − 3 ) ≤ 2 n ⋅ 2 4 n − 3 ≤ 2 n ⋅ 2 4 n = 2 n 3 / 2
The second line is because 4 n − 3 ≥ 1 for n ≥ 1 . The third line is because 4 n ≥ 4 n − 3 for all n . So we can take N ≥ 1 , C 2 = 2 .
It remains to prove the lower bound. To do this, we need to exhibit an example.
There are objects called finite projective planes , in which the numbers of points and lines are finite. These are almost like our P , L , except that it's required that every pair of points do actually have a line passing through it, and every pair of lines do actually have a point in common. There is a construction that, given prime p , can produce a finite projective plane with p 2 + p + 1 points and p 2 + p + 1 lines, with each point lying on p + 1 lines (and each line passing through p + 1 points); such plane is called a finite projective plane of order p .
We will first outline the construction, then we will prove that this gives a lower bound. The construction needs some knowledge in linear algebra; if you want to accept the existence of this finite projective plane without needing any proof, you can skip down to the proof of this being a lower bound for I ( n ) .
The construction can be obtained from linear algebra. Let F p be the field of p elements (we can take this as the integers modulo p , with the usual addition and multiplication). We consider F p 3 , formed by triples of elements in F p . Let P be the set of 1-dimensional subspaces and L be the set of 2-dimensional subspaces of F p 3 , and p ∈ P and l ∈ L are incident exactly when p ⊂ l . We claim that:
The first point is relatively easy. There are p 3 − 1 elements of F p 3 other than ( 0 , 0 , 0 ) . Each 1-dimensional subspace contains ( 0 , 0 , 0 ) and p − 1 other elements. Each element is contained in exactly one 1-dimensional subspace. Thus there are p − 1 p 3 − 1 = p 2 + p + 1 1-dimensional subspaces, so ∣ P ∣ = p 2 + p + 1 . To prove ∣ L ∣ = ∣ P ∣ , just note that each 2-dimensional subspace is normal to exactly one 1-dimensional subspace, so we can make a bijection between 1-dimensional subspaces and 2-dimensional subspaces.
The second point is also pretty simple. To prove each line is incident to exactly p + 1 points, simply note that a 2-dimensional subspace has p 2 − 1 nonzero elements, so it contains p − 1 p 2 − 1 = p + 1 1-dimensional subspaces, so a line contains p + 1 points. Proving the other part uses the normality as well: each 1-dimensional subspace x is normal to a 2-dimensional subspace x T , which contains p + 1 1-dimensional subspaces y T , each of which is normal to a 2-dimensional subspace y . Because y T ⊂ x T , we have x ⊂ y , so each point x is incident to p + 1 lines y .
The third point can be shown using linear algebra again. If we have two different 1-dimensional subspaces, they together span a 2-dimensional subspace. So any two distinct points span a single line, and so there exists exactly one line that contains two points. Again, the other part uses normality; this is left as an exercise to the reader.
Thus we have shown that for any prime p , there exists a finite projective plane of order p . We will now show that this will give a lower bound for I ( n ) .
Since there are p 2 + p + 1 points and each point is incident to p + 1 lines, there are ( p 2 + p + 1 ) ( p + 1 ) incidences in total. Since p + 1 ≥ p 2 + p + 1 , there are at least ( p 2 + p + 1 ) 3 / 2 incidences. So if there are n points where n = p 2 + p + 1 , we have at least n 3 / 2 incidences: take P , L as given by the finite projective plane.
Unfortunately we need that n is indeed in the form p 2 + p + 1 . However, we can take the largest prime p so that p 2 + p + 1 ≤ n ; now, for p 2 + p + 1 points of them, we put them as in the finite projective plane, while we just throw away the remaining points and lines (put them arbitrarily, no need to make any incidences).
We will now make a formal proof that this is in fact good enough. Assume that n ≥ 6 4 = 4 3 . Let k be an integer such that 4 k ≤ n < 4 k + 1 ; by the above, we have k ≥ 3 . By Bertrand's postulate , there exists a prime p such that 2 k − 1 < p < 2 k − 1 (because 2 k − 1 ≥ 4 ). Since p 2 < p 2 + p + 1 < ( p + 1 ) 2 , we have 4 k − 1 < p 2 + p + 1 < 4 k . Since 4 k ≤ n and 4 k − 1 = 1 6 1 4 k + 1 > 1 6 1 n , we have 1 6 1 n < p 2 + p + 1 < n .
Let s = p 2 + p + 1 and S be the number of incidences. Since s < n , we can indeed construct a finite projective plane of order p from our n points, so we obtain at least s 3 / 2 incidences; that is, S ≥ s 3 / 2 . Since s > 1 6 1 n , we have S ≥ s 3 / 2 > 6 4 1 n 3 / 2 . Thus S ≥ 6 4 1 n 3 / 2 . And by definition, I ( n ) ≥ S , so we can take N ≥ 6 4 , C 1 ≥ 6 4 1 in our claim above.
The two results above are summarized here:
Thus, we can take c = 2 3 , N = 6 4 , C 1 = 6 4 1 , C 2 = 2 into the problem. This proves that c = 2 3 = 1 . 5 0 0 0 or I ( n ) = Θ ( n 3 / 2 ) .
Note that we have been working on projective planes. Can our construction actually be exhibited on the standard Euclidean plane? The answer turns out to be no. And in fact, on the Euclidean plane we have an even lower exponent: there are at most Θ ( n 4 / 3 ) incidences (and this can be achieved in some configurations). This is Szemerédi–Trotter theorem ; the proof is not very difficult, but it needs some bright ideas. Note that this problem proves that finite projective planes of large order (order greater than 1, in fact) cannot be realized on the Euclidean plane, since we get Θ ( n 3 / 2 ) incidences in that plane but we know that on the Euclidean plane we cannot have more than O ( n 4 / 3 ) incidences.