On small dense sets in Galois planes
M. Giulietti(cid:3) Dipartimento di Matematica e Informatica Universit(cid:18)a di Perugia, Italy giuliet@dipmat.unipg.it
Submitted: Jul 17, 2007; Accepted: Oct 31, 2007; Published: Nov 5, 2007 Mathematics Subject Classi(cid:12)cation: 51E20
Abstract
This paper deals with new in(cid:12)nite families of small dense sets in desarguesian projective planes P G(2; q). A general construction of dense sets of size about 3q 2=3 is presented. Better results are obtained for speci(cid:12)c values of q. In several cases, an improvement on the best known upper bound on the size of the smallest dense set in P G(2; q) is obtained.
1 Introduction
K
K
in P G(2; q), the projective plane coordinatized over the (cid:12)nite (cid:12)eld with q A dense set elements Fq, is a point-set whose secants cover P G(2; q), that is, any point of P G(2; q) . As well as being a natural geometrical belongs to a line joining two distinct points of problem, the construction of small dense sets in P G(2; q) is relevant in other areas of Combinatorics, as dense sets are related to covering codes, see Section 4, and de(cid:12)ning sets of block designs, see [2]; also, it has been recently pointed out in [13] that small dense sets are connected to the degree/diameter problem in Graph Theory [17].
(cid:21)
A straightforward counting argument shows that a trivial lower bound for the size k p2q, see e.g. [19]. On the other hand, for q square there of a dense set in P G(2; q) is k is a nice example of a dense set of size 3pq, namely the union of three non-concurrent lines of a subplane of P G(2; q) of order pq.
3
c 5pqlogq b
(cid:3)This research was performed within the activity of GNSAGA of the Italian INDAM, with the (cid:12)nancial support of the Italian Ministry MIUR, project \Strutture geometriche, combinatorica e loro applicazioni", PRIN 2006-2007
the electronic journal of combinatorics 14 (2007), #R75
1
If q is not a square, however, the trivial lower bound is far away from the size of was shown by means the known examples. The existence of dense sets of size of probabilistic methods, see [2, 14]. The smallest dense sets explicitly constructed so 4 , with c a constant independent on q, see [1, 9, 18]; for far have size approximately cq
3
4 .
2
3 , see Theorem 3.2. For large non-square q, q
a survey see [2, Sections 3,4]. A construction by Davydov and (cid:127)Osterg(cid:23)ard [6, Thm. 3] provides dense sets of size 2q=p + p, where p is the characteristic of Fq; note that in the special case where q = p3, p 17, the size of these dense sets is less than q (cid:21)
6
The main result of the present paper is a general explicit construction of dense sets = p3, these are in P G(2; q) of size about 3q the smallest explicitly constructed dense sets, whereas for q = p3 the size is the same as that of the example by Davydov and (cid:127)Osterg(cid:23)ard.
Using the same technique, smaller dense sets are provided for speci(cid:12)c values of q, see Theorem 3.7 and Corollary 3.8; in some cases they even provide an improvement on the probabilistic bound, see Table 1.
Our constructions are essentially algebraic, and use linearized polynomials over the (cid:12)nite (cid:12)eld Fq. For properties of linearized polynomials see [15, Chapter 3]. In the a(cid:14)ne line AG(1; q), take a subset A whose points are coordinatized by an additive subgroup H of Fq. Then H consists of the roots of a linearized polynomial LH (X). Let D1 be the union of two copies of A, embedded in two parallel lines in AG(2; q), namely the lines with equation Y = 0 and Y = 1. The condition for a point P = (u; v) in AG(2; q) to belong to some secant of D1 is that the equation
LH (X) vLH(Y ) + u = 0 (cid:0)
has at least one solution in Fq2. This certainly occurs when the equation
(1) LH(X) vLH(Y ) = 0 has precisely q solutions in F2 q. (cid:0)
This leads to the purely algebraic problem of determining the values of v for which (1) holds. A complete solution is given in Section 2, see Proposition 2.5, by showing that v belongs to the set Fq n MH, with this occurs if and only if (cid:0)
: (2) (cid:26) MH := LH1((cid:12)1)p LH2((cid:12)2)p (cid:27)
H = = p, while Hi j j j j H Hi. n
v (cid:0)
the electronic journal of combinatorics 14 (2007), #R75
2
Here, H1 and H2 range over all subgroups of H of index p, that is (cid:12)i 2 This shows that the points which are not covered by the secants of D1 are the points P = (u; v) with 2 MH. The (cid:12)nal step of our construction consists in adding a possibly small number of points Q1; : : : ; Qt to D1 to obtain a dense set. For the general case, this is done by just ensuring that the secants QiQj cover all points uncovered by the secants of D1. For special cases, the above construction can give better results when more than two copies of A are used. It should be noted that sometimes in the literature dense sets are referred to as 1- saturating sets as well.
2 On the number of solutions of certain equations
over Fq
‘. (cid:20) Let q = p‘ with p prime, and let H be an additive subgroup of Fq of size ps with 2s Also, let
(3) (X h) LH (X) = Fq[X]: (cid:0) 2 Yh2H
s
i=0 (cid:12)iX pi; see e.g. [15, Theorem 3.52]. For m
Fq such that LH (X) = Then LH is a linearized polynomial, that is, there exist (cid:12)0; : : : ; (cid:12)s 2
Fq, let P 2 Fm(X; Y ) = LH (X) mLH (Y ): (cid:0) As the evaluation map (x; y) Fm(x; y) is an additive map from F2 7!
Fm(X; Y ) = 0 has at least q solutions in F2 what m (4) q to Fq, the equation q. The aim of this section is to determine for Fq the number of solutions of Fm(X; Y ) = 0 is precisely q, see Proposition 2.5. 2 Let Fp denote the prime sub(cid:12)eld of Fq.
q of the equation Fm(X; Y ) = 0
Fp, then the number of solutions in F2 2 Lemma 2.1. If m is qps.
Proof. Note that as m Fp, mLH(Y ) = LH(mY ) holds. Then, 2
mY mY ) = (X h): Fm(X; Y ) = LH(X (cid:0) (cid:0) (cid:0) Yh2H
q, the claim follows.
mY As the equation X h = 0 has q solutions in F2 (cid:0) Lemma 2.2. For any (cid:11) (cid:0) Fq, 2
X p (cid:11)p(cid:0)1X = (X i(cid:11)) : (cid:0) (cid:0) Yi2Fp
p
Proof. The assertion is trivial for (cid:11) = 0. For (cid:11) = 0, the claim follows from 6
i : (X i(cid:11)) = (cid:11)p = (cid:11)p (cid:18) (cid:19) X (cid:11) (cid:19) X (cid:11) (cid:19) (cid:18)(cid:18) X (cid:11) (cid:0) (cid:0) (cid:0) Yi2Fp Yi2Fp
H For any subgroup H 0 of H of size ps(cid:0)1, pick an element (cid:12) H 0 and let 2 n
(5) aH 0 = LH 0((cid:12))p(cid:0)1:
Note that aH 0 does not depend on (cid:12). In fact,
the electronic journal of combinatorics 14 (2007), #R75
3
h0 i(cid:12)) = (X h) = (X i(cid:12)) = (LH 0(X) iLH 0((cid:12))) ; LH 0(X (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) Yi2Fp Yi2Fp Yh02H 0 Yi2Fp Yh2H
and then, by Lemma 2.2,
(6) LH (X) = LH 0(X)p aH 0LH 0(X): (cid:0)
Also, if aH1 = aH2 holds for two subgroups H1 and H2 of H, then by (6) it follows that
(LH1(X) LH2(X))p = aH1(LH1(X) LH2(X)); (cid:0) (cid:0)
this yields LH1 (X) = LH2 (X), whence H1 = H2. Let
: H (7) Hi(cid:27) (cid:26) MH := H1; H2 subgroups of H of size ps(cid:0)1; (cid:12)i 2 n
Note that for any (cid:21) LH1((cid:12)1)p LH2((cid:12)2)p j Fp, 2
LH1((cid:21)(cid:12)1)p LH2((cid:12)2)p = (cid:21)
LH1((cid:12)1)p LH2((cid:12)2)p ; = 0. In particular, whence (cid:21) MH = MH holds provided that (cid:21) 6
(8) MH:
(cid:0)MH = As H1 = H2 is allowed in (7), we also have that
(9) F(cid:3) p (cid:18) MH:
H H2, in such a H1, and (cid:12)2 2 n n Lemma 2.3. For any m Proof. Fix H1, H2 subgroups of H of size ps(cid:0)1, (cid:12)1 2 way that m = LH1 ((cid:12)1)p LH2 ((cid:12)2)p . Let (cid:11) = LH1 ((cid:12)1) 2 MH, the equation Fm(X; Y ) = 0 has at least pq solutions. H LH2 ((cid:12)2) . We claim that
(10) Fm(X; Y ) = (LH1(X i(cid:12)1) (cid:11)LH2(Y )): (cid:0) (cid:0) Yi2Fp
In order to prove (10), note (cid:12)rst that by Lemma 2.2
(LH1(X i(cid:12)1) (cid:11)LH2(Y )) = (LH1(X) (cid:11)LH2(Y ))p aH1(LH1(X) (cid:11)LH2(Y )): (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) Yi2Fp
Then, Equation (6) for H 0 = H1 gives
(LH1(X i(cid:12)1) (cid:11)LH2(Y )) = LH(X) (cid:11)pLH2(Y )p + aH1(cid:11)LH2(Y ): (cid:0) (cid:0) (cid:0) Yi2Fp
q to Fq. As the solutions of LH1(X
the electronic journal of combinatorics 14 (2007), #R75
4
As aH1(cid:11) = (cid:11)paH2 and m = (cid:11)p, Equation (6) for H 0 = H2 implies (10). Now, the set of solutions of LH1(X) (cid:0) i(cid:12)1) (cid:0) (cid:11)LH2(Y ) = 0 has size at least q, as it is the (cid:11)LH2(Y ) = 0 X + i(cid:12)1, (10) (cid:11)LH2(Y ) = 0 by the substitution X (cid:0) (cid:0) 7! nucleus of an Fp-linear map from F2 are obtained from those of LH1(X) yields that Fm(X; Y ) = 0 has at least pq solutions.
Lemma 2.4. The size of 1)2=(p 1). MH is at most (ps (cid:0) (cid:0)
p(cid:0)1
Proof. Note that for each pair H1; H2 of subgroups of H of size ps(cid:0)1 there are precisely p 1 elements in (cid:0)
: = (cid:18) MH of type LH1((cid:12)1)p=LH2((cid:12)2)p. In fact, LH1 ((cid:12)1)p LH2 ((cid:12)2)p (cid:19) ap H1 ap H2
2
As aH1=aH2 only depends on H1 and H2, the claim follows. Now, the number of additive subgroups of H of size ps(cid:0)1 is (ps 1)=(p 1). Therefore (cid:0) (cid:0) MH consists of at most (p 1) ps p 1 1 (cid:19) (cid:0) (cid:1) (cid:18) (cid:0) (cid:0) elements.
We are now in a position to prove the main result of the section.
Proposition 2.5. Let Fm(X; Y ) be as in (4). The equation Fm(X; Y ) = 0 has more than 2 MH or m = 0. q solutions if and only if either m
q=F(cid:3)
p. Consider the map
6 = 0. Denote p the factor group of the Proof. The claim for m = 0 follows from Lemma 2.1. Assume then that m (cid:23)m the number of solutions of Fm(X; Y ) = 0. Also, denote F(cid:3) multiplicative group of F(cid:3)
q=F(cid:3) F(cid:3)
p
LH1 ((cid:12)1)p LH2 ((cid:12)2)p
q by F(cid:3) H1; H2 subgroups of H of size ps(cid:0)1; H1 6 7!
(cid:8) : (H1; H2) f j = H2g ! (H1; H2) F(cid:3) p ;
i)p
p, as
i 2 i)p(cid:0)1 = aHi
H H Hi, LHi((cid:12)i)p = (cid:21)LHi((cid:12)0 n Hi. Note that (cid:8) is well de(cid:12)ned: for any (cid:12)i; (cid:12)0 F(cid:3) with (cid:12)i 2 for some (cid:21) n 2 LHi((cid:12)i)p(cid:0)1 = LHi((cid:12)0
p) is related to (cid:23)(cid:22). More precisely,
(see (5)). For any (cid:22) 2 MH, the size of (cid:8)(cid:0)1((cid:22)F(cid:3)
(cid:23)(cid:22) q (cid:0) p 1
1 : (11) #(cid:8)(cid:0)1((cid:22)F(cid:3) p) (cid:20) (cid:0) In order to prove (11), write the unique factorization of F(cid:22) as follows:
: : : F(cid:22)(X; Y ) = P1(X; Y ) P2(X; Y ) Pr(X; Y ): (cid:1) (cid:1) (cid:1)
p. Let (cid:11) = LH1 ((cid:12)1)
LH2 ((cid:12)2) , and note that, by Equation (10),
Note that the multiplicity of each factor is 1. In fact, all the roots of LH(X) are sim- ple, whence both the partial derivatives of F(cid:22) are non-zero constants. Assume that (cid:8)(H1; H2) = (cid:22)F(cid:3)
p
the electronic journal of combinatorics 14 (2007), #R75
5
F(cid:22)(X; Y ) = (LH1(X) (cid:11)LH2(Y )) (LH1(X i(cid:12)1) (cid:11)LH2(Y )) : (cid:0) (cid:0) (cid:0) Yi2F(cid:3)
2
2 Assume without loss of generality that P1(0; 0) = 0, so that P1(X; Y ) divides LH1(X) (cid:0) (cid:11)LH2(Y ). We consider two actions of the group H on the set of irreducible factors of F(cid:22). H, let (Pi(X; Y ))(cid:27)1(h) = Pi(X + h; Y ), and (Pi(X; Y ))(cid:27)2(h) = Pi(X; Y + h). For each h Assume that the stabilizer S1 of P1(X; Y ) with respect to the action (cid:27)1 has order pt. Then the X-degree of P1(X; Y ) is at least pt. Note also that the orbit of P1(X; Y ) with respect to (cid:27)1 consists of ps(cid:0)t factors, each of which has X-degree not smaller than pt. As the X-degree of F(cid:22) is ps, we have that r = ps(cid:0)t, and that the X-degree of P1(X; Y ) is precisely pt. Taking into account that S1 stabilizes P1(X; Y ), we have that for any h S1 the polynomial X + h divides P1(X; Y ) P1(0; Y ), whence (cid:0)
(12) P1(X; Y ) P1(0; Y ) = Q(Y )LS1(X) (cid:0)
be the order of S2. The above argument yields that r = ps(cid:0)t0 for some polynomial Q. Now, let S2 be the stabilizer of P1(X; Y ) under the action (cid:27)2, and let pt0 , and therefore t = t0. Also,
P1(X; 0) = (cid:22)Q(X)LS2(Y ) P1(X; Y ) (cid:0)
(13) for some polynomial (cid:22)Q. As the degrees of P1(X; Y ), LS1(X), LS2(Y ) are all equal to pt, Equation (12) together with (13) imply that
P1(X; Y ) = (cid:13)LS1(X) (cid:13)0LS2(Y ); (cid:0)
for some (cid:13)0, (cid:13) Fq. Therefore, 2 qr = qps(cid:0)t: (cid:23)(cid:22) (cid:21)
(cid:0) (cid:0)
2. Then
As P1(X; Y ) divides LH1(X) (cid:11)LH2(Y ), and as H1 is the stabilizer of the set of factors (cid:11)LH2(Y ) with respect to the action (cid:27)1, the group S1 is a subgroup of H1. of LH1(X) The number of possibilities for subgroups H1 is then less than or equal to the number of subgroups of H of size ps(cid:0)1 containing S1, which is ps(cid:0)t(cid:0)1 p(cid:0)1 . Also, for a (cid:12)xed H1, there is at most one possibility for H2; in fact, (cid:8)(H1; H2) = (cid:8)(H1; H 0 2) yields aH2 = aH 0 2, which has already been noticed to imply H2 = H 0
1 ; #(cid:8)(cid:0)1((cid:22)F(cid:3) p) ps(cid:0)t p (cid:0) 1 (cid:20) (cid:0)
q such
F2 and therefore (11) is ful(cid:12)lled. Now, let M be the size of Fp. By counting the number of pairs (x; y) MH n 2 = 0, we obtain that LH (x) = 0 and LH (y) 6 6
q
p2s) : ps)2 = (q ((cid:23)m (cid:0) (cid:0) Xm2F(cid:3)
Then, taking into account Lemma 2.1,
the electronic journal of combinatorics 14 (2007), #R75
6
p (14) ps)2 (q (p 1)(qps p2s) + (q M )(q p2s) M p2s + (cid:23)(cid:22): (cid:0) (cid:21) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) X(cid:22)2MH nFp
Note that if equality holds in (14), then the proposition is proved. Straightforward com- putation yields that (14) is equivalent to
M + (ps p)(ps 1): (cid:0) (cid:23)(cid:22) q (cid:20) (cid:0) (cid:0) X(cid:22)2MH nFp
Let Mv be the number of elements (cid:22) in Fp such that (cid:23)(cid:22) = qpv. Then
M + 1): Mv(pv MH n (cid:23)(cid:22) = q (cid:0) (cid:0) Xv X(cid:22)2MH nFp
p) = (p
p2Im((cid:8))
= (ps p)(ps 1): 1) 1)2#(cid:8)(cid:0)1((cid:22)F(cid:3) (p Mv(pv On the other hand, taking into account (11), we obtain that 1)2 ps p ps p 1 1 p 1 (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) Xv (cid:21) X(cid:22)F(cid:3) (cid:0) (cid:0) (cid:0) (cid:0)
Therefore equality must hold in (14), and the claim is proved.
3 Dense sets in P G(2; q)
‘, let LH(X) be as in (cid:20) Let q = p‘. For an additive subgroup H of Fq of size ps with 2s (3), and 2
a P G(2; q): (15) MH be as in (7). For an element (cid:11) (LH (a) : (cid:11) : 1) DH;(cid:11) = f j Fq, de(cid:12)ne Fqg (cid:26) 2
As a corollary to Proposition 2.5, the following result is obtained.
(cid:11)1) DH;(cid:11)2 provided that v = 2
(cid:11)1) ((cid:11)2 (cid:0) 6 Proposition 3.1. Let (cid:11)1; (cid:11)2 be distinct elements in Fq. Then a point P = (u : v : 1) MH + (cid:11)2. belongs to a line joining two points of DH;(cid:11)1 [ ((cid:11)2 (cid:0) Proof. Assume that v = = (cid:11)2. Then by Proposition 2.5, 2 the equation
LH(Y ) = 0 LH(X) + MH + (cid:11)2 and that v (cid:11)2 (cid:11)2 v (cid:0) (cid:11)1 (cid:0) has precisely q solutions, or, equivalently, the additive map
(x; y) LH (x) + LH (y) 7! (cid:11)2 (cid:11)2
is surjective. This yields that there exists b; b0 Fq such that
LH (b) + v (cid:0) (cid:11)1 (cid:0) 2 LH(b0) = u; (cid:11)2 (cid:11)2 v (cid:0) (cid:11)1 (cid:0)
the electronic journal of combinatorics 14 (2007), #R75
7
which is precisely the condition for the point P = (u : v : 1) to belong to the line joining (LH (b0 + b) : (cid:11)1 : 1) DH;(cid:11)1 and (LH(b) : (cid:11)2 : 1) 2 2 a DH;(cid:11)2. If v = (cid:11)2, then clearly P is collinear with two points in (LH (a) : (cid:11)2 : 1) f j Fqg . 2
Theorem 3.2. Let q = p‘, and let H be any additive subgroup of Fq of size ps, with 2s ‘. Let LH (X) be as in (3), and (cid:20)
a m D = MH be as in (7). Then the set Fqg [ f (0 : m : 1) 2 j j 2 MHg (0 : 1 : 0); (1 : 0 : 0) (LH(a) : 1 : 1); (LH(a) : 0 : 1) f [ f g
is a dense set of size at most
+ 1: 2q ps + (ps p 1)2 1 (cid:0) (cid:0)
2
a The set is the image of an Fp-linear map on Fq (cid:24)= F‘ LH(a) f j
m a 2 Fqg and (0 : m : 1) 2 Fqg 2 MHg 2 f j Proof. Let P = (u : v : 1) be a point in P G(2; q). If v = 2 MH, then P belongs to the line joining two points of D by Proposition 3.1, together with (8). If v 2 MH, then P is collinear with (0 : v : 1) D. Clearly the points P = (u : v : 0) are D and (1 : 0 : 0) covered by D as they are collinear with (1 : 0 : 0) and (0 : 1 : 0). Then D is a dense set. p whose kernel has dimension s, therefore its size is p‘(cid:0)s. Note that the point (0 : 1 : 1) belongs to both (LH(a) : 1 : 1) . Then the upper bound on the f j size of D follows from Lemma 2.4.
2
1 3 +1
3 + 1 + q
as The order of magnitude of the size of D of Theorem 3.2 is pmaxf‘(cid:0)s;2s(cid:0)1g. If s is chosen , then the size of D satis(cid:12)es ‘=3 e d
2
2 3
1 3 +1
2 3 (cid:0)2q p(cid:0)1 p2( q p )
q p
2
1 3 +1
2 3 (cid:0)2(qp) p(cid:0)1
p, and then the size of D is 2 q
3 + 1 + (qp) ; MH coincides with F(cid:3) p + p. A dense set of the same size and contained in three non-concurrent lines was constructed in [6, Thm. 3]. It can be proved by straightforward computation that it is not projectively equivalent to any dense set D constructed here.
if ‘ (mod 3) 0 2q (cid:17) : #D ; + 1 + 2 if ‘ (mod 3) 1 ; 3 (cid:0)2p( q p ) p(cid:0)1 (cid:20) (cid:17) (mod 3) if ‘ 2 (cid:16) (cid:17) 2 1 p (qp) (cid:17) 8 >>>< >>>: Note that when s = 1, then
In order to obtain a new upper bound on the size of the smallest dense set in P G(2; q), a be any subset of k elements (cid:11)1; : : : ; (cid:11)kg f generalization of Theorem 3.2 is useful. Let A = of Fq, and let
D(A) = (A) = (16) (cid:11)i) DH;(cid:11)i ; M ((cid:11)j (cid:0) MH + (cid:11)j: [i=1;:::;k \i;j=1;:::;k; i6=j
Arguing as in the proof of Theorem 3.2, the following result can be easily obtained from Proposition 3.1.
Theorem 3.3. The set
m D(H; A) = D(A) (0 : m : 1) (A) (0 : 1 : 0); (1 : 0 : 0) [ f j 2 M g [ f g
the electronic journal of combinatorics 14 (2007), #R75
8
is dense in P G(2; q).
M Computing the size of D(H; A) is di(cid:14)cult in the general case, as we do not have (A). However, by using some counting argument it is enough information on the set possible to prove the existence of sets A for which a useful upper bound on the size of (A) can be established.
M Proposition 3.4. For any v > 1, there exists a set A Fq of size v + 1 such that (cid:26)
# (A) (# (q M (cid:20) MH)v 1)v(cid:0)1 : (cid:0)
q. Then there exists some (cid:11)
In order to prove Proposition 3.4, the following two lemmas are needed.
F(cid:3) q 2 Lemma 3.5. Let E1 and E2 be any two subsets of F(cid:3) such that #E1#E2 : (cid:11)E2) q 1 (cid:20) (cid:0)
q consisting of those (cid:11) for which (cid:12)
(cid:11)E2. #(E1 \ q, let E((cid:12)) be the subset of F(cid:3) F(cid:3) 2 2 Proof. For any (cid:12) Then
q)2
q
q
(cid:12) E((cid:12)). Therefore, (17)
(cid:12) ((cid:11); (cid:12)) (F(cid:3) = (17) #(cid:11)E2 = (q 1)#E2: #E((cid:12)) = # f 2 (cid:11)E2g 2 j (cid:0) X(cid:12)2F(cid:3) X(cid:11)2F(cid:3)
q. Then
F(cid:3) Note that the size of E ((cid:12)) does not depend on (cid:12), since E ((cid:12)0) = (cid:12)0 yields that #E((cid:12)) = #E2 for any (cid:12) 2
q)2
q
(cid:12) ((cid:11); (cid:12)) (F(cid:3) = #E1#E2 = (cid:11)E2); #E((cid:12)) = # f 2 E1 \ (cid:11)E2g 2 j #(E1 \ X(cid:12)2E1 X(cid:11)2F(cid:3)
q, and let v be an integer greater than 1. Then there
whence the claim follows.
F(cid:3) Lemma 3.6. Let E be a subset of F(cid:3) q such that exist (cid:11)1 = 1; (cid:11)2; : : : ; (cid:11)v 2
# (#E)v(q 1)1(cid:0)v: (cid:11)iE (cid:20) (cid:0) \i:=1;:::;v
q such that
(cid:20) F(cid:3) Proof. We prove the assertion by induction on v. For v = 2 the claim is just Lemma 3.5 for E1 = E2 = E. Assume that the assertion holds for any v0 v. Then there exist (cid:11)1 = 1; (cid:11)2; : : : ; (cid:11)v(cid:0)1 2
# (#E)v(cid:0)1(q 1)2(cid:0)v: (cid:11)iE (cid:20) (cid:0) \i:=1;:::;v(cid:0)1
the electronic journal of combinatorics 14 (2007), #R75
9
Lemma 3.5 for E1 = \i:=1;:::;v(cid:0)1(cid:11)iE, E2 = E, yields the assertion.
F(cid:3) q such that # Proof of Proposition 3.4. According to Lemma 3.6, there exist (cid:11)1 = 1; (cid:11)2; : : : ; (cid:11)v 2 (# 1)1(cid:0)v: (cid:11)iMH (cid:20) (cid:0) MH)v(q (cid:0) \i:=1;:::;v
Let A = , and let (A) be as in (16). As 0; (cid:11)1; : : : ; (cid:11)ng f M
(A) M (cid:11)iMH; (cid:0) (cid:18) \i:=1;:::;v
2 the claim follows. As a straightforward corollary to Theorems 3.3 and 3.2, and Proposition 3.4, the following result is then obtained.
Theorem 3.7. Let q = p‘, with ‘ odd. Let H be any additive subgroup of Fq of size ps, MH be as in (7). Then for any integer with 2s + 1 = ‘. Let LH (X) be as in (3), and v 1 there exists a dense set D in P G(2; q) such that (cid:21)
#D (v + 1)ps+1 + (# 1)1(cid:0)v + 2: (18) (cid:20) MH)v(q (cid:0)
Corollary 3.8. Let q = p2s+1. Then there exists a dense set in P G(2; q) of size less than or equal to 1)2v : (v + 1)ps+1 + (cid:0) (ps 1)v(p(2s+1) (p 1)(v(cid:0)1) + 2 (cid:27) min v=1;:::;2s+1 (cid:26) (cid:0) (cid:0) Proof. The claim follows from Theorem 3.7, together with Lemma 2.4.
For several values of s and p, Corollary 3.8 improves the probabilistic bound on the size of the smallest dense set in P G(2; q), namely, there exists some integer v such that
1)2v (v + 1)ps+1 + q log q; (19) (cid:0) (ps 1)v(p(2s+1) (p 1)(v(cid:0)1) + 2 < 5 p (cid:0) (cid:0)
the electronic journal of combinatorics 14 (2007), #R75
10
see Table 1.
Table 1 - Values of p; s; v for which (19) holds
1
p p [5; 29] p p = 3 p [5; 13] 2 p = 3 p = 5 2 p = 3 p p p p p p p [3; 79] [3; 53] [2; 83] [2; 53] [7; 31] p p = 3 p = 5 p = 7 p = 3 p p 2 2 2 2 p = 2 2 p = 3 [5; 7] p p [3; 73] [5; 23] 2 p = 2 [5; 7] 2 [11; 17] 2 p = 3 p = 5 p p [3; 47] 2 p = 3 p = 5 [7; 13] p [7; 29] 2 p = 3 2 p = 3 p = 5 p = 7 p = 3 p p 2 p = 2 p = 3 2 p = 3 [5; 7] p p p [5; 61] [5; 23] 2 p = 2 p [3; 43] 2 p = 3 p = 5 [5; 7] 2 [11; 13] 2 p = 3 p = 5 p p [7; 23] [7; 13] 2 p = 2 p = 3 2 p = 3 2 p = 3 p p p [5; 47] [5; 19] p 2 p = 2 p = 3 2 p = 3 p = 5 p p [5; 37] [7; 23] [5; 7] 2 [11; 13] 2 p = 3 p = 5 p 2 p = 3 [7; 11] p 2 p = 2 p = 3 [5; 19] 2 p = 3 p [5; 43] 2 p = 3 p = 5 p 2 p = 2 p = 3 [7; 19] p [5; 31] 2 p = 3 [5; 7] p 2 p = 11 p = 3 p = 5 p p [5; 17] [7; 11] 2 p = 2 p = 3 2 p = 3 2 p = 3 p p [5; 37] p s 1 2 3 4 5 5 6 6 7 7 7 8 8 9 9 9 10 10 10 11 11 11 12 12 12 13 13 13 14 2 p = 3 v 1 2 2 3 4 3 5 4 6 5 4 7 5 8 6 5 9 7 6 10 7 6 11 8 7 12 8 7 9 s 14 15 15 15 16 16 17 17 17 18 18 19 19 19 20 20 21 21 21 22 22 23 23 23 24 24 25 25 25 v 8 10 9 8 10 9 11 10 9 11 10 12 11 10 13 11 13 12 11 14 12 15 13 12 15 13 16 14 13 s 26 26 27 27 27 28 28 28 29 29 29 30 30 30 31 31 31 32 32 32 33 33 33 34 34 34 35 35 35 p [5; 7] 2 p = 11 v 16 14 17 15 14 18 16 15 18 16 15 19 17 16 19 17 16 20 18 17 21 18 17 21 19 18 22 19 18 s 36 36 36 37 37 38 38 38 39 39 40 40 40 41 41 41 42 42 42 43 43 44 44 45 45 46 47 48 49 2 p = 3 p = 5 p = 7 p = 3 p = 5 p = 7 p = 3 p = 5 p = 7 p = 5 p = 7 p = 5 p = 7 p = 5 p = 7 p = 5 p = 5 p = 5 p = 5 v 22 20 19 23 20 24 21 20 24 21 25 22 21 26 23 22 26 23 22 24 23 24 23 25 24 25 26 26 27 [5; 7] 2 [11; 17] 2
the electronic journal of combinatorics 14 (2007), #R75
11
(cid:20) In order to produce concrete examples of small dense sets of type D = D(H; A), with ‘ = 2s + 1, for which the strict inequality holds in (18), a computer search has been carried out. The sizes of the resulting dense sets are described in Table 2 below. Taking 859 dense sets of size smaller than 4ps+ into account that for q 2 have been obtained by computer in [7, 8], only values of q > 859 are considered in Table 2.
Table 2 - Sizes of some dense sets in P G(2; q) of type D(H; A) with ‘ = 2s + 1
q #A #D(H; A) 211 213 215 217 219 37 39 311 313 55 57 258 532 1162 2576 5210 245 764 2771 8788 376 1877 4 4 4 5 5 3 3 3 4 2 3 q #A #D(H; A) 59 75 77 79 115 117 135 137 175 177 195 9609 1030 7205 50947 3994 43947 6592 85712 14740 250599 20578 3 2 3 3 2 3 2 3 2 3 2
4 Applications to covering codes
A code with covering radius R is a code such that every word is at distance at most R from a codeword. For linear covering codes over Fq, it is relevant to investigate the so-called length function l(m; R)q, that is the minimum length of a linear code over Fq with covering radius R and codimension m, see the monography [3]. It is well known that the minimum size of a dense set in P G(2; q) coincides with l(3; 2)q, see e.g. [4]. From our Corollary 3.8, we then obtain the following result.
Theorem 4.1. Let q = p‘, with ‘ = 2s + 1. Then
1)2v : (v + 1)ps+1 + (cid:0) (ps 1)v(p(2s+1) (p 1)(v(cid:0)1) + 2 min v=1;:::;2s+1 (cid:26) (cid:27) l(3; 2)q (cid:20) (cid:0) (cid:0) It should also be noted that upper bounds on l(m; 2)q, m (cid:21)
5 odd, can be obtained from small dense sets. In fact, from a dense set of size k in P G(2; q) it can be constructed a linear code over Fq with covering radius 2, codimension 3 + 2m, and length about qmk, see [5, Theorem 1].
References
[1] U. Bartocci, k-insiemi densi in piani di Galois, Boll. Un. Mat. Ital. D 2 (1983), 71{77.
[2] E. Boros, T. Sz}onyi, and K. Tichler On de(cid:12)ning sets for projective planes, Discrete Math. 303 (2005), 17{31.
[3] G.D. Cohen, I. Honkala, S. Litsyn, and A.C. Lobstein, \Covering Codes". Amster- dam, The Netherlands: Elsevier, 1997.
the electronic journal of combinatorics 14 (2007), #R75
12
[4] A.A. Davydov, Constructions and Families of Covering Codes and Saturated Sets of Points in Projective Geometry, IEEE Trans. Inform. Theory 41 (1995), 2071{2080.
[5] A.A. Davydov, Constructions and Families of Nonbinary Linear Codes with Covering Radius 2, IEEE Trans. Inform. Theory 45 (1999), 1679{1686.
[6] A.A. Davydov and P.R.J. (cid:127)Osterg(cid:23)ard, On saturating sets in small projective geome- tries, European J. Combin. 21 (2000), 563{570.
[7] A.A. Davydov, S. Marcugini and F. Pambianco, On saturating sets in projective spaces, J. Combin. Theory Ser. A 103 (2003), 1{15.
[8] A.A. Davydov, S. Marcugini and F. Pambianco, Linear Codes With Covering Radius 2, 3 and Saturating Sets in Projective Geometry, IEEE Trans. Inform. Theory 50 (2004), 537{541.
[9] M. Giulietti and F. Torres, On dense sets related to plane algebraic curves, Ars Combinatoria 72 (2004), 33{40.
[10] B.D. Gray, N. Hamilton, C.M. O’Keefe, On the size of the smallest de(cid:12)ning set of P G(2; q), Bull. Inst. Combin. Appl. 21 (1997), 91{94.
[11] K. Gray, De(cid:12)ning sets of single-transposition-free designs, Utilitas Mathematica 38 (1990), 97{103.
[12] K. Gray, On the minimum number of blocks de(cid:12)ning a design, Bull. Austral. Math. Soc. 41 (1990), 97{112.
[13] G. Kiss, I. Kov(cid:19)acs, K. Kutnar, J. Ru(cid:11) and P. (cid:20)Sparl, A note on a geometric construc- tion of large Cayley graphs of given degree and diameter, submitted.
[14] S.J. Kov(cid:19)acs, Small saturated sets in (cid:12)nite projective planes Rend. Mat. 12 (1992), 157{164.
[15] R. Lidl and H. Niederreiter, Finite Fields, Enc. of Math. 20, Addison-Wesley, Read- ing, 1983.
[16] L. Lunelli and M. Sce, Considerazioni aritmetiche e risultati sperimentali sui K; n f gq archi, Ist. Lombardo Accad. Sci. Rend. A 98 (1964), 3{52.
[17] M. Miller and J. (cid:20)Sir(cid:19)a(cid:20)n, Moore graphs and beyond: A survey of the degree/diameter problem, Electron. J. Comb., Dynamical Surveys DS14.
[18] T. Sz}onyi, Complete arcs in (cid:12)nite projective geometries, Ph. D. Thesis, Univ. L. E(cid:127)otv(cid:127)os, Budapest, 1984.
the electronic journal of combinatorics 14 (2007), #R75
13
[19] E. Ughi, Saturated con(cid:12)gurations of points in projective Galois spaces, European J. Combin. 8 (1987), 325{334.
