ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 18 (2020) 281-288
https://doi.org/10.26493/1855-3974.2019.30b
(Also available at http://amc-journal.eu)
Schur numbers involving rainbow colorings
Mark Budden ©
Department of Mathematics and Computer Science, Western Carolina University, Cullowhee, North Carolina, USA
Received 5 June 2019, accepted 26 April 2020, published online 21 October 2020
In this paper, we introduce two different generalizations of Schur numbers that involve rainbow colorings. Motivated by well-known generalizations of Ramsey numbers, we first define the rainbow Schur number RS (n) to be the minimum number of colors needed such that every coloring of {1,2,..., n}, in which all available colors are used, contains a rainbow solution to a + b = c. It is shown that
Second, we consider the Gallai-Schur number GS (n), defined to be the least natural number such that every n-coloring of {1,2,..., GS(n)} that lacks rainbow solutions to the equation a + b = c necessarily contains a monochromatic solution to this equation. By connecting this number with the n-color Gallai-Ramsey number for triangles, it is shown that for all n > 3,
Keywords: Schur numbers, anti-Ramsey numbers, rainbow triangles, Gallai colorings. Math. Subj. Class. (2020): 05C55, 05D10, 11B75
1 Introduction
One of the earliest results that falls under the blanket of Ramsey theory is a theorem of Issai Schur [11] from 1916. In fact, his work predates Frank Ramsey's foundational paper [10]. Schur proved that for any n G N, there exists a minimal S(n) G N such that every n-coloring of the elements in the set {1,2,..., S(n)} contains elements a, b, and c of the same color such that a + b = c. Such a triple a, b, and c is called a monochromatic
E-mail address: mrbudden@email.wcu.edu (Mark Budden)
Abstract
RS(n) = [log2 (n)J + 2, for all n > 3.
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
282
Ars Math. Contemp. 18 (2020) 187-210
Schur solution and we note that it is possible that a = b. The number S(n) is called a Schur number and it is well-known that S(1) = 2, S(2) = 5, S(3) = 14, S(4) = 45 (see Golomb and Baumert [ ]). Recently, Heule [ ] has shown that S(5) = 161. We note that some authors define a Schur number to be the largest f (n) G N such that some n-coloring of {1,2,..., f (n)} lacks a monochromatic Schur solution. It is easily seen that S (n) = f (n) + 1.
A thorough overview of Schur numbers is given in Landman and Robertson's book [9] and in Section 3 of Soifer's article [12]. Schur's theorem is interesting from a combinatorial perspective, but his motivation was a tool for proving that the congruence
xm + ym = zm (mod p)
contains a nontrivial solution when p is a sufficiently large prime (specifically, p > S(n)). This result had been originally proved by Dickson [4] in 1908 in his attempt to prove Fermat's Last Theorem.
In this paper, we adapt some common generalizations of Ramsey numbers that involve rainbow colorings to Schur numbers. In Section 2, we consider the minimum number of colors such that every coloring of {1,2,..., n}, using all of the colors, contains a rainbow Schur solution. This leads us to the definition of the rainbow Schur number RS(n), which is a Schur number analogue of rainbow numbers (closely related to anti-Ramsey numbers). The number RS(n) is similar in definition to the number ss(k) defined in [5], but does not restrict the number of times each color can be used. In Section 3, we restrict ourselves to colorings of {1,2,..., k} that lack rainbow Schur solutions: a, b, and c with distinct colors such that a + b = c. Limiting the colorings in this way leads to the definition of the Gallai-Schur number GS (n). We provide exact evaluations of both RS (n) and GS (n) and offer some related open questions for future inquiry.
2 Rainbow Schur numbers
In this section, we consider Schur number analogues of rainbow numbers and anti-Ramsey numbers (c.f., Chapter 11, Section 4 of [2]). For n > 3, define the rainbow Schur number RS(n) to be the minimum number of colors such that every coloring of {1, 2,..., n}, using all RS(n) colors, contains a rainbow Schur solution: a, b, and c all distinct colors such that a + b = c. Observe that a + b = c is never a rainbow Schur solution when a = b. As with the case of graphs, the rainbow Schur number is closely related to the anti-Schur number AS(n), defined to be the maximum number of colors that can be used to color {1, 2,..., n} so that no rainbow Schur solution exists. From these definitions, it follows that
RS(n) = AS(n) + 1, for all n > 3.
Since determining the values of these two numbers is equivalent, we will focus on RS (n) for the remainder of this section, beginning with a few small values of n.
Observe that at least three colors are needed to have a rainbow triangle. Using all three colors to color {1,2,3}, we find that 1 + 2 = 3 is rainbow. Thus,
RS(3) = 3.
Next, consider the following 3-coloring of
{1, 2, 3, 4}.
M. Budden: Schur numbers involving rainbow colorings
283
It is easily checked that no rainbow Schur solutions exist, implying that RS(4) > 3. Of course, 4-coloring {1,2,3,4} produces a rainbow Schur solution, implying that
RS (4) = 4.
The following 3-coloring does not contain any rainbow Schur solutions:
{1, 2, 3, 4, 5}.
Thus, RS(5) > 3. Now consider a 4-coloring of {1,2,3,4, 5}. If 5 is assigned the same color as some i < 5, then the coloring induces a 4-coloring of {1,2,3,4}, which necessarily contains a rainbow Schur solution. Otherwise, the color assigned to 5 is not assigned to any other number. In order to avoid a rainbow Schur solution, 1 and 4 receive the same color, as do 2 and 3. Since all three remaining colors must be used, either 1+4 = 5 or 2 + 3 = 5 must be rainbow. Hence,
RS(5) = 4.
As a crude general bound, note that giving unique colors to the numbers in {1, 2,..., n} necessarily produces a rainbow Schur solution when n > 3. Thus,
RS (n) < n,
proving that RS(n) exists for all n > 3. Suppose that every k-coloring of {1,2,..., n} contains a rainbow Schur solution, then every (k + 1)-coloring of {1, 2,..., n +1} also contains a rainbow Schur solution. It follows that
RS (n + 1) < RS (n) + 1.
If there exists a k-coloring of {1,2,..., n + 1} that lacks a rainbow Schur solution, then it induces such a coloring on {1, 2,..., n}. Hence,
RS(n) < RS(n + 1), for all n > 3.
The following lemma will allow us to show that equality holds for most values of n.
Lemma 2.1. Let n > 6 and suppose that RS(n — 1) = k and RS (|_nj) < k — 1. Then RS (n) = k.
Proof. Suppose that RS(n — 1) = k and RS (|_2j) < k — 1 and consider a k-coloring of {1, 2, . . . , n}. If the color assigned to n is shared with some i < n, then this coloring induces a k-coloring of {1, 2,..., n — 1}, which necessarily contains a rainbow Schur solution. So, assume that n is assigned a unique color. If n is even, and a rainbow Schur solution is avoided, then numbers in each of the sets
,1.»—1}, ,2.»—2,,..., {=—!.=+!}. {n}
are colored according to the set they are in. That is, 1 and n — 1 receive the same color, 2 and n — 2 receive the same color, etc. If n is odd, and a rainbow Schur solution is avoided, then numbers in each of the sets
r	in — 1 n +1]
{1, n — 1}, {2, n — 2},...,|—,j
are colored according to which set they are in. In both cases, we are reduced to considering a (k — 1)-coloring of {1,2,..., |_nj }, which contains a rainbow Schur solution. □
284
Ars Math. Contemp. 18 (2020) 187-210
Observe that the colorings that have given us lower bounds for RS(4) and RS(5) have both had the odd numbers grouped into a single color class (red). This leads us to the following lemma.
Lemma 2.2. For all k > 2, RS(2k ) > k +1.
Proof. Define the map ê2 : N —> N U{0} by
tf2(a) = t ^ 2£ | a and 2£+1 f a.
Color the elements of {1,2,..., 2k} according to their images $2(a) G {0,1,..., k}. It can now be confirmed that this (k + 1)-coloring does not contain any rainbow Schur solutions. Certainly any Schur solution a + b = c in which $2(a) = $2(b) is not rainbow colored. Now, consider the case in which (a) = t < k = $2 (b). Then we can write
a + b = 2£(e + f ), where e is odd and f is even.
So, (a + b) = t and we see that such a Schur solution is not rainbow colored. We have produced a (k + 1)-coloring of {1,2,..., 2k} that does not contain any rainbow Schur solutions. It follows that RS(2k) is greater than k + 1.	□
Theorem 2.3. For all n > 3, RS(n) = |>g2(n)J + 2.
Proof. Proving this theorem is equivalent to proving that if 2k < n < 2k+1 — 1, then RS (n) = k + 2 for all n > 3. We have already shown this result to be true for 3 < n < 5. We proceed by strong induction on n. Suppose that the theorem is true for all n such that 3 < n < m, for some m > 6 and consider the rainbow Schur number RS(m + 1). There are two cases to consider.
Case 1: If m + 1 is not a power of 2, then we can write
2k + 1 < m + 1 < 2k+1 — 1, for some k. It follows that m < 2k+1 — 2 and the inductive hypothesis implies that
RS (m) = |_log2(m)J + 2 and RS
m + 1 2
log2
m +1 2
+ 2
= log2(m) + 1.
Hence, RS(m + 1) = |_log2(m)J +2 by Lemma 2.1.
Case 2: If m + 1 = 2k for some k > 2, then RS(m) = k +1 by the inductive hypothesis. By Lemma 2.2, RS(m + 1) > k +1. Consider a (k + 2)-coloring of {1,2,..., m + 1}. Regardless of the color assigned to m+1, at least k+1 colors are assigned to {1,2,..., m}, which necessarily contains a rainbow Schur solution. Thus, RS(m + 1) = k + 2, when
m + 1 = 2k.	□
3 Gallai-Schur numbers
A Gallai n-coloring of {1,2,..., k} is a coloring that lacks rainbow Schur solutions. For every n G N, define the Gallai-Schur number GS (n) to be the least positive integer such
M. Budden: Schur numbers involving rainbow colorings
285
that every Gallai n-coloring of {1,2,..., GS(n)} contains a monochromatic Schur solution. It is easily observed that GS(1) = S(1) = 2, GS(2) = S(2) = 5, and
GS(n) < S(n), for all n > 3.
The Gallai-Schur number GS (n) is closely related to the Gallai-Ramsey number grn(3), defined to be the minimum number of vertices p needed to guarantee that every rainbow-triangle-free n-coloring of the edges of the complete graph Kp contains a monochromatic triangle. The following theorem makes this relationship explicit.
Theorem 3.1. For all n > 3, GS(n) < grn(3) - 1.
Proof. Let p = grn(3) and identify the vertices in Kp with {1, 2,... ,p}. For every pair of distinct vertices a, b e {1,2,... ,p}, color edge ab according to the value of |b - a| e {1, 2,...,p - 1}. If we consider a Gallai n-coloring of Kp, it necessarily contains a monochromatic triangle. Suppose the vertices of such a triangle are given by a < b < c. Then setting x = b — a, y = c — b, and z = c — a, it follows that
x + y =(b — a) + (c — b) = c — a = z
is monochromatic. Also, note that no rainbow Schur solutions exist because if x + y = z is rainbow, then the triangle with vertices 1, x + 1, and x + y +1 would be rainbow as well. Thus, every Gallai n-coloring of {1,2,... ,p — 1} produces a monochromatic Schur solution:
GS(n) < grn(3) — 1,
completing the proof of the theorem.	□
In 1983, Chung and Graham (see Theorem 1 of [3]) proved a result equivalent to
V + 1 if n = 2k
grn(3) = Hence, Theorem 3.1 gives
2 • 5k + 1 if n = 2k + 1.
i 5k if n = 2k GS(n) < 5 ,f 2	(3.1)
2 • 5k if n = 2k +1.
To find a lower bound for GS (n) when n > 3, we begin with some preliminary examples. It is straight-foward to check that
{1, 2, 3,4, 5, 6, 7, 8, 9}
is a Gallai 3-coloring that lacks a monochromatic Schur solution. It follows that GS(3) > 9. Combining this inequality with Theorem 3.1, we find that
GS (3) = 10.
One can also check that
{1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19, 20, 21, 22, 23, 24}
286
Ars Math. Contemp. 18 (2020) 187-210
is a Gallai 4-coloring that lacks a monochromatic Schur solution, which implies GS(4) > 24. Combining this inequality with Theorem 3.1, we find that
GS (4) = 25.
The following theorem offers a general lower bound for GS (n).
Theorem 3.2. The set {1,2,..., grn(3) — 2} can be Gallai n-colored without producing a monochromatic Schur solution.
Proof. Similar to the proof of Lemma 2.2, define the map $5 : N —> N U {0} by
$5(a) = £	5 | a and 5i+1 \ a.
First, we consider the case in which n = 2k, where n > 4. We will construct a Gallai n-coloring of S = {1,2,..., 5k — 1} that lacks a monochromatic Schur solution. We start by partitioning S according to the images of elements under the map $5. This gives us the following k sets:
Si = {a | $5(a) = £}, where I = 0,1,..., k — 1. Each Si is then partitioned into two distinct color classes:
S+ = {a $5 (a) = £ and = ±1 (mod 5)} ,
S— = I a $5(a) = I and 0> = ±2 (mod
We have now partitioned S into n = 2k color classes. It remains to be shown that such a coloring lacks both rainbow and monochromatic Schur solutions. We consider several cases for adding a, b e S.
Case 1: Suppose that a and b receive different colors. Then there exist two subcases.
Subcase 1.1: Assume that $5(a) = $5(b) = Since a and b receive different colors, without loss of generality, it follows that
= ±1 (mod 5) and = ±2 (mod 5).
It follows that $5 (a + b) = and hence, either a or b receives the same color as a + b. So, this subcase does not produce a rainbow or monochromatic Schur solution.
Subcase 1.2: Without loss of generality, assume that $5 (a) — £1 < £2 — $5(b). Then
$5 (a + b) = £1 and
a + b a bp» a . , . —r- = -T- +—t • 5i2 1 ^^ (mod 5).
5ii	5ii 5i2	5ii v	'
In this subcase, a and a + b receive the same color, avoiding both a rainbow and monochromatic Schur solution.
Case 2: Suppose that a and b receive the same color. Then $5 (a) = $5 (b) = I and either
a = ±1 (mod 5) or	= ±2 (mod 5).
M. Budden: Schur numbers involving rainbow colorings
287
Once again, we consider two subcases.
Subcase 2.1: If $5(a+b) > $5(a) = $5(6), then a+b necessarily receives a color different than that of a and b.
Subcase 2.2: Suppose that $5(a + b) = $5 (a) = $5(b) = Of § = £ = ±1 (mod 5), then ^ = ±2 (mod 5) and if 5 = ^ = ±2 (mod 5), then ^ = ± 1 (mod 5).
In all cases, we find that a, b, and a + b never form a rainbow or monochromatic Schur solution. The same construction also provides a Gallai n-coloring of
4 Conclusion
We have shown how extremal results from graph theory can be used to prove related number theoretic results. Although we have succeeded in providing exact evaluations of GS(n) and RS (n), the generalizations considered here lead to analogous constructions involving weak Schur numbers (see [8]) and generalized Schur numbers (see [1]). Such work is reserved for future inquiry.
ORCID iD
Mark Budden © https://orcid.org/0000-0002-4065-6317 References
[1]	A. Beutelspacher and W. Brestovansky, Generalized Schur numbers, in: Combinatorial Theory, Springer, Berlin-New York, volume 969 of Lecture Notes in Mathematics, 1982 pp. 30-38, Proceedings of a Conference held at Schloss Rauischholzhausen, May 6-9, 1982.
[2]	G. Chartrand and P. Zhang, Chromatic Graph Theory, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, Florida, 2009.
[3]	F. R. K. Chung and R. L. Graham, Edge-colored complete graphs with precisely colored subgraphs, Combinatorica 3 (1983), 315-324, doi:10.1007/bf02579187.
[4]	L. E. Dickson, On the last theorem of Fermat, Quart. J. Pure Appl. Math. 40 (1908), 27-45.
[5]	J. Fox, V. Jungic and R. Radoicic, Sub-Ramsey numbers for arithmetic progressions and Schur triples, Integers 7 (2007), #A12, http://math.colgate.edu/~integers/ a12int2 0 0 5/a12int2 0 05.Abstract.html.
[6]	S.W. Golomb and L.D.Baumert, Backtrack programming, J.Assoc. Comput. Mach. 12 (1965), 516-524, doi:10.1145/321296.321300.
[7]	M. J. H. Heule, Schur number five, in: S. A. Mcllraith and K. Q. Weinberger (eds.), Thirty-Second AAAI Conference on Artificial Intelligence, AAAI Press, 2018 pp. 6598-6606, Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th
S' = {1, 2, .. ., 2 • 5k - 1}
when n = 2k +1, and we leave the details to the reader.
□
Putting together the results of Theorems 3.1 and 3.2, we find that
288
Ars Math. Contemp. 18 (2020) 187-210
innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, https://www.aaai.org/ocs/index.php/AAAI/AAAI18/ paper/view/16 952.
[8]	R. W. Irving, An extension of Schur's theorem on sum-free partitions, ActaArith. 25 (1973/74), 55-64, doi:10.4064/aa-25-1-55-64.
[9]	B. M. Landman and A. Robertson, Ramsey Theory on the Integers, volume 24 of Student Mathematical Library, American Mathematical Society, Providence, Rhode Island, 2004.
[10]	F. P. Ramsey, On a Problem of Formal Logic, Proc. London Math. Soc. 30 (1929), 264-286, doi:10.1112/plms/s2-30.1.264.
[11]	I. Schur, Uber die Kongruenz xm + ym = zm (mod p), Jber. Deutsch. Math-Verein. 25 (1916), 114-117.
[12]	A. Soifer, Ramsey theory before Ramsey, prehistory and early history: an essay in 13 parts, in: A. Soifer (ed.), Ramsey Theory: Yesterday Today and Tomorrow, Birkhäuser/Springer, New York, volume 285 of Progress in Mathematics, pp. 1-26, 2011, doi:10.1007/ 978-0-8176-8092-3_1, Papers from the workshop held at Rutgers University, Piscataway, NJ, May 27 - 29, 2009.