Complete caps in projective space which are disjoint from a subspace of codimension two

David L. Wehlau

Working over the field of order 2 we consider those complete caps which are disjoint from some codimension 2 subspace of projective space. We derive restrictive conditions which such a cap must satisfy in order to be complete. Using these conditions we obtain explicit descriptions of complete caps which do not meet every hyperplane in at least 5 points. In particular, we determine the set of cardinalities of all such complete caps in all dimensions.

1 Introduction

A subset of the projective space Σ = ℙ𝔾(n, 2) is a cap if no three points of S are collinear. A cap in Σ is said to be complete if it is not properly contained in any other cap of Σ. A cap S in Σ is called large if |S| ≥ 2^{n−1} + 1; otherwise S is said to be small. Much is known about the structure of large complete caps. In particular, it was shown in [5] that if S ⊂ Σ is a large complete cap then |S| = 2^{n−1} +2^{i} for some i ∈ {0, 1, 2, …, n−3, n−1}. In [5] it is also shown that if S is a cap in Σ satisfying |S| ≥ 2^{n−1} + 2 then there exists a codimension 2 subspace H_{∞} ≅ ℙ𝔾(n − 2, 2) of Σ such that S ∩ H_{∞} = ∅. In [3] the same result was shown to hold for all large caps. Conversely in [1] it was shown that given a fixed r ≥ 1 then for all sufficiently large n there exists a cap S in ℙ𝔾(n, 2) such that S meets every codimension r subspace H ≅ ℙ𝔾(n − r, 2) of ℙ𝔾(n, 2).

Here we will consider complete caps, S ⊂ Σ = ℙ𝔾(n, 2) with the property that some codimension 2 subspace H_{∞} ≅ ℙ𝔾(n − 2, 2) of Σ satisfies the condition S ∩ H_{∞} = ∅. Fix such an H_{∞} and denote the three hyperplanes of Σ which contain H_{∞} by K_{A}, K_{B} and K_{C}. Furthermore we write H_{A} := K_{A} \H_{∞}, H_{B} := K_{B} \ H_{∞} and H_{C} := K_{C} \ H_{∞}. Write A := H_{A} ∩ S = K_{A} ∩ S, B := H_{B} ∩S = K_{B} ∩S and C := H_{C} ∩S = K_{C} ∩S. Finally define A′ = H_{A} \A, B′ = H_{B} \ B, and C′ = H_{C} \ C.

If C = ∅ then S is complete if and only if S = Σ \ K_{C}. Henceforth we will assume that none of the three sets A, B, and C is empty.

0Corrected version, September 1, 2001

1I thank A. Davydov for pointing out a error at the bottom of page 7, Sept. 15, 2003

2 David L. Wehlau

Consider the subspace F̃ ≅ ℙ𝔾(r, 2) of K_{C} generated by C. Put F := F̃∩H_{∞} and Ĉ := F̃ \ F. Then F ≅ ℙ𝔾(r − 1, 2) and Ĉ ≅ 𝔸𝔾(r, 2). Consider the decomposition of H_{A} and of H_{B} into cosets of C̃. Each such coset F′ consists of 2^{r} points such that F′ ⊔ F ≅ ℙ𝔾(r, 2). There are 2^{n−r−1} such cosets in each of H_{A} and H_{B}. Each of these cosets is isomorphic to F̃ \ F ≅ 𝔸𝔾(r, 2). We will denote the cosets in H_{A} by H_{A}(1), H_{A}(2), …, H_{A}(2^{n−r−1}). Similarly we denote the cosets in H_{B} by H_{B}(1), H_{B}(2), …, H_{B}(2^{n−r−1}) ordered so that H_{B}(i) = Ĉ + H_{A}(i) for all i. Write A(i) := H_{A}(i) ∩ A, A′(i) := H_{A}(i) ∩ A′, B(i) := H_{B}(i) ∩ B and B′(i) := H_{B}(i) ∩ B′.

The cap S is complete if and only if

A + B = C′, A + C = B′, B + C = A′;  (1.1)
(A ⊕ A) ⊔ (B ⊕ B) ⊔ (C ⊕ C) = H_{∞}.  (1.2)

In particular, if S is complete we must have

A(i) + C = B′(i) and B(i) + C = A′(i)  (1.3)

for all i = 1, 2, …, 2^{n−r−1}.

One way to satisfy Equation 1.3 is to take A(i) = H_{A}(i) and B(i) = ∅. Similarly we may take A(i) = ∅ and B(i) = H_{B}(i). We will call these two solutions the trivial solutions. A second way to satisfy this equation is to take A(i) = {a_{1}} and B(i) = H_{B}(i) \ (a_{1} + C). Symmetrically we may take B(i) = {b_{1}} and A(i) = H_{A}(i) \ (b_{1} + C). If either |A| = 1 or |B| = 1 then we call the solution a singleton solution.

Once we have solutions to Equation 1.3 we still will need the extra conditions of A + B = C′ together with Equation 1.2. In Section 3 we explicitly describe all complete caps with |C| = 1. Using these results we are able in Section 4 to give detailed sufficient conditions on a cap S which satisfies Equation 1.3 for all i, for S to be complete.

In Sections 6, 7 and 8 we consider complete caps which meet at least one hyperplane in less than 5 points. For such caps we are able to find all solutions to Equation 1.3 and thus to explicitly describe such complete caps.

In particular, we are able to construct many small complete caps. Also note that the Plotkin doubling construction (described in Section 2), as well as its generalization the Black/White lift (described in [4]) can be used to build a great many more small complete caps from the small complete caps constructed here.

2 Preliminaries

Complete caps in projective space which are disjoint from a subspace of codimension two 3

