Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

YukonModule.PolyFun.PFunctor.Bound.part0

Definition
Yukon_3e259ba73c40aefea227f941

by yukon · Sep 30, 2026 · Mathlib 0df444a (Lean v4.33.1)

better-codes

Source module PolyFun.PFunctor.Bound.

Definition code
/-
Copyright (c) 2026 PolyFun Contributors. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Devon Tuma
-/
module

public import Definitions.Def_Yukon_724dee21e2f24de1aadc0f0e



public import Mathlib.Data.PFunctor.Univariate.Basic
public import Mathlib.Tactic.Common
public import Mathlib.Init
public import Lean.Message
public import Batteries.Tactic.Lint.Basic
public import Init
public import Batteries.Tactic.Lint
public import Mathlib.Data.PFunctor.Multivariate.Basic
public import Mathlib.CategoryTheory.Monad.Types
public import Mathlib.Order.CompleteLattice.Basic
public import Mathlib.Probability.ProbabilityMassFunction.Monad
meta import Definitions.Def_Yukon_724dee21e2f24de1aadc0f0e
set_option backward.isDefEq.respectTransparency.types false
/-!
# Roll Bounds for the Free Monad of a Polynomial Functor

We define `PFunctor.FreeM.IsRollBound oa budget canRoll cost`, a generalized
predicate that bounds the number of `roll` constructors a term `oa : FreeM P α`
unfolds, parameterized by:
- `B` — the budget type
- `budget : B` — the initial budget
- `canRoll : P.A → B → Prop` — whether a `roll` at position `a` is allowed under
  budget `b`
- `cost : P.A → B → B` — how the budget is updated after a `roll` at `a`

The definition is structural via `FreeM.rec`: `pure` satisfies any bound,
and `liftBind a r` satisfies the bound when `canRoll a b` holds and each
continuation `r y` satisfies the bound at `cost a b`.

`OracleComp.IsQueryBound` (in `VCVio/OracleComp/QueryTracking/QueryBound.lean`)
is the specialization of this predicate to `FreeM (spec.toPFunctor)` and is
equal to `IsRollBound` definitionally; the bridge lemma in `QueryBound.lean`
witnesses the equivalence by `Iff.rfl`.
-/

@[expose] public section

universe v w uA uB

namespace PFunctor.FreeM

variable {P : PFunctor.{uA, uB}} {α β : Type v} {B : Type*}

/-- Generalized roll bound on `FreeM P` parameterized by a budget type `B`,
a validity check `canRoll`, and a cost function `cost`. `pure` satisfies any
bound; `roll a r` satisfies the bound when `canRoll a b` holds and every
continuation satisfies the bound at `cost a b`. -/
def IsRollBound (oa : FreeM P α) (budget : B)
    (canRoll : P.A → B → Prop) (cost : P.A → B → B) : Prop :=
  FreeM.rec (motive := fun _ => B → Prop)
    (fun _ _ => True)
    (fun a _r ih b => canRoll a b ∧ ∀ y, ih y (cost a b))
    oa budget

@[simp, grind .]
lemma isRollBound_pure (x : α) (b : B)
    (canRoll : P.A → B → Prop) (cost : P.A → B → B) :
    IsRollBound (pure x : FreeM P α) b canRoll cost := trivial

@[simp, grind =]
lemma isRollBound_lift_bind_iff (a : P.A) (r : P.B a → FreeM P α) (b : B)
    (canRoll : P.A → B → Prop) (cost : P.A → B → B) :
    IsRollBound ((FreeM.lift a).bind r) b canRoll cost ↔
      canRoll a b ∧ ∀ y, IsRollBound (r y) (cost a b) canRoll cost :=
  Iff.rfl

@[grind =]
lemma isRollBound_lift_iff (a : P.A) (b : B)
    (canRoll : P.A → B → Prop) (cost : P.A → B → B) :
    IsRollBound (FreeM.lift a : FreeM P (P.B a)) b canRoll cost ↔ canRoll a b := by
  simp [IsRollBound, lift, - liftBind_eq, ← pure_eq_pure]

