Nearly subadditive sequences

Abstract

We show that the de Bruijn-Erdős condition for the error term in their improvement of Fekete's Lemma is not only sufficient but also necessary in the following strong sense. Suppose that given a sequence $0\le f(1)\le f(2)\le f(3)\le \dots$ such that \begin{equation}\sum_{ n=1}^{\infty} f(n)/n^2 = \infty. \end{equation} Then, there exists a sequence $\{b(n){\}}_{n=1,2,\dots }$ satisfying \begin{equation}\label{eq1} b(n+m) \leq b(n) + b(m) + f(n+m) \end{equation} such that the sequence of slopes $\{b(n)/n{\}}_{n=1,2,\dots }$ takes every rational number. When the series is bounded we improve their result as follows. If there exist $N$ and real $\mu >1$ such that near $f$-subadditivity holds for all pairs $(n,m)$ with $N\le n\le m\le \mu n$, then ${\lim }_{n}b(n)/n$ exists.

11 pages