tag:blogger.com,1999:blog-26379284728594538312017-10-10T13:06:11.671-04:00Accidental Desultory CogitationsRandom thoughts on a variety of topics, but mostly on science and technology.Chai Wah Wunoreply@blogger.comBlogger95125tag:blogger.com,1999:blog-2637928472859453831.post-61948037345600438392017-10-10T13:06:00.000-04:002017-10-10T13:06:11.715-04:00The triangle inequality and its converse<h2>The triangle inequality</h2>The triangle inequality is a workhorse in many branches of mathematics. It expresses the subadditivity of norms and is stated as:<br />$$ \| A+B\| \leq \|A\| + \|B\|.$$<br />The name comes from its interpretation on the plane. If $A$ and $B$ are complex numbers, then we can draw a triangle with vertices at the points $0$, $A$ and $A+B$, with the resulting sides having norms equal to $|A|$, $|B|$ and $|A+B|$. Stated in another way, if $a$, $b$ and $c$ are the lengths of the $3$ sides of a triangle, then $a \leq b+c$. This is illustrated in Fig. 1.<br />A slightly different, but clearly equivalent statement is the following: if $a \geq b \geq c \geq 0$ are the lengths of the $3$ sides of a triangle, then $a \leq b+c$. We will use this alternative formulation as it is easier to state and prove the converse and its generalization.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-UUyo-lQaCmA/Wdwj3tfX7HI/AAAAAAAAAlc/LmIaNDApXIgYwmB5VPHURYf2zGliPTdhQCLcBGAs/s1600/triangle1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="207" data-original-width="500" height="132" src="https://3.bp.blogspot.com/-UUyo-lQaCmA/Wdwj3tfX7HI/AAAAAAAAAlc/LmIaNDApXIgYwmB5VPHURYf2zGliPTdhQCLcBGAs/s320/triangle1.png" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;">Fig. 1: Illustration of the triangle inequality and its converse.</div><div class="separator" style="clear: both; text-align: left;"><br /></div><h2>Converse of the triangle inequality on the plane</h2>The converse of the triangle inequality is also true: If $a \geq b \geq c \geq 0$ and $a \leq b+c$, then there exists a triangle whose sides have lengths $a$, $b$ and $c$ respectively. Equivalently this can be restated as: If $a \geq b \geq c \geq 0$ and $a \leq b+c$, then there exists complex numbers $A$, $B$ and $C$ with $|A|=a$, $|B| = b$, $|C| = c$ such that $A+B+C = 0$.<br /><br />The following is a simple construction of this triangle.<br />First we show that $d = \frac{b^2+c^2 - a^2}{2bc}$ satisfies $|d| \leq 1$. This follows from the fact that $d = \frac{(b+c)^2 -a^2-2bc}{2bc} = -1 + \frac{(b+c)^2 - a^2}{2bc} \geq -1$<br />and $d= \frac{(b-c)^2 -a^2+2bc}{2bc} = \frac{(b-c)^2 -a^2}{2bc} + 1\leq 1$.<br />Thus we can choose $\phi = \cos^{-1}(d)$ which satisfies $a^2 = b^2+c^2-2bc\cos (\phi)$ and the <a href="http://mathworld.wolfram.com/LawofCosines.html">law of cosines</a> shows that the triangle with sides of length $b$ and $c$ and angle $\phi$ with have the third side of length $a$. (see Fig. 1).<br /><br /><h2>The generalized triangle inequality and its converse</h2>A simple induction argument generalizes the triangle inequality to the summation of more than 2 quantities:<br />$$\left\| \sum_i^n A_i\right\| \leq \sum_i^n \|A_i\|$$<br />The geometrical interpretation is that if $r_i$ are the lengths of edges of a polygon, then $r_i \leq \sum_{j\neq i} r_j$ or equivalently, if $r_i$ are the lengths of edges of a polygon, and $r_1\geq r_i$, then $r_1\leq \sum_{i > 1}r_i$ (Fig. 2).<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-Q079PAYpCCc/WdwkcDuh5-I/AAAAAAAAAlg/-sAk_pNRpiAAhEPCZ2XwX1_hfqa1u_kNgCLcBGAs/s1600/polygon1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="345" data-original-width="625" height="176" src="https://1.bp.blogspot.com/-Q079PAYpCCc/WdwkcDuh5-I/AAAAAAAAAlg/-sAk_pNRpiAAhEPCZ2XwX1_hfqa1u_kNgCLcBGAs/s320/polygon1.png" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;">Fig. 2: Illustration of the generalized triangle inequality and its converse.</div><div style="text-align: left;"><br /></div>The converse of the generalized triangle inequality is true as well. If $r_1\geq r_i \geq 0$ and $r_1\leq \sum_{i = 2}^n r_i$, then there is a $n$-polygon with $r_i$ as the lengths of its sides (Fig. 2). Having one vertex of the polygon at the origin of the complex plane this can be reformulated as:<br /><br /><b>Lemma 1: </b>(Ref. [1])<br />Let $n\geq 2$ and $r_1\geq r_2\geq \cdots r_n \geq 0$ be real sumbers such that $r_1 \leq \sum_{i=2}^n r_i$, then there exists complex numbers $c_i$ such that $|c_i| = r_i$ and $\sum_i c_i = 0$.<br /><br /><b>Proof: </b><br />As stated in [1] this is easily proved by induction. For $n=2$ this implies that $|r_1| = |r_2|$ and thus we can set $c_1 = r_1 = -c_2$. For $n=3$ this is the converse of the triangle inequality described above. Suppose the Lemma is true for $n = k \geq 3$. Let $n = k+1$, and $s_k = r_k+r_{k+1}$. If $s_k \leq r_1$, then applying the Lemma to $r_1,\cdots r_{k-1}, s_k$ and then splitting $c_k$ into $\frac{r_k}{s_k}c_k$ and $\frac{r_{k+1}}{s_k}c_k$ would prove it for $n=k+1$. If $s_k > r_1$, then $s_k \leq r_1 + r_2 \leq \sum_{i=1}^{k-1} r_k$ and again we can apply the Lemma for $n=k$.<br /><br /> <br />The degenerate case occurs when $r_1 = \sum_{i=2}^n r_i$ in which the resulting polygon must have zero area (Fig. 3). The proof of Lemma 1 also shows that the polygon can be arranged to look like a triangle, i.e. there is a partition of $\{r_i\}$ into $3$ sets $R_1$, $R_2$ and $R_3$ such that $\sum_{r_i\in R_1}r_i \geq \sum_{r_j\in R_2}r_j \geq \sum_{r_k\in R_3}r_k $ and $\sum_{r_i\in R_1}r_i \leq \sum_{r_j\in R_2\cup R_3}r_j $. This is illustrated in Fig. 4.<br /> <br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-jtRhPydn-L0/WdwxP_MzMqI/AAAAAAAAAl0/UAyZJeBnpYQ4Zg2g15QpRXkkYI0JqXy5QCLcBGAs/s1600/line1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="325" data-original-width="616" height="168" src="https://2.bp.blogspot.com/-jtRhPydn-L0/WdwxP_MzMqI/AAAAAAAAAl0/UAyZJeBnpYQ4Zg2g15QpRXkkYI0JqXy5QCLcBGAs/s320/line1.png" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;">Fig. 3: The degenerate polygon when $r_1 = \sum_{i=2}^n r_i$.</div><div class="separator" style="clear: both; text-align: center;"><br /></div><div style="text-align: center;"><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-bDq-l2LR8pA/WdwxdlM0B2I/AAAAAAAAAl4/qQqPwETiaYAUuN7Y5NC7fqNEmdLikpvUgCLcBGAs/s1600/triangle2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="293" data-original-width="603" height="155" src="https://3.bp.blogspot.com/-bDq-l2LR8pA/WdwxdlM0B2I/AAAAAAAAAl4/qQqPwETiaYAUuN7Y5NC7fqNEmdLikpvUgCLcBGAs/s320/triangle2.png" width="320" /></a></div><div style="text-align: center;">Fig. 4: The edges of the polygon can be reordered to form a triangle.</div><div style="text-align: center;"><br /></div><h4>overlapping edges</h4>We have implicitly allowed the possibility that the edges of the polygon may overlap, i.e. the angles of the vertices are allowed to be $0$ (see for example the degenerate case in Fig. 3). The next result shows that we can have up to $n-3$ angles to be either $0$ or $\pi$. <br /><br /><br /><b>Lemma 2: </b>(Ref. [2])<br />Let $r_i$ be real numbers such that $r_1\geq r_2 \geq \cdots \geq r_n \geq 0$ and $r_1 \leq \sum_{i=2}^n r_i$, then there exists $c_i$ such that $|c_i| = r_i$ and $\sum_i c_i = 0$ and either all $c_i$'s are real or $n-2$ of the $c_i$'s are real.<br /><br /><b>Proof:</b><br />We follow the proof in [2]. Select $j\geq 3$ to be the smallest number such that $\sum_{i=3}^j r_i \geq r_1-r_2$. Such an $j$ is possible since $\sum_{i=3}^n r_i \geq r_1-r_2$. Since $r_i\leq r_2$ for $i\geq 3$, this implies that $\sum_{i=3}^j r_i < r_1$ as otherwise $\sum_{i=3}^{j-1} r_i \geq r_1-r_2$. For $k = j+1,\dots n$, if $\sum_{i=3}^{k-1} r_i \leq r_1$, then set $c_k = r_k$, otherwise set $c_k = -r_k$. Ths ensures that $r_1-r_2\leq \sum_{i=3}^k c_i \leq r_1+r_2$ for each $k$ and by the converse of the triangular inequality there exists $c_1$ and $c_2$ with $|c_1| = r_1$ and $|c_2| = r_2$ such that $\sum_i c_i = 0$. Note that in the degenerate case both $c_1$ and $c_2$ are real.<br /><br /><br />The geometric interpretation of this result is that the polygon can be folded into a triangle (possibly with some overlapping edges and angles equals to $0$) as illustrated in Fig. 5 with the edges with lengths $a$ and $b$ being the 2 longest edges.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-0DsoNWluXz8/WdwyXLrI4XI/AAAAAAAAAl8/9s5QvgDWX9MCok_9802RRjyoLqkKDyPpQCLcBGAs/s1600/triangle3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="352" data-original-width="1005" height="112" src="https://1.bp.blogspot.com/-0DsoNWluXz8/WdwyXLrI4XI/AAAAAAAAAl8/9s5QvgDWX9MCok_9802RRjyoLqkKDyPpQCLcBGAs/s320/triangle3.png" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;">Fig. 5: The edges of the polygon can be reordered and folded to form a triangle with the edges with lengths $a$ and $b$ being the longest 2 edges. Some of the edges may be overlapping.</div><div class="separator" style="clear: both; text-align: left;"><br /></div><h2><br />Singularity of matrices</h2>The Levy-Desplanques theorem [3,4] (which is equivalent to Gershgorin's circle criterion [5]) gives a sufficient condition for a complex matrix to be nonsingular:<br /><br /><b>Theorem 1</b><br />The matrix $A = \{a_{ij}\}$ is nonsingular if $|a_{ii}| > \sum_{j\neq i}|a_{ij}|$ for all $i$.<br /><br />This is easily shown by using the generalized triangle inequality. Suppoe $A$ is singular, i.e. $Ax = 0$ for some nonzero vector $x$.<br />Let $i$ be such that $|x_i|\geq |x_j|$ for all $j$. Since $x\neq 0$, this implies that $|x_i| > 0$. Then applying the generalized triangle inequality to $|\sum_{j\neq i}a_{ij}x_j| = |a_{ii}x_i|$ results in:<br />$$ |a_{ii}||x_i| \leq \sum_{j\neq i}|a_{ij}||x_i|$$<br />Dividing both sides by $|x_i|$ shows that it violates the condition that $|a_{ii}| > \sum_{j\neq i}|a_{ij}|$ for all $i$.<br /><br />Similarly, the converse of the triangle inequality can be used to prove the following statement:<br /><br /><b>Theorem 2:</b> (Ref. [1])<br />Let $A$ be a real nonnegative matrix and let $D$ is a nonzero diagonal matrix with nonnegative diagonal elements. If $B=DA$ satisfies $b_{ij}\leq \sum_{k\neq i} b_{kj}$ for all $i$, $j$, there there exists a complex singular matrix $C = \{c_{ij}\}$ with $|c_{ij}| = a_{ij}$.<br /><br />If $d_ia_{ij}\leq \sum_{k\neq i} d_ka_{kj}$ for all $i$, $j$, then Lemma 1 implies that there are $g_{ij}$ with $|g_{ij}| = d_ia_{ij}$ such that $\sum_i{g_{ij}} = 0$.<br />By choosing $c_{ij} = \frac{g_{ij}}{d_i}$ if $d_i \neq 0$ and $c_{ij} = a_{ij}$ if $d_i = 0$, we get a matrix such that $\sum_i d_ic_{ij} = 0$ and $|c_{ij}| = a_{ij}$. Since $D$ is not the zero matrix, this implies that the rows of $\{c_{ij}\}$ are linear dependent, hence $C$ is singular.<br /><br /><br />These results were extended by the Camion-Hoffman theorem [1] which gives necessary and sufficient conditions for a real matrix $A$ such that any complex matrix whose elements have the same norm as the corresponding elements in $A$ is nonsingular. More precisely it is stated as:<br /><br /><b>Theorem 3:</b> (Camion-Hoffman)<br />Let $A = \{a_{ij}\}$ be a real matrix of nonnegative numbers. The following conditions are equivalent:<br /><br /><ol><li>If $C = \{c_{ij}\}$ is a complex matrix with $|c_{ij}| = a_{ij}$ then $C$ is nonsingular.</li><li>If $D$ is a nonzero diagonal matrix with nonnegative diagonal elements, then $B = DA$ contains an entry $b_{ij}$ such that $b_{ij} >\sum_{k\neq i} b_{kj}$.</li><li>There exists a permutation matrix $P$ and a diagonal matrix $D$ with positive diagonal elements such that $B = PAD$ is strictly row sum dominant, i.e. $b_{ii} >\sum_{i\neq j} b_{ij}$.</li></ol><br /><br />If the conditions in Theorem 3 are not satisfied, then there is a candidate matrix $C$ with $|c_{ij}| = a_{ij}$ such that $C$ is singular.<br />Lemma 2 can be used to show that this candidate can be chosen such that each row is real except for possibly two elements.<br /><br /><b>Lemma 3: </b>(Ref. [2])<br />If $B$ is a singular complex matrix, then there exists a singular complex matrix $C$ such that each row has either $0$ or $2$ complex elements and $|b_{ij}| = |c_{ij}|$.<br /><br /><b>Proof:</b><br />Suppose $Bz = 0$. As before, we select $c_{ij} = \frac{b_{ij}z_j}{|z_j|}$ if $z_j\neq 0$ and $c_{ij} = |b_{ij}|$ otherwise, i.e. $\sum_i c_i = 0$. This means that $\sum_i c_{ij}|z_j| = 0$, i.e. $C$ is singular. By Lemma 2, we can replace up to $n-2$ of $c_{ij}$ with real numbers of the same norm. <br /><br />This result is extended in [2] to show that this candidate can be chosen with at most $2$ complex elements:<br /><br /><b>Theorem 4:</b> (Ref. [2])<br />If $B$ is a singular complex matrix, then there exists a singular complex matrix $C$ with either $0$ or $2$ complex elements such that $|b_{ij}| = |c_{ij}|$.<br /><br /><b>References</b><br />[1] P. Camion and A. J. Hoffman, "<a href="https://msp.org/pjm/1966/17-2/pjm-v17-n2-p03-p.pdf">On the nonsingularity of complex matrices</a>," <i>Pacifi c Journal of Mathematics</i>, vol. 17, no. 2, pp. 211-214, 1966.<br />[2] D. Coppersmith and A. J. Hoffman, "<a href="https://doi.org/10.1016/j.laa.2004.03.029">On the singularity of matrices</a>," <i>Linear Algebra and its Applications</i>, vol. 411, pp. 277-280, 2005.<br />[3] L. Lévy, "Sur la possibilité du l'équilibre électrique," <i>C. R. Acad. Sci. Paris</i>, vol. 93, pp. 706-708, 1881.<br />[4] J. Desplanques, "Théorème d'algèbre," <i>J. de Math. Spec.</i>, vol. 9, pp. 12-13, 1887.<br />[5] S. A. Geršgorin, "Über die Abgrenzung der Eigenwerte einer Matrix," <i>Izv. Akad. Nauk SSSR Otd. Fiz.-Mat. Nauk</i>, vol. 7, pp. 749-754, 1931.<br /><br /><br /> <br /><br /> <br /><br /> <br /><br />Chai Wah Wunoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-8521707709229286372017-09-08T23:28:00.000-04:002017-09-08T23:28:26.740-04:00Numbers such that 7 is the smallest decimal digit of their squares.9949370777987917 is the smallest number whose square has as its smallest decimal digit 7.<br />Note that $9949370777987917^2 = 98989978877879888789778997998889$. What is the next such number?Chai Wah Wunoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-40611437103828599982017-07-23T23:02:00.001-04:002017-07-23T23:02:38.726-04:00Solar eclipse 2017On August 21, 2017, there will be a <a href="https://www.space.com/33797-total-solar-eclipse-2017-guide.html">solar eclipse</a> occurring coast to coast across the continental United States. The last time this happened was almost a century ago in 1918. This has two effects on states that generate a lot of solar energy: the solar energy generated decreases during an Eclipse and people turn on their lights as the sky darkens. Both of these events stress the utility grid. California's utilities <a href="http://www.sfgate.com/business/article/Eclipse-plea-from-regulators-Stay-in-the-dark-11307981.php">are asking people not to turn on the lights during this event</a>. I am surprised such a short event (and California is not even in the path of totality) can cause concerns for power utilities operators. I wonder if something similar happens when there is no wind in the summer and more people turn on their fans to cool off?Chai Wah Wunoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-83337018620909083602017-07-17T18:41:00.001-04:002017-07-17T19:33:21.742-04:00Happy Yellow Pig Day!Today, July 17 is <a href="http://holidayinsights.com/other/pigday.htm">Yellow Pig Day</a>. This "holiday" was created by Princeton math students Michael Spivak and David C. Kelly when they were analyzing the number 17 and wanted to have a day to celebrate this number. This year (2017) is extra special since the year also ends in the digits 17.<br />Michael Spivak is the author of the wonderful differential geometry texts (published by Publish-or-Perish Press which he founded) which I fondly remember reading in graduate school. He also wrote a popular typesetting book on TeX which I did not read since Leslie Lamport's book on LaTeX makes typesetting papers using LaTeX so easy that I have skipped learning TeX and went straight to using LaTeX (which sits on top of TeX).<br />If I remember correctly, the typesetting software I used prior to LaTeX was ChiWriter, which is quite easy to use as it is WYSIWYG, so moving to a typesetting paradigm where you relinquish control on the formatting, page breaks, etc. to the software is quite unnerving, but I soon learn to appreciate it as I can focus on the content of the document, rather than spend time improving its appearance.Chai Wah Wunoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-70563981728433430522017-06-04T11:22:00.002-04:002017-06-04T11:40:59.505-04:00Moon and Jupiter on June 3, 2017The Moon and Jupiter are in close proximity (not physically, but as viewed from Earth) on the night of June 3, 2017.<br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-oLd0NjsdKtg/WTQlleG4I_I/AAAAAAAAAkg/nA3yG6rkpEwD-QdFAuEi_Qwk3FphDdvjQCLcB/s1600/Moon%2Band%2BJupiter.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1600" data-original-width="911" height="640" src="https://1.bp.blogspot.com/-oLd0NjsdKtg/WTQlleG4I_I/AAAAAAAAAkg/nA3yG6rkpEwD-QdFAuEi_Qwk3FphDdvjQCLcB/s640/Moon%2Band%2BJupiter.JPG" width="363" /></a></div><br />Chai Wah Wunoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-86717597040703302262017-05-21T10:28:00.002-04:002017-05-21T10:28:41.988-04:00The race of Cloud ComputingI wrote <a href="http://accidentaldesultorycogitations.blogspot.com/2016/11/bots-creating-news-digests-about-bots.html">earlier</a> about a news digest app returning supplemental information which is not directly related to the article. Today, I read on the app that the horse "Cloud Computing" has won the Preakness race. And sure enough, there is a box underneath the article with a definition of cloud computing from Wikipedia. What is ironic is that this news summary is probably enabled by leveraging cloud computing. "Cloud Computing" won over "Classic Empire" by coming in from behind and won the race by a head. Perhaps this is an indication how cloud computing will overtake the classical empire of on premise computing😊.Chai Wah Wunoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-61084621597873111042017-05-11T12:22:00.001-04:002017-05-11T12:22:22.014-04:00Find interesting properties of your favorite numberI created a simple web application where you can enter a positive integer < 10<sup>12 </sup>, wait a few moments and it will return a list of interesting properties about this number. Please give it a try and let me know what you think!<br /><br />To start, please visit: <a href="http://postvakje.pythonanywhere.com/">http://postvakje.pythonanywhere.com/</a>Chai Wah Wunoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-65153458445777302502017-05-07T17:05:00.000-04:002017-05-07T17:35:58.236-04:00Spring is here, pt. 2<div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-yuhesL5GL1U/WQ-LJi0T9xI/AAAAAAAAAkA/xuYzTjU7-rEN1IXeKEBlN6Z1ldA-HLI3wCLcB/s1600/housefinch.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="376" src="https://1.bp.blogspot.com/-yuhesL5GL1U/WQ-LJi0T9xI/AAAAAAAAAkA/xuYzTjU7-rEN1IXeKEBlN6Z1ldA-HLI3wCLcB/s400/housefinch.JPG" width="400" /></a></div><div style="text-align: center;"><br /></div><div style="text-align: center;">House Finch</div><div style="text-align: center;"><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-r2WMmYq3XPY/WQ-LhS9OV8I/AAAAAAAAAkE/KupeRX-htRwWnajF6mrs65y5Ik2NQNC3ACLcB/s1600/chippingsparrow.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="376" src="https://2.bp.blogspot.com/-r2WMmYq3XPY/WQ-LhS9OV8I/AAAAAAAAAkE/KupeRX-htRwWnajF6mrs65y5Ik2NQNC3ACLcB/s400/chippingsparrow.JPG" width="400" /></a></div><div style="text-align: center;"><br /></div><div style="text-align: center;">Chipping Sparrow</div><div style="text-align: center;">My wife says it reminds her of Red from Angry Birds</div>Chai Wah Wunoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-30704029233172138212017-05-02T21:37:00.000-04:002017-05-02T21:37:09.549-04:0012345The number 12345 is interesting as it is a sphenic number (product of 3 distinct primes) and its digit reversal 54321 is also a sphenic number.Chai Wah Wunoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-69731025901704763722017-04-18T19:52:00.000-04:002017-04-18T21:19:32.497-04:00Palindromic primes which are sums of 3 consecutive primes<a href="https://oeis.org/">OEIS</a> sequence <a href="https://oeis.org/A113846">A113846</a> lists palindromic primes $q$ which are the sums of 3 consecutive primes $p_1$, $p_2$, $p_3$ such that $p_2$ is also a palindromic prime.<br /><br /><b>Theorem</b>: All terms of A113846 have an odd number of digits and the first digit (and last digit) is either 3 or 9. In addition, $p_2$ and $p_3$ have the same first digit and $p_2$ and $p_3$ have the same number of digits as $q$. The first digit of $p_2$ (and $p_3$) is equal to the first digit of $q$ divided by 3, i.e. if the first digit of $q$ is $3$, then the first digit of $p_2$ and $p_3$ is $1$.<br /><br /><b>Proof</b>: First note that all palindromes with an even number of digits is divisible by 11. Let $p_1$, $p_2$, $p_3$ be 3 consecutive primes such that $p_2$ is a palindrome and $q = p_1+p_2+p_3$ is a palindromic prime. It is clear that $q, p_2 > 11$ and have a odd number of digits since the first term of A113846 is 31513.<br />The first digit of $p_2$ cannot be 2 since $p_2$ is odd. Next we show that the first digit of $p_2$ is either 1 or 3.<br />Let $k$ be an even integer such that $p_2$ has $k+1$ digits. Suppose the first digit of $p_2$ is 4 or larger, i.e. $4\cdot 10^k \leq p_2 < 10^{k+1}$. Then by <a href="https://en.wikipedia.org/wiki/Bertrand%27s_postulate">Bertrand's postulate</a> (or Bertrand-Chebyshev theorem), $p_1\geq \frac{p_2}{2}$ and $p_3 \leq 2p_2$. This implies that $10^{k+1} > p_1 \geq 2\cdot 10^k$, $4\cdot 10^k < p3 \leq 2\cdot 10^{k+1}$ and thus $10^{k+1} < q < 4\cdot 10^{k+1}$, i.e. $q$ has an even number of digits, a contradiction.<br />Next we show that the first digit of $q$ is 3 or 9. To do this, we need a stronger result than Bertrand's postulate for the prime gap. Since $p_2 > 647$, Rohrback and Weis's 1964 result [1] shows that $p_1 \geq \frac{12}{13}p_2$ and $p_3 \leq \frac{14}{13}p_2$.<br />This shows that $2\frac{12}{13} p_2 \leq q \leq 3\frac{1}{13} p_2$. Since $q$ is prime, it cannot start with the digit 5. If $p_2$ start with the digit 1, then $2\cdot 10^k \leq q \leq 6 \frac{2}{13} 10^k$ and thus $q$ must start with the digit 3.<br />If $p_2$ start with the digit 3, then $8\frac{10}{13}10^k \leq q \leq 12\frac{4}{13}10^k$. Since $q < 10^{k+1}$, this means that $q$ must start with the digit 9.<br />Clearly $p_3$ must have the same number of digits as $p_2$ and as $q$.<br />Finally, we show that $p_3$ has the same starting digit as $p_2$. Suppose $p_2$ starts with the digit 1. If $p_3$ has a different starting digit, this must mean that $p_3 \geq 2\cdot 10^k$, i.e.<br />$p_2 \geq 1\frac{11}{13}10^k$, $p_1\geq 1\frac{119}{169} 10^k$ and $q \geq 4\cdot 10^k$, a contradiction.<br />Suppose $p_2$ start with the digit 3. If $p_3$ has a different starting digit, this must mean that $p_3 \geq 4\cdot 10^k$, i.e.<br />$p_2 \geq 3\frac{9}{13} 10^k$, $p_1 \geq 3\frac{69}{169}10^k$ and $q\geq 10^{k+1}$, a contradiction. QED<br /><br />This argument also shows that to search for terms, for each $k$, one only needs to consider for $p_2$ the palindromic primes in the ranges $(10^k, 1\frac{7}{19}10^k)$ and $(3\cdot 10^k, 3 \frac{8}{19}\cdot 10^k)$ which amount to approximately $0.79\cdot 10^{\frac{k}{2}}$ palindromes to consider rather than a full search of $10\cdot 10^{\frac{k}{2}}$ palindromes of length $k+1$.<br /><br /><b>Conjecture</b>: For all terms in A113846, the corresponding primes $p_1$ has the same number of digits and the same first digit as $p_2$ and $p_3$.<br /><br /><b>References:</b><br />1. H. Rohrback and J. Weis, "Zum finiten Fall des Bertrandschen Postulats", J. Reine Angew. Math., 214/215 (1964), 432–440.<br /><br />Chai Wah Wunoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-39472009756355315752017-03-30T20:50:00.001-04:002017-03-30T20:50:24.877-04:00Spring is hereIt is amazing how a couple of days of sunshine and warmer weather erased most of the evidence that we had a major winter storm 2 weeks ago.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-GR1LfKdlXAI/WN2nozspfzI/AAAAAAAAAjk/kR3H46NBluwWjJMmhGEvhFqta7VfdalBACLcB/s1600/mourning%2Bdove.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="258" src="https://2.bp.blogspot.com/-GR1LfKdlXAI/WN2nozspfzI/AAAAAAAAAjk/kR3H46NBluwWjJMmhGEvhFqta7VfdalBACLcB/s400/mourning%2Bdove.JPG" width="400" /></a></div><br />Chai Wah Wunoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-32122408108750276142017-03-15T19:29:00.000-04:002017-03-15T19:32:57.894-04:00Winter storm Stella<div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-x6FUNcvXv5s/WMnPHZl5dlI/AAAAAAAAAjI/MVhsdRbCsWEH7HK0gE98Pe2dUYevG0w-ACLcB/s1600/winterstormstella.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="276" src="https://1.bp.blogspot.com/-x6FUNcvXv5s/WMnPHZl5dlI/AAAAAAAAAjI/MVhsdRbCsWEH7HK0gE98Pe2dUYevG0w-ACLcB/s640/winterstormstella.JPG" width="640" /></a></div><br />Chai Wah Wunoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-42726732514805362017-03-14T00:30:00.000-04:002017-03-14T09:53:16.039-04:00Pi Day 2017Happy Pi day (and a snowy one in the Northeastern US)! One of the early childhood mathematical memories I had was learning that <span style="background-color: white;">π</span> can be approximated by 22/7 and accurate up to 2 decimal places, a fact that was known since antiquity. In particular, Archimedes gave the first <a href="https://en.wikipedia.org/wiki/Proof_that_22/7_exceeds_%CF%80">proof</a> that 22/7 is strictly larger than <span style="background-color: white;">π. The fifth century Chinese mathematician and astronomer </span><a href="https://en.wikipedia.org/wiki/Zu_Chongzhi">Zu Chongzhi</a> gave the approximation <a href="https://en.wikipedia.org/wiki/Mil%C3%BC">355/113</a> that is accurate up to 6 decimal places. Today, sophisticated algorithms using Ramanujan's formula and its variants can compute<a href="http://www.numberworld.org/misc_runs/pi-12t/"> <span style="background-color: white;">trillions of digits of </span></a><span style="background-color: white;"><a href="http://www.numberworld.org/y-cruncher/">π</a>.</span>Chai Wah Wunoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-58410116509383636222017-03-09T20:46:00.000-05:002017-03-09T20:46:46.909-05:00Binomial coefficientsWhen studying binomial coefficients and how they form Pascal's Triangle, we learn that they are the coefficients of $(x+y)^n$, i.e.<br /><div>$$(x+y)^n = \sum_{k=0}^n \left(\begin{array}{c}n\\k\end{array}\right)x^ky^{n-k}$$</div><div>Replacing $y$ with $-y$ we get:</div><div>$$(x-y)^n = \sum_{k=0}^n -1^k\left(\begin{array}{c}n\\k\end{array}\right)x^{n-k}y^{k}$$</div><div><br /></div><div>For example, the coefficients of $(x+y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4$ are 1,4,6,4,1 which form the 5th row of Pascal's triangle.</div><div><br /></div><div>What happens if the coefficients of the polynomial are repeated binomial coefficients such as 1,1,4,4,6,6,4,4,1,1? What is $$\sum_{k=0}^{2n+1} \left(\begin{array}{c}n\\\lfloor k/2\rfloor\end{array}\right)x^ky^{n-k}?$$</div><div><br /></div><div>It is easy to show that this is equal to $y(x^2+y^2)^n + x(x^2+y^2)^n = (x+y)(x^2+y^2)^n$.</div><div><br /></div><div>What about repeating coefficients with sign changes such as 1,1,-4,-4,6,6,-4,-4,1,1?</div><div>The same argument shows that </div><div><br /></div><div>$$\sum_{k=0}^{2n+1} -1^{\lfloor k/2\rfloor}\left(\begin{array}{c}n\\\lfloor k/2\rfloor\end{array}\right)x^{n-k}y^{k}$$</div><div><br /></div><div>is equal to $y(x^2-y^2)^n + x(x^2-y^2)^n = (x+y)(x^2-y^2)^n$ which can be further simplified as $(x+y)^{n+1}(x-y)^n$.</div><div><br /></div><div>If we now change the sign of every other coefficient as well, i.e. 1,-1,-4,4,6,-6,-4,4,1, -1,</div><div>we get </div><div><br /></div><div>$$\sum_{k=0}^{2n+1} -1^{\lfloor k/2\rfloor+n-k}\left(\begin{array}{c}n\\\lfloor k/2\rfloor\end{array}\right)x^{n-k}y^{k}$$</div><div><br /></div><div>This can be shown to be equal to $x(x^2-y^2)^n -y(x^2-y^2)^n = (x-y)(x^2-y^2)^n$ which is equal to $(x-y)^{n+1}(x+y)^n$.</div><div><br /></div><div>We can repeat the coefficients more than 2 times as well and show that</div><div><br /></div><div> $$\sum_{k=0}^{m(n+1)-1} \left(\begin{array}{c}n\\\lfloor k/m\rfloor\end{array}\right)x^ky^{n-k}$$</div><div><br /></div><div>is equal to $\sum_{t=0}^{t=m-1}x^ty^{m-1-t}(x^m+y^m)^n$.</div><div><br /></div><div><br /></div>Chai Wah Wunoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-61029137528646240052017-01-20T11:12:00.000-05:002017-01-20T12:12:35.823-05:00Interesting number: 1440000The number 1440000 satisfies the following equation:<br /><br />$$1440000^3 - 1 = 1439940^3 + 71999^3 = 1440060^3 - 72001^3$$<br /><br />By <a href="https://en.wikipedia.org/wiki/Fermat%27s_Last_Theorem">Fermat's Last Theorem</a> (for which the <a href="https://en.wikipedia.org/wiki/Proof_of_Fermat's_Last_Theorem_for_specific_exponents">case $n=3$</a> 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.<br /><br />Chai Wah Wunoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-12204631500289172222017-01-12T19:53:00.002-05:002017-01-12T19:53:56.958-05:00March 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.<br />Chai Wah Wunoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-25059927377696524382017-01-12T13:56:00.001-05:002017-01-12T13:58:48.605-05:00Number of 2 by 2 matrices with all elements in {0,1,..,n} and its permanent equal to the sum of all elementsOEIS sequence <a href="https://oeis.org/A280934">A280934</a> 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.<br /><br />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$. <br /><br />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$.<br /><br />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)$:<br /><br />$$a(n) = a(n-1) + 4\tau(n+1)+8 \quad\mbox{for}\quad n> 3$$.Chai Wah Wunoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-40120328163078687292016-11-18T19:37:00.000-05:002016-11-18T19:37:07.745-05:00Transistor radiosI was listening to Van Morrison's classic hit "Brown Eyed Girl" and the line about transistor radios always appeals to me as I am fascinated by how song lyrics capture science and technology of the era. Another example is the song "Kodachrome" by Paul Simon and I have written about fractals in the song "Frozen" in an earlier <a href="http://accidentaldesultorycogitations.blogspot.com/2014/03/fractals-in-fairy-tale.html">post</a>. When I was younger, I built a <a href="https://en.wikipedia.org/wiki/Crystal_radio">crystal radio receiver</a> and was amazed that I can listen to AM radio stations with a device that has no external power source and is powered solely by the energy in the radio waves! I also had a vintage transistor radio that is shaped like a pack of Marlboro cigarettes and powered by a 9V battery. The potentiometers for volume and channel have such a satisfying feel. The transistor radio was born as transistors have supplanted vacuum tubes in the demodulation and amplification circuitry of a radio receiver, resulting in portable receivers that are much smaller and use much less power. Today, portable radios are so much smaller and is packed with integrated circuits as more signal processing is done in the digital domain. The goal of software defined radio (<a href="https://en.wikipedia.org/wiki/Software-defined_radio">SDR</a>) is to replace all analog signal processing with digital signal processing done by computer algorithms by moving the analog to digital (A/D) conversion as early as possible. However, current computer processors and A/D converters do not have the speed and bandwidth to process digital samples at RF frequencies, so some analog processing is still done in SDR to demodulate the signals to intermediate frequencies or baseband frequencies. So the transistor is still necessary in radios today. But then again, even if the ideal SDR, where all processing is done by software, is possible, since computer processors today are still filled with transistors, technically the term "transistor radios" will be here to stay for a long time!Chai Wah Wunoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-20070052762143178362016-11-05T21:24:00.000-04:002016-11-05T21:24:03.107-04:00"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.<br /><br />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. Chai Wah Wunoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-86424883132760183842016-09-28T19:24:00.000-04:002016-10-04T22:18:20.416-04:00Add oilIn Chinese slang, the phrase "<span style="background-color: white; color: #2c353c; font-family: "source sans pro" , "helvetica neue" , "helvetica" , "roboto" , "arial" , sans-serif; font-size: 16px;">加油</span><span style="background-color: white; color: #2c353c; font-family: "source sans pro" , "helvetica neue" , "helvetica" , "roboto" , "arial" , sans-serif; font-size: 16px;">"</span><span style="background-color: white; color: #2c353c;"><span style="font-family: inherit;">, 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. </span></span><br /><span style="background-color: white; color: #2c353c;"><span style="font-family: inherit;"><br /></span></span><span style="background-color: white; color: #2c353c;"><span style="font-family: inherit;"><b>Addendum: October 4, 2016</b></span></span><br /><span style="background-color: white; color: #2c353c;"><span style="font-family: inherit;">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 </span></span><span style="background-color: white; color: #2c353c;">"充電" is slang for "refresh" or "renew" and is typically used when one is tired or drained of energy.</span>Chai Wah Wunoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-24666791543715700282016-09-27T20:26:00.000-04:002016-09-28T18:20:58.207-04:00Continued fraction expansion of the square root of n: part II<span style="font-family: inherit;">In an earlier blog <a href="http://accidentaldesultorycogitations.blogspot.com/2016/06/continued-fraction-expansion-of-square.html">post</a>, <span style="background-color: white; color: #333333;">$\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.</span></span><br /><span style="font-family: inherit;"><span style="background-color: white; color: #333333;"><br /></span></span>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.<br /><br />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.<br /><br /><br />Chai Wah Wunoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-49135318896459994322016-09-21T21:53:00.001-04:002016-10-04T22:02:58.796-04:00Paul Erdős and Kevin BaconIn his famous 1967 paper, <a href="https://en.wikipedia.org/wiki/Stanley_Milgram">Stanley Milgram</a> 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 "<a href="https://en.wikipedia.org/wiki/Six_Degrees_of_Separation_(play)">six degrees of separation</a>" being coined by <a href="https://en.wikipedia.org/wiki/John_Guare">John Guare</a> in his play of the same name. Mathematicians study a similar concept called <a href="https://en.wikipedia.org/wiki/Erd%C5%91s_number">Erdős numbers</a>. 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$.<br /><br />As a consequence of a drinking game, there is a similar notion among actors, called the <a href="https://en.wikipedia.org/wiki/Six_Degrees_of_Kevin_Bacon">Bacon number</a>. <a href="https://en.wikipedia.org/wiki/Kevin_Bacon">Kevin Bacon</a> has Bacon number 0 and the authors who are his co-stars in a movie have Bacon number 1, etc.<br /><br />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 "<a href="https://en.wikipedia.org/wiki/Small-world_experiment">small world effect</a>". 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.<br /><br />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 <a href="https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Bacon_number">4</a>.<br /><br />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 <a href="https://oracleofbacon.org/">link</a> and this <a href="http://www.ams.org/mathscinet/collaborationDistance.html">link</a>, Paul Erdős has Bacon number $\infty$ and Kevin Bacon has Erdős number $\infty$. <br /><br />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 "<a href="https://en.wikipedia.org/wiki/N_Is_a_Number:_A_Portrait_of_Paul_Erd%C5%91s">N Is a Number: A Portrait of Paul Erdős</a>". 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.<br /><br />So Mr. Bacon, if you are reading this, please make that your next project!Chai Wah Wunoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-76077701111422781552016-08-25T23:24:00.001-04:002016-08-25T23:24:56.912-04:00The 2016 Rio OlympicsI<span style="background-color: white; font-family: inherit;">t 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 (<span style="line-height: 18.48px;">周潤發)</span><span style="line-height: 18.48px;">, especially when he smiles. </span>Chow Yun Fat is <span style="line-height: 18.48px;">one of my favorite Hong Kong actors and I grew up watching him in several TVB TV series, with </span><span style="line-height: 22.4px;">北斗雙雄 </span><span style="line-height: 22.4px;">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. </span></span><br /><span style="background-color: white;"><span style="font-family: inherit;"><span style="line-height: 22.4px;"><br /></span></span><span style="font-family: inherit;"><span style="line-height: 22.4px;">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. </span></span></span>Chai Wah Wunoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-65196330424316951792016-08-25T20:03:00.001-04:002016-08-25T20:08:25.728-04:00The Hartman-Grobman Linearization Theorem<i>Theorem</i>: In the neighborhood of a hyperbolic fixed point, a smooth vector field or a diffeomorphism is topologically conjugate to its linear part.<br /><br />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).<br /><br />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.<br /><br />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<br />= h(A+\phi_2)$. After using the fact that $h=I+\delta$ and some manipulation, we get the following Eq. (1):<br />\[\delta - A^{-1}\delta(A+\phi_2) = A^{-1}(\phi_2-\phi_1(I+\delta))<br />\]<br />Next we argue that the linear operator $H: \delta \rightarrow \delta - A^{-1} \delta(A+\phi_2)$ is invertible.<br />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.<br />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<br />$\delta^s \rightarrow A \delta^s (A+\phi_1)^{-1}$ is a contraction and therefore<br />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.<br /><br />Coming back to Eq. (1) above, we get<br />\[ \delta = H^{-1}A^{-1}(\phi_2-\phi_1(I+\delta)) = \psi(\delta)\]<br /><br />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.<br /><br /><b>References</b><br />D. M. Grobman, "Homeomorphisms of systems of differential equations," Doklady Akademii Nauk SSSR, vol. 128, pp. 880–881, 1959.<br />P. Hartman, "A lemma in the theory of structural stability of differential equations," Proc. AMS, vol. 11, no. 4, pp. 610–620, 1960.Chai Wah Wunoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-85169336555576987322016-08-17T22:48:00.000-04:002016-08-17T22:48:06.426-04:00Rounding the k-th root of nConsider 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.<br /><br />Let $i$ be the largest integer such that $i \leq \sqrt[k]{n}$. The number $i$ can be <a href="https://gmplib.org/manual/Nth-Root-Algorithm.html#Nth-Root-Algorithm">computed</a> using integer arithmetic with an iterative Newton's method.<br />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.<br /><br />A simple python function using the <a href="https://pypi.python.org/pypi/gmpy2">gmpy2</a> module to implement this is the following:<br /><br /><span style="font-family: "courier new" , "courier" , monospace;">from gmpy2 import iroot</span><br /><span style="font-family: "courier new" , "courier" , monospace;">def round_root(n,k): # round(k-th root of n), n >= 0</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> i = iroot(n,k)[0]</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> return int(i) + int(2**k*n >= (2*i+1)**k)</span><br /><span style="font-family: "courier new" , "courier" , monospace;"><br /></span>The gmpy2 module also includes the functions <span style="font-family: "courier new" , "courier" , monospace;">isqrt_rem</span> and <span style="font-family: "courier new" , "courier" , monospace;">iroot_rem. </span><span style="font-family: inherit;">The function </span><span style="font-family: "courier new" , "courier" , monospace;">isqrt_rem(n)</span><span style="font-family: inherit;">returns a pair of numbers $i,j$ such that $i$ is the largest integer $\leq \sqrt{n}$ and $j = n-i^2$.</span><br />Similarly, <span style="font-family: "courier new" , "courier" , monospace;">iroot_rem(n,k)</span>returns a pair of numbers $i,j$ such that $i$ is the largest integer $\leq \sqrt[k]{n}$ and $j = n-i^k$.<br />Since<br />\begin{eqnarray*}(2i+1)^k &=& (2i)^k + (2i+1)^{k-1} + \\<br />&&(2i+1)^{k-2}2i + \cdots + (2i+1)(2i)^{k-2} + (2i)^{k-1}\end{eqnarray*}<br />the condition can be rewritten as:<br />\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*}<br />For $k=2$, this is reduced to: $4j \geq 4i + 1$. A python function implementing $[\sqrt{n}]$ is:<br /><br /><span style="font-family: "courier new" , "courier" , monospace;">from gmpy2 import isqrt_rem</span><br /><span style="font-family: "courier new" , "courier" , monospace;">def round_sqrt(n): # round(square root of n), n >= 0</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> i, j = isqrt_rem(n)</span><br /><span style="font-family: "courier new" , "courier" , monospace;"> return int(i) + int(4*(j-i) >= 1)</span><br /><span style="font-family: "courier new" , "courier" , monospace;"><br /></span><span style="font-family: inherit;">Similarly, for $k=3$, the condition is reduced to $8j \geq 6i(2i+1)+1$.</span>Chai Wah Wunoreply@blogger.com0