An antidemocratic representation

Imre Z. Ruzsa*

Mathematical Institute of the Hungarian Academy of Sciences, Budapest, Pf. 127, H–1364 Hungary. e-mail: ruzsa@math-inst.hu

1. Introduction

Let A be a set of positive integers and write

r(n) = #{(a, a′) : a, a′ ∈ A, a + a′ = n},
B = A + A = {n : r(n) ≥ 1}.

P. Erdős and A. Ivič asked whether it is possible to have d(B) = 0 and at the same time r(n) → ∞ when n is restricted to n ∈ B. We construct a class of such sets.

We write

A(x) = #(A ∩ [1, x])

and similarly for B.

Theorem 1.

There is a set A such that B(x) ≪ x^{1−α} while r(n) ≫ n^{β} for all n ∈ B with certain absolute constants α, β.

Obviously r(n) ≤ A(n) ≤ B(n)+O(1) for all n, thus we have necessarily α+β ≤ 1. I cannot decide whether β can be arbitrarily near to 1.

* Supported by Hungarian National Foundation for Scientific Research, Grant No. T 017433 Theorem 2.

If ω(x) → ∞ arbitrarily slowly, then there is a set A such that

A(x) ≪ B(x) ≪ (log x)^{ω(x)}

while r(n) → ∞ for n ∈ B.

I cannot decide whether A(x) ≪ (log x)^{O(1)} is possible for such a set.

The construction is described in the next section. The proof that these sequences have the desired properties is given in Section 3.

2. The construction

For a positive integer n let s(n) denote the number of 1’s in the binary representation of n.

Let t : ℕ → ℕ ∪ {0} be a nondecreasing function with the properties

t(k) ≤ \frac{3}{8}k, t(k + 1) ≤ 1 + t(k).

We consider, for each such function t, the set

A = A_{t} = {n : 2^{k} ≤ n < 2^{k+1} and s(n) ≤ t(k) for some k}.

The sets in Theorems 1 and 2 will be particular cases of this construction for suitable choices of the function t. In this section we establish a general property of these sequences.

Take an integer n, and define k by

2^{k} ≤ n < 2^{k+1}.  (2.1)

Develop n in base 2. Either n = 2^{k}, or we can write this development as

n = 2^{k} + 2^{l} + ∑_{i=0}^{l−1} ε_{i}2^{i}. (k > l)  (2.2)

Throughout this section k and l will denote the numbers determined by (2.1) and (2.2). Now put

T (n) = max(t(k) + t(l), 2t(k − 1) − 1).

For n = 2^{k}, we define T (n) = 2t(k − 1) − 1.

Theorem 3.

If n ∈ B, then s(n) ≤ T (n), and

r(n) ≥ c\frac{2^{(2/3)t(k)}}{\sqrt{t(k)}}  (2.3)

with a positive absolute constant c and k defined by (2.1) .

We shall need the following property of the function s.

Lemma 2.1.

For arbitrary positive integers m, n we have

s(m + n) ≤ s(m) + s(n),

with equality if there is no i such that the i’th digits in the binary representations of m and n are both equal to 1 and strict inequality otherwise.

We leave the simple proof to the reader.

Lemma 2.2. If n ∈ B, then

s(n) ≤ T (n).

Proof. We use representation (2.2). Assume n = a+a′, a, a′ ∈ A, a ≥ a′. If a ≥ 2^{k}, then a′ < 2^{l+1}, hence

s(a) ≤ t(k), s(a′) ≤ t(l),

and so

s(n) ≤ s(a) + s(a′) ≤ t(k) + t(l) ≤ T (n).

If a < 2^{k}, then

s(a) ≤ t(k − 1), s(a′) ≤ t(k − 1),

and there must be a common 1 in the representations of a and a′, since otherwise we could add them without carry and n = a + a′ would not contain 2^{k}. Consequently we have

s(n) ≤ s(a) + s(a′) − 1 ≤ 2t(k − 1) − 1 ≤ T (n).

If n = 2^{k}, then only the second case is possible and we get the result by the second argument.

From now on we fix the following notation: s(n) = s and

n = ∑_{i=1}^{s} 2^{u_{i}}, u_{1} > u_{2} > ... > u_{s}, u_{1} = k, u_{2} = l.  (2.4)