Let 𝔽_{2}^{n+1} denote the (n+1)-dimensional vector space over 𝔽_{2}, the field of order 2. The elements of ℙ𝔾(n, 2) are the one dimensional subspaces of 𝔽_{2}^{n+1}. Each such subspace may be uniquely represented by the non-zero vector it contains. Fix a basis {e_{0}, e_{1}, …, e_{n}} of 𝔽_{2}^{n+1} and consider a point x ∈ ℙ𝔾(n, 2). For ease of notation, we write x = s_{1}s_{2} ⋯ s_{r} if e_{s_{1}} +e_{s_{2}} +…+e_{s_{t}} is the non-zero vector in x where s_{1}, s_{2}, …, s_{r} are distinct elements of {0, 1, …, n}. For example, 013 denotes the element of ℙ𝔾(n, 2) comprised by the one-dimensional subspace containing e_{0} + e_{1} + e_{3}. From this point of view, the three points of ℙ𝔾(n, 2) represented by x, y and z are collinear if and only if x, y and z lie in a plane in 𝔽_{2}^{n+1} which occurs if and only if x+y = z in 𝔽_{2}^{n+1}. The usual inner product on 𝔽_{2}^{n+1} induces an inner product on ℙ𝔾(n, 2). We will write (x)^{⊥} to denote the hyperplane of points in ℙ𝔾(n, 2) which are orthogonal to x with respect to this inner product. On occasion we will identify 𝔽_{2}^{n} with the affine space 𝔸𝔾(n, 2). In that setting we will use ∅ to denote the zero vector in 𝔸𝔾(n, 2) = 𝔽_{2}^{n}.

Let X and Y be two subsets of Σ = ℙ𝔾(n, 2) and let z ∈ ℙ𝔾(n, 2). We write X ⊕Y to denote the set {x+y | x ∈ X, y ∈ Y, x ≠ y} ⊆ Σ. If X ∩Y = ∅ we also write X + Y = X ⊕ Y. If z ∉ X we write z + X := {z + x | x ∈ X} = {z} + X.

A subset X of ℙ𝔾(n, 2) is said to be periodic if there exists a point v ∈ ℙ𝔾(n, 2) such that v + X = X. If such a point v exists it is called a vertex of X. The (possibly empty) set of all vertices of X is denoted V (X). Note that if X is periodic then necessarily |X| is even.

Let X be a subset of Σ = ℙ𝔾(n, 2). Embed Σ in Σ̃ ≅ ℙ𝔾(n + 1, 2) and let v ∈ Σ̃ \ Σ. We define the Plotkin double of X (from the vertex v) by

ϕ(X) := X ⊔ {v + x | x ∈ X}.

Then ϕ(X) is a periodic subset of Σ̃ with V (ϕ(X)) = ϕ(V (X)) ⊔ {v}. It is straightforward to verify that ϕ(X) is a cap in Σ̃ if and only if X is a cap in Σ; also, ϕ(X) is complete if and only if X is.

A slightly more general version of the following lemma may be found in [3, Lemma 3.9]. We include a proof here for the reader’s convenience.

Lemma 2.1 Let S ⊂ Σ be complete. Suppose there exists a hyperplane L of Σ such that S ∩ L is periodic. Then S is periodic. Furthermore, if v is a vertex for S ∩ L then v is also a vertex for S.

Proof Let v be a vertex for S∩L and assume, by way of contradiction, that v is not a vertex for S. Then there exists a point x_{1} of S such that x_{2} := x_{1} +v ∉ S. Clearly x_{1} ∉ L since v ∈ L and thus x_{2} ∉ L. Since S is complete, x_{2} lies on a secant of S: say x_{2} = y_{1} + z_{1} where y_{1}, z_{1} ∈ S. Without loss of generality y_{1} ∈ L since every line of Σ meets L. Therefore y_{2} := v + y_{1} ∈ L ∩ S. But y_{2} = v + y_{1} = v + x_{2} + z_{1} = x_{1} + z_{1} and thus the line {y_{2}, x_{1}, z_{1}} is fully contained in S, a contradiction. □

Lemma 2.2 Let X be a subset of Σ = ℙ𝔾(n, 2) and let V (X) denote the (possibly empty) set of vertices for X. Then V (X) is a projective subspace of Σ.

Proof We must prove that V (X) is closed under addition, i.e., if u, v are two distinct points of V (X) then u + v ∈ V (X). Accordingly let u, v be two distinct points of V (X). We must show that w = v + u is also a vertex of X. Let p ∈ X. Since u is a vertex, u + p ∈ X. Similarly, since v ∈ V (X) we have w + p = v + (u + p) ∈ X. Hence w + X ⊆ X and thus w is a vertex of X. □

3 Caps having a tangent hyperplane

In this section we characterize those complete caps S which have a tangent hyperplane. Many of the results of this section are related to results found in [3].

We suppose that K_{C} is a hyperplane which is tangent to S, i.e., that C consists of a single point, C = {c_{o}}. Choose a codimension 2 subspace H_{∞} ≅ ℙ𝔾(n − 2, 2) contained in K_{C} and disjoint from S. Clearly if S is complete we must have B′ = c_{0} + A and A′ = c_{0} + B. Thus S is determined by A (or by B). We wish to investigate conditions on the set A which guarantee that S is complete.

Define E = Σ \ (S ⊔ (S ⊕ S)) and T = S ⊔ E.

Lemma 3.1 T is a complete cap in Σ = ℙ𝔾(n, 2).

Proof Assume, by way of contradiction that T contains a line, ℓ Clearly ℓ must contain at least two points of E, say e, e_{1}. Clearly E ⊂ K_{C} and thus |ℓ ∩ K_{C}| ≥ 2 from which it follows that ℓ ⊂ K_{C}. Thus ℓ contains at least one point of H_{∞}, e say. Therefore, e + A = A′ and e + B = B′. Now if e_{1} ∈ H_{∞} then e_{1} + A = A′ and e_{1} + B = B′. Conversely if e_{1} ∈ H_{C} then e_{1} + A = B′ and e_{1} + B = A′. In both of these cases we have e + e_{1} + (A ⊔ B) = (A ⊔ B). This shows that e + e_{1} ∈ (A ⊔ B) ⊕ (A ⊔ B) ⊂ S ⊕ S. Therefore e + e_{1} ∉ T. This contradiction proves the lemma. □

Proposition 3.2 Let A and B be as defined above. Then V (A) = V (B). In particular, A is periodic if and only if B is periodic.

Proof Suppose A is periodic, i.e., suppose there exists v ∈ H_{∞} such that v + A = A. Since v + H_{A} = H_{A} we have v + A′ = A′. Now c_{0} + B = A′ and c_{0} + A = B′. Therefore v + B = v + c_{o} + A′ = c_{0} + v + A′ = c_{0} + A′ = B. □

Next we give a sufficient condition on A to guarantee that the set S = {c_{0}}⊔A⊔B is a complete cap. The following theorem is similar to [3, Theorem 4.1].

