Portugaliae Mathematica   EMIS ELibM Electronic Journals PORTUGALIAE
Vol. 62, No. 1, pp. 55-72 (2005)

Previous Article

Next Article

Contents of this Issue

Other Issues

ELibM Journals

ELibM Home



Every function is the representation function of an additive basis for the integers

Melvyn B. Nathanson

Department of Mathematics, Lehman College (CUNY),
Bronx, New York 10468 -- USA
E-mail: melvyn.nathanson@lehman.cuny.edu

Abstract: Let $A$ be a set of integers. For every integer $n$, let $r_{A,h}(n)$ denote the number of representations of $n$ in the form $n=a_1+a_2+\cdots+a_h$, where $a_1,a_2,\ldots,a_h\in A$ and $a_1\leq a_2\leq\cdots\leq a_h$. The function
$$ r_{A,h}: \Z\to\N_0\cup\{\infty\} $$
is the {\em representation function of order $h$ for $A$.} The set $A$ is called an {\em asymptotic basis of order $h$} if $r_{A,h}^{-1}(0)$ is finite, that is, if every integer with at most a finite number of exceptions can be represented as the sum of exactly $h$ not necessarily distinct elements of $A$. It is proved that every function is a representation function, that is, if $f:\Z\to\N_0\cup\{\infty\}$ is any function such that $f^{-1}(0)$ is finite, then there exists a set $A$ of integers such that $f(n)=r_{A,h}(n)$ for all $n\in\Z$. Moreover, the set $A$ can be arbitrarily sparse in the sense that, if $\varphi(x)\geq 0$ for $x\geq 0$ and $\varphi(x)\to\infty$, then there exists a set $A$ with $f(n)=r_{A,h}(n)$ and $\card\left(\{a\in A: |a|\leq x\}\right)<\varphi(x)$ for all $x$.
It is an open problem to construct dense sets of integers with a prescribed representation function. Other open problems are also discussed.

Keywords: additive bases; sumsets; representation functions; density; Erdos--Turán conjecture; Sidon set.

Classification (MSC2000): 11B13, 11B34, 11B05.

Full text of the article:

Electronic version published on: 7 Mar 2008.

© 2005 Sociedade Portuguesa de Matemática
© 2005–2008 ELibM and FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition