\documentclass[12pt]{article}%{amsart} \usepackage{amssymb} \textwidth= 6.5in \textheight= 9.0in \topmargin = -20pt \evensidemargin=0pt \oddsidemargin=0pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 %------ GENERAL MACROS ----- % % Standard rings and fields, affine and projective space % \def\NZQ{\mathbb} % the font for N,Z,Q,R,C \def\NN{{\NZQ N}} \def\QQ{{\NZQ Q}} \def\ZZ{{\NZQ Z}} \def\RR{{\NZQ R}} \def\CC{{\NZQ C}} \def\AA{{\NZQ A}} \def\PP{{\NZQ P}} % %------------------------------------------------ % Symbols in "Fraktur" % \def\frk{\frak} % font for "Fraktur" \def\aa{{\frk a}} \def\pp{{\frk p}} \def\Pp{{\frk P}} \def\qq{{\frk q}} \def\Qq{{\frk Q}} \def\mm{{\frk m}} \def\Mm{{\frk M}} \def\nn{{\frk n}} \def\Nn{{\frk N}} % %------------------------------------------------ % Small letters in bold % \def\ab{{\bold a}} \def\bb{{\bold b}} \def\xb{{\bold x}} \def\yb{{\bold y}} \def\zb{{\bold z}} % \def\opn#1#2{\def#1{\operatorname{#2}}} % to make operators %------------------------------------------------ % Numerical invariants of rings, ideals, and modules % \opn\chara{char} \opn\length{\ell} %\opn\pd{pd} %\opn\rk{rk} \opn\projdim{proj\,dim} \opn\injdim{inj\,dim} \opn\rank{rank} \opn\depth{depth} \opn\grade{grade} \opn\height{height} \opn\embdim{emb\,dim} \opn\codepth{codepth} \opn\codim{codim} \def\OO{{\cal O}} \opn\Tr{Tr} \opn\bigrank{big\,rank} \opn\superheight{superheight}\opn\lcm{lcm} \opn\trdeg{tr\,deg}% \opn\reg{reg} \opn\ini{in} %------------------------------------------------ % Divisors % \opn\div{div} \opn\Div{Div} \opn\cl{cl} \opn\Cl{Cl} % %------------------------------------------------ % Subsets of the spectrum of a ring % \opn\Spec{Spec} \opn\Supp{Supp} \opn\supp{supp} \opn\Sing{Sing} \opn\Ass{Ass} % %------------------------------------------------ % Standard operations on ideals and modules % \opn\Ann{Ann} \opn\Rad{Rad} \opn\Soc{Soc} % %------------------------------------------------ % Linear algebra and homology, endo- and automorphisms % \opn\Ker{Ker} \opn\Coker{Coker} \opn\Im{Im} \opn\Hom{Hom} \opn\Tor{Tor} \opn\Ext{Ext} \opn\End{End} \opn\Aut{Aut} \opn\id{id} \def\Frob{{\cal F}} \opn\nat{nat} \opn\pff{pf}% \pf exists already \opn\Pf{Pf} \opn\GL{GL} \opn\SL{SL} \opn\mod{mod} \opn\ord{ord} % %------------------------------------------------ % Convexity % \opn\aff{aff} \opn\con{conv} \opn\relint{relint} \opn\st{st} \opn\lk{lk} \opn\cn{cn} \opn\core{core} \opn\vol{vol} %------------------------------------------------ % Graded rings and Rees algebras \opn\gr{gr} \def\Rees{{\cal R}} % %------------------------------------------------ % Polynomials and power series % \def\poly#1#2#3{#1[#2_1,\dots,#2_{#3}]} \def\pot#1#2{#1[\kern-0.28ex[#2]\kern-0.28ex]} \def\Pot#1#2#3{\pot{#1}{#2_1,\dots,#2_{#3}}} \def\konv#1#2{#1\langle #2\rangle} \def\Konv#1#2#3{\konv{#1}{#2_1,\dots,#2_{#3}}} % %------------------------------------------------ % Direct and inverse limits % \opn\dirlim{\underrightarrow{\lim}} \opn\invlim{\underleftarrow{\lim}} % % % Names with a meaning % \let\union=\cup \let\sect=\cap \let\dirsum=\oplus \let\tensor=\otimes \let\iso=\cong \let\Union=\bigcup \let\Sect=\bigcap \let\Dirsum=\bigoplus \let\Tensor=\bigotimes % %------------------------------------------------ % \let\to=\rightarrow \let\To=\longrightarrow \def\Implies{\ifmmode\Longrightarrow \else \unskip${}\Longrightarrow{}$\ignorespaces\fi} \def\implies{\ifmmode\Rightarrow \else \unskip${}\Rightarrow{}$\ignorespaces\fi} \def\iff{\ifmmode\Longleftrightarrow \else \unskip${}\Longleftrightarrow{}$\ignorespaces\fi} \let\gets=\leftarrow \let\Gets=\longleftarrow \let\followsfrom=\Leftarrow \let\Followsfrom=\Longleftarrow \let\:=\colon % % % \newtheorem{Theorem}{Theorem}[section] \newtheorem{Lemma}[Theorem]{Lemma} \newtheorem{Corollary}[Theorem]{Corollary} \newtheorem{Proposition}[Theorem]{Proposition} \newtheorem{Remark}[Theorem]{Remark} \newtheorem{Remarks}[Theorem]{Remarks} \newtheorem{Example}[Theorem]{Example} \newtheorem{Examples}[Theorem]{Examples} \newtheorem{Definition}[Theorem]{Definition} \newtheorem{Problem}[Theorem]{Problem} \newtheorem{Conjecture}[Theorem]{Conjecture} \newtheorem{Claim}[Theorem]{Claim} \newtheorem{Question}[Theorem]{Question} \newtheorem{Proof}[Theorem]{Proof} % % We like the var forms of some greek letters (as taught in German schools) % \let\epsilon=\varepsilon \let\phi=\varphi \let\kappa=\varkappa % % We print on A4 paper % \textwidth=15cm \textheight=22cm \topmargin=0.5cm \oddsidemargin=0.5cm \evensidemargin=0.5cm % % The pf environment of AMSART needs a little help % \def\qed{\ifhmode\textqed\fi \ifmmode\ifinner\quad\qedsymbol\else\dispqed\fi\fi} \def\textqed{\unskip\nobreak\penalty50 \hskip2em\hbox{}\nobreak\hfil\qedsymbol \parfillskip=0pt \finalhyphendemerits=0} \def\dispqed{\rlap{\qquad\qedsymbol}} \def\noqed{\def\qed{\relax}} % % ------ END OF GENERAL MACROS ------- % % ------ MACROS FOR THIS ARTICLE ------- % \def\CT{{\tilde{\cal C}}} \def\HT{{\tilde H}} \def\KK{{\cal K}} \def\FF{{\cal F}} \def\MM{{\cal M}} \def\LL{{\cal L}} \def\rr{{\frak r}} \def\dsp{\displaystyle} % % %================================================================= % % % Latest Revision: 03 May 2006 % Sent to: INTEGERS on 22 Sep 2005 % \makeatletter %% this should really go into a style file! \renewcommand\section{\@startsection {section}{1}{\z@}% % {-3.5ex \@plus -1ex \@minus -.2ex}% % here is your vskip of 30pt: {-30pt \@plus -1ex \@minus -.2ex}% {2.3ex \@plus.2ex}% {\normalfont\normalsize\bfseries}} \renewcommand\subsection{\@startsection{subsection}{2}{\z@}% {-3.25ex\@plus -1ex \@minus -.2ex}% {1.5ex \@plus .2ex}% {\normalfont\normalsize\bfseries}} % add a point after section numbers: \renewcommand{\@seccntformat}[1]{\csname the#1\endcsname. } %\quad} \makeatother \textwidth= 6.5in \textheight= 9.0in \topmargin = -20pt \evensidemargin=0pt \oddsidemargin=0pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 \begin{document} \vspace*{-40pt} \centerline{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 6 (2006), \#A25} \vskip 40pt \thispagestyle{empty} \begin{center} \uppercase {\bf Some Observations on Subset Sum Representations} \vskip 20pt {\bf Donald Mills}\\ {\smallit Department of Mathematics, Rose-Hulman Institute of Technology, Terre Haute, IN 47803-3999}\\ {\tt mills@rose-hulman.edu}\\ \end{center} \vskip 30pt \centerline{\smallit Received: 9/22/05, Revised: 5/31/06, Accepted: 9/24/06, Published: 10/06/06} \vskip 30pt \centerline{\bf Abstract} \noindent Moulton and Develin have investigated the notion of representing various sets $S$ of positive integers, of size $m$ say, as subset sums of smaller sets. The {\it rank\/} of a given set $S$ is the smallest positive integer $rk(S) \leq m$ such that $S$ is represented by an integer set of size $rk(S)$. In this note, we primarily consider sets of the form $\{1, 2^{m}, 3^{m}, \dots\}$ for positive integer $m \geq 2$. Given a positive integer $k$, we ask for the smallest $M$ such that $\{1, 2^{m}, 3^{m}, \dots, k^{m}\}$ is independent for all $m \geq M$, and provide some answers. We then use a result of Sprague to show that any nondecreasing positive integer sequence ${\bf a}=\{a_{1}, a_{2},\dots\}$ that grows polynomially, and in particular the set $\{1, 2^{m}, 3^{m}, \dots\}$ for fixed exponent $m$, has limiting rank zero.\\ %\begin{footnotesize} %\noindent %2000 Mathematics Subject Classification: 11B75 (primary); 11P99 %(secondary)\\ %Keywords: sum, representation, optimal, integer\\ %\end{footnotesize} \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 6 (2006), \#A25\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 30pt \section{Introduction} The concept of representing sets of positive integers, and more generally sets of rationals, in an ``efficient" manner according to the operation of addition, has received some attention in recent years, specifically in a pair of companion papers published in 2001 by Moulton \cite{mou} and Develin \cite{dev}. Lev \cite{lev} and Ilie and Salomaa \cite{ili} have also considered questions related to subset sums. By efficient representation, we mean the following, as illustrated by way of example. The set of powers of $2$ given by $S=\{1,2,4,8,16\}$ can be represented by $P=\{-5,1,7,9\}$, for $1 \in P$, $2=-5+7$, $4=-5+9$, $8=1+7$, and $16=7+9$. Thus $S$ has a {\it subset sum representation\/} given by $P$. As the cardinality of $P$, denoted $|P|$, is less than $|S|$, $S$ is said to be {\it dependent\/}. We give some definitions that will be useful later. The terms given below, with the exception of total dependence, are taken from \cite{mou}. \begin{Definition}[Span, Representation] The \underline{span} of a set $B$, denoted by sp$(B)$, is the set of all sums of subsets of $B$. In other words, $sp(B)=\{\sum_{b \in A}b: A \subseteq B,\hspace{0.02in}A \neq \emptyset\}.$ Hence, $B$ \underline{represents} $P$, when $P \subseteq sp(B)$. \end{Definition} \begin{Definition}[Rank, Optimal Set] For any set $P$ the \underline{rank} of $P$, denoted by $rk(P)$, is the smallest size of a set representing $P$. Any set representing $P$ with size $rk(P)$ is said to be \underline{optimal}. \end{Definition} Moulton shows that $\{-5,1,7,9\}$ is one of the $19$ optimal representing sets of $S=\{1,2,4,8,16\}$. Hence, $rk(S)=4$ here. In general, it is clear that $rk(P) \leq |P|$. \begin{Definition}[Independent Set] A set $P$ for which $rk(P)=|P|$ is an \underline{independent set}. Else, $P$ is said to be \underline{dependent}. \end{Definition} \begin{Definition}[Limiting Rank, Total Dependence] For any infinite set of distinct positive integers $A=\{a_{n}\}_{n \geq 1}$ with $A_{m}=\{a_{1},a_{2},\dots,a_{m}\}$ for each $m$, we define the \underline{limiting rank} of $A$ by $$\rho(A)=\lim_{m \rightarrow \infty}\frac{rk(A_{m})}{m},$$ \noindent provided said limit exists. Thus, if $\rho(A)=1$, $A$ is an independent set, while $A$ is dependent if $\rho(A)<1$. If $\rho(A)=0$ we will say that $A$ is \underline{totally dependent}. \end{Definition} In Section 2 we consider the following problem: For sets of the form $A_{(k,m)}=\{1, 2^{m}, 3^{m},$ $ \dots, k^{m}\}$, where $k$, $m \geq 2$ are positive integers and $k$ is fixed, find the smallest $M$ such that $A_{(k,m)}$ is independent for all $m \geq M$. In Section 3, we use a result of Sprague to show that, for fixed exponent $m$, the set $P_{m}=\{1, 2^{m}, 3^{m}, \dots\}$ has limiting rank zero. This is, so far as the author knows, the first class of sets for which the limiting rank is known. \section{Independent Sets of $n$th Powers} In contrast to Moulton and Develin, who are interested in sets of the form $\{1, r, r^{2}, \dots, r^{n}\}$ for integer (Moulton) and rational (Develin) $r$, we are interested in sets of the form $A_{(k,m)}=\{1,2^{m},3^{m},\dots,k^{m}\}$ for integral $m \geq 2$. In this section, we determine, for certain sets $A_{(k,m)}$ with fixed size $k$, the minimum $M$ such that $A_{(k,m)}$ is independent for all $m \geq M$. Contrastingly, in Section 3 we show that for fixed $m$, $\displaystyle \lim_{k \rightarrow \infty}\frac{rk(A_{(k,m)})}{k}=0$. First, consider $m=2$. A simple argument shows that $A_{(3,2)}=\{1, 4, 9\}$ is independent, while the set $\{1, 4, 9, 16\}$ can be represented by $S_{4}=\{-3, 4, 12\}$, and hence $A_{(k,2)}$ is dependent for all $k \geq 4$. Next, consider $m=3$. It is easy to show that $A_{(3,3)}=\{1, 8, 27\}$ is independent, and an adaptation of Moulton's arguments for powers of $2$ (Proposition 2 of \cite{mou}) shows that $A_{(4,3)}=\{1, 8, 27, 64\}$ is also independent. However, $\{1, 8, 27, 64, 125\}$ can be represented by $\{-34, 8, 27, 98\}$ or $\{-26, 27, 34, 90\}$, and so $A_{(k,3)}$ is dependent for all $k \geq 5$. As the first three squares and the first four cubes are independent, we ask the following. \begin{Question}\label{indep_powers_ques} For $k \geq 3$, is $A_{(k,m)}$ independent for $m \geq k-1$? More generally, given $k$ and $m$, what is necessary to guarantee the independence of $A_{(k,m)}$? %Given $m \geq 2$, is $A_{(k,m)}$ independent for $3 \leq k \leq m+1$? More generally, given $k$ and $m$, what is necessary to guarantee the independence of $A_{(k,m)}$? \end{Question} We make progress below towards answering this. First, we note the following. \begin{Theorem}\label{A3m} $A_{(3,m)}$ is an independent set for $m \geq 2$. \end{Theorem} \noindent{\it Proof.} The case $m=2$ is resolved (see above). For $m \geq 3$, we note that, if a set $P=\{a,b\}$, $a < b$, represents $A_{(3,m)}$, then we must have $a=1$ and $b=2^{m}$. But then $a+b=3^{m}$, which cannot happen by Fermat's Last Theorem. \hfill$\Box$ \begin{Theorem}\label{A4m} $A_{(4,m)}$ is an independent set for $m \geq 3$. \end{Theorem} \noindent{\it Proof.} The method of proof is like that of Proposition 2 in Moulton's paper. Suppose by way of contradiction that $S=\{a, b, c\}$ represents $A_{(4,m)}$. Note that each element of $A_{(4,m)}$ is equal to one of $a$, $b$, $c$, $a+b$, $a+c$, $b+c$, or $a+b+c$. We have four possibilities. \begin{itemize} \item{Case 1: All three of $a$, $b$, $c$ belong to $A_{(4,m)}$. Then $A_{(4,m)}=\{a, b, c, d\}$ for some $d$, and so $d$ is the sum of either two of $a$, $b$, and $c$, or the sum of all three. For the first case, we have an integer solution to the Diophantine equation \begin{eqnarray}\label{fermat_a4m} x^{m}+y^{m}=z^{m}, \end{eqnarray} \noindent an impossibility by Fermat's Last Theorem. If $d=a+b+c$ then we have an integer solution to $x^{m}+y^{m}+z^{m}=w^{m}$. One observes that the only possibility is $1+2^{m}+3^{m}=4^{m}$, that is, $3^{m}=4^{m}-2^{m}-1$. As $m \geq 3$, we have \begin{eqnarray}\label{eqn_case1_a4m} 4^{m}-2^{m}-1 & \geq & \left(\frac{55}{64}\right)4^{m}\nonumber \end{eqnarray} \noindent where the fraction $\frac{55}{64}$ is obtained by setting $m=3$. Hence by the above, we conclude $\left(\frac{4}{3}\right)^{m} \leq \frac{64}{55}$, which is impossible.} \item{Case 2: Exactly two of $a$, $b$, $c$ belong to $A_{(4,m)}$. Suppose without loss of generality that $a$, $b \in A_{(4,m)}$, so that $A_{(4,m)}=\{a, b, d_{1}, d_{2}\}$. Observe that both $d_{1}$ and $d_{2}$ require $c$ as a summand, otherwise we have an integer solution to (\ref{fermat_a4m}), a contradiction. By appealing to (\ref{fermat_a4m}), we are able to eliminate the cases $(d_{1},d_{2})=(a+b+c,a+c)$ and $(d_{1},d_{2})=(a+b+c,b+c)$ as possibilities, and thus $A_{(4,m)}=\{a, b, a+c, b+c\}$. Thus we have an integer solution to the equation $x^{m}+y^{m}=z^{m}+w^{m}$, and in particular we must have $2^{m}+3^{m}=4^{m}+1$. Equivalently, $3^{m}=4^{m}-2^{m}+1$. We then argue as in Case 1 to conclude that such a scenario is impossible.} \item{Case 3: Exactly one of $a$, $b$, $c$ is in $A_{(4,m)}$. Suppose without loss of generality that $a \in A_{(4,m)}$. There are four possibilities for the remaining elements of $A_{(4,m)}$, and of these only the following two are viable: $A_{(4,m)}=\{a, a+b, a+c, a+b+c\}$ and $A_{(4,m)}=\{a, a+b, a+c, b+c\}$. The reason that these are the only two acceptable choices for $A_{(4,m)}$ is that, with $a \in A_{(4,m)}$, $b+c$ and $a+b+c$ cannot both belong to $A_{(4,m)}$, otherwise there exists a pair of positive integers $s$, $u$ such that $s^{m}+a=u^{m}$, a contradiction to Fermat's Last Theorem as $m \geq 3$. \par For the first representation, we see that the sum of the first and fourth elements equals the sum of the second and third elements in $A_{(4,m)}$, and we are led to the same contradiction as in Case 2. If the second representation is possible, we have integral solutions to the set of equations \begin{eqnarray} x^{m}+b & = & w^{m}, \nonumber\\ x^{m}+c & = & z^{m}, \mbox{and} \nonumber\\ b+c & = & y^{m}, \nonumber \end{eqnarray} \noindent which in turns yields an integral solution to $2x^{m}+y^{m}=z^{m}+w^{m}$. As $m \geq 3$, the only possibility is $2+4^{m}=2^{m}+3^{m}$, that is, $3^{m}=4^{m}-2^{m}+2$. An argument similar to that given in Case 1 shows that such a scenario is impossible.} \item{Case 4: None of $a$, $b$, $c$ lie in $A_{(4,m)}$. Thus, $A_{(4,m)}=\{a+b, a+c, b+c, a+b+c\}$. Since $(a+b)+(a+c)+(b+c)=2(a+b+c)$, we must have an integer solution to $2x^{m}=y^{m}+z^{m}+w^{m}$. The only possibility is $2(4^{m})=3^{m}+2^{m}+1$, that is, $2^{2m+1}-2^{m}-1=3^{m}$. Since $2^{2m+1}-2^{m}-1 \geq \left(\frac{119}{64}\right)4^{m}$, we have $\left(\frac{4}{3}\right)^{m} \leq \frac{64}{119}$, which is a contradiction. This completes the proof.} \end{itemize} \hfill$\Box$ \noindent {\bf Remark.} As we have made reference to Moulton's Proposition 2, we should also note that his proof has a small hole, which is easily corrected. Namely, Moulton states that the set $\{a, a+b, a+c, b+c\}$ has the property that the sum of two of its elements equals the sum of the other two, but a quick check denies this assertion. However, one can still verify the claim of independence for $\{1,2,4,8\}$ in this case by way of contradiction. Specifically, if $a=1$, then $1+b=2^{m_{1}}$, $1+c=2^{m_{2}}$, and $b+c=2^{m_{3}}$, where we assume WLOG $m_{1} & \Delta_{n-1}\sum_{j=1}^{n-1}|p_{j}| \end{eqnarray} \noindent (where $\Delta_{k}$, for $k \geq 1$, denotes the maximum determinant of $k \times k$ $0-1$ matrices), then $P$ is independent. \end{Lemma} The well-known Hadamard bound is $\Delta_{k} \leq k^{k/2}$ (see for instance \cite{joh}). Using this bound and the above lemma allows us to extend Theorem \ref{A4m} in the following manner. \begin{Theorem}\label{extend_A4m} The following statements hold. \begin{enumerate} \item{$A_{(5,m)}$ is independent for all $m \geq 19$.} \item{$A_{(6,m)}$ is independent for all $m \geq 30$.} \item{$A_{(7,m)}$ is independent for all $m \geq 45$.} \end{enumerate} \end{Theorem} Thus, in view of Question \ref{indep_powers_ques}, Theorem \ref{extend_A4m} resolves all cases for $A_{(5,m)}$ except $4 \leq m \leq 18$, while the remaining cases of $A_{(6,m)}$ and $A_{(7,m)}$ are $5 \leq m \leq 29$ and $6 \leq m \leq 44$, respectively. Resolution of the above problem would likely involve, in light of Theorem \ref{extend_A4m}, finding better lower bounds for $m$, coupled with the use of a sieve. \section{Total Dependence of Polynomially Growing Sequences} While it is certainly possible to construct independent sets of $n$th powers for any positive integer $n \geq 2$, as we observed in the previous section, the question remains as to what, given such an $n$, the limiting rank of the set $P_{n}=\{1, 2^{n}, 3^{n}, \dots.\}$ is, provided the limit exists. We shall answer a more general version of this question. First, we give the following definition. \begin{Definition} A sequence of real numbers $\{a_{1}, a_{2}, a_{3}, \dots\}$ \underline{grows polynomially in $k$} if there exists a polynomial $P$ (of degree $n$, say) with real coefficients, and a positive integer $K$, such that $a_{k} \leq P(k)$ for all $k \geq K$. \end{Definition} Let ${\bf a}=\{a_{1}, a_{2}, \dots\}$ be a nondecreasing positive integer sequence that grows polynomially in $k$, with $\lim_{k \rightarrow \infty}a_{k}=\infty$. Thus, $a_{k} \leq P(k)$ for $k \geq K$, say, where the degree of $P$ is $n$, say. In particular, there exists a positive constant $C$ such that $a_{k} \leq Ck^{n}$ for all $k \geq K$. We claim that $\rho({\bf a})$ exists, and equals $0$. It is known (thanks to R. Sprague, see \cite{spr}) that, for every integer $n \geq 2$, there exists a largest positive integer $r_{n}$ that is not expressible as a sum of distinct $n$th powers of positive integers. Let $q$ be the largest positive integer such that $q^{n+1} \leq r_{n+1}$, and let $w=\max\{v,K-1\}$, where $v$ is the largest integer $k$ such that $a_{k} \leq r_{n+1}$. Set $T^{(0)}=\{a_{1}, a_{2}, \dots, a_{w}\}$, and $S^{(0)}=T^{(0)} \cup \{1, 2^{n+1}, \dots, q^{n+1}\}$, with $\lambda=|S^{(0)}|$. Clearly, $S^{(0)}$ represents $T^{(0)}$. We view the above setup as the zeroth stage of an algorithm whose purpose is to, ultimately, efficiently represent ${\bf a}$. At the $j$th stage, $j \geq 1$, we represent $T^{(j)}=\{a_{1}, a_{2}, \dots, a_{w}, \dots, a_{w+j}\}$. To do this, we append, as necessary, $(q+1)^{n+1}$, $(q+2)^{n+1}$, \dots, $(q+m_{j})^{n+1}$ to $S^{(j-1)}$ to create $S^{(j)}$. Here $m_{j}0$ for infinitely many $j$. Now observe that $$0<\frac{rk(T^{(j)})}{|T^{(j)}|} \leq \frac{|S^{(j)}|}{|T^{(j)}|}=\frac{m_{j}+\lambda}{w+j}<\frac{(C(w+j)^{n})^{\frac{1}{n+1}}-q+\lambda}{w+j}\longrightarrow0$$ as $j \rightarrow \infty$, which completes the proof of the following statement. \begin{Theorem}\label{sq_and_cu} Let ${\bf a}=\{a_{1}, a_{2}, \dots\}$ be a nondecreasing positive integer sequence that grows polynomially in $k$, with $\lim_{k \rightarrow \infty}a_{k}=\infty$. Then $\rho({\bf a})=0$. \end{Theorem} \begin{Corollary}\label{n_powers} Let $n$ be a positive integer. For the set $P_{n}=\{1, 2^{n}, 3^{n}, \dots.\}$, we have $\rho(P_{n})=0$. \end{Corollary} The converse, namely what can be said of a given set $S$ for which $\rho(S)=0$, seems to be more difficult, and is left as an open problem. \section{Summary} For sets consisting of $n^{th}$ powers, we have contrasted the notion of building independent sets using these powers with the limiting rank of such a set. In so doing, we have illustrated the crucial role that rate of growth plays in determining, both for finite and infinite sets, whether a set is independent, and if not, the level of dependence under which the set operates. In particular, we now know that the limiting rank of any polynomially growing positive integer sequence ${\bf a}$ with infinite limit, and in particular the set $P_{n}=\{1, 2^{n}, 3^{n}, \dots.\}$ for $n$ a positive integer, exists and equals zero. On the other hand, sets of powers of a positive integer $r \geq 2$ have limiting rank at most $(2r-2)/(2r-1)$ (see \cite{dev} and \cite{mou}), while the factorial sequence has limiting rank at least $1/2$ \cite{dev}. The above observations provoke the following question, an answer to which would be most welcome. \begin{Problem}\label{gen_ques} For a given set $S$ of positive integers whose elements are listed in increasing fashion, determine $\rho(S)$ if it exists, or at least offer reasonable upper and lower bounds for such. If $\rho(S)$ does not exist, explain why the limit fails to exist, and in so doing, describe the behavior of the sequence of ratios $\{rk(S_{1}), rk(S_{2})/2, rk(S_{3})/3, \dots\}$, where $S_{m}$ is the subset of $S$ consisting of the first $m$ elements of $S$. \end{Problem} \section{Acknowledgements} The author wishes to thank Joseph L. Yucas of Southern Illinois University and Patrick Mitchell of Midwestern State University for helpful discussions carried out in the course of writing this paper. The author also thanks the referee for his or her efforts in helping to improve the paper's quality. \begin{thebibliography}{9} \footnotesize \bibitem{dev} Develin, Mike. {\it On optimal subset representations of integer sets.\/} J. Number Theory {\bf 89} (2001), no. 2, 212-221. \bibitem{ili} Ilie, Lucian and Salomaa, Arto. {\it On the expressiveness of subset-sum representations.\/} Acta Inform. {\bf 36} (2000), no. 8, 665-672. \bibitem{joh} Johnson, Charles R. and Newman, Morris. {\it How bad is the Hadamard determinantal bound?\/} J. Res. Nat. Bur. Standards Sect. B {\bf 78B} (1974), 167-169. \bibitem{lev} Lev, Vsevolod F. {\it Blocks and progressions in subset sums sets.\/} Acta Arith. {\bf 106} (2003), no. 2, 123-142. \bibitem{mou} Moulton, David Petrie. {\it Representing powers of numbers as subset sums of small sets.\/} J. Number Theory {\bf 89} (2001), no. 2, 193-211. \bibitem{spr} Sprague, Roland. {\it $\ddot{U}$ber Zerlegungen in $n$-te Potenzen mit lauter verschiedenen Grundzahlen.\/} Math. Z. {\bf 51} (1948), 466-468. \end{thebibliography} \end{document}