First the basic definitions: Let $H$ be a family of sets, and let $P$ be a set of points. Then $H$ is said to shatter $P$ if $\{ h \cap P:~h \in H\}=2^P$, that is, if every subset of $P$ can be obtained by intersecting $P$ with an element of $H$. The Vapnik-Chervonenkis dimension of $H$ is the maximal cardinality of a point set $P$ that is shattered by $H$. See also https://en.wikipedia.org/wiki/VC_dimension.

Let $A$ be the family of axis-parallel boxes in the $d$-dimensional unit cube $[0,1]^d$ having one vertex at the origin. It is known that the VC dimension of $A$ is $d$. Let $B$ be the family of all axis-parallel boxes in $[0,1]^d$ (not necessarily anchored at the origin). The VC dimension of $B$ is known, it is $2d$.

Now the question: Let $C$ be the class of all axis-parallel boxes on the $d$-dimensional unit torus. You could also thing of $C$ as the class of all sets in $[0,1]^d$ which are the $d$-dimensional Cartesian product of elements of $D$, where $D$ is the collection of all subintervals and all complements of subintervals of $[0,1]^d$. Now, what is the VC dimension of $C$?

  • $\begingroup$ Do you have some bounds in general or for $d=2$? $\endgroup$
    – domotorp
    Jan 29, 2017 at 21:27
  • $\begingroup$ Well, obviously a lower bound is the dimension for "non-periodic" boxes (boxes contained in the proper cube, not in the torus), which is 2d. For an upper bound, I don't have any idea. Probably you could use the fact that a "periodic" box on the torus splits into $2^d$ "non-periodic" boxes, but I do not see how this should lead to a reasonable result. My guess would be that the solution could be something linear in $d$, maybe $4d$ or something similar. $\endgroup$ Jan 31, 2017 at 10:03

1 Answer 1


Update (May 5, 2020)

Gillibert, Lachmann, and Müllner have just posted an arXiv preprint in which they show that the VC-dimension of $C$ is on the order of $d\log_2 d$. So they prove that the VC-dimension of $C$ is not linear in $d$, which is remarkable given the behavior of similarly defined geometric set systems in $\mathbb{R}^d$.

Their proof techniques appear quite involved, especially the lower bound, which is arguably the more interesting part. But I wanted to point to Lemma 3.1 of their paper, which highlights an easy (and obvious in retrospect) way to both improve the upper bound I gave below, and also eliminate the appeal to Sauer-Shelah in this particular case.

For $1\leq i\leq d$, let $C_i$ be the set of periodic boxes of the form $I_1\times\ldots\times I_d$ such that $I_j=[0,1]$ for all $j\neq i$. So $C=C_1\wedge\ldots\wedge C_d$ in my notation below. The easy part of the Lemma below is that, if $\pi_C$ denotes the shatter function for $C$, then $\pi_C(m)\leq \pi_{C_1}(m)\ldots\pi_{C_d}(m)$ for all $m$. It's also easy to see that $C_i$ has VC-dimension $3$, and thus my original argument used Sauer-Shelah to bound $\pi_{C_i}(m)=(em/3)^3$ (for $m\geq 3$). So we get $\pi_C(m)\leq (em/3)^{3d}$ and one optimizes $(em/3)^{3d}<2^m$ to get my upper bound of $(3+o(1))d\log_2d$ on the VC-dimension of $C$.

But it's easier (and much more sensible) to see directly that $\pi_{C_i}(m)$ grows on the order of $m^2$. In particular, $\pi_{C_i}$ coincides the shatter function of intervals on the circle, and so $\pi_{C_i}(m)$ is the number of subsets of $m$ points on $S^1$, which themselves are cyclic intervals. This is easily bounded above by $m^2$ (I think the precise figure is $m^2-m+2$).

So altogether we have $\pi_C(m)\leq m^{2d}$ and so if $m^{2d}<2^m$ then the VC-dimension of $C$ is less than $m$. If particular, for any $c>2$, the VC-dimension of $C$ is less than $cd\log_2 d$ if $d$ is sufficiently large (depending on $c$).

Another way of putting this is that we get a better bound using the fact that, while each $C_i$ has VC-dimension $3$, it has VC-density $2$.

Still, this argument (like the one below) only uses geometry in dimension $1$. In their preprint, the authors above use more sophisticated techniques to bring down the upper bound to the order of $d\log_2d$. And, of course, their argument for the lower bound is another story.

Original post (December 10, 2019)

This answer doesn't provide the exact VC-dimension of $C$, but does provide an almost linear upper bound.

The observation that a periodic box is a union of at most $2^d$ boxes could be used get a bound of $(2d^2+o(d^2))2^d$ for the VC-dimension of non-periodic boxes (using the fact that boxes have VC-dimension $2d$). I will use a similar idea to obtain a much better bound (but still not linear in $d$, unfortunately).

Lemma. Suppose $H_1,\ldots,H_n$ are set systems on a set $X$, each of VC-dimension at most $k$. Suppose $H$ is one of the following two set systems:

  1. $H_1\vee\ldots\vee H_n:=\{S_1\cup\ldots\cup S_n:S_i\in H_i\}$, or
  2. $H_1\wedge\ldots\wedge H_n:=\{S_1\cap\ldots\cap S_n:S_i\in H_i\}$.

Then $H$ has VC-dimension at most $k(1+o(1))n\log_2(n)$ (where $o(1)$ depends only on $n$).

Proof. Let $\pi_i$ be the shatter function for $H_i$, i.e., $$ \pi_i(m)=\max\{|\{Y\cap S:S\in H_i\}|:Y\subseteq X,~|Y|=m\}. $$ Let $\pi$ be the shatter function for $H$. One can show $\pi(m)\leq\pi_1(m)\cdot\ldots\cdot\pi_n(m)$ for any $m$. By the Sauer-Shelah lemma, we have $\pi_i(m)\leq (em/k)^k$ for all $i$ and $m\geq k$. So $\pi(m)\leq (em/k)^{kn}$ for any $m\geq k$. In particular, if $m\geq k$ and $(em/k)^{kn}<2^m$, then $\pi(m)<2^m$, and so the VC-dimension of $H$ is less than $m$. So we just need to optimize $m$ satisfying these inequalities. The following works and is of the form stated in the lemma: $$ m:=kn\log_2(cn\log_2(cn)) $$ where $c=e+\log_2(e)$.

So if we use case $(1)$ and write a periodic box as a union of at most $2^d$ boxes, then we get $(2d^2+o(d^2))2^d$.

Instead, we can use case $(2)$ to get a better bound. In particular, for $i\leq d$, let $C_i$ be the set of periodic boxes of the form $I_1\times\ldots\times I_d$ such that $I_j=[0,1]$ for all $j\neq i$. Then the collection $C$ of all periodic boxes is precisely $C_1\wedge\ldots\wedge C_d$. Moreover, each $C_i$ has the same VC-dimension as the set of $1$-dimensional periodic boxes, which is $3$. So altogether, this yields:

Corollary. The VC-dimension of $C$ is at most $(3+o(1))d\log_2(d)$.

The precise VC-dimension of $C$ appears to still be an open problem. I only found one paper discussing it, which only conjectures that the VC-dimension is linear in $d$ (but gives no known bounds). One major defect in my argument as that geometry is only being used in dimension $1$, and then the rest is just abstract combinatorics. One would expect intersections of elements from the $C_i$'s to be much better behaved than intersections of arbitrary sets. Probably the bound in the lemma can be improved a little bit, but not to something linear.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.