Computing the fixed field of an automorphism of a function field - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T01:53:37Z http://mathoverflow.net/feeds/question/84993 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/84993/computing-the-fixed-field-of-an-automorphism-of-a-function-field Computing the fixed field of an automorphism of a function field Syed 2012-01-05T19:18:24Z 2012-01-20T10:10:21Z <p>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.</p> <p>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).</p> <p>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?</p> <p>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).</p> <p><strong>Long story short, please tell me what is the fixed field algorithm for automorphisms of (global) function field, that normal people use?</strong></p> <p>Thanks a lot</p> <p>post scriptum: I ran into this theorem stated in <a href="http://arxiv.org/abs/0805.2331v1" rel="nofollow">link text</a> with no proof or reference (beside that Dr. Peter Muller suggested it to the authers (whoever he is)),</p> <p>[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$.</p> <p>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 ;)</p> <p>postquam post scriptum: I pasted the "fixed field" functions (for number fields) from both Magma and Pari, here:<a href="http://everramified.wordpress.com/2012/01/08/fixed-field-computation-magma-vs-pari/" rel="nofollow">link text</a>. 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. </p> <p>Follow-up on @paul garrett's proposed solution to Stichtenoth's problem.</p> <p>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:</p> <pre><code>kx.&lt;x&gt; = 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 </code></pre> <p>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). </p> <p>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. </p> <p>But, anyway, my question is not the Stichtenoth's question, I just brought-up it as an example that my problem isn't trivial. </p> http://mathoverflow.net/questions/84993/computing-the-fixed-field-of-an-automorphism-of-a-function-field/85140#85140 Answer by paul garrett for Computing the fixed field of an automorphism of a function field paul garrett 2012-01-07T17:19:10Z 2012-01-12T13:38:23Z <p>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.</p> <p>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 <em>summing</em> $(x^q-x)^{q-1}$ over these automorphisms visibly gives a non-zero, non-constant element fixed under $G$. </p> <p>Further edit in respons to @Syd Lavasani's questions/comments: I don't know a story to tell to <em>find</em> 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...)</p> <p>The up-side is that these considerations (the Artin-Schreier and Kummer) still apply in <em>arbitrary</em> 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).</p> <p>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$.</p> <p>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...</p> http://mathoverflow.net/questions/84993/computing-the-fixed-field-of-an-automorphism-of-a-function-field/86189#86189 Answer by Syed for Computing the fixed field of an automorphism of a function field Syed 2012-01-20T10:10:21Z 2012-01-20T10:10:21Z <p><a href="http://math.ucalgary.ca/profiles/colin-weir" rel="nofollow">Colin Weir</a>, 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:</p> <p>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. </p>