Csdrhrt

Disclaimer / Introduction

I am a physicist by training who hasn't taken courses in invariant theory. I hope my description of my question that doesn't mis-use the terminology in `invariant theory' -- but in case it does I have provided a concrete example in less mathematical terminology to try to make clear what I actually meant!

Attempt at mathematical statement:

Notation

Suppose I have an $n$-dimensional vector space $V$ over a field $F$ which may (at your preference) be taken to be either the reals or the complex numbers. I also have a group $G$ which permutes (some of) the components of the vectors $vec x$ in $V$. In all the cases I am interested in, $G$ is a proper subgroup of the $S_n$, by which I mean that it does not include all possible $(n!)$ permutations of the $n$ elements of each $vec x$. We will assume that $G$ is generated by $m$ generators $g_1,ldots,g_min G$.

We new define an equivalence relation $sim$ in the vector space by: $$(vec xsim vec y) Leftrightarrow (exists gin G text{s.t.} vec x = gvec y). $$

The problem itself

Given any concretely specified $G$, $n$, $F$ and $V$ as defined above, I wish to learn how I can construct a set of $n$ functions (let's call them $f_1,f_2,ldots, f_n$) which each map $Vrightarrow F$ in such a way that:
$$( f_i(vec x) = f_i(vec y) forall iin{1,2,ldots,n})Leftrightarrow(vec x sim vec y).$$

[I think these might be called "indicator functions" or "complete sets of invariants", in that they unambiguously indicate to which equivalence class any $vec x$ belongs. Though perhaps I am mis-using those terms.]

A very simple example (Example 1)

Suppose $n=3$, and an arbitrary element of $V$ is denoted $vec x=(a,b,p)$. Assume that $G$ is generated by a single generator $g$ which exchanges the first and second elements of $x$ ($aleftrightarrow b$). I.e. $$g=left( begin{array}{ccc}
0 & 1 & 0 \
1 & 0 & 0 \
0 & 0 & 1
end{array}right)$$ (Note that in more complicated examples $G$ could have more than one generator!)

In the above case, the three functions:
$$
f_1(vec x) = a+b
\
f_2(vec x) = ab
\
f_3(vec x) = p
$$
is a set of functions $f_i$ which satisfies my requirements, but in contrast
$$
f_1(vec x) = a+b
\
f_2(vec x) = a-b
\
f_3(vec x) = p
$$
is a bad set of functions which does not meet the requirement, and
$$
f_1(vec x) = a+b+p
\
f_2(vec x) = ab+ap+bp
\
f_3(vec x) = abp
$$ does not work either.

A more complicated example (Example 2)

Suppose $n=6$, and an arbitrary element of $V$ is denoted $vec x=(a,b,p,q,x,y)$. Assume that $G$ is generated by a single generator $g$ which exchanges the first and second elements of $x$ ($aleftrightarrow b$) at the same time as exchanging the third and fourth elements ($pleftrightarrow q$). I.e. $$g=left( begin{array}{cccccc}
0 & 1 & 0 & 0 & 0 & 0 \
1 & 0 & 0 & 0 & 0 & 0 \
0 & 0 & 0 & 1 & 0 & 0 \
0 & 0 & 1 & 0 & 0 & 0 \
0 & 0 & 0 & 0 & 1 & 0 \
0 & 0 & 0 & 0 & 0 & 1
end{array}right)$$ (Note that in more complicated examples $G$ could have more than one generator!)

In the above case, the six functions:
$$
f_1(vec x) = p+q
\
f_2(vec x) = a+b
\
f_3(vec x) = pq-ab
\
f_4(vec x) = bp+aq
\
f_5(vec x) = x
\
f_6(vec x) = y
$$
is a set of functions $f_i$ which satisfies my requirements.

An example showing why I am not interested in the case where $G=S_n$

If $G$ were $S_6$, the symmetric group on six objects having all possible $6!$ elements, then symmetric polynomials would (trivially) be a valid set of $f_i$:
$$
f_1 = a+b+p+q+x+y \
f_2 = ab+ap+aq+ax+ay+bp+bq+bx+by+pq+px+py+qx+qy+xy \
f_3 = abp+abq+cdots+qxy \
f_4 = abpq+cdots+pqxy \
f_5 = abpqx+abpqy+abpxy+abqxy+apqxy+bpqxy\
f_6 = abpqxy.
$$
The above sets are easy to construct, but do not answer the question when $G$ is not $S_n$ (see my examples above).

Notes

The limitations of my own method of finding functions $f_i$

Alas: the way (which I have not described) that I generated a valid set of functions for Example 2 does not allow me to work with any $G$ containing an element which contains three or more transpositions. I cannot therefore presently write down a set of functions which meets my requirements if the generator $g$ above is replaced by, say
$$g'=left( begin{array}{cccccc}
0 & 1 & 0 & 0 & 0 & 0 \
1 & 0 & 0 & 0 & 0 & 0 \
0 & 0 & 0 & 1 & 0 & 0 \
0 & 0 & 1 & 0 & 0 & 0 \
0 & 0 & 0 & 0 & 0 & 1 \
0 & 0 & 0 & 0 & 1 & 0
end{array}right).$$ I can't believe that there is no way of answering such marginally more complicated cases, though, so I assume that any invariant-theory professional will have an armoury of tools much better than mine, and can point me to books and or resources that will tell me how to turn any $G$ that's a permutation group into a set of functions $f_i$ that meet my needs.

I think I might have an answer for the case that $F$ is the reals.
First construct a polynomial $P(vec X)$ that is a function of an arbitrary point $vec X=(X_1,X_2,ldots,X_n)in V$ as follows
$$ P(vec X) =
| vec X - g_1 vec x |^2
| vec X - g_2 vec x |^2
| vec X - g_3 vec x |^2
cdots
| vec X - g_m vec x |^2
$$ in which $|vec x|^2$ represents a Euclidean norm. This $P$ has roots at $vec x$ and all the places to which $vec x$ can be moved by the action of the group $G$. Because of the way we have constructed $P$, if we were to multiply out all its terms we would find that the collected coefficients of any given term (e.g. the collected coefficients of the $X_1^4 X_2^2 X_5$ term) would be invariant under the action of $G$. The set of all of these coefficients entirely specifies the polynomial, and the polynomial is entirely specified by its roots and its form, so these coefficients are almost the set of functions $f_i$ requested. The only problem is that there are (in general) too many of them. Among the big list, though, exactly $n$ independent ones must exist, since the coefficients capture the same information as exists in the specification of the $n$ roots of the polynomial. A sufficient set of $n$ independent coefficients could be extracted by the following algorithm:

(1) create an empty set $K$.

(2) put all the polynomial coefficients in a set $C$.

(3) choose an element $cin C$ and remove that element from $C$ permanently.

(4) create a set $T=K cup {c}$.

(5) construct a Groebner basis for the polynomials in $T$. If this basis has a length equal to the number of elements in $T$, then replace $K$ with $T$, otherwise leave $K$ unaltered.

(6) If $K$ has fewer than $n$ elements, go to step (3).

(7) If this step is reached, $K$ contains a set of $n$ independent functions $f_i$ which (I hope) answer my question.

At least, I hope so.

I have tried this on a few concrete examples which have all worked out, though that doesn’t prove much.