\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}


\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf 
Bounds for the Eventual Positivity \\
of Difference Functions of Partitions \\
\vskip .12in
into Prime Powers}
\vskip 1cm
\large
Roger Woodford\\
Department of Mathematics\\
University of British Columbia\\
Vancouver, BC V6T 1Z2\\
Canada \\
\href{mailto:rogerw@math.ubc.ca}{\tt rogerw@math.ubc.ca}\\
\end{center}

\vskip .2 in

\begin{abstract}
In this paper we specialize work done by Bateman and Erd\H{o}s
concerning difference functions of partition functions. In
particular we are concerned with partitions into fixed powers of the
primes. We show that any difference function of these partition
functions is eventually increasing, and derive explicit bounds for
when it will attain strictly positive values. From these bounds an
asymptotic result is derived.
\end{abstract}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section] 


\newtheorem{notation}{Notation}
\newtheorem{remark}{Remark}
\newtheorem{example}{Example}
\newtheorem{conjecture}{Conjecture}
\newcommand{\p}{\textit{Proof. }}
\newcommand{\q}{\hfill $\Box$}
\newcommand{\lt}{\left( }
\newcommand{\rt}{\right) }
%\newtheorem{proof}{Proof}


\section{Introduction}

Given an underlying set $A\subseteq\mathbb{N}$, we denote the number
of partitions of $n$ with parts taken from $A$ by $p_A(n)$. The
$k$-th difference function $p_A^{(k)}(n)$ is defined inductively as
follows: for $k=0$, $p_A^{(k)}(n) = p_A(n)$. If $k>0$, then

\begin{equation*}
p_A^{(k)}(n) = p_A^{(k-1)}(n) - p_A^{(k-1)}(n-1).
\end{equation*}

Let $f_A^{(k)}(x)$ be the generating function for $p_A^{(k)}(n)$. We
have~\cite{pB56} the following power series identity:

\begin{align}f_A^{(k)}(x)&= \sum_{n=0}^{\infty}p_A^{(k)}(n)x^n\\ &=
(1-x)^k\sum_{n=0}^{\infty}p_A(n)x^n\label{e:1}\\ &=
(1-x)^k\prod_{a\in A}\frac{1}{1-x^a}.
\end{align}
This may be used to define $p_A^{(k)}(n)$ for all $k\in\mathbb{Z}$,
including $k<0$.

Bateman and Erd\H{o}s~\cite{pB56} characterize the sets $A$ for
which $p_A^{(k)}(n)$ is ultimately nonnegative. Note that if $k<0$,
then the power series representation of $(1-x)^k$ has nonnegative
coefficients so that $p_A^{(k)}(n)\ge 0$. For $k\ge0$, they prove
the following: if $A$ satisfies the property that whenever $k$
elements are removed from it, the remaining elements have greatest
common divisor 1, then

\begin{equation*}\lim_{n\to\infty}p_A^{(k)}(n) =
\infty.
\end{equation*}
A simple consequence of this is the fact that $p_A(n)$ is eventually
monotonic if $k>0$.

No explicit bounds for when $p_A^{(k)}(n)$ becomes positive are
included with the result of Bateman and Erd\H{o}s~\cite{pB56}. By
following their approach but specializing to the case when

\begin{equation}\label{e:30}
A=\{p^{\ell}:p\text{ is prime}\},
\end{equation}
for some fixed $\ell\in\mathbb{N}$, we shall find bounds for $n$
depending on $k$ and $\ell$ which guarantee that $p_A^{(k)}(n)>0$.
For the remainder, $A$ shall be as in~\eqref{e:30}, with
$\ell\in\mathbb{N}$ fixed.

In a subsequent paper, Bateman and Erd\H{o}s~\cite{2pB56} prove that
in the special case when $\ell=1$, $p_A^{(1)}(n)\ge 0$ for all
$n\ge2$. That is, the sequence A000607 of partitions of $n$ into
primes is increasing for $n\ge1$. Our result pertains to more
general underlying sets; partitions into squares of primes
(A090677), cubes of primes, etc.

In a series of papers (cf.~\cite{lR75}-~\cite{lR762}), L. B.
Richmond studies the asymptotic behaviour for partition functions
and their differences for sets satisfying certain stronger
conditions. The results none-the-less apply to the cases of interest
to us, that is, where $A$ is defined as above. Richmond
proves~\cite{lR76} an asymptotic formula for $p_A^{(k)}(n)$.
Unfortunately, his formula is not useful towards finding bounds for
when $p_A^{(k)}(n)$ must be positive, since, as is customary, he
does not include explicit constants in the error term.

Furthermore, his asymptotic formula includes functions such as
$\alpha = \alpha(n)$ defined by
\begin{equation*}
n=\sum_{a\in A}\frac{a}{e^{\alpha a}-1} - \frac{k}{e^{\alpha}-1}.
\end{equation*}
As we are seeking explicit constants, a direct approach will be
cleaner than than attempting to adapt the aforementioned formula.

Another result worthy of comment from Richmond~\cite{lR76} pertains
to a conjecture of Bateman and Erd\H{o}s~\cite{pB56}. His result
applies to $A$ as defined in~\eqref{e:30}, and states that
\begin{equation*}
\frac{p_A^{(k+1)}(n)}{p_A^{(k)}(n)} = O(n^{-1/2}), \text{ as
$n\to\infty$}.
\end{equation*}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We omit the subscript and write $p^{(k)}(n)$ in case the underlying
set is $A$, and omit the superscript if $k=0$. The letter $B$ will
always be used to denote a finite subset of $A$. We shall also write
$\zeta_n$ for the primitive $n$-th root of unity $e^{2\pi i/n}$. The
letters $\zeta$ and $\eta$ shall always denote roots of unity. We
shall denote the $m$-th prime by $p_m$.

Our main results are Theorems~\ref{t:2} and~\ref{t:5}. The former is
established in Sections~\ref{s:2} and~\ref{s:3}.


%%%insert the theorem here

\begin{theorem}\label{t:2}Let $k$ be a nonnegative integer, let $b_0=2\pi\sqrt{1-\frac{\pi^2}{12}}$
and let
\begin{equation*}t=\left\lfloor6\lt\frac{2}{b_0}\rt^{3(k+1)}(k+2)^{8\ell k +10\ell
+3}\right\rfloor.
\end{equation*}
Then there are positive absolute constants $a_1,\ldots , a_7$ such
that if
\begin{equation*}N=N(k,\ell)=a_1t\lt \frac{a_2a_3^{\ell\log^2{t}}}{a_4^{(k+3)^{\ell}}}
\rt^{t-1} + a_5t^3\lt a_6(a_7t)^{6\ell}\rt^{t-1},
\end{equation*}
then $n\ge N$ implies that $p^{(k)}(n)>0$.
\end{theorem}

\begin{remark}\label{r:1}The values of the constants are approximately
\begin{align*}a_1&\approx 1.000148266,\\
a_2&\approx 2757234.845,\\
a_3&\approx 1424.848799,\\
a_4&\approx 2.166322546,\\
a_5&\approx 1.082709333,\\
a_6&\approx .0193095561,\\
a_7&\approx 2.078207555.
\end{align*}
\end{remark}


%%%%and here

For the remainder of the paper, $b_0$ shall be as defined in
Theorem~\ref{t:2}. Note that $b_0\approx2.6474$. Furthermore, Define
\begin{equation*}F(k,\ell)=\min{\{N\in\mathbb{N}:n\ge N \text{ implies that }
p^{(k)}(n)>0\}}.
\end{equation*}
We show in Section~\ref{s:1} that Theorem~\ref{t:2} yields the
following asymptotic result:

