An asymptotically exact additive completion

Imre Z. Ruzsa*

Mathematical Institute of the Hungarian Academy of Sciences, Budapest, Pf. 127, H–1364 Hungary.

1 Introduction

We call two sets A, B of positive integers additive complements, if their sum

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

contains all sufficiently large integers. A pair of additive complements obviously satisfies

A(x)B(x) ≥ x − K  (11)

with some constant K, where A(x) denotes the number of elements of A up to x. Disproving a conjecture of Hanani, Danzer [1] constructed sets satisfying

A(x)B(x) ∼ x.  (12)

For sets satisfying (2), Sárközy and Szemerédi [4] strengthened (11) to

A(x)B(x) − x → ∞.

The aim of this note is to show that (12) can happen for very simple sets.

Theorem.

Let a ≥ 3 be a positive integer and put

A = {a^{k} : k ≥ 0}.

There is a set B of positive integers which is an additive complement of A and satisfies (12).

* Supported by Hungarian National Foundation for Scientific Research, Grant No. 1901.

2 Modular and global completion

Definition 21. Let a, m be positive integers, a ≥ 2, (a, m) = 1, and let r be the order of a modulo m (the smallest number for which a^{r} ≡ 1(modm)). We say that m is a fissile modulus for a if there is a set {d_{1}, ..., d_{l}} of integers such that the sums

a^{i} + d_{j},  0 ≤ i < r, 1 ≤ j ≤ l  (21)

represent every residue modulo m exactly once. We call r the rank of this modulus.

This is a finite analogue of an exact additive complement. If such a set exists, we must have m = kl.

We shall connect this ‘modular’ additive completion with the ordinary one.

Lemma 22.

Suppose that there exists an infinite sequence m_{1}, m_{2}, ... of fissile moduli for a of ranks r_{1}, r_{2}, ... satisfying r_{i} → ∞ and r_{j+1}/r_{j} → 1. Then there is a set B of positive integers which is an additive complement of A and satisfies (22).

Proof. We are going to construct B in the form

B = ⋃_{k=1}^{∞} B_{k},

where the B_{k} are finite sets such that

A + B_{k} ⊃ (a^{k}, a^{k+1}].  (22)

Such a B is clearly an additive complement of A.

Fix an integer k, and let m be the fissile modulus with the largers rank r satisfying

a^{r−1} < a^{k}/k^{2}.

(Observe that m = 1, r = 1 is always a possibility.) We preserve the notations of the definition. We define

B_{k} = {b : a^{k} − a^{k}/k^{2} < b ≤ a^{k+1}, b ≡ d_{j}(modm) for some1 ≤ j ≤ l}.

First we show (22). Consider an integer a^{k} < n ≤ a^{k+1}. By definition we can find 0 ≤ i < r, 1 ≤ j ≤ l such that

n ≡ a^{i} + d_{j}(modm).

The number b = n − a^{i} satisfies b ≡ d_{j} and also

b ≤ n ≤ a^{k+1}, b ≥ n − a^{r−1} > a^{k} − a^{k}/k^{2},

hence indeed b ∈ B_{k}.

Next we estimate |B_{k}|. Observe that r is the largest rank of a fissile modulus below log(a^{k}/k^{2}) / log a. Since the quotient of consecutive terms of the sequence r_{k} tends to 1, we have

r ∼ \frac{log(a^{k}/k^{2})}{log a} ∼ k.

We also know by definition that m|a^{r} − 1, hence

m < a^{r} < a^{k+1}/k^{2}.

The set B_{k} is the union of l = m/r residue classes modulo m, consequently

|B_{k}| = l (\frac{a^{k+1} − (a^{k} − a^{k}/k^{2})}{m} + O(1)) = \frac{(a − 1)a^{k}}{r} + O(a^{k}/k^{2}) ∼ \frac{(a − 1)a^{k}}{k} .

Now we estimate B(x). Let a^{k} < x ≤ a^{k+1}. The set B ⋂[1, x] contains B_{1}, ..., B_{k−1}, a part (possibly the whole) of B_{k} end possibly a part of B_{k+1}. From the previous estimate we deduce

|B_{1}| + ... + |B_{k−1}| ∼ \frac{a^{k}}{k} .

B_{k} is the union of l residue classes modulo m, hence

|B_{k} ∩ [1, x]| = |B_{k} ∩ [a^{k} − a^{k}/k^{2}, x]|

≤ l (\frac{x − (a^{k} − a^{k}/k^{2})}{m} + 2)

