Theorem 7 — A polynomial estimate for ground constructor potential
OpenMoserSchneckenreither.constructor_potential_estimateUnder the stated polynomial constructor conditions, the whole-term potential of any ground constructor term at annotation is at most . The zero annotation has potential zero by homogeneity. The estimate concerns the constructor-potential portion of Theorem 7.
import Definitions.Def_MoserSchneckenreither_Typing
namespace MoserSchneckenreither
theorem constructor_potential_estimate {sig : Signature} {P : Problem sig}
(F : AnnotatedSignature P) (hp : PolynomialConstructors F) (v : Term sig)
(q : Annotation) (hg : v.Ground) (hv : v.Constructor) :
potential F v q ≤ q.maxCoeff * (v.size : ℚ≥0) ^ q.degree := by sorry
end MoserSchneckenreitherRead-back
What the Lean code literally says, in plain math · GPT-6 (Codex)
For every finite signature with a natural-number arity for each symbol, a nonempty designated set of constructor symbols and at least one symbol of arity zero, let be any pair of lists of rules, called strict and weak. A rule has a left side whose head is outside the constructor set, and every variable of its right side occurs on the left. Terms are natural-numbered variables or applications of symbols to their arity-many ordered argument terms. An annotation is a finitely supported sequence of nonnegative rational numbers indexed by . Write for the largest coefficient, with , and for the maximum of over the indices with nonzero coefficients, with . An annotated signature specifies a nonempty collection of declarations per symbol, each consisting of one input annotation per argument, a nonnegative rational cost and an output annotation. It also specifies functions and for the input at position and the cost. For every symbol that is a designated constructor or occurs in a left-side argument of a rule from either list, the declarations with any given output consist exactly of the one with inputs and cost , and both functions preserve addition and nonnegative rational scaling in the annotation. Assume that for each designated constructor and each nonzero annotation , , and that for each argument position there exists an annotation with coordinatewise, and . This argument-position condition is vacuous for arity zero. For any term and annotation , define its raw potential as zero at a variable and as at . Define to be this raw potential if is ground and every symbol occurring in it is a designated constructor or occurs in a left-side argument of a rule of , and zero otherwise. For every term with no variable occurrences that is a constructor term, and every annotation , the theorem asserts , where a constructor term is inductively a variable or an application of a designated constructor to constructor terms, and counts one node for each application or variable occurrence and is cast to a nonnegative rational for the inequality. Groundness therefore restricts to constructor applications throughout. The annotation is included and gives a right-hand side of zero.