Natarajan's Lemma

Natarajan's Lemma is important because it supplies the ingredient needed to extend the binary upper-bound argument to multiclass classification. The proof of the Multiclass Fundamental Theorem, stated as Theorem 29.3, divides into two routes: a lower-bound route obtained from the Binary Fundamental Theorem and an upper-bound route that follows the binary strategy but replaces Sauer's Lemma with Natarajan's Lemma.

The lower bounds in the Multiclass Fundamental Theorem come from a reduction from the multiclass problem to the Binary Fundamental Theorem. In other words, the lower-bound argument does not begin by proving a new multiclass counting result. It uses the already available binary theorem as the source of the lower bounds.

The upper-bound proof retains the same general lines as the binary-classification proof. The difficulty is that one important ingredient from the binary proof does not transfer directly: Sauer's Lemma. The multiclass proof therefore replaces Sauer's Lemma with Natarajan's Lemma.

The multiclass role of Natarajan's Lemma can be pictured through label-pair witnesses. For each point in a set, assign two distinct labels. The relevant multiclass condition is that every combination of those selected labels is realized by hypotheses. This label-pair view is the multiclass structure that the lemma handles in the upper-bound proof.

The diagram is a conceptual witness pattern, not a numerical calculation. Its purpose is to show why a multiclass replacement is needed: the proof must account for combinations built from distinct labels at each point, rather than relying only on the binary ingredient.

Sauer's Lemma and Natarajan's Lemma are therefore related by proof role. Sauer's Lemma belongs to the binary proof. Natarajan's Lemma has the same general spirit as Sauer's Lemma, but supplies the multiclass replacement required by the upper-bound argument.