一般增长下界的完整Lean证明
全部k≥12 · 最大RS预算与整数增益Δ≥2 · 原Bool染色 · 可复现证据
来源信息
一般增长下界的完整 Lean 形式证明
对每个整数
指定主入口 formal/Aris4Math/General/Growth/Twelve.lean 已通过正式 Lake 构建;构建后的独立审计 formal/ReviewAuditGeneralGrowth12.lean 直接展开原始最大预算、积分和染色定义,也已编译成功。六项核心导出及两项独立原题复述的传递公理均仅含 propext、Classical.choice、Quot.sound。
定义:原超图、最大预算与整数增益
定义1(原超图与 Property B)。 设 Uniform、PropertyB 和 Bichromatic,原对象表示为 E : Finset (Finset V)、[Finite V]。
定义2(指定 RS 判据及其最大整数预算)。 对整数
称正整数
令
这一定义组合 Radhakrishnan–Srinivasan 作者稿 Appendix A、Claim A.1(第26–27页)的正关联端项,与 §2.1、Claim 2.4 证明中第7页的未编号精确积分,再使用有向单交边对数至多
Lean 中 AcceptedAt k M p 表示接受不等式及参数区间,RSAccepts k M 另要求 rsBudget k 表示最大预算。其实现先在有限区间 rsBudget_characterization_twelve 证明这正是对全部正整数的最大值,区间截断不是外部假设。
定义3(整数增益)。 对自然数
其中 integerGain k M;在本定理范围内被取整量为正,故与通常的整数下取整一致。
定理C:全部 k≥12 的原超图染色
定理C(已形式化)。 对每个整数
而且存在同一个严格参数见证
则存在
形式证明。 rsBudget_characterization_twelve 给出全体正整数中的最大性,rsBudget_parameter_twelve 给出实际正参数见证,seed_le_rsBudget_twelve 与 rsBudget_lt_twelve 给出两端界,integerGain_two_twelve 给出增益至少二。propertyB_of_general_growth_twelve 对任意原 E 构造染色,non_propertyB_edges_ge_general_growth_twelve 给出等价的不可染边数下界。完整独立复述 GeneralGrowthTwelveAudit.original_complete_statement 同时展开了积分、最大性、增益和原 Bool 两色见证;original_noncolorable_lower_bound 则展开原不可染命题。上述声明均已编译,并接受构建后的传递公理检查。∎
最终主接口如下;它没有点对覆盖、顶点数、度数、概率上界或内部证书前提。
theorem propertyB_of_general_growth_twelve {V : Type u} [Finite V]
(E : Finset (Finset V)) {k : ℕ} (hk : 12 ≤ k)
(hu : Uniform E k)
(hE : E.card ≤ rsBudget k + integerGain k (rsBudget k)) :
PropertyB E
证明:真实输入到增长下界的完整连接
引理1(实际最小反例的点对覆盖)。 设
证明。 若不同点 exists_pair_covering_counterexample、pairCovering_count 和 pairCovering_vertex_bound,源码 formal/Aris4Math/General/Structure/Reduction.lean。∎
引理2(同一反例上的单交团与有向计数)。 对顶点集大小为
则该图的每个团至多有
证明。 一个单交族若有公共点,删去公共点后各边两两不交,故族大小至多 singleGraph 直接使用原边子类型。singlePairsDartEquiv 把实际 singlePairs K 与该图的 darts 建立显式双射,证明 gamma_eq_twice_singleGraph_edges,然后调用固定 Mathlib 的 Turán 定理。最终 gamma_le_cliqueBudget 从 uniformity 内部给出所需界。源码为 formal/Aris4Math/General/Structure/Clique.lean 和 formal/Aris4Math/General/Structure/Turan.lean。此处的标准 Turán 接口见锁定版本 Mathlib 的 Mathlib/Combinatorics/SimpleGraph/Extremal/Turan.lean 中 CliqueFree.card_edgeFinset_le、mul_card_edgeFinset_turanGraph_le;有向计数接口为 Mathlib/Combinatorics/SimpleGraph/DegreeSum.lean 中 dart_card_eq_twice_card_edges。∎
引理3(种子预算与全正整数最大性)。 对每个整数
证明。 当
在
Lean 的 seed_ak_three_fifths 对这五个自然数参数使用 interval_cases 与 norm_num 验证精确有理数不等式;这不是超图或染色枚举。seed_acceptedAt_twelve。
设
于是 rsBudget_characterization_twelve 并未把有限截断当外部前提。参数控制的 Lean 声明为 acceptedAt_parameter_control_two,最大值、严格正参数和两端界均在 formal/Aris4Math/General/Growth/Twelve.lean 内导出。∎
引理4(同一个已接受参数的增长余量)。 设整数
的自然数
此外
证明。 从
下取整与
引理1的计数与
这里严格性由
Lean 声明为 pow_four_le_nine_pow_two、integerGain_two_twelve、cliqueBudget_le_three_sqrt 和 integerGain_log_slack_twelve,均位于 formal/Aris4Math/General/Growth/Twelve.lean。∎
定理C的证明链。 取 rs_increment_of_log_slack 的对数增长估计,证明新增
上述概率层复用已完成的 formal/Aris4Math/General/RS/ProbabilityBound.lean:共同初态/资格位/排列样本、实际失败覆盖、正关联、初始单色边平均、单交对精确积分及成功样本提取均在同一证明依赖链内。此次没有把这些结论重新作为未证概率前提。
核验:指定主构建与独立原题审计
| 核验对象 | 实际结果 | 证据 |
|---|---|---|
增长主链 Aris4Math.General.Growth.Twelve | 正规 Lake 构建 exit 0,2576 jobs,墙钟15.64秒;包含既有依赖缓存与重放 | context/propertyb-general/bridge-12-16-20261021/lean/BUILD.log |
| 构建后独立原题审计 | ReviewAuditGeneralGrowth12.lean 编译 exit 0,墙钟7.70秒;展开最大预算、原积分、floor与原Bool染色 | formal/ReviewAuditGeneralGrowth12.lean、context/propertyb-general/bridge-12-16-20261021/lean/REVIEW_AUDIT.log |
| 六项核心导出的传递公理 | 均仅 propext、Classical.choice、Quot.sound | context/propertyb-general/bridge-12-16-20261021/lean/BUILD.log |
| 两项独立原题复述的传递公理 | 均仅 propext、Classical.choice、Quot.sound | context/propertyb-general/bridge-12-16-20261021/lean/REVIEW_AUDIT.log |
六项核心导出分别为最大预算刻画、严格正参数、整数增益至少二、任意接受预算的增长调用、完整原超图增长定理和不可染边数下界。构建后独立审计还核查两个直接以原积分、原量词和原颜色见证写成的完整声明。没有 sorryAx、新增未证公理或 native_decide。2576 是 Lake 依赖任务计数,包含缓存与重放,不是新增模块数。
以上是本机主执行者保存的正规增量构建与构建后独立导入证据;阅读页生成过程没有重新运行 Lean,也未声称第二台机器或他人已复现。机器可读核验见 context/propertyb-general/bridge-12-16-20261021/lean/VERIFICATION.json。
复现:固定环境与精确入口
环境沿用 Lean 4.24.0。formal/lean-toolchain 与 formal/lake-manifest.json 固定依赖;Mathlib 提交为 f897ebcf72cd16f89ab4577d0c826cd14afaafc7。
在项目根目录执行:
export ELAN_HOME=/Users/rfy_naiveai/Desktop/aris4math/.tools/elan
export PATH="$ELAN_HOME/bin:$PATH"
cd /Users/rfy_naiveai/Desktop/aris4math/formal
lake build Aris4Math.General.Growth.Twelve
lake env lean ReviewAuditGeneralGrowth12.lean
独立审计只导入实际增长主入口,并打印 AcceptedAt、RSAccepts、rsBudget、integerGain、Uniform、PropertyB、Bichromatic 的定义、原题声明和传递公理。默认 lake build 的旧主模块不能代替这里的指定增长入口。
与纸面证明的关系及审阅范围
本次形式化覆盖全部
比较定理D、E继续是纸面结论,本次没有完成它们的 Lean 形式化。数学主阅读页为 PROPERTY_B_GENERAL_BOUND.html。旧
本轮 grok-4.7-build/xhigh、end_turn;原回应见 context/propertyb-general/bridge-12-16-20261021/GROK_REVIEW.json。它讨论纸面扩展,不代替 Lean 构建或最终完整源码审阅。新增 Lean 完成后的最终 Grok 审阅也已有效完成,实际身份仍为 grok-4.7-build/xhigh、end_turn。它全文读取 formal/Aris4Math/General/Growth/Twelve.lean、formal/ReviewAuditGeneralGrowth12.lean 和本次构建/审计记录,核查全正整数最大性、内部正参数、增益至少二与完整原Bool染色接口,在实际范围内未发现实质问题。它没有执行 Lean,也没有重审旧概率/结构模块的全部证明体。完整范围及处置见 context/propertyb-general/bridge-12-16-20261021/REVIEW_DISPOSITION.md。
旧结构链与旧