%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% Note on hyper m-ary partitions (with Kevin Courtright) %%%% %%%% Submitted to INTEGERS, March 2004 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \documentclass[12pt]{article} \textwidth= 6.25in \textheight= 9.0in \topmargin = -10pt \evensidemargin=10pt \oddsidemargin=10pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 %\usepackage{hyperref} \usepackage{amssymb} \usepackage{amsthm} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \newtheorem{Lemma}{Lemma}[section] \newtheorem{Theorem}[Lemma]{Theorem} \newtheorem{Prop}[Lemma]{Proposition} \newtheorem{Corollary}[Lemma]{Corollary} \newcommand{\N}[2]{N^{\#}_{#1}(#2)} \newtheorem{Notation}[Lemma]{Notation} \newtheorem{Remark}[Lemma]{Remark} \newtheorem{Table}[Lemma]{Table} \newtheorem{Definition}[Lemma]{Definition} %\renewcommand{\baselinestretch}{1.2} %\renewcommand{\arraystretch}{.7} \begin{document} %\title{Arithmetic Properties for Hyper $m$--ary Partition Functions} %\author{Kevin M. Courtright \ \ and \ \ James A. Sellers\\ %\\ %Department of Mathematics\\ %The Pennsylvania State University\\ %University Park, PA 16802\\ %\\ %{\tt kmc260@psu.edu} \ \ and \ \ {\tt sellersj@math.psu.edu}} %\date{\today} %\maketitle %\begin{abstract} %Numerous functions which enumerate partitions into powers of a fixed %number $m$ have been studied ever since Churchhouse's original work in %the late 1960's on the unrestricted binary partition function. In %particular, Calkin and Wilf recently considered the hyperbinary partition %function (as they ``recounted the rationals''). In this paper, we first %prove an unexpected partition congruence satisfied by the hyperbinary %partition function. We then consider a natural generalization of %hyperbinary partitions, which we call hyper $m$--ary partitions, and %prove surprising arithmetic properties for these via elementary means. %\end{abstract} \begin{center} {\bf ARITHMETIC PROPERTIES FOR HYPER $M$--ARY PARTITION FUNCTIONS} \vskip 20pt {\bf Kevin M. Courtright}\\ {\smallit Department of Mathematics, The Pennsylvania State University, University Park, PA 16802}\\ {\tt kmc260@psu.edu}\\ \vskip 10pt {\bf James A. Sellers}\\ {\smallit Department of Mathematics, The Pennsylvania State University, University Park, PA 16802}\\{\tt sellersj@math.psu.edu}\\ \end{center} \vskip 30pt \centerline{\smallit Received: 3/3/04, Accepted: 4/23/04, Published: 4/23/04} \vskip 30pt \centerline{\bf Abstract} \noindent Numerous functions which enumerate partitions into powers of a fixed number $m$ have been studied ever since Churchhouse's original work in the late 1960's on the unrestricted binary partition function. In particular, Calkin and Wilf recently considered the hyperbinary partition function (as they ``recounted the rationals''). In this paper, we first prove an unexpected partition congruence satisfied by the hyperbinary partition function. We then consider a natural generalization of hyperbinary partitions, which we call hyper $m$--ary partitions, and prove surprising arithmetic properties for these via elementary means. \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 4 (2004), \#A06\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 30pt \begin{section}*{\normalsize 1. Introduction} \addtocounter{section}{+1} In a recent note, Calkin and Wilf \cite{CalkinWilf} utilized the enumerating function for hyperbinary partitions, $h_2(n),$ to ``recount the rationals.'' Here $h_2(n)$ is the number of ways of writing $n$ as a sum of powers of 2, wherein each power of 2 is allowed to be used as a part at most twice. Our first goal in this note is to study $h_2(n)$ from a different perspective, that of partition congruences in arithmetic progressions, and Section \ref{section_binary} is devoted to this. Then, in Section \ref{section_m-ary}, we consider a natural generalization of $h_2(n),$ denoted $h_m(n)$, which is the number of partitions of $n$ into parts which are powers of $m\geq 2$ wherein each power of $m$ is allowed to be used as a part at most $m$ times. We close by proving a surprising infinite family of arithmetic results for $h_m(n)$ for $m\geq 3$ which imply infinitely many partition congruences in arithmetic progressions. \end{section} \begin{section}*{\normalsize 2. A Congruence for Hyperbinary Partitions} \addtocounter{section}{+1} \label{section_binary} We now focus our attention on arithmetic properties of the function $h_2(n).$ Such a perspective is not at all new. Beginning with Churchhouse's groundbreaking work on the (unrestricted) binary partition function \cite{Churchhouse}, numerous authors have considered arithmetic properties for a wide variety of related binary partition functions \cite{Gupta3}, \cite{Reznick}, \cite{RodsethSellersJCTA}. It appears that very few congruences in arithmetic progressions exist for $h_2(n).$ Indeed, only one such congruence is evident (based on extensive computational evidence). We prove that congruence here. \begin{Theorem} \label{mainthm-binary} For all $n\geq 0,$ $h_2(3n+2) \equiv 0 \pmod{2}.$ \end{Theorem} \begin{proof} Rather than resorting to the usual proof techniques (such as generating function dissections or bijective arguments), we prove this result by contradiction, using the following recurrences (for $n\geq 0$) provided by Calkin and Wilf \cite{CalkinWilf} (and the fact that $h_2(0)=1$): \begin{equation} \label{recurs} h_2(2n+1) = h_2(n) \textrm{\ \ \ and\ \ \ } h_2(2n+2) = h_2(n+1)+h_2(n) \end{equation} These quickly follow from the fact that the generating function for $h_2(n)$ is given by $$H_2(q):= \sum_{n\geq 0} h_2(n) q^n = \prod_{i\geq 0} (1+q^{2^i} + q^{2\cdot 2^i}),$$ which means $$ H_2(q) = (1+q+q^2)H_2(q^2). $$ We assume, to contradict, that $N$ is the {\bf smallest} positive integer such that $h_2(3N+2)$ is odd. We then consider three cases: \noindent \textbf{Case 1:} $N=2J+1$ for some integer $J$ \begin{eqnarray*} \textrm{Then\ \ } h_2(3N+2) &=& h_2(6J+5)\\ &=& h_2(3J+2) \end{eqnarray*} by (\ref{recurs}). This yields a contradiction, as $J$ is clearly less than $N.$ \noindent \textbf{Case 2:} $N=4J$ for some integer $J$ \begin{eqnarray*} \textrm{Then\ \ } h_2(3N+2) &=& h_2(12J+2) \\ &=& h_2(6J+1) + h_2(6J) \textrm{\ \ \ by (\ref{recurs})}\\ &=& h_2(3J) + h_2(3J) + h_2(3J-1) \textrm{\ \ \ by (\ref{recurs})}\\ &\equiv & h_2(3J-1) \pmod{2}\\ &=& h_2(3(J-1)+2). \end{eqnarray*} This again yields a contradiction. \noindent \textbf{Case 3:} $N=4J+2$ for some integer $J$ \begin{eqnarray*} \textrm{Then\ \ } h_2(3N+2) &=& h_2(12J+8) \\ &=& h_2(6J+4) + h_2(6J+3) \textrm{\ \ \ by (\ref{recurs})}\\ &=& h_2(3J+2) + h_2(3J+1) + h_2(3J+1) \textrm{\ \ \ by (\ref{recurs})}\\ &\equiv & h_2(3J+2) \pmod{2}. \end{eqnarray*} This is a contradiction and the proof is complete. \end{proof} We close this section with two remarks. First, it is clear that results involving $h_2(n)$ and geometric progressions exist in abundance. For example, one can easily prove by induction that $h_2(2^{n-1}(2^m-1)) = mn-(m-1)$ for all $m\geq 0$ and $n\geq 1.$ In contrast, a result involving an arithmetic progression, such as Theorem \ref{mainthm-binary}, is quite unexpected. Secondly, Theorem \ref{mainthm-binary} can be strengthened. Calkin and Wilf note that, for all $n\geq 0,$ $\gcd(h_2(n+1), h_2(n)) =1.$ Hence, the theorem implies that $h_2(3n+1)$ and $h_2(3n+3)$ must be odd for all $n\geq 0.$ Therefore, we know $$ h_2(\ell) \equiv 0 \pmod{2} \textrm{\ \ if and only if\ \ } \ell \equiv 2 \pmod{3} $$ for all nonnegative integers $\ell.$ \end{section} \begin{section}*{\normalsize 3. A Natural Generalization} \label{section_m-ary} \addtocounter{section}{+1} \addtocounter{Lemma}{-1} Soon after Churchhouse \cite{Churchhouse} wrote his landmark paper on the unrestricted binary partition function $b_2(n),$ which enumerates the partitions of $n$ into parts which are powers of 2, Andrews \cite{Andrews1}, Gupta \cite{Gupta}, and R\o dseth \cite{Rodseth} proved all of Churchhouse's results and generalized his work by considering $b_m(n),$ the enumerating function for partitions of $n$ into parts which are powers of $m$ for some fixed $m\geq 2.$ Since that time, numerous authors have considered related $m$--ary partition functions; see \cite{Dirdal}, \cite{DolphReynoldsSellers}, \cite{Reznick}, \cite{RodsethSellersJCTA}, and \cite{RodsethSellersJNT} for examples. In the same vein, we now generalize hyperbinary partitions in the obvious way, letting $h_m(n)$ be the number of partitions of $n$ into powers of $m$ wherein each power of $m$ is allowed to be used as a part at most $m$ times. Unlike the comment made in the previous section (that $h_2(n)$ appears to satisfy only one congruence in an arithmetic progression), it is clear that $h_m(n)$ behaves much differently for $m\geq 3.$ Indeed, we now prove that $h_m(n)$ satisfies infinitely many congruences in arithmetic progressions when $m\geq 3.$ For fixed $m\geq 2,$ the generating function for $h_m(n)$ is given by $$ H_m(q) := \sum_{n\geq 0} h_m(n) q^n = \prod_{i\geq 0} (1+q^{m^i} + q^{2m^i} + \dots + q^{m\cdot m^i}). $$ Hence, $$ H_m(q) = (1+q+q^2+\dots + q^m)H_m(q^m), $$ from which we obtain the following recurrences: \begin{equation} \label{recur0} h_m(mn) =h_m(n) + h_m(n-1), \end{equation} \begin{equation} \label{recur1} h_m(mn+r)=h_m(n) \textrm{\ \ \ \ \ \ for\ } 1\leq r\leq m-1 \end{equation} Armed with (\ref{recur0}) and (\ref{recur1}), and the fact that $h_m(0)=1,$ we can prove the following theorem which implies infinitely many congruence properties for the functions $h_m(n)$ for $m\geq 3.$ \begin{Theorem} \label{mainthm-m-ary} Let $m\geq 3$ and $j\geq 1$ be fixed integers and let $k$ be some integer between $2$ and $m-1.$ Then, for all $n\geq 0,$ $$h_m(m^jn + m^{j-1}k) = jh_m(n).$$ \end{Theorem} \begin{proof} We prove this result by induction on $j$ using the recurrences (\ref{recur0}) and (\ref{recur1}). The basis case occurs when $j=1.$ In that case, the left--hand side of Theorem \ref{mainthm-m-ary} is $h_m(mn+k).$ Since $2\leq k\leq m-1,$ we see that $h_m(mn+k) = h_m(n)$ by (\ref{recur1}) above. This is the right--hand side of Theorem \ref{mainthm-m-ary} when $j=1.$ Next, assume $h_m(m^jn+m^{j-1}k) = jh_m(n)$ for some positive integer $j.$ We then wish to prove $h_m(m^{j+1}n+m^{j}k) = (j+1)h_m(n).$ We have \begin{eqnarray*} h_m(m^{j+1}n+m^{j}k) &= & h_m(m^{j}n+m^{j-1}k) + h_m(m^{j}n+m^{j-1}k - 1) \textrm{\ \ \ by (\ref{recur0})} \\ &= & jh_m(n) + h_m(m^{j}n+m^{j-1}k - 1) \\ &= & jh_m(n) + h_m(m(m^{j-1}n+m^{j-2}k -1)+m- 1) \\ &=& jh_m(n) + h_m(m^{j-1}n+m^{j-2}k- 1) \textrm{\ \ \ by (\ref{recur1})} \\ &=& \vdots\\ &=& jh_m(n) + h_m(mn+ k- 1) \\ &=& jh_m(n) + h_m(n) \textrm{\ \ \ by (\ref{recur1})}. \end{eqnarray*} This last equality is true since $2\leq k\leq m-1,$ so that $k-1$ is clearly not a multiple of $m$. The last quantity above is clearly equal to $(j+1)h_m(n),$ which completes the proof. \end{proof} We close with two comments. First, Theorem \ref{mainthm-m-ary} clearly implies that for all $m\geq 3,$ $j\geq 1,$ $k$ between 2 and $m-1,$ and $n\geq 0,$ $$h_m(m^jn + m^{j-1}k) \equiv 0 \pmod{j}.$$ Secondly, Theorem \ref{mainthm-m-ary} can also be used to find additional results (of similar form) by iterative substitution. For example, one of the special cases of Theorem \ref{mainthm-m-ary} is that, for all $n\geq 0,$ $h_3(9n+6) = 2h_3(n).$ Replacing $n$ by $9n+6$ in this equality yields $h_3(81n+60) = 2h_3(9n+6) = 4h_3(n).$ Because 60 is not divisible by 27, we see that this identity is different from any identity obtained by substituting $m=3$ and $j=4$ in Theorem \ref{mainthm-m-ary}. \end{section} \begin{thebibliography}{99} \footnotesize %\bibitem{And1} %G.E. Andrews, %{\it The Theory of Partitions}, %Addison-Wesley, 1976. \bibitem{Andrews1} G. E. Andrews, \textsl{Congruence properties of the $m$-ary partition function}, J. Number Theory \textbf{3} 1971, 104--110. \bibitem{CalkinWilf} N. Calkin and H. Wilf, \textsl{Recounting the rationals}, Amer. Math. Monthly \textbf{107} (2000), no. 4, 360--363. \bibitem{Churchhouse} R. F. Churchhouse, \textsl{Congruence properties of the binary partition function}, Proc. Camb. Phil. Soc. \textbf{66} (1969), 371--376. \bibitem{Dirdal} G. Dirdal, \textsl{Congruences for $m$-ary partitions}, Math. Scand. \textbf{37} (1975), no. 1, 76--82. \bibitem{DolphReynoldsSellers} L. L. Dolph, A. Reynolds, and J. A. Sellers, \textsl{Congruences for a restricted $m$-ary partition function}, Discrete Math. \textbf{219} (2000), no. 1-3, 265--269. \bibitem{Gupta} H. Gupta, \textsl{On $m$-ary partitions}, Proc. Cambridge Philos. Soc. \textbf{71} (1972), 343--345. \bibitem{Gupta3} H. Gupta, \textsl{A direct proof of the Churchhouse conjecture concerning binary partitions}, Indian J. Math. \textbf{18} (1976), 1--5. \bibitem{Reznick} B. Reznick, \textsl{Some binary partition functions}, Analytic number theory (Allerton Park, IL, 1989), 451--477, Progr. Math., 85, Birkhauser Boston, Boston, MA, 1990. \bibitem{Rodseth} \O. J. R\o dseth, \textsl{Some arithmetical properties of $m$-ary partitions}, Proc. Cambridge Philos. Soc. \textbf{68} 1970, 447--453. \bibitem{RodsethSellersJCTA} \O. J. R\o dseth and J. A. Sellers, \textsl{Binary Partitions Revisited}, J. Comb. Thy. Series A \textbf{98} (2002), 33--45. \bibitem{RodsethSellersJNT} \O. J. R\o dseth and J. A. Sellers, \textsl{On $m$-ary partition function congruences: a fresh look at a past problem}, J. Number Theory \textbf{87} (2001), no. 2, 270--281. \end{thebibliography} \end{document}