Approximation algorithms for Max-3-Cut and other problems via complex semidefinite programmingMichel X. GoemansMIT 77 Mass. Ave., Room 2-351 Cambridge, MA 02139David P. WilliamsonIBM Almaden 650 Harry Rd., K53/B1 San Jose, CA 95120goemans@ ABSTRACTdpw@ 1. INTRODUCTIONA number of recent papers on approximation algorithms have used the square roots of unity, ?1 and 1 to represent binary decision variables for problems in combinatorial optimization, and have relaxed these to unit vectors in real space using semide nite programming in order to obtain near optimal solutions to these problems. In this paper, we consider using the cube roots of unity, 1, ei2 =3 , and ei4 =3 , to represent ternary decision variables for problems in combinatorial optimization. Here the natural relaxation is that of unit vectors in complex space. We use an extension of semide nite programming to complex space to solve the natural relaxation, and use a natural extension of the random hyperplane technique introduced by the authors in 8] to obtain near-optimal solutions to the problems. In particular, we consider the problem of maximizing the total weight of satis ed equations xu ? xv c (mod 3) and inequations xu ? xv 6 c (mod 3), where xu 2 f0; 1; 2g for all u. This problem can be used to model the Max-3-Cut problem and a directed variant we call Max-3-Dicut. For the general problem, we obtain a .79373-approximation algorithm. If the instance contains only inequations (as it does for Max-3-Cut), we obtain a performance guarantee 7 of 12 + 4 32 arccos2 (?1=4) :83601. This compares with proven performance guarantees of .800217 for Max-3-Cut (by Frieze and Jerrum 7]) and 1 + 10?8 for the general 3 problem (by Andersson, Engebretson, and Hastad 2]). It matches the guarantee of .836008 for Max-3-Cut found independently by de Klerk, Pasechnik, and Warners 4]. We show that all these algorithms are in fact identical in the case of Max-3-Cut./cs/people/dpwA current version of the paper can be found at .Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. STOC’01, July 6-8, 2001, Hersonissos, Crete, Greece. Copyright 2001 ACM 1-58113-349-9/01/0007 ... 5.00.$The uses of linear programming for designing algorithms for combinatorial optimization problems has long been known. Since the seminal paper of Lovasz 13], researchers have investigated the use of nonlinear programming, particularly semide nite programming, since semide nite programs can be solved in polynomial time (up to any prescribed accuracy). At rst it was shown that semide nite programs could be solved via the ellipsoid method 9, 10]; later it was shown that practical interior-point methods for linear programs could be adapted to semide nite programming 1, 15]. One particular use of semide nite programming that has received a good deal of attention is its application to approximation algorithms. An -approximation algorithm is a polynomial-time algorithm for a combinatorial optimization problem that produces a solution of value with a factor of of the optimal value. In 8], the authors introduced the following technique. An optimization problem with binary decisions (e.g. MAX CUT, MAX 2SAT) is modelled with n variables xi 2 f?1; +1g, and an objective function quadratic in these variables. These variables xi are relaxed to n-dimensional unit length vectors vi , and their products xi xj to inner products hvi ; vj i. It is not di cult to show that this relaxation is a semide nite program, and thus can be solved in polynomial time, up to any given accuracy. The solution to the relaxation is mapped to the solution in the original variables by choosing a random vector r from the ndimensional normal distribution, and deriving the solution xi = sgn(hr; vi i). The expected value of this solution can be compared to the value of the relaxation. This technique has been applied, with modi cations, to several other problems in combinatorial optimization (e.g. 2, 3, 6, 7, 12, 14, 21, 23]). In the meantime, researchers in mathematical programming have shown that the interior-point methods that extend polynomial-time solvability from linear programming to semide nite programming also extend polynomial-time solvability to the class of symmetric cones. This includes the second-order cone (also called the ice-cream cone), the cone of semide nite matrices over real numbers/complex numbers/quaternions, and the cone of 3 3 semide nite matrices over octonions. Toh and Trefethen showed that semide nite programming over the complex domain is solvable in polynomial time 22]. Guler 11] showed that theself-scaled cones for which Nesterov and Todd 16, 17] had provided polynomial-time algorithms are exactly the symmetric cones. We propose to take advantage of these developments by using semide nite programming over the complex domain; we call this complex semide nite programming (CSDP). Previously we modelled binary decisions with the square roots of unity 1; we now model ternary decisions with the cube roots of unity 1, ei2 =3 , and ei4 =3 . Given a model of this problem with an objective function quadratic in these variables, we relax these variables to unit length vectors vi 2 C n , where C n is n-dimensional complex space, and relax their products xi xj to inner products hvi ; vj i. This relaxation turns out to be a semide nite program over the complex domain, and is solvable in polynomial time. We extend our randomized rounding technique by drawing a random vector r from the n-dimensional complex normal distribution, then mapping back to the original space by considering the angle of the inner product sei = hr; vi i. We apply these ideas to the problem of maximizing the weight of satis ed two variable equations or inequations mod 3. In particular, in the problem Max 2-Lin-Mod-3 we have n variables xi and m equations xi ? xj c (mod 3) or inequations xi ? xj 6 c (mod 3). For each (in)equation j we are given a nonnegative weight wj , and we must nd values of the xi 2 f0; 1; 2g that maximize the total weight of the satis ed (in)equations. The problem Max 2-Lin-Mod3 can be used to model other optimization problems. We give two examples here, Max-3-Cut and Max-3-Dicut. In Max-3-Cut, we are given a graph G = (V; E ) with a weight we on edge e 2 E . We assume that the weights are nonnegative. For a partition of V into 3 sets V0 , V1 and V2 , we let (V0 ; V1 ; V2 ) = fe = (u; v) 2 E : u 2 Vi ; v 2 Vj for i 6= j g. The goal is to nd a 3-partition (V0 ; V1 ; V2 ) such that w( (V0 ; V1 ; V2 )) is maximized where w(F ) = Pe2F we . Max-3-Dicut is similarly de ned except that G is now a digraph and we would like to maximize w( + (V0 ; V1 ; V2 )) where + (V0 ; V1 ; V2 ) = fe = (u; v) 2 E : u 2 Vi ; v 2 Vj with j ? i 1 (mod 3)g: To model these two problems, we introduce a variable xv for each v 2 V . For the problem Max-3-Cut, we introduce an inequation xu ? xv 6 0 (mod 3) of weight we for each edge e = (u; v). For the problem Max-3-Dicut, we introduce an equation xv ? xu 1 (mod 3) of weight we for each directed edge e = (u; v). We obtain a :79373-approximation algorithm for the general problem Max 2-Lin-Mod-3, a :79373-approximation 7 algorithm for Max-3-Dicut, and a ( 12 + 4 32 arccos2 (?1=4))approximation algorithm for instances of Max 2-Lin-Mod3 that have inequations only, where 3 7 2 12 + 4 2 arccos (?1=4) :83601: This implies a :83601-approximation algorithm for Max-3Cut. Previously, Andersson, Engebretson, and Hastad 2] considered a more general variant of the problem Max 2Lin-Mod-p (for two-variable equations mod p) and shown 1 that they could obtain an ( p + (p))-approximation algorithm, where (p) > 0 is a constant that depends on p; for our simpler version, they gave a proven performance guar1 antee of p (1 + 10?8 ). Their algorithm is based on a (real)semide nite programming relaxation involving p vectors for each variable. In the conclusion of their manuscript, the authors claim numerical evidence for a bound of 1=1:27 :787 in the case p = 3. This is actually not surprising since we are able to show that our complex semide nite programming relaxation (for p = 3) and our rounding scheme are both equivalent to theirs; we can therefore prove that their performance guarantee is :79373. Frieze and Jerrum 7] gave a ( k?1 + (k))-approximation algorithm for the Max k-Cut k problem, and in particular a :800217-approximation algorithm for Max-3-Cut. In 7, pg. 74], the authors state that by computing further terms in their series expansion, they are able to obtain a bound of .832718 for Max-3-Cut. Frieze and Jerrum also use a (real) semide nite programming relaxation and we can show that in the case of Max-3-Cut, our complex relaxation and our rounding scheme is equivalent to theirs, and thus the performance guarantee of their algorithm is :83601. Independently, de Klerk, Pasechnik, and Warners 4] have shown that the performance guarantee of Frieze and Jerrum is .836008. In terms of negative results, Andersson et al. 2] have shown that no -approximation algorithm for Max 2-Lin-Mod-3 can have > 17=18 :944 unless P = NP . Our use of complex semide nite programming is in some sense purely a modelling decision, since complex semide nite programming is reducible to standard (real) semide nite programming. However, we think it makes for cleaner models, algorithms, and analysis than the equivalent models using standard semide nite programming. For instance, the performance guarantee of de Klerk et al. for Max-3-Cut is determined numerically, whereas our performance guarantee for Max-3-Cut is analytic. Also, we believe our model is somewhat cleaner. The modelling approach of Frieze and Jerrum 7] for Max-3-Cut of introducing a single 2dimensional vector for each vertex and then relaxing the dimension restriction does not immediately extend to the case of Max-3-Dicut since in the real case the inner product of two vectors commute. To handle the more general case (of Max-3-Dicut or Max 2-Lin-Mod-3), Andersson et al. 2] de ne three 2-dimensional vectors for each vertex. This is also the general approach taken by de Klerk et al. 4]. The approach described in this paper allows the use of a single complex number (1-dimensional vector) for each vertex or each variable, which is then relaxed to a higher-dimensional vector. The fundamental reason why we can easily formulate a non-symmetric problem (such as Max 2-Lin-Mod-3, in which xu ? xv 6 xv ? xu ) comes from the fact that the inner product of two complex vectors does not commute. Our paper is organized as follows. In Section 2, we review basic ideas of complex numbers and matrices, and introduce some notation we will be using. In Section 3, we introduce complex semide nite programming. Section 4 shows how we model the Max 2-Lin-Mod-3 problem in terms of the cube roots of unity, and how its relaxation is a complex semidefinite program. We also show there that our relaxation is equivalent to Frieze and Jerrum's relaxation in the case of Max-3-Cut. In Section 5 we introduce our algorithm and present its analysis. Section 6 contains a brief discussion of some of the complexity issues since almost all computations have to be carried out approximately. The appendix contains the proofs of equivalence between the various algorithms of Frieze and Jerrum 7], Andersson et al. 2], and de Klerk et al. 4] in the case of Max-3-Cut.For a complex number z = x + iy 2 C , we denote its real part x by Re z and its imaginary part y by Im z. For the polar representation z = rei = cos( ) + i sin( ), r is the modulus jzj and is the argument arg z. The complex conjugate of z = x + iy is denoted by z = x ? iy. Let R n n (resp. C n n ) denote the set of n n matrices over the eld R (resp. C ). We denote the transpose of a matrix M = mij ] (of any size, including of a vector) by M T = mji ] and its adjoint by M = M T = mji ]. We extend the operators Re and Im to complex matrices by letting Re M for M 2 C n n be the real matrix Re mij ] and Im M be the real matrix Im mij ], so that M = Re M + iIm M . A real matrix M 2 R n n is symmetric if M = M T and skew-symmetric if M = ?M T . A complex matrix M 2 C n n is Hermitian if M = M . We let Sn denote the set of symmetric n n real matrices and Hn the set of complex n n Hermitian matrices. Note that for M 2 Hn , Re M is symmetric and Im M is skew-symmetric. As an inner product over C n , we use hu; vi = v u. Recall that hv; ui = hu; vi. For any two matrices A; B 2 Hn , where A = (aij ) and B = (bij ), we let hA; B i be the (Frobenius) inner P product of the two matrices; that is, hA; B i = Tr(B A) = i;j bij aij (which is also Tr(BA) or Tr(AB ) since A; B 2 Hn ). Recall that for a Hermitian matrix M , we have that x Mx = hMx; xi is real for all x 2 C n , and all its eigenvalues are real. A Hermitian matrix M 2 Hn is said to be positive semidefinite if x Mx 0 for all x 2 C n . A Hermitian matrix is positive semide nite if and only if all of its eigenvalues are nonnegative. We denote a positive semide nite matrix M 2 Hn by M 0. A Hermitian matrix M = (mij ) 2 Hn is positive semide nite if and only if it can be expressed as M = V V for some V 2 Hn ; thus M is positive semide nite if and only if there exist vectors v1 ; : : : ; vn 2 C n such that mij = hvi ; vj i.3. COMPLEX SEMIDEFINITE PROGRAMMING2. PRELIMINARIESinite programs are also solvable in polynomial time (up to any given degree of accuracy). Additionally, several interiorpoint methods used to solve SDPs can be generalized to CSDPs 5, 19, 18]. For the purpose of our approximation algorithms, most of the computations have to be done approximately and this is discussed in Section 6. For combinatorial optimization problems, decisions which have two alternatives (such as, whether an edge/vertex is present, or whether a job precedes another) are generally formulated by introducing a binary variable x 2 f0; 1g, or possibly x 2 f?1; 1g. When there are three alternatives, we propose to introduce a complex variable x 2 C which takes as values the third roots of unity, 1, ei2 =3 and ei4 =3 . For simplicity of notation, we will denote ei2 =3 by ! and ei4 =3 by !2 (or !?1 ). We let R3 denote the set of cube roots of unity, then: R3 = f1; !; !2 g. To illustrate this principle, we consider the optimization problem Max 2-Lin-Mod-3. In Max 2-Lin-Mod-3, we are given n variables xu , and m equations xu ? xv c (mod 3) or inequations xu ? xv 6 c (mod 3), where c 2 f0; 1; 2g. The j th (in)equation is associated with a nonnegative weight wj 0. We must choose a setting of the variables xu to values in f0; 1; 2g in such a way that we maximize the total weight of satis ed (in)equations. As we showed in the introduction, Max 2-Lin-Mod-3 can be used to model other optimization problems, including Max-3-Cut and Max-3Dicut. To model Max 2-Lin-Mod-3, we introduce a variable yu for each variable xu . Each variable yu is constrained to belong to R3 . For any set of variables xu 2 f0; 1; 2g, we set yu = !xu . For yu ; yv 2 R3 , observe that hyu ; yv i can take only three values, namely the values in R3 . Furthermore, the equation xu ? xv c (mod 3) is satis ed if and only if hyu ; yv i = !c , and the inequation is satis ed if and only if hyu ; yv i 2 R3 n f!c g. Thus the contribution of the j th equation xu ? xv c (mod 3) to the objective function is 1 1 wj 3 + 1 !?c hyu ; yv i + 3 !c hyv ; yu i ; (1) 3 and the contribution of the j th inequation xu ?xv 6 c (mod 3) to the objective function is 2 wj 3 ? 1 !?c hyu ; yv i ? 1 !c hyv ; yu i : (2) 3 3 Instead of imposing that yu 2 R3 for every u, we relax it to: hyu ; yu i = 1, and hyu ; yv i + hyv ; yu i ?1 for every u; v and every 2 R3 . The last constraint says that hyu ; yv i belongs to the triangle with vertices R3 in the complex plane. The relaxation we have obtained can now be formulated as a complex semide nite program. Letting Y = hyu ; yv i] 2 Hn , we have the constraints hEuu ; Y i = 1 (3) for all u, and the constraints hAc ; Y i ?1 (4) uv4. FORMULATING Max2-Lin-Mod-3Just as linear programming can be generalized by semidefinite programming, semide nite programming over the reals can be generalized by semide nite programming over the complex domain. For lack of a better term, we will call this complex semide nite programming (CSDP). As in semidefinite programming, in CSDP we maximize or minimize a linear function over a square matrix Z 2 Hn subject to linear constraints on Z and the constraint that Z is positive semide nite. More formally, we maximize or minimize hC; Z i for an objective matrix C 2 Hn , subject to m linear constraints of the form hAi ; Z i bi or hAi ; Z i = bi or hAi ; Z i bi where Ai 2 Hn , and subject to Z 0, Z 2 Hn . In fact, CSDP is reducible to SDP, and thus is not a strict generalization of it. We omit the simple reduction for space reasons. The reduction is obtained by using the linear transformation T below that maps matrices in Hn to matrices in S2n : Re T (Z ) = Im Z ?ImZZ : Z Re The polynomial-time solvability of semide nite programs (up to any given degree of accuracy) and the reduction claimed above immediately implies that complex semidef-for every u; v and c = 0; 1; 2, where eu is the vector with zeroes everywhere except for a 1 in the uth component, Euu = eu eT , and Ac = !c eu eT + !?c ev eT . Similarly, the u uv v u objective function can be formulated as hC; Y i (5) where C 2 Hn , by appropriately combining (1) and (2) for each equation/inequation. Our discussion implies that if we solve (5) subject to (3), (4) and Y 0, Y 2 Hn , we obtain an upper bound on the optimum objective function value of Max 2-Lin-Mod-3. We would like to mention that if Y is feasible for the above complex semide nite programming relaxation then Y T is also feasible. This is because ! and !2 are both cube roots of unity. However, in general, the objective function value of Y and Y T are not equal. They will be equal in the special case in which every equation is of the form xi ? xj 0 (mod 3) and every inequation of the form xi ? xj 6 0 (mod 3). This includes the case of Max-3-Cut. If the objective function value is unchanged by replacing Y by Y T , it is also by replacing it with (Y + Y T )=2 which is a real matrix. This means that in this special case our complex semide nite programming relaxation simply reduces to a (real) semide nite programming relaxation. In the case of Max-3-Cut, the above argument shows that our relaxation is exactly identical to the relaxation considered by Frieze and Jerrum 7]. In the algorithm and in our analysis, we will however not take advantage of the fact that the optimum solution can be assumed to be real in the case of Max-3-Cut.5. THE ALGORITHM AND ITS ANALYSIS 5.1 The algorithm10.80.60.40.20 1 0.5 0 −0.5 −1 −0.5 0 0.5 1Figure 1: Probability of xu ? xv satis ed as a function of hyu ; yv i.0 (mod 3) beingWe can now describe the algorithm for Max 2-Lin-Mod3. For a given problem instance, we solve the associatedCSDP as described in the previous section in polynomial time (see Section 6 for a discussion of complexity issues), and obtain vectors yu for each u from the solution matrix Y in polynomial time by Cholesky decomposition (see also Section 6). We then pick a random vector p 2 C n from the complex normal distribution. This is equivalent to drawing each entry pk independently from the univariate complex normal distribution, which in turn is equivalent to drawing Re pk and Im pk independently from the univariate real normal distribution. We then consider the inner products hp; yu i for each u. We create a solution x to the Max 2-Lin-Mod3 instance by setting 8 0 if arghp; y i 2 0; 2 =3) < u xu = : 1 if arghp; yu i 2 2 =3; 4 =3) 2 if arghp; yu i 2 4 =3; 2 ):5.2 The analysisWe now turn to the analysis of the algorithm. As in 8], we rst analyze the probability that a given equation xu ? xv c (mod 3) or inequation xu ? xv 6 c (mod 3) is satis ed, solely given the inner product hyu ; yv i. We then compare this probability to the contribution made to the objective function for the given (in)equation, which also depends solely on the inner product hyu ; yv i. Since this inner product must belong to the triangle de ned by R3 in thecomplex plane (by the constraints of the CSDP), we nd the minimum of the ratio of probability to objective function contribution over the triangle R3 . Throughout this paper, arccos( ) has range in 0; ]. Theorem 1. If hyu ; yv i = re?i then the probability that the equation xu ? xv c (mod 3) is satis ed is 1 P = 3 + 83 2 2 arccos2 ?r cos 23 c + ? arccos2 ?r cos 2 (c3+ 1) + ? arccos2 ?r cos 2 (c3? 1) + : For example, if hyu ; yv i = 1 (r = 1, = 0) and c = 0, we 1 have P = 3 + 8 32 2 2 ? 92 ? 92 = 1, while for c = 1, 1 we have P = 3 + 8 32 2 92 ? 2 ? 92 = 0. If hyu ; yv i = 0, 1 1 we have P = 3 + 8 32 2 42 ? 42 ? 42 = 3 , as expected. Figure 5.2 shows the probability given in Theorem 1 over the entire range of values for hyu ; yv i. By simply complementing the probability in Theorem 1, we get Theorem 2. If hyu ; yv i = re?i then the probability that the equation xu ? xv 6 c (mod 3) is satis ed is P = 2 ? 83 2 2 arccos2 ?r cos 23 c + 3 ? arccos2 ?r cos 2 (c3+ 1) + ? arccos2 ?r cos 2 (c3? 1) + : In order to be able to derive a performance guarantee for the algorithm, we need to compare the probabilities in Theorems 1 and 2 with the corresponding contribution to the objective function of the relaxation, namely to (1) and (2) respectively. We are able to show the following guarantees, from which we can easily derive the existence of approximation algorithms with the performance guarantees claimed in the introduction.R3 thenTheorem 3. If hyu ; yv i belongs to the triangle de ned by1. the probability that xu ? xv c (mod 3) is satis ed is at least 0:79373 times ? 1 + 1 !?chy ; y i + 1 !chy ; y i , u v v u 3 3 3 2. the probability that xu ? xv 6 c (mod 3) is satis ed 7 3 is arccos2 ? ? 2 at 1leastchy ;+ i4 ?2 1 !chy ;(y 1=.4) 0:83601 times ? 12 yv ? 3! u v ui 3 3To prepare for the proof of Theorem 1, we rst need a few simplications. Consider the equation xu ? xv c (mod 3), and the vectors yu and yv .Claim 4. The probability that xu ? xv c (mod 3) is satis ed depends only on hyu ; yv i. In particular, given hyu ; yv i = re?i , one can choose without loss 2of generality yu = e1 and yv = (rei ; s; 0; ; 0) 2 C n with r + s2 = 1.1 , a uniformly distributed angle. Given , this implies that arghp; yv i = + 1 . If we add or subtract from arghp; yu i and arghp; yv i any multiple of 2 =3, xv ? xu is una ected. We can therefore replace 1 by , where is uniformly distributed in 0; 2 =3) and assume that xu = 0. Therefore, Pr xv ? xu c (mod 3) satis ed] Z 2 =3 Pr xv = cj 1 = ] 23 d = 0 Z 2 =3 2 c + < 2 (c3+ 1) d : Pr 3 = 23 0Proof. First note that hp; yu i = p1 ei 1 , and thus arghp; yu i =b1 ; ; bn be an orthonormal basis of C n such that b1 = yu and b2 = c(yv ? hyv ; yu iyu ) with c 2 R so that b2 b2 = 1. Let U 2 C n n have bi as ith column. Hence, UU = I and thus U U = I and U is unitary. Consider now the linear transformation that maps x 2 C n to Ux; this is a rotation. We rst observe that Uyu = e1 and Uyv = (yu yv ; cyv yv ? c(yu yv )yu yv ; 0; ; 0), with the second coe cient being real. Since U is unitary, for any x; y 2 C n we have x y = (Ux) (Uy), and therefore anyProof. Letinner product is preserved after the linear transformation. Thus, Uyv = (rei ; s; 0; ; 0) where r2 + s2 = 1. Also, if we let q = Up where p is distributed according to a complex normal distribution, we notice that (i) q is also distributed according to the same distribution (since q q = p p), (ii) hp; yu i = hq; Uyu i and hp; yv i = hq; Uyv i. Therefore, if we consider Uyu and Uyv instead of yu and yv , we obtain exactly the same distribution for xu and xv , proving the claim.We therefore need to study the distribution for = arghp; yv i? arghp; yu i. Since hp; yu i = p1 ei 1 and hp; yv i = p1 rei( 1 ? ) + p2 sei 2 , we have that = arg(p1 rei( 1 ? ) + p2 sei 2 ) ? 1 = arg(p1 re?i + p2 sei( 2 ? 1 ) ) = ? + arg(p1 r + p2 sei ); where = + 2 ? 1 is uniformly distributed and independent of p1 and p2 . We de ne = arg(p1 r + p2 sei ) where p1 ; p2 ; are independent and p1 ; p2 are distributed according to the density (6) and is uniform in 0; 2 ). Thus = ? . The next step in our analysis is to get a grasp of the distribution of . To do this, we will rst need the following lemma. Lemma 6. For a given ` 0, Pr p2 s `p1 r] = (1 ? r`2 )r+ `2 r2 :2 2By the claim, we can assume that yu = e1 and yv = (rei ; s; 0; ; 0). Now consider the inner products hp; yu i and hp; yv i. We can thus restrict our attention to the rst two coordinates of p; call them p1 ei 1 and p2 ei 2 . Since these coordinates are drawn independently from the complex normal distribution, it is equivalent if we draw independently j uniformly from 0; 2 ) and pj from the density function 2 f (r) = re?r =2 : (6) The probability that the equation xv ? xu c (mod 3) is satis ed depends on arghp; yu i, and on arghp; yv i. The following lemma gives a precise dependence. In the lemma below, as in the rest of the paper, whenever we write Pr < ] we assume that and that is determined up to multiples of 2 ; that is, Pr < ] = Pr +2k < for some k 2 Z ]. = arghp; yv i ? arghp; yu i. Then Pr xv ? xu c (mod 3) satisfied] Z 2 =3 2 c = 23 < 2 (c3+ 1) ? d : Pr 3 ? 0Lemma 5. LetWe have Pr p2 s `p1 r] = = =2 Proof. Recall that p1 and p2 have density f (r) = re?r =2 .Z10 0Z1 Z10f (p1 )Z p1`r=s h0f (p2 )dp2 dp11 2 2 2 2 1 = 1 ? ? 1 + `2 r2 =s2 e?(p1 =2)(1+` r =s ) 0 1 `2 r 2 = 1 ? 1 + `2 r2 =s2 = (1 ? r2 ) + `2 r2 ; where we have used the fact that r2 + s2 = 1. We can now prove the following lemma about the distribution of the angle . Lemma 7. For any 0 2 , we have Pr 0 < ] = 21 + p r sin 2 arccos(?r cos ) : 1 ? r2 cos= 1?Z102 h 2 2 2 2 i p1 e?p1 =2 1 ? e?p1 ` r =(2s ) dp10f (p1 ) ?e?p2 =22 2ip1`r=s2 2dp1p1 e?(p1 =2)(1+` r =s ) dp12γpr 1αps 2Figure 2: Angle .Proof. We argue rst for the case , and obtain the general case later by symmetry. Consider Figure 2. Certainly if 2 ( ; 2 ) then 2 0; ], while if 2 0; ], = then 2 0; ]. If 2 ( ; ), we have if and only if sin , p2 s p1 r sin( ? ) , by the law of sines. Thus forFor the proof of Theorem 1, it is useful to be able to compute Pr 1 < 2 ] for any 1 ; 2 even if one of them is outside the range 0; 2 ). For this purpose, we have the following corollary of Lemma 7. Corollary 8. For any , let g(r; ) = 21 + p r sin 2 arccos(?r cos ) : 1 ? r2 cos Then, for any 1 ; 2 with 0 2 ? 1 2 , we have that Pr 1 < 2 ] = g(r; 2 ) ? g(r; 1 ):Proof. The corollary follows from the fact that (i) g(r; 2 + ) = 1 + g(r; ) and (ii) for 0 1 2 2 , we have that Pr 1 < 2 ] = Pr 0 < 2 ] ? Pr 0 < 1 ]. We can now prove Theorem 1. Proof of Theorem 1. By Lemma 5 and the fact that = ? , we have that Pr xv ? xu c (mod 3) satis ed] is Z 3 2 =3 Pr 2 c + ? < 2 (c3+ 1) + ? d : 2 0 3 By Corollary 8, this is Z 3 2 =3 g(r; 2 (c + 1) + ? ) ? g(r; 2 c + ? ) d : 2 0 3 3 In order to t this integral in the two column format, we take each part at a time. We have that 3 Z 2 =3 g(r; 2 (c + 1) + ? ) d 2 0 3 Z 2 (c+1)=3+ g(r; )d (9) = 23 2 c=3+ Z 2 (c+1)=3+ = 23 21 d 2 c=3+ ! 1 arccos2 (?r cos ) 2 (c+1)=3+ ? 2 (10) 2 c=3+ " # 3 2 (c + 1) + 2 ? 2 c + 2 = 8 2 3 3 + 83 2 arccos2 ?r cos 23 c + ? arccos2 ?r cos 2 (c3+ 1) + ; where (9) follows from a change of variable and (10) from observing that g(r; ) = 21 ? 1 dd farccos2 (?r cos )g : 2 Similarly, we have that Z 2 =3 g(r; 23 c + ? ) d ? 23 0 # " 3 2 (c ? 1) + 2 ? 2 c + 2 = 8 2 3 3 + 83 2 arccos2 ?r cos 23 c + ? arccos2 ?r cos 2 (c3? 1) + :Pr 0sin sin( ? ) p1 r d ; where 2 is the probability that 2 0; ] and the other term is the probability that 2 0; ] given that 2 ( ; ). For convenience, we change variables so that = ? , and the probability becomes Z 1 + ? Pr p s sin p r d : Pr 0 < ]= 2 2 sin 1 0 Then we get Pr 0 < ] Z ? r2 sin2 (7) d = 21 + 2 ) sin2 (1 ? r + r2 sin2 0 = 21 + p r sin 2 1 ? r2 cos ! p = ? tan 1 ? r2 cos2 (8) arctan r sin =0 p 2 2 r = 21 + p r sin 2 arctan ? 1 ?coscos r 1 ? r2 cos = 21 + p r sin 2 arccos(?r cos ) 1 ? r2 cos where (7) follows by applying Lemma 6 and (8) follows from 20, pg. 441, number 360]. To obtain the proof statement for all values of , we use symmetry. First observe that for 0 , we have that Pr 0 < ] = Pr 2 ? < 2 ]. Thus (using the fact that takes any speci c angle value with probability 0): Pr 0 <2 ? ] = 1 ? Pr 0 < ] 1 p r sin = 1? 2 arccos(?r cos ) 1 ? r2 cos2 = 21 ((2 ? ) ! r sin(2 ? ) arccos(?r cos(2 ? )) : +p 1 ? r2 cos2 (2 ? ) This is the same expression as in the statement of the lemma with replaced by 2 ? . We have thus shown the lemma for all values of . + Pr p2 s< ] = 21Z。