\begin{theorem}\label{t:5}Fix $\ell\in\mathbb{N}$.
Then as $k\rightarrow\infty$,
\begin{equation*}\log{F(k,\ell)}=o\lt (k+2)^{8\ell k} \rt.
\end{equation*}
\end{theorem}



%%%%%%%%%%%%%%%%%%%%%%%%%%%



Following Bateman and Erd\H{o}s~\cite{pB56}, we first tackle the
finite case.

\section{Finite subsets of $A$}\label{s:2}

\begin{lemma}\label{l:parfrafin}Let $B$ be a finite subset of $A$ of size $r$,
and suppose $k<r$. The function $p_B^{(k)}(n)$ can be decomposed as
follows:

\begin{equation*}p_B^{(k)}(n) = g_B^{(k)}(n) + \psi_B^{(k)}(n),
\end{equation*}
where $g_B^{(k)}(n)$ is a polynomial in $n$ of degree $r-k-1$ with
leading coefficient $\lt(r-k-1)!\prod_{q\in B}q\rt^{-1}$, and
$\psi_B^{(k)}(n)$ is periodic in $n$ with period $\prod_{q\in B}q$.
\end{lemma}
\begin{proof}
We use partial fractions to decompose the generating function
$f_B^{(k)}(x)$ as follows:
\begin{align}f_B^{(k)}(x) &=
\frac{1}{(1-x)^{r-k}}\prod_{q\in B}\prod_{j=1}^{q-1}\frac{1}{1-\zeta_q^j x}\label{e:7}\\
&= \frac{\alpha_1}{1-x}+\frac{\alpha_2}{(1-x)^2} +\ldots +
\frac{\alpha_{r-k}}{(1-x)^{r-k}} + \sum_{q\in
B}\sum_{j=1}^{q-1}\frac{\beta(\zeta_q^j)}{1-\zeta_q^j x},\label{e:8}
\end{align}
where the $\alpha_i$, and $\beta(\zeta_q^j)$ are complex numbers
that can be determined. Note that
\begin{equation*} \alpha_{r-k} =
\lt\prod_{q\in B}q\rt^{-1}.
\end{equation*}

The power series expansion for $(1-x)^{-h}$ is given by

\begin{equation*}
\frac{1}{(1-x)^h} = \sum_{n=0}^{\infty}\binom{n+h-1}{h-1} x^n.
\end{equation*}
Hence, if
\begin{equation*}g_B^{(k)}(n) =
\sum_{h=1}^{r-k}\alpha_h\binom{n+h-1}{h-1},
\end{equation*}
and
\begin{equation*}\psi_B^{(k)}(n) =
\sum_{q\in B}\sum_{j=1}^{q-1}\beta(\zeta_q^j)\zeta_q^{jn},
\end{equation*}
then the lemma is proved.
\end{proof}

For the remainder of this paper, $g_B^{(k)}(n)$ and
$\psi_B^{(k)}(n)$ shall be as in Lemma~\ref{l:parfrafin}, for a
given finite set $B\subseteq A$ which shall be clear from the
context.


\begin{remark}\label{r:2}Let $B$ be as in Lemma~\ref{l:parfrafin}. We wish to know the precise value of
$\beta(\zeta_q^j)$. To simplify notation a little, we will
frequently write $\beta_{\zeta}$ instead, when $\zeta$ is clear from
the context. In particular, suppose $\eta = \zeta_q^j$, where $q\in
B$, and $0<j<q$. Then
\begin{align*}(1-\eta x)f_B^{(k)}(x)&=(1-x)^k\frac{1}{1+\eta x +
\cdots + (\eta x)^{q-1}}\prod_{\substack{p\in B \\ p\ne q}}\frac{1}{1-x^p}\\
&= \beta_{\eta} + (1-\eta x)\lt \frac{\alpha_1}{1-x} + \cdots
+\frac{\alpha_{r-k}}{(1-x)^{r-k}} +
\sum_{\zeta\neq\eta}\frac{\beta_{\zeta}}{1-\zeta x} \rt,
\end{align*}
hence,
\begin{equation*}\beta_{\eta}=\frac{(1-\bar{\eta})^k}{q}
\prod_{\substack{p\in B \\ p\ne q}}\frac{1}{1-\bar{\eta}^p}.
\end{equation*}
\end{remark}

We shall frequently make use of the inequality

\begin{equation*}1-\frac{\theta^2}{2} \le \cos{\theta} \le 1-\frac{\theta^2}{2} +
\frac{\theta^4}{24},
\end{equation*}
which holds for all values of $\theta$. Note that
\begin{equation*}|e^{i\theta} - 1 | = \sqrt{2(1-\cos{\theta})},
\end{equation*}
so for $-2\sqrt{3}\le \theta \le 2\sqrt{3}$,

\begin{equation*}|\theta|\sqrt{1-\frac{\theta^2}{12}} \le |e^{i\theta} - 1 | \le
|\theta|.
\end{equation*}
In particular, for $0\le \theta \le \pi$,
\begin{equation}\label{e:20}\theta\sqrt{1-\frac{\theta^2}{12}} \le |e^{i\theta} - 1 | \le
\theta.
\end{equation}

\begin{lemma}\label{l:1}Suppose that $\zeta\neq 1$
is a $q$-th root of unity, $q\ge 2$. Then
\begin{equation*}\frac{b_0}{q}\le|1-\zeta|\le 2.
\end{equation*}
\end{lemma}
\begin{proof}
Clearly $|1-\zeta|\le 2$. On the other hand, by
equation~\eqref{e:20},

\begin{align*}|1-\zeta| &\ge |1-e^{2\pi i/q}|\\ &\ge
\frac{2\pi}{q}\sqrt{1-\frac{4\pi^2}{12q^2}}\\ &\ge \frac{b_0}{q}.
\end{align*}
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{lemma}\label{l:2}Suppose that $k<r$, and $B\subseteq A$, satisfies $|B| = r$.
Suppose further that $\eta = \zeta_q^j$, for some $q\in B$,
$j\in\{1,\ldots,q-1\}$. Then for $k\ge 0$,

\begin{equation*}
|\beta_{\eta}| \le
\begin{cases}\frac{2^k q^{r-2}}{b_0^{r-1}}, &\text{ if $k\ge0$;}\\
\frac{q^{r-k-2}}{b_0^{r-k-1}}, &\text{ if $k<0$.}
\end{cases}
\end{equation*}
\end{lemma}
\begin{proof}
Making use of Remark~\ref{r:2} and Lemma~\ref{l:1} we have that for
$k\ge0$:
\begin{align*}|\beta_{\eta}| &=
\frac{|1-\zeta_q^{-j}|^k}{q}\prod_{\substack{p\in B \\ p\ne
q}}\frac{1}{|1-\zeta_q^{-jp}|}\\ &\le \frac{2^k}{q} \prod_{\substack{p\in B \\ p\ne q}}\frac{1}{|1-\zeta_q|}\\
&\le \frac{2^k}{q} \lt\frac{q}{b_0}\rt^{r-1}\\
&=\frac{2^k q^{r-2}}{b_0^{r-1}}.
\end{align*}
A similar arguments works for the case when $k<0$.
\end{proof}


