PC0034

prime_count_functional

The exact prime count is independent of every mask and sum-trace encoding choice.

Alpha v34 checked-use · first admitted v27 · 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. Exact original first-admission records.

These are the exact finite integer inequalities with constant 8, for every N≥2. The proof uses constructive binomial and primorial infrastructure; it does not assume logarithms, asymptotic estimates, the prime number theorem, or a factorization oracle.

Exact theorem in conservative defined notation

∀ N. ∀ k. ∀ K. PrimeCount(N,k) → PrimeCount(N,K) → k = K

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

Definition DAG

PrimeCount(x,z) · 2

Actual proof prerequisites

le_antisymm · checked external prerequisitebeta_sum_pointwise_le · checked external prerequisiteprime_bit_prefix_equal_entryle_refl · checked external prerequisite
Original expanded first-order statement 
forall N k K. (exists pc_code_count_functional_left pc_scale_count_functional_left. (forall pc_index_count_functional_left_mask. (exists pc_lt_count_functional_left_mask_bound. pc_lt_count_functional_left_mask_bound + S (pc_index_count_functional_left_mask) = (N)) -> exists pc_bit_count_functional_left_mask. (((exists fs_h_pc_count_functional_left_mask_entry. fs_h_pc_count_functional_left_mask_entry + S (pc_bit_count_functional_left_mask) = S ((S (pc_index_count_functional_left_mask)) * pc_scale_count_functional_left)) /\ exists fs_q_pc_count_functional_left_mask_entry. pc_code_count_functional_left = fs_q_pc_count_functional_left_mask_entry * S ((S (pc_index_count_functional_left_mask)) * pc_scale_count_functional_left) + (pc_bit_count_functional_left_mask))) /\ (((((~(S (pc_index_count_functional_left_mask) = 1) /\ forall bpr_left_pc_count_functional_left_mask_choice_prime bpr_right_pc_count_functional_left_mask_choice_prime. S (pc_index_count_functional_left_mask) = bpr_left_pc_count_functional_left_mask_choice_prime * bpr_right_pc_count_functional_left_mask_choice_prime -> bpr_left_pc_count_functional_left_mask_choice_prime = 1 \/ bpr_right_pc_count_functional_left_mask_choice_prime = 1)) /\ pc_bit_count_functional_left_mask = 1) \/ (~((~(S (pc_index_count_functional_left_mask) = 1) /\ forall bpr_left_pc_count_functional_left_mask_choice_prime bpr_right_pc_count_functional_left_mask_choice_prime. S (pc_index_count_functional_left_mask) = bpr_left_pc_count_functional_left_mask_choice_prime * bpr_right_pc_count_functional_left_mask_choice_prime -> bpr_left_pc_count_functional_left_mask_choice_prime = 1 \/ bpr_right_pc_count_functional_left_mask_choice_prime = 1)) /\ pc_bit_count_functional_left_mask = 0)))) /\ (exists fs_u_pc_count_functional_left_sum fs_v_pc_count_functional_left_sum. ((((exists fs_h_pc_count_functional_left_sum_body_start. fs_h_pc_count_functional_left_sum_body_start + S (0) = S ((S (0)) * fs_v_pc_count_functional_left_sum)) /\ exists fs_q_pc_count_functional_left_sum_body_start. fs_u_pc_count_functional_left_sum = fs_q_pc_count_functional_left_sum_body_start * S ((S (0)) * fs_v_pc_count_functional_left_sum) + (0))) /\ ((((exists fs_h_pc_count_functional_left_sum_body_terminal. fs_h_pc_count_functional_left_sum_body_terminal + S (k) = S ((S (N)) * fs_v_pc_count_functional_left_sum)) /\ exists fs_q_pc_count_functional_left_sum_body_terminal. fs_u_pc_count_functional_left_sum = fs_q_pc_count_functional_left_sum_body_terminal * S ((S (N)) * fs_v_pc_count_functional_left_sum) + (k))) /\ forall fs_i_pc_count_functional_left_sum_body_steps. (exists fs_lt_pc_count_functional_left_sum_body_steps_bound. fs_lt_pc_count_functional_left_sum_body_steps_bound + S fs_i_pc_count_functional_left_sum_body_steps = N) -> exists fs_a_pc_count_functional_left_sum_body_steps fs_r_pc_count_functional_left_sum_body_steps fs_s_pc_count_functional_left_sum_body_steps. ((((exists fs_h_pc_count_functional_left_sum_body_steps_summand. fs_h_pc_count_functional_left_sum_body_steps_summand + S (fs_a_pc_count_functional_left_sum_body_steps) = S ((S (fs_i_pc_count_functional_left_sum_body_steps)) * pc_scale_count_functional_left)) /\ exists fs_q_pc_count_functional_left_sum_body_steps_summand. pc_code_count_functional_left = fs_q_pc_count_functional_left_sum_body_steps_summand * S ((S (fs_i_pc_count_functional_left_sum_body_steps)) * pc_scale_count_functional_left) + (fs_a_pc_count_functional_left_sum_body_steps))) /\ ((((exists fs_h_pc_count_functional_left_sum_body_steps_partial. fs_h_pc_count_functional_left_sum_body_steps_partial + S (fs_r_pc_count_functional_left_sum_body_steps) = S ((S (fs_i_pc_count_functional_left_sum_body_steps)) * fs_v_pc_count_functional_left_sum)) /\ exists fs_q_pc_count_functional_left_sum_body_steps_partial. fs_u_pc_count_functional_left_sum = fs_q_pc_count_functional_left_sum_body_steps_partial * S ((S (fs_i_pc_count_functional_left_sum_body_steps)) * fs_v_pc_count_functional_left_sum) + (fs_r_pc_count_functional_left_sum_body_steps))) /\ ((((exists fs_h_pc_count_functional_left_sum_body_steps_successor. fs_h_pc_count_functional_left_sum_body_steps_successor + S (fs_s_pc_count_functional_left_sum_body_steps) = S ((S (S fs_i_pc_count_functional_left_sum_body_steps)) * fs_v_pc_count_functional_left_sum)) /\ exists fs_q_pc_count_functional_left_sum_body_steps_successor. fs_u_pc_count_functional_left_sum = fs_q_pc_count_functional_left_sum_body_steps_successor * S ((S (S fs_i_pc_count_functional_left_sum_body_steps)) * fs_v_pc_count_functional_left_sum) + (fs_s_pc_count_functional_left_sum_body_steps))) /\ fs_s_pc_count_functional_left_sum_body_steps = fs_r_pc_count_functional_left_sum_body_steps + fs_a_pc_count_functional_left_sum_body_steps))))))) -> (exists pc_code_count_functional_right pc_scale_count_functional_right. (forall pc_index_count_functional_right_mask. (exists pc_lt_count_functional_right_mask_bound. pc_lt_count_functional_right_mask_bound + S (pc_index_count_functional_right_mask) = (N)) -> exists pc_bit_count_functional_right_mask. (((exists fs_h_pc_count_functional_right_mask_entry. fs_h_pc_count_functional_right_mask_entry + S (pc_bit_count_functional_right_mask) = S ((S (pc_index_count_functional_right_mask)) * pc_scale_count_functional_right)) /\ exists fs_q_pc_count_functional_right_mask_entry. pc_code_count_functional_right = fs_q_pc_count_functional_right_mask_entry * S ((S (pc_index_count_functional_right_mask)) * pc_scale_count_functional_right) + (pc_bit_count_functional_right_mask))) /\ (((((~(S (pc_index_count_functional_right_mask) = 1) /\ forall bpr_left_pc_count_functional_right_mask_choice_prime bpr_right_pc_count_functional_right_mask_choice_prime. S (pc_index_count_functional_right_mask) = bpr_left_pc_count_functional_right_mask_choice_prime * bpr_right_pc_count_functional_right_mask_choice_prime -> bpr_left_pc_count_functional_right_mask_choice_prime = 1 \/ bpr_right_pc_count_functional_right_mask_choice_prime = 1)) /\ pc_bit_count_functional_right_mask = 1) \/ (~((~(S (pc_index_count_functional_right_mask) = 1) /\ forall bpr_left_pc_count_functional_right_mask_choice_prime bpr_right_pc_count_functional_right_mask_choice_prime. S (pc_index_count_functional_right_mask) = bpr_left_pc_count_functional_right_mask_choice_prime * bpr_right_pc_count_functional_right_mask_choice_prime -> bpr_left_pc_count_functional_right_mask_choice_prime = 1 \/ bpr_right_pc_count_functional_right_mask_choice_prime = 1)) /\ pc_bit_count_functional_right_mask = 0)))) /\ (exists fs_u_pc_count_functional_right_sum fs_v_pc_count_functional_right_sum. ((((exists fs_h_pc_count_functional_right_sum_body_start. fs_h_pc_count_functional_right_sum_body_start + S (0) = S ((S (0)) * fs_v_pc_count_functional_right_sum)) /\ exists fs_q_pc_count_functional_right_sum_body_start. fs_u_pc_count_functional_right_sum = fs_q_pc_count_functional_right_sum_body_start * S ((S (0)) * fs_v_pc_count_functional_right_sum) + (0))) /\ ((((exists fs_h_pc_count_functional_right_sum_body_terminal. fs_h_pc_count_functional_right_sum_body_terminal + S (K) = S ((S (N)) * fs_v_pc_count_functional_right_sum)) /\ exists fs_q_pc_count_functional_right_sum_body_terminal. fs_u_pc_count_functional_right_sum = fs_q_pc_count_functional_right_sum_body_terminal * S ((S (N)) * fs_v_pc_count_functional_right_sum) + (K))) /\ forall fs_i_pc_count_functional_right_sum_body_steps. (exists fs_lt_pc_count_functional_right_sum_body_steps_bound. fs_lt_pc_count_functional_right_sum_body_steps_bound + S fs_i_pc_count_functional_right_sum_body_steps = N) -> exists fs_a_pc_count_functional_right_sum_body_steps fs_r_pc_count_functional_right_sum_body_steps fs_s_pc_count_functional_right_sum_body_steps. ((((exists fs_h_pc_count_functional_right_sum_body_steps_summand. fs_h_pc_count_functional_right_sum_body_steps_summand + S (fs_a_pc_count_functional_right_sum_body_steps) = S ((S (fs_i_pc_count_functional_right_sum_body_steps)) * pc_scale_count_functional_right)) /\ exists fs_q_pc_count_functional_right_sum_body_steps_summand. pc_code_count_functional_right = fs_q_pc_count_functional_right_sum_body_steps_summand * S ((S (fs_i_pc_count_functional_right_sum_body_steps)) * pc_scale_count_functional_right) + (fs_a_pc_count_functional_right_sum_body_steps))) /\ ((((exists fs_h_pc_count_functional_right_sum_body_steps_partial. fs_h_pc_count_functional_right_sum_body_steps_partial + S (fs_r_pc_count_functional_right_sum_body_steps) = S ((S (fs_i_pc_count_functional_right_sum_body_steps)) * fs_v_pc_count_functional_right_sum)) /\ exists fs_q_pc_count_functional_right_sum_body_steps_partial. fs_u_pc_count_functional_right_sum = fs_q_pc_count_functional_right_sum_body_steps_partial * S ((S (fs_i_pc_count_functional_right_sum_body_steps)) * fs_v_pc_count_functional_right_sum) + (fs_r_pc_count_functional_right_sum_body_steps))) /\ ((((exists fs_h_pc_count_functional_right_sum_body_steps_successor. fs_h_pc_count_functional_right_sum_body_steps_successor + S (fs_s_pc_count_functional_right_sum_body_steps) = S ((S (S fs_i_pc_count_functional_right_sum_body_steps)) * fs_v_pc_count_functional_right_sum)) /\ exists fs_q_pc_count_functional_right_sum_body_steps_successor. fs_u_pc_count_functional_right_sum = fs_q_pc_count_functional_right_sum_body_steps_successor * S ((S (S fs_i_pc_count_functional_right_sum_body_steps)) * fs_v_pc_count_functional_right_sum) + (fs_s_pc_count_functional_right_sum_body_steps))) /\ fs_s_pc_count_functional_right_sum_body_steps = fs_r_pc_count_functional_right_sum_body_steps + fs_a_pc_count_functional_right_sum_body_steps))))))) -> k = K

