# 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$? – domotorp 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. – Kurisuto Asutora Jan 31 '17 at 10:03

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.