PQ0054

prime_field_polynomial_synthetic_exists_unique

Every nonempty canonical input has a constructively encoded synthetic quotient and remainder, unique in decoded values rather than raw codes.

Alpha v34 checked-use · first admitted v32 · independently kernel and Lean verified; not Stable

Current library: Alpha v34, 4,223 checked-use theorems; Stable remains 432. Historical first admissions, original proof editions, and non-admitted aliases are preserved.

All coefficients retain the established highest-degree-first order. Trimming handles empty and all-zero prefixes; monic normalization requires a nonzero leading coefficient. Synthetic division has a nonempty input of length S n and a quotient of length n, unique in decoded values. Its coefficient recurrence, actual evaluation remainder and positive-degree drop are checked. General polynomial Euclidean division, gcd/Bezout, an arbitrary-convolution factor theorem, irreducible-polynomial existence and the full G091 prime-power-field endpoint remain open. These exact theorems are first admitted to Alpha v32; Stable remains unchanged.

Exact theorem in conservative defined notation

∀ p. ∀ b. ∀ c. ∀ a. ∀ n. Prime(p)BetaPrefixInto(b,c,S n,p)Lt(a,p) → ∃ x. ∃ y. ∃ z. FpSyntheticDivision(p,b,c,a,n,x,y,z) ∧ (∀ m. ∀ k. ∀ i. FpSyntheticDivision(p,b,c,a,n,m,k,i) → i = z ∧ (∀ j. ∀ u. Lt(j,n)BetaAt(m,k,j,u)BetaAt(x,y,j,u)))

Every linked abbreviation expands hygienically to the identical original native formula.

Definition DAG

Actual proof prerequisites

