Deducing Asymptotic Behaviour of a(x)

This page contains explanations pertaining to the "Deducing Asymptotic Behaviour of a(x)" section of Roth's paper.

### Rewriting delta and lower bounding b squared

We can write $\delta$ as $\frac{b(x)}{2c_1}$ and then, noting from an earlier Lemma that $b(x) \leq 1$ we have $c_1 \{ b(x) \delta + b^2(x) \delta^2 \} \leq b^2(x) \left\{ \frac{1}{2} + \frac{1}{4 c_1} \right\} < \frac{3}{4} b^2(x)$.

We know that $\delta$ is $(N\eta)^{-1}$. We can pick any $c_1$ larger than an absolute lower bound $\widetilde{c_1} > 1$ defined by the asymptotic notation. As $N$ and $b(x)$ are both very large and increasing, we can certainly assume $\widetilde{c_1} < \frac{b(x)N}{4}$ so that it is simple to pick a $c_1 > \widetilde{c}$ and $\eta < \frac{1}{2}$ such that

(1)
\begin{align} c_1 = \frac{b(x) N \eta}{2} = \frac{b(x)}{2 \delta}. \end{align}

Knowing that $\delta = \frac{b(x)}{2 c_1}$ we also know that $b(x) = a(m)$ so that by Lemma 12 we have

(2)
\begin{align} \frac{1}{2^{4^x}} = \frac{1}{m} \leq b(x) \leq 1. \end{align}

Now we rewrite the left hand side of the inequality in a simpler form

(3)
\begin{align} c_1 \{ b(x) \delta + b^2(x) \delta^2 \} = \frac{b(x)}{2 \delta} \{ b(x) \delta + b^2(x) \delta^2 \} = \frac{b^2(x)}{2} + b^2(x) \left( \frac{b(x) \delta}{2} \right). \end{align}

Now we know from Equation 2 that $b(x) < 1$ so that

(4)
\begin{align} b(x) < \frac{1}{b(x)} \end{align}

and so

(5)
\begin{align} \frac{b(x) \delta}{2} < \frac{\delta}{2 b(x)} = \frac{2 \delta}{4 b(x)} = \frac{1}{4 c_1}. \end{align}

Substituting back into 3 we get

(6)
\begin{align} \leq \frac{b^2(x)}{2} + b^2(x) \frac{1}{4 c_1} = b^2(x) \left( \frac{1}{2} + \frac{1}{4c_1} \right). \end{align}

Finally, we have the trivial assumption that $c_1 > 1$ so that $\frac{1}{4c_1} < \frac{1}{4}$ and applying to Equation 6 we have

(7)
\begin{align} b^2(x) \left( \frac{1}{2} + \frac{1}{4 c_1} \right) < \frac{3}{4} b^2(x); \end{align}

which is what was required.

