VC dimension

Computed exactly for halfspaces, and bounded in both directions for a dual class.

• MTH.C-2026-6030FLT.Halfspace.vcDim_halfspace_eq

  VC dimension of homogeneous linear halfspaces is exactly n (Cover 1965; Vapnik–Chervonenkis). The class signClass (coordSpace n) of homogeneous linear halfspaces of ℝⁿ has VC dimension equal to the ambient dimension n: the Dudley bound gives ≤ n, and the n standard basis points are shattered, giving ≥ n.

• MTH.C-2026-6031vcDim_dualClass_le

  Assouad's dual VC bound. If VCDim X C ≤ d, then VCDim(dualClass C) ≤ 2^(d+1) − 1.

• MTH.C-2026-6032log₂_vcDim_le_vcDim_dualClass

  Assouad's lower bound. For a finite-VC class, ⌊log₂ VCDim⌋ ≤ VCDim(dualClass): the exponential blow-up under dualization is necessary, not merely permitted. Together with the proven upper bound vcDim_dualClass_le (VCDim(dual) ≤ 2^(VCDim+1) − 1) this sandwiches the dual VC dimension between ⌊log₂ d⌋ and 2^(d+1) − 1.