A New Lower Bound for the Distinct Distance Constant

Raffaele Salvia

                    raffaelesalvia@alice.it

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.

1 Introduction

A Sidon sequence, also called a B_{2}-sequence, is a sequence of positive integers

a_{1} < a_{2} < a_{3} < …

such that all the sums a_{i} + a_{j} (i ≤ j) are distinct.

The distinct distance constant (DDC) is the supremum of the set of the reciprocal sums of Sidon sequences. Levine [1] observed that

DDC ≤ ∑_{n=0}^{∞} \frac{1}{1 + \frac{n(n+1)}{2}} = \frac{2π}{\sqrt{7}} tanh (\frac{\sqrt{7}}{2}π) < 2.37366 .  (1)

Let S_{A} be the reciprocal sum of the sequence A; that is, S_{A} = ∑_{i=1}^{∞} \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 [2, p. 351]. We only know from Taylor and Yovanof [3] 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, … }. The sequence G is named the Mian-Chowla sequence. Lewis found that

2.158435 ≤ S_{G} ≤ 2.158677 ,  (2)

where S_{G} is the reciprocal sum of G [4, pp. 164–165].

In 1991, Zhang [5] 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

S_{Z} > 2.1597 .  (3)

The aim of this note is to exhibit a Sidon sequence H such that S_{H} > S_{Z}.

2 Computation of reciprocal sums

2.1 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 ≥ j) are all distinct. That is,

a_{i} ≥ a_{j} + (i − j), i ≥ j  (4)

a_{i} > \frac{i(i − 1)}{2} .  (5)

Therefore, if we know the values of a_{n} for 1 ≤ n ≤ k, we also know that

∑_{n=1}^{k} \frac{1}{a_{n}} < S_{A} < ∑_{n=1}^{k} \frac{1}{a_{n}} + ∑_{n=k}^{∞} \frac{1}{max (a_{k} + n − k, \frac{n(n−1)}{2})} .  (6)

Further assumptions could be made on a_{i}, but for large values of k they would not yield a significant improvement of the bounds.

2.2 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 ≤ n ≤ 25000, computed on my notebook, are listed in the accompanying file MianChowla.txt. We get the following bounds for S_{G}:

∑_{n=1}^{25000} \frac{1}{g_{n}} < S_{G} < ∑_{n=1}^{25000} \frac{1}{g_{n}} + ∑_{n=25001}^{510096} \frac{1}{g_{25000} + n − 25000} + ∑_{n=510097}^{∞} \frac{2}{n(n − 1)} ,  (7)

i.e.,

2.15845268 < S_{G} < 2.15846062 .  (8)

2.3 The reciprocal sum of the Zhang sequence

The Zhang sequence Z [5] is, at the moment, the known Sidon sequence with the largest reciprocal sum. In the accompanying file Zhang.txt there are the first 25000 terms of Z. Their values allow us to compute the following bounds for S_{Z}:

∑_{n=1}^{25000} \frac{1}{z_{n}} < S_{Z} < ∑_{n=1}^{25000} \frac{1}{z_{n}} + ∑_{n=25001}^{510290} \frac{1}{z_{25000} + n − 25000} + ∑_{n=510291}^{∞} \frac{2}{n(n − 1)}  (9)

S_{G} < 2.16007769 < S_{Z} < 2.16008532 .  (10)

2.4 The sequence H and its reciprocal sum

Definition 1.

h_{n} = \begin{cases}1, & if n = 1; \\ 229, & if n = 15; \\ 962, & if n = 27; \\ min\{x|∀i, j, k ≤ n, a_{i} + a_{j} ≠ a_{k} + x\}, & otherwise. \end{cases}

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 ≤ n ≤ 25000) in the accompanying file H.txt. Hence we get

∑_{n=1}^{25000} \frac{1}{h_{n}} < S_{H} < ∑_{n=1}^{25000} \frac{1}{h_{n}} + ∑_{n=25001}^{510140} \frac{1}{h_{25000} + n − 25000} + ∑_{n=510141}^{∞} \frac{2}{n(n − 1)}  (11)

2.16027651 < S_{H} < 2.16028417 .  (12)

In conclusion,

S_{Z} < 2.16027651 < S_{H} ≤ DDC ,  (13)

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}, …, 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}, …, 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.

References

[1] Eugene Levine, An extremal result for sum-free sequences, J. Number Theory 12 (1980), 251–257.

[2] Richard K. Guy, Unsolved Problems in Number Theory, 3rd ed., Springer, 2004.

[3] H. Taylor and G. S. Yovanof, B_{2}-sequences and the distinct difference constant, Comput. Math. Appl. 39 (2000), 37–42.

[4] Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003.

[5] Zhenxiang Zhang, A B_{2}-sequence with larger reciprocal sum, Math. Comput. 60 (1993), 835–839.

2010 Mathematics Subject Classification: Primary 05B10; Secondary 11Y55 Keywords: Sidon sequence, distinct difference constant, Mian-Chowla sequence, Zhang sequence.

(Concerned with sequence \underline{A005282}).

Received November 16 2014; revised version received February 26 2015. Published in Journal of Integer Sequences, May 17 2015.

Return to Journal of Integer Sequences home page.