If $a_{nk} \leqslant n a_k$ for all $k \geqslant 0$ and $n > 0$, does $a_n/n$ converge?

Question

A sequence $a_n$ is called subadditive if $a_{n+k} \leqslant a_n + a_k$ for all $n, k \in \mathbb{N}$. Fekete's subadditive lemma states that if a sequence $a_n$ is subadditive, then the sequence $a_n/n$ converges. What about a sequence satisfying the weaker condition $a_{nk} \leqslant n a_k$ for all $k \geqslant 0$ and $n > 0$?

Answer 1

Let $a_{k}=k$ if $k$ is a power of $2$ and $a_l=1$ otherwise. This sequence satisfies your condition. So if $nk=2^j$ is a power of two, both $n$ and $k$ are powers of two, and we have $$nk = a_{nk} \leq n a_k = n k.$$

Now suppose $nk$ is not a power of two. Then $a_{nk}=1$, so $$1 = a_{nk} \leq n a_k$$ which must be true as $a_k \geq 1$.

Yet we have two subsequences of $a_k/k$, one converging to 1 and another converging to 0.

---

Here's another fun example. Set $a_1 = 1$. Let $a_p = p$ for $p$ prime, and $a_k$ be 1 otherwise. We must always have $a_{kn} \leq n a_k$ when $kn$ is prime because $p=kn$ implies $k=1$ or $k=p$.

---

The essence of your change is that you've taken away a lot by getting rid of the addition and replacing it with multiplication, to the extent that factorization and prime numbers matter a lot.