DIMACS Series in Discrete Mathematics and Theoretical Computer Science On the Number of Con

Abstract. The notion of relative closure (X, Y)0 of a semi-Pfaffian couple (X, Y) was introduced by Gabrielov to give a description of the o-minimal structure generated by Pfaffian functions. In this paper, an effective bound is given for the number of con

DIMACSSeriesinDiscreteMathematics

andTheoreticalComputerScience

OntheNumberofConnectedComponentsoftheRelative

ClosureofaSemi-Pfa anFamily

AndreiGabrielovandThierryZell

Abstract.Thenotionofrelativeclosure(X,Y)0ofasemi-Pfa ancouple

(X,Y)wasintroducedbyGabrielovtogiveadescriptionoftheo-minimal

structuregeneratedbyPfa anfunctions.Inthispaper,ane ectivebound

isgivenforthenumberofconnectedcomponentsof(X,Y)0intermsofthe

Pfa ancomplexityofXandY.

Introduction

Pfa anfunctionsarerealanalyticfunctionsthataresolutionstocertaintrian-gularsystemsofpolynomialpartialdi erentialequations(seeDe nition1).TheywereintroducedbyKhovanski [12],whoshowedthatthesetranscendentalfunc-tionsexhibit,intherealdomain,global nitenesspropertiessimilartotheproper-tiesofpolynomials.Itfollowsinturnthatthegeometricalandtopologicalcharac-teristicsofsetsde nedusingPfa anfunctionsarealsowellcontrolled.E ectiveupperboundsforthosegeometricpropertiescanbefoundin[3,5,7,8,18,22].

O-minimalityisanaturalframeworkforthestudyofPfa anfunctions.(ThereadercanrefertovandenDries[2]forde nitions.)Wilkieprovedin[21]thatthestructuregeneratedbyPfa anfunctionsiso-minimal(seealso[9,19]forgeneralizationsofthisresult.)

In[6],Gabrielovintroducedthenotionofrelativeclosureofasemi-Pfa ancouple,asanalternativetoWilkie’sconstruction.Inthisway,heobtainedano-minimalstructureinwhichde nablesets(calledlimitsets)haveasimplepresen-tation.Asaresult,thisstructuresupportsanotionofcomplexitywhichnaturallyextendstheusualPfa ancomplexity,andallowsonetoestimatethecomplexityofBooleanoperationsinthatstructure.

Inthispaper,weusethisnotionofcomplexitytogiveanexplicitboundonthenumberofconnectedcomponentsofalimitset.Inthe rstpart,werecalltheusualde nitionsrelatedtoPfa anfunctions,thenwecovertheessentialmaterialwewillusefrom[6].Inthesecondpart,wegiveexplicitboundsforthesmoothcase(Theorem15)andforthegeneralcase(Theorem17).Section3isdevotedtotwoapplicationstothefewnomialcase:Theorem19andTheorem20.

Abstract. The notion of relative closure (X, Y)0 of a semi-Pfaffian couple (X, Y) was introduced by Gabrielov to give a description of the o-minimal structure generated by Pfaffian functions. In this paper, an effective bound is given for the number of con

2ANDREIGABRIELOVANDTHIERRYZELL

Notations.IfXisasubsetofRn,we’lldenotebyX\Xitsfrontier.Unlessotherwisenoted,allsubsetsXareassumedtoberelativelycompact.

1.Semi-Pfa ansetsandrelativeclosure

Wewillrecallinthissectiontheusualde nitionsofPfa anfunctionsandsemi-Pfa ansetsasgivenbyKhovanski .Then,wewillde netherelativeclosureofasemi-Pfa ancouplethatappearsin[6].

Rnbeanopendomain.Thefollowing1.1.Pfa anfunctions.Let

de nitionsareduetoKhovanski [12](seealso[10,11]).

Definition1.Asequence(f1,...,f )offunctionsthatarede nedandana-

iscalledaPfa anchainifitsatis esonadi erentialsystemofthelyticin

form:

(1)dfi=n

j=1Pi,j(x,f1(x),...,fi(x))dxj,

whereeachPi,jisapolynomialinx,f1,...,fi,andthefollowingholds.

(P1)ThegraphΓioffiiscontainedinadomain ide nedbypolynomialin-

equalitiesin(x,f1(x),...,fi 1(x),t),andsuchthat Γi i.

(P2)Γiisaseparatingsubmanifoldin i,i.e. i\Γiisadisjointunionoftwo opensets +iand i.(See[12,p.38].ThisisalsocalledtheRolleleaf

conditionintheterminologyof[14,15].)