\begin{theorem}\label{t:3}Suppose that $k<r$, and $B\subseteq A$, satisfies $|B|=r$. Then
\begin{equation*}
|\psi_B^{(k)}(n)| \le
\begin{cases}
\frac{2^k}{b_0^{r-1}}\sum_{q\in B}q^{r-1}, &\text{ if $k\ge0$;}\\
\frac{1}{b_0^{r-k-1}}\sum_{q\in B}q^{r-k-1}, &\text{ if $k < 0$.}
\end{cases}
\end{equation*}
\end{theorem}
\begin{proof}
First assume that $k\ge 0$. By Lemmas~\ref{l:2}
and~\ref{l:parfrafin},
\begin{align*}|\psi_B^{(k)}(n)| &=
\left|\sum_{q\in B}\sum_{j=1}^{q-1}\beta(\zeta_q^j)\zeta_q^{jn}\right|\\
&\le
\sum_{q\in B}\sum_{j=1}^{q-1}|\beta(\zeta_q^j)|\\
&\le
\sum_{q\in B}\sum_{j=1}^{q-1}\frac{2^kq^{r-2}}{b_0^{r-1}}\\
&= \frac{2^k}{b_0^{r-1}}\sum_{q\in B}(q-1)q^{r-2}\\
&\le \frac{2^k}{b_0^{r-1}}\sum_{q\in B}q^{r-1}.
\end{align*}
A similar argument works for $k<0$.
\end{proof}

To obtain bounds for the coefficients $\alpha_h$, we will use
Laurent series.

\begin{lemma}\label{l:3}Suppose that $k<r$, and $B\subseteq A$, satisfies
$|B|=r$. Denote the largest element of $B$ by $Q$, and suppose
further that $0<r_0<|1-\zeta_Q|$. Let

\begin{equation*}
d_B(r_0)=\prod_{q\in B} \prod_{j=1}^{q-1}(|\zeta_q^j - 1| - r_0).
\end{equation*}
Then
\begin{equation*}|\alpha_h|\le\frac{1}{r_0^{r-k-h}d_B(r_0)}.
\end{equation*}
\end{lemma}
\begin{proof}
Let $\gamma$ be the circle $|z-1|=r_0$. From equations~\eqref{e:7}
and~\eqref{e:8}, and the Laurent expansion theorem, we have that
\begin{align*}|\alpha_h| &= \left| \frac{1}{2\pi i} \int_{\gamma}f_B^{(k)}(z)(z-1)^{h-1}\, dz
\right|\\ &\le
\frac{1}{2\pi}\int_{\gamma}\frac{1}{|z-1|^{r-k-h+1}}\prod_{q\in B}
\prod_{j=1}^{q-1}\frac{1}{|1-\zeta_q^jz|} \,dz\\
&\le \frac{1}{r_0^{r-k-h}d_B(r_0)}.
\end{align*}
\end{proof}







For the following proposition, we define several new constants:
\begin{align*}c_1&=\prod_{k=3}^{\infty}\left( 1-\frac{\pi^2}{3\cdot4^k}
\right),\\ c_2&=\prod_{k=3}^{\infty}\left( 1-\frac{\pi^2}{3\cdot4^k}
\right)^{\frac{1}{2^k}}, \\c_3&=4\pi^{-6}c_1,\\
c_4&=\frac{2\log{\pi}}{\log{2}}-1,\\c_5&=\lt\frac{\pi}{2}\rt^{1/2}c_2,\\
c_6&=\lt\frac{\pi}{2}\rt^{1/2}\lt1-\frac{\pi^2}{48}\rt^{1/4},
\\c_7&= \frac{\sin{4\pi/5}}{4\pi/5},\\b_1 &= c_5c_6 = 1.471843248\ldots,\\ b_2 &=\frac{c_3}{c_6} =
.003278645140\ldots,\\ b_3 &= c_4 =
2.302992260\ldots,\\b_4&=c_7\pi/2=.3673657828\ldots.
\end{align*}


\begin{proposition}\label{p:2}Let $B\subseteq A$ satisfy $|B|=r$,
and suppose that all the elements of $B$ are odd. Let $Q=\max\{B\}$,
and $T=\left\lceil\log_2{Q}\right\rceil$. If
\begin{equation*}r_0 = \min{\{|\zeta_q^{\left\lceil \frac{q}{2^j}\right\rceil} - 1|
-|\zeta_{2^j} - 1|:q\in B, j=2,\ldots, T\}},
\end{equation*}
then
\begin{equation*}0< \frac{b_4}{Q^2}\le r_0 < |1-\zeta_Q| \le
\frac{2\pi}{Q}.
\end{equation*}
Furthermore, if $d_B=d_B(r_0)$, then
\begin{equation*}d_B\ge b_1^{\sum_{q\in B}q}\lt
b_2Q^{b_3}e^{-\frac{\log^2{Q}}{\log{2}}} \rt^r.
\end{equation*}
\end{proposition}
\begin{proof}
Observe that $T$ satisfies
\begin{equation*}2^{T-1}<Q<2^T.
\end{equation*}
Now, let
\begin{equation*}
\delta_q = \prod_{j=1}^{q-1}(|\zeta_q^j - 1| - r_0),
\end{equation*}
so that
\begin{equation*}
d_B = \prod_{q\in B}\delta_q.
\end{equation*}
Note that since each element of $B$ is odd, we have that
\begin{equation*}
\delta_q = \prod_{j=1}^{\frac{q-1}{2}}(|\zeta_q^j - 1| - r_0)^2.
\end{equation*}
Consequently,
\begin{align*}
\delta_q &\ge
\prod_{k=2}^{T}\prod_{\left\lceil\frac{q}{2^k}\right\rceil \le j <
\left\lceil\frac{q}{2^{k-1}}\right\rceil}|\zeta_{2^k} - 1|^2\\
&\ge \prod_{k=2}^{T}\lt \frac{\pi^2}{4^{k-1}}\left(1 -
\frac{\pi^2}{3\cdot4^k}\right)
\rt^{\left\lceil\frac{q}{2^{k-1}}\right\rceil -
\left\lceil\frac{q}{2^k}\right\rceil}\\
&= \lt \frac{\pi^2}{4}\left(1 - \frac{\pi^2}{48}\right)
\rt^{\left\lceil\frac{q}{2}\right\rceil -
\left\lceil\frac{q}{4}\right\rceil} \times \prod_{k=3}^{T}\lt
\frac{\pi^2}{4^{k-1}}\left(1 - \frac{\pi^2}{3\cdot4^k}\right)
\rt^{\left\lceil\frac{q}{2^{k-1}}\right\rceil -
\left\lceil\frac{q}{2^k}\right\rceil}\\
&\ge \lt \frac{\pi^2}{4}\left(1 - \frac{\pi^2}{48}\right)
\rt^{\frac{q-1}{4}} \times \prod_{k=3}^{T}\lt
\frac{\pi^2}{4^{k-1}}\left(1 - \frac{\pi^2}{3\cdot4^k}\right)
\rt^{\frac{q}{2^k}+1}.
\end{align*}

Now

