User ken fan - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T04:00:59Z http://mathoverflow.net/feeds/user/7434 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/77279/movies-about-mathematics-mathematicians/77327#77327 Answer by Ken Fan for Movies about mathematics/mathematicians Ken Fan 2011-10-06T04:26:51Z 2011-10-06T04:26:51Z <p>Agora (2009) starring Rachel Weisz as Hypatia.</p> <p>Directed by Alejandro Amenabar, this film contains the best depiction of what it is like to do mathematics that I have seen in a movie. It's also beautifully filmed.</p> <p>Spoiler alert! Stop reading now if you plan to see the movie.</p> <p>--</p> <p>The writers chose to (very likely!) bend facts by suggesting that Hypatia deduced that planets orbit in ellipses just before she was stoned to death. Her struggle, however, to solve this problem is given in vignettes stretching over a significant period of time culminating in a great Aha! moment.</p> http://mathoverflow.net/questions/62820/pythagorean-5-tuples/62880#62880 Answer by Ken Fan for Pythagorean 5-tuples Ken Fan 2011-04-25T02:23:37Z 2011-04-25T02:36:54Z <p>In the early 90s, I took a class from Victor Kac and in it, he explained a very beautiful way of generating all the primitive solutions for the Pythagorean equation for a sum of $n-1$ perfect squares is equal to a perfect square where $n$ can be 3, 4, 5, ..., 10. Unfortunately, I do not know where in the literature this is described in detail. It might be in his Infinite Dimensional Lie Algebras book, but I don't know.</p> <p>The idea is to realize the solutions as the isotropic roots for a certain root system.</p> <p>Consider the lattice ${\Bbb Z}^n$ with bilinear form $-x_0y_0 + x_1y_1 + \cdots + x_{n-1}y_{n-1}$ and standard basis $v_0$, $v_1$, $v_2$, \dots, $v_{n-1}$.</p> <p>Change basis to:</p> <p>$\alpha_1 = v_1 - v_2$, $\alpha_2 = v_2 - v_3$, \dots, $\alpha_{n-2} = v_{n-2} - v_{n-1}$, and $\alpha_{n-1} = v_{n-1}$.</p> <p>If $n \geq 4$, let $\alpha_n = -v_0 - v_1 - v_2 - v_3$.</p> <p>If $n=3$, let $\alpha_n = -v_0 - v_1 - v_2$.</p> <p>The corresponding Cartan matrix $a_{ij} = \frac{2(\alpha_i, \alpha_j)}{(\alpha_i, \alpha_i)}$ is represented by the diagram: <img src="http://www.girlsangle.org/images/MO_042511_g01.jpg" alt="alt text"></p> <p>Then the set of primitive solutions to the equation $x_0^2 = x_1^2 + x_2^2 + \cdots + x_{n-1}^2$ is the orbit under the corresponding Coxeter group of $(1, 1, 0, \dots, 0)$ if $n &lt; 10$. If $n=10$, then you have to add the orbit $(3, 1, 1, 1, \dots, 1)$ to get them all.</p> <p>One doesn't need the theoretical machinery to prove the result. One can just construct the matrices and use a descent argument to show that it works.</p> <p>For the Pythagorean triple case, for instance, you take the orbit of the vector $(1, 1, 0)$ under the action of the group generated by the matrices:</p> <p><code>$$\begin{pmatrix} 1 &amp; 0 &amp; 0 \\ 0 &amp; 0 &amp; 1\\ 0 &amp; 1 &amp; 0 \end{pmatrix},$$</code></p> <p><code>$$\begin{pmatrix} \pm 1 &amp; 0 &amp; 0 \\ 0 &amp; \pm 1 &amp; 0 \\ 0 &amp; 0 &amp; \pm 1 \end{pmatrix},$$</code> and</p> <p><code>$$\begin{pmatrix} 3 &amp; 2 &amp; 2 \\ 2 &amp; 1 &amp; 2 \\ 2 &amp; 2 &amp; 1 \end{pmatrix}.$$</code></p> <p>For $n=4$, you can use the matrices that permute the appropriate variables, change the sign of any variable, and the following:</p> <p><code>$$\begin{pmatrix} 2 &amp; 1 &amp; 1 &amp; 1 \\ 1 &amp; 0 &amp; 1 &amp; 1 \\ 1 &amp; 1 &amp; 0 &amp; 1 \\ 1 &amp; 1 &amp; 1 &amp; 0 \end{pmatrix}.$$</code></p> <p>I'm sorry I cannot give a reference to the literature...I hope someone else is able to.</p> http://mathoverflow.net/questions/59003/occurrences-of-a-simple-reflection-in-the-longest-element-of-a-weyl-group/59037#59037 Answer by Ken Fan for Occurrences of a simple reflection in the longest element of a Weyl group? Ken Fan 2011-03-21T04:50:06Z 2011-03-21T04:50:06Z <p>First, I'll show that you can assume that $ws_nw'$ is a reduced product.</p> <p>To see this, first note that if we multiply $s_n$ by a reduced expression for $w'$, the result will still be reduced, and this can then be extended to a reduced expression for the longest element by multiplying some reduced expression $s_{i_1} \cdots s_{i_k}$ on the left, where $k$ is $1 + l(w')$ less than the length of the longest element...although, as of yet, we don't know that none of the $i_p$ are equal to $n$.</p> <p>But then $s_{i_1} \cdots s_{i_k} s_nw' = ws_nw'$ so that $s_{i_1} \cdots s_{i_k} = w$. By the nature of the braid relations, any simple reflection that appears in $s_{i_1} \cdots s_{i_k}$ must appear in any expression for $w$, so if $s_n$ appears in $s_{i_1} \cdots s_{i_k}$, then it must also appear in $w$, which is a contradiction.</p> <p>So, if we have your expression $ws_nw'$, we then in fact have a reduced expression for the longest element that has only a single occurrence of $s_n$.</p> <p>Now consider any positive root $\alpha$ that has a nonzero coefficient on the simple root $\alpha_n$ corresponding to $s_n$ and also satisfies $w_0 \alpha = -\alpha$.</p> <p>Claim: $\alpha$ must go negative at the location of $s_n$ in our reduced expression.</p> <p>Proof: As you apply the simple reflections in our reduced expression one by one to $\alpha$, the only simple reflection that can affect the coefficient of $\alpha_n$ is $s_n$, and so when you get to $s_n$, the simple reflection $s_n$ must negate the coefficient of $\alpha_n$ (for otherwise $w_0 \alpha$ could not be equal to $-\alpha$). (That is, if $s_n$ just nullified the coefficient on $\alpha_n$, because $s_n$ doesn't occur again, one could not end up at $-\alpha$ after all the simple reflections in the reduced expression for $w_0$ have been applied.)</p> <p>In every case except for type A, there are at least two such $\alpha$...for instance, you can take the sum of the simple roots and the highest root. But they cannot both go negative at the occurrence of $s_n$ in our reduced expression for $w_0$!</p> <p>Therefore, no such expression exists except in type A.</p> <p>And then in type A, there's the expression 1 21 321 4321 ... n (n-1) (n-2) ... 321.</p> http://mathoverflow.net/questions/50876/how-many-edge-disjoint-paths-go-from-upper-left-to-lower-right-in-a-4-times-n How many edge-disjoint paths go from upper left to lower right in a $4 \times N$ rectangular gridwork of streets? Ken Fan 2011-01-01T18:35:46Z 2011-01-08T05:58:55Z <h2>Background/Motivation</h2> <p>My interest in this problem traces back to an 11 year old girl who really took to one-way path counting problems. After doing several configurations of streets, she decided to come up with a problem of her own. She presented a $3 \times 3$ gridwork of two-way streets (forming 4 blocks in a $2 \times 2$ arrangement) and added the condition that a street could be traversed at most once. She asked how many such paths are there from upper left to lower right? (Answer: 16.)</p> <p>Stirred by her enthusiasm, we tried generalizing in various directions. If you have 2 long horizontal streets with $N$ verticals, and let $a_N$ be the number of edge-disjoint paths from upper left to lower right and $b_N$ be the number of edge-disjoint paths from upper left to upper right, then $a_{N+1} = b_{N+1} = a_N + b_N$ for $N > 1$ and $a_1 = b_1 = 1$.</p> <p>The $3 \times N$ case is trickier, but the number of edge-disjoint paths from upper left to lower right still satisfies a finite linear recurrence relation.</p> <p>Naturally, I turned to OEIS and found sequences A013991-A013997, where Dan Hoey gives the number of edge-disjoint paths between opposite corners of $K \times N$ grids for $K = 3, 4, 5, ..., 9$ and small $N$. He also provides the first few values for the $N \times N$ cases (sequence A013990). (Note, his numbering counts blocks, not streets.) For $K=3$, he provides a generating function. In a recent communication, he explained the computer algorithm he used to compute the values but indicates that he did not find a recurrence relation for these sequences, so as far as I know, there is no known way to determine the answer to the title question for large $N$. </p> <p>I've also spoken with Gregg Musiker, Bjorn Poonen, and Tim Chow about this problem. Although none knew how to do the $4 \times N$ case, Gregg simplified my recurrence relations for the $3 \times N$ case, Bjorn suggested many related questions and suggested an asymptotic formula for the $N \times N$ case, and Tim suggested looking at the related literature on self-avoiding walks, such as the book by Neal Madras and Gordon Slade, though it's not clear to me how related edge-disjoint and self-avoiding are with respect to counting them.</p> <p>Because there are finite linear recurrence relations for the $2 \times N$ and $3 \times N$ cases, it seems natural to also ask:</p> <blockquote> <p>Is there a finite linear recurrence relation for the number of edge-disjoint paths between opposite corners of a $4 \times N$ gridwork of streets?</p> </blockquote> <p>Are these problems intractable?</p> http://mathoverflow.net/questions/50538/good-ways-to-engage-in-mathematics-outreach/50547#50547 Answer by Ken Fan for Good ways to engage in mathematics outreach? Ken Fan 2010-12-28T07:30:16Z 2010-12-28T07:30:16Z <p>There are a number of people who explain mathematics through videos and then post them on a widely used video viewing site such as YouTube. The Khan Academy (which got the notice of Bill Gates and Google) is a good example of this.</p> http://mathoverflow.net/questions/47952/proving-interesting-theorems-about-s-n-using-its-character-table/47995#47995 Answer by Ken Fan for Proving interesting theorems about S_n using its character table. Ken Fan 2010-12-02T03:58:06Z 2010-12-02T05:11:12Z <p>I'm not sure if you will consider this nontrivial, but from the character table you can very quickly show that the number of conjugacy classes of even permutations is always greater than or equal to the number of conjugacy classes of odd permutations.</p> <p>One just applies the general fact that the sum of the entries in any row of a character table (not weighted by the size of the conjugacy class) is a nonnegative integer (because the character <code>$\chi ( \pi ) = \frac{\# S_n}{\# C_\pi}$</code>, where $C_\pi$ is the set of conjugates of the permutation $\pi$, corresponds to an actual representation, namely, take a vector space with basis $\{ e_\pi \mid \pi \in S_n\}$ and define $g(e_\pi) = e_{g \pi g^{-1}}$ for $g \in S_n$) to the sign character.</p> http://mathoverflow.net/questions/985/applications-and-natural-occurrences-of-prime-numbers/34559#34559 Answer by Ken Fan for Applications and Natural Occurrences of Prime Numbers Ken Fan 2010-08-04T21:15:51Z 2010-08-04T21:15:51Z <p>Maybe this one is too frivolous, but sometimes, at Chinese restaurants, I get 5 shumai or 7 peking ravioli, instead of 6 or 8, and I've always wondered if that was a deliberate ploy to entice people to order more servings!</p> http://mathoverflow.net/questions/33037/are-there-consecutive-integers-of-the-form-a2b3-where-a-b-1 Are there consecutive integers of the form $a^2b^3$ where $a$, $b$ > 1? Ken Fan 2010-07-23T03:51:30Z 2010-07-23T17:20:50Z <p>Let $S$ = { $a^2b^3$ : $a, b \in \mathbb{Z}_{>1}$ }.</p> <p>Does there exist $n$ such that $n$, $n+1 \in S$?</p> <p>Motivation: I was thinking about <a href="http://mathoverflow.net/questions/32412/question-on-consecutive-integers-with-similar-prime-factorizations" rel="nofollow">http://mathoverflow.net/questions/32412/question-on-consecutive-integers-with-similar-prime-factorizations</a>, wondering whether any such pair had to have prime signatures with at least one 1. This would follow if the answer to the above question is negative. (This would also follow from weaker versions of the above question too, such as taking out perfect $n$th powers from $S$.)</p> <p>Please note that $a$ and $b$ in the set definition are not allowed to be equal to 1. Otherwise, there'd be solutions like 8, 9 or 465124, 465125. (465124 = $(2\cdot 11 \cdot 31)^2$ and 465125 = $61^25^3$.)</p> http://mathoverflow.net/questions/32412/question-on-consecutive-integers-with-similar-prime-factorizations/32657#32657 Answer by Ken Fan for Question on consecutive integers with similar prime factorizations Ken Fan 2010-07-20T17:17:23Z 2010-07-21T17:42:14Z <p>This is actually meant to be a comment, not an answer, but I'm new here and I don't have enough reputation to post a comment yet...sorry!</p> <p>I just wanted to note that Dickson's conjecture would imply infinitely many consecutive numbers with the same prime signature.</p> <p>For example, Dickson's conjecture would say that there are infinitely many k such that 4k+1 and 9k+2 are both prime. For each such k, 4(9k+2) and 9(4k+1) would be consecutive numbers with the prime signature (1,2). One might expect there to be roughly $\frac{3N}{\log 4N \log 9N}$ values of k between 1 and N such that 4k+1 and 9k+2 are both prime.</p> <hr> <p><em>This additional comment is directed toward Davidac897's comment about having more than one prime factor with exponent greater than 1, which TonyK already pointed out that Tom Sirgedas' program has already found examples of.</em></p> <p>Dickson's conjecture also would imply infinitely many such examples where more than one prime has exponent greater than 1.</p> <p>For example, say we want prime signature (1,2,2). Let $a = 2^27^2$ and $b = 3^25^2$. We seek solutions in primes $p$ and $q$ to $ap + 1 = bq$. If $p = bk + 194$, then $q = ak + 169$. Dickson's conjecture would say there are infinitely many $k$ such that $bk+194$ and $ak + 169$ are both prime. (The first consecutive pair using this method is $2463524 = 2^27^212569$ and $2463525 = 3^25^210949$.)</p> <p>In a similar vein, you can use Dickson's conjecture to force any prime signature you wish provided that at least one of the exponents is 1.</p> http://mathoverflow.net/questions/32479/what-are-some-mathematical-sculptures/32585#32585 Answer by Ken Fan for What are some mathematical sculptures? Ken Fan 2010-07-20T03:28:11Z 2010-07-20T03:28:11Z <p>Jane and John Kostick make many mathematically inspired sculptures some of which can be seen here: <a href="http://www.jjkostick.com/jjkostick/Welcome.html" rel="nofollow">http://www.jjkostick.com/jjkostick/Welcome.html</a></p> <p>For example, Jane made a coffee table whose base is a trefoil knot.</p> <p>For two more examples of sculptures that Jane built, please see the December 2008 issue of the Girls' Angle Bulletin, which can be downloaded from: <a href="http://www.girlsangle.org/page/bulletin.html" rel="nofollow">http://www.girlsangle.org/page/bulletin.html</a></p> http://mathoverflow.net/questions/29323/math-puzzles-for-dinner/31914#31914 Answer by Ken Fan for Math puzzles for dinner Ken Fan 2010-07-14T22:20:44Z 2010-07-14T22:20:44Z <p>Here's a balance scale problem that I decided to post because a little bit of googling around for it came up negative. It differs from most balance scale puzzles I've seen because it doesn't involve "bad weights". I learned of it from a friend of mine who is an engineer.</p> <p>There are 10 balls which come in two possible weights. Using a balance scale at most 3 times, determine whether all the balls are the same weight or not.</p> http://mathoverflow.net/questions/23478/examples-of-common-false-beliefs-in-mathematics/31076#31076 Answer by Ken Fan for Examples of common false beliefs in mathematics. Ken Fan 2010-07-08T16:41:24Z 2010-07-08T16:41:24Z <p>That the notion of "picking a random number" is well-defined without providing any further information.</p> http://mathoverflow.net/questions/80101/3-piece-dissection-of-square-to-equilateral-triangle Comment by Ken Fan Ken Fan 2011-11-05T02:18:14Z 2011-11-05T02:18:14Z 2 is not possible because the side length of the triangle is more than the diagonal of the square. http://mathoverflow.net/questions/56441/mathematics-tv-clips Comment by Ken Fan Ken Fan 2011-02-24T05:47:41Z 2011-02-24T05:47:41Z I thought this was good: <a href="http://www.youtube.com/watch?v=kkGeOWYOFoA" rel="nofollow">youtube.com/watch?v=kkGeOWYOFoA</a> Is that an example of the kind of thing you're looking for? http://mathoverflow.net/questions/50876/how-many-edge-disjoint-paths-go-from-upper-left-to-lower-right-in-a-4-times-n/51034#51034 Comment by Ken Fan Ken Fan 2011-01-08T17:30:47Z 2011-01-08T17:30:47Z Thanks for including the matrix graphic! I understand now that you're counting physically different path snippets (which includes the information of pairings on the right) without regard to orientation. In retrospect, Christian does seem to have this notion (with pairings on the left), but I was thrown by the first matrix with all zeroes and ones. I think as far as the question I posed here goes, the problem is settled and I think it should be so noted. I wish I could accept both answers. I've marked both up, but will go ahead and accept this one because of the pretty picture... http://mathoverflow.net/questions/50876/how-many-edge-disjoint-paths-go-from-upper-left-to-lower-right-in-a-4-times-n/50925#50925 Comment by Ken Fan Ken Fan 2011-01-04T17:44:35Z 2011-01-04T17:44:35Z @Christian: Thanks for the transition list. But, that method won't work because there can be multiple ways to string up a path for a given admissible covering. One can't use a matrix that has &gt;1 entries to fix: local choices influence global possibilities. If one does the analog for 3 X N case using Dylan's matrix, one undercounts. But if Dylan's T is replaced with 6 X 6 that does account for multiple ways, one will overcount because the local situation affects the global situation. That's why I'm not sure about the 4 by N case even with order information. But 3 by N with order is good. http://mathoverflow.net/questions/50876/how-many-edge-disjoint-paths-go-from-upper-left-to-lower-right-in-a-4-times-n/50925#50925 Comment by Ken Fan Ken Fan 2011-01-04T02:29:19Z 2011-01-04T02:29:19Z cntd: so I think in general, for the K by N case, it might be that T has a row and column for every up/down pattern with order information and that the entries can be &gt; 1, and so the basic idea is correct and it's a linear recurrence relation for all those cases...This seems right...I'm not 100% sure yet. http://mathoverflow.net/questions/50876/how-many-edge-disjoint-paths-go-from-upper-left-to-lower-right-in-a-4-times-n/50925#50925 Comment by Ken Fan Ken Fan 2011-01-04T02:06:31Z 2011-01-04T02:06:31Z Here's the 9 by 9 matrix for the 3 by N case: [1 1 1 0 0 0 1 0 1; 1 1 1 1 1 1 1 1 1; 1 1 1 1 0 1 0 0 0; 1 1 0 1 0 0 0 0 0; 1 1 0 0 1 0 0 0 0; 0 1 0 0 0 1 0 0 0; 0 1 0 0 0 0 1 0 0; 0 1 1 0 0 0 0 1 0; 0 1 1 0 0 0 0 0 1]. Take powers of this and, just as Dylan says, the (1,3) entry seems to count the number of paths. http://mathoverflow.net/questions/50876/how-many-edge-disjoint-paths-go-from-upper-left-to-lower-right-in-a-4-times-n/50925#50925 Comment by Ken Fan Ken Fan 2011-01-04T01:55:53Z 2011-01-04T01:55:53Z cntd.: However, I think that even with order of traversal information, there is a problem in the 4 by N case because it seems there can be more than one path per admissible covering. (I haven't actually checked it in the 3 by N case, but the agreement with the data seems to suggest that it is ok in this case.) But in the 4 by N case, using a variant of Dylan's notation with U=up and D=down, if o U1 D U2 is stacked on top of U1 D U2 o, there are two ways to string these together. (The numbers indicate the order the streets are traversed.) http://mathoverflow.net/questions/50876/how-many-edge-disjoint-paths-go-from-upper-left-to-lower-right-in-a-4-times-n/50925#50925 Comment by Ken Fan Ken Fan 2011-01-04T01:42:46Z 2011-01-04T01:42:46Z @all commenters: Thanks Dylan and Christian for these detailed answers. I've been thinking about them and here's what I've come up with so far. As described in both answers, it isn't quite right because there is more than one way to string up a given admissible covering into an edge disjoint path. However, in the 3 by N case, if one adds an order to the two horizontal left-to-right edges indicating which is traversed first, then you get a 9 by 9 matrix and this seems to work! For the 4 by N case, this would mean using a 28 by 28 matrix instead of 16 by 16. http://mathoverflow.net/questions/50876/how-many-edge-disjoint-paths-go-from-upper-left-to-lower-right-in-a-4-times-n Comment by Ken Fan Ken Fan 2011-01-02T04:47:21Z 2011-01-02T04:47:21Z Thank you for these comments and the reference. http://mathoverflow.net/questions/50343/what-would-you-want-to-see-at-the-museum-of-mathematics/50471#50471 Comment by Ken Fan Ken Fan 2010-12-27T17:13:34Z 2010-12-27T17:13:34Z This was implemented by MoMath in the form of a square-wheeled tricycle. See mathmidway.org/math-midway-activities-pedal.php. http://mathoverflow.net/questions/50343/what-would-you-want-to-see-at-the-museum-of-mathematics Comment by Ken Fan Ken Fan 2010-12-27T00:44:00Z 2010-12-27T00:44:00Z @Andy: Also, are you aware of Germany's Mathematikum? http://mathoverflow.net/questions/50343/what-would-you-want-to-see-at-the-museum-of-mathematics Comment by Ken Fan Ken Fan 2010-12-27T00:39:49Z 2010-12-27T00:39:49Z Andy's comment reminds me of the math section at Boston's Museum of Science. I haven't been there in 5-10 years, but their list of &quot;Living Mathematicians&quot; has more and more dead ones on it...and it also has &quot;Bourbaki&quot;. I offered to update the list for them for free about 15 years ago but they declined. http://mathoverflow.net/questions/47952/proving-interesting-theorems-about-s-n-using-its-character-table/47995#47995 Comment by Ken Fan Ken Fan 2010-12-02T04:33:43Z 2010-12-02T04:33:43Z Oh sorry...I missed your fix before I changed it back...I was struggling to get it to display properly...if you have a chance, please refix it! Thanks so much! http://mathoverflow.net/questions/29323/math-puzzles-for-dinner/31914#31914 Comment by Ken Fan Ken Fan 2010-08-18T17:32:34Z 2010-08-18T17:32:34Z Sorry...you're not allowed to use more than one scale...you have to use a particular balance scale at most 3 times to solve the puzzle! I think in these puzzles it's also understood that all a balance scale can tell you is whether the stuff you put on one side is the same weight or not as the stuff you put on the other side, and if they aren't, which side is the heavier. http://mathoverflow.net/questions/35980/2-and-3-body-problems-when-gravity-is-not-inverse-square Comment by Ken Fan Ken Fan 2010-08-18T17:20:47Z 2010-08-18T17:20:47Z There's more on the 2-body case in Needhams' Visual Complex Analysis Book, see pp. 241-247. There, he refers to Arnol'd's work, but also mentions that Arnol'd rediscovered the general result of E. Kasner in Kasner's 1913 work Differential-Geometric Aspects of Dynamics.