Additive completion and disjoint translations

Laurent Habsieger

Laboratoire d’Algorithmique Arithmetique, CNRS UMR 9936, Université de Bordeaux 1, 351 cours de la Libération, F-33405 Talence Cedex

Imre Z. Ruzsa *

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

Abstract.

Let P be a polynomial of degree k ≥ 2 with nonnegative integer coefficients and let N be a positive integer. Let B be a set of nonnegative integers from [0, N] such that the sets P (λ) + B (0 ≤ P (λ) ≤ N) are disjoint sets. We show that | B | P^{−1}(N) ≤ ((1 − \frac{1}{k} )^{−1} \frac{sin(π/k)}{π/k} + o(1)) N. We also give examples of such sets when P is an odd monomial. We investigate the connection of this problem with the classical problem of additive completion.

1. Introduction

Let A ⊂ [0, N] be a nonempty set of integers. We define the covering number L of A as

L = min{|B| : B ⊂ ℤ, A + B ⊃ {0, 1, ..., N}}.

(The implicit dependence on N is not indicated.) Such a set B is called an additive complement of A. Bounds for L for arithmetically important sets were given in numerous papers. Obviously L ≥ (N + 1)/|A|. For the classical results on additive completion see Halberstam-Roth [3].

* This research was done while the author was visiting the Laboratoire de Mathématiques Discretes, Université de Marseille (Luminy), and Université de Bordeaux I; their support is gratefully acknowledged.

Let now P be a polynomial of degree d ≥ 2, with integral coefficients and positive leading coefficient, and consider (for varying N) the sets

A = A_{N} = {P (n) : n ∈ ℕ, 0 ≤ P (n) ≤ N}.  (1.1)

The best known lower bound of L for these sets is due to Cilleruelo [1] (where only P (n) = n^{k} is considered, and the formulation is slightly different) and Habsieger [2] and it sounds as follows.

Theorem 1.

For a polynomial set (1.1) we have (for a fixed polynomial P and N → ∞)

L ≥ (1 + o(1))s(1/d)\frac{N}{|A|},

where

s(t) = \frac{sin πt}{πt(1 − t)} = 1 + t + (1 − \frac{π^{2}}{6} )t^{2} + ...

Here we consider the covering number together with a “dual” problem. We define the disjoint translation number D as

D = sup{|B| : B ⊂ [0, N] ∩ ℤ, A + b_{1} ∩ A + b_{2} = ∅ for all b_{1}, b_{2} ∈ B, b_{1} ≠ b_{2}}.

With r(n) = #{(a, b) : a ∈ A, b ∈ B, a + b = n}, D is defined by the requirement r(n) ≤ 1 and L by r(n) ≥ 1 for 0 ≤ n ≤ N. By an obvious counting argument we have D ≤ (2N + 1)/|A|. For polynomial sets we have an improvement, similar to Theorem 1.

Theorem 2.

For a polynomial set (1.1) we have (for a fixed polynomial P and N → ∞)

D ≤ (1 + o(1))s(1/d)\frac{N}{|A|}.

The similarity of the bounds suggests that there is a closer connection between L and D than this formal analogy; this will be explored in the next section.

For certain polynomials the bound of Theorem 2 is rather tight.

Theorem 3.

Let P (x) = x^{d} with an odd integer d ≥ 3. We have

D ≥ (1 + o(1))\frac{N}{|A|}.

We can prove a somewhat weaker bound for even powers. For a general polynomial we cannot decide whether D ≫ N/|A| holds.

2. Generalizations

We define the fractional covering number as follows:

Λ = min ∑_{k=−N}^{N} λ_{k},

where the numbers λ_{k} are subject to the conditions λ_{k} ≥ 0 and

∑_{a∈A} λ_{n−a} ≥ 1

for all 0 ≤ n ≤ N. With the additional restriction λ_{k} = 0 or 1 we get the definition of L.

We define a fractional analog of D similarly:

Δ = max ∑_{k=0}^{N} δ_{k},

where δ_{k} ≥ 0 and

∑_{a∈A,n−N≤a≤n} δ_{n−a} ≤ 1

for all 0 ≤ n ≤ 2N. Again, imposing δ_{k} = 0 or 1 we get D.

The quantities L, D, Λ, Δ are connected in the following way.

Theorem 4.

We have always

D ≤ Δ = Λ ≤ L.

Proof. The inequalities are obvious. To prove the middle equality, consider the matrix (α_{ij}), 0 ≤ i ≤ 2N, 0 ≤ j ≤ N with the entries