\begin{align*}
\prod_{k=3}^{T}\lt \frac{\pi^2}{4^{k-1}}\left(1 -
\frac{\pi^2}{3\cdot4^k}\right) \rt^{\frac{q}{2^k}+1} &\ge
\frac{\pi^{2(T-2)}}{4^{\binom{T}{2}-1}}\lt
\frac{\pi^{2(\frac{1}{4}-\frac{1}{2^T})}}{4^{\frac{3}{4}-\frac{T+1}{2^T}}}
\rt^qc_1c_2^q\\
&\ge
\frac{4\pi^{-4}Q^{\frac{2\log{\pi}}{\log{2}}}}{Qe^{\frac{\log^2{Q}}{\log{2}}}}
\lt \frac{\pi^{2(\frac{1}{4}-\frac{1}{Q})}}{4^{\frac{1}{4}}}
\rt^qc_1c_2^q\\ &\ge
4\pi^{-4}c_1Q^{\frac{2\log{\pi}}{\log{2}}-1}e^{-\frac{\log^2{Q}}{\log{2}}}
\lt\frac{\pi^{1/2}c_2}{2^{1/2}}\rt^q\pi^{-2}\\ &=
c_3Q^{c_4}e^{-\frac{\log^2{Q}}{\log{2}}}c_5^q
\end{align*}
So we have that

\begin{align*}
d_B &\ge \prod_{q\in
B}\lt\lt\frac{c_3}{c_6}\rt(c_5c_6)^qQ^{c_4}e^{-\frac{\log^2{Q}}{\log{2}}}\rt\\
&=b_1^{\sum_{q\in B}q}\lt b_2Q^{b_3}e^{-\frac{\log^2{Q}}{\log{2}}}
\rt^r
\end{align*}

Our next task is to bound $r_0$ from below. For $q\in B$, $j\in
\{2,\ldots,T\}$, let
\begin{align*}f(x)&=\sqrt{2(1-\cos{x})},\\ \theta &= \theta(j) =
\frac{2\pi}{2^j}, \text{ and }\\ \varepsilon &= \varepsilon(q,j) =
\frac{2\pi}{q}\left\lceil\frac{q}{2^j}\right\rceil -
\frac{2\pi}{2^j}.
\end{align*}
Then by the mean value theorem,
\begin{align*}|\zeta_q^{\left\lceil \frac{q}{2^j}\right\rceil} - 1|
-|\zeta_{2^j} - 1| &= f(\theta+\varepsilon)-f(\theta)\\ &=
\frac{\varepsilon\sin{c}}{\sqrt{2(1-\cos{c})}},
\end{align*}
for some $c\in (\theta,\theta+\varepsilon)$.

It is easily seen that $2\pi\lceil q/2^j\rceil/q$ can be no greater
than $4\pi/5$. On the interval $[0,4\pi/5]$, we have $\sin{x}\ge
c_7x$. Therefore

\begin{equation}\label{e:21}f(\theta+\varepsilon)-f(\theta) \ge \frac{\varepsilon
c_7c}{c} = \varepsilon c_7.
\end{equation}

Choose $a\in\mathbb{N}$ such that $(a-1)2^j+1\le q \le a2^j-1$. Then
clearly $a\le 2^{T-j}$. Furthermore,

\begin{align*}\varepsilon&\ge \frac{2\pi
a}{a2^j-1}-\frac{2\pi}{2^j}\\&=
\frac{2\pi}{2^j-1/a}-\frac{2\pi}{2^j}\\ &\ge
\frac{2\pi}{2^j-2^{j-T}}-\frac{2\pi}{2^j}\\&\ge
\frac{2\pi}{2^T-1}-\frac{2\pi}{2^T}\\ &\ge \frac{\pi}{2Q^2}.
\end{align*}

Hence, by~\eqref{e:21} we conclude that

\begin{equation*}r_0\ge \frac{b_4}{Q^2}.
\end{equation*}

Bounding $r_0$ from above is a far simpler matter. By definition,
\begin{equation}\label{e:26}r_0 < |\zeta_Q - 1| \le \frac{2\pi}{Q}.
\end{equation}

\end{proof}

\section{Infinite subsets of $\mathbb{N}$ and $A$}\label{s:3}

\begin{proposition}\label{p:1}For $k\le 0$, and $D_1\subseteq D_2\subseteq\mathbb{N}$, we
have $p_{D_2}^{(k)}(n)\ge p_{D_1}^{(k)}(n)\ge 0.$
\end{proposition}
\begin{proof}
This follows immediately from equation~\ref{e:1} and the fact that
for $k\le 0$, the power series expansion for $(1-x)^k$ has
nonnegative coefficients.
\end{proof}

For the sake of clarity and the comprehensiveness of this exposition
we include the following theorem of Bateman and
Erd\H{o}s~\cite{pB56} suitably adapted to our needs.

\begin{theorem}\label{t:4}Let $D\subseteq\mathbb{N}$ be an infinite set. For any $t\in\mathbb{N}$, we have that
\begin{equation*}\frac{p_D(n)}{p_D^{(-1)}(n)}\le \frac{1}{t+1} +
\frac{(t-1)^2}{t+1}\frac{n^{2t-3}}{p_D^{(-1)}(n)}.
\end{equation*}
\end{theorem}
\begin{proof}Denote by $P_q(n)$, the number of partitions of $n$ into parts
from $D$ such that there are exactly $q$ distinct parts. $P_q(n)$
has generating function
\begin{equation*}\sum_{n=0}^{\infty}P_q(n)x^n=\sum_{\{a_1,\ldots a_q\}
\subseteq
D}\frac{x^{a_1}}{1-x^{a_1}}\cdots\frac{x^{a_q}}{1-x^{a_q}}.
\end{equation*}

If $R_q(n)$ is defined by
\begin{equation*}\sum_{n=0}^{\infty}R_q(n)x^n=\sum_{\{a_1,\ldots a_q\}
\subseteq
[n]}\frac{x^{a_1}}{1-x^{a_1}}\cdots\frac{x^{a_q}}{1-x^{a_q}},
\end{equation*}
where $[n]=\{1,\ldots , n\}$, then $P_q(n)\le R_q(n)$.

There are $\binom{n}{q}$ subsets of $[n]$ of size $q$. Also, the
coefficient of $x^n$ in

\begin{equation*}(x^{a_1} + x^{2a_1} + \cdots)\cdots(x^{a_q}
+ x^{2a_q} + \cdots)
\end{equation*}
is less than or equal to the coefficient of $x^n$ in

\begin{equation*}
(x+x^2+\cdots)^q = \sum_{m=q}^{\infty}\binom{m-1}{q-1}x^m,
\end{equation*}
so
\begin{equation*}P_q(n)\le\binom{n}{q}\binom{n-1}{q-1}\le n^{2q-1}.
\end{equation*}

Any partition $n=n_1a_1+\cdots n_qa_q$, where $a_1,\ldots , a_q\in
A$, gives rise to a partition of $n-a_i$ for $i=1,\ldots , q$,
namely
\begin{align*}n-a_1 &= (n_1-1)a_1 + n_2a_2 + \cdots + n_qa_q,\\
n-a_2 &= n_1a_1 + (n_2-1)a_2 + \cdots + n_qa_q, \\ &\vdots\\ n-a_q
&= n_1a_1+n_2a_2+\cdots+(n_q-1)a_q.
\end{align*}
Note that no two distinct partitions of $n$ can give rise to the
same partition of any $m<n$ in this way, and so
\begin{equation*}\sum_{q=1}^nqP_q(n)\le \sum_{m=0}^{n-1}p_D(m).
\end{equation*}

