### (no subject)

Dang I was hoping there was some way of generating multi-resolution deterministic pseudorandom noise in a "local" way by constructing two invertible functions f, g acting on some finite set S such that

f o g o g = g o f

in a diagram:

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

And so I tried considering the noncommutative ring over

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

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

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

We claim that fgg = gf.

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

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

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

It remains to show 2

2

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.