If \(m\mid n\) then \(n/m\) is an integer, so \(e(hn/m)=1\) for all \(h\in \mathbb {Z}\), so the right-hand side is \(1\).

If \(m\nmid n\) then \(e(n/m)\neq 1\). Let \(S=\sum _{h\in I}e(hn/m)\), so it suffices to show that \(S=0\). Using \(e(x+y)=e(x)e(y)\) we have

If \(r=\min (I)\) and \(s=\max (I)\) then the right-hand side is \(S + e((s+1)n/m)-e(rn/m)\). But since \(I\) is a set of \(m\) consecutive integers we know that \(s=r+m-1\), and so

since \(e(n)=1\). Therefore \(e(n/m)S=S\), and hence since \(e(n/m)\neq 1\), this forces \(S=0\) as required.

We first note that if \(p\mid [A]\) then \(p\in \mathcal{P}_A\). If not, suppose \(p\not\in \mathcal{P}_A\) and \(p\mid [A]\). Let \(M=[A]/p\). We claim every \(n\in A\) divides \(M\), contradicting the definition of lowest common multiple. It suffices to show that if a prime power \(q^r\mid n\) then \(q\mid M\). But we know \(q^r\mid [A]=Mp\), and \((q^r,p)=1\), so \(q\mid M\) as required.

By the fundamental theorem of arithmetic, we can write \([A] = \prod _{p\in \mathcal{P}_A}p^{s_p}\) for some integers \(s_p\geq 0\). It remains to show that \(s_p=r_p\).

That \(s_p\geq r_p\) follows from the fact that \(p^{r_p}\mid n\) for some \(n\in A\) by definition, hence \(p^{r_p}\mid [A]\), hence \(r_p\leq s_p\).

Suppose that \(s_p{\gt}r_p\), and as above consider \(M=[A]/p\). We claim every \(n\in A\) divides \(M\), the required contradiction. If a prime power \(q^r\mid n\) with \(q\neq p\) then \(q\mid Mp\) hence \(q\mid M\). If \(p^r\mid n\) then \(r\leq r_p\), so \(p^r\mid p^{r_p}\mid p^{s_p-1}\mid M\), as required.

We have \([A]=\prod _{p\in \mathcal{P}_A}p^{r_p}\), where \(p^{r_p}\in \mathcal{Q}_A\), by Lemma 4.7. By hypothesis \(p^{r_p}\leq X\) and so \([A]\leq X^{\left\lvert \mathcal{P}_A\right\rvert }\). The set \(\mathcal{P}_A\) is a subset of all primes \(\leq X\), and so \(\left\lvert \mathcal{P}_A\right\rvert \leq \pi (X)\ll X/\log X\) by Chebyshev’s estimate Lemma 2.4. Therefore

We have Jordan’s inequality, which says \(\sin (\pi x)\geq 2x\) for all \(x\in [0,1/2]\). Therefore

Since \(1-y\leq e^{-y}\) for all \(y\geq 0\), the right-hand side is \(\leq e^{-4x^2}\). Taking square roots, and using \(\cos (\pi x)\geq 0\) for all \(x\in [0,1/2]\), yields

The first step is to show that \(\prod _{q\in \mathcal{Q}(n)}q\mid n\) (in fact they’re equal, but all we need is the one direction). This can be shown by showing that every \(q\in \mathcal{Q}(n)\) divides \(n\), since \(n\in A_q\) implies \(q\mid n\), and then noting that any two distinct \(q_1,q_2\in \mathcal{Q}(n)\) are coprime. If not, then since they are prime powers, they must both be powers of the same prime, say \(q_1=p^{r_1}{\lt} q_2=p^{r_2}\). Since \(n\in A_{q_2}\) we have \(p^{r_2}\mid n\), but then \(p\mid n/q_1\), so \(p\mid (q_1,n/q_1)\), and so \(n\not\in A_{q_1}\).

Therefore \(\prod _{q\in \mathcal{Q}(n)}q\leq n\). Since all prime powers are \(\geq 2\) it follows that \(2^{\left\lvert \mathcal{Q}(n)\right\rvert }\leq n\), and the result follows taking logarithms.

For any \(S\subset A\), \(k\sum _{n\in S}\frac{1}{n}\in \mathbb {Z}\) if and only if \(k\sum _{n\in S}\frac{[A]}{n}\in [A]\cdot \mathbb {Z}\). By definition \(n\mid [A]\) for all \(n\in A\), and so \(k\sum _{n\in S}\frac{[A]}{n}\) is an integer. It is \(\geq 0\) since each summand is. Therefore by Lemma 4.6, if \(I\) is any set of \([A]\) consecutive integers

Therefore, changing summation,

The lemma now follows choosing \(I=(-[A]/2,[A]/2]\cap \mathbb {Z}\), and using the general fact that for any indexed set of complex numbers \((x_i)_{i\in I}\)

