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

Melvyn B. Nathanson

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:

• Compressed PostScript file (224 kilobytes)
• PDF file (192 kilobytes)