Lemma 2.3.

If 4 ≤ s ≤ T (n), then

r(n) ≥ \binom{s − 2}{[s/2] − 2} ≥ \frac{c2^{s}}{\sqrt{s}} .  (2.5)

Proof. First case: t(k) + t(l) ≥ 2t(k − 1) .

Here

t(l) ≥ 2t(k − 1) − t(k) ≥ t(k) − 2

and so

s ≤ t(k) + t(l) ≤ 2t(l) + 2.

Since s ≤ t(k) + t(l), we can find integers q and r such that s = q + r, q ≤ t(k), r ≤ t(l). Moreover, we can achieve

[\frac{s}{2} − 1] ≤ r ≤ [\frac{s}{2}] .

Indeed, if s ≥ 2t(l), then r = t(l), q = s − t(l) is such a choice, while if s < 2t(l), then r = [s/2], q = s − [s/2] works.

Now for each decomposition

{3, 4, ..., s} = X ∪ Y

into disjoint sets X, Y such that |X| = q − 1, |Y | = r − 1 we can set

a = 2^{k} + ∑_{i∈X} 2^{u_{i}}, a′ = 2^{l} + ∑_{i∈Y} 2^{u_{i}}.

This will be a valid decomposition of n, since s(a) = q ≤ t(k), s(a′) = r ≤ t(l). The number of such decompositions is

\binom{s − 2}{r − 1} ≥ \binom{s − 2}{[s/2] − 2}.

Second case: t(k) + t(l) ≤ 2t(k − 1) − 1 . Then also s ≤ 2t(k − 1) − 1. If we put now

r = [\frac{s − 1}{2}] , q = [\frac{s}{2}] ,

then we have r ≤ q ≤ t(k − 1) − 1 and r + q = s − 1.

Again we write n in the form (2.4). If we put

{2, 3, ..., s} = X ∪ Y

with disjoint sets X, Y such that |X| = q, |Y | = r, then the numbers

a = 2^{k−1} + ∑_{i∈X} 2^{u_{i}}, a′ = 2^{k−1} + ∑_{i∈Y} 2^{u_{i}}

satisfy s(a) ≤ q + 1 ≤ t(k − 1), s(a′) ≤ r + 1 ≤ t(k − 1) (if u_{2} = k − 1, then a carry may occur so strict inequality is possible), hence a, a′ ∈ A and a + a′ = n. The number of such decompositions is

\binom{s − 1}{r} = \binom{s − 1}{[(s − 1)/2]} > \binom{s − 2}{[s/2] − 2}.

Lemma 2.3 provides many representations for an n ∈ B if s is not too small. For small values of s we use a different method.

Consider the representations of n in the form

n = ∑_{i=0}^{k} δ_{i}2^{i},  (2.6)

with δ_{i} = 0, 1 or 2.

Lemma 2.4.

Suppose 3s < k. For every integer

0 ≤ p ≤ \frac{k − 3s}{4}  (2.7)

there is a representation of n in the form (2.6) such that the number of δ_{i} = 1 is s + p and the number of δ_{i} = 2 is at most p. Moreover, if k′ is the largest subscript such that δ_{k′} ≠ 0, then k′ = k or k − 1, δ_{k′} = 1 and δ_{k′−1} = 0 or 1.

Proof. We construct these representations recursively. The usual binary representation provides such a representation for p = 0.

Now we make changes to a given representation, in each step increasing the number of ones by one and the number of twos by at most one.

To achieve this, we do one of the following two operations.

If there is a substring 20 in the sequence δ_{k}, ..., δ_{0}, we change it into 12. This increases the number of ones by 1 and does not change the number of twos.

If there is a 1000, we change it into 0112. This increases both the number of ones and the number of twos by 1.

The property that the first two nonzero δ’s are 10 or 11 holds in the starting representation and it is preserved by these operations.

We repeat these steps as long as we can. Suppose that after p steps we stop. We have now s + p ones, ≤ p twos, and blocks of 0’s between them (and possibly a block of zeros before them). Since none of the described operations is possible, a block of 0’s (not in the initial position) can only follow a 1 and its length is at most 2, hence these give at most 2(s + p) zeros. Thus altogether we have at most

