Symbolic Sets for Proving Bounds on Rado Numbers

Tanbir Ahmed, Lamina Zaman, Curtis Bright · 2025

Read Symbolic Sets for Proving Bounds on Rado Numbers by Tanbir Ahmed, Lamina Zaman, Curtis Bright (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-12085.txt.

Introduction

Tanbir Ahmed and co-authors compute Rado numbers with solver help and prove new bounds, in work from 2025. A Rado number is the smallest span where any coloring with a set count of colors must hide a same-color solve of a fixed equation. The team works with three colors and two equation shapes.

Satisfiability solvers found many values that were not known before. The solver's winning colorings then hinted at general bounds, which the team proved by wide case checks. Those checks are too long to trust by hand, so a new tool checks them with symbolic sets built on known math libraries.

Catalog record

CREATORTanbir Ahmed, Lamina Zaman, Curtis Bright
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE67 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-12085

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Symbolic Sets for Proving Bounds on Rado Numbers Tanbir Ahmed, Lamina Zaman, Curtis Bright Abstract Given a linear equation ℰ \cal E of the form a ​ x + b ​ y = c ​ z ax+by=cz where a a , b b , c c are positive integers, the k k -colour Rado number R k ​ ( ℰ ) R_{k}({\cal E}) is the smallest positive integer n n , if it exists, such that every k k -colouring of the positive integers { 1 , 2 , … , n } \{1,2,\dotsc,n\} contains a monochromatic solution to ℰ {\cal E} . In this paper, we consider k = 3 k=3 and the linear equations a ​ x + b ​ y = b ​ z ax+by=bz and a ​ x + a ​ y = b ​ z 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 ) , … , f ⁡ ( a ) } \{f(1),f(2),\dotsc,f(a)\} where a a is a symbolic variable and f f is a function possibly dependent on a 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 . keywords Rado numbers, Ramsey Theory on the Integers, Satisfiability, SMT, Symbolic Computation † † copyrightyear: 2025 † † copyright: Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). † † venue: 10th International Workshop on Satisfiability Checking and Symbolic Computation, August 2, 2025, Stuttgart, Germany † † email: [email protected] † † url: https://tanbir.github.io/ † † email: [email protected] † † email: [email protected] † † url: https://cs.curtisbright.com/ † † address: School of Computer Science, University of Windsor, Canada 1 Introduction The study of Rado numbers Rado (1933) and colouring problems lies at the heart of Ramsey theory and additive combinatorics. In this paper, we present a number of new values and bounds on Rado numbers, as well as an automated framework for proving lower bounds on Rado numbers using symbolic partitioning and satisfiability checking. 1.1 Combinatorial context For integers a , b , let [a,b] denote the set of integers \left\{x:a\leq x\leq b\right\} . For a positive integer k\geq 2 , a system of linear equations is k -regular if there exists a positive integer n such that for every k -colouring of [1,n] , there exists a monochromatic solution to the system. A system is regular if it is k -regular for every integer k\geq 2 . The following theorem by Rado Rado (1933) gives necessary and sufficient conditions for when a linear equation is regular. Theorem 1.1 (Rado Rado (1933) ) . For nonzero integers a_{1} , a_{2} , \dotsc , a_{m} and integer c , let s=\sum_{i=1}^{m}a_{i} . Then: • The equation \sum_{i=1}^{m}a_{i}x_{i}=0 is regular if and only if there exists a nonempty set D\subseteq[1,m] such that \sum_{d\in D}a_{d}=0 . • The equation \sum_{i=1}^{m}a_{i}x_{i}=c is regular if and only if one of the following two conditions holds: (a) c/s\in{\mathbb{Z}}^{+} ; (b) c/s\in{\mathbb{Z}}^{-} and \sum_{i=1}^{m}a_{i}x_{i}=0 is regular. For nonzero integers a_{1} , a_{2} , \dotsc , a_{m} and integer c , let the linear equation \sum_{i=1}^{m-1}a_{i}x_{i}+c=a_{m}x_{m} be represented by {\cal E}(m,c;a_{1},a_{2},\ldots,a_{m}) . For a linear equation {\cal E}(m,c;a_{1},a_{2},\ldots,a_{m}) and a positive integer k , the k -colour Rado number R_{k}({\cal E}(m,c;a_{1},a_{2},\ldots,a_{m})) is defined as the smallest positive integer n , if it exists, from the definition of k -regularity demonstrating that the equation {\cal E}(m,c;a_{1},a_{2},\ldots,a_{m}) is k -regular. Otherwise, we say that R_{k}({\cal E}(m,c;a_{1},a_{2},\ldots,a_{m})) is infinite if there is a k -colouring of the positive integers with no monochromatic solution to {\cal E}(m,c;a_{1},a_{2},\ldots,a_{m}) . Surprisingly, not much is known about the properties of Rado numbers for k=3 . In 1995, Schaal Schaal (1995) proved that the 3-colour Rado numbers R_{3}({\cal E}(3,c;1,1,1)) are always finite and R_{3}({\cal E}(3,c;1,1,1))=13c+14 for c\geq 0 . In 2015, Adhikari et al. Adhikari et al. (2016) proved exact formulas for R_{3}({\cal E}(4,c;1,1,1,1)) and R_{3}({\cal E}(5,c;1,1,1,1,1)) with c\geq 0 . In 2022, Chang, De Loera, and Wesley Chang et al. (2022) proved • R_{3}({\cal E}(3,0;1,-1,a-2))=a^{3}-a^{2}-a-1 for a\geq 3 (previously conjectured by Myers Myers (2015) ), • R_{3}({\cal E}(3,0,a,-a,(a-1)))=a^{3}+(a-1)^{2} for a\geq 3 , and • R_{3}({\cal E}(3,0;a,-a,b))=a^{3} for b\geq 1 , a\geq b+2 , and \gcd(a,b)=1 . They also determined exact values of the Rado numbers • R_{3}({\cal E}(3,0;a,-a,b)) for 1\leq a,b\leq 15 , • R_{3}({\cal E}(3,0;a,a,b)) for 1\leq a,b\leq 10 , • R_{3}({\cal E}(3,0;a,b,c)) for 1\leq a,b,c\leq 6 , as well as the following theorem. Theorem 1.2 . R_{3}({\cal E}(3,0;1,1,a))=\infty for a\geq 4 and R_{3}({\cal E}(3,0;a,a,1))=\infty for a\geq 2 . 1.2 Our contributions In this paper, we have investigated values and bounds of Rado numbers for the equations {\cal E}(3,0;a,a,b) and {\cal E}(3,0;a,b,b) . We have computed a number of previously unknown exact values using SAT solvers, extending the results presented by Chang, De Loera, and Wesley Chang et al. (2022) to the values of • R_{3}({\cal E}(3,0;a,b,b)) for 1\leq b\leq 15 and 1\leq a\leq 30 , and • R_{3}({\cal E}(3,0;a,a,b)) for 1\leq a\leq 15 and 1\leq b\leq 25 . Note that we may assume that a and b are coprime, since if a and b share a common factor g we may divide the coefficients of the equation {\cal E} by g without changing its solutions, e.g., R_{3}({\cal E}(3,0;a,b,b))=R_{3}({\cal E}(3,0;a/g,b/g,b/g)) . Guided by the satisfying assignments generated by the SAT solver in the process of computing these values, we proved the following two theorems. Theorem 1.3 . For coprime positive integers a , b with a>b\geq 3 and a^{2}+a+b>b^{2}+ba , {R_{3}}({\cal E}(3,0;a,b,b))\geq a^{3}+a^{2}+(2b+1)a+1. Theorem 1.4 . For odd integers a\geq 7 , {R_{3}}({\cal E}(3,0;a,a,a+1))\geq a^{3}(a+1). Based on the computational data we generated and the above lower bounds, we propose the following conjectures. Conjecture 1.1 . For coprime positive integers a , b with a>b\geq 3 and a^{2}+a+b>b^{2}+ba , {R_{3}}({\cal E}(3,0;a,b,b))=a^{3}+a^{2}+(2b+1)a+1. Conjecture 1.2 . For coprime positive integers a , b , with a odd, if 3\leq a<b\leq 2a-1 then R_{3}({\cal E}(3,0;a,a,b))=a^{3}b. The proofs of Theorems 1.3 and 1.4 are automatically verified using a symbolic analyzer we developed in Python called AutoCase. 1 1 1 github.com/laminazaman/RadoNumbers/tree/main/AutoCase The motivation has been to avoid errors in the intricate case-based analysis which is often routine and repetitive. For example, in order to verify Theorem 1.4 , AutoCase takes as input three symbolically-defined subsets R , G , B of the integers [1,a^{3}(a+1)-1] (where a\geq 7 is a symbolic odd integer). AutoCase verifies that the union of R , G , and B is the set [1,a^{3}(a+1)-1] and that R ,

Read the complete text