\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}{-.1in} \setlength{\textheight}{8.4in} \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} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf A New Lower Bound for the \\ \vskip .12in Distinct Distance Constant } \vskip 1cm \large Raffaele Salvia \\ \href{mailto:raffaelesalvia@alice.it}{\tt raffaelesalvia@alice.it} \\ \end{center} \vskip .2 in \begin{abstract} The reciprocal sum of the Zhang sequence is not equal to the distinct distance constant. This note introduces a $B_2$-sequence with larger reciprocal sum, and provides a more precise estimate of the reciprocal sums of the Mian-Chowla sequence and the Zhang sequence. \end{abstract} \vskip .2in \section{Introduction} A \emph{Sidon sequence}, also called a \emph{$B_2$-sequence}, is a sequence of positive integers $$a_1~<~a_2~<~a_3~<~\cdots$$ such that all the sums $a_i+a_j \ (i \leq j)$ are distinct. The \emph{distinct distance constant} (DDC) is the supremum of the set of the reciprocal sums of Sidon sequences. Levine \cite{Levine} observed that \begin{equation} {\rm DDC} \leq \sum_{n=0}^\infty \frac{1}{1+\frac{n(n+1)}{2}} = \frac{2\pi}{\sqrt{7}}\tanh{ \left( \frac{\sqrt{7}}{2}\pi \right)} < 2.37366\,. \end{equation} Let $S_A$ be the reciprocal sum of the sequence $A$; that is, $S_A= \sum_{i=1}^\infty \frac{1}{a_i}$. It is an open problem to find, if it exists, a Sidon sequence $U$ whose reciprocal sum is equal to the DDC \cite[p.~351]{Guy}. We only know from Taylor and Yovanof \cite{Taylor and Yovanof} that, if some Sidon sequence achieves the DDC, then it must begin with the values 1, 2, 4. The $B_2$-sequence with the largest known reciprocal sum had been, for a long time, the one produced by the greedy algorithm, $G=\{ 1, 2, 4, 8, 13, 21, 31, 45, 66, 81, \dots \}$. The sequence $G$ is named the \emph{Mian-Chowla sequence}. Lewis found that \begin{equation} 2.158435 \leq S_G \leq 2.158677\,, \end{equation} where $S_G$ is the reciprocal sum of $G$ \cite[pp.~164--165]{Finch}. In 1991, Zhang \cite{Zhang} found a Sidon sequence with a reciprocal sum greater than $S_A$. Zhang's sequence $Z$ is obtained by running the greedy algorithm for the first 14 terms, setting $z_{15}=229$, and then continuing with the greedy algorithm. Zhang proved that \begin{equation} S_Z > 2.1597\,. \end{equation} The aim of this note is to exhibit a Sidon sequence $H$ such that $S_H > S_Z$. \section{Computation of reciprocal sums} \subsection{Preliminary considerations} To estimate the reciprocal sum, we will use two basic properties of Sidon sequences: they are growing sequences, and their differences $a_i-a_j \ (i \geq j)$ are all distinct. That is, \begin{equation} a_i \geq a_j + (i-j), \ i \geq j \end{equation} \begin{equation} a_i > \frac{i(i-1)}{2}\,. \end{equation} Therefore, if we know the values of $a_n$ for $1 \leq n \leq k$, we also know that \begin{equation} \sum_{n=1}^k \frac{1}{a_n} < S_A < \sum_{n=1}^k \frac{1}{a_n} + \sum_{n=k}^\infty \frac{1}{\max\left(a_k+n-k , \frac{n(n-1)}{2} \right)}\,. \end{equation} Further assumptions could be made on $a_i$, but for large values of $k$ they would not yield a significant improvement of the bounds. \subsection{The reciprocal sum of the Mian-Chowla sequence} Let $G$ be the $B_2$-sequence constructed by the greedy algorithm. The values of $g_n$ for $1 \leq n \leq 25000$, computed on my notebook, are listed in the accompanying file \texttt{MianChowla.txt}. We get the following bounds for $S_G$: \begin{equation} \sum_{n=1}^{25000} \frac{1}{g_n} < S_G < \sum_{n=1}^{25000} \frac{1}{g_n} + \sum_{n=25001}^{510096} \frac{1}{g_{25000}+n-25000} + \sum_{n=510097}^\infty \frac{2}{n(n-1)}\,, \end{equation} i.e., \begin{equation} 2.15845268 < S_G < 2.15846062\,. \end{equation} \subsection{The reciprocal sum of the Zhang sequence} The Zhang sequence $Z$ \cite{Zhang} is, at the moment, the known Sidon sequence with the largest reciprocal sum. In the accompanying file \texttt{Zhang.txt} there are the first 25000 terms of $Z$. Their values allow us to compute the following bounds for $S_Z$: \begin{equation} \sum_{n=1}^{25000} \frac{1}{z_n} < S_Z < \sum_{n=1}^{25000} \frac{1}{z_n} + \sum_{n=25001}^{510290} \frac{1}{z_{25000}+n-25000} + \sum_{n=510291}^\infty \frac{2}{n(n-1)} \end{equation} \begin{equation} S_G < 2.16007769 < S_Z < 2.16008532\,. \end{equation} \subsection{The sequence $H$ and its reciprocal sum} \begin{definition} \begin{displaymath} h_n = \begin{cases} 1, & \text{if $n=1$;} \\ 229, & \text{if $n=15$;} \\ 962, & \text{if $n=27$;} \\ \min \{ x | \forall i, j, k \leq n, a_i + a_j \neq a_k + x \} , & \text{otherwise.} \end{cases} \end{displaymath} \end{definition} The first 26 terms of the sequence $H$ are the same of the Zhang seqence, the 27$^{th}$ term is 962, and from there on the values are provided by the greedy algorithm. We will now prove that the sequence $H$ satisfies our aim, i.e., $S_H>S_Z$. We can find the first values of $h_n$ ($1 \leq n \leq 25000$) in the accompanying file \texttt{H.txt}. Hence we get \begin{equation} \sum_{n=1}^{25000} \frac{1}{h_n} < S_H < \sum_{n=1}^{25000} \frac{1}{h_n} + \sum_{n=25001}^{510140} \frac{1}{h_{25000}+n-25000} + \sum_{n=510141}^\infty \frac{2}{n(n-1)} \end{equation} \begin{equation} 2.16027651 < S_H < 2.16028417\,. \end{equation} In conclusion, \begin{equation} S_Z < 2.16027651 < S_H \leq {\rm DDC}\,, \end{equation} which was what we wanted to prove. I found the sequence $H$ using an algorithm which proceeds as follows: given a finite Sidon sequence $b_1, b_2, \ldots , b_n$, choose as $b_{n+1}$ the value that would yield the largest reciprocal sum if the sequence were continued with the greedy algorithm; then repeat with the sequence $b_1, b_2, \ldots , b_n, b_{n+1}$. The program considered 20 candidate values in each step, and estimated the reciprocal sums with the terms up to 64000. Giving as input the first 13 terms of the Mian-Chowla sequence, I obtained the first 30 terms of $H$. I have experimented with a number of other starting sequences, without finding any other sequence with a reciprocal sum greater than $S_Z$. The most likely place to find a $B_2$-sequence $X$ achieving a reciprocal sum $S_X > S_H$, if it exists, is between the sequences having the first 27 terms in common with $H$, or with the Zhang sequence. \begin{thebibliography}{1} \bibitem{Levine} Eugene Levine, An extremal result for sum-free sequences, \emph{J. Number Theory} \textbf{12} (1980), 251--257. \bibitem{Guy} Richard K. Guy, \emph{Unsolved Problems in Number Theory}, 3rd ed., Springer, 2004. \bibitem{Taylor and Yovanof} H. Taylor and G. S. Yovanof, $B_2$-sequences and the distinct difference constant, \emph{Comput. Math. Appl.} \textbf{39} (2000), 37--42. \bibitem{Finch} Steven R. Finch, \emph{Mathematical Constants}, Cambridge University Press, 2003. \bibitem{Zhang} Zhenxiang Zhang, A $B_2$-sequence with larger reciprocal sum, \emph{Math. Comput.} \textbf{60} (1993), 835--839. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 05B10; Secondary 11Y55 \noindent \emph{Keywords:} Sidon sequence, distinct difference constant, Mian-Chowla sequence, Zhang sequence. \bigskip \hrule \bigskip \noindent (Concerned with sequence \seqnum{A005282}). \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received November 16 2014; revised version received February 26 2015. Published in {\it Journal of Integer Sequences}, May 17 2015. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}