# VC dimension of axis-parallel boxes on the torus

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$?

• Do you have some bounds in general or for $d=2$? Jan 29 '17 at 21:27
• 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. Jan 31 '17 at 10:03

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.