Another Proof of Nathanson’s Theorems

Quan-Hui Yang School of Mathematical Sciences Nanjing Normal University Nanjing 210046 P. R. CHINA

                     yangquanhui01@163.com

Abstract In this paper, without using generating functions, we give new combinatorial proofs of several theorems by Nathanson on the representation functions, and we also obtain generalizations of these theorems.

1 Introduction

Let A be a set of nonnegative integers. Let r_{h}^{A}(n) denote the number of representations of n as a sum of h elements of A and r^{A}(n) denote the number of representations of n as a sum of an arbitrary number of elements of A, where representations differing only in the arrangement of their summands are counted separately. We notice that if 0 ∉ A, then r^{A}(n) = ∑_{h=1}^{∞} r_{h}^{A}(n) is finite for all n. Representation functions have been extensively studied by many authors [1, 2, 3, 5, 6] and are still a fruitful area of research in additive number theory. Using generating functions, Nathanson [4] proved the following results.

Theorem 1. Let A and B be sets of nonnegative integers, and let r_{h}^{A}(n) and r_{h}^{B}(n) denote the number of representations of n as a sum of h elements of A and B, respectively. If r_{h}^{A}(n) = r_{h}^{B}(n) for all n ⩾ 0, then A = B.

Theorem 2. Let A and B be sets of positive integers, and let r^{A}(n) and r^{B}(n) denote the number of representations of n as a sum of an arbitrary number of elements of A and B, respectively. If r^{A}(n) = r^{B}(n) for all n ⩾ 1, then A = B.

Theorem 3. Let A and B be sets of positive integers, and let p^{A}(n) and p^{B}(n) denote the number of representations of n as a sum of an arbitrary number of elements of A and B, respectively, where representations differing only in the arrangement of their summands are not counted separately. If p^{A}(n) = p^{B}(n) for all n ⩾ 1, then A = B.

In this paper, we give new proofs of theorems above. Indeed, we shall prove slightly more. We first introduce some notation. If A is a strictly increasing sequence of integers, then a_{n} denotes the nth element of A. Let A be a set of nonnegative integers and H be a set of positive integers. If |H| is finite, then r_{H}^{A}(n) denotes the number of representations of n as a sum of h_{1} or h_{2} or … elements of A; if |H| is infinite, then r_{H}^{A}(n) denotes the number of representations of n as a sum of h_{1} or h_{2} or … elements of A\{0}.

Theorem 4. Let A and B be nonempty sets of nonnegative integers. Let H be a nonempty set of positive integers, and let S = {min{a_{i}, b_{i}} : i = 1, 2, …}. Write t = (min(H) − 1) min{a_{1}, b_{1}}. If r_{H}^{A}(n) = r_{H}^{B}(n) for all n ∈ t + S, then A = B.

Let H = {h}. Since t + S ⊆ {0, 1, 2, …}, Theorem 4 is a generalization of Theorem 1. Let H = {1, 2, 3, …}. If A and B are sets of positive integers, then t+S ⊆ {1, 2, …}. Hence, Theorem 4 is also a generalization of Theorem 2.

Theorem 5. Let A, B and H be nonempty sets of positive integers. Let S = {min{a_{i}, b_{i}} : i = 1, 2, …}, and let p_{H}^{A}(n) denote the number of representations of n as a sum of h_{1} or h_{2} or … elements of A, where representations differing only in the arrangement of their summands are not counted separately. Write t = (min(H) − 1) min{a_{1}, b_{1}}. If p_{H}^{A}(n) = p_{H}^{B}(n) for all n ∈ t + S, then A = B.

Let H = {1, 2, 3, …}. Since t + S ⊆ {1, 2, …}, Theorem 5 is a generalization of Theorem 3.

Let A, B, and T be finite sets of integers. If each residue class modulo m contains exactly the same number of elements of A as elements of B, then we write A ≡ B (mod m). If the number of solutions of the congruence a + t ≡ n (mod m) with a ∈ A, t ∈ T, equals the number of solutions of the congruence b + t ≡ n (mod m) with b ∈ B, t ∈ T, for each residue class n modulo m, then we write A + T ≡ B + T (mod m). Nathanson [4] also proved the following theorem.

Theorem 6. Let A and B be distinct nonempty sets of nonnegative integers such that r_{2}^{A}(n) = r_{2}^{B}(n) for all sufficiently large n. Then there exist finite sets A, B, and T with A ∪ B ⊂ {0, 1, …, N} and T ⊂ {0, 1, …, m − 1} such that A + T ≡ B + T (mod m), and A = A ∪ C and B = B ∪ C, where C = {c > N| c ≡ t (mod m) for some t ∈ T }.

In this paper, we prove theorems above without using generating functions. We notice that for a prime number p, if A and B are sets of nonnegative integers such that r_{p}^{A}(n) = r_{p}^{B}(n) for all sufficiently large n, then A and B eventually coincide. Now, I pose the following problem.

Problem 7. Let p ⩾ 3 be a prime number and A be a set of nonnegative integers. Does there exist a set of nonnegative integers B with B ≠ A such that r_{p}^{A}(n) = r_{p}^{B}(n) for all sufficiently large n?

2 Proof of Theorems 4 and 5

Suppose that A ≠ B. Let h = min(H) and j_{0} be the smallest index such that a_{j_{0}} ≠ b_{j_{0}}. Without loss of generality, we can assume that a_{j_{0}} < b_{j_{0}}. Let C = {a_{j} : j < j_{0}}. Since a_{j} = b_{j} for all j < j_{0} and t = (h − 1)a_{1}, we have (h − 1)a_{1} + a_{j_{0}} ∈ t + S and

