AFTD Auto-Formalizing Theoretical Domains

random_greedy_survival_poly

def

For a finite simple graph J on a finite vertex type V with decidable equality and decidable adjacency, and a vertex subset A : Finset V, the formal polynomial in ℝ[X] in the variable Y = 1 - t, recursively defined on |E(J)| by mapping each recursive polynomial on J - e and A ∪ V(e) for edges e incident to A via the zero-constant antiderivative p ↦ ∑_n (p.coeff n / (n + 1)) X^(n + 1), summing over all such incident edges e, and setting the constant term to 1 minus the evaluation of this sum at 1, so that it evaluates to 1 at 1.

Statement

noncomputable def random_greedy_survival_poly {V : Type*} [Fintype V] [DecidableEq V]
    (J : SimpleGraph V) [DecidableRel J.Adj] (A : Finset V) : Polynomial ℝ
Defined in
arXiv:2611.13571 Lemma 3.1
Verified
12 Nov 2026
Axioms
none listed
Used by 1
  • random_greedy_survival_probFor a finite simple graph J on a finite vertex type V with decidable equality and decidable adjacency, a vertex subset A : Finset V, and…

Read back from the Lean

A recursive definition of random_greedy_survival_poly, which takes: - a finite type V with decidable equality, - a simple graph J on V with decidable adjacency, and - a finite subset A of vertices of V, and returns a real polynomial Polynomial ℝ. The function is defined by well-founded recursion on the number of edges in J (J.edgeFinset.card): 1. Let incident be the set of edges e in J.edgeFinset that are incident to at least one vertex in A (i.e., ∃ v ∈ A, v ∈ e). 2. For each edge e ∈ incident, make a recursive call to random_greedy_survival_poly on the graph J.deleteEdges {e} with the vertex set A ∪ {endpoints of e}. 3. Take the formal antiderivative vanishing at 0 of each resulting polynomial (mapping $\sum a_n X^n$ to $\sum \frac{a_n}{n+1} X^{n+1}$). 4. Sum these antiderivatives over all e ∈ incident to obtain a polynomial step_sum. 5. Return the polynomial $P(X) = (1 - \text{step\_sum}(1)) + \text{step\_sum}(X)$ (i.e., the unique polynomial with antiderivative part given by step_sum and normalized so that $P(1) = 1$). If incident is empty (e.g. if J has no edges incident to A), step_sum is 0 and the definition yields the constant polynomial 1.

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 survival polynomial of vertex set A in graph J under random greedy matching. -/
noncomputable def random_greedy_survival_poly {V : Type*} [Fintype V] [DecidableEq V]
    (J : SimpleGraph V) [DecidableRel J.Adj] (A : Finset V) : Polynomial ℝ :=
  let incident : Finset (Sym2 V) := J.edgeFinset.filter (fun e => ∃ v ∈ A, v ∈ e)
  let poly_antideriv' (p : Polynomial ℝ) : Polynomial ℝ :=
    ∑ n ∈ p.support, Polynomial.C (p.coeff n / (n + 1 : ℝ)) * Polynomial.X ^ (n + 1)
  let step_sum := ∑ e ∈ incident.attach,
    poly_antideriv' (random_greedy_survival_poly (J.deleteEdges ↑({e.val} : Finset (Sym2 V))) (A ∪ e.val.toMultiset.toFinset))
  Polynomial.C (1 - step_sum.eval 1) + step_sum
termination_by J.edgeFinset.card
decreasing_by
  have he_inc : e.val ∈ incident := e.property
  have he_edge : e.val ∈ J.edgeFinset := (Finset.mem_filter.mp he_inc).1
  have h1 : (J.deleteEdges ↑({e.val} : Finset (Sym2 V))).edgeFinset = J.edgeFinset \ {e.val} :=
    SimpleGraph.edgeFinset_deleteEdges ({e.val} : Finset (Sym2 V))
  rw [h1, Finset.sdiff_singleton_eq_erase]
  exact Finset.card_erase_lt_of_mem he_edge
See it in the graphDiscuss this resultChallenge it