Hacker News Reader

Comment by biddlesby | Hacker News Reader

Ever since my undergraduate I've wanted to understand what representation theory is and the rough outline of how Andrew Wile's proof was constructed.

This article gave me both in a very understandable and engaging way. Thank you to the author!!!

View on HN

A somehow-much-less-popular way to come at representation theory is via generalized Fourier transforms. The irreducible representations are basically different "frequencies" which you can use to decompose functions on a group. And in fact, all of the major Fourier theorems carry over perfectly... There's even analogues of the fast Fourier transform, via chains of subgroups.

Are there any good references for this approach (via generalized Fourier transforms)?

I wouldn’t call this 3blue1brown video a reference, but until I watched this (coming from an audio background), I didn’t quite grasp that a continuous stencil of any complex silhouette could be described in terms of a set of contributing vectors. Helped click that there is a perfect visual analogy to the deconstruction of complex audio to sine waves.

https://youtu.be/r6sGWTCMz2k

Yes: Folland, A course in abstract harmonic analysis, CRC press

There is a thesis by Kondor: "Group theoretical methods for machine learning" - https://people.cs.uchicago.edu/~risi/papers/KondorThesis.pdf which provides links to the associated literature.

The documentation of his library (SnOB) is great: http://www.gatsby.ucl.ac.uk/~risi/SnOB/SnOB/SnOB.pdf

introductory slides on representation theory in machine learning: http://www.gatsby.ucl.ac.uk/~risi/courses/mini08/symmetric.p...

Full mini course: http://www.gatsby.ucl.ac.uk/~risi/courses/mini08/mini08.html

Thanks. These all look very readable.

Persi Diaconis' book is excellent. You come away with the proof that it takes seven shuffles to fully randomize a deck of cards...

https://www.amazon.com/Group-Representations-Probability-Sta...

Interesting you mention this. I wrote a Julia library a few years ago to generate both real and unitary irreducible representations for O3 and the symmetric group. It also implements the Fourier transform for the symmetric group and the fast Fourier transform for O3. I really miss that type of interesting work in grad school... unfortunately I don't have any projects that involve representation theory in industry anymore :(

Is the library publicly available? I would be interested in playing and learning from it.

Well, it depends. Some people would say, justly I think, the way to come at Fourier transform is as a commutative representation theory.

Yeah, I've always found generalized Fourier transforms and harmonic analysis to be really interesting! For those interested in reading more, some of the foundational work is the notion of a Haar measure and the Pontryagin duality. Basically, for any locally compact abelian group you can define a Fourier transform, and this Fourier transform is unique up to multiplicative identity. If you use this definition on the group of real numbers under addition you get the continuous Fourier transform, and if you use it on the group of integers under addition you get the discrete Fourier transform! And you can define the Fourier transform for more exotic groups, like on elliptic curves. In fact, this is how Shor's algorithm is able to factor large numbers, solve the discrete log problem, and break elliptic curve cryptography all in one algorithm: the algorithm is essentially just taking the Fourier transform of said function and measuring. Thanks to harmonic analysis, you can define a Fourier transform for elliptic curves and just plug that into Shor's algorithm

Will harmonic analysis play into P!=NP then, if its usable in quantum math?

I mean it could be, but not in the way you're talking about. There's a common misconception that quantum algorithms being able to factor integers and solve the discrete log problem in polynomial time has some implications for P vs NP. However, integer factoring and the discrete log problems are NOT NP complete problems, and there is no quantum algorithm published that can solve an NP complete problem in polynomial time. It's actually an open problem if quantum computers, in terms of computability classes, are any more powerful than classical computers (I think even assuming P!=NP, but I'm not a computing theory person haven't looked into more recent work on it).

That sounds really interesting - thank you

There's a good undergraduate-level text that gives enough background to understand the proof.

http://www.amazon.com/exec/obidos/ASIN/0123392519/donhosek

I still want to know what was the proof Fermat wrote was that couldn't fit in a margin.

It seems there's a fair chance it was a flawed proof, in which case I doubt we'll ever be particularly confident although we could possibly surface some candidates.

Something I always wondered is if we know of the existence of a proof that is both simple and also non-obviously flawed and as such could have been Fermat's solution?

Yes, Lamé solution, which assumes unique factorization in the rings of integers of cyclotomic fields, and can in fact be salvaged to prove the case of regular primes

Thanks while I don't fully understand what this means I think I get the idea. I assume it's a proof that has the "n" over infinite many cases (primes) but not all of them? Googling it was hard because there are other Lamé things. I'll just imagine he wrote this proof. Not the full proof, but not lame!

Yes, for some details look at http://fermatslasttheorem.blogspot.com/2006/01/lams-proposed... or https://math.stackexchange.com/questions/953462/what-was-lam...

Despite Fermat's brilliance, it's barely feasible that such a proof exists after 300 years of attempts by professionals and amateurs alike.

Ironically though, the tantalising idea of the existence of a simple proof - motivated by that infamous quote - contributed massively (along with the simplicity of the conjecture itself) to the theorem's notoriety and the myriad attempts to solve it.

Fermat was a brilliant social engineer as well as mathematician.

It's the predecessor of the dictum about putting a wrong answer on the internet to get the right answer. Sorta, and with a few hundred years involved.

He wrote the note to himself, a long time before he died. He then publicly announced a proof for the n=4 case, and nothing about the general case. It strongly suggests that he realized his proof was wrong.

Reply on news.ycombinator.com