Cover's Theorem is stated on Wikipedia (and similarly elsewhere) as
A complex pattern-classification problem, cast in a high-dimensional space nonlinearly, is more likely to be linearly separable than in a low-dimensional space, provided that the space is not densely populated.
That exact text doesn't appear in Cover's paper, nor do small variations. I'm trying to figure out which of its six theorems actually correspond to the oft-quoted one. It’s not obvious to me.
Where in Cover 1965 is “Cover's Theorem” actually stated?
The closest parts I can find are Theorem 6, which Cover summarizes
Theorem 6 establishes the probability that a new pattern is ambiguous with respect to a random dichotomy of the training set. This probability is independent of the configuration of the pattern vectors.
and equation 36, which essentially says that the probability of ambiguous generalizations asymptotically approaches zero as the ratio of patterns (i.e. samples) to dimensions increases:
Theorem 6 and equation 36 seem related to Cover's Theorem. But they aren't exactly it, because ambiguous generalization already requires linear separability. The closest thing one could trivially derive from theorem 6 and equation 36 is that the probability of ambiguous generalization increases with dimension. But that's not the same as probability of linear separability increasing with dimension. The "densely populated" or “cast nonlinearly” aspects are also unexplained.
I must be missing/misinterpreting something. Any help is appreciated.