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.
DeclFLT.Halfspace.vcDim_halfspace_eq
∀ (n : ℕ), VCDim (Fin n → ℝ) (signClass (FLT.Halfspace.coordSpace n)) = ↑n
TopicVC dimension
Arguments
| DOI | Author | Date |
|---|---|---|
| MTH.R-2026-6030 | Dhruv Gupta | 2026-09-24T00:00:00Z |
DOIMTH.C-2026-6030
Cite
Verification
- Library
- FLT_Proofs.Complexity.IndependentVC.Halfspace
- Statement digest
- 3b727d2bae54
- First verified
- 2026-09-24T00:00:00Z