Cardinality of $\{ n_i + i^k: i \in \mathbb{N} \} \cap [1,T]$ where $\{n_i \}$ is all natural numbers in some order

Question

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!

Answer 1

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.