Symbolic Sets for Proving Bounds on Rado Numbers

Résumé : Given a linear equation $\cal E$ of the form $ax + by = cz$ where $a$, $b$, $c$ are positive integers, the $k$-colour Rado number $R_k({\cal E})$ is the smallest positive integer $n$, if it exists, such that every $k$-colouring of the positive integers $\{1, 2, \dotsc, n\}$ contains a monochromatic solution to $\cal E$. In this paper, we consider $k = 3$ and the linear equations $ax + by = bz$ and $ax + ay = bz$. Using SAT solvers, we compute a number of previously unknown Rado numbers corresponding to these equations. We prove new general bounds on Rado numbers inspired by the satisfying assignments discovered by the SAT solver. Our proofs require extensive case-based analyses that are difficult to check for correctness by hand, so we automate checking the correctness of our proofs via an approach which makes use of a new tool we developed with support for operations on symbolically-defined sets -- e.g., unions or intersections of sets of the form $\{f(1), f(2), \dotsc, f(a)\}$ where $a$ is a symbolic variable and $f$ is a function possibly dependent on $a$. No computer algebra system that we are aware of currently has sufficiently capable support for symbolic sets, leading us to develop a tool supporting symbolic sets using the Python symbolic computation library SymPy coupled with the Satisfiability Modulo Theories solver Z3.