Unit Fractions

4 Fourier Analysis

This section contains the part of the proof that uses Fourier analysis to reduce finding solutions to a combinatorial problem involving divisors.

In this section, we write \([A]\) for the lowest common multiple of \(A\) (if \(A\) is a finite set of naturals).

4.1 Local definitions

Definition 4.1
#

For any finite set \(A\) of natural numbers and integer \(k\geq 1\) we write \(F(A;k)\) for the count of the number of subsets \(S\subset A\) such that \(kR(S)\) is an integer.

Definition 4.2
#

Let \(J(A) = (-[A]/2,[A]/2]\cap \mathbb {Z}\backslash \{ 0\} \).

Definition 4.3
#

For any finite set of naturals \(B\) and integer \(t\), we define \(C(B;t) = \prod _{n\in B}\left\lvert \cos (\pi t/n)\right\rvert \).

Definition 4.4
#

For any finite set of naturals \(A\) and integer \(k\geq 1\), and real \(K{\gt}0\), we define the ‘major arc’ corresponding to \(t\in \mathbb {Z}\) as

\[ \mathfrak {M}(t;A,k,K) = \{ h\in J(A): \left\lvert h-t[A]/k\right\rvert \leq K/2k\} \]

Let \(\mathfrak {M}(A,k,K) = \cup _{t\in \mathbb {Z}}\mathfrak {M}(t;A,k,K)\).

Definition 4.5
#

Let \(I_h(K,k)\) be the interval of length \(K\) centred at \(kh\), and let \(\mathfrak {m}_1(A,k,K,\delta )\) be those \(h\in J(A)\backslash \mathfrak {M}(A,k,K)\) such that

\[ \# \{ n\in A : \textrm{no element of }I_h(K,k)\textrm{ is divisible by }n\} \geq \delta . \]

Let \(\mathfrak {m}_2(A,k,K,\delta )\) be the rest of \(J(A)\backslash \mathfrak {M}(A,k,K)\).

4.2 Precursor general lemmas

Lemma 4.6
#

For any \(n,m\in \mathbb {N}\), if \(e(x) = e^{2\pi ix}\), then if \(I\) is any set of \(m\) consecutive integers then

\[ 1_{m\mid n}=\frac{1}{m}\sum _{h\in I}e(h n/m). \]

Proof

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

\[ e(n/m)S = \sum _{h\in I}e((h+1)n/m). \]

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

\[ e((s+1)n/m)-e(rn/m) = e(rn/m+n)-e(rn/m)=e(rn/m)e(n)-e(rn/m)=0, \]

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

Lemma 4.7
#

Let \(A\) be a finite set of natural numbers not containing \(0\). If

\[ \mathcal{P}_A = \{ p \textrm{ prime}: \exists n\in A : p \mid n\} \]

and for all \(p\in \mathcal{P}_A\) then \(r_p\geq 0\) is the greatest integer such that \(p^{r_p}\) divides some \(n\in A\), then

\[ [A]=\prod _{p\in \mathcal{P}_A}p^{r_p}. \]
(NOTE: This is a generally useful fact when working with lowest common multiples, perhaps this should be in mathlib somewhere.)

Proof

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.

Lemma 4.8
#

If \(A\) is a finite set of natural numbers not containing \(0\) such that if \(q\in \mathcal{Q}_A\) then \(q\leq X\), then \([A]\leq e^{O(X)}\).

Proof

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

\[ [A]\leq X^{O(X/\log X)}=e^{O(X)}. \]

Lemma 4.9
#

If \(x\in [0,1/2]\) then

\[ \cos (\pi x) \leq e^{-2x^2}. \]

Proof

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

\[ \cos (\pi x)^2 = 1-\sin (\pi x)^2\leq 1-4x^2. \]

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

\[ \cos (\pi x) \leq e^{-2x^2}. \]

Lemma 4.10
#

Let \(A\) be a finite set of naturals not containing \(0\). For any \(n\in A\), let \(\mathcal{Q}_A(n)\) denote all those \(q\in \mathcal{Q}_A\) such that \(n\in A_q\), then

\[ \left\lvert \mathcal{Q}_A(n)\right\rvert \leq \tfrac {1}{\log 2}\log n. \]

Proof

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.

4.3 Towards the main proposition

Lemma 4.11
#

If \(A\) is a finite set of natural numbers not containing \(0\) and \(k\geq 1\) is an integer then

\[ F(A;k)= \frac{1}{[A]}\sum _{-[A]/2{\lt} h\leq [A]/2}\prod _{n\in A}(1+e(kh/n)). \]

Proof

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

\[ 1_{k\sum _{n\in S}\frac{1}{n}\in \mathbb {Z}}=1_{[A]\mid k\sum _{n\in S}\frac{[A]}{n}} = \frac{1}{[A]}\sum _{h\in I}e(kh\sum _{n\in S}\frac{1}{n}). \]

Therefore, changing summation,

\[ F(A;k) = \sum _{S\subset A}1_{k\sum _{n\in S}\frac{1}{n}\in \mathbb {Z}} = \frac{1}{[A]} \sum _{h\in I}\sum _{S\subset A}\prod _{n\in S}e(kh/n). \]

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}\)

