Inducing a Permutation

Question

I'm trying to understand the following, from the OEIS, sequence A294673:

a(n) is equal to the order of multiplication-by-2 acting on the set of non-zero elements in (Z/(4n+3)Z), modulo the action of +-1. To be precise, identify i=1,2,...,2*n+1 with the odd representatives J=1,3,...,4*n+1 of this set, via the map J = 2*i-1. It is not hard to show that the induced permutation on the set of J values is given on integer representatives by J -> (4*n+3+J)/2 if i=(J+1)/2 is even and J -> (4*n+3-J)/2 if i=(J+1)/2 is odd. It follows that this induces the permutation J -> +-J/2 (mod 4*n+3), from which we immediately see that the order is as stated.

Note that the order of 2 acting on (Z/(4n+3)Z)/{+-1} is the same as the order of either 2 or -2 acting on (Z/(4n+3)Z), depending on which of these is a quadratic residue modulo 4n+3. Thus an equivalent (and often easier) way to compute a(n) is as the order of -2*(-1)^n acting on (Z/(4n+3)Z).

Among other things, the lower and upper bounds log_2(n) + 2 < a(n) <= 2*n+1 follow immediately.

...but I can't figure out what inducing a permutation means - can't understand it well enough to follow the presentation.

I have a feeling that it's pretty simple, but I haven't been able to find a simple presentation of it; everything I find assumes that the reader knows what it is.

Answer 1

Take $n=3$, so that we're working over $\mathbb Z/15\mathbb Z$.

Then the possible remainders modulo $15$, up to sign, are: $$ 0, \pm1, \pm2, \pm3, \pm4, \pm5, \pm6,\pm7 $$ and multiplying them by $2$ gives $$ 0, \pm2, \pm4, \pm6, \pm7, \pm5, \pm3, \pm1. $$ (For example, $\pm6 \times 2 = \pm 12 \equiv \pm 3 \pmod {15}$.)

The permutation of $\{1,2,3,4,5,6,7\}$ that this operation induces is the bijective function $f$ from $\{1,2,3,4,5,6,7\}$ to $\{1,2,3,4,5,6,7\}$ for which $f(x)=y$ whenever $\pm x \times 2 \equiv \pm y \pmod{15}$. (For example, $f(6) = 3$.)

In this case, we can specify this permutation as the list $$ f(1)=2,\, f(2)=4,\, f(3)=6,\, f(4)=7,\, f(5)=5,\, f(6)=3,\, f(7)=1 $$ or in one-line notation as $2\,4\,6\,7\,5\,3\,1$.

The order of this permutation is $4$, because

• $f(f(f(f(x)))) = x$ for all inputs $x$: applying $f$ $4$ times always returns you to where you started,
• $4$ is the least positive integer for which it's true. (It's also true for all multiples of $4$.)

So in the sequence A294673, $a(3) = 4$.