Nội dung

Arcs with large conical subsets K. Coolsaet H. Sticker Department of Applied Mathematics and Computer Science Ghent University Krijgslaan 281–S9, B–9000 Gent, Belgium Kris.Coolsaet@UGent.be, Heide.Sticker@UGent.be Submitted: Dec 16, 2009; Accepted: Jul 29, 2010; Published: Aug 9, 2010 Mathematics Subject Classification: 51E21 Abstract We classify the arcs in PG(2, q), q odd, which consist of (q + 3)/2 points of a conic C and two points not on te conic but external to C, or (q + 1)/2 points of C and two additional points, at least one of which is an internal point of C. We prove that for arcs of the latter type, the number of points internal to C can be at most 4, and we give a complete classification of all arcs that attain this bound. Finally, we list some computer results on extending arcs of both types with further points. 1 Introduction Consider the Desarguesian projective plane PG(2, q) over the finite field of order q, with q odd. For k a positive integer, define a k-arc to be a set S of points of PG(2, q) of size |S| = k, such that no three elements of S are collinear. An arc S is called complete if it is not contained in a bigger arc. When q is odd it is well known that an arc can be of size at most k = q + 1 and that an arc in that case always coincides with the set of points of some conic C (and is complete). It is natural to ask what the second biggest size for a complete arc in PG(2, q) is. Removing some points from a conic C yields an arc, but this arc is obviously not complete. However, removing a sufficient number of points (at least (q − 1)/2, as will be shown later) it may be possible to extend the set thus obtained to an arc by adding a point that does not belong to C. This new arc might not be complete, but can be made complete by adding yet more points. This is the kind of arc we will study in this paper. For many values of q, arcs of this type are among the largest ones known. Let S be any arc. Then we define a conical subset of S to be any subset T of S of the form T = S ∩ C where C is a conic. In this paper, most of the time the conic C and the conical subset T will be clear from context. We will therefore usually leave out the the electronic journal of combinatorics 17 (2010), #R112 1 reference to C when talking about internal or external points of C, tangents and secants of C and lines external to C. def The elements of U = S \T will be called supplementary points and the number e = |U| of supplementary points will be called the excess of the arc. We shall always assume that e > 1, i.e., that S is not fully contained in a conic. Arcs with excess 1 fall into two categories, depending on whether the supplementary point Q is an external or an internal point (of C). When Q is an external point, the arc property for S implies that the two tangents through Q, and each of the (q − 1)/2 secants through Q, may intersect T in at most one point, and hence that |T | 6 (q + 3)/2. Likewise, when Q is an internal point, the (q + 1)/2 secants imply that |T | 6 (q + 1)/2 (there are no tangents through Q in this case). We call conical subsets which attain these bounds large. In this paper we divide the arcs with large conical subsets into three categories : • An arc S of type I has a conical subset of size (q + 1)/2 where all supplementary points are internal points of C. • An arc S of type E has a conical subset of size (q + 3)/2 where all supplementary points are external points of C. • An arc S of type M (for ‘mixed’) has a conical subset of size (q + 1)/2 where some of the supplementary points are internal points of C and some are external points. Only a few arcs are known with large conical subsets and with an excess greater than 2. The primary purpose of this paper is to establish a simple theoretical framework for an extensive computer search for arcs of that type. In Sections 3, 4 and 5 we provide a complete (computer-free) classification of all such arcs with excess 2, up to projective equivalence (i.e., equivalence with respect to the group PGL(3, q)). This classification forms the basis for a fast computer program that classifies arcs with larger excess, for specific values of q. Results of these searches are presented in Section 7. Arcs of this type have also been studied by Pellegrino [5, 6], Korchmáros and Sonnino [3, 4] and Davydov, Faina, Marcugini and Pambianco [2]. In particular, our methods are similar to those of Korchmáros and Sonnino [4], except for a few differences which we think are important : • Instead of using the group structure of a cyclic affine plane of order q, we use the properties of the cyclic group of norm 1 elements of the field GF(q 2 ). This has the advantage that much of the theory that is developed subsequently can be formulated in terms of integers modulo q + 1, i.e., without the explicit use of groups. • As a consequence, we were able to write down a complete classification of the arcs of excess 2 and obtain an explicit formula for the number of inequivalent arcs of that type. • Korchmáros and Sonnino have used a computer algebra system (Magma) to implement their computer searches. Because we do not need the group functionality we could instead implement a very straightforward (and efficient) program in Java. the electronic journal of combinatorics 17 (2010), #R112 2 Also note that Korchmáros and Sonnino only treat arcs of type E. 2 Notation and preliminary definitions Before we proceed to the main part of the paper, we shall first establish some notations and list some elementary results. Most of the properties described here belong to ‘mathematical folklore’ and shall be given without proof. Similar notation and properties are used in [5, 6]. Let K denote the field of order q. In what follows we shall use the abbreviation def 1 r = 2 (q + 1). Without loss of generality we may fix C to be the conic with equation XZ = Y 2 . Mapping t ∈ K to the point with (homogeneous) coordinates (1 : t : t2 ) and ∞ to the point with coordinates (0 : 0 : 1) defines a one–one relation between K ∪ {∞} and C.  Thesubgroup of PGL(3, q) that stabilizes C is isomorphic to PGL(2, q). The matrix b + dt a b . acts on the point with coordinates (1 : t : t2 ) by sending t to c d a + ct With every point Q of the plane that does not belong to C we associate an involution σQ on the points of C, as follows : if P is a point of C, then σQ (P ) is the second intersection of the line P Q with C (or equal to P when P Q is tangent to C). This involution can be extended to the entire plane and corresponds to the matrix   b c def MQ = , −a −b when Q has coordinates (a : b : c). On the plane σQ has exactly q + 2 fixed points: the point Q and the q + 1 points on the polar line of Q with respect to C. The lines fixed by σQ are the q + 1 lines through Q and the polar line of Q. Conversely, every involution of PGL(2, q) has trace zero and must therefore be of the form σQ for some point Q not on C. Q is an external point to C if and only if − det MQ = b2 − ac is a (non-zero) square of K. In that case the two √ points of C whose tangents go through Q have coordinates (1 : t : t2 ) with t = c/(b ± b2 − ac). √ Fix a non-square β of K and let L = K[ β] denote the quadratic extension field of K. Let α be a primitive element of L. Then every element of L∗ can be written as αi for some exponent i which is unique modulo q 2 − 1. For i ∈ Zq2 −1 define ci , si ∈ K to be √ def the ‘real’ and ‘imaginary’ part of αi , i.e., αi = ci + si β. Note that ci , si have properties that are similar to those of the cosine and sine, and therefore it is also natural to define def def a ‘tangent’ ti = si /ci ∈ K ∪ {∞}. We may express ti directly in terms of φ = α/ᾱ, as follows :   1 φi − 1 √ i , when φi 6= −1, ti = (1) βφ +1  i ∞, when φ = −1. the electronic journal of combinatorics 17 (2010), #R112 3 We have the following properties : t0 = tq+1 = 0, ti+j = ti + tj , 1 + ti tj β ti+(q+1) = ti , t−i = −ti , tr = ∞, ti+r = 1 . ti β (Recall that r = (q + 1)/2.) The index i of ti can be treated as an element of Zq+1 . The sequence t0 , t1 , . . . , tq contains every element of K ∪ {∞} exactly once. Let ℓ be an external line of C. Without loss of generality we may assume that ℓ has equation X = βZ. The points of ℓ may be numbered as Q0 , Q1 , . . . , Qq so that Qi has coordinates (si β : ci : si ). When i 6= 0, we may normalize these coordinates to (β : 1/ti : 1), while Q0 has coordinates (0 : 1 : 0). The index i of Qi will be called the orbital index of Qi . Orbital indices can be treated as elements of Zq+1 . The point Qi is an external (resp. internal) point of C if and only if its orbital index i is even (resp. odd). In a similar way, we number the points of the conic C as P0 , P1 , . . . , Pq where Pi has coordinates (1 : ti : t2i ), for i 6= r and Pr has coordinates (0 : 0 : 1). Again, the index i of Pi will be called its orbital index, and again it can be treated as an element of Zq+1 . The following lemma illustrates that orbital indices are a useful concept in this context. Lemma 1 Let i, j, k ∈ Zq+1 . Then • Pi , Pj , Qk are collinear if and only if k = i + j (mod q + 1). • Pi Qk is a tangent to C if and only if k = 2i (mod q + 1). The subgroup G of PGL(3, q) that leaves both the conic C and its external line ℓ invariant, is a dihedral group of order 2(q + 1) whose elements correspond to matrices of the following type :         ci si 1 ti ci si 1 ti def ′ def Mi = ≈ , Mi = ≈ . −si β −ci −ti β −1 s i β ci ti β 1 (The ‘≈’-sign denotes equality upto a scalar factor.) We have i ′ M0′ = 1, Mi′ = M1′ , Mi+j = Mi′ Mj′ . (Again indices can be treated as belonging to Zq+1 .) We shall call these group elements reflections and rotations (reminiscent of similar transformations in the Euclidian plane). Note that the reflections are precisely the involutions σQ for the points of ℓ. Indeed Mi ≈ MQi . Apart from these reflections, the group G contains one more involution: the element Mr′ which could also be written as σR , where R is the pole of ℓ, with coordinates (−β : 0 : 1). The action of the reflections and rotations on C and ℓ is given by Mi : Pj 7→ Pi−j , Mi′ : Pj 7→ Pj+i , Qj 7→ Q2i−j , Qj 7→ Qj+2i . Note the factor 2 in the orbital index of the images of Qj . This ensures that even orbital indices remain even and odd indices remain odd. Indeed, the group G has two orbits on the electronic journal of combinatorics 17 (2010), #R112 4 ℓ, one consisting of external points, the other of internal points. Note that Mr′ stabilizes every point of ℓ. The stabilizer Gk of Qk in G has order 4 and consists of M0′ (the identity), Mr′ , Mk and Mk+r . Gk fixes Qk and Qk+r and interchanges Qi and Q2k−i for i 6= a, a + r. 3 Arcs of type I with excess two In this and the following sections we shall treat arcs S with a large conical subset and excess two. Before we proceed to the case of arcs of type I, we first introduce the following definitions that will be useful in all three cases. Let C be a conic and let U denote a set of points not on that conic (the supplementary points of an arc S, say). Define the graph Γ(C, U) as follows : • Vertices are the elements of Zq+1 , • Two different vertices i, j are adjacent if and only if the line Pi Pj contains a point of U. Note that the degree of a vertex of Γ(C, U) is at most |U|. Let S be an arc with corresponding conical subset T = C ∩ S. Write U = S \ T . Denote by N(T ) the set of orbital indices of vertices of T , i.e., the unique subset of Zq+1 such that T = {Pi | i ∈ N(T )}. Since S is an arc, no pair of points of T can be collinear with one of the supplementary points. Therefore, in Γ(C, U), vertices of N(T ) can never be adjacent. In other words, N(T ) is an independent set of Γ(C, U). We now turn to the case where S denotes an arc of type I with excess two, i.e., |T | = r = (q + 1)/2 and U consists of two points that are internal to C. As was explained in the introduction, each secant line through one of the supplementary points intersects C in exactly one point of T . In particular, since S is an arc, the line that joins the supplementary points cannot contain a third point of S, and hence is not a secant line of C. Because the supplementary points are internal, the line cannot be a tangent to C either and hence it must be an external line. Without loss of generality we may assume this line to be ℓ. All internal points on ℓ lie in a single orbit of G, and therefore we may take the first of the supplementary points to be Q1 . The second supplementary point must have an odd orbital index, and therefore is of the form Q2a+1 . Note that the integer a is only determined up to a multiple of r. Consider the graph Γ = Γ(C, U) = Γ(C, {Q1 , Q2a+1 }). The edges of Γ are of the form {j, 1 − j} and {j, 2a + 1 − j} (by Lemma 1) and therefore Γ must be a regular graph of order q + 1 and of degree 2, i.e., a disjoint union of cycles. Consider the cycle which contains vertex i. We can enumerate the consecutive vertices in this cycle as follows : . . . , i, 1 − i, 2a + i, 1 − 2a − i, 4a + i, 1 − 4a − i, . . . Eventually this sequence starts to repeat, hence either the cycle has length 2n with i = (2na) + i (mod q + 1), or length 2n + 1 with i = 1 − (2na) − i (mod q + 1). The latter the electronic journal of combinatorics 17 (2010), #R112 5 case would imply 2(na + i) = 1 (mod q + 1) which is impossible as q + 1 is even, hence the first case applies. Hence n is equal to the order of 2a (mod q + 1), i.e., n is the smallest positive integer such that na = 0 (mod r). Note that n is independent of the choice of i and therefore all cycles have the same size. This proves the following result. Lemma 2 If S is an arc of type I with supplementary points Q1 and Q2a+1 , then Γ(C, U) consists of d disjoint cycles of length 2n, where n is the order of a (mod r) and d = r/n, i.e., d = gcd(a, r). Note that the largest independent set in a cycle of size 2n has size n and consists of alternating vertices. We shall call these sets half cycles. There are two disjoint half cycles def in each cycle. In our particular example, let Zk = k + 2aZq+1 = k + 2dZq+1 . Define Zk+ = Zk , Zk− = Z1−k . Then Zk+ ∪ Zk− , k = 1, . . . , d, are the cycles that constitute Γ and Zk+ , Zk− are the corresponding half cycles. It is now easy to see that the largest possible independent set of Γ consists of d half cycles, one for each cycle, and therefore has size dn = r. Recall that N(T ) must be an independent set of Γ. This proves the following result. Theorem 1 Let a ∈ {1, . . . , r − 1}. Let d = gcd(a, r). Let S = T ∪ {Q1 , Q2a+1 }, with T ⊂ C and |T | = (q + 1)/2. Then S is an arc of PG(2, q) if and only if N(T ) can be written as a disjoint union of the form N(T ) = Z1± ∪ . . . ∪ Zd± , with independent choices of sign. Every arc listed in Theorem 1 can be uniquely described by its signature I(a; ǫ1 , . . . , ǫd ), where ǫk = ±1 depending on the choice made for the half cycle Zk± . Of course, arcs with different signature can still be projectively equivalent, even for fixed a. More work needs to be done to enumerate all arcs of this type up to equivalence only. Before we proceed, we want to point out that some caution is necessary when q is small. Indeed, in the treatment above, we have always considered the conic C as fixed. However, there are many conics, and therefore for a given arc S there could be several conical subsets that are large. Fortunately, we have the following Lemma 3 Let S be an arc with a conical subset T with excess e. Then the excess e′ of any other conical subset T ′ of S must satisfy e′ > |S| − e − 4 = |T | − 4. Proof : Two different conics can intersect in at most 4 points. Hence also T and T ′ can intersect in at most 4 points. We have |S| + |S| = |T | + e + |T ′ | + e′ = e + e′ + |T ∪ T ′ | + |T ∩ T ′ | 6 e + e′ + |S| + 4, and therefore |S| 6 e + e′ + 4. the electronic journal of combinatorics 17 (2010), #R112 6 Corollary 1 If q > 13, then an arc S of PG(2, q) of size |S| = (q + 5)/2 can contain at most one conical subset with excess at most 2. Proof : Assume S has a conical subset T with excess e 6 2. Then by Lemma 3, any other conical subset must have excess e′ > (q + 5)/2 − e − 4 > 9 − 2 − 4 = 3. Henceforth we shall assume that q > 13. By the above, S determines C uniquely. Any isomorphism between any of the arcs listed in Theorem 1 must therefore leave C invariant, and also the pair of supplementary points and the line ℓ. In other words, any isomorphism of this type must belong to the group G. From Section 2 we know that the elements of G that fix Q1 are the following : M0′ (the identity) : Pj Mr′ : Pj M1 : Pj Mr+1 : Pj 7→ 7 → 7→ 7 → Pj , Pj+r , P1−j , Pr+1−j , Qj Qj Qj Qj 7→ 7 → 7→ 7 → Qj , Qj , Q2−j , Q2−j . (2) Note that the reflections M1 and Mr+1 interchange Q2a+1 and Q1−2a . In other words, for every arc with a signature of the form I(a; ǫ1 , · · · , ǫd ) there is an equivalent arc with a signature of the form I(r − a; ǫ′1 , · · · , ǫ′d ) (or I(−a; · · · ), if you prefer). To enumerate all arcs up to isomorphism, it is therefore sufficient to consider only those a that satisfy 1 6 a 6 r/2. We now consider the case where a is fixed. Theorem 2 Let q > 13, a ∈ {1, . . . , r − 1} d = gcd(a, r) and n = r/d. Further, let Ha denote the subgroup of PG(3, q) that leaves the conic C invariant and fixes the pair {Q1 , Q2a+1 }. Then the elements of Ha are as follows : 1. When n 6= 2 Element of Ha Image of Zk± Image of I(a; ǫ1 , . . . , ǫd ) I(a; ǫ1 , . . . , ǫd ) M0′ (the identity) Zk± Mr′ Zk± I(a; ǫ1 , . . . , ǫd ) when n is even, ∓ = Zd+1−k I(a; −ǫd , . . . , −ǫ1 ) when n is odd. ± Zd+k Ma+1 ± Z1−k = Zk∓ ± Zd+1−k I(a; −ǫ1 , . . . , −ǫd ) when a/d is even, I(a; ǫd , . . . , ǫ1 ) when a/d is odd. Ma+r+1 ± Zd+1−k ± Zd+1−k ± Z1−k = Zk∓ I(a; ǫd , . . . , ǫ1 ) when n is even, a/d is odd, I(a; ǫd , . . . , ǫ1 ) when n is odd, a/d is even, I(a; −ǫ1 , . . . , −ǫd ) when n is odd, a/d is odd. the electronic journal of combinatorics 17 (2010), #R112 7 2. When n = 2 Element of Ha Image of Zk± M0′ (the identity) ± ′ Mr/2 Zd+k Mr′ ± ′ M3r/2 Zd+k M1 Mr/2+1 Mr+1 M3r/2+1 Zk± ∓ = Zd+1−k Zk± ∓ = Zd+1−k ± Z1−k = Zk∓ ± Zd+1−k ± Z1−k = Zk∓ ± Zd+1−k Image of I(a; ǫ1 , . . . , ǫd ) I(a; ǫ1 , . . . , ǫd ) I(a; −ǫd , . . . , −ǫ1 ) I(a; ǫ1 , . . . , ǫd ) I(a; −ǫd , . . . , −ǫ1 ) I(a; −ǫ1 , . . . , −ǫd ) I(a; ǫd , . . . , ǫ1 ) I(a; −ǫ1 , . . . , −ǫd ) I(a; ǫd , . . . , ǫ1 ) Proof : (Note that n = r/d and a/d can not both be even, for otherwise 2d would be a divisor of both a and r, contradicting d = gcd(a, r). The case n = 2 is equivalent to a = r/2, and then d = a.) Note that Ha fixes the line ℓ and hence is a subgroup of G. Any element of Ha must either fix the points Q1 and Q2a+1 or interchange them. From (2) we easily derive that the identity and Mr′ will fix both points, and so will M1 and Mr+1 provided that (2a + 1) = 2 − (2a + 1), i.e., when 4a = 0, i.e., a = r/2. Similarly, it is easily proved that the following elements of G are those that map Q1 onto Q2a+1 : Ma′ : Pj 7→ Pi+j , Qj 7→ Qj+2a , ′ Ma+r : Pj 7→ Pa+r+j , Qj 7→ Qj+2a , Ma+1 : Pj 7→ Pa+1−j , Qj 7→ Q2a+2−j , Ma+r+1 : Pj 7→ Pa+r+1−j , Qj 7→ Q2a+2−j . ′ and hence Ma+1 and Ma+r+1 interchange Q1 and Q2a+1 , and so do Ma′ and Ma+r when 4a = 0, i.e., a = r/2. To complete the proof, we compute the action of these isomorphisms on the half cycles Zk . (And from these, the action on the signatures can be easily computed.) A rotation of the form Mi′ maps a vertex k of Γ to the vertex k + i. Hence Zk = k + 2dZq+1 is mapped to k + i + 2dZq+1 = Zk+i. Similarly, the reflection Mi maps k to i − k and hence Zk = k + 2dZq+1 to i − k − 2dZq+1 = Zi−k . Note that indices of half cycles can be treated modulo 2d. For example, as r is a multiple of d, Zk+r is equal to either Zk or Zk+d, depending on whether n = r/d is even or odd. Similarly, Za+1−k is either Z1−k or Zd+1−k depending on the parity of a/d. (Although this theorem is valid for all a ∈ {1, . . . , r}, we only need it when a 6 r/2, as explained earlier.) The group Ha in Theorem 2 contains precisely the projective equivalences that exist among the arcs listed in Theorem 1, for fixed a. The information given on the images of the signatures in the various cases allows us to compute the automorphism groups of the corresponding arcs. the electronic journal of combinatorics 17 (2010), #R112 8 Corollary 2 Let q > 13. Let HS denote the subgroup of PGL(3, q) that leaves invariant the arc S with signature I(a; ǫ1 , . . . , ǫd ). 1. If n is even and n 6= 2, then • HS = {M0′ , Mr′ , Ma+1 , Ma+r+1 } if and only if ǫd = ǫ1 , ǫd−1 = ǫ2 , . . ., • HS = {M0′ , Mr′ } otherwise. 2. If n is odd and a/d is odd, then • HS = {M0′ , Mr′ } if and only if ǫd = −ǫ1 , ǫd−1 = −ǫ2 , . . . (d even), • HS = {M0′ , Ma+1 } if and only if ǫd = ǫ1 , ǫd−1 = ǫ2 , . . ., • HS = {M0′ } otherwise. 3. If n is odd and a/d is even, then • HS = {M0′ , Mr′ } if and only if ǫd = −ǫ1 , ǫd−1 = −ǫ2 , . . . (d even), • HS = {M0′ , Ma+r+1 } if and only if ǫd = ǫ1 , ǫd−1 = ǫ2 , . . ., • HS = {M0′ } otherwise. 4. If n = 2, then ′ ′ • HS = {M0′ , Mr/2 , Mr′ , M3r/2 } if and only if ǫd = −ǫ1 , ǫd−1 = −ǫ2 , . . . (d even), • HS = {M0′ , Mr′ , Mr/2+1 , M3r/2+1 } if and only if ǫd = ǫ1 , ǫd−1 = ǫ2 , . . ., • HS = {M0′ , Mr′ } otherwise. The theorems above provide us with sufficient information to count the number of arcs of type I for given q. Again we first consider the case where a is fixed. Lemma 4 Let Iq (a) denote the number of projectively inequivalent arcs S with a signature of the form I(a; ǫ1 , . . . , ǫd ), with d = gcd(a, (q + 1)/2). Then ( d−2 when q+1 is odd or q+1 = 2, 2d−2 + 2⌊ 2 ⌋ , 2d 2d (3) Iq (a) = d−1 q+1 q+1 ⌊ 2 ⌋ d−1 2 +2 , when 2d is even and 2d 6= 2. Proof : The number Iq (a) is obtained by summing the value of 1/|S Ha | over all arcs S with a signature of the form I(a; ǫ1 , . . . , ǫd ), where Ha is as in Theorem 2 and |S Ha | is the size of the orbit of Ha on this arc. We have |S Ha | = |Ha |/|HS |, where |HS | can be derived from Corollary 2. The number of signatures with ǫd = ǫ1 , ǫd−1 = ǫ2 , . . . is equal to 2d/2 when d is even, and to 2(d+1)/2 when d is odd, i.e., 2⌊(d+1)/2⌋ for general d. Similarly the number of signatures the electronic journal of combinatorics 17 (2010), #R112 9 with ǫd = −ǫ1 , ǫd−1 = ǫ2 , . . . is equal to 2d/2 when d is even, and is zero when d is odd. The sum of these two values is equal to 2⌊(d+2)/2⌋ for general d. P The four cases of Corollary 2 now lead to the following values for Iq (a) = |HS |/|Ha| : 1. If n is even and n 6= 2, then Iq (a) = 2⌊ d+1 ⌋ 2 d+1 d−1 1 + (2d − 2⌊ 2 ⌋ ) = 2d−1 + 2⌊ 2 ⌋ . 2 2 and 3. If n is odd, then d+2 d−2 1 d+2 1 Iq (a) = 2⌊ 2 ⌋ + (2d − 2⌊ 2 ⌋ ) = 2d−2 + 2⌊ 2 ⌋ . 2 4 4. If n = 2, then d+2 d−2 1 d+2 1 Iq (a) = 2⌊ 2 ⌋ + (2d − 2⌊ 2 ⌋ ) = 2d−2 + 2⌊ 2 ⌋ . 2 4 Theorem 3 Let q > 13. The number Iq of projectively inequivalent arcs S in PG(2, q) of size |S| = (q + 5)/2, with a conical subset T = S ∩ C of size |T | = (q + 1)/2 such that the elements of S \ T are internal points of C, is given by X′ 1  q + 1  ⌈ φ ⌉Iq (d) 2 2d d where the sum is taken over all proper divisors d of (q + 1)/2, φ denotes Eulers totient function, and Iq (d) is as given in Lemma 4. P⌊r/2⌋ Proof : The total number of inequivalent arcs is given by a=1 Iq (a). Note that Iq (a) does not directly depend on a, but only on d = gcd(a, r). The number of integers a, 1 6 a < r such that d = gcd(a, r) is equal to φ(r/d) = φ(n). If we restrict ourselves to a 6 r/2 we obtain φ(n)/2 values, except when a = d = r/2 (or equivalently n = 2) in which case there is 1 value. Note that φ(2) = 1 and hence ⌈ 12 φ(n)⌉ = 1 in this case. 4 Arcs of type E with excess two The arcs of type E are in many aspects very similar to those of type I in the previous section. We shall therefore mainly focus on the differences between both cases. Arcs of type E have a conical subset T of size |T | = (q + 3)/2 (which is one larger than in the other cases). As a consequence, not only must all secants through a given supplementary point Q contain exactly one point of T , but also the tangents through Q must contain a point of T . (The points of T on these tangents will be called the tangent points of Q.) As a consequence, again any line through two supplementary points must be external. the electronic journal of combinatorics 17 (2010), #R112 10