Crab Research
返回结果列表
组合数学

关于 x + by = bz 的 Rado 数:b^k 模式与阈值猜想

On Rado Numbers for x + by = bz: The b^k Pattern and a Threshold Conjecture

工作论文 · SSRN首次公开 修订

研究概述

对于方程 x + by = bz,R_k(b) 是使每一种 k 色染色都必有单色解的最小区间大小。论文给出已知情形的解析证明、有限可满足性(SAT)检查,以及证明 R_5(3) 大于 296 的显式五色染色。阈值猜想描述何时 R_k(b) 等于 b^k;一般猜想仍未解决。2026 年 9 月更正将已知下界 R_5(2) ≥ 56 正确归于 Chang、De Loera 和 Wesley 的 R_4(2) = 56 结果。研究包含部分 Lean 形式化,并非整篇证明均已由 Lean 内核检查。

原文摘要(英文)

For integers b >= 2 and k >= 1, let R_k(b) denote the k-color Rado number for the equation x + by = bz, defined as the least positive integer n such that every k-coloring of {1, 2, ..., n} contains a monochromatic solution. Under the substitution d = z - y, this equation is equivalent to x = bd, placing it in the family studied by Chang, De Loera, and Wesley, who established R_k(b) >= b^k via the b-adic valuation, proved R_3(b) = b^3 for every b >= 3, and computed several four-color values. We contribute the following new results. First, we develop a Color Compression Lemma yielding a new self-contained analytic proof that R_2(b) = b^2 for all b >= 2 (with the compression step covering the case b >= 3 analytically and b = 2 by direct case analysis), and a hybrid analytic-SAT proof that R_3(3) = 27. Second, we give a hybrid analytic-SAT proof that R_4(3) = 81, in which the structural reduction (a self-loop step combined with a tree-shaped obstruction graph G*) is analytic and a single finite key lemma is verified by SAT; the same Distance Pair Lemma also independently verifies R_3(b) = b^3 for b in {4, ..., 10} and R_4(b) = b^4 for b in {3, 4, 5}. Third, we prove that the b^k pattern breaks: R_5(3) > 296 > 243 = 3^5, with an explicit public 5-coloring witness. Fourth, we identify a structural mechanism (the Distance Pair Lemma) underlying the b^k pattern and propose a precise threshold conjecture: R_k(b) = b^k if and only if k <= 2(b - 1). Fifth, we prove a Lift Lemma, an Upper-Bound Descent Lemma, and a Two-Cell Threshold Reduction: at any fixed b >= 2, the entire conjecture is equivalent to the adjacent boundary pair R_{2b-2}(b) = b^{2b-2} and R_{2b-1}(b) > b^{2b-1}. In particular, the backward direction at b in {2, 3} is thereby established in the threshold regime, and b >= 4 reduces to one finite witness per b. The case b = 3, k = 4 is the boundary case k = 2(b - 1) at b = 3, so R_4(3) = 81 is the largest boundary instance verified here. This revision corrects the attribution of the known lower bound R_5(2) >= 56; the analytic arguments and SAT-supported results are unchanged.

公开摘要来源

Rado numbersRamsey theorySAT solvingpartition regularityb-adic valuation

数学审核

内部定稿

内部定稿(Paper Close)表示该工作在公开前已完成整理和内部审核,并以工作论文形式发布。请将它作为普通学术预印本来阅读和讨论;后续检查或讨论仍可能带来更正。它不表示已经完成完整形式化或经过外部同行评审。

审核标准
返回结果列表
返回 数学