= \frac{x − a^{k}}{r} + o(x/k) = \frac{x − a^{k}}{k} + o(x/k).

Finally, since B_{k+1} consists exclusively of numbers ≥ a^{k+1} − a^{k+1}/(k + 1)^{2}, there are at most a^{k+1}/(k + 1)^{2} = o(x/k) elements in B_{k+1} ∩ [1, x]. Summing up we find

B(x) ≤ \frac{x}{k} + o(x/k) = log a\frac{x}{log x} + o (\frac{x}{log x}) .

This and the lower estimate given by (1.1) yield (1.2).

3 Finding fissile moduli

In this section we construct fissile moduli for any a > 2. Since a fissile modulus m of rank r satisfies r|m|a^{r} − 1 and the divisibility r|2^{r} − 1 is well known to be impossible for r > 1, there is no nontrivial fissile modulus for 2.

Lemma 31. Let p be a prime, a a positive integer, and let s be the exponent of p in a − 1.

Assume s ≥ 1, and if p = 2, then assume s ≥ 2. The exponent of p in a^{p} − 1 is s + 1.

Proof. Write

a = 1 + tp^{s}, p |̸ t.

By the binomial theorem we have

a^{p} = 1 + tp^{s+1} + \frac{p − 1}{2}t^{2}p^{2s+1} + T p^{3s}

with some integer T. Hence

\frac{a^{p} − 1}{p^{s+1}} = t + p (\frac{(p − 1)p^{s−1}}{2} t^{2} + T p^{2s−2})

is an integer but not a multiple of p.

Lemma 32. Assume a ≥ 2, p|a−1 and define s by p^{s+1}∥a^{p} −1. For every integer u ≥ 1 we have

p^{s+u}∥a^{p^{u}} − 1.

Proof. This follows from the previous lemma by an easy induction.

Remark. This s is the exponent of p in a − 1 if p is odd, and it is 1 + the highest of the exponents of 2 in a − 1 and a + 1 for p = 2.

Lemma 33. Assume a ≥ 2, p|a − 1 and define s by p^{s+1}∥a^{p} − 1. The order of a modulo p^{s+u} is

p^{u} for every u ≥ 1, and also for u = 0 if p is odd.

Proof. Immediate consequence of the previous lemmas.

Lemma 34.

Let p, a be as in the previous lemmas. There is an odd prime q ≠ p such that q|a^{p^{2}} − 1, q |̸ a^{p} − 1.

Proof. We have

a^{p^{2}} − 1 = (a^{p} − 1)(1 + a^{p} + ... + a^{(p−1)p}) = (a^{p} − 1)T.

We have

T ≡ p(moda^{p} − 1)  (31)

because each term is ≡ 1. Since p^{2}|a^{p} − 1, we conclude that the exponent of p in T is 1. We know T > a^{p} > p, so T must have a prime divisor q ≠ p. (31) shows that q |̸ a^{p} − 1. If p = 2, then q is odd by q ≠ p, and if p ≠ 2, then T is odd and hence so is q.

From now on we fix an a > 2, a prime p|a − 1 and another prime q satisfying the previous lemma. We define s as in Lemma 3.2, and let t be the exponent of q in a^{p^{2}} − 1.

Lemma 35.

Let u ≥ 2, v ≥ 0 be integers. The order of a modulo p^{s+u}q^{t+v} is r = p^{u}q^{v}.

Proof. The order of a modulo p^{s+u} is p^{u} by Lemma 3.3. The order modulo q is p^{2} by the definition of q. By applying the same lemma after substituting q, t and a^{p^{2}} in the place of p, s and a we obtain that the order modulo q^{t+v} is p^{2}q^{v}. The order modulo p^{s+u}q^{t+v} is the least common multiple of these orders.

Lemma 36.

If p is odd, then p^{s} is a fissile modulus of rank 1. If p = 2, then 2^{s+1} is a fissile modulus of rank 2.

Proof. The statement for odd p is an immediate consequence of the definitions. Consider p = 2. The order of a modulo 2^{s+1} is 2 by the definition of s. Let w be

the exponent of 2 in a − 1; we have 1 ≤ w ≤ s − 1. Let D be the set of numbers in the form

j + 2^{w+1}k, 0 ≤ j ≤ 2^{w} − 1, 0 ≤ k ≤ 2^{s−w} − 1.

This set has 2^{s} elements. It is sufficient to show that the residues of 2^{i} + d, i = 0 or 1, d ∈ D modulo 2^{s} are all distinct. Assume that

a^{i} + j + 2^{w+1}k ≡ a^{i′} + j′ + 2^{w+1}k′(mod2^{s+1}).  (32)

