The Szemer´edi-Trotter Theorem in the Complex Plane Csaba D. T´oth [email protected] 5 Abstract 0 0 2 This paper generalizes the Szemer´edi-Trotter theorem to the complex plane. Szemer´edi and Trotter proved that the number of point-line incidences of n points y a and e lines in the real Euclidean plane is O(n2/3e2/3 +n+e), and this bound is M tight. We extend themethods of Szemer´edi and Trotter and prove that the number of point-line incidences of n points and e complex lines in the complex plane 2 is 3 C O(n2/3e2/3+n+e), which is tight, too. ] O C 1 Introduction and Applications . h t a Szemer´edi and Trotter — settling a conjecture of Erd˝os — determined the maximal order m of magnitude of the number of incidences between n points and e straight lines of the [ Euclidean plane [15]. Their result has innumerable applications and several generaliza- 3 tions, e.g., to pseudo-lines [2] and families of curves of degree r of freedom [11]. The v importance of the Szemer´edi-Trotter theorem is also shown by the fact that two com- 3 8 pletely different methods (or, rather, theories) have been developed for demonstrating 2 their bound and proving wide-spread generalizations since the publication of the original 5 0 result. A probabilistic “cutting plane” approach can be found in [2], while the “crossing 3 number method” in [11] and [14]. The latter is usually considered “the” proof of the 0 / Szemer´edi-Trotter bound. h t Extending some applications to a more general setting requires a similar bound for a m complex points and lines (see some examples below). Unfortunately, all three existing proofsrely heavily upon the topologyof the real Euclidean plane and no natural complex : v or multidimensional counterparts have been found so far. The goal of this paper is to i X prove such aboundandshow some applications. Our mainresult isformulated asfollows. r a Theorem 1. There exists an absolute constant C such that, for any n points and e complex lines in the complex plane 2, the number of incidences of points and lines is at C most Cn2/3e2/3 +3n+3e. An equivalent formulation of the Szemer´edi-Trotter theorem gives an upper bound on the number of lines containing at least t, 2 t n, points in the plane. Since the ≤ ≤ equivalence of the two formulations is solely combinatorial and does not depend on the underlying space (see [15] for a proof), it generalizes as well to the complex plane: 1 Theorem 2. For n point in the complex place 2, and any natural number 2 t n, C ≤ ≤ the number of complex lines incident to at least t points is n2 n O + . t3 t (cid:18) (cid:19) Theorem 1 (and also Theorem 2) is asymptotically tight: For every e and n, there exists a system of complex points and lines with at least Ω(n2/3e2/3 +n+e) incidences. Erd˝os [10] showed that the Szemer´edi-Trotter bound is tight, and there are n points and e lines in 2 with Ω(n2/3e2/3 +n+e) incidences. Every point (a,b) 2 and every line R ∈ R y = cx+d, (c,d) 2, in this construction can be interpreted as a point (a,b) 2 and ∈ R ∈ C a complex line y = cx+d, (c,d) 2, with the same incidence structure. ∈ C The proof of Theorem 1 canbe foundin Sections 2–5. In the remainder ofthis section, we present three immediate consequences of Theorem 1. All three results generalize theorems on plane geometry and their proof is based on the Szemer´edi-Trotter bound. Sinceeachofthemuses purelycombinatorialargumentsapartfromtheSzemer´edi-Trotter bound, they generalize to the complex plane with the same combinatorial proof and our Theorem 1. The first result is the generalization of a theorem due to Beck [1]. Corollary 1. There exists an absolute constant c > 0 such that, for any n points in the 1 complex plane, at least one of the following two statements holds true there are at least c n2 complex lines incident to at least two points, 1 • there is a complex line incident to at least n/100 points. • The next result is about sum sets and product sets. Given a set A , we denote ⊂ C by A + A and A A the set of all pairwise sums and products, respectively, formed by · elements of A. Elekes [4] proved that if A then max A + A , A A = Ω(n5/4). ⊂ R {| | | · |} This was recently improved to Ω(n14/11) by Solymosi [13]. We show the following. Corollary 2. There is an absolute constant c such that, for any set A 0 of n 2 ⊂ C−{ } elements, c n14/11 max A+A , A A . 2 · ≤ {| | | · |} Our last result is about point sets in 2. It generalizes a theorem of Elekes [5] from R homothetic subsets to similar ones. For two point sets A,B 2, we put ⊂ R S(A,B) = A 2 : A B,A A , ′ ′ ′ |{ ⊂ R ⊂ ∼ }| where A A means that A and A are similar to each other (i.e., they are equivalent ′ ′ ∼ under a sequence of translation, rotation, and scaling). The maximal number of similar copies of a configuration of t points in a set of n points in 2 is denoted by s(t,n) = R max S(A,B) : A = t, B = n . { | | | | } Corollary 3. There is an absolute constant c , such that 3 c n2 2 s(t,n) . ≤ t 2 2 Outline of the proof Our proof follows, in some sense, the arguments of Szemer´edi and Trotter. It has the same schematic structure: (i) The proof will be by contradiction; (ii) we consider a minimal counterexample (i.e., for which n+e is minimal) and show that it must contain a rather regular substructure of points and lines (see our Separation Lemma in Section 3); (iii) we state and prove an elaborate version of the Covering Lemma of Szemer´edi and Trotter [16] (our Covering Lemma in Section 4); (iv) the contradiction follows froma lower boundon the number of intersecting (cross- ing) pairs of lines in the minimal counterexample (Section 5–5.1). There are several principal differences, however, compared to the original Szemer´edi- Trotter proof. They cover a constant portion of the points by squares but it is not easy to find the appropriate cover in 2. They make use of the simple but crucial fact C that if a square is dissected into four parts by its diagonals then, for any two points in one quadrant, if we build a square on these points as two opposite corners, a suitable neighborhood of at least one of the other corner points will lie inside the original square. Unfortunately, the natural four-dimensional idea of covering by hypercubes does not have this property. That is why we need a much more involved covering lemma in the four (real) dimensional space 4. R Similar difficulties arise if we want to find appropriate regular structures, like those in our Separation Lemma. Szemer´edi and Trotter used the space of directions of lines of the Euclidean plane and find a linear transformation that produces two almost orthogonal families of lines. Unfortunately again, the space of directions of complex lines is two- dimensional, and thus much more difficult to handle. AnaturalgeneralizationoftheSzemer´edi-Trotter theorem(andourTheorem1)would beanupperboundonthenumber ofincidences ofpointsandd-flatsinthe2d-dimensional real Euclidean space. Conjecture 3. We are given n points and e d-flats (d-dimensional affine subspaces) in 2d such that any two subspaces intersect in at most one point. The number of incidences R of points and d-flats is O(n2/3e2/3 +n+e). For d = 1, this is equivalent to the Szemer´edi-Trotter theorem. Our Theorem 1 is a special case for d = 2 where all 2-flats correspond to complex lines in 2. Our proof C technique does not establish Conjecture 3 for d = 2 because the Separation Lemma (our Lemma 4) does not seem to extend for arbitrary 2-flats in 2d. We exploit the R geometryofthecomplexplaneonlyinSubsection 3.3,theproofoftheSeparationLemma. Subsections 3.1 and 3.2 use purely combinatorial arguments, and then Sections 4 and 5 rely exclusively on real Euclidean geometry and real linear transformations, and we treat complex lines of 2 as 2-flats of 4. C R In the next subsection we summarize some basic properties of complex lines in the complex plane, which are used in Subsection 3.3. We also point out why this approach does not seem to extend to 2-flats in 4. R 3 2.1 Grassmannian manifolds Besides the space of complex lines in 2, we consider the space of directions of complex C lines, which we denote by H. The direction of a line y = ax + b (a,b ) is a ; ∈ˆC ∈ C the direction of a line x = c (c ) is . For a complex line ℓ, let ℓ H denote its direction, and similarly let Lˆ∈ CH de∞note the multiset of directions o∈f a set L of ⊆ complex lines. The space of directions H is called the Grassmannian manifold1 H(1,1) and it can be represented by the complex projective line 1 or the Riemann-sphere 2 CP S [7]. The (standard) correspondence between H and 2 is defined as follows: We identify S every complex direction a with a point (Re(a),Im(a),0) in the plane z = 0 of ∈ C 3, then a stereographic projection maps every point from the plane z = 0 to a sphere R x2 +y2+(z 1)2 = 1 in 3; and the direction is mapped to the point (0,0,1) of the − 2 4 R ∞ sphere. Notice that a main circle H of the sphere corresponds to the circle of unit slope 0 directions, that is, to directions of the lines y = ax with a and a = 1 [7]. ∈ C | | H(1,1) has an essentially unique invariant metric (invariant to unitary transforma- tions). The distance dist(ℓˆ,ℓˆ) between directions of two complex lines ℓ and ℓ in 2 1 2 1 2 C can be defined in terms of their principal angle arccos(max uv : u ℓ , v ℓ , u = 1 2 { | | ∈ | | ∈ | | v = 1 ), which is equivalent to the chordal distance in the Riemann-sphere representa- | | } tion [6, 17]. In this paper, we always use the chordal metrics of 2 measured in degrees. S For example, if two directions a and a are orthogonal, (i.e., a a = 1 or a = 0 1 2 1 2 1 ∈ C · − and a = ), then they correspond to antipodal points in the sphere representation 2 ∞ H(1,1) = 2, hence dist(a ,a ) = 180 . 1 2 ◦ S The identification τ : 2 4, (z ,z ) (Re(z ),Im(z ),Re(z ,),Im(z )) maps 1 2 1 1 2 2 C → R → complex lines to 2-flats of 4. In particular, τˆ = τ maps the space of complex H(1,1) R | 1-subspaces H = H(1,1) to the Grassmannian manifold Gr(2,2) of 2-subspaces in 4. R Gr(2,2) has several different invariant metrics (invariant to orthogonal transformations). Allmetricscanbedefinedintermsofthetwoprincipleanglesbetweentwo2-subspaces[7]. We consider the distance between the directions of two 2-flats in 4 to be the sum R of their principle angles. In this way, the distance of two orthogonal 2-subspaces is 2 90 = 180 . A simple consequence of this notation is that τˆ maps a small neighborhood ◦ ◦ · ˆ ˆ of an ℓ H(1,1) into a subset of a neighborhood of τˆ(ℓ) Gr(2,2). Specifically, we will ∈ ∈ use later that τˆ maps a 1 -neighborhood in H(1,1) to a subset of a 10 -neighborhood in ◦ ◦ Gr(2,2). Note that the group of non-degenerate complex linear transformations GL(2, ) acts C on 2 and preserves the point-line incidences. Therefore we use freely these transforma- C tions on the complex plane. GL(2, ) also acts on the space of its 1-subspaces H(1,1). C We use one more property of the space of complex directions in the proof of our Separation Lemma: Two sufficiently small disjoint disks in H(1,1) can be mapped into two small neighborhoods around two orthogonal directions by a nondegenerate linear transformation if the disks are at least a constant (say, 5 ) distance apart. Gr(2,2) does ◦ not have this property: Two disjoint disks in Gr(2,2) may contain 2-subspaces incident to a common line, hence no linear transformation can increase their distance above 90 . ◦ This is why the proof technique of Szemer´edi and Trotter does not apply to 2-flats in 4. R 1 1 Forcompleteness,H(1,1)=SU(2)/S(U(1) U(1))whereU(1)= andSU(2)standsforthespace × S of special unitary two-by-two matrices. 4 3 Separation Lemma Our first main lemma (Separation Lemma) is a straightforward generalization of Sze- mer´edi and Trotter’s result in the plane. It claims that a hypothetic counterexample to Theorem 1 contains a fairly regular (grid-like) sub-structure of points and complex lines. Let (P,E) be a system of a point set P and a line set E in the complex plane. Let n = P | | and e = E denote the number of points and lines, respectively, and let I = I denote P,E | | the number of point-line incidences. A system (P,E) is critical system if e+n is minimal among all systems where I > max(Cn2/3e2/3,3n,3e) with constant C = 1070. Lemma 4. (Separation Lemma) In a critical system (P,E), there is a point set O P ⊆ and two line sets L ,L E such that for the constant M = 1010 1 2 ⊂ (a) O n/M8; | | ≥ (b) every point p O is incident to at least I/(nM3) lines from both L and L ; 1 2 ∈ ˆ ˆ (c) there are two orthogonal directions ℓ ,ℓ H(1,1), such that the directions of the 1 2 ∈ ˆ ˆ lines of L and L are in the 1 -neighborhood of ℓ and ℓ , resp., after a non-degenerate 1 2 ◦ 1 2 complex linear transformation of 2. C 3.1 Preliminaries Consider a critical system (P,E) of n points and e lines in 2. First we show that in C this hypothetic system, n and e cannot be extremely far from each other, more precisely, either of them is much larger than the square root of the other. Lemma 5. In a critical system (P,E), we have C3 C3 e > √n, and n > √e. (1) 33/2 33/2 Proof. By symmetry, it suffices to prove the first inequality. Let d denote the number of p complex lines incident to the point p P. By the inequality of quadratic and arithmetic ∈ means, we have 2 e d d2 d 1 1 e2 > p = p p d d = p p 2 ≥ 2 2 − 2 ≥ 2n − 2 ! (cid:18) (cid:19) p P (cid:18) (cid:19) p P p P p P p P X∈ X∈ X∈ X∈ X∈ 1 1 1 1 I2 = I2 I > I2 I2 = , 2n − 2 2n − 6n 3n where the last step follows from I > 3n. Therefore, by I > Cn2/3e2/3, we have C2 e2 > n1/3e4/3, 3 whence the desired inequality. Corollary 4. 3 3 3 3 e = e1/3e2/3 < n2/3e2/3 < I and n = n1/3n2/3 < n2/3e2/3 < I. C2 C3 C2 C3 5 Corollary 5. In a critical system (P,E), we have max(Cn2/3e2/3,3n,3e) = Cn2/3e2/3. Our next goal is to show that every point is incident to a large number of lines. For a set F of complex lines and a point p 2, we denote by Fp the subset of lines from F ∈ C incident to p. Let d = I/n denote the average degree of a point and let let f = I/e A A denote the average degree of a line in (P,E). We show that the degree of every point in P is at least half of the average. Lemma 6. In a critical system (P,E), every p P is incident to at least d /2 lines of A ∈ E (i.e, Ep d /2) and every e E is incident to at least f /2 points of P. A A | | ≥ ∈ Proof. By symmetry, it is enough to prove Ep d /2. We suppose, by contradiction, A | | ≥ that there exists a point p P incident to less than d /2 lines from E. A ∈ Since the system (P p ,E) is smaller than the critical system (P,E), we have − { } I max(C(n 1)2/3e2/3,3(n 1),3e). This, together with Corollary 4, implies an P p ,E −{ } ≤ − − upper bound on the total number of incidences in the system (P,E). 2/3 d 1 n 1 10 I < A +max(C(n 1)2/3e2/3,3(n 1),3e) < I +max − , I, 2 − − 2n · n C3 · ! (cid:18) (cid:19) 2/3 1 n 1 10 1 < +max − , . 2n n C3 ! (cid:18) (cid:19) The last inequality is equivalent to either 4n2 2n 1 0 or n 1/(2 (1 10/C3)) − − ≤ ≤ · − depending on the value in the maximum. In either case, the inequality has no integer solution: A contradiction. 3.2 Distinguishing two line sets Denote by H the space 1 = H(1,1) = 2 of directions of complex lines. The direction CP S of a line y = ax + b (a,b ) is a , the direction of a line x = c (c ) is . ∈ C ∈ C ∈ C ∞ We represent H as the sphere 2, where a main circle H corresponds to the unit slope 0 S directions (cf., Subsection 2.1). Let us denote the two closed hemispheres on the two sides of H by H and H . We may assume (after a non-degenerate linear transformation 0 1 2 of 2) that ℓˆ H : ℓ E e/2, ℓˆ H : ℓ E e/2, and there is at most one 1 2 C |{ ∩ ∈ }| ≥ |{ ∩ ∈ }| ≥ class of parallel lines whose direction lies on H . 0 ˆ ˆ Definition 1. Let E ℓ E : ℓ H and E ℓ E : ℓ H such that 1 1 2 2 ⊂ { ∈ ∈ } ⊂ { ∈ ∈ } E = e/2 and E = e/2 . 1 2 | | ⌊ ⌋ | | ⌈ ⌉ Note that lines from a class of parallel lines whose direction corresponds to a point in H may be in either E or E . 0 1 2 Definition 2. Let P = p P : Ep d /100 and Ep d /100 be the set of points 0 { ∈ | 1| ≥ A | 2| ≥ A } incident to at least d /100 lines from both E and E . We split the points of P P into A 1 2 0 \ two subsets, let P = p P P : Ep > Ep and let P = p P P : Ep Ep . 1 { ∈ \ 0 | 1| | 2|} 2 { ∈ \ 0 | 1| ≤ | 2|} Lemma 7. In a critical system (P,E), we have P n/10. 0 | | ≥ 6 Proof. Let P = x n and let I denote the number of incidences of the system (P ,E), j j j j | | that is, the number of incidences of P and all lines of E, for j = 0,1,2. Suppose, by j contradiction, that x < 0.1. 0 The systems (P ,E), (P ,E ), and (P ,E ) are all smaller than the critical system 0 1 1 2 2 (P,E). This implies that the bound of Theorem 1 holds for each of these three systems. Takingintoaccounttheincidencesofthesystems(P ,E )and(P ,E ),aswell, weobtain: 1 2 2 1 I < C(x n)2/3e2/3 +3x n+3e 0 0 0 I < C(x n)2/3 e/2 2/3 +3x n+3 e/2 +(x n)(d /100) 1 1 1 1 A ⌊ ⌋ ⌊ ⌋ I < C(x n)2/3 e/2 2/3 +3x n+3 e/2 +(x n)(d /100). 2 2 2 2 A ⌈ ⌉ ⌈ ⌉ We estimate e/2 by using e > C2 from Lemma 5, and so e/2 C2+1e. We have ⌈ ⌉ ⌈ ⌉ ≤ C2 2 2 C2 +1e 2/3 (x +x )nd I = I < x2/3Cn2/3e2/3 +(x2/3 +x2/3)Cn2/3 + 1 2 A +3n+6e. j 0 1 2 C2 2 100 j=0 (cid:18) (cid:19) X Applying x2/3 +x2/3 2 x1+x2 2/3 = 2 1 x0 2/3, we obtain 1 2 ≤ 2 −2 2 (1 x )2/3 C2 +1 (1 x ) 2/3 (cid:0) 0(cid:1) (cid:0) (cid:1) 0 I = I < x + − + − I +6(n+e). j 0 21/3 · C2 100 j=0 (cid:18) (cid:19) X By Corollary 4, we deduce that (1 x )1/3 (C2 +1) 1 x 36 2/3 0 0 1 < x + − + − + . 0 21/3 · C2 100 C3 This inequality has no roots in the interval [0,0.1], (the smallest root is approximately 0.108). This proves that x > 0.1. 0 3.3 Separation of two line sets Let Ψ G( ,2) denote the set of non-degenerate linear transformations of 2 that act ⊂ C C as an automorphism on each of H , H H , and H H . Relying on the definitions 0 1 0 2 0 \ \ of E , E , P , and Ψ, we formulate a lemma that immediately implies the Separation 1 2 0 Lemma. Lemma 8. There exists a point set O P of size at least n/M8 and two line sets 0 ⊆ L E and L E such that for every point p O, p is incident to at least d /M3 1 1 2 2 A ⊆ ⊆ ∈ lines from L and from L , respectively, and the directions of the lines of L and L are 1 2 1 2 in the 1 neighborhood of two orthogonal directions of H after a transformation ψ Ψ. ◦ ∈ We prove Lemma 8 in the end of this section after several small steps. One difficulty in finding sets L and L is that the boundary of the two hemispheres H and H is a 1 2 1 2 one-dimensional manifold: It is possible that for every point p P , the directions of 0 ∈ most of the incident lines are very close the boundary H . This undesirable property of 0 a point p P is captured in Definition 3 below. ∈ Definition 3. Consider a direction a H . A point p P is called an N(a)-point, if 0 ∈ ∈ the directions of at least Ep dA lines of Ep and at least Ep dA lines of Ep lie | 1|− 200 M 1 | 2|− 200 M 2 in the open disk in H with radius 10 and center at a. ◦ Lemma 9. There is a set P P of at least n/M6 points and a transformation ψ Ψ 1 0 ⊆ ∈ such that no point of O is a N(a)-point for any a H after applying ψ to 2. 0 ∈ C 7 For the proof of Lemma 9, we initiate a recursive algorithm. Put O = P , n = O , 0 0 0 0 ˆ ˆ | | and U = ℓ E : ℓ H , V = ℓ E : ℓ H . We obtain U (reps., V ) from E 0 1 0 0 2 0 0 0 1 { ∈ 6∈ } { ∈ 6∈ } (resp., E ) by deleting at most one class of parallel lines, that is, lines whose direction 2 lies in H . Every p O is incident to at least d /100 1 d /200 lines of U and at 0 0 A A 0 ∈ − ≥ least d /100 1 d /200 lines of V . Setting j = 0, the system (O ,V U ) satisfies A A 0 j j j − ≥ ∪ the following four properties. Invariant (Sparse). We have O P , U E , and V E such that j 0 j 1 j 2 ⊆ ⊆ ⊆ 1. O n , where n = (1 3 )j(1)j n; | j| ≥ j j − M 3 10 2. Uˆ H and Vˆ H ; j 1 j 2 ⊂ ⊂ 3. U V e , where e = e ; | j ∪ j| ≤ j j 2j 4. for every p O , we have Up t and Vp t , where t = dA(1 j ). ∈ j | j| ≥ j | j | ≥ j j 200 − M The following lemma provides an induction on the systems (O ,U V ) under certain j j j ∪ condition. (Notice that Lemma 9 follows immediately if this condition is not satisfied and n n/M5.) j ≥ Lemma 10. If a system (O ,V U ), j , satisfies the Sparse Invariant but there is j j j ∪ ∈ N no ψ Ψ such that after applying ψ at least n /M points are not N(a)-points for any j ∈ a H , then there are sets O O , V V , and U U satisfying the Sparse 0 j+1 j j+1 j j+1 j ∈ ⊆ ⊂ ⊂ Invariant. In order to prove Lemma 10, we define a few more concepts and determine a trans- formation ψ Ψ in Lemma 11 below. We partition the circle H into three arcs: A half 0 ∈ circle A = [i, i], and two quarter circles A = [ i, 1], and A = [ 1,i] (see Figure 1). 1 2 3 − − − − We define two new properties for every point p O with respect to an arc A H . j 0 ∈ ⊂ A point p O is an N(A)-point, if it is an N(a) point for an a H and a j 0 ∈ ∈ is in the 10 -neighborhood of the arc A H . ◦ 0 ⊂ Let γ : H 0, H be the projection to H along main halfcircles 0 0 \ { ∞} → incident to 0 H and H. A point p O is a Γ(A)-point, if the j ∈ ∞ ∈ ∈ projection of the direction of at least 1 Ep lines of Ep are in A. 3| | Let N(A) and Γ(A) denote the number of N(A)-points and Γ(A)-points in the | | | | system (O ,U V ). Since H = A A A , every point p O is a Γ(A )-point for j j j 0 1 2 2 j k ∪ ∪ ∪ ∈ at least one of k = 1,2,3. Lemma 11. Consider a system (O ,U V ) satisfying the Sparse Invariants. There is j j j a transformation ψ Ψ which assures Γ∪(A ) nj simultaneously for k = 1,2,3. ∈ | k | ≥ 3 For every λ , 0 λ < 1, we define the transformation ∈ R ≤ 1 1 λ z π1 : 2 2, (z ,z ) 1 . λ C −→ C 1 2 −→ √1 λ2 · λ 1 z2 − (cid:18) (cid:19)(cid:18) (cid:19) For every vector (z ,z ) 2, the transformation π1 scales the component parallel to 1 2 ∈ C λ (1,1) 2 by 1+λ and the perpendicular component by 1 λ . Note that − ∈ C 1 λ ∈ R 1+λ ∈ R − q q 8 ∞ A2 i f2 10 H ◦ 1 A2 i A − 3 1 H − 0 10 1 ◦ H i 0 A − 1 A 1 A 3 0 i 10◦ − Figure 1: A , A , and A . 1 2 3 π1 Ψ because a vector (z ,z ) has unit slope (that is, z = z ) if and only if so does λ ∈ 1 2 | 1| | 2| π1((z ,z )). λ 1 2 For every a H , we define πa := ̺aπ1(̺a) 1, where ∈ 0 λ λ − 1 0 z ̺a : 2 2, (z ,z ) 1 . C −→ C 1 2 −→ 0 1/a z2 (cid:18) (cid:19)(cid:18) (cid:19) ̺a is a unary transformation (i.e., it is an isometry on the sphere H = 2) and ̺a Ψ. S ∈ Consider the orbit of elements of H under π1 for all 0 λ < 1. These orbits are the λ ≤ main halfcircles between 1 H and its antipodal 1 H. If we increase λ continuously ∈ − ∈ from 0 to 1 then the image of every point (except for 1 and its antipodal 1) will move − continuously toward 1 H along a main halfcircle. The directions of lines of V U will j j ∈ ∪ enter any small neighborhood of 1. Proof of Lemma 11. We build ψ as a combination of a π1 and a πi for some λ and λ κ κ. First we apply a π1 with a λ such that exactly n /3 points of O are Γ(A ) points. λ j j 1 Such a λ exists because every point of p O becomes a Γ(A )-point for a sufficiently j 1 ∈ big λ, 0 λ < 1. (As we increase λ continuously, possibly several points of O become j ≤ Γ(A )-points at the same time. We can model this event as if these points change their 1 status one by one.) In a second step, we apply a πi with appropriate 0 κ < 1. Note κ ≤ that for any 0 κ < 1, the transformation πi is an automorphism on the hemisphere ≤ κ γ 1(A ) and so the set of Γ(A ) points remains fixed. We can choose a κ, 0 κ < 1, − 1 1 ≤ such that the remaining 2n points are balanced between Γ(A ) and Γ(A ). 3 j 2 3 We are now ready to prove the iteration, Lemma 10. Proof of Lemma 10. Consider the system (O ,U V ) satisfying the Sparse Invariants. j j j ∪ Assume that after any transformation ψ Ψ, at least n (1 3/M) points of O are N(a)- j j ∈ − points for some a. We apply the transformation ψ Ψ provided by Lemma 11 such that ∈ 9 Γ(A ) nj for k = 1,2,3. Observe that if a Γ(A )-point is also an N(a)-point for some | k | ≥ 3 k a H then a must be in the 10 neighborhood of arc A and so p is an N(A )-point. 0 ◦ k k Th∈is implies that N(A ) (1 3 )nj for k = 1,2,3. | k | ≥ − M 3 Consider the embedding of H into a unit sphere of the Euclidean three-space centered at the origin (H = 2 3). For every a H, let f(a) be the plane in 3 whose S ⊂ R ∈ R normal vector is parallel to the 3-embedding of a and that partitions the multiset of (the 3-embeddings of) the direRctions Vˆ Uˆ into two equal parts. If a is in generic j j R ∪ position, then f(a) passes through the embeddings of at most one direction of Vˆ Uˆ . j j ∪ Let a ,a ,a H be three generic points at or in the very small neighborhood of the 1 2 3 0 ∈ midpoints of the arcs A , A , and A (that is, the directions 1 H , ( 1+i)/√2 H , 1 2 3 0 0 ∈ − ∈ and ( 1 i)/√2 H ), respectively. As a shorthand notation, let f = f(a ),f = f(a ), 0 1 1 2 2 − − ∈ and f = f(a ). 3 3 Along with the partition H = A A A , we define another partition H = 0 1 2 3 0 ∪ ∪ B B B , such that for every k = 1,2,3, A B = and the endpoints of B are the 1 2 3 k k k ∪ ∪ ∩ ∅ centers of A and A . More specifically, B = [ 1+i, 1 i], B = [ 1 i,1], k+1 mod3 k+2 mod3 1 −√2 −√−2 2 −√−2 and B = [1, 1+i]. We can now define the sets O , U , and V as follows. 3 −√2 j+1 j+1 j+1 - If there is a k 1,2,3 such that f does not intersect the 10 -neighborhood of k ◦ ∈ { } A (see Figure 1, right, for k = 2), then let O = p O : p is N(A )-point . k j+1 j k { ∈ } Let U (resp., V ) be the set of lines from U (resp., V ) whose direction are j+1 j+1 j j embedded in 3 on the same side of the plane f as A . k k R - If f intersects the 10 -neighborhood of A for every k 1,2,3 , then consider the k ◦ k ∈ { } arc B for m 1,2,3 where N(B ) is maximal. Let O = p O : p is an m m j+1 j ∈ { } | | { ∈ N(B )-point . Let U (resp., V ) be the set of lines from U (resp., V ) whose m j+1 j+1 j j } directions are embedded in 3 on the same side of the plane f as B . m m R It is easy to check that O , U , and V satisfy all four Sparse Invariants. j+1 j+1 j+1 Proof of Lemma 9. Wemay suppose without loss of generality that U V . We count j j | | ≥ | | the number I of incidences of the system (O ,U ). On one hand, every point is incident j j j to at least t lines and so I n t . On the other hand, the system (O ,U ) is smaller j j j j j j ≥ than the critical system (P,E) and so the Szemer´edi-Trotter bound applies. 2/3 2/3 n t I Cn e +3n +3e . (2) j j ≤ j ≤ j j j j Assuming M = 1010 and j 100, we have (1 j/M) 4/5 and 1/4 (1 3/M)j < 1. ≤ − ≥ ≤ − We can bound each term in Inequality (2) as follows: j j j 3 1 n d j 1 1 A n t = 1 1 I, j j − M 3 10 · 200 − M ≥ 104 3 (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19) 2j/3 2j/3 2j/3 j 3 1 n 2/3 1 1 Cn2/3e2/3 = C 1 e2/3 I j j − M 3 10 · 2 ≤ 62/3 (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19) (cid:16) (cid:17) j j j 3 1 n 1 I n = 1 j − M 3 10 ≤ 3 C3 (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19) j e 1 I e = j 2j ≤ 2 C3 (cid:18) (cid:19) 10