<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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}

\begin{center}
\vskip 1cm{\LARGE\bf Unique Difference Bases of $\mathbb{Z}$ }
\vskip 1cm \large {Chi-Wu Tang, Min Tang,\footnote{
Corresponding author. The second author was supported
by the National Natural Science Foundation of China, Grant No.\
10901002 and the SF of the Education Department of Anhui Province,
Grant No. KJ2010A126.
} and Lei Wu}\\
Department of Mathematics \\
Anhui Normal University\\
Wuhu 241000 \\
P. R. China\\
\href{mailto:tmzzz2000@163.com}{\tt tmzzz2000@163.com} \\
\end{center}

\vskip .2in

\begin{abstract}
For $n\in \mathbb{Z}, A\subset \mathbb{Z}$, let $\delta_{A}(n)$
denote the number of representations of $n$ in the form $n=a-a'$,
where $a,a'\in A$. A set $A\subset \mathbb{Z}$ is called a unique
difference basis of $\mathbb{Z}$ if $\delta_{A}(n)=1$ for all $n\neq
0$ in $\mathbb{Z}$. In this paper, we prove that there exists a unique
difference basis of $\mathbb{Z}$ whose growth is logarithmic. These
results show that the analogue of the Erd\H{o}s-Tur\'{a}n conjecture
fails to hold in $(\mathbb{Z},-)$.
\end{abstract}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\section{Introduction}

\def\card{{\rm card}}

