no. 12 · Tuesday 10 November 2026
A $33$-polynomial proof of a three-color Rado number formula
Abstract
For $k\ge 3$, let $T_k(3)$ denote the least $N$ such that every $3$-coloring of $[1,N]$ contains a monochromatic solution to $x+(k-1)y=z$. The formula $T_k(3)=k^3+2k^2-2$ is already known: it follows from a Theorem of Chang, De Loera, and Wesley. Their proof uses a symbolic SAT certificate with $685$ polynomials and $9468$ solution triples. The purpose of this paper is to give an independent, explicit proof based on a much smaller certificate. We exhibit a fixed set $\Xmin$ of $33$ polynomials in $k$ and the $144$ polynomial identities $z=x+(k-1)y$ among them, and show that no $3$-coloring of $\Xmin$ avoids a monochromatic identity. The resulting case analysis has $62$ cases, depth $8$, and uses only two elementary rules; it is given in full and independently checked by a program. We also prove that $\Xmin$ is a critical subset of minimum cardinality of the $51$-element set from which it was extracted, and describe the rigid structure shared by all extremal colorings of $[1,k^3+2k^2-3]$. The lower bound is supplied by an explicit recursive coloring. In the notation $s_a(3)$ of the first author, with $a=k-1$, the formula is $s_a(3)=a^3+5a^2+7a+1$, which was conjectured before.
- comments
- We have added a discussion of the earlier result of Chang, De Loera, and Wesley (ISSAC 2022), which establishes the same numerical formula under an equivalent change of variables. We have clarified the scope of our contribution, emphasizing the independent proof, the smaller polynomial certificate, and the structural results concerning extremal colorings
- fields
- Combinatorics