2
$\begingroup$

Can the behavior of infinite group generators be related to the behavior of random number generators? It may be coincidence, but in Donald Knuth's Art of Programming Volume 2 on seminumerical algorithms, he uses notation similar to $\left<g \right>$, the notation used for the subgroup generated by $g$, when describing a random sequence. Are there group properties that imply a generator will generate random sequences? Do groups have too much structure to generate random sequences?

$\endgroup$
  • $\begingroup$ Your last question is thoroughly discussed in seminumerical algorithms $\endgroup$ – Hagen von Eitzen Apr 29 '18 at 20:52
  • $\begingroup$ @HagenvonEitzen Thanks for responding. To be clear, I'm more curious if there are group properties that imply that the generated sequence will be distributed in the way he discusses. $\endgroup$ – Dan Kowalczyk Apr 29 '18 at 20:59
2
$\begingroup$

I think so. For example, if you take $g$ a generator of $F_{p^n}^*$ (the group of units in the field with $p^n$ elements), then it's powers look pseudo-random (whatever this means), if I recall correctly. This is related to the shift register sequence construction for pseudo-random numbers.

For example, if we take $F_5^*$, and the generator 3, we get $3,4, 2, 1$, which looks pretty random I guess. (Especially if you didn't know it was mod 5.)

The pattern is easy to guess when $n = 1$, but when $n$ is larger and you write $F_{p^n}$ as a vector space over $F_p$, it becomes trickier guess the pattern.

You can look in the book Applied Abstract Algebra by Lidl/Pilz for more on this. (The chapter on Linear recurring sequences.) There is also the original book by Golomb. (I have read neither.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is also the content of the first chapter of Donald Knuth's Art of Programming Volume 2, if I recall correctly. (That is, is the content of the first chapter of the book the OP is reading!) $\endgroup$ – user1729 Apr 30 '18 at 8:16
  • $\begingroup$ @user1729 Good to know! Thanks. $\endgroup$ – Lorenzo Najt Apr 30 '18 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.