Formulas for the structure constants of a field extension basis given by a primitive element

Let $L/K$ be a finite separable field extension and let $\theta$ be a primitive element for $L/K$ with minimal polynomial $\mu(t) \equiv \mu_{\theta/K}(t) = \sum_{k=0}^n c_k t^k$. I am trying to compute the powers $\theta^n,\dots,\theta^{2n-2}$ in terms of $1,\theta,\dots,\theta^{n-1}$. In other words, I am trying to compute the structure constants of the basis $1,\theta,\dots,\theta^{n-1}$ in terms of the coefficients of $\mu(t)$, but the expressions quickly become unmanageable. I can hardly imagine that I am the first one to attempt such a calculation, so my question is

Are there perhaps some nice general formulas or manageable expressions/patterns that capture the structure constants of such a basis in terms of the coefficients of $\mu(t)$? Is there some general context where these appear? Or is it hopeless?

Notice that using the dual basis with respect to the trace essentially seems to run into the same issues. I have looked into J.S.Milne's notes on Fields and Galois Theory and on Algebraic Number Theory as well as in Neukirch's Algebraic Number Theory, but in this regard they don't seem to go beyond calculating the discriminant.

• $\theta^{n-2}$ is a typo for ... ? – Gerry Myerson Mar 26 '18 at 4:40
• @GerryMyerson: oops, sorry, it's a typo for $\theta^{2n-2}$. Thanks for noticing! – M.G. Mar 26 '18 at 9:31

edit: I assume $c_n = 1$, as we have a minimal polynomial.

More like a long comment, not a complete answer: Set $c_k := 0$ for negative $k$ to simplify computations. Then we have (hoping I did no errors, as I calculated this by hand):

$$\theta^n = \sum_{k=0}^{n-1} -c_k\theta^k$$ $$\theta^{n+1} = \sum_{k=0}^{n-1} (c_{n-1}c_k - c_{k-1})\theta^k$$ $$\theta^{n+2} = \sum_{k=0}^{n-1} ((-c_{n-1}^2+c_{n-2})c_k + c_{n-1}c_{k-1}-c_{k-2})\theta^k$$ $$\theta^{n+3} = \sum_{k=0}^{n-1} ((c_{n-1}^3 - 2c_{n-1}c_{n-2} + c_{n-3})c_k + (-c_{n-1}^2+c_{n-2})c_{k-1}+ c_{n-1}c_{k-2}-c_{k-3})\theta^k$$

Thus, if we define a sequence of polynomials $p_i$ as $$p_0 = -1, \,\,\, p_1 = c_{n-1}, \,\,\, p_2 = -c_{n-1}^2+c_{n-2}, \,\,\,p_3 = c_{n-1}^3 - 2c_{n-1}c_{n-2}+c_{n-3}, \ldots$$ then I claim that $$\theta^{n+m} = \sum_{k=0}^{n-1} \left( \sum_{\ell = 0}^m p_{\ell} c_{k-m+\ell} \right)\theta^k.$$

Of course to prove this, one first needs to find and prove the structure of the $p_i$, but there seems to be a lot of structure in these polynomials to work with; e.g. there $c_{n-1}$ degree, the switching sign,...

Another edit: I would suggest to first use a computer to compute $p_0,\ldots, p_{10}$ and then check OEIS if you find them there, as I think the structure of these polynomials can be shown with combinatorial methods.

• Thanks for typing some of the calculations in. Indeed the question boils down to the polynomials $p_k$. I am hoping someone might already know something about these expressions or find an already known pattern there before I start reinventing the wheel :-) Re your edit: yes, that's a good idea! – M.G. Mar 26 '18 at 12:17
• @July As I just wrote in my edit, I would suggest to compute them (and properly check that you have the right ones, e.g. by doing examples with a computer, I just computed them on 2 pages of paper by hand, so no guarantee that there are no errors) and then search databases like OEIS to get an idea. I think that there should be a combinatorial structure in how the coefficients of the $p_i$ get picked, similar to the coefficients in the multiplication of certain polynomials, in the binomial theorem, etc. – Dirk Mar 26 '18 at 12:20
• Yes, that's a really good idea. I too think there should be some combinatorial structure to them. I was not aware that one can search OEIS for polynomials. What other databases are there for polynomials? – M.G. Mar 26 '18 at 12:24
• The polynomials $p_i$, in your notation, are (up to a minus sign) equal to the "complete homogeneous symmetric polynomials" in the roots of $\mu(t)$, usually denoted by $h_i$ in the literature. I suggest looking up Newton's identities, which explain how to compute polynomials such as your $p_i$ using the given $c_i$-s. – Ofir Gorodetsky Mar 26 '18 at 12:26
• @OfirGorodetsky: thanks, this is great! – M.G. Mar 26 '18 at 12:47

