Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Separation of Fd+1F_{d+1}Fd+1​ from FdF_dFd​ by depth-ddd tautologies

Open
FdVersusFdSucc.krajicek_depth_dependent_separation

by Lucas · Oct 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

logicproof-complexity

There is d0d_0d0​ such that for every d≥d0d\ge d_0d≥d0​ there is a family (τm)m∈N(\tau_m)_{m\in\mathbb N}(τm​)m∈N​ of tautologies of depth at most ddd with ∣τm∣≥m|\tau_m|\ge m∣τm​∣≥m such that

  1. for some CCC, each τm\tau_mτm​ has an Fd+1F_{d+1}Fd+1​-proof of size at most C ∣τm∣CC\,|\tau_m|^{C}C∣τm​∣C;
  2. for some ε>0\varepsilon>0ε>0 and all sufficiently large mmm, every FdF_dFd​-proof of τm\tau_mτm​ has size at least 2∣τm∣ε2^{|\tau_m|^{\varepsilon}}2∣τm​∣ε.

This is the case of the problem in which the depth kkk of the tautologies may depend on ddd (with k=dk=dk=d), recorded as known on the Open Problem Garden page.

Formalization Note The statement is asked only for all sufficiently large ddd, to be robust to the offset between depth conventions (here literals have depth 000; in this convention the statement fails for d=1d=1d=1, since depth-1 tautologies have linear-size F1F_1F1​-proofs).

Preamble
import Definitions.Def_FdVersusFdSucc_defs

open Filter
Formal statement
namespace FdVersusFdSucc

/-- (Krajíček 1994, as recorded on the Open Problem Garden page: the problem is solved when `k`
may depend on `d`, with `k := d`.) For all sufficiently large `d` there is a sequence of
depth-`d` tautologies with polynomial-size `F_{d+1}`-proofs that require exponential-size
`F_d`-proofs. -/
theorem krajicek_depth_dependent_separation :
    ∃ d₀ : ℕ, ∀ d : ℕ, d₀ ≤ d → ∃ τ : ℕ → Formula, PolySeparates d d τ := by sorry

end FdVersusFdSucc
Source
J. Krajíček, Lower bounds to the size of constant-depth propositional proofs, J. Symbolic Logic 59(1), 1994, 73-86; stated as known (k := d) on Open Problem Garden, 'F_d versus F_{d+1}' (J. Krajíček), http://www.openproblemgarden.org/op/f_d_versus_f_d_1
Human review
  • Endorsed by Shuze Chen · Oct 11, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Lucas · Oct 11, 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