User ken fan - MathOverflow

Answer by Ken Fan for Movies about mathematics/mathematicians

2011-10-06T04:26:51Z

Agora (2009) starring Rachel Weisz as Hypatia.

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.

Spoiler alert! Stop reading now if you plan to see the movie.

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.

Answer by Ken Fan for Pythagorean 5-tuples

2011-04-25T02:23:37Z

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.

The idea is to realize the solutions as the isotropic roots for a certain root system.

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}$.

Change basis to:

$\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}$.

If $n \geq 4$, let $\alpha_n = -v_0 - v_1 - v_2 - v_3$.

If $n=3$, let $\alpha_n = -v_0 - v_1 - v_2$.

The corresponding Cartan matrix $a_{ij} = \frac{2(\alpha_i, \alpha_j)}{(\alpha_i, \alpha_i)}$ is represented by the diagram:

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 < 10$. If $n=10$, then you have to add the orbit $(3, 1, 1, 1, \dots, 1)$ to get them all.

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.

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:

$$ \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1\\ 0 & 1 & 0 \end{pmatrix}, $$

$$ \begin{pmatrix} \pm 1 & 0 & 0 \\ 0 & \pm 1 & 0 \\ 0 & 0 & \pm 1 \end{pmatrix}, $$ and

$$ \begin{pmatrix} 3 & 2 & 2 \\ 2 & 1 & 2 \\ 2 & 2 & 1 \end{pmatrix}. $$

For $n=4$, you can use the matrices that permute the appropriate variables, change the sign of any variable, and the following:

$$ \begin{pmatrix} 2 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix}. $$

I'm sorry I cannot give a reference to the literature...I hope someone else is able to.

Answer by Ken Fan for Occurrences of a simple reflection in the longest element of a Weyl group?

2011-03-21T04:50:06Z

First, I'll show that you can assume that $ws_nw'$ is a reduced product.

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

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.

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

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

Claim: $\alpha$ must go negative at the location of $s_n$ in our reduced expression.

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

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$!

Therefore, no such expression exists except in type A.

And then in type A, there's the expression 1 21 321 4321 ... n (n-1) (n-2) ... 321.

How many edge-disjoint paths go from upper left to lower right in a $4 \times N$ rectangular gridwork of streets?

2011-01-01T18:35:46Z

Background/Motivation

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

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

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.

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

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.

Because there are finite linear recurrence relations for the $2 \times N$ and $3 \times N$ cases, it seems natural to also ask:

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?

Are these problems intractable?

Answer by Ken Fan for Good ways to engage in mathematics outreach?

2010-12-28T07:30:16Z

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.

Answer by Ken Fan for Proving interesting theorems about S_n using its character table.

2010-12-02T03:58:06Z

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.

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 $\chi ( \pi ) = \frac{\# S_n}{\# C_\pi}$ , 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.

Answer by Ken Fan for Applications and Natural Occurrences of Prime Numbers

2010-08-04T21:15:51Z

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!

Are there consecutive integers of the form $a^2b^3$ where $a$, $b$ > 1?

2010-07-23T03:51:30Z

Let $S$ = { $a^2b^3$ : $a, b \in \mathbb{Z}_{>1}$ }.

Does there exist $n$ such that $n$, $n+1 \in S$?

Motivation: I was thinking about http://mathoverflow.net/questions/32412/question-on-consecutive-integers-with-similar-prime-factorizations, 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$.)

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$.)

Answer by Ken Fan for Question on consecutive integers with similar prime factorizations

2010-07-20T17:17:23Z

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!

I just wanted to note that Dickson's conjecture would imply infinitely many consecutive numbers with the same prime signature.

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.

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.

Dickson's conjecture also would imply infinitely many such examples where more than one prime has exponent greater than 1.

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$.)

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.

Answer by Ken Fan for What are some mathematical sculptures?

2010-07-20T03:28:11Z

Jane and John Kostick make many mathematically inspired sculptures some of which can be seen here: http://www.jjkostick.com/jjkostick/Welcome.html

For example, Jane made a coffee table whose base is a trefoil knot.

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: http://www.girlsangle.org/page/bulletin.html

Answer by Ken Fan for Math puzzles for dinner

2010-07-14T22:20:44Z

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.

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.

Answer by Ken Fan for Examples of common false beliefs in mathematics.

2010-07-08T16:41:24Z

That the notion of "picking a random number" is well-defined without providing any further information.

Comment by Ken Fan

2011-11-05T02:18:14Z

2 is not possible because the side length of the triangle is more than the diagonal of the square.

Comment by Ken Fan

2011-02-24T05:47:41Z

I thought this was good: youtube.com/watch?v=kkGeOWYOFoA Is that an example of the kind of thing you're looking for?

Comment by Ken Fan

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

Comment by Ken Fan

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

Comment by Ken Fan

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

Comment by Ken Fan

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.

Comment by Ken Fan

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

Comment by Ken Fan

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.

Comment by Ken Fan

2011-01-02T04:47:21Z

Thank you for these comments and the reference.

Comment by Ken Fan

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.

Comment by Ken Fan

2010-12-27T00:44:00Z

@Andy: Also, are you aware of Germany's Mathematikum?

Comment by Ken Fan

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 "Living Mathematicians" has more and more dead ones on it...and it also has "Bourbaki". I offered to update the list for them for free about 15 years ago but they declined.

Comment by Ken Fan

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!

Comment by Ken Fan

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.

Comment by Ken Fan

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.