private lemma isRollBound_map_aux (oa : FreeM P α) (f : α → β)
    (canRoll : P.A → B → Prop) (cost : P.A → B → B) :
    ∀ {b : B}, (f <$> oa).IsRollBound b canRoll cost ↔
      oa.IsRollBound b canRoll cost := by
  induction oa with
  | pure x => intro b; exact ⟨fun _ => trivial, fun _ => trivial⟩
  | lift_bind a r ih =>
    intro b
    rw [show (f <$> (lift a).bind r) = (lift a).bind (fun y => f <$> r y) from rfl,
      isRollBound_lift_bind_iff, isRollBound_lift_bind_iff]
    exact and_congr_right fun _ => forall_congr' fun y => ih y

@[simp, grind =]
lemma isRollBound_map_iff (oa : FreeM P α) (f : α → β) (b : B)
    (canRoll : P.A → B → Prop) (cost : P.A → B → B) :
    IsRollBound (f <$> oa) b canRoll cost ↔ IsRollBound oa b canRoll cost :=
  isRollBound_map_aux oa f canRoll cost

/-- If `f <$> oa = ob` for any `f`, the roll-bound predicate transfers between
them. The standard shape arises when `oa` and `ob` are two views of the same
underlying computation that agree up to a projection. -/
lemma isRollBound_iff_of_map_eq
    {oa : FreeM P α} {ob : FreeM P β} {f : α → β} {b : B}
    (h : f <$> oa = ob)
    (canRoll : P.A → B → Prop) (cost : P.A → B → B) :
    IsRollBound oa b canRoll cost ↔ IsRollBound ob b canRoll cost := by
  rw [← h]; exact (isRollBound_map_iff oa f b canRoll cost).symm

private lemma isRollBound_congr_aux
    (oa : FreeM P α)
    (canRoll₁ canRoll₂ : P.A → B → Prop) (cost₁ cost₂ : P.A → B → B)
    (hcan : ∀ (a : P.A) (b : B), canRoll₁ a b ↔ canRoll₂ a b)
    (hcost : ∀ (a : P.A) (b : B), cost₁ a b = cost₂ a b) :
    ∀ {b : B}, oa.IsRollBound b canRoll₁ cost₁ ↔ oa.IsRollBound b canRoll₂ cost₂ := by
  induction oa using FreeM.induction <;> intro b <;> grind

lemma isRollBound_congr
    {oa : FreeM P α} {b : B}
    {canRoll₁ canRoll₂ : P.A → B → Prop} {cost₁ cost₂ : P.A → B → B}
    (hcan : ∀ (a : P.A) (b : B), canRoll₁ a b ↔ canRoll₂ a b)
    (hcost : ∀ (a : P.A) (b : B), cost₁ a b = cost₂ a b) :
    oa.IsRollBound b canRoll₁ cost₁ ↔ oa.IsRollBound b canRoll₂ cost₂ :=
  isRollBound_congr_aux oa canRoll₁ canRoll₂ cost₁ cost₂ hcan hcost

/-- Project an `IsRollBound` along a budget projection `proj : B → B'`.

If the source bound at budget `b` validates rolls at every step, the projected
bound at `proj b` is also validated, provided:
* `h_can`  — whenever a step is allowed in the source (`canRoll a b'`), it is
  allowed in the projection (`canRoll' a (proj b')`);
* `h_cost` — the projection commutes with the cost step on the allowed branch
  (`proj (cost a b') = cost' a (proj b')`). -/
