f o g o g = g o f

in a diagram:

g g g g g g g g *->*->*->*->*->*->*->*->* f| f| f |f |f v v v v v *--g->*--g->*--g->*--g->* f| |f |f v v v *-----g---->*-----g---->* f| |f v v *---------------------->* g

So that g represents moving one step horizontally "in the current scale" and f is a zoom-out and f

^{-1}is a zoom-in. At every vertex of this diagram you have some element of S, which is analogous to the random seed in the usual sort of LFSR pseudorandom number generator. But both f and g are to be invertible, so we can freely move around in this (infinite) graph up and down, left and right.

And so I tried considering the noncommutative ring over

**Z**

_{2}generated by strings over {f, g} (viewed as noncommutative polynomials) quotiented by fgg - gf, and further quotiented by something like f

^{3}+ f

^{2}+ 1 (because I'm imagining that just doing f repeatedly should behave like a LFSR). But I tried doing some calculations by hand, and it seemed like imposing that equation caused some nontrivial equations to hold of g.... so I wasn't totally free, as I'd hoped, to turn iterates of f into an LFSR and iterates of g into an LFSR in independent ways.

And then I remembered Wedderburn's little theorem which meant that if I have a finite "noncommutative field" (which are apparently called "division rings") then it's actually a field, and I can't avoid fg = gf, which ruins the whole game. Bummer.

---

An interesting *group* (not field) I can construct (and since it's not a LFSR-ish field it seems useless for random number generation) is the following.

For any n, let G

_{n}be the group of permutations on [2

^{n}-1] × [n] generated by:

f maps (x, y) to (x, (y + 1) % n)

g maps (x, y) to ((x + 2

^{y}) % (2

^{n}- 1), y)

We claim that fgg = gf.

Well, gg maps (x, y) to ((x + 2

^{y+1}) % (2

^{n}- 1), y)

so that fgg maps (x, y) to ((x + 2

^{y+1}) % (2

^{n}- 1), (y + 1) % n).

But gf maps (x, y) to ((x + 2

^{(y + 1) % n}) % (2

^{n}- 1), (y + 1) % n).

It remains to show 2

^{y+1}and 2

^{(y + 1) % n}are congruent mod 2

^{n}- 1. But this is easy:

2

^{(y + 1) % n}differs from 2

^{y+1}by a factor of 2

^{kn}for some k, and 2

^{n}is 1 mod 2

^{n}- 1.