On the degree of regularity of a certain quadratic Diophantine equation

On the degree of regularity of a certain quadratic Diophantine equation S.D. Adhikari a, L. Boza b, S. Eliahou c,d, M.P. Revuelta b, M.I. Sanz b a Harish-Chandra Research Institute, HBNI, 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 ab s t r a c t We show that, for every positive integer r, there exists an integer b = b(r) such that the 4-variable quadratic Diophantine equation (x1 − y1)(x2 − y2) = b is r-regular. Our proof uses Szemerédi’s theorem on arithmetic progressions. 1. Introduction Denote N= {0,1,2, . . .}and N+=N\ {0}. Given a polynomial f∈Z[x1,x2, . . . , xn], let D(f) denote the corresponding Diophantine equation f(x1,x2, . . . , xn)=0. This equation is said to be r-regular, for some integer r≥1, if for every r-coloring of N+, there is a monochromatic solution to it. It is said to be regular if it is r-regular for all r≥1. The degree of regularity of D(f), denoted dor(D(f)), is defined to be infinite if D(f) is regular, or else, it is the largest rsuch that D(f) is r-regular. Determining the degree of regularity of a given Diophantine equation is difficult in general, even if it is linear. In this paper, we shall consider the 4-variable Diophantine quadratic equation (x1−y1)(x2−y2)=b,(1) E-mail addresses: [email protected] (S.D. Adhikari), [email protected] (L. Boza), [email protected] (S. Eliahou), [email protected] (M.P. Revuelta), [email protected] (M.I. Sanz). denoted Q(b), where bis a given positive integer. This equation is not regular. Indeed, it is not b-regular, and actually not even s-regular where s= ⌊√b⌋+1, as witnessed by the s-coloring given by the class mod s; for if x1,y1,x2,y2are all congruent mod s, then (x1−y1)(x2−y2) is divisible by s2, and hence cannot equal bsince s2>b. That is, we have dor(Q(b)) ≤ ⌊√b⌋. Our purpose in this paper is to show that, nevertheless, the numbers dor(Q(b)) are unbounded as bvaries. Here is our main result. Theorem 1.1. Given a positive integer r, there is a positive integer b =b(r)such that the equation (x1−y1)(x2−y2)=b is r-regular. A more specific version is stated and proved in Section 3. Our motivation to study this particular quadratic equation comes from previous work on the linear version (x1−y1)+(x2−y2)=b, and more generally on the 2k-variable linear Diophantine equation (x1−y1)+···+(xk−yk)=b,(2) the object of the following conjecture by Fox and Kleitman [6]. Conjecture 1.2. Let Lk(b)denote Eq. (2).Then max b∈N+ dor(Lk(b)) =2k−1. If true, that estimate would be best possible, since it is shown in [6] that dor(Lk(b)) ≤2k−1 for all k,b≥1. See [1,2] for solutions of the Fox–Kleitman conjecture for k=2 and 3, respectively, and [12] for a very recent full proof. Note that the solved case k=2 of the conjecture and Theorem 1.1 imply a sharp contrast between the additive and the multiplicative versions of the equation, namely maxbdor(L2(b)) =3 versus maxbdor(Q(b)) = ∞. 1.1. Contents Here is a brief description of the contents of the paper. In Section 2, we recall some classical problems on partition regularity. In Section 3, after recalling Szemerédi’s theorem on arithmetic progressions, we prove our main result on the unboundedness of dor(Q(b)) as bvaries. In Section 4, after setting up specific tools for the task at hand, we provide estimates for one of the numbers M(k, δ) involved in Szemerédi’s theorem. In Section 5, we determine all b≥1 for which Q(b) is 2-regular, as well as the smallest b≥1 for which Q(b) is 3-regular. The last section is devoted to a few remarks and open questions. 2. Background We first recall some background results and problems on partition regularity. The following abridged version of a theorem of Rado [9–11] characterizes the regular linear homogeneous equations on Z. Theorem 2.1 (Rado’s Theorem, Abridged Version).For n ≥2and c1, . . . , cn∈Z\{0}, the Diophantine equation c1x1+···+cnxn=0 (3) is regular if and only ∑i∈Ici=0for some non-empty subset I ⊆ {1, . . . , n}. One of the main open problems in the linear case is Rado’s boundedness conjecture. A simplified version of it states that if Eq. (3) is r-regular for some integer r=r(n) only depending on n, then it is regular. See for instance [6], where the conjecture is settled for n=3 with the value r(3) =24. See also [3,4,7] for related papers. Other open problems in the linear case concern the m-color Rado number of a given equation. Recall that for a Diophantine equation D, the m-color Rado number Rm(D) of Dis defined as the smallest positive integer Nsuch that for every m-coloring of [1,N], there is a monochromatic solution in [1,N] to D. If no such Nexists, then Rm(D)= ∞by definition. Still less is known in the nonlinear case. For instance, it is an open question whether the quadratic Diophantine equation x2+y2=z2(4) is regular. According to a recent preprint using massive computer computations with a SAT solver, Eq. (4) turns out to be 2-regular [5]. More precisely, for every 2-coloring of the integer interval [1,7825], there is a monochromatic solution in that interval to Eq. (4), and 7825 is minimal in that respect. However, it is not known whether that equation is 3-regular, and it remains an open problem to determine its precise degree of regularity. Note that some other homogeneous quadratic equations in three variables have recently been shown to be regular [8]. 3. Main result In this section, we show that the numbers dor(Q(b)) are unbounded as bvaries. 3.1. Some tools To start with, for the statement and proof of our main result, we need the deep theorem of Szemerédi about the existence of long arithmetic progressions in sufficiently dense subsets of sufficiently large integer intervals [13, p. 244, Corollary]. Theorem 3.1 (Szemerédi).Given a desired length k ∈N+and a specified density 0< δ ≤1, there exists a positive integer N =N(k, δ)such that every subset A ⊆ [1,N]of density |A|/N≥δcontains an arithmetic progression of length k. For definiteness and in the sequel, we shall denote by M(k, δ) the smallest positive integer Nwith the above property. We also need an elementary folklore lemma about the preservation of density under partitions of finite sets. Lemma 3.2. Let A ⊆E be nonempty finite sets. Denote δ= |A|/|E|the density of A in E. Let E=E1⊔ ··· ⊔ Erbe a partition of E into r nonempty parts. Then there exists an index i ≤r such that |A∩Ei|/|Ei| ≥ δ. Proof. Assume for a contradiction that |A∩Ei|/|Ei|< δ for all i≤r. Then |A∩Ei|< δ|Ei|for all i≤r and, summing over i, we get ∑ i|A∩Ei|< δ ∑ i|Ei|. Since ∑i|A∩Ei|=|A|and ∑i|Ei|=|E|, the above inequality leads to |A|< δ|E|=|A|, a contradiction. □ 3.2. Unboundedness of dor(Q(b)) Let r∈N+be given. For the statement below, we invoke Szemerédi’s theorem with the desired length k=r! + 1 and density δ=1/r. Let N=M(r! + 1,1/r). Then Nhas the property that every subset B ⊆ [1,N]of density |B|/N≥1/r contains an arithmetic progression of length r!+1. Clearly, the same property holds for any integer interval [a,a+N−1]of length N. Recall that Q(b) denotes the Diophantine equation (x1−y1)(x2−y2)=b. Theorem 3.3. Let r ∈N+, and let N =M(r!+1,1/r)be as defined above. Then the Diophantine equation Q(N!r!)is r-regular. Proof. Let ∆be an arbitrary r-coloring of the integer interval E= [1,(r+1)N!]. Then there exists a color class S⊆Eof density |S|/|E| ≥ 1/r. Let us partition Einto subintervals of length N, as is possible since Ndivides |E|. By Lemma 3.2, there exists one such subinterval A⊆Eof size |A| = Nsuch that |S∩A|/|A| ≥ 1/r. By the defining property of N, the subset S∩Acontains an arithmetic progression of length r! + 1, with common difference dfor some d≥1. Thus, there exists s∈S∩Asuch that {s,s+d, . . . , s+r!d} ⊆ S∩A.(5) Not much is known about dbesides the inequality r!d≤N. As customary in additive combinatorics, let us denote S−S= {s1−s2|s1,s2∈S}. Fact 1. We have [1,r!]d⊆S−S. Indeed, for all 1 ≤j≤r!, we have jd =(s+jd)−s, and so jd ∈S−Sby (5). Set m=N!/d. Partition Einto its classes mod m, and then partition each class mod minto subsets of cardinality r+1 of the form C= {a,a+m, . . . , a+rm} ⊂ E. This is possible since mdivides |E|and r+1 divides |E|/m. By Lemma 3.2 again, for at least one such subset C, we must have |S∩C|/|C| ≥ 1/r. But since |C| = r+1, this implies |S∩C| ≥ 2. Thus, there exist two distinct indices 0 ≤i<j≤r such that a+im,a+jm ∈S∩C. Fact 2. We have um ∈S−S for some u ∈ [1,r]. Indeed, simply take um =(a+jm)−(a+im) for the two elements in S∩Cfound above. Note that 1≤u=j−i≤r, as desired. We now combine the above facts. Since m=N!/d, by Fact 2 we have uN!/d∈S−S for some u∈ [1,r]. Now since udivides r!, we have r!/u∈ [1,r!], and hence (r!/u)d∈ [1,r!]d. Therefore (r!/u)d∈S−S by Fact 1. Multiplying these two elements of S−Stogether, it follows that N!r! ∈ (S−S)(S−S). That is, there exist x1,y1,x2,y2∈Ssuch that (x1−y1)(x1−y1)=N!r!, thus yielding a monochromatic solution of equation Q(N!r!). Therefore this equation is r-regular, as claimed. □ 3.3. More properties of dor(Q(b)) The problem of determining dor(Q(b)) as a function of b∈N+is probably very difficult. In Section 5.1, we show that dor(Q(b)) ≥2 if and only if b∈4N+, thereby improving the case r=2 of Theorem 3.3. The case r=3 of that result is improved in Section 5.2, where we show that dor(Q(36)) =3. We conclude this section with some general properties of dor(Q(b)). Proposition 3.4. Let b,m∈N+. If b ≡ 0 mod m2, then dor(Q(b)) ≤m−1. Proof. Consider the m-coloring of N+given by the class mod m. That is, color classes correspond to congruence classes mod m. If m2does not divide b, then equation (x1−y1)(x2−y2)=bhas no monochromatic solution under this coloring, for if x1,y1,x2,y2are of the same color, i.e., are congruent mod m, then m2divides (x1−y1)(x2−y2). □ For instance, if bis not divisible by 36 =62, then equation Q(b) is not 3-regular, as follows by successively taking m=2 and m=3 in the above result. Proposition 3.5. Let b,t∈N+. Then dor(Q(b)) ≤dor(Q(t2b)). Proof. Set r=dor(Q(b)). Let c:N+→ [1,r]be an r-coloring. Define a new r-coloring c′: N+→ [1,r]by setting c′(n)=c(tn) for all n≥1. Since Q(b) is r-regular by hypothesis, there is a solution (x1,y1,x2,y2) of equation Q(b) which is monochromatic under c′. Hence (tx1,ty1,tx2,ty2) is monochromatic under c. Moreover, since (x1−y1)(x2−y2)=bby hypothesis, it follows that (tx1−ty1)(tx2−ty2)=t2b. Therefore (tx1,ty1,tx2,ty2) is a solution of equation Q(t2b), and it is monochromatic under cas already seen. We conclude that Q(t2b) is r-regular. □ 4. On M(3,1/2) Theorem 3.3 involves the numbers M(r!+1,1/r) arising from Szemerédi’s theorem. In this section, after setting up some useful tools, we determine this number for r=2, namely M(3,1/2). 4.1. Detecting arithmetic progressions Let (G,+) be an abelian group. Here we set up some notation and terminology to help determine the presence or absence of arithmetic progressions of a given length in sequences in G. This will then be used in G=Zto show M(3,1/2) =17. Let A=(a1, . . . , an) be a sequence in Gof length |A| = n. A block in Ais any subsequence of consecutive elements, i.e., of the form A[i,j] = (ai,ai+1, . . . , aj) for some indices 1 ≤i,j≤n, allowing the empty subsequence if j<i. We denote by σ(A)=∑iai the sum of the elements of A. Definition 4.1. Let Abe a finite sequence in G. A block decomposition of Ais a sequence (A1, . . . , Am) of consecutive blocks Atof A, 1 ≤t≤m, whose concatenation is A. A contraction of Ais a sequence in Gof the form (σ(A1), . . . , σ (Am)) where (A1, . . . , Am) is a block decomposition of A. A minor of Ais a contraction of a block Bof Aor, equivalently, a block in a contraction of A. For instance, if A=(1,5,1,8,2,3,1) in G=Z, then ((1,5,1),(8,2),(3,1)) is a block decomposition of Aand (7,10,4) is the corresponding contraction of A. Some minors of Aare (6,1,8), (7,10), (9,5,1), (10,3) and (10,4). Note that (6,1,8) is a contraction of the block (1,5,1,8) in A, and a block in the contraction (6,1,8,6) of A. Definition 4.2. Let X=(x0,x1, . . . , xn) be a sequence in Gwith n≥1. The discrete derivative of Xis its sequence of successive jumps, i.e., ∆(X)=(x1−x0, . . . , xn−xn−1). For instance, Xis an arithmetic progression of length n+1 in Gif and only if ∆(X) is a constant sequence of length n. Let us now observe that for a sequence X, block sums in ∆(X) correspond to differences of two terms in X. Lemma 4.3. Let X =(x0,x1, . . . , xn)be a sequence in G. Let A =∆(X)=(a1,...,an)where ai=xi−xi−1for i ≥1. Let B =A[i,j]for some 1≤i≤j≤n. Then σ(B)=xj−xi−1. Proof. We have σ(A[i,j])=∑ i≤t≤j (xt−xt−1)=xj−xi−1.□ Here is a correspondence between subsequences of Xand minors of ∆(X). Lemma 4.4. Let X be a finite sequence in G. If Y is a subsequence of X, then ∆(Y)is a minor of ∆(X). Conversely, if C is a minor of ∆(X), then C =∆(Y)for some subsequence Y of X. Proof. Let X=(x0,x1,...,xn) and A=∆(X)=(a1,...,an) where ai=xi−xi−1for i≥1. Let Y=(xi0,xi1, . . . , xim) be a subsequence of X, with 0 ≤i0<i1<··· <im≤n. Then ∆(Y)=(xi1−xi0, . . . , xim−xim−1). Let Bt=A[it−1+1,it]for 1 ≤t≤m. By Lemma 4.3, we have ∆(Y)=(σ(B1), . . . , σ (Bm)). Let B=A[i0+1,im]. Then (B1, . . . , Bm) is a block decomposition of B. Therefore ∆(Y) is a contraction of block Band hence a minor of A. Conversely, let Cbe a minor of A. Hence there is a block Bin Asuch that C=(σ(B1), . . . , σ (Bm)) for some block decomposition (B1, . . . , Bm) of B. For each 1 ≤t≤m, we have Bt=A[jt,it]for some 1≤jt≤it≤n. Since the Bt’s are consecutive blocks in B, and hence in A, we have jt=it−1+1 for t≥2. Thus, denoting i0=j1−1, we have Bt=A[it−1+1,it]for all 1 ≤t≤m, and σ(Bt)=xit−xit−1 by Lemma 4.3. Therefore C=∆(Y) where Y=(xi0,xi1, . . . , xim). □ This correspondence yields the following convenient tool to determine the presence or absence of arithmetic progressions of a given length in sequences in G. Proposition 4.5. Let X be a finite sequence in G. Then X contains an arithmetic progression of length k≥3if and only if ∆(X)has a constant minor of length k −1. Proof. If Xcontains an arithmetic sequence Yof length k, then ∆(Y) is a constant sequence of length k−1, and it is a minor of ∆(X) by the preceding lemma. Conversely, let Cbe a constant minor of length k−1 of ∆(X). Then by the above lemma, there exists a subsequence Yof Xsuch that C=∆(Y), and Yis an arithmetic progression of length ksince ∆(Y) is constant of length k−1. □ For instance, let X=(1,2,4,5,10,11,13,14) in G=Z. Let A=∆(X). Then A=(1,2,1,5,1,2,1) and Acontains no constant minor of length 2 as easily checked by inspection. Therefore Xcontains no arithmetic progression of length 3. 4.2. Determining M(3,1/2) As an application in G=Z, we obtain here the exact value of M(r!+1,1/r) for r=2. Even though the result is easy to obtain by computer, the present method will hopefully, in future works, yield exact values or good bounds in harder cases. Proposition 4.6. Every subset X ⊂ [1,17]of cardinality |X| = 9contains an arithmetic progression of length 3. Proof. We first claim that the only sequences Bin N+such that |B| = 4, σ(B)≤8 and admitting no constant minor of length 2 satisfy σ(B)=8. More precisely, the only such sequences are, up to reversal, (1,2,4,1) and (2,1,4,1). This is easy. Indeed, let (C1,C2) be a block decomposition of B with |Ci| = 2 for i=1,2. Since σ(C1)+σ(C2)=σ(B)≤8, and no Cican be constant, then each Ci coïncides, up to reversal, with one of the sequences (1,2),(1,3),(1,4),(2,3). Moreover σ(C1)= σ(C2), for otherwise (σ(C1), σ (C2)) would be a constant minor of length 2 of B. Up to reversal of B, we may assume σ(C1)< σ (C2). Hence C1=(1,2) up to reversal, and σ(C2)=4 or 5. By considering all possible combinations, it is easily seen that C2=(4,1) is the only valid possibility. This proves the claim. Assume, for a contradiction, that there exists X⊂ [1,17]of cardinality |X| = 9 containing no arithmetic progression of length 3. Let A=∆(X), when Xis viewed as an increasing sequence. Then |A| = 8, σ(A)=max(X)−min(X)≤16 and Aadmits no constant minor of length 2. Let (B1,B2) be a block decomposition of Awith |B1| = |B2| = 4. Then neither B1nor B2admits a constant minor of length 2. Moreover, since σ(B1)+σ(B2)=σ(A)≤16, we may assume σ(B1)≤8 up to reversal of A. Hence σ(B1)=8 by the above claim. Therefore σ(B2)≤8 as well, whence σ(B1)=8 by the above claim again. But then, (σ(B1), σ(B2)) =(8,8) is a constant minor of length 2 of A, a contradiction. □ Corollary 4.7. We have M(3,1/2) =17. Proof. The proposition yields M(3,1/2) ≤17. In order to establish the equality, we must exhibit, for all 1 ≤m≤16, a subset Xm⊆ [1,m]of density at least 1/2 and containing no 3-term arithmetic progression. Let X= {1,2,4,5,10,11,13,14}. Then the set Xmdefined as follows will do: Xm={X∩[1,m]if m= 9 {1,2,4,8,9}if m=9.□ 4.3. Comparison with W(k,r) It would be desirable to determine M(k,1/r) for more instances of the pair (k,r), as nothing precise seems to be known about these numbers. We have started to make the first few steps towards that objective in a paper under preparation. Of course, these numbers are bounded below by the corresponding van der Waerden numbers. Given integers k,r≥1, recall that the van der Waerden number W(k,r) denotes the least integer Msuch that, for every r-coloring of [1,M], there is a monochromatic arithmetic progression of length kin [1,M]. Clearly, we have M(k,1/r)≥W(k,r).(6) Indeed, let N=M(k,1/r), and consider any r-coloring of [1,N]. Then some color class X⊆ [1,N] is of density |X|/N≥1/r, and hence Xcontains an arithmetic progression of length k, of course monochromatic by construction. The only exactly known van der Waerden numbers at the time of writing are given in the following table. See e.g. [14], a web page which also displays lower bounds on W(k,r) for many more pairs (k,r). W(3,2) =9W(3,3) =27 W(3,4) =76 W(4,2) =35 W(4,3) =293 W(5,2) =178 W(6,2) =1132 5. When ris small In this section, we obtain sharper statements than Theorem 3.3 for r=2 and 3. We also discuss some corresponding Rado numbers. 5.1. The case r =2 For r=2, and with the notation of Section 3, our main result states that with N=M(3,1/2), equation (x1−y1)(x2−y2)=2N!is 2-regular. We have seen above that M(3,1/2) =17. Thus, Theorem 3.3 states that equation Q(2 ·17!) is 2-regular. However, we now show that the same already holds for equation Q(4), and more generally for equation Q(b) whenever b∈4N+. Proposition 5.1. The equation (x1−y1)(x2−y2)=b is 2-regular if and only if b is a multiple of 4. Proof. Proposition 3.4 implies that if b≡ 0 mod 4, then Q(b) is not 2-regular. Assume now b≡0 mod 4. First some notation. Let X⊆N+be any nonempty subset. We denote D(X)=(X−X)∩N, the set of distances in X, and D2(X)= {d1d2|d1,d2∈D(X)}, the set of products of two distances in X. Thus, equation Q (b)has a solution in X if and only if b ∈D2(X). Finally, we denote X=N+\X. Claim 1. If m ∈N\D(X), then m +X⊆X. Indeed, for any x∈X, we have m=(m+x)−x, and since mis not a distance in X, it follows that m+xcannot belong to X. Claim 2. If D(X)= N, then D(X)⊆D(X). Indeed, let d∈D(X). Then d=x−yfor some x,y∈Xwith x≥y. Let now m∈N\D(X). Then d=(m+x)−(m+y), and m+x,m+y∈Xby Claim 1. Hence d∈D(X). Claim 3. Let t ∈Nsatisfy t +X⊆X. Then tN⊆D(X). Indeed, the hypothesis implies nt +X⊆Xfor all n∈N. Hence, for x∈X, we have nt +x∈Xand so nt =(nt +x)−x∈D(X). Let now N+=A0⊔A1be a partition of N+into two nonempty parts. Thus A1−i=Aifor i=0,1. We must show that Q(b) has a solution in either A0or A1or, equivalently, that b∈D2(A0)∪D2(A1). Clearly, if D(Ai)=Nfor i=0 or 1, we are done since then b∈D2(Ai). Assume now D(A0),D(A1)= N. Claim 4. Let m ∈N\D(A0). Then 2mN+⊆D(A0). Indeed, Claim 1 implies m+A0⊆A0=A1.(7) Moreover, Claim 2 implies both D(A0)⊆D(A1) and D(A1)⊆D(A0). Therefore D(A0)=D(A1). Hence m∈N\D(A1), and Claim 1 implies m+A1⊆A0.(8) It follows from (7) and (8) that 2m+A0⊆A0, and then Claim 3 implies 2mN+⊆D(A0). This settles Claim 4. We now examine four possible cases. Case 1. Assume 1∈ D(A0).Then Claim 4 implies 2N+⊆D(A0). Hence 2,b/2∈D(A0), implying b=2·b/2∈D2(A0). Case 2. Assume 1∈D(A0)and 2∈ D(A0).Then Claim 4 implies 4N+⊆D(A0). Hence b∈D(A0), and since 1 ∈D(A0) it follows that b∈D2(A0). Case 3. Assume 1∈D(A0)and b/2∈ D(A0).Then Claim 4 implies b∈D(A0). But since 1 ∈D(A0), it follows that b∈D2(A0). Case 4. Assume 1,2,b/2∈D(A0).Then b=2·b/2∈D2(A0). All four cases lead to the conclusion b∈D2(A0). Therefore Q(b) is 2-regular. □ Remark 5.2. As easily seen, the 2-color Rado number for equation Q (4) is equal to 5. That is, for any 2-coloring of [1, 5], there is a monochromatic solution to that equation, and 5 is minimal for that property. 5.2. The case r = 3 We now show that equation (x1 −y1)(x2 −y2) = 36 is 3-regular. By Proposition 3.4, the right-hand side b = 36 is minimal for that property. Again, this is a much sharper statement than that provided by Theorem 3.3 for r = 3. Indeed, the number N = M(6! + 1, 1/3) is huge already, since N ≥ W (721, 3) by (6), and even more so is the constant term b = 6N! involved in our main result. As in [1], for a finite sequence Ain N+, we denote by bs(A) the set of all signed block sums in A, i.e., bs(A)= {±σ(B)|Bis a block in A}. We shall also need the following ad-hoc definition, specifically tailored to deal with equation Q(36). Of course, it may be easily adapted to deal with equation Q(b) for any b≥1. Definition 5.3. A sequence A=(a1, . . . , an) of positive integers is said to be admissible if bs(A) contains no solution of the equation uv=36, i.e., contains none of the following subsets: {6},{4,9},{3,12},{2,18},{1,36}.(9) Moreover, if Ais admissible and σ(A)≤tfor some integer t, then Ais said to be t-admissible. Finally, if Ais not admissible then Ais said to be forbidden. For instance, the sequence A=(1,1,9,1) is 12-admissible. Indeed, we have bs(A)∩N= {0,1,2,9,10,11,12}, a set containing no subset {u, v}from list (9). Remark 5.4. Every block in a t-admissible sequence is itself t-admissible. A sequence Ais admissible if and only if its reverse sequence A′is admissible. In the sequel, as in [1], we say that a set X⊆N+is regular with respect to a Diophantine equation D if Xcontains a solution of D.1 Lemma 5.5. Let X be a finite subset of N+. Let A =∆(X)be the discrete derivative of X. Then X is regular with respect to equation Q (36) if and only if A is forbidden. Proof. We have X−X=bs(A) as follows from Lemma 4.3. Hence Xis regular if and only if 36 =uv for some u, v ∈X−X, if and only if Ais forbidden. □ Proposition 5.6. Every 18-admissible sequence A of length 6satisfies σ(A)=18 and contains 1. More precisely, the list of all such sequences, up to reversal, is: (1,3,1,3,7,3),(1,3,4,3,4,3),(1,3,7,3,1,3), (3,1,3,1,3,7),(3,1,3,4,3,4),(3,4,3,1,3,4). Proof. The proof is completely elementary but too long to be included here. It exploits the fact that if (a1, . . . , ar,c) is t-admissible then (a1, . . . , ar) is (t−1)-admissible, and in fact (t−c)-admissible. Thus, one may start with the set of all 13-admissible sequences of length 1, look for their respective extensions of length 2 which are 14-admissible, and so on up to length 6. This process takes a few hours by hand, or a few microseconds on a suitably programmed home computer. As an illustrative example, consider the 8-admissible sequence A=(1,3,1,3) of length 4. It is admissible since the set bs(A)∩N+= {1,3,4,5,7,8}contains none of the forbidden subsets in list (9). 1That is, if there is some solution (x1,...,xn) of Dwith xi∈Xfor all i.