op_1239_candidate36_recurrence_values
The ten coefficients produced by the explicit rooted recurrence for the 36-vertex candidate are 8339521563, 20789154045, 21845817576, 12541674376, 4251096840, 852919728, 94592768, 4666944, 32640, and 256.
Statement
theorem op_1239_candidate36_recurrence_values : (PetrialCert.padd PetrialCert.s0.1 (0 :: PetrialCert.s0.2)).take 10 = [8339521563, 20789154045, 21845817576, 12541674376, 4251096840, 852919728, 94592768, 4666944, 32640, 256]- Source
- OP-1239: rooted-state arithmetic for the 36-vertex candidate, computed independently in experiments 28328 and 28332.
- Verified
- 16 Nov 2026
- Axioms
- none — Lean reports it depends on no axioms
- Used by 1
- op_1239_candidate36_petrial_coefficientsThe partial Petrial coefficients of op_1239_candidate36 in ranks 27, 28, and 29 are respectively 256, 32640, and 4666944.
The proof, explained
The proof computes the polynomial coefficients of a 36-vertex graph candidate using an explicit rooted tree recurrence. Intermediate states are certified bottom-up from the leaves to the root s0 via computational reflection (decide). Finally, the root state s0 is substituted into the expression, and direct arithmetic evaluation verifies that its first ten recurrence values match the specified list.
Evaluate the recurrence certificate bottom-up from the leaves to the root state s0. automation
Starting from the trivial base cases on empty subtrees, each intermediate node combination is simplified and evaluated by finite arithmetic via decide, culminating in the certified polynomial pair for s0.
simp only [s71] decide def s34 := combine [] theorem s34_cert : s34 = ([1], [1]) := by simp only [s34] decide def s73 := combine [] theorem s73_cert : s73 = ([1], [1]) := by simp only [s73] decide def s42 := combine [s71] theorem s42_cert : s42 = ([3], [1]) := by simp only [s42, s71_cert] decide def s31 := combine [s34] theorem s31_cert : s31 = ([3], [1]) := by simp only [s31, s34_cert] decide def s52 := combine [] theorem s52_cert : s52 = ([1], [1]) := by simp only [s52] decide def s25 := combine [] theorem s25_cert : s25 = ([1], [1]) := by simp only [s25] decide def s61 := combine [] theorem s61_cert : s61 = ([1], [1]) := by simp only [s61] decide def s46 := combine [s73] theorem s46_cert : s46 = ([3], [1]) := by simp only [s46, s73_cert] decide def s33 := combine [] theorem s33_cert : s33 = ([1], [1]) := by simp only [s33] decide def s17 := combine [] theorem s17_cert : s17 = ([1], [1]) := by simp only [s17] decide def s60 := combine [] theorem s60_cert : s60 = ([1], [1]) := by simp only [s60] decide def s26 := combine [s31, s42] theorem s26_cert : s26 = ([21, 2], [9]) := by simp only [s26, s31_cert, s42_cert] decide def s30 := combine [] theorem s30_cert : s30 = ([1], [1]) := by simp only [s30] decide def s15 := combine [] theorem s15_cert : s15 = ([1], [1]) := by simp only [s15] decide def s10 := combine [s25, s52] theorem s10_cert : s10 = ([5, 2], [1]) := by simp only [s10, s25_cert, s52_cert] decide def s21 := combine [s46, s61] theorem s21_cert : s21 = ([11, 2], [3]) := by simp only [s21, s46_cert, s61_cert] decide def s9 := combine [] theorem s9_cert : s9 = ([1], [1]) := by simp only [s9] decide def s68 := combine [] theorem s68_cert : s68 = ([1], [1]) := by simp only [s68] decide def s41 := combine [] theorem s41_cert : s41 = ([1], [1]) := by simp only [s41] decide def s14 := combine [s33] theorem s14_cert : s14 = ([3], [1]) := by simp only [s14, s33_cert] decide def s13 := combine [s17] theorem s13_cert : s13 = ([3], [1]) := by simp only [s13, s17_cert] decide def s16 := combine [s26, s60] theorem s16_cert : s16 = ([81, 24], [21, 2]) := by simp only [s16, s26_cert, s60_cert] decide def s12 := combine [s30] theorem s12_cert : s12 = ([3], [1]) := by simp only [s12, s30_cert] decide def s7 := combine [s10, s15] theorem s7_cert : s7 = ([17, 8], [5, 2]) := by simp only [s7, s10_cert, s15_cert] decide def s6 := combine [s9, s21] theorem s6_cert : s6 = ([39, 12], [11, 2]) := by simp only [s6, s9_cert, s21_cert] decide def s35 := combine [] theorem s35_cert : s35 = ([1], [1]) := by simp only [s35] decide def s11 := combine [s41, s68] theorem s11_cert : s11 = ([5, 2], [1]) := by simp only [s11, s41_cert, s68_cert] decide def s50 := combine [] theorem s50_cert : s50 = ([1], [1]) := by simp only [s50] decide def s5 := combine [s13, s14] theorem s5_cert : s5 = ([21, 2], [9]) := by simp only [s5, s13_cert, s14_cert] decide def s4 := combine [s12, s16] theorem s4_cert : s4 = ([531, 174, 4], [243, 72]) := by simp only [s4, s12_cert, s16_cert] decide def s2 := combine [s6, s7] theorem s2_cert : s2 = ([1427, 1146, 240, 8], [663, 516, 96]) := by simp only [s2, s6_cert, s7_cert] decide def s8 := combine [s11, s35] theorem s8_cert : s8 = ([17, 8], [5, 2]) := by simp only [s8, s11_cert, s35_cert] decide def s3 := combine [s5, s50] theorem s3_cert : s3 = ([81, 24], [21, 2]) := by simp only [s3, s5_cert, s50_cert] decide def s1 := combine [s2, s4] theorem s1_cert : s1 = ([2155365, 2720202, 1247288, 247536, 18096, 32], [757737, 856824, 332552, 50592, 2352, 32]) := by simp only [s1, s2_cert, s4_cert] decide def s0 := combine [s1, s3, s8] theorem s0_cert : s0 = ([8339521563, 17821216440, 15824033982, 7537795408, 2070824856, 327124224, 27912416, 1158720, 26496, 256], [2967937605, 6021783594, 5003878968, 2180271984, 525795504, 66680352, 3508224, 6144]) := by simp only [s0, s1_cert, s3_cert, s8_cert] decide
Substitute the certified root polynomial pair for s0 into the goal.
Rewriting by PetrialCert.s0_cert substitutes the explicit pair of coefficient lists computed for the root s0.
uses
PetrialCert.s0_certrw [PetrialCert.s0_cert]The first ten coefficients of padd s0.1 (0 :: s0.2) match the target list. automation
Evaluating the polynomial addition and taking the first ten elements yields the expected coefficient list by direct arithmetic computation (decide).
decide
PetrialCert.s0_cert- The precomputed polynomial pair at the root state s0
- The recurrence tree computations (s71 through s0) are verified entirely by computational reflection (`decide`) after unfolding definitions and earlier certified values.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option maxRecDepth 100000set_option maxHeartbeats 0namespace PetrialCertdef padd : List Nat → List Nat → List Nat | [], b => b | a, [] => a | a::as, b::bs => (a+b)::padd as bsdef psub : List Nat → List Nat → List Nat | [], _ => [] | a, [] => a | a::as, b::bs => (a-b)::psub as bsdef pmul : List Nat → List Nat → List Nat | [], _ => [] | a::as, b => padd (b.map (a * ·)) (0 :: pmul as b)def combine (xs : List (List Nat × List Nat)) : List Nat × List Nat := let s := xs.foldl (fun p x => pmul p x.1) [1] let d := xs.foldl (fun p x => pmul p (padd x.1 (0::x.2))) [1] (padd s ((psub d s).drop 1 |>.map (2 * ·)), s)def s71 := combine []theorem s71_cert : s71 = ([1], [1]) := by simp only [s71] decidedef s34 := combine []theorem s34_cert : s34 = ([1], [1]) := by simp only [s34] decidedef s73 := combine []theorem s73_cert : s73 = ([1], [1]) := by simp only [s73] decidedef s42 := combine [s71]theorem s42_cert : s42 = ([3], [1]) := by simp only [s42, s71_cert] decidedef s31 := combine [s34]theorem s31_cert : s31 = ([3], [1]) := by simp only [s31, s34_cert] decidedef s52 := combine []theorem s52_cert : s52 = ([1], [1]) := by simp only [s52] decidedef s25 := combine []theorem s25_cert : s25 = ([1], [1]) := by simp only [s25] decidedef s61 := combine []theorem s61_cert : s61 = ([1], [1]) := by simp only [s61] decidedef s46 := combine [s73]theorem s46_cert : s46 = ([3], [1]) := by simp only [s46, s73_cert] decidedef s33 := combine []theorem s33_cert : s33 = ([1], [1]) := by simp only [s33] decidedef s17 := combine []theorem s17_cert : s17 = ([1], [1]) := by simp only [s17] decidedef s60 := combine []theorem s60_cert : s60 = ([1], [1]) := by simp only [s60] decidedef s26 := combine [s31, s42]theorem s26_cert : s26 = ([21, 2], [9]) := by simp only [s26, s31_cert, s42_cert] decidedef s30 := combine []theorem s30_cert : s30 = ([1], [1]) := by simp only [s30] decidedef s15 := combine []theorem s15_cert : s15 = ([1], [1]) := by simp only [s15] decidedef s10 := combine [s25, s52]theorem s10_cert : s10 = ([5, 2], [1]) := by simp only [s10, s25_cert, s52_cert] decidedef s21 := combine [s46, s61]theorem s21_cert : s21 = ([11, 2], [3]) := by simp only [s21, s46_cert, s61_cert] decidedef s9 := combine []theorem s9_cert : s9 = ([1], [1]) := by simp only [s9] decidedef s68 := combine []theorem s68_cert : s68 = ([1], [1]) := by simp only [s68] decidedef s41 := combine []theorem s41_cert : s41 = ([1], [1]) := by simp only [s41] decidedef s14 := combine [s33]theorem s14_cert : s14 = ([3], [1]) := by simp only [s14, s33_cert] decidedef s13 := combine [s17]theorem s13_cert : s13 = ([3], [1]) := by simp only [s13, s17_cert] decidedef s16 := combine [s26, s60]theorem s16_cert : s16 = ([81, 24], [21, 2]) := by simp only [s16, s26_cert, s60_cert] decidedef s12 := combine [s30]theorem s12_cert : s12 = ([3], [1]) := by simp only [s12, s30_cert] decidedef s7 := combine [s10, s15]theorem s7_cert : s7 = ([17, 8], [5, 2]) := by simp only [s7, s10_cert, s15_cert] decidedef s6 := combine [s9, s21]theorem s6_cert : s6 = ([39, 12], [11, 2]) := by simp only [s6, s9_cert, s21_cert] decidedef s35 := combine []theorem s35_cert : s35 = ([1], [1]) := by simp only [s35] decidedef s11 := combine [s41, s68]theorem s11_cert : s11 = ([5, 2], [1]) := by simp only [s11, s41_cert, s68_cert] decidedef s50 := combine []theorem s50_cert : s50 = ([1], [1]) := by simp only [s50] decidedef s5 := combine [s13, s14]theorem s5_cert : s5 = ([21, 2], [9]) := by simp only [s5, s13_cert, s14_cert] decidedef s4 := combine [s12, s16]theorem s4_cert : s4 = ([531, 174, 4], [243, 72]) := by simp only [s4, s12_cert, s16_cert] decidedef s2 := combine [s6, s7]theorem s2_cert : s2 = ([1427, 1146, 240, 8], [663, 516, 96]) := by simp only [s2, s6_cert, s7_cert] decidedef s8 := combine [s11, s35]theorem s8_cert : s8 = ([17, 8], [5, 2]) := by simp only [s8, s11_cert, s35_cert] decidedef s3 := combine [s5, s50]theorem s3_cert : s3 = ([81, 24], [21, 2]) := by simp only [s3, s5_cert, s50_cert] decidedef s1 := combine [s2, s4]theorem s1_cert : s1 = ([2155365, 2720202, 1247288, 247536, 18096, 32], [757737, 856824, 332552, 50592, 2352, 32]) := by simp only [s1, s2_cert, s4_cert] decidedef s0 := combine [s1, s3, s8]theorem s0_cert : s0 = ([8339521563, 17821216440, 15824033982, 7537795408, 2070824856, 327124224, 27912416, 1158720, 26496, 256], [2967937605, 6021783594, 5003878968, 2180271984, 525795504, 66680352, 3508224, 6144]) := by simp only [s0, s1_cert, s3_cert, s8_cert] decideend PetrialCert/-- A checked arithmetic certificate for a recursively computed candidate coefficient list; relating the recurrence to matrix nullities remains a separate obligation. -/theorem op_1239_candidate36_recurrence_values : (PetrialCert.padd PetrialCert.s0.1 (0 :: PetrialCert.s0.2)).take 10 = [8339521563, 20789154045, 21845817576, 12541674376, 4251096840, 852919728, 94592768, 4666944, 32640, 256] := by rw [PetrialCert.s0_cert] decide