Part II: Maps on Points and/or Lines

Contributions to Algebra and Geometry Volume 43 (2002), No. 2, 303-324.

Distance-preserving Maps in Generalized Polygons

Part II: Maps on Points and/or Lines

Eline Govaert^∗ Hendrik Van Maldeghem

University of Ghent, Pure Mathematics and Computer Algebra Galglaan 2, 9000 Gent, Belgium

e-mail: egovaert@@cage.rug.ac.be; hvm@@cage.rug.ac.be

Abstract. In this paper, we characterize isomorphisms of generalized polygons (in particular automorphisms) by maps on points and/or lines which preserve a certain fixed distance. In Part I, we considered maps on flags. Exceptions give rise to interesting properties, which on their turn have some nice applications.

MSC 2000: 51E12

Keywords: generalized polygons, distance-preserving maps

1. Introduction

For an extensive introduction to the problem, we refer to Part I of this paper. Let us briefly describe the situation we are dealing with.

For the purpose of this paper, a generalized n-gon, n ≥3, is a thick geometry such that every two elements are contained in some ordinary n-gon, and no ordinary k-gons exist for k < n.

Given two generalized n-gons, and a map from either the point set or the point set and the line set of the first polygon to the point set, or the point set and the line set, respectively, of the second polygon, preserving the set of pairs of elements at a certain fixed distancei≤n, we investigate when this map can be extended to an isomorphism (“preserving” means that elements of the first polygon are at distanceiif and only if their images in the second polygon

∗The first author is a research assistant of the FWO, theFund for Scientific Research – Flanders (Belgium)

0138-4821/93 $ 2.50 c 2002 Heldermann Verlag

are at distancei). In the first part of this paper, we dealt with the same problem considering maps on the set of flags. More precisely, we showed (denoting theorderof a polygon by (s, t) if there are s+ 1 points on every line, and t+ 1 lines through every point):

Theorem 1. Let ∆ and ∆⁰ be two generalized m-gons, m≥2, let r be an integer satisfying 1≤ r ≤ m, and let α be a surjective map from the set of flags of ∆ onto the set of flags of

∆⁰. Furthermore, suppose that the orders of ∆ and ∆⁰ either both contain 2, or both do not contain 2. If for every two flags f, g of ∆, we have δ(f, g) = r if and only if δ(f^α, g^α) = r, then α extends to an (anti)isomorphism from ∆ to ∆⁰, except possibly when ∆ and ∆⁰ are both isomorphic to the unique generalized quadrangle of order (2,2) and r= 3.

In [7], we also gave an explicit counterexample for the quadrangle of order (2,2).

In this part, we will show:

Theorem 2.

• Let Γ and Γ⁰ be two generalized n-gons, n ≥ 2, let i be an even integer satisfying 1≤i≤n−1, and let α be a surjective map from the point set of Γ onto the point set of Γ⁰. Furthermore, suppose that the orders of Γ and Γ⁰ either both contain 2, or both do not contain 2. If for every two points a, b of Γ, we have δ(a, b) = i if and only if δ(a^α, b^α) =i, then α extends to an isomorphism from Γ to Γ⁰.

• LetΓ andΓ⁰ be two generalizedn-gons,n ≥2, let i be an odd integer satisfying1≤i≤ n−1, and letα be a surjective map from the point set ofΓ onto the point set of Γ⁰, and from the line set of Γ onto the line set ofΓ⁰. Furthermore, suppose that the orders of Γ andΓ⁰ either both contain2, or both do not contain2. If for every point-line pair{a, b}

of Γ, we have δ(a, b) = i if and only if δ(a^α, b^α) = i, then α extends to an isomorphism from Γ to Γ⁰.

As already mentioned in Part I, there do exist counterexamples for the case n = i, and we will construct some in Section 3, where we also prove two little applications. Also, the condition i 6=n can be deleted for n = 3,4, of course, in a trivial way. For finite polygons, the condition i 6= n is only necessary if n = 6 and the order (s, t) of Γ satisfies s = t. For Moufang polygons, the condition i 6= n can be removed if Γ is not isomorphic to the split Cayley hexagon H(K) over some field K (this is the hexagon related to the group G₂(K)).

We will prove these statements in Section 3.

