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 Z2 generated by strings over {f, g} (viewed as noncommutative polynomials) quotiented by fgg - gf, and further quotiented by something like f3 + f2 + 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 Gn be the group of permutations on [2n-1] × [n] generated by:
f maps (x, y) to (x, (y + 1) % n)
g maps (x, y) to ((x + 2y) % (2n - 1), y)
We claim that fgg = gf.
Well, gg maps (x, y) to ((x + 2y+1) % (2n - 1), y)
so that fgg maps (x, y) to ((x + 2y+1) % (2n - 1), (y + 1) % n).
But gf maps (x, y) to ((x + 2(y + 1) % n) % (2n - 1), (y + 1) % n).
It remains to show 2y+1 and 2(y + 1) % n are congruent mod 2n - 1. But this is easy:
2(y + 1) % n differs from 2y+1 by a factor of 2kn for some k, and 2n is 1 mod 2n - 1.
