Repository navigation
Description
Summary
The Lean v4.36.0 update (#1169) brought in mathlib4#41506. Since then, the kernel can refuse a
proof about the support of an OracleComp that samples from a large type. The proof is valid, and
the same proof checks on Lean v4.35.0 with VCVio #1085.
The kernel refuses the proof when it compares x ∈ support mx with x ∈ support my, and mx and
my are definitionally equal but not syntactically equal. Since mathlib4#41506, Set is a
structure, and x ∈ s unfolds to the applied projection s.Mem x. For an applied projection, the
kernel reduces support mx to a Set.ofPred constructor before it compares mx with my.
support is structural, so this reduction runs the computation. For $ᵗ BitVec (2 ^ 32), the
reduction reaches FinEnum.card (BitVec (2 ^ 32)) = 2 ^ (2 ^ 32), which the kernel refuses to
evaluate.
The kernel behaviour is filed upstream as leanprover/lean4#16613, with a reproduction that
does not use Mathlib.
Reproduction
With VCVio at f1e63c7 (Lean v4.36.0, Mathlib fc4f59e):
import VCVio.OracleComp.Constructions.SampleableType.Basic
import VCVio.OracleComp.EvalDist
open OracleComp
/-- Sample a salt of exactly 2^32 bits, then return a constant. -/
def sampleThenFive : ProbComp Nat := do
let _salt ← $ᵗ BitVec (2 ^ 32)
return 5
theorem sampleThenFive_support (r : Nat) : r ∈ support sampleThenFive → r = 5 := by
simp only [sampleThenFive, mem_support_bind_iff, support_pure, Set.mem_singleton_iff]
rintro ⟨_, _, rfl⟩
rflThe elaborator accepts the proof, and the kernel refuses it:
error: (kernel) the kernel refused to evaluate `Nat.pow` because its second argument does not fit in a 32-bit unsigned integer
On Lean v4.35.0 with VCVio #1085 (ed759d2), the kernel accepts the same file.
The examples state their theorems as implications on purpose. With a named hypothesis such as
(h : r ∈ support sampleThenFive), the constructorNameAsVariable linter also fails, on both
Lean versions. That failure has a different cause, which leanprover/lean4#16612 reports.
When the kernel compares different terms under ∈
Each of these steps makes the kernel compare x ∈ support mx with x ∈ support my for different
terms mx and my:
- Unfolding a definition by
unfoldorsimp. These tactics change the goal or hypothesis by
definitional equality and add no rewriting step to the proof term. - Rewriting with
mem_support_bind_ifforsupport_pure. These lemmas statebindandpure
with theMonadinstance. OnOracleComp,donotation elaborates them with
PFunctor.FreeM.instBindandPFunctor.FreeM.instPure(gotcha 13). - Matching
ProbCompwithOracleComp unifSpec.ProbCompis anabbrev, but the kernel
still sees two different terms.
Lemmas stated with the free monad's own instances avoid step 2. We tested such lemmas on a proof
like the one above. The kernel accepted the proof when the computation had type
OracleComp unifSpec Nat. It refused the proof when the computation had type ProbComp Nat,
because of step 3.
The elaborator can also run a concrete computation. With the definitions above, a proof that passes
h : r ∈ support sampleThenFive to a lemma stops with maximum recursion depth has been reached,
even when the types match exactly. An abbrev for sampleThenFive has the same effect. Applying
the lemma to the goal instead, as in exact lemma r, avoids this.
Workaround
Prove the statement once for an abstract parameter. Then rewrite with the equation lemma, whose
right-hand side matches the definition body exactly, and generalize the expensive argument before
you apply the lemma. No step then compares different terms under ∈:
import VCVio.OracleComp.Constructions.SampleableType.Basic
import VCVio.OracleComp.EvalDist
open OracleComp
/-- Sample a salt of `w` bits, then return a constant. -/
def sampleOf (w : Nat) : ProbComp Nat := do
let _salt ← $ᵗ BitVec w
return 5
def sampleThenFive : ProbComp Nat := sampleOf (2 ^ 32)
/-- The statement for every width, proved with `w` abstract. -/
theorem sampleOf_support (w r : Nat) (h : r ∈ support (sampleOf w)) : r = 5 := by
simp only [sampleOf, mem_support_bind_iff, support_pure, Set.mem_singleton_iff] at h
obtain ⟨_, _, rfl⟩ := h
rfl
/-- The concrete statement: rewrite with the equation lemma, then generalize the width. -/
theorem sampleThenFive_support (r : Nat) : r ∈ support sampleThenFive → r = 5 := by
rw [sampleThenFive]
generalize 2 ^ 32 = w
exact sampleOf_support w rThe kernel accepts this file on Lean v4.36.0 with VCVio f1e63c7, and on Lean v4.35.0 with VCVio
ed759d2.
Proposal
Document the behaviour and the workaround in docs/agents/gotchas.md. A pull request that closes
this issue adds them as entry 13b, next to entry 13 on the Bind instance of do notation. The
entry can be removed once Lean changes the kernel behaviour.
🤖 Generated with Claude Code
Activity
dtumad commentedon Nov 21, 2026
Thanks for tracking this down and for the Mathlib-free reproduction in leanprover/lean4#16613, which made the cause easy to see. A follow-up removes the need for the workaround on the VCVio side. Verified-zkEVM/PolyFun#509 makes the free monad's return predicate an inductive
PFunctor.FreeM.CanReturn, and #1204 pins it.x ∈ support mxnow unfolds toCanReturn mx x, which neither the kernel nor the elaborator reduces, so comparing two memberships compares the computations instead of running them.With that change, the proof in this issue checks as first written, with
simp only [sampleThenFive, mem_support_bind_iff, …]and nogeneralize. So doexact sampleThenFive_support r h, anabbrevof the computation, andunfold;VCVioTest/OracleComp/SupportKernel.leankeeps all four. TheconstructorNameAsVariablefailure from leanprover/lean4#16612 also no longer appears on those named hypotheses. AProp-valued recursive predicate would not have been enough: on your example it fails in both the kernel and the elaborator, like the oldSet-valued one.The cost is that
support (pure x) = {x}is no longerrfl. Proofs that used a membership insupport (pure x)as an equation now go througheq_of_mem_support_pureormem_support_pure_iff; VCVio#1204 changes about 40 of them. From their diffs, your open PRs don't rely on that, and #1201 already usesmem_support_pure_iff. A rebase onto the new pin will confirm it.VCVio#1204 rewrites gotcha 13b around this, replacing your entry. Could you check the wording? It keeps the general warning about sets computed by recursion over a program, since lean4#16613 still applies to those. If the downstream proof where you first hit this compares memberships in other recursively computed sets, I'd be glad to look at those too.
chore(deps): pin PolyFun's inductive return predicate and retire the …