Abstract
Given a set A of natural numbers, i.e., nonnegative integers, there are three distinctive functions attached to it, each of which completely determines A. These are the characteristic function \(\chi _{A}(n)\) which is equal to 1 or 0 according as the natural number n lies or does not lie in A, the counting function A(n) which gives the number of elements a of A satisfying \(a\le n\), and the representation function \(r_{A}(n)\) which counts the ordered pairs (a, b) of elements \(a, b\in A\) such that \(a+b=n\). We establish direct relations between these three functions. In particular, we express each one of them in terms of each other one. We also characterize the representation functions by an intrinsic recursive relation which is a necessary and sufficient condition.
Access provided by CONRICYT-eBooks. Download conference paper PDF
Similar content being viewed by others
Keywords
AMS Classification Numbers:
1 Introduction
Let A be a subset of \(\mathbb {N} =\{0,1,2,\ldots \}\).
The characteristic function of A is defined by
The counting function of A is defined by
The representation function of A is defined by
Here \(n \in {\mathbb N}\). But the three functions \(chi_A(n)\), A(n), \(r_A(n),\) can be extended to all real numbers \(x\in {\mathbb R}\), by simply replacing n by x in the above definitions.
Clearly, the functions \(\chi _A(n)\) and A(n) completely determine A, since the condition \(n\in A\) is equivalent to either conditions: \(\chi _A(n)=1\) or \(A(n)>A(n-1)\).
It is not as obvious that the function \(r_A(n)\) completely determines A too, but it does, and several authors have written about this topic. In particular, the consequences of the equality, or of the partial equality from some point on, of the representation functions \(r_A(n)\) and \(r_B(n)\) of two sets of natural numbers A and B have been studied rather extensively [1, 2, 12,13,14, 17, 22, 23]. Other research has focused on studying the properties of representation functions, trying to characterize the class of representation functions and to determine which functions belong to this class. Also, many outstanding open problems and conjectures have been made in this respect [3,4,5,6,7,8,9,10,11, 15, 16, 18,19,20,21]. In particular, Melvyn B. Nathanson highlights in one of his papers [18] the following problem:
What functions are representation functions?
The purpose of the present paper is twofold, first to establish relations between the three functions defined above, expressing each one of them in terms of each other one; and second, and more particularly, to attempt an answer to Nathanson’s question. We thus give an intrinsic characterization of representation functions by proving that a function \(f : {\mathbb N}\longrightarrow {\mathbb N}\) is the representation function of a subset A of \({\mathbb N}\) if and only if it satisfies the relation
for all \(n \in {\mathbb N}\).
2 Preliminaries and Generating Series
We first note the following obvious relations between the characteristic and the counting functions of A:
and
for all \(n\in \mathbb {N}\).
We then introduce the generating series of the three functions.
The generating series of \(\chi _A(n)\) is
also called the series associated with A.
The generating series of \(r_A(n)\) is
which is the square of the generating series \(f_A(X)\) of \(\chi _A(n)\).
The generating series of A(n) is
3 Relations Between the Counting and Representation Functions
Squaring the generating series of the counting function, we get
On the other hand, as \(g_A(X)\) is the generating series of \(r_A(n)\), and as
we also have
Thus,
This yields the following result, which gives the first relation between A(n) and \(r_A(n)\).
Proposition 1
For every \(n\in \mathbb N\), we have
i.e.,
Corollary 1
For \(n\in \mathbb N\), we have
Example 1
Applying the relation in the Corollary to \(n=0,1,2,\ldots \) in increasing order and back-substituting in terms of the A(n)’s alone, we get
\(r_A(0) = A(0)^2,\)
\(r_A(1) =2A(0)A(1) - 2A(0)^2,\)
\(r_A(2) = A(0)^2 - 4A(0)A(1) + 2A(0)A(2) + A(1)^2,\)
\(r_A(3) = 2A(0)A(1) - 4A(0)A(2) + 2A(0)A(3) - 2A(1)^2 + 2A(1)A(2)\)
Proposition 2
For any \(n\in {\mathbb N}\), we have
Proof
Using the generating series for \(r_A(n)\) and for A(n), we get
Hence, for all \(n\in {\mathbb N}\),
Corollary 2
For any \(n\in {\mathbb N}\), we have
where
Proof
By Proposition 2,
Corollary 3
For any \(n\in {\mathbb N}\), we have
the last two sums being obviously restricted to \(a\le n\) and \(b\le n.\)
Proof
For any \(k\in {\mathbb N}\), we have
Hence, for any \(j\in {\mathbb N}\),
This, in conjunction with Proposition 2, implies
Example 2
By Corollary 2, \(r_A (5) = \sum \limits _{\begin{array}{c} j, k \in {\mathbb N}: \\ j+k \le 5 \end{array}} c_5 (j, k) A(j)A(k)\), where
Hence,
Similarly,
Remark 1
It follows from Corollary 2 that, for \(n\in {\mathbb N}\),
Indeed, for \(n \ge 1\), we have
For \(n=0,\) the sum reduces to \(c_0 (0,0) =1.\) \(\square \)
Remark 2
For \(n\ge 1,\) we have
So the last two sums in Corollary 3 have the same number of terms each if \(n\notin A,\) while the first of the two sums has one more term than the second one if \(n\in A.\)
Let \(I = A \cap (1+A), B=A \smallsetminus (1+A) = A \smallsetminus I\), and \(C= (1+A) \smallsetminus A = (1+A) \smallsetminus I\). Then,
Let \(B[n] =B \cap [0,n] = \{ b_1< b_2< \cdots< b_{h-1} < b_h \}\) and \(C[n] = C \cap [0,n] = \{ c_1< c_2< \cdots < c_{h-1} \le c_h \}\), where \(c_h = c_{h-1}\) if \(n \in A\), and \(c_{h-1} < c_h\) if \(n \notin A\). In view of Corollary 3,
i.e.,
Note also that \(b_k < c_k\) for \(1 \le k <h\) (and for \(k=h\) if \(n \notin A\)), since if \(A = \{ a_1< a_2< \cdots< a_n < \cdots \}\), then \(1+A = \{ a_1 +1< a_2 +1< \cdots< a_n +1 < \cdots \}\), and B (resp. C) is obtained from A (resp. \(1+A\)) by removing the same set I. It follows that \(n- b_k > n- c_k\) and therefore \(A(n- b_k) \ge A(n- c_k)\) for \(1 \le k <h\) (and for \(k=h\) if \(n \notin A\)).
Remark 3
We have
Indeed, letting \(I = A \cap (1+A)\), so that \(A \smallsetminus (1+A) = A \smallsetminus I\) and \((1+A) \smallsetminus A = (1+A) \smallsetminus I\), we have
4 Relations Between the Characteristic and the Representation Functions
Just as the counting function A(n) determines A, the number of representations function \(r_{A}(n)\) also determines A.
Indeed, as
we have
where if
then
with the power series \(v(X) =\sum \limits _{n=2}^{\infty }X^{a_n - a_1 -1}\), so that
with a power series u(X), and therefore
is well defined. Moreover, replacing A by \(-a_1 +A= \{ a_n - a_1 : n\ge 1 \}\), we may assume that \(0\in A\), so that \(r_A (0) =1\), and
with
Then,
where \(\genfrac(){0.0pt}0{x}{k}\) denotes the binomial coefficient, defined by
for integers \(k\ge 1,\) while \(\genfrac(){0.0pt}0{x}{0}=1\).
Proposition 3
Assuming that \(0 \in A\), we have, for \(n \ge 1\),
Proof
We have \(f_A(X)=1+ \sum \limits _{n=1}^{\infty }\chi _A(n) X^n \), and
where u(X) is a power series with nonnegative integer coefficients. So
Moreover, for a positive integer \(k \in {\mathbb N}^*\), we have
Hence,
Thus, for \(n \ge 1\),
Furthermore, for \(k \ge 1\),
Therefore, for \(n \ge 1\),
Example 3
\(\chi _A(1) = \dfrac{1}{2} r_A (1) ,\)
\(\chi _A (2) = \dfrac{1}{2} r_A (2) - \dfrac{1}{8} r_A (1)^2,\)
\(\chi _A (3) = \dfrac{1}{2} r_A (3) - \dfrac{1}{4} r_A (1) r_A (2) + \dfrac{1}{16} r_A (1)^3,\)
\(\chi _A (4) = \dfrac{1}{2} r_A (4) - \dfrac{1}{4} r_A (1) r_A (3) - \dfrac{1}{8} r_A (2)^2 + \dfrac{3}{16} r_A ( 1)^2 r_A (2) - \dfrac{5}{128} r_A (1)^4,\)
Corollary 4
For a subset A of \({\mathbb N}\) containing 0, the counting function of A is given by
for \(x\ge 0.\)
Example 4
For \(n\ge 6,\)
Remark 4
Conversely, \(r_A(n)\) can be written in terms of \(\chi _A(n)\). Indeed, using Proposition 2 and the relations between the characteristic and the counting functions, we get, for \(n\in {\mathbb N}\),
i.e.,
for all \(n\in {\mathbb N}\).
Alternatively,
So
5 Characterization of the Representation Function
Lemma 1
For any \(n \in {\mathbb N}\), we have
Proof
In view of (39),
Corollary 5
For any \(n \in {\mathbb N}\), we have
Definition 1
For an integer \(a \in {\mathbb Z}\), let \(res_2(a)\) denote the least nonnegative residue of a modulo 2, i.e.,
Remark 5
It is easy to verify that, for \(a, b \in {\mathbb Z}\), we have
Remark 6
It follows from Lemma 1 and from Remark 5 that, for any \(n \in {\mathbb N}\), we have
Hence,
Moreover, for any \(n \in {\mathbb N}\),
and
Thus, the values of \(r_A(2n) \pmod 2\) completely determine A and therefore completely determine all values of \(r_A(n)\). In other words, the representation function \(r_A\) of A is completely determined by the parity of its values at the even natural numbers.
Moreover, the relation (51) characterizes the representation function, as seen from the following Theorem.
Theorem 1
Let \(f : {\mathbb N}\longrightarrow {\mathbb N}\) be a function from the set of nonnegative integers \({\mathbb N}\) into itself, satisfying the relation
Then \(f = r_A\) is the representation function of the subset A of \({\mathbb N}\) defined by
Proof
For any \(n \in {\mathbb N}\), we have
where
and
Now, by definition of A, we have
and
Clearly,
so that
and
It follows from this, and from the defining relation (52) of f, that
Moreover,
in view of (38).
Thus,
for all \(n \in {\mathbb N}\).
Corollary 6
A function \(f : {\mathbb N}\longrightarrow {\mathbb N}\) is the representation function of a subset A of \({\mathbb N}\) if and only if it satisfies the relation
Proof
This follows from (51) in Remark 6 and from Theorem 1.
Remark 7
Corollary 6 provides a characterization of representation functions. It is easier to characterize the characteristic and the counting functions. Indeed, any function \(f : {\mathbb N}\longrightarrow \{ 0, 1 \}\) is the characteristic function of a unique subset A of \({\mathbb N}\), namely of \(A = f^{-1}(1)\). Also, any increasing (not necessarily strictly increasing) function \(f : {\mathbb N}\longrightarrow {\mathbb N}\) is the counting function of a unique subset A of \({\mathbb N}\), namely of \(A = \{n \in {\mathbb N}: f(n) > f(n-1) \}\), where we set, by definition, \(f(-1) =0\).
References
Y.-G. Chen, M. Tang, Partitions of natural numbers with the same representation functions. J. Number Theory 129(11), 2689–2695 (2009)
J. Cilleruelo, M.B. Nathanson, Dense sets of integers with prescribed representation functions. European J. Comb. 34(8), 1297–1306 (2013)
A. Dubickas, A basis of finite and infinite sets with small representation function. Electron. J. Comb. 19(1), Paper 6, 16 pp (2012)
A. Dubickas, On the supremum of the representation function of a sumset. Quaest. Math. 37(1), 1–8 (2014)
P. Erdős, W.H.J. Fuchs, On a problem of additive number theory. J. Lond. Math. Soc. 31, 67–73 (1956)
P. Erdős, P. Turán, On a problem of Sidon in additive number theory. J. Lond. Math. Soc. 16, 212–215 (1941)
G. Grekos, L. Haddad, C. Helou, J. Pihko, On the Erdős-Turán conjecture. J. Number Theory 102, 339–352 (2003)
G. Grekos, L. Haddad, C. Helou, J. Pihko, The class of Erdős-Turán sets. Acta Arith. 117, 81–105 (2005)
G. Grekos, L. Haddad, C. Helou, J. Pihko, Representation functions, Sidon sets and bases. Acta Arith. 130(2), 149–156 (2007)
G. Grekos, L. Haddad, C. Helou, J. Pihko, Supremum of representation functions. Integers 11, A30, 14 pp (2011)
H. Halberstam, K.F. Roth, Sequences (Clarendon Press, Oxford, 1966)
J. Lee, Infinitely often dense bases for the integers with a prescribed representation function. Integers 10(A24), 299–307 (2010)
V.F. Lev, Reconstructing integer sets from their representation functions. Electron. J. Comb. 11(1), Research Paper 78, 6 pp (2004)
M.B. Nathanson, Representation functions of sequences in additive number theory. Proc. Am. Math. Soc. 72, 16–20 (1978)
M.B. Nathanson, in The inverse problem for representation functions of additive bases. Number Theory. (Springer, New York, 2004), pp. 253–262
M.B. Nathanson, Representation functions of additive bases for abelian semigroups. Int. J. Math. Math. Sci. 29–32, 1589–1597 (2004)
M.B. Nathanson, Every function is the representation function of an additive basis for the integers. Port. Math. (N.S.) 62(1), 55–72 (2005)
M.B. Nathanson, Inverse problems for representation functions in additive number theory. Surveys in number theory, 89–117, Dev. Math. 17 (Springer, New York, 2008)
C. Sándor, Range of bounded additive representation functions. Period. Math. Hungar. 42(1–2), 169–177 (2001)
C. Sándor, Partitions of natural numbers and their representation functions. Integers 4, A18, 5 pp (2004)
A. Sárközy, V.T. Sós, On additive representation functions. The mathematics of Paul Erdős, I, 129–150, Algorithms Comb. 13 (Springer, Berlin, 1997)
M. Tang, Partitions of the set of natural numbers and their representation functions. Discrete Math. 308(12), 2614–2616 (2008)
M. Tang, Dense sets of integers with a prescribed representation function. Bull. Aust. Math. Soc. 84(1), 40–43 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Helou, C. (2017). Characteristic, Counting, and Representation Functions Characterized. In: Nathanson, M. (eds) Combinatorial and Additive Number Theory II. CANT CANT 2015 2016. Springer Proceedings in Mathematics & Statistics, vol 220. Springer, Cham. https://doi.org/10.1007/978-3-319-68032-3_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-68032-3_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-68030-9
Online ISBN: 978-3-319-68032-3
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)