Complete tactic proof in conservative notation

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

82 script commands · 15 reading checkpoints · 2 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 (1)
prime bit prefix equal entry
01Fix variables and assumptionsL1–5

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

  1. L1
    intro N
  2. L2
    intro k
  3. L3
    intro K
  4. L4
    intro hk
  5. L5
    intro hK
02Separate the logical casesL6–11

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

  1. L6
    cases hk
  2. L7
    cases hk_witness
  3. L8
    cases hk_witness_witness
  4. L9
    cases hK
  5. L10
    cases hK_witness
  6. L11
    cases hK_witness_witness
03Use earlier factsL12–21

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

  1. L12
    specialize le_antisymm k
  2. L13
    specialize le_antisymm K
  3. L14
    apply le_antisymm
  4. L15
    specialize beta_sum_pointwise_le x
  5. L16
    specialize beta_sum_pointwise_le x1
  6. L17
    specialize beta_sum_pointwise_le x2
  7. L18
    specialize beta_sum_pointwise_le x3
  8. L19
    specialize beta_sum_pointwise_le N
  9. L20
    specialize beta_sum_pointwise_le k
  10. L21
    specialize beta_sum_pointwise_le K
04Use earlier factsL22–22

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

  1. L22
    apply beta_sum_pointwise_le
