One-loop renormalisation of N=12 supersymmetric gauge theory

a rX iv:mat h /6511v1[mat h.NT]3M a y261NOTES ON HILBERT’S 12TH PROBLEM SIXIN ZENG Abstract.In this note we will study the Hilbert’s 12th problem for a primitive CM field,and the corresponding Stark’s ing the idea of “Mirror Symmetry”,we will show how to generate all the class fields of a given primitive CM field,thus complete the work of Shimura-Taniyama-Weil.Introduction 0.1.Let K be a number field,H K be the ideal class group of K ,and let K 0be the Hilbert class field of K .The class field theory tells us there is a canonical isomorphism Gal (K 0/K )≃H K .In general given any integral ideal d ,let K d be the maximal abelian extension of K unramified outside d ,and let H d be the generalized ideal class group relative to d ,then a similar isomorphism holds as well:Gal (K d /K )≃H d .On the other hand,Hilbert’s 12th problem asking for an explicit generation of all the abelian extension of K ,more precisely it is asking for finding a special transcendental function,whose values at some special points would generate all the abelian extension of K .When K is the rational field Q ,the transcendental function is the exponen-tial function and the special points are the division points on the unit circle.Indeed by the classical Kronecker-Weber theorem,all the abelian extension of Q can be obtained by adding the roots of unity to Q .When K is an imaginery quadratic field,this problem is answered by the theory of complex multiplications.As this theory has very much influenced the later thinking about this problem,let’s recall some details.So let K be such a field,consider the set of elliptic curves E satisfying End (E )⊗Q ≃K ,i.e.,the set of elliptic curves with complex multiplications by K .All such elliptic curves can be constructed by the following way:take the caononical embeddingι:K −→C ,let a be an integral ideal of K ,then a is a rank 2Z -module in C ,i.e.,ι(a )is a lattice in C ,so we can take the quotient C /ι(a )which is an2SIXIN ZENGelliptic curve with complex multiplication by K.From the construction it is clear that the ideal group of K operates on this set of elliptic curves,indeed for any representative b of an ideal class,we have the isogeny:C/ι(a)→C/ι(ab). On the other hand all such elliptic curves are defined over some numberfield, and they are represented by the moduli points on the moduli space of all elliptic curves M1=H/P SL2(Z).In particular the Galois group acts naturally on the moduli points of this set of elliptic curves.So if E=C/ι(a),let℘be a prime of K,E(℘)=C/ι(a℘),s(℘)∈H K≃Gal(K0/K)the Artin symbol,then the main result of the complex multiplication is E s(℘)≃E(℘).In more concrete terms if j is the classical modular function,and let p E be the moduli point of E on M1=H/P SL2(Z),then j(p E)is an algebraic number and generates the Hilbert classfield of K.Similar statements hold for all the ray classfields of K.The idea behind the theory of complex multiplication can be summerized as the following:•Given the numberfield K,in order to solve the Hilbert’s12th problem,first we need tofind a suitable class of algebro-geometric objects X,say varieties;•X should be closely related to K such that the ideal classes of K cannaturally act on them;•All such X should be defined over some numberfield,all such X shouldbe living on some natural moduli space so theirfield of moduli are givenby the coordinate function evaluated at the moduli points.The Galoisgroup can naturally acts on them;•Moreover the action of the ideal classes of K and the action of Galoisgroup on the moduli points should be related by the reciprocity law ofclassfield theory and the Kronecker congruence relations;If we canfind such a class of X,then thefield of moduli of X give the answer to Hilbert’s12th problem.For a general numberfield besides imaginery quadratic,this philosophy is difficult to apply.So from now on we will concentrate on a special case.From now on let K be a primitive CMfield of degree2n,n≥1.K is then an imaginery quadratic extension of a totally realfield F,with[F:Q]=n. Further let K∗be the reflexivefield of K,F∗be the maximal totally real subfield of K∗,then K∗is also a primitive CMfield of degree2n,[K∗:F∗]=2. Let{σ1,σ2,···,σn}be the set of archemidean primes of F,lifted to K as the CM types,and letρbe the complex conjugate.When n>1,according to the above philosophy,we naturally consider the set of abelian varieties of dimension n with complex multiplication by K with CM type{σ1,σ2,···,σn},i.e.,those abelian varieties satisfying End(X)⊗Q≃NOTES ON HILBERT’S12TH PROBLEM3 K,and moreover for anyα∈K the action ofαon the space of holomorphic differentials of X is given as the diagonal action of diag(ασ1,···,ασn).All such X can be constructed in the following way:letι:K→C n be the embedding ι(x)=(xσ1,···,xσn),then for any integral ideal a,ι(a)⊂C n as a Z-lattice is of rank2n,hence the quotient X=C n/ι(a)is an abelian variety,one see that such X satisfying the above conditions.From the construction such set of abelian varieties are naturally associated to K,with the integral ideals of K act on them as isogenies.This is exactly the same as elliptic curves.So next we shall consider the moduli space for these X and their arithmetic properties,it is here some complication arised,let’s be careful.Let O K and O F be the rings of integers of K and F,and let a be an integral ideal of O K.Regarding a as a module of O F,it is of rank2.More precisely we have the following(see for example,Yoshita’s book[19]):Lemma0.1.For any ideal a of O K we have the isomorphism as O F-module: a≃b·ω1⊕O F·ω2,whereω1,ω2∈K,b a fractional ideal of O F.Moreover the ideal class of b is c·N K/F(a)=c·aaρ,where c is a fractional ideal of F, independent of a,and c2=D K/F.In particular O K=c·ω1⊕O F·ω2,and if a satisfying a·aρ=(µ),then a=c·ω1⊕O F·ω2.Now let X=C n/ι(a),by Shimura the polarization of X is given by the Riemann form E(x,y)which is E(x,y)=T r K/Q(ζxyρ),withζ∈K satisfying ζρ=−ζ,Im(ζσi)>0,any i.The“type”of this polarization,by definition,is the ideal class ofζd K/F aaρ,where d K/F is the relative different of K over F. From the above lemma it is clear that b is the type of X.For any moduli problem,in order to have a good moduli space we need to fix a polarization of X.For our class of X,we observe that they all have a large ample cone,in fact the dimension of the ample cone are all of n,hence it makes sense to consider the moduli problem with all the ample classesfixed. This is the moduli space of“type polarized abelian varieties”.Concretely for any fractional ideal b of O F,we can constructed a moduli space M n(b)which parametrizes families of abelian varieties with the form C n/v n·ι(b)⊕ι(O F),where v n is a vector in the product of upper half plane H n,and the dot product is defined component-wise.It is well-known that M n(b)=H n/Γ(b)withΓ(b)={α∈SL2(O F)|α≡1mod(b)}.If X is the above abelian variety of type b,the X=C n/ι(a)with a=b·ω1⊕O F·ω2, up to isomorphism we can chooseω1,ω2∈K such thatωX=ω1/ω2satisfyingIm(ωσiX )>0for any i,i.e.(ωσ1X,···,ωσnX)is a vector in H n,hence defines amoduli point of X in M n(b).4SIXIN ZENGSo in summary given the class of CM abelian varieties with afixed CM type,we can construct a natural moduli space M n(b)for afixed type of X,i.e.,ifX1,X2are of the same type,they live on the same moduli space,but differenttypes can produce different moduli spaces.So although the ideal classes of Kcan act on all of the X,the Galois group can only act on the subclass of Xwith the same type.On the other hand it is easy to show that all X are defined over afiniteextension of the reflexfield K∗.In fact for an ideal a∗of K∗,we definea=g(a∗)= τi a∗τi,where{τ1,···,τn}is a CM type of K∗,then g(a∗) acting on X will not change the type of X.It is from this point of view thatin1955,Shimura-Taniyama-Weil(see Shimura’s book[12])established that thefield of moduli of X will generate part of the classfield of K∗,precisely it isthe classfield corresponding to the subgroup of the ideal class group H0K∗= {a∈H K∗|g(a)=(µ),µ∈K}.0.2.In this note we will try to extend the work of Shimura-Taniyama-Weil to cover all the classfields of K.There are actually two problems here.First, the appearance of the reflexfield K∗is quite inconvenient,since our abelian varieties X,their moduli spaces M n(a),and the CM points on the moduli are all constructed naturally from the given CMfield K,it is natural for us to look for the invariants from these abelian varieties that directly generate the class fields of K,instead of the reflex K∗.Second and more important problem,is how can we deal with the classfields that corresponding to the isogenies of abelian varieties that live on the different type of moduli spaces.Thefirst problem can be solved in the following way.Since thefields K and K∗are reflex to each other,by Shimura-Taniyama-Weil theory,the classfields of K is generated by the abelian varieties associated to K∗.So the problem is tofind invariants on X that somehow related to Shimura varieties associated to K∗.For this purpose Ifind the following notion of“cone polarized Hodge Structure”quite useful.First we observed the for all the abelian varieties of the CM type the Kahler cone is very large.Indeed as the polarizations are determined by the Riemann form E(x,y)=T r K/Q(ζxyρ),so the polarizations are determined byζ∈K such thatζρ=−ζ,Im(ζσi)>0,any i.Suchζform a cone of dimension n, hence the Kahler cone is of n dimensional.We can also see this by the fact that since End(X)is an order in K,the automorphism group of X is then the unit group of the order,which is of the form Z n−1⊕T orsion.So the Kahler cone of X is necessarily n dimensional.Given such Kahler cone C X of X we can consider the primitive classes of X in the middle dimension relateive to this cone,i.e.,those classes of dimension n such that are annilated by any element in the Kahler cone.NOTES ON HILBERT’S12TH PROBLEM5{α∈H n(X,C) α·x=0,∀x∈C X}This is the generalization of the notion“transcendental lattice”in the theory of K3surface.The Kahler cone and these primitive classes relative to this cone should be considered as the most basic Hodge theoretical invariants of our abelian varieties.So to understand these abelian varieties,we need to construct the appropriate moduli spaces for these invariants.First let’sfix the Kahler cone and consider the primitive classes of the middle degree relative to this cone.Such primitive classes carries a natural Hodge structure,indeed for abelian varieties with F-multiplication the primi-tive classes can be characterized as the invariant classes of the automorphism group U F,it carries a Hodge structure of weight n,with the i-th Hodge number to be i n =n!6SIXIN ZENGTheorem0.2.(1)We have a natural isomorphism M P H≃H n/SL2(O F∗);(2)The natural morphisms M n(a)→M C→M P H are allfinite.By the theory of Shimura-Taniyama-Weil,the moduli points of X on this moduli space will generate the classfield of K.The natural modular function on the Hilbert modular variety of K∗,when pulled back to M n(a),will become a natural modular function on M n(a).In this way,by directly considering the geometry of X,we can have the classfields of K generated.This answers our first question.Note that in our approach we do not emphasis on the use of“field of moduli”, indeed since our moduli space of primitive Hodge structures can actually be regarded as the moduli space of abelian varieties with multiplication by F∗,the natural“field of moduli”somehow lose its meaning on this moduli space(1). We only need the natural modular functions on the moduli spaces,which give the coordinates of the CM points.In any case our approach is more natural in view of Hodge theory,and serve the purpose of generating classfields of K well.0.3.The second question is more difficult.We need tofind a natural way to interpolate the moduli spaces of different types.For this purpose we will use the idea of Mirror Symmetry.Precisely if R1and R2are two ideals suchthat R1R−12is a real ideal,then although the abelian varieties X R1and X R2defined by R1and R2are living on the different moduli space,we will showtheir“Mirror partners”X′R1and X′R2are living on a single moduli,and theMirrors’field of moduli can be used to generate the classfields.To motivate our idea,let’s consider another approach to the Hilbert’s12th problem,namely the Stark’s conjectures([16]).The point of departure is to consider the Dedekind zeta function and Hecke L-functions for the numberfields.Hilbert’s problem asks for a natural tran-scendental function,indeed for the abelian extension point of view,nothing can be more natural than these L-functions,as they transformed under the Galois group ually the Stark’s conjectures are formulated and studied for a totally realfield,but as we shall see,it is more natural and sim-ple to study it for the CMfield,because all thefinite extension of CMfields are necessarily CM,i.e.,any extension of K has no real infinity.The remarkable fact about the Stark’s conjectures is that it can be for-mulated on any classfields of K uniformly,not just those classfields in the Shimura-Taniyama-Weil theory,so in the explicit form it can be used as a guide for us to search for the solution of missing classfields of the old theory.NOTES ON HILBERT’S12TH PROBLEM7 So let K as above,let R be an ideal class of K,recall that the Dedekind zeta function is defined asζK(s)= a1s−1κK+ρK+O(s−1)whereκK=(2π)n R KN(a)s .NatuallyζK(s)= RζK(s,R),with the limitformula:ζK(s,R)=κw Ks n−1(1+δK(R)s)+O(s n+1) thenδK(R)=nγ+nlog2π−log|D K|−w K|D K|1/2ρK(R−1)w Ks n−1(1+δK s)+O(s n+1) withδK= RδK(R)•ifχ=χ0is not trivial,thenL K(s,χ)=ζK(s,R)=−R Kw K0=(−1)m(R K8SIXIN ZENGThe Stark’s conjecture predicts that if we write L K(s,χ)=R K(χ)s n+ O(s n+1),then R K(χ)also has the form of regulators,i.e.it is a determinent of a matrix whose entries are linear combination of logarithm of units of K0. Moreover we should expect R K(χ)σ=R K(χσ)for anyσ∈Aut(C).In our present case K is a primitive CMfield,in this case Stark’s conjec-ture is somehow simple in the following sense:the regulator R K of K is a determinent of(n−1)×(n−1)matrix,and the regulator R Kof K0is a determinent of(mn−1)×(mn−1)matrix.Stark’s conjecture in fact says that the quotient R K/R K is a determinent of(mn−n)×(mn−n)matrix, and this matrix should be diagonalized into m−1blocks,with each block a n×n matrix,further in this case we can use the R K matrix to simplify these blocks,so in this extension there are only m−1essential new units.In other words,U Kas a module of U K is free of rank m−1.This is very much similar to the classical case of imaginery quadraticfields.By some elementry argument we can show that R K=(R K)m·vol(S), where vol(S)is a determinent of(m−1)×(m−1)matrix whose entries are linear combinations of logarithm of units in K0.These are the basis of U Kas the module of U K.On the other hand by the Frobenius determinent formula, χ=χ( Rχ(R)δK(R))=det R1,R2=1(δK(R1)−δK(R2)) Hence we should expect:•δK(R)=log|ηK(R)|;•δK(R1)−δK(R2)=log|ηK(R1)ηK(R2)is a unit in K0.More overthese units should transform under the Galois group according to thereciprocity law.0.4.To prove things like this we need to have a good expression forδK(R), this can be done by using the theory of GL(2)Eisenstein series over the totally realfield F.The Eisenstein series is defined asE(w,s;a)=(c,d)∈(a⊕O F)/U F,(c,d)=(0)ni=1y s i|cσi z i+dσi|−2sThe idea is a classical one,sinceζK(s,R)= a∈R1w2satisfyingIm wσi>0,∀i.Then we haveNOTES ON HILBERT’S 12TH PROBLEM 9ζK (s,R )=N (a 1)s α∈a 1/U F ,α=012n −2πn h F RF [χF (d F )L F (2,χ−1F )i Im(ωi )+πn D −3/2F 0=b ∈d −1F a σ1,χ(bda )|N (b )|−1exp (2πi (n j =1b j ℜ(w j )+i |b j Im(w j )|))]where (1)a,d ∈A ×F such that div (a −1)=a and div (d )=d F ;(2)σs,χ(x )is a function defined asσs,χ(s )= v ∈(finite primes ) 1+χv (w v )q s v +···+(χv (w v )q s v )ord v (x v )if x v ∈d v ,0if x v /∈d v .Here d v denotes the ring of integers of F v ,w v is the prime elementof F v and q v =|d v /w v d v |.So we haveζK (s,R )=−R K10SIXIN ZENGδK(R)=h(ω;a)−log i Im(w i)−logN(a)We reminded that a is the type of R−1,w=(w1,···,w n)∈H n is the CM point defined by R,and h(w,a)is the complicated function defined above.So our basic task is to understand this function.0.5.We notice that hχFsatisfying the following modular properties([19]):for γ∈Γa we have(1)hχF (γω;a)=hχF(ω,a)ifχF is not trivial;(2)h1(γω;a)−log( i Im(γω)i)=h1(ω,a)−log( i Imωi)So in particular we haveχFχF(a)hχF(γω;a)−log( i Im(γω)i)= χFχF(a)hχF(ω,a)−log( i Imωi)which suggests that we may actually have a Hilbert modular formηK(w;a) of parallel weight such that h(w;a)=log|ηK(w;a)|.Classically in case F= Q this is indeed the case asηK is the classical Dedekind eta functionη,it is well-known thatηhas an infinite product expression,which when taking the logarithm translated into a Fourier expansion,which is exactly the above Fourier series.In the higher dimensional case it is not that easy2.Besides the fact that the Fourier expansion is too complicated and difficult to work with,we can not expect by directly exponenciate the above expression of h to get a meaningful function,precisely because of the infinite unit group of F,as shown as the regulator term R F in the leading coefficients of the Fourier expansion.The regulator R F is not a rational number,in fact we expect it to be transcendental, so even if we exponenciate h we can not get anything useful for the arithmetic purpose.In particular we can not expect to get an infinite product expression as the classicalηfunction.0.6.What should I do?It turns out although we can not exponenciate theh function,can not get the explicit formula forηK(w;a),we still can say something quantitatively about it.The idea is to consider a twisted version of Eisentein series:E u,v(w,s;a)=(c,d)∈(a⊕O F)/U F,(c,d)=(0)ni=1e2πi(cσi u i+dσi v i)(Im w i)s|cσi w i+dσi|−2sNOTES ON HILBERT’S12TH PROBLEM11 where(u,v)∈R n⊕R n.This is entirely adopted from the classical Kronecker’s second limit for-mula(see[18]).To explain why we need to develop the twisted Eisenstein series,let’s recall the classical situation,i.e.,when F=Q.In this case the Eisenstein series isE(w,s)=m,n∈Z,(m,n)=0(Im(w))s2[1+(CONST+log Im(w)−4log|η(w)|)s]+O(s2)The twisted Eisenstein series is:E u,v(w,s)=m,n∈Z,(m,n)=0e2πi(mu+nv)(Im(w))s24w∞n=1(1−q n w)and g u,v is the Siegel’s function:g u,v=−q1q zφ(w,z) and we haveg u,v=q112SIXIN ZENG(3)g u,v is also closely related to Dedekindη.In fact as a function of zg u,v has a simple zero at z=0withη(w)as the coefficient,i.e.,|g u,v|=|η(w)|2|q z−1|+O(z2)This shows that the absolute value|η(w)|is not a theta null,but rather a“derivative theta null”.But we note our theta functions arenormalized at z=0to be zero,φ(w,0)=0,if the theta functionnormalized in this way,their derivatives can also be used as the coor-dinates on the moduli space.By abuse of notation we still call|η(w)|a theta null,hence it gives a modular function on the moduli space.From the definition,E u+1,v=E u,v+1=E u,v,hence g u+1,v=g u,v+1= g u,v,but since|g−v,u|=|q12B2(−v)w g−v,u(w)Then from the periodic condition of g u,v we immediately see that|φ(w,z+1)=φ(w,z);|φ(w,z+w)|=|q−1z|·|φ(w,z)| That is,|φ(w,z)|satisfying the characterization of a theta function,moreover since we know it is an analytic function,it then has to be a theta function itself.This is the idea we would follow in the higher dimensional case,as we observed before,since in the higher dimension we can not expect any explicit infinite product formula for the functionηK(w;a),but we still have all the periodic properties as the1-dimensional case.Now we go back to the higher dimensional case,the Eisenstein series is:E(w,s;a)=(c,d)∈(a⊕O F))/U F,(c,d)=(0)ni=1(Im(w i))s|cσi w i+dσi|−2sWe have the limit formula:E(w,s;a)=−2n−2h F R F s n−1[1+(CONST+logN(a)+log( i Im(w i))−h(w;a))s]+O(s n+1) The twisted Eisenstein series is:NOTES ON HILBERT’S12TH PROBLEM13E u,v(w,s;a)=(c,d)∈(a⊕O F)/U F,(c,d)=(0)ni=1e2πi(cσi u i+dσi v i)(Im w i)s|cσi w i+dσi|−2sand we have the limit formula:E u,v(w,s;a)=−2n−2hF R F log|g−v,u(w;a)|s n+O(s n+1)where log|g−v,u(w;a)|has an explicit Fourier expansion,just like h(w;a).Then we argue as the following:(1)Recall that u=(u1,···,u n)∈R n,v=(v1,···,v n)∈R n,and O F⊂R n as a lattice.From the definition,for anyα∈O F,we have E u+α,v=E u,v+α=E u,v,i.e.,translate invariant under O F,hence|g−v+α,u|=|g−v,u+α|=|g−v,u|.(2)Now write z=u−vw,i.e.,z=(z1,···,z n),z i=u i−v i w i,∀i.We try to write g−v,u as a function of(w,z),so we defineφ(w,z)=q−12B2(−v)w= i q−112wφ(w,z)|−log(|ηK(w;a)|2 i|z i|)}=0that islim z→0|q1|ηK(w;a)|2 i|z i|=1Also we verify that our theta function is normalized at z=0to be 0.This implies thatηK(w;a)is a theta null.By the classical theory of theta function,theta null naturally gives rise to the modular forms on the moduli space.In fact this should be more or less expected.By Mumford’s theory of algebraic theta function,we may further conclude that these theta nulls in fact defines the moduli space as an integral scheme over Z,hence have all the expected integral properties.14SIXIN ZENG0.7.In summary we have found the explicit form of the functionδK(R).δK(R)=logN(a)+log i Im(w i)−h(w;a)=logN(a)+log i Im(w i)−log|ηK(w;a)|2=log[N(a) i Im(w i)|ηK(w;a)−2|]where R is an ideal class of O K,a its type,w its CM point on M n(a),and ηk(w;a)is the theta null:∂∂z nφ(w,z)|z=0=ηK(w;a)2By the Stark’s conjecture,we need to understandδK(R1)−δK(R2),i.e., we need to understand the quotientηK(w1;a1)ηK(w2;a)is meaningful,as the modular function evaluating at the CMpoints,and the natural action of Galois group on them is prescribed by the reciprocity law.But when R1and R2are of the different type,for example, when R1R−12is a real ideal,thenηK(w;a1)andηK(w;a2)are on the different moduli spaces,thus their quotient becomes meaningless.This is precisely the limit of Shimura-Taniyama-Weil’s theory.So what can we do?To go further we need tofind a natural way to inter-polate the different moduli spaces,and it is here the idea of Mirror symmetry comes.As we shall see,in this case this quotient will have a meaning similar to the classical one if we consider the complexified Kahler moduli of the abelian varieties.Why should we interpolate the different moduli spaces?The functionδK(R) is defined not on a single moduli space of thefixed type,but rather automati-cally been defined on all the moduli spaces,as the type a can vary accordingly. Likewise the modular formηK is a Hilbert modular form on all the type-fixed Hilbert modular varieties,and when the type vary,can be regarded as a mod-ular form on all the moduli spaces.This strongly suggests that we should have a natural way to interpolate all these moduli spaces of different types,such that these functions can naturally defined.In other words,when wefix the type a,we get the Hilbert modular forms,what then happens if wefix the CM pointsωand let the type vary?When we look the explicit form ofδK(R)and h,we note the apparent symmetric roles played by the quantities σIm(ωσi)and N(a).Indeed if we fix the CM pointsωand let a vary,we should have a meaning for the quantity N(a).This can be achieved by considering the Kahler moduli of our abelian varieties.0.8.Mirror Symmetry is usually formulated for the Calabi-Yau varieties, roughly it asserts that Calabi-Yau always come in pairs,X and X′,with theNOTES ON HILBERT’S12TH PROBLEM15“complex moduli”and“Kahler moduli”exchanged.In terms of the Hodgenumber,it means the Hodge diamond of X′is a rotation of X.For abelian varieties,Mirror Symmetry is generally regarded as“trivial”,as the underlying topological type would not change.Nevertheless we canstill talk about it.There are several constructions of Mirror manifold for theabelian varieties,the simplest one I believe,is given by Manin([9]).It goes asthe following:let k be any completefield,X an abelian variety over k,T bethe algebraic torus of dimension n over k,T≃(k×)n.Then the multiplicativeuniformization is0→P X→T→X→0,where P X is a free abelian groupof rank n,P X is called the period of X.Under this uniformization the Mirrorpartner X′is then0→P X→T∨→X′→0,i.e.,we explicitly indentify theperiods in T and T∨.When k≃C one verify that the complex moduli andKahler moduli of the two are exchanged.In our situation,given the Mirror pair X and X′we will be mainly concernabout the relations of theta functions on them.Since the underlying topologicaltype would not change,we may regard the Mirror transform as a“rotation”of complex structure of X.So to compare the theta functions on X and X′we have tofix the underlying real structures.We begin with X=C n/(w·a⊕O F)≃R2n/Z2n,any polarization of X isgiven by an integral skew-symmetric bilinear form on R2n.Given such a formω,we canfind an integral basis{λ1,···,λ2n}of the integral lattice such thatif{x1,···,x2n}is the dual basis,thenω= n i=1δi dx i∧dx n+i,withδ1|δ2|···the elementary divisors.Note in our case the biliear form is given by the trace T r K/Q(ζxyρ)withthe admissibleζ∈K such thatζρ=−ζ,Im(ζσi)>0.Thus we may regard(x1,···,x n)as an integral basis of O F,and(x n+1,···,x2n)as an integralbasis of a.In particular(x n+1,···,x2n)depends on a.In the following we willdenote it as x n+i(a)if we need to use this dependence.Next we introduce the complex structure,so X becomes a complex tori,and we can introduce the complex coordinates.To do this let e i=λi/δi,i=1,2,···,n,and let{z i}be the complex dual of{e i}.Consider the changeof coordinates transform:Ω·(x1,···,x2n)T=(z1,···,z n)TThenΩ=(∆δ,Z)with∆δ=diag(δ1,···,δn)the diagonal matrix,and Zsymmetrical,Im(Z)>0.We recogonize that∆−1δZ is the period matrix of X.Note in our case for abelian varieties with CM by K,the peiod martix Z isnecessarily diagonal∆−1δZ=diag(w1,···,w n),with w=(w1,···,w n)∈H n.In particular we have z i=δi·x i+δi·w i·x n+i(a),we may regard it as the transform from the underlying real coordinates to the complex coordinates.16SIXIN ZENGNow recall the theta function on X is characterized by the periodic condi-tion:θ(z+λi)=θ(z);θ(z+λn+i)=e−2πiz iθ(z)Taking absolute values we have:|θ(z+λi)|=|θ(z)|;|θ(z+λn+i)|=e2πIm(z i)|θ(z)|However from the above coordinates transformation,Im(z i)=δi·Im(w i)·x n+i(a)The Mirror symmetry transform says that we can exchange the complex moduli with the Kahler moduli,while the coordinates w=(w1,···,w n)∈H n can be regarded as the complex moduli of X,where is the Kahler moduli?Our Kahler moduli coordinates are actually in the variables(x n+1(a),···,x2n(a)). Since they are depend on the type a,we want to write the dependency explic-itly,in order to understand the transformation of types.For this end let’s write x n+i=x n+i(O F).The type ideal a as a Z module,is a submodule of O F of full rank,i.e.,if wefix an integral basis of O F,then O F/a≃⊕n i=1Z/t i Z,with x n+i(a)=t i x n+i and i t i=N(a)/D F.Thus the positive rational numbers(t1,···,t n)can be conviniently regarded as the coordinates of the ideal a,and under appropriate identification,can be regardedas the coordinates of of the Kahler class in the the Kahler moduli.So in particular we haveIm(z i)=δi·Im(w i)·t i·x n+iBut from the above formula,when we exchange the complex moduli(w1,···,w n) and Kahler moduli(t1,···,t n),it’s not going to change the multiplier e2πIm(z i)=e2πδi·t i·Im(w i)·x n+i.Since the absolute value of theta functions can be regardedas a real analytic function on R2n,thus we conclude that for the given Mir-ror pair X and X′,their theta functions’absolute values satisfying the same periodic condition,hence must be only differed by a constant!Recall our previous puzzle,when two ideal classes R1and R2of O K sat-isfying R1R−12is a real ideal,then R1and R2are of the different type,sothe corresponding abelian varieties X1and X2living on the different moduli spaces,soηK(w,a1)/ηK(w,a2)has no meaning.But we knowηK(w,a)is the theta null of X,thus by the above formula,ηK(w,a)is also the theta null of the Mirror X′.So although X1and X2living on the different moduli space,if their Mirror X′1and X′2are in the same moduli space,thenηK(w,a1)/ηK(w,a2) would be meaningful!This is indeed the case,as X′1and X′2are on the sin-gle moduli space,the complexified Kahler moduli space of X.This is the underlying rationale for us to use the Mirror symmetry.Note from this relation of theta functions we also see that if X is defines over a numberfield,then the Mirror X′also is defined over that numberfield.。

