Which theorem in Cover's 1965 paper is actually referred to as Cover's Theorem?

Question

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?

---

Extra Notes

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.

Answer 1

History of the quote

Probably the quote is not originally by Thomas Cover. It occurred in a textbook from 1994 (and later editions) from Simon Haykin (Neural Networks: A Comprehensive Foundation) in section 5.2 Cover's theorem on the separability of patterns. Haykin used the typesetting of a quote, but was more like paraphrasing:

The underlying justification is found in Cover’s theorem on the separability of patterns, which, in qualitative terms, may be stated as follows (Cover, 1965):

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

It may have been copied from there into other works. It is amazing that at some point it got changed into an actual quote and many articles simply copy it as being a quote. This proves once again that many people are actually not checking their original sources and are just copying others.

Relationship with Cover's article

It seems to be a bit unclear what Cover's theorem exactly is. The first theorem in the paper, which Cover calls the Function-Counting Theorem is about linear separability of points n points in d-dimensional space.

In section III of the paper extensions are made to non-linear separability by viewing points in m-dimensional space being mapped to d-dimensional space. The particular quote might refer to that section of the paper and equation 19

In general, for $r$th-order polynomial separating surfaces, the number $L_m(r)$ of separable truth functions of $m$ variables is bounded above by $$L_m(r) \leq C\left(2m ,{m+r \choose m} \right)$$

So the more $m$ variables (which means casting into a higher dimensional space), the easier it becomes to separate the points.