On disjunctive Rado numbers for some sets of equations (Q6131743)

Summary: Given a set of linear equations \(\mathscr{S}\) with positive integral parameters \(a_1, \ldots, a_k\), \(k \geqslant 2\), the disjunctive Rado number for the set \(\mathscr{S}\) is the least positive integer \(R=\mathscr{R}_d(\mathscr{S})\), if it exists, such that every \(2\)-coloring \(\chi\) of the integers in \([1, R]\) admits a monochromatic solution to at least one equation in \(\mathscr{S}\). We give conditions for the existence of \(\mathscr{R}_d(\mathscr{S})\), and also give general upper and lower bounds on \(\mathscr{R}_d(\mathscr{S})\), when \(\mathscr{S}\) is a set of additive equations \(\{y=x+a_1, \ldots, y=x+a_k\}\). We also determine \(\mathscr{R}_d(\mathscr{S})\) when \(\max a_i\) is large enough, or when \(a_1, \ldots, a_k\) form an arithmetic or geometric progression. We also give conditions for the existence of \(\mathscr{R}_d(\mathscr{S})\) when \(\mathscr{S}\) is a set of multiplicative equations \(\{y=a_1 x, \ldots, y=a_k x\}\). Further, we give a general search-based algorithm to determine \(\mathscr{R}_d(\mathscr{S})\) when \(\mathscr{S}\) is a system of equations in two variables, given an upper bound on \(\mathscr{R}_d(\mathscr{S})\) and an algorithm to determine solutions to \(\mathscr{S}\). This algorithm runs in time \(O(ka_k \log a_k)\) for the case of additive equations, which is exponentially better than the brute-force algorithm for the problem.