Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

No Free Lunch, `k`-ary deck form.

Proved
KnownUnresolvedCards.no_free_lunch_kary_expected_score

by raver1975 · Sep 12, 2026 · Mathlib c5ea003 (Lean v4.30.0)

aether-catalogmachinelearning

No Free Lunch, k-ary deck form. A consistent learner over a k-letter label alphabet has expected fair-odds score exactly (k - 1) * |T|: each of the |T| resolved points pays the full k - 1, and the unresolved points pay nothing on average.

theorem KnownUnresolvedCards.no_free_lunch_kary_expected_score(T : Finset X) (L : (X → ZMod k) → (X → ZMod k))
    (hL : ∀ f g : X → ZMod k, (∀ y ∈ T, f y = g y) → L f = L g)
    (hT : ∀ f : X → ZMod k, ∀ y ∈ T, L f y = f y) :
    E (fun f : X → ZMod k => ∑ y : X, (if L f y = f y then ((k : ℚ) - 1) else -1))
      = ((k : ℚ) - 1) * (T.card : ℚ) := by sorry

Formalization Note Transplanted verbatim from the Aether Catalog source MachineLearning/KnownUnresolvedCards/NoFreeLunch.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.

Preamble
-- Thm stub generated from MachineLearning/KnownUnresolvedCards/NoFreeLunch.lean
import Mathlib
import Definitions.Def_MachineLearning_KnownUnresolvedCards_Basic
import Definitions.Def_MachineLearning_KnownUnresolvedCards_NoFreeLunch
/-
Copyright (c) 2025. All rights reserved.
Released under Apache 2.0 license.

# Known versus unresolved cards — V. The learning-theoretic incarnation

The deck of `d` known and `u` unresolved cards has an exact analogue in learning
theory.  Fix a finite domain `X` and let the *target* `f : X → Bool` be uniformly
random.  A learner sees the labels on a training set `T` and outputs a hypothesis
`L f`.  Then:

* the points of `T` are the **known cards** — a consistent learner reproduces
  their labels with certainty;
* the points outside `T` are the **unresolved cards** — and, scored at fair odds,
  each of them has *exactly* zero expected value.

The second statement is Wolpert's No-Free-Lunch phenomenon, and the proof here is
the sharpest possible one: the label-flip at an off-training point is a
fixed-point-free involution of the space of targets which preserves the
hypothesis and negates the score.  The `k`-ary version replaces the involution by
the free action of the cyclic group `ZMod k`.

## Main results

* `sum_offTraining_score_eq_zero` — the involution argument (binary labels).
* `no_free_lunch_expected_score` — **`E[total ±1 score] = |T|` exactly**: the
  learning-theoretic form of "expected payoff is exactly `d`".
* `expected_correct_count` — equivalently, expected accuracy is
  `|T| + (|X| - |T|)/2`: chance level off the training set.
* `training_dependence_is_necessary` — sharpness: a learner allowed to peek at
  off-training labels achieves the maximal score, so the hypothesis that `L`
  depends only on the training labels cannot be dropped.
* `sum_offTraining_kary_score_eq_zero`, `no_free_lunch_kary_expected_score` —
  the `ZMod k` generalisation, with fair odds `(k-1) : 1`.

All of these are instances of the splitting theorem
`expected_total_eq_certain_sum` of `Basic.lean`.
-/


open KnownUnresolvedCards

open Finset

variable {X : Type*} [Fintype X] [DecidableEq X]

/-! ## Binary labels: the flip involution -/










/-! ## `k`-ary labels: the cyclic action -/

variable {k : ℕ} [NeZero k]
Formal statement
theorem KnownUnresolvedCards.no_free_lunch_kary_expected_score(T : Finset X) (L : (X → ZMod k) → (X → ZMod k))
    (hL : ∀ f g : X → ZMod k, (∀ y ∈ T, f y = g y) → L f = L g)
    (hT : ∀ f : X → ZMod k, ∀ y ∈ T, L f y = f y) :
    E (fun f : X → ZMod k => ∑ y : X, (if L f y = f y then ((k : ℚ) - 1) else -1))
      = ((k : ℚ) - 1) * (T.card : ℚ) := by sorry
Source
https://github.com/paulklemstine/Lean/blob/53c2925a02/Catalog/MachineLearning/KnownUnresolvedCards/NoFreeLunch.lean#L253

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me