环境管理体系国家注册审核员复习题及答案一、单项选择题1、GB/T24001-2004标准的全称是（ A ）。

A 环境管理体系要求及使用指南B 环境管理体系规范及使用指南C 环境管理体系原则体系和支持技术通用指南D 环境管理体系要求及支持技术指南2、下列不属于废水治理技术的是 A. 。

A. 稀释法B.混凝法 C反渗透法. D.生物膜法3、《城市区域环境噪声标准》中各类标准的适用区域由（ A ）划定。

A、当地人民政府B、当地环境保护行政主管部门C、当地气象部门D、当地人民代表大会4、关于GB/T24001-2004标准，下面哪一个提法是正确的 C 。

A. 标准包含了一些针对其他管理体系的要求B. 标准可能不适用于个别的地理、文化和社会条件C. 两个从事类似活动但具有不同环境绩效的组织可能都是符合标准要求的D. 以上全部5．按照标准的要求，组织应就将其环境方针进行传达，传达的范围应包括( C )。

A 组织内的所有员工B 组织内的所有员工和所有的相关方C 组织内的所有员工，以及所有代表组织工作的人员D 组织所使用的产品或服务所涉及的相关方6、随着宏观经济调控政策的逐步落实，我国经济增速会适度放缓，对石油天然气资源的需求有所减少，供求矛盾在一定程度上将得到缓解。

