\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{problem}[theorem]{Problem} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \def\ul{\underline} \def\imp{\rightarrow} \def\ds{\displaystyle} \def\ts{\textstyle} \def\pr{\prime} \def\lf{\lfloor} \def\rf{\rfloor} \def\lc{\lceil} \def\rc{\rceil} \def\sm{\setminus} \def\A{\mathscr A} \def\I{\mathscr I} \def\N{\mathbb N} \def\R{\mathbb R} \def\S{\mathcal S} \def\Z{\mathbb Z} \def\a{\alpha} \def\d{\delta} \def\k{\kappa} \def\l{\lambda} \def\o{\overline} \def\s{\sigma} \begin{center} \vskip 1cm{\LARGE\bf Another Proof of Nathanson's Theorems} \vskip 1cm \large Quan-Hui Yang \\ School of Mathematical Sciences \\ Nanjing Normal University \\ Nanjing 210046 \\ P. R. China\\ \href{mailto:yangquanhui01@163.com}{\tt yangquanhui01@163.com} \end{center} \vskip .2 in \begin{abstract} In this paper, without using generating functions, we give new combinatorial proofs of several theorems by Nathanson on the representation functions, and we also obtain generalizations of these theorems. \end{abstract} \section{Introduction} Let $\mathcal{A}$ be a set of nonnegative integers. Let $r_h^ \mathcal{A}(n)$ denote the number of representations of $n$ as a sum of $h$ elements of $\mathcal{A}$ and $r^\mathcal{A}(n)$ denote the number of representations of $n$ as a sum of an arbitrary number of elements of $\mathcal{A}$, where representations differing only in the arrangement of their summands are counted separately. We notice that if $0 \notin \mathcal{A}$, then $r^\mathcal{A}(n)=\sum_{h=1}^{\infty}{r_h^\mathcal{A}(n)}$ is finite for all $n$. Representation functions have been extensively studied by many authors \cite{ChenSarkozy,Erdos86,Erdos94,Nathanson05,Nathanson07} and are still a fruitful area of research in additive number theory. Using generating functions, Nathanson \cite{Nathanson78} proved the following results. \begin{theorem}\label{thm1} Let $\mathcal{A}$ and $\mathcal{B}$ be sets of nonnegative integers, and let $r_h^\mathcal{A}(n)$ and $r_h^\mathcal{B}(n)$ denote the number of representations of $n$ as a sum of $h$ elements of $\mathcal{A}$ and $\mathcal{B}$, respectively. If $r_h^\mathcal{A}(n)=r_h^\mathcal{B}(n)$ for all $n\geqslant 0$, then $\mathcal{A}=\mathcal{B}$. \end{theorem} \begin{theorem}\label{thm2} Let $\mathcal{A}$ and $\mathcal{B}$ be sets of positive integers, and let $r^\mathcal{A}(n)$ and $r^\mathcal{B}(n)$ denote the number of representations of $n$ as a sum of an arbitrary number of elements of $\mathcal{A}$ and $\mathcal{B}$, respectively. If $r^\mathcal{A}(n)=r^\mathcal{B}(n)$ for all $n\geqslant 1$, then $\mathcal{A}=\mathcal{B}$. \end{theorem} \begin{theorem}\label{thm3} Let $\mathcal{A}$ and $\mathcal{B}$ be sets of positive integers, and let $p^\mathcal{A}(n)$ and $p^\mathcal{B}(n)$ denote the number of representations of $n$ as a sum of an arbitrary number of elements of $\mathcal{A}$ and $\mathcal{B}$, respectively, where representations differing only in the arrangement of their summands are not counted separately. If $p^\mathcal{A}(n)=p^\mathcal{B}(n)$ for all $n\geqslant 1$, then $\mathcal{A}=\mathcal{B}$. \end{theorem} In this paper, we give new proofs of theorems above. Indeed, we shall prove slightly more. We first introduce some notation. If $\mathcal{A}$ is a strictly increasing sequence of integers, then $a_n$ denotes the $n$th element of $\mathcal{A}$. Let $\mathcal{A}$ be a set of nonnegative integers and $\mathcal{H}$ be a set of positive integers. If $|\mathcal{H}|$ is finite, then $r_\mathcal{H}^\mathcal{A}(n)$ denotes the number of representations of $n$ as a sum of $h_1$ or $h_2$ or $\ldots$ elements of $\mathcal{A}$; if $|\mathcal{H}|$ is infinite, then $r_\mathcal{H}^\mathcal{A}(n)$ denotes the number of representations of $n$ as a sum of $h_1$ or $h_2$ or $\ldots$ elements of $\mathcal{A} \backslash \{0\}$. \begin{theorem}\label{thm4} Let $\mathcal{A}$ and $\mathcal{B}$ be nonempty sets of nonnegative integers. Let $\mathcal{H}$ be a nonempty set of positive integers, and let $S=\{\min\{a_i,b_i\}:i=1,2,\ldots\}$. Write $t=(\min(\mathcal{H})-1)\min \{a_1,b_1\}$. If $r_\mathcal{H}^\mathcal{A}(n)=r_\mathcal{H}^\mathcal{B}(n)$ for all $n \in t+S$, then $\mathcal{A}=\mathcal{B}$. \end{theorem} Let $\mathcal{H}=\{h\}$. Since $t+S \subseteq \{0,1,2,\ldots\}$, Theorem \ref{thm4} is a generalization of Theorem \ref{thm1}. Let $\mathcal{H}=\{1,2,3,\ldots\}$. If $\mathcal{A}$ and $\mathcal{B}$ are sets of positive integers, then $t+S \subseteq \{1,2,\ldots\}$. Hence, Theorem \ref{thm4} is also a generalization of Theorem \ref{thm2}.\vskip 3mm \begin{theorem}\label{thm5} Let $\mathcal{A}$, $\mathcal{B}$ and $\mathcal{H}$ be nonempty sets of positive integers. Let $S=\{\min\{a_i,b_i\}:i=1,2,\ldots\}$, and let $p_\mathcal{H}^\mathcal{A}(n)$ denote the number of representations of $n$ as a sum of $h_1$ or $h_2$ or $\ldots$ elements of $\mathcal{A}$, where representations differing only in the arrangement of their summands are not counted separately. Write $t=(\min(\mathcal{H})-1)\min \{a_1,b_1\}$. If $p_\mathcal{H}^\mathcal{A}(n)=p_\mathcal{H}^\mathcal{B}(n)$ for all $n \in t+S$, then $\mathcal{A}=\mathcal{B}$. \end{theorem} Let $\mathcal{H}=\{1,2,3,\ldots\}$. Since $t+S \subseteq \{1,2,\ldots\}$, Theorem \ref{thm5} is a generalization of Theorem \ref{thm3}. Let $A,B,$ and $T$ be finite sets of integers. If each residue class modulo $m$ contains exactly the same number of elements of $A$ as elements of $B$, then we write $A\equiv B$ (mod $m$). If the number of solutions of the congruence $a+t \equiv n$ (mod $m$) with $a\in A,$ $t\in T$, equals the number of solutions of the congruence $b+t \equiv n$ (mod $m$) with $b\in B$, $t\in T$, for each residue class $n$ modulo $m$, then we write $A+T \equiv B+T$ (mod $m$). Nathanson \cite{Nathanson78} also proved the following theorem. \begin{theorem}\label{thm6} Let $\mathcal{A}$ and $\mathcal{B}$ be distinct nonempty sets of nonnegative integers such that $r_2^\mathcal{A}(n)=r_2^\mathcal{B}(n)$ for all sufficiently large $n$. Then there exist finite sets $A,B,$ and $T$ with $A \cup B \subset \{0,1,\ldots,N \}$ and $T\subset \{0,1,\ldots,m-1\}$ such that $A+T \equiv B+T$ (mod $m$), and $\mathcal{A}=A \cup ~\mathcal{C}$ and $\mathcal{B}=B \cup ~\mathcal{C}$, where $\mathcal{C}=\{c>N |~ c \equiv t$ (mod $m$) for some $t \in T\}$. \end{theorem} In this paper, we prove theorems above without using generating functions. We notice that for a prime number $p$, if $\mathcal{A}$ and $\mathcal{B}$ are sets of nonnegative integers such that $r_p^\mathcal{A}(n)=r_p^\mathcal{B}(n)$ for all sufficiently large $n$, then $\mathcal{A}$ and $\mathcal{B}$ eventually coincide. Now, I pose the following problem. \begin{problem} Let $p \geqslant 3$ be a prime number and $\mathcal{A}$ be a set of nonnegative integers. Does there exist a set of nonnegative integers $\mathcal{B}$ with $\mathcal{B} \neq \mathcal{A}$ such that $r_p^\mathcal{A}(n)=r_p^\mathcal{B}(n)$ for all sufficiently large $n$? \end{problem} \section{Proof of Theorems \ref{thm4} and \ref{thm5}} Suppose that $\mathcal{A} \neq \mathcal{B}$. Let $h=\min(\mathcal{H})$ and $j_0$ be the smallest index such that $a_{j_0}\neq b_{j_0}$. Without loss of generality, we can assume that $a_{j_0} < b_{j_0}$. Let $C=\{a_j: j < j_0\}$. Since $a_j=b_j$ for all $j < j_0$ and $t=(h-1)a_1$, we have $(h-1)a_1+a_{j_0}\in t+S$ and $$\begin{array}{rl} r_\mathcal{H}^\mathcal{A}((h-1)a_1+a_{j_0})& = r_\mathcal{H}^C((h-1)a_1+a_{j_0})+1\\ & \\ &=r_\mathcal{H}^\mathcal{B}((h-1)a_1+a_{j_0})+1, \end{array}$$ which is a contradiction. Hence, we have $\mathcal{A}=\mathcal{B}$. This completes the proof of Theorem \ref{thm4}. The proof of Theorem \ref{thm5} is very similar to the proof of Theorem \ref{thm4}, and we omit it here. \section{Proof of Theorem \ref{thm6}} Clearly, $r_2^{\mathcal{A}}(2n)$ is odd if and only if $n\in \mathcal{A}$. Similarly, $n\in \mathcal{B}$ if and only if $r_2^{\mathcal{B}}(2n)$ is odd. If $r_2^{\mathcal{A}}(n)=r_2^{\mathcal{B}}(n)$ for all $n > N_0$, then for all $n > N_0$ we have $n\in \mathcal{A}$ if and only if $n\in \mathcal{B}$. Let $$\mathcal{D}=\mathcal{A}\cap [N_0 +1,\infty )=\mathcal{B}\cap [N_0 +1,\infty )$$ and write $$\eta(n)=\begin{cases} 1,~~\text{if}~~n\in \mathcal{D}; \\ 0,~~\text{otherwise}. \end{cases}$$ Then for $n > 2N_0$, we have $$\begin{array}{rl} r_2^{\mathcal{A}}(n)& =2 \sharp \{(a,d): a \in \mathcal{A} \backslash \mathcal{D},d \in \mathcal{D}, a+d=n\}\\ & \\ &~~+\sharp \{(d',d''): d',d'' \in \mathcal{D} , d'+d''=n\}\\ & \\ &=2\sum\limits_{a\in \mathcal{A} \backslash \mathcal{D}} \eta(n-a) + \sharp \{(d',d''): d',d'' \in \mathcal{D} , d'+d''=n\}. \end{array} \ \eqno{(1)} $$ Similarly, we have $$r_2^{\mathcal{B}}(n)=2\sum\limits_{b\in \mathcal{B} \backslash \mathcal{D}} \eta(n-b) + \sharp \{(d',d''): d',d'' \in \mathcal{D} , d'+d''=n\}.\ \eqno{(2)}$$ Since $r_2^{\mathcal{A}}(n)=r_2^{\mathcal{B}}(n)$ for all $n > N_0$, by (1) and (2), we have $$\sum\limits_{a\in \mathcal{A} \backslash \mathcal{D}}\eta(n-a) =\sum\limits_{b\in \mathcal{B} \backslash \mathcal{D}}\eta(n-b)\ \eqno{(3)}$$ for all $n> 2N_0$. Let $i_0$ be the smallest index such that $a_{i_0} \neq b_{i_0}.$ Without loss of generality, we may assume that $a_{i_0}< b_{i_0}.$ Let $$t=n-a_{i_0}$$ and $$\mathcal{D'}=\{a:a< a_{i_0}, a\in \mathcal{A}\}.$$ Then by (3), we have $$\eta(t)=\sum\limits_{b\in \mathcal{B} \backslash (\mathcal{D}\cup \mathcal{D'})}{\eta(t+a_{i_0}-b)}-\sum\limits_{a \in \mathcal{A} \backslash (\mathcal{D}\cup \mathcal{D'} \cup {a_{i_0}})}{\eta(t+a_{i_0}-a)}.$$ Since $\eta(t)$ defined by a linear recurrence on a finite set $\{0,1\}$, we have that it must be eventually periodic. Hence, for some $N > N_0$, $\mathcal{D}\cap [N+1,\infty )$ is periodic. We denote such a period by $m$. Let $T=\{t: t\equiv d$ (mod $m$) for some $d\in \mathcal{D}\cap [N+1,\infty )$ and $0\leqslant t < m\}$. Then we have $n\in \mathcal{A} \cap \mathcal{B} \cap [N+1,\infty )$ if and only if $n\equiv t$ (mod $m$) for some $t\in T$. The remainder of the proof is the same as that of the proof by Nathanson. To make this paper self-contained, we formulate it here. Let $$A=\{a \leqslant N: a\in \mathcal{A}\},~~~B=\{b \leqslant N: b\in \mathcal{B}\},$$ and $$\mathcal{C}=\{c> N: c \in \mathcal{A}\cap \mathcal{B}\}=\{c> N: c \equiv t ~(\text{mod}~m) ~\text{for some }~t\in T\}.$$ Then $\mathcal{A}=A \cup \mathcal{C}$ and $\mathcal{B}=B \cup \mathcal{C}.$ Next we prove that $A+T \equiv B+T$ (mod $m$). For $n> 2N$, we have $$\begin{array}{rl} r_2^{\mathcal{A}}(n)&=r_2^{\mathcal{C}}(n)+2 \sharp \{(a,c): a \in A, c \in \mathcal{C},a+c=n\}\\ & \\ &=r_2^{\mathcal{C}}(n)+2 \sharp \{(a,t): a \in A, t \in T,a+t \equiv n~ (\text{mod}~ m)\}. \end{array} \ \eqno{(4)} $$ Similarly, $$r_2^{\mathcal{B}}(n)=r_2^{\mathcal{C}}(n)+2 \sharp \{(b,t): b \in B, t \in T,b+t \equiv n~ (\text{mod}~ m)\}.\ \eqno{(5)}$$ Since $r_2^{\mathcal{A}}(n)=r_2^{\mathcal{B}}(n)$ for $n>2N$, by (4) and (5), we have that $A+T \equiv B+T$ (mod $m$). This completes the proof of Theorem \ref{thm6}. \section{Acknowledgement} I sincerely thank my supervisor Professor Yong-Gao Chen for his valuable suggestions and useful discussions. I am also grateful to the referee for his/her valuable comments. \bibliographystyle{amsplain} \begin{thebibliography}{10} \bibitem{ChenSarkozy} Y. G. Chen, A. S\'{a}rk\H{o}zy, V. T. S\'{o}s, and M. Tang, On the monotonicity properties of additive representation functions, {\it Bull. Aust. Math. Soc.} {\bf 72} (2005), 129--138. \bibitem{Erdos86} P. Erd\H{o}s, A. S\'{a}rk\H{o}zy, and V. T. S\'{o}s, Problems and results on additive properties of general sequences, V, {\it Monatsh. Math.} {\bf 102} (1986), 183--197. \bibitem{Erdos94} P. Erd\H{o}s, A. S\'{a}rk\H{o}zy, and V. T. S\'{o}s, On additive properties of general sequences, {\it Discrete Math.} {\bf 136} (1994), 75--99. \bibitem{Nathanson78} M. B. Nathanson, Representation functions of sequences in additive number theory, {\it Proc. Amer. Math. Soc.} {\bf 72} (1978), 16--20. \bibitem{Nathanson05} M. B. Nathanson, Every function is the representation function of an additive basis for the integers, {\it Port. Math.} {\bf 62} (2005), 55--72. \bibitem{Nathanson07} M. B. Nathanson, Representation functions of bases for binary linear forms, {\it Funct. Approx. Comment. Math.} {\bf 37} (2007), 341--350. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11B34; Secondary 11D85. \noindent \emph{Keywords: } Nathanson's theorems; representation functions; generating functions. \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received March 13 2011; revised version received August 13 2011. Published in {\it Journal of Integer Sequences}, September 25 2011. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}