On the Two-Color Disjunctive Rado Number for the Equations \(\sum_{i=1}^{m-2} x_i+ax_{m-1}-x_m=c_j, j=1,2\)
Full text
#A108 INTEGERS 25 (2025) ON THE TWO-COLOR DISJUNCTIVE RADO NUMBER FOR THE EQUATIONS Pm−2 i=1 xi+axm−1−xm=cj,j= 1,2 Srashti Dwivedi Department of Pure and Applied Mathematics, Alliance University, Bengaluru, India [email protected] Amitabha Tripathi1 Department of Mathematics, Indian Institute of Technology, New Delhi, India [email protected] Received: 6/7/25, Revised: 9/19/25, Accepted: 11/10/25, Published: 11/25/25 Abstract Given a system of linear equations S, the disjunctive Rado number for the system Sis the least positive integer R=R(S), if it exists, such that every 2-coloring of the integers in [1, R] admits a monochromatic solution to at least one equation in S. We determine R(S) when Sis the pair of equations Pm−2 i=1 xi+axm−1−xm= c1,Pm−2 i=1 xi+axm−1−xm=c2for some range of values of c1and c2. 1. Introduction By an r-coloring of {1, . . . , N}we mean a mapping χ:{1, . . . , N}→{1, . . . , r}. In 1916, Schur showed that for every positive integer r, there exists a least positive integer s=s(r) such that for every r-coloring of the integers in the interval [1, s], there exists x, y, x +y∈[1, s] such that χ(x)=χ(y) = χ(x+y). Schur’s theorem was generalized in a series of results in the 1930’s by Rado leading to a complete resolution to the following problem: characterize systems of linear homogeneous equations with integral coefficients Ssuch that for a given positive integer r, there exists a least positive integer n=R(S;r) such that every r-coloring of the integers in the interval [1, n] yields a monochromatic solution to the system S. There has been a growing interest in the determination of the Rado numbers R(S;r), particularly when Sis a single equation and r= 2; for instance, see [1, 6, 7, 8, 9, 10, 12]. When r= 2, we denote this number simply by R(S). DOI: 10.5281/zenodo.17711638 1Corresponding author
INTEGERS: 25 (2025) 2 The problem of disjunctive Rado numbers was introduced by Johnson and Schaal in [11]. The 2-color disjunctive Rado number for the set of equations E1,...,Ek is the least positive integer Nsuch that any 2-coloring of {1, . . . , N}admits a monochromatic solution to at least one of the equations E1,...,Ek; we denote this by R(E1,...,Ek). Johnson and Schaal gave necessary and sufficient conditions for the existence of the 2-color disjunctive Rado number for the additive equations x1−x2=aand x1−x2=bfor all pairs of distinct positive integers a, b, and also determined exact values when it exists. They also determined exact values for the pair of multiplicative equations ax1=x2and bx1=x2whenever a, b are distinct positive integers; for alternate proofs, see [2]. Dileep, Moondra and Tripathi [3] extended the results of Johnson and Schaal to the set of equations x1−x2=ai, 1≤i≤k, giving conditions for the existence of the 2-color disjunctive Rado number, exact values in some cases, and upper and lower bounds in all cases. They also investigated and obtained parallel results for the set of multiplicative equations y=aix, 1 ≤i≤k. Further, they gave a general search-based algorithm with a run time of O(kaklog ak) for the case of additive equations, which is exponentially better than the brute-force algorithm for the problem. Lane-Harvard and Schaal [14] determined exact values of 2-color disjunctive Rado number for the pair of equations ax1+x2=x3and bx1+x2=x3for all distinct positive integers a, b. Sabo, Schaal and Tokaz [15] determined exact values of 2-color disjunctive Rado number for x1+x2−x3=c1, and x1+x2−x3=c2, whenever c1, c2are distinct positive integers. Kosek and Schaal [13] determined the exact value of 2-color disjunctive Rado number for the equations x1+···+xm−1=xm, and x1+···+xn−1=xn, for all pairs of distinct positive integers m, n. Schaal and Zinter [16] studied the 2-color Rado number for the equation x1+ 3x2+c=x3for c≥3, giving a lower bound in all cases and upper bounds in some. Dwivedi and Tripathi [4] generalized this to investigate the 2-color Rado number for the equation x1+ax2−x3=cfor positive integers a, giving conditions for existence, upper and lower bounds in all cases, and exact results in a few. The same authors [5] further generalized this to investigate the 2-color Rado number for the equation Pm−2 i=1 xi+axm−1+xm=cwhen 4 ≤m≤a. They give a necessary and sufficient condition for the Rado number to exist, give upper and lower bounds in all cases, and exact values in many cases. This paper investigates the disjunctive Rado number problem for the pair of equations Pm−2 i=1 xi+axm−1−xm=c1and Pm−2 i=1 xi+axm−1−xm=c2. We reproduce some pertinent results from [5] for ready reference. Theorem 1 ([5, Theorem 1]). Let a, c, m ∈Z, and 4 ≤m≤a. If a+m, and care both odd, then R m−2 X i=1 xi+axm−1−xm=c! does not exist.
INTEGERS: 25 (2025) 3 Proposition 2 ([5, Proposition 1]). For a∈N, and 4 ≤m≤a, R m−2 X i=1 xi+axm−1−xm=a+m−3!= 1. Theorem 3 ([4, Theorem 3], [5, Theorem 5]). Let a, m be integers of the same parity, with a≥3, and m≥3. Let a′=a+m−3. If either of (i) m= 3, and c≤ −a(a−3) 2; (ii) m≥4, and c<−(a′+ 3)(a−2) is true, then R m−2 X i=1 xi+axm−1−xm=c!= (a′+ 3)(a′−c) + 1. 2. Results for Pm−2 i=1 xi+axm−1−xm=cj,j= 1,2 We study the disjunctive Rado number for the pair of equations m−2 X i=1 xi+axm−1−xm=c1,(1a) m−2 X i=1 xi+axm−1−xm=c2,(1b) where a≥3, m≥3, and c1,c2are any integers. Throughout this paper, we denote this 2-color Rado number by Rad21,...,1 | {z } m−2 times , a, −1; c1, c2, or more briefly by R(c1, c2). By assigning the color of xiin the solution of Equation (1a) and Equation (1b) to xi−1, we note that this is equivalent to determining the smallest positive integer Rfor which every 2-coloring of [0, R −1] contains a monochromatic solution to m−2 X i=1 xi+axm−1−xm=c′ 1,(2a) or m−2 X i=1 xi+axm−1−xm=c′ 2,(2b) where c′ j=cj−a′,j∈ {1,2}, and a′=a+m−3.
INTEGERS: 25 (2025) 4 Proposition 4. Let a, λ, n ∈Nsuch that a≥3,n≥1, and λ≥a−1. Then for each N∈ {0, . . . , λ(a+n)}the equation n X i=1 xi+axn+1 =N(3) admits a solution with each xi∈ {0, . . . , λ}. Proof. If N=λ(a+n), then xi=λfor i∈ {1, . . . , n + 1}is a solution to Equation (3). If 0 ≤N < λ(a+n), we can write N=q(a+n)+ϵa +r, where 0 ≤q < λ, 0≤r≤n, and ϵ∈ {0,1}. Then, xi=q+ 1 for 1 ≤i≤r,xi=qfor r+ 1 ≤i≤n, and xn+1 =q+ϵis a solution to Equation (3). Theorem 5. Let 4≤m≤a, and cj=kj(a+m−3) with 1< kj≤a+m−2for j∈ {1,2}. Then, R(c1, c2) = min{k1, k2}. Proof. Let k= min{k1, k2}. The coloring ∆ : [1, k−1] → {0,1}defined by ∆(x)=0 is a valid coloring, since m−2 X i=1 xi+axm−1−xm≤(a+m−2)(k−1) −1 =k(a+m−3) + (k−2) −(a+m−3) < k(a+m−3). Hence, R(c1, c2)≥k. On the other hand, since x1=· · · =xm=ksatisfies Equations (1a) or (1b) for cj=k(a+m−3), j= 1,2, every coloring χ: [1, k]→ {0,1}admits a monochromatic solution to Equations (1a) or (1b). Hence, R(c1, c2)≤k. Theorem 6. Let a, m be integers of the same parity, with a≥3, and m≥4. Let a′=a+m−3, and c′ j=cj−a′for j∈ {1,2}. Then, for c1<−(a′+ 3)(a−2), R(c1, c2) = (a′+ 3)(a′−c1)+1 if c1−a′≤c2≤c1, (a′+ 2)(a′−c1)+1 if (a′+ 2)c1−a′(a′+ 1) ≤c2< c1−a′, (a′−c2)+1 if (a′+ 3)c1−a′(a′+ 2) < c2<(a′+ 2)c1−a′(a′+ 1), (a′+ 3)(a′−c1)+1 if c2≤(a′+ 3)c1−a′(a′+ 2). (4a) (4b) (4c) (4d) Proof. We note that a′=a+m−3, and that R(c1, c2)≤min{R(c1),R(c2)}= (a′+ 3)(a′−c1) + 1 = −(a′+ 3)c′ 1+ 1
INTEGERS: 25 (2025) 5 by Theorem 1. We consider two cases: (I) given by Equation (4a) and Equation (4d), and (II) given by Equation (4b) and Equation (4c). Thus, in Case I, it suffices to prove that R(c1, c2)≥(a′+3)(a′−c1)+1 to complete the proof of Case I. Case I. We exhibit a valid coloring of [1,(a+m)(a+m−c1−3)] with respect to Equation (1a) and (1b). Let ∆ : [1,(a+m)(a+m−c1−3)] → {0,1}be defined by ∆(x) = 0 if x∈[1, a +m−c1−3] S[(a+m−1)(a+m−c1−3) + 1,(a+m)(a+m−c1−3)], 1 if x∈[a+m−c1−2,(a+m−1)(a+m−c1−3)]. Let A= [1, a +m−c1−3], B= [a+m−c1−2,(a+m−1)(a+m−c1−3)], and C= [(a+m−1)(a+m−c1−3) + 1,(a+m−1)(a+m−c1−3)]. Suppose x1, . . . , xmis a solution to Equation (1a), with ∆(x1) = ··· = ∆(xm). Suppose ∆(xi) = 0 for i∈ {1, . . . , m}. If x1, . . . , xm−1all belong to A, then a+m−c1−2≤xm= m−2 X i=1 xi+axm−1−c1 ≤(a+m−2)(a+m−c1−3) −c1 ≤(a+m−1)(a+m−c1−3). Hence, xm∈B, and so χ(xm) = 1. If at least one of x1, . . . , xm−1belongs to Cand min Cdenotes the least element in C, then, xm= m−2 X i=1 xi!+axm−1−c1≥(a+m−c1−3)+min C= (a+m)(a+m−c1−3)+1. Hence, xmis outside the domain of ∆. Therefore, ∆(xi) = 1 for i∈ {1, . . . , m}, and so xm= m−2 X i=1 xi!+axm−1−c1≥(a+m−2)·min B−c1≥(a+m−1)(a+m−c1−3)+1, where min Bdenotes the least element in B. Hence, xm∈C. This proves that ∆ is a valid coloring of [1,(a+m)(a+m−c1−3)] with respect to Equation (1a). For Equation (4a), the same argument applies with respect to Equation (1b). For Equation (4d) xm= m−2 X i=1 xi+axm−1−c2>(a+m)(a+m−c1−3). Hence, xmis outside the domain of ∆. Thus, ∆ is a valid coloring of [1,(a+m)(a+ m−c1−3)] with respect to Equation (1b). This concludes the proof of Case I.
INTEGERS: 25 (2025) 6 Case II. The coloring ∆, with suitable modifications, also provides a valid coloring for Equation (4b) and (4c). For Equation (4b), we consider the function ∆, restricted to [1,(a+m−1)(a+m−c1−3)] = A∪B. A sub-argument used in Equation (4a) shows that this is a valid coloring for Equation (1a) and (1b). For Equation (4c), we consider the function ∆, restricted to [1, a+m−c2−3]=A∪B∪C′, where C′= [(a+m−1)(a+m−c1−3)+1, a+m−c2−3]. An argument similar to the one for Equation (4a) shows that this is a valid coloring for Equation (1a) and (1b). Since we have provided valid colorings for Case II, it only remains to prove the upper bounds in this case. By assigning the color of xiin the solution of Equation (1a) and (1b) to xi− 1, we equivalently consider monochromatic solutions to Equation (2a) and (2b), respectively, under colorings that start with x= 0. Let χ: [0,−(a′+ 3)c′ 1]→ {0,1} be any 2-coloring of [0,−(a′+ 3)c′ 1]. Without loss of generality, let χ(0) = 0. Each step in the following sequence forces a color on some number in the given range in order to avoid a mononchromatic solution to Equation (2a) or (2b): •xi= 0 for 1 ≤i≤m−1 implies χ(−c′ 1) = 1 and χ(−c′ 2) = 1; •xi=−c′ 1for 1 ≤i≤m−1 implies χ−(a′+ 2)c′ 1= 0; •xi= 0 for 2 ≤i≤m−1, and xm=−(a′+ 2)c′ 1implies χ−(a′+ 1)c′ 1= 1. We capture this information in Table 1. 0 1 0−c′ j −(a′+ 2)c′ j−(a′+ 1)c′ j Table 1 To complete the proof in Case II, we must show that: •every 2-coloring of χ: [0,−(a′+ 2)c′ 1]→ {0,1}must yield a monochromatic solution to one of Equation (2a), (2b) for −(c′ 1−a′)<−c′ 2≤ −(a′+2)c′ 1, and •every 2-coloring of χ: [0,−c′ 2]→ {0,1}must yield a monochromatic solution to one of Equation (2a), (2b) for −(a′+ 2)c′ 1<−c′ 2<−(a′+ 3)c′ 1. We have assumed, without loss of generality, that χ(0) = 0. There are two possibilities for χ(1), of which the case χ(1) = 1 is common to Equation (4b) and (4c). We first assume χ(1) = 1. We claim that χ−tc′ 1−a′=(0 if tis odd; 1 if tis even
INTEGERS: 25 (2025) 7 for t∈ {1, . . . , a′}. With each xi= 1, 2 ≤i≤m−1, and xm=−(a′+ 1)c′ 1in Equation (2a), we have x1=−a′(c′ 1+ 1), forcing χ−a′c′ 1−a′= 0 in order to avoid a monochromatic coloring. This proves the claim for t=a′. Suppose t∈ {3, . . . , a′},tis odd, and that χ−tc′ 1−a′= 0. We begin the inductive step at t=a′. To complete the claim, we show that if χ−tc′ 1−a′= 0, then χ−(t−1)c′ 1−a′= 1 and χ−(t−2)c′ 1−a′= 0 for t∈ {3, . . . , a′}. Each step in the following sequence forces a color on some number in the given range in order to avoid a mononchromatic solution to Equation (2a): •xi= 0 for 2 ≤i≤m−1, and xm=−tc′ 1−a′implies χ−(t−1)c′ 1−a′= 1; •x1=−(t−1)c′ 1−a′, and xi= 1 for 2 ≤i≤m−1 implies χ−tc′ 1= 0; •xi= 0 for 2 ≤i≤m−1, and xm=−tc′ 1implies χ−(t−1)c′ 1= 1; •xi= 1 for 2 ≤i≤m−1, and xm=−(t−1)c′ 1implies χ−(t−2)c′ 1−a′= 0. In particular, from the above claim, χ−c′ 1−a′= 0. We note that χ(a+m− 1)c′ 1= 0 from Table 1. Each step in the following sequence forces a color on some number in the given range in order to avoid a mononchromatic solution to Equation (2a) or (2b): •x1=−c′ 1−a′,xi=−c′ 1+ 1 for 2 ≤i≤m−1, and xm=−(a+m−1)c′ 1 implies χ−c′ 1+ 1= 1; •x1=−c′ 1+ 1, and xi= 1 for 2 ≤i≤m−1 implies χ−2c′ 1+ (a′+ 1)= 0; •xi= 0 for 2 ≤i≤m−1, and xm=−2c′ 1+(a′+1) implies χ−c′ 1+(a′+1)= 1. Now xi= 1 for 1 ≤i≤m−1, and xm=−c′ 1+ (a′+ 1) forms a monochromatic solution to Equation (2a). This completes the proof when χ(1) = 1. For the remainder of the proof, we consider the case when χ(1) = 0. We claim that χ(n)=0for0≤n≤−2c′ 1 a′=K. (5) By way of contradiction, assume χ(n) = 1 for some n≤K. We claim this implies χ−tc′ 1=(0 if tis even; 1 if tis odd for t∈ {1, . . . , a′}. From Table 1, we have χ(−c′ 1) = 1. Let t∈ {1,...,a′−2}. Assuming χ(−tc′ 1) = 1 when tis odd, we show that χ−(t+ 1)c′ 1= 0 and χ−(t+2)c′ 1= 1. Each step in the following sequence forces a color on some number in the given range in order to avoid a mononchromatic solution to Equation (2a): •x1=−tc′ 1, and xi=nfor 2 ≤i≤m−1 implies χ−(t+ 1)c′ 1+na′= 0;
INTEGERS: 25 (2025) 8 •x1=−(t+1)c′ 1+na′, and xi= 0 for 2 ≤i≤m−1 implies χ−(t+2)c′ 1+na′= 1; •xi=nfor 2 ≤i≤m−1, and xm=−(t+2)c′ 1+na′implies χ−(t+1)c′ 1= 0; •x1=−(t+ 1)c′ 1, and xi= 0 for 2 ≤i≤m−1 implies χ−(t+ 2)c′ 1= 1. In particular, we have χ−a′c′ 1= 1. We note that the maximum allowable value of numbers used is −a′c′ 1+Ka′from the second step, and this lies in the domain of χ. In order that the numbers lie in the domain of χ, we must have −a′c′ 1+na′≤ −(a′+ 2)c′ 1, in particular. This implies n≤ −2c′ 1 a′. To complete the claim that χ(n) = 0 for 0 ≤n≤K, we show that χ−a′c′ 1= 0 by using Table 1. Each step in the following sequence forces a color on some number in the given range in order to avoid a mononchromatic solution to Equation (2a) or (2b): •xi=nfor 2 ≤i≤m−1, and xm=−(a′+ 1)c′ 1implies χ−a′c′ 1−na′= 0; •xi= 0 for 2 ≤i≤m−1, and xm=−a′c′ 1−na′implies χ−(a′−1)c′ 1−na′= 1; •x1=−(a′−1)c′ 1−na′, and xi=nfor 2 ≤i≤m−1 implies χ−a′c′ 1= 0. This contradiction completes the proof of the claim that χ(n) = 0 for 0 ≤n≤K. It can be shown that a≤K, and so we have χ(n) = 0 for 0 ≤n≤a, in particular. For the rest of this proof, we consider Equation (4b) and (4c) separately. We first consider Equation (4b). By assigning the color of xiin the solution of Equation (1a) and (1b) to xi−1, we note that the ranges of c1and c2translate to −c′ 1+a′+ 1 ≤ −c′ 2≤ −(a′+ 2)c′ 1. We use χ(n) = 0 for 0 ≤n≤a, and prove that χ(n) = 0 for a+1 ≤n≤ −c′ 1−1. Let t+ 1 = min{n:χ(n)=1}; we have shown that t+ 1 > a. By way of contradiction, we may assume t+1 ≤ −c′ 1−1. By Proposition 4, the expression Pm−2 i=1 xi+axm−1 assumes every value in the interval [0,(a′+1)t] as each xiruns over the set {0, . . . , t}. Under the same range for the xi’s, the expression m−2 X i=1 xi+axm−1−c′ 2=xm assumes every value in the interval I= [−c′ 1+a′+ 1,(a′+ 1)t−(a′+ 2)c′ 1]. So in order to avoid a monochromatic solution to Equation (2b), we must have χ(n) = 1 for each n∈I. Now choosing xi=t+ 1, 1 ≤i≤m−1 in Equation (2a) forces χ(a′+ 1)(t+ 1) −c′ 1= 0 in order to avoid a mononchromatic solution. But (a′+ 1)(t+ 1) −c′ 1lies within [−c′ 1+a′+ 1,(a′+ 1)t−(a′+ 2)c′ 1], and this is a contradiction to the conclusion from the previous paragraph. Therefore, we have the claim that χ(n) = 0 for 0 ≤n≤ −c′ 1−1.
INTEGERS: 25 (2025) 9 From the above argument for t=−c′ 1−1, the expression m−2 X i=1 xi+axm−1−c′ 2=xm assumes every value in the interval J= [−c′ 1+a′+ 1,−(a′+ 1)(c′ 1+ 1) −(a′+ 2)c′ 1]. Since −(a′+2)c′ 1∈J, there exist x1, . . . , xm−1, with each xi∈ {0,...,−c′ 1−1}, such that Pm−2 i=1 xi+axm−1−c′ 2=−(a′+ 2)c′ 1. This gives a monochromatic solution to Equation (2b), since χ−(a′+ 2)c′ 1= 0 by Table 1. This completes the argument for Equation (4b). We now consider Equation (4c). By assigning the color of xiin the solution of Equation (1a) and (1b) to xi−1, we note that the ranges of c1and c2translate to −(a′+ 2)c′ 1<−c′ 2≤ −(a′+ 3)c′ 1−1. Recall that χ(n) = 0 for 0 ≤n≤−2c′ 1 a′. Each step in the following sequence forces a color on some number in the given range in order to avoid a mononchromatic solution to Equation (2a): •xi=−c′ 1for 2 ≤i≤m−1, and xm=−c′ 2implies χ(a′+ 1)c′ 1−c′ 2= 0; •x1= (a′+ 1)c′ 1−c′ 2, and xi= 0 for 2 ≤i≤m−1 implies χa′c′ 1−c′ 2= 1. We capture this information in Table 2. 0 1 0−c′ 1 −(a′+ 2)c′ 1−c′ 2 (a′+ 1)c′ 1−c′ 2−(a′+ 1)c′ 1 Table 2 Arguing as in Equation (4b), with t=K, the expression m−2 X i=1 xi+axm−1−c′ 2=xm assumes every value in the interval K= [−c′ 2,(a′+1)K−c′ 2]. Since (a′+1)c′ 1−c′ 2∈K, there exist x1, . . . , xm−1, with each xi∈ {0, . . . , K}, such that Pm−2 i=1 xi+axm−1− c′ 2= (a′+ 1)c′ 1−c′ 2. This gives a monochromatic solution to Equation (2b), since χ(a′+ 1)c′ 1−c′ 2= 0 by Table 2. This completes the argument in Equation (4c), thereby completing the proof of Theorem 6.