Ifα∈NisaboundonthedegreesofthepolynomialsPi,j,wesaythatthedegreeofthechainis(atmost)α.Theinteger iscalledthelengthofthechain.

APfa anfunctionq(x)withthechain(f1,...,f )isanyfunctionthatcanbewrittenas

q(x)=Q(x,f1(x),...,f (x)),

forsomepolynomialQ(x,y1,...,y ).IfthedegreeofQisβ,wesaythatthedegreeofthefunctionq(x)is(atmost)β.

Example2.Foranya=(a1,...,an)∈Rnthefunctionea:x→exp(a·x)isaPfa anfunctiononRn,since

dea(x)=n

j=1ajea(x)dxj.

Pfa anfunctionsformaratherlargeclassoffunctions.NoteinparticularthatelementaryfunctionscanbeseenasPfa anfunctionsonappropriatesubsetsoftheirdomainofde nition(seetheChapter1of[12]or[7]formoreprecisestatements).

tobeoftheformRn,Rn 1×R+,or(R+)n.Insections2and3,wewilltake

Inthatcase,wewillusethefollowingresultwhichisduetoKhovanski [12,p.79].Thereadercanalsorefertotherevisededition(inRussian)[13].

Abstract. The notion of relative closure (X, Y)0 of a semi-Pfaffian couple (X, Y) was introduced by Gabrielov to give a description of the o-minimal structure generated by Pfaffian functions. In this paper, an effective bound is given for the number of con

NUMBEROFCONNECTEDCOMPONENTSOFTHERELATIVECLOSURE...3Theorem3.Let(f1,...,f )beaPfa anchainon,whereisoneofRn,Rn 1×R+,or(R+)n.Ifq1,...,qnarePfa anfunctionsofrespectivedegreesβi,thenumberofsolutionsofthesystem

q1(x)=···=qn(x)=0,

forwhichtheJacobiandeterminantisnotzeroisboundedby

(2)2 ( 1)/2β1···βn[β1+···+βn n+min(n, )α+1] .

isnotRemark.Itispossibletogivee ectiveestimateswhenthedomain

oftheaboveform,butonehastomodifytheestimatestotakeintoaccountthecomplexityofthedomain.

1.2.Semi-Pfa ansets.Let(f1,...,f )beaPfa anchainofdegreeα,

Rn.de nedonadomain

Definition4.Abasicsemi-Pfa ansetisasetXoftheform:

(3)X={x∈| i(x)=0,ψj(x)>0,fori=1,..,I;j=1,..,J},

whereallthefunctionsabovearePfa anwiththechain(f1,...,f ).Ifallthesefunctionshavedegreeatmostβ,thesetXissaidtohaveformat(I,J,n, ,α,β).

Asemi-Pfa ansetisany niteunionofbasicsemi-Pfa ansets.Asemi-Pfa ansethasformat(N,I,J,n, ,α,β)ifitistheunionofatmostNbasicsemi-Pfa ansetshavingformatscomponent-wisenotexceeding(I,J,n, ,α,β).

Wesaythatasemi-Pfa ansetXisrestrictedifitisrelativelycompactin.Definition5.Abasicsemi-Pfa ansetiscalled(e ectively)non-singularifforallx∈X,thefunctions iappearingin(3)verify

d 1(x)∧···∧d I(x)=0.

1.3.E ectiveboundsontheBettinumbers.FollowingideasofOle nik-Petrovski [17],Milnor[16]andThom[20]foralgebraicvarieties,wecanusetheboundappearinginTheorem3toestimatethesumoftheBettinumbersofasemi-Pfa anset[12,22].

AssumeXisacompactsemi-Pfa ansetde nedonlybyequations,

(4)X={x∈Rn|p1(x)=···=pr(x)=0},

2andletp=p21+···+pr.Then,itcanbeshownthatthesumoftheBettinumbers

ofXisexactlyone-halfthesumoftheBettinumbersofthecompactcomponentsoftheset{p=ε},whereεisasmallpositiverealnumber.

Countingthenumberofcriticalpointsofagenericprojection,weobtainthefollowingbound.

Corollary6.AssumeX Rnisoftheform(4),wherep1,...,prareof

=RnwithalengthdegreeatmostβinaPfa anchain(f1,...,f )de nedin

anddegreeα.Then,thesumoftheBettinumbersofXisboundedby

(5)2 ( 1)/2β(α+2β 1)n 1[(2n 1)β+(n 1)(α 2)+min(n, )α] .