Theorem 3.3 Let S be a cap in Σ = ℙ𝔾(n, 2) with |C| = 1 and B′ = c_{0} + A. Suppose that |A| ≠ 2^{n−2}. If A (or B) is not periodic then S is a complete cap.

Proof Clearly every point of Σ \ L_{C} lies on a secant to S through c_{0}. Let α = |A| and β = |B|. Then α + β = 2^{n−1}. Since α ≠ 2^{n−1} one of α or β, say without loss of generality α, exceeds 2^{n−2}. Therefore A ⊕ A = H_{∞}, i.e., every point of H_{∞} lies on a secant to A.

Finally we prove that if S is not complete (and |A| ≠ 2^{n−2}) then A is periodic. Thus we suppose that S is not complete. By the foregoing this implies that there exists x ∈ H_{C} with x ≠ c_{0} such that x ∉ A + B. Then x + A = B′ and c_{0} + A = B′. Therefore v + A = x + c_{0} + A = x + B′ = A. Therefore A is periodic with vertex v. □

Remark 3.4 Note that the hypothesis that |A| ≠ 2^{n−2} is required. See Example 3.12.

Suppose that S is a cap with |C| = 1 and B′ = c_{0} + A. Then |S| = 2^{n−1} + 1. Since |S| is odd, S cannot be periodic. Thus by Lemma 2.1, we have that both A and B are not periodic. Hence we have proved the following result.

Theorem 3.5 In Σ = ℙ𝔾(n, 2), let S be a cap which meets a hyperplane K_{C} of Σ in a single point, c_{0}. Choose a codimension 2 subspace H_{∞} ≅ ℙ𝔾(n−2, 2) contained in K_{C} and disjoint from S. Suppose B′ = c_{0}+A and that |A| ≠ 2^{n−2}. Then S is complete if and only if A is not periodic if and only if B is not periodic.

Next we consider in detail the case where |A| = |B| = 2^{n−2}.

Suppose first that A ⊕ A ≠ H_{∞}, i.e., suppose there exists p ∈ H_{∞} \ (A ⊕ A). Then p + A = A′. Therefore A ⊕ A = (p + A′) ⊕ (p + A′) = A′ ⊕ A′ = (c_{0}+A′)⊕(c_{0}+A′) = B⊕B. In particular, p ∉ B⊕B. Note that we have shown that whenever |A| = |B| = 2^{n−2}, we have A ⊕ A = B ⊕ B = A′ ⊕ A′ = B′ ⊕ B′.

Lemma 3.6 If |E ∩ H_{∞}| ≥ 2 then A, B, A′ and B′ are each periodic.

Proof Let e_{1}, e_{2} ∈ E ∩ H_{∞}. Then e_{1} + e_{2} + A = e_{1} + A′ = A and thus A is periodic. Similarly e_{1} + e_{2} is a vertex for B, A′ and B′. □

Suppose A is not periodic. By the preceding lemma, |E| ≤ 1. Hence either S is complete or T = S ⊔ {e}. Thus we have proved the following theorem.

Theorem 3.7 In Σ = ℙ𝔾(n, 2), let S be a cap which meets a hyperplane K_{C} of Σ in a single point, c_{0}. Choose a codimension 2 subspace H_{∞} ≅ ℙ𝔾(n−2, 2) contained in K_{C} and disjoint from S. Suppose B′ = c_{0} + A. If S is complete then A and B are not periodic. If A (or B) is not periodic then either

(i) S is complete or

(ii) |A| = |B| = 2^{n−2} and Σ = S ⊔ (S ⊕ S) ⊔ {e} where e ∈ H_{∞} and the complete cap T = S ⊔ {e} is periodic with V (T) = {e + c_{0}}.

Remark 3.8 If n ≤ 4 and |A| = 2^{n−2} then A ⊕ A ≠ H_{∞} since then |A ⊕ A| ≤ \binom{|A|}{2} < |H_{∞}|.

The following four examples show that A⊕A may or may not equal H_{∞} and A may or may not be periodic in all possible combinations when |A| = 2^{n−2}.

Example 3.9 In ℙ𝔾(9, 2) take A_{0} = {8}, A_{1} = {08, 18, 28, 38, 48, 58, 68, 78}, A_{5} = {ijklm8 | 0 ≤ i < j < k < l < m ≤ 7}, A_{8} = {012345678} and A^{♯} = A_{0}⊔A_{1}⊔A_{5}⊔A_{8}. With K_{A} = (9)^{⊥} and K_{B} = (8)^{⊥} we have A^{♯}⊕A^{♯} = H_{∞} and |A^{♯}| = 66. Now the point v := 01 ∈ H_{∞} lies on 16 secants to A^{♯} and thus |A^{♯} ⊔ (v + A^{♯})| = 116. Hence we may easily extend A^{♯} to a set A ⊂ (K_{A} \ H_{∞}) with |A| = 128 and v + A = A by adding the 12 points of 6 new secant lines of v to A^{♯}. Then A ⊕ A = H_{∞} and A is periodic.

Example 3.10 In ℙ𝔾(5, 2) take A = {4, 04, 14, 24, 34, 01234, 0134, 0234} where K_{A} = (5)^{⊥} and K_{B} = (4)^{⊥}. Then A is not periodic and A ⊕ A = H_{∞}. Thus S = A ⊔ (45 + A) ⊔ {45} is complete.

Example 3.11 In ℙ𝔾(5, 2) take A = {4, 04, 14, 014, 24, 024, 34, 034} where K_{A} = (5)^{⊥} and K_{B} = (4)^{⊥}. Then A is periodic (with vertex 0) and A ⊕ A ≠ H_{∞}. Here if c_{0} = 45 then E = {045, 123, 0123}.

Example 3.12 In ℙ𝔾(4, 2) take A = {3, 03, 13, 23} where K_{A} = (4)^{⊥} and K_{B} = (3)^{⊥}. Then A is not periodic and A ⊕ A ≠ H_{∞}. Thus H_{∞} \ (A ⊕ A) = {e = 012} and S = A ⊔ (c_{0} + A) ⊔ {c_{0}, e} is a complete cap.

4 General Case

Next we suppose that the sets A and B are such that Equation 1.3 is satisfied for all i. Under this hypothesis we want to investigate conditions on A and B which are sufficient to guarantee that the S is a complete cap.