We now use the definition that $\delta = (N \eta)^{-1}$ and and earlier Lemma to show $\eta = \frac{1}{N \delta} = \frac{c_2}{m^4 a(m)} < \frac{c_2}{m^3}$ so that [[0 < \eta < \frac{1}{2}$]] for large$x. We start from an earlier Lemma, to get (8) \begin{align} 1 \leq \frac{1}{a(m)} \leq m. \end{align} Now we simply do some algebraic manipulation: (9) \begin{eqnarray} \eta = \frac{1}{N \delta} &=& \frac{2}{m^4} \cdot \frac{2 c_1}{b(x)}\\ &=& \frac{4 c_1}{m^4 a(m)}\\ &\leq& \frac{4 c_1}{m^4} \cdot m = \frac{4 c_1}{m^3}. \end{eqnarray} We then simply definec_2$to be$4c_1$and the result follows. Finally, for large$x$, we have very large$m$and so$\eta$is small, and certainly between$0$and$\frac{1}{2}$. ### Upper bounding b squared We now use the previous lemmata to see that we have$b^2(x) < c_3 \left( b(x) - b(x+1) + \frac{1}{2^{4^x}} \right)$for$x > c_4. From our previous work we have (10) \begin{align} b^2(x) < c_1 \left\{ b(x) \delta + b^2(x) \delta^2 \right\} + c_1 \left\{ \left( \frac{b(x)}{\delta} + 1 \right) \left( b(x) - b(x+1) + \frac{1}{2^{4^x}} \right) \right\}. \end{align} We now use our earlier bound to get (11) \begin{align} b^2(x) < \frac{3}{4} b^2(x) + c_1 \left\{ \left( \frac{b(x)}{\delta} + 1 \right) \left( b(x) - b(x+1) + \frac{1}{2^{4^x}} \right) \right\} \end{align} and so collecting theb^2(x)terms we have (12) \begin{align} b^2(x) < 4c_1 \left\{ \left( \frac{b(x)}{\delta} + 1 \right) \left( b(x) - b(x+1) + \frac{1}{2^{4^x}} \right) \right\}. \end{align} But then from our earlier bound we also have (13) \begin{align} \delta = \frac{b(x)}{2 c_1} \end{align} and so our inequality becomes (14) \begin{eqnarray} b^2(x) &<& 4c_1 \left\{ (2c_1 + 1) \left( b(x) - b(x+1) + \frac{1}{2^{4^x}} \right) \right\}\\ &=& c_3 \left( b(x) - b(x+1) + \frac{1}{2^{4^x}} \right). \end{eqnarray} (wherec_3 = 8{c_1}^2 + 4c_1$) for large$x$, that is$x > c_4$for some absolute constant$c_4$. ### b is decreasing and bounding Pb^2(2P) First,$b(x)$is a decreasing function by an earlier Corollary. This gives, for all integers$P > c_4$, the following string of inequalities:$P b^2(2P) \leq \sum_{x=P}^{2P-1} b^2(x) < c_5 \left( b(P) - b(2P) + \frac{4c_5}{2P} \right)$. First we must show that$b(x)is indeed decreasing. From our earlier Corollary we know that (15) \begin{align} a(m_1 \cdot m_2) \leq a(m_1) \end{align} for any positive integersm_1$and$m_2$. But by definition$b(x) = a(m) = a\left(2^{4^x} \right)so that (16) \begin{align} b(x+1) = a\left( 2^{4^{x+1}} \right) = a\left( \left( 2^{4^x} \right)^4 \right) = a(m^4) \leq a(m) = b(x) \end{align} and henceb$is decreasing. Now consider$Pb^2(2P)$, and write out the sum as$P$copies of$b^2(2P): (17) \begin{align} Pb^2(2P) = b^2(2P) + \cdots + b^2(2P); \end{align} and apply the fact thatb$is decreasing to bound each of these terms with$b^2(P)$,$b^2(P+1)$and so forth up to$b^2(2P-1): (18) \begin{align} Pb^2(2P) \leq b^2(P) + \cdots + b^2(2P - 1) = \sum_{x=P}^{2P-1} b^2(x). \end{align} We are assuming thatP>c_4$, and so we can apply our earlier bound to each of these terms and so bound$b^2(2P)as follows: (19) \begin{align} Pb^2(2P) \leq \sum_{x=P}^{2P-1} c_3 \left( b(x) - b(x+1) + \frac{1}{2^{4^x}} \right) = c_3 \sum_{x=P}^{2P-1} (b(x) - b(x+1)) + c_3 \sum_{x=P}^{2P-1} \frac{1}{2^{4^x}}. \end{align} The first thing to note about Equation 19 is that the first sum is in fact telescoping. That is, the second term in each summand cancels out the first term in the consecutive summand, so that, on cancellation, we are left with simply the first and last terms: (20) \begin{align} \sum_{x=P}^{2P-1} (b(x) - b(x+1)) = b(P) - b(2P). \end{align} Therefore, as long asc_5 > c_3$we will have this first sum bounded by$c_5 (b(P) - b(2P))$. Now for any$x$in the second sum, we have$x \geq P \geq c_4. We now use the fact that this implies (21) \begin{align} \frac{1}{2^{4^x}} \leq \frac{1}{2^{4^P}}. \end{align} So we have the second sum in 19 bounded as follows: (22) \begin{align} c_3 \sum_{x=P}^{2P-1} \frac{1}{2^{4^x}} \leq \frac{c_3 P}{2^{4^P}}. \end{align} We wish to show that this is bounded by\frac{4{c_5}^2}{2P}and so this is equivalent to having (23) \begin{align} c_5 > \sqrt{\frac{c_3 P^2}{2 \cdot 2^{4^P}}} \qquad \qquad \forall P > c_4. \end{align} To find such ac_5$we use the obvious fact that$\frac{y^2}{2^{4^y}}$is decreasing with integers$y>0$. As$P>c_4we can therefore bound as follows: (24) \begin{align} \frac{P^2}{2^{4^P}} < \frac{{c_4}^2}{2^{4^{c_4}}}. \end{align} If we hence choosec_5such that (25) \begin{align} c_5 > \sqrt{\frac{{c_4}^2 c_3}{2 \cdot 2^{4^{c_4}}}} \end{align} then Equation 23 will hold. Therefore we are left with the condition that if (26) \begin{align} c_5 > \max \left\{ c_3 , \sqrt{\frac{{c_4}^2 c_3}{2 \cdot 2^{4^{c_4}}}} \right\} \end{align} then we have (27) \begin{eqnarray} Pb^2(2P) &<& c_3 \left( b(P) - b(2P) \right) + \frac{c_3 P}{2^{4^P}}\\ &<& c_5 \left( b(P) - b(2P) + \frac{4 c_5}{2P} \right); \end{eqnarray} and so the Lemma holds. ### Showing 2Pb(2P) < Pb(P) Under the additional assumption that2Pb(2P) > 4c_5$, as well as$P > c_4$, we get$2Pb(2P) < \frac{1}{4 c_5} \{ 2Pb(2P) \}^2$which is then$< P \left\{ b(P) - b(2P) + \frac{4 c_5}{2P} \right\}$which is finally$< Pb(P)$. We start by looking at the additional assumption, and write it in the following alternative ways. First, we can divide by the$4 c_5factor to rewrite the assumption in the form (28) \begin{align} \frac{2 P b(2P)}{4 c_5} > 1 \end{align} which will be useful for our first inequality. The second form we will write it in simply involves canceling a factor of two and rearranging to get (29) $$2c_5 - Pb(2P) < 0$$ which we will need in the final step. So we start by using Equation 28 to get (30) \begin{align} 2Pb(2P) < \left( \frac{2Pb(2P)}{4 c_5} \right) \cdot (2Pb(2P)) = \frac{1}{4 c_5} \{ 2Pb(2P)\}^2. \end{align} Now we can cancel the factor of four and, asP > c_4, apply our bound on b to Equation 30 to get (31) \begin{align} = \frac{1}{c_5} P(Pb^2(2P)) < \frac{1}{c_5} P\left( c_5 \left( b(P) - b(2P) + \frac{4c_5}{2P} \right) \right) \end{align} which we can simplify to get Equation 31 equalling (32) \begin{align} = P\left( b(P) - b(2P) + \frac{4 c_5}{2P} \right) = Pb(P) + 2c_5 - Pb(2P). \end{align} We can now apply Equation 29 to remove the excess terms and finally bound Equation 32 as (33) $$< Pb(P)$$ as we required. ### Showing b(x) is asymptotically O(1/x) We can apply backward induction and see that ifc_4 < 2^{t_0} < 2^t$then$2^t b(2^t)$is less than or equal to$\max ( 4c_5, 2^{t_0} b(2^{t_0}) )$, which gives$b(2^t) = O\left( \frac{1}{2^t} \right)$. As$b(x)$is a decreasing function, this gives us that for any$x$,$b(x) = O\left( \frac{1}{x} \right). Define (34) \begin{align} \zeta := \max \left( 4c_5, 2^{t_0} b\left( 2^{t_0} \right) \right). \end{align} The first thing we must do is choose at_0$such that$2^{t_0} > c_4$. This is obviously possible, and we can choose$c_5such that (35) \begin{align} 2^{t_0} b(2^{t_0}) \leq 4 c_5 \end{align} and so our base case oft = t_0$is satisfied. Now let us assume the result is true for$t-1 \geq t_0so that (36) \begin{align} 2^{t-1} b(2^{t-1}) \leq \zeta. \end{align} We wish to show the result then holds fortso let us assume that (37) \begin{align} 2^t b(2^t) > \zeta; \end{align} and we will derive a contradiction. We now show we can apply the inequality on b withP = 2^{t-1}$. First, as [[P \geq 2^{t_0} b(2^{t_0}) > c_4$]] we satisfy the first requirement that $P > c_4$. Now we look at Equation 37 and see that