Abstract. The notion of relative closure (X, Y)0 of a semi-Pfaffian couple (X, Y) was introduced by Gabrielov to give a description of the o-minimal structure generated by Pfaffian functions. In this paper, an effective bound is given for the number of con

4ANDREIGABRIELOVANDTHIERRYZELL

1.4.Relativeclosure.¿Fromnowon,weconsidersemi-Pfa ansubsetsofR×R+witha xedPfa anchain(f1,...,f )inadomain.Wewrite(x1,...,xn)forthecoordinatesinRnandλforthelastcoordinate(whichwethinkofasapa-rameter.)IfXissuchasubset,weletXλ={x|(x,λ)∈X} RnandconsiderXasthefamilyofits bersXλ.ˇ=WeletX+=X∩{λ>0}andXn

Y)+=Y+;

( X)+ Y.

Then,theformatofthecouple(X,Y)isthecomponent-wisemaximumofthefor-matsofthefamiliesXandY.

Definition9.Let(X,Y)beasemi-Pfa ancouplein

ativeclosureof(X,Y)atλ=0by

ˇ\Yˇ ˇ.(6)(X,Y)0=X.Wede netherel-

Definition10.Let Rnbeanopendomain.Alimitsetin isasetoftheform(X1,Y1)0∪···∪(XK,YK)0,where(Xi,Yi)aresemi-Pfa ancouplesre-spectivelyde nedindomainsi Rn×R+,suchthatˇi= for1≤i≤K.Iftheformatsofthecouples(Xi,Yi)areboundedcomponent-wiseby(N,I,J,n, ,α,β),wesaythattheformatofthelimitsetis(K,N,I,J,n, ,α,β).

Example11.Any(notnecessarilyrestricted)semi-Pfa ansetXisalimitset.

oftheform(3).Proof.ItisenoughtoprovetheresultforabasicsetX

n={x∈R|gi(x)>0,1≤i≤r}.Letψ=ψ1···ψJandg=g1···gr.Assume

De nethesets W=(x,λ)∈X×Λ|g(x)>λ,|x|<λ 1; ×Λ| 1(x)=···= I(x)=0,ψ(x)=0,g(x)≥λ,|x|≤λ 1;Y1=(x,λ)∈ ×Λ| 1(x)=···= I(x)=0,g(x)=λ,|x|≤λ 1;Y2=(x,λ)∈ ×Λ| 1(x)=···= I(x)=0,g(x)≥λ,|x|=λ 1;Y3=(x,λ)∈

whereΛ=(0,1].IfY=Y1∪Y2∪Y3,itisclearthat(W,Y)satis estherequirementsofDe nition8.Thus(W,Y)isasemi-Pfa ancouple;itsrelativeclosureisX.

Foralln∈NweletSnbethecollectionoflimitsetsinRn,andS=∪n∈NSn.Thefollowingtheoremsumsuptheresultsin[6,Theorems2.9and5.1].

Abstract. The notion of relative closure (X, Y)0 of a semi-Pfaffian couple (X, Y) was introduced by Gabrielov to give a description of the o-minimal structure generated by Pfaffian functions. In this paper, an effective bound is given for the number of con

NUMBEROFCONNECTEDCOMPONENTSOFTHERELATIVECLOSURE...5Theorem12.ThestructureSiso-minimal.Moreover,ifXisade nablesetde nedbyaformulainvolvingthelimitsetsL1,...,LN,Xcanbepresentedasalimitsetwhoseformatisboundedbyane ectivefunctionoftheformatsofL1,...,LN.

2.Connectedcomponentsofalimitset

Inthissection,weestablishe ectiveboundsonthenumberofconnectedcom-ponentsoftherelativeclosureofasemi-Pfa ancouple(X,Y).Inwhatfollows,wewillalwaysassumethatYisnotempty.NotethatifYisempty,itfollowsfromDe nition8that( X)+mustbeemptytoo;then,XλiscompactandthenumberofconnectedcomponentsofX0isatmostthenumberofconnectedcomponentsofXλ.E ectiveboundsforthiscaseappearin[12,22].

Asannouncedintheintroduction,weassumeasin[6]thatXandYarerelativelycompact.Tokeeptheestimatessimple,we’llalsoassumethatthePfa anchain(f1,...,f )isde nedoverthewholeofRn×R+,sothattheboundgiveninTheorem3isapplicable.

2.1.Generalconsiderations.Weshowherehowtoreducetheproblemofcountingthenumberofconnectedcomponentsofalimitsettoaprobleminthesemi-Pfa ansetting.

LetΦbethe(squared)distancefunctiononRn×Rn:

Φ:Rn×Rn →R(7)(x,y)→|x y|2