We suppose that {1, 2, …, t} = {i | H_{A}(i) ⊂ S} for some t with 0 ≤ t ≤ 2^{n−r−1}. Thus {1, 2, …, t} = {i | H_{B}(i) ∩ S = ∅}. Further suppose that {t+1, t+2, …, t+u} = {i | H_{A}(i)∩S = ∅} for some u with 0 ≤ u ≤ 2^{n−r−1} −t. Then {t + 1, t + 2, …, t + u} = {i | H_{B}(i) ⊂ S}. Thus the pair of cosets corresponding to i = 1, 2, …, t + u are precisely those having a trivial solution to Equation 1.3.

Let \overline{Σ} ≅ ℙ𝔾(n−r, 2) denote the quotient geometry of Σ by F. This is just the projective geometry associated to the quotient of the vector space associated to Σ = ℙ𝔾(n, 2) by the vector space associated to F.

Let \overline{a_{i}} and \overline{b_{i}} denote the points of \overline{Σ} corresponding to the cosets H_{A}(i) and H_{B}(i) respectively. Write \overline{C} for the point of \overline{Σ} corresponding to F̃. Similarly we define \overline{H_{A}}, \overline{H_{B}}, etc. for the subsets of \overline{Σ} corresponding to H_{A}, H_{B}, etc. respectively.

Corresponding to the full, empty and non-empty cosets of A and B we define the following subsets of \overline{Σ}. Put \overline{A_{f}} = \{\overline{a_{1}}, \overline{a_{2}}, …, \overline{a_{t}}\}, \overline{B_{f}} = \{\overline{b_{t+1}}, \overline{b_{t+2}}, …, \overline{b_{t+u}}\}, \overline{A_{e}} = \{\overline{a_{t+1}}, \overline{a_{t+2}}, …, \overline{a_{t+u}}\}, \overline{B_{e}} = \{\overline{b_{1}}, \overline{b_{2}}, …, \overline{b_{t}}\}, \overline{A_{ne}} = \overline{H_{A}} \ \overline{A_{e}} and \overline{B_{ne}} = \overline{H_{B}} \ \overline{B_{e}}. Recall that Ĉ = F̃ \ F.

Theorem 4.1 Suppose that A and B are such that Equation 1.3 is satisfied for all i = 1, 2 …, 2^{n−r−1}. Suppose 0 < t+u < 2^{n−r−1}, that t ≠ u, and that either \overline{A_{f}} or \overline{B_{f}} is non-periodic. Further suppose that Ĉ \ C ⊆ ∪_{i=1}^{2^{n−r−1}} (A(i) + B(i)). Then S is a complete cap in Σ.

Proof By construction, S is a cap in Σ. Also Equation 1.3 guarantees that every point of A′ and every point of B′ lies on at least one secant of S through a point of C. Thus we need to show that every point of H_{∞} and every point of H_{C} \ C lies on a secant of S.

Without loss of generality suppose that \overline{A_{f}} is non-periodic. Consider the cap \overline{S_{1}} in \overline{Σ} given by \overline{S_{1}} = \overline{A_{f}} ⊔ \overline{B_{ne}} ⊔ \{\overline{C}\}. Applying Theorem 3.7 we see that for every point \overline{c_{k}} of \overline{H_{C}} different from \overline{C} there exists i ≤ t and j ≥ t + 1 such that \overline{a_{i}} + \overline{b_{j}} = \overline{c_{k}}. Since the coset H_{A}(i) is entirely contained in S, and H_{B}(j)∩S ≠ ∅, this means that every point of the coset H_{C}(k) = H_{A}(i)+H_{B}(j) lies on a secant to S.

By assumption, every point of Ĉ \ C is contained in A + B.

Hence it only remains to prove that every point of H_{∞} lies on at least one secant to S. Note that every point of F lies in H_{A}(1) ⊕ H_{A}(1) (or in H_{B}(1) ⊕ H_{B}(1) if t = 0). Thus we consider a point z ∈ H_{∞} \ F and write \overline{z} for the point of \overline{Σ} corresponding to the coset of F generated by z. As above, if \overline{z} ∈ \overline{A_{f}} + \overline{A_{ne}} or \overline{z} ∈ \overline{B_{f}} + \overline{B_{ne}} then z lies on a secant line to S. Thus we assume, by way of contradiction, that \overline{z} + \overline{A_{f}} ⊂ \overline{A_{e}} and \overline{z} + \overline{B_{f}} ⊂ \overline{B_{e}}. The first inclusion implies that t ≤ u while the second implies that u ≤ t. Thus t = u contradicting our hypothesis. □

Remark 4.2 Note that if there exists at least one value of i for which a singleton solution occurs then Ĉ \ C ⊆ ∪_{i=1}^{2^{n−r−1}} (A(i) + B(i)). Conversely if t + u = 2^{n−r−1} then A(i) + B(i) = ∅ for all i and thus Ĉ \ C ⊈ ∪_{i=1}^{2^{n−r−1}} (A(i) + B(i)). Hence if t + u = 2^{n−r−1} then S is not complete. Furthermore, in order that 1 ≤ t + u ≤ 2^{n−r−1} − 1 we must have r ≤ n − 2.

Remark 4.3 Note that, if t or u is odd, then \overline{A_{f}} or \overline{B_{f}} respectively is nonperiodic. Thus for a fixed value of t + u with 1 ≤ t + u ≤ 2^{n−r−1} − 1 we may take t = 1, for example, to arrange that \overline{A_{f}} is non-periodic. Furthermore, if t + u ≠ 2 we may simultaneously arrange that t ≠ u.

Remark 4.4 There do exist complete caps for which t + u = 0 (and thus \overline{A_{f}} = \overline{B_{f}} = ∅). See Example 5.4. The condition that t ≠ u is also sufficient but not necessary.

5 A family of examples

In this section we consider the case where |C| = 2^{r} − 1, i.e., where Ĉ \ C is a single point {c_{0}}. If r = 0 then C is empty contrary to our earlier assumption. If r = 1 then |C| = 1 and we are in the case considered in Section 3. Thus we will assume that r ≥ 2. Accordingly, we must have n ≥ 3.

Using the cap property of S we see that if |S∩H_{A}(i)| ≥ 2 then S∩H_{B}(i) = ∅. Furthermore if S ∩ H_{B}(i) is a single point, {α_{i}}, then using the completeness of S we must have S ∩ H_{B}(i) = {β_{i} := α_{i} + c_{0}}. Finally if S ∩ H_{B}(i) = ∅ then the completeness of S implies that H_{B}(i) ⊂ S.

