Cyclic Functions

by nsato, Oct 14, 2010, 7:00 PM

The other day, I was teaching our Algebra 3 class, and one of the topics was using cyclic functions to solve functional equations. (We will also cover functional equations in an upcoming WOOT class.)

[jump]Learn more after the jump![/jump]

A function $f$ is cyclic with order $n$ if
$f^{n}(x) = x,$
where $f^{n}$ denotes the $n^{\text{th}}$ iterate of $f$ , i.e. it is the function obtained when applying the function $f$ $n$ times. For example, the function $f(x) = 1/x$ is cyclic with order 2, because
$f^2(x) = f(f(x)) = f \left( \frac{1}{x} \right) = x.$

The function $f(x) = (x - 1)/x$ is cyclic with order 3, because
$f^2(x) = f(f(x)) = f \left( \frac{x - 1}{x} \right) = \frac{(x - 1)/x - 1}{(x - 1)/x} = -\frac{1}{x - 1},$
and
$f^3(x) = f^2(f(x)) = f^2 \left( \frac{x - 1}{x} \right) = \frac{1}{-(x - 1)/x - 1} = x.$

Note that these equations do not quite hold for all $x$ . For example, $f(x) = 1/x$ is not defined for $x = 0$ . This is typical for most cyclic functions that we deal with - they are defined for all real numbers, except possibly for a finite number of points. So in the definition of a cyclic function, it will be implicit that the equation $f^{n}(x) = x$ holds for all $x$ , except possibly for a finite number of points.

We can use cyclic functions to solve functional equations as follows: For example, let $f(x)$ be a function such that
$3f \left( \frac{1}{x} \right) + \frac{2f(x)}{x} = x^2$
for all $x \neq 0$ . Find $f(x)$ . (This is a generalization of a 1998 HMMT problem.)

We know that the function $1/x$ is cyclic with order 2, which means that if we replace $x$ with $1/x$ , the terms $f(1/x)$ and $f(x)$ switch, and we get
$3f(x) + 2x f \left( \frac{1}{x} \right) = \frac{1}{x^2}.$
We can view these two equations as a system of equations in $f(x)$ and $f(1/x)$ . Solving for $f(x)$ , we find
$f(x) = \frac{3 - 2x^5}{5x^2}.$

We then check this solution. We have that
$f \left( \frac{1}{x} \right) = \frac{3 - 2/x^5}{5/x^2} = \frac{3x^5 - 2}{5x^3},$
so
$3f \left( \frac{1}{x} \right) + \frac{2f(x)}{x} = \frac{3(3x^5 - 2)}{5x^3} + \frac{2(3 - 2x^5)}{5x^3} = \frac{5x^5}{5x^3} = x^2.$
Thus, our solution works.

A student in the class asked if there exist cyclic functions with order $n$ , for any positive integer $n$ . Because the function $f(x) = 1/x$ is cyclic with order 2, it is also cyclic with order $2k$ for any positive integer $k$ , but that's not very interesting. The function $f(x) = x$ is cyclic with order 1, so it is also cyclic with order $k$ for any positive integer $k$ , which is even less interesting.

For a given positive integer $n$ , can you come up with a function $f$ , from the real numbers to the real numbers (except possibly for a finite number of values), that is cyclic with order $n$ , and that does not have any smaller order? In other words, we have to apply $f$ to $x$ $n$ times to get back $x$ . I'm looking for a nice, simple formula, that you could plug into a calculator. I'll post my answer in a few days.

Here is the answer I was thinking of: First, can you think of an "operation" that has order $n$ ? That is, if you perform the operation $n$ times, then you get back what you started with. Furthermore, you have to apply the operation at least $n$ times to get back what you started with.

Here is an example: Take a point $P$ , and a line passing through $P$ . The operation consists of rotating the line around $P$ by a certain angle.

If the angle is 90 degrees, then you get back the same line after two steps. If the angle is 60 degrees, then you get back the same line after three steps. In general, if the angle is $\tfrac{180^\circ}{n}$ , then you get back the same line after $n$ steps.

How do we turn this operation into a function that takes real numbers to real numbers?

We can think of the slope of the line, which can be any real number. If a line makes an angle $\theta$ with the $x$ -axis, then the slope of the line is given by $m = \tan \theta$ . Hence, the operation described above takes a line with slope $\tan \theta$ to a line with slope $\tan (\theta + \tfrac{180^\circ}{n})$ .

By the addition formula for tangent,
$\tan \left( \theta + \frac{180^\circ}{n} \right) = \frac{\tan \theta + \tan \tfrac{180^\circ}{n}}{1 - \tan \theta \tan \tfrac{180^\circ}{n}}.$
Hence, the function
$f(x) = \frac{x + \tan \tfrac{180^\circ}{n}}{1 - (\tan \tfrac{180^\circ}{n}) x}$
has the desired property, i.e. it is cyclic with order $n$ , and it has no smaller order.

This post has been edited 4 times. Last edited by nsato, Nov 19, 2010, 11:59 PM

cyclic functions

math

Comment

3 Comments

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Matrix Idea: There's a known isomorphism between functions of the form $\frac{ax+b}{cx+d}$ (called linear fractional transformations, or LFTs) and two-by-two matrices $\begin{pmatrix} a & b \\ c & d \end{pmatrix}$ . Namely, composing LFTs is like multiplying the corresponding matrices. So to find an LFT that has cyclic order $n$ , we need to find a two-by-two matrix whose $n$ th power is (a multiple of) the identity matrix, but whose earlier powers aren't. One way to come up with such a matrix is to use a rotation matrix $\begin{pmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{pmatrix}$ . Namely, set $\theta$ to $\frac{\pi}{n}$ .

This post has been edited 1 time. Last edited by Ravi B, Oct 22, 2010, 1:16 PM

by Ravi B, Oct 14, 2010, 8:13 PM

Report

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Seems like $f(x) = \lfloor x \rfloor + \{ x + 1/n \}$ will do the trick, with the added benefit of being defined on the entire domain. All the calculator would need would be the floor function since fractional parts can be expressed in terms of those.

This post has been edited 1 time. Last edited by MellowMelon, Oct 15, 2010, 6:31 AM

by MellowMelon, Oct 15, 2010, 6:30 AM

Report

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Neat idea, MellowMelon. After thinking about your example, I hit upon $f(x) = \tan(\tan^{-1}(x) + \frac{\pi}{n})$ . Then I realized that if you apply the tangent addition formula to that function, you get essentially the same example as in my first post. My examples still have the disadvantages of having holes in the domain.

by Ravi B, Oct 15, 2010, 3:59 PM

Report

Art of Problem Solving Blog

Cyclic Functions

by nsato, Oct 14, 2010, 7:00 PM

3 Comments