(38)
$$2Pb(2P) = 2^t b(2^t) > 4 c_5 > c_5$$

so that our additional assumption holds.

The inequality on b gives

(39)
$$2Pb(2P) < Pb(P)$$

which becomes

(40)
$$2^t b(2^t) < 2^{t-1} b(2^{t-1}).$$

Finally we use Equation 36 and Equation 37 to get the string of inequalities

(41)
\begin{align} \zeta < 2^t b(2^t) < 2^{t-1} b(2^{t-1}) \leq \zeta \end{align}

which is clearly a contradiction and proves our induction.

So for large enough $t$ we have

(42)
\begin{align} 2^t b(2^t) \leq \zeta \end{align}

and we get

(43)
\begin{align} b(2^t) \leq \frac{\zeta}{2^t} = O\left( \frac{1}{2^t} \right). \end{align}

We are now going to generalize for numbers that are not powers of 2. For any large $x$ there exists a $k$ so that we have

(44)
$$2^{t_0} < 2^{k-1} < x < 2^k$$

and also that

(45)
\begin{align} \frac{1}{2^k} \leq \frac{1}{x} \leq \frac{1}{2^{k-1}}. \end{align}

We know that $b(x)$ is decreasing, and so

(46)
\begin{align} O \left( \frac{1}{2^k} \right) = b(2^k) \leq b(x) \leq b(2^{k-1}) = O \left( \frac{1}{2^{k-1}} \right). \end{align}