(s + p) + p + 2(s + p) = 3s + 4p

digits from δ_{k′} on. This means that

3s + 4p ≥ k′ + 1.

Since

n ≥ 2^{k} > ∑_{i=0}^{k−2} 2 · 2^{i} = 2^{k} − 2,

we have necessarily k′ ≥ k − 1 and we obtain

3s + 4p ≥ k,

hence the range in (2.7) is indeed covered.

Proof of Theorem 3. From Lemma 2.2 we know that s(n) ≤ T (n) is necessary for n ∈ B. Now we prove the lower estimation.

Write t = t(k). We may suppose that t ≥ 9, otherwise the theorem is obvious. If s > (2/3)t − 2, we apply Lemma 2.3. Assume now s ≤ (2/3)t − 2. We use Lemma 2.4 with

p = [\frac{2}{3}t] − s − 2.

The condition p ≤ (k − 3s)/4 follows from the assumption t ≤ (3/8)k.

Take representation (2.6), where there are s + p = [(2/3)t] − 2 ones and at most p twos. Let k′ be the largest subscript with δ_{i} ≠ 0; we know that k′ = k or k − 1. Let U be the set of those i’s that satisfy i ≤ k′ − 2 and δ_{i} = 1; we have |U| ≤ s + p − 1 and

|U| ≥ s + p − 2 = [\frac{2}{3}t] − 4.

Now let U = X ∪ Y be a decomposition of U into sets of size

|X| = [\frac{|U|}{2}] , |Y | = [\frac{|U| + 1}{2}] .

The number of such decompositions is

\binom{|U|}{[|U|/2]} ≫ \frac{2^{|U|}}{\sqrt{|U|}} ≫ \frac{2^{(2/3)t}}{\sqrt{t}} .

Each of these decompositions induces a representation n = a + a′, namely

a = 2^{m} + ∑_{i∈X} 2^{i} + ∑_{δ_{i}=2} 2^{i},

a′ = 2^{m′} + ∑_{i∈Y} 2^{i} + ∑_{δ_{i}=2} 2^{i},

where m and m′ are defined as follows. If δ_{k′−1} = 0, then m = m′ = k′ − 1; if δ_{k′−1} = 1, then m = k′, m′ = k′ − 1. We have to show that a, a′ ∈ A. To this end observe that

s(a) ≤ s(a′) ≤ 1 + p + |Y | ≤ 1 + p + \frac{s + p}{2} ≤ t − s − 1.

Moreover a, a′ ≥ 2^{k′−1} ≥ 2^{k−2} and t(k − 2) ≥ t − 2 ≥ t − s − 1 which shows that a, a′ ∈ A.

3. Proof of Theorems 1 and 2

Proof of Theorem 1.

We take a 0 < γ < 1/4 and put t(k) = [γk]. Then for n ≤ x and n ∈ B we have s(n) ≤ 2γk with k = [log_{2} x]. Thus we have

B(x) ≤ ∑_{i≤2γk} \binom{k + 1}{i} ≪ 2^{(1−α)k} ≪ x^{1−α}

for any

α < 1 + 2γ log_{2} 2γ + (1 − 2γ) log_{2}(1 − 2γ)

(this follows by Stirling’s formula and a routine calculation). Moreover for an n ∈ B we know

r(n) ≫ 2^{(2γ/3)k}/\sqrt{k} ≫ n^{β}

with any β < 2γ/3.

With this method we can achieve β = 1/6 − ε. If γ passes 1/4, then the “typical” numbers with approximately k/2 digits will be in B, thus we have d(B) = 1.

Proof of Theorem 2. If t(k) → ∞, then r(n) → ∞ for n ∈ B by Theorem 3. On the other hand, if n ≤ x and n ∈ B, then n is the sum of at most 2t(k) powers of 2 with k = [log_{2} x]. Hence

B(x) ≤ ∑_{i=0}^{2t(k)}(k + 1)^{i} ≪ t(k)(k + 1)^{2t(k)},

and this will be O((log x)^{ω(x)}) if t(k) tends to infinity sufficiently slowly.

Printed 1999.2.28.