Now if $t\in\mathbb{N}$, then
\begin{align*}p_D^{(-1)}(n) &= \sum_{m=0}^np_D(m)\\ &\ge
p_D(n)+\sum_{q=1}^nqP_q(n)\\ &= (t+1)p_D(n) + \sum_{q=1}^n(q-t)P_q(n)\\
&\ge (t+1)p_D(n) -(t-1)\sum_{q=1}^{t-1}P_q(n)\\ &\ge
(t+1)p_D(n)-(t-1)^2n^{2t-3},
\end{align*}
and the theorem is proved.
\end{proof}





For the remainder of this section, we follow the approach of Bateman
and Erd\H{o}s~\cite{pB56} and simultaneously make the results
explicit by applying them to the special case under consideration.
To be consistent, we shall assume $k\ge0$, and use the following
notation:
\begin{notation}
Let $B$ be the least $k+2$ elements of $A$, and let $C=A\setminus
B$. $B_1 = \{p_{k+3}^{\ell},p_{k+4}^{\ell},\ldots,
p_{k+2t}^{\ell}\}$ be the least $2t-2$ elements of $C$, where $t$ is
determined as in the statement of Theorem~\ref{t:2} from the values
of $k$ and $\ell$ in question. Furthermore, let
\begin{align}
g &= \lt\frac{2}{b_0}\rt^{k+1}(k+2)^{2\ell(k+1)+1}, \text{ and}\label{e:22}\\
h &= 3(k+2)^{2\ell(k+2)}g=3\lt\frac{2}{b_0}\rt^{k+1}(k+2)^{4\ell k +
6\ell+1}.\notag
\end{align}
Finally, let us remark that numerous constants shall be defined in
the subsequent argument. Their definitions shall remain consistent
throughout.
\end{notation}

Note that the right hand side of~\eqref{e:22} is increasing in $k$
and $\ell$, so $g\ge 16/b_0 = 6.04\ldots$.


%%%%% In here we shall begin breaking up the big proof

\begin{lemma}\label{l:5}
For all $n\ge 0$, we have
\begin{equation}\label{e:27}p_B^{(k)}(n) \ge 1 - g.
\end{equation}
\end{lemma}
\begin{proof}
Since $|B|=k+2,$ $g_B^{(k)}(n)$ is linear in $n$, and
$g_B^{(k+1)}(n)$ is a constant function. By Lemma~\ref{l:parfrafin},

\begin{equation*} g_B^{(k)}(n)=\sum_{h=1}^2\alpha_h\binom{n+h-1}{h-1}
\end{equation*}
where $\alpha_2=(p_1\cdots p_{k+2})^{-\ell}$. Substituting $x=0$
into~\eqref{e:7} and~\eqref{e:8} gives

\begin{equation*} \alpha_1 + \alpha_2 +
\sum_{q\in B}\sum_{j=1}^{q-1}\beta(\zeta_q^j) = 1.
\end{equation*}
Hence,

\begin{equation*} g_B^{(k)}(n) = (p_1\cdots p_{k+2})^{-\ell}n + 1 -
\sum_{q\in B}\sum_{j=1}^{q-1}\beta(\zeta_q^j),
\end{equation*}
so

\begin{align*}
p_B^{(k)}(n) &= g_B^{(k)}(n) + \psi_B^{(k)}(n)\\ &= (p_1\cdots
p_{k+2})^{-\ell}n + 1 - \sum_{q\in B}\sum_{j=1}^{q-1}(1
- \zeta_q^{jn} )\beta(\zeta_q^j)\\
&\ge (p_1\cdots p_{k+2})^{-\ell}n + 1 - \sum_{q\in
B}\sum_{j=1}^{q-1}|1 -
\zeta_q^{jn}||\beta(\zeta_q^j)|\\
&\ge (p_1\cdots p_{k+2})^{-\ell}n + 1 -
2\sum_{q\in B}\sum_{j=1}^{q-1}|\beta(\zeta_q^j)|\\
&\ge (p_1\cdots p_{k+2})^{-\ell}n + 1 -
\lt\frac{2}{b_0}\rt^{k+1}\sum_{q\in B}q^{k+1}\\
&\ge 1 - \lt\frac{2}{b_0}\rt^{k+1}\sum_{q\in B}q^{k+1}.
\end{align*}
Now, it is easy to see that

\begin{equation*}\sum_{q\in B}q^{k+1} \le Q_0^{k+1}(k+2)
\le (k+2)^{2\ell(k+1)+1},
\end{equation*}
where $Q_0=\max{(B)}$. From this, the Lemma follows.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{lemma}\label{l:7}
For all $n\ge 0$, we have
\begin{equation}\label{e:28}
1 + |p_B^{(k+1)}(n)| < g -1.
\end{equation}
\end{lemma}
\begin{proof}
Note that

\begin{equation*}g_B^{(k+1)}(n)=(p_1\cdots p_{k+2})^{-\ell}.
\end{equation*}
Making use of Theorem~\ref{t:3}, we see that
\begin{align*}g-2-|p_B^{(k+1)}(n)| \ge& g-2 - (p_1\cdots p_{k+2})^{-\ell}
- |\psi_B^{(k+1)}(n)|\\ \ge& g-2 - (p_1\cdots p_{k+2})^{-\ell} -
\frac{2^k}{b_0^{k+1}}\sum_{q\in B}q^{k+1}\\ \ge& \sum_{i=1}^{k+2}\lt
\lt\frac{2(k+2)^{2\ell}}{b_0}\rt^{k+1} -
\frac{1}{2}\lt\frac{2p_i^{\ell}}{b_0}\rt^{k+1} \rt\\& - 2 -
(p_1\cdots p_{k+2})^{-1}.
\end{align*}
Observe that for a fixed $i$, $1\le i\le k+2$, the expression

\begin{equation*}
\lt\frac{2(k+2)^{2\ell}}{b_0}\rt^{k+1} -
\frac{1}{2}\lt\frac{2p_i^{\ell}}{b_0}\rt^{k+1},
\end{equation*}
is positive and increasing in $\ell$, for $\ell\ge1$, so,

\begin{align*}
\lt\frac{2(k+2)^{2\ell}}{b_0}\rt^{k+1} -
\frac{1}{2}\lt\frac{2p_i^{\ell}}{b_0}\rt^{k+1} &\ge
\lt\frac{2(k+2)^2}{b_0}\rt^{k+1} -
\frac{1}{2}\lt\frac{2p_i}{b_0}\rt^{k+1}\\ &\ge
\lt\frac{2(k+2)^2}{b_0}\rt^{k+1} -
\frac{1}{2}\lt\frac{2p_{k+2}}{b_0}\rt^{k+1}\\ &\ge
\frac{2(k+2)^2}{b_0} - \frac{p_{k+2}}{b_0}\\ &\ge \frac{4}{b_0} +
\frac{(k+2)^2 - p_{k+2}}{b_0}\\ &\ge \frac{4}{b_0}.
\end{align*}
Hence,

\begin{align*}
g-2 - |p_B^{(k+1)}(n)| &\ge (k+2)\frac{4}{b_0}- 2 - (p_1\cdots
p_{k+2})^{-1}\\ &\ge \frac{8}{b_0}-\frac{13}{6} = 0.855167405\ldots
> 0,
\end{align*}
that is,
\begin{equation*}
1 + |p_B^{(k+1)}(n)| < g -1.
\end{equation*}
\end{proof}

