[math-fun] cyclic groups; permutations
A cyclic group has a generator that generates all of the elements of the group; i.e., it produces a permutation of the elements of the group. Different generators may produce different permutations. Is there any algebraic structure that elegantly generates *all* permutations? One problem with generators is that there aren't nearly enough of them: there's only N elements, but N! permutations. Are there any other mechanisms -- perhaps high-degree polynomial evaluation or matrices -- that can generate all (& only) permutations? Obviously, matrices can permute the elements of rows & columns, but I'm interested in 1-1 functions of the elements themselves.
Answering own question: Lagrange interpolation can allow a polynomial to construct *any* function on a finite field(?), yes/no? So such an interpolation should allow any 1-1 function. Is there any elegant form of this interpolation that is specialized to 1-1 functions? At 11:08 AM 3/18/2016, Henry Baker wrote:
A cyclic group has a generator that generates all of the elements of the group; i.e., it produces a permutation of the elements of the group.
Different generators may produce different permutations.
Is there any algebraic structure that elegantly generates *all* permutations?
One problem with generators is that there aren't nearly enough of them: there's only N elements, but N! permutations.
Are there any other mechanisms -- perhaps high-degree polynomial evaluation or matrices -- that can generate all (& only) permutations?
Obviously, matrices can permute the elements of rows & columns, but I'm interested in 1-1 functions of the elements themselves.
Is there any algebraic structure that elegantly generates *all* permutations? I'm not exactly sure what you mean by algebraic structure, but "base factorial" gives an isomorphism between natural numbers and permutations.
https://en.wikipedia.org/wiki/Factorial_number_system On Fri, Mar 18, 2016 at 11:31 AM, Henry Baker <hbaker1@pipeline.com> wrote:
Answering own question:
Lagrange interpolation can allow a polynomial to construct *any* function on a finite field(?), yes/no?
So such an interpolation should allow any 1-1 function.
Is there any elegant form of this interpolation that is specialized to 1-1 functions?
At 11:08 AM 3/18/2016, Henry Baker wrote:
A cyclic group has a generator that generates all of the elements of the group; i.e., it produces a permutation of the elements of the group.
Different generators may produce different permutations.
Is there any algebraic structure that elegantly generates *all* permutations?
One problem with generators is that there aren't nearly enough of them: there's only N elements, but N! permutations.
Are there any other mechanisms -- perhaps high-degree polynomial evaluation or matrices -- that can generate all (& only) permutations?
Obviously, matrices can permute the elements of rows & columns, but I'm interested in 1-1 functions of the elements themselves.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
Instead of having each place worth b^n for some base b, they're worth n! each. Then given an n-tuple of numbers (1, ..., n), each digit of the number in factorial base tells which number to remove from the tuple and add to the permutation, e.g. 74 in base factorial is 24 06 02 01 3 0 1 0 (0,1,2,3)[3] = 3 (0,1,2)[0] = 0 (1,2)[1] = 2 (1)[0] = 1 so the permutation is (3,0,2,1). On Fri, Mar 18, 2016 at 5:31 PM, Dan Asimov <dasimov@earthlink.net> wrote:
How does that work, Mike?
—Dan
On Mar 18, 2016, at 11:36 AM, Mike Stay <metaweta@gmail.com> wrote:
"base factorial" gives an isomorphism between natural numbers and permutations.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
Interesting. I've long known of factorial base, but never knew that about it! —Dan
On Mar 18, 2016, at 8:03 PM, Mike Stay <metaweta@gmail.com> wrote:
Instead of having each place worth b^n for some base b, they're worth n! each. Then given an n-tuple of numbers (1, ..., n), each digit of the number in factorial base tells which number to remove from the tuple and add to the permutation, e.g. 74 in base factorial is 24 06 02 01 3 0 1 0
(0,1,2,3)[3] = 3 (0,1,2)[0] = 0 (1,2)[1] = 2 (1)[0] = 1
so the permutation is (3,0,2,1).
On Fri, Mar 18, 2016 at 5:31 PM, Dan Asimov <dasimov@earthlink.net> wrote:
How does that work, Mike?
—Dan
On Mar 18, 2016, at 11:36 AM, Mike Stay <metaweta@gmail.com> wrote:
"base factorial" gives an isomorphism between natural numbers and permutations.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Dan Asimov -
Henry Baker -
Mike Stay