Thursday, August 25, 2016

The 2016 Rio Olympics

It has been a thrilling Summer Olympics in the last 2 weeks and we enjoyed watching many of the events on TV. While watching the swimming competition, we noticed that Nathan Adrian looks surprisingly similar to Chow Yun Fat (周潤發), especially when he smiles. Chow Yun Fat is one of my favorite Hong Kong actors and I grew up watching him in several TVB TV series, with 北斗雙雄 being my favorite series (having watched it several times over the years). Perhaps they can cast Mr. Adrian when they need to make a biopic of Mr. Chow. 

Another thing during the Olympics that I like is that I can listen to a special CD. Many years ago, (around the 1996 Atlanta Olympics I believe), I took some pictures on film (yes, there used to be such a thing as photographic film) and went to the local drugstore to get them developed. There was a special promotion from Kodak that included a CD titled "The Sound and the Spirit" with music from various Olympic games. Since then I would play this CD every 4 (sometimes 2) years. 

The Hartman-Grobman Linearization Theorem

Theorem: In the neighborhood of a hyperbolic fixed point, a smooth vector field or a diffeomorphism is topologically conjugate to its linear part.

This result was proved by Grobman and Hartman independently around 1959-1960 and basically states that the dynamics near a hyperbolic fixed point is essentially the same as the dynamics of its linearization which we can characterize completely from the eigenvalues pattern.  This is true for both continuous-time dynamics (vector field) or discrete-time dynamics (diffeomorphism).

Here is a sketch of the standard proof for the case of  a diffeomorphism.  First, we need the following simple fact for linear maps in Banach spaces: if $F$ is an invertible contraction, then $I+F^{-1}$ is also invertible. This can be seen as follows. $I+F^{-1} = F^{-1}(I+F)$.  If $I+F$ is not invertible, then there exists $x\neq y$ such that $x+F(x) = y+F(y)$.  This implies that $x-y = F(y)-F(x)$, i.e. $\|x-y\| = \|F(y)-F(x)\|$, contradicting the fact that $F$ is a contraction. Therefore $I+F$ is invertible, and thus $I+F^{-1}$ is invertible since it is the product of two invertible maps.

Consider a diffeomorphism $f$ with a hyperbolic fixed point at $0$. Let $A$ be the linear part of $f$ at $0$.  We want to find a homeomorphism $h = I+\delta$ such that $fh = hA$.  As we are interested only at $f$ near a neighborhood of $0$, we can assume that $f$ can be written as $f = A+\phi_1$ such that $\phi_1$ is bounded and have a small Lipschitz constant.  Furthermore, $\phi_1$ can be chosen small enough such that $A+\phi_1$ is a homeomorphism. Consider the equation $(A+\phi_1)h
= h(A+\phi_2)$.  After using the fact that $h=I+\delta$ and some manipulation, we get the following Eq. (1):
\[\delta - A^{-1}\delta(A+\phi_2) = A^{-1}(\phi_2-\phi_1(I+\delta))
\]
Next we argue that the linear operator $H: \delta \rightarrow \delta - A^{-1} \delta(A+\phi_2)$ is invertible.
By hyperbolicity of $A$, we can decompose the phase space into the stable subspace $W^s$ and the unstable subspace $W^u$. Since $W^s$ and $W^u$ are invariant under $A^{-1}$, if $\delta$ is a bounded function into $W^s$ and $W^u$ then $H(\delta)$ is also a bounded function into $W^s$ and $W^u$ respectively. Split $\delta = \delta^s + \delta^u$ into two functions $\delta^s$ and $\delta^u$ which maps into $W^s$ and $W^u$ respectively.
The map  $\delta^s \rightarrow A^{-1}\delta^s(A+\phi_1)$ is invertible with inverse $\delta^s \rightarrow A \delta^s (A+\phi_1)^{-1}$ since  $A \delta^s (A+\phi_1)^{-1} = A^s\delta^s(A+\phi_1)^{-1}$ the map
$\delta^s \rightarrow A \delta^s (A+\phi_1)^{-1}$ is a contraction and therefore
the map $\delta^s \rightarrow \delta^s - A^{-1}\delta^s(A+\phi_1)$ is invertible based on the fact discussed before. The same thing can be done with the $W^u$ and this implies that $H$ is invertible.

