Concepts / The Binary Fundamental Theorem

The Binary Fundamental Theorem

The proof of the Multiclass Fundamental Theorem is easiest to understand as two separate routes.

  • Programming

The Proof Map

The proof of the Multiclass Fundamental Theorem is easiest to understand as two separate routes. The lower-bound route reduces the multiclass problem to the Binary Fundamental Theorem. The upper-bound route keeps the general strategy used for binary classification, but replaces one ingredient that does not transfer directly: Sauer's Lemma is replaced by Natarajan's Lemma.

Multiclass theoremLower-bound routeReduction to binary theoremLower boundsUpper-bound routeBinary strategy withreplacementUpper boundsbranchbranchestablishesestablishes
How do the lower-bound and upper-bound arguments branch into different proof routes, and what does each route establish?

The Lower-Bound Route

The lower bounds are obtained by reduction. Instead of proving the multiclass lower bounds from scratch, the argument reduces the multiclass problem to the Binary Fundamental Theorem. The binary result then supplies the lower-bound information needed for the multiclass theorem.

Worked example

Reading a Reduction-Based Lower Bound

Identify the logical role of the lower-bound argument in the Multiclass Fundamental Theorem proof.

  1. 1
    Begin with the multiclass problem

    The proof needs lower bounds for the multiclass setting.

  2. 2
    Apply the reduction

    The multiclass lower-bound question is reduced to the Binary Fundamental Theorem.

  3. 3
    Use the binary result

    The Binary Fundamental Theorem provides the lower-bound basis for the multiclass conclusion.

Result

The lower-bound route is a reduction route: it obtains the multiclass lower bounds from the Binary Fundamental Theorem.

The Upper-Bound Route

The upper-bound proof follows the same general lines as the binary-classification proof. However, the binary strategy cannot be transferred unchanged. One important ingredient must be replaced: Sauer's Lemma is not retained as the counting ingredient for the multiclass argument. Natarajan's Lemma takes its place.

Binary upper-boundstrategyOverall proof linesSauer's LemmaBinary ingredientMulticlassupper-boundstrategySame general linesNatarajan's LemmaMulticlass replacementusesuses instead
What key ingredient changes when the binary upper-bound proof is adapted to the multiclass setting, and where does that replacement occur?

The important distinction is between the proof strategy and the proof ingredient. The strategy remains recognizable from the binary proof. The ingredient changes precisely where the binary argument uses Sauer's Lemma. Natarajan's Lemma supplies the multiclass replacement, and its proof has the same general spirit as Sauer's Lemma.

Two Lemmas, Different Roles

LemmaRole in the proofSetting described by the source
Sauer's LemmaThe ingredient used in the binary upper-bound proofBinary classification
Natarajan's LemmaThe replacement ingredient in the multiclass upper-bound proofMulticlass classification

The multiclass proof preserves the binary upper-bound strategy but changes the lemma used at the nontransferable step.

The source distinguishes the lemmas by their positions in the proof. Sauer's Lemma belongs to the binary upper-bound argument. Natarajan's Lemma occupies the corresponding position in the multiclass argument. The point is not that the entire binary proof is discarded; rather, the binary counting ingredient is replaced while the overall proof strategy is retained.

A Complete Proof Trace

Worked example

Tracing Theorem 29.3

Put the major proof moves in the order described by the source.

  1. 1
    Separate the goals

    Treat the lower-bound and upper-bound parts as two distinct proof routes.

  2. 2
    Establish the lower bounds

    Reduce the multiclass problem to the Binary Fundamental Theorem.

  3. 3
    Retain the upper-bound strategy

    Follow the same general lines as the binary-classification proof.

  4. 4
    Replace the nontransferable ingredient

    Replace Sauer's Lemma with Natarajan's Lemma for the multiclass upper-bound argument.

  5. 5
    Combine the routes

    The reduction supplies the lower bounds, while the adapted upper-bound proof supplies the upper bounds.

Result

The proof of the Multiclass Fundamental Theorem has a lower-bound reduction and an upper-bound adaptation, joined in the final theorem.

Separate boundsLower and upper routesBinary reductionLower-bound routeMulticlass theoremLower and upper boundsUpper-boundadaptationBinary strategy retainedNatarajan's LemmaReplaces Sauer's Lemmalower routeupper routechange ingredientsupplies lower boundssupports upper bounds
What is the order of the lower-bound construction, combinatorial lemma, and upper-bound argument, and how do these steps connect to the final theorem?

Common Proof-Reading Mistakes

  • Common mistake

    Treating the proof as one undivided argument

    What it looks like

    Describing only a single route from the binary theorem to the multiclass theorem

    Why it fails

    The proof divides naturally into separate lower-bound and upper-bound routes.

    Do this instead

    Identify which route establishes lower bounds and which route establishes upper bounds.

  • Common mistake

    Assuming Sauer's Lemma transfers unchanged

    What it looks like

    Saying that the multiclass upper-bound proof simply reuses Sauer's Lemma

    Why it fails

    The source identifies Sauer's Lemma as the important ingredient that must be replaced.

    Do this instead

    State that Natarajan's Lemma replaces Sauer's Lemma in the multiclass upper-bound argument.

  • Common mistake

    Thinking the entire binary strategy is discarded

    What it looks like

    Describing the multiclass proof as unrelated to the binary proof

    Why it fails

    The upper-bound proof follows the same general lines as the binary-classification proof.

    Do this instead

    Separate the retained strategy from the replaced ingredient.

  • Common mistake

    Reversing the lemma roles

    What it looks like

    Assigning Natarajan's Lemma to the binary proof and Sauer's Lemma to the multiclass replacement

    Why it fails

    The source assigns Sauer's Lemma to the binary upper-bound proof and Natarajan's Lemma to its multiclass replacement.

    Do this instead

    Remember: Sauer for the binary ingredient, Natarajan for the multiclass replacement.

Check Your Understanding

MEDIUM

Explain in two or three sentences why the upper-bound proof can be described as both similar to and different from the binary proof.

Hints
  • Identify what remains the same at the level of overall strategy.
  • Identify the one important ingredient that changes.
EASY

Classify each statement as describing the lower-bound route or the upper-bound route: reduction to the Binary Fundamental Theorem; replacement of Sauer's Lemma; same general lines as the binary-classification proof; obtaining the lower bounds.

Hints
  • The lower-bound route is defined by reduction.
  • The upper-bound route keeps the binary strategy but changes its key lemma.

Final Takeaways

  1. 1
    The Multiclass Fundamental Theorem proof has separate lower-bound and upper-bound routes.
  2. 2
    The lower bounds come from reducing the multiclass problem to the Binary Fundamental Theorem.
  3. 3
    The upper-bound proof retains the general binary strategy.
  4. 4
    Sauer's Lemma is the binary ingredient that must be replaced.
  5. 5
    Natarajan's Lemma supplies the multiclass replacement and has the same general spirit as Sauer's Lemma.

At a glance

  • The proof separates naturally into lower-bound and upper-bound routes.
  • A reduction from the Binary Fundamental Theorem gives the multiclass lower bounds.
  • The upper-bound route follows the binary proof strategy but replaces Sauer's Lemma.
  • Natarajan's Lemma is the multiclass replacement for Sauer's Lemma.
  • The central proof-reading skill is distinguishing the retained strategy from the changed ingredient.

Related Topics

Related concepts

More concepts starting with T