Foranyλ>0,wecande nethedistancetoYλ,ΨλonXλby:

(8)Ψλ(x)=minΦ(x,y).y∈Yλ

ˇ:De nesimilarlyforx∈X

(9)Ψ(x)=minΦ(x,y).ˇy∈Y

Thefollowingresultappearsin[6,Theorem2.12].Theproofispresentedhereforthesakeofself-containment.

Theorem13.Let(X,Y)beasemi-Pfa ancouple.Then,thereexistsλ 1suchthatforeveryconnectedcomponentCof(X,Y)0,wecan ndaconnectedcomponentDλofthesetoflocalmaximaofΨλsuchthatDλisarbitrarilycloseto

C.

Proof.LetCbeaconnectedcomponentof(X,Y)0.Notethatbyde nitionˇSowemusthaveΦ(x,y)>0oftherelativeclosure,ifxisinC,itcannotbeinY.ˇ,andsinceYˇiscompact,wemusthaveΨ(x)>0.Also,anypointinforally∈Yˇ,henceΨ| C≡0.ˇbutnotin(X,Y)0.Sowemusthave C Y CmustbeinX,

ThismeansthattherestrictionofΨtoCtakesitsmaximuminsideofC.

Choosex0∈C,andletc=Ψ(x0)>0.Forasmallλ,thereisapointxλ∈Xλclosetox0suchthatcλ=Ψλ(xλ)isclosetoc,andisgreaterthanthemaximumofthevaluesofΨλoverpointsofXλcloseto C.Hencetheset{x∈Xλ|Ψλ(x)≥cλ}isnonempty,andtheconnectedcomponentAλofthissetthatcontainsxλisclosetoC.Thereexistsalocalmaximumx λ∈AλofΨλ.IfDλistheconnectedcomponentinthesetoflocalmaximaofΨλ,itiscontainedinZλandisclosetoC.

Abstract. The notion of relative closure (X, Y)0 of a semi-Pfaffian couple (X, Y) was introduced by Gabrielov to give a description of the o-minimal structure generated by Pfaffian functions. In this paper, an effective bound is given for the number of con

6ANDREIGABRIELOVANDTHIERRYZELL

2.2.Aboundforthesmoothcase.WewillnowshowhowthenumberofconnectedcomponentsofthesetoflocalmaximaofΨλthatappearinTheorem13canbeestimatedwhenthesetsXλandYλaresmooth.

De neforallp,

(10)

where

(11)p={(x,y0,...,yp)∈Xλ×(Yλ)p+1|yi=yj,0≤i<j≤p}.Wλpp={(x,y0,...,yp)∈Wλ|Φ(x,y0)=···=Φ(x,yp)},Zλ

