INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 4 (2004), #A18

PARTITIONS OF NATURAL NUMBERS AND THEIR REPRESENTATION FUNCTIONS

Csaba Sándor^{1}

Department of Stochastics, Technical University, Budapest, Hungary

                           csandor@math.bme.hu

Received: 1/19/04, Accepted: 10/22/04, Published: 10/25/04

Abstract

For a given set A of nonnegative integers the representation functions R_{2}(A, n), R_{3}(A, n) are defined as the number of solutions of the equation n = x + y, x, y ∈ A with condition x < y, x ≤ y, respectively. In this note we are going to determine the partitions of natural numbers into two parts such that their representation functions are the same from a certain point onwards.

1. Introduction

Throughout this paper we use the following notations: let ℕ be the set of nonnegative integers. For A ⊂ ℕ let R_{1}(A, n), R_{2}(A, n), R_{3}(A, n) denote the number of solutions of

x + y = n x, y ∈ A
x + y = n x < y, x, y ∈ A
x + y = n x ≤ y, x, y ∈ A

respectively. A Sárközy asked whether there exist two sets A and B of nonnegative integers with infinite symmetric difference, i.e.

|(A ∪ B)\(A ∩ B)| = ∞

and

R_{i}(A, n) = R_{i}(B, n) n ≥ n_{0}

for i = 1, 2, 3. For i=1 the answer is negative (see [2]). For i = 2 G. Dombi (see [2]) and for i = 3 Y. G. Chen and B. Wang (see [1]) proved that the set of nonnegative integers can be partitioned into two subsets A and B such that R_{i}(A, n) = R_{i}(B, n) for all n ≥ n_{0}. In this note we determine the sets A ⊂ ℕ for which either

1Supported by Hungarian National Foundation for scientific Research, Gant No T 38396 and FKFP 0058/2001.

R_{2}(A, n) = R_{2}(ℕ\A, n) for n ≥ n_{0}

or

R_{3}(A, n) = R_{3}(ℕ\A, n) for n ≥ n_{0}.

Theorem 1. Let N be a positive integer. The equality R_{2}(A, n) = R_{2}(ℕ\A, n) holds for n ≥ 2N − 1 if and only |A ∩ [0, 2N − 1]| = N and 2m ∈ A ⇔ m ∈ A, 2m + 1 ∈ A ⇔ m ∉ A for m ≥ N.

Setting out from N = 1 and 0 ∈ A we get Dombi’s construction which is the set of nonnegative integers n where in the binary representation of n the sum of the digits is even.

Theorem 2. Let N be a positive integer. The equality R_{3}(A, n) = R_{3}(ℕ\A, n) holds for n ≥ 2N − 1 if and only if |A ∩ [0, 2N − 1]| = N and 2m ∈ A ⇔ m ∉ A, 2m + 1 ∈ A ⇔ m ∈ A for m ≥ N.

Setting out from N = 1 and 0 ∈ A we get Y. G. Chen and B. Wang’s construction which is the set of nonnegative integers n where in the binary representation the number of the digits 0 is even.

2. Proofs

The proofs are very similar therefore we only present here the proof of Theorem 2.

Proof of Theorem 2. For A ⊂ ℕ let

f(x) = ∑_{a∈A} x^{a} = ∑_{i=0}^{∞} ϵ_{i}x^{i}.

Then we have

∑_{n=0}^{∞} R_{3}(A, n)x^{n} = \frac{1}{2}(f(x^{2}) + f^{2}(x))

and

∑_{n=0}^{∞} R_{3}(ℕ\A, n)x^{n} = \frac{1}{2}(\frac{1}{1 − x^{2}} − f(x^{2}) + (\frac{1}{1 − x} − f(x))^{2}),

moreover the condition R_{3}(A, n) = R_{3}(ℕ\A, n) for n ≥ 2N − 1 is equivalent to the existence of a polynomial p(x) of degree at most 2N − 2 such that

∑_{n=0}^{∞}(R_{3}(A, n) − R_{3}(ℕ\A, n))x^{n} = p(x).

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 4 (2004), #A18 3

Then

∑_{n=0}^{∞}(R_{3}(A, n) − R_{3}(ℕ\A, n))x^{n} =

\frac{1}{2}(f(x^{2}) + f^{2}(x) − (\frac{1}{1 − x^{2}} − f(x^{2}) + (\frac{1}{1 − x} − f(x))^{2})) =

\frac{1}{2}(2f(x^{2}) − \frac{1}{1 − x^{2}} − \frac{1}{(1 − x)^{2}} − \frac{2f(x)}{1 − x}) =

f(x^{2}) − \frac{1}{(1 − x)^{2}(1 + x)} + \frac{f(x)}{1 − x} = p(x),

i.e.

f(x) = \frac{1}{1 − x^{2}} − f(x^{2}) + f(x^{2})x + p(x)(1 − x).

First let us suppose that R_{3}(A, n) = R_{3}(ℕ\A, n) holds for n ≥ 2N − 1. Then there exists a polynomial p(x) of degree at most 2N − 2 such that

f(x) = \frac{1}{1 − x^{2}} − f(x^{2}) + f(x^{2})x + p(x)(1 − x).

