\documentclass[12pt,reqno]{article}

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

\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{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://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}
\begin{document}

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


\begin{center}
\vskip 1cm{\LARGE\bf Integer Partitions and Convexity} \vskip 1cm
\large Sadek Bouroubi\\
USTHB\\
Faculty of Mathematics\\
Department of Operational Research\\
Laboratory LAID3\\
P. O. Box 32\\
16111 El-Alia\\
Bab-Ezzouar, Algiers\\
Algeria\\
\href{mailto:sbouroubi@usthb.dz}{\tt sbouroubi@usthb.dz}\\
\href{mailto:bouroubis@yahoo.fr.}{\tt bouroubis@yahoo.fr}\\
\end{center}

\vskip .2in

\begin{abstract}
\noindent Let $n$ be an integer $\geq 1$, and let $p(n,k)$ and
$P(n,k)$ count the number of partitions
of $n$ into $k$ parts, and the number of partitions of $n$ into parts
less than or equal to $k$, respectively.
In this paper, we show that these
functions are convex. The result includes the actual value of the
constant of Bateman and Erd\H{o}s.
\end{abstract}


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


\section{Introduction}
The $k^{th}$ difference $\Delta^{k}f$ of any function $f$ of the
nonnegative integers  is defined recursively by
$\Delta^{k}f=\Delta(\Delta^{k-1}f)$, with $\Delta f(n)=f(n)-f(n-1)$
for $n\geq1$ and $\Delta f(0)=f(0)$. Good \cite{Good2} studied the
behavior of $\Delta^{k}p(n)$, where $p(n)$ denotes the total number
of partitions of $n$. He initially conjectured \cite{Good2} that if
$k>3$, then the sequence $\Delta^{k}p(n)$, $n\geq0$ alternates in
sign. However, computations by Razen, and, independently, by Good
\cite{Good2}, found counterexamples to this conjecture, and led to a
new conjecture, namely that $\Delta^{k}p(n)>0$ for each fixed $k$.
Good \cite{Good2} even made a stronger conjecture that for each $k$,
there is an $n_{0}(k)$ such that $\Delta^{k}p(n)$ alternates in sign
for $n<n_{0}(k)$, and $\Delta^{k}p(n)\geq0$ for $n\geq n_{0}(k)$. He
also suggested that $6(k-1)(k-2)+k^{3}/2$ might be a good
approximation to $n_{0}(k)$. Some further computations by Gaskin led
Good to revise his conjecture about the size of $n_{0}(k)$, and
suggest that $\pi k^{5/2}$ might be a good approximation to it
\cite{Good3}.

At about the same time as the first publication of Good's problem,
the same question about the sign of $\Delta^{k}p(n)$ was also raised
independently by Andrews, and was answered by Gupta \cite{Gupta}.
Gupta noted that $\Delta p(n)>0$ for all $n$, and gave a simple
proof of the result that $\Delta^{2}p(n)\geq0$ for $n\geq2$, while
$\Delta^{2}p(0)=1$, $\Delta^{2}p(1)=-1$; in other
words, he showed that the function $p(n)$ is convex for $n\geq2$.

Another easy proof that $\Delta^{k}p(n)$ is positive for large $n$
can be obtained by applying the result of the theorem of Beteman and
Erd\H{o}s \cite{Bateman}. They showed that if $p(\mathcal{A},n)$ is
the number of partitions of $n$ into parts taken from
$\mathcal{A}\subset\{1,2,3,\ldots\}$, then
$\Delta^{k}p(\mathcal{A},n)\geq0$ for all $n$ large enough iff the
greatest common divisor of each subset
$\mathcal{B}\subseteq\mathcal{A}$ with $\mid\mathcal{A}\setminus
\mathcal{B}\mid=k$ is equal to 1.  In particular, the theorem of
Beteman and Erd\H{o}s asserts that there is
$n_{0}=n_{0}(\mathcal{A})$ such that the function $p(\mathcal{A},n)$
is convex for $n\geq n_{0}$ iff for all pairs $\{a, b\}$ of
$\mathcal{A}$, $\gcd(\mathcal{A}\setminus\{a, b\})=1$.

For more historical details see \cite{Odl}. The aim of this paper is
to give the actual form of this result when
$\mathcal{A}=\{1,2,\ldots,k\}$.

\section{Definitions and notation}
A \emph{partition} of an integer $n$ into $k$ parts $(1\leq k\leq
n)$ is an integer solution of the system:
\begin{eqnarray}\label{eq1}
\left\{\begin{array}{l}
n=a_{1}+2a_{2}+\cdots+na_{n},\\
k=a_{1}+a_{2}+\cdots+a_{n},\\
a_{i}\geq 0,\ i=1,\ldots ,n,
\end{array} \right.
\end{eqnarray}
where $a_{i}$ counts the number of parts $i$.

Thus, a partition of $n$ into parts less than or equal to $k$ is an
integer solution of the following system:
\begin{eqnarray}\label{eq2}
\left\{\begin{array}{l} n=a_{1}+2a_{2}+\cdots+ka_{k},

a_{i}\geq 0,\ i=1,\ldots ,k.
\end{array} \right.
\end{eqnarray}
\noindent Let $p(n)$, $p(n,k)$ and $P(n,k)$ be respectively the
total number of partitions of $n$, the number of partitions of $n$
into exactly $k$ parts and the number of partitions of $n$ into
parts less than or equal to $k$. According to Bouroubi
\cite{bouroubi} and Comtet \cite{comtet}, we have
\begin{eqnarray}\label{eq3}
p(n)=P(n,n),
\end{eqnarray}
\begin{eqnarray}\label{eq4}
p(n,k)=p(n-1,k-1)+p(n-k,k),
\end{eqnarray}
\begin{eqnarray}\label{eq5}
p(n,k)=P(n-k,k),
\end{eqnarray}
and
\begin{eqnarray}\label{eq6}
P(n,k)=P(n,k-1)+P(n-k,k).
\end{eqnarray}

\section{Convexity of the functions $(P(n,k))_{n}$ and $(p(n,k))_{n}$}
\begin{theorem}\label{th2}
The function $P(n,k)$ is convex for $n\geq2$ and $k\geq7$.
\end{theorem}

\begin{proof}
Setting,
\begin{eqnarray*}
\gamma(n,k)=P(n,k)+P(n-2,k)-2P(n-1,k).
\end{eqnarray*}
First we note that if $n\leq k$ then
\begin{eqnarray*}
\gamma(n,k)=P(n,n)+P(n-2,n-2)-2P(n-1,n-1).
\end{eqnarray*}
From (\ref{eq3}), we get $\gamma(n,k)=p(n)+p(n-2)-2p(n-1)>0$.

\noindent Suppose now $n>k$, since $\gamma(7,6)=\gamma(13,6)=-1$,
let us show by mathematical induction on $k$ that $\gamma(n,k)$ is
positive for every $n$, $n>k\geq7$. For that we consider $g_{k}$ the
generating function of $P(n,k)$ \cite{comtet}, i.e.,
\begin{eqnarray*}
g_{k}(z)=\frac{1}{(1-z)\cdots (1-z^{k})},\ \mid z\mid < 1.
\end{eqnarray*}
Thus, the generating function of $\gamma(n,k)$ equals
\begin{eqnarray*}
h_{k}(z)=\frac{(1-z)^{2}}{\prod\limits_{i=1}^{k}(1-z^{i})}\cdot
\end{eqnarray*}
Hence
\begin{eqnarray*}
h_{k}(z)=\frac{1}{1-z^{k}}\ h_{k-1}(z).
\end{eqnarray*}
Consequently
\begin{eqnarray*}
\gamma(n,k)=\sum\limits_{j=0}^{n}\alpha(j,k)\ \gamma(n-j,k-1),
\end{eqnarray*}
where $\alpha(j,k)=1$ if $k$ divides $j$ and $\alpha(j,k)=0$
otherwise.\vspace{0.5cm}\\
Now let us show that $\gamma(n,7)\geq0$ for every $n\geq8$.

\noindent By the decomposition of the rational function of
$h_{7}(z)$ into partial fractions, we get

\begin{eqnarray*}
\begin{array}{lll}
\vspace*{0.4cm}
h_{7}(z)&=&\frac{1}{5040}\frac{1}{(1-z)^{5}}+\frac{1}{480}\frac{1}{(1-z)^{4}}+\frac{47}{4320}\frac{1}{(1-z)^{3}}+\frac{161}{4320}\frac{1}{(1-z)^{2}}
+\frac{16051}{172800}\frac{1}{1-z}+\\&&
+\frac{1}{192}\frac{1}{(1+z)^{3}}+\frac{23}{384}\frac{1}{(1+z)^{2}}+\frac{713}{2304}\frac{1}{1+z}+\frac{1}{7}\frac{(1-z)^{2}}{1-z^{7}}
+\frac{1}{108}\frac{(21-2z)(1-z)}{1-z^{3}}+\vspace*{0.4cm}\\&&
+\frac{1}{54}\frac{(2+z)(1-z)^{2}}{(1-z^{3})^{2}}+\frac{1}{36}\frac{(1-2z)(1+z)}{1+z^{3}}
+\frac{1}{25}\frac{(2-z+z^{2}-2z^{3})(1-z)}{1-z^{5}}-\frac{1}{16}\frac{z}{1+z^{2}}\cdot
\end{array}
\end{eqnarray*}

\noindent By taking lower bounds of each of the coefficients of
$z^{n}$ for the power series expansions of the above functions we find:\\
\begin{eqnarray*}
\begin{array}{lll}
\vspace*{0.4cm}
\gamma(n,7)&\geq&\frac{1}{5040}\left(\frac{1}{24}n^{4}+\frac{5}{12}n^{3}+\frac{35}{24}n^{2}+\frac{25}{12}n+1\right)+\frac{1}{480}\left(\frac{1}{6}n^{3}+n^{2}+\frac{11}{6}n+1\right)+\\\vspace*{0.4cm}&&
+\frac{47}{4320}\left(\frac{1}{2}n^{2}+\frac{3}{2}n+1\right)+\frac{161}{4320}(n+1)+\frac{16051}{172800}-\frac{1}{192}(\frac{1}{2}n^{2}+\frac{3}{2}n+1)-\\&&-\frac{23}{384}(n+1)
-\frac{713}{2304}-\frac{2}{7}-\frac{23}{108}-\frac{1}{54}(n+2)-\frac{1}{18}+\frac{2}{25}+\frac{1}{16}\cdot
\end{array}
\end{eqnarray*}
i.e.,
\begin{eqnarray*}
\begin{array}{lll}
\vspace{0.4cm}
\gamma(n,7)&\geq&\frac{1}{120960}n^{4}+\frac{13}{30240}n^{3}+\frac{1}{192}n^{2}-\frac{859}{30240}n-\frac{16451}{24192}
  \\\vspace*{0.4cm}&=&
0.8267195767\ 10^{-5}\times(n+30.63520805)\times(n-9.699836835)\\\
&\times&(n^{2}+31.064628784\ n+276.8069841)\cdot
\end{array}
\end{eqnarray*}
Hence
\begin{eqnarray*}
\gamma(n,7)\geq0, \forall n\geq10.
\end{eqnarray*}
For $n\in \{8,9\}$, we have
\begin{eqnarray*}
\gamma(8,7)=2\ ; \ \gamma(9,7)=1.
\end{eqnarray*}
Suppose now that $\gamma(n,j)\geq0$, for $7\leq j\leq k-1$ and show
that $\gamma(n,k)\geq0$.\vspace{0.5cm}

\noindent On the one hand, we have
\begin{eqnarray*}
\begin{array}{lll}
\vspace{0.4cm}
\gamma(n,k)&=&\alpha(n,k)-\alpha(n-1,k)+\alpha(n-k-1,k)\
\gamma(k+1,k-1)\ +\\\vspace{0.4cm}&+& \sum\limits_{j=0:j\neq
n-k-1}^{n-2}\alpha(j,k)\ \gamma(n-j,k-1).
\end{array}
\end{eqnarray*}
Hence by the induction assumption, we get
\begin{eqnarray*}
\gamma(n,k)\geq \alpha(n,k)-\alpha(n-1,k)+\alpha(n-k-1,k)\
\gamma(k+1,k-1).
\end{eqnarray*}
On the other hand from (\ref{eq6}), we have
\begin{eqnarray*}
\gamma(n,k)=\gamma(n,k-1)+\gamma(n-k,k).
\end{eqnarray*}
Therefore
\begin{eqnarray*}
\gamma(k+1,k-1)=\gamma(k+1,k-2)+\gamma(2,k-1)=1+\gamma(k+1,k-2).
\end{eqnarray*}\vspace{0.05 cm}

- if $k-2\geq7$ then $\gamma(k+1,k-2)\geq0$, by the induction
assumption.

- if $k-2=6$ then $\gamma(k+1,k-2)=\gamma(9,6)=0$.\\

\noindent Consequently
\begin{eqnarray*}
\gamma(n,k)\geq\alpha(n,k)-\alpha(n-1,k)+\alpha(n-k-1,k)\geq0.
\end{eqnarray*}
Indeed

- if $k$ divides $n$ then
$\alpha(n,k)-\alpha(n-1,k)+\alpha(n-k-1,k)=1$,

- if $k$ divides $n-1$ then
$\alpha(n,k)-\alpha(n-1,k)+\alpha(n-k-1,k)=0$,

- if $k$ divides neither $n$ nor $n-1$ then
$\alpha(n,k)-\alpha(n-1,k)+\alpha(n-k-1,k)=0$.
\end{proof}
\begin{corollary}
The function $p(n,k)$ is convex for $n\geq k+2$ and $k\geq7$.
\end{corollary}
\begin{proof}
Using (\ref{eq5}), we have
\begin{eqnarray*}
p(n,k)+p(n-2,k)-2p(n-1,k)=P(n-k,k)+P(n-k-2,k)-2P(n-k-1,k),
\end{eqnarray*}
and the result follows immediately, using Theorem \ref{th2}.
\end{proof}

\begin{Remark} Using the same method we can show that the function
$P(n,5)$ and $P(n,6)$ are convex for $n\geq2$ and $n\geq14$
respectively. We give below the value of $\gamma(n,5)$ and
$\gamma(n,6)$, for $0\leq n\leq20$.
\end{Remark}
\begin{table}[htbp]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  $n$&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20\\
  \hline
  $\gamma(n,5)$&1&-1&1&0&1&0&1&0&2&0&2&0&3&2&3&1&3&1&4&1&5 \\
  \hline
  $\gamma(n,6)$&1&-1&1&0&1&0&2&-1&3&0&3&0&5&-1&6&1&6&1&9&0&11 \\
  \hline
\end{tabular}
\caption{The value of $\gamma(n,5)$ and $\gamma(n,6)$, for $0\leq
n\leq20$.\label{table-nom}}
\end{center}
\end{table}
\section{Conclusion}Let $\mathcal{A}=\{1,2,\ldots,k\}$,
$k\geq2$. In this paper we showed that the partition function
$P(\mathcal{A},n)$ is convex for $k\geq5$ and the constant of
Bateman and Erd\H{o}s, $n_{0}(\mathcal{A})$ equals 2 if $k=5$ or
$k\geq7$, however for $\mathcal{A}=\{1,2,3,4,5,6\}$,
$n_{0}(\mathcal{A})=14$.

\section{Acknowledgments} The author would like to thank the
referee for the detailed instructive \mbox{comments} and suggestions
which helped to improve the quality of the paper.

\begin{thebibliography}{12}
\bibitem[1]{Andrews}
G. E. Andrews, The Theory of Partitions, \emph{Encyclopedia of
Mathematics and its Applications}, Vol. 2, Addison-Wesley, 1976.

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

\bibitem[3]{bouroubi}
S. Bouroubi, \emph{Optimisation dans les Posets}, Th\'{e}se de
Doctorat d'Etat en Math\'{e}matiques, USTHB, Alger, 2004.

\bibitem[4]{comtet}
L. Comtet, \emph{Advanced Combinatorics}, D. Reided, Dordrecht,
1974.

\bibitem[5]{Good2}
I. J. Good and R. Razen, Solution to
Advanced Problem 6137. \emph{Amer. Math. Monthly}, \textbf{85}
(1978), 830--831.

\bibitem[6]{Good3}
I. J. Good, Solution to Advanced Problem
6137. \emph{Amer. Math. Monthly}, \textbf{88} (1981), 215.

\bibitem[7]{Gupta}
H. Gupta, Finite differences of the partition function. \emph{Math.
Comp.}, \textbf{32} (1978), 1241--1243.

\bibitem[8]{Odl}
A. M. Odlyzko, Differences of the partition function, \emph{Acta
Arithmetica}, \textbf{49} (1988), 237--254.
\end{thebibliography}


\bigskip
\hrule
\bigskip


\noindent 2000 {\it Mathematics Subject Classification}: Primary 11P81.


\noindent \emph{Keywords: } integer partition, convexity.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence \seqnum{A026812}.)

\bigskip
\hrule
\bigskip


\vspace*{+.1in} \noindent Received March 6 2007;  revised version 
received June 9 2007.  Published in {\it Journal of
Integer Sequences}, June 10 2007.
\bigskip
\hrule
\bigskip

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

\end{document}