Lemma14.Assume(X,Y)isaPfa ancouplesuchthatXλandYλaresmoothforallλ>0.Foragivenλ>0,letx bealocalmaximumofΨλ(x).p ,...,yp)∈ZλsuchThen,thereexists0≤p≤dim(Xλ)andapointz =(x ,y0ppthatZλissmoothatz ,andz isacriticalpointofΦ(x,y0)onZλ.

∈YλProof.Sincex isalocalmaximumofΨλ(x),thereexistsapointy0 suchthatΦ(x,y0)=miny∈YλΦ(x,y)=Ψλ(x).Inparticular,dyΦ(x,y)=0at ).If(x ,y0)isacriticalpointofΦ(x,y)(thisisalwaysthecase(x,y)=(x ,y0 )=0atwhendim(Xλ)=0)thestatementholdsforp=0.OtherwisedxΦ(x,y0 )(ξ)>0.x=x .LetξbeatangentvectortoXatx suchthatdxΦ(x ,y0 Assumethatforally∈YλsuchthatΦ(x,y)=Ψλ(x),wehavedxΦ(x,y)(ξ)>

˙(0)=ξ.For0whenx=x .Letγ(t)beacurveonXλsuchthatγ(0)=x andγ

ally∈Yλ,thereexistsTysuchthatforall0<t<Ty,theinequalityΦ(γ(t),y)>Φ(x ,y)holds.BycompactnessofYλ,thismeanswecan ndsometsuchthatthatinequalityholdsforally∈Yλ.Hence,Ψλ(γ(t))>Ψλ(x ),whichcontradictsthehypothesisthatΨλhasalocalmaximumatx . ∈YλsuchSincex isalocalmaximumofΨλ(x),thereexistsapointy1 =thatdxΦ(x,y1)(ξ)≤0atx=xandΦ(x,y1)=Ψλ(x).Inparticular,y1 y0,dyΦ(x,y)=0aty=y1,anddxΦ(x,y1)=dxΦ(x,y0)atx=x.This 11 ,y1)∈Zλ,andZλissmoothat(x ,y0,y1).If(x ,y0,y1)isimpliesthat(x ,y01acriticalpointofΦ(x,y0)onZλ(thisisalwaysthecasewhendim(Xλ)=1) )anddxΦ(x,y1)arelinearlythestatementholdsforp=1.OtherwisedxΦ(x,y0 independentatx=x.Sincedim(Xλ)≥2,thereexistsatangentvectorξtoXλ atx suchthatdxΦ(x ,y0)(ξ)>0anddxΦ(x ,y0)(ξ)>0.Sincex isalocal ∈YλsuchthatdxΦ(x,y2)(ξ)≤0atmaximumofΨλ(x),thereexistsapointy2 22isx=xandΦ(x,y2)=Ψλ(x).Thisimpliesthat(x,y0,y1,y2)∈Zλ,andZλ 23smoothat(x,y0,y1,y2).TheaboveargumentscanberepeatednowforZλ,Zλ,etc.,toprovethestatementforallp≤dim(Xλ).

AssumenowthatXλandYλaree ectivelynon-singular,i.e.theyareofthefollowingform:

(12)Xλ={x∈Rn|p1(x,λ)=···=pn d(x,λ)=0};

Yλ={y∈Rn|q1(y,λ)=···=qn k(y,λ)=0};

where,forallλ>0,weassumethatdxp1∧···∧dxpn d=0onXλandthatdyq1∧···∧dyqn k=0onYλ.Inparticular,wehavedim(Xλ)=danddim(Yλ)=k.Remark.Notethatweassumethatnoinequalitiesappearin(12).WecanclearlymakethatassumptionforYλ,sincethatsethastobeclosedforallλ>0.ForXλ,p,thecriticalsetofweobservethefollowing:ifCisaconnectedcomponentofCλ

Abstract. The notion of relative closure (X, Y)0 of a semi-Pfaffian couple (X, Y) was introduced by Gabrielov to give a description of the o-minimal structure generated by Pfaffian functions. In this paper, an effective bound is given for the number of con

NUMBEROFCONNECTEDCOMPONENTSOFTHERELATIVECLOSURE...7p,thefunctionΦisconstantonC.IfCcontainsalocalmaximumforΨ,itΦ|Zλλcannotmeet Xλbecause Xλ Yλ.Hence,wedonotneedtotakeintoaccounttheinequalitiesappearinginthede nitionofXλ.

Letusnowde neforallp,

(13)θp:(y0,...,yp)∈(Yλ)p+1→

0≤i<j≤p|yi yj|2.

parede nedforallpbythefollowingThen,forXλandYλasin(12),thesetsZλconditions. p1(x,λ)=···=pn d(x,λ)=0;

(14)q1(yi,λ)=···=qn k(yi,λ)=0,0≤i≤p; Φ(x,yi) Φ(x,yj)=0,0≤i<j≤p;

andtheinequality

(15)θp(y0,...,yp)>0.

Underthesehypotheses,weobtainthefollowingbound.

Theorem15.Let(X,Y)beasemi-Pfa ancouplesuchthatforallsmallλ>0,XλandYλaree ectivelynon-singularbasicsetsofdimensionrespectivelydandk.Iftheformatof(X,Y)is(1,I,J,n, ,α,β),thenumberofconnectedcomponentsof(X,Y)0isboundedby

(16)2d

p=02q (q 1)/2βp(α+2βp)nq 1[nq(2βp+α 2)+qmin(n, )α]q ,

whereq=p+2andβp=max{1+(n k)(α+β 1),1+(n d+p)(α+β 1)}.

Proof.AccordingtoTheorem13,wecanchoseλ>0suchthatforanyconnectedcomponentCof(X,Y)0,wecan ndaconnectedcomponentDλofthesetoflocalmaximaofΨλsuchthatDλisclosetoC.Weseethatforλsmallenough,twoconnectedcomponentsCandC of(X,Y)0cannotsharethesameˇforλsmallenough.Indeed,theconnectedcomponentDλ,sinceDλcannotmeetYˇisboundedfrombelowbythedistancefromDλtoYλ,–distancefromDλtoYˇButthelatterdistancewhichisatleastcλ,–minusthedistancebetweenYλandY.

goestozero,whereastheformergoestoapositiveconstantcwhenλgoestozero.

Oncethatλis xed,allweneedtodoisestimatethenumberofconnectedcomponentsofthesetoflocalmaximaofΨλ.AccordingtoLemma14,wecanpreducetoestimatingthenumberofconnectedcomponentsofthecriticalsetsCλ

pfor0≤λ≤d.oftherestrictionΦ|Zλ

Forthesakeofconcision,wewilldropλfromthenotationsinthisproof,p,pi(x)forpi(x,λ),etc...writingZpforZλ

Apointz=(x,y0,...,yp)∈ZpisinCpifandonlyifthefollowingconditionsaresatis ed: dyΦ(x,yj)=0,0≤j≤p;(17)rank(dxΦ(x,y0),...,dxΦ(x,yp))≤p.

Abstract. The notion of relative closure (X, Y)0 of a semi-Pfaffian couple (X, Y) was introduced by Gabrielov to give a description of the o-minimal structure generated by Pfaffian functions. In this paper, an effective bound is given for the number of con

8ANDREIGABRIELOVANDTHIERRYZELL

ForXλandYλasin(12),thoseconditionstranslateinto:

(18) rank{ yq1(yi),..., yqn k(yi), yΦ(x,yi)}≤n k,0≤i≤p;

rank{ xp1(x),..., xpn d(x), xΦ(x,y0),..., xΦ(x,y0)}≤n d+p.

Thoseconditionstranslateintoallthemaximalminorsofthecorrespondingmatri-cesvanishing.TheseminorsarePfa anfunctionsinthechainusedtode neXandY.Theirdegreesarerespectively1+(n k)(α+β 1)and1+(n d+p)(α+β 1).

ThenumberofconnectedcomponentsofCpisboundedbythenumberofconnectedcomponentsofthesetDpde nedbytheconditionsin(14)and(15),andthevanishingofthemaximalminorscorrespondingtotheconditionsin(18).

LetEpbethesetde nedbytheequations(14)and(18),sothatDp=Ep∩{θp>0}.Then,thenumberofconnectedcomponentsofDpisboundedbythenumberofconnectedcomponentsofEpplusthenumberofconnectedcomponentsofEp∩{θp=ε}forachoiceofε>0smallenough.

Hence,we’rereducedtotheproblemofestimatingthenumberofconnectedcomponentsoftwosemi-Pfa ansetsinRn(p+2)thatarede nedwithoutinequalitiesusingaPfa anchaininn(p+2)variablesofdegreeαandlength(p+2) .UsingtheboundsontheBettinumbersfromCorollary6,weobtain(16).

2.3.Boundsforthesingularcase.Let’sconsidernowthecasewhereXλandYλmaybesingular.Wecanusedeformationtechniquestoreducetothesmoothcase.First,thefollowinglemmashowswecanreducetothecasewhereXλisabasicset.

Lemma16.LetX1,X2andYbesemi-Pfa ansetssuchthat(X1,Y)and(X2,Y)arePfa anfamilies.Then,(X1∪X2,Y)0=(X1,Y)0∪(X2,Y)0.

Theprooffollowsfromthede nitionoftherelativeclosure.

Theorem17.Let(X,Y)beasemi-Pfa ancouple.AssumeXλandYλareunionsofbasicsetshavingaformatoftheform(I,J,n, ,α,β).IfthenumberofbasicsetsinXλisMandthenumberofbasicsetsinYλisN,thenthenumberofconnectedcomponentsof(X,Y)0isboundedby

(19)2MNn 1

p=02q (q 1)/2γp(α+2γp)nq 1[nq(2γp+α 2)+qmin(n, )α]q ,

whereq=p+2andγp=1+(p+1)(α+2β 1).

Proof.Again,wewanttoestimatethenumberoflocalmaximaofthefunctionΨλde nedin(8).

ByLemma16,wecanrestrictourselvestothecasewhereXisbasic.LetY=Y1∪···∪YN,whereallthesetsYiarebasic.Foreachbasicset,wetakethesumofsquaresoftheequationsde ningit:thecorrespondingpositivefunctions,whichwedenotebypandq1,...,qN,havedegree2βinthechain.Fixεi>0,for0≤i≤N,andλ>0,andletX={p(x,λ)=ε0}andforall1≤i≤N,letYi={qi(x,λ)=εi}.SinceYλiscompact,ifx isapointinXλsuchthatΨλhasalocalmaximumatx=x ,thereisapointy insome(Yi)λsuchthatΦ(x,y)=Ψλ(x).Then,we

Abstract. The notion of relative closure (X, Y)0 of a semi-Pfaffian couple (X, Y) was introduced by Gabrielov to give a description of the o-minimal structure generated by Pfaffian functions. In this paper, an effective bound is given for the number of con

NUMBEROFCONNECTEDCOMPONENTSOFTHERELATIVECLOSURE...9can ndacouple(x ,y )∈Xλ×(Yi)λcloseto(x ,y )suchthatΦ(x ,y )isalocalmaximumofthedistance(measuredbyΦ)fromXλto(Yi)λ.

Sinceforsmallenoughε0,...,εN,thesetsXλand(Yi)λaree ectivelynon-singularhypersurfaces,thenumberoflocalmaximaofthedistanceofXλto(Yi)λcanbeboundedby(16),forappropriatevaluesoftheparameters.Theestimate(19)follows.

3.Applicationtofewnomials

Inthissection,wewillapplyourpreviousresultstothecasewherethePfa anfunctionsweconsiderarefewnomials.

3.1.Fewnomialsandlowadditivecomplexity.Recallthatwecancon-sidertherestrictionofanypolynomialqtoanorthantasaPfa anfunctionwhosecomplexitydependsonlyonthenumberofnonzeromonomialsinq.FixK={m1,...,mr}∈Nnasetofexponents.

Definition18.ThepolynomialqisaK-fewnomialifitisoftheform:

q(x)=a0+a1xm1+···arxmr,wherea0,...,ar∈R.

Let =n+r,and(f1,...,f )bethefunctionsde nedby: 1x if1≤i≤n,i(20)fi(x)=xmi nifi>n.

Itiseasytoseethat(f1,...,f )isaPfa anchainoflength anddegreeα=2in

=(R+)n,sincewehave:thepositiveorthant

fi

S∩ .Notethatthisisindeedan

importantcase,sinceanexampleisgivenin[4]ofafewnomialsemialgebraicsetforwhichtheclosurecannotbedescribedindependentlyofthedegreesofthede ningpolynomials.

Abstract. The notion of relative closure (X, Y)0 of a semi-Pfaffian couple (X, Y) was introduced by Gabrielov to give a description of the o-minimal structure generated by Pfaffian functions. In this paper, an effective bound is given for the number of con

10ANDREIGABRIELOVANDTHIERRYZELL

3.2.Boundsforfewnomialcouples.Wenowgiveexplicitboundsinthecasewherethe bersinthesemi-Pfa ancouple(X,Y)canbothbede nedK-fewnomials,i.e.bydegree1Pfa anfunctioninachainofthetype(20).In

= ,theseboundswillparticular,ifSisasemi-algebriacsetsuchthat S∩

applytoXasin(21)andtoY={x1=λ}∪···∪{xn=λ}.

Theorem19.Let(X,Y)beasemi-Pfa ancouplede nedbydegree1func-tionsinthechain(20).Then,thefollowingboundscanbeestablishedforthenumberofconnectedcomponentsof(X,Y)0.

Case1.Ifforallλ>0,XλandYλaree ectivelynon-singularofdimensionrespectivelydandk,weobtainfrom(16)thebound

(22)d

p=02q2(n+r)2/2(4n+6)q(3n+2r)qq(n+r).

Case2.IfXandYaretheunionofrespectivelyMandNbasicsets,thenumberofconnectedcomponentsof(X,Y)0isboundedby:

(23)MNn 1

p=02q2(n+r)2/2(6n+6)q(3n+2r)qq(n+r).

Proof.TheseboundsareobtainedusingtheresultsfromTheorems15and17,withα=2,β=1and =n+r,andthenboundingverybluntlythetermsβpandγp.

3.3.Closurerelativetothefrontierofafewnomialset.LetXbeasemi-Pfa anfamilysuchthatforallλ>0,thesetXλisde nedbyK-fewnomials.Byde nitionofafamily,theset XλiscontainedinthedomainofthePfa anchain,sobytheresultsof[5],thissetisasemi-Pfa ansetde nedbyfunctionsinthechain,thatis,polynomialsoflowadditivecomplexity.Moreover,theformatof XλcanbeestimatedfromtheformatofXλ.ApplyingthoseresultstogetherwiththoseofTheorem17,wecangiveestimatesforthenumberofconnectedcomponentsof(X, X)0.

Theorem20.LetXbeasemi-Pfa anfamilyinaPfa anchainoftype(20).IftheformatofXisoftheform(N,I,J,n, =n+r,α=2,β=1),thenumberofconnectedcomponentsof(X, X)isboundedby

(24)N(I+J)2N+rO(n2)(n+r)nnO(n2+nr).

Proof.Following[5],theset Xλcanbede nedusingthesamePfa anchainasXλ,usingN basicsetsandfunctionsofdegreeatmostβ ,where,underthehypothesesabove,thefollowingboundshold.

β ≤n(n+r)O(n),N ≤N(I+J)N+rO(n)N(n+r)2rO(n).

Theboundonthenumberofconnectedcomponentsfollowsreadily.

References

[1]R.BenedettiandJ.-J.Risler.RealAlgebraicandSemi-algebraicSets.Hermann,1990.

[2]L.vandenDries.TameTopologyandO-minimalStructures.LMSLectureNoteSeries

No.248.CambridgeUniversityPress,1998.

Abstract. The notion of relative closure (X, Y)0 of a semi-Pfaffian couple (X, Y) was introduced by Gabrielov to give a description of the o-minimal structure generated by Pfaffian functions. In this paper, an effective bound is given for the number of con

NUMBEROFCONNECTEDCOMPONENTSOFTHERELATIVECLOSURE...11

[3]A.Gabrielov.MultiplicitiesofPfa anintersections,andtheL ojasiewiczinequality.Selecta

Math.(N.S.),1(1):113–127,1995.

[4]A.Gabrielov.Counter-examplestoquanti ereliminationforfewnomialandexponentialexp-

ressions.Preprint,1997.

Availableat:http://www.math.purdue.edu/~agabriel/preprint.html

[5]A.Gabrielov.Frontierandclosureofasemi-Pfa anset.DiscreteComput.Geom.,19(4):605–

617,1998.

[6]A.Gabrielov.RelativeclosureandthecomplexityofPfa anelimination.Preprint,2000.

Availableat:http://www.math.purdue.edu/~agabriel/preprint.html

[7]plexityofstrati cationsofsemi-Pfa ansets.Discrete

Comput.Geom.,14(1):71–91,1995.

[8]plexityofcylindricaldecompositionsofsub-Pfa ansets.

J.PureAppl.Algebra164:179–197,2001.

[9]M.KarpinskiandA.Macintyre,AgeneralizationofWilkie’stheoremofthecomplement,and

anapplicationtoPfa anclosure.SelectaMath.(N.S.)5(4):507–516,1999.

[10]A.G.Khovanski .Aclassofsystemsoftranscendentalequations.Dokl.Akad.NaukSSSR,

255(4):804–807,1980.

[11]A.G.Khovanski .FewnomialsandPfa manifolds.InProceedingsoftheInternationalCon-

gressofMathematicians,Vol.1,2(Warsaw,1983),pp.549–564,Warsaw,1984.PWN.

[12]A.G.Khovanski .Fewnomials.AmericanMathematicalSociety,Providence,RI,1991.Trans-

latedfromtheRussianbySmilkaZdravkovska.

[13]A.G.Khovanski .Malochleny.FAZIS,Moscow,1997.(Russian.)

[14]J.-M.LionandJ.-P.Rolin.Homologiedesensemblessemi-pfa ens.Ann.Inst.Fourier

(Grenoble)46:723–741,1996.

[15]J.-M.LionandJ.-P.Rolin.Volumes,FeuillesdeRolledeFeuilletagesanalytiquesetTh´eor`eme

deWilkie,Ann.Fac.Sci.ToulouseMath.7:93–112,1998.

[16]J.Milnor,OntheBettinumbersofrealvarieties.Proc.Amer.Math.Soc.15:275–280,1964.

[17]O.Ole nikandI.G.Petrovski .Onthetopologyofrealalgebraicsurfaces.Izv.Akad.Nauk

SSSR,13:389–402,1949.

[18]S.PericleousandN.Vorobjov.Newcomplexityboundsforcylindricaldecompositionsof

sub-Pfa ansets.Preprint,2001.

[19]P.Speissegger.ThePfa anclosureofano-minimalstructure.J.ReineAngew.Math.,

508:189–211,1999.

[20]R.Thom.Surl’homologiedesvari´et´esalg´ebriquesr´eelles.inDi erentialandCombinatorial

Topology,S.S.CairnsEd.,pp.255–265,PrincetonUniv.Press,1965.

[21]A.J.Wilkie.Atheoremofthecomplementandsomenewo-minimalstructures.SelectaMath.

(N.S.),5(4):397–421,1999.

[22]T.Zell.Bettinumbersofsemi-Pfa ansets.J.PureAppl.Algebra,139(1-3):323–338,1999.

E ectivemethodsinalgebraicgeometry(Saint-Malo,1998).

1395MathSciencesBldgWestLafayetteIN47907-1395USA

E-mailaddress:agabriel@math.purdue.edu

E-mailaddress:tzell@math.purdue.edu

本文来源：https://www.bwwdw.com/article/tl81.html