Jason (jcreed) wrote,

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:
  g  g  g  g  g  g  g  g
f|    f|     f     |f    |f
 v     v     v     v     v
f|           |f          |f
 v           v           v
f|                       |f
 v                       v

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.
Tags: math

  • (no subject)

    Guy from Seattle team we've been working with showed up today at work; no matter how much I'm generally comfortable working with remote teams (and I…

  • (no subject)

    Sean's back in town --- good fun working with nonremote teammates.

  • (no subject)

    Sean's in town at work, good times.

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded