Cover's theorem¶

Count the binary labelings of general-position points that a specified linear threshold family can separate.

Version: v1 · 2026-10-17 · History
Domain-specific #: 14110
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomains: Combinatorial Geometry, Pattern Recognition → Mathematics
Aliases: Function-counting theorem, Cover's function-counting theorem

Core Idea¶

Cover's function-counting theorem counts how many of the \(2^N\) binary labelings of \(N\) measured points can be separated by a declared linear threshold family. For \(N\) vectors in general position in a \(d\)-dimensional feature space, with a hyperplane through the origin, the count is \(C(N,d)=2\sum_{k=0}^{d-1}\binom{N-1}{k}\). General position here requires every subset of at most \(d\) measured vectors to be linearly independent. A labeling counts only if a weight vector puts every point strictly on its assigned side.[^ref-6b9f72b97122] Cardinality supplies the set-size concept; the separator geometry supplies this particular exact count.

Scope of Application¶

Use the theorem for a fixed finite point set, binary labels, a declared separator family and general position in its effective feature space.[^ref-6b9f72b97122]

Homogeneous thresholds: Separate the original measured vectors with a hyperplane through the origin.
Affine thresholds: Lift \(x\in\mathbb R^m\) to \((1,x)\) in \(m+1\) dimensions to include an intercept.[^ref-6b9f72b97122]
Mapped surface families: Declare the feature map before counting; curved boundaries may result in the original space.[^ref-6b9f72b97122]
Capacity comparisons: Compare \(C(N,d)\) with \(2^N\) only for the same fixed point set and family.
General-position boundary: Apply the exact formula only when the mapped vectors satisfy the needed independence condition.[^ref-6b9f72b97122]

Clarity¶

\(2^N\) counts all labelings; \(C(N,d)\) counts the separable ones. Their ratio is a probability only if labels are chosen uniformly. At \(N=2d\), the ratio equals one half; that means half of complete labelings can be separated, not that a trained classifier is correct on half the points.[^ref-6b9f72b97122] In the homogeneous case all labelings are separable when \(N\le d\). For affine separation in \(\mathbb R^m\) the corresponding threshold is \(N\le m+1\), under the mapped general-position condition.

Manages Complexity¶

The binomial sum replaces a separate separator-feasibility test for each of \(2^N\) assignments. It gives the total count without identifying which individual assignments work or how an algorithm finds their separating weights. If the measured vectors are dependent, the exact count may change, so a feature dimension alone is not enough.[^ref-6b9f72b97122]

Abstract Reasoning¶

Fix the patterns and their feature map; state whether the separator is homogeneous or affine; verify general position; then count realizable labelings in that effective dimension. For three vectors \((1,0),(0,1),(1,1)\) in \(\mathbb R^2\), every pair is independent, so the theorem gives \(C(3,2)=6\) of eight sign assignments. The missing assignments are \((+,+,-)\) and \((-,-,+)\) because the third vector is the sum of the first two. This small case shows what the total counts without claiming to identify a learning algorithm.

Knowledge Transfer¶

The same count applies after a valid feature map when the mapped vectors meet the theorem's independence condition; Cover treats linear, spherical and polynomial families this way.[^ref-6b9f72b97122] Transfer the pattern fixed binary assignments → declared separator family → general-position mapped vectors → exact number realizable, not a numeric count divorced from its feature dimension. Linear separability asks whether one labeled set has a separator; Cover's theorem counts across all assignments of the fixed point set.

[^ref-6b9f72b97122]: Thomas M. Cover, “Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition,” IEEE Transactions on Electronic Computers EC-14, no. 3 (1965): 326–334, doi:10.1109/PGEC.1965.264137. https://isl.stanford.edu/~cover/papers/paper2.pdf . Original full article inspected: printed p.326 Theorem 1 and definitions; pp.327–330 measurement-map generalization, Figure 1 and Table I; pp.330–332 random-label capacity and separate generalization analysis.

Relationships to Other Abstractions¶

Current abstraction Cover's theorem Domain-specific

Parents (1) — more general patterns this builds on

Cover's theorem presupposes Cardinality Prime

The theorem counts the cardinality of realizable dichotomies among all binary labelings.

Hierarchy paths (5) — routes to 3 parentless roots

Cover's theorem → Cardinality → Bijectivity → Function (Mapping)

Show alternative paths (4)

Neighborhood in Abstraction Space¶

Cover's theorem sits in a sparse region of the domain-specific corpus (87^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2721 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-17