05Fix variables and assumptionsL23–28

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

  1. L23
    intro i
  2. L24
    intro a
  3. L25
    intro z
  4. L26
    intro hi
  5. L27
    intro ha
  6. L28
    intro hz
06Establish heqL29–38

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply prime bit prefix equal entry.

  1. L29
    have heq : a = z
  2. L30
    specialize prime_bit_prefix_equal_entry x
  3. L31
    specialize prime_bit_prefix_equal_entry x1
  4. L32
    specialize prime_bit_prefix_equal_entry x2
  5. L33
    specialize prime_bit_prefix_equal_entry x3
  6. L34
    specialize prime_bit_prefix_equal_entry N
  7. L35
    specialize prime_bit_prefix_equal_entry i
  8. L36
    specialize prime_bit_prefix_equal_entry a
  9. L37
    specialize prime_bit_prefix_equal_entry z
  10. L38
    apply prime_bit_prefix_equal_entry
07Use earlier factsL39–43

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

  1. L39
    exact hk_witness_witness_left
  2. L40
    exact hK_witness_witness_left
  3. L41
    exact hi
  4. L42
    exact ha
  5. L43
    exact hz
08Calculate and transport equalitiesL44–44

Carry out the recorded arithmetic or equality steps; inspect the exact commands for their direction and premises.

  1. L44
    rewrite heq
