Computing the fixed field of an automorphism of a function field Let say we have a function field $k(x,y)$ defined by $f(x,y)$ over $k$, with $\sigma \in Aut(k(x,y)/k)$ and. Suppose, I'm not that out of luck, so that either of $\prod \sigma^i(x)$ or $\sum \sigma^i(x)$ (and the same for $y$) don't fall in $k$, let call them $x^\sigma$ and $y^\sigma$. Then I can compute $k(x^\sigma, y^\sigma)$ and it is not hard to see that if $(\deg(x),\deg(y)) = 1$, that would be my fixed field and I can compute it by finding the min poly of one over another.
However, for example in the case of hyperelliptic involution, we have $\sum \sigma^i(y)=0$. Or there are situations that finding such an $x,y$ is not an easy question. For example, in Algebraic Function Fields and Codes of Stichtenoth, Question 6.9, he asks for such an element $t$ in $F_q(x)$ such that $t^{Aut(F_q(x)/F_q)} = t^{PGL(2,q)}$ is not in $F_q$, and I couldn't solve it (So, it's hard for me at least. I can of course use computer algebra for a particular $q$ but this not what the question asks).
So, I was wondering what is a fail-free way of choosing these generators, such that the fixed field algorithm always works (to prevent them from falling into the constant field and have relatively prime degree). If I use all symmetric polynomials of $Order(\sigma)$ variables, is there a guarantee that at least one of them won't let me down?
Or, if is there better, fixed field computation algorithm there, please tell me (the fixed field algorithm for number field doesn't work straight forward because it could be that $k(x) \not \subseteq k(x^\sigma)$ but one can fixed this if they change the underlying rational function field to the latter, under condition that $x^\sigma$ doesn't fall into $k$, which was my problem to begin with).
Long story short, please tell me what is the fixed field algorithm for automorphisms of (global) function field, that normal people use?
Thanks a lot
post scriptum:
I ran into this theorem stated in link text with no proof or reference  (beside that Dr. Peter Muller suggested it to the authers (whoever he is)),
[knowing that one can embed a group of automorphisms of rational function field into the field] Let $G = {g_1, . . . , g_m} \subseteq K(x)$ be a finite group. Let $P(t) = \prod^{m}_1 (t−g_i) ∈ K(x)[t]$. Then any non–constant coefficient of $P(t)$ generates $F^G$.
Beside the fact that without having the proof it's hard to generalize it to the nonrational case, it also doesn't guarantee that it doesn't happen that all coeffients of $P(t)$ are constant. In any case, I thought it might help the person who's going to help me ;)
postquam post scriptum: I pasted the "fixed field" functions (for number fields) from both Magma and Pari, here:link text. I see that Magma basically is doing the same thing as I guessed, computing lots of symmetric polynomials and adding them to the base field till the relative degree is the size of the subgroup. For PARI, I don't understand what's the significance of "fixedfieldorbits" and "vandermondeinversemod". I thought It might be helpful. They both lack the function to compute the fixed field of a function field. 
Follow-up on @paul garrett's proposed solution to Stichtenoth's problem.
If I understood the proposed method to generate the generator of $F_q(x)^{Aut(F_q(x))}$ correctly, following (sage) code should be able to generate it:
kx.<x> = FunctionField(FiniteField(q))
w = GL2q(Matrix([[0,1],[1,0]]))
Ns = [GL2q(Matrix([[1,n],[0,1]])) for n in range(0,q)]

invElm = (x^q - x)^(q-1)
t = invElm;
for n in Ns:
    ninvElm = PGLAction(PGL2GL, GL2PGL.Image(n*w), invElm);
    t += ninvElm

print t