Original expanded first-order statement
forall p b c a n. (~((p) = 1) /\ forall pfa_factor_left_unique_prime pfa_factor_right_unique_prime. (p) = pfa_factor_left_unique_prime * pfa_factor_right_unique_prime -> pfa_factor_left_unique_prime = 1 \/ pfa_factor_right_unique_prime = 1) -> (forall fom_index_pfp_unique_coefficients. (exists fom_gap_pfp_unique_coefficients_index_bound. fom_gap_pfp_unique_coefficients_index_bound + S (fom_index_pfp_unique_coefficients) = S n) -> exists fom_value_pfp_unique_coefficients. ((((exists fom_beta_height_pfp_unique_coefficients_entry. fom_beta_height_pfp_unique_coefficients_entry + S (fom_value_pfp_unique_coefficients) = S ((S (fom_index_pfp_unique_coefficients)) * c)) /\ exists fom_beta_quotient_pfp_unique_coefficients_entry. b = fom_beta_quotient_pfp_unique_coefficients_entry * S ((S (fom_index_pfp_unique_coefficients)) * c) + (fom_value_pfp_unique_coefficients))) /\ (exists fom_gap_pfp_unique_coefficients_value_bound. fom_gap_pfp_unique_coefficients_value_bound + S (fom_value_pfp_unique_coefficients) = p))) -> (exists pfa_gap_unique_base. pfa_gap_unique_base + S (a) = (p)) -> exists qb qc r. ((exists pfs_history_code_unique_execution pfs_history_scale_unique_execution. ((((exists pfa_gap_unique_executiontracebase. pfa_gap_unique_executiontracebase + S (a) = (p)) /\ (((((exists ff_h_pfp_unique_executiontraceinitial. ff_h_pfp_unique_executiontraceinitial + S (0) = S ((S (0)) * pfs_history_scale_unique_execution)) /\ exists ff_q_pfp_unique_executiontraceinitial. pfs_history_code_unique_execution = ff_q_pfp_unique_executiontraceinitial * S ((S (0)) * pfs_history_scale_unique_execution) + (0))) /\ (((((exists ff_h_pfp_unique_executiontraceterminal. ff_h_pfp_unique_executiontraceterminal + S (r) = S ((S (S (n))) * pfs_history_scale_unique_execution)) /\ exists ff_q_pfp_unique_executiontraceterminal. pfs_history_code_unique_execution = ff_q_pfp_unique_executiontraceterminal * S ((S (S (n))) * pfs_history_scale_unique_execution) + (r))) /\ ((forall pfh_index_unique_executiontracesteps. (exists pfa_gap_unique_executiontracestepsindex. pfa_gap_unique_executiontracestepsindex + S (pfh_index_unique_executiontracesteps) = (S (n))) -> (exists pfh_coefficient_unique_executiontracestepsstep pfh_before_unique_executiontracestepsstep pfh_after_unique_executiontracestepsstep pfh_product_unique_executiontracestepsstep. ((((exists ff_h_pfp_unique_executiontracestepsstepcoefficient. ff_h_pfp_unique_executiontracestepsstepcoefficient + S (pfh_coefficient_unique_executiontracestepsstep) = S ((S (pfh_index_unique_executiontracesteps)) * c)) /\ exists ff_q_pfp_unique_executiontracestepsstepcoefficient. b = ff_q_pfp_unique_executiontracestepsstepcoefficient * S ((S (pfh_index_unique_executiontracesteps)) * c) + (pfh_coefficient_unique_executiontracestepsstep))) /\ (((((exists ff_h_pfp_unique_executiontracestepsstepbefore. ff_h_pfp_unique_executiontracestepsstepbefore + S (pfh_before_unique_executiontracestepsstep) = S ((S (pfh_index_unique_executiontracesteps)) * pfs_history_scale_unique_execution)) /\ exists ff_q_pfp_unique_executiontracestepsstepbefore. pfs_history_code_unique_execution = ff_q_pfp_unique_executiontracestepsstepbefore * S ((S (pfh_index_unique_executiontracesteps)) * pfs_history_scale_unique_execution) + (pfh_before_unique_executiontracestepsstep))) /\ (((((exists ff_h_pfp_unique_executiontracestepsstepafter. ff_h_pfp_unique_executiontracestepsstepafter + S (pfh_after_unique_executiontracestepsstep) = S ((S (S (pfh_index_unique_executiontracesteps))) * pfs_history_scale_unique_execution)) /\ exists ff_q_pfp_unique_executiontracestepsstepafter. pfs_history_code_unique_execution = ff_q_pfp_unique_executiontracestepsstepafter * S ((S (S (pfh_index_unique_executiontracesteps))) * pfs_history_scale_unique_execution) + (pfh_after_unique_executiontracestepsstep))) /\ (((((exists pfa_gap_unique_executiontracestepsstepmultiplyleft. pfa_gap_unique_executiontracestepsstepmultiplyleft + S (pfh_before_unique_executiontracestepsstep) = (p)) /\ (((exists pfa_gap_unique_executiontracestepsstepmultiplyright. pfa_gap_unique_executiontracestepsstepmultiplyright + S (a) = (p)) /\ ((((exists pfa_gap_unique_executiontracestepsstepmultiplyresultbound. pfa_gap_unique_executiontracestepsstepmultiplyresultbound + S (pfh_product_unique_executiontracestepsstep) = (p)) /\ ((exists pfa_offset_left_unique_executiontracestepsstepmultiplyresultcongruence pfa_offset_right_unique_executiontracestepsstepmultiplyresultcongruence. ((pfh_before_unique_executiontracestepsstep) * (a)) + (p) * pfa_offset_left_unique_executiontracestepsstepmultiplyresultcongruence = (pfh_product_unique_executiontracestepsstep) + (p) * pfa_offset_right_unique_executiontracestepsstepmultiplyresultcongruence))))))))) /\ ((((exists pfa_gap_unique_executiontracestepsstepaddleft. pfa_gap_unique_executiontracestepsstepaddleft + S (pfh_product_unique_executiontracestepsstep) = (p)) /\ (((exists pfa_gap_unique_executiontracestepsstepaddright. pfa_gap_unique_executiontracestepsstepaddright + S (pfh_coefficient_unique_executiontracestepsstep) = (p)) /\ ((((exists pfa_gap_unique_executiontracestepsstepaddresultbound. pfa_gap_unique_executiontracestepsstepaddresultbound + S (pfh_after_unique_executiontracestepsstep) = (p)) /\ ((exists pfa_offset_left_unique_executiontracestepsstepaddresultcongruence pfa_offset_right_unique_executiontracestepsstepaddresultcongruence. ((pfh_product_unique_executiontracestepsstep) + (pfh_coefficient_unique_executiontracestepsstep)) + (p) * pfa_offset_left_unique_executiontracestepsstepaddresultcongruence = (pfh_after_unique_executiontracestepsstep) + (p) * pfa_offset_right_unique_executiontracestepsstepaddresultcongruence)))))))))))))))))))))))))) /\ ((forall ff_index_mcp_pfs_unique_executionquotient ff_source_mcp_pfs_unique_executionquotient ff_target_mcp_pfs_unique_executionquotient. (exists mcp_gap_pfs_unique_executionquotient_bound. mcp_gap_pfs_unique_executionquotient_bound + S (ff_index_mcp_pfs_unique_executionquotient) = (n)) -> (((exists fs_h_mcp_pfs_unique_executionquotient_source. fs_h_mcp_pfs_unique_executionquotient_source + S (ff_source_mcp_pfs_unique_executionquotient) = S ((S ((1) + (1) * ff_index_mcp_pfs_unique_executionquotient)) * pfs_history_scale_unique_execution)) /\ exists fs_q_mcp_pfs_unique_executionquotient_source. pfs_history_code_unique_execution = fs_q_mcp_pfs_unique_executionquotient_source * S ((S ((1) + (1) * ff_index_mcp_pfs_unique_executionquotient)) * pfs_history_scale_unique_execution) + (ff_source_mcp_pfs_unique_executionquotient))) -> (((exists fs_h_mcp_pfs_unique_executionquotient_target. fs_h_mcp_pfs_unique_executionquotient_target + S (ff_target_mcp_pfs_unique_executionquotient) = S ((S (ff_index_mcp_pfs_unique_executionquotient)) * qc)) /\ exists fs_q_mcp_pfs_unique_executionquotient_target. qb = fs_q_mcp_pfs_unique_executionquotient_target * S ((S (ff_index_mcp_pfs_unique_executionquotient)) * qc) + (ff_target_mcp_pfs_unique_executionquotient))) -> ff_target_mcp_pfs_unique_executionquotient = ff_source_mcp_pfs_unique_executionquotient)))) /\ ((forall Qb Qc s. (exists pfs_history_code_unique_other pfs_history_scale_unique_other. ((((exists pfa_gap_unique_othertracebase. pfa_gap_unique_othertracebase + S (a) = (p)) /\ (((((exists ff_h_pfp_unique_othertraceinitial. ff_h_pfp_unique_othertraceinitial + S (0) = S ((S (0)) * pfs_history_scale_unique_other)) /\ exists ff_q_pfp_unique_othertraceinitial. pfs_history_code_unique_other = ff_q_pfp_unique_othertraceinitial * S ((S (0)) * pfs_history_scale_unique_other) + (0))) /\ (((((exists ff_h_pfp_unique_othertraceterminal. ff_h_pfp_unique_othertraceterminal + S (s) = S ((S (S (n))) * pfs_history_scale_unique_other)) /\ exists ff_q_pfp_unique_othertraceterminal. pfs_history_code_unique_other = ff_q_pfp_unique_othertraceterminal * S ((S (S (n))) * pfs_history_scale_unique_other) + (s))) /\ ((forall pfh_index_unique_othertracesteps. (exists pfa_gap_unique_othertracestepsindex. pfa_gap_unique_othertracestepsindex + S (pfh_index_unique_othertracesteps) = (S (n))) -> (exists pfh_coefficient_unique_othertracestepsstep pfh_before_unique_othertracestepsstep pfh_after_unique_othertracestepsstep pfh_product_unique_othertracestepsstep. ((((exists ff_h_pfp_unique_othertracestepsstepcoefficient. ff_h_pfp_unique_othertracestepsstepcoefficient + S (pfh_coefficient_unique_othertracestepsstep) = S ((S (pfh_index_unique_othertracesteps)) * c)) /\ exists ff_q_pfp_unique_othertracestepsstepcoefficient. b = ff_q_pfp_unique_othertracestepsstepcoefficient * S ((S (pfh_index_unique_othertracesteps)) * c) + (pfh_coefficient_unique_othertracestepsstep))) /\ (((((exists ff_h_pfp_unique_othertracestepsstepbefore. ff_h_pfp_unique_othertracestepsstepbefore + S (pfh_before_unique_othertracestepsstep) = S ((S (pfh_index_unique_othertracesteps)) * pfs_history_scale_unique_other)) /\ exists ff_q_pfp_unique_othertracestepsstepbefore. pfs_history_code_unique_other = ff_q_pfp_unique_othertracestepsstepbefore * S ((S (pfh_index_unique_othertracesteps)) * pfs_history_scale_unique_other) + (pfh_before_unique_othertracestepsstep))) /\ (((((exists ff_h_pfp_unique_othertracestepsstepafter. ff_h_pfp_unique_othertracestepsstepafter + S (pfh_after_unique_othertracestepsstep) = S ((S (S (pfh_index_unique_othertracesteps))) * pfs_history_scale_unique_other)) /\ exists ff_q_pfp_unique_othertracestepsstepafter. pfs_history_code_unique_other = ff_q_pfp_unique_othertracestepsstepafter * S ((S (S (pfh_index_unique_othertracesteps))) * pfs_history_scale_unique_other) + (pfh_after_unique_othertracestepsstep))) /\ (((((exists pfa_gap_unique_othertracestepsstepmultiplyleft. pfa_gap_unique_othertracestepsstepmultiplyleft + S (pfh_before_unique_othertracestepsstep) = (p)) /\ (((exists pfa_gap_unique_othertracestepsstepmultiplyright. pfa_gap_unique_othertracestepsstepmultiplyright + S (a) = (p)) /\ ((((exists pfa_gap_unique_othertracestepsstepmultiplyresultbound. pfa_gap_unique_othertracestepsstepmultiplyresultbound + S (pfh_product_unique_othertracestepsstep) = (p)) /\ ((exists pfa_offset_left_unique_othertracestepsstepmultiplyresultcongruence pfa_offset_right_unique_othertracestepsstepmultiplyresultcongruence. ((pfh_before_unique_othertracestepsstep) * (a)) + (p) * pfa_offset_left_unique_othertracestepsstepmultiplyresultcongruence = (pfh_product_unique_othertracestepsstep) + (p) * pfa_offset_right_unique_othertracestepsstepmultiplyresultcongruence))))))))) /\ ((((exists pfa_gap_unique_othertracestepsstepaddleft. pfa_gap_unique_othertracestepsstepaddleft + S (pfh_product_unique_othertracestepsstep) = (p)) /\ (((exists pfa_gap_unique_othertracestepsstepaddright. pfa_gap_unique_othertracestepsstepaddright + S (pfh_coefficient_unique_othertracestepsstep) = (p)) /\ ((((exists pfa_gap_unique_othertracestepsstepaddresultbound. pfa_gap_unique_othertracestepsstepaddresultbound + S (pfh_after_unique_othertracestepsstep) = (p)) /\ ((exists pfa_offset_left_unique_othertracestepsstepaddresultcongruence pfa_offset_right_unique_othertracestepsstepaddresultcongruence. ((pfh_product_unique_othertracestepsstep) + (pfh_coefficient_unique_othertracestepsstep)) + (p) * pfa_offset_left_unique_othertracestepsstepaddresultcongruence = (pfh_after_unique_othertracestepsstep) + (p) * pfa_offset_right_unique_othertracestepsstepaddresultcongruence)))))))))))))))))))))))))) /\ ((forall ff_index_mcp_pfs_unique_otherquotient ff_source_mcp_pfs_unique_otherquotient ff_target_mcp_pfs_unique_otherquotient. (exists mcp_gap_pfs_unique_otherquotient_bound. mcp_gap_pfs_unique_otherquotient_bound + S (ff_index_mcp_pfs_unique_otherquotient) = (n)) -> (((exists fs_h_mcp_pfs_unique_otherquotient_source. fs_h_mcp_pfs_unique_otherquotient_source + S (ff_source_mcp_pfs_unique_otherquotient) = S ((S ((1) + (1) * ff_index_mcp_pfs_unique_otherquotient)) * pfs_history_scale_unique_other)) /\ exists fs_q_mcp_pfs_unique_otherquotient_source. pfs_history_code_unique_other = fs_q_mcp_pfs_unique_otherquotient_source * S ((S ((1) + (1) * ff_index_mcp_pfs_unique_otherquotient)) * pfs_history_scale_unique_other) + (ff_source_mcp_pfs_unique_otherquotient))) -> (((exists fs_h_mcp_pfs_unique_otherquotient_target. fs_h_mcp_pfs_unique_otherquotient_target + S (ff_target_mcp_pfs_unique_otherquotient) = S ((S (ff_index_mcp_pfs_unique_otherquotient)) * Qc)) /\ exists fs_q_mcp_pfs_unique_otherquotient_target. Qb = fs_q_mcp_pfs_unique_otherquotient_target * S ((S (ff_index_mcp_pfs_unique_otherquotient)) * Qc) + (ff_target_mcp_pfs_unique_otherquotient))) -> ff_target_mcp_pfs_unique_otherquotient = ff_source_mcp_pfs_unique_otherquotient)))) -> (((s=r) /\ ((forall mdr_i_pfp_unique_values mdr_a_pfp_unique_values. (exists mdr_gap_pfp_unique_valuesb. mdr_gap_pfp_unique_valuesb + S (mdr_i_pfp_unique_values) = (n)) -> (((exists ff_h_mdr_pfp_unique_valueso. ff_h_mdr_pfp_unique_valueso + S (mdr_a_pfp_unique_values) = S ((S (mdr_i_pfp_unique_values)) * Qc)) /\ exists ff_q_mdr_pfp_unique_valueso. Qb = ff_q_mdr_pfp_unique_valueso * S ((S (mdr_i_pfp_unique_values)) * Qc) + (mdr_a_pfp_unique_values))) -> (((exists ff_h_mdr_pfp_unique_valuesn. ff_h_mdr_pfp_unique_valuesn + S (mdr_a_pfp_unique_values) = S ((S (mdr_i_pfp_unique_values)) * qc)) /\ exists ff_q_mdr_pfp_unique_valuesn. qb = ff_q_mdr_pfp_unique_valuesn * S ((S (mdr_i_pfp_unique_values)) * qc) + (mdr_a_pfp_unique_values))))))))))