\[ \sum _{J\subset I}\prod _{j\in J}x_j = \prod _{i\in I}(1+x_i). \]

Lemma 4.12
#

If \(k\geq 1\) is an integer and \(A\) is a finite set of natural numbers such that there is no \(S\subset A\) such that \(R(S)=1/k\), and \(R(A){\lt}2/k\), then

\[ \sum _{-[A]/2{\lt} h\leq [A]/2}\Re \left( \prod _{n\in A}(1+e(kh/n))\right)= [A]. \]

Proof

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

\[ 1=\frac{1}{[A]}\sum _{-[A]/2{\lt} h\leq [A]/2}\prod _{n\in A}(1+e(kh/n)). \]

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

Lemma 4.13
#

If \(k\geq 1\) is an integer and \(A\) is a finite set of natural numbers such that there is no \(S\subset A\) such that \(R(S)=1/k\), and \(R(A){\lt}2/k\), and \([A]\leq 2^{\left\lvert A\right\rvert -1}\) then

\[ \sum _{h\in J(A)}\Re \left( \prod _{n\in A}(1+e(kh/n))\right)\leq -2^{\left\lvert A\right\rvert -1}. \]

Proof

By Lemma 4.12

\[ \sum _{-[A]/2{\lt} h\leq [A]/2}\Re \left( \prod _{n\in A}(1+e(kh/n))\right)= [A]. \]

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

When \(h=0\)

\[ \Re \left( \prod _{n\in A}(1+e(kh/n))\right)= \Re \left( \prod _{n\in A}2\right)=2^{\left\lvert A\right\rvert }. \]

Therefore

\[ \sum _{h\in J(A)}\Re \left( \prod _{n\in A}(1+e(kh/n))\right)+2^{\left\lvert A\right\rvert }\leq 2^{\left\lvert A\right\rvert -1}, \]

and the result follows after rearranging.

Lemma 4.14
#

If \(A\) is a finite set of integers and \(K\) is a real such that \([A]{\gt}K\) then, for any integer \(k\geq 1\), the sets \(\mathfrak {M}(t;A,k,K)\) are disjoint for distinct \(t\in \mathbb {Z}\).

Proof

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

\[ \left\lvert hk-t_1[A]\right\rvert \leq K/2 \]

and

\[ \left\lvert hk-t_2[A]\right\rvert \leq K/2, \]

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.

Lemma 4.15
#

For any finite set of natural numbers \(A\) and \(\theta \in \mathbb {R}\)

\[ \Re \left( \prod _{n\in A}(1+e(\theta /n))\right)=2^{\left\lvert A\right\rvert }\cos (\pi \theta R(A))\prod _{n\in A}\cos (\pi \theta /n). \]

Proof

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

\[ \Re \left( \prod _{n\in A}(1+e(\theta /n))\right) = \Re \left( 2^{\left\lvert A\right\rvert }e(\theta R(A)/2)\prod _{n\in A}\cos (\pi \theta /n)\right). \]

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.

Lemma 4.16
#

Let \(M\geq 1\) and \(A\) a finite set of naturals such that \(n\geq M\) for all \(n\in A\). Let \(K\) be a real such that \(K{\lt}M\). Let \(k\geq 1\) be an integer which divides \([A]\). Suppose that \(kR(A) \in [2-k/M,2)\).

\[ \sum _{h\in \mathfrak {M}(A,k,K)}\Re \left( \prod _{n\in A}(1+e(kh/n))\right) \geq 0. \]

Proof

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

\[ J_t =[-K/2k,K/2k]\cap (J(A)-t[A]/k), \]

then

\[ \sum _{h\in \mathfrak {M}(t)}\Re \left( \prod _{n\in A}(1+e(kh/n))\right)=\sum _{r\in J_t}\Re \left( \prod _{n\in A}(1+e((t[A]+rk)/n))\right)=\sum _{r\in J_t}\Re \left( \prod _{n\in A}(1+e(rk/n))\right), \]

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

