Property of some permutations of non-negative integers such that $a(n)<2^k$ iff $n<2^k$

Question

• Let $$ \ell(n) = \left\lfloor\log_2 n\right\rfloor $$

• Let $$ f(n) = 2^{\ell(n)} $$

• Let $q_1(n)$ and $q_2(n)$ be an arbitrary self-inverse permutations of non-negative integers (that is, $q_i(q_i(n)) = n$) such that $q_i(n)<2^k$ iff $n<2^k$.

• Let $p_1(n)$ and $p_2(n)$ be a permutations of non-negative integers such that $p_i(n)<2^k$ iff $n<2^k$. Here $$ p_1(n) = q_1(p_2(q_2(n) - f(n)) + f(n)), \\ p_1(0) = 0, \\ p_2(n) = q_2(p_1(q_1(n) - f(n)) + f(n)), \\ p_2(0) = 0 $$

I conjecture that $$p_1(p_2(n)) = n.$$

At least it works for any combination of A054429 (complement all but the most significant bit in binary expansion of $n$), A059893 (reverse the order of all but the most significant bit in binary expansion of $n$) and A059894 (complement and reverse the order of all but the most significant bit in binary expansion of $n$).

Here is the PARI/GP prog to check it numerically:

bc(n) = if(n == 0, 0, 3*2^logint(n, 2) - n - 1)
br(n) = my(A = binary(n)); fromdigits(concat(1, Vecrev(vector(#A - 1, i, A[i+1]))), 2)
bcr(n) = my(A = binary(n)); fromdigits(concat(1, Vecrev(vector(#A - 1, i, 1 - A[i+1]))), 2)
p1(n) = if(n == 0, 0, my(A = 2^logint(n, 2)); bc(p2(br(n) - A) + A))
p2(n) = if(n == 0, 0, my(A = 2^logint(n, 2)); br(p1(bc(n) - A) + A))
test(n) = p1(p2(n)) == n

I also conjecture that if we go backwards from the resulting pair $p_1(n)$ and $p_2(n)$ to the original pair $q_1(n)$ and $q_2(n)$, then the last one is unique (that is, there are no two different pairs of $q_1(n)$ and $q_2(n)$ which result to the same pair of $p_1(n)$ and $p_2(n)$).

Is there a way to prove it? If the last conjecture is true, is there a way to go backwards and find unique original pair of $q_1(n)$ and $q_2(n)$ when the resulting pair $p_1(n)$ and $p_2(n)$ is known?

Answer 1

I'm going to use $\operatorname{msb}$ (for most significant bit) as an alias of $f$.

Since $q_i$ is a permutation, the property that $q_i(n)<2^k$ iff $n < 2^k$ is equivalent to $\operatorname{msb}(q_i(n)) = \operatorname{msb}n$ by a simple counting argument.

$$p_i(n) = q_i(p_{3-i}(q_{3-i}(n) - \operatorname{msb}n) + \operatorname{msb}n)$$

is easily seen to be, as claimed, another permutation which preserves $\operatorname{msb}$, so

$$p_i( \color{blue}{p_{3-i}(n)} ) = q_i(p_{3-i}(q_{3-i}(\color{blue}{p_{3-i}(n)}) - \operatorname{msb}(\color{blue}{p_{3-i}(n)})) + \operatorname{msb}(\color{blue}{p_{3-i}(n)})) \\ = q_i(p_{3-i}(q_{3-i}(\color{blue}{p_{3-i}(n)}) - \operatorname{msb}n) + \operatorname{msb}n) \\ = q_i(p_{3-i}(q_{3-i}(\color{blue}{q_{3-i}(p_i(q_i(n) - \operatorname{msb}n) + \operatorname{msb}n)}) - \operatorname{msb}n) + \operatorname{msb}n) \\ = q_i(p_{3-i}( \color{blue}{p_i(q_i(n) - \operatorname{msb}n) + \operatorname{msb}n} - \operatorname{msb}n) + \operatorname{msb}n) \\ = q_i(p_{3-i}(p_i(q_i(n) - \operatorname{msb}n)) + \operatorname{msb}n) \\ $$

If $p_{3-i}(p_i(q_i(n) - \operatorname{msb}n)) = q_i(n) - \operatorname{msb}n$ then we can further simplify $q_i(p_{3-i}(p_i(q_i(n) - \operatorname{msb}n)) + \operatorname{msb}n) = q_i(q_i(n) - \operatorname{msb}n + \operatorname{msb}n) = q_i(q_i(n)) = n$.

So we have an induction on $\operatorname{msb}n$: if $\forall 1 \le n < 2^k: p_1(p_2(n)) = p_2(p_1(n)) = n$ then $\forall 1 \le n < 2^{k+1}: p_1(p_2(n)) = p_2(p_1(n)) = n$, and the base case is easy because $1$ is necessarily a fixed point.

---

The answer to the second question is negative. Suppose $q_1 = q_2 = q$.

$$p_i(n) = q(p_{3-i}(q(n) - \operatorname{msb}n) + \operatorname{msb}n)$$

and by a similar induction on $\operatorname{msb}n$ we find that $p_1 = p_2$ is the identity permutation.