Vapnik-Chervonenkis density in some theories without the independence property, I

Aschenbrenner, Matthias; Dolich, Alf; Haskell, Deirdre; Macpherson, Dugald; Starchenko, Sergei

doi:10.1090/tran/6659

Vapnik-Chervonenkis density in some theories without the independence property, I
HTML articles powered by AMS MathViewer

by Matthias Aschenbrenner, Alf Dolich, Deirdre Haskell, Dugald Macpherson and Sergei Starchenko PDF

Trans. Amer. Math. Soc. 368 (2016), 5889-5949 Request permission

Abstract:

We recast the problem of calculating Vapnik-Chervonenkis (VC) density into one of counting types, and thereby calculate bounds (often optimal) on the VC density for some weakly o-minimal, weakly quasi-o-minimal, and $P$-minimal theories.

References

Khaled A. S. Abdel-Ghaffar, Maximum number of edges joining vertices on a cube, Inform. Process. Lett. 87 (2003), no. 2, 95–99. MR 1983932, DOI 10.1016/S0020-0190(03)00257-6
H. Adler, Theories controlled by formulas of Vapnik-Chervonenkis codimension $1$, preprint (2008).
—, An introduction to theories without the independence property, preprint (2008).
Martin Anthony, Graham Brightwell, and Colin Cooper, The Vapnik-Chervonenkis dimension of a random graph, Discrete Math. 138 (1995), no. 1-3, 43–56. 14th British Combinatorial Conference (Keele, 1993). MR 1322079, DOI 10.1016/0012-365X(94)00187-N
Matthias Aschenbrenner and Lou van den Dries, Closed asymptotic couples, J. Algebra 225 (2000), no. 1, 309–358. MR 1743664, DOI 10.1006/jabr.1999.8128
Matthias Aschenbrenner, Alf Dolich, Deirdre Haskell, Dugald Macpherson, and Sergei Starchenko, Vapnik-Chervonenkis density in some theories without the independence property, II, Notre Dame J. Form. Log. 54 (2013), no. 3-4, 311–363. MR 3091661, DOI 10.1215/00294527-2143862
Patrice Assouad, Densité et dimension, Ann. Inst. Fourier (Grenoble) 33 (1983), no. 3, 233–282 (French, with English summary). MR 723955, DOI 10.5802/aif.938
Patrice Assouad, Observations sur les classes de Vapnik-Cervonenkis et la dimension combinatoire de Blei, Seminar on harmonic analysis, 1983–1984, Publ. Math. Orsay, vol. 85, Univ. Paris XI, Orsay, 1985, pp. 92–112 (French). MR 802778
John T. Baldwin and Saharon Shelah, Randomness and semigenericity, Trans. Amer. Math. Soc. 349 (1997), no. 4, 1359–1376. MR 1407480, DOI 10.1090/S0002-9947-97-01869-2
József Balogh and Béla Bollobás, Unavoidable traces of set systems, Combinatorica 25 (2005), no. 6, 633–643. MR 2199428, DOI 10.1007/s00493-005-0039-x
Saugata Basu, Richard Pollack, and Marie-Françoise Roy, On the number of cells defined by a family of polynomials on a variety, Mathematika 43 (1996), no. 1, 120–126. MR 1401711, DOI 10.1112/S0025579300011621
Luc Bélair, Types dans les corps valués munis d’applications coefficients, Illinois J. Math. 43 (1999), no. 2, 410–425 (French, with English summary). MR 1703196
Luc Bélair and Michel Bousquet, Types dans les corps valués, C. R. Acad. Sci. Paris Sér. I Math. 323 (1996), no. 8, 841–844 (French, with English and French summaries). MR 1414544
Oleg Belegradek, Ya’acov Peterzil, and Frank Wagner, Quasi-o-minimal structures, J. Symbolic Logic 65 (2000), no. 3, 1115–1132. MR 1791366, DOI 10.2307/2586690
Oleg Belegradek, Viktor Verbovskiy, and Frank O. Wagner, Coset-minimal groups, Ann. Pure Appl. Logic 121 (2003), no. 2-3, 113–143. MR 1982944, DOI 10.1016/S0168-0072(02)00084-2
Garrett Birkhoff, Lattice theory, 3rd ed., American Mathematical Society Colloquium Publications, Vol. XXV, American Mathematical Society, Providence, R.I., 1967. MR 0227053
A. Bobkov, VC density for trees, manuscript (2014).
H. Brönnimann and M. T. Goodrich, Almost optimal set covers in finite VC-dimension, Discrete Comput. Geom. 14 (1995), no. 4, 463–479. ACM Symposium on Computational Geometry (Stony Brook, NY, 1994). MR 1360948, DOI 10.1007/BF02570718
Enrique Casanovas and Martin Ziegler, Stable theories with a new predicate, J. Symbolic Logic 66 (2001), no. 3, 1127–1140. MR 1856732, DOI 10.2307/2695097
Gregory Cherlin and Françoise Point, On extensions of Presburger arithmetic, Proceedings of the fourth Easter conference on model theory (Gross Köris, 1986) Seminarberichte, vol. 86, Humboldt Univ., Berlin, 1986, pp. 17–34. MR 884718
Artem Chernikov and Pierre Simon, Externally definable sets and dependent pairs, Israel J. Math. 194 (2013), no. 1, 409–425. MR 3047077, DOI 10.1007/s11856-012-0061-9
Artem Chernikov and Pierre Simon, Externally definable sets and dependent pairs II, Trans. Amer. Math. Soc. 367 (2015), no. 7, 5217–5235. MR 3335415, DOI 10.1090/S0002-9947-2015-06210-2
Raf Cluckers, Analytic $p$-adic cell decomposition and integrals, Trans. Amer. Math. Soc. 356 (2004), no. 4, 1489–1499. MR 2034315, DOI 10.1090/S0002-9947-03-03458-5
J. Denef and L. van den Dries, $p$-adic and real subanalytic sets, Ann. of Math. (2) 128 (1988), no. 1, 79–138. MR 951508, DOI 10.2307/1971463
M. A. Dickmann, Elimination of quantifiers for ordered valuation rings, J. Symbolic Logic 52 (1987), no. 1, 116–128. MR 877859, DOI 10.2307/2273866
Alfred Dolich, John Goodrick, and David Lippel, Dp-minimality: basic facts and examples, Notre Dame J. Form. Log. 52 (2011), no. 3, 267–288. MR 2822489, DOI 10.1215/00294527-1435456
Lou van den Dries, Tame topology and o-minimal structures, London Mathematical Society Lecture Note Series, vol. 248, Cambridge University Press, Cambridge, 1998. MR 1633348, DOI 10.1017/CBO9780511525919
Lou van den Dries, Deirdre Haskell, and Dugald Macpherson, One-dimensional $p$-adic subanalytic sets, J. London Math. Soc. (2) 59 (1999), no. 1, 1–20. MR 1688485, DOI 10.1112/S0024610798006917
R. M. Dudley, A course on empirical processes, École d’été de probabilités de Saint-Flour, XII—1982, Lecture Notes in Math., vol. 1097, Springer, Berlin, 1984, pp. 1–142. MR 876079, DOI 10.1007/BFb0099432
R. M. Dudley, Uniform central limit theorems, Cambridge Studies in Advanced Mathematics, vol. 63, Cambridge University Press, Cambridge, 1999. MR 1720712, DOI 10.1017/CBO9780511665622
Jean-Louis Duret, Les corps faiblement algébriquement clos non séparablement clos ont la propriété d’indépendence, Model theory of algebra and arithmetic (Proc. Conf., Karpacz, 1979), Lecture Notes in Math., vol. 834, Springer, Berlin-New York, 1980, pp. 136–162 (French). MR 606784
Herbert Edelsbrunner, Algorithms in combinatorial geometry, EATCS Monographs on Theoretical Computer Science, vol. 10, Springer-Verlag, Berlin, 1987. MR 904271, DOI 10.1007/978-3-642-61568-9
Gy. Elekes, SUMS versus PRODUCTS in number theory, algebra and Erdős geometry, Paul Erdős and his mathematics, II (Budapest, 1999) Bolyai Soc. Math. Stud., vol. 11, János Bolyai Math. Soc., Budapest, 2002, pp. 241–290. MR 1954729
P. Erdös and R. Rado, A partition calculus in set theory, Bull. Amer. Math. Soc. 62 (1956), 427–489. MR 81864, DOI 10.1090/S0002-9904-1956-10036-0
Z. Füredi and J. Pach, Traces of finite sets: extremal problems and geometric applications, Extremal problems for finite sets (Visegrád, 1991) Bolyai Soc. Math. Stud., vol. 3, János Bolyai Math. Soc., Budapest, 1994, pp. 251–282. MR 1319167
Vincent Guingona, On uniform definability of types over finite sets, J. Symbolic Logic 77 (2012), no. 2, 499–514. MR 2963018, DOI 10.2178/jsl/1333566634
Vincent Guingona and Cameron Donnay Hill, On Vapnik-Chervonenkis density over indiscernible sequences, MLQ Math. Log. Q. 60 (2014), no. 1-2, 59–65. MR 3171609, DOI 10.1002/malq.201300040
Y. Gurevich and P. H. Schmitt, The theory of ordered abelian groups does not have the independence property, Trans. Amer. Math. Soc. 284 (1984), no. 1, 171–182. MR 742419, DOI 10.1090/S0002-9947-1984-0742419-0
Jehuda Hartman, The homeomorphic embedding of $K_{n}$ in the $m$-cube, Discrete Math. 16 (1976), no. 2, 157–160. MR 427118, DOI 10.1016/0012-365X(76)90143-6
Deirdre Haskell and Dugald Macpherson, Cell decompositions of $\textrm {C}$-minimal structures, Ann. Pure Appl. Logic 66 (1994), no. 2, 113–162. MR 1262433, DOI 10.1016/0168-0072(94)90064-7
Deirdre Haskell and Dugald Macpherson, A version of o-minimality for the $p$-adics, J. Symbolic Logic 62 (1997), no. 4, 1075–1092. MR 1618009, DOI 10.2307/2275628
Deirdre Haskell and Dugald Macpherson, VC density in real closed valued fields, Prépublications de la séminaire de structures algébriques ordonnées 83 (2008–2009), Equipe de logique, Université Paris VII.
David Haussler, Sphere packing numbers for subsets of the Boolean $n$-cube with bounded Vapnik-Chervonenkis dimension, J. Combin. Theory Ser. A 69 (1995), no. 2, 217–232. MR 1313896, DOI 10.1016/0097-3165(95)90052-7
Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR 1221741, DOI 10.1017/CBO9780511551574
Jan E. Holly, Canonical forms for definable subsets of algebraically closed and real closed valued fields, J. Symbolic Logic 60 (1995), no. 3, 843–860. MR 1348997, DOI 10.2307/2275760
Ehud Hrushovski and David Kazhdan, Integration in valued fields, Algebraic geometry and number theory, Progr. Math., vol. 253, Birkhäuser Boston, Boston, MA, 2006, pp. 261–405. MR 2263194, DOI 10.1007/978-0-8176-4532-8_{4}
U. Hrushovski and A. Pillay, Weakly normal groups, Logic colloquium ’85 (Orsay, 1985) Stud. Logic Found. Math., vol. 122, North-Holland, Amsterdam, 1987, pp. 233–244. MR 895647, DOI 10.1016/S0049-237X(09)70556-7
Gabriela Jeronimo and Juan Sabia, On the number of sets definable by polynomials, J. Algebra 227 (2000), no. 2, 633–644. MR 1759839, DOI 10.1006/jabr.1999.8243
H. R. Johnson and M. C. Laskowski, Compression schemes, stable definable families, and o-minimal structures, Discrete Comput. Geom. 43 (2010), no. 4, 914–926. MR 2610477, DOI 10.1007/s00454-009-9201-3
Itay Kaplan, Alf Onshuus, and Alexander Usvyatsov, Additivity of the dp-rank, Trans. Amer. Math. Soc. 365 (2013), no. 11, 5783–5804. MR 3091265, DOI 10.1090/S0002-9947-2013-05782-0
Marek Karpinski and Angus Macintyre, Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks, J. Comput. System Sci. 54 (1997), no. 1, 169–176. 1st Annual Dagstuhl Seminar on Neural Computing (1994). MR 1463257, DOI 10.1006/jcss.1997.1477
Marek Karpinski and Angus Macintyre, Approximating volumes and integrals in o-minimal and $p$-minimal theories, Connections between model theory and algebraic and analytic geometry, Quad. Mat., vol. 6, Dept. Math., Seconda Univ. Napoli, Caserta, 2000, pp. 149–177. MR 1930686
T. Kövari, V. T. Sós, and P. Turán, On a problem of K. Zarankiewicz, Colloq. Math. 3 (1954), 50–57. MR 65617, DOI 10.4064/cm-3-1-50-57
K. Zh. Kudaĭbergenov, On the independence property, Sibirsk. Mat. Zh. 41 (2000), no. 1, 134–135, iii (Russian, with Russian summary); English transl., Siberian Math. J. 41 (2000), no. 1, 113. MR 1756481, DOI 10.1007/BF02674000
K. Zh. Kudaĭbergenov, Weakly quasi-o-minimal models, Mat. Tr. 13 (2010), no. 1, 156–168 (Russian, with Russian summary); English transl., Siberian Adv. Math. 20 (2010), no. 4, 285–292. MR 2682771, DOI 10.3103/s1055134410040036
Franz-Viktor Kuhlmann, Abelian groups with contractions. II. Weak $\textrm {o}$-minimality, Abelian groups and modules (Padova, 1994) Math. Appl., vol. 343, Kluwer Acad. Publ., Dordrecht, 1995, pp. 323–342. MR 1378210
Michael C. Laskowski, Vapnik-Chervonenkis classes of definable sets, J. London Math. Soc. (2) 45 (1992), no. 2, 377–384. MR 1171563, DOI 10.1112/jlms/s2-45.2.377
Michael C. Laskowski, unpublished notes.
L. Lipshitz, Rigid subanalytic sets, Amer. J. Math. 115 (1993), no. 1, 77–108. MR 1209235, DOI 10.2307/2374723
L. Lipshitz and Z. Robinson, One-dimensional fibers of rigid subanalytic sets, J. Symbolic Logic 63 (1998), no. 1, 83–88. MR 1610778, DOI 10.2307/2586589
László Lovász and Balázs Szegedy, Regularity partitions and the topology of graphons, An irregular mind, Bolyai Soc. Math. Stud., vol. 21, János Bolyai Math. Soc., Budapest, 2010, pp. 415–446. MR 2815610, DOI 10.1007/978-3-642-14444-8_{1}2
Angus Macintyre, On definable subsets of $p$-adic fields, J. Symbolic Logic 41 (1976), no. 3, 605–610. MR 485335, DOI 10.2307/2272038
Dugald Macpherson, David Marker, and Charles Steinhorn, Weakly o-minimal structures and real closed fields, Trans. Amer. Math. Soc. 352 (2000), no. 12, 5435–5483. MR 1781273, DOI 10.1090/S0002-9947-00-02633-7
Dugald Macpherson and Charles Steinhorn, On variants of o-minimality, Ann. Pure Appl. Logic 79 (1996), no. 2, 165–209. MR 1396850, DOI 10.1016/0168-0072(95)00037-2
David Marker, Model theory, Graduate Texts in Mathematics, vol. 217, Springer-Verlag, New York, 2002. An introduction. MR 1924282
J. Matoušek, Tight upper bounds for the discrepancy of half-spaces, Discrete Comput. Geom. 13 (1995), no. 3-4, 593–601. MR 1318799, DOI 10.1007/BF02574066
Jiří Matoušek, Geometric set systems, European Congress of Mathematics, Vol. II (Budapest, 1996) Progr. Math., vol. 169, Birkhäuser, Basel, 1998, pp. 1–27. MR 1645816
Jiří Matoušek, Lectures on discrete geometry, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, New York, 2002. MR 1899299, DOI 10.1007/978-1-4613-0039-7
Jiří Matoušek, Bounded VC-dimension implies a fractional Helly theorem, Discrete Comput. Geom. 31 (2004), no. 2, 251–255. MR 2060639, DOI 10.1007/s00454-003-2859-z
Jiří Matoušek, Emo Welzl, and Lorenz Wernisch, Discrepancy and approximations for bounded VC-dimension, Combinatorica 13 (1993), no. 4, 455–466. MR 1262921, DOI 10.1007/BF01303517
Christian Michaux and Roger Villemaire, Presburger arithmetic and recognizability of sets of natural numbers by automata: new proofs of Cobham’s and Semenov’s theorems, Ann. Pure Appl. Logic 77 (1996), no. 3, 251–277. MR 1370990, DOI 10.1016/0168-0072(95)00022-4
Marie-Hélène Mourgues, Cell decomposition for $P$-minimal fields, MLQ Math. Log. Q. 55 (2009), no. 5, 487–492. MR 2568759, DOI 10.1002/malq.200810009
Alf Onshuus and Alexander Usvyatsov, On dp-minimality, strong dependence and weight, J. Symbolic Logic 76 (2011), no. 3, 737–758. MR 2849244, DOI 10.2178/jsl/1309952519
János Pach and Micha Sharir, Repeated angles in the plane and related problems, J. Combin. Theory Ser. A 59 (1992), no. 1, 12–22. MR 1141318, DOI 10.1016/0097-3165(92)90094-B
János Pach and Micha Sharir, On the number of incidences between points and curves, Combin. Probab. Comput. 7 (1998), no. 1, 121–127. MR 1611057, DOI 10.1017/S0963548397003192
János Pach and Micha Sharir, Geometric incidences, Towards a theory of geometric graphs, Contemp. Math., vol. 342, Amer. Math. Soc., Providence, RI, 2004, pp. 185–223. MR 2065264, DOI 10.1090/conm/342/06151
Michel Parigot, Théories d’arbres, J. Symbolic Logic 47 (1982), no. 4, 841–853 (1983) (French). MR 683159, DOI 10.2307/2273103
Anand Pillay, The model-theoretic content of Lang’s conjecture, Model theory and algebraic geometry, Lecture Notes in Math., vol. 1696, Springer, Berlin, 1998, pp. 101–106. MR 1678531, DOI 10.1007/978-3-540-68521-0_{6}
Klaus-Peter Podewski and Martin Ziegler, Stable graphs, Fund. Math. 100 (1978), no. 2, 101–107. MR 485336, DOI 10.4064/fm-100-2-101-107
Françoise Point, On decidable extensions of Presburger arithmetic: from A. Bertrand numeration systems to Pisot numbers, J. Symbolic Logic 65 (2000), no. 3, 1347–1374. MR 1791380, DOI 10.2307/2586704
Françoise Point and Frank O. Wagner, Essentially periodic ordered groups, Ann. Pure Appl. Logic 105 (2000), no. 1-3, 261–291. MR 1786147, DOI 10.1016/S0168-0072(99)00053-6
Bruno Poizat, Cours de théorie des modèles, Bruno Poizat, Lyon, 1985 (French). Une introduction à la logique mathématique contemporaine. [An introduction to contemporary mathematical logic]. MR 817208
Richard Pollack and Marie-Françoise Roy, On the number of cells defined by a set of polynomials, C. R. Acad. Sci. Paris Sér. I Math. 316 (1993), no. 6, 573–577 (English, with English and French summaries). MR 1212207
George Pólya and Gabor Szegő, Problems and theorems in analysis. I, Classics in Mathematics, Springer-Verlag, Berlin, 1998. Series, integral calculus, theory of functions; Translated from the German by Dorothee Aeppli; Reprint of the 1978 English translation. MR 1492447, DOI 10.1007/978-3-642-61905-2
Mike Prest, Model theory and modules, London Mathematical Society Lecture Note Series, vol. 130, Cambridge University Press, Cambridge, 1988. MR 933092, DOI 10.1017/CBO9780511600562
N. Sauer, On the density of families of sets, J. Combinatorial Theory Ser. A 13 (1972), 145–147. MR 307902, DOI 10.1016/0097-3165(72)90019-2
James H. Schmerl, $\aleph _{0}$-categorical distributive lattices of finite breadth, Proc. Amer. Math. Soc. 87 (1983), no. 4, 707–713. MR 687647, DOI 10.1090/S0002-9939-1983-0687647-2
James H. Schmerl, Partially ordered sets and the independence property, J. Symbolic Logic 54 (1989), no. 2, 396–401. MR 997874, DOI 10.2307/2274855
Saharon Shelah, Stability, the f.c.p., and superstability; model theoretic properties of formulas in first order theory, Ann. Math. Logic 3 (1971), no. 3, 271–362. MR 317926, DOI 10.1016/0003-4843(71)90015-5
Saharon Shelah, A combinatorial problem; stability and order for models and theories in infinitary languages, Pacific J. Math. 41 (1972), 247–261. MR 307903, DOI 10.2140/pjm.1972.41.247
S. Shelah, Classification theory and the number of nonisomorphic models, 2nd ed., Studies in Logic and the Foundations of Mathematics, vol. 92, North-Holland Publishing Co., Amsterdam, 1990. MR 1083551
Saharon Shelah, Dependent first order theories, continued, Israel J. Math. 173 (2009), 1–60. MR 2570659, DOI 10.1007/s11856-009-0082-1
Saharon Shelah, Strongly dependent theories, Israel J. Math. 204 (2014), no. 1, 1–83. MR 3273451, DOI 10.1007/s11856-014-1111-2
Saharon Shelah and Joel Spencer, Zero-one laws for sparse random graphs, J. Amer. Math. Soc. 1 (1988), no. 1, 97–115. MR 924703, DOI 10.1090/S0894-0347-1988-0924703-8
Pierre Simon, On dp-minimal ordered structures, J. Symbolic Logic 76 (2011), no. 2, 448–460. MR 2830411, DOI 10.2178/jsl/1305810758
József Solymosi and Terence Tao, An incidence theorem in higher dimensions, Discrete Comput. Geom. 48 (2012), no. 2, 255–280. MR 2946447, DOI 10.1007/s00454-012-9420-x
Joel Spencer, The strange logic of random graphs, Algorithms and Combinatorics, vol. 22, Springer-Verlag, Berlin, 2001. MR 1847951, DOI 10.1007/978-3-662-04538-1
J. Spencer, E. Szemerédi, and W. Trotter Jr., Unit distances in the Euclidean plane, Graph theory and combinatorics (Cambridge, 1983) Academic Press, London, 1984, pp. 293–303. MR 777185
E. Szemerédi and W. T. Trotter Jr., A combinatorial distinction between the Euclidean and projective planes, European J. Combin. 4 (1983), no. 4, 385–394. MR 743162, DOI 10.1016/S0195-6698(83)80036-5
Csaba D. Tóth, The Szemerédi-Trotter theorem in the complex plane, Combinatorica 35 (2015), no. 1, 95–126. MR 3341142, DOI 10.1007/s00493-014-2686-2
V. N. Vapnik and A. Ja. Červonenkis, The uniform convergence of frequencies of the appearance of events to their probabilities, Teor. Verojatnost. i Primenen. 16 (1971), 264–279 (Russian, with English summary). MR 0288823
Volker Weispfenning, Elimination of quantifiers for certain ordered and lattice-ordered abelian groups, Bull. Soc. Math. Belg. Sér. B 33 (1981), no. 1, 131–155. MR 620968
J. Wierzejewski, On stability and products, Fund. Math. 93 (1976), no. 2, 81–95. MR 429539, DOI 10.4064/fm-93-2-81-95