\begin{corollary}
\begin{equation}\label{e:29}\frac{p_B^{(k)}(n)}{1 + |p_B^{(k+1)}(n)|}\ge2\text{
if $n\ge h$}.
\end{equation}
\end{corollary}
\begin{proof}
It follows from the proof of Lemma~\ref{l:5} that
\begin{align*}p_B^{(k)}(n)&\ge (p_1\cdots p_{k+2})^{-\ell}n + 1 -
g\\ &> (p_1\cdots p_{k+2})^{-\ell}n  - g.
\end{align*}
The Corollary follows from this, together with Lemma~\ref{l:7} and
the fact that
\begin{equation*}p_1\cdots p_{k+2}\le (k+2)^{2(k+2)}.
\end{equation*}
\end{proof}

%%%%%%%%%%%%%%%%%%%%%Lemma 14

\begin{lemma}\label{l:6}
There is an $h_1\in\mathbb{N}$ such that such that $n\ge h_1$
implies
\begin{equation}\label{e:24}\frac{(t-1)^2}{t+1}\frac{n^{2t-3}}{p_C^{(-1)}(n)}\le
\frac{(t-1)^2}{t+1}\frac{n^{2t-3}}{p_{B_1}^{(-1)}(n)}\le
\frac{1}{t+1}.
\end{equation}
\end{lemma}

\begin{proof}
The first inequality is a consequence of Proposition~\ref{p:1}. Note
that

\begin{align*}t &\ge 6\lt\frac{2}{b_0}\rt^{3(k+1)}(k+2)^{8\ell k +10\ell
+3} - 1\\ &\ge 6\lt\frac{2}{b_0}\rt^{3k+3}2^{8k+13}-1\\ &\ge
\frac{3\cdot 2^{16}}{b_0^3}\lt\frac{2^{11}}{b_0^3}\rt^k.
\end{align*}
Hence
\begin{equation*}\log{t}\ge \log{\lt\frac{3\cdot2^{16}}{b_0^3}\rt} +
k\log{\lt\frac{2^{11}}{b_0^3}\rt}.
\end{equation*}
since $\log{t}\le t/e$, if we let $M=e\log{(2^{11}/b_0^3)}$, then
\begin{equation*}k\le \frac{t}{M}.
\end{equation*}


Choose $r_0$ and $d_{B_1}$ with respect to the set $B_1$ as in
Proposition~\ref{p:2}, and let $Q=p_{k+2t}^{\ell} = \max{(B_1)}$. It
is clear that $t\ge \lfloor6(2/b_0)^32^{13} \rfloor = 21192$, which
we denote by $t_0$. By equation~\eqref{e:26}, we have that

\begin{equation*}r_0\le \frac{2\pi}{Q}\le \frac{2\pi}{(2t)^{\ell}}
\le \frac{\pi}{t_0}.
\end{equation*}
We also have that

\begin{equation*}r_0\ge \frac{b_4}{Q^2} \ge
\frac{b_4}{(k+2t)^{4\ell}},
\end{equation*}
and

\begin{align*}d_{B_1} &\ge b_1^{\sum_{q\in B_1}q}\lt
b_2Q^{b_3}e^{-\frac{\log^2{Q}}{\log{2}}} \rt^{2t-2}\\ &\ge
b_1^{(k+3)^{\ell}(2t-2)}\lt
b_2(k+2t)^{b_3\ell}(k+2t)^{-\frac{2\ell\log{(k+2t)}}{\log{2}}}
\rt^{2t-2}\\ &= \lt \frac{b_2\cdot
b_1^{(k+3)^{\ell}}(k+2t)^{b_3\ell}}{(k+2t)^{\frac{2\ell\log{(k+2t)}}{\log{2}}}}
\rt^{2t-2}
\end{align*}

Let us now bound $p_{B_1}^{(-1)}(n)$ from below. Assume that $n\ge
2t$, and let $b_5=1/M+2 =2.078207555\ldots$, and
$b_7=t_0/(t_0-\pi)$. Making use of Theorem~\ref{t:3}, we have

\begin{align*}p_{B_1}^{(-1)}(n)
=& g_{B_1}^{(-1)}(n) + \psi_{B_1}^{(-1)}(n)\\
\ge& \alpha_{2t-1}\binom{n+2t-2}{2t-2} -
\sum_{h=1}^{2t-2}|\alpha_h|\binom{n+h-1}{h-1}\\ &- |\psi_{B_1}^{(-1)}(n)|\\
\ge& \frac{(p_{k+3}\cdots p_{k+2t})^{-\ell}n^{2t-2}}{(2t-2)!} -
\binom{n+2t-3}{2t-3}
\sum_{h=1}^{2t-2}|\alpha_h|\\
&- \frac{1}{b_0^{2t-2}}\sum_{m=k+3}^{k+2t}p_m^{\ell(2t-2)}\\
\ge& \frac{(k+2t)^{-\ell(2t-2)}n^{2t-2}}{(2t-2)!} -
\frac{(n+2t-3)^{2t-3}}{(2t-3)!}
\sum_{h=1}^{2t-2}\frac{r_0^h}{r_0^{2t-1}d_{B_1}}\\ &-
\frac{1}{b_0^{2t-2}}(2t-2)(k+2t)^{2\ell(2t-2)}\\
\ge& \frac{(b_5t)^{-\ell(2t-2)}n^{2t-2}}{(2t-2)!} -
\frac{n^{2t-3}2^{2t-3}}{(2t-3)!} \frac{1}{(1-r_0)r_0^{2t-2}d_{B_1}}\\
&- \frac{(2t-2)(k+2t)^{2\ell(2t-2)}}{b_0^{2t-2}}\\
\ge& \frac{(b_5t)^{-\ell(2t-2)}n^{2t-2}}{(2t-2)!} -
\frac{b_7n^{2t-3}2^{2t-3}}{(2t-3)!}\lt \frac{(k+2t)^{(4-b_3)\ell +
\frac{2\ell\log{(k+2t)}}{\log{2}}}}{b_4b_2b_1^{(k+3)^{\ell}}}
\rt^{2t-2}\\
&- \frac{2t(b_5t)^{2\ell(2t-2)}}{b_0^{2t-2}}.
\end{align*}

Observe that

\begin{align*}(k+2t)&^{(4-b_3)\ell +
\frac{2\ell\log{(k+2t)}}{\log{2}}}\\ &\le (b_5t)^{(4-b_3)\ell +
\frac{2\ell\log{Ct}}{\log{2}}}\\ &= e^{\ell(\log{b_5} + \log{t})\lt
\lt4-b_3 +\frac{2\log{C}}{\log{2}}\rt
+\frac{2\log{t}}{\log{2}} \rt}\\
&= e^{\ell \lt\frac{2}{\log{2}}\log^2{t} + \lt 4-b_3 +
\frac{4\log{b_5}}{\log{2}} \rt\log{t} +  \lt 4-b_3 +
\frac{4\log{b_5}}{\log{2}} \rt\log{b_5}\rt}\\
&\le e^{b_6\ell\log^2{t}},
\end{align*}
where $b_6$ is a constant determined as follows. Let
$x_0=\log{t_0}$. Then we may take

\begin{align*}b_6&=\frac{2}{\log{2}} + \lt 4-b_3 +
\frac{4\log{b_5}}{\log{2}} \rt\frac{1}{x_0} +  \lt 4-b_3 +
\frac{4\log{b_5}}{\log{2}} \rt\frac{\log{b_5}}{x_0^2}\\ &=
3.523150893\ldots.
\end{align*}