Using Lemma 4.15, this is

\[ 2^{[A]}\sum _{h\in \mathfrak {M}(t)}\cos (\pi krR(A))\prod _{n\in A}\cos (\pi kr/n). \]

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,

\[ \sum _{h\in \mathfrak {M}(A,k,K)}\Re \left( \prod _{n\in A}(1+e(kh/n))\right) =\sum _{r\in [-K/2k,K/2k]\cap \mathbb {Z}}\left( \sum _{t\in \mathbb {Z}}1_{r\in J_t}\right)\cos (\pi krR(A))\prod _{n\in A}\cos (\pi kr/n). \]

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)

\[ \cos (\pi kr R(A)) = \cos (-\pi r\epsilon )\geq 0, \]

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

\[ \left( \sum _{t\in \mathbb {Z}}1_{r\in J_t}\right)\cos (\pi krR(A))\prod _{n\in A}\cos (\pi kr/n)\geq 0 \]

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.

Lemma 4.17
#

Let \(M\geq 1\) and \(A\) a finite set of naturals such that \(n\geq M\) for all \(n\in A\). Let \(K\) be a real such that \(K{\lt}M\). Let \(k\geq 1\) be an integer which divides \([A]\). Suppose that \(kR(A) \in [2-k/M,2)\), and there is no \(S\subset A\) such that \(R(S)=1/k\), and \([A]\leq 2^{\left\lvert A\right\rvert -1}\). Then

\[ \sum _{h\in J(A)\backslash \mathfrak {M}(A,k,K)} C(A;hk)\geq 1/2. \]

Proof

By Lemma 4.13

\[ \sum _{h\in J(A)}\Re \left( \prod _{n\in A}(1+e(kh/n))\right)\leq -2^{\left\lvert A\right\rvert -1}. \]

By Lemma 4.16

\[ \sum _{h\in \mathfrak {M}(A,k,K)}\Re \left( \prod _{n\in A}(1+e(kh/n))\right) \geq 0. \]

Therefore

\[ \sum _{h\in J(A)\backslash \mathfrak {M}(A,k,K)}\Re \left( \prod _{n\in A}(1+e(kh/n))\right)\leq -2^{\left\lvert A\right\rvert -1}. \]

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 )\),

\[ \sum _{h\in J(A)\backslash \mathfrak {M}(A,k,K)}\left\lvert \cos (\pi kh/n)\right\rvert \geq 1/2 \]

as required.

Lemma 4.18
#

For any finite set \(A\) such that \(n\leq N\) for all \(n\in A\), and integer \(t\), if \(t\equiv t_n\pmod{n}\) for \(\left\lvert t_n\right\rvert \leq n/2\) for all \(n\in A\), then

\[ C(A;t)\leq \exp \left( -\frac{2}{N^2}\sum _{n\in A}t_n^2\right). \]

Proof

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

\[ \left\lvert \cos (\pi t/n)\right\rvert \leq \exp (-2t_n^2/n^2)\leq \exp (-\tfrac {2}{N^2}t_n^2), \]

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

Lemma 4.19
#

Suppose that \(N\) is sufficiently large and \(M\geq 8\). Let \(T{\gt}0\) be a real and \(k\geq 1\) be an integer. Let \(A\subset [M,N]\) be a set of integers such that if \(q\in \mathcal{Q}_A\) then \(q\leq \frac{TK^2}{N^2 \log N}\). Then

\[ \sum _{h\in \mathfrak {m}_1(A,k,K,T)} C(A;hk)\leq 1/8. \]

Proof

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

\[ C(A;hk)\leq 1/[A]^2. \]

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,

\[ C(A;hk)\leq \exp \left( -\frac{2}{N^2}\sum _{n\in A}h_n^2\right), \]

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

\[ C(A;h)\leq \exp \left( -\frac{K^2T}{2N^2}\right). \]

It remains to note that by Lemma 4.8

\[ [A]\leq \exp \left( O\left( \frac{K^2T}{N^2\log N}\right)\right)\leq \exp \left( \frac{K^2T}{4N^2}\right) \]

assuming \(N\) is sufficiently large.

Lemma 4.20
#

Suppose that \(N\geq 4\). Let \(A\subset [1,N]\) be a finite set of integers and \(t\) an integer. Let \(K,L{\gt}0\) be reals and suppose that \(q\leq \tfrac {1}{16}LK^2/N^2(\log N)^2\) for all \(q\in \mathcal{Q}_A\). Let \(\mathcal{D}=\mathcal{D}_I(A;L)\) where \(I\) is the interval of length \(K\) centred at \(t\). Then

