Equation-regular sets and the Fox–Kleitman conjecture

Equation-regular sets and the Fox–Kleitman conjecture S.D. Adhikari a, L. Boza b, S. Eliahou c,d,*, M.P. Revuelta b, M.I. Sanz b a Harish-Chandra Research Institute, Chhatnag Road, Jhunsi, Allahabad-211 019, India b Departamento de Matemática Aplicada I, Universidad de Sevilla, Avenida de la Reina Mercedes 4, C.P. 41012 Sevilla, Spain c Univ. Littoral Côte d’Opale, EA 2597 - LMPA - Laboratoire de Mathématiques Pures et Appliquées Joseph Liouville, F-62228 Calais, France d CNRS, FR 2956, France Keywords: Partition regularity Degree of regularity Monochromatic solution Discrete derivative a b s t r a c t Given k≥1, the Fox–Kleitman conjecture from 2006 states that there exists a nonzero integer bsuch that the 2k-variable linear Diophantine equation k ∑ i=1 (xi−yi)=b is (2k−1)-regular. This is best possible, since Fox and Kleitman showed that for all b≥1, this equation is not 2k-regular. While the conjecture has recently been settled for all k≥2, here we focus on the case k=3 and determine the degree of regularity of the corresponding equation for all b≥1. In particular, this independently confirms the conjecture for k=3. We also briefly discuss the case k=4. 1. Introduction A Diophantine equation Lis said to be n-regular, for some positive integer n, if for every n-coloring of N+= {1,2, . . .}, there is a monochromatic solution to L. Further, Lis said to be regular if it is n-regular for all n≥1. Of course, (n+1)-regularity implies n-regularity. The degree of regularity of L, denoted as dor(L), is defined to be infinite if Lis regular, or else, it is the largest nsuch that Lis n-regular [4]. Determining the degree of regularity of a given Diophantine equation is difficult in general, even if it is linear. In this paper, we focus on a particular linear equation proposed by Fox and Kleitman in [3]. Given positive integers k,b, we shall denote by Lk(b) the 2k-variable Diophantine equation k ∑ i=1 (xi−yi)=b. Fox and Kleitman [3] showed that this equation is never 2k-regular, i.e., that dor(Lk(b)) ≤2k−1 (1) for all b∈N+. Moreover, they conjectured that this upper bound is best possible. * Corresponding author at: Univ. Littoral Côte d’Opale, EA 2597-LMPA—Laboratoire de Mathématiques Pures et Appliquées Joseph Liouville, F-62228 Calais, France. E-mail addresses: [email protected] (S.D. Adhikari), [email protected] (L. Boza), [email protected] (S. Eliahou), [email protected] (M.P. Revuelta), i Conjecture 1.1 ([3]).Let k ≥1. Then there exists an integer b ≥1, depending on k, such that dor(Lk(b)) =2k−1. The case k=2 of the conjecture was recently settled in [1], where it is shown that dor(L2(b)) =3 for all b≡0 mod 6. More generally, the authors determined dor(L2(b)) for all b≥1, as follows: Theorem 1.2 ([1]).For all positive integers b, we have dor(L2(b)) ={1if b ≡1 mod 2, 2if b ≡2,4 mod 6, 3if b ≡0 mod 6. A reduced 3-variable version of the 4-variable equation L2(b) had already been studied in [2]. Indeed, they considered the equation x3−x2=x2−x1+b, which can be obtained from the equation (x1−y1)+(x2−y2)=bby setting y1=y2and renaming the resulting three variables x1,x2,y2as x1,x3,x2, respectively. Finally, as pointed out by a referee, the conjecture has recently been fully settled, using sophisticated methods of additive combinatorics [5]. 1.1. The functions νand f We now introduce two functions ν, f:N+→N+which are somehow related to dor(Lk(b)). In particular, they will provide nice reformulations of the above formulas for dor(L2(b)). For n∈N+, define ν(n)=the smallest non-divisor of n, i.e. the least integer m≥2 such that mdoes not divide n. For instance, we have ν(n)=2 if nis odd, and ν((p−1)!)=pif p is prime. Still for n∈N+, define f(n)=the largest rsuch that r!divides n. Thus for instance, we have f(n)=1 if nis odd, and f(n)=2 if and only if nis even and not divisible by 6, i.e. n ≡2,4 mod 6. As is easily seen, Theorem 1.2 is equivalent to the formulas dor(L2(b)) =min(3,f(b)) =min(3, ν(b)−1) (2) for all b≥1. Our purpose in this paper is to similarly determine dor(L3(b)) for all b≥1. Indeed, with the upper bound (1) in mind, we shall establish the equality dor(L3(b)) =min(5,f(b)) (3) for all b≥1. This implies dor(L3(5!)) =5, thereby verifying the Fox–Kleitman conjecture for k=3. Unfortunately, in contrast with (2), there is no equality in general between dor(L3(b)) and min(5, ν(b)−1). For b=60 for instance, we shall see that dor(L3(60)) =3, whereas min(5, ν(60) −1) =5. However, the inequality dor(Lk(b)) ≤min(2k−1, ν(b)−1) (4) always holds, as will be shown further down. Moreover, for fixed b≥1, we shall prove that dor(Lk(b)) =min(2k−1, ν(b)−1) =ν(b)−1 (5) for all sufficiently large k, in fact for all k≥b. As for the function f, can one expect, based on (2),(3) and (4), an equality or at least an inequality between dor(Lk(b)) and min(2k−1,f(b)) for k≥4? Here again, the answer turns out to be negative. Indeed, for k=4, we shall establish the following values. bdor(L4(b)) min(7,f(b)) 12 4 3 720 =6!5 6 This indicates that the behavior of dor(Lk(b)) as a function of b, for fixed k≥4, is much more tricky than what formulas (2) and (3) for k≤3 might lead one to expect. In the same vein, we shall show that if bis a positive integer satisfying the Fox–Kleitman conjecture for k=4, i.e. such that dor(L4(b)) =7, then necessarily bmust be divisible by 22·3·5·7·11 ·13 ·19 =1141140. At the time of writing, we do not know whether dor(L4(b)) reaches 7 for b=1141140. 1.2. Contents In Section 2, we provide basic lemmas regarding the behavior of dor(Lk(b)). In Section 3we introduce L-regular and L-singular sets with respect to a Diophantine equation L, and we provide tools to determine such sets for the equation Lk(b). In Section 4we give a new proof of the above formula for dor(L2(b)). In Section 5we determine dor(L3(b)) for all b≥1, with some computer assistance in the specific case b=120, and we independently verify the Fox–Kleitman conjecture for k=3. In Section 6we briefly discuss the case k=4. Finally, in Section 7we determine dor(Lk(b)) whenever k≥b. 2. Basic lemmas We shall use the following notation from additive combinatorics. For subsets A,Bof an abelian group G, we write A+B= {a+b|a∈A,b∈B},−A= {−a|a∈A}and kA =A+ · · · + A, the k-fold sum of Awith itself. Thus, given a subset X⊆Z, we see that equation Lk(b)has a solution with all entries in X if and only if b∈k(X−X). (See also Remark 3.5.) This will be used throughout the paper. For instance, using this formulation, here is a brief explanation for Fox and Kleitman’s upper bound (1) stating that Lk(b) is never 2k-regular. For integers a≤b, we shall denote by [a,b] the integer interval consisting of all n∈Zsuch that a≤n≤b. Lemma 2.1 ([3]).For all integers k,b≥1, one has dor(Lk(b)) ≤2k−1. Proof. If bis not a multiple of k, then Lk(b) is not even k-regular by the independent Lemma 2.4 below. If b=kr with r∈N+, we first 2k-color [1,2b]as follows. The color class C1is given by C1= [1,r].For 2 ≤i≤2k, the color class Ciis the translate of C1by (i−1)r, namely Ci=C1+(i−1)r.We then extend this coloring to the whole of N+by 2b-periodicity, namely where the color classes are Xi=Ci+2bZ=Ci+2krZfor all 1 ≤i≤2k. We claim that b∈ k(Xi−Xi) for all 1 ≤i≤2k. It suffices to check it for i=1, since Xi−Xiis independent of i. Now X1−X1= [−(r−1),r−1] + 2krZ, whence k(X1−X1)= [−k(r−1),k(r−1)] + 2krZ. Therefore b∈ k(X1−X1), as claimed. It follows that Lk(b) is not 2k-regular. □ We now show that dor(Lk(b)) is monotone with respect to k. Lemma 2.2. Let b,k1,k2be positive integers such that k1≤k2. Then dor(Lk1(b)) ≤dor(Lk2(b)). Proof. Let n=dor(Lk1(b)). We claim that Lk2(b) is n-regular. Let cbe an n-coloring of N+. Then there is a c-monochromatic subset X⊆N+such that b∈k1(X−X). Now k1(X−X)⊆k2(X−X) since 0 ∈X−Xand k1≤k2. Hence b∈k2(X−X). Therefore Lk2(b) is n-regular, as claimed. □ Next, for fixed k, here are two basic lemmas about the behavior of dor(Lk(b)) as a function of b. The first one shows that this function is monotone with respect to multiplication. Lemma 2.3. Let b1,b2,k be positive integers such that b1divides b2. Then dor(Lk(b1)) ≤dor(Lk(b2)). Proof. By hypothesis, there is an integer t∈N+such that b2=tb1. Let r=dor(Lk(b1)). We now show that Lk(b2) is r-regular. Let cbe a r-coloring of N+. It suffices to establish the existence of a c-monochromatic solution of Lk(b2). Let c′be the new r-coloring of N+defined by c′(n)=c(tn) for all n≥1. Since Lk(b1) is r-regular, there is a c′-monochromatic solution a1, . . . , ak,d1, . . . , dkin N+of Lk(b1), i.e. satisfying k ∑ i=1 (ai−di)=b1. Multiplying this equality by t, we get k ∑ i=1 (tai−tdi)=tb1=b2.(6) Since the ai’s, di’s are c′-monochromatic, it follows by construction that the tai’s, tdi’s are c-monochromatic. Moreover, by (6), they constitute a solution of Lk(b2). Hence r≤dor(Lk(b2)), as desired. □ On the other hand, here is an obvious upper bound on dor(Lk(b)). Lemma 2.4. Let b,m be positive integers such that m does not divide b. Then dor(Lk(b)) ≤m−1. Proof. It suffices to find an m-coloring of N+for which there is no monochromatic solution of Lk(b). Consider the coloring πmgiven by the classes mod m. That is, the subset Xi⊆N+of elements of color i, for 1 ≤i≤m, is defined as Xi=i+m·N. Then Xi−Xi⊆m·Z. Since b≡ 0 mod m, it follows that b∈ k(Xi−Xi). Hence equation Lk(b) admits no πm-monochromatic solution, as desired. □ Proposition 2.5. Let b ≥ 1. Then dor(Lk(b)) ≤ min(2k − 1, ν(b) − 1). Proof. We have dor(Lk(b)) ≤ 2k − 1 by Lemma 2.1, and dor(Lk(b)) ≤ ν(b) − 1 by Lemma 2.4 since ν(b) does not divide b. □ 3. Equation-regular sets We now introduce a notion of regularity for sets which is closely linked to the usual notion of partition-regularity for Diophantine equations. This will turn out to be useful to determine, in some cases, the degree of regularity of the Fox– Kleitman equation Lk(b). Definition 3.1. Given a Diophantine equation L, or a system of such equations, we say that a set X⊂N+is regular with respect to L, or more shortly L-regular, if it contains a solution of L. We say that Xis singular if Xis not regular. Here is an easy remark linking these notions of regularity. Remark 3.2. Let Lbe a Diophantine equation. Then Lis n-regular if and only if every partition of N+into nparts admits an L-regular part. The notion of equation-regular sets moves the focus away from partitions and more towards those properties of a set which will force it to contain a solution of a given Diophantine system L. For instance, given k,b≥1, we shall see that any sufficiently dense subset of a sufficiently large integer interval is Lk(b)-regular. That is, for sets, density alone implies regularity. This will allow us to determine the degree of regularity of Lk(b) in some instances, and in particular to independently verify the Fox–Kleitman conjecture for k=3, as well as to provide a shorter proof of it for k=2. 3.1. Block sums We first need some basic notions to be used throughout the paper. Let A=(a1,a2, . . . , ar) be a sequence of positive integers. •Ablock in Ais any subsequence A′of consecutive terms in A,i.e. of the form A′=(ai,ai+1, . . . , aj) for some indices i,jsuch that 1 ≤i≤j≤r. •The empty subsequence of length 0 is also considered to be a block of A. •We denote by σ(A)=∑r i=1aithe sum of the elements of A, and by µ(A) the average of A,i.e. µ(A)=σ(A)/r. •Finally, we denote by bs(A) the set of signed block sums in A,i.e. bs(A)= {±σ(A′)|A′is a block in A}. For instance, if A=(1,10,4), then bs(A)∩N= {0,1,4,10,11,14,15}. Note that 5 is not a block sum in A. Note that if A′is a block in A, then bs(A′)⊆bs(A). We will further discuss this property later on. Observe also that A⊆bs(A). 3.2. The discrete derivative We shall need a variant of the discrete derivative, associating to a subset X⊂Zof cardinality r+1 a sequence of length r, as follows: Definition 3.3. Let X⊂Zbe a finite subset of cardinality r+1. Let the elements of Xbe x0<x1<· · · <xr. We associate to Xthe sequence ∆X=(x1−x0,x2−x1, . . . , xr−xr−1) of length r, and call ∆Xthe discrete derivative of X. Of interest to us here is the fact that X−Xcan be read off from the signed block sums of ∆X. Lemma 3.4. Let X ⊂Zbe a nonempty finite subset. Then X−X=bs(∆X). Proof. Let the elements of Xbe x0<x1<· · · <xr. Then X−X= {xt−xs|0≤s,t≤r}. Let now A=∆X=(a1, . . . , ar), where ai=xi−xi−1for 1 ≤i≤r. Then for indices s,tsuch that 0 ≤s≤t≤r, we have xt−xs= t ∑ i=s+1 (xi−xi−1)= t ∑ i=s+1 ai. Thus xt−xs=σ(A′), where A′is the block (as+1, . . . , at) of A. Hence xt−xs∈bs(A)∩Nfor s≤t, and xt−xs∈ −(bs(A)∩N) if s≥t. The claim follows. □ 3.3. Lk(b)-regular sets We now turn to equation Lk(b) for given integers k,b≥1. We first recall an informal observation made at the beginning of Section 2. Remark 3.5. Let Ldenote equation Lk(b) for some integers k,b≥1. Let X⊂N+. Then Xis regular with respect to Lif and only if b∈k(X−X). Indeed, we have b∈k(X−X) if and only if there exist x1, . . . , xk,y1, . . . , yk∈Xsuch that b=∑k i=1(xi−yi),which therefore constitute a solution of Lin X. This allows us to express the Lk(b)-regularity of a set Xin terms of the discrete derivative ∆X. The resulting lemma will be tacitly used in the sequel. Lemma 3.6. Let X ⊂Zbe a nonempty finite subset. Then X is regular with respect to equation Lk(b)if and only if b ∈kbs(∆X). Proof. Directly follows from the equality X−X=bs(∆X) of Lemma 3.4 together with Remark 3.5.□ 3.4. Forbidden sequences and subsets In the sequel, we will try to construct finite subsets X⊂Zwhich are singular with respect to Lk(b), with the purpose of showing that it is hard to achieve if Xis sufficiently dense in a suitable integer interval. Moreover, working with ∆Xrather than Xis more convenient. This justifies the following terminology. Definition 3.7. Let Ldenote equation Lk(b) for some integers k,b≥1. Let A=(a1, . . . , ar) be a sequence of positive integers. We say that Ais admissible (with respect to L) if b∈ kbs(A). We say that Ais forbidden if it is not admissible, i.e. if b∈kbs(A). Remark 3.8. With respect to equation Lk(b), a subset X⊂Nis regular if and only if its discrete derivative A =∆X is forbidden. Equivalently, Xis singular if and only if ∆Xis admissible. The following result is the heart of our approach to evaluate the degree of regularity of the Fox–Kleitman equation Lk(b). Recall that µ(A) denotes the average of the sequence A=(a1, . . . , ar). Proposition 3.9. Let L denote equation Lk(b)for some integers k,b≥1. Let d ≥1. Assume that there exists an integer N ≥1 such that all positive integer sequences A of length N and average µ(A)≤d are forbidden with respect to L. Then L is d-regular. Proof. Consider an arbitrary d-coloring of the integer interval [1,dN +1]. By the pigeonhole principle, there exists a monochromatic subset X⊂ [1,dN +1]of cardinality |X| = N+1. Let A=∆X. Then Ais of length N. Let x0=min X, xN=max X. Then xN−x0=σ(A). Since X⊂ [1,dN +1], it follows that xN−x0≤dN, whence µ(A)≤d. It follows from the hypothesis that Ais forbidden with respect to L, and hence that b∈kbs(A). Therefore b∈k(X−X), i.e. X is L-regular. Since the d-coloring was arbitrary, it follows that Lis d-regular, as claimed. □ We end this section by looking at ways to construct new forbidden sequences from a given one. Definition 3.10. Let A=(a1, . . . , ar) be a sequence of positive integers. •An elementary contraction of Ais any sequence Aobtained by replacing a block A′in Aby its sum σ(A′). That is, if A′=(ai, . . . , aj) for some 1 ≤i≤j≤r, then A=(a1, . . . , ai−1, σ(A′),aj+1, . . . , ar). •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. Definition 3.11. Let A=(a1,...,ar) be a sequence of positive integers. A minor of Ais either a block A′in Aor a contraction Aof A. We now show that if a sequence Ahas a forbidden minor, then Aitself is forbidden. Proposition 3.12. Let L denote equation Lk(b)for some integers k,b≥1. Let A be a finite sequence of positive integers, and let B be a minor of A. If B is forbidden with respect to L, then A also is. Proof. We have b∈kbs(B) by hypothesis. Therefore, to prove that Ais forbidden, it suffices to show that bs(B)⊆bs(A). This inclusion clearly holds if Bis a block in A, since any block sum in Bis a block sum in A. If now Bis an elementary contraction of A, then again, any block sum in Bis a block sum in A. Therefore, the same holds if Bis obtained from Aby successive elementary contractions. □ Here is another condition forcing a sequence Ato be forbidden. Proposition 3.13. Let L denote equation Lk(b)for some integers k,b≥1, and let A be a finite sequence of positive integers. If bs(A)contains a subset Z such that b ∈k(Z∪ −Z), then A is forbidden with respect to L. Proof. If Z⊆bs(A), then (Z∪ −Z)⊆bs(A) since bs(A)= −bs(A). Therefore k(Z∪ −Z)⊆kbs(A). The hypothesis on bthen implies b∈kbs(A), and we are done. □ Observe finally that if A=(a1,...,ar) is forbidden with respect to Lk(b), then so is the reverse sequence A′=(ar,...,a1). Indeed, Aand A′have identical block sums, i.e. bs(A)=bs(A′). Hence, when looking for admissible or forbidden sequences, we only need do it up to reversal. 4. The case k=2 As an illustration of the method, we provide here a proof of the Fox–Kleitman conjecture for k=2, and more generally of Theorem 1.2, which is shorter than the ones given in [1,5]. The key tool is Proposition 3.9. Proposition 4.1. Let L denote equation L2(2). Every positive integer sequence A of length 1 and average µ(A)≤2is forbidden with respect to L. Proof. The only sequences to consider are A=(a) with a∈ {1,2}. Then bs(A)= {0,a,−a}and 2 bs(A)= {0,a,2a,−a,−2a}. Hence 2 ∈2 bs(A) in either case, showing that Ais forbidden. □ Corollary 4.2. We have dor(L2(2)) =2. Proof. Propositions 3.9 and 4.1 imply that L2(2) is 2-regular, i.e. dor(L2(2)) ≥2. Since ν(2) =3, the reverse inequality follows from the bound dor(Lk(b)) ≤min(2k−1, ν(b)−1) of Proposition 2.5.□ Proposition 4.3. Let L denote equation L2(6). Every positive integer sequence A of length 6 and average µ(A)≤3is forbidden with respect to L2(6). Proof. In length 1, the sequences (3) and (6) are clearly forbidden. Therefore, by Proposition 3.12, any sequence admitting either (3) or (6) as a minor is forbidden. Let us now look at forbidden minors of length 2. •The sequences A=(1,a) with 2 ≤a≤7 are forbidden. This is clear if a∈ {2,3,6}by the above. If 4 ≤a≤5, then 1,5∈bs(A), hence 6 ∈2 bs(A). Finally, if a=7, then 6 = −1+7∈2 bs(A). •The sequences A=(2,a) with a∈ {2,3,4,6,8}are forbidden. This is clear if a∈ {3,6}by the above. If a=2 or 4, then 2,4∈bs(A), hence 6 ∈2 bs(A). Finally, if a=8, then 6 = −2+8∈bs(A). Claim. If A=(a1,a2,a3) is admissible and if µ(A)≤3, then A=(2,5,2). Indeed, we have σ(A)≤9 by hypothesis. Let x=min A. Then x≤3. As Ais admissible, it cannot contain 3 for otherwise (3) would be a forbidden minor. Hence x≤2. Assume x=1. Since (1,1,1) is forbidden, because (3) is a minor of it, there can be at most two 1’s in A. Let a∈Awith a= 1. We may assume that (1,a) or (a,1) is a block in A. As Ais admissible, we must have a≥8 by the length 2 case above, whence σ(A)≥10. But this is impossible since σ(A)≤9 by assumption. Hence x=2. Let (2,a) or (a,2) be a block in A. Since Ais admissible, then a≥5 by the length 2 case, whence σ(A)≥2+2+a≥9. But since σ(A)≤9, we must have a=5 and A=(2,5,2). This settles the claim. Claim. Let A=(a1, . . . , a6) such that µ(A)≤3. Then Ais forbidden. Indeed, assume for a contradiction that Ais admissible. Then every block in Ais admissible, and in particular so are its two halves A1=(a1,a2,a3), A2=(a4,a5,a6). Since µ(A)≤3, we have µ(Ai)≤3 for some i∈ {1,2}, say µ(A1)≤3 up to renumbering. But since A1is admissible, we must have A1=(2,5,2) by the above claim, and in particular µ(A1)=3. Therefore µ(A2)≤3 as well, whence A2=A1by the same argument as for A1. Hence A=(2,5,2,2,5,2). But this sequence cannot be admissible, since it contains the forbidden minor (2,2). This contradiction establishes the claim, and the proof is complete. □ Corollary 4.4. We have dor(L2(6)) =3. Proof. Propositions 3.9 and 4.3 imply dor(L2(6)) ≥3. The reverse inequality follows from Proposition 2.5 using ν(6) =4. □ Note that this equality alone settles the Fox–Kleitman conjecture for k=2. We are now ready to prove Theorem 1.2 in the following reformulation. Theorem 4.5. We have dor(L2(b)) =min(3, ν(b)−1) for all b ≥1. Proof. If ν(b)=2, then bis odd, whence dor(L2(b)) =1 by Lemma 2.4. If ν(b)=3, then bis even but not divisible by 3. Since dor(L2(2)) =2 and since 2 divides b, it follows from Lemma 2.3 that dor(L2(b)) ≥2. The reverse inequality follows from Lemma 2.4. Finally, if ν(b)≥4, then 6 divides b. Again, since dor(L2(6)) =3, it follows that dor(L2(b)) =3 by Lemmas 2.1 and 2.3.□ 5. The case k=3 Our purpose here is to determine dor(L3(b)) for all b≥1 and, in the process, independently settle the Fox–Kleitman conjecture for k=3. The development is self-contained, except for b=120 where we need to rely on some computer calculations. The determination of dor(L3(b)) is achieved in Theorem 5.11. We start with the more challenging case b≡0 mod 4, treated in the next three sections. 5.1. On equation L3(b)when b ≡4 mod 8 Let Ldenote equation L3(b) for some b≡4 mod 8. Our present purpose is to prove that Lis not 4-regular. We shall work with the group G=Z/8Z. Quite naturally, we shall say that a subset X⊆Gis regular if b∈3 (X−X), singular otherwise. We start by partitioning Ginto four singular subsets of cardinality 2. Lemma 5.1. The four subsets {0,1},{2,3},{4,5},{6,7}of G =Z/8Zconstitute a partition of G into singular subsets. Proof. Let X= {0,1} ⊂ G. Then X−X= {−1,0,1}, whence 3(X−X)= {−3,−2,−1,0,1,2,3} = G\ {4}. Thus Xis L-singular, as claimed. Since the property of being L-singular is stable under translation, the three translates X+t with t∈ {2,4,6}are also singular. □ Proposition 5.2. If b ≡ 0 mod 8, then equation L3(b)is not 4-regular, i.e. dor(L3(b)) ≤3. Proof. First, if b≡ 0 mod 4, i.e. if ν(b)≤4, then dor(L3(b)) ≤3 by Lemma 2.4. Assume now b≡4 mod 8, the last remaining case. The subset X= {0,1} + 8Zsatisfies b∈ 3(X−X), since in the quotient group G=Z/8Z, we have b=4∈ 3(X−X) as seen in the above lemma. Said otherwise, the subset X⊂Zis singular with respect to equation L3(b). This property remaining true under translation, the subsets X+twith t∈ {0,2,4,6}constitute a partition of Zinto four L3(b)-singular sets. This implies dor(L3(b)) ≤3 as stated. □ 5.2. On equation L3(24) Let Ldenote equation L3(24). Our aim here is to prove that Lis 4-regular. During research on this paper, our first proof of this followed the same line of reasoning as above, using Proposition 3.9 as the key ingredient. Indeed, the 4-regularity of L directly follows from that tool applied to the following statement. Proposition 5.3. Let L denote equation L3(24). Every positive integer sequence A of length 8and average µ(A)≤4is forbidden with respect to L. Now, our detailed proof of this proposition is several pages long. In its place, we shall present here an alternate shorter proof of the 4-regularity of Lwith a slightly different and more ad-hoc approach. We start with a lemma on L-singular subsets of [0,32]which are constant mod 4,i.e. contained in a single class a+4Nfor some integer a. Lemma 5.4. Let S ⊂ [0,32]be an L-singular subset of cardinality at least 3 which is constant mod 4. Then S is constant mod 16. Proof. We may assume |S| = 3, since if the statement is valid in that particular case, its validity automatically extends to the general case |S| ≥ 3. Let A=∆S=(δ1, δ2) be the discrete derivative of S. We have δ1+δ2≤32 since S⊂ [0,32], and δ1, δ2∈ {4,8,12,16,20,24,28}since Sis constant mod 4. We must show that δ1=δ2=16. Since Sis singular, we have 24 ∈ 3 bs(A). Note that bs(A)= ±{0, δ1, δ2, δ1+δ2}. Let j∈ {1,2}. Since 3 bs(A) contains ±{3δj,2δj, δj}and does not contain 24, it follows that δj∈ {8,12,24}. Further, we may assume δ1≤δ2. This is achieved by replacing Sby S′=32 −Sif necessary, and noting that S′is singular if and only if Sis, since S′−S′=S−S. It follows that δ1≤16. Let us now show that δ1= 4. For assume, on the contrary, that δ1=4. Each possible value of δ2∈ {4,16,20,28}is then excluded by the following table, which in each case would explicitly write 24 as an element of 3 bs(A), in contradiction with the hypothesis. For that, it suffices to note that 3 bs(A) contains 3(δ1+δ2), 2δ1+δ2,δ1+δ2+0 and δ2−δ1+0. δ224 = 4 3(4 +4) 16 4 +4+16 20 4 +20 +0 28 28 −4+0 It follows that δ1=16, whence δ2=16 as well, since δ1≤δ2and δ1+δ2≤32. □ This lemma will be used below in conjunction with the following obvious remark. Remark 5.5. The only subset B⊂ [0,32]of cardinality at least 3 which is constant mod 16 is B= {0,16,32}of cardinality 3. We are now ready to prove the main result of this section. Theorem 5.6. Let L denote equation L3(24). Every subset X ⊂ [0,32]of cardinality |X| = 9is regular with respect to L. Proof. Let X⊂ [0,32]be such that |X| = 9. Assume for a contradiction that Xis singular. Let us partition Xaccording to the class mod 4: X=X0∪X1∪X2∪X3, where Xi=X∩(i+4N) for all 0 ≤i≤3. There are several steps. Step 1. Since subsets of singular sets are singular, and since Xis singular, it follows that Xiis singular for all 0 ≤i≤3. Step 2. We claim that X0= {0,16,32}and that |Xj| = 2 for 1 ≤j≤3. Indeed, since 9= |X| = |X0|+|X1|+|X2|+|X3|,(7) there is some index 0 ≤i≤3 for which |Xi| ≥ 3. As Xiis singular and constant mod 4, it follows from Lemma 5.4 that Xi=B= {0,16,32}. Thus i=0 and X0= {0,16,32}as claimed. Further, it now follows from (7) that |X1| = |X2| = |X3| = 2. Step 3. Taking the discrete derivative of X1,X2,X3, let ∆Xj=(δj) for j=1,2,3. Since the Xj’s are positive and constant mod 4, it follows that δj∈4N+. Moreover, since 0 < δj<32 for 1 ≤j≤3, we have δj∈ {4,8,12,16,20,24,28}. Step 4. We claim that δ1=δ2=δ3=16. Indeed, let j∈ {1,2,3}. Since Xis singular, we have 24 ∈ 3 (X−X). On the other hand, since X∋0 and X⊃Xj, we have 3 (X−X)⊇ {3δj,2δj, δj}. Hence δj∈ {8,12,24}. Further, since 24 =4+4+16 =20 +20 −16 =28 +28 −32 and since X−X⊇ {±16,−32, δj}, it follows that δj∈ {4,20,28}. Hence δj=16, as claimed. Step 5. For j∈ {1,2,3}and z∈N, let us denote Yj(z)= {4z+j,4z+j+16}. Since Xjis of class jmod 4 and since δj=16, we have Xj=Yj(aj) for some aj∈N. Further, since Xj⊂ [0,32], we have aj∈ {0,1,2,3}. Step 6. Thus Xdepends on the three parameters a1,a2,a3. We shall then write X=X(a1,a2,a3)=X0∪Y1(a1)∪Y2(a2)∪Y3(a3). Since 0 ≤aj≤3 for j∈ {1,2,3}, there are 64 cases to consider. Our task is to show that X(a1,a2,a3) is regular in each one, thereby leading to a contradiction and concluding the proof of the theorem. Fortunately, it turns out that only 8 cases need to be considered. Step 7. To start with, we may assume a2∈ {0,2}. Indeed, for any subset Z⊆ [0,32], denote Z′=32 −Zas in the proof of the preceding lemma. Then Z′⊆ [0,32]and Z′is singular if and only if Zis. Now note that for 0 ≤a≤3, we have Y2(a)′=Y2(3 −a) as easily verified. In particular, we have Y2(1)′=Y2(2) and Y2(3)′=Y2(0). The claim follows by replacing Xby X′if a2is odd. This reduces the number of cases to consider from 64 to 32. Step 8. We now see that it suffices to consider the 8 cases given by (a2,a3)∈ {0,2}×{0,1,2,3}, the value of the parameter a1being irrelevant. Indeed, for the 8 listed cases, the following table shows that X=X(a1,a2,a3) is regular by explicitly writing 24 as an element of 3 (X−X). (a2,a3)X2∪X3=Y2(a2)∪Y3(a3) 24 = (0,0) {2,18,3,19}(18 −0) +(3 −0) +(3 −0) (0,1) {2,18,7,23}(23 −2) +(7 −2) +(0 −2) (0,2) {2,18,11,27}(11 −0) +(11 −0) +(2 −0) (0,3) {2,18,15,31}(15 −2) +(15 −2) +(0 −2) (2,0) {10,26,3,19}(10 −3) +(10 −3) +(10 −0) (2,1) {10,26,7,23}(10 −0) +(7 −0) +(7 −0) (2,2) {10,26,11,27}(27 −10) +(27 −10) +(0 −10) (2,3) {10,26,15,31}(15 −0) +(15 −0) +(10 −16) These contradictions conclude the proof of the theorem. □ Corollary 5.7. We have dor(L3(24)) =4. Proof. Consider an arbitrary 4-coloring of the integer interval [0,32]. Since that interval has cardinality 33, one of the color classes contains a subset Xof cardinality 9. By the theorem, Xis regular, and hence contains a solution to L, which is monochromatic by construction. This implies dor(L3(24)) ≥4. The reverse inequality follows from Lemma 2.4 and the fact that 5 does not divide 24. □ 5.3. On equation L3(120) We establish here that equation L3(120) is 5-regular, thereby independently settling the Fox–Kleitman conjecture for k=3. We give two different proofs. They both require some computer calculations, but of a very different nature. Here is the first approach. Proposition 5.8. Let X = −Y∪ {0} ∪ Y, where Y= [1,30] ∪ 5· [7,20] ∪ (110 +10 · [0,5])∪(220 +60 · [0,4]) = {1, . . . , 30}∪{35,40, . . . , 100}∪{110,120, . . . , 160}∪{220,280, . . . , 460}. Then |X| = 111 and, for every 5-coloring of X, there is a monochromatic solution of equation L3(120) in X. Proof. By translating this coloring problem as a Boolean satisfiability problem and then feeding it to a SAT solver. The solver march reached the conclusion in about 20 s on a standard desktop computer. The set Xitself was discovered through a patient and delicate computer-aided purification process using march.□ Corollary 5.9. We have dor(L3(120)) =5. Proof. Proposition 5.8 implies that L3(120) is 5-regular, i.e. dor(L3(120)) ≥5. The reverse inequality follows from Lemma 2.1.□ Our second proof of the 5-regularity of L3(120) uses Proposition 3.9. Here is the precise statement. Theorem 5.10. Every positive integer sequence A of length 80 and average µ(A)≤5is forbidden with respect to L3(120). Moreover, 80 is minimal with respect to that property. Proof. The first part of this result has been obtained by exhaustive computer search. Combined with Proposition 3.9, it directly implies Corollary 5.9. The fact that length 80 is minimal for the stated property is witnessed by the following instances. First, for 1 ≤r≤39, the sequence (1, . . . , 1    r )