Littlestone and VC-dimension of families of zero sets

Abstract

We prove that, for any $d$ linearly independent functions from some set into a $d$-dimensional vector space over any field, the family of zero sets of all non-trivial linear combination of these functions has VC-dimension and Littlestone dimension $d-1$. Additionally, we characterize when such families are maximal of VC-dimension $d-1$ and give a sufficient condition for when they are maximal of Littlestone dimension $d-1$.

18 pages