So we have

p(x)(1 − x) = ∑_{i=0}^{2N−1} α_{i}x^{i},

where ∑_{i=0}^{2N−1} α_{i} = 0, furthermore

\frac{1}{1 − x^{2}} − f(x^{2}) + f(x^{2})x = ∑_{i=0}^{∞}((1 − ϵ_{i})x^{2i} + ϵ_{i}x^{2i+1}).

Hence

f(x) = ∑_{i=0}^{∞} ϵ_{i}x^{i} =

\frac{1}{1 − x^{2}} − f(x^{2}) + f(x^{2})x + p(x)(1 − x) =

∑_{i=0}^{N−1}((1 − ϵ_{i})x^{2i} + ϵ_{i}x^{2i+1}) + ∑_{i=0}^{2N−1} α_{i}x^{i} + ∑_{i=N}^{∞}((1 − ϵ_{i})x^{2i} + ϵ_{i}x^{2i+1}) =

∑_{i=0}^{2N−1} ϵ_{i}x^{i} + ∑_{i=2N}^{∞} ϵ_{i}x^{i},

where

∑_{i=0}^{2N−1} ϵ_{i} = ∑_{i=0}^{N−1}((1 − ϵ_{i}) + ϵ_{i}) + ∑_{i=0}^{2N−1} α_{i} = N,

therefore

|A ∩ [0, 2N − 1]| = N

and

ϵ_{2m} = 1 − ϵ_{m}, ϵ_{2m+1} = ϵ_{m} for m ≥ N,

which means that 2m ∈ A if and only if m ∉ A and 2m + 1 ∈ A if and only if m ∈ A for m ≥ N, which proves the necessary part of Theorem 2.

In the sufficient part we assume that |A ∩ [0, 2N − 1]| = N and 2m ∈ A ⇔ m ∉ A, 2m + 1 ∈ A ⇔ m ∈ A for m ≥ N. This is equivalent to the assumptions that for the generating function f(x) = ∑_{i=0}^{∞} ϵ_{i}x^{i} we have

∑_{i=0}^{2N−1} ϵ_{i} = N

and

ϵ_{2m} = 1 − ϵ_{m}, ϵ_{2m+1} = ϵ_{m} for m ≥ N.

Hence

f(x) = ∑_{i=0}^{∞} ϵ_{i}x^{i} = ∑_{i=0}^{2N−1} ϵ_{i}x^{i} + ∑_{i=N}^{∞} ϵ_{2i}x^{2i} + ∑_{i=N}^{∞} ϵ_{2i+1}x^{2i+1} =

∑_{i=0}^{2N−1} ϵ_{i}x^{i} + ∑_{i=N}^{∞}(1 − ϵ_{i})x^{2i} + ∑_{i=N}^{∞} ϵ_{i}x^{2i+1} =

∑_{i=0}^{2N−1} ϵ_{i}x^{i} + ∑_{i=0}^{∞}(1 − ϵ_{i})x^{2i} − ∑_{i=0}^{N−1}(1 − ϵ_{i})x^{2i} + ∑_{i=0}^{∞} ϵ_{i}x^{2i+1} − ∑_{i=0}^{N−1} ϵ_{i}x^{2i+1} =

∑_{i=0}^{∞} x^{2i} − ∑_{i=0}^{∞} ϵ_{i}x^{2i} + x ∑_{i=0}^{∞} ϵ_{i}x^{2i} + ∑_{i=0}^{2N−1} ϵ_{i}x^{i} − ∑_{i=0}^{N−1}(1 − ϵ_{i})x^{2i} − ∑_{i=0}^{N−1} ϵ_{i}x^{2i+1} =

\frac{1}{1 − x^{2}} − f(x^{2}) + xf(x^{2}) + ∑_{i=0}^{2N−1} γ_{i}x^{i},

where

∑_{i=0}^{2N−1} γ_{i} = ∑_{i=0}^{2N−1} ϵ_{i} − ∑_{i=0}^{N−1}(1 − ϵ_{i}) − ∑_{i=0}^{N−1} ϵ_{i} = N − N = 0,

therefore there exists a polynomial p(x) of degree at most 2N-2 such that

∑_{i=0}^{2N−1} γ_{i}x^{i} = p(x)(1 − x).

Hence

f(x) = \frac{1}{1 − x^{2}} − f(x^{2}) + f(x^{2})x + p(x)(1 − x),

which proves the sufficient part of Theorem 2.

References

[1] Y. G. Chen and B.Wang, On additive properties of two special sequences, Acta Arithm, Vol 110 (2003), 299-303.

[2] G. Dombi, Additive properties of certain sets, Acta Arithm. Vol 103 (2002), 137-146.

[3] P. Erdős and A. Sárközy, Problems and results on additive properties of general sequences I, Pacific J. Math. 118 (1985), 347-357.

[4] P. Erdős, A. Sárközy and V. T. Sós, Problems and results on additive properties of general sequences III, Studia Sci. Math. Hung. 22 (1987), 53-63.

[5] —,—,—, Problems and results on additive properties of general sequences IV,in: Number Theory (Ootacamund, 1984), Lecture Notes in Math. 1122, Springer, Berlin, 1985, 85-104.