Complete tactic proof in conservative notation

All 45 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

45 script commands · 9 reading checkpoints · 1 local claims

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.

Definition notation is shown below. Open the paired exact edition for the original native formulas. Source pairing is not a new equivalence certificate.

Named ingredients (2)
01Fix variables and assumptionsL1–8

Work with arbitrary variables or the premises of the current implication.

  1. L1
    intro p
  2. L2
    intro b
  3. L3
    intro c
  4. L4
    intro a
  5. L5
    intro n
  6. L6
    intro hp
  7. L7
    intro hc
  8. L8
    intro ha
02Establish heL9–18

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply prime field polynomial synthetic exists.

  1. L9
    have he : ∃ qb. ∃ qc. ∃ r. FpSyntheticDivision(p,b,c,a,n,qb,qc,r)Definitions: FpSyntheticDivision(p,b,c,a,n,qb,qc,r)Original native command in the exact edition
  2. L10
    specialize prime_field_polynomial_synthetic_exists (p)
  3. L11
    specialize prime_field_polynomial_synthetic_exists (b)
  4. L12
    specialize prime_field_polynomial_synthetic_exists (c)
  5. L13
    specialize prime_field_polynomial_synthetic_exists (a)
  6. L14
    specialize prime_field_polynomial_synthetic_exists (n)
  7. L15
    apply prime_field_polynomial_synthetic_exists
  8. L16
    exact hp
  9. L17
    exact hc
  10. L18
    exact ha
