Orbits of the Baker's Map FunctionDate: 12/11/2000 at 06:58:23 From: Niamh Subject: Baker's map, primitive roots of primes I'm investigating the function known as the Baker's map: f(x) = { 2x if x <= 1/2 { 2x-1 otherwise in Mathematica that would be: f[x_] := If[x<=1/2,2x,2x-1] I'm looking at inputs of the form x = p/q, where p and q are positive integers and p < q. I'm investigating the number of "orbits" a particular input has. For example, let x = 1/11. If you iterate this function enough times it outputs: {1/11, 2/11, 3/11, 4/11, 5/11, 6/11, 7/11, 8/11, 9/11, 10/11} i.e. all possible values of p/q are present, 1 <= p <= q. However, let x = 1/7, and when this is iterated it outputs only: {1/7, 2/7, 4/7} Letting x = 3/7, it outputs: {3/7, 5/7, 6/7} So, as you can see, 7 has 2 orbits. I've iterated the function for a lot of values of x, and I'm mainly looking at values of q that are prime. I found that all the ones with 1 orbit are the primes of primitive root 2. I am wondering why this is so, and if there is any other connection between Baker's map and primes of other primitive roots. Thanks. Date: 12/11/2000 at 15:08:58 From: Doctor Rob Subject: Re: Baker's map, primitive roots of primes Thanks for writing to Ask Dr. Math, Niamh. If you restrict yourself to a starting value of x of the form a/q, where 0 < a < q and q is prime, then: g(a) = q*f(a/q) = { 2*a if 2*a < q { 2*a - q if 2*a > q This is just the least positive residue of 2*a (mod q). Thus applying the map g is just multiplication by 2 (mod q). Orbits of this map are in one-to-one correspondence with orbits of f. Repeated application of g is multiplication by a power of 2 (mod q). That is the reason that f(x) and having 2 as a primitive root modulo q are related. Baker's map is connected to the number 2 because of its definition. If you wanted something connected to the number 3, you could define a map by: { 3*x 0 <= x < 1/3 f(x) = { 3*x-1 1/3 <= x < 2/3 { 3*x-2 2/3 <= x < 1 Then this function would have orbits related to powers of 3 mod q. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/