\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}

                                                                                


.
