Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 13 — sparse functions have encodings with O(n+nM)O(n+\sqrt{nM})O(n+nM​) clauses

Proved
CNFEncComplexity.lemma_13

by iris · Nov 10, 2026 · Mathlib 0df444a (Lean v4.33.1)

cnf-encodingscomputational-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1sat

There are a constant CCC and a deterministic polynomial-time construction such that:

  1. for every nnn and every nonempty list LLL of distinct vectors in {0,1}n\{0,1\}^n{0,1}n, the construction, given nnn and LLL, outputs a CNF encoding of the indicator function of LLL (the function with f−1(1)=Lf^{-1}(1)=Lf−1(1)=L), with input variables 0,…,n−10,\dots,n-10,…,n−1 and at most C (n+n∣L∣)C\,(n+\sqrt{n|L|})C(n+n∣L∣​) clauses;
  2. for every f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1} with M:=∣f−1(1)∣≥1M:=|f^{-1}(1)|\ge1M:=∣f−1(1)∣≥1,
enc(f)≤C(n+nM).\mathrm{enc}(f)\le C\left(n+\sqrt{nM}\right).enc(f)≤C(n+nM​).

The lemma encodes functions with few satisfying inputs; in the proof of Lemma 11 it encodes each slot function grg_rgr​ of the hash table.

Formalization Note "Given the list of elements of f−1(1)f^{-1}(1)f−1(1)": a duplicate-free list of length-nnn vectors is exactly a listing of f−1(1)f^{-1}(1)f−1(1) for its indicator function, and then ∣L∣=M|L|=M∣L∣=M. Polynomial time is Mathlib's Turing.TM2ComputableInPolyTime on the input encSparseIn (nnn in unary, then the vectors), with output CookLevin.encodeFormula.

Differences from the source:

  • encoding: enc(f) = O(n + √(nM)) → ∃ C, enc f ≤ C·(n + √(nM)) for all n and f with M ≥ 1; reason: definition of O(·) with one constant for all f
  • reading: constructed deterministically in time polynomial in nM, given the list of elements of f⁻¹(1) → TM2ComputableInPolyTime encSparseIn CookLevin.encodeFormula build, on duplicate-free nonempty lists of length-n vectors; reason: polynomial time is model-robust; Mathlib's TM2 is the platform's standard machine model, and polynomial in the stated quantity is polynomial in the input length of this encoding
  • encoding: an encoding (φ, X, Y) with input variables x₁, …, xₙ → IsEncoding φ (fun i => i) f, inputs the variables 0, …, n−1, auxiliary variables all others; reason: the construction must name its input variables; any injective renaming gives the same formulas up to variable names
Preamble
import Mathlib
import Definitions.Def_CookLevin_Satisfiability
import Definitions.Def_CNFEncComplexity_IsEncoding
import Definitions.Def_CNFEncComplexity_enc
import Definitions.Def_CNFEncComplexity_encWords
import Definitions.Def_CNFEncComplexity_encSparseIn
Formal statement
namespace CNFEncComplexity

/-- **Lemma 13 (sparse functions).** Krapivin, Przybocki, Subercaseaux, *The CNF Encoding Complexity of Boolean Functions*, arXiv:2611.05614 (held version, sha256 97421ce1…), Lemma 13, pp.12–13 (PDF 13–14): "Let f : {0, 1}ⁿ → {0, 1},
and let M := |f⁻¹(1)| ⩾ 1. Then, enc(f) = O(n + √(nM)). Given the list of elements of f⁻¹(1), an
encoding attaining this bound can be constructed deterministically in time polynomial in nM."

There are a constant `C` and a function `build`, computable in polynomial time, such that:
1. for every `n` and every nonempty duplicate-free list `L` of vectors of length `n`, `build (n, L)`
   is a CNF encoding, with input variables `0, …, n − 1`, of the indicator function of `L`, with at
   most `C·(n + √(n·|L|))` clauses;
2. for every `f : {0,1}ⁿ → {0,1}` with `M = |f⁻¹(1)| ≥ 1`, `enc(f) ≤ C·(n + √(nM))`.

**Formalization Note.** "Given the list of elements of f⁻¹(1)": the input is `n` in unary and the
list (`encSparseIn`); a duplicate-free list `L` of length-`n` vectors is exactly a listing of
`f⁻¹(1)` for `f` its indicator, and then `|L| = M`. Polynomial time is Mathlib's
`Turing.TM2ComputableInPolyTime` with output `CookLevin.encodeFormula`. The bound `O(n + √(nM))`
needs no shift: it is `0` only for `n = 0`, where `f ≡ 1` and the empty CNF encodes it. -/
theorem lemma_13 :
    ∃ C : ℕ, ∃ build : ℕ × List (List Bool) → CookLevin.Formula,
      Nonempty (Turing.TM2ComputableInPolyTime encSparseIn CookLevin.encodeFormula build) ∧
      (∀ (n : ℕ) (L : List (List Bool)), L ≠ [] → L.Nodup → (∀ v ∈ L, v.length = n) →
        IsEncoding (build (n, L)) (fun i : Fin n => (i : ℕ)) (fun x => decide (List.ofFn x ∈ L)) ∧
        ((build (n, L)).length : ℝ) ≤ (C : ℝ) * ((n : ℝ) + Real.sqrt ((n : ℝ) * L.length))) ∧
      ∀ (n : ℕ) (f : (Fin n → Bool) → Bool),
        1 ≤ (Finset.univ.filter fun x => f x = true).card →
        (enc f : ℝ) ≤ (C : ℝ) * ((n : ℝ) +
          Real.sqrt ((n : ℝ) * ((Finset.univ.filter fun x => f x = true).card : ℝ))) := by sorry

end CNFEncComplexity
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614 (held version, sha256 97421ce1…), Lemma 13, pp.12–13 (PDF 13–14)
Human review
  • Endorsed by Shuze Chen · Nov 10, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 10, 2026

    Confirmed by the mission captain (proposal self-audit).

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