09Use earlier factsL45–54

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

  1. L45
    specialize le_refl z
  2. L46
    apply le_refl
  3. L47
    exact hk_witness_witness_right
  4. L48
    exact hK_witness_witness_right
  5. L49
    specialize beta_sum_pointwise_le x2
  6. L50
    specialize beta_sum_pointwise_le x3
  7. L51
    specialize beta_sum_pointwise_le x
  8. L52
    specialize beta_sum_pointwise_le x1
  9. L53
    specialize beta_sum_pointwise_le N
  10. L54
    specialize beta_sum_pointwise_le K
10Use earlier factsL55–56

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

  1. L55
    specialize beta_sum_pointwise_le k
  2. L56
    apply beta_sum_pointwise_le
11Fix variables and assumptionsL57–62

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

  1. L57
    intro i
  2. L58
    intro a
  3. L59
    intro z
  4. L60
    intro hi
  5. L61
    intro ha
  6. L62
    intro hz
12Establish heqL63–72

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply prime bit prefix equal entry.

  1. L63
    have heq : a = z
  2. L64
    specialize prime_bit_prefix_equal_entry x2
  3. L65
    specialize prime_bit_prefix_equal_entry x3
  4. L66
    specialize prime_bit_prefix_equal_entry x
  5. L67
    specialize prime_bit_prefix_equal_entry x1
  6. L68
    specialize prime_bit_prefix_equal_entry N
  7. L69
    specialize prime_bit_prefix_equal_entry i
  8. L70
    specialize prime_bit_prefix_equal_entry a
  9. L71
    specialize prime_bit_prefix_equal_entry z
  10. L72
    apply prime_bit_prefix_equal_entry
13Use earlier factsL73–77

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

  1. L73
    exact hK_witness_witness_left
  2. L74
    exact hk_witness_witness_left
  3. L75
    exact hi
  4. L76
    exact ha
  5. L77
    exact hz