lemma IsRollBound.proj
    {B' : Type*} (proj : B → B')
    {oa : FreeM P α} {b : B}
    {canRoll : P.A → B → Prop} {cost : P.A → B → B}
    {canRoll' : P.A → B' → Prop} {cost' : P.A → B' → B'}
    (h_can : ∀ (a : P.A) (b' : B), canRoll a b' → canRoll' a (proj b'))
    (h_cost : ∀ (a : P.A) (b' : B), canRoll a b' → proj (cost a b') = cost' a (proj b'))
    (h : IsRollBound oa b canRoll cost) :
    IsRollBound oa (proj b) canRoll' cost' := by
  induction oa using FreeM.induction generalizing b with
  | pure x => simp
  | lift_bind a r ih =>
      rw [isRollBound_lift_bind_iff] at h ⊢
      refine ⟨h_can a b h.1, fun y => ?_⟩
      have hy : IsRollBound (r y) (proj (cost a b)) canRoll' cost' :=
        ih y (h.2 y)
      rwa [h_cost a b h.1] at hy

/-- Generic bind composition for `IsRollBound` parameterised by an arbitrary
budget type `B` and a binary `combine` operation on it.

The two side conditions are universally quantified so they survive recursion
under `generalizing b₁`:
* `h_can` — extending any validated budget on either side via `combine` keeps
  the roll valid;
* `h_cost` — `cost` distributes left and right over `combine` on validated
  budgets. -/
lemma isRollBound_bind {γ : Type w} {oa : FreeM P α} {ob : α → FreeM P γ}
    {canRoll : P.A → B → Prop} {cost : P.A → B → B}
    (combine : B → B → B) {b₁ b₂ : B}
    (h_can : ∀ a b₁' b₂' b, canRoll a b → canRoll a (combine b₁' b) ∧
      canRoll a (combine b b₂'))
    (h_cost : ∀ a b₁' b₂' b, canRoll a b →
      combine b₁' (cost a b) = cost a (combine b₁' b) ∧
      cost a (combine b b₂') = combine (cost a b) b₂')
    (h₁ : IsRollBound oa b₁ canRoll cost)
    (h₂ : ∀ x, IsRollBound (ob x) b₂ canRoll cost) :
    IsRollBound (FreeM.bind oa ob) (combine b₁ b₂) canRoll cost := by
  induction oa using FreeM.induction generalizing b₁ with
  | pure x =>
      change IsRollBound (ob x) (combine b₁ b₂) canRoll cost
      exact IsRollBound.proj (combine b₁)
        (fun a b hcan => (h_can a b₁ b₂ b hcan).1)
        (fun a b hcan => (h_cost a b₁ b₂ b hcan).1)
        (h₂ x)
  | lift_bind a r ih =>
      rw [isRollBound_lift_bind_iff] at h₁
      rw [FreeM.liftBind_bind, isRollBound_lift_bind_iff]
      refine ⟨(h_can a b₁ b₂ b₁ h₁.1).2, fun y => ?_⟩
      have hrec := ih y (h₁.2 y)
      rw [(h_cost a b₁ b₂ b₁ h₁.1).2]
      exact hrec

/-- Forward-direction `seq` analogue of `isRollBound_bind`. Reduces to the
bind case via `seq_eq_bind_map` plus `isRollBound_map_iff`. -/
lemma isRollBound_seq {og : FreeM P (α → β)} {oa : FreeM P α}
    {canRoll : P.A → B → Prop} {cost : P.A → B → B}
    (combine : B → B → B) {b₁ b₂ : B}
    (h_can : ∀ a b₁' b₂' b, canRoll a b → canRoll a (combine b₁' b) ∧
      canRoll a (combine b b₂'))
    (h_cost : ∀ a b₁' b₂' b, canRoll a b →
      combine b₁' (cost a b) = cost a (combine b₁' b) ∧
      cost a (combine b b₂') = combine (cost a b) b₂')
    (h₁ : IsRollBound og b₁ canRoll cost)
    (h₂ : IsRollBound oa b₂ canRoll cost) :
    IsRollBound (og <*> oa) (combine b₁ b₂) canRoll cost := by
  rw [seq_eq_bind_map]
  exact isRollBound_bind combine h_can h_cost h₁
    (fun g => (isRollBound_map_iff oa g b₂ canRoll cost).mpr h₂)

/-! ### Total roll bounds -/

/-- A total roll bound: `oa` encounters at most `n` `FreeM.liftBind` constructors
along every branch. Each roll consumes one unit of a natural-number budget,
independently of its position. -/
def IsTotalRollBound (oa : FreeM P α) (n : ℕ) : Prop :=
  IsRollBound oa n (fun _ b => 0 < b) (fun _ b => b - 1)

/-- The total-bound specialization exposes the underlying generalized
`IsRollBound` definitionally. -/
theorem isTotalRollBound_iff_isRollBound (oa : FreeM P α) (n : ℕ) :
    IsTotalRollBound oa n ↔
      IsRollBound oa n (fun _ b => 0 < b) (fun _ b => b - 1) :=
  Iff.rfl

@[simp, grind .]
lemma isTotalRollBound_pure (x : α) (n : ℕ) :
    IsTotalRollBound (pure x : FreeM P α) n := trivial

@[simp, grind =]
lemma isTotalRollBound_lift_bind_iff (a : P.A) (r : P.B a → FreeM P α) (n : ℕ) :
    IsTotalRollBound ((FreeM.lift a).bind r) n ↔
      0 < n ∧ ∀ y, IsTotalRollBound (r y) (n - 1) :=
  Iff.rfl

/-- A total roll bound remains valid when its budget is increased. -/
lemma IsTotalRollBound.mono {oa : FreeM P α} {n₁ n₂ : ℕ}
    (h : IsTotalRollBound oa n₁) (hle : n₁ ≤ n₂) :
    IsTotalRollBound oa n₂ := by
  induction oa using FreeM.induction generalizing n₁ n₂ with
  | pure _ => simp
  | lift_bind a r ih =>
      rw [isTotalRollBound_lift_bind_iff] at h ⊢
      exact ⟨Nat.lt_of_lt_of_le h.1 hle,
        fun y => ih y (h.2 y) (Nat.sub_le_sub_right hle 1)⟩

/-- Total roll bounds add under monadic sequencing. This uses the named
`FreeM.bind`, whose result may live in an independent universe; in the
homogeneous specialization it is definitionally the typeclass bind. -/
lemma isTotalRollBound_bind {γ : Type w} {oa : FreeM P α}
    {ob : α → FreeM P γ} {n₁ n₂ : ℕ} (h₁ : IsTotalRollBound oa n₁)
    (h₂ : ∀ x, IsTotalRollBound (ob x) n₂) :
    IsTotalRollBound (FreeM.bind oa ob) (n₁ + n₂) := by
  refine isRollBound_bind (fun a b => a + b) ?_ ?_ h₁ h₂ <;> grind

/-- Total roll bounds add under applicative sequencing. -/
lemma isTotalRollBound_seq {og : FreeM P (α → β)} {oa : FreeM P α}
    {n₁ n₂ : ℕ} (h₁ : IsTotalRollBound og n₁)
    (h₂ : IsTotalRollBound oa n₂) :
    IsTotalRollBound (og <*> oa) (n₁ + n₂) := by
  refine isRollBound_seq (fun a b => a + b) ?_ ?_ h₁ h₂ <;> grind

end PFunctor.FreeM


Source
https://github.com/Verified-zkEVM/PolyFun/blob/dd77aa91dd425ebaec4388270f3a8e3dc7ace571/PolyFun/PFunctor/Bound.lean yukon-proof-operation:3716ac0004d3c876964c636a734b2d1c864a2ae2cd8afc2781c76fb1a8939b3e [yukon-proof-receipt:eyJ2IjoxLCJtYXJrZXIiOiJ5dWtvbi1wcm9vZi1vcGVyYXRpb246MzcxNmFjMDAwNGQzYzg3Njk2NGM2MzZhNzM0YjJkMWM4NjRhMmFlMmNkOGFmYzI3ODFjNzZmYjFhODkzOWIzZSIsImhhc2giOiIzOTM4ODY4NDFmNmQ3ZmI4M2I2MGExMWExZmVkOTU2ZmY0ODg5YjRiNjhkOTFjOTFmYjM3ZjI3YmM4NjE2NWQwIiwia2luZCI6ImRlZmluaXRpb24iLCJ0YXJnZXQiOiJZdWtvbl8zZTI1OWJhNzNjNDBhZWZlYTIyN2Y5NDEiLCJlbnZpcm9ubWVudCI6eyJtYXRobGliUmV2IjoiMGRmNDQ0YTM2MGVhYTYwYWI4YzExZGNhNTFhODZhZjY5Mjk1NTQ3NCIsInRvb2xjaGFpbiI6ImxlYW5wcm92ZXIvbGVhbjQ6djQuMzMuMSJ9LCJ0YWciOiJiZXR0ZXItY29kZXMifQ]

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