Unfortunately, the result is always $(x^q-x)^{(q-1)}$ because summing up over n*w is always zero. Unless, I chose the wrong set of automorphism to apply (this is image of identity plus sum of images of n*w for n =0,..,q-1). 
There is another part to that question (that wasn't hard to solved) before asking for finding t. It's to find the ramification locus of $F_q(x)^{Aut(F_q(x))}$ and to prove that all places of deg 2 are conjugates. It probably helps. 
But, anyway, my question is not the Stichtenoth's question, I just brought-up it as an example that my problem isn't trivial. 
 A: The question about fixed elements of a finite group $G$ of automorphisms of a field $k$ has a reasonable answer, by Galois theory: for any $\alpha\in k$, the coefficients of $P(t)=\prod_{\sigma\in G} (t-\sigma(\alpha))$ are in the fixed field of $G$. Since $P(\alpha)=0$, certainly $\alpha$ is of degree at most the degree of $P$ over the fixed field of $G$. Thus, for example, if all the coefficients (the elementary symmetric polynomials) were to vanish, $\alpha=0$. Or, for $\alpha=x\in \mathbb F_q(x)$, if all the coefficients were constant, then $x$ would be of finite degree over $\mathbb F_q$, which is not so.
The specific question about the fixed field of $G=PGL_2(\mathbb F_q)$ on $k=\mathbb F_q(x)$ admits some simplification, as follows. One might know for other reasons that the subgroup generated by automorphism $x\rightarrow x+1$ fixes (the Artin-Schreier element) $A=x^q-x$. Certainly $x$ satisfies $x^q-x-A=0$, so the group $N$ of automorphisms $x\rightarrow x+\ell$ (with $\ell\in \mathbb F_q$) is the Galois group of the extension $\mathbb F_q(x)/\mathbb F_q(A)$. The multiplications $x\rightarrow \beta\cdot x$ with $\beta\in \mathbb F_q^\times$ fix $B=A^{q-1}=(x^q-x)^{q-1}$. Let $P$ be the upper-triangular subgroup in $G$, generated by $N$ and multiplications, and $w$ the anti-diagonal $1's$ matrix (=the long Weyl element). Then the (Bruhat) decomposition $G=P\cup NwP$ shows that $G/P$ has representatives $1$ and $nw$ for $n\in N$. I think summing $(x^q-x)^{q-1}$ over these automorphisms visibly gives a non-zero, non-constant element fixed under $G$. 
Further edit in respons to @Syd Lavasani's questions/comments: I don't know a story to tell to find the Artin-Schreier construction, but it is not hard to explain why/what purpose it fulfills. Namely, in characteristic $p>0$, abelian extensions of degree $p$ (obviously) cannot be given by taking $p$th roots... What, then? The Artin-Schreier equations $X^p-X+a=0$. The $X^{q-1}-a=0$ is a "Kummer equation", since the groundfield $\mathbb F_q$ contains $(q-1)$th roots of unity, and is the way to obtain cyclic Galois extensions of this degree. (The history of taking roots to obtain cyclic extensions is centuries old...)
The up-side is that these considerations (the Artin-Schreier and Kummer) still apply in arbitrary fields of char $p>0$ containing $\mathbb F_q$. Beyond that, all I'd think to try would be some basic repn theory of whatever groups you have in hand (such as $PGL_2(\mathbb F_q)$), although when the characteristic divides the group order things will not necessarily be straightforward (loss of semi-simplicity).
Further edit, in response to @SydLavasani's further comment/question about the utility of some sort of repn theory here. For $K/k$ cyclic of degree $n$, when $k$ contains the $n\th$ roots of unity, and char $k$ not dividing $n$, then $K$ as repn space for the cyclic group decomposes as a direct sum of one-dimensional irreducibles, each of which is some "multiply-by-$\zeta_n$" where $\zeta_n$ is an $n$-th root of unity. (Note, these are all the irreducibles, and by assumption they are definable over $k$.) Galois theory shows that this decomposition must actually be the sum over all such, each occurring exactly once. This suggests a form of the conclusion of "Kummer theory", namely, that there is an element generating the extension whose $n$\th power is in the base field, whence the $X^n-a$.
I have not thought enough about positive-characteristic repn theory to give an analogous story for the Artin-Schreier polynomial, but it would not surprise me if someone else has...
A: Colin Weir, suggested the following algorithm to solve the problem in non-rational case, I thought for the sake of others who probably have the same question, I'll post it, here:
Suppose that $\sigma$ is an automorphism of $k(x,y)$. Using above theorem we can find a $x^\sigma$ such that $k(x^\sigma) = k(x)^{\sigma}$. Now, we can re-compute $k(x,y)$ as $k(x^\sigma, y)$. Using degree argument, now one can easily prove that $k(x^\sigma)[\textrm{All elementary symmetric polynomials in } \{y, \sigma(y), \sigma^2(y),...,\sigma^{d-1}(y)\}]$ is equal to $k(x^\sigma, y)^\sigma$. In practice, you add these symmetric polynomials one by one, till your tower reaches the desirable degree. 
