## Friday, January 20, 2017

### Interesting number: 1440000

The number 1440000 satisfies the following equation:

$$1440000^3 - 1 = 1439940^3 + 71999^3 = 1440060^3 - 72001^3$$

By Fermat's Last Theorem (for which the case $n=3$ was proven by Euler), $1440000^3$ cannot be the sum or difference of 2 positive integer cubes. The above equation shows that $1440000^3-1$ is the sum and the difference of 2 positive integer cubes.

## Thursday, January 12, 2017

### March or May?

I looked at the expiration date on a tube of toothpaste today and it said: MA17.  Is it March 2017 or May 2017? There doesn't seem to be a standard 2-digit abbreviation for the English names of months.

### Number of 2 by 2 matrices with all elements in {0,1,..,n} and its permanent equal to the sum of all elements

OEIS sequence A280934 is defined as: $a(n) =$ the number of 2 by 2 matrices with all elements integers in the set $\{0,1,..,n\}$ and its permanent is equal to the sum of all elements.

Consider a 2 by 2 matrix $\left(\begin{array}{cc}a & c \\ d & b\end{array}\right)$. The sum of all elements equal to the permanent is written as $a+b+c+d = ab+cd$. This can be rewritten as $(a-1)(b-1) + (c-1)(d-1) = 2$. In other words, $a(n) =$ the number of 2 by 2 matrices with all elements integers in the set $\{-1,..,n-1\}$ and its permanent is equal to 2. We will consider this alternative formulation in the rest of this note. Suppose $n > 3$ and at least one of members of the matrix has value $n-1$. Let us count how many of such matrices has permanent 2, i.e. $ab+cd = 2$.

First consider the case $a = n-1$. If  $b = -1$, then $cd = n+1$. Note that $c \neq 1$ and $c \neq n+1$ since $-1\leq c,d\leq n-1$. Since $n> 3$, any nontrivial factor of $n+1$ is less than $n-1$. Thus setting $c>1$ equal to any nontrivial factor of $n+1$ and $d = (n+1)/c$ will result in a matrix with permanent 2. Thus there are $\tau(n+1)-2$ such matrices. Here $\tau(n)$ denotes the number of divisors of $n$. If $b = 0$, then $cd = 2$ and there are 2 cases: $(c,d) = (1,2)$ and $(c,d) = (2,1)$. If $b=1$, then $cd = 3-n$ and there are 2 cases as well: $(c,d) = (-1,n-3)$ and $(c,d) = (n-3,-1)$. Note that $cd \geq 1-n$ since $-1\leq c,d\leq n-1$. This means that if $b > 1$ then $ab+cd \geq n-1 > 2$. Thus we have a total of $\tau(n+1)+2$ cases. Note that in all cases, exactly one element of the matrix is of value $n-1$.

By symmetry, the same analysis applies to $b=n-1$, $c=n-1$ and $d=n-1$ as well. Since in all the cases only one element of the matrix is of value $n-1$, there is no double counting. Thus the number of matrices with at least one member equal to $n-1$ and permanent 2 is $4\tau(n+1)+8$. This implies the following recurrence relation for $a(n)$:

$$a(n) = a(n-1) + 4\tau(n+1)+8 \quad\mbox{for}\quad n> 3$$.

## Saturday, November 5, 2016

### "Bots" creating news digests about "bots"

I use a news digest app on my phone to read a selection of important news in areas I selected. This is nice since it only lists news items that I am most likely interested in and saves me time in reading the day's news.  I think the news summary is created automatically via computer algorithms, since many times the highlighted quote does not make sense or is attributed to the wrong person.  In addition, the "to explore further" section sometimes points to unrelated and/or inappropriate Wikipedia articles. Sometimes, this is because the person in the news has the same name as someone who is much more famous, so the Wikipedia article is about the wrong (but more well known) person.

Today, in the "science" section, there is a summary digest article about news organizations utilizing "bots", or automatic algorithms to aggregate data and generate news article. It is quite amusing, since again the highlighted quote is attributed to the wrong person and the "to explore further" section points to a specific news paper and is tangentially related to the news article.

## Wednesday, September 28, 2016

In Chinese slang, the phrase "加油", literally translated as "add oil", means "put more effort" and is typically used as encouragement to try harder in order to succeed at something. I believe the origin come from the fact that we need to add oil (gasoline) to cars in order for it to move. As we are all expected to drive electric or hydrogen cars in the future, this might become an archaic slang in the not too distant future.