根据国际能源署的最新预测，今年我国原油产量将达1.75亿吨，比去年增长1%；而原油消费量将有可能突破3亿吨，比去年增长12%左右；进口将会超过1亿吨，有可能接近1.2亿吨，比去年增长30%左右。

根据这段文字，我们可以知道是 C 。

A．我国原油供给紧张 B．我国原油消费主要靠进口C．我国对进口原油的依赖加大 D．我国对能源的需求会越来越少7、盛入固体容器的液态化学危险品的污染防治，适用：（ C ）A、中华人民共和国水污染防治法B、中华人民共和国安全生产法C、中华人民共和国固体废物污染环境防治法D、中华人民共和国水法8、环境管理体系的详细程度、体系文件的规模及所投入的资源，主要取决于 D 因素。

新理念大学英语阅读教程unit12 entropy EntropyIt was about two months ago when I realized that entropy was getting the better of me. On the same day my car broke down (again), myrefrigerator conked out and I learned that I needed root-canal work in my right rear tooth. The windows in the bedroom were still leaking every time it rained and my son’s baby sitter was still failing to show up everytime I really needed her. My hair was turning gray and my typewriter was wearing out. The house needed paint and I needed glasses. My son’s sneakers were developing holes and I was developing a deep sense of futility.After all, what was the point of spending half of Saturday at the Laundromat if the clothes were dirty all over again the following Friday?Disorder, alas, is the natural order of things in the universe.There is even a precise measure of the amount of disorder, called entropy. Unlike almost every other physical property (motion, gravity, energy), entropydoes not work both ways. It can only increase. Once i t’s created it can never be destroyed. The road to disorder is a one-way street. (entropy的特性)Because of its unnerving irreversibility, entropy has been calledthearrow of time. We all understand this instinctively. Children’s rooms, left on their own, tend to get messy, not neat. Wood rots, metal rusts, people wrinkle and flowers wither. Even mountains wear down; even the nucleiof atoms decay. In the city we see entropy in the rundown subways and worn-out sidewalks and torn-down buildings, in the increasing disorder of our lives. We know, without asking, what is old. If we were suddenly to see the paint jump back on an old building, we would know that something was wrong. If we saw an egg unscramble itself and jump back into its shell, we would laugh in the same way we laugh at a movie run backward. (注意本段的一系列动词) (entropy是什么,为什么被称作时光之箭?)Entropy is no laughing matter, however, because with every increase in entropy energy is wasted and opportunity is lost. Water flowing down a mountainside can be made to do some useful work on its way. But once all the water is at the same level it can work no more. That is entropy. When my refrigerator was working, it kept all the cold air ordered in one part of the kitchen and warmer air in another. Once it broke down the warm and cold mixed into a lukewarm mess that allowed my butter to melt, my milk to rot and my frozen vegetables to decay. (注意本段的一系列动词) (entropy是什么)Of course the energy is not really lost, but it has diffused anddissipated into a chaotic caldron of randomness that can do us no possible good. Entropy is chaos. It is loss of purpose. (entropy是什么) People are often upset by the entropy they seem to see in the haphazardness of their own lives. Buffeted about like so many molecules in my tepid kitchen, they feel that they have lost their sense of direction,that they are wasting youth and opportunity at every turn. It iseasy to see entropy in marriages, when the partners are too preoccupied to patch small things up, almost guaranteeing that they will fall apart. There is much entropy in the state of our country, in the relationships between nations—lost opportunities to stop the avalanche of disorders that seems ready to swallow us all.Entropy is not inevitable everywhere, however. Crystals andsnowflakes and galaxies are islands of incredibly ordered beauty in the midst of random events. If it was not for exceptions to entropy, the sky would be black and we would be able to see where the stars spend their days; it is only because air molecules in the atmosphere clusterin ordered groups that the sky is blue.The most profound exception to entropy is the creation of life. A seed soaks up some soil and some carbon and some sunshine and some water and arranges it into a rose. A seed in the womb takes some oxygen and pizza and milk and transforms it into a baby.The catch is that it takes a lot of energy to produce a baby. Italso takes energy to make a tree. The road to disorder is all downhill but the road to creation takes work. Though combating entropy is possible, italso has its price. That’s why it seems so hard to get ourselves together, so easy to let ourselves fall apart.Worse, creating order in one corner of the universe always creates more disorder somewhere else. We create ordered energy from oil and coal at the price of the entropy of smog.I recently took up playing the flute again after an absence of several months. As the uneven vibrations screeched through the house, my soncovered his ears and said, “Mom, what’s wrong with your flute?” Nothing was wrong with my flute, of course. It was my ability to play it that had atrophied, or entropied, as the case may be. The only way to stop that process was to practice every day, and sure enough my tone improved, though only at the price of constant work. Like anything else, abilities deteriorate when we stop applying our energies to them.That’s why entropy is depressing. It seems as if just breaking even is an uphill fight. There’s a good reason that this should be so. The mechanics of entropy are a matter of chance. Take any ice-cold air molecule milling around my kitchen. The chances that it will wander in the direction of my refrigerator at any point are exactly 50-50. The chances that it will wander away from my refrigerator are also 50-50.But take billions of warm and cold molecules mixed together, and the chances that all the cold ones will wander toward the refrigerator and all the warm ones will wander away from it are virtually nil.Entropy wins not because order is impossible but because there are always so many more paths toward disorder than toward order. There are so many more different ways to do a sloppy job than a good one, so many more ways to make a mess than to clean it up. The obstacles and accidents in our lives almost guarantee that constant collisions will bounce us on to random paths, get us off the track. Disorder is the path of least resistance, the easy but not the inevitable road.Like so many others, I am distressed by the entropy I see around me today. I am afraid of the randomness of international events, of the lack of common purpose in the world; I am terrified that it will lead into the ultimate entropy of nuclear war. I am upset that I could not in the city where I live send my child to a public school; that people are unemployed and inflation is out of control ; that tensions between sexes and races seem to be increasing again; that relationships everywhere seem to be falling apart.Social institutions—like atoms and stars—decay if energy is not added to keep them ordered. Friendships and families and economiesall fall apart unless we constantly make an effort to keep them working and well oiled . And far too few people, it seems to me, are willing to contribute consistently to those efforts.Of course, the more complex things are, the harder it is. If there were only a dozen or so air molecules in my kitchen, it would be likely—ifI waited a year or so—that at some point the six coldest ones wouldcongregate inside the freezer. But the more factors in the equation—themore players in the game—the less likely it is that their pathswillcoincide in an orderly way. The more pieces in the puzzle, theharder it isto put back together once order is disturbed. “Irreversibility,” said aphysicist, “is the price we pay for complexity.”。

