On Heights and Diameters of Ternary Cyclotomic and Inclusion-Exclusion Polynomials Gennady Bachman Abstract . For the n n th cyclotomic polynomial Φ n \Phi_{n} , let A ⁡ ( n ) A(n) denote the greatest absolute value of its coefficients, its height, and let D ⁡ ( n ) D(n) denote the difference between its largest and smallest coefficients, its diameter. We show that for any odd prime p p and an integer h h in the range 1 ≤ h ≤ ( p + 1 ) / 2 1\leq h\leq(p+1)/2 , there are arbitrarily large primes q q and r r such that Φ p ​ q ​ r \Phi_{pqr} has the height h h . This certainly answers the question of whether every natural number occurs as the height of some cyclotomic polynomial. Our construction specifies explicit choices of q q and r r with A ⁡ ( p ​ q ​ r ) = h A(pqr)=h , and for these choices D ⁡ ( p ​ q ​ r ) D(pqr) has one of two values: it is either 2 ​ h 2h or 2 ​ h − 1 2h-1 , depending on the congruence class of h h modulo p p . 2020 Mathematics Subject Classification Primary 11B83; Secondary 11C08 1. Introduction Let \Phi_{n} be the n th cyclotomic polynomial, that is, \Phi_{n}(x)=\prod(x-\zeta) , where the product is taken over the primitive n th roots of unity \zeta , and write \Phi_{n}(x)=\sum_{0\leq m\leq\varphi(n)}a_{m}x^{m}\qquad[a_{m}=a(m;n)], where \varphi is the Euler’s totient function. It is well known that the coefficients a_{m} are integral and there is a growing body of literature studying their properties and especially properties of the function A(n)\coloneqq\max_{m}|a_{m}|=\max_{m}|a(m;n)|. (See [ 7 , 8 ] and the references therein.) As has become increasingly common in the literature, we shall refer to A(n) as the height of \Phi_{n} . It is an interesting and nontrivial question if there is a polynomial \Phi_{n} of any given height h ? To gain a better understanding of this question we review the following easy facts (see, for example, [ 17 ] ). To investigate possible heights, it suffices to study possible values of A(\prod_{1\leq i\leq k}p_{i}) , for primes 2r>n and R\equiv r\pmod{n} . Then A(nR)=A(nr) . Combining this result with computationally obtained evaluation A(3\cdot 5\cdot 31\cdot 929)=1 , he showed that there are infinitely many flat polynomials of the form \Phi_{3\cdot 5\cdot 31\cdot R} . 2. Background and Results Modifying our earlier convention, we now let p , q and r denote three relatively prime in pairs positive integers \geq 3 (so they need not be primes). Put T=\{p,q,r\} and (4) Q_{T}(x)=Q_{\{p,q,r\}}(x)\coloneqq\frac{(x^{pqr}-1)(x^{p}-1)(x^{q}-1)(x^{r}-1)}{(x^{pq}-1)(x^{qr}-1)(x^{rp}-1)(x-1)}. Routine application of the inclusion-exclusion principle to the roots of the polynomials on the right side shows that Q_{T} reduces to a polynomial, a ternary inclusion-exclusion polynomial . We refer the reader to [ 4 ] for an introduction to inclusion-exclusion polynomials. This class of polynomials may be thought of as a tool for studying coefficients of cyclotomic polynomials and other divisors of x^{n}-1 , or as looking at cyclotomic polynomials from a combinatorial rather than algebraic point of view. In particular, when the parameters p , q and r are distinct odd primes, the polynomial Q_{\{p,q,r\}} is better known as the cyclotomic polynomial \Phi_{pqr} . Polynomial Q_{T} is of degree (5) \varphi(T)=\varphi(p,q,r)\coloneqq(p-1)(q-1)(r-1) and we write, as before, Q_{T}(x)=\sum_{0\leq m\leq\varphi(T)}a_{m}x^{m}\qquad[a_{m}=a(m;T)]. We also put \mathcal{A}_{T}\coloneqq\{a_{m}\}\quad\text{and}\quad A(T)\coloneqq\max_{m}|a_{m}|, as well as A^{+}(T)\coloneqq\max_{m}a_{m}\quad\text{and}\quad A^{-}(T)\coloneqq\min_{m}a_{m}. Quantities A^{\pm}(T) completely determine \mathcal{A}_{T} for it is known (see [ 10 ] and [ 4 ] ) that (6) \mathcal{A}_{T}=[A^{-}(T),A^{+}(T)]\cap\mathbb{Z}. We shall see that the following assumptions on triples T allow us to evaluate A^{\pm}(T) with a reasonable amount of effort. Let p\geq 3 be an arbitrary fixed integer and let t\in[1,p-1] be relatively prime to p . For each such pair of p and t , let q , r and r^{\prime} be any integers satisfying the conditions (7) r,r^{\prime}>q>p^{2},\quad q\equiv t\pmod{p},\quad rt\equiv 1\pmod{pq}, and (8) r^{\prime}t\equiv-1\pmod{pq}. Note that if t\neq 1 , then any positive n satisfying nt\equiv\pm 1\pmod{pq} is automatically >q , so our assumption r,r^{\prime}>q was only needed to preclude the possibility r=t=1 in ( 7 ). Note also that the triples T=\{p,q,r\} and T^{\prime}=\{p,q,r^{\prime}\} are each relatively prime in pairs. Evaluation of A^{\pm} for such triples depends on the parameters \underline{t} and \underline{s} defined as follows. First, let s\in[1,p-1] be the inverse of t modulo p , so that r\equiv s\pmod{p} . Now put \underline{t}\coloneqq\min(t,p-t)\quad\text{and}\quad\underline{s}\coloneq\min(s,p-s). We are now ready to state the result that underpins all the findings in our paper. Theorem 3 . Let T=\{p,q,r\} and T^{\prime}=\{p,q,r^{\prime}\} be any triples satisfying ( 7 ) and ( 8 ). Then the sets \mathcal{A}_{T} and \mathcal{A}_{T^{\prime}} satisfy the identity (9) \mathcal{A}_{T^{\prime}}=-\mathcal{A}_{T}. Therefore, by ( 6 ), we only need to evaluate A^{\pm}(T) . These are as follows. (i) If t=s=1 , then A^{-}(T)=-1,\quad A^{+}(T)=1,\quad A(T)=1. (ii) If t>1 and \underline{s}<\underline{t} , then A^{-}(T)=-\underline{s}-1,\quad A^{+}(T)=\underline{s}+1,\quad A(T)=\underline{s}+1. (iii) If t>1 , \underline{s}\geq\underline{t} and (\underline{t},\underline{s})=(t,s) or (p-t,p-s) , then A^{-}(T)=-\underline{s},\quad A^{+}(T)=\underline{s}+1,\quad A(T)=\underline{s}+1. (iv) If t>1 \underline{s}\geq\underline{t} and (\underline{t},\underline{s})=(t,p-s) or (p-t,s) , then A^{-}(T)=-\underline{s}-1,\quad A^{+}(T)=\underline{s},\quad A(T)=\underline{s}+1. Example 1 . Recall that cyclotomic polynomials of order <3 are all flat. The first non-flat cyclotomic polynomial is \Phi_{105} , and it is a classic example that its coefficients form a set \mathcal{A}_{\{3,5,7\}}=\{-2,-1,0,1\} . It is interesting to note that Theorem 3 gives a theoretic evaluation of \mathcal{A}_{\{3,5,7\}} . To see this we take p=3,\quad t=2,\quad s=2,\quad q=5,\quad r^{\prime}=7, and ingnore the requirement q>p^{2} . Then (\underline{t},\underline{s})=(1,1)=(p-t,p-s) and Theorem 3 (iii) gives A^{-}(3,5,r)=-1\quad\text{and}\quad A^{+}(3,5,r)=2, from which the conclusion follows by ( 9 ) and ( 6 ). This is a good place to make a brief comment on our requirement q>p^{2} in Theorem 3 . This condition will be seen to yield technical simplifications in our proof of the theorem. We did not explore the extent to which this requirement can be relaxed, and it is entirely possible that simply having q>p is not sufficient for our conclusions. But it happens to be sufficient in this example. Part (i) of Theorem 3 is not new and in certain important ways is different from the other parts, as we now explain. In [ 3 ] , the author gives the result q\equiv-1\pmod{p}\quad\text{and}\quad r\equiv 1\pmod{pq}\implies A(p,q,r)=1. But in fact, the method of that paper reaches the same conclusion under any of the four assumptions q\equiv\pm 1\pmod{p} and r\equiv\pm 1\pmod{pq} (containing Theorem 3 (i)). Then Kaplan [ 13 ] showed that the condition r\equiv\pm 1\pmod{pq} alone is sufficient for this. Theorem 4 . A(p,q,r)=1 , if r\equiv\pm 1\pmod{pq} . Later, Bachman and Moree [ 5 ] studied heights of polynomials Q_{\{p,q,r\}} , where p\frac{p+1}{2} for all primes p\geq 11 . Findings of Theorem 3 yield new results for the diameter problem. For the sake of simplicity, let us eliminate the requirement \gcd(h-1,p)=1 in Corollary 5 by assuming that p is an odd prime. In fact, we will state our diameter results in the language of cyclotomic polynomials \Phi_{pqr} and write D(pqr) in place of D(p,q,r) . Thus, we are now concerned with solving the equation (11) D(pqr)=d\qquad[2\leq d\leq p,\ r>q>p]. Example 2 . Let us begin with four examples, starting with two evaluations of D(pqr) that were previously known. a) Theorem 3 (i) solves ( 11 ) with d=2 , for each (prime) p . b) Theorem 3 (iv) with t=2 and s=\frac{p+1}{2} , so that (\underline{t},\underline{s})=(2,\frac{p-1}{2}) , solves ( 11 ) with d=p , for each p . c) Theorem 3 (iii) with t=s=p-1 , so that \underline{t}=\underline{s}=1 , solves ( 11 ) with d=3 , for each p . d) It is not possible to use Theorem 3 to solve ( 11 ) with d=4 . We should also remark that the existence of arbitrarily large primes q and r satisfying the required conditions ( 7 ) is guaranteed by the Dirichlet’s theorem for primes in arithmetic progressions. With p fixed, D(pqr) takes on at most p-1 possible values, by ( 10 ). Theorem 3 is sufficient to show that D(pqr) can assume at least half of these values. Corollary 6 . With p fixed, the equation D(pqr)=d is soluble in arbitrary large primes q and r for at least (p+1)/2 different values of 2\leq d\leq p . We saw that Theorem 3 yields no information about polynomials with diameter 4, but shows that D(pqr)=2,3,p are always possible, for a fixed p . In fact, we can do a little better than this. Corollary 7 . Fix p . There are arbitrarily large q and r such that D(pqr)=2 , and D(pqr)=2h , for each 3\leq h<\sqrt{p} . Moreover, there are arbitrarily large q and r such that D(pqr)=p , and D(pqr)=p-2k , for each 1\leq k<\sqrt{p}/2-1 . So Corollary 7 shows that every even number \geq 6 is a diameter of some \Phi_{pqr} with p sufficiently large. We do not have an analogue of this for odd numbers \geq 5 . But at least we can assert the following weaker conclusion. Corollary 8 . For each odd number d\geq 3 , the equation D(pqr)=d is soluble for at least one prime p . We give proofs of all the corollaries first and collect them in the next section. The rest of the paper gives a proof of Theorem 3 , which is elementary but rather lengthy. 3. Proofs of Corollaries 3.1. Proof of Corollary 5 Theorem 4 takes care of h=1 . If h-1

