Current library: Alpha v34, 4,223 checked-use theorems; Stable remains 432. Historical first admissions, original proof editions, and non-admitted aliases are preserved.
Length is representation length, not polynomial degree. Leading zeros and the empty zero polynomial are allowed; the canonical argument guard x<p also applies to the empty case. Evaluation is defined by actual field-operation steps, not an assumed residue invariant. Polynomial division, gcd, irreducibles and general prime-power extension fields remain open; this does not close G091.
Exact theorem in conservative defined notation
∀ p. ∀ b. ∀ c. ∀ d. ∀ e. ∀ t. ∀ l. ∀ n. ∀ r. Prime(p) → FpCoefficientReduction(p,b,c,d,e,l) → Lt(t,p) → Horner(b,c,t,l,n) → (FpHorner(p,d,e,t,l,r) → CanonicalModularResidue(p,n,r)) ∧ (CanonicalModularResidue(p,n,r) → FpHorner(p,d,e,t,l,r))
Every linked abbreviation expands hygienically to the identical original native formula.
Definition DAG
Actual proof prerequisites
Complete tactic proof in conservative notation
All 74 original proof lines are preserved. Only local proposition formulas are abbreviated; every abbreviation has an exact binder-safe expansion check. The linked exact edition contains the unchanged replay script.
Read the argument
Proof checkpoints
This is a reading aid, not a new proof or a proof-tree certificate. Checkpoint groups are consecutive commands, not inferred branch boundaries. Every step links to the preserved script.
Named ingredients (3)
01Fix variables and assumptionsL1–10
02Fix variables and assumptionsL11–13
03Separate the logical casesL14–14
Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.
- L14
split
04Fix variables and assumptionsL15–15
Work with arbitrary variables or the premises of the current implication.
- L15
intro he
05Use earlier factsL16–25
Instantiate or apply named facts and discharge the corresponding proof obligations.
- L16
specialize prime_field_polynomial_horner_normalization_residue (p) - L17
specialize prime_field_polynomial_horner_normalization_residue (b) - L18
specialize prime_field_polynomial_horner_normalization_residue (c) - L19
specialize prime_field_polynomial_horner_normalization_residue (d) - L20
specialize prime_field_polynomial_horner_normalization_residue (e) - L21
specialize prime_field_polynomial_horner_normalization_residue (t) - L22
specialize prime_field_polynomial_horner_normalization_residue (l) - L23
specialize prime_field_polynomial_horner_normalization_residue (n) - L24
specialize prime_field_polynomial_horner_normalization_residue (r) - L25
apply prime_field_polynomial_horner_normalization_residue
06Use earlier factsL26–29
07Fix variables and assumptionsL30–30
Work with arbitrary variables or the premises of the current implication.
- L30
intro hr
08Establish heL31–40
Establish this local claim before using it. It is not an additional assumption. The following proof commands apply prime field polynomial horner exists.
- L31
have he : ∃ s. FpHorner(p,d,e,t,l,s)Definitions: FpHorner(p,d,e,t,l,s)Original native command in the exact edition - L32
specialize prime_field_polynomial_horner_exists (p) - L33
specialize prime_field_polynomial_horner_exists (d) - L34
specialize prime_field_polynomial_horner_exists (e) - L35
specialize prime_field_polynomial_horner_exists (t) - L36
specialize prime_field_polynomial_horner_exists (l) - L37
apply prime_field_polynomial_horner_exists - L38
exact hp - L39
specialize prime_field_polynomial_normalization_bounded (p) - L40
specialize prime_field_polynomial_normalization_bounded (b)
09Use earlier factsL41–47
Instantiate or apply named facts and discharge the corresponding proof obligations.
- L41
specialize prime_field_polynomial_normalization_bounded (c) - L42
specialize prime_field_polynomial_normalization_bounded (d) - L43
specialize prime_field_polynomial_normalization_bounded (e) - L44
specialize prime_field_polynomial_normalization_bounded (l) - L45
apply prime_field_polynomial_normalization_bounded - L46
exact hred - L47
exact ht
10Separate the logical casesL48–48
Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.
- L48
cases he
11Establish hsL49–58
Establish this local claim before using it. It is not an additional assumption.
- L49
have hs : CanonicalModularResidue(p,n,x)Definitions: CanonicalModularResidue(p,n,x)Original native command in the exact edition - L50
specialize prime_field_polynomial_horner_normalization_residue (p) - L51
specialize prime_field_polynomial_horner_normalization_residue (b) - L52
specialize prime_field_polynomial_horner_normalization_residue (c) - L53
specialize prime_field_polynomial_horner_normalization_residue (d) - L54
specialize prime_field_polynomial_horner_normalization_residue (e) - L55
specialize prime_field_polynomial_horner_normalization_residue (t) - L56
specialize prime_field_polynomial_horner_normalization_residue (l) - L57
specialize prime_field_polynomial_horner_normalization_residue (n) - L58
specialize prime_field_polynomial_horner_normalization_residue (x)
12Use earlier factsL59–63
13Establish heqL64–73
Establish this local claim before using it. It is not an additional assumption. The following proof commands apply binary canonical residue functional.
- L64
have heq : x=r - L65
specialize binary_canonical_residue_functional (p) - L66
specialize binary_canonical_residue_functional (n) - L67
specialize binary_canonical_residue_functional (x) - L68
specialize binary_canonical_residue_functional (r) - L69
apply binary_canonical_residue_functional - L70
exact hs - L71
exact hr - L72
rewrite heq at he_witness - L73
rewrite heq at he_witness
14Use earlier factsL74–74
Instantiate or apply named facts and discharge the corresponding proof obligations.
- L74
exact he_witness
Original defined command ledger · 74 lines
- 0001
intro p - 0002
intro b - 0003
intro c - 0004
intro d - 0005
intro e - 0006
intro t - 0007
intro l - 0008
intro n - 0009
intro r - 0010
intro hp - 0011
intro hred - 0012
intro ht - 0013
intro hn - 0014
split - 0015
intro he - 0016
specialize prime_field_polynomial_horner_normalization_residue (p) - 0017
specialize prime_field_polynomial_horner_normalization_residue (b) - 0018
specialize prime_field_polynomial_horner_normalization_residue (c) - 0019
specialize prime_field_polynomial_horner_normalization_residue (d) - 0020
specialize prime_field_polynomial_horner_normalization_residue (e) - 0021
specialize prime_field_polynomial_horner_normalization_residue (t) - 0022
specialize prime_field_polynomial_horner_normalization_residue (l) - 0023
specialize prime_field_polynomial_horner_normalization_residue (n) - 0024
specialize prime_field_polynomial_horner_normalization_residue (r) - 0025
apply prime_field_polynomial_horner_normalization_residue - 0026
exact hp - 0027
exact hred - 0028
exact hn - 0029
exact he - 0030
intro hr - 0031
have he : ∃ s. FpHorner(p,d,e,t,l,s) - 0032
specialize prime_field_polynomial_horner_exists (p) - 0033
specialize prime_field_polynomial_horner_exists (d) - 0034
specialize prime_field_polynomial_horner_exists (e) - 0035
specialize prime_field_polynomial_horner_exists (t) - 0036
specialize prime_field_polynomial_horner_exists (l) - 0037
apply prime_field_polynomial_horner_exists - 0038
exact hp - 0039
specialize prime_field_polynomial_normalization_bounded (p) - 0040
specialize prime_field_polynomial_normalization_bounded (b) - 0041
specialize prime_field_polynomial_normalization_bounded (c) - 0042
specialize prime_field_polynomial_normalization_bounded (d) - 0043
specialize prime_field_polynomial_normalization_bounded (e) - 0044
specialize prime_field_polynomial_normalization_bounded (l) - 0045
apply prime_field_polynomial_normalization_bounded - 0046
exact hred - 0047
exact ht - 0048
cases he - 0049
have hs : CanonicalModularResidue(p,n,x) - 0050
specialize prime_field_polynomial_horner_normalization_residue (p) - 0051
specialize prime_field_polynomial_horner_normalization_residue (b) - 0052
specialize prime_field_polynomial_horner_normalization_residue (c) - 0053
specialize prime_field_polynomial_horner_normalization_residue (d) - 0054
specialize prime_field_polynomial_horner_normalization_residue (e) - 0055
specialize prime_field_polynomial_horner_normalization_residue (t) - 0056
specialize prime_field_polynomial_horner_normalization_residue (l) - 0057
specialize prime_field_polynomial_horner_normalization_residue (n) - 0058
specialize prime_field_polynomial_horner_normalization_residue (x) - 0059
apply prime_field_polynomial_horner_normalization_residue - 0060
exact hp - 0061
exact hred - 0062
exact hn - 0063
exact he_witness - 0064
have heq : x=r - 0065
specialize binary_canonical_residue_functional (p) - 0066
specialize binary_canonical_residue_functional (n) - 0067
specialize binary_canonical_residue_functional (x) - 0068
specialize binary_canonical_residue_functional (r) - 0069
apply binary_canonical_residue_functional - 0070
exact hs - 0071
exact hr - 0072
rewrite heq at he_witness - 0073
rewrite heq at he_witness - 0074
exact he_witness