a r X i v :c o n d -m a t /0412425v 1 [c o n d -m a t .m e s -h a l l ] 16 D e c 2004Current noise spectrum of a quantum shuttleChristian Flindt a ,1,Tom´a ˇs Novotn´y b ,c and Antti-Pekka Jauho aa MIC–Department of Micro and Nanotechnology,Technical University of Denmark,DTU -Building 345east,DK-2800Kongens Lyngby,Denmarkb Nano-Science Center,University of Copenhagen -Universitetsparken 5,DK-2100Copenhagen Ø,Denmarkc Department of Electronic Structures,Faculty of Mathematics and Physics,Charles University -Ke Karlovu 5,12116Prague,Czech Republic1.IntroductionA decade of advances in microfabrication technol-ogy has pushed the typical length scales of electrome-chanical systems to the limit,where quantum mechan-ical effects of the mechanical motion must be taken into account [1].Such nano-electromechanical systems (NEMS)exhibit a strong interplay between mechan-ical and electronic (or magnetic)degrees of freedom,and their electronic transport properties reflect this in-terplay in an intricate manner.The aforementioned three studies deal with thespectra of a classical shuttle,a classicalical resonator coupled to a single electron (SET),and the C60-SET in a strongcal coupling regime,respectively.Thefirst twoies[4,5]found peaks in the current noise spectra thefirst two multiples of the mechanical frequency. low bias voltages and strong electromechnicalthe third study[6]found a power-law frequency pendence of the noise spectrum attributed to avalanche charge transfer processes.In all three cases the noise spectra revealed interesting details about the systems.From the technical point of view,two of the studies[4,6]used Monte Carlo simulations,whereas[5] used a model-specific numerical evaluation of the Mac-Donald formula(see below).In this work,we present a study of the full frequency spectrum of the current noise of a quantum shuttle [7,8,9].We extend the general formalism developed for the zero-frequency noise[10,11]and the FCS[12]cal-culations for NEMS described by a Markovian general-ized master equation.The presented formalism applies not only to the shuttle studied here but could equally well be used for all three systems from the previous studies[4,5,6]for the determination of the noise spec-tra.We apply the developed theory to compute numer-ically the noise spectrum of the shuttle in the deep quantum regime2as function of the damping coeffi-cient.The spectrum has peaks at integer multiples of the slightly renormalized mechanical frequency.The renormalization of the bare oscillator frequency as read offfrom the current spectrum explains a small but ob-servable deviation from the expected value of the cur-rent in the shuttling regime I shut=eω0/2π[8].It turns out that it is the renormalized oscillator frequency˜ω0 which should enter this relation.Finally,we focus on the low-frequency part of the spectrum when approach-ing the semi-classical regime for intermediate values of the damping,i.e.in the coexistence regime,where both shuttling and tunneling are effective.We use the frequency dependence of the spectrum forω≪ω0to identify additional qualitative evidence for the bistable behavior of the shuttle in this regime described by a/mω0sets the length scale for the quantum mechanical zero-point motion.˙ˆρ(n) 00(t)=12{e−2ˆxλˆρ(n−1)11(t)eˆx i[ˆH osc−eEˆx,ˆρ(n)11(t)]+L dampˆρ(n)11(t)−ΓRλ,ˆρ(n)11(t)}+ΓL e−ˆxλ,(1)with n=0,1,2,...andˆρ(−1)11(t)≡0.The commu-tators describe the coherent evolution of the charged(ˆρ(n)11≡ 1|ˆρ(n)|1 )or empty(ˆρ(n)00≡ 0|ˆρ(n)|0 )shuttlewith mass m and natural frequencyω0.The electric field3between the leads is denoted E.The terms pro-portional toΓL(R)describe transfer processes from the left(to the right)lead with hopping amplitudes that depend exponentially on the ratio between positionˆx and the electron tunneling lengthλ.The mechanical damping of the oscillator is described by the damp-ing kernel(here at zero temperature)L dampˆρ(n)jj=−iγ2 [ˆx,[ˆx,ˆρ(n)jj]],j=0,1[8,10].The n-resolved GME can be recast into the compactform[11]˙ˆρ(n)=(L−IR)ˆρ(n)+I Rˆρ(n−1),ˆρ(−1)≡0,(2) where we have introduced the Liouvillean L,describ-ing the evolution of the system density matrixˆρ(t)= nˆρ(n)(t),i.e.˙ˆρ(t)=Lˆρ(t),and the superoperator for the tunnel current through the right junction(taking e=1),defined by its action on the density operatorI Rˆρ=ΓR eˆxλ.(3) Assuming that the system tends exponentially to a stationary stateˆρstat the Liouvillean has a single eigen-value equal to zero withˆρstat being the(unique and nor-malized)right eigenvector which we denote by|0 [11]. The corresponding left eigenvector is the identity oper-atorˆ1which we denote by ˜0|,and from the definition of the inner product4we have ˜0|0 =Tr(ˆ1†ˆρstat)=iωP−Q1iωP−R(ω),(5) where we have introduced the frequency dependent su-peroperator R(ω),which is well-defined even forω= 0,since the inversion in that case is performed only in the subspace where L is regular.3.TheoryWe consider the current autocorrelation function de-fined asC II(t′,t′′)=12{∆ˆI(t),∆ˆI(0)} .(7) The current noise spectrum is the Fourier transform ofC II(t),i.e.S II(ω)≡ ∞−∞dtC II(t)e iωt.(8) In order to calculate the current noise measurable in, say,the right lead one must recognize that the cur-rent running in the lead is a sum of two contributions, namely the tunnel current through the right junction and a displacement current induced by electrons tun-neling between leads and grain.This is reflected in the Ramo-Shockley theorem[2]ˆI=cLˆIR+c RˆI L.(9) HereˆI is the current operator for the current running in the lead,whereasˆI L(R)is the operator for the tunnel current through the left(right)junction,and c L(R)is the relative capacitance of the left(right)junction in the sense c L+c R=bining the Ramo-Shockley 3theorem with charge conservation leads to an expres-sion for the current noise measured in the lead[14]S II(ω)=c L S IR I R (ω)+c R S IL I L(ω)−c L c Rω2S NN(ω),(10)whereˆN=|1 1|is the occupation number operator of the electronic level of the grain.In the following we neglect any dependence of the capacitances on the position of the grain and consider the symmetric case c L=c R=12d2i e i(ω+iε)t.(15)Since {∆ˆQ R(t),∆ˆI R(0)} = {∆ˆQ R(t),∆ˆI R(t)} = ddt ∆ˆQ2R(t)ω+iεdt∆ˆQ2R(t)ω−iε5Thefirst equality follows from a simple substitu-tionτ→t−τin the chain {∆ˆQ R(t),∆ˆI R(0)} = t0dτ {∆ˆI R(τ),∆ˆI R(0)} = t0dτ {∆ˆI R(t),∆ˆI R(τ)} = {∆ˆQ R(t),∆ˆI R(t)} .and consequentlyS IR I R(ω)= ∞0dt ddt n2(t) − n(t) 2 ,(20) where the regularizationωsin(ωt)→1dt n2(t) − n(t) 2=ddtn2(t) −2 n(t)ddtn(t) =Tr(I Rˆρ(t))= ˜0|I R|0 ,(25) dwhere we have usedˆρ(t)=ˆρstat,since we are consider-ing the stationary limit.The sum entering Eq.(26)isevaluated by introducing an operator-valued generat-ing function defined asˆF(t,z)= ∞n=0ˆρ(n)(t)z n,from which we get∂∂z˜ˆF(s=−iω,z) z=1=G(−iω)I R G(−iω)ˆρ(0)+G(−iω) n nˆρ(n)(0).(28)Again,we haveˆρ(0)=ˆρstat,and moreover we as-sume the factorized initial condition[14,16]ˆρ(n)(0)=δ0nˆρstat,i.e.we start counting the charge passing through the right junction at t=0and the system is in its stationary state.Now,combining Eqs.(5,23-28) and having in mind that Pˆρstat=ˆρstat,Qˆρstat=0, straightforward algebra leads to˜S(ω)=i ˜0|I R|0 −2 ˜0|I R R(ω)I R|0 .(29) We thus arrive atS IR I R(ω)= ˜0|I R|0 −2Re ˜0|I R R(ω)I R|0= ˜0|I R|0 −2 ˜0|I R Lλ|1 0|ˆρ|0 1|e−ˆx2) S II(ω)= ˜0|I R|0 +ω22)ˆρ+ˆρ(ˆA−iωFig.2.The ratio between the current noise and the current F(ω)=S II(ω)/ ˆI as function of the dampingγand fre-quencyω.The other parameters areΓL=ΓR=0.05ω0,λ=x0,d≡eE/mω20=0.5x0,where x0=IΓS←TΓT←S(ΓS←T+ΓT←S)2+ω2,(38)whereI=I SΓS←T+I TΓT←S6I S=˜ω0˜ΓL+˜ΓR,with˜ΓR=ΓR e /mω0λ2e2eE/mω20λ,˜ΓL=ΓL e /mω0λ2[10,13].6。

Monotone circuits for the majority functionShlomo Hoory Avner Magen†Toniann Pitassi†AbstractWe present a simple randomized construction of size O n3and depth53log n O1monotone circuits for the majority function on n variables.This result can be viewed as a reduction in the size anda partial derandomization of Valiant’s construction of an O n53monotone formula,[15].On the otherhand,compared with the deterministic monotone circuit obtained from the sorting network of Ajtai, Koml´o s,and Szemer´e di[1],our circuit is much simpler and has depth O log n with a small constant.The techniques used in our construction incorporate fairly recent results showing that expansion yields performance guarantee for the belief propagation message passing algorithms for decoding low-density parity-check(LDPC)codes,[3].As part of the construction,we obtain optimal-depth linear-size mono-tone circuits for the promise version of the problem,where the number of1’s in the input is promised to be either less than one third,or greater than two thirds.We also extend these improvements to general threshold functions.At last,we show that the size can be further reduced at the expense of increased depth,and obtain a circuit for the majority of size and depth about n1Department of Computer Science,University of British Columbia,Vancouver,Canada.†Department of Computer Science,University of Toronto,Toronto,Canada.1IntroductionThe complexity of monotone formulas/circuits for the majority function is a fascinating,albeit perplexing,problem in theoretical computer science.Without the monotonicity restriction,majority can be solvedwith simple linear-size circuits of depth O log n,where the best known depth(over binary AND,OR,NOT gates)is495log n O1[12].There are two fundamental algorithms for the majority function thatachieve logarithmic depth.Thefirst is a beautiful construction obtained by Valiant in1984[15]that achievesmonotone formulas of depth53log n O1and size O n53.The second algorithm is obtained from the celebrated sorting network constructed in1983by Ajtai,Koml´o s,and Szemer´e di[1].Restricting to binaryinputs and taking the middle output bit(median),reduces this network to a monotone circuit for the majorityfunction of depth K log n and size O n log n.The advantage of the AKS sorting network for majority is thatit is a completely uniform construction of small size.On the negative side,its proof is quite complicated andmore importantly,the constant K is huge:the best known constant K is about5000[11],and as observed byPaterson,Pippenger,and Zwick[12],this constant is important.Further converting the circuit to a formulayields a monotone formula of size O n K,which is roughly n5000.In order to argue about a quality of a solution to the problem,one should be precise about the differentresources and the tradeoffs between them.We care about the depth,the size,the number of random bitsfor a randomized construction,and formula vs circuit question.Finally,the conceptual simplicity of boththe algorithm and the correctness proof is also an important goal.Getting the best depth-size tradeoffs isperhaps the most sought after goal around this classical question,while achieving uniformity comes next. An interesting aspect of the problem is the natural way it splits into two subproblems,the solution to which gives a solution to the original problem.Problem I takes as input an arbitrary n-bit binary vector,and outputs an m-bit vector.If the input vector has a majority of1’s,then the output vector has at least a2/3fraction of 1’s,and if the input vector does not have a majority of1’s,then the output vector has at most a1/3fraction of1’s.Problem II is a promise problem that takes the m-bit output of problem I as its input.The output of Problem II is a single bit that is1if the input has at least a2/3fraction of1’s,and is a0if the input has at most a1/3fraction of1’s.Obviously the composition of these two functions solves the original majority problem.There are several reasons to consider monotone circuits that are constructed via this two-phase approach.First,Valiant’s analysis uses this viewpoint.Boppana’s later work[2]actually lower bounds each of thesesubproblems separately(although failing to provide lower bound for the entire problem).Finally,the secondsubproblem is of interest in its own right.Problem II can be viewed as an approximate counting problem,and thus plays an important role in many areas of theoretical computer science.Non monotone circuits forthis promise problem have been widely studied.Results The contribution of the current work is primarily in obtaining a new and simple construction ofmonotone circuits for the majority function of depth53log n and size O n3,hence significantly reducing the size of Valiant’s formula while not compromising at all the depth parameter.Further,for subproblem II as defined above,we supply a construction of a circuit size that is of a linear size,and it too does not compromise the depth compared to Valiant’s solution.A very appealing feature of this construction is that it is uniform,conditioned on a reasonable assumption about the existence of good enough expander graphs. To this end we introduce a connection between this circuit complexity question and another domain,namely message passing algorithms.The depth we achieve for the promise problem nearly matches the1954lower bound of Moore and Shannon[10].We further show how to generalize our solution to a general threshold function,and explore another optionin the tradeoffs between the different resources we use;specifically,we show that by allowing for a depth of roughly twice that of Valiant’s construction,we may get a circuit of size O n12Definitions and amplificationFor a monotone boolean function H on k inputs,we define its amplification function A H:0101 as A H p Pr H X1X k1,where X i are independent boolean random variables that are one with probability p.Valiant[15],considered the function H on four variables,which is the OR of two AND gates,H x1x2x3x4x1x2x3x4.The amplification function of H,depicted in Figure1,is A H p11p22,and has a non-trivialfixed point atβ512152.Let H k be the depth2k binary tree with alternating layers of AND and OR gates,where the root is labeled OR.Valiant’s construction uses the fact that A Hk is the composition of A H with itself k times.Therefore,H k probabilistically amplifiesβ∆β∆to βγεk∆βγεk∆,as long asγεk∆∆0.This implies that for any constantε0we can take2k33log n O1to probabilistically amplifyβΩ1nβΩ1n toε1ε,where33is any constant bigger thanαlogDefinition1.Let F be a boolean function F:01n01m,and let S01n be some subset of the inputs.We say that F deterministically amplifies p l p h to q l q h with respect to S,if for all inputs x S, the following promise is satisfied(we denote by x the number of ones in the vector x):F x q l m if x p l nF x q h m if x p h nNote that unlike the probabilistic amplification,deterministic amplification has to work for all inputs or scenarios in the given set S.From here on,whenever we simply say“amplification”we mean deterministic amplification.For an arbitrary small constantε0,the construction we give is composed of two independent phases that may be of independent interest.A circuit C1:01n01m for m O n that deterministically amplifiesβΩ1nβΩ1n toδ1δfor an arbitrarily small constantδ0.This circuit has size O n3and depth αεlog n O1.A circuit C2:01m01,such that C2x0if xδm and C2x1if x1δm,whereδ0is a sufficiently small constant.This circuit has size O m and depth2εlog m O1.Thefirst circuit C1is achieved by a simple probabilistic construction that resembles Valiant’s construction. We present two constructions for the second circuit,C2.Thefirst construction is probabilistic;the second construction is a simulation of a logarithmic number of rounds of a certain message passing algorithm on a good bipartite expander graph.The correctness is based on the analysis of a similar algorithm used to decode a low density parity check code(LDPC)on the erasure channel[3].Combining the two circuits together yields a circuit C:01n01for theβn-th threshold function. The circuit is of size O n3and depthα22εlog n O1.3Monotone circuits for MajorityIn this section we give a randomized construction of the circuit C:01n01such that C x is one if the portion of ones in x is at leastβn and zero otherwise.The circuit C has size O n3and depth2αεlog n O1for an arbitrary small constantε0.As we described before,we will describe C as the compositions of the circuits C1and C2whose parameters are given by the following two theorems: Theorem2.For everyεεc0,there exists a circuit C1:01n01m for m O n,of size O n3and depthαεlog n O1that deterministically amplifies all inputs fromβc nβc n toε1ε. Theorem3.For everyε0,there existsε0and a circuit C2:01n01,of size O n and depth 2εlog n O1that deterministically amplifies all inputs fromε1εto01.The two circuits use a generalization of the four input function H used in Valiant’s construction.For any integer d2,we define the function H d on d2inputs as the d-ary OR of d d-ary AND gates,i.e d i1d j1 x i j.Note that Valiant’s function H is just H2.Each of the circuits C1and C2is a layered circuit,where layer zero is the input,and each value at the i-th layer is obtained by applying H d to d2independently chosen inputs from layer i 1.However,the valuesof d we choose for C1and C2are different.For C1we have d2,while for C2we choose sufficiently large d dεto meet the depth requirement of the circuit.We let F n m F denote a random circuit mapping n inputs to m outputs,where F is afixed monotone boolean circuit with k inputs,and each of the m output bits is calculated by applying F to k independently chosen random inputs.We start with a simple lemma that relates the deterministic amplification properties of F to the probabilistic amplification function A F.1Lemma4.For anyεδ0,the random function F deterministically amplifies p l p h to A F p l1δA F p h1δwith respect to S01n with probability at least1ε,if:log S log1εmΩΘγ2εi1c nβγεγ2εi1c nThat is,we can chooseδas an increasing geometric sequence,starting fromΘ1n for i1,up toΘ1 for i logγ2εn.The implied layer size for error probability2n(which is much better than we need),is Θnδ2.Therefore,it decreases geometrically fromΘn3down toΘn.It is not difficult to see that after achieving the desired amplification fromβc n toβ∆0,only a constant number of layers is needed to get down toε.The corresponding value ofδin these last steps is a constant (that depends onε),and therefore,the required layer sizes are allΘn.Proof of Theorem3.The circuit C2is a composition of F n m1H d F m1m2H dF mt1m t H d,where d andthe layer sizes n m0m1m t1are suitably chosen parameters depending onε.We prove that with high probability such a circuit deterministically amplifies all inputs fromε1εto01.As before,we restrict our attention to the lower end of the promise problem and prove that C2outputs zero on all inputs with portion of ones smaller thanε.As in the circuit C1,the layer sizes must be sufficiently large to allow accurate computation.However, for the circuit C2,accurate computation does not mean that the portion of ones in each layer is close to its expected value.Rather,our aim is to keep the portion of ones bounded by afixed constantε,while making each layer smaller than the preceding one by approximately a factor of d.We continue this process until the layer size is constant,and then use a constant size circuit tofinish the computation.Therefore,since the number of layers of such a circuit is about log n log d,and the depth of the circuit for H d is2log d,the total depth is about2log n for large d.By the above discussion,it suffices to prove the following:For everyε0there exists a real number δ0and two integers d n0,such that for all n n0the random circuit F n m H d with m1εn d, deterministically amplifiesδtoδwith respect to all inputs,with failure probability at most1n.Since A Hδ11δd d dδd,the probability of failure for any specific input with portion of ones at most δ,is bounded by:mδmA Hδδm eamplification method to analyze the performance of a belief propagation message passing algorithm for decoding low density parity check(LDPC)codes.Today the use of belief propagation for decoding LDPC codes is one of the hottest topics in error correcting codes[9,14,13].Let G V L V R;E be a d regular bipartite graph with n vertices on each side,V L V R n.Consider the following message passing algorithm,where we think of the left and right as two players.The left player “plays AND”and the right player“plays OR”.At time zero the left player starts by sending one boolean message through each left to right edge,where the value of the message m uv from u V L to v V R is the input bit x u.Subsequently,the messages at time t0are calculated from the messages at time t 1.At odd times,given the left to right messages m uv,the right player calculates the right to left messages m vw, from v V R to w V L by the formula m vw u N v w m uv.That is,the right player sends a1along the edge from v V R to w V L if and only if at least one of the incoming messages/values(not including the incoming message from w)is1.Similarly,at even times the algorithm calculates the left to right messages m vw,v V L,w V R,from the right to left messages m uv,by the formula m vw u N v w m uv.That is,the left player sends a1along the edge from v V L to w V R if and only if all of the incoming messages/values (not including the incoming message from w)are1.We further need the following definitions.We call a left vertex bad at even time t if it transmits at least one message of value one at time t.Similarly,a right vertex is bad at odd time t if it is a right vertex that transmits at least one message of value zero at time t.We let b t be the number of bad vertices at time t.These definitions will be instrumental in providing a potential function measuring the progress of the message passing algorithm which is expressed in Lemma5.We say that a bipartite graph G V L V R;E isλe-expanding,if for any vertex set S V L(or S V R)of size at mostλn,N S e S.It will be convenient to denote the expansion of the set S by e S N S S. Lemma5.Consider the message passing algorithm using a d4regular expander graph with d1e d12.If b tλn d2then b t2b tη,whereηd1d1ηt and so b2t10for t log a d2d e gets,and the better the time guarantee above gets.How good are the expanders that we may use?One can show the existence of such expanders for sufficiently large d large,and e d c for an absolute constant c.The best known explicit construction that gets close to what we need,is the result of[4].However,that result does not suffice here for two reasons.Thefirst is that it only achieves expansion1εd for anyε0 and sufficiently large d depending onε.The second is that it only guarantees left-to-right expansion,while our construction needs both left-to-right and right-to-left expansion.We refer the reader to the survey[6] for further reading and background.For such expanders,ηd1d1log d1log d1iterations,all mes-sages contain the right answer,whereεcan be made arbitrarily small by choosing sufficiently large d.It remains to convert the algorithm into a monotone circuit,which introduces a depth-blowup of log d1 owing to the depth of a binary tree simulating a d1-ary gate.Thus we get a2εlog n-depth circuit for arbitrarily smallε0.The size is obviously dn depth O n log n.To get a linear circuit,further work is needed,which we now describe.The idea is to use a sequence of graphs G 0G G 1,where each graph is half the size of its preceding graph,but has the same degree and expansion parameters.We start the message passing algorithm using the graph G G 0,and every t 0rounds (each round consists of OR and then AND),we switch to the next graph in the sequence.Without the switch,the portion of bad vertices should decrease by a factor of ηt 0,every t 0rounds.We argue that each switch can be performed,while losing at most a constant factor.To describe the switch from G i to G i 1,we identify V L G i 1with an arbitrary half of the vertices V L G i ,and start the message passing algorithm on G i 1with the left to right messages from each vertex in V L G i 1,being the same as at the last round of the algorithm on G i .As the number of bad left vertices cannot increase at a switch,their portion,at most doubles.For the right vertices,the exact argument is slightly more involved,but it is clear that the portion of bad right vertices in the first round in G i 1,increases by at most a constant factor c ,compared with what it should have been,had there been no switch.(Precise calculation,yields c 2d η.)Therefore,to summarize,as the circuit consists of a geometrically decreasing sequence of blocks starting with a linear size block,the total size is linear as well.As for the depth,the amortized reduction in the portion of bad vertices per round,is by a factor of ηηc 1t 0.Therefore,the resulting circuit is only deeper than the one described in the previous paragraph,by a factor of log ηlog η.By choosing a sufficiently large value for t 0,we obtain:Theorem 6.For any ε0,there exists a 0such that for any n there exists a monotone circuit of depth 2εlog n O 1and size O n that solves a-promise problem.We note here that O log n depth monotone circuits for the a -promise problem can also be obtained from ε-halvers.These are building blocks used in the AKS network.However,our monotone circuits for the a -promise problem have two advantages.First,our algorithm relates this classical problem in circuit com-plexity to recent popular message passing algorithms.And second,the depth that we obtain is nearly ly,Moore and Shannon [10]prove that any monotone formula/circuit for majority requires depth 2log n O 1,and the lower bound holds for the a -promise problem as well.Proof of Lemma 5.(based on Burshtein and Miller [3])We consider only the case of bad left vertices.The proof for bad right vertices follows from the same proof,after exchanging ones with zeroes,ANDs with ORs,and lefts with rights.Let B V L be the set of bad leftvertices,and assume Bλd 2at some even time t and B the set of bad vertices at time t 2.We bound the size of B by considering separately B B and B B .Note that all sets considered in the proof have size at most λn ,and therefore expansion at least e.N(B’)To bound B B ,consider the set Q N B B N B N B B N B .Since vertices in Q are not adjacent to B ,then at time t 1they send right to left messages valued zero.On the other hand,any vertex in B B can receive at most one such zero message (otherwise all its messages at time t 2will be valuedzero and it cannot be in B).Therefore,since each vertex in Q must have at least one neighbour in B B,it follows that Q B B.Therefore,we have:N B B N B Q N B B B e B B B BOn the other hand,N B B e B B e B B B.Combining the above two inequalities,we obtain:B B e Be2B B1d12B(2) Combining inequalities(1)and(2)we get that:B B e B ed12Since e d12,and e B e,this yields the required bound:B B2d e d1As noted before in Section2,replacing the last2log n layers of Valiant’s tree with2log r n layers of r-ary AND/OR gates,results in an arbitrarily small increase in the depth of the corresponding formula for a large value of r.It is interesting to compare the expected behavior of the suggested belief-propagation algorithm to the behavior of the d1-ary tree.Assume that the graph G is chosen at random(in theconfiguration model),and that the number of rounds k is sufficiently small,d12k n.Then,almost surely the computation of all but o1fraction of the k-th round messages is performed by evaluating a d1-ary depth k trees.Moreover,introducing an additional o1error,one may assume that the leaves are independently chosen boolean random variables that are one with probability p,where p is the portion of ones in the input.This observation sheds some light on the performance of the belief propagation algorithm. However,our analysis proceeds far beyond the number of rounds for which a cycle free analysis can be applied.4Monotone formulas for threshold-k functionsConsider the case of the k-th threshold function,T k n,i.e.a function that is one on x01n if xk1and zero otherwise.We show that,by essentially the same techniques of Section3,we can construct monotone circuits to this more general problem.We assume henceforth that k n2,since otherwise, we construct the circuit T n1k n and switch AND with OR gates.For k nΘ1,the construction yields circuits of depth53log n O1and size O n3.However,when k o n,circuits are shallower and smaller (this not surprising fact is also discussed in[2]in the context of formulas).The construction goes as follows:(i)Amplify k n k1n toβΩ1kβΩ1k by randomly applying to the input a sufficiently large number of OR gates with arityΘn k(ii)AmplifyβΩ1kβΩ1k to O11O1using a variation of phase I,and(iii)Amplify O11O1to01using phase II.We now give a detailed description.For the sake of the section to follow,we require the following lemma which is more general than is needed for the results of this section.Lemma7.Let S01n,andε0.Then,for any k,there is a randomized construction of a monotone circuit that evaluates T k n correctly on all inputs from S and hasdepth log n23log k2εloglog S O1size O log S k nHere k min k n1k,and the constants of the O depend only onε.Proof.Let s log S,and let i be the OR function with arity i.Then An kk n11k n n k,while An k k1n11k1n n k.Hence An kk n is a constant bounded from zero andone.We further notice thatAn k k1nΘ1kIt is not hard to see that we can pick a constantρso that Aρn k knβΩ1k.Therefore,ρn k probabilistically amplify k n k1n toβΩ1kβΩingLemma4withδΘ1k and m sk2we get that F n mρn k amplifies k n k1n toβΩ1kβΩ1k with arbitrarily high probability.The depth required to implement the above circuit is log n k and the size is O skn.Next we apply a slight modification of phase I.The analysis there remains the same except that the starting point is separation guarantee ofΩ1k instead ofΩ1n,and log S is s instead of n.This leads to a circuit of depthαεlog k O1and of size O sk2,for an arbitrarily small constantε0.Also,we note that the output of this phase is of sizeΘs.Finally,we apply phase II,where the number of inputs isΘs instead ofΘn,to obtain an amplification from O11O1to01.This requires depth2εlog s O1and size O s,for an arbitrarily small constantε0.To guarantee the correctness of a monotone circuit for T n k,it suffices to check its output on inputs of weight k k1(as the circuit is monotone).Therefore,S n k n k1,implying that log S O k log n k. Therefore,we have:Theorem8.There is a randomized construction of a monotone circuit for T k n with:depth log n43log k O loglog n ksize O k2n log n kwhere k min k n1k,and the constants of the O are absolute.5Reducing the circuit sizeThe result obtained so far for the majority,is a monotone circuit of depth53log n O1and size O n3.In this section,we would like to obtain smaller circuit size,at the expense of increasing the depth somewhat. The crucial observation is that the size of our circuit depends linearly on the logarithm of the number of scenarios it has to handle.Therefore,applying a preprocessing stage to reduce the wealth of scenarios may save up to a factor of n in the circuit size.We propose a recursive construction that reduces the circuit size to about n1We chooseαi2σi1to equate1αiσi with3αi.This implies thatσi132σi1,and δi153δi22σi1,resulting in the following sequence:iαiσiδi2,and the sequence of δi tends to129896.Therefore,we have:Theorem9.There is a randomized construction of a monotone circuit for the majority of size n1There are two central open problems related to this work.First,is the promise version really simpler than majority?A lower bound greater than2log n on the communication complexity of mMaj-search would settle this question.Boppana[2]and more recent work[5]show lower bounds on a particular method for obtaining monotone formulas for majority.However we are asking instead for lower bounds on the size/depth of unrestricted monotone formulas/circuits.Secondly,the original question remains unresolved. Namely,we would like to obtain explicit uniform formulas for majority of optimal or near optimal size.A related problem is to come up with a natural(top-down)communication complexity protocol for mMaj-Search that uses O log n many bits.References[1]M.Ajtai,J.Koml´o s,and E.Szemer´e di.Sorting in c log n parallel binatorica,3(1):1–19,1983.[2]R.B.Boppana.Amplification of probabilistic boolean formulas.IEEE Symposium on Foundations ofComputer Science(FOCS),pages20–29,1985.[3]D.Burshtein and ler.Expander graph arguments for message-passing algorithms.IEEE Trans.Inform.Theory,47(2):782–790,2001.[4]M.Capalbo,O.Reingold,S.Vadhan,and A.Wigderson.Randomness conductors and constant-degreeexpansion beyond the degree2barrier.In Proceedings34th Symposium on Theory of Computing, pages659–668,2002.[5]M.Dubiner and U.Zwick.Amplification by read-once formulas.SIAM put.,26(1):15–38,1997.[6]S.Hoory,N.Linial,and A.Wigderson.Expander graphs and their applications.survey article toappear in the Bulletin of the AMS.[7]Mauricio Karchmer and Avi Wigderson.Monotone circuits for connectivity require super-logarithmicdepth.In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing,pages539–550,Chicago,IL,May1988.[8]M.Luby,M.Mitzenmacher,and A.Shokrollahi.Analysis of random processes via and-or tree evalu-ation.In ACM-SIAM Symposium on Discrete Algorithms(SODA),1998.[9]M.Luby,M.Mitzenmacher,A.Shokrollahi,and D.A.Spielman.Analysis of low density codes andimproved designs using irregular graphs.ACM Symposium on Theory of Computing(STOC),1998.[10]E.F.Moore and C.E.Shannon.Reliable circuits using less reliable relays.I,II.J.Franklin Inst.,262:191–208,281–297,1956.[11]M.S.Paterson.Improved sorting networks with O log N depth.Algorithmica,5(1):75–92,1990.[12]M.S.Paterson,N.Pippenger,and U.Zwick.Optimal carry save networks.In Boolean functioncomplexity(Durham,1990),volume169of London Math.Soc.Lecture Note Ser.,pages174–201.Cambridge Univ.Press,Cambridge,1992.[13]T.Richardson and R.Urbanke.Modern coding theory.Draft of a book.[14]T.Richardson and R.Urbanke.The capacity of low-density parity-check codes under message-passingdecoding.IEEE rm.Theory,47(2):599–618,2001.[15]L.G.Valiant.Short monotone formulae for the majority function.J.Algorithms,5(3):363–366,1984.。