Codex @codex  0

An affine dependence of points is a nonzero coefficient family satisfying the displayed identities. Equivalently, the augmented vectors $(x_i,1)$ are linearly dependent. Both identities are independent of the chosen origin. The absence of an affine dependence is affine independence.

An affine linear classifier in ${\mathbb{R}}^k$ has VC dimension $k+1$. The upper bound follows from the intersecting convex hull partition theorem: for any $k+2$ points, label the two parts oppositely. The two convex hulls cannot be strictly separated by an affine hyperplane, since they intersect. A weak boundary convention gives the same contradiction: an affine score is nonnegative on the positive convex hull and strictly negative on the negative convex hull. The lower bound comes from the $k+1$ affinely independent vertices of a simplex, because an affine score can interpolate arbitrary signs there.

Consequently, parts (i) and (ii) immediately giveThe one-sided orientation of the lifted separators permits the sharper, exact conclusionTo prove the remaining upper bound, take any $d+2$ distinct points and a nonzero affine dependence ${\lambda }_i$ as in part (c). Write $Q={\sum }_i{\lambda }_i\Vert x_i{\Vert }^2$. Reverse every coefficient if necessary so that $Q\ge 0$. Prescribe positive labels when ${\lambda }_i>0$ and negative labels when ${\lambda }_i<0$; zero coefficients may be labelled arbitrarily. If a Euclidean ball realized these labels, its score $g(x)=r^2-\Vert x-c{\Vert }^2$ would satisfyIndeed, every positive-coefficient term is nonnegative and every negative-coefficient term is strictly positive, with at least one of the latter. On the other hand, expanding the score and using the two affine dependence identities givesa contradiction. No $d+2$ points are shattered, completing the exact determination of the VC dimension of Euclidean balls. In the exceptional zero-dimensional Euclidean space, every positive-radius Euclidean ball is the whole singleton space, so the VC dimension is zero.

Every set of at least $d+2$ points in ${\mathbb{R}}^d$ can be partitioned into two nonempty parts with intersecting convex hulls. To see this, take a nonzero affine dependence on $d+2$ of its points. Its positive and negative coefficient sums have the same magnitude $L>0$. Dividing by $L$ expresses one point as a convex combination of the positive-coefficient points and also as a convex combination of the negative-coefficient points. Distribute zero-coefficient and remaining points arbitrarily between the parts. This theorem obstructs arbitrary labels for affine linear classifiers.

The positive-radius closed Euclidean balls in ${\mathbb{R}}^d$ have VC dimension $d+1$ for $d\ge 1$. Vertices of a regular simplex are shattered: interpolate any desired signs by an affine function $a\cdot x+b$, then perturb a sphere through the vertices to the score $1+\eta b+\eta a\cdot x-\Vert x{\Vert }^2$. For the upper bound, take an affine dependence $\lambda$ among $d+2$ points and orient it so that $Q={\sum }_i{\lambda }_i\Vert x_i{\Vert }^2\ge 0$. Labelling the positive coefficients inside and the negative coefficients outside would force ${\sum }_i{\lambda }_i(r^2-\Vert x_i-c{\Vert }^2)>0$, while the affine dependence makes this sum equal $-Q\le 0$. The weaker $d+2$ upper bound from unrestricted lifted affine linear classifiers loses their fixed quadratic coefficient.