For any \(S\subset A\) we have \(k\sum _{n\in S}\frac{1}{n}\leq kR(A){\lt}2\), and therefore if \(k\sum _{n\in S}\frac{1}{n} \in \mathbb {N}\) then \(k\sum _{n\in S}\frac{1}{n} =0\) or \(=1\). The latter can’t happen by assumption, so \(k\sum _{n\in S}\frac{1}{n} =0\). A non-empty sum of \({\gt}0\) summands is \({\gt}0\), so if \(k\sum _{n\in S}\frac{1}{n}\in \mathbb {Z}\) then \(S=\emptyset \). Therefore \(F(A;k)=1\).

By Lemma 4.11 therefore

The conclusion follows multiplying both sides by \([A]\) and taking real parts of both sides.

By Lemma 4.12

By assumption the right-hand side is \(\leq 2^{\left\lvert A\right\rvert -1}\).

When \(h=0\)

Therefore

and the result follows after rearranging.

Suppose not and \(h\in \mathfrak {M}(t_1)\cap \mathfrak {M}(t_2)\). By definition,

and

and so by the triangle inequality \([A]\left\lvert t_1-t_2\right\rvert \leq K\). Since \(t_1\neq t_2\), we know \(\left\lvert t_1-t_2\right\rvert \geq 1\), and so \([A]\leq K\), contradicting the assumption.

Rewrite each factor in the product using \(1+e(\theta /n)=2e(\theta /2n)\cos (\pi \theta /n)\), so

Taking out real factors, this is \(2^{\left\lvert A\right\rvert }\prod _{n\in A}\cos (\pi \theta /n)\Re e(\theta R(A)/2)\), and the claim follows.

Since \(k\) divides \([A]\), we know that \(t[A]/k\) is an integer for any \(t\in \mathbb {Z}\), and hence by definition of \(\mathfrak {M}(t)\) we can write \(h=t[A]/k+r\), where \(r\) is an integer satisfying \(\left\lvert r\right\rvert \leq K/2k\). Therefore, letting

then

since \(t[A]/n\) is always an integer, by definition of \([A]\).

Using Lemma 4.15, this is

Since \([A]\geq \min (A)\geq M{\gt}K\), the hypotheses of Lemma 4.14 are all met, and so \(\mathfrak {M}\) is the disjoint union of \(\mathfrak {M}(t)\) as \(t\) ranges over \(t\in \mathbb {Z}\). Therefore \(1_{h\in \mathfrak {M}}=\sum _t 1_{h\in \mathfrak {M}(t)}\), and therefore using the above and rearranging the sum,

Since for all \(n\in A\) we have \(n\geq M{\gt}K\) we have \(\left\lvert kr/n\right\rvert {\lt} 1/2\) for all \(r\) with \(\left\lvert r\right\rvert \leq K/2k\), and hence \(\cos (\pi kr/n)\geq 0\) for all such \(n\) and \(r\).

Furthermore, writing \(kR(A)=2-\epsilon \) for some \(0{\lt}\epsilon \leq k/M\), we have (since \(r\) is an integer)

since \(\left\lvert r\epsilon \right\rvert \leq K/2M{\lt}1/2\) for all \(\left\lvert r\right\rvert \leq K/2k\). It follows that

for all \(r\in [-K/2k,K/2k]\cap \mathbb {Z}\), and hence as the sum of non-negative summands the original sum is non-negative as required.

By Lemma 4.13

By Lemma 4.16

Therefore

By the triangle inequality, using \(\left\lvert \Re z\right\rvert \leq \left\lvert z\right\rvert \) and \(\left\lvert 1+e(\theta )\right\rvert =2\cos (\pi \theta )\),

as required.

We first note that \(\left\lvert \cos (\pi t/n)\right\rvert =\left\lvert \cos (\pi t_n/n)\right\rvert \) for all \(n\in A\), by periodicity of cosine. By Lemma 4.9, therefore

and the lemma follows taking the product over all \(n\in A\).

We show in fact that for any \(h\in \mathfrak {m}_1(A,k,K,T)\) we have

The result then immediately follows since \(\left\lvert \mathfrak {m}_1(A,k,K,T)\right\rvert \leq \left\lvert J(A)\right\rvert \leq [A]\), assuming \([A]\geq 8\), which is true since \([A]\geq \min (A)\geq M\geq 8\).

By Lemma 4.18,

where \(kh\equiv h_n\pmod{n}\) and \(\left\lvert h_n\right\rvert \leq n/2\). Let \(I_h\) be the interval of length \(K\) centred around \(kh\). If no element of \(I_h\) is divisible by \(n\) then \(\left\lvert h_n\right\rvert {\gt}K/2\). Therefore, by definition of \(\mathfrak {m}_1\), \(\left\lvert h_n\right\rvert {\gt}K/2\) for at least \(T\) many \(n\in A\), and hence \(\sum _{n\in A}h_n^2\geq K^2T/4\), and so