It suffices to select $h_1$ such that for $n\ge h_1$,
\begin{equation}\label{e:23}p^{(-1)}_{B_1}(n)n^{-(2t-3)} \ge (t-1)^2.
\end{equation}
Observe that~\eqref{e:23} is implied by
\begin{equation*}\frac{(b_5t)^{-\ell(2t-2)}n}{(2t-2)!} -
\frac{b_7}{2(2t-3)!}\lt
\frac{2e^{b_6\ell\log^2{t}}}{b_4b_2b_1^{(k+3)^{\ell}}} \rt^{2t-2} -
\frac{2t(b_5t)^{2\ell(2t-2)}}{n^{2t-3}b_0^{2t-2}}\ge (t-1)^2,
\end{equation*}
which is equivalent to

\begin{align}&n \ge (b_5t)^{\ell(2t-2)}\times\notag \\ &\lt b_7(t-1)\lt
\frac{2e^{b_6\ell\log^2{t}}}{b_4b_2b_1^{(k+3)^{\ell}}} \rt^{2t-2} +
\frac{2t(b_5t)^{2\ell(2t-2)}(2t-2)!}{n^{2t-3}b_0^{2t-2}} +
(t-1)^2(2t-2)! \rt.\label{e:25}
\end{align}

The inequality

\begin{equation*}e^nn!\le n^{n+1},
\end{equation*}
holds for $n\ge 7$. This implies that

\begin{equation*}\frac{(2t-2)!}{(2t)^{2t-3}} \le
\frac{(2t)^3}{e^{2t}(2t-1)}.
\end{equation*}
Thus, since $n\ge2t$ by assumption,~\eqref{e:25} is implied by

\begin{equation*}n \ge (b_5t)^{\ell(2t-2)}(A_1 + A_2 + A_3),
\end{equation*}
where

\begin{align*}A_1 &= b_7t\lt
\frac{2e^{b_6\ell\log^2{t}}}{b_4b_2b_1^{(k+3)^{\ell}}}
\rt^{2t-2}\\
A_2 &=\frac{16t^4(b_5t)^{2\ell(2t-2)}}{(2t-1)e^{2t}b_0^{2t-2}}\\
A_3 &=\frac{(t-1)^2(2t)^{2t}}{(2t-1)e^{2t}}.
\end{align*}

The term $A_3$ is negligible relative to $A_2$, yet $A_1$ and $A_2$
are not easily compared since one or the other may dominate
depending on the values chosen for $k$, and $\ell$. None the less,
we may simplify matters a little by absorbing $A_3$ into $A_2$ in
the following way:

\begin{align*}\frac{A_2+A_3}{t^3(b_5t)^{2\ell(2t-2)}/(e^{2t}b_0^{2t-2})}
&\le \frac{16t}{2t-1} +
\frac{b_0^{2t-2}(2t)^{2t}}{t(2t-1)(b_5t)^{2(2t-2)}}\\
&=\frac{16t}{2t-1} +
\lt\frac{4t}{2t-1}\rt\lt\frac{2b_0}{b_5^2t}\rt^{2t-2}\\
&\le\frac{16t_0}{2t_0-1} +\lt\frac{4t_0}{2t_0-1}\rt\lt\frac{2b_0}{b_5^2t_0}\rt^{2t_0-2}\\
&\le 8.000188756.
\end{align*}

So, let

\begin{equation*}A_2'=8.000188756\frac{t^3(b_5t)^{2\ell(2t-2)}}{e^{2t}b_0^{2t-2}}.
\end{equation*}
Then we may take

