My question is based on an observation made by Vepir in their question "Grasshopper jumping on circles".
Vepir's observation was essentially that the sequence of triangle numbers $T\colon \mathbb{Z} \rightarrow \mathbb{Z}$ $$ T(n) = \frac{n(n+1)}{2} $$ forms a permutation when the inputs are restricted to $\{0,1,\dots,2^k-1\}$ and the outputs are considered $(\text{mod } 2^k)$. Moreover, this only works modulo powers of two.
Example
For example, when $k=3$, the sequence is $$ \begin{alignat*}{8} n: &&\ 0,\ & 1,\ & 2,\ & 3,\ & 4,\ & 5,\ & 6,\ & 7\\ T(n): &&\ 0,\ & 1,\ & 3,\ & 6,\ & 10,\ & 15,\ & 21,\ & 28\\ T(n) \pmod {8}: &&\ 0,\ & 1,\ & 3,\ & 6,\ & 2,\ & 7,\ & 5,\ & 4 \end{alignat*} $$
Question
I showed this to a colleague, and he proved it was a bijection for all $2^m$, however, his proof involved a good deal of case analysis.
Is there a quick and easy way to see that the triangle numbers restrict to a permutation if and only if $k$ is a power of two?
Also, are there examples of polynomials with rational coefficients $f \in \mathbb Q[x]$ that restrict to a permutation if and only if $k$ is a power of three? A power of four? A prime number? A Fibonacci number?
I'll be using $\equiv$ between non-integers to denote that the two sides differ by a multiple of the modulus $b^k$.
The map is a permutation, that is, bijective, exactly if $\frac12m(m+1)\equiv\frac12n(n+1)$ implies $m=n$ for $0\le m,n\lt b^k$. So assume $\frac12m(m+1)\equiv\frac12n(n+1)$. Adding $\frac18$ yields $\frac12\left(m+\frac12\right)^2\equiv\frac12\left(n+\frac12\right)^2$. Bringing both terms to one side and factoring the difference yields $\frac12\left(m+\frac12+n+\frac12\right)\left(m+\frac12-n-\frac12\right)\equiv0$, that is, $\frac12\left(m+n+1\right)\left(m-n\right)=rb^k$.
Now if $b=2$, since $m+n+1$ and $m-n$ have different parity, at most one of them can contribute factors of $2$. Moreover, since $m,n\lt 2^k$, either factor can contain at most $k$ factors of $2$ unless $m=n$. One factor is divided out by the factor $\frac12$, so the equation cannot be fulfilled unless $m=n$.
This argument doesn't work for $b\ne2$; indeed we can always choose $m=b^k-1$ and $n=0$ to get $k$ factors of $b$ in $n+k+1$, and none of them are divided out.