2
$\begingroup$

Consider finite group $G$ , symmetric set of its elements $S$, construct a Cayley graph.

Consider $d(g)$ - word metric or distance on the Cayley graph from identity to $g$.

As any function on a group it can be decomposed into "Fourier" basis coming from the irreducible representations. See formula below. It is the very standard fact that decomposition of the representations like regular representation - is generalization of the Fourier decomposition. Fourier decompositions are particular cases for the abelian groups. See e.g. wikipedia.

That basis does not depend on $S$ and while $d(g)$ obviously depends, that decomposition can be kind of simple for $S$ and complicated for the other, nevertheless , we can ask:

Question: are there some known properties or expectations that such decomposition can be a good one ? Can one estimate the reside term if we take only some irreps ? Or more generally are there some techniques that relate some knowledge on the representation theory of a given group to question on its Cayley graph (metric approximation , diameter estimation, growth, etc. )?

Results by J.Swan (see below) suggests that sometimes Fourier decomposition can be sparse, i.e. only few are non-zero for some approximations of the word metrics. In general representation theory is quite related to Cayley graphs studies see e.g. Tao's blog: https://terrytao.wordpress.com/2011/12/16/254b-notes-3-quasirandom-groups-expansion-and-selbergs-316-theorem/

Motivation comes from the paper, where authors search by machine learning methods the function using such decomposition. More precisely - one uses such an ansatz and coefficients are found by gradient descent technique. They argue there approach is reasonably effective, so I wonder is there any theoretical basis which might shed light on such an approach ?

"Fourier Bases for Solving Permutation Puzzles" (Horace Pan, Risi Kondor) https://proceedings.mlr.press/v130/pan21a.html

enter image description here

Reminder. The Fourier transform and its inverse over the groups looks like that. Pay attention - coefficients are MATRICES, and so the inverse transform contains "Tr".

enter image description here Here n! because of S_n.

Interesting facts. "Harmonic Analysis and Resynthesis of Sliding-Tile Puzzle Heuristics" 2017 Jerry Swan - interesting paper observed sparsity of Fourier coefs for Hamming/Manhatten function on 15-puzzle. https://ieeexplore.ieee.org/abstract/document/7969355

enter image description here

These is not "word/Cayley" metric , but these are standard approximations, which are always used.

PS

Some my colleagues and me are thinking to apply machine learning methods to similar task in group theory - if any one interested - would be great to keep in touch !

Improve this question
$\endgroup$
7
  • $\begingroup$ What do you mean by “any function on a group it can be decomposed into "Fourier" basis coming from the irreducible representations”? $\endgroup$
    – Andy Putman
    Commented Jun 7 at 12:24
  • $\begingroup$ @AndyPutman well , I mean plain standard thing - t_{ij} is basis . To say it longer - like in textbook - consider functions of G - regular representation - it is decomposed as \sum V\times V^* over all irreps. How does one achieve that decompostion ? One takes irrep V , chooses a basis e_i looks on matrix elements t_{ij} - they are functions on the group G , now how to they behave with respect to right action of G on G ? Exactly as representation V from the one they constructuted. "Peter-Weyl" for finite groups says that all functions on G are covered by \sum V\times V^* over all irreps $\endgroup$
    – Alexander Chervov
    Commented Jun 7 at 12:30
  • $\begingroup$ In the paper they use computationaly more pleasent from : \sum Tr( MatrixOfCoefs * \rho(g) ) - but it is just the form $\endgroup$
    – Alexander Chervov
    Commented Jun 7 at 12:32
  • $\begingroup$ Two remarks: 1. The basis of matrix entries of irreducible representations is highly non-canonical since it involves a choice of basis for each irreducible representation. 2. Even with that clarification the question is very vague. You need to edit the question to make it precise and comprehensible without requiring the reader the either read the comments or guess what you mean. $\endgroup$
    – Andy Putman
    Commented Jun 7 at 14:19
  • $\begingroup$ @AndyPutman Thanks for the remarks, will try to change it. By the way in your field - for infinite f.g. groups - any relations between between word metric(s) and irreps ? I see there is something in Tao's blog: terrytao.wordpress.com/2011/12/16/… but not sure at the moment , does it imply directly some good properties of the decomposition in my question . $\endgroup$
    – Alexander Chervov
    Commented Jun 7 at 19:11

0

Reset to default