Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search