Thus the only solutions to Equation 1.3 are the trivial solutions and the singleton solutions. Let s denote the number of these pairs of cosets which have the singleton solution.

Then |S| = (2^{r} − 1) + 2s + 2^{r}(2^{n−r−1} − s) = 2^{n−1} + 2^{r} − 1 − (2^{r} − 2)s. By Remark 4.2, s cannot equal 0. Furthermore by Theorem 4.1 (and Remark 4.3) there do exist complete caps of this form for all s = 1, 2, …, 2^{n−r−1} − 3 and s = 2^{n−r−1} − 1. Thus we find complete caps of this form of all cardinalities: 2^{n−r} + k(2^{r} − 2) + 1 for k = 2, 4, 5, …, 2^{n−r−1} where 2 ≤ r ≤ n − 2.

Next we consider the case s = 2^{n−r−1} − 2. Then u + v = 2 and either u = v or else both \overline{A_{f}} and \overline{B_{f}} are periodic. Reordering the cosets we may suppose |H_{A}(i)| = |H_{B}(i)| = 1 for i = 3, 4, …, 2^{n−r−1}. Write {α_{i}} = H_{A}(i) and {β_{i}} = H_{B}(i) for i = 3, 4, …, 2^{n−r−1}. We consider first the case that t = u = 1. Examining the proof of Theorem 4.1 we see that every point of ℙ𝔾(n, 2) lies on a secant to S except possibly the 2^{r} points in the coset H_{A}(1) + H_{A}(2) = H_{B}(1) + H_{B}(2) = {z_{1}, z_{2}, …, z_{2^{r}}} ⊂ H_{∞}. These points z_{k} can only lie on secants of the form α_{i} + α_{j} = z_{k} or β_{i} + β_{j} = z_{k}. Since β_{i} +β_{j} = α_{i} +α_{j} we may restrict our attention to the α_{i}. Thus we see that S is complete if and only if for every k = 1, 2, …, 2^{r} there exists 3 ≤ i(k) < j(k) ≤ 2^{n−r−1} such that α_{i(k)} + α_{j(k)} = z_{k}. Since the α_{i} all lie in different cosets, it is clear that α_{i(1)}, α_{j(1)}, …, α_{i(2^{r})}, α_{j(2^{r})} must be distinct. Thus we must have 2(2^{r}) ≤ 2^{n−r−1} − 2 or equivalently 2r + 3 ≤ n.

The case (t, u) = (2, 0) (or (0, 2)) is entirely similar to the above case. The only difference being that the 2^{r} points which may not lie on secants to S form a coset in H_{C} instead of in H_{∞}. In summary we see that there exists a complete cap S with |Ĉ \C| = 1 and with |S| = 2^{n−r} +2^{r+1} +2^{r} −5 (and s = 2^{n−r−1} −2) if and only if n ≥ 2r + 3.

The only remaining possibility is that s = 2^{n−r−1}, i.e., t = u = 0. Thus we now consider caps with Ĉ \ C = {c_{0}} and with |H_{A}(i)| = |H_{B}(i)| = 1 for all i = 1, 2, …, 2^{n−r−1}.

Lemma 5.1 Let 2 ≤ r ≤ n − 1 and suppose that Ĉ \ C is a single point {c_{0}} and that |A(i)| = |B(i)| = 1 for all i = 1, 2, …, 2^{n−r−1}. Then S is a complete cap if and only if A ⊕ A = H_{∞} \ F.

Proof Note that A⊕A = B ⊕B since α_{i} +α_{j} = (α_{i} +c_{0})+(α_{j} +c_{0}) = β_{i} +β_{j}. Furthermore A ⊕ A ⊆ H_{∞} \ F and C ⊕ C = F. Thus H_{∞} ⊂ S ⊕ S if and only if A ⊕ A = H_{∞} \ F.

Suppose now that A ⊕ A = H_{∞} \ F. By construction A + C = B′ and B + C = A′ thus S is complete if and only if A + B = C′. Now A + B = A + (c_{0} + A) = {c_{0}} ⊔ (c_{0} + (A ⊕ A)) = {c_{0}} ⊔ (c_{0} + (H_{∞} \ F)) = C′. Hence we conclude that S is complete if and only if A ⊕ A = H_{∞} \ F. □

We will now attempt to determine those sets A = {α_{1}, α_{2}, …, α_{2^{n−r−1}}} for which A ⊕ A = H_{∞} \ F. The remainder of this section will be devoted to answering this question. We will reduce this question to an equivalent geometric question in \overline{K_{A}} where, as above, \overline{K_{A}} denotes a hyperplane in \overline{Σ}, the quotient geometry of Σ with respect to F.

To do this we will fix some subspace L ≅ ℙ𝔾(n − r − 1, 2) ⊂ K_{A} such that L ∩ F = ∅. Choose an identification of one of the cosets H_{A}(i), say H_{A}(i), with 𝔸𝔾(r, 2). Choose this identification so that the unique point a_{0} :=∈ H_{A}(1) ∩ L is the point identified with the zero vector in 𝔸𝔾(r, 2). Note that with this identification if u, v ∈ 𝔸𝔾(r, 2) correspond to x, y ∈ H_{A}(1) respectively then u + v ∈ 𝔸𝔾(r, 2) corresponds to x + y + a_{0} ∈ H_{A}(1).

Now for each point a of K_{A} \ F there exists a unique point x of 𝔸𝔾(r, 2) such that x + a ∈ L. For each x ∈ 𝔸𝔾(r, 2) define (K_{A})_{x} := {a ∈ (K_{A} \ F) | x + a ∈ L}. This partitioning of K_{A} \ F induces a partitioning of A: A = ⊔_{x∈𝔸𝔾(r,2)}A_{x} where A_{x} := A ∩ (K_{A})_{x}. Similarly we have the partitioning of H_{∞}: H_{∞} = ⊔_{x∈𝔸𝔾(r,2)}(H_{∞})_{x} where (H_{∞})_{x} := H_{∞} ∩ (K_{A})_{x} ≅ ℙ𝔾(n − r − 2) for all x ∈ 𝔸𝔾(r, 2).

