Unique Difference Bases of ℤ

Chi-Wu Tang, Min Tang,^{1} and Lei Wu Department of Mathematics Anhui Normal University Wuhu 241000 P. R. China

                   tmzzz2000@163.com

Abstract

For n ∈ ℤ, A ⊂ ℤ, let δ_{A}(n) denote the number of representations of n in the form n = a − a′, where a, a′ ∈ A. A set A ⊂ ℤ is called a unique difference basis of ℤ if δ_{A}(n) = 1 for all n ≠ 0 in ℤ. In this paper, we prove that there exists a unique difference basis of ℤ whose growth is logarithmic. These results show that the analogue of the Erdős-Turán conjecture fails to hold in (ℤ, −).

1 Introduction

For sets A and B of integers and for any integer c, we define the set

A − B = {a − b : a ∈ A, b ∈ B},

and the translations

A − c = {a − c : a ∈ A},
c − A = {c − a : a ∈ A}.

The counting function for the set A is

A(y, x) = card{a ∈ A : y ≤ a ≤ x}.

For n ∈ ℤ, we write

δ_{A}(n) = card{(a, a′) ∈ A × A : a − a′ = n},

1 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.

σ_{A}(n) = card{(a, a′) ∈ A × A : a + a′ = n}.

We call A ⊂ ℤ a difference basis of ℤ if δ_{A}(n) ≥ 1 for all n ∈ ℤ, and a unique difference basis of ℤ if δ_{A}(n) = 1 for all n ≠ 0 in ℤ. We call A a subset of ℕ an additive asymptotic basis of ℕ if there is n_{0} = n_{0}(A) such that σ_{A}(n) ≥ 1 for all n ≥ n_{0}. The celebrated Erdős-Turán conjecture [1] states that if A ⊂ ℕ is an additive asymptotic basis of ℕ, then the representation function σ_{A}(n) must be unbounded. In 1990, Ruzsa [5] constructed a basis of A ⊂ ℕ for which σ_{A}(n) is bounded in the square mean. Pŭs [4] first established that the analogue of the Erdős-Turán conjecture fails to hold in some abelian groups. Nathanson [3] constructed a family of arbitrarily sparse unique additive representation bases for ℤ. In 2004, Haddad and Helou [2] showed that the analogue of the Erdős-Turá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 ≠ 2 and G the additive group of K × K. Recently, Chi-Wu Tang and Min Tang [6] proved there exists a set B ⊂ G such that 1 ≤ δ_{B}(g) ≤ 14 for all g ≠ 0.

It is natural to consider the analogue of the Erdős-Turán conjecture in (ℤ, −). In this paper, we obtain the following results.

Theorem 1. There exists a family of unique difference bases of ℤ.

Theorem 2. There exists a unique difference basis A of ℤ such that

\frac{2 log(3x + 3)}{log 3} − \frac{2 log 5}{log 3} < A(0, x) ≤ \frac{2 log(x + 3)}{log 2} − 2 for all x ≥ 1.

2 Proof of Theorem 1.

We shall construct an ascending sequence A_{1} ⊆ A_{2} ⊆ ⋯ of finite sets of nonnegative integers such that

|A_{k}| = 2k, for all k ≥ 1,
δ_{A_{k}}(n) ≤ 1, for all n ≠ 0.

We shall prove that the infinite set

A = ⋃_{k=1}^{∞} A_{k}

is a unique difference basis of ℤ.

We construct the sets A_{k} by induction. Let A_{1} = {0, 1}. We assume that for some k ≥ 1 we have constructed sets A_{1} ⊆ ⋯ ⊆ A_{k} such that |A_{i}| = 2i and δ_{A_{i}}(n) ≤ 1 for all 1 ⩽ i ⩽ k and all integers n ≠ 0. We define the integers

d_{k} = max{a : a ∈ A_{k}},
b_{k} = min{|b| : b ∉ 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} ∪ {2c_{k}, b_{k} + 2c_{k}}.

Then |A_{k+1}| = 2k + 2 = 2(k + 1) for all k ≥ 1, and A_{k} ⊆ [0, d_{k}], A_{k} − A_{k} ⊆ [−d_{k}, d_{k}].

Note that

