6
$\begingroup$

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

    1. 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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ @Ofir Gorodetsky: does this address your question? $\endgroup$
    – kodlu
    Dec 1 '15 at 10:02
  • 1
    $\begingroup$ Your answer indeed solves several special cases which weren't mentioned in my question. Specifically, all your examples are abelian and so can be attacked using discrete fourier analysis. More generally, if I identify my set with some abelian additive group $A$, discrete fourier analysis over $A$ solves the case $G:=\{ x\mapsto x+a \mid a \in A\}$ quite efficiently. This is a generalization of my second example, where I took $A= \mathbb{Z}/n\mathbb{Z}$. I am actually more interested in new ideas, about non-commutative $G$'s. $\endgroup$ Dec 3 '15 at 13:17
  • $\begingroup$ I will edit the question accordingly. Still, thank you for sharing your examples, with details. $\endgroup$ Dec 3 '15 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.