\underline{t},\end{cases} for primes q and r satisfying ( 7 ). Now, for each a in the range 2\leq a\leq\frac{p-1}{2} there corresponds a unique b , 2\leq b\leq\frac{p-1}{2} , such that ab\equiv\pm 1\pmod{p} . It follows that the set of integers n\neq u in the range 2\leq n\leq\frac{p-1}{2} partitions uniquely into pairs (13) \Bigl\{\,a,b\mid 2\leq aa. We now address the odd diameter claim. In Example 2 (b) we established the solubility of D(pqr)=p for each p . It remains to consider D(pqr)=p-2k for k<\sqrt{p}/2-1 and p\geq 17 . We argue in essentially the same way as in the even case. This time, for each pair \{a,b\} in ( 13 ), we want to take t=a to get the diameter 2b+1=p-2k . We claim that this certainly works for every b=\frac{p-1}{2}-k , with 0\leq k<\sqrt{p}/2-1 . To verify this we need to show that if \Bigl(\frac{p-1}{2}-l\Bigr)\Bigl(\frac{p-1}{2}-k\Bigr)\equiv\pm 1\pmod{p}, for k in this range and l in 0\leq l

2n+1. Applying Lemma 9 with n=b shows that there is a prime p\geq 2b+1 and an integer 2\leq a\leq b such that ab\equiv-1\pmod{p} , as required. 4. Preliminaries In this section we collect the required background material on Q_{T} of general nature—we do not yet specialize to require the parameters p , q and r to satisfy ( 7 ). Our starting point for studying coefficients of Q_{T} is the relation (14) \displaystyle Q_{T}\equiv(1-x^{q}-x^{r}+x^{q+r} \displaystyle)(1+x+\dots+x^{p-1}) \displaystyle\times\sum_{i,j,k\geq 0}x^{iqr+jpr+kpq}\pmod{x^{\varphi(T)+1}}, which readily follows from ( 4 ) and ( 5 ). In this formulation, the central role played by integers representable by linear combinations of qr , pr and pq with nonnegative coefficients is quite clear. By the Chinese remainder theorem, every integer n has a unique representation in the form (15) n=x_{n}qr+y_{n}pr+z_{n}pq+\delta_{n}pqr, with 0\leq x_{n}

\max(p,q)], and, in particular, to study A^{\pm}(p,q,r) we may assume that r>pq . Furthermore, if r^{\prime}\equiv-r\pmod{pq} and r^{\prime}>p,q , then (25) \mathcal{A}_{\{p,q,r^{\prime}\}}=-\mathcal{A}_{\{p,q,r\}}. In an earlier work Kaplan [ 13 ] derived these identities under the assumption that r,r^{\prime}>pq . We end this section with two lemmas which will be used to greatly narrow down the search for coefficients a_{m} such that a_{m}=A^{\pm}(T) . We use \mathcal{N}_{m} to denote the set of all arguments occuring in the sum ( 19 ), that is, (26) \mathcal{N}_{m}\coloneq I_{m}\cup I_{m-q}\cup I_{m-r}\cup I_{m-q-r}, where I_{x}\coloneq(x-p,x]\cap\mathbb{Z} . Lemma 13 . The identity a_{m}=a_{m-pq} holds for every index m such that the range \mathcal{N}_{m} contains no multiples of r . An if \mathcal{N}_{m} contains no multiples of q , then a_{m}=a_{m-pr} . ( Of course, we extended the definition of a_{m} by setting a_{i}=0 for i<0 . ) Proof. This is Lemma 7 in [ 4 ] . ∎ Lemma 14 . If \mathcal{N}_{m} contains exactly two multiples of r , say r\mid l , (27) l\in I_{m}\cup I_{m-q-r}\quad\text{and}\quad l\mp r\in I_{m-r}\cup I_{m-q}, then (28) a_{m}-a_{m-pq}=\chi(l)-\chi(l\mp r). If \mathcal{N}_{m} contains exactly two multiples of q , say q\mid l^{\prime} , (29) l^{\prime}\in I_{m}\cup I_{m-q-r}\quad\text{and}\quad l^{\prime}\mp q\in I_{m-q}\cup I_{m-r}, then (30) a_{m}-a_{m-pr}=\chi(l^{\prime})-\chi(l^{\prime}\mp q). The pair of choices of signs \mp above is unique and corresponds to the inclusion l\mp r,l^{\prime}\mp q\in\mathcal{N}_{m} . Proof. The validity of both of these assertions is contained in the proof of Lemma 8 in [ 4 ] . ∎ 5. Proof of Theorem 3 5.1. Preparation and Reductions We are now ready to focus on the family of polynomials Q_{T} covered by Theorem 3 —polynomials with parameters p,q,r,r^{\prime} satisfying ( 7 ) and ( 8 ). Noting that the congruences rt\equiv 1\pmod{pq} and r^{\prime}t\equiv-1\pmod{pq} imply that r^{\prime}\equiv-r\pmod{pq} , we immediately conclude that ( 9 ) is a consequence of ( 25 ) in Lemma 12 . This reduces the theorem to evaluation of A^{\pm}(p,q,r) for p,q,r satisfying ( 7 ). Furthermore, recalling that Theorem 3 (i) corresponding to the case t=1 is a special case of Theorem 4 (as discussed in Section 2), we make our second reduction leaving us to consider t>1 —Parts (ii-iv)— as we shall assume henceforth. Consider the subranges I_{m} and I_{m-q} of \mathcal{N}_{m} . They are disjoint ( q>p ) and if r\geq p+q , there cannot be more than one multiple of r in I_{m}\cap I_{m-q} , whence there are at most two multiples of r in \mathcal{N}_{m} . Recall that, by ( 24 ), we are free to assume that r>pq , as we do now. Therefore, any range \mathcal{N}_{m} which contains a multiple of r must contain exactly two of them, as given in ( 27 ). We show now that the condition rt\equiv 1\pmod{pq} implies that the same is true for multiples of q : any range \mathcal{N}_{m} which contains a multiple of q must contain exactly two of them, as given in ( 29 ). Indeed, if the number of multiples of q in \mathcal{N}_{m} exceeded two, there would be four of them, one in each of the I -subranges. So consider the possibility that l^{\prime}\in I_{m} and l^{\prime}-r+i\in I_{m-r} are both multiples of q . Then q\mid(i-r) for some i with 0<|i|