It remains to note that by Lemma 4.8

assuming \(N\) is sufficiently large.

For any \(n\in A\), let \(\mathcal{Q}(n)\) denote all those \(q\in \mathcal{Q}\) such that \(n\in A_q\). Therefore, for any real \(x_n\geq 0\),

By Lemma 4.10 for any \(n\in A\) we have \(\left\lvert \mathcal{Q}(n)\right\rvert \leq \tfrac {1}{\log 2}\log n\leq 2\log N\), and so if \(0\leq x_n\leq 1\),

In particular,

Using the trivial bound \(C(A_q;t)\leq 1\), to prove the lemma it therefore suffices to show that for every \(q\in \mathcal{Q}\backslash \mathcal{D}_h\) we have \(C(A_q;t)\leq N^{-8\log N}\).

For any \(n\in A\) let \(t\equiv t_n\pmod{n}\), where \(\left\lvert t_n\right\rvert \leq n/2\). For any \(q\in \mathcal{Q}\backslash \mathcal{D}\) there are, by definition of \(\mathcal{D}\), at least \(L/q\) many \(n\in A_q\) such that \(n\) divides no element of the interval of length \(K\) centred at \(t\).

Recall that \(t_n\) is the integer in \((-n/2,n/2]\) such that \(t\equiv t_n\pmod{n}\), so that \(n\) divides \(t-t_n\). If \(\left\lvert t_n\right\rvert \leq K/2\) then \(t-t_n\) is in the interval of length \(K\) centred at \(t\), which contradicts the previous paragraph. Therefore \(\left\lvert t_n\right\rvert {\gt}K/2\). Hence by Lemma 4.18

By assumption, \(q\leq LK^2/16N^2(\log N)^2\), and the proof is complete.

For any \(h\in \mathfrak {m}_2\), let \(I_h\) be the interval of length \(K\) centred at \(kh\). Since \(h\not\in \mathfrak {m}_1\), condition 2(a) cannot hold, and therefore there is some \(x\in I_h\) divisible by all \(q\in \mathcal{D}_{I_h}(A;L)\). In particular, \(kh\) is distance at most \(K/2\) from some multiple of \([\mathcal{D}_{I_h}(A;L)]\). Since \(h\in \mathfrak {m}(A,k,K,T)\), we know \(h\not\in \mathfrak {M}(A,k,K)\), and hence \(kh\) is distance greater than \(K/2\) from any multiple of \([A]\). Since \([\mathcal{Q}]=[A]\), it follows that \(\mathcal{D}_{I_h}(A;L)\neq \mathcal{Q}\).

Furthermore, for any \(\mathcal{D}\subset \mathcal{Q}\), the number of \(h\in \mathfrak {m}_2\) with \(\mathcal{D}_{I_h}(A;L)=\mathcal{D}\) is at most \(K\) times the number of multiples of \([\mathcal{D}]\) in \([1,k[A]+K]\). The number of multiples of \([\mathcal{D}]\) in \([1,k[A]+K]\) is at most \((k[A]/[\mathcal{D}])+K\), and hence the number of \(h\in \mathfrak {m}_2\) with \(\mathcal{D}_{I_h}(A;L)=\mathcal{D}\) is at most

In particular, when \(\mathcal{D}\neq \mathcal{Q}\), the right-hand side is at most \(2kN^{\left\lvert \mathcal{Q}\backslash \mathcal{D}\right\rvert +1}\), that is,

(Here we have used the fact that \([A]\leq [D]\prod _{q\in \mathcal{Q}\backslash \mathcal{D}}q\), which is true because every prime power dividing \([A]\) is in \(\mathcal{Q}\), and hence either divides \([D]\) or divides \(\prod _{q\in \mathcal{Q}\backslash \mathcal{D}}q\).)

Therefore, for any \(\mathcal{D}\subset \mathcal{Q}\), using Lemma 4.20,

Since \(\mathcal{D}\neq \mathcal{Q}\), this is at most \(2kN^{-1-\left\lvert \mathcal{Q}\backslash \mathcal{D}\right\rvert }\).

Therefore (using the trivial estimate \(\left\lvert \mathcal{Q}\right\rvert \leq N\))

If the conclusion fails, there is an immediate contradiction by combining Lemmas 4.17, 4.19 and 4.21. The only hypothesis that is not immediate to check is the upper bound \([A]{\lt}2^{\left\lvert A\right\rvert -1}\). This follows since \(\lvert A\rvert \geq MR(A)\geq \frac{2}{k}M-1\geq M/k\), and by Lemma 4.8 we have \([A]\leq e^{O(cM/k)}\), which is at most \(2^{\left\lvert A\right\rvert /2}\) assuming \(c\) is sufficiently small.