J. Geom. 86 (2006) 154 – 164 0047–2468/06/020154 – 11 © Birkh¨auser Verlag, Basel, 2006 DOI 10.1007/s00022-006-1889-0
How many s-subspaces must miss a point set in PG(d, q) Klaus Metsch
Abstract. The following result is well-known for finite projective spaces. The smallest cardinality of a set of points of PG(n, q) with the property that every s-subspace has a point in the set is (q n+1−s − 1)/(q − 1). We solve in finite projective spaces PG(n, q) the following problem. Given integers s and b with 0 ≤ s ≤ n − 1 and 1 ≤ b ≤ (q n+1−s − 1)/(q − 1), what is the smallest number of s-subspaces that must miss a set of b points. If d is the smallest integer such that b ≤ (q d+1 − 1)/(q − 1), then we shall see that the smallest number is obtained only when the b points generate a subspace of dimension d. We then also determine the smallest number of s-subspaces that must miss a set of b points of PG(n, q) which do not lie together in a subspace of dimension d. The results are obtained by geometrical and combinatorial arguments that rely on a strong algebraic result for projective planes by T. Sz˝ onyi and Z. Weiner. Mathematics Subject Classification (2000): 51E20, 05B25, 51E21. Key words: Finite projective space, blocking set
1. Introduction What is the largest number of s-subspaces a collection of b points in the finite projective space PG(n, q) of order q can meet? The origin of this question is the following problem. For integers n, s, t with −1 < t, s < n and prime-powers q denote by b(s, t, n, q) the smallest cardinality of a set T of t-subspaces of PG(n, q) with the property that every ssubspace of PG(n, q) is incident with at least one element of T . Determine the integers b(s, t, n, q). An overview on this problem is given in [4]. If this problem is attacked in the case t = 1, then the difficulty is to solve the problem of how many s-subspaces through a point contain one of b given lines through that point. Going to the quotient geometry at P , this problem can be formulated as follows: given a set B of b points in a projective space PG(n, q), what is the smallest number of (s − 1)-subspaces that must miss B? For example, if B is a set of b points in PG(3, q) and if q + 1 < b ≤ q 2 + q + 1, what is the smallest number of lines a set of b points can miss. It will be seen that the answer is (q 2 + q + 1 − b)q 2 , and this number can be attained only for sets of b points that are contained in a plane and meet all lines of that plane. At first sight, this seems to be evident, and in fact it is easy to prove unless b is small; so b is close to q + 1. It was impossible to find a proof for all b using geometrical and combinatorial arguments only. The proof given here depends on the following algebraic result proved in [5]. 154
Vol. 86, 2006
How many s-subspaces must miss a point set in PG(d, q)
155
RESULT 1.1. Let B be a set of points of PG(2, q), let P be a point not in B and let r be the number of lines on P that meet B. Then B meets at most 1 + rq + (|B| − r)(q + 1 − r) lines. This statement was conjectured in [4] where it also has been shown that it implies the above mentioned bound (q 2 + q + 1 − b)q 2 in PG(3, q). Note that the bound in the result is sharp. Also, this result implies a famous result of Jamison [3] stating that a blocking set of AG(2, q) has size at least 2q − 1. Finally, the bound in the result is in general not correct for non-desarguesian planes. Result 1.1 will be used to determine in PG(n, q) the smallest number of s-subspaces that can miss a point set of a given cardinality. Here, dn q , for n, d ≥ 0, denotes the number of (d − 1)-subspaces in the finite projective space PG(n − 1, q), see Section 2 for a precise definition. THEOREM 1.2. Let s, d, n be integers with s, d ≥ 1 and n ≥ d + s. Let B be a set of . points of PG(n, q) and suppose that |B| ≤ d+1 1 q
(a) The number of s-subspaces missing B is at least n−d d +1 (s+1)(d+1) n − d q − |B| q sd . + s s+1 q 1 q q (b) Equality holds in (a) if and only if there exists ad-subspace D such that B ⊆ D and d B meets all lines of D (this implies that |B| ≥ 1 ). q
(c) Suppose that the set B generates a subspace of dimension at least d + 1. If |B| > d + 1, then the bound in (a) can be improved by a term 1 q
If |B| =
d (s−1)d n − d − 1 |B| − 1 − q . 1 q s−1 q
d 1 q
+ 1, then the bound in (a) can be improved by a term (q d−1 − 1)q (s−1)d
n−d −1 s−1
. q
REMARKS (1) For a given set B,the best when d is chosen as the bound in (a) is obtained d+1 d smallest integer satisfying |B| ≤ 1 . In fact, if |B| ≤ 1 , then the difference in the q
q
156
Klaus Metsch
J. Geom.
bounds in (a) when applied for d − 1 and d is d s(d−1) n − d − |B| . q s−1 q 1 q (2) The number obtained with the improvement of part (c) is not necessarily the second smallest number of s-subspaces which can miss a set of |B| points. In fact, if s+1 d +1 d − , < |B| ≤ 1 1 1 q q q then B can can be contained in a subspace D of dimension d such that not all s-subspaces of D meet B. For example, in the case when s = 1, the improvement in (c) is |B| − 1 − d1 . q But, for d +1 d + q d−1 − 2 ≤ |B| ≤ − q − 1, 1 1 q q a configuration for B inside a d-subspace D exists such that all lines except exactly one of D meet B; so the number of lines missing B is just one larger than the number of the statement of part (a). (3) The theorem also implies that the smallest number of points in a set of PG(n, q) meeting and only the point sets of subspaces of codimension s meet the all s-subspaces is n−s+1 1 q bound. This result is due to Bose and Burton [1]. 2. Proof of the main theorem Let n q be a fixed prime power for the rest of the paper. For integers n, d ≥ 0 we denote by d the number of (d − 1)-subspaces of PG(n − 1, q). Some values, including the ones reflecting degenerate situations, are n n n n qn − 1 . = = 1, = 0 if d > n, = q −1 n 0 d 1 We also put d := d+1 1 , which is the number of points of PG(d, q). The following result is a special case of many known theorems; see, for example, [2]. RESULT 2.1. Let d and n be integers with n ≥ 2 and n ≥ d ≥ 0. Suppose that B is a √ set of points meeting every subspace of dimension n − d. If |B| < d + qq d−1 , then B contains a d-subspace. We start the proof of the main theorem with the following lemma. The crucial part consisting of the application of Result 1.1 is in Proposition 2.3. Lemma 2.4 handles the situation when s = 1. Finally we solve the general case using an inductive argument.
Vol. 86, 2006
How many s-subspaces must miss a point set in PG(d, q)
157
LEMMA 2.2. Let d and n be integers with 1 ≤ d ≤ n. Let B be a set of more than d−1 points of PG(n, q). (a) The number of points that lie on no secant of B is at most n − d with equality if and only if B generates a subspace of dimension d. (b) If at least n − d − q points do not lie on a secant of B, then B generates a subspace of dimension d. (c) If B meets more than d +1 + |B|(n−1 − d−1 ) − (|B| − d−1 ) 2 lines, then there exist at least n − d − q points outside B that lie on more than d−1 lines that meet B. Proof. (a) If B generates a subspace D of dimension d, then |B| > d−1 implies that every point of D lies on a secant of B, so exactly n − d points lie on no secant of B. Conversely, suppose that at least n − d points lie on no secant of B. Let M be the set consisting of all points that lie on a secant of B. Then B ⊆ M and |M| ≤ d . If S is any subspace of dimension n − d, then |B| > d−1 implies that some subspace of dimension n − d + 1 on S meets B in more than one point. Hence some point of S lies on a secant of B. This shows that M meets every subspace of dimension n − d. As |M| ≤ d , Result 2.1 shows that M is a subspace of dimension d. As B ⊆ M, the lemma is proved. (b) This is easy for d = 1, so suppose that d ≥ 2. Define the set M as in part (a). As before, B ⊆ M, and M meets every subspace of dimension n−d. However, this time |M| ≤ d +q. As d ≥ 2, Result 2.1 shows that M contains a d-subspace S. Assume that B is not a subset of S. Then let P ∈ B \ S. As |M| ≤ d + q, at least |B| − q ≥ d−1 + 1 − q ≥ 2 points of B lie in S. Hence P lies on at least two secants, so at least 2q − 1 points outside S lie on a secant of B. But |M| ≤ d + q and S ⊆ M, a contradiction. (c) Let C be the set of lines meeting B. Each point of B lies on n−1 lines of C. Suppose that s of the n − |B| points outside B lie on more than d−1 lines of C. As these lie on at most |B| lines that meet C, a double counting gives |B|n−1 + (n − |B| − s)d−1 + s|B| ≥ |C|(q + 1). Using the lower bound for |C|, this gives s(|B| − d−1 ) > (n − d − q − 1)(|B| − d−1 ). As |B| > d−1 , the assertion follows.
158
Klaus Metsch
J. Geom.
PROPOSITION 2.3. Let B be a set of points of PG(n, q), let P be a point outside B and denote by r and s respectively the number of lines and planes on P that meet B. Then the number of lines that meet B is at most s + |B|q n−1 + (|B| − r)(n−2 − r). Proof. Let l1 , . . . , lr be the lines and π1 , . . . , πs the planes on P that meet B. Put bi := |πi ∩ B| and let ri be the number of lines lj that are contained in πi . Result 1.1 shows that at most 1 + ri q + (bi − ri )(q + 1 − ri ) lines of πi meet B. Thus, a part from the ri lines of πi through P , at most 1 + ri (q − 1) + (bi − ri )(q + 1 − ri ) further lines of πi meet B. Thus B meets at most A := r +
s
[1 + ri (q − 1) + (bi − ri )(q + 1 − ri )]
i=1
lines. Put b := |B|. From the definitions we have rn−2 =
s
ri and bn−2 =
i=1
s
bi .
i=1
It follows that A = s + bq n−1 + (b − r)(2n−2 − 1) −
s
(bi − ri )ri .
i=1
Put |lj ∩ B| = 1 + kj with kj ≥ 0. Then b − r = s
(bi − ri )ri =
s i=1 j :lj ⊆πi
i=1
=
(bi − ri ) =
r
j =1 kj .
r
Hence
(bi − ri )
j =1 i:lj ⊆πi
r
b − r + (n−2 − 1)kj = (b − r)(r + n−2 − 1).
j =1
It follows that A = s + bq n−1 + (b − r)(n−2 − r).
LEMMA 2.4. Let d and n be integers with 1 ≤ d ≤ n. Let B be a set of at most d points of PG(n, q). (a) B meets at most d+1 + |B|(n−1 − d−1 ) lines. Equality holds if and only if B 2 is contained in a subspace of dimension d and meets all lines of this subspace (this implies that |B| ≥ d−1 ).
Vol. 86, 2006
How many s-subspaces must miss a point set in PG(d, q)
159
(b) Suppose that B generates a subspace of dimension at least d +1. If |B| > d−1 +1, then the bound in (a) can be improved by a term |B| − 1 − d−1 . If |B| = d−1 + 1, then the bound in (a) can be improved by a term q d−1 − 1. Proof. First notice that the assertions are trivial for d = n. Suppose next that d = 1. Then the number in part (a) is the number of lines meeting a set B of collinear pints, 1 ≤ |B| ≤ q +1. If B is a set of b ≤ q +1 non-collinear points, then three non-collinear points of these b points together meet 3(n−1 − 1) lines, and every further point lies on at most n−1 − 2 lines that have not yet been counted. This gives 3(n−1 − 1) + (b − 3)(n−1 − 2) lines, proving (b) in the case d = 1. Hence, the proposition is true when n = d or d = 1. This implies that the proposition is true for n = 1 and n = 2. Suppose now that n ≥ 3 and d ≥ 2. Using induction on n + d, we may assume that the assertions in (a) and (b) are true for pairs (n , d ) with n ≤ n and d ≤ d and (n, d) = (n , d ). (a) If |B| ≤ d−1 , then the assertions of (a) follows from the induction hypothesis with n and d − 1. We may thus assume that |B| > d−1 . If no point outside B lies on more than d−1 lines that meet B, then Lemma 2.2 (c) proves the proposition. We may thus assume that there exists a point P outside B that lies on r > d−1 lines that meet B. Let s be the number of planes on P that meet B. Applying the induction hypothesis to the quotient geometry at P we see that d +1 s≤ + r(n−2 − d−1 ). (1) 2 Hence, if A is the number of lines meeting B, then Proposition 2.3 shows that A ≤ A0 + (|B| − r)(d−1 − r),
with A0 :=
d +1 + |B|(n−1 − d−1 ). 2
As r > d−1 , then (|B| − r)(d−1 − r) ≤ 0 and thus A ≤ A0 . Thus B meets at most A0 lines. Suppose that we have equality. Then (|B| − r)(d−1 − r) = 0, that is b = r, which means that P lies on no secant of B. Similarly, every point outside B that lies on more than d−1 lines that meet B lies on no secant of B. Thus parts (b) and (c) of Lemma 2.2 imply that B generates a subspace of dimension d. Clearly, the statement in (a) holds for sets B that are contained in a d-subspace. (b) First consider the case when d−1 + 1 < |B| ≤ d . We assume that B meets at least A0 − (|B| − 1 − d−1 ) lines and we shall show that equality holds. As B generates a subspace of dimension at least d + 1, parts (b) and (c) of Lemma 2.2 imply that there exists a point P outside B such that the number r of lines on P that meet B satisfies r ≥ d−1 + 1 and such that P lies on a secant of B. Then d−1 + 1 ≤ r ≤ |B| − 1. Hence
160
Klaus Metsch
J. Geom.
(|B| − r)(r − d−1 ) ≥ |B| − 1 − d−1 and the arguments of the proof of part (a) give the desired improvement. Now consider the case when |B| = d−1 + 1. As B generates a subspace of dimension at least d + 1, we must have d ≥ 2. Clearly B is not a subspace, so we find a point P outside B that lies on a secant of B. If r and s are respectively the number of lines and planes on P that meet B, then r ≤ |B| − 1 ≤ d−1 . Clearly r ≥ |B|/q > d−2 . Now we apply the induction hypothesis with n − 1 and d − 1 to the quotient geometry at P , taking into account that the lines on P that meet B considered as points in the quotient geometry generate a subspace of dimension at least d (since B generates a subspace of dimension at least d + 1). Hence the induction hypothesis shows that (use part (a) of the induction hypothesis when r = d−2 + 1 and use part (b) for larger r) d s≤ + r(n−2 − d−2 ) − (r − 1 − d−2 ). 2 Combining this with Proposition 2.3 gives A ≤ A0 − (d−1 + 1 − r)(r − 1 − d−2 ) with A and A0 as in the proof of (a). If d−2 + 2 ≤ r, this implies A ≤ A0 − (q d−1 − 1) as desired (remember that r ≤ d−1 ). Hence we are left with the case when r = d−2 + 1. Similarly, we may assume that every point that lies on a secant of B lies on exactly d−2 +1 lines that meet B. Let t be the number of points outside B that lie on no secant of B. Let L be the set consisting of all lines that meet B. Count incident pairs (P , l) with points P and lines l ∈ L. The points of B lie on n−1 lines of L, exactly t points lie on |B| lines of L, and the remaining points lie on d−2 + 1 lines of L. Hence |B|n−1 + t|B| + (n − |B| − t)(d−2 + 1) = |L|(q + 1).
(2)
From Lemma 2.2 we have t ≤ n − d . Using this upper bound for t and using |B| = d−1 + 1, equation (2) implies that (|L| − A0 )(q + 1) ≥ (q d−1 − 1)(q d − 1). As d ≥ 2, then q d − 1 ≥ q + 1, and hence |L| ≤ A0 − (q d−1 − 1).
REMARK. Suppose in the situation of the above proposition that there exists a point P outside B such that the number r of lines on P that meet B satisfies d−1 < r < |B|. Suppose also that d−1 < |B| ≤ d . Then the above proof shows that the bound Lemma 2.4 (a) can be improved by a term (|B| − r)(r − d−1 ). Proof of Theorem 1.2 We use induction on s to prove the theorem. The case s = 1 has been handled in Lemma 2.4, so we suppose from now on that s ≥ 2 and that the assertions of the theorem hold for s − 1.
Vol. 86, 2006
How many s-subspaces must miss a point set in PG(d, q)
161
Proof of parts (a) and (b) The first term in the formula of Theorem 1.2 (a) is the number n−d sd is the number of s-subspaces that are skew to a given d-subspace. The term q s of s-subspaces that meet a given d-subspace in a given point. Hence, if B is contained in an d-subspace D, then the number of s-subspaces missing B is at least the one given in Theorem 1.2 (a) with equality, if B meets every line of D (since otherwise there are s-subspaces missing B and meeting D in more than one point). This proves one direction of part (b) of Theorem 1.2. Now let B be arbitrary. For every point P not in B, denote by bP the number of lines on P meeting B, and by sP the number of s-subspaces on P missing B. The induction hypothesis applied to the quotient geometry at P gives d +1 (s−1)d n − d − 1 s(d+1) n − 1 − d sP ≥ q . (3) + − bP q s−1 s 1 If L is the set of lines meeting B, then bP = (q + 1 − |l ∩ B|) = |L|(q + 1) − |B|n−1 . P ∈B /
(4)
l∈L
Lemma 2.4 shows that
d +1 |L| ≤ + |B|q d n−d−1 2
(5)
with equality if and only if B is contained in a subspace D of dimension d and meets all lines of this subspace. Thus, if we have equality here, then every point P ∈ D \ B lies on d−1 lines meeting B, so the induction hypothesis shows that (3) holds with equality for points P ∈ D \ B; also for P ∈ / D the induction hypothesis shows that (3) holds with equality for P .
The number x of s-subspaces missing B satisfies xs = P ∈B / sP . Putting all together we find a lower for x. Our argument shows that the bound is attained only if B lies in a d-subspace D and meets all lines of D. Without doing the calculation we know that the lower bound is the one stated in part (a), since we have seen in the beginning of the proof that the bound in part (a) holds with equality for a set B contained in a d-subspace and meeting all lines of the d-subspace. This proves (a) and (b) of Theorem 1.2. Proof of part (c) when dim B = d + 1. By part (b) of Lemma 2.4, we can improve the bound (5) for |L| by a term where
:=
b − 1 − d−1 if |B| > d−1 + 1, q d−1 − 1 if |B| = d−1 + 1.
162
Klaus Metsch
J. Geom.
This will improve the bound in Theorem 1.2 (a) by a term (the following coefficient of is the coefficient of |L| in the lower bound for x obtained in the above proof) 1 (s−1)d n − d − 1 . (6) (q + 1)q s s−1 Each point P outside B satisfies bP = |B|, and part (c) of Theorem 1.2 applied to the quotient geometry at such points P , improves the bound (3) for sP by the term (s−2)d n − d − 2 q . (7) s−2 For the contribution of this to the improvement of the bound on x we have to divide by s ,
since xs = sP . Thus, the improvement for x coming from the n − d+1 points P outside B is 1 (s−2)d n − d − 2 . (8) (n − d+1 )q s−2 s Adding (6) and (8) gives the term of Theorem 1.2 (c). Proof of part (c) when dim B ≥ d + 2 and |B| = d−1 + 1. Now, the bound sP of (3) can be improved for all points P outside B, since B seen in the quotient geometry on P is not contained in a d-subspace! The improvement comes from the induction hypothesis for 1.2(c). If bP = |B| = d−1 + 1, then the improvement is (s−2)d n − d − 2 q (9) s−2 where again = q d−1 − 1 (see Theorem 1.2 applied for n − 1, d, s − 1). For points P with bP ≤ |B| − 1 ≤ d−1 , we show that the improvement is d q (s−1)(d−1) n−d−1 + bp − 1 − d−1 q (s−2)(d−1) n−d−1 s−2 1 − bP 1 s−2 d (s−2)(d−1) n−d−1 = − 1 − b q P 1 s−2 d (s−2)d n−d−2 ≥ 1 − 1 − bP q s−2 ≥ q (s−2)d n−d−2 . s−2 The first term on the left hand side comes from Remark (1) in the introduction applied with n−1, d, s −1, and the second term on the left hand side comes from Theorem 1.2(c) applied with n − 1, d − 1, s − 1. Hence for all points outside B we can improve the bound (3) on sP by the term in (9). The arguments of the case dim B = d + 1 thus prove the assertion.
Vol. 86, 2006
How many s-subspaces must miss a point set in PG(d, q)
163
Proof of part (c) when dim B ≥ d + 2 and |B| ≥ d−1 + 2. Again we can improve the bound (3) on sP for all points P outside B. The improvement on the bound on sP is n−d −2 (bP − 1 − d−1 )q (s−2)d s−2 and comes from Theorem 1.2 (c) applied to the quotient at P . Note that this holds trivially / B to the improvement when bP < d−1 +2. Instead of (8) the contribution of all points P ∈ of lower bound x for the number of s-subspaces missing B is 1 n−d −2 . (10) (bP − 1 − d−1 )q (s−2)d s−2 s P ∈B /
For the improvement (6) in the case when dim B = d + 1 coming for the better bound for |L|, we are more careful now, and put d +1 |L| = + |B|q d n−d−1 − − λ (11) 2 with λ ≥ 0, so that we can replace (6) by
1 (s−1)d n − d − 1 . ( + λ)(q + 1)q s−1 s
(12)
In order to complete the proof, it is sufficient to show that the sum of (12) and (10) is at
least as large as the sum of (6) and (8). In (10) we use (4) to replace bP and then (11) to replace |L|. The new version of (10) then involves a term with λ. It is immediately checked that the coefficient of λ in the sum of (12) and (10) is non-negative. Hence in order to show that (12) + (10) ≥ (6) + (8) we may assume that λ = 0. Then (12) = (6), so it remains to show that (10) ≥ (8) for λ = 0, that is we have to show (bP − 1 − d−1 ) ≥ (n − d+1 )
P ∈B /
where bP = |L|(q + 1) − |B|n−1 and |L| as in (11) with λ = 0. Thus, we have to show that d+1 d + |B|q − (q + 1) − |B|n−1 − (n − |B|)(1 + d−1 ) n−d−1 2 ≥ (n − d+1 ). This is equivalent to |B|(q d+1 − q) ≥ d−1 (q d+1 + q 2 − q − 1) As |B| ≥ d−1 + 2, this is true.
164
Klaus Metsch
J. Geom.
Open Problems. One can study similar questions for higher dimensional subspaces than points. The most general question is probably the following. Given a set T with a certain number of t-subspaces, how many s-subspaces can be incident with an element of T at most. Though there are easy instances of this problem, the problem in general seems to be very difficult. In contrast to the Theorem of Bose and Burton [1] for points, it is in general even not known how many t-subspaces in a set T are needed in order that every s-subspace is incident with at least one element of T . It is known for all s, t in PG(n, q) for n ≤ 4. The only open case in PG(5, q) is t = 2 and s = 3 (and its dual t = 2 and s = 1). References [1] [2] [3] [4] [5]
R.C. Bose and R.C. Burton, A characterization of flat spaces in a finite geometry and the uniqueness of the Hamming and the MacDonald codes, J. Combin. Theory 1 (1966) 96–104. M. Huber, Baer cones in finite projective spaces, J. Geom. 28 (1987) 128–144. R. Jamison, Covering finite fields with cosets of subspaces, J. Combin. Theory Ser. A 22 (1977) 253–266. K. Metsch, Blocking sets in projective spaces and polar spaces, J. Geom. 76 (2003) 216–232. T. Sz˝ onyi and Z. Weiner, On some stability theorems in finite geometry, Manuscript.
Klaus Metsch Mathematisches Institut Arndtstrasse 2 D-35392 Giessen Germany e-mail:
[email protected]
Received 1 November 2004; revised 29 March 2005.
