AFTD Auto-Formalizing Theoretical Domains

is_dominating_distribution

def

A probability distribution μ on Fin n supported on cache C is dominating with respect to pairwise hitting probabilities α if for every resident page q in C, the expected probability that a page drawn from μ is requested before q is at most 1/2.

Statement

def is_dominating_distribution {n : ℕ} (C : Finset (Fin n))
    (α : Fin n → Fin n → ℝ) (μ : Fin n → ℝ) : Prop
Defined in
arXiv:2610.40824 Definition 6, eq. (2)
Verified
07 Nov 2026
Axioms
none listed
Used by 4

Read back from the Lean

Given a natural number $n$, a subset $C \subseteq \mathrm{Fin}(n)$, a function $\alpha : \mathrm{Fin}(n) \to \mathrm{Fin}(n) \to \mathbb{R}$, and a function $\mu : \mathrm{Fin}(n) \to \mathbb{R}$, is_dominating_distribution C α μ asserts that: 1. For every $p \in \mathrm{Fin}(n)$, $\mu(p) \ge 0$; 2. The sum of $\mu(p)$ over all $p \in \mathrm{Fin}(n)$ is equal to $1$; 3. For every $p \in \mathrm{Fin}(n)$, if $p \notin C$, then $\mu(p) = 0$ (so $\mu$ is supported on $C$); 4. For every $q \in C$, the sum $\sum_{p \in C} \mu(p) \cdot \alpha(p, q) \le \frac{1}{2}$.

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

/-- A distribution μ supported on C is dominating if ∑_{p ∈ C} μ(p) α(p, q) ≤ 1/2 for all q ∈ C. -/
def is_dominating_distribution {n : ℕ} (C : Finset (Fin n))
    (α : Fin n → Fin n → ℝ) (μ : Fin n → ℝ) : Prop := (∀ p, 0 ≤ μ p) ∧
  (∑ p, μ p = 1) ∧
  (∀ p, p ∉ C → μ p = 0) ∧
  (∀ q ∈ C, ∑ p ∈ C, μ p * α p q ≤ 1 / 2)
See it in the graphDiscuss this resultChallenge it