Example 5.2 Take n = 7 and r = 2. Put K_{A} = (7)^{⊥}, K_{B} = (6)^{⊥} and K_{C} = (67)^{⊥}. Then H_{∞} ≅ ℙ𝔾(5, 2) is the projective subspace generated by {0, 1, 2, 3, 4, 5}. Take C = {067, 167, 0167} so that c_{0} = 67. Then Ĉ = {067, 167, 0167, 67}, F̃ ≅ ℙ𝔾(2, 2) is generated by {0, 1, 67} and F is the line {0, 1, 01}. Choose L ≅ ℙ𝔾(4, 2) to be the subspace of K_{A} generated by {2, 3, 4, 5, 6}. Then L∩F = ∅ as required. We take H_{A}(1) to be the coset containing 6 say. Thus H_{A}(1) = {6, 06, 16, 016} and a_{0} = 6 ∈ H_{A}(1)∩L. Then for example if we choose our identification so that u = 1 ∈ 𝔸𝔾(2, 2) corresponds to 16 ∈ H_{A}(1) we have (H_{∞})_{u} = (H_{∞})_{16} = {1, 12, 13, 14, 15, 123, 124, 125, 134, 135, 145, 1234, 1235, 1245, 1345, 12345}.

Now the useful property of this partition is that for u, w ∈ 𝔸𝔾(r, 2) we have A_{u}⊕A_{v} ⊆ (H_{∞})_{u+v}. Thus A⊕A = H_{∞}\F if and only if for every w ∈ 𝔸𝔾(r, 2) we have ∪_{u∈𝔸𝔾(r,2)} (A_{u} ⊕ A_{u+w}) = (H_{∞})_{w} \ F. Note that the partition of A yields a partition of \overline{A} = \overline{H_{A}}:

\overline{H_{A}} = ⊔_{x∈𝔸𝔾(r,2)}\overline{A_{x}}.

Furthermore A ⊕ A = H_{∞} \ F if and only if for every w ∈ 𝔸𝔾(r, 2) we have

∪_{u∈𝔸𝔾(r,2)} (\overline{A_{u}} ⊕ \overline{A_{u+w}}) = \overline{(H_{∞})}.  (5.1)

Thus we have proved the following proposition:

Proposition 5.3 Let C ≅ 𝔸𝔾(r, 2) \ {c_{0}} and suppose |A(i)| = |B(i)| = 1 for all i = 1, 2, …, 2^{n−r−1}. Then S is a complete cap if and only if the partition of 𝔸𝔾(n − r, 2) = \overline{H_{A}} induced by A satisfies Equation 5.1 for all w ∈ 𝔸𝔾(r, 2).

Example 5.4 We continue with the notation of the previous example. Thus \overline{H_{A}} ≅ 𝔸𝔾(4, 2) ⊂ \overline{K_{A}} ≅ ℙ𝔾(4, 2). Hence to obtain a complete cap S we require a partition of 𝔸𝔾(4, 2) into 4 subsets, \overline{A_{0}}, \overline{A_{1}}, \overline{A_{01}}, \overline{A_{∅}} satisfying Equation 5.1 for all w ∈ 𝔸𝔾(2, 2) = {0, 1, 01, ∅}. It is not too difficult to find such partitions. For example, \overline{A_{∅}} := ∅, \overline{A_{0}} := \{6, 246, 346, 256, 2346, 2456\} \overline{A_{1}} := \{236, 356, 456, 2356, 3456\}, and \overline{A_{01}} := \{26, 36, 46, 56, 23456\}. This partition corresponds to the complete cap S = A ⊔ B ⊔ C where which A = {1236, 1356, 1456, 12356, 13456, 06, 0246, 0346, 0256, 02346, 02456, 0126, 0136, 0146, 0156, 0123456} and B = c_{0} + A = 01 + A.

Lemma 5.5 Let 𝔸𝔾(k, 2) ⊂ Λ = ℙ𝔾(k, 2) denote the complement of a hyperplane H of Λ. Suppose there exists a partition of 𝔸𝔾(k, 2) indexed by 𝔸𝔾(r, 2) : 𝔸𝔾(k, 2) = ⊔_{w∈𝔸𝔾(r,2)}X_{w} such that

∪_{u∈𝔸𝔾(r,2)} (\overline{X_{u}} ⊕ \overline{X_{u+w}}) = H (5.1)

for all w ∈ 𝔸𝔾(r, 2). Then r ≤ k − 2.

Proof The partition of 𝔸𝔾(k, 2) induces a partition of the secant lines of 𝔸𝔾(k, 2) as follows. If a_{1} ∈ X_{u} and a_{2} ∈ X_{v} then we say the secant line through a_{1} and a_{2} is of type u + v ∈ 𝔸𝔾(r, 2). Equation 5.1 is the condition that every point of H lies on at least one secant line of type w for all w ∈ 𝔸𝔾(r, 2). Since |H| = 2^{k} − 1 and since there are \binom{2^{k}}{2} = 2^{k−1}(2^{k} − 1) secant lines we must have 2^{k−1}(2^{k} − 1) ≥ 2^{r}(2^{k} − 1). Thus k − 1 ≥ r. Furthermore, if r = k − 1 then every point of H must lie on exactly one secant line of each type w ∈ 𝔸𝔾(r, 2).

Suppose then that r = k − 1 and assume by way of contradiction that a partition of 𝔸𝔾(k, 2) satisfying Equation 5.1 exists. Define x_{w} := |X_{w}| for w ∈ 𝔸𝔾(k, 2). Then we have ∑_{u∈𝔸𝔾(r,2)} x_{w}x_{u} = 2^{k} − 1 for all w different from zero in 𝔸𝔾(r, 2). Also ∑_{u∈𝔸𝔾(r,2)} \binom{x_{u}}{2} = 2^{k} − 1. Since ∑_{u∈𝔸𝔾(r,2)} x_{u} = 2^{r} − 1, this gives ∑_{u∈𝔸𝔾(r,2)} x_{u}^{2} = 2^{k} − 2. Thus

2^{2k} = ( ∑_{u∈𝔸𝔾(r,2)} x_{u})^{2} = ∑_{u≠v} x_{u}x_{v} + ∑_{u∈𝔸𝔾(r,2)} x_{u}^{2}
= 2^{r}(2^{k} − 1) + 2^{k} − 2 = 2^{k−1}(2^{k} − 1) + (2^{k} − 1) − 1 = (2^{k} − 1)(2^{k}).

This contradiction shows that r ≤ k − 2. □