I am not entirely sure on the policy of answering one's own question, I am posting this for the sake of completeness and closure for anyone who might be interested in the same question.

Following Ofir Gorodetsky's observation above, let is denote by $$h_k := h_k(X_1,\dots,X_n) := \sum_{1\leq i_1\leq i_2\leq\dots\leq i_k\leq n}X_{i_1}X_{i_2}\dots X_{i_k}$$ $$\sigma_k := \sigma_k (X_1,\dots,X_n) := \sum_{1\leq i_1< i_2<\dots< i_k\leq n}X_{i_1}X_{i_2}\dots X_{i_k},\ \sigma_0 := 1$$ the complete homogeneous symmetric polynomials and the elementary symmetric polynomials in $n$ variables respectively. We have the following fundamental relation (which can be found for example in Stanley's Enumerative Combinatorics Vol.2):

Lemma: $\forall m\geq 1$: $$\sum_{\ell=0}^{m}(-1)^{m-\ell} \sigma_{m-\ell} h_\ell = 0$$ In particular, we have the recursion $\forall m\geq 0$: $$h_{m+1} = - \sum_{\ell=0}^m (-1)^{m-\ell+1}\sigma_{m-\ell+1}h_\ell,\ h_0 = 1$$ $\square$

As a corollary of this, if $\theta_1,\dots,\theta_n$ are the roots of the minimal polynomial $\mu$, we obtain the following recursive relation: $$h_{m+1}(\theta_1,\dots,\theta_n) = -\sum_{\ell=0}^m c_{n-m-1+\ell} h_\ell(\theta_1,\dots,\theta_n),\ h_0(\theta_1,\dots,\theta_n) = 1,$$ which we are going to use to prove the next

Claim: We have $\forall m\geq 0$: $$\theta^{n+m} = -\sum_{k=0}^{n-1}\left(\sum_{\ell=0}^m c_{k-m+\ell} h_\ell \right)\theta^k$$

Proof: Induction on $m$. The cases $m=0$ and $m=1$ are known from Dirk Liebhold's answer. Now suppose the claim is true for $m$. We calculate: $$\theta^{n+m+1} = -\sum_{k=0}^{n-1}\left(\sum_{\ell=0}^m c_{k-m+\ell} h_\ell\right)\theta^{k+1} = -\sum_{k=1}^{n-1}\left(\sum_{\ell=0}^m c_{k-1-m+\ell} h_\ell\right)\theta^k -\left(\sum_{\ell=0}^m c_{n-1-m+\ell}h_\ell \right)\left(-\sum_{k=0}^{n-1}c_k\theta^k\right) = \sum_{k=0}^{n-1}\left(\sum_{\ell=0}^m \left(c_k c_{n-1-m+\ell}-c_{k-1-m+\ell}\right)h_\ell \right)\theta^k,$$ where we have used that $c_{k-1-m+\ell}=0$ for $k=0$ and $0\leq\ell\leq m$. Therefore it suffices to show that $\forall 0\leq k\leq n-1$: $$\sum_{\ell=0}^m \left(c_k c_{n-1-m+\ell}-c_{k-1-m+\ell}\right) h_\ell = -\sum_{\ell=0}^{m+1} c_{k-m-1+\ell} h_\ell$$ We compute the difference of both terms: $$c_k h_{m+1} + \sum_{\ell=0}^m c_{k-m-1+\ell} h_\ell + \sum_{\ell=0}^m c_k c_{n-1-m+\ell} h_\ell - \sum_{\ell=0}^m c_{k-1-m+\ell} h_\ell = c_k \Bigg(h_{m+1} + \underbrace{\sum_{\ell=0}^m c_{n-1-m+\ell} h_\ell}_{=-h_{m+1}}\Bigg)=0$$ $\square$