A_{k+1} − A_{k+1} = (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}}.  (1)

We shall show that A_{k+1} − A_{k+1} is the disjoint union of the above six sets. If u ∈ A_{k} − A_{k}, then

−d_{k} ≤ u ≤ d_{k}.  (2)

If v_{1} ∈ A_{k} − (b_{k} + 2c_{k}) and v_{2} ∈ (b_{k} + 2c_{k}) − A_{k}, then there exist a, a′ ∈ A_{k} such that v_{1} = a − (b_{k} + 2c_{k}) and v_{2} = (b_{k} + 2c_{k}) − a′. Since 0 ≤ a, a′ ≤ d_{k}, we have

−b_{k} − 2c_{k} ≤ v_{1} ≤ −b_{k} − 2c_{k} + d_{k},  (3)
b_{k} + 2c_{k} − d_{k} ≤ v_{2} ≤ b_{k} + 2c_{k}.  (4)

If w_{1} ∈ A_{k} − 2c_{k} and w_{2} ∈ 2c_{k} − A_{k}, similarly, we have

−2c_{k} ≤ w_{1} ≤ −2c_{k} + d_{k},  (5)
2c_{k} − d_{k} ≤ w_{2} ≤ 2c_{k}.  (6)

For any n ∈ ℤ, if n ∈ A_{k} − A_{k}, then −n ∈ A_{k} − A_{k}, thus by the definition of b_{k}, we have

b_{k} ∉ A_{k} − A_{k} and − b_{k} ∉ A_{k} − A_{k}.  (7)

Assume (2c_{k} −A_{k})∩((b_{k} +2c_{k})−A_{k}) ≠ ∅, then there exist a, a′ ∈ A_{k} such that b_{k} +2c_{k} −a = 2c_{k} − a′, b_{k} = a − a′ ∈ A_{k} − A_{k} which contradicts with the fact b_{k} ∉ A_{k} − A_{k}. Similarly, we have (A_{k} − (b_{k} + 2c_{k})) ∩ (A_{k} − 2c_{k}) = ∅.

Moreover, we have d_{k} ∈ A_{k} − A_{k}, hence b_{k} ≠ d_{k}. If b_{k} < d_{k}, it is easy to see that the set {−b_{k}, b_{k}} is disjoint with the other five sets. If b_{k} > d_{k}, since d_{k} ∈ A_{k} − A_{k} and by the definition of b_{k}, we have b_{k} = d_{k} + 1. Then 2c_{k} − d_{k} ⩾ 2(d_{k} + 1) − d_{k} = d_{k} + 2 > b_{k} and −2c_{k} + d_{k} ⩽ −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, δ_{A_{k+1}}(n) ≤ 1 for all integers n ≠ 0.

Let A = ⋃_{k=1}^{∞} A_{k}. Then for all k ≥ 1, by (7) and the definition of b_{k}, we have

{−b_{k} + 1, −b_{k} + 2, ⋯, −1, 1, ⋯, b_{k} − 2, b_{k} − 1} ⊂ A_{k} − A_{k} ⊂ A − A,

and the sequence {b_{k}}_{k⩾1} is strictly increasing, since A_{k} − A_{k} ⊂ A_{k+1} − A_{k+1} and ±b_{k} ∈ A_{k+1} − A_{k+1} but ±b_{k} ∉ A_{k} − A_{k}. Thus A is a difference basis of ℤ. If δ_{A}(n) ≥ 2 for some n, then by construction, δ_{A_{k}}(n) ≥ 2 for some k, which is impossible. Therefore, A is a unique difference basis of ℤ.

It completes the proof of Theorem 1.

3 Proof of Theorem 2.

We apply the method of Theorem 1 with

