\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,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://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 On the Number of Representations of an \\ \vskip 0.05in Integer by a Linear Form} \vskip 1cm \large Gil Alon and Pete L. Clark \\ 1126 Burnside Hall \\ Department of Mathematics and Statistics \\ McGill University \\ 805 Sherbrooke West \\ Montreal, QC H3A 2K6 \\ Canada\\ \href{mailto:alon@math.mcgill.ca}{\tt alon@math.mcgill.ca}\\ \href{mailto:clark@math.mcgill.ca}{\tt clark@math.mcgill.ca}\\ \end{center} \vskip .2 in \newtheorem{theorem}{Theorem}[section] \newtheorem{thm}[theorem]{Theorem} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{prop}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{lem}[theorem]{Lemma} %\documentclass{amsart} %\usepackage{amsmath, amssymb} \title{On the number of representations of an integer by a linear form} %\begin{document} %\newtheorem{lemma}{Lemma} %\newtheorem{prop}[lemma]{Proposition} %\newtheorem{cor}[lemma]{Corollary} %\newtheorem{thm}[lemma]{Theorem} %\newtheorem*{ques}{Question} %\newtheorem{metaques}{Meta-Question} %\maketitle % \newcommand{\F}{\ensuremath{\mathbb F}} \newcommand{\N}{\ensuremath{\mathbb N}} \newcommand{\Q}{\ensuremath{\mathbb Q}} \newcommand{\R}{\ensuremath{\mathbb R}} \newcommand{\Z}{\ensuremath{\mathbb Z}} \newcommand{\C}{\ensuremath{\mathbb C}} \newcommand{\SSS}{\ensuremath{\mathcal{C}}} \newcommand{\Rn}{\ensuremath{\mathbb R^n}} \newcommand{\Ri}{\ensuremath{\R^\infty}} \newcommand{\Cn}{\ensuremath{\mathbb C^n}} \newcommand{\Ci}{\ensuremath{\C^\infty}} \newcommand{\U}{\ensuremath{\mathcal U}} \newcommand{\gn}{\ensuremath{\gamma^n}} \newcommand{\ra}{\ensuremath{\rightarrow}} \newcommand{\fhat}{\ensuremath{\hat{f}}} \newcommand{\ghat}{\ensuremath{\hat{g}}} \newcommand{\hhat}{\ensuremath{\hat{h}}} \newcommand{\covui}{\ensuremath{\{U_i\}}} \newcommand{\covvi}{\ensuremath{\{V_i\}}} \newcommand{\covwi}{\ensuremath{\{W_i\}}} \newcommand{\Gt}{\ensuremath{\tilde{G}}} \newcommand{\gt}{\ensuremath{\tilde{\gamma}}} \newcommand{\Gtn}{\ensuremath{\tilde{G_n}}} \newcommand{\gtn}{\ensuremath{\tilde{\gamma_n}}} \newcommand{\gnt}{\ensuremath{\gtn}} \newcommand{\Gnt}{\ensuremath{\Gtn}} \newcommand{\Cpi}{\ensuremath{\C P^\infty}} \newcommand{\Cpn}{\ensuremath{\C P^n}} \newcommand{\lla}{\ensuremath{\longleftarrow}} \newcommand{\lra}{\ensuremath{\longrightarrow}} \newcommand{\Rno}{\ensuremath{\Rn_0}} \newcommand{\dlra}{\ensuremath{\stackrel{\delta}{\lra}}} \newcommand{\pii}{\ensuremath{\pi^{-1}}} \newcommand{\la}{\ensuremath{\leftarrow}} \newcommand{\gonem}{\ensuremath{\gamma_1^m}} \newcommand{\gtwon}{\ensuremath{\gamma_2^n}} \newcommand{\omegabar}{\ensuremath{\overline{\omega}}} \newcommand{\dlim}{\underset{\lra}{\lim}} \newcommand{\ilim}{\operatorname{\underset{\lla}{\lim}}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\Ext}{\operatorname{Ext}} \newcommand{\Part}{\operatorname{Part}} \newcommand{\Ker}{\operatorname{Ker}} \newcommand{\im}{\operatorname{im}} \newcommand{\ordp}{\operatorname{ord}_p} \newcommand{\unr}{\operatorname{unr}} \newcommand{\B}{\ensuremath{\mathcal B}} \newcommand{\Ocr}{\ensuremath{\Omega_*}} \newcommand{\Rcr}{\ensuremath{\Ocr \otimes \Q}} \newcommand{\Cptwok}{\ensuremath{\C P^{2k}}} \newcommand{\CC}{\ensuremath{\mathcal C}} \newcommand{\gtkp}{\ensuremath{\tilde{\gamma^k_p}}} \newcommand{\gtkn}{\ensuremath{\tilde{\gamma^k_m}}} \newcommand{\PP}{\ensuremath{\mathcal P}} \newcommand{\QQ}{\ensuremath{\mathcal Q}} \newcommand{\I}{\ensuremath{\mathcal I}} \newcommand{\sbar}{\ensuremath{\overline{s}}} \newcommand{\Kn}{\ensuremath{\overline{K_n}^\times}} \newcommand{\tame}{\operatorname{tame}} \newcommand{\Qpt}{\ensuremath{\Q_p^{\tame}}} \newcommand{\Qpu}{\ensuremath{\Q_p^{\unr}}} \newcommand{\scrT}{\ensuremath{\mathfrak{T}}} \newcommand{\That}{\ensuremath{\hat{\mathfrak{T}}}} \newcommand{\Gal}{\operatorname{Gal}} \newcommand{\Aut}{\operatorname{Aut}} \newcommand{\tors}{\operatorname{tors}} \newcommand{\Zhat}{\hat{\Z}} \newcommand{\linf}{\ensuremath{l_\infty}} \newcommand{\Lie}{\operatorname{Lie}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\End}{\operatorname{End}} \newcommand{\aone}{\ensuremath{(a_1,\ldots,a_k)}} \newcommand{\raone}{\ensuremath{r(a_1,\ldots,a_k,N)}} \newcommand{\rtwoplus}{\ensuremath{\R^{2 +}}} \newcommand{\rkplus}{\ensuremath{\R^{k +}}} \newcommand{\length}{\operatorname{length}} %\newcommand{\det}{\operatorname{det}} \newcommand{\Vol}{\operatorname{Vol}} \newcommand{\cross}{\operatorname{cross}} \renewcommand{\gcd}{\operatorname{gcd}} \newcommand{\lcm}{\operatorname{lcm}} \renewcommand{\ss}{\mathfrak{s}} \newcommand{\pp}{\mathfrak{p}} \newcommand{\ff}{\mathfrak{f}} \newcommand{\qq}{\mathfrak{q}} \renewcommand{\aa}{{\bf a}} \begin{abstract} Let $a_1,\ldots,a_k$ be positive integers generating the unit ideal, and $j$ be a residue class modulo $L = \lcm(a_1,\ldots,a_k)$. It is known that the function $r(N)$ that counts solutions to the equation $x_1a_1 + \ldots + x_ka_k = N$ in non-negative integers $x_i$ is a polynomial when restricted to non-negative integers $N \equiv j \pmod L$. Here we give, in the case of $k=3$, exact formulas for these polynomials up to the constant terms, and exact formulas including the constants for $\qq = \gcd(a_1,a_2) \cdot \gcd(a_1,a_3) \cdot \gcd(a_2,a_3)$ of the $L$ residue classes. The case $\qq = L$ plays a special role, and it is studied in more detail. %The paper is %written for a general mathematical audience; in particular we have %made an effort to replace (where possible) %generatingfunctionological arguments with geometric and %combinatorial considerations. \end{abstract} \section{Introduction} We begin with some notation. For $a \in \Z$ and $n \in \Z^+$, let $\langle a \rangle_n$ denote the unique non-negative integer that is congruent to $a \pmod n$ and less than $n$. We view this as giving a map $\langle \ \rangle: \Z/n\Z \ra \{0,\ldots,n-1\}$, and the convention is that operations appearing inside the brackets are performed in the ring $\Z/n\Z$. In particular, if $\gcd(b,n) = 1$, then $\langle b^{-1} \rangle_n$ is the unique integer $N$ in the interval $[0,n-1]$ such that $Nb \equiv 1 \pmod n$. Let $a_1, \ldots, a_k$ be positive integers and $N \in \N$ be a non-negative integer. We are interested in the quantity \[r(N) = r(a_1,\ldots,a_k;N) = \# \{(x_1,\ldots,x_k) \in \N^k \ | \ x_1a_1 + \ldots +x_ka_k = N \}. \] We say that $r(N)$ counts the number of representations of $N$ by the system of weights $\aone$. A system of weights is $\aone$ is \textbf{primitive} if $\gcd(a_1,\ldots,a_k) = 1$. Given a system $(a_1,\ldots,a_k)$ of weights with $\gcd(a_1,\ldots,a_k) = d$, clearly $r(a_1,\ldots,a_k;N) = 0$ unless $N$ is a multiple of $d$. And if $N = dM$, say, then we have $r(a_1,\ldots,a_k;dM) = r(\frac{a_1}{d},\ldots,\frac{a_k}{d};M)$. So we may, and shall, consider only the primitive case. Issai Schur showed long ago that there is a simple asymptotic formula for $r(N)$ (Theorem \ref{Theorem1}(b)). We are interested in the problem of giving an ``exact formula.'' When $k = 2$ this is indeed possible: we have \textbf{Popoviciu's formula} \cite{Popoviciu} \begin{equation} r(a,b;N) = \frac{N}{ab} - \left\{ \frac{\langle a^{-1} \rangle_b N}{b} \right\} -\left\{\frac{ \langle b^{-1}\rangle_a N}{a}\right\} + 1, \end{equation} where $\{x\} = x - \lfloor x \rfloor$ denotes the fractional part of $x$. Some consequences: it follows that $r(N)$ is the sum of a polynomial $P(N)=\frac{N}{ab}$ and an $ab$-periodic function $A(N)$. Moreover, for all $N$, $-1 < A(N) \leq 1$, so \[ \left\lfloor \frac{N}{ab} \right\rfloor \leq r(a,b;N) \leq \left\lfloor \frac{N}{ab} \right\rfloor + 1. \] More precisely, the minimum value of $A$ is $1- \frac{b-1}{b} - \frac{a-1}{a}$, attained when \[\langle a^{-1}N \rangle_b \equiv -1 \pmod b, \ \langle b^{-1}N \rangle_a \equiv -1 \pmod a. \] The unique solution in the interval $[0,ab)$ is $N_0 = (a-1)(b-1) -1$. A straightforward calculation gives $r(N_0) = 0$; alternately, just observe that $A(N_0) < 0, \ \frac{N_0}{ab} < 1$, and $r(N_0) \in \N$. Also, for $N_0 < N < ab$ we have $A(N) > A(N_0)$ and $P(N) > P(N_0)$, so $r(N) > r(N_0) = 0$; and since we clearly have $r(N) \geq 1$ for $N \geq ab$, it follows that $N_0$ is the largest value of $N$ for which $r(N) = 0$. For any primitive set $\aone$ of weights, one defines the \textbf{Frobenius number} $\ff(a_1,\ldots,a_k)$ to be the largest $N$ such that $r(N) = 0$. That such a number exists is not \emph{a priori} obvious, but follows from Theorem \ref{Theorem1}(b) (or from Theorem \ref{Brauer}). Thus one of the merits of Popoviciu's formula is that from it we can ``read off'' the Frobenius number for two weights:\footnote{Admittedly this formula is easily derived in many other ways; see Section 7.} \begin{equation} \ff(a_1,a_2) = (a_1-1)(a_2-1)-1. \end{equation} The ideal would be to give a formula for $r(N)$ in the general case that is ``as satisfactory'' as (1) in the $k =2$ case. This is probably impossible, and subject to a formalization of ``as satisfactory'' may even be provably impossible: we propose the heuristic that a ``sufficiently satisfactory'' formula for $r(a_,\ldots,a_k;N)$ should (as above) lead to an exact formula for the Frobenius number $\ff(a_1,\ldots,a_k)$. However, there is no known exact formula for the Frobenius number when $k \geq 3$, although $\ff$ can be computed in polynomial time for fixed $k$ \cite{Kannan}. When $k$ is included as a parameter, it is known \cite{Ramirez-Alfonsin} that the problem of computing $\ff(a_1,\ldots,a_k)$ is NP-hard! Still, one observes in the $k = 2$ case that by restricting to values of $N$ in a fixed residue class $j$ modulo $a_1a_2$, the function $r(a_1,a_2;N)$ is a polynomial in $N$. Equivalently, for all $j$, the function $r_j(n) = r(a_1,a_2;j+a_1a_2n)$ is a polynomial. This turns out to hold true in the general case: the function $r_j(n) = r(j + a_1 \cdots a_kn)$ is a polynomial function, so we can exchange the one problem of finding a formula for $r(N)$ for the $a_1 \cdots a_k$ problems of finding the coefficients of these polynomials. The problem of finding a formula for $r_j(n)$ (for any given $j$) seems not to have received much attention as such. The reasons for this may be as follows: first, ``all one has to do'' is to compute the coefficients in the partial fraction decomposition the rational function $R(x)$ of equation (\ref{rationalfunction}). More precisely, the method of partial fractions leads to a decomposition of $r(N)$ into a finite sum of terms -- indexed by the poles of $R(x)$ -- in which the term $f_0(n)$ corresponding to the pole at $x=1$ has the highest order of magnitude. Moreover the computation of $f_0(n)$ is relatively tractable; indeed \cite{BGK} gives an exact formula for $f_0(n)$ in the general case. Computation of the other terms is more involved, but in the case in which the weights are coprime in pairs, the difference $r(n) - f_0(n)$ is a periodic function, so knowing $f_0(n)$ is enough to compute each polynomial $r_j(n)$ up to a constant. This does not hold in the general case, and here the method of partial fractions, will, in the words of \cite{Sertoz}, ``entail an enormous amount of bookkeeping.'' The unpleasantness of these calculations, together with the existence of a formula due to Johnson (\ref{Johnson}) which in the case of $k=3$ reduces the computation of the Frobenius number $\ff(a_1,a_2,a_3)$ to the pairwise coprime case, seems to have focused attention away from the problem of computation of the $r_j(n)$ in the general case. In this paper we derive explicit formulas for $r_j(a_1,a_2,a_3;n)$ up to a constant for a general primitive system $(a_1,a_2,a_3)$. In contrast to the methods described above, our approach is mostly independent of the partial fraction decomposition. Moreover, in a sense that will shortly be made precise, our results \emph{improve} as the weights become ``less and less pairwise coprime.'' In particular, for a certain class of weights (called \textbf{extremal}), we get exact formulas for $r_j(n)$ for all $j$. \section{Statement of the Main Results} Let $\aone$ be a primitive set of weights, $\PP = a_1 \cdots a_k$ and $L = \lcm(a_1,\ldots,a_k)$. For $0 \leq j < L$, let $r_j(n) = r(j+Ln)$. \begin{thm} \label{Theorem1} For any primitive set of weights $(a_1,\ldots,a_k)$, we have \\ \begin{itemize} \item[(a)] For each $j$, the function $n \mapsto r_j(n)$ is the restriction to $\N$ of a degree $k-1$ polynomial with rational coefficients. \item[(b)] $$r(N) \sim \frac{N^{k-1}}{(k-1)!(a_1 \cdots a_k)}.$$ \end{itemize} \end{thm} \noindent Remark: Part (b) is due to Issai Schur and has been rediscovered many times since. Part (a) is also well known. Probably the quickest proof is via the method of generating functions, as we shall have reason to recall. On the other hand, we shall also give combinatorial/geometric proofs of part (b), and of part (a) in the case $k = 3$. \medskip The remainder of the results concern only the case $k = 3$. We introduce the following additional notation: For any ordering $(i, j, k)$ of the set $\{1,2,3\}$, let $d_k = \gcd(a_i,a_j)$, and put $\qq = d_1d_2d_3$. The following are all consequences of primitivity: \begin{itemize} \item[(i)] the $d_i$'s are pairwise coprime; \item[(ii)] $\qq L = \PP$; \item[(iii)] $\qq$ divides $L$. \end{itemize} For $0 \leq j < L$, define $R_j(N) = r_j(\frac{N-j}{L})$. The point of this change of variables is so that $R_j(N) = r(N)$ when $N \equiv j \pmod L$. % \begin{thm} \label{Theorem2} \[r_0(n) = \frac{L}{2\qq}n^2+\frac{a_1d_1 + a_2d_2 + a_3d_3}{2\qq}n + 1. \] \end{thm} \noindent Remark: This result appears in several places in the case where the weights are pairwise coprime, but we were not able to find the general case in the literature. Again we give an elementary geometric proof, using a version of Pick's Theorem. \medskip For $0 \leq j < L$, define \[y_i(j) = \langle a_i^{-1}j \rangle_{d_i}, \] \[y(j) = y_1(j)a_1+y_2(j)a_2+y_3(j)a_3. \] (The function $j \mapsto y(j)$ has the effect of projecting a complete system of residues modulo $L$ onto a set of $\qq$ distinct ``good'' residue classes modulo $L$, which form a complete system of residues modulo $\qq$.) Also define polynomials $Q_j(N), P_j(N)$ as follows: \[Q_j(N) = r_0 \left(\frac{N-y(j)}{L} \right), \] \[P_j(N) = Q_j(N) - Q_j(j) + r(j). \] The following is our main result: \begin{thm} \label{Theorem3} For all $0 \leq j < L$ \begin{itemize} \item[(a)] For all $N \equiv y(j) \pmod L$, we have $r(N) = R_j(N) = Q_j(N)$. \item[(b)] For all $N \equiv j \pmod L$, we have $r(N) = R_j(N) = P_j(N)$. \end{itemize} \end{thm} To illustrate Theorem \ref{Theorem3} we consider the case of \emph{Chicken McNuggets}. Recall that they are sold in packs of $6$, $9$ and $20$, and a now classic brainteaser asks, ``What is the largest number of Chicken McNuggets you \emph{can't} buy?'' or more succinctly, ``What is $\ff(6,9,20)$?'' An answer to this question follows directly from some material we shall present in Section 7. Here we are concerned with the problem of computing $r(6,9,20;N)$. Example 1: We will compute the number of ways to buy $1,080,005$ Chicken McNuggets, or $r(6,9,20;1,080,005)$. We have $(d_1,d_2,d_3) = (1,2,3)$, $\qq = 6$ and $L = 180$. We shall compute $R_j(N)$ for $N$ congruent to $1080005 \equiv 5 \mod L$. We have $y_1(5) = 0$, $y_2(5) = 1$, $y_3(5) = 1$, so $y(5) = 29$. By Theorem \ref{Theorem3} we get \[Q_{5}(N) = R_{46}(N) = \frac{1}{2160}N^2+\frac{13}{1080}N + \frac{113}{432} \] and \[R_{5}(N) = Q_5(N) - Q_5(5) + r(5). \] Since clearly $r(5) = 0$, we get \[R_5(N) = \frac{1}{2160}N^2 + \frac{13}{1080}N - \frac{31}{432}. \] Thus there are $r(1,080,005) = R_5(1,080,005) = 540,018,000$ ways to buy $1,080,005$ Chicken McNuggets. Example 2: We will compute $r(6,9,20;1,000,000)$. We have $1000000 \equiv 100 \pmod L$, so we compute $y_1(100) = 0$, $y_2(100) = 0$, $y_3(100) = 2$, $y(100) = 40$. %We get $r_0(n) = 15n^2+7n+1$, $Q_{100}(N) = %\frac{1}{2160}N^2 + \frac{1}{540}x+\frac{5}{27}$ Applying Theorem \ref{Theorem3}, we get \[Q_{100}(N) = \frac{1}{2160}N^2 + \frac{1}{540}x+\frac{5}{27}\] and \[R_{100}(N) = Q_{100}(N) - Q_{100}(100) + r(100). \] This last quantity can be evaluated using the identities \[r(100) = r(80) + r(6,9;100) = \ldots = \sum_{i=0}^5 r(6,9;100-20i), \] which divide up the set of all representations of $100$ by $(6,9,20)$ according to the number of times the weight $20$ is used. Clearly $r(6,9,100-20i) = 0$ unless $100 \equiv 20i \pmod 3$, i.e., unless $i = 2$ or $i= 5$. Certainly $r(6,9;0) = 1$, and one sees easily (by Popoviciu's formula, or otherwise) that $r(6,9;60) = r(2,3;20) = 4$. \\ \indent Thus $r(100) = 5$. In fact $Q_{100}(100) = 5$ as well, so that we have $R_{100}(N) = Q_{100}(N) = R_{40}(N)$. Thus the answer is $r(1,000,000) = 462,964,815$. As mentioned above, the strength of Theorem \ref{Theorem3} is inversely proportional to the size of $\frac{L}{\qq}$: we know that $r(N)$ is given by a (possibly) different quadratic polynomial on each residue class of $N \pmod L$, and part (a) gives an exact formula for the $\qq$ ``good'' residue classes. For the other classes, we are giving the leading term (always $\frac{1}{2\PP}$) and the linear term but not the constant term. As the above examples show, the amount of computation needed to compute the constant term depends upon the size of the residue class $j$: if $j$ is nearly as large as $L$, then it would require only about twice as much calculation to compute both $r(j)$ and $r(j+L)$ and interpolate, but if $j$ is small the above method is much faster. In particular, we certainly have $r(j) = 0$ if $0 < j < \min(a_1,a_2,a_3)$ (as in Example 1), so we have rather more exact formulas than was originally advertised. Note that in the case $\qq = L$ we are getting exact formulas for \emph{every} residue class; in this case (and only in this case) we claim Theorem \ref{Theorem3} as the analogue of Popoviciu's formula for $k = 3$. And indeed it is ``sufficiently satisfactory'' in the above sense: it can be used to derive an exact formula for $\ff(a_1,a_2,a_3)$. This discussion is carried out in Section 7. Unfortunately our use of generating functions in the proof of Theorem \ref{Theorem3}(b) seems to be essential, so in order to make our work self-contained, we begin with a review of the generatingfunctionological approach. % \section{Quasi-polynomials, generating functions and partial fractions} A function $r: \N \ra \C$ for which there exists $L \in \Z^+$ such that for each $j, \ 0 \leq j < L$, $r_j(n) = r(j+L n)$ is a polynomial function $P_j(n)$ is called a \textbf{quasi-polynomial} with period $L$. We define the degree of a quasipolynomial as the maximum of the degrees of the $P_j$'s. Consider the collection $Q = Q(L,d)$ of all quasipolynomials of period $L$ and degree at most $d-1$. Evidently $Q$ is a $\C$-subspace of the vector space of all functions $r: \N \ra \C$. Moreover, since each polynomial $P_j$ is uniquely determined by the values of $r$ at $j, j+ L, \ldots, j + (d-1)L$, an element of $Q$ is uniquely specified by its first $dL$ values, so $\dim Q = dL$. In this case, the implied basis is given by $L$ applications of the Lagrange interpolation theorem. Another basis is given as follows: for $0 \leq i < d$ and $0 \leq j < L$, we define $\mu_{ij}(n) = \zeta^{nj} n^i$, where $\zeta$ is a fixed choice of a primitive $L$th root of unity (say $\zeta = e^{\frac{2\pi i}{L}}$). A slight modification of this basis turns out be more convenient: for $i$ and $j$ as above, put $e_{ij}(n) = {n \choose i} \zeta^{nj}$. To see why, consider the generating function \[E_{ij}(x) = \sum_{n \geq 0} e_{ij}(n) x^n. \] By taking the $i$th derivative of the identity $\sum_n x^n = \frac{1}{1-x}$, we get: \[E_{i0}(x) = \sum_{n \geq 0} {n+i \choose i} x^n = \frac{1}{(1-x)^{i+1}}. \] It follows that \begin{equation} E_{ij}(x) = E_{i0}(\zeta^j x) = \sum_m {n+i \choose i} \zeta^{nj} x^n = \frac{1}{(1-\zeta^j x)^{i+1}}. \end{equation} From this we readily deduce the following basic result: % \begin{prop} For a function $f: \N \ra \C$, the following are equivalent: \begin{itemize} \item[(a)] $f \in Q(L,d)$ is a quasi-polynomial of period $L$ and degree at most $d-1$. \item[(b)] The generating function $F(x) = \sum_n f(n) x^n$ of $f$ is a rational function of the form $\frac{P(x)}{(1-x^{L})^d}$, where $\deg P < Ld$. \end{itemize} \end{prop} \begin{proof} Certainly the space of proper rational functions of the above form has the right dimension, so it suffices to see that the Taylor series coefficients are quasipolynomial functions of $n$. The key point is that, as for any proper rational function $R(X) = \frac{P(x)}{Q(x)}$ with $Q(0) \neq 0$, we have a \textbf{partial fractions decomposition} \begin{equation} \label{partialfractions} \frac{P(x)}{Q(x)} = \sum_{j=0}^{M-1} \sum_{i=1}^{m_j} \frac{C_{ij}}{(1-s_jx)^i}. \end{equation} Here $s_1, \ldots, s_M$ are the reciprocals ($s_j = r_j^{-1}$) of the distinct zeros $r_j$ of the denominator $Q(x)$, and $m_j$ denotes the multiplicity of $r_j$. In the given case, the (reciprocal) zeros of the denominator are $L$th roots of unity, so the partial fractions decomposition precisely expresses $\frac{P(x)}{(1-x^{L})^d}$ as a $\C$-linear combination of the $E_{ij}(x)$'s. This proves the result. \end{proof} Now fix a primitive system of weights $\aone$ and consider the generating function $R(x) = \sum r(n) x^n$ for $r(n) = r(a_1,\ldots,a_k;n)$. We have the identity \begin{equation} \label{rationalfunction} R(x) = (1+ x^{a_1} + x^{2a_1} + \ldots) \cdots (1+x^{a_k} + x^{2a_k} + \ldots) = \frac{1}{(1-x^{a_1})\cdots(1-x^{a_k})}. \end{equation} Let $D(x) = (1-x^{a_1}) \cdots (1-x^{a_k})$. Recalling that we have put $L = \lcm(a_1,\ldots,a_k)$, the (reciprocal) zeros of $D(x)$ are all $L$th roots of unity, but some zeros may occur with multiplicity greater than one: e.g., $x = 1$ occurs with multiplicity $k$. Since $1-x^{a_i}$ has distinct zeros, it is clear that $m_i \leq k$ for all $i$, so there exists a polynomial $N(x)$ such that $N(x)D(x) = (1-x^L)^k$, whence $R(x) = \frac{N(x)}{(1-x^L)^k}$, and we conclude that $r(n)$ is a quasipolynomial of period $L$ and degree at most $k-1$. Thus we have proved Theorem \ref{Theorem1}(a). Before proceeding further, there is something to be addressed: is it not the case that Proposition 4 already gives the explicit formula for $r(N)$ that we seek? Namely, with $C_{ij}$ equal to the coefficient of $(1-\zeta^{-j}x)^{-i}$, then using (\ref{partialfractions}) and (\ref{rationalfunction}), do we not get \[r(n) = \sum_{j=0}^{M-1} \sum_{i=1}^{m_j} C_{ij} {n+i-1 \choose i-1} \zeta^{nj}\ ? \] Certainly we do. However, this formula has its shortcomings. First, it is not really a formula at all until we say what the coefficients $C_{ij}$ are. The total number of such coefficients is equal to $S = a_1 + \ldots + a_k$. We all know how the $C_{ij}$'s are supposed to be computed: starting with the identity \begin{equation} \label{6} \frac{1}{(1-x^{a_1}) \cdots (1-x^{a_k})} = \sum_{j=0}^{M-1} \sum_{i=1}^{m_j} \frac{C_{ij}}{(1-s_jx)^i}, \end{equation} cross multiplication yields an $S \times S$ linear system to be solved for the $C_{ij}$'s. But, as any calculus student knows, the amount of computation needed to solve such linear systems quickly gets out of hand. Second, even if we happen to know all the $C_{ij}$'s, then our explicit formula for $r(n)$ will still be an unwieldy mess. Our difficulties are really linear algebraic in nature: the method of partial fractions computes the coefficients of the basis $e_{ij}$ of $Q(L,d)$, which is the wrong basis for efficient computation of the coefficients of $r_j(n)$. However, the partial fractions decomposition is a powerful tool for extracting other information about the function $r(n)$. Let us look at it a bit more carefully: first, for any fixed $j$ corresponding to an $L$th root of unity $\zeta^{-j}$ of order $w_j$, we get a contribution to $r(n)$ that is a function of the form $f_j(n) \zeta^{-jn}$, where $f_j(n)$ is a polynomial of degree $m_j-1$. If $j = 0$, $f_0(n)$ is an honest polynomial of degree $k-1$. For a general $j$, the multiplicity $m_j$ is equal to the number of $i$'s for which $w_j \ | \ a_i$, so if $w_j > 1$, the primitivity of the system assures that $m_j \leq k-1$. (So if the coefficients $a_i$ were coprime in pairs, we would have that $f_j(n)$ is a constant for all $j \neq 0$.) This implies $r(n)$ is asymptotic to the leading term of $f_0(n)$: \[r(n) \sim C_{0k} {n+k-1 \choose k-1} = \frac{C_{0k}}{(k-1)!} n^{k-1}. \] We can compute $C_{0k}$: just multiply (\ref{6}) by $(1-x)^k$ and evaluate at $x = 1$, getting \[C_{0k} = \frac{1}{(1+x+\ldots+x^{a_1-1}) \cdots (1+x + \ldots + x^{a_k-1}) } |_{x=1} = \frac{1}{a_1 \cdots a_k}. \] Thus we get \[r(n) \sim \frac{n^{k-1}}{(k-1)!(a_1 \cdots a_k)}, \] establishing Theorem \ref{Theorem1}(b). For later use (indeed, the only essential use we shall make of the methods of this section), we record the following result: \begin{lemma} \label{TechLemma} Let $k = 3$, and write $r(n) = c_2(n) n^2 + c_1(n) n + c_0(n)$, where the $c_i(n)$'s are periodic modulo $L$. The linear term $c_1$ is in fact periodic modulo $\qq = d_1d_2d_3.$ \end{lemma} \begin{proof} In general we have $r(n) = \sum_{j=0}^{M-1} f_j(n) \zeta^{-jn}$, where $f_j(n)$ is a polynomial of degree equal to one less than the number of $i$'s for which $a_i$ divides the order $w_j$ of $\zeta^{-j}$. Thus $f_j(n)$ has a linear term only when $w_j$ divides two of $a_1, \ a_2, a_3$, i.e., when $w_j \ | \ d_1d_2d_3$. \end{proof} \section{Lattice Geometry} The problem of computing the number of solutions to $x_1a_1 + \ldots + x_ka_k = N$ has an evident geometric interpretation: let $T_N$ denote the locus of solutions to this same equation among non-negative \emph{real numbers}: this forms a simplex in $\R^k$ whose vertices are $V_i = (0,0,\ldots,\frac{N}{a_i},\ldots,0)$ for $1 \leq i \leq k$. Thus we can look at $r(N)$ as counting the lattice points -- i.e., points with integral coordinates, on the simplex $T_N$. In other words, even counting lattice points in triangles with rational vertices is a difficult problem! However, it has long been known that if the vertices of the triangle have \emph{integral} coordinates (i.e., are themselves lattice points), then there is a wonderful explicit formula. Theorem \ref{Theorem2} will follow easily from the following elementary result (for the proof, see e.g. \cite{ES}), a version of Pick's Theorem ``renormalized'' for two-dimensional lattices in higher-dimensional Euclidean spaces. % \begin{thm}(Pick's Theorem) Let $\Lambda$ be a two-dimensional lattice in $\R^k$ with $2$-volume $\delta$. Let $P$ be a lattice polygon containing $h$ interior lattice points and $b$ boundary lattice points. Then the area $A(P)$ of $P$ is equal to $\delta \cdot (h+\frac{b}{2}-1)$. \end{thm} Let $r(P) = h+b$ be the total number of lattice points of $P$. Then Pick's Theorem is equivalent to the formula \begin{equation} r(P) = \frac{A(P)}{\delta} + \frac{b}{2} + 1. \end{equation} We can now prove Theorem \ref{Theorem2}. \begin{proof} Although we have ``the right'' to compute $r_0(n) = r(nL)$ directly, we will find it easier to first derive a formula for $r(n\PP)$ and then change variables to obtain the formula for $r_0(n)$. To compute $r(n\PP)$ we must count lattice points on the simplex \[T_n: x_1a_1 + x_2a_2 + x_3a_3 = n\PP, \] whose vertices are $V_1 = (a_2a_3n,0), \ V_2 = (0,a_1a_3n,0) \ V_3 = (0,0,a_1a_2n)$. Clearly we have $\frac{A(P)}{\delta} = \alpha n^2$ for some nonzero $\alpha$, whereas from Section 3 we know that $r(T_n)$ is a quadratic polynomial in $n$ whose leading coefficient is $(\PP)^2/2(\PP) = \frac{\PP}{2}$. Thus from our algebraic formalism we get that $\alpha = \frac{a_1a_2a_3}{2}$. As for the linear term, the number of lattice points on any line segment joining two integer points $V_i = (x_i,y_i,z_i)$ and $V_j = (x_j,y_j,z_j)$ is equal to $\gcd(x_i-x_j,y_i-y_j,z_i-z_j)$. If for distinct $i, \ j \in \{1,2,3\}$ we denote by $\ell_{ij}$ the line segment from $V_i$ to $V_j$, we have \[\# (\Z^3 \cap \ell_{ij}) = a_k N \gcd(a_i,a_j) = a_kd_k N, \] where $k$ is the remaining index. This gives \[r(n\PP) = \frac{a_1a_2a_3}{2} + \frac{a_1d_1 + a_2d_2 + a_3d_3}{2}n + 1. \] Finally, observe that $r(nL)$ is also given by a quadratic polynomial in $n$. On the one hand, this follows immediately from the considerations of the previous section -- we know that $r(N)$ is a quasi-polynomial with period $L$. On the other hand, even without computing the coefficients explicitly, the above argument using Pick's Theorem establishes this fact. Thus $r_0(\qq n) = r(\qq L n) = r(\PP n)$ is an identity of quadratic polynomials, so it can be inverted to give $r_0(n) = r(\PP(\frac{n}{\qq}))$. Performing this change of variables gives the formula of Theorem \ref{Theorem2}. \end{proof} \noindent Remark: A less sneaky proof would compute $A(T_n)$ and $\delta$ and not merely their ratio. This will be done in Section 6. \section{Recursions and congruences} Let $(a_1,\ldots,a_k)$ be any primitive set of weights. We will get a lot of mileage out of the following innocuous identity: \begin{equation} r(n+a_1) = r(n) + r(a_2,\ldots,a_k;n+a_1). \end{equation} The proof could hardly be simpler: the representations of $n+a_1$ by weights $a_1,\ldots,a_k$ that use $a_1$ at least once are in one-to-one correspondence with all representations of $n$ by $a_1,\ldots,a_k$, and the ones that do not use $a_1$ at all are actually representations by $a_2,\ldots,a_k$. There are of course analogous formulas for the other weights, which we use without comment. We now return to the case of $k=3$. % \begin{prop} \label{RecursionProp} Let $0 \leq y_i < d_i$. Then \[r(y_1a_1 + y_2a_2 + y_3a_3 + nL) = r(nL). \] \end{prop} \begin{proof} Assume that $d_1 > 1$. We have $r(a_1 + nL) = r(nL) + r(a_2,a_3;a_1 + nL)$. Since $\qq$ divides $L$ and $(a_1,d_1) = 1$, we have that $d_1$ does not divide $a_1+nL$, so necessarily $r(a_2,a_3;a_1+nL) = 0$. Repeated application of this argument gives the result. \end{proof} Recall that we have defined numbers $y_i(j) = \langle a_i^{-1} j \rangle_{d_i}$ and $y_j = y_1a_1+ y_2a_2+y_3a_3$. By construction $y(j)$ is congruent to $j$ modulo $L$ and satisfies the hypothesis of Proposition \ref{RecursionProp}. Thus we have \[r_{y(j)}(n) = r(y_1a_1 + y_2a_2 + y_3a_3 + nL) = r(nL) = r_0(n). \] The change of variables $n = \frac{N - y(j)}{L}$ gives us the expression for $r(N)$ valid on the congruence class $y(j)$, which gives Theorem \ref{Theorem3}(a). Since $y(j) \equiv j \pmod L$, applying Lemma \ref{TechLemma}, the expression $Q_j(N) = r_0(\frac{N-y(j)}{L})$ differs from the correct expression for $r(N)$ on the class $j$ by at most a constant. The expression for $P_j(N)$ corrects for this (in a rather tautological way) by ensuring that $P_j(j) = r(j)$. This completes the proof of Theorem \ref{Theorem3}. \section{Geometric and Combinatorial Proofs} In this section we give proofs of the results of this paper (except Theorem \ref{Theorem3}(b)) that do not require the theory of generating functions. \subsection{More lattice geometry} First, recall that $r(N) = r(a_1,\ldots,a_k;N)$ counts lattice points on the simplex $T_N$ given by the intersection of the hyperplane $x_1a_1 + \ldots + x_ka_k = N$ with the positive orthant. As $N$ varies, the lattices of integral solutions are isometric -- they are all principal homogeneous spaces for the rank $k-1$ free abelian group of integral solutions to $x_1a_1 + \ldots x_k a_k = 0$. Thus these lattices have a common $2$-volume $\delta$. Because the simplices $T_N$ are similar, as $N$ approaches infinity we must have $r(N) \sim \frac{A(T_N)}{\delta}$ (more precisely, the geometric picture gives $|r(N)-\frac{A(T_N)}{\delta}| = O(N^{k-2})$.) We saw earlier that the ratio of these two quantities is $\frac{N^{k-1}}{(k-1)!(a_1 \cdots a_k)}$, but we shall now compute both quantities individually. Let $\Lambda \subset \R^k$ be a $d$-dimensional sublattice of $\Z^k$, i.e., the $\Z$-span of $d$ $\R$-linearly independent vectors $\{v_1,\ldots,v_k\}$ with integral coordinates. The volume of $\Lambda$ is the $d$-dimensional volume of any fundamental region for $\Lambda$, e.g. of the paralleletope formed by $\{ x_1 v_1 + \ldots x_d v_d \ | \ 0 \leq x_i \leq 1 \}$. Given an orthonormal basis $e_1, \ldots, e_d$ of the vector space $V$ spanned by $\Lambda$, we can write $v_i = \sum_{ij} \alpha_{ij} e_j$, and we have $\Vol(\Lambda) = \det(\alpha_{ij})$. Alternately, for any $\Z$-basis $\{v_1,\ldots,v_k\}$ for $\Lambda$, $\Vol(\Lambda)$ is the square root of the determinant of the \textbf{Gram matrix} $M_{ij} = v_i \cdot v_j$. The problem is that our lattice \[\Lambda_0 = \{(z_1,\ldots,z_k) \in \Z^k \ | \ z_1a_1 + \ldots + z_k a_k = 0 \}, \] a $k-1$-dimensional lattice in $\R^k$, does not come equipped with any natural basis. Nevertheless we present the following method to compute the volume of any lattice $\Lambda_{\aa}$ defined by the hyperplane equation $(z_1,\ldots,z_k) \cdot \aa = 0$, for $\aa = (a_1,\ldots,a_k)$ a primitive set of weights (rebaptized here as a \textbf{primitive vector}). Let $\Lambda = \Z v_1 \oplus \ldots \oplus \Z v_{k-1} \subset \Z^k$. With $e_1,\ldots, e_k$ an orthonormal basis of $\R^k$, define the generalized cross-product \[\cross(v_1,\ldots,v_{k-1}) = \left[ \begin{array}{cccc} e_1 & \ldots & e_k \\ \lla & v_1 & \lra \\ \ & \vdots & \\ \lla & v_{k-1} & \lra \end{array} \right] \] By expanding out the determinant, one checks that $\cross(v_1,\ldots,v_{k-1})$ is orthogonal to $\Lambda$ and that $\Vol(\Lambda) = ||\cross(v_1,\ldots,v_{k-1})||$. Example: Take $k = 2$ and $\aa = (a_1,a_2)$ a primitive vector. Then $\Lambda_{\aa} = \Z (-a_2,-a_1)$, i.e. the orthogonal complement of $v$ is obtained by rotating $\Z \aa$ through a $90$ degree angle. Notice that in this case the $1$-volume of $\aa$ is equal to the $(k-1)$-volume of $\Lambda_{\aa}$. That this remains true in higher dimensions is the content of the following result: % \begin{lemma} \label{dualitylemma} Let $\aa = \aone$ be a primitive vector. Then \[\Vol(\Lambda_{\aa}) = \Vol({\aa}) = \sqrt{a_1^2 + \ldots + a_k^2}. \] \end{lemma} \begin{proof} For any $v_1,\ldots,v_{k-1}$ is a $\Z$-basis of $\Lambda_{\aa}$, $\Vol(\Lambda_{\aa}) = ||\cross(v_1,\ldots,v_{k-1})||$. On the other hand, the cross product of integer vectors remains an integer vector, so $\cross(v_1,\ldots,v_{k-1})$ and $\aa$ are two integer vectors spanning the same 1-dimensional $\R$-subspace. Since $\aa$ is assumed to be primitive, we must have $\cross(v_1,\ldots,v_{k-1}) = n\aa$, for some integer $n$, so that $\Vol(\Lambda_{\aa}) \geq \Vol(\aa)$. We claim that $n=1$, which will finish the proof. To establish the claim, consider the set $\SSS = \{\cross(w_1,\ldots, w_{k-1}) \ |\ w_i \in \Lambda_{\aa} \}$ of vectors that are cross-products from $\Lambda_{\aa}$. Writing $w_i = \Sigma \alpha_{ij} v_j$ with $\alpha_{ij}$ in $\Z$, we get \[ \cross(w_1,\ldots,w_{k-1}) = \det(\alpha_{ij}) \cross(v_1,\ldots,v_{k-1}),\] which shows that $\SSS$ is just the 1-dimensional lattice generated by $\cross(v_1,\ldots,v_{k_1})$. In particular, we can exploit the fact that $\SSS$ is a $\Z$-module as follows: note that $\Lambda_{\aa}$ is precisely the set of integer solutions of \[ a_1z_1 + \ldots + a_kz_k = 0. \] Thus \[v_1 = (-a_2,a_1,0,\ldots,0), \ v_2 = (-a_3,0,a_1,0,\ldots,0), \ldots, \ v_{k-1} = (-a_k,0,\ldots,a_1) \] are all elements of $\Lambda_{\aa}$, so that \[\cross(v_1,\ldots,v_{k-1}) = a_1^{k-2}(a_1,\ldots,a_{k-1})\] is a vector in $\SSS$. By symmetry, we see that $a_2^{k-2}(a_1,\ldots,a_{k-1}), \ldots, a_k^{k-2}(a_1,\ldots,a_k)$ are also vectors of $\SSS$. Since $\SSS$ is a $\Z$-module, we know that for any integers $z_1,\ldots,z_k$, we have \[(z_1 a_1^{k-2} + z_2 a_2^{k-2} + \ldots z_k a_k^{k-2}) \aone \in \SSS. \] Since $\aone$ is primitive, so is $(a_1^{k-2},\ldots,a_k^{k-2})$, so that we can choose $z_1,\ldots,z_k$ such that $z_1 a_1^{k-2} + \ldots + z_k a_k^{k-2} = 1$. But this implies that $\aa = \aone$ is in $\SSS$, and $n = 1$. This establishes the claim and completes the proof of Lemma \ref{dualitylemma}. \end{proof} %Remarks: \\ $\bullet$ If $\gcd(a_1,\ldots,a_k) = d$, then the %volume of the hyperplane \\ $(z_1,\ldots,z_k) \cdot %(a_1,\ldots,a_k) = N$ is equal to %$\sqrt{\frac{a_1}{d}^2+\ldots+\frac{a_k}{d}^2} = %\frac{a_1^2+\ldots+a_k^2}{d}$. \\ $\bullet$ We say that a %sublattice $\Lambda \subset \Z^k$ is \textbf{primitive} if: when %$v \in \Z^k$ is such that $dv \in \Lambda$ for some $d \in \Z^+$, %then $v \in \Lambda$. Then one can show the following result, %which generalizes Lemma \ref{dualitylemma}: for any primitive %sublattice $\Lambda$, $\Vol(\Lambda) = \Vol(\Lambda^{\perp})$, %where $\Lambda^{\perp}$ is the set of all vectors $w \in \Z^k$ %such that $w \cdot v$ for all $v \in \Lambda$. Coming back to our lattice $\Lambda_0$, we have $\Vol(\Lambda_0) = \sqrt{a_1^2 + \ldots + a_k^2}$. It remains to compute the volume of $T_N$. First consider the $(k-1)$-paralleletope $P_N$ whose sides are the vectors $v_1 - v_2, v_1 - v_3, \ldots, v_1 - v_k$, where $v_i = \frac{N}{a_i} e_i$ gives the intersection points of the simplex $H_N \cap \rkplus$ with the coordinate axes. Using the cross-product, we calculate \[\Vol(P_N) = \frac{\sqrt{a_1^2 + \ldots + a_k^2} N^{k-1}}{a_1 \cdots a_k}.\] Noting that the cone on an $r$-dimensional base has volume equal to $1/(r+1)$ times the corresponding cylinder, induction then gives that % \[ \Vol(T_N) = \frac{1}{(k-1)!} \Vol(P_N) = \frac{\sqrt{a_1^2 + \ldots + a_k^2}}{a_1 \cdots a_k} \frac{N^{k-1}}{(k-1)!}. \] Thus we conclude once again that \[ \raone \sim \frac{N^{k-1}}{a_1 \cdots a_k (k-1)!}. \] \subsection{More recursions and congruences} Using the results of the last section, it is easy to rederive the quasipolynomiality of $r(N) = r(a_1,a_2,a_3;N)$. We need only use our basic recursion formula \[r(a_1+N) = r(N) + r(a_2,a_3;a_1+N) \] ``in reverse.'' Namely, fix a class $j \pmod L$. Since, for all positive integers $N$ we have $r(N) = r(N+a_1)-r(a_2,a_3;N+a_1)$, taking $N = j+nL$, we get \begin{equation} r(j+nL) = r(a_1 + j + nL) - r(a_2,a_3;a_1+j+nL). \end{equation} A similar formula holds for $a_2$ and $a_3$. By Theorem 1(b), every sufficiently large integer $N$ is representable by the system $(x_1,x_2,x_3)$; in particular, there exist $x_1, x_2, x_3$ such that $L \ | \ x_1a_1+x_2a_2 + x_3a_3 + j$. Repeated application of (8) gives that $r(j+nL)-r(x_1a_1+x_2a_2+x_3a_3 + j + nL)$ is equal to a sum of $x_1+x_2+x_3$ terms of the form $r(a_i,a_j;a_k + c_{ijk} + nL)$ for various positive integers $c_{ijk}$. Now it is easy to see that each of these terms is either zero or a linear polynomial in $n$: e.g. this can be seen by contemplating the family of planar line segments \[L_N = \{(x_1,x_2) \in \R^2 \ | \ x_1a_1 + x_2a_2 = N, \ x_1, \ x_2 \geq 0 \}, \] the two-dimensional analogue of the family of simplices $T_N$ considered above. The geometric picture makes clear that for any positive integers $a,b,j$, $r(a,b;j+\lcm(a,b))-r(a,b;j)$ is equal to $1$ if $\gcd(a,b) \ | \ j$ and $0$ otherwise. Details are left to the reader. \\ \indent Thus $r(j+nL)$ differs from $r(x_1a_1+x_2a_2+x_3a_3 + j +nL)$ by a linear polynomial. But since $x_1a_1+x_2a_2 + x_3a_3 + j = ML$, we have $r(x_1a_1+x_2a_2+x_3a_3+j+nL) = r((M+n)L) = r_0(M+n)$, which by Theorem 2 is a quadratic polynomial. Thus $r(j+nL)$ is itself a quadratic polynomial, which was to be shown. % \section{Extremal systems} Suppose $(a_1,a_2,a_3)$ is a primitive system of weights with $\qq = L$; we say the system is \textbf{extremal}. This implies that $a_i = \frac{\qq}{d_i}$. Conversely, given any triple $(d_1,d_2,d_3)$ of pairwise coprime positive integers, by putting $a_i = \frac{d_1d_2d_3}{d_i}$, we get an extremal system. The extremal systems are, in many ways, the three-dimensional systems whose behavior most closely parallels that of two-dimensional systems. In particular, their Frobenius number can be computed:\footnote{Another property enjoyed by all extremal systems is the so-called Gorenstein condition: namely, that exactly half of the positive integers $N \leq \ff(a_1,\ldots,a_k)+1$ can be represented \cite{Nijenhuis-Wilf}.} \begin{prop} \label{SavittProp1} Let $d_1,d_2,d_3$ pairwise coprime positive integers. Then \[\ff(d_1d_2,d_1d_3,d_2d_3) = 2d_1d_2d_3 - d_1d_2 - d_1d_3 - d_2d_3. \] \end{prop} This result appeared as Problem A3 on the 1983 International Mathematical Olympiad. We shall discuss four proofs. First, we begin with the following general observation. \begin{lemma} \label{GilLemma} Let $(a_1,a_2,a_3)$ be any primitive system of weights. For $1 \leq i \leq 3$, the Frobenius number $\ff = \ff(a_1,a_2,a_3)$ satisfies $\ff \equiv -a_i \pmod{d_i}.$ \end{lemma} \begin{proof} By symmetry, it suffices to consider the case $i=1$. Since $\ff+a_1>\ff$, we can write $\ff + a_1$ as $x_1a_1+x_2a_2+x_3a_3$, with nonnegative $x_i$'s. But $x_1$ cannot be positive, since that would lead to a representation of $\ff$ by $a_1,a_2$ and $a_3$. So $\ff+a_1$ is an integral combination of $a_2$ and $a_3$, and is therefore divisible by $d_1$. Compiling the three congruences, we get \begin{equation} \label{10} \ff \equiv (d_1-1)a_1 + (d_2-1)a_2 + (d_3 - 1) a_3 \pmod \qq. \end{equation} The right-hand side of (\ref{10}) is equal to $3d_1d_2d_3 - d_1d_2 - d_1d_3 - d_2d_3 = j_0$, say. By Theorem \ref{Theorem3}, we have $r_{j_0}(n) = r_0(n)$ for all $n$, so that we have an \emph{explicit formula} for $r$ on the class containing $\ff$, namely $\qq^2R_{j_0}(N) =$ \[ \frac{1}{2} N^2 + \frac{2a_1+2a_2+2a_3-3\qq}{2}N + \qq^2 - \frac{3}{2}(a_1+a_2+a_3)\qq + \frac{1}{2}(a_1^2+a_2^2+a_3^2) + \qq(d_1+d_2+d_3). \] Hence $R_{j_0}(j_0-L) = R_{j_0}(j_0-2L) = 0$. Since $R_{j_0}(N)$ is a quadratic polynomial, it can have no further zeros, so $\ff(a_1,a_2,a_3) = j_0-L$. \end{proof} Here is a second, more conceptual proof: we know that $r(j_0) = r_{j_0}(0) = r_0(0) = 1$, so $\ff \neq j_0$. In general, since $r(L)> 0$, the function $r(N)$ is nondecreasing on any given congruence class modulo $L$. Here $L = \qq = a_id_i$, so we conclude that $\ff < j_0$ and it is enough to show that $r(j_0-L) = 0$. But, by our usual recursion we have \[1 = r(j_0) = r(j_0 - d_1a_1) + \sum_{i=0}^{d_1-1} r(a_2,a_3;j_0 - ia_i). \] Clearly $r(j_0-L) = r(j_0 - d_1a_1) \in \{0,1\}$ and is zero if and only if any one of the terms of the sum is nonzero. But taking $i = d_1-1$, we have \[r(a_2,a_3; j_0 - (d_1-1)a_i) = r(a_2,a_3; (d_2-1)a_2 + (d_3-1)a_3) > 0. \] Third proof: Let us recall the following formula, due to Johnson \cite{Johnson}: \begin{lemma} For any primitive system $(a_1,a_2,a_3)$, one has \begin{equation} \label{Johnson} \ff(a_1,a_2,a_3) = d_3\ff(\frac{a_1}{d_3},\frac{a_2}{d_3},a_3) + (d_3-1)a_3. \end{equation} \end{lemma} \begin{proof} Let $\ff= \ff(a_1,a_2,a_3)$. By lemma \ref{GilLemma}, we have $\ff \equiv -a_3 \pmod {d_3}$. For any number $N$ satisfying $N \equiv -a_3 \pmod {d_3}$, in any representation of $N$ as $x_1a_1+x_2a_2+x_3a_3$ we must have $x_3\equiv -1 \pmod {d_3}$, hence $N$ is representable by $a_1,a_2$ and $a_3$ if and only if $N- (d_3-1)a_3$ is representable by $a_1,a_2$ and $d_3a_3$. This is equivalent to $(N-(d_3-1)a_3)/d_3$ being representable by $\frac{a_1}{d_3},\frac{a_2}{d_3}$ and $a_3$, whence the result. \end{proof} This leads to an explicit formula for $\ff$ whenever $a_1 = d_2d_3$:\footnote{This holds in particular for the ``McNuggets'' system $(6, 9,20)$, and so can be used to answer the brainteaser.} \[\ff(d_2d_3,a_2,a_3) = d_3\ff(d_2, \frac{a_2}{d_3},a_3) + (d_3-1)a_3 = d_3\ff(d_2,\frac{a_2}{d_3}) + (d_3-1)a_3 =\] \[d_2a_2-d_2d_3 - a_2 + d_3a_3-a_3 = a_2d_2 + a_3d_3-a_1-a_2-a_3, \] where the second equality uses the fact that, since the weight $a_3$ is a multiple of the weight $d_2$, it can be omitted without changing the Frobenius number. Finally, Proposition \ref{SavittProp1} is a consequence of the following beautiful result of Alfred Brauer \cite{Brauer}. % \begin{thm} \label{Brauer} Given a primitive set of weights $\aone$, for $1 \leq i \leq k$ let $e_i = \gcd(a_1,\ldots,a_i)$. Then \begin{itemize} \item[(a)] $\ff(a_1,\ldots,a_k) \leq \sum_{i=2}^k a_i \frac{e_{i-1}}{e_i} - \sum_{i=1}^k a_i + 1$. \\ \item[(b)] One has equality in part (a) if and only if, for all $i \geq 2$, $\frac{e_{i-1}}{e_i}a_i$ can be represented by the system $(a_1,\ldots,a_i)$. \end{itemize} \end{thm} There is an analogue of Proposition \ref{SavittProp1} for arbitrary $k \geq 2$: let $d_1,\ldots,d_k$ be a set of pairwise coprime positive integers, define $\mathcal{D} = \prod_j d_j$, and for $1 \leq i \leq k$ put $a_i = \frac{\mathcal{D}}{d_i}$. Then we say $(a_1,\ldots,a_k)$ is an \textbf{extremal} system of weights. % \begin{prop} \label{SavittProp2} Let $(a_1,\ldots,a_k)$ be the extremal system formed from the pairwise coprime system $(d_1,\ldots,d_k)$. Then: \begin{equation} \label{extremaleq} \ff(a_1,\ldots,a_k) = (k-1)(d_1 \cdots d_k) - \sum_{i=1}^k a_i. \end{equation} \end{prop} The result is again a consequence of Brauer's Theorem \ref{Brauer}. We leave to the interested reader the task of investigating which of the other proofs of Proposition \ref{SavittProp1} can be made to go through. We end with an explanation of the term ``extremal.'' For this, let $r: \N \ra \C$ be any function given by a quasipolynomial mod $L$, of total degree at most $d$, and which is not identically zero on any residue class. Then we can define $\ff(r)$ as the largest $N$ for which $r(N) = 0$. Indeed, since $r$ can have at most $d$ zeros on any given residue class, we have $\ff(r) \leq dL-1$. By Theorem \ref{Theorem1}, we can apply this to any primitive system of weights $\aone$, getting the bound \[\ff(a_1,\ldots,a_k) \leq (k-1)L-1. \] In fact this bound is never sharp, as can be seen by comparing to Brauer's bound. This is not so surprising, since the quasipolynomial associated with a set of weights has many special properties. Notice however that this bound differs from the right hand side of (\ref{extremaleq}) by precisely $a_1+\ldots+a_k-1$. This can be explained as follows: for a primitive system $\aone$, define $\ff^+(a_1,\ldots,a_k)$ to be the largest positive integer $N$ such that the equation $x_1a_1 + \ldots + x_ka_k = N$ has no solution in \emph{positive integers} $x_i$. This is closely related to the Frobenius number defined above; indeed, we have \[\ff^+\aone = \ff\aone + a_1 + \ldots + a_k . \] Moreover, we can define \[r^+(a_1,\ldots,a_k;N) = \#\{(x_1,\ldots,x_k) \in (\Z^+)^k \ | \ x_1a_1 + \ldots + x_k a_k = N \} .\] The associated generating function $R^+(x)$ is easily computed: \[\sum_{n \geq 0} r^+(n)x^n = (x^{a_1}+x^{2a_1}+\ldots) \cdots (x^{a_k} + x^{2a_k} + \ldots) = \frac{x^{a_1+\ldots+a_k}}{(1-x^{a_1}) \cdots (1-x^{a_k})}. \] This is very nearly the generating function of a quasipolynomial: the only problem is that the degree of the numerator is equal to the degree of the denominator. Thus \[x^{-1}R^+(x) = \sum_{n \geq 0} a_{n+1}x^n \] is a quasipolynomial, so that $r^+(n)$ is a quasipolynomial modulo $L$ when restricted to positive integral values, of degree $k-1$ on each residue class. From this information alone we deduce as above the bound \[\ff^+(a_1,\ldots,a_k) \leq (k-1)L \] and thus the bound \[\ff(a_1,\ldots,a_k) \leq (k-1)L - \sum_{i=1}^k a_i. \] It is remarkable that this bound \emph{is} attained, by all extremal systems. Comparing with Brauer's bound, it is easily seen that the bound is \emph{only} attained for extremal systems, whence the name. \begin{thebibliography}{Niren} % \bibitem[1]{BGK} M. Beck, I. Gessel and T. Komatsu, The polynomial part of a restricted partition function related to the Frobenius problem, {\it Electronic J. Comb.} {\bf 8} (2001), N7. % \bibitem[2]{Brauer} A. Brauer, On a problem of partitions, {\it Amer. J. Math.} {\bf 64} (1942), 299--312. \bibitem[3]{ES} P. Erdos and J. Suranyi, {\it Topics in the theory of numbers} , Springer, 2003. % \bibitem[4]{Johnson} S. M. Johnson, A linear diophantine problem, {\it Canad. J. Math.} {\bf 12} (1960), 390--398. % \bibitem[5]{Kannan} R. Kannan, Lattice translates of a polytope and the Frobenius problem, {\it Combinatorica} {\bf 12} (1992), 161--177. % \bibitem[6]{Nijenhuis-Wilf} A. Nijenhuis and H. Wilf, Representations of integers by linear forms in non-negative integers, {\it J. Number Theory} {\bf 4} (1972), 98--106. % \bibitem[7]{Popoviciu} T. Popoviciu, Asupra unei probleme de patitie a numerelor, {\it Acad. Republicii Populare Romane, Filiala Cluj, Studii si cercetari stiintifice} {\bf 4} (1953), 7--58. % \bibitem[8]{Ramirez-Alfonsin} J. L. Ramirez-Alfonsin, Complexity of the Frobenius problem, {\it Combinatorica} {\bf 16} (1996), 143--147. % \bibitem[9]{Sertoz} S. Sertoz, On the number of solutions of the Diophantine equation of Frobenius, {\it Diskret. Mat.} {\bf 10} (1998), 62--71. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 05A15; Secondary 52C07. \noindent \emph{Keywords: } Frobenius problem, quasi-polynomial, representation numbers, Pick's theorem. \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received June 23 2005; revised version received October 19 2005. Published in {\it Journal of Integer Sequences}, October 20 2005. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}