On the n-Color Weak Rado Numbers for the Equation x1 + x2 + ··· + xk + c = xk +1

Abstract

For integers k, n, c with k, n ≥ 1, the n-color Rado number Rk(n, c) is defined to be the least integer N, if it exists or ∞ otherwise, such that for every n-coloring of the set {1, 2,...,N}, there exists a monochromatic solution in that set to the equation x1 + x2 + ··· + xk + c = xk+1. In this paper, we mostly restrict to the case c ≥ 0, and consider two main issues regarding Rk(n, c): is it finite or infinite, and when finite, what is its value? Very few results are known so far on either one. On the first issue, we formulate a general conjecture, namely that Rk(n, c) should be finite if and only if every divisor d ≤ n of k − 1 also divides c. The “only if” part of the conjecture is shown to hold, as well as the “if” part in the cases where either k − 1 divides c, or n ≥ k − 1, or k ≤ 7, except for two instances to be published separately. On the second issue, we obtain new bounds on Rk(n, c) and determine exact formulae in several new cases, including R3(3, c) and R4(3, c). As for the case R2(3, c), first settled by Schaal in 1995, we provide a new shorter proof. Finally, the problem is reformulated as a Boolean satisfiability problem, allowing the use of a SAT solver to treat some instances.