\begin{aligned}r_{H}^{A}((h − 1)a_{1} + a_{j_{0}}) & = r_{H}^{C}((h − 1)a_{1} + a_{j_{0}}) + 1 \\ & = r_{H}^{B}((h − 1)a_{1} + a_{j_{0}}) + 1, \end{aligned}

which is a contradiction. Hence, we have A = B. This completes the proof of Theorem 4. The proof of Theorem 5 is very similar to the proof of Theorem 4, and we omit it here.

3 Proof of Theorem 6

Clearly, r_{2}^{A}(2n) is odd if and only if n ∈ A. Similarly, n ∈ B if and only if r_{2}^{B}(2n) is odd. If r_{2}^{A}(n) = r_{2}^{B}(n) for all n > N_{0}, then for all n > N_{0} we have n ∈ A if and only if n ∈ B. Let

D = A ∩ [N_{0} + 1, ∞) = B ∩ [N_{0} + 1, ∞)

and write

η(n) = \begin{cases}1, if n ∈ D; \\ 0, otherwise. \end{cases}

Then for n > 2N_{0}, we have

\begin{aligned}r_{2}^{A}(n) & = 2♯\{(a, d) : a ∈ A\D, d ∈ D, a + d = n\} \\ & + ♯\{(d′, d′′) : d′, d′′ ∈ D, d′ + d′′ = n\} \\ & = 2 ∑_{a∈A\D} η(n − a) + ♯\{(d′, d′′) : d′, d′′ ∈ D, d′ + d′′ = n\}. \end{aligned}  (1)

Similarly, we have

r_{2}^{B}(n) = 2 ∑_{b∈B\D} η(n − b) + ♯{(d′, d′′) : d′, d′′ ∈ D, d′ + d′′ = n}.  (2)

Since r_{2}^{A}(n) = r_{2}^{B}(n) for all n > N_{0}, by (1) and (2), we have

∑_{a∈A\D} η(n − a) = ∑_{b∈B\D} η(n − b)  (3)

for all n > 2N_{0}. Let i_{0} be the smallest index such that a_{i_{0}} ≠ b_{i_{0}}. Without loss of generality, we may assume that a_{i_{0}} < b_{i_{0}}.

Let

t = n − a_{i_{0}}

and

D′ = {a : a < a_{i_{0}}, a ∈ A}.

Then by (3), we have

η(t) = ∑_{b∈B\(D∪D′)} η(t + a_{i_{0}} − b) − ∑_{a∈A\(D∪D′∪a_{i_{0}})} η(t + a_{i_{0}} − a).

Since η(t) defined by a linear recurrence on a finite set {0, 1}, we have that it must be eventually periodic. Hence, for some N > N_{0}, D ∩ [N + 1, ∞) is periodic. We denote such a period by m. Let T = {t : t ≡ d (mod m) for some d ∈ D ∩ [N + 1, ∞) and 0 ⩽ t < m}. Then we have n ∈ A ∩ B ∩ [N + 1, ∞) if and only if n ≡ t (mod m) for some t ∈ T.

The remainder of the proof is the same as that of the proof by Nathanson. To make this paper self-contained, we formulate it here. Let

A = {a ⩽ N : a ∈ A}, B = {b ⩽ N : b ∈ B},

and

C = {c > N : c ∈ A ∩ B} = {c > N : c ≡ t (mod m) for some t ∈ T }.

Then A = A ∪ C and B = B ∪ C. Next we prove that A + T ≡ B + T (mod m). For n > 2N, we have

\begin{aligned}r_{2}^{A}(n) & = r_{2}^{C}(n) + 2♯\{(a, c) : a ∈ A, c ∈ C, a + c = n\} \\ & = r_{2}^{C}(n) + 2♯\{(a, t) : a ∈ A, t ∈ T, a + t ≡ n (mod m)\}. \end{aligned}  (4)

Similarly,

r_{2}^{B}(n) = r_{2}^{C}(n) + 2♯{(b, t) : b ∈ B, t ∈ T, b + t ≡ n (mod m)}.  (5)

Since r_{2}^{A}(n) = r_{2}^{B}(n) for n > 2N, by (4) and (5), we have that A + T ≡ B + T (mod m). This completes the proof of Theorem 6.

4 Acknowledgement

I sincerely thank my supervisor Professor Yong-Gao Chen for his valuable suggestions and useful discussions. I am also grateful to the referee for his/her valuable comments.

References

[1] Y. G. Chen, A. Sárkőzy, V. T. Sós, and M. Tang, On the monotonicity properties of additive representation functions, Bull. Aust. Math. Soc. 72 (2005), 129–138.

[2] P. Erdős, A. Sárkőzy, and V. T. Sós, Problems and results on additive properties of general sequences, V, Monatsh. Math. 102 (1986), 183–197.

[3] P. Erdős, A. Sárkőzy, and V. T. Sós, On additive properties of general sequences, Discrete Math. 136 (1994), 75–99.

[4] M. B. Nathanson, Representation functions of sequences in additive number theory, Proc. Amer. Math. Soc. 72 (1978), 16–20.

[5] M. B. Nathanson, Every function is the representation function of an additive basis for the integers, Port. Math. 62 (2005), 55–72.

[6] M. B. Nathanson, Representation functions of bases for binary linear forms, Funct. Approx. Comment. Math. 37 (2007), 341–350.

2010 Mathematics Subject Classification: Primary 11B34; Secondary 11D85. Keywords: Nathanson’s theorems; representation functions; generating functions.

Received March 13 2011; revised version received August 13 2011. Published in Journal of Integer Sequences, September 25 2011.

Return to Journal of Integer Sequences home page.