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.