Coming back to Eq. (1) above, we get
\[ \delta = H^{-1}A^{-1}(\phi_2-\phi_1(I+\delta)) = \psi(\delta)\]

For small $\phi_1$ and $\phi_2$, $\psi$ is a contraction and thus for given $\phi_1$ and $\phi_2$ there exists a unique $\delta$ and hence a unique $h$.  It can be shown that $h$ is a homeomorphism and by choosing $\phi_2 = 0$ we get the desired result.

References
D. M. Grobman, "Homeomorphisms of systems of differential equations," Doklady Akademii Nauk SSSR, vol. 128, pp. 880–881, 1959.
P.  Hartman, "A lemma in the theory of structural stability of differential equations," Proc. AMS, vol. 11, no. 4, pp. 610–620, 1960.

Wednesday, August 17, 2016

Rounding the k-th root of n

Consider the problem of finding the $k$-th root of a number $n\geq 0$ and rounding it to the nearest integer, i.e. find $[\sqrt[k]{n}]$, where $[x]$ is $x$ rounded to the nearest integer. This can be easily computed in many computer languages using floating point arithmetic, but care must be taken for large $n$ to ensure enough significant digits are available. On the other hand, languages such as Python has built-in support for integers of arbitrary sizes and will automatically allocate more space to fit the number under consideration. This can be used to compute $[\sqrt[k]{n}]$ using only integer arithmetic without worrying whether there are enough precision in the floating point representation.

Let $i$ be the largest integer such that $i \leq \sqrt[k]{n}$. The number $i$ can be computed using integer arithmetic with an iterative Newton's method.
Since $n \geq 0$, $[\sqrt[k]{n}] = i+1$ if $\sqrt[k]{n}-i \geq \frac{1}{2}$ and $[\sqrt[k]{n}] = i$ otherwise. The condition $\sqrt[k]{n}-i \geq \frac{1}{2}$ is equivalent to $2^k n \geq (2i+1)^k$ which can be computed using integer arithmetic.

A simple python function using the gmpy2 module to implement this is the following:

from gmpy2 import iroot
def round_root(n,k): # round(k-th root of n), n >= 0
    i = iroot(n,k)[0]
    return int(i) + int(2**k*n >= (2*i+1)**k)

The gmpy2 module also includes the functions isqrt_rem and iroot_rem. The function isqrt_rem(n)returns a pair of numbers $i,j$ such that $i$ is the largest integer $\leq \sqrt{n}$ and $j = n-i^2$.
Similarly, iroot_rem(n,k)returns a pair of numbers $i,j$ such that $i$ is the largest integer $\leq \sqrt[k]{n}$ and $j = n-i^k$.
Since
\begin{eqnarray*}(2i+1)^k &=& (2i)^k + (2i+1)^{k-1} + \\
&&(2i+1)^{k-2}2i + \cdots + (2i+1)(2i)^{k-2} + (2i)^{k-1}\end{eqnarray*}
the condition can be rewritten as:
\begin{eqnarray*}2^k j  &\geq &(2i+1)^{k-1} + (2i+1)^{k-2}2i + \cdots + (2i+1)(2i)^{k-2} + (2i)^{k-1}\\ & \geq & \sum_{m=0}^{k-1} (2i+1)^{k-1-m}(2i)^m \end{eqnarray*}
For $k=2$, this is reduced to: $4j \geq 4i + 1$. A python function implementing $[\sqrt{n}]$ is:

from gmpy2 import isqrt_rem
def round_sqrt(n): # round(square root of n), n >= 0
    i, j = isqrt_rem(n)
    return int(i) + int(4*(j-i) >= 1)

Similarly, for $k=3$, the condition is reduced to $8j \geq 6i(2i+1)+1$.