Remark 5.6 Clearly, if a partition of 𝔸𝔾(k, 2) exists which satisfies Equation 5.1 for some value r_{0} of r then such a partition exists for all values of r less than r_{0}.

6 |C| = 2

Lemma 6.1 Let S be a complete cap in Σ = ℙ𝔾(n, 2) satisfying |C| = 2. Then S = ϕ(S′) where S′ = S∩Σ′ is a complete cap in a hyperplane Σ′ ≅ ℙ𝔾(n−1, 2). In particular, |S| = 2^{n−1} + 2.

Proof Write C = S ∩ K_{C} = {c_{1}, c_{2}}. Then C is periodic with vertex v = c_{1} + c_{2} ∈ H_{∞}. By Lemma 2.1, S is also periodic with vertex v. Choose any hyperplane Σ′ of Σ not containing v and put S′ = S ∩ Σ′. Then S = ϕ(S′) (with respect to the vertex v). Since S is complete in Σ, it follows that S′ is complete in Σ′. Also the hyperplane K_{C} ∩ Σ′ of Σ′ is a tangent hyperplane for S′ and thus |S′| = 2^{n−2} + 1. Hence |S| = 2|S′| = 2(2^{n−2} + 1) = 2^{n−1} + 2. □

7 |C| = 3

Now suppose that S is a complete cap meeting a hyperplane K_{C} in 3 points. Choose a codimension 2 subspace H_{∞} ≅ ℙ𝔾(n − 2, 2) contained in K_{C} and disjoint from S. Write C = {c_{1}, c_{2}, c_{3}}. Then F = {c_{1} + c_{2}, c_{1} + c_{3}, c_{2} + c_{3}} is a line in H_{∞}. Put c_{0} = c_{1} + c_{2} + c_{3}. Then F̃ = F ∪ C ∪ {c_{0}} ≅ ℙ𝔾(2, 2) and Ĉ := C ∪ {c_{0}} ≅ 𝔸𝔾(2, 2). Thus |C| = 3 implies that we are in the case described in Section 5 with r = 2.

Thus by Theorem 4.1 (and Remark 4.3) we have maximal caps with |C| = 3 of all cardinalities 3+2m+4(2^{n−3}−m) = 2^{n−1}−2m+3 where 1 ≤ m ≤ 2^{n−3}−3 or m = 2^{n−3} − 1, i.e., of cardinalities 2^{n−2} + 5, 2^{n−2} + 9, 2^{n−2} + 11, 2^{n−2} + 13, …, 2^{n−1} + 1 for n ≥ 4.

Now we show that there for all n ≥ 3 there exist complete caps with |C| = 3 and with |A(i)| = |B(i)| = 1 for all i = 1, 2, …, 2^{n−3}. By Proposition 5.3 we must find a partition of 𝔸𝔾(n − 2, 2) into 4 subsets indexed by 𝔸𝔾(2, 2) satisfying Equation 5.1. There are very many ways to do this. We give one construction here. We proceed by induction on k = n − 2. Since we have assumed that r ≥ 2 the first case is k = 4. We exhibited such a partition for k = 4 in Example 5.2. Now we will inductively construct from this example a partition for all values of k ≥ 5. Suppose we have a partition of 𝔸𝔾(k, 2) into four sets \overline{A_{∅}}, \overline{A_{0}}, \overline{A_{1}} and \overline{A_{01}} where we further suppose that \overline{A_{∅}} = ∅. Write ℙ𝔾(k + 1, 2) = ϕ(ℙ𝔾(k, 2)) with respect to some vertex z ∈ P G(k + 1, 2) \ ℙ𝔾(k, 2). Then 𝔸𝔾(k + 1, 2) = ϕ(𝔸𝔾(k, 2)). Let H̃ = ℙ𝔾(k + 1, 2) \ 𝔸𝔾(k + 1, 2) = ϕ(H). We partition 𝔸𝔾(k + 1, 2) into 4 sets: 𝔸𝔾(k + 1, 2) = Ã_{∅} ⊔ Ã_{0} ⊔ Ã_{1} ⊔ Ã_{01} by defining Ã_{w} := ϕ(\overline{A_{w}}) = \overline{A_{w}} ⊔ (z + \overline{A_{w}}). This partition almost satisfies Equation 5.1. However the point z ∈ H̃ is not contained in any of the three sets Ã_{0} + Ã_{1}, Ã_{0} + Ã_{01} and Ã_{1} + Ã_{01}. To overcome this defect we modify the partition slightly. Note that every point of H̃ different from z lies on at least two secants of each type u ∈ 𝔸𝔾(2, 2). Consider the three points of 𝔸𝔾(k, 2): a_{0} := 6, a_{1} := 236 and a_{01} := 26 and the line in H: z_{01} := a_{0} + a_{1}, z_{1} := a_{0} + a_{01} and z_{0} := a_{1} + a_{01}. Each of the three points of this line lies on secants of all types which do not utilize a_{0}, a_{1} nor a_{01}. Specifically we have z_{01} = 23 = 256 + 356 = 2346 + 46 = 456 + 23456, z_{1} = 2 = 2456 + 456 = 246 + 46 = 356 + 56 and z_{0} = 3 = 256 + 2356 = 346 + 46 = 356 + 56. We shift z + a_{0} into Ã_{1}, z + a_{1} into Ã_{01} and z + a_{01} into Ã_{0}. This modified partition now satisfies Equation 5.1. Also note that we have not shifted any of the points a_{0}, a_{1}, a_{01} nor indeed any of the points of 𝔸𝔾(k, 2) and so our induction proceeds using the same points a_{0}, a_{1}, a_{01} at each stage.

In conclusion we see that there are complete caps, S in ℙ𝔾(n, 2) with |C| = 3 of cardinality 2^{n−2} + 3 for all n ≥ 7. Thus we have the following.

Proposition 7.1 Suppose n ≥ 4 and that S is a complete cap in ℙ𝔾(n, 2). Further suppose that S meets a hyperplane K_{C} of ℙ𝔾(n, 2) in exactly 3 points. Then |S| is one of the numbers: 2^{n−2}+5, 2^{n−2}+9, 2^{n−2}+11, 2^{n−2}+13, …, 2^{n−1}+ 1 or, if n ≥ 7, |S| may also be 2^{n−2} + 3 or 2^{n−2} + 7. Moreover complete caps of all these sizes exist for all corresponding values of n.

8 |C| = 4

