Wilkie’s conjecture for restricted elementary functions

Abstract

We consider the structure $\mathbb{R}^{\mathrm{RE}}$ obtained from $(\mathbb{R},<,+,\cdot)$ by adjoining the restricted exponential and sine functions. We prove Wilkie's conjecture for sets definable in this structure: the number of rational points of height $H$ in the transcendental part of any definable set is bounded by a polynomial in $\log H$. We also prove two refined conjectures due to Pila concerning the density of algebraic points from a fixed number field, or with a fixed algebraic degree, for $\mathbb{R}^{\mathrm{RE}}$-definable sets.

Note: To view the article, click on the URL link for the DOI number.

  • [basu:book] S. Basu, R. Pollack, and M. Roy, Algorithms Real Algebraic Geometry, Second ed., New York: Springer-Verlag, 2006.
    @BOOK{basu:book, mrkey = {2248869},
      number = {10},
      author = {Basu, Saugata and Pollack, Richard and Roy, Marie-Françoise},
      mrclass = {14P10 (03C10 52C45 68Q25 68W30)},
      series = {Algorithms in Comput. Math.},
      edition = {Second},
      address = {New York},
      isbn = {978-3-540-33098-1; 3-540-33098-4},
      publisher = {Springer-Verlag},
      zblnumber = {1102.14041},
      mrnumber = {2248869},
      title = {Algorithms Real Algebraic Geometry},
      year = {2006},
      pages = {x+662},
      }
  • [bianconi:elliptic] Go to document R. Bianconi, "Model completeness results for elliptic and abelian functions," Ann. Pure Appl. Logic, vol. 54, iss. 2, pp. 121-136, 1991.
    @ARTICLE{bianconi:elliptic, mrkey = {1134193},
      number = {2},
      issn = {0168-0072},
      author = {Bianconi, Ricardo},
      mrclass = {03C62 (03C10)},
      doi = {10.1016/0168-0072(91)90028-K},
      journal = {Ann. Pure Appl. Logic},
      zblnumber = {0756.03018},
      volume = {54},
      mrnumber = {1134193},
      fjournal = {Annals of Pure and Applied Logic},
      mrreviewer = {David E. Marker},
      title = {Model completeness results for elliptic and abelian functions},
      year = {1991},
      pages = {121--136},
      }
  • [me:interpolation] G. Binyamini and D. Novikov, The Pila-Wilkie theorem for subanalytic families: a complex analytic approach, 2016.
    @MISC{me:interpolation,
      author = {Binyamini, Gal and Novikov, Dmitry},
      note = {preprint, to appear in {\em Compos. Math.}},
      title = {The {P}ila-{W}ilkie theorem for subanalytic families: a complex analytic approach},
      year = {2016},
      }
  • [bombieri-pila] Go to document E. Bombieri and J. Pila, "The number of integral points on arcs and ovals," Duke Math. J., vol. 59, iss. 2, pp. 337-357, 1989.
    @ARTICLE{bombieri-pila, mrkey = {1016893},
      number = {2},
      issn = {0012-7094},
      author = {Bombieri, Enrico and Pila, J.},
      mrclass = {11P21 (11D99)},
      doi = {10.1215/S0012-7094-89-05915-2},
      journal = {Duke Math. J.},
      zblnumber = {0718.11048},
      volume = {59},
      mrnumber = {1016893},
      fjournal = {Duke Mathematical Journal},
      mrreviewer = {Ulrich Rausch},
      title = {The number of integral points on arcs and ovals},
      year = {1989},
      pages = {337--357},
      }
  • [bombieri:heights] Go to document E. Bombieri and W. Gubler, Heights in Diophantine Geometry, Cambridge: Cambridge Univ. Press, 2006, vol. 4.
    @BOOK{bombieri:heights, mrkey = {2216774},
      author = {Bombieri, Enrico and Gubler, Walter},
      mrclass = {11G50 (11-02 11G10 11G30 11J68 14G40)},
      series = {New Math. Monogr.},
      isbn = {978-0-521-84615-8; 0-521-84615-3},
      address = {Cambridge},
      publisher = {Cambridge Univ. Press},
      doi = {10.1017/CBO9780511542879},
      zblnumber = {1115.11034},
      volume = {4},
      mrnumber = {2216774},
      mrreviewer = {Yuri Bilu},
      title = {Heights in {D}iophantine Geometry},
      year = {2006},
      pages = {xvi+652},
      }
  • [butler] Go to document L. A. Butler, "Some cases of Wilkie’s conjecture," Bull. Lond. Math. Soc., vol. 44, iss. 4, pp. 642-660, 2012.
    @ARTICLE{butler, mrkey = {2967234},
      number = {4},
      issn = {0024-6093},
      author = {Butler, Lee A.},
      mrclass = {11G50 (03C64)},
      doi = {10.1112/blms/bdr126},
      journal = {Bull. Lond. Math. Soc.},
      zblnumber = {1253.03063},
      volume = {44},
      mrnumber = {2967234},
      fjournal = {Bulletin of the London Mathematical Society},
      mrreviewer = {Chris Miller},
      title = {Some cases of {W}ilkie's conjecture},
      year = {2012},
      pages = {642--660},
      }
  • [denef-vdd] Go to document J. Denef and L. van den Dries, "$p$-adic and real subanalytic sets," Ann. of Math., vol. 128, iss. 1, pp. 79-138, 1988.
    @ARTICLE{denef-vdd, mrkey = {0951508},
      number = {1},
      issn = {0003-486X},
      author = {Denef, J. and van den Dries, L.},
      mrclass = {03C10 (03C60 14G20 14G30 32B20)},
      doi = {10.2307/1971463},
      journal = {Ann. of Math.},
      zblnumber = {0693.14012},
      volume = {128},
      mrnumber = {0951508},
      fjournal = {Annals of Mathematics. Second Series},
      mrreviewer = {Max A. Dickmann},
      title = {{$p$}-adic and real subanalytic sets},
      year = {1988},
      pages = {79--138},
      }
  • [yomdin-friedland] Go to document O. Friedland and Y. Yomdin, "Vitushkin-type theorems," in Geometric Aspects of Functional Analysis, New York: Springer-Verlag, 2014, vol. 2116, pp. 147-157.
    @INCOLLECTION{yomdin-friedland, mrkey = {3364686},
      author = {Friedland, Omer and Yomdin, Yosef},
      mrclass = {26B15},
      series = {Lecture Notes in Math.},
      address = {New York},
      publisher = {Springer-Verlag},
      doi = {10.1007/978-3-319-09477-9_12},
      zblnumber = {1327.14240},
      volume = {2116},
      mrnumber = {3364686},
      booktitle = {Geometric Aspects of Functional Analysis},
      title = {Vitushkin-type theorems},
      pages = {147--157},
      year = {2014},
      }
  • [gv:strata] Go to document A. Gabrièlov and N. Vorobjov, "Complexity of stratifications of semi-Pfaffian sets," Discrete Comput. Geom., vol. 14, iss. 1, pp. 71-91, 1995.
    @ARTICLE{gv:strata, mrkey = {1320587},
      number = {1},
      issn = {0179-5376},
      author = {Gabrièlov, A. and Vorobjov, N.},
      mrclass = {14Q20 (14P10)},
      doi = {10.1007/BF02570696},
      journal = {Discrete Comput. Geom.},
      zblnumber = {0832.68056},
      volume = {14},
      mrnumber = {1320587},
      fjournal = {Discrete \& Computational Geometry. An International Journal of Mathematics and Computer Science},
      mrreviewer = {Patrice Orro},
      title = {Complexity of stratifications of semi-{P}faffian sets},
      year = {1995},
      pages = {71--91},
      }
  • [gv:complexity] A. Gabrielov and N. Vorobjov, "Complexity of computations with Pfaffian and Noetherian functions," in Normal Forms, Bifurcations and Finiteness Problems in Differential Equations, Dordrecht: Kluwer Acad. Publ., 2004, vol. 137, pp. 211-250.
    @INCOLLECTION{gv:complexity, mrkey = {2083248},
      author = {Gabrielov, Andrei and Vorobjov, Nicolai},
      mrclass = {14P99 (03C10 03C64)},
      series = {NATO Sci. Ser. II Math. Phys. Chem.},
      address = {Dordrecht},
      publisher = {Kluwer Acad. Publ.},
      volume = {137},
      mrnumber = {2083248},
      booktitle = {Normal Forms, Bifurcations and Finiteness Problems in Differential Equations},
      title = {Complexity of computations with {P}faffian and {N}oetherian functions},
      pages = {211--250},
      year = {2004},
      }
  • [gv:compact-approx] Go to document A. Gabrielov and N. Vorobjov, "Approximation of definable sets by compact families, and upper bounds on homotopy and homology," J. Lond. Math. Soc., vol. 80, iss. 1, pp. 35-54, 2009.
    @ARTICLE{gv:compact-approx, mrkey = {2520376},
      number = {1},
      issn = {0024-6107},
      author = {Gabrielov, Andrei and Vorobjov, Nicolai},
      mrclass = {14P10 (03C64)},
      doi = {10.1112/jlms/jdp006},
      journal = {J. Lond. Math. Soc.},
      zblnumber = {1177.14097},
      volume = {80},
      mrnumber = {2520376},
      fjournal = {Journal of the London Mathematical Society. Second Series},
      title = {Approximation of definable sets by compact families, and upper bounds on homotopy and homology},
      year = {2009},
      pages = {35--54},
      }
  • [gr:analytic] Go to document R. C. Gunning and H. Rossi, Analytic Functions of Several Complex Variables, Providence, RI: AMS Chelsea Publishing, 2009.
    @BOOK{gr:analytic, mrkey = {2568219},
      author = {Gunning, Robert C. and Rossi, Hugo},
      mrclass = {32-01},
      isbn = {978-0-8218-2165-7},
      address = {Providence, RI},
      publisher = {AMS Chelsea Publishing},
      doi = {10.1090/chel/368},
      zblnumber = {1204.01045},
      mrnumber = {2568219},
      note = {reprint of the 1965 original},
      title = {Analytic Functions of Several Complex Variables},
      year = {2009},
      pages = {xiv+318},
      }
  • [jones-thomas] Go to document G. O. Jones and M. E. M. Thomas, "The density of algebraic points on certain Pfaffian surfaces," Q. J. Math., vol. 63, iss. 3, pp. 637-651, 2012.
    @ARTICLE{jones-thomas, mrkey = {2967167},
      number = {3},
      issn = {0033-5606},
      author = {Jones, G. O. and Thomas, M. E. M.},
      mrclass = {03C64 (11G05 14G05)},
      doi = {10.1093/qmath/har011},
      journal = {Q. J. Math.},
      zblnumber = {1253.03065},
      volume = {63},
      mrnumber = {2967167},
      fjournal = {The Quarterly Journal of Mathematics},
      mrreviewer = {Jean-Philippe Rolin},
      title = {The density of algebraic points on certain {P}faffian surfaces},
      year = {2012},
      pages = {637--651},
      }
  • [khovanskii:fewnomials] A. G. Khovanskiui, Fewnomials, Providence, RI: Amer. Math. Soc., 1991, vol. 88.
    @BOOK{khovanskii:fewnomials, mrkey = {1108621},
      author = {Khovanski\u\i, A. G.},
      mrclass = {14P05 (58A17)},
      series = {Transl. Math. Monogr.},
      isbn = {0-8218-4547-0},
      address = {Providence, RI},
      publisher = {Amer. Math. Soc.},
      volume = {88},
      mrnumber = {1108621},
      note = {translated from the Russian by Smilka Zdravkovska},
      mrreviewer = {Jean-Jacques Risler},
      title = {Fewnomials},
      year = {1991},
      pages = {viii+139},
      zblnumber = {0728.12002},
      }
  • [macintyre:pfaffian] Go to document A. Macintyre, "Some observations about the real and imaginary parts of complex Pfaffian functions," in Model Theory with Applications to Algebra and Analysis. Vol. 1, Cambridge: Cambridge Univ. Press, 2008, vol. 349, pp. 215-223.
    @INCOLLECTION{macintyre:pfaffian, mrkey = {2441381},
      author = {Macintyre, Angus},
      mrclass = {03C60 (32B20)},
      series = {London Math. Soc. Lecture Note Ser.},
      address = {Cambridge},
      publisher = {Cambridge Univ. Press},
      doi = {10.1017/CBO9780511735226.011},
      zblnumber = {1162.33312},
      volume = {349},
      mrnumber = {2441381},
      booktitle = {Model Theory with Applications to Algebra and Analysis. {V}ol. 1},
      title = {Some observations about the real and imaginary parts of complex {P}faffian functions},
      pages = {215--223},
      year = {2008},
      }
  • [malgrange:complex] B. Malgrange, Lectures on the Theory of Functions of Several Complex Variables, New York: Springer-Verlag, 1984, vol. 13.
    @BOOK{malgrange:complex, mrkey = {0742775},
      author = {Malgrange, B.},
      mrclass = {32-01},
      series = {Tata Inst. Fund. Res. Lect. Math. Phys.},
      address = {New York},
      isbn = {3-540-12875-1},
      publisher = {Springer-Verlag},
      volume = {13},
      mrnumber = {0742775},
      note = {reprint of the 1958 edition, notes by Raghavan Narasimhan},
      title = {Lectures on the Theory of Functions of Several Complex Variables},
      year = {1984},
      pages = {i+128},
      zblnumber = {0561.32006},
      }
  • [ps:theta-definability] Go to document Y. Peterzil and S. Starchenko, "Definability of restricted theta functions and families of abelian varieties," Duke Math. J., vol. 162, iss. 4, pp. 731-765, 2013.
    @ARTICLE{ps:theta-definability, mrkey = {3039679},
      number = {4},
      issn = {0012-7094},
      author = {Peterzil, Ya'acov and Starchenko, Sergei},
      mrclass = {03C64 (11F46 11G18 14G35 14K25)},
      doi = {10.1215/00127094-2080018},
      journal = {Duke Math. J.},
      zblnumber = {1284.03215},
      volume = {162},
      mrnumber = {3039679},
      fjournal = {Duke Mathematical Journal},
      mrreviewer = {Jean-Philippe Rolin},
      title = {Definability of restricted theta functions and families of abelian varieties},
      year = {2013},
      pages = {731--765},
      }
  • [pila:density-Q] Go to document J. Pila, "Geometric postulation of a smooth function and the number of rational points," Duke Math. J., vol. 63, iss. 2, pp. 449-463, 1991.
    @ARTICLE{pila:density-Q, mrkey = {1115117},
      number = {2},
      issn = {0012-7094},
      author = {Pila, Jonathan},
      mrclass = {11J99},
      doi = {10.1215/S0012-7094-91-06320-9},
      journal = {Duke Math. J.},
      zblnumber = {0763.11025},
      volume = {63},
      mrnumber = {1115117},
      fjournal = {Duke Mathematical Journal},
      mrreviewer = {Richard T. Bumby},
      title = {Geometric postulation of a smooth function and the number of rational points},
      year = {1991},
      pages = {449--463},
      }
  • [pila-wilkie] Go to document J. Pila and A. J. Wilkie, "The rational points of a definable set," Duke Math. J., vol. 133, iss. 3, pp. 591-616, 2006.
    @ARTICLE{pila-wilkie, mrkey = {2228464},
      number = {3},
      issn = {0012-7094},
      author = {Pila, Jonathan and Wilkie, A. J.},
      mrclass = {03C64 (11G99 11U09)},
      doi = {10.1215/S0012-7094-06-13336-7},
      journal = {Duke Math. J.},
      zblnumber = {1217.11066},
      volume = {133},
      mrnumber = {2228464},
      fjournal = {Duke Mathematical Journal},
      mrreviewer = {Alexandra Shlapentokh},
      title = {The rational points of a definable set},
      year = {2006},
      pages = {591--616},
      }
  • [pila:subanalytic-dilation] Go to document J. Pila, "Integer points on the dilation of a subanalytic surface," Q. J. Math., vol. 55, iss. 2, pp. 207-223, 2004.
    @ARTICLE{pila:subanalytic-dilation, mrkey = {2068319},
      number = {2},
      issn = {0033-5606},
      author = {Pila, Jonathan},
      mrclass = {32B20},
      doi = {10.1093/qjmath/55.2.207},
      journal = {Q. J. Math.},
      zblnumber = {1111.32004},
      volume = {55},
      mrnumber = {2068319},
      fjournal = {The Quarterly Journal of Mathematics},
      mrreviewer = {P. Bundschuh},
      title = {Integer points on the dilation of a subanalytic surface},
      year = {2004},
      pages = {207--223},
      }
  • [pila:subanalytic] Go to document J. Pila, "Rational points on a subanalytic surface," Ann. Inst. Fourier $($Grenoble$)$, vol. 55, iss. 5, pp. 1501-1516, 2005.
    @ARTICLE{pila:subanalytic, mrkey = {2172272},
      number = {5},
      issn = {0373-0956},
      author = {Pila, Jonathan},
      mrclass = {11D99 (14G05 14P15 32B20)},
      url = {http://aif.cedram.org/item?id=AIF_2005__55_5_1501_0},
      journal = {Ann. Inst. Fourier $($Grenoble$)$},
      zblnumber = {1121.11032},
      volume = {55},
      mrnumber = {2172272},
      fjournal = {Université de Grenoble. Annales de l'Institut Fourier},
      mrreviewer = {P. Bundschuh},
      title = {Rational points on a subanalytic surface},
      year = {2005},
      pages = {1501--1516},
      }
  • [pila:pfaff] Go to document J. Pila, "The density of rational points on a Pfaff curve," Ann. Fac. Sci. Toulouse Math., vol. 16, iss. 3, pp. 635-645, 2007.
    @ARTICLE{pila:pfaff, mrkey = {2379055},
      number = {3},
      issn = {0240-2963},
      author = {Pila, Jonathan},
      mrclass = {11G50 (11D45 11D75)},
      url = {http://afst.cedram.org/item?id=AFST_2007_6_16_3_635_0},
      journal = {Ann. Fac. Sci. Toulouse Math.},
      zblnumber = {1229.11053},
      volume = {16},
      mrnumber = {2379055},
      fjournal = {Annales de la Faculté des Sciences de Toulouse. Mathématiques. Série 6},
      mrreviewer = {Alexandra Shlapentokh},
      title = {The density of rational points on a {P}faff curve},
      year = {2007},
      pages = {635--645},
      }
  • [pila:algebraic-points] Go to document J. Pila, "On the algebraic points of a definable set," Selecta Math., vol. 15, iss. 1, pp. 151-170, 2009.
    @ARTICLE{pila:algebraic-points, mrkey = {2511202},
      number = {1},
      issn = {1022-1824},
      author = {Pila, Jonathan},
      mrclass = {11G99 (03C64 11U09)},
      doi = {10.1007/s00029-009-0527-8},
      journal = {Selecta Math.},
      zblnumber = {1218.11068},
      volume = {15},
      mrnumber = {2511202},
      fjournal = {Selecta Mathematica. New Series},
      mrreviewer = {Ricardo Bianconi},
      title = {On the algebraic points of a definable set},
      year = {2009},
      pages = {151--170},
      }
  • [pila:exp-alg-surface] Go to document J. Pila, "Counting rational points on a certain exponential-algebraic surface," Ann. Inst. Fourier $($Grenoble$)$, vol. 60, iss. 2, pp. 489-514, 2010.
    @ARTICLE{pila:exp-alg-surface, mrkey = {2667784},
      number = {2},
      issn = {0373-0956},
      author = {Pila, Jonathan},
      mrclass = {11G50 (03C64)},
      journal = {Ann. Inst. Fourier $($Grenoble$)$},
      zblnumber = {1210.11074},
      volume = {60},
      mrnumber = {2667784},
      fjournal = {Université de Grenoble. Annales de l'Institut Fourier},
      mrreviewer = {Alexandra Shlapentokh},
      title = {Counting rational points on a certain exponential-algebraic surface},
      year = {2010},
      pages = {489--514},
      doi = {10.5802/aif.2530},
      }
  • [pila:andre-oort] Go to document J. Pila, "O-minimality and the André-Oort conjecture for $\Bbb C^n$," Ann. of Math., vol. 173, iss. 3, pp. 1779-1840, 2011.
    @ARTICLE{pila:andre-oort, mrkey = {2800724},
      number = {3},
      issn = {0003-486X},
      author = {Pila, Jonathan},
      mrclass = {11G18 (03C64 11U09 14G35)},
      doi = {10.4007/annals.2011.173.3.11},
      journal = {Ann. of Math.},
      zblnumber = {1243.14022},
      volume = {173},
      mrnumber = {2800724},
      fjournal = {Annals of Mathematics. Second Series},
      mrreviewer = {Alexandra Shlapentokh},
      title = {O-minimality and the {A}ndré-{O}ort conjecture for {$\Bbb C^n$}},
      year = {2011},
      pages = {1779--1840},
      }
  • [scanlon:survey] Go to document T. Scanlon, "Counting special points: logic, Diophantine geometry, and transcendence theory," Bull. Amer. Math. Soc., vol. 49, iss. 1, pp. 51-71, 2012.
    @ARTICLE{scanlon:survey, mrkey = {2869007},
      number = {1},
      issn = {0273-0979},
      author = {Scanlon, Thomas},
      mrclass = {11U09 (03C64 11G99)},
      doi = {10.1090/S0273-0979-2011-01354-4},
      journal = {Bull. Amer. Math. Soc.},
      zblnumber = {1323.11041},
      volume = {49},
      mrnumber = {2869007},
      fjournal = {American Mathematical Society. Bulletin. New Series},
      mrreviewer = {Alexandra Shlapentokh},
      title = {Counting special points: logic, {D}iophantine geometry, and transcendence theory},
      year = {2012},
      pages = {51--71},
      }
  • [vdd:Rre] Go to document L. van den Dries, "On the elementary theory of restricted elementary functions," J. Symbolic Logic, vol. 53, iss. 3, pp. 796-808, 1988.
    @ARTICLE{vdd:Rre, mrkey = {0960999},
      number = {3},
      issn = {0022-4812},
      author = {van den Dries, Lou},
      mrclass = {03C65 (03C40 03C68 12L12)},
      doi = {10.2307/2274572},
      journal = {J. Symbolic Logic},
      zblnumber = {0698.03023},
      volume = {53},
      mrnumber = {0960999},
      fjournal = {The Journal of Symbolic Logic},
      mrreviewer = {M. Yasuhara},
      title = {On the elementary theory of restricted elementary functions},
      year = {1988},
      pages = {796--808},
      }
  • [wilkie:Rexp] Go to document A. J. Wilkie, "Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function," J. Amer. Math. Soc., vol. 9, iss. 4, pp. 1051-1094, 1996.
    @ARTICLE{wilkie:Rexp, mrkey = {1398816},
      number = {4},
      issn = {0894-0347},
      author = {Wilkie, A. J.},
      mrclass = {03C62 (03C60 03C65 14P15)},
      doi = {10.1090/S0894-0347-96-00216-0},
      journal = {J. Amer. Math. Soc.},
      zblnumber = {0892.03013},
      volume = {9},
      mrnumber = {1398816},
      fjournal = {Journal of the American Mathematical Society},
      mrreviewer = {Luc BÂ\copyright{}lair},
      title = {Model completeness results for expansions of the ordered field of real numbers by restricted {P}faffian functions and the exponential function},
      year = {1996},
      pages = {1051--1094},
      }

Authors

Gal Binyamini

Weizmann Institute of Science, Rehovot, Israel

Dmitry Novikov

Weizmann Institute of Science, Rehovot, Israel