A strange determinant – Timothy Gowers solves a problem [video] | Hacker News Reader

A strange determinant – Timothy Gowers solves a problem [video]

youtube.com

87 pointsdls201620 comments

The OP[0] in r/math provides good description of the video:

"This video is Gowers showing us that the false starts and silly mistakes we normal people make when first attempting a problem do not disappear at his "level". Watching his fumbles and frustrations might provide discouraged older students with some much-needed perspective on being "gifted", while watching him think out-loud might help unsure younger students learn what it means to "attack" a problem.

Gowers fails to solve the problem in this video. He tries again a few hours later and succeeds in this second video[1], but then tries and fails to find an "elegant" proof. The next morning, he wakes with an idea and figures out an elegant proof in a third video[2]."

[0] https://www.reddit.com/r/math/comments/mwxkso/timothy_gowers...

[1] https://youtu.be/frvBdaqLgLo

[2] https://youtu.be/m8R9rVb0M5o

I see he's using the program "write" by stylus labs[1]. It's an absolute favorite of mine (Especially on the ipad), and deserves to be more popular than it is.

It's not without rough edges, but it's killer feature: You can quickly reflow your handwritten text to add more blank space in the middle of a sentence, in the middle of a paragraph, in the middle of your paper. Or arbitrarily reorder anything at any time.

To me, it really is the features of the word processor finally come to handwritten text.

[1] http://www.styluslabs.com/

I have been using OpenBoard [1] to teach my classes, but this seems better.

What I am particularly excited about is Stylusboard [2], which apparently lets multiple people collaborate in real time online. This is going to make research meetings much better.

[1] https://twitter.com/wtgowers/status/1385364812239183872

[2] https://github.com/styluslabs/stylusboard

This looks awesome. But wow wow wow they're serving executables over HTTP and the website doesn't load if you try HTTPS. I wish I could try this out

All credit to Tim Gowers for doing this. He tweeted the quote "Being good at maths is being good at being stuck" from this video a little while ago

https://www.youtube.com/watch?v=kenf8E1RuoA

But of course he wouldn't be doing a voice-over in a real non-recorded attempt to solve a problem and I think it's notable that he falls silent when focusing at times. Interesting that he solves it by sleeping on the problem.

He's quite active on Twitter: a friend of mine has had some good debates with him on particular problems using Twitter.

Some context:

Tim growers follows the pedagogical style of producing the proofs on the blackboard in front of you without notes. This is reasonably possible in the kind of pure mathematics where his interests lie. The idea is that it forces the kind of straightforward proofs which have few ideas and are mostly doing only the obvious thing. It also means the audience get to see someone actually doing it rather than just presenting some notes. Morally, I want to say this style is good, but I don’t really have any idea if it’s the best way to lecture something.

I saw an attempt at something similar to this video—trying to solve a mostly unseen problem in real-time—from him about 5 years ago. In that case it was some attempt at an IMO problem and I think he got stuck at the end which relied on some weird equivalence classes of functions which were apparently quite common in IMO questions at the time but hard to derive if you’d not seen them before.

He has a reasonably popular blog at growers.wordpress.com where he has run some “polymath projects” which were attempts to prove or disprove certain conjectures through wide scale collaborative mathematics over the internet.

> Morally, I want to say this style is good, but I don’t really have any idea if it’s the best way to lecture something.

I think the entire point is that it's not a lecture. The internet allows us to share a video showing how the sausage is made, instead of the usual "definition, theorem, example" cadence of what many people consider a good math lecture.

* https://gowers.wordpress.com/

His surname is 'Gowers'!

Oops thank you! It was autocorrect and I failed to notice

I had a combinatorics prof who taught this way, and I found it really effective. There's usually some key insight, and then you can just follow you nose through the rest of the proof.

What a cool fact. The first thing that jumps into my mind for solving this would be the Schur Complement [1], which gives a way of computing the determinant of a block matrix in terms of its components. This would give us a formula where we could express the determinant of block matrix as

det([[A, B], [C, D]]) = det(A) det(D - CA^{-1}B)