\begin{equation*}h_1 = (b_5t)^{\ell(2t-2)}(A_1 + A_2').
\end{equation*}
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Remark 9

\begin{remark}\label{r:3}
Note that
\begin{equation*}t=
\left\lfloor6\lt\frac{2}{b_0}\rt^{3(k+1)}(k+2)^{8\ell k +10\ell
+3}\right\rfloor=\lfloor2g^2h\rfloor,
\end{equation*}
and so

\begin{equation*}\frac{1}{t+1}\le \frac{1}{2(g+1)(g-1)h}.
\end{equation*}
\end{remark}


\begin{lemma}\label{l:4}There exists an $N=N(k,\ell)>0$, such
that if $n\ge N$, then

\begin{equation*}p^{(k)}(n)\ge p_C^{(-1)}(n)>0.
\end{equation*}
\end{lemma}

\begin{proof}
The second inequality is obvious. For the first, by
Proposition~\ref{p:1}, Theorem~\ref{t:4}, Lemma~\ref{l:6} and
Remark~\ref{r:3}, we have that for $n\ge h_1$,
\begin{equation}\label{e:5}\frac{p_C(n)}{p_C^{(-1)}(n)} \le \frac{1}{t+1} +
\frac{(t-1)^2}{t+1}\frac{1}{p_{B_1}^{(-1)}(n)n^{-(2t-3)}} \le
\frac{1}{(g+1)(g-1)h}.
\end{equation}

Now, using,~\eqref{e:27},~\eqref{e:28},~\eqref{e:29},~\eqref{e:5},
and the identity

\begin{equation*}
p^{(k)}(n) = \sum_{m=0}^np_B^{(k)}(n-m)p_C(m),
\end{equation*}
we have that for $n\ge h+h_1-1$,

\begin{align*}p^{(k)}(n) \ge&
2\sum_{0\le m\le n-h}(1+|p_B^{(k+1)}(n-m)|)p_C(m)\\
&- (g-1)\sum_{n-h<m\le n}(1+|p_B^{(k+1)}(n-m)|)p_C(m)\\
\ge& 2\sum_{m=0}^{n}(1+|p_B^{(k+1)}(n-m)|)p_C(m) -
(g+1)(g-1)\sum_{n-h<m\le n}p_C(m)\\
\ge& 2\sum_{m=0}^{n}(1+|p_B^{(k+1)}(n-m)|)p_C(m)\\
&- (g^2-1)\lt
\sum_{n-h<m\le n}^n\frac{p_C(m)}{p^{(-1)}_C(m)} \rt p_C^{(-1)}(n)\\
\ge& \left(2 - (g^2-1)\sum_{n-h< m\le n}\frac{p_C(m)}{p^{(-1)}_C(m)}
\right)\times\sum_{m=0}^{n}(1+|p_B^{(k+1)}(n-m)|)p_C(m)\\
\ge& \sum_{m=0}^{n}(1+|p_B^{(k+1)}(n-m)|)p_C(m)\\
\ge& \sum_{m=0}^{n}p_C(m)\\
=& p_C^{(-1)}(n).\\
\end{align*}

\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Proof of Theorem 1
\begin{flushleft}
\textit{Proof of Theorem~\ref{t:2}.}
\end{flushleft}
By the proofs of Lemmas~\ref{l:6} and~\ref{l:4}, it suffices us to
choose $N\ge h+h_1 = h + (b_5t)^{\ell(2t-2)}(A_1 + A_2')$. First
observe that $A_2'\ge 2t$. The quantity $(b_5t)^{\ell(2t-2)}A_1$ may
be simplified further with an upper bound. Let

\begin{equation*}b_9 = \frac{\log{b_5}}{x_0^2} + \frac{1}{x_0} + b_6 = 3.630910490\ldots,
\end{equation*}
and

\begin{equation*}b_{10} = \frac{2}{b_2b_4}.
\end{equation*}
Then

\begin{align*}(b_5t)^{\ell(2t-2)}A_1 &= b_7t\lt
\frac{b_{10}(b_5t)^{\ell}e^{b_6\ell\log^2{t}}}{b_1^{(k+3)^{\ell}}}
\rt^{2t-2}\\
&= b_7t\lt \frac{b_{10}e^{\ell(\log{b_5} + \log{t} +
b_6\log^2{t})}}{b_1^{(k+3)^{\ell}}}
\rt^{2t-2}\\
&\le b_7t\lt \frac{b_{10}e^{b_9\ell\log^2{t}}}{b_1^{(k+3)^{\ell}}}
\rt^{2t-2}
\end{align*}

Denote

\begin{equation*}A_1'=b_7t\lt
\frac{b_{10}e^{b_9\ell\log^2{t}}}{b_1^{(k+3)^{\ell}}} \rt^{2t-2}.
\end{equation*}

 We will
use the fact that $h\le t$ to absorb $h$ into
$(b_5t)^{\ell(2t-2)}A_2'$ in the following way:

\begin{align*}\frac{h+(b_5t)^{\ell(2t-2)}A_2'}{t^3(b_5t)^{3\ell(2t-2)}/(e^{2t}b_0^{2t-2})}
&\le \frac{e^{2t}b_0^{2t-2} }{t^2(b_5t)^{3(2t-2)}} + 8.000188756\\
&= \frac{e^2}{t^2}\lt\frac{eb_0}{b_5^3t^3}\rt^{2t-2}+ 8.000188756\\
&\le \frac{e^2}{t_0^2}\lt\frac{eb_0}{b_5^3t_0^3}\rt^{2t_0-2}+ 8.000188756\\
&\le 8.000188757
\end{align*}

Letting $b_8 = 8.0002$, we may take

\begin{align*}N &= A_1' +
\frac{b_8t^3(b_5t)^{3\ell(2t-2)}}{e^{2t}b_0^{2t-2}}\\
&= b_7t\lt \frac{b_{10}e^{b_9\ell\log^2{t}}}{b_1^{(k+3)^{\ell}}}
\rt^{2t-2} + \frac{b_8t^3(b_5t)^{3\ell(2t-2)}}{e^{2t}b_0^{2t-2}}.
\end{align*}

We conclude the proof by restructuring the constants as follows:
\begin{align*}a_1&=b_7\\
a_2&=b_{10}^2\\
a_3&=e^{2b_9}\\
a_4&=b_1^2\\
a_5&=e^{-2}b_8\\
a_6&=e^{-2}b_0^{-2}\\
a_7&=b_5.
\end{align*}
\begin{flushright} $\Box$
\end{flushright}





















































\section{Asymptotic results}\label{s:1}



Observe that as $k\rightarrow\infty$, $\log{t}\asymp k\log{k}$, when
$\ell$ remains fixed. This implies that if $\ell>2$, then
\begin{equation*}\frac{a_3^{\ell\log^2{t}}}{a_4^{(k+2)^{\ell}}}\rightarrow
0, \text{ as $k\rightarrow\infty$},
\end{equation*}
and so in this situation, the second term dominates in the
expression for $N(k,\ell)$ in Theorem~\ref{t:2}.

If $\ell=1$ or 2, then
\begin{equation*}\frac{a_3^{\ell\log^2{t}}}{a_4^{(k+2)^{\ell}}} =
e^{\lambda_1(k)},
\end{equation*}
where $\lambda_1(k)\asymp k^2\log^2{k}$, and
\begin{equation*}(a_7t)^{6\ell} = e^{\lambda_2(k)},
\end{equation*}
where $\lambda_2(k)\asymp k\log{k}$. In this case the first term
dominates in the expression for $N(k,\ell)$. Thus we have proved the
following corollary to Theorem~\ref{t:2}:

\begin{corollary}\label{c:1}Let $\ell\in\mathbb{N}$ be fixed.
Then as $k\rightarrow\infty$,
\begin{align*}F(k,\ell)&=O\lt t\lt \frac{a_2a_3^{\ell\log^2{t}}}{a_4^{(k+3)^{\ell}}}
\rt^{t-1}\rt, \text{ if $\ell=1,2$};\\ F(k,\ell)&=O\lt t^3\lt
a_6(a_7t)^{6\ell} \rt^{t-1}\rt, \text{ if $\ell>2$}.
\end{align*}
\end{corollary}

Theorem~\ref{t:5} follows from Corollary~\ref{c:1} simply by taking
logarithms.

%%%%%thm t:5 cut from here

\section{Acknowledgements}
The author is supported by an NSERC CGS D research grant and wishes
to acknowledge the Natural Sciences and Engineering Research Council
for their generous funding, as well as the support of his supervisor
Dr. Izabella Laba.


\begin{thebibliography}{99}

\bibitem{gH16}
G. H. Hardy, and S. Ramanujan, Asymptotic formulae for the
distribution of integers of various types, \emph{Proc. London Math.
Soc., Ser. 2,} \textbf{16} (1916), 112--132.

\bibitem{pE42}
P. Erd\H{o}s, On an elementary proof of some asymptotic formulas in
the theory of partitions, \emph{Ann. Math.,} \textbf{43} (1942),
437--450.

\bibitem{cH54}
C. G. Haselgrove, and H. N. V. Temperley, Asymptotic formulae in the
theory of partitions, \emph{Proc. Cambridge Philos. Soc.,}
\textbf{50} Part 2 (1954), 225--241.

\bibitem{oG55}
O. P. Gupta, and S. Luthra, Partitions into primes, \emph{Proc. Nat.
Inst. Sci. India,} \textbf{A21} (1955), 181--184.

\bibitem{pB56}
P. T. Bateman, and P. Erd\H{o}s, Monotonicity of partition
functions, \emph{Mathematika,} \textbf{3} (1956), 1--14.

\bibitem{2pB56}
P. T. Bateman, and P. Erd\H{o}s, Partitions into primes, \emph{Publ.
Math. Debrecen,} \textbf{4} (1956), 198--200.

\bibitem{tM57}
Takayoshi Mitsui, On the partitions of a number into the powers of
prime numbers, \emph{J. Math. Soc. Japan,} \textbf{9} (1957),
428--447.

\bibitem{eG60}
E. Grosswald, Partitions into prime powers, \emph{Michigan Math.
J.,} \textbf{7} (1960), 97--122.

\bibitem{sK69}
S. M. Kerawala, On the asymptotic values of $\ln{p_A(n)}$ and
$\ln{p_A^(d)(n)}$ with $A$ as the set of primes, \emph{J. Natur.
Sci. and Math.,} \textbf{9} (1969), 209--216.

\bibitem{lR75}
L. B. Richmond, Asymptotic relations for partitions, \emph{J. Number
Theory,} \textbf{7} (1975), 389--405.

\bibitem{lR760}
L. B. Richmond, Asymptotic results for partitions (I) and the
distribution of certain integers, \emph{J. Number Theory,}
\textbf{8} (1976), 372--389.

\bibitem{lR76}
L. B. Richmond, Asymptotic results for partitions (II) and a
conjecture of Bateman and Erd\H{o}s, \emph{J. Number Theory,}
\textbf{8} (1976), 390--396.

\bibitem{lR762}
L. B. Richmond, Asymptotic relations for partitions, \emph{Trans.
Amer. Math. Soc.,} \textbf{219} (1976), 379--385.


\end{thebibliography}





\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A17; Secondary 11P81.

\noindent \emph{Keywords: } 
partition function, difference function.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000607} and
\seqnum{A090677}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 10 2006;
revised version received  November 18 2006.
Published in {\it Journal of Integer Sequences}, December 29 2006.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}