G-Correlation of Vectors

Question

Let $\vec{a},\vec{b} \in \mathbb{R}^{n}$. Consider the function $f: S_n \to \mathbb{R}$ given by $f(\sigma):= \sum_{i=1}^{n} a_i b_{\sigma(i)}$. Let $G$ be a subgroup of $S_n$, given by $O(\log n)$ generators.

Question: What is the most efficient algorithm for finding the maximum of $f$ restricted to $G$, and the permutation at which the maximum is attained?

Of course, for some $G$'s it should be simpler than for others. Here are several classical examples:

1. If $G=S_n$, one can use the rearrangement inequality to solve this problem. The inequality reduces to problem to that of sorting the entries of $a$ and $b$, so the complexity is $O(n\log n)$. The same idea also solves the case $G=A_n$.

2. If $G=\langle \sigma \rangle$ where $\sigma(i)=i+1$ for $ 1 \le i \le n-1$, the sums $f(G)$ are known as "circular correlations", and the best correlation can be found with $O(n \log n)$ complexity using DFT over $\mathbb{Z}/n\mathbb{Z}$.

   3. More generally, if we identify the set $\{1,2,\cdots, n\}$ with some finite abelian group $A$, and take $G:=\{ x\mapsto x+a \mid a \in A\}$, we can use DFT over $A$ and achieve again a similar complexity.

Other examples are welcome.

It is easy to reduce to the case of transitive $G$. One can also assume that the entries of the vectors are integers.

[EDIT] I will make the question more concrete.

More Concrete Question: Can one solve the original question for some non-commutative $G$ (apart from $S_n$ and $A_n$)?

Specifically, here are some examples of $G$'s for which I don't know what is the best algorithm:

1. Identify $\{1,2,\cdots, n\}$ with $\mathbb{F}_q$ (so $n$ is a power of a prime), and consider $G=\{x \mapsto ax+b \mid a \in \mathbb{F}_q^{\times}, b \in \mathbb{F}_q\}$.
2. Identify $\{1,2,\cdots, n\}$ with $\mathbb{F}_q \cup \{\infty\}$ and consider $G=PGL_2(\mathbb{F}_q)$ or $G=PSL_2(\mathbb{F}_q)$.

Even More Concrete: Can someone solve the original question for these two (and a half) examples of $G$?

A naive solution is to reduce to the abelian case by writing $G$ as a union of abelian groups, but I feel this is too naive.

Answer 1

Let $n=2^m$ and let the integers from $0$ to $2^m-1$ be identified with the vector space $Z_2^m$ where operations are modulo 2 componentwise. For any $a\in Z_2^m$ the permutation $\sigma_a:x \rightarrow x+a$ can be defined on $Z_2^m$ and the correlation is then $$C_a(f)=\sum_{x \in Z_2^m} f(x) f(x+a)$$

In this case we can use the Walsh-Hadamard fast transform

$$\hat{f}(u)=\sum_{x \in Z_2^m} (-1)^{u\cdot x} f(x)$$

(which is of course the fourier transform for this setup) to find the maximum correlation and the maximizing $\sigma_a$ in $O(n \log n)$ time complexity.

The case when $f(x)=\pm 1,$ has specific applications to coding theory and cryptography, but this is not necessary.

Note this can also be done for any prime $p,$ and the space $Z_p^m$ where complex $p^{th}$ roots of unity and a corresponding generalized Hadamard transform can be used to define the appropriate fourier transform.

A related example: If $n=2^m-1$ and the space is the multiplicative group $GF(2^m)^{\ast}$ of $GF(2^m)$ which includes the elements $1,\alpha,\ldots,\alpha^{2^m-2}$ where $\alpha$ is a primitive element of $GF(2^m)$ one can define $$\tilde{f}(t)=f(\alpha^t),\quad t \in Z_{2^m-1}$$ taking on values in $GF(2)$ and use the transform $$\hat{f}(a)=\sum_{x \in GF(2^m)^{\ast}}(-1)^{tr(a x)+\tilde{f}(x)},\quad a \in GF(2^m)^{\ast}$$ to compute ``cyclic'' correlations since where the shift of the function $\tilde{f}$ by $\tau$ is given by $\tilde{f}(\alpha^{t+\tau})$, if you like in discrete log order instead of integer order.

Using a self-dual basis, which always exists for a finite field, the two transforms above can be related to each other.