But $O(2^k) = O(2^{k-1})$ so that

(47)
\begin{align} b(x) = O \left( \frac{1}{2^k} \right) \end{align}

and $x^{-1} \geq 2^{-k}$ so that we finally get

(48)
\begin{align} b(x) = O\left( \frac{1}{x} \right) \end{align}

which was needed.

### Our final asymptotic

For any $x$ we have $\frac{A(x)}{x}$ is $O \left( \frac{1}{\log \log x} \right)$.

For any large integer $x$ we can choose an $\widehat{x}$ such that

(49)
\begin{align} 2^{4^{\widehat{x}}} < x \leq 2^{4^{\widehat{x} + 1}}, \end{align}

whence

(50)
\begin{align} 2 \widehat{x} < \log \log x < 2(\widehat{x} + 1). \end{align}

We then us our earlier Corollary to get

(51)
\begin{align} a(x) \leq 2 a \left( 2^{4^{\widehat{x}}} \right) = 2b(\widehat{x}). \end{align}

Finally, we use our asymptotic on b with this inequality to get that

(52)
\begin{align} a(x) = O \left( \frac{1}{\widehat{x}} \right) \end{align}

and so

(53)
\begin{align} a(x) = O \left( \frac{1}{\log \log x} \right). \end{align}
page revision: 13, last edited: 11 Apr 2011 19:58