Bit-permutation function and Cantor Dust?

[mike3]

Hi.

Consider the following function on the interval [0, 1].

For x < 1:

1. Obtain the binary expansion of the fractional part of x (infinitely
long: if it "terminates" then just append an infinite
string of zeroes.)

2. Divide this into bit pairs, so the first 2 digits becomes pair 1,
the next 2 are another pair, and so on.

3. Reverse the bits in each pair.

4. Take this to be the binary expansion of the fractional part of
f(x), which has integer part 0.

For x = 1, f(x) = 1.

To illustrate this, I'll use the following example. Let's find the
value of f(1/3). Now, 1/3 in binary looks like 0.01010101010101...
Dividing that into bit pairs, we get 0.(01)(01)(01)... . Now,
reversing the bits iin the pairs, we get 0.(10)(10)(10)... . Then that
is the binary expansion of f(1/3), and is, of course, 2/3. So, f(1/3)
= 2/3.

The graph looks sort of like a "Cantor dust" (cartesian product of 2
copies of a Cantor set) that has been skewed and stretched or rotated.
The dust looks more like "middle half" than "middle third", however.
(i.e. remove the middle 2 quarters of the segument when divided into 4
quarters.)

Why does it produce this interesting pattern?

[Robert Israel]

mike3 <mike...@yahoo.com> writes:

This might be part of it:
Note that the base-4 expansion of f(x) - x + 1/3 contains only the
digits 0, 1 and 2, and thus is a member of a Cantor-type set.
--
Robert Israel isr...@math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada

[Dan Hoey]

mike3 wrote:
> Consider the following function on the interval [0, 1].
>
> For x < 1:
>
> 1. Obtain the binary expansion of the fractional part of x (infinitely
> long: if it "terminates" then just append an infinite
> string of zeroes.)
>
> 2. Divide this into bit pairs, so the first 2 digits becomes pair 1,
> the next 2 are another pair, and so on.
>
> 3. Reverse the bits in each pair.
>
> 4. Take this to be the binary expansion of the fractional part of
> f(x), which has integer part 0.

[...]

> The graph looks sort of like a "Cantor dust" (cartesian product of 2
> copies of a Cantor set) that has been skewed and stretched or rotated.
> The dust looks more like "middle half" than "middle third", however.
> (i.e. remove the middle 2 quarters of the segument when divided into 4
> quarters.)

Let P be the set of (x,f(x)) in [0,1]x[0,1]. P is the union of
P_1 = P/4,
P_2 = (P+(2,1))/4,
P_3 = (P+(1,2))/4, and
P_4 = (P+(3,3))/4.
where addition is interpreted as translation and division as scaling.

Let T be the linear transform defined by T((x,y))=(2x-y, 2y-x).
Then T(P) is the union of
T(P_1) = T(P)/4,
T(P_2) = (T(P)+(3,0))/4,
T(P_3) = (T(P)+(0,3))/4, and
T(P_4) = (T(P)+(3,3))/4,
which is the middle-halves set you describe.

Dan Hoey
haoyuep at aol.com

[mike3]

Hmm. But how does the transform given relate to the function
described?

[Dan Hoey]

The transform describes the inverse of the way in which the
middle-halves set has been "skewed and stretched or rotated"
to form the graph of the function.

[Dan Hoey]

I wrote:
> The transform describes the inverse of the way in which the
> middle-halves set has been "skewed and stretched or rotated"
> to form the graph of the function.

Another way of looking at this is that the middle-halves set
consists of those coefficient pairs (r,s) such that every
digit in the base-4 expansion of r and s is either 0 or 3.
Thus each digit position can be written as (3r_i, 3s_i) where
r_i and s_i are in {0,1}.

When mapped by the inverse transform
U(r,s) = (2r/3 + s/3, 2s/3 + r/3),
each digit position is mapped to x = 2r_i + s_i, y = 2s_i + r_i,
which describes the operation of exchanging pairs of bits of
x to form y.

[mike3]

On Oct 6, 4:09 am, Dan Hoey <haoy...@aol.com> wrote:
> I wrote:
> > The transform describes the inverse of the way in which the

> > middle-halves set has been "skewedand stretched or rotated"

> > to form the graph of the function.
>
> Another way of looking at this is that the middle-halves set
> consists of those coefficient pairs (r,s) such that every
> digit in the base-4 expansion of r and s is either 0 or 3.
> Thus each digit position can be written as (3r_i, 3s_i) where
> r_i and s_i are in {0,1}.
>
> When mapped by the inverse transform
>        U(r,s) = (2r/3 + s/3, 2s/3 + r/3),
> each digit position is mapped to x = 2r_i + s_i, y = 2s_i + r_i,
> which describes the operation of exchanging pairs of bits of
> x to form y.
>

Thanks for the answer.