[proofplan] We show that no set of $d+1$ points can be shattered by $\mathcal{H}$, where $d = \dim(\mathcal{F})$. The argument uses the linear evaluation map $L : \mathcal{F} \to \mathbb{R}^{d+1}$, $f \mapsto (f(x_1), \ldots, f(x_{d+1}))$. Since $\dim(\mathcal{F}) = d < d + 1$, the image $L(\mathcal{F})$ is a proper subspace of $\mathbb{R}^{d+1}$. Its orthogonal complement is therefore non-trivial, and we use a vector in this complement to exhibit a labelling that $\mathcal{H}$ cannot realise. [/proofplan] [step:Set up the evaluation map and identify a non-trivial orthogonal relation] Set $d := \dim(\mathcal{F})$ and take any $d + 1$ points $x_1, \ldots, x_{d+1} \in \mathcal{X}$. Define the linear evaluation map \begin{align*} L : \mathcal{F} &\to \mathbb{R}^{d+1} \\ f &\mapsto (f(x_1), \ldots, f(x_{d+1})). \end{align*} Since $L$ is a linear map from a $d$-dimensional vector space into $\mathbb{R}^{d+1}$, the rank-nullity theorem gives $\dim(L(\mathcal{F})) \leq d < d+1$. Therefore $L(\mathcal{F})$ is a proper subspace of $\mathbb{R}^{d+1}$, and its orthogonal complement $L(\mathcal{F})^\perp$ in $\mathbb{R}^{d+1}$ has dimension at least $1$. Choose a non-zero vector $\gamma = (\gamma_1, \ldots, \gamma_{d+1}) \in L(\mathcal{F})^\perp$. By definition of the orthogonal complement (with respect to the standard Euclidean inner product on $\mathbb{R}^{d+1}$): \begin{align*} \sum_{i=1}^{d+1} \gamma_i f(x_i) = \gamma \cdot L(f) = 0 \quad \text{for all } f \in \mathcal{F}. \end{align*} [guided] The evaluation map $L$ encodes how the entire function space $\mathcal{F}$ behaves on the chosen $d+1$ points. Because $\mathcal{F}$ is only $d$-dimensional, its image under $L$ cannot fill all of $\mathbb{R}^{d+1}$ -- there must be a linear relation among the evaluations $f(x_1), \ldots, f(x_{d+1})$ that holds for every $f \in \mathcal{F}$. This relation is encoded by the vector $\gamma$. More precisely, $L$ is linear because $\mathcal{F}$ is a vector space: $L(\alpha f + \beta g) = \alpha L(f) + \beta L(g)$. The rank-nullity theorem applied to $L : \mathcal{F} \to \mathbb{R}^{d+1}$ gives $\dim(\ker L) + \dim(L(\mathcal{F})) = \dim(\mathcal{F}) = d$, so $\dim(L(\mathcal{F})) \leq d < d+1$. The orthogonal complement of a $k$-dimensional subspace of $\mathbb{R}^{d+1}$ has dimension $d+1-k \geq 1$, guaranteeing the existence of a non-zero $\gamma$. [/guided] [/step] [step:Partition the indices by the sign of $\gamma$ and identify a labelling that $\mathcal{H}$ cannot realise] Since $\gamma \neq 0$, at least one component $\gamma_i$ is non-zero. Partition $\{1, \ldots, d+1\}$ into \begin{align*} I_+ := \{i : \gamma_i > 0\}, \qquad I_- := \{i : \gamma_i \leq 0\}. \end{align*} Since at least one $\gamma_i > 0$ (if all $\gamma_i \leq 0$, replace $\gamma$ by $-\gamma$, which is also in $L(\mathcal{F})^\perp$, and at least one $-\gamma_i > 0$ since $\gamma \neq 0$), the set $I_+$ is non-empty. Consider the labelling $y_i = +1$ for $i \in I_+$ and $y_i = -1$ for $i \in I_-$. We claim that no $f \in \mathcal{F}$ satisfies $\operatorname{sgn}(f(x_i)) = y_i$ for all $i$. [guided] The idea is that the orthogonal constraint $\sum_i \gamma_i f(x_i) = 0$ forces a "balance" between the evaluations of $f$ that is incompatible with the particular labelling we have constructed. We are choosing the labelling that aligns with the signs of $\gamma$: positive label where $\gamma_i$ is positive, negative label where $\gamma_i$ is non-positive. This alignment is precisely what creates the contradiction. [/guided] [/step] [step:Derive a contradiction from the orthogonality condition] Suppose for contradiction that some $f \in \mathcal{F}$ satisfies $\operatorname{sgn}(f(x_i)) = y_i$ for all $i$. This means: - For $i \in I_+$: $\operatorname{sgn}(f(x_i)) = +1$, so $f(x_i) > 0$. - For $i \in I_-$: $\operatorname{sgn}(f(x_i)) = -1$, so $f(x_i) \leq 0$ (using the convention $\operatorname{sgn}(0) = -1$). Compute the inner product $\sum_{i=1}^{d+1} \gamma_i f(x_i)$: - For each $i \in I_+$: $\gamma_i > 0$ and $f(x_i) > 0$, so $\gamma_i f(x_i) > 0$. - For each $i \in I_-$: $\gamma_i \leq 0$ and $f(x_i) \leq 0$, so $\gamma_i f(x_i) \geq 0$. Therefore \begin{align*} \sum_{i=1}^{d+1} \gamma_i f(x_i) = \underbrace{\sum_{i \in I_+} \gamma_i f(x_i)}_{> 0} + \underbrace{\sum_{i \in I_-} \gamma_i f(x_i)}_{\geq 0} > 0. \end{align*} The first sum is strictly positive because $I_+$ is non-empty and every term $\gamma_i f(x_i) > 0$ for $i \in I_+$. This contradicts the orthogonality condition $\sum_{i=1}^{d+1} \gamma_i f(x_i) = 0$. [guided] The sign structure of $\gamma$ determines which labelling is unrealisable. For each $i \in I_+$, both $\gamma_i$ and $f(x_i)$ would need to be positive (the labelling demands $f(x_i) > 0$), making $\gamma_i f(x_i) > 0$. For each $i \in I_-$, we have $\gamma_i \leq 0$ and the labelling forces $f(x_i) \leq 0$, making $\gamma_i f(x_i) \geq 0$ (the product of two non-positive numbers). Since at least one term is strictly positive and none are negative, the sum is strictly positive -- but the orthogonality constraint forces it to be zero. This is the crucial point: the constraint $\gamma \cdot L(f) = 0$ for all $f \in \mathcal{F}$ means the evaluations $f(x_1), \ldots, f(x_{d+1})$ cannot take on arbitrary sign patterns. The labelling aligned with the signs of $\gamma$ is the one that is blocked. [/guided] [/step] [step:Conclude that $\operatorname{VC}(\mathcal{H}) \leq d$] We have shown that for any choice of $d+1$ points $x_1, \ldots, x_{d+1} \in \mathcal{X}$, there exists a labelling $(y_1, \ldots, y_{d+1})$ that no hypothesis $h \in \mathcal{H}$ can realise. Therefore $\{x_1, \ldots, x_{d+1}\}$ is not shattered by $\mathcal{H}$. Since this holds for every set of $d+1$ points, $\operatorname{VC}(\mathcal{H}) \leq d = \dim(\mathcal{F})$. [/step]