03Separate the logical casesL19–21

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L19
    cases he
  2. L20
    cases he_witness
  3. L21
    cases he_witness_witness
04Construct an explicit witnessL22–24

Supply the displayed value, then prove that it has the required property.

  1. L22
    exists x
  2. L23
    exists x1
  3. L24
    exists x2
05Separate the logical casesL25–25

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L25
    split
06Use earlier factsL26–26

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L26
    exact he_witness_witness_witness
07Fix variables and assumptionsL27–30

Work with arbitrary variables or the premises of the current implication.

  1. L27
    intro Qb
  2. L28
    intro Qc
  3. L29
    intro s
  4. L30
    intro hQ
08Use earlier factsL31–40

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L31
    specialize prime_field_polynomial_synthetic_functional (p)
  2. L32
    specialize prime_field_polynomial_synthetic_functional (b)
  3. L33
    specialize prime_field_polynomial_synthetic_functional (c)
  4. L34
    specialize prime_field_polynomial_synthetic_functional (a)
  5. L35
    specialize prime_field_polynomial_synthetic_functional (n)
  6. L36
    specialize prime_field_polynomial_synthetic_functional (Qb)
  7. L37
    specialize prime_field_polynomial_synthetic_functional (Qc)
  8. L38
    specialize prime_field_polynomial_synthetic_functional (s)
  9. L39
    specialize prime_field_polynomial_synthetic_functional (x)
  10. L40
    specialize prime_field_polynomial_synthetic_functional (x1)
