AFTD Auto-Formalizing Theoretical Domains

is_forward_biased_selector_output

def

A distribution μ is the forward-biased selector output for cache C, hitting probabilities α, and target page e if μ is an optimal solution to the forward-biased linear program and every other optimal solution ν is strictly smaller than μ in lexicographical order Pi.Lex (· < ·) (· < ·).

Statement

def is_forward_biased_selector_output {n : ℕ} (C : Finset (Fin n))
    (α : Fin n → Fin n → ℝ) (e : Fin n) (μ : Fin n → ℝ) : Prop
Defined in
arXiv:2610.40824 Definition 6
Verified
07 Nov 2026
Axioms
none listed
Built on 2
  • is_dominating_distributionA probability distribution μ on Fin n supported on cache C is dominating with respect to pairwise hitting probabilities α if for every…
  • is_forward_biased_optimalA distribution μ is an optimal solution to the forward-biased linear program if μ is a dominating distribution supported on cache C and…
Used by 3

Read back from the Lean

For a given natural number $n$, a subset $C \subseteq \mathrm{Fin}\ n$, a payoff/weight function $\alpha : \mathrm{Fin}\ n \to \mathrm{Fin}\ n \to \mathbb{R}$, an element $e \in \mathrm{Fin}\ n$, and a distribution $\mu : \mathrm{Fin}\ n \to \mathbb{R}$, is_forward_biased_selector_output C α e μ asserts that: 1. $\mu$ is forward-biased optimal with respect to $C, \alpha, e$. 2. For every $\nu : \mathrm{Fin}\ n \to \mathbb{R}$, if $\nu$ is forward-biased optimal with respect to $C, \alpha, e$, then either $\nu = \mu$ or $\nu$ is strictly lexicographically smaller than $\mu$ (under the standard strict ordering on indices $\mathrm{Fin}\ n$ and real numbers $\mathbb{R}$). In other words, $\mu$ is the lexicographically maximal forward-biased optimal distribution.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The lexicographically largest optimal solution to the forward-biased LP. -/
def is_forward_biased_selector_output {n : ℕ} (C : Finset (Fin n))
    (α : Fin n → Fin n → ℝ) (e : Fin n) (μ : Fin n → ℝ) : Prop := is_forward_biased_optimal C α e μ ∧
  ∀ ν, is_forward_biased_optimal C α e ν → (ν = μ ∨ Pi.Lex (· < ·) (· < ·) ν μ)
See it in the graphDiscuss this resultChallenge it