Los números triangulares ( $\text{mod } 2^n$ ) como una permutación de $\{0,1,2,\dots,2^n-1\}$

Question

Mi pregunta se basa en una observación hecha por Vepir en su pregunta " Saltamontes saltando en círculos ".

La observación de Vepir fue esencialmente que la secuencia de números triangulares $T\colon \mathbb{Z} \rightarrow \mathbb{Z}$ $$ T(n) = \frac{n(n+1)}{2} $$ forma una permutación cuando las entradas están restringidas a $\{0,1,\dots,2^k-1\}$ y las salidas se consideran $(\text{mod } 2^k)$ . Además, esto sólo funciona en módulo de dos.

Ejemplo

Por ejemplo, cuando $k=3$ la secuencia es $$ \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*} $$

Pregunta

Le mostré esto a un colega, y demostró que era una biyección para todos $2^m$ , sin embargo, su prueba implicaba una buena cantidad de análisis de casos.

¿Existe una manera rápida y fácil de ver que los números triangulares restringen a una permutación si y sólo si $k$ es una potencia de dos?

Además, ¿hay ejemplos de polinomios con coeficientes racionales $f \in \mathbb Q[x]$ que se restringen a una permutación si y sólo si $k$ es una potencia de tres? ¿Una potencia de cuatro? ¿Un número primo? ¿Un número de Fibonacci?

Answer 1

Utilizaré $\equiv$ entre números no enteros para denotar que los dos lados difieren en un múltiplo del módulo $b^k$ .

El mapa es una permutación, es decir, biyectiva, exactamente si $\frac12m(m+1)\equiv\frac12n(n+1)$ implica $m=n$ para $0\le m,n\lt b^k$ . Por lo tanto, asuma $\frac12m(m+1)\equiv\frac12n(n+1)$ . Añadir $\frac18$ produce $\frac12\left(m+\frac12\right)^2\equiv\frac12\left(n+\frac12\right)^2$ . Si se separan ambos términos y se factoriza la diferencia, se obtiene $\frac12\left(m+\frac12+n+\frac12\right)\left(m+\frac12-n-\frac12\right)\equiv0$ Es decir, $\frac12\left(m+n+1\right)\left(m-n\right)=rb^k$ .

Ahora bien, si $b=2$ ya que $m+n+1$ y $m-n$ tienen diferente paridad, como máximo uno de ellos puede aportar factores de $2$ . Además, como $m,n\lt 2^k$ cualquiera de los dos factores puede contener como máximo $k$ factores de $2$ a menos que $m=n$ . Un factor se divide por el factor $\frac12$ por lo que la ecuación no puede cumplirse a menos que $m=n$ .

Este argumento no sirve para $b\ne2$ En efecto, siempre podemos elegir $m=b^k-1$ y $n=0$ para conseguir $k$ factores de $b$ en $n+k+1$ y ninguno de ellos está dividido.