The Schur degree of additive sets

Discrete Mathematics 344 (2021) 112332 Contents lists available at ScienceDirect Discrete Mathematics journal homepage: www.elsevier.com/locate/disc The Schur degree of additive sets S. Eliahou a,b,∗, M.P. Revuelta c aUniv. Littoral Côte d’Opale, UR 2597 - LMPA - Laboratoire de Mathématiques Pures et Appliquées Joseph Liouville, F-62100 Calais, France bCNRS, FR2037, France cDepartamento de Matemática Aplicada I, Universidad de Sevilla, Avenida de la Reina Mercedes 4, C.P. 41012 Sevilla, Spain article info Article history: Received 21 October 2020 Received in revised form 22 January 2021 Accepted 25 January 2021 Available online 12 February 2021 Keywords: Sumfree Schur numbers Ramsey numbers Discrete derivative Minors abstract Let (G,+) be an abelian group. A subset of Gis sumfree if it contains no elements x,y,z such that x+y=z. We extend this concept by introducing the Schur degree of a subset of G, where Schur degree 1 corresponds to sumfree. The classical inequality S(n)≤Rn(3)−2, between the Schur number S(n) and the Ramsey number Rn(3) =R(3,...,3), is shown to remain valid in a wider context, involving the Schur degree of certain subsets of G. Recursive upper bounds are known for Rn(3) but not for S(n) so far. We formulate a conjecture which, if true, would fill this gap. Indeed, our study of the Schur degree leads us to conjecture S(n)≤n(S(n−1) +1) for all n≥2. If true, it would yield substantially better upper bounds on the Schur numbers, e.g. S(6) ≤966 conjecturally, whereas all is known so far is 536 ≤S(6) ≤1836. ©2021 Elsevier B.V. All rights reserved. 1. Introduction For a,b∈Z, let [a,b] = {z∈Z|a≤z≤b}and [a,∞[= {z∈Z|a≤z}denote the integer intervals they span. Denote N= {0,1,2, . . . }and N+=N\ {0}. A subset of Zis sumfree if it contains no elements x,y,zsuch that x+y=z. The problem of partitioning [1,N]into as few sumfree parts as possible was initiated by Schur [11]. Given n∈N+, Schur established the existence of a number S(n) such that [1,N]can be partitioned into nsumfree parts if and only if N≤S(n). The S(n) are called the Schur numbers and, despite more than a century in existence, remain poorly understood at the time of writing. Their only currently known values are (S(1),S(2),S(3),S(4),S(5))=(1,4,13,44,160).(1) See Section 5.2 for more details. In his paper, Schur proved the following upper bound and recursive lower bound on the S(n) for n≥2, namely 3S(n−1) +1≤S(n)≤n!e,(2) leading in particular to S(n)≥(3n−1)/2 for all n≥2. ∗Corresponding author at: Univ. Littoral Côte d’Opale, UR 2597 - LMPA - Laboratoire de Mathématiques Pures et Appliquées Joseph Liouville, F-62100 Calais, France. E-mail addresses: [email protected] (S. Eliahou), [email protected] (M.P. Revuelta). https://doi.org/10.1016/j.disc.2021.112332 0012-365X/©2021 Elsevier B.V. All rights reserved. S. Eliahou and M.P. Revuelta Discrete Mathematics 344 (2021) 112332 For n≥1, the n-color Ramsey number Rn(3) =R(3,...,3) denotes the smallest Nsuch that, for any n-coloring of the edges of the complete graph KNon Nvertices, there is a monochromatic triangle. See [10] for an extensive dynamic survey on this topic. Only three of the numbers Rn(3) are currently known, namely (R1(3),R2(3),R3(3))=(3,6,17).(3) As for n=4, the presently known bounds are 51 ≤R4(3) ≤62. It is conjectured in [14] that R4(3) equals 51. Similarly to the upper bound in (2), it was shown in [8] that Rn(3) ≤n!e+1 for all n≥1. This bound has later been improved to Rn(3) ≤n!(e−1/6) +1 for all n≥4 in [15]. See also [4], where the conjecture R4(3) =51 is shown to imply Rn(3) ≤n!(e−5/8) +1 for all n≥4. In fact, there is a well known relationship between the Schur and the Ramsey numbers, namely S(n)≤Rn(3) −2.(4) See e.g. [12]. That is, if the set [1,N]admits a partition into n sumfree parts, then N ≤Rn(3) −2. We shall show here that (4) holds in a more general context. Let (G,+) be an abelian group. As in Z, a subset of Gis sumfree if it contains no elements x,y,zsuch that x+y=z. Given a finite sequence A=(a1,...,aN) in G, let us denote by ˆ Athe set of all block sums ai+ · · · + ajof A, where 1 ≤i≤j≤N. For instance, if A=(1,...,1) of length Nin G=Z, then ˆ A= [1,N]. In this paper, we are concerned with partitioning subsets of Gof the form ˆ Ainto as few sumfree parts as possible. As just noted, this includes Schur’s original problem for the integer intervals [1,N]. Our extension of (4) to this more general setting states that if A is a sequence in G of length |A| = N and if ˆ A can be covered by n sumfree parts, then N ≤Rn(3) −2. Currently, the best available theoretical upper bound on S(n) for n≥4 is the one provided by (4). While the Ramsey numbers Rn(3) satisfy the well known recursive upper bound Rn(3) ≤n(Rn−1(3) −1) +2 for all n≥2 [8, Theorem 6, p. 6], no similar statement is known yet for the S(n). Here we fill this gap, at least conjecturally, as an outcome of our study of sumfree partitions of sets of the form ˆ A. Indeed, as we shall see, that study leads us to conjecture the following recursive upper bound, for all n≥2: S(n)≤n(S(n−1) +1).(5) The contents of this paper are as follows. In Section 2, we introduce the Schur degree and the basic notions and tools needed in the sequel. In Section 3, we prove initial properties of the Schur degree and illustrate them with selected examples in Z. Our main result, an extension of (4) to sets ˆ Abounding their Schur degree with the Ramsey numbers Rn(3), is proved in Section 4. The material developed so far leads us in Section 5to the conjectural recursive upper bound (5), a substantial would-be improvement over (4). 2. Basic notions and tools Here is the main notion introduced and studied in this paper. Definition 2.1. Let (G,+) be an abelian group. Let X⊆Gbe a subset. We define the Schur degree of X, denoted sdeg(X), as the smallest n≥1 such that Xcan be covered by nsumfree subsets. If no such nexists, we set sdeg(X)= ∞. For instance, sdeg(X)=1 if and only if Xis sumfree, whereas sdeg(X)= ∞ whenever 0 ∈X, as {0}is not sumfree. As another instance, in Nwe have sdeg([1,S(n)])=n,sdeg([1,S(n)+1])=n+1 (6) by definition of S(n). Equivalently, sdeg([1,N])≤n⇐⇒ N≤S(n). Measuring the Schur degree of most subsets is likely to remain an extremely difficult task, even for the integer intervals [1,N]as witnessed by the still highly mysterious Schur numbers S(n). In this paper, we focus on subsets of a certain form ˆ A, generalizing the intervals [1,N]and introduced below. 2.1. Block sums Let (G,+) be an abelian group. Let A=(a1,...,aN) be a finite sequence in G. We denote by |A| = Nits length and by σ(A)=∑iaithe sum of its elements. Ablock in Ais any nonempty subsequence of consecutive elements of A. That is, any subsequence of the form B=(ai,...,aj) for some 1 ≤i≤j≤N. A block sum in Ais a sum σ(B) where Bis any block in A, i.e. any element in Gof the form ai+ · · · + ajfor some 1 ≤i≤j≤N. 2 S. Eliahou and M.P. Revuelta Discrete Mathematics 344 (2021) 112332 Notation 2.2. Let A =(a1,...,aN)be a sequence in G. We denote by ˆ A= {σ(B)|B is a block in A}, the set of block sums in A. For instance, if A=(1,...,1) of length Nin Z, then ˆ A= [1,N]as noted above. In this paper, we initiate the study of the Schur degree of subsets of the form ˆ Afor finite sequences Ain G, with the hope to shed some light on the basic case [1,N]in Z. Our main result is Theorem 4.1, an extension of (4) to this context. 2.2. Minors We show here that the association A↦→ ˆ Ais monotone with respect to taking minors, as defined below. Definition 2.3. Let A=(a1,...,aN) be a sequence in the abelian group G. •An elementary contraction of Ais any sequence Aobtained by replacing a block Bin Aby its sum σ(B). That is, if B=(ai,...,aj) for some 1 ≤i≤j≤N, then A=(a1,...,ai−1, σ(B),aj+1,...,aN). •Acontraction of Ais any sequence obtained from Aby successive elementary contractions. For instance, let A=(1,2,3,4). Then (3,3,4), (6,4) and (3,7) are contractions of A, the first two ones being elementary. See also [1]. Definition 2.4. Let A=(a1,...,aN) be a sequence in G. A minor of Ais either a block Bin Aor a contraction Aof A. Proposition 2.5. Let G be an abelian group. Let A be a finite sequence in G. If B is a minor of A, then ˆ B⊆ˆ A. Proof. The stated inclusion clearly holds if Bis a block in A, since any block sum of Bis a block sum of A. If Bis an elementary contraction of Athen again, any block sum of Bis a block sum of A. Therefore, the same holds if Bis obtained from Aby successive elementary contractions. □ 2.3. The discrete derivative For subsets X,Yof a group (G,+), their sumset is X+Y= {x+y|x∈X,y∈Y}. Thus, Xis sumfree if and only if (X+X)∩X= ∅; equivalently, if and only (X−X)∩X= ∅, where −X= {−x|x∈X}. In this section, for X⊂Zfinite, we relate X−Xwith a subset of the form ˆ Afor a certain sequence Aclosely linked to X. This is done with a variant of the discrete derivative, associating to a subset X⊂Zits sequence of successive jumps. See also [1]. Definition 2.6. Let X⊂Zbe a finite subset. Let the elements of Xbe x0<x1<· · · <xr. The discrete derivative of Xis the sequence ∆X=(x1−x0,x2−x1,..., xr−xr−1) of successive jumps in X. The interesting point for our purposes here is that X−Xcan be read off from the block sums of ∆X. Proposition 2.7. Let X ⊂Zbe a nonempty finite subset, and let A =∆X. Then ˆ A=(X−X)∩N+. Proof. Denote by x0<x1<· · · <xrthe elements of X. Then (X−X)∩N+= {xt−xs|0≤s<t≤r}. Let A=∆X=(a1,...,ar), where ai=xi−xi−1for 1 ≤i≤r. For any indices 0 ≤s<t≤r, let B=(as+1,...,at) be the corresponding block in A. Then xt−xs=σ(B).(7) Indeed, σ(B)=∑t i=s+1ai=∑t i=s+1(xi−xi−1)=xt−xs. Hence xt−xs∈ˆ A. This concludes the proof of the proposition. □ 3 S. Eliahou and M.P. Revuelta Discrete Mathematics 344 (2021) 112332 The next proposition bounds the Schur degree of certain subsets ˆ Ain Z. We start with a lemma. Lemma 2.8. Let X be a sumfree subset of [1,N]for some N ∈N+. Let A =∆(X). Then ˆ A⊆ [1,N−1] \ X. Proof. Denote X= {x0,...,xn}with 1 ≤x0<x1<· · · <xn≤N. Then A=(a1,...,an) where ai=xi−xi−1for all 1≤i≤n. Let s∈ˆ A. Then s=ai+ · · · + aj=xj−xi−1 for some 1 ≤i≤j≤n. Therefore 1 ≤s≤N−1, and s/∈Xsince s+xi−1=xjand Xis sumfree. That is, s∈ [1,N−1] \ X, as desired. □ Proposition 2.9. Let N ≥1, and let X1⊔. . .⊔Xnbe a sumfree partition of [1,N]. Let Ai=∆(Xi)for all i. Then sdeg(ˆ Ai)≤n−1. Proof. Let i∈ [1,n]. It follows from Lemma 2.8 that ˆ Aiis contained in X1⊔. . . ⊔Xi−1⊔Xi+1⊔. . . ⊔Xn. This induces a partition of ˆ Aiinto at most n−1 sumfree parts. □ 3. Basic properties of the Schur degree In this section, we compute the Schur degree in a few examples after giving its first basic properties. Let us start with the monotonicity of the Schur degree with respect to set inclusion. Lemma 3.1. Let G be an abelian group. If X ⊆Y⊆G then sdeg(X)≤sdeg(Y). Proof. Let n=sdeg(Y). If n= ∞, we are done. Otherwise, Yadmits a partition into nsumfree parts, inducing a partition of Xinto at most nsumfree parts. □ Here is a useful consequence. Proposition 3.2. Let A be a finite sequence in the abelian group G. If B is a minor of A, then sdeg(ˆ B)≤sdeg(ˆ A). Proof. We have ˆ B⊆ˆ Aby Proposition 2.5. Now apply Lemma 3.1.□ Note also that if A′denotes the reverse sequence of A, then sdeg(ˆ A)=sdeg(ˆ A′). Indeed, Aand A′have identical block sums, i.e. ˆ A=ˆ A′. Our next proposition shows that the Schur degree is also monotone with respect to inverse images under group morphisms. We start with a lemma. Lemma 3.3. Let G1,G2be abelian groups and let f :G1→G2be a morphism. Let Y ⊆G2. If Y is sumfree then f −1(Y)also is. Proof. Assume that f−1(Y) is not sumfree. Then there exist x1,x2,x3∈f−1(Y) such that x1+x2−x3=0. Hence f(x1)+f(x2)−f(x3)=0, implying that Yis not sumfree either. □ Proposition 3.4. Let G1,G2be abelian groups and let f :G1→G2be a morphism. Let Y ⊆G2. Then sdeg(f−1(Y)) ≤sdeg(Y). Proof. Let n=sdeg(Y). Then there exist sumfree subsets Y1,...,Yn⊆Ysuch that Y=Y1⊔. . . ⊔Yn. Therefore f−1(Y)=f−1(Y1)⊔. . . ⊔f−1(Yn), and f−1(Yi) is sumfree for all iby Lemma 3.3. Hence sdeg(f−1(Y)) ≤n.□ 3.1. Examples As an illustration, we determine the Schur degree of a few selected subsets of Zor groups containing Z. In some cases, the results were obtained using specially written functions in Mathematica 10 [13]. Example 3.5. Let B= [1,2]∪[m,m+4]. We claim that sdeg(B)=3 for all m≥3. Indeed, let A=(1,1,m,1,1). Then ˆ A=B, and sdeg(ˆ A)≥3 by Corollary 4.2 in the next section. Equality is obvious here. 4 S. Eliahou and M.P. Revuelta Discrete Mathematics 344 (2021) 112332 Example 3.6. Let A=(2i)0≤i≤13. Then here also, sdeg(ˆ A)=3. But with one more term, i.e. for B=(2i)0≤i≤14, it is no longer the case as sdeg(ˆ B)=4. Example 3.7. This example is an application of Proposition 3.4. Let x,ybe positive integers, and let A=(x,y,...,x,y) be the 2-periodic sequence of length 14. Then sdeg(ˆ A\ {7x+7y})=3. Indeed, here are three sumfree classes covering that set: C1:x,y,2x+2y,5x+5y,7x+6y,6x+7y. C2:x+y,2x+y,x+2y,6x+5y,5x+6y,6x+6y. C3:3x+2y,2x+3y,3x+3y,4x+3y,3x+4y,4x+4y,5x+4y,4x+5y. Mapping x,yto 1 yields a sumfree 3-partition of [1,13]. In fact, the partition C1,C2,C3was constructed to do exactly that, using Proposition 3.4. Example 3.8. For each integer x≥8, one has sdeg([1,6]∪[x,x+13])=3. Indeed, this is shown by the following sumfree 3-partition of this set: C1:1,6,x,x+3,x+7,x+10. C2:2,5,x+1,x+2,x+8,x+9. C3:3,4,x+4,x+5,x+6,x+11,x+12,x+13. However, adjoining 7 to it, one has sdeg([1,7]∪[x,x+13])=4. Example 3.9. Let Gbe an abelian group containing Zand let x∈G\Z. Then sdeg({1,2}∪[x,x+3])=2, sdeg({1,2}∪[x,x+4])=3. Indeed, as easily seen, the only sumfree 2-coloring of {1,2} ∪ [x,x+3]is given by the two color classes {1,x,x+3}and {2,x+1,x+2}. Hence, it is impossible to add x+4 to either class while maintaining the sumfree property. Example 3.10. Let Gbe an abelian group containing Z. Let x∈G\Zbe such that {1,x}is Z-free, i.e. spans a free-abelian subgroup of rank 2 of G. Then sdeg([1,6] ∪ (x+N)) =3. Indeed, consider the 3-partition of Example 3.8 and extend it periodically as follows: C1:1,6,x,x+3,x+7,x+10,x+14,x+17, . . . C2:2,5,x+1,x+2,x+8,x+9,x+15,x+16, . . . C3:3,4,x+4,x+5,x+6,x+11,x+12,x+13,x+18,x+19,x+20, . . . One can also extend it towards the left. Thus in fact, sdeg([1,6] ∪ (x+Z)) =3. But here again, adjoining 7 to it, one has sdeg([1,7] ∪ (x+Z)) =4. 4. Comparison with Rn(3) Recall that, for n≥1, the Ramsey number Rn(3) denotes the smallest Nsuch that, for any n-coloring of the edges of the complete graph KN, there is a monochromatic triangle. There is a well known relationship between the Schur and the Ramsey numbers, namely S(n)≤Rn(3) −2.(8) Using the Schur degree of [1,N], this may be expressed as follows: N≥Rn(3) −1H⇒ sdeg([1,N])≥n+1. Theorem 4.1 below extends this relationship to the Schur degree of ˆ Afor any finite sequence Ain an abelian group. Theorem 4.1. Let G be an abelian group. Let A be a finite sequence in G. If |A| ≥ Rn(3) −1then sdeg(ˆ A)≥n+1. 5 S. Eliahou and M.P. Revuelta Discrete Mathematics 344 (2021) 112332 Proof. Let N= |A| ≥ Rn(3) −1. Denote b(i,j)=xi+ · · · + xj−1for all 1 ≤i<j≤N+1. Then ˆ A= {b(i,j)|1≤i<j≤N+1}. Let χ:ˆ A→ [1,n]be an arbitrary n-coloring of ˆ A. Consider the complete graph KN+1=(V,E) on the vertex set V= [1,N+1]. Then χinduces an n-coloring χ′:E→ [1,n]on Edefined by χ′({i,j})=χ(b(i,j)) for all 1 ≤i<j≤N+1. Since N+1≥Rn(3), there is a monochromatic triangle under χ′in KN+1, say with vertices i,j,h for some 1 ≤i<j<h≤N+1. This yields, under χ, the monochromatic subset {b(i,j),b(j,h),b(i,h)} ⊂ ˆ A. Since b(i,j)+b(j,h)=b(i,h), the corresponding color class in ˆ Ais not sumfree. Since χwas an arbitrary n-coloring of ˆ A, we conclude that sdeg(ˆ A)≥n+1. □ In particular, for n=2, 3 and 4, one has the following consequences. Corollary 4.2. Let A be a sequence in an abelian group G. If |A| ≥ 5, then sdeg(ˆ A)≥3. If |A| ≥ 16, then sdeg(ˆ A)≥4. If |A| ≥ 61, then sdeg(ˆ A)≥5. Proof. Follows from Theorem 4.1 and the well-known values R2(3) =6, R3(3) =17 and current upper bound R4(3) ≤62. □ The converse of Theorem 4.1 does not hold in general. For instance, for n=3 and A=(1,...,1) of length 14 in Z, by (6) we have sdeg(ˆ A)≥4 since ˆ A= [1,14]and S(3) =13, yet |A| ≤ R3(3) −2=15. However, here is a partial converse showing that Theorem 4.1 is best possible. First observe that if |A| = N, then |ˆ A| ≤ 1+2+ · · · + N=(N+1 2). The case of equality, where all block sums in Aare pairwise distinct, is of interest. It occurs for instance if Ais Z-free, i.e. generates a subgroup isomorphic to ZN. Theorem 4.3. Let A be a finite sequence in an abelian group G. If |A| ≤ Rn(3) −2and A is Z-free, then sdeg(ˆ A)≤n. Proof. Denote A= {x1,...,xN}. Reusing the notation introduced in the proof of Theorem 4.1, we have ˆ A= {b(i,j)|1≤i<j≤N+1}. Again, let KN+1=(V,E) be the complete graph on the vertex set V= [1,N+1]. Consider the map f:E→ˆ Adefined by f({i,j})=b(i,j) (9) for all 1 ≤i<j≤N+1. Since |E|=|ˆ A|and the b(i,j) are pairwise distinct by assumption, the map fis a bijection. Since N+1≤Rn(3) −1, there is an n-coloring χ:E→ [1,n]without any monochromatic triangle. Consider the composed map χ◦f−1:ˆ A−→ [1,n]. We claim that under this n-coloring of ˆ A, every color class is sumfree. Indeed, let u1,u2,u3be any triple in ˆ Asatisfying u1+u2=u3. We claim that it cannot be monochromatic under χ◦f−1. We have u1=b(i1,j1), u2=b(i2,j2), u3=b(i3,j3) for some indices i1<j1,i2<j2,i3<j3in [1,N+1]. The relation u1+u2=u3then becomes (xi1+ · · · + xj1−1)+(xi2+ · · · + xj2−1)=(xi3+ · · · + xj3−1). We may freely assume i1≤i2. Since the sequence x1,...,xNis Z-free by hypothesis, the above equality is only possible if i1=i3,j1=i2and j2=j3. That is, if the three edges {i1,j1},{i2,j2},{i3,j3}form a triangle in KN+1. Since that triangle is not monochromatic under χ, the triple u1,u2,u3=u1+u2in ˆ Ais not monochromatic under χ◦f−1either, since f−1(uk)= {ik,jk}for k=1,2,3 by (9). Hence sdeg(ˆ A)≤n, as claimed. □ Remark 4.4. The hypothesis that Abe Z-free is not strictly needed in Theorem 4.3. For instance, let A=(1,3,32,...,3N−1). Even though Ais not Z-free, it is still true that if N≤Rn(3) −2 then sdeg(ˆ A)≤n. This derives from the above proof and the fact that the only triples u, v, u+vin ˆ Aare those of the form b(i,j),b(j,h),b(i,h). 6 S. Eliahou and M.P. Revuelta Discrete Mathematics 344 (2021) 112332 5. A recursive upper bound on S(n)? The Ramsey numbers admit well-known recursive upper bounds, including Rn(3) ≤n(Rn−1(3) −1) +2 (10) [8, Theorem 6, p. 6]. To the best of our knowledge, no recursive upper bounds are known yet for the Schur numbers. We propose here a conjecture which, if true, would fill this gap. Let us start with an upper bound on S(n) involving the number L(n) defined below. Definition 5.1. Let n≥2. We define L(n) to be the smallest positive integer with the following property: for every sequence Ain N+of length |A| = L(n) and average µ(A)≤n, one has sdeg(ˆ A)≥n. Example 5.2. Let n=2. Then L(2) =2. Indeed, up to symmetry, the only sequences Ato consider are (1,1), (1,2), (1,3), (2,2). This yields ˆ A= {1,2},{1,2,3},{1,3,4},{2,4}, respectively. As none is sumfree, we have sdeg(ˆ A)≥2 in all cases, as required. Let us now establish the existence of L(n) in full generality. Proposition 5.3. For all n ≥2, the number L(n)exists and satisfies S(n−1) +1≤L(n)≤Rn−1(3) −1.(11) Proof. If Ais any sequence in N+of length |A| = Rn−1(3) −1, then irrespective of its average µ(A), we have sdeg(ˆ A)≥n by Theorem 4.1, as desired. Thus L(n) exists and is bounded above by Rn−1(3) −1. On the other hand, let A=(1,...,1) of length L(n) and average µ(A)=1. Then ˆ A= [1,L(n)], whence sdeg([1,L(n)])≥nby hypothesis. Hence L(n)≥S(n−1)+1, by definition of S(n−1). □ Here is our upper bound on S(n) involving L(n). Theorem 5.4. We have S(n)≤nL(n)for all n ≥2. Proof. We claim that [1,nL(n)+1]has Schur degree at least n+1. This will imply nL(n)+1≥S(n)+1, the desired conclusion. Assume for a contradiction that nL(n)+1≤S(n). Let then [1,nL(n)+1] = X1⊔. . . ⊔Xn(12) be a sumfree partition. By the pigeonhole principle, one of the Xi’s has cardinality at least L(n)+1, say |X1| ≥ L(n)+1. Let A=∆(X1). Then |A| ≥ L(n), and sdeg(ˆ A)≤n−1byProposition 2.9. Let Bbe a block of Aof length |B| = L(n). Since B is a minor of A,Proposition 2.5 implies sdeg(ˆ B)≤sdeg(ˆ A)≤n−1.(13) Let s=min(X1), t=max(X1). Then σ(A)=t−sby (7), and t−s≤nL(n) since X1⊆ [1,nL(n)+1]by (12). Hence σ(B)≤nL(n) and so µ(B)=σ(B)/L(n)≤n. Since |B| = L(n), the defining property of L(n) implies sdeg(ˆ B)≥n, contradicting (13). This concludes the proof of the theorem. □ Remark 5.5. Proposition 5.3 and Theorem 5.4 imply the upper bound S(n)≤n(Rn−1(3) −1) for all n≥2. However, this also follows by combining (8) and (10), namely S(n)≤Rn(3)−2 and Rn(3) ≤n(Rn−1(3)−1)+2. 5.1. Conjectures Given n≥2, what is the exact value of L(n)? It follows from Proposition 5.3 that if S(n−1) +1=Rn−1(3) −1then L(n)=S(n−1) +1.(14) This occurs for n=2 and 3, since by (1) and (3), we have (S(1),R1(3)) =(1,3) and (S(2),R2(3)) =(4,6). Thus L(2) =2 as already seen, and L(3) =5. As for n=4, we have (S(3),R3(3)) =(13,17). Proposition 5.3 then implies 14 ≤L(4) ≤16.We conjecture that L(4) =14 and, more generally, that the lower bound on L(n) in (11) is optimal. 7 S. Eliahou and M.P. Revuelta Discrete Mathematics 344 (2021) 112332 Table 1 S(n)≤n(S(n−1) +1) for 2 ≤n≤5. n S(n)n(S(n−1) +1) 1 1 2 4 4 3 13 15 4 44 56 5 160 225 Conjecture 5.6. Let n ≥2. Then L(n)=S(n−1) +1. That is, every sequence A in N+of length |A| = S(n−1) +1and average µ(A)≤n satisfies sdeg(ˆ A)≥n. As shown below, this has very interesting consequences for the Schur numbers themselves. We have seen above that Conjecture 5.6 holds for n=2 and 3. Does it hold for n=4? That is, is it true that for any sequence Ain N+of length 14 and average µ(A)≤4, one has sdeg(ˆ A)≥4? We do not know yet. In any case, some hypothesis bounding µ(A) from above cannot be completely dispensed of. For instance, consider the sequence A=(23,375,23,209,209,60,60,60,23,1,60,261,209,23) of length 14. Then |ˆ A| = 83, and sdeg(ˆ A)=3 as can be verified. But this does not contradict Conjecture 5.6 for n=4, since µ(A)=114 here. Such exotic examples in length 14 are hard to come by. This one was found with a semi-random search by computer. See also Example 3.6 with the powers of 2, also of length 14 but with a still higher average. Here is a worthwhile consequence of Conjecture 5.6 for the Schur numbers, potentially the first known recursive upper bound for them. Conjecture 5.7. S(n)≤n(S(n−1) +1) for all n ≥2. This directly follows from Theorem 5.4 and Conjecture 5.6.Table 1 shows that Conjecture 5.7 actually holds for 2≤n≤5. 5.2. Comparisons Let us now compare this conjectural upper bound on S(n) with the general currently known ones given by (8) and (10), namely S(n)≤Rn(3) −2,Rn(3) ≤n(Rn−1(3) −1) +2.(15) The currently known bounds on R4(3) are 51 ≤R4(3) ≤62, established in [3] and [6], respectively. Starting with R4(3) ≤62, the bounds (15) yield S(5) ≤R5(3) −2≤305,S(6) ≤R6(3) −2≤1836. •For n=4, the equality S(4) =44 was established by computer [2]. But, as far as theory is concerned, nothing better than S(4) ≤R4(3) −2≤60 is currently known. A proof of Conjecture 5.6 for n=4 would yield S(4) ≤56, still far away from the true value 44, yet a little closer to it. •For n=5, the bound S(5) ≥160 was first established in [5], with equality later conjectured to hold in [7]. Indeed, the exact value S(5) =160 has recently been established by massive computer calculations with a certified SAT solver [9]. A proof of Conjecture 5.6 for n=5, namely that every sequence Ain N+such that |A| = 45 and µ(A)≤5 satisfies sdeg(ˆ A)≥5, would imply S(5) ≤225. Here again, it would still be far away from the true value, yet it would provide a marked improvement over the currently best known theoretical upper bound S(5) ≤305. •For n=6, on the one hand we have S(6) ≥536 by [7], while at the time of writing, the best known upper bound is again the one given above, namely S(6) ≤R6(3) −2≤1836. By sharp contrast, using the true value S(5) =160, Conjecture 5.7 implies the following substantial improvement. Conjecture 5.8. S(6) ≤966. •As for n=7, Conjectures 5.7 and 5.8 yield the conjectural upper bound S(7) ≤6769, to be compared with the known ones given by (15), namely S(7) ≤R7(3) −2≤12859. For a lower bound, the best we currently have is S(7) ≥1680, by [7] again. 8 S. Eliahou and M.P. Revuelta Discrete Mathematics 344 (2021) 112332 Declaration of competing interest The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper. References [1] S.D. Adhikari, L. Boza, S. Eliahou, M.P. Revuelta, M.I. Sanz, Equation-regular sets and the Fox–Kleitman conjecture, Discrete Math. 341 (2018) 287–298. [2] L.D. Baumert, Sum-free sets, J.P.L. Research Summary No. 36-10 1 (1961) 16–18. [3] F.R.K. Chung, On the Ramsey numbers N(33 . . . 32), Discrete Math. 5 (1973) 317–321. [4] S. Eliahou, An adaptive upper bound on the Ramsey numbers R(3,...,3), Integers 20 (2020) 7, Paper No. A54. [5] G. Exoo, A lower bound for Schur numbers and multicolor Ramsey numbers of K3, Electron. J. Combin. 1 (1994) 3, Research Paper 8, approx. (electronic). [6] S.E. Fettes, R.L. Kramer, S.P. Radziszowski, An upper bound of 62 on the classical Ramsey number R(3,3,3,3), Ars Combin. 72 (2004) 41–63. [7] H. Fredricksen, M.M. Sweet, Symmetric sum-free partitions and lower bounds for Schur numbers, Electron. J. Combin. 7 (2000) 9, Research Paper 32, (electronic). [8] R.E. Greenwood, A.M. Gleason, Combinatorial relations and chromatic graphs, Canad. J. Math 7 (1955) 1–7. [9] M.J.H. Heule, Schur number five, in: Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18), https://arxiv.org/ abs/1711.08076. [10] S.P. Radziszowski, Small Ramsey numbers, Electron. J. Combin. 1 (1994) 104, Dynamic Survey DS1, Revision #16 (2021), (Electronic). [11] I. Schur, Uber die Kongruenz xm+ym≡zm(mod p), Jahresber. Dtsch. Math.-Ver. 25 (1916) 114–117. [12] A. Soifer, The mathematical coloring book, in: Mathematics of Coloring and the Colorful Life of Its Creators, Springer, New York, ISBN: 978-0-387-74640-1, 2009. [13] Wolfram Research Inc., Mathematica, Version 10, Champaign, IL, 2014. [14] X. Xu, S.P. Radziszowski, On some open questions for Ramsey and Folkman numbers, in: Graph Theory–Favorite Conjectures and Open Problems, in: Probl. Books in Math., vol. 1, Springer, Cham, 2016, pp. 43–62. [15] X. Xu, Z. Xie, Z. Chen, Upper bounds for Ramsey numbers Rn(3) and Schur numbers, Math. Econ. 19 (2002) 81–84. 9