c_{k} = d_{k} + 1 for all k ≥ 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}, 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}, 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} ∪ (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 ≥ d_{1} and k is the unique integer such that d_{k} ≤ x < d_{k+1}, by the construction of A, we know A_{k} = |2k| and A_{k+1} = A_{k} ∪ {2c_{k}, 2c_{k} + b_{k}}, then

A(0, x) = A_{k+1}(0, x) = \begin{cases}2k, & if d_{k} ≤ x < 2c_{k}, \\ 2k + 1, & if 2c_{k} ≤ x < 2c_{k} + b_{k} = d_{k+1}. \end{cases}

For k ≥ 1, we have 1 < b_{k} ≤ d_{k} + 1 = c_{k} and c_{k+1} = d_{k+1} + 1 = 2c_{k} + b_{k} + 1, hence

2c_{k} + 2 < c_{k+1} ≤ 3c_{k} + 1.

Since c_{1} = d_{1} + 1 = 2, it follows by induction on k that

2^{k+1} − 2 ≤ c_{k} ≤ \frac{5}{2} · 3^{k−1} − \frac{1}{2},

and so

\frac{log \frac{6}{5}(c_{k} + \frac{1}{2})}{log 3} ≤ k ≤ \frac{log \frac{c_{k} + 2}{2}}{log 2} for all k ≥ 1.

We obtain an upper bound for A(0, x) as follows. If d_{k} ≤ x < 2c_{k}, then c_{k} ≤ x + 1, and

A(0, x) = A_{k+1}(0, x) = 2k ≤ 2\frac{log \frac{c_{k} + 2}{2}}{log 2} = \frac{2 log(c_{k} + 2)}{log 2} − 2 ≤ \frac{2 log(x + 3)}{log 2} − 2.

If 2c_{k} ≤ x < d_{k+1}, then c_{k} ≤ \frac{x}{2}, and

A(0, x) = A_{k+1}(0, x) = 2k + 1 ≤ \frac{2 log \frac{c_{k} + 2}{2}}{log 2} + 1 ≤ \frac{2 log (\frac{x}{4} + 1)}{log 2} + 1 = \frac{2 log(x + 4)}{log 2} − 3.

Therefore,

A(0, x) ≤ \frac{2 log(x + 3)}{log 2} − 2 for all x ≥ 1.

Similarly, we obtain a lower bound for A(0, x). If d_{k} ≤ x < 2c_{k}, then

A(0, x) = 2k ≥ \frac{2 log \frac{6}{5}(c_{k} + \frac{1}{2})}{log 3} > \frac{2 log \frac{3}{5}(x + 1)}{log 3} = \frac{2 log(3x + 3)}{log 3} − \frac{2 log 5}{log 3}.

If 2c_{k} ≤ x < d_{k+1}, then d_{k+1} = b_{k} + 2c_{k} ≤ 3c_{k}. So c_{k} ≥ \frac{1}{3}d_{k+1} > \frac{1}{3}x and

A(0, x) = 2k + 1 ≥ \frac{2 log \frac{6}{5}(c_{k} + \frac{1}{2})}{log 3} + 1 > \frac{2 log \frac{6}{5}(\frac{x}{3} + \frac{1}{2})}{log 3} + 1 = \frac{2 log(2x + 3)}{log 3} + 1 − \frac{2 log 5}{log 3}.

Therefore,

A(0, x) > \frac{2 log(3x + 3)}{log 3} − \frac{2 log 5}{log 3} for all x ≥ 1.

This completes the proof of Theorem 2.

4 Acknowledgements

We would like to thank the referee for his/her many helpful suggestions.

References

[1] P. Erdős and P. Turán, On a problem of Sidon in additive number theory, and on some related problems, J. London Math. Soc. 16 (1941), 212–215.

[2] L. Haddad and C. Helou, Bases in some additive groups and the Erdős-Turán conjecture, J. Combin. Theory Series A 108 (2004), 147–153.

[3] M. B. Nathanson, Unique representation bases for integers, Acta Arith. 108 (2003), 1–8.

[4] V. Pǔs, On multiplicative bases in abelian groups, Czech. Math. J. 41 (1991), 282–287.

[5] I. Z. Ruzsa, A just basis, Monatsh. Math 109 (1990), 145–151.

[6] Chi-Wu Tang and Min Tang, Note on a result of Haddad and Helou, Integers 10 (2010),

   229–232. Available electronically at http://integers-ejcnt.org/vol10.html.

2000 Mathematics Subject Classification: Primary 11B13; Secondary 11B34. Keywords: Erdős-Turán conjecture; difference bases; counting function.

Received October 12 2010; revised version received January 26 2011. Published in Journal of Integer Sequences, February 9 2011.

Return to Journal of Integer Sequences home page.