\[ C(A;t)\leq N^{-4\left\lvert \mathcal{Q}_A\backslash \mathcal{D}\right\rvert }. \]

Proof

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\),

\[ \prod _{n\in A}x_n=\prod _{n\in A}\prod _{q\in \mathcal{Q}(n)}x_n^{1/\left\lvert \mathcal{Q}(n)\right\rvert } =\prod _{q\in \mathcal{Q}}\prod _{n\in A_q}x_n^{1/\left\lvert \mathcal{Q}(n)\right\rvert }. \]

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\),

\[ \prod _{n\in A}x_n\leq \prod _{q\in \mathcal{Q}}\prod _{n\in A_q}x_n^{1/2\log N}=\prod _{q\in \mathcal{Q}}\left( \prod _{n\in A_q}x_n\right)^{1/2\log N}. \]

In particular,

\[ C(A;t)\leq \prod _{q\in \mathcal{Q}}C(A_q;t)^{/2\log N}. \]

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

\[ C(A_q;t)\leq \exp \left( -\frac{2}{N^2}\cdot \frac{L}{q}\cdot \frac{K^2}{4}\right). \]

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

Lemma 4.21

Let \(N\) be a sufficiently large integer. Let \(K,L{\gt}0\) be reals such that \(0{\lt}K\leq N\). Let \(T{\gt}0\) be any real. Let \(k\) be an integer such that \(1\leq k \leq N/64\). Let \(A\subset [1,N]\) be a finite set of integers such that

  1. if \(q\in \mathcal{Q}_A\) then \(q\leq \tfrac {1}{16}\frac{LK^2}{N^2(\log N)^2}\), and

  2. for any interval \(I\) of length \(K\), either

    1. \[ \# \{ n\in A : \textrm{no element of }I\textrm{ is divisible by }n\} \geq T, \]

      or

    2. there is some \(x\in I\) divisible by all \(q\in \mathcal{D}_I(A;L)\).

Then

\[ \sum _{h\in \mathfrak {m}_2(A,k,K,T)}C(A;hk)\leq 1/8. \]

Proof

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

\[ Kk\frac{[A]}{[\mathcal{D}]} +K^2\leq Kk\prod _{q\in \mathcal{Q}\backslash \mathcal{D}}q+K^2\leq kN^{\left\lvert \mathcal{Q}\backslash \mathcal{D}\right\rvert +1}+K^2. \]

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,

\[ \sum _{h\in \mathfrak {m}_2}1_{\mathcal{D}_{I_h}(A;L)=\mathcal{D}}\leq 2kN^{\left\lvert \mathcal{Q}\backslash \mathcal{D}\right\rvert +1}. \]

(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,

\[ \sum _{h\in \mathfrak {m}_2}1_{\mathcal{D}_{I_h}(A;L)=\mathcal{D}}C(A;hk)\leq 2kN^{1-3\left\lvert \mathcal{Q}_A\backslash \mathcal{D}\right\rvert }. \]

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\))

\begin{align*} \sum _{h\in \mathfrak {m}_2}C(A;h,k) & \leq \frac{2k}{N}\sum _{\mathcal{D}\subseteq \mathcal{Q}}N^{-\left\lvert \mathcal{Q}\backslash \mathcal{D}\right\rvert }\\ & = \frac{2k}{N}(1+1/N)^{\left\lvert \mathcal{Q}\right\rvert }\\ & \leq 8k/N \leq 1/8. \end{align*}

Proposition 4.22
#

There exists a constant \(c{\gt}0\) such that the following holds. Suppose that \(N\) is sufficiently large. Let \(K,L,M,T\) be reals such that \(T,L{\gt}0\) and \(8\leq K{\lt}M\leq N\), and let \(k\) be an integer such that \(1\leq k\leq M/64\). Let \(A\subset [M,N]\) be a set of integers such that

  1. \(R(A)\in [2/k-1/M,2/k)\),

  2. \(k\) divides \([A]\),

  3. if \(q\in \mathcal{Q}_A\) then \(q\leq c\min \left( M/k,\frac{LK^2}{N^2(\log N)^2},\frac{TK^2}{N^2\log N}\right)\), and

  4. for any interval \(I\) of length \(K\), either

    1. \[ \# \{ n\in A : \textrm{no element of }I\textrm{ is divisible by }n\} \geq T, \]

      or

    2. there is some \(x\in I\) divisible by all \(q\in \mathcal{D}_I(A; L)\).

There is some \(S\subset A\) such that \(R(S)=1/k\).

Proof

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.