Let $n\_1, n\_2, ...$ be a sequence of natural numbers such that $\{n\_i: i \in \mathbb{N}\}$ as a set is all of natural numbers. Let $k$ be a positive integer. Is is possible to obtain a lower bound of the form
$$
\# (\{ n\_i + i^k: i \in \mathbb{N} \} \cap [1,T]) \gg T^c 
$$
for some $c>0$? I'm not sure where to start so any reference and comments are appreciated!



Cardinality of $\{ n_i + i^k: i \in \mathbb{N} \} \cap [1,T]$ where $\{n_i \}$ is all natural numbers in some order
Such a lower bound is not possible, even when $k=1$. Indeed, there exists a sequence $(n\_1,n\_2,\dotsc)$ containing every natural number such that for infinitely many positive integers $N$ we have $n\_i=2^i$ for $i\in\{N+1,N+2,\dotsc, 2^N\}$. Then, for such an $N$ we have that
$$\{ n\_i + i: i \in \mathbb{N} \} \cap [1,2^N]\subset [1,N],$$
so that no $c>0$ satisfies the desired bound.