\Big\lfloor\frac{l+i}{r}\Big\rfloor=\frac{l}{r}\qquad[0p^{2} . Next we consider the implications of the requirement \chi(l+Q)=0 . By ( 46 ), this means that f(l+Q)>\Big\lfloor\frac{l+Q}{r}\Big\rfloor=aq+\Big\lfloor\frac{\varepsilon_{Q}}{r}\Big\rfloor. But l+Q is a multiple of q , and we conclude that f(l+Q)=\langle a+x_{Q}\rangle_{p}q=(a+x_{Q})q, that is a+x_{Q}

\Big\lfloor\frac{l+Q+i}{r}\Big\rfloor\qquad[|i|aq. Therefor, by ( 65 ), ( 66 ) and ( 45 ), we see that f(l+Q+i)\geq aq+x_{Q}q+it>aq. On the other hand, \Big\lfloor\frac{l+Q+i}{r}\Big\rfloor=aq+\Big\lfloor\frac{\varepsilon_{Q}}{r}\Big\rfloor\leq aq, and ( 64 ) follows. We now address the remaining range \mathcal{R}_{1}(l+Q+R) and show that \chi\equiv 0 here. This takes the form of showing that (67) f(l+Q+R+i)>\Big\lfloor\frac{l+Q+R+i}{r}\Big\rfloor\qquad[|i|aq+\varepsilon_{R}; \displaystyle\bullet\quad \displaystyle f(l+Q+R+i)\geq(a+x_{Q})q+\varepsilon_{R}+it>aq+\varepsilon_{R}; \displaystyle\bullet\quad \displaystyle\Big\lfloor\frac{l+Q+R+i}{r}\Big\rfloor=aq+\varepsilon_{R}+\Big\lfloor\frac{\varepsilon_{Q}}{r}\Big\rfloor\leq aq+\varepsilon_{R}; \displaystyle\bullet\quad ( 67 ) now follows. We are now ready to evaluate S(Q,R;M) . Since l\in I_{M} , M satisfies l\leq M0 ) and put a=\langle a^{\prime}+j\rangle_{p} , so that, by ( 43 ), x_{l}=a . Moreover, by ( 41 ), y_{l}=\langle-\vartheta j\rangle_{q}=q-\vartheta j=\vartheta(p-j)+t=\vartheta b+t, where 0t>\eta_{R}>0 , we see that the second inequality in ( 75 ) is equivalent to the condition b\frac{l}{r}-1 , and we conclude that (79) a+b+x_{Q}l/r, while, by ( 69 ), ( 70 ) and ( 79 ), l/r+x_{Q}q+it=(a+b+x_{Q})q+(p-b+i)t\leq(p-1)q+(p-1)^{2}l/r. But \lfloor\frac{l+Q+i}{r}\rfloor=\frac{l}{r}+\lfloor\frac{\varepsilon_{Q}}{r}\rfloor , and ( 80 ) follows. The situation in the remaining range \mathcal{R}_{2}(l+Q+R) is essentially identical to the range \mathcal{R}_{2}(l+Q) . Indeed, from the preceding argument it is clear that f(l+Q+R+i)\equiv l/r+\varepsilon_{R}+x_{Q}q+it\pmod{pq}, and that l/r+\varepsilon_{R}\frac{l}{r}+\varepsilon_{R}\geq\Big\lfloor\frac{l+Q+R+i}{r}\Big\rfloor, and we conclude that (81) \chi\equiv 0\quad\text{on}\quad\mathcal{R}_{2}(l+Q+R). We are now ready to evaluate S(Q,R;M) . As we already mentioned, the forgoing analysis is applicable since I_{M}\subset\mathcal{R}_{2}(l) . Recall that l-p+b=l^{\prime}\in I_{M} . From this it is plain, by ( 72 ), ( 78 ), ( 80 ) and ( 81 ), that S(Q,R;M)\leq S(Q,R;l)=0, as claimed. ∎ 5.4. Evaluation of S(Q,R;M) : (Case 3) l^{\prime}\in I_{M+Q+R} It remains to evaluate S(Q,R;M) for (Q,R;M)\in\mathcal{M} , with l^{\prime}\in I_{M+Q+R} . This case is more involved than the preceding cases and we split its discussion into two lemmas. Lemma 21 . Let (Q,R;M)\in\mathcal{M} and assume that l^{\prime}\in I_{M+Q+R} , so that ( 37 ) and ( 38 ) read (82) \chi(l)=\chi(l^{\prime})=1\quad\text{and}\quad\chi(l+R)=\chi(l^{\prime}-Q))=0. Then x_{Q},x_{R}>1 , and l and l^{\prime} must be of the form (83) l=aqr+(\vartheta b+\eta_{R}-t)pr\quad\text{and}\quad l^{\prime}=l+Q+R+p+b-x_{R}, where a and b satisfy (84) 0\leq a1 , and l and l^{\prime} are given by ( 83 ), then l and l^{\prime} satisfy ( 82 ), and l\in I_{M} , l^{\prime}\in I_{M+Q+R} and (Q,R;M)\in\mathcal{M} , for every (85) l+p+b-x_{R}\leq ML . To that end we write L^{\prime}=L+B , so that |B|

\frac{L}{r} , since \chi(L^{\prime})=0 . But f(L^{\prime})=f(L+B)\equiv\frac{L}{r}+Bt\pmod{pq}, and we conclude that f(L^{\prime})\geq\frac{L}{r}+Bt . Now, note that: • f(L^{\prime})=x_{L^{\prime}}q\leq pq-q (since y_{L^{\prime}}=0 ), and • L/r+Bt+pq\geq pq-(p-1)^{2}>pq-q . Evidently f(L^{\prime})=L/r+Bt>L/r , so that B>0 , as claimed. Let us note two immediate important consequences of the fact that L^{\prime}>L . The first is that, by ( 43 ), (86) y_{L^{\prime}}=\langle y_{L}-\vartheta B\rangle_{q}=0\implies y_{L}=\vartheta B. The second is the relation (87) x_{L^{\prime}}=\langle x_{L}+B\rangle_{p}=x_{L}+B-p. The last equality here readily follows from ( 86 ) and the equations (88) \displaystyle f(L^{\prime}) \displaystyle=\langle x_{L}+B\rangle_{p}q+\langle y_{L}-\vartheta B\rangle_{q}p=\langle x_{L}+B\rangle_{p}q \displaystyle=\frac{L}{r}+Bt and f(L)=x_{L}q+y_{L}p=\frac{L}{r}+pq. We are now ready to start examining l and its coefficients x_{l} and y_{l} . Firstly, by our hypothesis and ( 15 ), we have l=x_{l}qr+y_{l}pr\quad\text{and}\quad f(l)=x_{l}q+y_{l}p=l/r. Furthermore, \displaystyle f(L) \displaystyle=\langle x_{l}+x_{R}\rangle_{p}q+\langle y_{l}+y_{R}\rangle_{q}p=\frac{L}{r}+pq \displaystyle=\frac{l}{r}+\varepsilon_{R}+pq=(x_{l}+x_{R})q+(y_{l}+y_{R})p, by ( 52 ). We conclude that (89) x_{L}=x_{l}+x_{R}\quad\text{and}\quad y_{L}=y_{l}+y_{R}. Recalling that y_{L}=\vartheta B and y_{R}=q-\vartheta x_{R}-\eta_{R} (see ( 53 )), we deduce the shape of y_{l} : (90) \displaystyle y_{l} \displaystyle=y_{L}-y_{R}=\vartheta(B+x_{R})+\eta_{R}-q \displaystyle=\vartheta(B+x_{R}-p)+\eta_{R}-t=\vartheta b+\eta_{R}-t, where we put b=B+x_{R}-p\ (0 (see ( 53 ) and ( 41 )). This means that ( 90 ) requires b\geq 1 , so that (92) 1\leq b1 , x_{R}>x^{\prime}_{Q}-a\geq x^{\prime}_{Q}-x^{\prime}_{R}+1=x_{R}-x_{Q}+1, and we see that x_{Q}>1 . In the opposite direction, assume that x_{Q},x_{R}>1 . Now let b be any integer satisfying \max(1,x_{R}-x_{Q}+1)\leq b\Big\lfloor\frac{l+R+i}{r}\Big\rfloor, and ( 103 ) follows. Next we consider the range \mathcal{R}_{3}(l+Q+R) . In this range it is more convenient to work with respect to l^{\prime} , which was determined to be of the form l^{\prime}=l+Q+R+p+b-x_{R}=l+R+x^{\prime}_{R}+b+Q in Lemma 21 . To that end, we note that \mathcal{R}_{3}(l+Q+R)=(l^{\prime}-p,l^{\prime}+x_{R}-b)\cap\mathbb{N}. So we wish to evaluate f(l^{\prime}+j) , for -pb-x_{R}+x^{\prime}_{Q}>b-x_{R}. We now come to the range \mathcal{R}_{3}(l+Q) . Our analysis of this range will proceed along familiar lines, but it will require somewhat greater effort than the other ranges. We shall see that there are two cases resulting in different outcomes. Namely, if a-pq it follows that ( 113 ) holds if and only if (121) f(l+Q+i)=l/r-x^{\prime}_{Q}q+it. To deduce the range of i where this equality holds we appeal to ( 118 )-( 120 ) and ( 116 ). We also need to note that b1 . For any of the four possible choices of the pair Q and R , Lemmas 19, 20 and 22 tell us that (130) \max_{(Q,R;M)\in\mathcal{M}}S(Q,R;M)=\max\bigl[\min(x_{R}+1,x^{\prime}_{R},x^{\prime}_{Q}),\min(x^{\prime}_{R}+1,x_{R},x_{Q})\bigr]. Recall the definition of \underline{t} and \underline{s} and observe that, by ( 47 ) and ( 50 ), \underline{t}=\min(x_{Q},x^{\prime}_{Q})\quad\text{and}\quad\underline{s}=\min(x_{R},x^{\prime}_{R}), for every choice of Q and R . Suppose now that \underline{s}<\underline{t} . Then x_{Q},x^{\prime}_{Q}>\min(x_{R},x^{\prime}_{R}) and ( 130 ) gives \max_{(Q,R;M)\in\mathcal{M}}S(Q,R;M)=\max\bigl[\min(x_{R}+1,x^{\prime}_{R}),\min(x^{\prime}_{R}+1,x_{R})\bigr]=s+1 ( Q and R arbitrary). Part (ii) of the theorem now follows by Lemma 16 . Next, observe that, by ( 50 ), x^{\prime}_{Q}=x_{-Q} and x^{\prime}_{R}=x_{-R} , whence \min(x_{R}+1,x^{\prime}_{R},x^{\prime}_{Q})=\min(x^{\prime}_{-R}+1,x_{-R},x_{-Q}) and \min(x^{\prime}_{R}+1,x_{R},x_{Q})=\min(x_{-R}+1,x^{\prime}_{-R},x^{\prime}_{-Q}). Using these identities in ( 130 ) shows that, for any specific pair of Q and R , we have (131) \max_{(Q,R;M)\in\mathcal{M}}S(Q,R;M)=\max_{(Q,R;M)\in\mathcal{M}}S(-Q,-R;M). This identity is handy for the case \underline{s}\geq\underline{t} which we now consider. We make a specific choice of Q and R according to the value of \underline{t} , namely (132) \bigl(Q,R\bigr)=\begin{cases}(q,r),&\text{if }\underline{t}=t\\ (-q,-r),&\text{if }\underline{t}=p-t.\end{cases} Note that for this choice of Q and R , we have x_{Q}=\underline{t}\quad\text{and}\quad x^{\prime}_{Q}\geq x_{R},x^{\prime}_{R}. Then, by ( 39 ), ( 131 ) and ( 130 ) with Q and R given by ( 132 ), we have A^{+}(T)=\max_{(Q,R;M)\in\mathcal{M}}S(Q,R;M)=\min(x_{R}+1,x^{\prime}_{R}). Furthermore, in exactly the same way we obtain, by ( 40 ), -A^{-}(T)=\max_{(Q,R;M)\in\mathcal{M}}S(Q,-R;M)=\min(x_{-R}+1,x^{\prime}_{-R})=\min(x^{\prime}_{R}+1,x_{R}). Using the values of x_{R} , \underline{s} or p-\underline{s} , in these equations yields Parts (iii) and (iv) and completes the proof of the theorem.