After reading this post, my wife asked me what the corresponding Chinese slang should be for electric vehicles. She said that "充電" which is the translation of "charging electricity" is not a good choice since "充電" is slang for "refresh" or "renew" and is typically used when one is tired or drained of energy.

## Tuesday, September 27, 2016

### Continued fraction expansion of the square root of n: part II

In an earlier blog post$\delta(n)$ is defined as the smallest term in the periodic part of the continued fraction of $\sqrt{n}$ and I showed that if $r$ is even then $\delta((\frac{rm}{2})^2+m) = r$ for all $m\geq 1$. and if $r$ is odd, then $\delta((rm)^2+2m) = r$ for all $m\geq 1$. Note that $\delta(n)$ is only defined if $n$ is not a perfect square.

If you look at the first few numbers $n$ that satisfy $\delta(n) = r$, it would appear that they all follow the quadratric equations above. However, not all integers $n$ such that $\delta(n) = r$ are of the forms above. In particular, if $r > 0$ is even, then $\sqrt{\frac{r^4}{4} + r^3 + 2r^2 + 3r + 2} = \sqrt{\frac{(r^2-2)^2}{4}+(r+1)^3}$ has continued fraction expansion $\left[\frac{(r+1)^2+1}{2};\overline{r+1,r,r+1,(r+1)^2+1}\right]$ and thus $\delta\left(\frac{r^4}{4} + r^3 + 2r^2 + 3r + 2\right) = r$ and it is not of the forms above.

Similarly, if $r$ is odd, then $\sqrt{r^4 + r^3 + \frac{5(r+1)^2}{4}}$ has continued fraction expansion $\left[\frac{(r+1)(2r-1)+2}{2};\overline{r,2r-1,r,(r+1)(2r-1)+2}\right]$ and thus $\delta\left(r^4 + r^3 + \frac{5(r+1)^2}{4}\right) = r$ and it is not of the forms above either.

## Wednesday, September 21, 2016

### Paul Erdős and Kevin Bacon

In his famous 1967 paper, Stanley Milgram describes a study he conducted that shows that people are related to each other via a very small of number of acquaintances. This led to the phrase "six degrees of separation" being coined by John Guare in his play of the same name. Mathematicians study a similar concept called Erdős numbers. Two persons are linked if they have co-authored a mathematical paper together and a person's Erdős number is the minimum number of links between him/her and Paul Erdős. Thus Paul Erdős has Erdős number 0, A person other than Erdős who has written a paper with Erdős has Erdős number 1. A person who does not have Erdős number $\leq 1$ and has written a paper with a person with Erdős number 1 will have Erdős number 2, etc.  If you have not written a paper with anyone with a (finite) Erdős number, then your Erdős number is $\infty$.

As a consequence of a drinking game, there is a similar notion among actors, called the Bacon number. Kevin Bacon has Bacon number 0 and the authors who are his co-stars in a movie have Bacon number 1, etc.

The fascinating aspect is that the Erdős number and the Bacon number of most people whose number is finite is relatively small, which is typically referred to as the "small world effect". There are various websites that lets you type in a name and it will attempt to find the Erdős or Bacon number of this person.

There is an additional notion of an Erdős-Bacon number which is the sum of a person's Erdős number and Bacon number. As of now the lowest Erdős-Bacon number appears to be 4.

There is something unsatisfactory about the definition of the Erdős-Bacon number.  In particular, both Paul Erdős and Kevin Bacon have very large (and possibly infinite) Erdős-Bacon number.  As of today, according to this link and this link, Paul Erdős has Bacon number $\infty$ and Kevin Bacon has Erdős number $\infty$.

There is one way to remedy this injustice.  Kevin Bacon should publish a math paper with someone with Erdős number 1 (unfortunately Paul Erdős died in 1996) and starred in a movie with people who appeared in the documentary "N Is a Number: A Portrait of Paul Erdős".  Since several mathematicians in the above documentary have Erdős number 1, both these activities can be combined if  Kevin Bacon makes a documentary of how he collaborated with one (or more) of these mathematicians on a math paper. This will ensure that both  Paul Erdős and Kevin Bacon have Erdős-Bacon number 2 (the lowest possible) and the universe will be in order again.

## 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.