Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 11 (mass production) — enc(f∧b)=O~(2nb)\mathrm{enc}(f^{\wedge b})=\tilde O(\sqrt{2^n b})enc(f∧b)=O~(2nb​)

Proved
CNFEncComplexity.lemma_11

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

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

There are constants C,KC,KC,K and a deterministic polynomial-time construction such that for every nnn, every f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1} and every b∈[2n]b\in[2^n]b∈[2n] (that is, 1≤b≤2n1\le b\le 2^n1≤b≤2n), writing g=2nbg=\sqrt{2^n b}g=2nb​:

  1. the construction, given nnn, the truth table of fff and bbb, outputs a CNF encoding of f∧bf^{\wedge b}f∧b with input variables 0,…,bn−10,\dots,bn-10,…,bn−1;
  2. this encoding has at most C (g+1)log⁡2(g+2)KC\,(g+1)\log_2(g+2)^KC(g+1)log2​(g+2)K clauses;
  3. consequently
enc(f∧b)≤C (g+1)log⁡2(g+2)K,i.e. enc(f∧b)=O~(2nb).\mathrm{enc}(f^{\wedge b})\le C\,(g+1)\log_2(g+2)^K,\qquad\text{i.e. } \mathrm{enc}(f^{\wedge b})=\tilde O\big(\sqrt{2^n b}\big).enc(f∧b)≤C(g+1)log2​(g+2)K,i.e. enc(f∧b)=O~(2nb​).

Querying a boolean function bbb times costs substantially fewer clauses than bbb independent encodings, which need up to b⋅Ω~(2n)b\cdot\tilde\Omega(\sqrt{2^n})b⋅Ω~(2n​). The proof of Theorem 2 applies the lemma to the advice-lookup function h(j,v)=[A[j]=v]h(j,v)=[A[j]=v]h(j,v)=[A[j]=v].

Formalization Note Time is measured in Mathlib's Turing.TM2ComputableInPolyTime on the input encMassIn (nnn in unary, the 2n2^n2n-bit truth table with x1x_1x1​ the most significant bit, bbb in unary), output CookLevin.encodeFormula; polynomial in that length is polynomial in 2n2^n2n and bbb.

Differences from the source:

  • encoding: Õ(g) = O(g·polylog g) (footnote 2, p.2) → C·(g+1)·log₂(g+2)^K with C, K fixed before the instance; reason: Lean convention for the asymptotic statement; the shifts only matter at g = 0, where the paper's bound O(0) cannot hold for the constant-0 function with enc = 1
  • reading: obtained deterministically in time polynomial in 2ⁿ and b → TM2ComputableInPolyTime encMassIn CookLevin.encodeFormula build, input n and b in unary and the truth table of f; 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_andPow
import Definitions.Def_CNFEncComplexity_encWords
import Definitions.Def_CNFEncComplexity_encMassIn
Formal statement
namespace CNFEncComplexity

/-- **Lemma 11 (mass production).** Krapivin, Przybocki, Subercaseaux, *The CNF Encoding Complexity of Boolean Functions*, arXiv:2611.05614 (held version, sha256 97421ce1…), Lemma 11, p.11 (PDF 12): "Let f : {0, 1}ⁿ → {0, 1}, and let
b ∈ [2ⁿ]. Let f^∧b : {0, 1}^{bn} → {0, 1} be such that for every x⃗₁, . . . , x⃗_b ∈ {0, 1}ⁿ we have
f^∧b(x⃗₁, . . . , x⃗_b) = ⋀_{i∈[b]} f(x⃗ᵢ). Then, enc(f^∧b) = Õ(√(2ⁿb)). Furthermore, such an encoding
can be obtained deterministically in time polynomial in 2ⁿ and b."

There are constants `C, K` and a polynomial-time function `build` such that for every `n`, every
`f : {0,1}ⁿ → {0,1}` and every `1 ≤ b ≤ 2ⁿ`, with `g = √(2ⁿ b)`:
1. `build (n, truthTable f, b)` is a CNF encoding of `f^∧b` with input variables `0, …, bn − 1`;
2. it has at most `C·(g + 1)·log₂(g + 2)^K` clauses;
3. hence `enc(f^∧b) ≤ C·(g + 1)·log₂(g + 2)^K`.

**Formalization Note.** `b ∈ [2ⁿ]` is `1 ≤ b ≤ 2ⁿ`. Õ(g) = O(g·polylog g) (footnote 2, p.2) is
`C·(g + 1)·log₂(g + 2)^K` with `C, K` fixed before `n, f, b`. The construction receives `n` in
unary, the truth table of `f` (entry `v` = `f` at the binary expansion of `v`, `x₁` most
significant; `truthTable`) and `b` in unary (`encMassIn`); polynomial time is Mathlib's
`Turing.TM2ComputableInPolyTime`, output `CookLevin.encodeFormula`. Block `i` of the input of
`f^∧b` is the variables `i·n, …, i·n + n − 1` (`andPow`). -/
theorem lemma_11 :
    ∃ C K : ℕ, ∃ build : ℕ × List Bool × ℕ → CookLevin.Formula,
      Nonempty (Turing.TM2ComputableInPolyTime encMassIn CookLevin.encodeFormula build) ∧
      ∀ (n : ℕ) (f : (Fin n → Bool) → Bool) (b : ℕ), 1 ≤ b → b ≤ 2 ^ n →
        IsEncoding (build (n, truthTable f, b)) (fun i : Fin (b * n) => (i : ℕ)) (andPow f b) ∧
        ((build (n, truthTable f, b)).length : ℝ) ≤
          (C : ℝ) * (Real.sqrt (2 ^ n * (b : ℝ)) + 1) *
            Real.logb 2 (Real.sqrt (2 ^ n * (b : ℝ)) + 2) ^ K ∧
        (enc (andPow f b) : ℝ) ≤
          (C : ℝ) * (Real.sqrt (2 ^ n * (b : ℝ)) + 1) *
            Real.logb 2 (Real.sqrt (2 ^ n * (b : ℝ)) + 2) ^ K := by sorry

end CNFEncComplexity
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614 (held version, sha256 97421ce1…), Lemma 11, p.11 (PDF 12)
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