Discrete Fourier transform

Stream: Is there code for X?

[Yaël Dillies]

How far are we from the Fourier transform on finite groups? This is a commonplace tool in additive combinatorics (because it detects arithmetic sequences, see for example Freiman's theorem) so I would like it to be ready when the time comes.

[Yaël Dillies]

Incidentally, it's an item on the undergrad todo list.

[Yaël Dillies]

cc @Scott Morrison, @Antoine Labelle

[Antoine Labelle]

I assume that what you need is that characters of a finite abelian group form an orthonormal basis of the space of functions from G to the complex numbers?

[Yaël Dillies]

I have no idea. It doesn't seem like this is needed for the definition at least.

[Antoine Labelle]

You don't need it for the definition but I think that's what you need to be able to recover the function from its Fourier transform (Fourier inversion formula).

[Antoine Labelle]

We're not very far from the orthogonality part but we'd need more work to get the fact that the characters span the space of functions. I wonder if it would be worth to do some of the theory for characters of abelian groups separately since it's probably easier than the general theory for irreducible representations of finite groups.

[Yaël Dillies]

I don't mind waiting a bit more if this means doing things right, but @Bhavik Mehta should have a say.

[Bhavik Mehta]

I'm happy either way - perhaps the most fruitful approach is to have the version of finite abelian groups (which is almost always what you need in combinatorics) for now, and when the general correct version is done the special case can just be for the sake of API (something like how polynomial is useful indepedently but mv_polynomial is the correct general approach)

[Yaël Dillies]

There's also the fact that Gowers loves his funky convolution (f * g) x = ∑ y, f y * g (y - x). I don't really know what to do with this.

[Kevin Buzzard]

I guess it's $f(y)g(x-y)$?

[Yaël Dillies]

No, that's why I call it funky :smile:

[Yaël Dillies]

Here's the relevant document: https://drive.google.com/file/d/1ut0mUqSyPMweoxoDTfhXverEONyFgcuO/view

[Antoine Labelle]

Could it be formalized just as the convolution of f(x) with g(-x)?

[Yaël Dillies]

I hope, but there might be some friction. Time will tell.

[Scott Morrison]

I am grinding through https://klein.mit.edu/~etingof/repb.pdf (#13911 is a WIP tutorial PR that tracks progress), and this will eventually get there, via the general theory of f.d. irreducible representations of k-algebras, only specialising to k[G] for G a group, and G finite, when necessary.

[Scott Morrison]

Maybe I should say "would eventually get there, assuming I keep going" :-) If anyone wants to contribute to #13911, I think it is a fine roadmap/todo list for representation theory. Taking any statement from Etingof's book that is just past the end of the current tutorial and formalising it / adding it to the tutorial would be wonderful. I've been wrestling with Theorem 3.1.4 for a while; his proof is not great, but I think I have the right generality and structure now.

[Yaël Dillies]

How long do you think this will take, Scott?

[Yaël Dillies]

Also, what should we do with @Floris van Doorn's bilinear map generalization? that is ∑ y, L (f y) (g (x - y)) instead of ∑ y, f y * g (x - y).

[Scott Morrison]

Oh, for discrete fourier transform specifically don't wait for me. I'm taking forever, and can happily meet up with anything that gets done ahead of me.