\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}< 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}>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}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>b_k$ and $-2c_k+d_k\leqslant -2(d_k+1)+d_k=-d_k-2<-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 \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\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> \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)> \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}