If we let A be the matrix of size n-1 by n-1, it seems like this would reduce to a statement about a sum of products of binomial coefficients equaling some other binomial coefficient. Not sure if there's a deeper reason though.

[1]: https://en.wikipedia.org/wiki/Schur_complement#Properties

I've watched the video as far as Timothy Gowers sets out the problem. Now here's my attempt at a mental-arithmetic solution plan:

1. For any n, attempt to do an LU decomposition of the Pascal matrix P into the product of lower-triangular matrix L and upper-triangular matrix U.

2. By symmetry, these should be mirror-images of one another in the leading diagonal.

3. det(L) det(U) = det(P), which we know is 1. Also, by symmetry det(L) = det(U), which must then be either 1 or -1. The simplest approach would be to guess that is 1 and that the leading diagonal is all 1s.

4. Induct the first 3 cases, by mental arithmetic to reach:

  1 0 0     1 1 1     1 1 1
  1 1 0  *  0 1 2  =  1 2 3
  1 2 1     0 0 1     1 3 6

5. Guess that L and U are also Pascal's triangle arranged as rows and columns respectively.

6. Compute the bottom right corner for a couple more cases as a check:

  1^2 + 3^2 + 3^2 + 1^2 = 20
  1^2 + 4^2 + 6^2 + 4^2 + 1^2 = 70

... seems OK. So I guess, for the bottom right corner there's a binomial identity something like:

  $\sum_{k=0}^n \binom{n}{k}\binom{n}{k} = \binom{2n}{n}$

and a more general version of that identity for the cell (i,j) with 0 <= i, j <= n

  $\sum_{k=0}^n \binom{i}{k}\binom{j}{k} = \binom{i+j}{n}$

on an (n+1) x (n+1) matrix.

You got the right idea. The sum vanishes once $k > \min{i, j}$, so WLOG if $i \geq j$ you've got $\sum_{k=0}^j \binom{i}{k}\binom{j}{j - k}$, which is equal to $\binom{i + j}{j}$ by Vandermonde's identity [0], which is well-known enough that you can reliably expect people working in combinatorics to recognize it on sight. This goes through for every entry of the product, actually, so there's your proof.

[0] https://en.wikipedia.org/wiki/Vandermonde%27s_identity

Essentially then, the LU decomposition of P is just the matrix form of Vandermonde’s - which I recall now.

So I’m surprised that Timothy Gowers didn’t just write that down.

I still remember Gowers doing a live problem-solve as a lecture on what he calls "splitting questions" (that is, a sub-question whose resolution would ~halve the search space for a proof). He was given an unseen IMO problem and tried to demonstrate the process of solving it this way. I would have called this astonishingly brave, to live-solve a problem that you know in advance is extremely difficult; in fact he didn't succeed. It reminds me of something one of my schoolteachers once arranged a lesson to teach, to the effect of "you'll learn fastest if you're able to guess and be publicly wrong". It's brilliant to get more examples of this.

I know the point of this post is not the actual problem, but I couldn't help myself thinking about it.

It turns out that this is actually a more general phenomenon. Any matrix for which A[i,j] = A[i-1,j] + A[i,j-1] and that has all ones in the first column, i.e. A[0,j] =1, has unit determinant. Pascals triangle/determinant is just a special case when the first column and first row are all ones. Once you postulate this, you can prove it by induction since after one of your matrix "reductions", the (n-1) x (n-1) dimensional sub-determinant is still of the required form.

Every time I encounter anything from Gowers I'm impressed by his humility and real concern for people's struggles with learning mathematics - particularly at the undergraduate level.

He did a great blog when teaching Real Analysis to Cambridge first years.

https://gowers.wordpress.com/2014/01/11/introduction-to-camb...

I'm just starting this and I'm sure its over my head, but I love that he's cited Twitter as a source of inspiration immediately.

Some programmers might enjoy that he introduces zero-based indices for these determinants.

The best part is that he starts off with the "usual" one-based indexing, and then decides to change the indices because it suits his situation better. Us programmers mostly have to stick to the indexing scheme baked into our programming language; we can't switch things up based on the problem without introducing a separate abstraction to proxy access through.

Reply on news.ycombinator.com