14Calculate and transport equalitiesL78–78

Carry out the recorded arithmetic or equality steps; inspect the exact commands for their direction and premises.

  1. L78
    rewrite heq
15Use earlier factsL79–82

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

  1. L79
    specialize le_refl z
  2. L80
    apply le_refl
  3. L81
    exact hK_witness_witness_right
  4. L82
    exact hk_witness_witness_right

Library-wide reading audit

Original defined command ledger · 82 lines
  1. 0001intro N
  2. 0002intro k
  3. 0003intro K
  4. 0004intro hk
  5. 0005intro hK
  6. 0006cases hk
  7. 0007cases hk_witness
  8. 0008cases hk_witness_witness
  9. 0009cases hK
  10. 0010cases hK_witness
  11. 0011cases hK_witness_witness
  12. 0012specialize le_antisymm k
  13. 0013specialize le_antisymm K
  14. 0014apply le_antisymm
  15. 0015specialize beta_sum_pointwise_le x
  16. 0016specialize beta_sum_pointwise_le x1
  17. 0017specialize beta_sum_pointwise_le x2
  18. 0018specialize beta_sum_pointwise_le x3
  19. 0019specialize beta_sum_pointwise_le N
  20. 0020specialize beta_sum_pointwise_le k
  21. 0021specialize beta_sum_pointwise_le K
  22. 0022apply beta_sum_pointwise_le
  23. 0023intro i
  24. 0024intro a
  25. 0025intro z
  26. 0026intro hi
  27. 0027intro ha
  28. 0028intro hz
  29. 0029have heq : a = z
  30. 0030specialize prime_bit_prefix_equal_entry x
  31. 0031specialize prime_bit_prefix_equal_entry x1
  32. 0032specialize prime_bit_prefix_equal_entry x2
  33. 0033specialize prime_bit_prefix_equal_entry x3
  34. 0034specialize prime_bit_prefix_equal_entry N
  35. 0035specialize prime_bit_prefix_equal_entry i
  36. 0036specialize prime_bit_prefix_equal_entry a
  37. 0037specialize prime_bit_prefix_equal_entry z
  38. 0038apply prime_bit_prefix_equal_entry
  39. 0039exact hk_witness_witness_left
  40. 0040exact hK_witness_witness_left
  41. 0041exact hi
  42. 0042exact ha
  43. 0043exact hz
  44. 0044rewrite heq
  45. 0045specialize le_refl z
  46. 0046apply le_refl
  47. 0047exact hk_witness_witness_right
  48. 0048exact hK_witness_witness_right
  49. 0049specialize beta_sum_pointwise_le x2
  50. 0050specialize beta_sum_pointwise_le x3
  51. 0051specialize beta_sum_pointwise_le x
  52. 0052specialize beta_sum_pointwise_le x1
  53. 0053specialize beta_sum_pointwise_le N
  54. 0054specialize beta_sum_pointwise_le K
  55. 0055specialize beta_sum_pointwise_le k
  56. 0056apply beta_sum_pointwise_le
  57. 0057intro i
  58. 0058intro a
  59. 0059intro z
  60. 0060intro hi
  61. 0061intro ha
  62. 0062intro hz
  63. 0063have heq : a = z
  64. 0064specialize prime_bit_prefix_equal_entry x2
  65. 0065specialize prime_bit_prefix_equal_entry x3
  66. 0066specialize prime_bit_prefix_equal_entry x
  67. 0067specialize prime_bit_prefix_equal_entry x1
  68. 0068specialize prime_bit_prefix_equal_entry N
  69. 0069specialize prime_bit_prefix_equal_entry i
  70. 0070specialize prime_bit_prefix_equal_entry a
  71. 0071specialize prime_bit_prefix_equal_entry z
  72. 0072apply prime_bit_prefix_equal_entry
  73. 0073exact hK_witness_witness_left
  74. 0074exact hk_witness_witness_left
  75. 0075exact hi
  76. 0076exact ha
  77. 0077exact hz
  78. 0078rewrite heq
  79. 0079specialize le_refl z
  80. 0080apply le_refl
  81. 0081exact hK_witness_witness_right
  82. 0082exact hk_witness_witness_right