In this section we assume that S is a complete cap meeting a hyperplane K_{C} in 4 points. As usual we choose a codimension 2 subspace H_{∞} ≅ ℙ𝔾(n − 2, 2) contained in K_{C} and disjoint from S. Note that when |K_{C} ∩ S| = 4 there are two possibilities; either these four points lie in a Fano plane or they do not. Now if they do lie in a Fano plane they form a periodic set and it follows as in Section 6 that if S complete then |S| = 2^{n−1} + 4 and S is large.

It remains to consider the case where S ∩K_{C} consists of four points spanning a three dimensional projective subspace of K_{C}. In order to determine all solutions to Equation 1.3 we first assume that this three dimensional subspace is K_{C} and thus that n = 4. Without loss of generality, C = {04, 14, 24, 34}, K_{C} = (01234)^{⊥}, K_{B} = (4)^{⊥} and K_{A} = (0123)^{⊥}. Thus H_{∞} = {01, 02, 03, 12, 13, 23, 0123} and H_{A} = H_{A}(1) = {4, 014, 024, 034, 124, 134, 234, 01234}.

Let G denote the group of projectivities of Σ = ℙ𝔾(4, 2) which stabilize, C, K_{A}, K_{B} and K_{C}. Then G contains the subgroup L of projectivities which permute the points 0, 1, 2 and 3 and which also fix the point 4. The group G also contains the projectivities f and h defined by: f(0) = 0, f(1) = 0, f(2) = 0124, f(3) = 0134 and f(4) = 014 and h(0) = 123, h(1) = 023, h(2) = 013, h(3) = 012, and h(4) = 01234.

Suppose that A and B satisfy Equation 1.3 and further that A and B do not correspond to either trivial or singleton solutions of that equation. Thus |A| ≥ 2 and |B| ≥ 2. Since G acts transitively on H_{A} we may assume without loss of generality that 01234 ∈ A. Now the subgroup of G fixing 01234 contains the group L. The action of L decomposes the remaining points of H_{A} into two orbits: {4} and {014, 024, 034, 124, 134, 234}. Thus without loss of generality we have two cases to consider: (i) A ⊃ {01234, 4} and (ii) A ⊃ {01234, 014}. These two cases are distinguished by the fact that in the former case the point z_{0} := c_{1} + c_{2} + c_{3} + c_{3} = 04 + 14 + 24 + 34 = 0123 lies on the secant through the two given points of A while in the latter case it does not.

In the first case, we see that B′ = A + C ⊃ {01234, 4} + C = H_{B} and thus we have the trivial solution A = H_{A} and B = ∅. In the second case B′ = A + C ⊃ {01234, 014} + C = H_{B} \ {2, 3}. Since |B| ≥ 2, we must have B = {2, 3} and A = {01234, 014}.

Thus we find only one new solution to Equation 1.3. This solution is determined by A(i) = {a_{1}, a_{2}}, a_{1}+a_{2} ≠ z_{0}, and B(i) = {b_{1}, b_{2}} = H_{B}(i)\(A(i)+C) where z_{0} = c_{1} + c_{2} + c_{3} + c_{4}. Note that b_{1} + b_{2} = a_{1} + a_{2}. Thus we have five solutions in total: the two trivial solutions, the two singleton solutions and this new solution. Notice that for the new solution and for both of the singleton solutions we have z_{0} ∉ A(i) ⊕ A(i) and z_{0} ∉ B(i) ⊕ B(i). Since z_{0} ∉ C ⊕ C, if S is complete there must be at least one i for which the trivial solution occurs. In particular, we may apply Theorem 4.1 to obtain complete caps S with |C| = 4 and C not periodic.

Suppose that S is a complete cap with |C| = 4. If C is periodic then |S| = 2^{n−1} + 4. Suppose then that C is not periodic and that m of the pairs of cosets H_{A}(i), H_{B}(i) utilize the new solution, s of them utilize singleton solutions and t + u = 2^{n−4} − s − m of them utilize the trivial solution. Note that if s = 0 then we must have m ≥ 2 in order that Ĉ \ C ⊆ ∪_{i=1}^{2^{n−r−1}} (A(i) + B(i)). The cardinality of S is then given by |S| = 4 + 4m + 5s + 8(2^{n−4} − s − m) = 2^{n−1} − 3(s + m) − m + 4 where 0 ≤ m, s ≤ 2^{n−4} − 1 and 1 ≤ m + s ≤ 2^{n−4} − 1 (and (m, s) ≠ (1, 0)). Thus if |C| = 4 and C is not periodic then n ≥ 5 and we find complete caps S of all cardinalities satisfying 2^{n−2} + 8 ≤ |S| ≤ 2^{n−1} − 2. In summary we have the following.

Proposition 8.1 Suppose n ≥ 5 and that S is a complete cap in ℙ𝔾(n, 2). Further suppose that S meets a hyperplane K_{C} of ℙ𝔾(n, 2) in exactly 4 points. Then 2^{n−2} + 8 ≤ |S| ≤ 2^{n−1} − 2 or else |S| = 2^{n−1} + 1. Moreover except for n = 6 for sizes 29 and 30, complete caps of all these sizes and this structure exist for all n ≥ 5.

Acknowledgements

I thank Aiden Bruen for many useful conversations. This research was supported by grants from ARP and NSERC.

References

[1] A.E. Brouwer, A. A. Bruen, and D.L. Wehlau, There exist caps which block all subspaces of fixed codimension in ℙ𝔾(n, 2), J.C.T. A 73, #1 (1996) 168–169.

[2] Aiden A. Bruen, Lucien Haddad and David L. Wehlau, Binary Codes and Caps, J. Combin. Des. 6, #4 (1998) 275–284.

[3] Aiden A. Bruen and David L. Wehlau, Long Binary Linear Codes and Large Caps in Projective Space, D.C.C. 17, (1999) 37–60.

[4] Aiden A. Bruen and David L. Wehlau, New Codes From Old; A New Geometric Construction (to appear in J.C.T. A).

[5] A.A. Davydov and L.M. Tombak, Quasiperfect Linear Binary Codes with Distance 4 and Complete Caps in Projective Geometry, Problems of Information Transmission 25 No. 4 (1990) 265–275.

David L. Wehlau Department of Mathematics and Computer Science Royal Military College Kingston, Ontario Canada K7K 7B4

wehlau@rmc.ca