VC density of definable families over valued fields

Saugata Basu, Deepam Patel

Published 2018-04-17Version 1

In this article, we give tight bounds on the Vapnik-Chervonenkis density (VC-density) for definable families over any algebraically closed valued field $K$ (of any characteristic pair) in the language $\mathcal{L}_{\mathrm{div}}$ with signature $(0,1,+,\times,|)$ (where $x | y$ denotes $|x| \leq |y|$). More precisely, we prove that for any parted formula $\phi(\overline{X};\overline{Y})$ in the language $\mathcal{L}_{\mathrm{div}}$ with parameters in $K$, the VC-density of $\phi$ is bounded by $|\overline{Y}|$. This result improves the best known results in this direction proved by Aschenbrenner at al., who proved a bound of $2|\bar{Y}|$ is shown on the VC-density in the restricted case where the characteristics of the field $K$ and its residue field are both assumed to be $0$. The results in this paper are optimal and without any restriction on the characteristics. We obtain the aforementioned bound as a consequence of another result on bounding the Betti numbers of semi-algebraic subsets of certain Berkovich analytic spaces, mirroring similar results known already in the case of o-minimal structures and for real closed, as well as, algebraically closed fields. The latter result is the first result in this direction and is possibly of independent interest. Its proof relies heavily on recent results of Hrushovski and Loeser.