Orbits of the Baker's Map Function

Date: 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/