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?
Best Answer
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.