09Use earlier factsL41–45

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L41
    specialize prime_field_polynomial_synthetic_functional (x2)
  2. L42
    apply prime_field_polynomial_synthetic_functional
  3. L43
    exact hp
  4. L44
    exact hQ
  5. L45
    exact he_witness_witness_witness

Library-wide reading audit

Original defined command ledger · 45 lines
  1. 0001intro p
  2. 0002intro b
  3. 0003intro c
  4. 0004intro a
  5. 0005intro n
  6. 0006intro hp
  7. 0007intro hc
  8. 0008intro ha
  9. 0009have he : ∃ qb. ∃ qc. ∃ r. FpSyntheticDivision(p,b,c,a,n,qb,qc,r)
  10. 0010specialize prime_field_polynomial_synthetic_exists (p)
  11. 0011specialize prime_field_polynomial_synthetic_exists (b)
  12. 0012specialize prime_field_polynomial_synthetic_exists (c)
  13. 0013specialize prime_field_polynomial_synthetic_exists (a)
  14. 0014specialize prime_field_polynomial_synthetic_exists (n)
  15. 0015apply prime_field_polynomial_synthetic_exists
  16. 0016exact hp
  17. 0017exact hc
  18. 0018exact ha
  19. 0019cases he
  20. 0020cases he_witness
  21. 0021cases he_witness_witness
  22. 0022exists x
  23. 0023exists x1
  24. 0024exists x2
  25. 0025split
  26. 0026exact he_witness_witness_witness
  27. 0027intro Qb
  28. 0028intro Qc
  29. 0029intro s
  30. 0030intro hQ
  31. 0031specialize prime_field_polynomial_synthetic_functional (p)
  32. 0032specialize prime_field_polynomial_synthetic_functional (b)
  33. 0033specialize prime_field_polynomial_synthetic_functional (c)
  34. 0034specialize prime_field_polynomial_synthetic_functional (a)
  35. 0035specialize prime_field_polynomial_synthetic_functional (n)
  36. 0036specialize prime_field_polynomial_synthetic_functional (Qb)
  37. 0037specialize prime_field_polynomial_synthetic_functional (Qc)
  38. 0038specialize prime_field_polynomial_synthetic_functional (s)
  39. 0039specialize prime_field_polynomial_synthetic_functional (x)
  40. 0040specialize prime_field_polynomial_synthetic_functional (x1)
  41. 0041specialize prime_field_polynomial_synthetic_functional (x2)
  42. 0042apply prime_field_polynomial_synthetic_functional
  43. 0043exact hp
  44. 0044exact hQ
  45. 0045exact he_witness_witness_witness