To close this section, we repeat the notation that we use throughout the two parts of this paper. Let Γ be a generalizedn-gon. For any point or linex, and any integeri≤n, we denote by Γ_i(x) the set of elements of Γ at distance i from x, and we denote by Γ_6=i(x) the set of elements of Γ not at distanceifromx. Ifκis a set of integers, then Γκ(x) is the set of elements y of Γ satisfying δ(x, y) ∈ κ. If two elements are at distance n, then we say that they are opposite. Non-opposite elementsxandyhave a unique shortest chain (x=x₀, x₁, . . . , x_k =y) of length k =δ(x, y) joining them. We denote that chain by [x, y], and we set x1 = proj_xy (and hence x_k−1 = proj_yx). When it suits us, we consider a chain as a set so that we can take intersections of chains. For instance, if [x, z] = (x = x₀, x₁, . . . , x_i, x⁰_i+1, . . . , x⁰<sub>`</sub> = z), with no x<sup>0</sup><sub>j</sub> equal to any xj<sup>0</sup>, 0< i < j ≤k and i < j<sup>0</sup> ≤ `, then [x, y]∩[x, z] = [x, xi]. If for two non-opposite elements x, y the distance δ(x, y) is even, then there is a unique element

z at distance δ(x, y)/2 from both x and y; we denote z =x1y, or, if x and y are points at distance 2 from each other, then we also write xy:=x1y.

In the next section, we will prove Theorem 2. In Section 3, we produce some counterex- amples and prove some applications.

2. Proof of Theorem 2

As in the proof of Theorem 1, we again see that α is necessarily bijective.

We again prove the assertion in several steps, the general idea being to show that collinear- ity of points is preserved (then Lemma 1.3.14 of [9] gives the result).

Throughout we putT_a,b:= Γ_i(a)∩Γ_i(b), for points a, bof Γ.

2.1. Case i < ⁿ⁻¹₂ , with i even

This is the easy case. Putλ :={2i+ 2, . . . , n} 6=∅ and κ:={0,1, . . . , i−2}. Then one can easily check that for two arbitrary distinct points a, b of Γ, we have T_a,b = ∅ if and only if δ(a, b)∈ λ. Also, it is easily verified that, if δ(a, b) ∈/ λ∪ {i}, then Γ_i(a)∩Γ_λ(b) = ∅ if and only if δ(a, b)∈κ. Now clearly, if δ(a, b)∈κ, then

Γ_κ(a)⊆Γ_κ(b)∪Γ_i(b)⇐⇒δ(a, b) = 2.

Hence α preserves collinearity and the assertion follows.

2.2. Case i = ⁿ⁻¹₂ , with i even

Here, Ta,b is never empty, for all pointsa, b of Γ.

First supposes >2. Let a, bbe arbitrary points of Γ. Then clearly |T_a,b|= 1 if and only if δ(a, b) = 2i. So we can distinguish distance 2i. Also, it is clear that Γ_i(a)∩Γ_2i(b) = ∅ if and only if δ(a, b)< i. Now one proceeds as in case 2.1.

Next suppose s = 2. Then |T_a,b| = 1 if and only if δ(a, b) ∈ {2i−2,2i}. Also, Γ_i(a)∩

Γ_{2i−2,2i}(b) =∅ if and only ifδ(a, b)< i−2. Then similarly as before, ifδ(a, b)< i−2, then

Γi(a)∩Γ<i−2(b) = ∅ ⇐⇒δ(a, b) = 2.

So again, α preserves collinearity.

The next two cases have some overlap. In particular, if i = (n+ 1)/2, then two proofs apply.

2.3. Case i ∈ {ⁿ₂ + 1,ⁿ⁺¹₂ }, i even and n >6

LetSbe the set of pairs of distinct points (a, b) such thatδ(a, b)6=iand the setTa,b contains at least two points at distance i from each other. We claim that a pair (a, b) belongs to S if and only if δ(a, b)< i. Suppose first that 06=δ(a, b) =k, k < iand put m=a1b. Consider a point c at distancei−k/2 from m such that proj_ma 6= w := proj_mc6= proj_mb (note that δ(c, w) = i−k/2−1 > 0). Let v be the element of [c, w] at distance i/2 from c (such an element exists since i/2≤i−k/2−1). Consider a pointc⁰ at distance i/2 from v such that

proj_vm 6= proj_vc⁰ 6= proj_vc. The points c and c⁰ are both points of T_a,b and lie at distance i from each other.

Now let δ(a, b) = k > i and suppose by way of contradiction that c, c⁰ ∈ Ta,b with δ(c, c⁰) = i. If proj_ac6= proj_ac⁰, then we have a path of length 2ibetweencandc⁰ containinga.

This implies that δ(c, c⁰)≥2n−2i > i, a contradiction. Suppose now that proj_ac= proj_ac⁰. Define v as [a, c] ∩[a, c⁰] = [a, v]. If we put δ(a, v) = j, then there is a path of length

` = 2i−2j ≤ n between c and c<sup>0</sup>. Now ` = i implies j = i/2. If the path [b, c] does not contain v, there arises a circuit of length at most 3i < 2n, a contradiction (remembering n > 6). But if v ∈ [b, c], there arises a path between a and b of length at most i, the final contradiction. Our claim is proved.

Putκ={1,2, . . . , i−2}. Then (a, b)∈S if and only if δ(a, b)∈κ.

Now two distinct points a and b are collinear if and only if δ(a, b) ∈ κ and Γ_κ(a) ⊆ Γ_κ(b) ∪ Γ_i(b). Indeed, let δ(a, b) = k, 2 < k < i. Then k = i − j, 0 < j < i− 2.

Consider a point cat distance j+ 2 froma such that proj_ac6= proj_ab. Thenδ(a, c)∈κ, but δ(b, c) = i+ 2. Ifδ(a, b) = 2, then the triangle inequality shows the assertion. Hence we can distinguish distance 2 and so α preserves collinearity of points.

2.4. Case ⁿ⁺¹₂ ≤i < n−2, with i odd if i = ⁿ₂ + 1

LetS be the set of pairs of points (a, b) for which there exists a point c, a6=c6=b, such that T_a,b ⊆ Γ_i(c). Note that T_a,b is never empty because n/2 < i. We claim that the pair (a, b) with δ(a, b) = k belongs to S if and only if 2 < k < 2(n−i). Note that there are always even numbersk satisfying these inequalities becausei < n−2. So let a, bbe points of Γ with δ(a, b) = k and let m be an element at distance k/2 from both a and b (m is unique if a is not opposite b).

We first show that k < 2(n −i) if and only if every element y of T_a,b lies at distance i−k/2 from m with proj_ma 6= proj_my 6= proj_mb. Suppose first that k ≥ 2(n−i). Since k+ 2i ≥ 2n, it is possible to find an element y of T_a,b such that proj_ay 6= proj_ab. Clearly, δ(y, m) 6= i−k/2. Now suppose k < 2(n−i) and let y ∈ T_a,b. Let j be the length of the path [a, b]∩[a, y]. Then there is a path of length ` =k−2j+i between b and y. If ` ≤n, then ` = i and so necessarily j = k/2. Hence y is an element as claimed. If ` > n, then δ(b, y)≥2n−` > i, a contradiction.

From this, it is clear that all pairs (a, b) with 2 < δ(a, b) = k < 2(n−i) belong to S (indeed, choose the point c on the line proj_ab, at distance k from b).

We now show that

(∗) every point cat distanceifrom every element ofTa,bhas to lie at distancek/2 fromm, and proj_ma= proj_mc or proj_mb= proj_mc.

Suppose cis a point at distance i from every element of T_a,b. Consider the set T⁰ ={x∈T_a,b|δ(x, m) = i−k/2 and proj_ma6= proj_mx6= proj_mb}.

Then we may assume that T⁰ contains at least two elements yand y⁰ at distance 2 from each other (this is clear either if i > n/2 + 1, or if n is odd, or if t > 2 in case i = n/2 + 1 and i is odd; if t = 2 and i = n/2 + 1 with i odd, then we consider the dual of Γ; finally the

case i = n/2 + 1 with i even is not included in our assumptions, see Subsection 2.3). Put w = y1y⁰. Then δ(c, w) = i−1. Put γ = [c, w]. We show that γ contains m. Suppose by way of contradiction that this is not true. Define the element z as [w, c]∩[w, m] = [w, z].

Putγ⁰ = [z, c]. An element y⁰⁰ of T⁰ either lying onγ⁰ (if δ(c, m)≥i−k/2) or such that the path [y⁰⁰, m] contains γ⁰ (otherwise), clearly does not lie at distanceifromc, a contradiction.

So the point c has to lie at distance k/2 from m. But if proj_ma 6= proj_mc 6= proj_mb, then similarly we can find an element of T⁰ not at distance i fromc, which shows (∗).

Letk = 2 ork ≥2(n−i). We show that if a pointclies at distanceifrom every element of Ta,b, thenc∈ {a, b}. Ifk= 2, then this follows immediately from (∗). So supposek≥2(n−i) and let c be such a point. We may assume that, if δ(m, c) 6= n, then proj_ma = proj_mc. If δ(a, c)6=n, then we define the element z as [m, c]∩[m, a] = [m, z]; otherwise we define z as [proj_ma, c]∩[proj_ma, a] = [proj_ma, z]. Note that δ(c, z) =δ(a, z) =:`. Put j =i−n+k/2.

It is easy to check that for an elementv of the path [a,proj_ma], the following property holds.

(∗∗) There exists y∈T_a,b such that [a, y]∩[a, m] = [a, v] if and only if δ(a, v)≤j.

It follows from (∗∗) that`≤j (indeed, if y∈Ta,b is such thatm /∈[a, y], then the path [c, y]

is longer than the path [a, y]).

But similarly, if `≤j, then an elementy ∈T_a,b such that proj_zc∈ [a, y], does not lie at distancei from c, a contradiction.

This shows our claim. Note that, if 2< k <2(n−i) and if c is a point of Γ at distance k/2 from m with proj_mc∈ {proj_ma,proj_mb}, then automaticallyT_a,b⊆Γ_i(c).

Now defineS⁰ ={(a, c)| ∃b ∈ P such that Ta,b ⊆Γi(c)}. From the previous paragraph it is clear that S⁰ \S is precisely the set of all pairs of collinear points.

Hence α preserves collinearity.

2.5. Case i = n−2 2.5.1. Case n = 6

Let C be the set of pairs of points (a, b), δ(a, b) 6= 4, such that for every point y in T_a,b, there exists a point y⁰ in T_a,b, y⁰ 6=y and δ(y, y⁰) 6= 4, with the property that Γ₄(y)∩T_a,b = Γ4(y⁰)∩Ta,b. Clearly, C contains all pairs of collinear points. Suppose now that (a, b) ∈ C with δ(a, b) = 6. We look for a contradiction. If x is a point of T_a,b, then either x lies on a line at distance 3 from both a and b, or x is a point at distance 3 from a line A through a and from a line B through b, with A opposite B. Then one can check that for a point y of T_a,b on a line at distance 3 from both aand b, there does not exist a pointy⁰ 6=y inT_a,b such that Γ₄(y)∩T_a,b = Γ₄(y⁰)∩T_a,b. So the set C is the set of pairs of collinear points and the theorem follows.

2.5.2. Case n >6 Step 1: the set Sa,b

For two pointsa and b, we define

S_a,b ={x∈ P |Γ_n−2(x)∩T_a,b=∅}.

We claim the following:

(i) If δ(a, b) = 2 ands ≥3, then S_a,b = (Γ₂(a)∪Γ₂(b))\Γ₁(ab). If δ(a, b) = 2 ands = 2, then S_a,b= (Γ₂(a)∪Γ₂(b))\ {a, b}.

(ii) If δ(a, b) = 4, then {a1b} ⊆ S_a,b = {a1b} ∪[Γ₂(a1b)∩Γ₄(a)∩Γ₄(b)]. If t ≥ 3, then S_a,b = {a1b}. If k := δ(a, b) 6∈ {2,4, n}, then every x ∈ S_a,b lies at distance k/2 from a1b =: m with proj_ma 6= proj_mx 6= proj_mb. If moreover s > 2 and k ≡ 2 mod 4, or t >2 andk ≡0 mod 4, then S_a,b =∅. Finally, ifδ(a, b) = n, then let γ be an arbitrary path of lengthnjoiningaandb, letmbe the middle element ofγ and putv_a= proj_ma, v_b = proj_mb. Then

S_a,b ⊆ (Γ_n/2(m)∩Γ_n/2+1(v_a)∩Γ_n/2+1(v_b)) [

(Γ_n/2+1(v_a)∩Γ_n/2+2(m)∩Γ_n(a)) [

(Γ_n/2+1(v_b)∩Γ_n/2+2(m)∩Γ_n(b)).

If moreover s >2 and n≡2 mod 4, or t >2 and n≡0 mod 4, then S_a,b ⊆ (Γ_n/2+1(v_a)∩Γ_n/2+2(m)∩Γ_n(a))

[

(Γ_n/2+1(v_b)∩Γ_n/2+2(m)∩Γ_n(b)).

We prove these claims.

(i) Suppose δ(a, b) = 2. Clearly, every point collinear with a or b, not on the line ab, belongs toS_a,b. Also, if s= 2, then the unique point of abdifferent from a and b is an element ofS_a,b. Let xbe an arbitrary point inS_a,b. Put j =δ(x, a). If j =s = 2, then there is nothing to prove, so we may assume (j, s) 6= (2,2). Suppose first there exists a j-path γ between a and x containing ab, but not the point b. Let v be the element on γ at distance j/2 from a, and consider an element y at distance n−2−j/2 from v such that proj_va 6= proj_vy 6= proj_vx. Note that such an element v exists because (j, s) 6= (2,2). Then y lies at distance n−2 from a, b and x, a contradiction. So we can assume that proj_abx = a. If j = 2, then again, there is nothing to prove. So we may assume 2 < j < n (the case j = n is contained in the previous case, or can be obtained from the present case by interchanging the roles of a and b). Let v be an element at distance n−j −1 from the line ab such that a 6= proj_abv 6= b. Note that v and x are opposite and δ(a, v) = n −j. Consider an element v⁰ incident with v, different from proj_va, and let v⁰⁰ be the projection of x onto v⁰. Let w be the element of [x, v⁰⁰] at distance j/2−2 from v⁰⁰. An element y at distance j/2−2 from w such that proj_wx6= proj_wy6= proj_wv⁰⁰ lies at distancen−2 froma,b and x, a contradiction.

Claim (i) is proved.

(ii) We proceed by induction on the distance k between a and b, the case k = 2 being claim (i) above. Supposeδ(a, b) =k > 2 and let m be an element at distancek/2 from botha and b. Note that, if δ(a, b) = 4, the point a1b indeed belongs toS_a,b. Let now x be an arbitrary element of S_a,b and put `=δ(x, m).

Suppose first that, if ` 6= n, proj_ma 6= proj_mx 6= proj_mb. Then we have the following possibilities :

1. Suppose ` < k/2. Then δ(a, x)< k and we apply the induction hypothesis. Since b ∈ S_a,x 6= ∅ and m 6= a1x, we have δ(a, x) ∈ {2,4}. Hence either δ(a, b) = 4 and x = a1b (which is a possibility mentioned in (ii)), or δ(a, b) = 6 and x lies onm, or δ(a, b) = 8 and x =m. But in these last two cases, the “position” of b contradicts the induction hypothesis.

2. Suppose` ≥k/2. Letγ<sup>00</sup> be an`-path betweenm andxcontaining neither proj_ma nor proj_mb. Putγ⁰ = [a, m]∪γ⁰⁰. Letwbe the element onγ⁰ at distance (`+k/2)/2 from both x and a. If ` =k/2 (and hence w = m) and either k ≡ 2 mod 4 and s = 2, or k ≡ 0 mod 4 and t = 2, then there is nothing to prove. Otherwise, there exists an element y of Γ at distance n−2−(k/2 +`)/2 from w such that proj_wa 6= proj_wy 6= proj_wx and proj_wb 6= proj_wy. Now y lies at distance n−2 froma, b and x, a contradiction.

Let nowxbe a point ofS_a,bat distance`fromm, 0< ` < n, for which proj_mx= proj_ma.

Let [a, m]∩[x, m] = [v, m], and put i⁰ =δ(v, a). We have the following possibilities : 1. Suppose `≤k/2 or `=k/2 + 2 and i⁰ < k/2−1. Againδ(a, x)< k and applying

the induction hypothesis, we obtain a contradiction as in Case 1 above.

2. Suppose n > ` > k/2 + 2. Leth be an element at distancen−2 fromxsuch that proj<sub>m</sub>a6= proj<sub>m</sub>h6= proj<sub>m</sub>b andδ(m, h) =n−`+ 2. Letj =n−2−δ(h, m)−k/2.

Leth⁰ be the element on the (n−2)-path between x and h at distance j/2 from h. An elementy at distancej/2 fromh⁰ such that proj_h0x6= proj_h0y 6= proj_h0hlies at distancen−2 from a, b and x, a contradiction.

3. Suppose ` =k/2 + 2, i⁰ =k/2−1 andk < n−1. Then δ(b, x) =k+ 2 andv lies at distancek/2 + 1 from bothb andx. Let Σ be an apartment containingx,b and v, and letv⁰ be the element in Σ opposite v. Letw= proj_va, w⁰ = proj_v0wand d the length of the path [w, a]∩[w, w⁰]. Note thatd ≤k/2−2. For an elementynot opposite w⁰, let w_y⁰⁰ be the element such that [w, w⁰]∩[y, w⁰] = [w⁰⁰_y, w⁰]. Consider now an elementy such that δ(w⁰⁰_y, w⁰) =k/2−d−2 andδ(w⁰⁰_y, y) =d. Thenylies at distancen−2 from a, b and x, a contradiction.

4. If `=k/2 + 2,i⁰ =n/2−1 and k =n, there is nothing to prove.

5. Suppose finally` =k/2 + 2,i⁰ =k/2−1 and k =n−1. Then δ(b, x) =n−1. Let b⁰ and x⁰ be the elements of the path [b, x] at distance (n−1)/2−1 from b and x, respectively. Since a ∈S_b,x, either δ(a, b⁰) = (n+ 1)/2 or δ(a, x⁰) = (n+ 1)/2 (this is what we proved up to now for the “position” of a point ofS_b,x). But since we obtain a path betweena and b⁰ (x⁰) of lengthd= (3n−5)/2 (passing through proj_ma), the triangle inequality implies δ(a, b⁰), δ(a, x⁰) ≥ 2n−d > (n + 1)/2, a contradiction.

This completes the proof of our claims.

Step 2: the sets O and O

Ifs≥3 andt ≥3, letO be the set of pairs of distinct points (a, b) such that|Sa,b|>1. Then O contains only pairs of collinear points and pairs of opposite points, and all pairs of collinear

points are included inO. Note that, if n is odd, there are no pairs of opposite points, which concludes the proof in this case.

Let now s= 2 or t= 2 (so n is even). For a point c∈Sa,b, we define the set C_a,b;c ={c⁰ ∈S_a,b|S_c,c⁰ ∩ {a, b} 6=∅}.

Now let O be the set of pairs of points (a, b), δ(a, b) 6= n − 2 for which |S_a,b| > 1 and

|C_a,b;c| > 1, ∀c ∈ S_a,b. Note that if a and b are collinear, the pair (a, b) always belongs toO. Clearly, no pair of points at mutual distance 4 belongs to O. Now consider two points a and b at distance k, 4 < k < n −2. We show that such a pair (a, b) does not belong to O. Putm =a1b and let x be a fixed point of S_a,b. Let x⁰ be an element of S_a,b different from x. Since s = 2 or t = 2, we have proj_mx = proj_mx⁰, so δ(x, x⁰) ≤ k −2. But now δ(a, x1x⁰) = δ(b, x1x⁰)≥k/2 + 1> δ(x, x⁰)/2, so neitheranorb belongs toS_x,x⁰. This shows thatO contains only pairs of collinear or opposite points, and all pairs of collinear points are included in O.

Let O be the set of pairs of points (a, b) satisfying δ(a, b) 6= n−2, (a, b) 6∈ O and such that there exist a point c∈Sa,b for which (a, c) and (b, c) both belong to O. Then clearly, O contains all pairs (a, b) of points at mutual distance 4 (indeed, consider the point c=a1b), and also some pairs of opposite points (possibly none, or all).

Step 3: the set O⁰ Suppose first s≥3.

Let O⁰ be the subset of O of pairs (a, b) for which there exist points c and c⁰ such that the following conditions hold :

(i) T_a,b ⊆Γ_n−2(c)∪Γ_n−2(c⁰),T_c,c⁰ ⊆Γ_n−2(a)∪Γ_n−2(b);

(ii) (c, c⁰),(a, c),(a, c⁰),(b, c),(b, c⁰)∈O;

(iii) (c, y),(c⁰, y)6∈O, ∀y∈Ta,b.

We claim that O⁰ is the set of pairs of collinear points. A pair (a, b) of collinear points always belongs to O⁰. Indeed, here, we can choose c and c⁰ on the line ab, different from a and b (Condition (iii) is satisfied because n 6= 6). So let δ(a, b) = n and suppose by way of contradiction that we have two points c and c⁰ with the above properties. Let m ∈ Γ_n/2(a)∩ Γ_n/2(b). For an element x at distance j from m, 0 ≤ j ≤ n/2− 3, such that proj_ma6= proj_mx6= proj_mb, define the following set:

T_x ={y∈T_a,b|δ(x, y) =n/2−2−j,proj_xa6= proj_xy6= proj_xb}.

Note thatT_x ⊆T_a,b. We first prove that for any set T_x,

(3) there does not exist a point v ∈ {c, c⁰} such thatT_x⊆Γ_n−2(v).

Put M = Γn/2(a)∩Γn/2(b). Suppose Tm ⊆ Γn−2(v), with v ∈ {c, c⁰}. It is easy to see (see for instance Step 4 of Subsection 3.4 of [7]) that δ(v, m) = n/2 and proj_ma = proj_mv or proj_mb= proj_mv. Suppose proj_ma= proj_mv. But then δ(a, v)≤n−2, so δ(a, v) = 2 (since (a, v)∈O) andvis a point at distancen/2 frommlying on the lineL= proj_am. This implies that for an arbitrary point m⁰ of M, m⁰ 6=m, T_m⁰ ∩Γ_n−2(v) =∅ (note that T_m∩T_m⁰ =∅),

so T_m⁰ ⊆ Γ_n−2(v⁰), with {v, v⁰} = {c, c⁰}. We obtain a contradiction by considering a third element of M.

Letx be an element at distance j = 1 from m such that proj_ma6=x6= proj_mb. Suppose T_x ⊆Γ_n−2(v), withv ∈ {c, c⁰}. Then again it is easy to show that δ(v, x) = δ(x, a) = n/2 + 1 and proj_xv = proj_xa =m. If proj_ma= proj_mv or proj_mb = proj_mv, then we are back in the previous case, which led to a contradiction, so suppose proj_ma 6= proj_mv 6= proj_mb. Consider the n-path between aand v that containsm. Then we can find a pointyof T_a,b on this path that is collinear with v, in contradiction with condition (iii). Note that thus no element of {c, c⁰} lies at distance n/2 from m.

We now proceed by induction on the distance j between x and m. Let j > 1. Consider an element xat distancej fromm such that proj_ma6= proj_mx6= proj_mb. Suppose by way of contradiction that Tx ⊆Γn−2(v), with v ∈ {c, c⁰}. Letx⁰ = proj_xm. Then it is again easy to show that δ(v, x) =δ(a, x) =n/2 +j and proj_xv =x⁰. Remark that proj_x0a6= proj_x0v, since otherwiseT_x⁰ ⊆Γ_n−2(v) (sinceδ(v, x⁰) =n/2 +j−1 andδ(v, w) =n/2−j−1, withw∈T_x⁰), in contradiction with the induction hypothesis. Suppose first that in the case j = 2, t≥3 or n≡2 mod 4. Consider now an elementz incident with the elementw= proj_x0a, but different from proj_wa, from proj_wb and from x⁰ (such an element exists, because of the restrictions above). But then we have δ(v, w⁰) = n, for every element w⁰ of Tz, so Tz ⊆ Γn−2(v⁰), with {c, c⁰}={v, v⁰}, a contradiction with the induction hypothesis.

Now let j = 2, t = 2 and n ≡ 0 mod 4. Let L be the line mx and put w = proj_Lv.

Then Tw ⊆Γn−2(v⁰), with {v, v⁰} ={c, c⁰}, sov⁰ is a point at distance n/2 + 2 from m with δ(m, v⁰) 6= n/2, and proj_Lv⁰ 6= w. Now consider the point on [m, b] at distance n/2−4 from m. This is a point of T_c,c⁰, but it does not lie at distance n−2 from a, nor from b, in contradiction with condition (i). This completes the proof of (3).

Consider now a lineLat distance j =n/2−3 from m, such that proj_ma6= proj_mL6= proj_mb.

The points onLdifferent from the projection ofm ontoLare points ofT_L. By (3), we know that TL 6⊆ Γn−2(v), for v ∈ {c, c⁰}. Since s ≥ 3, TL contains at least 3 points, so we may suppose that at least two points of them are contained in Γ_n−2(v), with v ∈ {c, c⁰}. This implies that v is at distancen−3 fromL, so at distancen−4 from a unique pointxof L. If x= proj_La, thenTL ⊆Γn−2(v), a contradiction, so we can assume thatx6= proj_La. Let first n6= 8 or t≥3. Then consider a line L⁰ incident with proj_La,L⁰ 6=L, at distance n−3 from botha and b (such a line always exists because of our assumptions). NowT_L⁰ ∩Γ_n−2(v) = ∅ (because all points ofTL⁰ lie oppositev), soTL⁰ is contained in Γn−2(v⁰), with{v, v⁰}={c, c⁰}, the final contradiction.

Let now n = 8 and t = 2. Then δ(v⁰, x) = 6, with {v, v⁰} = {c, c⁰}, T_L 6⊆ Γ₆(v⁰) and δ(v, v⁰)∈ {2,8}. Now for each potential v⁰, it is possible to construct a point of Tv,v⁰ not at distancen−2 from a nor from b, a contradiction with condition (i). For example, let us do in detail the case δ(v, v⁰) = 2. Since v does not lie at distance 6 from a or b, we know that δ(a, vv⁰) = δ(b, vv⁰) = 7, v⁰ 6= proj_vv0a 6= v and v⁰ 6= proj_vv0b 6= v. Also proj_vv0a 6= proj_vv0b, since otherwise we would obtain a point ofT_a,b not at distance 6 fromv nor fromv⁰. Now let N be the line at distance 3 fromb and at distance 4 fromvv⁰. Then the points ofN different from proj_Nv are points of Tv,v⁰ \Γ6(b), but not all these points lie at distance 6 from a, a contradiction.

So in the caseδ(a, b) = n, pointscand c⁰ with the above properties cannot exist, and the

proof is finished for s≥3.

Suppose nows = 2.

Let first n = 8. Note that t ≥ 4. Let O⁰ be the subset of O of pairs of points (a, b) for which there exist a pointc∈S_a,band pointsc⁰,c⁰⁰ belonging toC_a,b;c such thatS_c,c⁰∩ {a, b}= S_c,c⁰⁰∩ {a, b}=S_c⁰_,c⁰⁰∩ {a, b}={a}. We claim thatO⁰ is the set of all pairs of collinear points.

Letδ(a, b) = 2. Then considering three pointsc, c⁰ and c⁰⁰ on three different lines through a, different from ab, shows that (a, b) ∈ O⁰. Now let δ(a, b) = 8, and suppose (a, b) ∈ O⁰. Let m be any point at distance 4 from both a and b. Put a⁰ = proj_ma and b⁰ = proj_mb. Suppose that the pointcmentioned in the property above lies at distance 5 from the linea⁰ (which is allowed by Step 1 above). Then it is easy to see that c⁰ and c⁰⁰ both have to lie at distance 5 fromb⁰, which contradicts S_c⁰_,c⁰⁰∩ {a, b}={a}. Similarly ifc lies at distance 5 from b⁰. Suppose from now on n >8. Let O⁰ be the subset of O of pairs (a, b) for which

(i) ∃!x₁ ∈S_a,b:∀x⁰ ∈S_a,b,|S_x1,x⁰ ∩ {a, b}|= 1,

(ii) there exist pointsc and c⁰ such that T_a,b ⊆Γ_n−2(c)∪Γ_n−2(c⁰), (iii) (x₁, v)∈O, with v an element of the set {a, b, c, c⁰},

(iv) (a, c),(a, c⁰),(b, c),(b, c⁰),(c, c⁰)∈O, (v) (c, y),(c⁰, y),(x₁, y)6∈O, ∀y∈T_a,b, (vi) x₁ =S_a,c∩S_a,c⁰ ∩S_b,c∩S_b,c⁰ ∩S_c,c⁰.

We claim that O⁰ is the set of pairs of points at distance 2.

The claim is clear for two collinear points a and b. Indeed, let x1 be the unique point on ab, different from a and b, and c and c⁰ points on two different lines (different from ab) through the point x₁ (Condition (v) in the definition of O⁰ does not hold if n = 8, which is the reason we treated the octagons before).

So let δ(a, b) =n and suppose by way of contradiction that we have two points c and c⁰ with the above properties. Let γ be a fixed n-path between a and b, and define m, a⁰ and b⁰ as above in the case n = 8.

For an element x at distance j from m, 0 ≤j ≤n/2−3, such that proj_ma 6= proj_mx6=

proj_mb, we define the sets T_x in the same way as for the case s ≥ 3. We again first prove thatTx6⊆Γn−2(c), for all sets Tx. Now, everything can be copied from the cases ≥3, except when j = 0 or j = 2.

(j = 0) Suppose T_m ⊆ Γ_n−2(v), with v ∈ {c, c⁰}. Then we know that δ(v, m) = n/2 and we may assume proj_mv = proj_ma. This implies that δ(a, v) ≤n−2, so δ(a, v) = 4 (see Condition (iv)). Then x₁ is the point of the path γ collinear with a (since S_a,v contains only the element a1v in this case), so δ(b, x₁) = n−2, which contradicts the fact that (x₁, b)∈O.

(j = 2) Note that this case is a problem only when n≡2 mod 4, so we may assume thatm is a line. Suppose T_L ⊆Γ_n−2(v), for a line L concurrent withm, at distance n/2 + 2 from a and b, and for a point v ∈ {c, c⁰}. Then δ(v, L) = δ(a, L) = n/2 + 2 and proj_La = proj_Lv. We may again assume that v does not lie at distance n/2 from m.

By Step 1, there are essentially two possibilities for x₁.

First, suppose the point x1 lies at distance n/2 + 2 from m and at distance n/2 + 1 from a⁰. Then there arises an n-path γ⁰ between a and x₁ sharing the path [a, a⁰]

withγ. Leta⁰⁰be the projection of x₁ ontoa⁰. Sincea⁰⁰ is a line at distancen/2 from both a and x₁, and v ∈S_x1,a, either the distance between v and a⁰⁰ is n/2 (which is not true), or the distance between v and a⁰⁰ is n/2 + 2, which is again impossible.

Secondly,x₁ cannot lie at distancen/2 fromm, since this would contradict condition (v) (x₁ would be collinear with a point of T_a,b).

Hence (3) is proved in this case.

Now we have to find an alternative argument for the last paragraph of the general case, since we relied there on the fact that a line contains at least 4 points. We keep the same notation of that paragraph. Now the only possibility (to rule out) that we have not considered yet (because it does not occur in the general case) is the case that c and c⁰ both lie at distance n−2 from different points u and u⁰ on L, δ(c, L) = δ(c⁰, L) = n−1 and u and u⁰ different from the projection w of a onto L.

Suppose first n > 10 (otherwise some of the notations introduced below don’t make sense). Put L⁰ = proj_wa and l⁰ = proj_L0a. Suppose the unique point z on L⁰ at distance n−2 from cis not l⁰. Then consider a line K through z, different from L⁰ and from proj_zc.

Because c is at distance n from all the points of K, different from z (which are elements of T_a,b) we can conclude that T_K ⊆ Γ_n−2(c⁰), a contradiction to (3). So [c, L⁰] contains l⁰. Define the element p as [l⁰, m]∩[l⁰, c] = [l⁰, p]. Suppose p6=m and let j =δ(l⁰, p). Consider the element z⁰ on [c, p] at distancej+ 3 from p. Note that z⁰ is a line at distance n−3 from both a and b. Since c is not at distance n−2 from any of the points of T_z⁰, we conclude that Tz⁰ ⊆ Γn−2(c⁰), a contradiction to (3). If p = m, but if a⁰ 6= proj_mc 6= b⁰, we obtain a contradiction considering the line z⁰ at distance n/2−3 from m on [c, m] that does not contain a⁰ orb⁰). So the path [c, l⁰] contains a⁰ orb⁰ (henceδ(c, m) = n/2 + 4). Suppose [c, l⁰] contains a⁰. Consider now the element q defined by [m, c]∩[m, a] = [m, q]. Then we first show that q coincides either with a⁰ (Case 2 below), or with the element a⁰⁰ = proj_a0a (Case 1 below). Indeed, if not, then δ(a, c)< n, which implies that δ(a, c) = 4 (by Condition (iv)) and x1 = a1c. Since (b, x1) ∈ O, δ(b, x1) is then equal to n. So it would be possible to find an element of T_a,b for which the projection onto ax₁ is different from a and from x₁, a contradiction (such a point would be at distance n−2 from x₁, which would imply that x1 6∈Sa,b). One checks that in the case n= 10, we end up with the same possibilities.

Case 1. Consider the element m⁰ ∈[a⁰⁰, c] that is at distance 2 from a⁰⁰. A point of S_a,c lies at distance n/2 or n/2 + 2 from m⁰. Because of the conditions, x₁ ∈S_a,c. If x₁ lies at distance n/2 + 1 from a⁰, then δ(x1, m⁰) =n/2 + 4, a contradiction. If x1 lies at distance n/2 + 1 from b⁰, there arises a path of length n/2 + 6 between x₁ and m⁰, which is again a contradiction, since n >8. Note that x₁ cannot lie at distance n/2 from m because (x1, y)6∈O for y∈Ta,b.

Case 2. Suppose x₁ lies at distance n/2 + 1 from b⁰. Let b₀ be the projection of x₁ onto b⁰. Then a point of S_x1,b lies at distance n/2 or n/2 + 2 from b₀. Because of the conditions, c ∈ S_x1,b. But we have a path of length n/2 + 6 between c and b₀ (containing [c, a⁰]), a contradiction since n 6= 8. Note that again, δ(x₁, m) 6= n/2.

So we know that x₁ lies at distance n/2 + 1 from a⁰. Suppose the projections of c and x₁ onto a⁰ are not equal (which only occurs if n ≡ 2 mod 4, since s = 2). Let a₀ = proj_a0x₁. Since c∈S_x1,a, the distance betweencanda₀ is eithern/2 orn/2 + 2,

a contradiction (δ(c, a₀) = n/2 + 4). So the projection of c onto a⁰ is the element a₀. Suppose proj_a0c6= proj_a0x₁. Since the distance betweencand a₀ isn/2 + 2, and c∈Sa,x1, the pointc has to lie at distance n/2 + 1 from either a⁰ or proj_a0x1, which is not true. So proj_a0c= proj_a0x₁ :=h. Note that the projections of cand x₁ onto h are certainly different, since we know that the distance between c and x₁ is either n or 2, and the last choice would contradict the fact that a ∈ Sx1,c. Now consider the projection m⁰ of c onto h. This is an element at distance n/2 from both c and x₁. Now δ(b, m⁰) = n/2 + 4, which contradicts the fact thatb ∈S_c,x1.

This completes the case s= 2 and hence the casei=n−2.

2.6. Case i = n−1

We can obviously assume n ≥ 6. If n = 6 and s = t = 2, then an easy counting argument yields the result. Ifs= 2, then, since both sand tare infinite forn odd,n is even and hence t > 2. In this case, we dualize the arguments below (this is possible since i is odd). So we may assume throughout thats >2.

For two points a and b with δ(a, b) 6=n−1, let O_a,b be the set of pairs of points {c, c⁰}, cand c⁰ different from a and from b, for which

T_v,v⁰ ⊆Γ_n−1(w)∪Γ_n−1(w⁰),

whenever {a, b, c, c⁰}={v, v⁰, w, w⁰}. For a pair {c, c⁰} ∈O_a,b, we claim the following:

(i) If δ(a, b) = 2, then either c and c⁰ are different points on the line ab (distinct from a and b), or, without loss of generality, c is a point onab and c⁰ ∈Γ₃(ab) with proj_abc⁰ 6∈

{a, b, c}. Moreover, all the pairs (c, c⁰) obtained in this way are elements of O_a,b. (ii) If δ(a, b) = 4, then either c and c⁰ are collinear points on the lines am or bm (where

m=a1b) different from m, or cand c⁰ are points collinear with m, at distance 4 from botha andb, and at distance 4 from each other. Again, all the pairs (c, c⁰) obtained in this way, are elements of O_a,b.

(iii) Let 4 < δ(a, b) = k < n−1 and put m = a1b. Then c and c⁰ are points at distance k/2 from m, at distancek from both a and b, and at distancek from each other.

Ifδ(a, b) = 2, then an elementx ofT_a,bis either opposite the line ab, or lies at distance n−3 from a unique point on ab, different from a and from b. If δ(a, b) = 4, then an element x of Ta,b either lies at distance n−1 or n−3 from m =a1b with proj_ma 6= proj_mx6= proj_mb or lies at distance n−3 from a point x⁰ on am orbm, x⁰ 6∈ {a, b, m} with am6= proj_x0x6=bm.

It is now easy to see that the given possibilities forc and c⁰ in (i) and (ii) indeed satisfy the claim for δ(a, b) = 2 and δ(a, b) = 4, respectively.

Letδ(a, b) = k ≤n−2 and again putm =a1b. Suppose {c, c⁰} ∈O_a,b. For an element y with δ(m, y) =j ≤n−k/2−2 and proj_ma 6= proj_my6= proj_mb, we define the following set:

Ty ={x∈ P |δ(x, y) = (n±1)−j−k/2 and proj_yx6= proj_ym if δ(x, y)6=n}.

For an element y with δ(m, y) = n−k/2− 1 and proj_ma 6= proj_my 6= proj_mb, we define T_y as the set of elements at distance 2 from y, not incident with proj_ym. For an element y

with δ(m, y) = n−k/2 and proj_ma 6= proj_my 6= proj_mb, we define T_y as the set of elements incident with y, different from proj_ym. Note that T_y ⊆T_a,b.

First we make the following observation. Let y be an element for which the set Ty is defined, and for which δ(m, y)≤n−k/2−2. Then there exists an element v ∈ {c, c⁰} such that T_y ⊆Γ_n−1(v) if and only if δ(v, y) = δ(a, y) and proj_yv = proj_ya or proj_yv = proj_yb.

Now we prove claims (i), (ii) and (iii) above by induction on the distance k between a and b. Let k≥2. In the sequel, we include the proof for the case k = 2 in the general case.

Suppose first there exists an element v ∈ {c, c⁰} such that T_m ⊆ Γ_n−1(v). Then, by the previous observation, δ(v, m) = δ(m, a) = k/2 and we may assume that proj_mv = proj_ma.

This implies that δ(a, v) ≤ k − 2. Put {c, c⁰} = {v, v⁰}. If k = 2, we obtain a = v, a contradiction. If k = 4, then v is a point on the line am, v 6= m, and the only remaining possibility, considering the induction hypothesis and the condition Ta,v ⊆Γn−1(b)∪Γn−1(v⁰) is thatv⁰ is also a point onam, different from m. Ifk > 4, the position ofbcontradicts again the fact thatT_a,v ⊆Γ_n−1(b)∪Γ_n−1(v⁰) and the induction hypothesis. Indeed, the element at distance δ(a, v)/2 from both a and v does not lie at distance δ(a, v)/2 from b. In this way, we described all the possibilities for the points c and c⁰ in case there is a point v ∈ {c, c⁰} for which T_m ⊆ Γ_n−1(c). So from now on, we assume that there does not exist an element v ∈ {c, c⁰} such that Tm ⊆Γn−1(v).

Let l be any element incident with m, different from the projection of a or b onto m.

Suppose there exists a point v ∈ {c, c⁰} such that T_l ⊆ Γ_n−1(v). Then δ(v, l) = δ(l, a) = k/2 + 1 and we can assume that proj_lv = proj_la = m. Since Tm 6⊆ Γn−1(v), we also know that proj_ma6= proj_mv =:w6= proj_mb. Put {v, v⁰}={c, c⁰}.

Suppose firstk = 2. Thenv is a point on the lineab. We now show that the point v⁰ lies at distance 2 or 4 fromv such that proj_vv⁰ =m. Indeed, suppose proj_vv⁰ 6=m orδ(v, v⁰) =n.

If δ(v, v⁰) 6=n, put γ⁰ = [v, v⁰]. If δ(v, v⁰) =n, let γ⁰ be an arbitrary n-path between v and v⁰ not containing m. Let x be an element of T_a,b at distance n−3 from v such that either x lies on γ⁰, or [v, x] contains γ⁰. Then x is an element ofT_a,b not at distance n−1 from v or v⁰, a contradiction. So we can assume that proj_vv⁰ =m. Suppose now 4 < δ(v, v⁰). Let Σ be an arbitrary apartment through v and v⁰. Then the unique element of Σ at distance n−3 from v and belonging to T_a,b, does not lie at distance n−1 from v⁰, a contradiction, so the distance between v and v⁰ is 2 or 4. Suppose δ(v, v⁰) = 4 and proj_abv⁰ =b. Then we obtain a contradiction (with the induction hypothesis) interchanging the roles of b and v. So v⁰ is a point onab, orv⁰ is a point at distance 3 from abfor which the projection ontoabis different froma,b orv, as claimed in (i).

Suppose now k 6= 2. Let w⁰ = proj_wv. Since the distance between v and any element of T_w⁰ is less than or equal to n−3, we have that T_w⁰ ⊆ Γ_n−1(v⁰), from which follows that δ(v⁰, w⁰) = δ(w⁰, a) = k/2 + 2 and proj_w0v⁰ = proj_w0a = w. Since T_m 6⊆ Γ_n−1(v⁰), we either have that v⁰ is a point at distance k/2 from m for which the projection onto m is different from w and proj_ma 6= proj_mv⁰ 6= proj_mb (as required in (ii) and (iii)), or v⁰ is a point at distance k/2 + 2 from m for which the projection onto m is w. In the latter case, let z be the projection of v⁰ onto w (then δ(v, z) = δ(v⁰, z) = k/2) and consider an element x at distance n−1−k/2−2 from z such that proj_zv 6= proj_zx 6= proj_zv⁰. Then x is an element of T_a,b at distance n−3 from both v and v⁰, a contradiction. In this way, we described all the possibilities for the points c and c⁰ in case there is a point v ∈ {c, c⁰} and an element l

as above for which T_l ⊆ Γ_n−1(c). So from now on, we assume that there does not exist an element v ∈ {c, c⁰} such that T_l⊆Γ_n−1(v), for any l as above.

We now prove that

(3) if yis an element for which the set T_y is defined, withδ(m, y)>1, then there does not exist a point v ∈ {c, c⁰} such that T_y ⊆Γ_n−1(v).

This is done by induction on the distance j between y and m.

So let by way of contradiction l be an element at distance j from m, j > 1, for which the set T_l is defined and such that there exists an element v ∈ {c, c⁰} with T_l ⊆ Γ_n−1(v).

Put {v, v⁰} = {c, c⁰}. Let first j < n −k/2−1. Then δ(v, l) = δ(l, a) = k/2 +j and w := proj_lv = proj_la but u := proj_wv 6= proj_wa. Let w⁰ = proj_uv. Note that the distance between w⁰ and an element of T_w⁰ is (n ± 1)− k/2 −(j + 1), so an element of T_w⁰ lies at distance at most n −3 from v. We conclude that Tw⁰ ⊆ Γn−1(v⁰), from which follows that δ(v⁰, w⁰) = δ(a, w⁰) = k/2 +j + 1 or δ(v⁰, w⁰) = n− 3 (the latter is possible only if j =n−k/2−2), and proj_w0v⁰ = proj_w0a=u. Let proj_wa=u⁰. First supposeδ(v⁰, w⁰)6=n−3.

From the assumptions, it follows that proj_wv⁰ 6=u⁰. Depending on whether the projection of v⁰ onto w is u or not, the distance between v⁰ and u⁰ is k/2 +j + 2 or k/2 +j. Note that δ(v, u⁰) = k/2 +j. Now consider an element x at distance (n−1)−(k/2 +j) from u⁰ such that proj_u0x6=w, and such that x either lies on [u⁰, b], or [u⁰, x] contains [u⁰, b]. Then x is an element of T_v,v⁰ not contained in Γ_n−1(a)∪Γ_n−1(b), a contradiction. Ifδ(v⁰, w⁰) =n−3, then we similarly obtain a contradiction. So T_y 6⊆ Γ_n−1(v), for any element y at distance j from m.

Now let j = n −k/2−1. Note that T_l consists of all elements at distance 2 from l, not incident with l⁰ = proj_lm. Then δ(v, l) = n−1 or δ(v, l) = n−3, and in both cases, proj_lv = proj_la. If δ(v, l) = n−1 (= δ(a, l)), we proceed as in the previous paragraph and end up with a contradiction. So let δ(v, l) =n−3. First suppose that proj_l0v 6= proj_l0a=w.

Now consider an element w⁰ incident with w,l⁰ 6=w⁰ 6= proj_wa and w⁰ 6= proj_wb. ThenT_w⁰ ⊆ Γn−1(v), a contradiction sinceδ(m, w⁰) =j −1. So proj_l0v =w. Let [u, m] = [v, m]∩[w, m]

and put u⁰ = proj_uv. Suppose first that proj_ma6=u⁰ 6= proj_mb and v 6=m (v =m can occur only if k = 4). Then T_u⁰ ⊆ Γ_n−1(v⁰). Indeed, if we put i= δ(u, l), then δ(v, u⁰) = n−4−i andδ(m, u⁰) = n−k/2−i. So the distance betweenu⁰ and an element ofTu⁰ isi±1, and the distance between v and an element of T_u⁰ is at most n−3. So T_u⁰ is contained in Γ_n−1(v⁰), which is a contradiction since δ(m, u⁰) < j (indeed, i ≥ 2). Suppose finally u⁰ = proj_ma or v =m. If k= 2, we end up with a pointv lying on ab(namelyv = proj_ml). But then, for an arbitrary pointxonm, different froma,b andv, we have thatT_x ⊆Γ_n−1(v), in contradiction with our assumptions. Ifk= 4, we end up with v =m, but then the position ofbcontradicts the fact that Ta,v ⊆ Γn−1(b)∪Γn−1(v⁰) and the (general) induction hypothesis. Finally, if k >4, then δ(v, a)≤δ(v,proj_ma) +δ(a,proj_ma) =k−4. Now the position of b contradicts again the fact that T_a,v ⊆Γ_n−1(b)∪Γ_n−1(v⁰) and the (general) induction hypothesis.

Let finally j = n−k/2. Note that Tl consists of all elements incident with l, different from the projection l⁰ of m onto l. Then δ(v, l⁰) = n−1 or δ(v, l⁰) = n−3. Note that, in both cases, proj_l0v 6= proj_l0a. Indeed, proj_l0v = proj_l0a would imply that T_l⁰ ⊆ Γ_n−1(v), a contradiction with our assumptions. Suppose firstδ(v, l⁰) = n−3. Letl⁰⁰= proj_l0v. Since no element incident with l⁰⁰ is at distance n−1 from v, we have T_l⁰⁰ ⊆Γ_n−1(v⁰), which implies

thatδ(v⁰, l⁰) is eithern−3 orn−1 and proj_l0v⁰ 6= proj_l0a. Consider now the element on [a, l⁰] at distance 2 from l⁰. This is an element of T_v,v⁰ which is at distance n−3 from botha and b, a contradiction. Suppose now δ(v, l⁰) = n−1. Let x be the element on [v, l⁰] at distance 2 from l⁰. Since xis the only element of T_l⁰ not at distance n−1 from v, this elementx lies at distance n−1 from v⁰. But then δ(v⁰, l⁰) is either n−1 or n−3. If proj_l0v⁰ = proj_l0a, then Tl⁰ ⊆ Γn−1(v⁰), a contradiction with our assumptions. If proj_l0v⁰ 6= proj_l0a, then again the element on [a, l⁰] at distance 2 froml⁰ is an element of T_v,v⁰ at distance n−3 from both a and b, the final contradiction. This proves (3).

Suppose nowTy 6⊆Γn−1(v) for allv ∈ {c, c⁰}and for any appropriate elementy. Consider an elementlat distancen−k/2 frommsuch that the projection ofl ontomis different from the projections ofaand bontom. Letube the projection ofaontol. SinceT_l 6⊆Γ_n−1(c) and Tl 6⊆Γn−1(c⁰), there is an elementxincident with l, different fromu, at distancen−1 fromc but not fromc⁰, and an elementy incident withl, different from u, at distance n−1 from c⁰ but not from c. Soδ(x, c⁰) =n−3 =δ(y, c) and proj_xc⁰ 6=l 6= proj_yc. But from this follows that, for an arbitrary element l⁰ incident with u, l 6= l⁰ 6= proj_ua, we have Tl⁰ ⊆ Γn−1(c), a contradiction. This proves the claims (i), (ii) and (iii).

For two points a, b, let C_a,b be the set containing a, b, and all points c for which there exists a point c⁰ such that {c, c⁰} ∈ Oa,b. Now let S be the set of pairs of points (a, b), δ(a, b)6=n−1, for which there does not exist an element at distancen−1 from all the points of C_a,b. We claim that S contains exactly the pairs of points (a, b) for which δ(a, b) = 2 or δ(a, b) = 4.

First assumeδ(a, b) = 2. Let by way of contradiction w be an element at distance n−1 from all points ofC_a,b. Since all the points of the lineabare contained inC_a,b,wlies opposite ab. If v is an arbitrary point on ab, different from a and from b, then the element on [v, w]

that is collinear withv, is contained inC_a,b, but lies at distancen−3 fromw, a contradiction.

Suppose nowδ(a, b) = 4. Let by way of contradictionwbe an element at distancen−1 from all points ofC_a,b. Then w lies at distance n−1 from all the points collinear with m=a1b, which is not possible. Finally suppose 4< δ(a, b) =k 6=n−1. Let a⁰ be the element on the path [a, b] at distance k/2−1 froma, and xan element at distance (n−1)−(k/2−1) from w with proj_a0a 6= proj_a0w 6= proj_a0b. Then w lies at distance n−1 from all points of C_a,b. Our claim is proved.

Now let S⁰ be the subset ofS containing all the pairs (a, b) with the property that there exist points x and x⁰ belonging to C_a,b such that (x, x⁰) 6∈ S. Then S⁰ contains exactly the pairs of collinear points. Indeed, if δ(a, b) = 2, we can find pointsxand x⁰ inC_a,bat distance 6 from each other, while if δ(a, b) = 4, then C_a,b ⊆ Γ₂(m). This completes the proof of the case i=n−1.

2.7. Case i = n/2

Let a and b be two points at distance k, and m an element at distance k/2 from both a and b. Then it is easy to see that, if k 6= n, an arbitrary element x ∈ T_a,b lies at distance n/2−k/2 from m such that proj_ma 6= proj_mc 6= proj_mb. Now we define the set S_a,b as the set of points c, a 6=c6=b, for which T_a,b ⊆Γ_n/2(c). Suppose first i is odd, and s6= 2. Let S