Since a^{i} ≡ 1(mod2^{w}) for every value of i, we conclude that j ≡ j′( mod 2^{w}), hence j = j′. Deleting j and j′ from (32) we conclude

a^{i} − a^{i′} ≡ 2^{w+1}(k′ − k)(mod2^{s+1}).

The right side is a multiple of 2^{w+1}, while the possible values of the left side are 0 and ±(a − 1), consequently i = i′. Finally we have 2^{w+1}(k′ − k) ≡ 0(mod2^{s+1}), that is, k ≡ k′(mod2^{s−w}) which yields k = k′ as wanted.

Lemma 37. Assume m|m′, and let r and r′ be the orders of a modulo m and m, resp. If

r′/r = m′/m and m is a fissile modulus, then so is m′.

Proof. Let d_{1}, ..., d_{l} be the numbers in the definition of a fissile modulus, l = m/r. We claim that the same numbers work for m′. We show that

a^{i} + d_{j}, 0 ≤ i ≤ r′ − 1, 1 ≤ j ≤ l

are all incongruent modulo m′. Assume the contrary, that is,

a^{i} + d_{j} ≡ a^{i′} + d_{j′}(modm′).

Indeed, considering this congruence modulo m we infer j = j′, and then we get a^{i} ≡ a^{i′}(modm′) which yields i = i′.

These are lr′ = (m/r)r′ = m′ incongruent numbers, thus they form a complete residue system.

Lemma 38. p^{s+u} is a fissile modulus of rank p^{u} for a for all u ≥ 1.

Proof. This is a consequence of previous three lemmas.

Lemma 39. The number m = p^{s+2}q^{t} is a fissile modulus of rank p^{2}.

Proof. We know that p^{s+2} is a fissile modulus of rank p^{2}; let d_{1}, ..., d_{l} be a complementing set for it, l = p^{s}. We claim that the following collection of p^{s}q^{t} numbers works for m:

d_{j} + p^{s+2}k, 1 ≤ j ≤ p^{s}, 0 ≤ k′q^{t} − 1.

We show that the numbers

a^{i} + d_{j} + p^{s+2}k, 0 ≤ i ≤ p^{2} − 1, 1 ≤ j ≤ p^{s}, 0 ≤ k ≤ q^{t} − 1

are all incongruent modulo m. Suppose the contrary. This means that

a^{i} + d_{j} + p^{s+2}k = a^{i′} + d_{j′} + p^{s+2}k′(modp^{s+2}q^{t}).

Taking the congruence modulo p^{s+2} we see that i = i′ and j = j′. Deleting these terms we obtain k ≡ k′(modq^{t}), hence also k = k′.

We proved that these sums form a complete residue system, and Lemma 3.5 implies that the order of a modulo p^{s+2}q^{t} is p^{2}.

Lemma 310. Let u ≥ 2, v ≥ 0 be integers. The number p^{s+u}q^{t+v} is a fissile modulus of rank

r = p^{u}q^{v}.

Proof. Follows from Lemmas 3.5, 3.7 and 3.9.

Proof of the Theorem. By Lemma 3.10, there is a fissile modulus of rank p^{u}q^{v} for every u ≥ 2, v ≠ 0. The quotient of consecutive terms of this sequence tends to 1 by the irrationality of (log p)/ log q. Now an application of Lemma 2.2 completes the proof.

4 Concluding remarks

An estimate for

B(x) − log a\frac{x}{log x}

could be given by applying a Baker-type estimate.

I cannot decide whether a complement satisfying (1.2) exists for the powers of 2. However, with the same method, using the primes 3 and 19, one can construct a set B satisfying

B(x) ∼ 2 log 2\frac{x}{log x}

such that every large integer n has at least two representations of the form 2^{k} +b, b ∈ B. An additive complement with the weaker property

A(x)B(x) = O(x)  (41)

was constructed for the powers of 2 in Ruzsa [2], and for any linear recurrence set in Ruzsa [3].

References

[1] Danzer, L., Über eine Frage von G. Hanani aus der additiven Zahlentheorie, J. Reine Angew. Math. 214/215(64), 392–394.

[2] Ruzsa, I., On a problem of P. Erdős, Canad. Math. Bull 15(72), 309–310.

[3] Ruzsa, I. Z., On the additive completion of linear recurrence sequences, Periodica Math. Hung. 9(78), 285–291.

[4] Sárközy, A., Szemerédi, E., On a problem in additive number theory, Acta Math. Acad. Sci. Hungar., to appear.