bibkey: aschenbrenner2011vcdensity
authors: Matthias Aschenbrenner, Alf Dolich, Deirdre Haskell, Dugald Macpherson, Sergei Starchenko
year: 2011
title: "Vapnik-Chervonenkis density in some theories without the independence property, I"
doi: null
url: https://arxiv.org/abs/1109.5438v1
claim: "Lemma 2.2 treats traces under arbitrary pullback maps; the Boolean-combination inequalities preceding Lemma 2.7 and Corollary 6.5(2) supply the finite-growth context for ordered additive integer groups and Presburger arithmetic."
strata_touched:
  - D5/S0/Computability/PresburgerPatternGrowth
license: citation-only
triage: anchor

Presburger finite traces

A fixed Presburger formula has polynomially bounded finite traces. The paper’s quasi-o-minimality theorem and ordered-group corollary provide the broader model-theoretic setting. VC density and VC dimension are distinct quantities; a bound on the former does not assert the same numerical bound on the latter.

The separated-atom proof uses finite threshold nesting, fixed source residues, and Boolean product upper bounds. Arbitrary source chart maps can pull back traces without being definable or injective. The paper does not state the native-tree descriptor obstruction or establish any native controller undecidability claim.

Verified locator

https://arxiv.org/abs/1109.5438v1

https://arxiv.org/pdf/1109.5438v1, Lemma 2.2; Boolean-combination inequalities preceding Lemma 2.7; Theorem 6.4 and Corollary 6.5(2).