For sets $A$ and $B$ of integers and for any integer $c$, we define
the set
$$A-B=\{a-b:a\in A,b\in B\},$$ and the translations
$$A-c=\{a-c:a\in A\},$$ $$c-A=\{c-a:a\in
A\}.$$ The counting function for the set $A$ is
$$A(y,x)=\card\{a\in A:y\leq a\leq x\}.$$
For $n\in \mathbb{Z}$, we write
$$\delta_{A}(n)=\card\{(a,a')\in A\times A:a-a'=n \},$$
$$\sigma_{A}(n)=\card\{(a,a')\in A\times
A:a+a'=n\}.$$ We call $A\subset \mathbb{Z}$ a difference basis of
$\mathbb{Z}$ if $\delta_{A}(n)\geq 1$ for all $n\in \mathbb{Z}$, and
a unique difference basis of
$\mathbb{Z}$ if $\delta_{A}(n)=1$ for all $n\neq
0$ in $\mathbb{Z}$. We call $A$ a subset of $\mathbb{N}$ an additive
asymptotic basis of $\mathbb{N}$ if there is $n_{0}=n_{0}(A)$ such that
$\sigma_{A}(n)\geq 1$ for all $n\geq n_{0}$. The celebrated
Erd\H{o}s-Tur\'{a}n conjecture \cite{ET} states that if
$A\subset\mathbb{N}$ is an additive asymptotic basis of
$\mathbb{N}$, then the representation function $\sigma_{A}(n)$ must
be unbounded. In 1990, Ruzsa \cite{Ruzsa} constructed a basis of
$A\subset \mathbb{N}$ for which $\sigma_{A}(n)$ is bounded in the
square mean. P\u{u}s \cite{Pus} first established that the analogue
of the Erd\H{o}s-Tur\'{a}n conjecture fails to hold in some abelian
groups. Nathanson \cite{Nath} constructed a family of arbitrarily
sparse unique additive representation bases for $\mathbb{Z}$. In
2004, Haddad and Helou \cite{HH} showed that the analogue of the
Erd\H{o}s-Tur\'{a}n conjecture does not hold in a variety of
additive groups derived from those of certain fields. Let $K$ be a
finite field of characteristic $\neq 2$ and $G$ the additive group
of $K\times K$. Recently, Chi-Wu Tang and Min Tang \cite{TT} proved
there exists a set $B\subset G$ such that $1\leq \delta_{B}(g)\leq
14$ for all $g\neq 0$.

It is natural to consider the analogue of the Erd\H{o}s-Tur\'{a}n
conjecture in $(\mathbb{Z},-)$. In this paper, we obtain the
following results.\vskip 3mm
\begin{theorem}\label{thm1}  There exists a family of unique difference bases of $\mathbb{Z}$.\vskip 3mm
\end{theorem}
\begin{theorem}\label{thm2}
 There exists a unique difference basis $A$ of
$\mathbb{Z}$ such that
$$\frac{2\log(3x+3)}{\log 3}-\frac{2\log
5}{\log 3}&lt; A(0,x)\leq\frac{2\log (x+3)}{\log 2}-2 \textnormal{ for
all }x\geq 1.
$$\end{theorem}
\bigbreak


\section{Proof of Theorem \ref{thm1}.}  We shall construct an ascending sequence $A_{1}\subseteq
A_{2}\subseteq \cdots $ of finite sets of nonnegative integers such that
$$|A_{k}|=2k,\textnormal{ for all }k\geq 1,$$ $$\delta_{A_{k}}(n)\leq 1, \textnormal
{ for all }n\neq 0.$$ We shall prove that the infinite set
$$A=\bigcup_{k=1}^{\infty}A_{k}$$ is a unique difference basis of $\mathbb{Z}$.

We construct the sets $A_{k}$ by induction. Let $A_{1}=\{0,1\}$. We
assume that for some $k\geq 1$ we have constructed sets
$A_{1}\subseteq\cdots \subseteq A_{k}$ such that $|A_{i}|=2i
$ and $\delta_{A_{i}}(n)\leq 1$ for all $1\leqslant i\leqslant k$ and all integers
$n\neq 0.$ We define the integers
$$d_{k}=\max\{a:a\in A_{k}\},$$
$$b_{k}=\min\{|b|:b \not\in A_{k}-A_{k}\}.$$
To construct the set $A_{k+1}$, we choose an integer $c_{k}$ such
that $c_{k}&gt;d_{k}$. Let
$$A_{k+1}=A_{k}\cup\{2c_{k}, b_{k}+2c_{k}\}.$$
Then $|A_{k+1}|=2k+2=2(k+1) \textnormal { for all }k\geq 1$, and
$A_{k}\subseteq[0, d_{k}],\; A_{k}-A_{k}\subseteq[-d_{k}, d_{k}].$

Note that
$$A_{k+1}-A_{k+1}=(A_{k}-A_{k})\cup(A_{k}-(b_{k}+2c_{k}))$$
$$\cup((b_{k}+2c_{k})-A_{k})\cup(A_{k}-2c_{k})\cup(2c_{k}-A_{k})\cup\{b_{k},
-b_{k}\}.\eqno{(1)}$$ We shall show that $A_{k+1}-A_{k+1}$ is the
disjoint union of the above six sets.

\noindent If $u\in A_{k}-A_{k}$, then $$-d_{k}\leq u\leq
d_{k}.\eqno{(2)}$$ If $v_{1}\in A_{k}-(b_{k}+2c_{k})$ and $v_{2}\in
(b_{k}+2c_{k})-A_{k}$, then there exist  $a, a'\in A_{k}$ such that
$v_{1}=a-(b_{k}+2c_{k})$ and $v_{2}=(b_{k}+2c_{k})-a' $. Since
$0\leq a, a'\leq d_{k}$, we have
$$-b_{k}-2c_{k}\leq v_{1}\leq
-b_{k}-2c_{k}+d_{k},\eqno{(3)}$$ $$b_{k}+2c_{k}-d_{k}\leq v_{2}\leq
b_{k}+2c_{k}.\eqno{(4)}$$  If $w_{1}\in A_{k}-2c_{k}$ and $w_{2}\in
2c_{k}-A_{k}$, similarly, we have
$$-2c_{k}\leq w_{1}\leq -2c_{k}+d_{k},\eqno{(5)}$$ $$2c_{k}-d_{k}\leq w_{2}\leq
2c_{k}.\eqno{(6)}$$ For any $n\in \mathbb{Z}$, if $n\in
A_{k}-A_{k}$, then $-n\in A_{k}-A_{k}$, thus by the definition of
$b_{k}$, we have $$b_{k}\not\in A_{k}-A_{k} \textnormal{ and }
-b_{k}\not\in A_{k}-A_{k}.\eqno{(7)}$$ Assume
$(2c_{k}-A_{k})\cap((b_{k}+2c_{k})-A_{k})\neq\emptyset$, then there
exist $a, a'\in A_{k}$ such that $b_{k}+2c_{k}-a=2c_{k}-a'$,
$b_{k}=a-a'\in A_{k}-A_{k}$ which contradicts with the fact
$b_{k}\not\in A_{k}-A_{k}$. Similarly, we have
$(A_{k}-(b_{k}+2c_{k}))\cap(A_{k}-2c_{k})=\emptyset$.

Moreover, we have $d_{k}\in
A_{k}-A_{k}$, hence $b_{k}\neq d_{k}$. If $b_{k}&lt;d_{k}$, it is easy to see that the set $\{-b_k,b_k\}$ is disjoint with the other five sets.
If $b_{k}&gt;d_{k}$, since $d_{k}\in A_{k}-A_{k}$ and by the
definition of $b_k$, we have $b_{k}=d_{k}+1$. Then $2c_k-d_k\geqslant 2(d_k+1)-d_k=d_k+2&gt;b_k$
and $-2c_k+d_k\leqslant -2(d_k+1)+d_k=-d_k-2&lt;-b_k$, thus the set $\{-b_k,b_k\}$ is disjoint with the other five sets.

By Eq.~(1)--(6) and the above discussion, we know that the sets
$A_{k}-A_{k},\; A_{k}-(b_{k}+2c_{k}), \;(b_{k}+2c_{k})-A_{k},
\;A_{k}-2c_{k}, \;2c_{k}-A_{k},\;\{b_{k}, -b_{k}\}$ are pairwise
disjoint. That is,
 $\delta_{A_{k+1}}(n)\leq 1 \textnormal{ for all integers
}n\neq 0. $

Let $A=\bigcup\limits_{k=1}^{\infty}A_{k}.$ Then for all $k\geq 1$,
by (7) and the definition of $b_k$, we have
$$\{-b_{k}+1,-b_{k}+2,\cdots,-1,1,\cdots,b_{k}-2,b_{k}-1\}\subset
A_{k}-A_{k}\subset A-A,$$ and the sequence $\{b_k\}_{k\geqslant 1}$ is strictly increasing, since $A_k-A_k\subset A_{k+1}-A_{k+1}$ and $\pm b_k\in A_{k+1}-A_{k+1}$ but $\pm b_k\not\in A_{k}-A_{k}$. Thus $A$ is a difference basis of
$\mathbb{Z}$. If $\delta_{A}(n)\geq 2$ for some $n$, then by
construction, $\delta_{A_{k}}(n)\geq 2$ for some $k$, which is
impossible. Therefore, $A$ is a unique difference basis of
$\mathbb{Z}$.

It completes the proof of Theorem \ref{thm1}.\vskip 1cm


\section{Proof of Theorem \ref{thm2}.}
We apply the method of Theorem \ref{thm1} with
$$c_{k}=d_{k}+1 \textnormal{ for all }k\geq 1.$$
This is essentially a greedy algorithm construction, since at each
iteration we choose the smallest possible value of $c_{k}$. It is
instructive to compute the first few sets $A_{k}$. Since
$$A_{1}=\{0,1\}, \quad A_{1}-A_{1}=\{-1,0,1\},$$ we have
$b_{1}=2,d_{1}=1$, and $c_{1}=d_{1}+1=2$. Then
$$A_{2}=\{0,1,4,6\}, \quad A_{2}-A_{2}=\{-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6\},$$
hence $b_{2}=7,d_{2}=6$, $c_{2}=d_{2}+1=7$. The next iteration of
the algorithm produces the sets
$$A_{3}=\{0,1,4,6,14,21\},$$
$$A_{3}-A_{3}=\{-21,-20,-17,-15,-14,-13,-10,-8,$$
$$-7,7,8,10,13,14,15,17,20,21\}\cup(A_{2}-A_{2}),$$
so we obtain $b_{3}=9,d_{3}=21,c_{3}=22$, and
$$A_{4}=\{0,1,4,6,14,21,44,53\}.$$
We shall compute upper and lower bounds for the counting function
$A(0,x)$. We observe that if $x\geq d_{1}$ and $k$ is the unique
integer such that $d_{k}\leq x&lt;d_{k+1}$, by the construction of $A$,
we know $A_{k}=|2k|$ and $A_{k+1}=A_{k}\cup\{2c_{k},2c_{k}+b_{k}\}$,
then
$$A(0,x)=A_{k+1}(0,x)= 
\begin{cases}
2k, &amp; \text{if $d_{k}\leq x&lt;2c_{k}$,}\\
2k+1, &amp; \text{if $2c_{k}\leq x&lt;2c_k+b_k=d_{k+1}$}.
\end{cases} $$ 
For
$k\geq 1$, we have $1&lt; b_{k}\leq d_{k}+1=c_{k}$ and
$c_{k+1}=d_{k+1}+1=2c_{k}+b_{k}+1$, hence
$$2c_{k}+2&lt;c_{k+1}\leq 3c_{k}+1.$$

\noindent Since $c_{1}=d_{1}+1=2$, it follows by induction on $k$
that
$$2^{k+1}-2\leq c_{k}\leq \frac{5}{2}\cdot 3^{k-1}-\frac{1}{2},$$
and so
$$\frac{\log\displaystyle\frac{6}{5}\big(c_{k}+\displaystyle\frac{1}{2}\big)}{\log
3}\leq k\leq\frac{\log\displaystyle\frac{c_{k}+2}{2}}{\log
2}\textnormal{ for all } k\geq 1.$$

We obtain an upper bound for $A(0,x)$ as follows. If $d_{k}\leq
x&lt;2c_{k}$, then $c_{k}\leq x+1$, and $$A(0,x)=A_{k+1}(0,x)=2k\leq
2\frac{\log\displaystyle\frac{c_{k}+2}{2}}{\log 2}\ = \frac{2\log
(c_{k}+2)}{\log 2}-2\leq \frac{2\log (x+3)}{\log 2}-2.$$

\noindent If $2c_{k}\leq x&lt;d_{k+1}$, then
$c_{k}\leq\displaystyle\frac{x}{2}$, and
$$A(0,x)=A_{k+1}(0,x)=2k+1\leq\frac{2\log\displaystyle\frac{c_{k}+2}{2}}{\log
2}+1\leq \frac{2\log\big(\displaystyle\frac{x}{4}+1\big)}{\log
2}+1=\frac{2\log (x+4)}{\log 2}-3.$$

\noindent Therefore,$$A(0,x)\leq\frac{2\log (x+3)}{\log 2}-2
\textnormal{ for all }x\geq 1 .$$

Similarly, we obtain a lower bound for $A(0,x)$. If $d_{k}\leq
x&lt;2c_{k}$, then $$A(0,x)=2k\geq
\frac{2\log\displaystyle\frac{6}{5}\big(c_{k}+\displaystyle\frac{1}{2}\big)}{\log
3}&gt; \frac{2\log\displaystyle\frac{3}{5}(x+1)}{\log 3}=
\frac{2\log(3x+3)}{\log 3}-\frac{2\log 5}{\log 3}.$$

\noindent If $2c_{k}\leq x&lt;d_{k+1}$, then
$d_{k+1}=b_{k}+2c_{k}\leq 3c_{k}.$ So $c_k\geq \frac{1}{3}d_{k+1}&gt;\frac{1}{3}x$
and $$A(0,x)=2k+1\geq
\frac{2\log\displaystyle\frac{6}{5}\big(c_{k}+\displaystyle\frac{1}{2}\big)}{\log
3}+1&gt;
\frac{2\log\displaystyle\frac{6}{5}\big(\displaystyle\frac{x}{3}+\displaystyle\frac{1}{2}\big)}{\log
3}+1= \frac{2\log(2x+3)}{\log 3}+1-\frac{2\log 5}{\log 3}.$$

\noindent Therefore,$$A(0,x)&gt; \frac{2\log(3x+3)}{\log
3}-\frac{2\log 5}{\log 3} \textnormal{ for all }x\geq 1.$$

This completes the proof of Theorem \ref{thm2}.


\section{Acknowledgements} We would
like to thank the referee for his/her many helpful suggestions. 


\begin{thebibliography}{9}

\bibitem{ET}  P. Erd\H{o}s and P. Tur\'{a}n, On a problem of Sidon
in additive number theory, and on some related problems,  {\it J.
London Math. Soc.} {\bf 16 } (1941), 212--215.

\bibitem{HH}  L. Haddad and C. Helou,  Bases in some additive groups
and the Erd\H{o}s-Tur\'{a}n conjecture,  {\it J. Combin. Theory Series
A} {\bf 108} (2004), 147--153.

\bibitem{Nath} M. B. Nathanson, Unique representation bases for
integers, {\it Acta Arith.} {\bf 108} (2003), 1--8.

\bibitem{Pus}  V. P\v{u}s, On multiplicative bases in abelian groups,
{\it Czech. Math. J. } {\bf 41} (1991), 282--287.

\bibitem{Ruzsa}  I. Z. Ruzsa, A just basis,  {\it Monatsh. Math}
{\bf 109} (1990), 145--151.

\bibitem{TT}  Chi-Wu Tang and Min Tang, Note on a result of Haddad
  and Helou, {\it Integers} {\bf 10} (2010), 229--232.
Available electronically at \href{http://integers-ejcnt.org/vol10.html}{\tt
http://integers-ejcnt.org/vol10.html}.



\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: Primary
11B13; Secondary 11B34.

\noindent \emph{Keywords: } Erd\H{o}s-Tur\'{a}n conjecture;
difference bases; counting function.

\bigskip
\hrule
\bigskip
\noindent
Received October 12 2010;
revised version received January 26 2011.
Published in {\it Journal of Integer Sequences}, February 9 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}

                                                                                

</pre></body></html>