= Solution
Fix an $m$-point <set> $S$. The restriction of an <intersection> $c_1\cap c_2$ to $S$ is determined by the ordered pair of restrictions $c_1|_S,c_2|_S$. Some pairs can yield the same <intersection>, so the <growth function of a hypothesis class> satisfies
$$
\Pi_{H_2}(m)\leq\Pi_H(m)^2.
$$
Assume first that $d\geq1$. If $12d$ points were shattered by $H_2$, the <Sauer-Shelah lemma> would imply
$$
2^{12d}=\Pi_{H_2}(12d)\leq\Pi_H(12d)^2\leq(12e)^{2d}.
$$
But $e<3$, so $(12e)^2<36^2=1296<4096=2^{12}$. Raising this strict inequality to the positive integer power $d$ gives a contradiction. No $12d$-point <set> can therefore be shattered; neither can any larger <set>, since shattering passes to subsets. Consequently
$$
\boxed{\operatorname{VC}(H_2)<12d\qquad(d\geq1).}
$$
\b[The printed strict inequality needs $d\geq1$.] For example, on a nonempty domain let $H$ contain only the identically zero <classifier>. Then $\operatorname{VC}(H)=\operatorname{VC}(H_2)=0$, whereas the stated conclusion would require $0<0$. More generally, a nonempty <hypothesis class> of <VC dimension> zero has only one distinct labelling <function>, since two different <functions> would shatter a point on which they differ. Its self-<intersection> class also has <VC dimension> zero.
Back to article page
