ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 19 (2020) 231-247 https://doi.org/10.26493/1855-3974.2125.7b0
(Also available at http://amc-journal.eu)
On resolving sets in the point-line incidence graph of PG(n, q)
Daniele Bartoli * ©
Dipartimento di Matematica e Informatica, Università degli Studi di Perugia, Via Vanvitelli 1, 06123 Perugia, Italy
Gyorgy Kiss f ©
Department of Geometry andMTA-ELTE Geometric and Algebraic
Combinatorics Research Group Eotvos Lorand University, Budapest, 1117 Budapest, Pazmany Péter sétany 1/C, Hungary, and FAMNIT, University of Primorska, 6000 Koper, Glagoljaska 8, Slovenia
Stefano Marcugini * ©, Fernanda Pambianco * ©
Dipartimento di Matematica e Informatica, Universita degli Studi di Perugia, Via Vanvitelli 1, 06123 Perugia, Italy
Received 25 September 2019, accepted 13 July 2020, published online 15 November 2020
Lower and upper bounds on the size of resolving sets and semi-resolving sets for the point-line incidence graph of the finite projective space PG(n, q) are presented. It is proved that if n > 2 is fixed, then the metric dimension of the graph is asymptotically 2qn-1.
Keywords: Point-line incidence graph, resolving sets, finite projective spaces. Math. Subj. Class. (2020): 05B25, 05C12, 51E20
*	The research was supported by the Italian National Group for Algebraic and Geometric Structures and their Applications (GNSAGA - INDAM).
t Corresponding author. The research was supported by the Hungarian National Research Development and Innovation Office, OTKA grant no. K 124950, and by the Slovenian Research Agency (research project J1-9110).
*	The research was supported by the Italian National Group for Algebraic and Geometric Structures and their Applications (GNSAGA - INDAM), and by the University of Perugia (Project: "Curve, codici e configurazioni di punti", Base Research Fund 2018).
E-mail ¡addresses: daniele.bartoli@unipg.it (Daniele Bartoli), kissgy@cs.elte.hu (Gyorgy Kiss), stefano.marcugini@unipg.it (Stefano Marcugini), fernanda.pambianco@unipg.it (Fernanda Pambianco)
Abstract
©® This work is licensed under https://creativecommons.Org/licenses/by/4.0/
231
Ars Math. Contemp. 19 (2020) 189-208
1	Introduction
For a simple, connected, finite graph r = (V, E) and x, y e V let d(x, y) denote the length of a shortest path joining x and y.
Definition 1.1. Let r = (V, E) be a finite, connected, simple graph. Two vertices v\,v2 e
V are divided by S = {si, s2,...,sr} c V if there exists si e S so that d(vi, si) = d(v2, Si). A vertex v e V is resolved by S if the ordered sequence (d(v, s1), d(v, s2),..., d(v, sr)) is unique. S is a resolving set in r if it resolves all the elements of V. The metric dimension of r, denoted by ^(r), is the size of the smallest example of resolving set in it.
The study of metric dimension is an interesting problem in its own right and it is also motivated by the connection with the base size of the corresponding graph. The base size of a permutation group is the smallest number of points whose stabilizer is the identity. The base size of r, denoted by b(r), is the base size of its automorphism group Aut(r). The study of base size dates back more than 50 years, see [18]. A resolving set in r is obviously a base for Aut(r), so the metric dimension of a graph gives an upper bound on its base size. The difference ^(r) - b(r) is called the dimension jump of r. Distance-transitive graphs whose dimension jump is large with respect to the number of vertices are rare, and hence interesting objects. For more information about general results on metric dimension and base size we refer the reader to the survey paper of Bailey and Cameron [2].
Resolving sets for incidence graphs of some linear spaces were investigated by several authors [4, 9, 10, 12]. In these cases much better bounds than the general ones are known. Estimates on the size of blocking sets can be used to prove lower bounds on the metric dimension, and the knowledge of geometric properties is useful for constructions and upper bounds. It was shown by Heger and Takats [12] that the metric dimension of the point-line incidence graph of a projective plane of order q is 4q - 4 if q > 23. In a recent paper Heger et al. [11] extended this result for small values of q, too.
There are two natural generalizations of this planar result in higher dimensional spaces: one can consider either the point-hyperplane incidence graph, or the point-line incidence graph of PG(n, q). In the former case resolving sets are connected with lines in a higgledy-piggledy arrangement which were investigated by Fancsali and Sziklai [9]. Their results were recently improved by the authors of this paper [5]. The latter case is studied in the present paper. We assume that the reader is familiar with finite projective geometries. For a detailed description of these spaces we refer to [14, 16].
Let rn,q denote the point-line incidence graph of the finite projective space PG(n, q). The two sets of vertices of this bipartite graph correspond to points and lines of PG(n, q), respectively, and there is an edge between two vertices if and only if the corresponding point is incident with the corresponding line. In rn q the distance of two different lines is
2	if they intersect each other and 4 if they are skew. The distance of a point P and a line I is 1 if P is on and it is 3 if P is not on I. Finally, the distance of two different points is always 2. Hence, points cannot be resolved by other points. Considering these properties, the following definitions are natural.
Definition 1.2. A set S of points and lines of PG(n, q) is a semi-resolving set for points (lines) in rn,q if it resolves all the vertices of rn,q corresponding to points (lines).
Definition 1.3. Let S be a (semi-)resolving set in rn q. A point or a line is called inner (outer) if it is (not) in S. An outer point is called t-covered if it is incident with exactly t
D. Bartoli et al.: On resolving sets in the point-line incidence graph of PG(n, q)
233
lines of S. A point or a line is called uncovered if it has empty intersection with all elements of S.
The paper is organized as follows. First, in Section 2 we provide a pure combinatorial proof of a lower bound for resolving sets in rn,q. In the second part of the section interesting constructions are presented for n > 3 which yield examples asymptotically close to the lower bound. These resolving sets are related with regular spreads of lines in projec-tive spaces. We prove that the metric dimension of rn q is asymptotically 2qn-1 and its dimension jump is roughly where v denotes the number of its vertices. In Section 3 algebraic curves and blocking sets are applied. We consider a different type of line spread in PG(3, q) and we obtain examples of resolving sets in rn,q of smaller size when q = ph, p prime and h > 1. Finally, in Section 4 computer aided results for small values of q are given.
2 General bounds
In this section we present lower and upper bounds on ^(rn,q) for all q and n > 3. Particular attention is paid to the case n = 3, since general upper bounds in any dimension depend on the 3-dimensional upper bound, see Proposition 2.15 and Theorem 2.11.
Theorem 2.1. The size of any semi-resolving set for points in rn,q is at least
2_ qn+1 -q
q2 + q - 2
Proof. Let S be a semi-resolving set for points in rn,q which consists of k lines and m points.
Count in two different ways the number of incident point-line pairs (P, with I G S. On the one hand, this number is exactly k(q +1). On the other hand, there is at most one uncovered point, the number of 1-covered points is at most k and any other outer point must be covered by at least two lines of S. Hence
/qn+^ — 1
k(q + 1) > k + 2 ---1 - k - m
q-1
so
^ 2(qn+1 - q) qm k + m > --—-- +
(q - 1)(q + 2) q + 2' This gives the required inequality at once.	□
Corollary 2.2. The size of any resolving set in r3,q is at least 2 [q2 - q + 3 - -q+ j .
Corollary 2.3. The metric dimension of r3,q is at least 2(q2 - q + 3) for q > 10.
From now on we focus on upper bounds which will be given by constructions. For our examples we need the notion of spreads, in particular line spreads.
Definition 2.4. A k-spread Sk of PG(n, q) is a set of k-dimensional subspaces with the property that each point of PG(n, q) is incident with exactly one element of Sk.
234
Ars Math. Contemp. 19 (2020) 189-208
By definition, a k-spread of PG(n, q) consists of	elements. The following
theorem about the existence of spreads was proved independently by several authors, see [1,7, 17].
Theorem2.5. The projective space PG(n, q) hasa k-spreadifandonly if (k+1) | (n+1).
Hence there exists a line spread in any odd dimensional projective space. Two line spreads are said to be disjoint, if they do not share any common line. Our first construction for a semi-resolving set for points in rn q is based on disjoint line spreads. We use the following theorem of Etzion [8] about the existence of disjoint line spreads.
Theorem 2.6 (Etzion). If n > 3 is odd, then there exist at least two disjoint line spreads in PG(n, q).
Theorem 2.7. If n > 3 is odd, then there exists a semi-resolving set for points in rn,q of size
q" -1 _ i
rp (n,q) = 2q2 q 2 1 .	(2.1)
q2 — 1
Proof. Let L1 and L2 be two disjoint line spreads in PG(n, q), and lj G Lj be arbitrary lines. We claim that S = L1 U L2 \ {¿i, ¿2} is a semi-resolving set for points in rn,q.
Each point not in £j is contained in a unique pair of lines (r1, r2) G L1 x L2. Each point of ¿1 \ ¿2 is contained in a unique line of L1 U L2 \ {¿1, ¿2} and each point of ¿2 \ ¿1 is contained in a unique line of L1 U L2 \ {¿1, ¿2}. The (possible) unique point ¿1 n ¿2 is the only point of PG(n, q) not contained in any line of L1 U L2 \ {¿1, ¿2}. The size of S is
n+1_1
2 q 2 1--2, hence the statement follows.	□
q2 — 1	'
Proposition 2.8. Let E be a hyperplane and L be a line spread in PG(n, q), n > 3 odd. Then E contains exactly qq2——1 elements of L.
Proof. Any element of L is either fully contained in E, or intersects it in exactly 1 point. The elements of L partition the set of points of E. Hence, if x denotes the number of fully contained lines, then
q" — 1 ( +1) + (q"+1 — 1
-- = (q + 1)x + —----
q — 1	V q2 — 1
The claim follows from this equation at once.	□
Theorem 2.9. Let L1 be a line spread in PG(3, q). Then there exists another line spread L2 in PG(3, q) such that L1 and L2 do not share any common line.
Proof. Let f (X, Y) be an irreducible homogeneous quadratic polynomial and Hi denote the hyperbolic quadric in PG(3, q) with equation
f (Xo,Xi)+ if (X2, X3) = 0
for i = 1,2,..., q — 1. Apply a suitable linear transformation so that the images ¿1 and ¿2 of the lines : X0 = X1 =0 and 1'2: X2 = X3 =0 do not belong to L1. Let Hj denote the image of Hj, and let E and Fj denote the two reguli of lines on Hj. Then for each i at most one of Ej and Fj contains some elements of Li, because any line of Ej intersects
D. Bartoli et al.: On resolving sets in the point-line incidence graph of PG(n, q)
235
any line of F and no two elements of A intersect each other. Hence we can choose the notation so that E does not contain any element of A for all i. This implies that the spread
q-1
L = u Ei
i=i
does not share any common line with L1.	□
The next proposition gives a useful recursive construction method.
Proposition 2.10. Let S be a semi-resolving set for points in rd,q of size k. Suppose that m elements of S are contained in a hyperplane Sd-1 of PG(d, q), and Sd-1 also contains the (at most one) uncovered point. Then rd+1q has a semi-resolving set for points of size (q + 1)k — qm.
Moreover, if S is a resolving set in rd,q and Sd-1 also contains the (at most one)
d— 1 1
uncovered line, then rd+1,q admits a resolving set of size (q + 1)k — qm + q q-- .
Proof. Embed Sd-1 C PG(d, q) into PG(d+1,q), and consider in PG(d+1,q) thepencil of hyperplanes with carrier Sd-1. These hyperplanes, Sd, Sd,..., Sd+1, are isomorphic to PG(d, q). Take a copy of S in Sd and denote it by S1 for i = 1,2,..., q + 1. Finally, let
_ q+1 s = u s 4.
¿=1
We claim that S is a semi-resolving set for points in rn+1q. Inner points are resolved by definition. If two outer points, P1 and P2, are in the same Sd, then they are already divided by S4. If P1 is in S4 and P2 is in Sj with i = j, then, as none of P1 and P2 is uncovered and none of them is in Sd-1, there exist distinct lines £4 G S4 through P1 and £j G Sj through P2. Hence £4 does not contain P2, so d(P1, £4) = d(P1, £4). Since the size of S is m + (q + 1)(k — m), the first part of the statement is proved.
Now suppose that S is a resolving set in rd q. Then the elements of any point-line pair are obviously divided by S. Let £1 and £2 be two lines. If at least one of them is an element of S, then they are divided by definition. From now on we assume that none of the two lines is an element of S. We distinguish three main cases and some subcases.
1.	If both of them are entirely contained in the same Sd, then they are divided by S4.
2.	If there is no Sd that contains both £1 and £2, but each of the lines is entirely contained in some Sd, say £1 C Sd1 and £2 C Sd2, then none of the lines is in Sd-1. Let Pj denote the unique point £j n Sd-1 for j = 1,2.
•	If P1 = P2, then let P3 = P1 be a point on £1. Since S41 is a semi-resolving set for points in Sd1 and P3 is not an uncovered point, either P3 G S41 or there exists at least one line £ G S11 which contains P3 but does not contain P1. In the former case d(£1,P3) = 1 = 3 = d(£2,P3). In the latter case d(£1, £) = 2 = 4 = d(£2, £), so we are done.
•	If P1 = P2, then we may assume that P1 is not an uncovered point, because there is at most one uncovered point. Again, either P1 G S41 or there exists at least one line £ G S11 which contains P1 but does not contain P2. In the former case d(£1,P1) = 1 = 3 = d(£2,P1), while in the latter case d(£1,£) = 2 = 4 = d(£2, £), so £1 and £2 are divided by S41.
236
Ars Math. Contemp. 19 (2020) 189-208
3. If ¿4 is not contained in any Ed, then it cannot meet Ed_i, so there exists a unique point Pi = n Ed for all i = 1,2,..., q + 1.
•	If is not contained in any Ed, then it cannot meet Ed-1, so there exists a unique point P2 = ¿2 n Ed for all i = 1, 2,..., q +1. The two lines have at most one point of intersection, hence there exist at least q superscripts so that Pi = P2\ Since Si is a semi-resolving set for points in Ed, there exists at least one element s G Si so that d(P1, s) = d(P2, s). Hence
d(^, s) = d(Pi, s) + 1 = d(P2\ s) + 1 = d(^2, s),
so the lines are divided by Si.
•	If ¿2 is contained in a unique Ed, then it is not contained in Ed_ 1, so there exists a unique point P2 = ¿2 n Ed-1. Let j = i and consider Ej which contains both Pj and P2. Since Sj is a semi-resolving set for points in Ej there exists at least one element s G Sj so that d(Pj, s) = d(P2, s). Hence
d(^, s) = d(Pj, s) + 1 = d(P2, s) + 1 = d(^2, s),
the claim is proved.
•	Finally, suppose that ¿2 is contained in Ed_ 1. Then and ¿2 are not necessarily
divided by S. Suppose that S consists of lines only. Then ¿2 and Pi are divided
by Si, but it could happen that a line of Si intersects ¿2 if and only if it contains
Pi. If it holds for all i, then and ¿2 have the same distance sequence with
- - d-l_ 1
respect to S. We can handle this problem by extending S with all the q _
points of a hyperplane in Ed-1. Then ¿2 contains at least one of these points
and does not contain any of them. Hence the two lines are divided.
The size of the constructed resolving set is (q + 1)k - qm + q _ , the statement is proved.	□
Theorem 2.11. If n > 4 is even, then there exists a semi-resolving set for points in rnq of size
rp(n, q) = 2qn-1 + 2qn_2 + 2(qn_4 + qn_6 + • • • + q2).	(2.2)
Proof. We apply Proposition 2.10 for d = n - 1. Let S be the semi-resolving set for points in r„_1jq which was constructed in Theorem 2.7. Its size is
k=2 ^.
q2 - 1
By Proposition 2.8, we can choose the hyperplane En_2 so that it contains
' q"_2 - 1 \ qn_2 - q2 m = 2 —^--1 =2-
q2 - 1	q2 - 1
elements of S. Thus we get from Proposition 2.10 that there exists a semi-resolving set for points in rn q of size
qn — q2 qn_2 — q2
rp(n, q) = 2(q + 2—r - 2q—2—r~
q2 - 1	q2 - 1
= 2qn_1 + 2qn_2 + 2(qn_4 + qn_6 + • • • + q2).	□
D. Bartoli et al.: On resolving sets in the point-line incidence graph of PG(n, q)
237
Now we turn to semi-resolving sets for lines. Let us start with a simple, but very useful observation.
Lemma 2.12. Let E be a hyperplane in PG(n, q), S be a semi-resolving set for points in E and t\ and t2 be two distinct lines in PG(n, q). Suppose that none of the lines is contained in E and the points P® = E n t\ and P2 = E n ¿2 are distinct. Then the lines t\ and t2 are divided by S in rn,q.
Proof. Since S is a semi-resolving set for points in E, there exists at least one element s € S so that d(Pi, s) = d(P2\ s). Hence
d(^, s) = d(Pi, s) + 1 = d(Pl, s) + 1 = d(l2, s), the statement follows.	□
Theorem 2.13. For all n > 3 and q > 2n — 1 there exists a semi-resolving set for lines in rn,q of size rL(n, q) = 2nrp (n — 1, q), where rp follows (2.1) or (2.2) depending on the parity of n — 1.
Proof. Let H = {Ei, E2,..., E2n} be a subset of 2n hyperplanes of the (q + 1)-element set formed by the dual hyperplanes of points on a normal rational curve. Then these hyperplanes are in general position, no n +1 of them have a point in common. Let S® be a semi-resolving set for points in E®. We claim that S = |J2=i S® is a semi-resolving set for lines in rn,q.
Let li and l2 be two distinct lines in PG(n, q). We may assume that ¿j is contained in the intersection of mj elements of H for j = 1,2, and mi > m2. The elements of H are in general position, so n — 1 > mj, hence 2n — mi — m2 > 2. We may assume without loss of generality that j intersects E® in a single point, denoted by P®, for i = 1,2,..., 2n — mi — m2 and j = 1,2. It could happen, that P®1 = P®2 = • • • = P®k for some indices, but k < n — m2, otherwise the point would be a common point of at least mi + (n — m2 + 1) > n elements of H. So we may assume that Pi = Px2. As contains at most one point of we may also assume that P/ is not on Then, by Lemma 2.12, ¿4 and are divided by Si.
By Theorems 2.7 and 2.11, the size of S is at most 2nrp (n — 1, q) for n > 3, thus the theorem is proved.	□
The union of a semi-resolving set for points and a semi-resolving set for lines is a resolving set. Thus Theorems 2.7, 2.11 and 2.13 give our first general upper bound.
Corollary 2.14. For all n > 3 and q > 2n — 1 there exists a resolving set in rn,q of size
r(n, q) = 2qn- i + (4n + 1 + ( — 1)n)qn-2 + gn(q),
where gn is a polynomial of degree n — 3 whose coefficients depend only on n.
In this bound the coefficient of the second highest degree term depends on the dimension. In the next part, by a more sophisticated construction, we prove an upper bound in which the coefficient of the second highest degree term is a constant.
238
Ars Math. Contemp. 19 (2020) 189-208
Proposition 2.15. Let q = ph, p prime. Suppose that there exists a resolving set S3 in r3,q of size 2q2 + aq + g3(p), where a G R, is a polynomial of degree s < h — 1, and S3 contains the 2q2 + 2 elements of two disjoint line spreads. Then there exists a resolving set
S4m+3 in r4m+3,q ofsize
2qn—1 + aqn-2 + g4m+3 (p) where g4m+3 is a polynomial of degree at most (n — 3)h + s.
Proof. As (4m + 3) + 1 is divisible by 3+1, there existsa 3-spreadin PG(4m + 3, q). This
4(m + 1)_i	10
3-spread contains t = q q4-1— elements, say £3,, £2,..., £3, each of them is isomorphic to PG(3, q). By the assumption of the theorem, in each £3 there exists a resolving set S3 of size 2q2 + aq + g3 (p). We claim that
t
s = U S3
¿=1
is a resolving set in T4m+3,q. The elements of any pair of points and any point-line pair are obviously divided by S. Let ¿4 and ¿2 be two lines. If at least one of them is contained in a £3, then they are divided by S3. If none of them is contained in any £3, then we may assume without loss of generality that ¿4 n £3 is a point P which is not on ¿2. Let s1 and s2 be the two elements of the disjoint line spreads in S33 which are incident with P. Then <(¿4, s3) = <¿(¿4, s2) = 2. As ¿2 is not contained in S3, it cannot intersect both s3 and s2. Hence at least one of the distances <(¿2, s3) and <(¿2, s2) is 4. Thus ¿3 and ¿2 are divided by S33 c S.
The size of S is
qn+1 _ 1
(2q2 + aq + g3(p)) qq4 — 1 = 2qn—1 + aqn-2 + g4m+3(p),
where the degree of g4m+3 is (n — 3)h + deg g4m+3 = (n — 3)h + s < (n — 2)h — 1, so we are done.	□
Theorem 2.16. Let q = ph, p prime. Suppose that there exists a resolving set in r3,q of size 2q2 + aq + g3 (p) where g3 is a polynomial of degree s < h — 1. Then for n > 3 there exists a resolving set in rn,q ofsize
r(n,q) =
'2qn—1 + (a + 2)qn—2 + g„,o(p),	if n = 0	(mod 4),
2qn-1 + (a + 2)qn—2 + g„,i(p),	if n = 1	(mod 4),
2qn—1 + (a + 4)qn-2 + gn,2(p),	if n = 2	(mod 4),
^2qn—1 + aqn-2 + g„,3(p),	ifn = 3	(mod 4),
where g„,j (i = 0,1, 2, 3) is a polynomial of degree (n — 3) h + s whose coefficients depend only on n.
Proof. We prove it by induction on the dimension modulo 4. For n = 3 (mod 4) the statement follows from Proposition 2.15.
If n = 0 (mod 4), then we apply Proposition 2.10 for d = n — 1 with k = rp (n — 1, q) and m = 0. Therefore by the induction hypothesis
qn-2 — 1
rp(n q) < (q + 1)rp(n — 1 q) +--
q — 1
= 2qn—1 + (a + 2)qn—2 + (q + 1)gn-1,3(p) + (a + 1)qn-3 + qn-4 + • • • + 1.
D. Bartoli et al.: On resolving sets in the point-line incidence graph of PG(n, q)
239
Thus gn,o(p) = (q + 1)g„-i,3(p) + (a + 1)qn-3 + qn-4 +----+ 1, hence its degree is
(n - 3)h + s < (n - 2)h - 1.
If n = 1 (mod 4), then n — 2 = 3 (mod 4), hence we can apply Proposition 2.10 for d = n - 1 so that £d-1 contains a resolving set constructed in Proposition 2.15. Then
k = 2qn-2 + (a + 2)qn-3 + gn-i,o(p) and m = 2qn-3 + aqn-4 + gn-2,s(p). Hence
q"-2 — 1
rp(n, q) = (q + 1)k - qm + q-— = 2qn-1 + (a + 2)qn-2 + g„,i(p),
q - 1
where
gn,l(p) = (q + 1)gn-1,0 (p) - qgn-2,3 (p) + 3q"-3 + q"-4 + • • • + 1,
so its degree is (n - 3)h + s < (n - 2)h - 1.
Finally, if n = 2 (mod 4), then n - 3 = 3 (mod 4). Hence we cannot do better than apply Proposition 2.10 for d = n - 1 so that £d-1 contains entirely only elements of a (d - 2)-dimensional resolving set constructed in Proposition 2.15. Now k = 2qn-2 + (a + 2)qn-3 + gn-1,1 (p) and m = 2qn-4 + aqn-5 + gn-3,3(p). This gives
qn-2 _ 1
rp(n, q) = (q + 1)k - qm + q-— = 2qn-1 + (a + 4)qn-2 + gn,2(p),
q - 1
where
gn,2(p) = (q + 1)gn-1,1 (p) - qgn-3,3(p) + (a + 1)q"-3 + q"-4 + • • • + 1,
thus its degree is (n - 3)h + s < (n - 2)h - 1 again. The theorem is proved.	□
Let us remark that the polynomials gn,j can be determined exactly. We omit the long, but straightforward calculations, because their coefficients do not play any role in the rest of the paper.
In the next part of the section semi-resolving sets for lines in rn,q are investigated. In their constructions double blocking sets and their duals play an important role. For the relevant definitions and estimates on their sizes we refer to the paper of Ball and Blokhuis [3].
Theorem 2.17. For all q > 3 there exists a semi-resolving set for lines in r3,q of size
rL(3, q) = min{12q - 22, 4r2(q) - 10}, where t2 (q) denotes the size of the smallest minimal double blocking set in PG(2, q).
Proof. First, we construct two sets of lines in PG(2, q) which are semi-resolving sets for points.
1. Let E1, E2, and E3 be the vertices of a triangle, ^ denote the line Ej Ek and P be the pencil of lines with carrier Ej. Let
S = P1 UP2 UP3 \{^2,4,^},
where I G P1, = I = ¿3. Then S is a semi-resolving set for points in r2,q, because U = I n is a unique uncovered point, every point in the set U U 4 \ {E1, E2, E3, U} is 1-covered and all other points are at least 2-covered, hence resolved. The size of S is 3q - 4.
240
Ars Math. Contemp. 19 (2020) 189-208
2. Let D be a dual double blocking set in PG(2, q). Then, by definition, each point is incident with at least two lines of D. Thus if we delete an arbitrary line I from D, then the set of lines D \ {¿} is still a semi-resolving set for points and, by the Principle of Duality, its size is at most T2(q) - 1.
Hence, for all q > 3 there is a set of lines in PG(2, q) of size min{3q — 4, r2(q) — 1} which is a semi-resolving set for points. Let Hi, H2, Hf, and H4 be the faces of a tetrahedron K in PG(3, q). Let Tj be a semi-resolving set for points in Hi which consists of lines only. We can choose Tj so that each edge of K belongs to both corresponding semi-resolving sets, because the full collineation group of PG(2, q) acts transitively on triangles. We claim that S = U4=1Tj is a semi-resolving set for lines in rf,q.
The edges of K belong to S, thus they are resolved by definition. Let and ¿2 be lines such that none of them is an edge of K. Then each of them is contained in at most one face of K, so we may assume without loss of generality that intersects Hi in a single point, denoted by Pi, for i = 1,2, 3. We distinguish two main cases.
1.	If Pi = P2 = Pf, then this point is a vertex K of K.
•	If ¿2 also contains K, then H4 n = H4 n ¿2, hence, by Lemma 2.12, the two lines are divided by T4.
•	If ¿2 does not contain K, then we may assume that H2 n ¿2 is a single point P22. Since P22 = K, by Lemma 2.12, the two lines are divided by T2.
2.	If none of and ¿2 contains any vertex, then we may assume that P/ = P2.
•	If ¿2 is not contained in neither H1 nor H2, then it intersects Hi in a single point, denoted by P2, for i = 1,2. Since n ¿2 contains at most one point, we may assume that P1 = P21. Then, by Lemma 2.12, the two lines are divided by T1.
•	Finally, if ¿2 is contained in one of H1 and H2, then we may assume that
¿2 C H1 and ¿2 n H2 in a single point P22. Then P22 is in H1, so P22 = Pf, because otherwise C H1. Hence, by Lemma 2.12, the two lines are divided by T2.
Since S has the required size, we are done.	□
Remark 2.18. Let us remark that if the double blocking set D in the proof of Theorem 2.17 is the disjoint union of two dual blocking sets, then not only one, but two lines can be deleted without violating the semi-resolving set property. We will consider this case in Section 3, Theorem 3.1.
Unfortunately, the exact value of t2 (q) is not known in general. It is known that t2 (q) = 2q + 2^q + 2 for q is a square and q > 16 [3, Theorem 3.1], and for some small values of q. In the latter case for the known values T2(q) > 3q — 3 always holds. Combining the semi-resolving set for points constructed in Corollary 2.7 and the semi-resolving set for lines of Theorem 2.17, we get the following upper bound on ^(rf,q).
Theorem 2.19. The metric dimension of rf ,q satisfies the inequality
M^.q) < 2q2 + 12q — 24
for all q > 3.
D. Bartoli et al.: On resolving sets in the point-line incidence graph of PG(n, q)
241
Proof. For q > 3 let SL be a semi-resolving set for lines of size 12q - 22 constructed in Theorem 2.17. Let L1 be a regular line spread of PG(3, q) which contains two skew (non-intersecting) elements of SL. Such spread exists, because the collineation group of PG(3, q) acts transitively on the pairs of skew lines. Create a semi-resolving set for points Sp which contains L1 as we did it in Corollary 2.7. Then S = SL U Sp is a resolving set in r3,q and its size is 2q2 + 12q - 24. This proves the inequality.	□
By combining Theorem 2.16, with s = 0, and Theorem 2.19, we get the following bounds.
Corollary 2.20. Let n > 3 and q > 3. Then the metric dimension of rn,q satisfies the inequality
{2qn-1 + 14qn-2 + hn,2(q), if n = 0 or n = 1 (mod 4), 2qn-1 + 16qn-2 + hn,3(q), if n = 2 (mod 4), 2qn-1 + 12qn-2 + hnj1(q), if n = 3 (mod 4),
where hnji (i = 1,2, 3) is a polynomial of degree at most n — 3 whose coefficients depend only on n.
The metric dimension of r2,q for q > 23 was determined by Heger and Takats [12 ]. For higher dimensions we do not know the exact value, but Theorems 2.1, 2.19, and Corollary 2.20 imply the following result.
Corollary 2.21. For all n > 2 and q > 3
|M(r„,q) — 2qn—11 = O(qn—2).
This means that M(rn,q) is asymptotically 2qn-1. The number of vertices in rn,q is v = q q--1 +	1), so its metric dimension is roughly The automorphism
group of PG(n, q) is PrL(n + 1, q) and it is well-known that its base size is n + 1 if q is a prime, and it is n + 2 if q = with h > 1. Hence the dimension jump of rn,q is roughly 2^v.
3 Bounds for q = ph, h > 2
In this section we consider the case q = ph, h > 1. In the case h even, we will present a better bound on the size of a semi-resolving set for points in r3 q using small dual double blocking sets in PG(2, q). When h > 2, then we will show that a particular type of spread of lines in PG(3, q) can be used to resolve the lines. In fact, for a regular spread, there exist many pairs of lines of the spaces intersecting the same set of elements of the spread. We now investigate a different type of spread, called aregular, and we determine all the lines of the space intersecting the same set of elements of the spread; see Theorem 3.6. The main goal is to construct a set of lines of PG(3, q) which resolves all the lines of the spaces; see Theorem 3.7.
Theorem 3.1. If q is a square, then the metric dimension of r3,q satisfies the inequality
M(r3,q) < 2q2 + 8q + vq — 8.
242
Ars Math. Contemp. 19 (2020) 189-208
Proof. The union of the sets of lines of two disjoint Baer subplanes is a dual double blocking set in PG(2, q) and its size is 2q + + 2. This set is the disjoint union of two dual blocking sets. Hence, by a result of Heger and Takats [12, Proposition 22], we can delete two of its lines so that the remaining set is still a semi-resolving set for points in PG(2, q); see also Remark 2.18.
Thus we can construct a semi-resolving set for lines SL of size 8q + - 6 by the method applied in the proof of Theorem 2.17. Finally, we can extend it to a resolving set of size 2q2 + 8q + - 8 in the same way as we did in the proof of Theorem 2.19. □
By combining Theorem 2.16, with s = 0, and Theorem 2.19, we get the following bounds.
Corollary 3.2. If q is a square and n > 3, then the metric dimension of rn,q satisfies the inequality
{2qn-1 + 10qn-2 + hn,2(q), if n = 0 or 1 (mod 4), 2qn—1 + 12qn—2 + h„,3(q), if n = 2 (mod 4), 2qn-1 + 8qn-2 + hn,1(q), if n = 3 (mod 4),
where hn,i (i = 1,2, 3) is a polynomial of degree at most n — 3 whose coefficients depend only on n.
Theorem 3.3 ([ , Theorem 17.3.3]). Let q = ph, h > 1, and choose b, c G F* such that the polynomial tp+1 — tb + c has no roots in Fq. Let
Ab,c = {ta,p : a, £ G Fq} U {Z = T = 0},
where ta,p is the line through the points (a : £ : 1 : 0) and (c£p : ap + b£p : 0 : 1). Then Ab,c is a spread, called the aregular spread.
In what follows, we will associate to each line r of the space an algebraic curve Cr : Fr (X, Y, T) = 0 such that taJj intersects r if and only if Fr (a, £, 1) = 0. We distinguish four types of lines.
1. Lines rx,y/,m through the points (x : y : 0 : 1) and (^ : m : 1 : 0). Note that if
x = cmp and y = £p + bmp then rx,y,^,m coincides with t^,m G Ab,c. From now on we consider (x, y) = (cmp, £p + bmp). A line tay intersects r = rx y im if and only if for some A G Fq the points
(x + A^ : y + Am : A : 1), (a : £ : 1 : 0), (c£p : ap + b£p : 0 : 1)
are collinear, that is
x + A^ — c£p = Aa, y + Am — (ap + b£p) = A£.
This implies
A(^ — a) = c£p — x, A(m — £) = ap + b£p — y,
and therefore
(c£p — x)(m — £) = (ap + b£p — y)(^ — a). In this case, Fr (X, Y, T) = (cYp — xTp)(mT — Y) — (Xp + bYp — yTp)(^T — X).
D. Bartoli et al.: On resolving sets in the point-line incidence graph of PG(n, q)
243
2.	Lines s = sx,y,z,£ through the points (x : y : z : 1) and : 1 : 0 : 0). A line intersects sx,y,z,£ if and only if for some A G Fq the points
(x + A^ : y + A : z : 1), (a : £ : 1 : 0), (c,0p : ap + b,0p : 0 : 1)
are collinear, that is
x + A^ - = za, y + A - (ap + = z£.
This implies
A^ = -x + + za, A = -y + + ap +
and therefore
-x + + za = ¿(-y + + ap + So, Fs(X, Y, T) = -¿Xp + (c - ¿b)Yp + zXTp-1 - ¿zYTp-1 + (¿y - x)Tp.
3.	Lines u = ux,y,z through the points (x : y : z : 1) and (1 : 0 : 0 : 0). In this case,
Fu(X, Y, T) = Xp + bYp + zYTp-1 - yTp.
4.	Lines v = vx,y,z contained in the planes T = 0 and xX + yY + zZ = 0. Then,
Fv (X,Y,T) = xX + yY + zT.
Such a curve is absolutely irreducible if z = 0, otherwise it collapses into a single line.
Proposition 3.4. Consider the curves Cr, Cs, Cu, and Cv. Then
1.	Cr is absolutely irreducible;
2.	Cs is either absolutely irreducible or a line repeated p times;
3.	Cu is either absolutely irreducible or a line repeated p times.
Proof.
1. Now we prove that Cr is absolutely irreducible. Let y(X, Y, T) = (X + x0T, Y + yoT, T) with xp = y - bx/c, yP = x/c. Then
Fr (^(X,Y,T))
= (c(Y + yoT)p - xTP)(mT - Y - yoT)
-	((X + xoT)p + b(Y + yoT)p - yTp)^T - X - xoT) = (cYp + cypTp - xTp)(mT - Y - yoT)
-	(Xp + xpTp + bYp + ypTp - yTp)^T - X - xoT) = (cYp + xTp - xTP)(mT - Y - yoT)
-	(Xp + yTP - bx/cTp + bYP + bx/cTP - yTP)^T - X - xoT) = cYp(mT - Y - yoT) - (Xp + bYp)^T - X - xoT)
= Gr (X, Y, T).
Finally
Gr(X, 1, Y) = c(mY - 1 - yoY) - (Xp + b)^Y - X - xoY),
244
Ars Math. Contemp. 19 (2020) 189-208
that is the curve Cr is Fq-isomorphic to
c - X (Xp + b)
C': Y =
cm - cyo + (xo - i)(Xp + b)'
which is an irreducible rational curve with q +1 Fq -rational points (note that (x, y) =
(cmp, ip+bmp) yields m = y0 or i = x0). This means that the curve Cr is absolutely irreducible.
2.	First, note that the homogeneous term —IXp + (c - ib)Yp cannot vanish otherwise c = 0, a contradiction.
•	If (i, z) = (0,0), Cs is a line of type b0Y + c0T = 0 repeated p times.
•	If i = 0 and z = 0, then Fs (X, Y, T) reads cYp + zXTp-1 - xTp and Cs is absolutely irreducible.
•	If i = 0 and z = 0 then Cs is a (repeated) line a0X + b0Y + c0T = 0, where
ap0 = -i, bp = (c - ib), cp = (iy - x).
•	If i = 0 and z = 0 then consider y(X, Y, T) = (X + ^(c - ¿b)/^ Y, Y, T) and so
Gs(X,Y,T) = Fs(^(X,Y,T)) =
- ¿Xp + zXTp-1 + z( ^(c - ib)/i - i)YTp-1 + (iy - x)Tp.
By our assumption of b, c, there is no i G Fq such that ^(c - ib)/i - i = 0. The curve Gs (X, Y, T) = 0 is rational and irreducible and it is Fq-isomorphic to Cs.
3.	Clear.	□
Proposition 3.5. Let q = ph, h > 2. Two fines of the same type (r,s,u,v) do not intersect the same set of lines of the aregular spread Ab,c.
Proof. The assumption h > 2 implies q +1 > (p + 1)2. The curves Cr, Cs, Cu, Cv have degree at most p and they have q +1 Fq -rational points (corresponding to the lines of the spread intersecting them). By Proposition 3.4, such curves are either absolutely irreducible or they consist of a repeated line. Thus, if two curves attached to the lines w1 and w2 of the same type share q +1 Fq-rational points, the corresponding polynomials must be proportional. By direct computations, this yields w1 = w2.	□
Theorem 3.6. Let q = ph, h > 2. If two lines in PG(3, q) intersect the same set of lines of the spread Ab,c then one of them lies on the plane Z = 0 and the other on the plane T = 0.
Proof. The reduced (absolutely irreducible) curves associated with the different types of lines (r, s, u, v) have degree p +1, degree p or 1, degree p or 1, and degree 1, respectively. They can share q +1 Fq-rational points only in the following cases:
•	both Cs and Cu have degree p;
•	both Cs and Cu have degree 1;
•	both Cs and Cv have degree 1;
D. Bartoli et al.: On resolving sets in the point-line incidence graph of PG(n, q)
245
• both Cu and Cv have degree 1.
The first case is not possible. The second case would imply c = 0, a contradiction. Recall that the lines v = vxyz are contained in the plane T = 0 of PG(3, q). The claim follows observing that if Cs or Cu have degree 1, then s = sx,y,o/ or u = ux,yi0. So, both s and u are contained in the plane Z = 0.	□
Theorem 3.7. Let q = ph, h > 2. Then there exists a set of q2 +3 lines resolving all the lines of PG(3, q).
Proof. Consider the aregular spread Abc with b,c e F* and such that the polynomial tp+1 — tb + c has no roots in Fq. We already know by Theorem 3.6 that lines of PG(3, q) intersecting the same set of elements of Ab,c are contained in the planes Z = 0 or T = 0. Note that two lines in a fixed plane cannot intersect the same elements of Abc. Consider two distinct extra lines w1 and w2 contained in Z = 0 intersecting the line Z = T = 0 at
two distinct points. It is readily seen that Ab,c U{wi, w2} resolves all the lines of PG(3, q).
' □
Corollary 3.8. If q = ph, h > 2, then there exists a resolving set in r3iq of size 2q2 + 2.
Proof. Consider the set of q2 + 3 lines from Theorem 3.7 and use the argument of Theorem 2.9. One of the two extra lines could be an element of the other spread. Finally, delete one line from the modified regular spread.	□
Finally, the following bounds are obtained combining again Theorem 2.16, with s = 0, and Theorem 2.19.
Corollary 3.9. If q = ph, h > 2, then the metric dimension of rn,q satisfies the inequality
{2qn-1 + 2qn-2 + hn,2(q), if n = 0 or 1 (mod 4), 2qn—1 + 4qn—2 + hn,s(q), if n = 2 (mod 4), 2qn—1 + hn,i(q),	ifn = 3 (mod 4),
where hnji (i = 1,2, 3) is a polynomial of degree at most n — 3 whose coefficients depend only on n.
4 Resolving sets for small q
We performed a computer search to obtain sets of lines that are semi-resolving sets for lines in PG(3, q) for small q. We used Magma, a computer algebra system for symbolic computation developed at the University of Sydney; see [6]. We started classifying all set of lines of a certain size k. Then we extended the non-equivalent sets of size k using a backtracking algorithm.
In PG(3,2) there are 35 lines, so a semi-resolving set for lines must contain at least six elements. We found that there are 165 non-equivalent sets of lines of size six. Forty-eight of them are semi-resolving sets for lines in PG(3,2). An example is the following set of six lines:
{((1	0	0	0), (0	1	0	0)), ((0	1	0	0), (0	0	0	1)),
((0	0	1	0), (0	0	0	1)), ((0	0	0	1), (1	1	0	0)),
((0	1	0	0), (1	1	1	1)), ((1	1	0	0), (0	0	1	1))}
247
Ars Math. Contemp. 19 (2020) 189-208
In PG(3,3) there are 130 lines, so a semi-resolving set for lines must contain at least eight elements. We found that there are 10681 non-equivalent sets of lines of size seven. An exhaustive search by backtracking has proved that no set of lines of size eight or nine is a semi-resolving set for lines in PG(3,3). There exist semi-resolving sets for lines of size ten. An example is the following set of ten lines:
{((1	0	0	0), (0	1	0	0)), ((1	0	0	0), (0	0	0	1)),
((0	1	0	0), (0	0	1	0)), ((0	1	0	0), (1	0	0	1)),
((1	0	1	2), (0	1	1	0)), ((1	0	0	2), (0	0	1	1)),
((1	0	0	0), (0	1	1	2)), ((1	0	0	0), (0	1	1	0)),
((0	1	1	1), (1	2	0	0)), ((1	1	1	0), (0	1	2	0))}
ORCID iDs
Daniele Bartoli S> https://orcid.org/0000-0002-5767-1679 Gyorgy Kiss © https://orcid.org/0000-0003-3312-9575 Stefano Marcugini © https://orcid.org/0000-0002-7961-0260 Fernanda Pambianco ¡> https://orcid.org/0000-0001-5476-5365
References
[1]	J. Andre, Uber nicht-Desarguessche Ebenen mit transitiver Translationsgruppe, Math. Z. 60 (1954), 156-186, doi:10.1007/bf01187370.
[2]	R. F. Bailey and P. J. Cameron, Base size, metric dimension and other invariants of groups and graphs, Bull. Lond. Math. Soc. 43 (2011), 209-242, doi:10.1112/blms/bdq096.
[3]	S. Ball and A. Blokhuis, On the size of a double blocking set in PG(2, q), Finite Fields Appl. 2 (1996), 125-137, doi:10.1006/ffta.1996.9999.
[4]	D. Bartoli, T. Heger, Gy. Kiss and M. Takats, On the metric dimension of affine planes, biaffine planes and generalized quadrangles, Australas. J. Combin. 72 (2018), 226-248, https:// ajc.maths.uq.edu.au/pdf/72/ajc_v7 2_p22 6.pdf.
[5]	D. Bartoli, Gy. Kiss, S. Marcugini and F. Pambianco, Resolving sets for higher dimensional projective spaces, Finite Fields Appl. 67 (2020), 101723 (14 pages), doi:10.1016/j.ffa.2020. 101723.
[6]	W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I: The user language, J. Symbolic Comput. 24 (1997), 235-265, doi:10.1006/jsco.1996.0125.
[7]	R. H. Bruck and R. C. Bose, The construction of translation planes from projective spaces, J. Algebra 1 (1964), 85-102, doi:10.1016/0021-8693(64)90010-9.
[8]	T. Etzion, Partial k-parallelisms in finite projective spaces, J. Combin. Des. 23 (2015), 101-114, doi:10.1002/jcd.21392.
[9]	S. L. Fancsali and P. Sziklai, Lines in higgledy-piggledy arrangement, Electron. J. Combin. 21
(2014),	#P2.56 (15 pages), doi:10.37236/4149.
[10]	T. Heger, B. Patkos and M. Takats, Search problems in vector spaces, Des. Codes Cryptogr. 76
(2015),	207-216, doi:10.1007/s10623-014-9941-9.
[11]	T. Heger, P. Szilard and M. Takats, The metric dimension of the incidence graphs of projective planes of small order, Australas. J. Combin. 78 (2020), 352-375, https://ajc.maths. uq.edu.au/pdf/78/ajc_v78_p352.pdf.
D. Bartoli et al.: On resolving sets in the point-line incidence graph of PG(n, q)
73
[12]	T. Heger and M. Takats, Resolving sets and semi-resolving sets in finite projective planes, Electron. J. Combin. 19 (2012), #P30 (21 pages), doi:10.37236/2582.
[13]	J. W. P. Hirschfeld, Finite Projective Spaces of Three Dimensions, Clarendon Press, Oxford, 1985.
[14]	J. W. P. Hirschfeld, Projective Geometries over Finite Fields, Clarendon Press, Oxford, 2nd edition, 1998.
[15]	J. W. P. Hirschfeld, G. Korchmaros and F. Torres, Algebraic Curves over a Finite Field, Princeton Series in Applied Mathematics, Princeton University Press, Princeton, 2008.
[16]	Gy. Kiss and T. Szonyi, Finite Geometries, CRC Press, Boca Raton, Florida, 2019, doi:10. 1201/9781315120072.
[17]	B. Segre, Teoria di Galois, fibrazioni proiettive e geometrie non desarguesiane, Ann. Mat. Pura Appl. 64 (1964), 1-76, doi:10.1007/bf02410047.
[18]	C. C. Sims, Determining the conjugacy classes of a permutation group, in: G. Birkhoff and M. Hall, Jr. (eds.), Computers in Algebra and Number Theory, American Mathematical Society, Providence, Rhode Island, volume IV of SIAM-AMS Proceedings, 1971 pp. 191-195, proceedings of a Symposium in Applied Mathematics of the American Mathematical Society and the Society for Industrial and Applied Mathematics, held in New York City, March 25 -26, 1970.