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:

- 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$.
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}$.

- 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:

- 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\}$.
- 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.