Current library: Alpha v34, 4,223 checked-use theorems; Stable remains 432. Historical first admissions, original proof editions, and non-admitted aliases are preserved.
Coefficients are highest-degree-first. The divisor has a nonzero decoded head; primality supplies its actual inverse. Empty quotients and remainders are included. Functionality compares the constructed execution lengths and decoded coefficients, never arbitrary beta codes. Formal polynomial equivalence compares every coefficient, not evaluations on a finite field. The formal identity and remainder-degree bound are proved separately, not assumed by the execution graph. Arbitrary quotient/remainder-pair uniqueness from a formal identity, multiplication associativity, gcd/Bezout, irreducible-polynomial existence, and the full G091 prime-power-field goal remain open. The seven displayed new names are conservative first-order notation, not new kernel primitives.
Exact theorem in conservative defined notation
∀ p. ∀ k. ∀ ab. ∀ ac. ∀ bb. ∀ bc. ∀ M. ∀ qb. ∀ qc. ∀ QB. ∀ QC. ∀ N. FpPolynomialQuotientPrefix(p,k,ab,ac,bb,bc,M,qb,qc,N) → FpPolynomialQuotientPrefix(p,k,ab,ac,bb,bc,M,QB,QC,N) → BetaPrefixEqual(qb,qc,QB,QC,N)
Every linked abbreviation expands hygienically to the identical original native formula.
Definition DAG
Actual proof prerequisites
Complete tactic proof in conservative notation
All 130 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–12
03Induction on NL13–19
04Separate the logical casesL20–20
Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.
- L20
exfalso
05Use earlier factsL21–26
06Fix variables and assumptionsL27–28
07Establish hequalL29–38
Establish this local claim before using it. It is not an additional assumption. The following proof commands apply IH.
- L29
have hequal : BetaPrefixEqual(qb,qc,QB,QC,N)Definitions: BetaPrefixEqual(qb,qc,QB,QC,N)Original native command in the exact edition - L30
apply IH - L31
specialize prime_field_polynomial_quotient_prefix_restrict (p) - L32
specialize prime_field_polynomial_quotient_prefix_restrict (k) - L33
specialize prime_field_polynomial_quotient_prefix_restrict (ab) - L34
specialize prime_field_polynomial_quotient_prefix_restrict (ac) - L35
specialize prime_field_polynomial_quotient_prefix_restrict (bb) - L36
specialize prime_field_polynomial_quotient_prefix_restrict (bc) - L37
specialize prime_field_polynomial_quotient_prefix_restrict (M) - L38
specialize prime_field_polynomial_quotient_prefix_restrict (qb)
08Use earlier factsL39–48
Instantiate or apply named facts and discharge the corresponding proof obligations.
- L39
specialize prime_field_polynomial_quotient_prefix_restrict (qc) - L40
specialize prime_field_polynomial_quotient_prefix_restrict (S N) - L41
specialize prime_field_polynomial_quotient_prefix_restrict (N) - L42
apply prime_field_polynomial_quotient_prefix_restrict - L43
specialize le_succ (N) - L44
specialize le_succ (N) - L45
apply le_succ - L46
specialize le_refl (N) - L47
apply le_refl - L48
exact hfirst
09Use earlier factsL49–58
Instantiate or apply named facts and discharge the corresponding proof obligations.
- L49
specialize prime_field_polynomial_quotient_prefix_restrict (p) - L50
specialize prime_field_polynomial_quotient_prefix_restrict (k) - L51
specialize prime_field_polynomial_quotient_prefix_restrict (ab) - L52
specialize prime_field_polynomial_quotient_prefix_restrict (ac) - L53
specialize prime_field_polynomial_quotient_prefix_restrict (bb) - L54
specialize prime_field_polynomial_quotient_prefix_restrict (bc) - L55
specialize prime_field_polynomial_quotient_prefix_restrict (M) - L56
specialize prime_field_polynomial_quotient_prefix_restrict (QB) - L57
specialize prime_field_polynomial_quotient_prefix_restrict (QC) - L58
specialize prime_field_polynomial_quotient_prefix_restrict (S N)
10Use earlier factsL59–66
Instantiate or apply named facts and discharge the corresponding proof obligations.
11Fix variables and assumptionsL67–70
12Establish hcaseL71–75
Establish this local claim before using it. It is not an additional assumption. The following proof commands apply finite lt succ eq or lt.
13Separate the logical casesL76–76
Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.
- L76
cases hcase
14Calculate and transport equalitiesL77–80
15Establish hchosenL81–85
Establish this local claim before using it. It is not an additional assumption. The following proof commands apply hsecond.
- L81
have hchosen : ∃ r. BetaAt(QB,QC,N,r) ∧ FpPolynomialQuotientStep(p,k,ab,ac,bb,bc,M,QB,QC,N,r)Definitions: BetaAt(QB,QC,N,r)FpPolynomialQuotientStep(p,k,ab,ac,bb,bc,M,QB,QC,N,r)Original native command in the exact edition - L82
specialize hsecond (N) - L83
apply hsecond - L84
specialize le_refl (S N) - L85
apply le_refl
16Separate the logical casesL86–87
17Establish hlastL88–97
Establish this local claim before using it. It is not an additional assumption.
- L88
have hlast : a=x - L89
specialize prime_field_polynomial_quotient_step_prefix_functional (p) - L90
specialize prime_field_polynomial_quotient_step_prefix_functional (k) - L91
specialize prime_field_polynomial_quotient_step_prefix_functional (ab) - L92
specialize prime_field_polynomial_quotient_step_prefix_functional (ac) - L93
specialize prime_field_polynomial_quotient_step_prefix_functional (bb) - L94
specialize prime_field_polynomial_quotient_step_prefix_functional (bc) - L95
specialize prime_field_polynomial_quotient_step_prefix_functional (M) - L96
specialize prime_field_polynomial_quotient_step_prefix_functional (qb) - L97
specialize prime_field_polynomial_quotient_step_prefix_functional (qc)
18Use earlier factsL98–107
Instantiate or apply named facts and discharge the corresponding proof obligations.
- L98
specialize prime_field_polynomial_quotient_step_prefix_functional (QB) - L99
specialize prime_field_polynomial_quotient_step_prefix_functional (QC) - L100
specialize prime_field_polynomial_quotient_step_prefix_functional (N) - L101
specialize prime_field_polynomial_quotient_step_prefix_functional (a) - L102
specialize prime_field_polynomial_quotient_step_prefix_functional (x) - L103
apply prime_field_polynomial_quotient_step_prefix_functional - L104
exact hequal - L105
specialize prime_field_polynomial_quotient_prefix_entry (p) - L106
specialize prime_field_polynomial_quotient_prefix_entry (k) - L107
specialize prime_field_polynomial_quotient_prefix_entry (ab)
19Use earlier factsL108–117
Instantiate or apply named facts and discharge the corresponding proof obligations.
- L108
specialize prime_field_polynomial_quotient_prefix_entry (ac) - L109
specialize prime_field_polynomial_quotient_prefix_entry (bb) - L110
specialize prime_field_polynomial_quotient_prefix_entry (bc) - L111
specialize prime_field_polynomial_quotient_prefix_entry (M) - L112
specialize prime_field_polynomial_quotient_prefix_entry (qb) - L113
specialize prime_field_polynomial_quotient_prefix_entry (qc) - L114
specialize prime_field_polynomial_quotient_prefix_entry (S N) - L115
specialize prime_field_polynomial_quotient_prefix_entry (N) - L116
specialize prime_field_polynomial_quotient_prefix_entry (a) - L117
apply prime_field_polynomial_quotient_prefix_entry
20Use earlier factsL118–122
21Calculate and transport equalitiesL123–124
Original defined command ledger · 130 lines
- 0001
intro p - 0002
intro k - 0003
intro ab - 0004
intro ac - 0005
intro bb - 0006
intro bc - 0007
intro M - 0008
intro qb - 0009
intro qc - 0010
intro QB - 0011
intro QC - 0012
intro N - 0013
induction N - 0014
intro hfirst - 0015
intro hsecond - 0016
intro i - 0017
intro a - 0018
intro hindex - 0019
intro hvalue - 0020
exfalso - 0021
specialize lt_not_le (i) - 0022
specialize lt_not_le (0) - 0023
apply lt_not_le - 0024
exact hindex - 0025
specialize zero_le (i) - 0026
apply zero_le - 0027
intro hfirst - 0028
intro hsecond - 0029
have hequal : BetaPrefixEqual(qb,qc,QB,QC,N) - 0030
apply IH - 0031
specialize prime_field_polynomial_quotient_prefix_restrict (p) - 0032
specialize prime_field_polynomial_quotient_prefix_restrict (k) - 0033
specialize prime_field_polynomial_quotient_prefix_restrict (ab) - 0034
specialize prime_field_polynomial_quotient_prefix_restrict (ac) - 0035
specialize prime_field_polynomial_quotient_prefix_restrict (bb) - 0036
specialize prime_field_polynomial_quotient_prefix_restrict (bc) - 0037
specialize prime_field_polynomial_quotient_prefix_restrict (M) - 0038
specialize prime_field_polynomial_quotient_prefix_restrict (qb) - 0039
specialize prime_field_polynomial_quotient_prefix_restrict (qc) - 0040
specialize prime_field_polynomial_quotient_prefix_restrict (S N) - 0041
specialize prime_field_polynomial_quotient_prefix_restrict (N) - 0042
apply prime_field_polynomial_quotient_prefix_restrict - 0043
specialize le_succ (N) - 0044
specialize le_succ (N) - 0045
apply le_succ - 0046
specialize le_refl (N) - 0047
apply le_refl - 0048
exact hfirst - 0049
specialize prime_field_polynomial_quotient_prefix_restrict (p) - 0050
specialize prime_field_polynomial_quotient_prefix_restrict (k) - 0051
specialize prime_field_polynomial_quotient_prefix_restrict (ab) - 0052
specialize prime_field_polynomial_quotient_prefix_restrict (ac) - 0053
specialize prime_field_polynomial_quotient_prefix_restrict (bb) - 0054
specialize prime_field_polynomial_quotient_prefix_restrict (bc) - 0055
specialize prime_field_polynomial_quotient_prefix_restrict (M) - 0056
specialize prime_field_polynomial_quotient_prefix_restrict (QB) - 0057
specialize prime_field_polynomial_quotient_prefix_restrict (QC) - 0058
specialize prime_field_polynomial_quotient_prefix_restrict (S N) - 0059
specialize prime_field_polynomial_quotient_prefix_restrict (N) - 0060
apply prime_field_polynomial_quotient_prefix_restrict - 0061
specialize le_succ (N) - 0062
specialize le_succ (N) - 0063
apply le_succ - 0064
specialize le_refl (N) - 0065
apply le_refl - 0066
exact hsecond - 0067
intro i - 0068
intro a - 0069
intro hindex - 0070
intro hvalue - 0071
have hcase : i = N ∨ Lt(i,N) - 0072
specialize finite_lt_succ_eq_or_lt (N) - 0073
specialize finite_lt_succ_eq_or_lt (i) - 0074
apply finite_lt_succ_eq_or_lt - 0075
exact hindex - 0076
cases hcase - 0077
rewrite hcase_left at hvalue - 0078
rewrite hcase_left at hvalue - 0079
rewrite hcase_left - 0080
rewrite hcase_left - 0081
have hchosen : ∃ r. BetaAt(QB,QC,N,r) ∧ FpPolynomialQuotientStep(p,k,ab,ac,bb,bc,M,QB,QC,N,r) - 0082
specialize hsecond (N) - 0083
apply hsecond - 0084
specialize le_refl (S N) - 0085
apply le_refl - 0086
cases hchosen - 0087
cases hchosen_witness - 0088
have hlast : a=x - 0089
specialize prime_field_polynomial_quotient_step_prefix_functional (p) - 0090
specialize prime_field_polynomial_quotient_step_prefix_functional (k) - 0091
specialize prime_field_polynomial_quotient_step_prefix_functional (ab) - 0092
specialize prime_field_polynomial_quotient_step_prefix_functional (ac) - 0093
specialize prime_field_polynomial_quotient_step_prefix_functional (bb) - 0094
specialize prime_field_polynomial_quotient_step_prefix_functional (bc) - 0095
specialize prime_field_polynomial_quotient_step_prefix_functional (M) - 0096
specialize prime_field_polynomial_quotient_step_prefix_functional (qb) - 0097
specialize prime_field_polynomial_quotient_step_prefix_functional (qc) - 0098
specialize prime_field_polynomial_quotient_step_prefix_functional (QB) - 0099
specialize prime_field_polynomial_quotient_step_prefix_functional (QC) - 0100
specialize prime_field_polynomial_quotient_step_prefix_functional (N) - 0101
specialize prime_field_polynomial_quotient_step_prefix_functional (a) - 0102
specialize prime_field_polynomial_quotient_step_prefix_functional (x) - 0103
apply prime_field_polynomial_quotient_step_prefix_functional - 0104
exact hequal - 0105
specialize prime_field_polynomial_quotient_prefix_entry (p) - 0106
specialize prime_field_polynomial_quotient_prefix_entry (k) - 0107
specialize prime_field_polynomial_quotient_prefix_entry (ab) - 0108
specialize prime_field_polynomial_quotient_prefix_entry (ac) - 0109
specialize prime_field_polynomial_quotient_prefix_entry (bb) - 0110
specialize prime_field_polynomial_quotient_prefix_entry (bc) - 0111
specialize prime_field_polynomial_quotient_prefix_entry (M) - 0112
specialize prime_field_polynomial_quotient_prefix_entry (qb) - 0113
specialize prime_field_polynomial_quotient_prefix_entry (qc) - 0114
specialize prime_field_polynomial_quotient_prefix_entry (S N) - 0115
specialize prime_field_polynomial_quotient_prefix_entry (N) - 0116
specialize prime_field_polynomial_quotient_prefix_entry (a) - 0117
apply prime_field_polynomial_quotient_prefix_entry - 0118
exact hfirst - 0119
specialize le_refl (S N) - 0120
apply le_refl - 0121
exact hvalue - 0122
exact hchosen_witness_right - 0123
rewrite hlast - 0124
rewrite hlast - 0125
exact hchosen_witness_left - 0126
specialize hequal (i) - 0127
specialize hequal (a) - 0128
apply hequal - 0129
exact hcase_right - 0130
exact hvalue