α_{ij} = \{ \begin{matrix}1 & if i − j ∈ A, \\ 0 & otherwise. \end{matrix}

Δ is the maximum of ∑_{j=0}^{N} y_{j} under the constraints y_{j} ≥ 0,

∑_{j=0}^{N} α_{ij}y_{j} ≤ 1 (i = 0, ..., 2N).

A familiar result on linear duality yields that this is the same as the minimum of ∑_{i=0}^{2N} x_{i} under the assumptions x_{i} ≥ 0,

∑_{i=0}^{2N} α_{ij}x_{i} ≥ 1 (i = 0, ..., N).

This reduces to the definition of Λ with the transformation λ_{k} = x_{N−k}.

In the light of this result, Theorems 1 and 2 have the following common generalization.

Theorem 5.

For a polynomial set (1.1) we have (for a fixed polynomial P and N → ∞)

Λ = (1 + o(1))s(1/d)\frac{N}{|A|}.

We shall determine the asymptotic behaviour of Δ for a wider class of sequences. Let A be an infinite set of nonnegative integers. We use the same letter A to denote its counting function, so that

A(x) = #{a ∈ A, a ≤ x}.

Let Λ_{N} denote the fractional covering number of the set A∩[0, N] for the interval [0, N].

Theorem 6.

Suppose that with some α ∈ (0, 1) we have A(tN)/A(N) → t^{α} for all t ∈ [0, 1] as N → ∞. Then we have

Λ_{N} = (1 + o(1))s(α)\frac{N}{A(N)}.

We prove this result in the next section. It implies Theorems 1, 2, 5.

3. Proof of Theorem 6.

As a motivation for the following argument, we mention the continuous analog of the problem, which concerns the convolution

h(t) = f ∗ g(t) = ∫ f(x)g(t − x)dx.

In the first case, we want to have h(t) ≥ 1 for 0 ≤ t ≤ 1 and minimize ∫ g; in the second case we want h(t) ≤ 1, g(t) = 0 for t ∉ [0, 1] and maximize ∫ g (and we assume g ≥ 0 in both cases). Now for the function

f(x) = αx^{α−1} for x ∈ [0, 1], 0 otherwise

which is the density corresponding to distribution x^{α}, not only the results are equal but there is a common g that solves both problems, namely

g(t) = s(α)(1 − α)t^{−α}.

Indeed, a change of variable yields

∫_{0}^{t} x^{α−1}(t − x)^{−α} dx = ∫_{0}^{1} y^{α−1}(1 − y)^{−α} dy = \frac{π}{sin πα}.  (3.1)

Now we start the proof. Take an ε > 0. We shall find an N_{0} such that

(1 − ε)s(α)\frac{N}{A(N)} < Λ_{N} < (1 + ε)s(α)\frac{N}{A(N)}  (3.2)

for N > N_{0}.

For 0 ≤ x ≤ N, write

A(x) = (x/N)^{α}A(N) + R_{N}(x), R_{N} = max |R(x, N)|.

The convergence of A(tN)/A(N) to t^{α}, as any convergence of monotonic functions to a continuous monotonic function, must be uniform, that is, R_{N} = o(A(N)) as N → ∞.

First we construct nonnegative reals λ_{n} such that

∑_{a} λ_{n−a} ≥ 1  (3.3)

for all n, while ∑ λ_{n} ≤ (1 + ε)s(α)N/A(N). To this end we select a number η > 0, depending on ε (this dependence will be made explicit later). We set ϱ = η(1 − η) and define

λ_{n} = β(n + ηN)^{−α}, −ϱN ≤ n ≤ N,

where

β = (1 + ε/2)s(α)(1 − α)\frac{N^{α}}{A(N)}.

Since

∑_{−ϱN}^{N}(n+ηN)^{−α} < ∫_{−ϱN−1}^{N}(t+ηN)^{−α} dt < ∫_{−ηN}^{N}(t+ηN)^{−α} dt = \frac{1}{1 − α}N^{1−α}(1+η)^{1−α},

we have

∑ λ_{n} < (1 + ε/2)(1 + η)^{1−α}s(α)\frac{N}{A(N)} < (1 + ε)s(α)\frac{N}{A(N)}

if η is so small that

(1 + ε/2)(1 + η)^{1−α} < 1 + ε.  (3.4)

Now we prove (3.3). We have

∑ λ_{n−a} = β ∑_{0≤a≤min(N,n+ϱN)}(n + ηN − a)^{−α} ≥ β ∑_{0≤a≤M}(n + ηN − a)^{−α},

where

M = (n + ηN)(1 − η) ≤ min(N, n + ϱN)

will be more comfortable for the following computations.

We turn this sum into a Stieltjes integral to obtain

\begin{matrix}β ∑_{0≤a≤M}(n + ηN − a)^{−α} = β ∫_{0−}^{M}(n + ηN − t)^{−α} dA(t) \\ = & βA(N)N^{−α} ∫_{0}^{M}(n + ηN − t)^{−α} dt^{α} + β ∫_{0−}^{M}(n + ηN − t)^{−α} dR_{N}(t). \end{matrix}

After a change of variable t = (n + ηN)u, the main term becomes

βA(N)N^{−α}α ∫_{0}^{1−η} u^{α−1}(1 − u)^{−α} du > 1 + ε/3,

if η is so small that

∫_{0}^{1−η} u^{α−1}(1 − u)^{−α} du > \frac{1 + ε/3}{1 + ε/2} \frac{π}{sin πα}.

(We remind that π/ sin πα is the value of the integral from 0 to 1, as mentioned in (3.1).)

We use integration by parts to estimate the remainder term.

|β ∫_{0−}^{M}(n + ηN − t)^{−α} dR_{N}(t)|

= β |R_{N}(M)(n + ηN − M)^{−α} + α ∫_{0}^{M} R_{N}(t)(n + ηN − t)^{−α−1} dt|
≤ 2βR_{N}(n + ηN − M)^{−α} = 2βR_{N}(η)^{−α}(n + ηN)^{−α}
≤ 2βR_{N}η^{−3α}N^{−α} < ε/3

if N is so large that

R_{N} < μA(N), μ = \frac{εη^{3α}}{6(1 + ε)s(α)(1 − α)}.

Hence for sufficiently large N, the required property (3.3) is established.

To prove Λ_{N} > (1 − ε)s(α)N/A(N), we construct nonnegative numbers δ_{n} for 0 ≤ n ≤ N, such that ∑_{a} δ_{n−a} ≤ 1 for all n, while ∑ δ_{n} ≥ (1 − ε)s(α)N/A(N). To this end we select a number η > 0, depending on ε and define

δ_{n} = β(n + ηN)^{−α}, 0 ≤ n ≤ N,

where now

β = (1 − ε/2)s(α)(1 − α)\frac{N^{α}}{A(N)}.

We suppress the details of the estimates of the calculations, which are very similar to the previous ones.

4. Proof of Theorem 3.

In this section P (x) = x^{k}, with k odd.

First we observe that if p is a prime number such that p − 1 and k are relatively prime, then we have

m^{k} ≡ n^{k} mod p ⟹ m ≡ n mod p .

Indeed, if p divides m (or n) this claim is obvious. Let us assume that m^{k} ≡ n^{k} mod p, with p |̸ mn. Then we have m^{p−1} ≡ n^{p−1} ≡ 1 mod p. Moreover there exist integers u and v such that (p − 1)u + kv = 1. Thus we get

m ≡ m^{(p−1)u+kv} ≡ (m^{k})^{v} ≡ (n^{k})^{v} ≡ n^{(p−1)u+kv} ≡ n mod p ,

and the claim is proved.

Let N be a sufficiently large number. Let us choose a prime p with p > N^{\frac{1}{k}} and p ∼ N^{\frac{1}{k}} as N goes to infinity, and such that p − 1 and k are relatively prime. Let us define

B := {ap : 1 ≤ a ≤ N/p} .

We clearly have

| B |∼ N/p ∼ N^{1− \frac{1}{k}} .

We prove that the sets P (λ) + B are disjoint for 0 ≤ P (λ) ≤ N. Assume that λ_{1}^{k} + b_{1} = λ_{2}^{k} + b_{2}, with 0 ≤ P (λ_{1}), P (λ_{2}) ≤ N and b_{1}, b_{2} ∈ B. Then λ_{1}^{k} ≡ λ_{2}^{k} mod p, hence we have λ_{1} ≡ λ_{2} mod p. Moreover we know that | λ_{1} − λ_{2} |≤ P^{−1}(N) = N^{\frac{1}{k}} < p, thus λ_{1} = λ_{2}.

5. Remarks

With some change in the proof, Theorem 6 can be extended to the cases α = 0 and α = 1 (we define s(α) by continuity at these numbers, so that s(0) = s(1) = 1).

Assume that 0 ∈ A. In this case there are additive complements consisting exclusively of nonnegative integers; let L^{∗} be the minimal cardinality of such a set. We can also define a fractional analog Λ^{∗} of this number. We have obviously L ≤ L^{∗} and Λ ≤ Λ^{∗}. We think that under the conditions of Theorem 6 we have Λ ∼ Λ^{∗}, though the proof in Section 3 does not immediately yield this.

References

[1] J. Cilleruelo, The additive completion of Kth powers, J. Number Theory 44(1993), 237–243.

[2] L. Habsieger, On the additive completion of polynomial sets, J. Number Theory, to appear.

[3] Halberstam, H.; Roth, K. F, Sequences, Clarendon, London; (2nd ed. Springer– Verlag, New York–Berlin, 1983) 1966.