15/16: Group 7

From LeicesterIPSC
Jump to: navigation, search

On this page we look in depth at the quartic polynomial $f(x)=x^4-4x+144$. We will study the irreducibility of $f(x)$ over different fields and look at what field extensions can be constructed using $f(x)$.

Factorisation over $\mathbb{C},\mathbb{R}$, $\mathbb{Q}$ and $\mathbb{Z}$

Factorisation over $\mathbb{C}$

Over $\mathbb{C}$, we expect our polynomial to be reducible into linear terms, by the fundamental theorem of algebra. To see this, let $y=x^2$, and consider \begin{align*} f(y)=y^2-4y+144. \end{align*} the roots of this polynomial can easily be calculated by the quadratic formula. From this we can deduce the roots of our original polynomial $f(x)$. \begin{align*} y^2 & = 2\pm 2\sqrt{35}i \\ \Rightarrow x & = \pm\sqrt{2\pm 2\sqrt{35}i} \end{align*} and so we have, as expected, an expression of $f(x)$ in terms of linear polynomials \begin{align*} f(x)=(x-(\sqrt{7}+\sqrt{5}i))(x-(\sqrt{7}-\sqrt{5}i))(x+(\sqrt{7}+\sqrt{5}i))(x+(\sqrt{7}-\sqrt{5}i)) \end{align*} and so $f(x)$ is reducible over $\mathbb{C}$.

Factorisation over $\mathbb{R}$

We see all the roots of $f(x)$ are $4$ complex. This means there are no roots in $\mathbb{R}$, so our factorisation in $\mathbb{R}$ cannot contain a linear term. This means the only possible factorisation left is of a product of two quadratic polynomials. From the roots calculated in the previous section, intuitively, we might try to combine those linear terms with roots that are conjugates of one another. In doing this, we obtain the following factorisation \begin{align*} f(x)=(x^2-2\sqrt{7}x+12)(x^2+2\sqrt{7}x+12). \end{align*} So, $f(x)$ is also reducible over $\mathbb{R}$.

Factorisation over $\mathbb{Q}$ and $\mathbb{Z}$

To check reducibility over $\mathbb{Q}$, we could use the same reasoning as we did for reducibility over $\mathbb{R}$. Since all the roots are complex, there can be no linear terms and the quadratic factors both contain irrational coefficients, so there can be no quadratic terms either. Thus $f(x)$ is irreducible over $\mathbb{Q}$

Alternatively, we can check the irreducibility of $f(x)$ over $\mathbb{Q}$ by looking at the minimal polynomial of its roots. Let $\alpha=\sqrt{7}+\sqrt{5}i$. We can construct the minimal polynomial of $\alpha$, $m_\alpha(x)$ in the following way. \begin{align*} \alpha-\sqrt{7}&=\sqrt{5}i\\ \Rightarrow \alpha^2-2\sqrt{7}\alpha+7&=-5\\ \Rightarrow \alpha^2+12&=2\sqrt{2}\\ \Rightarrow \alpha^4+24\alpha^2+144&=28\\ \Rightarrow \alpha^4-4\alpha^2+144&=0. \end{align*}

So we see that the minimal polynomial of $\alpha$ is in fact $f(x)$, and so $f(x)$ is irreducible over $\mathbb{Q}$.

It also follows that, since $f(x)$ is irreducible over $\mathbb{Q}$, it is also irreducible over $\mathbb{Z}$.

Factorisation over finite fields

Perhaps more interesting is the reducibility of $f(x)$ over finite fields, $\mathbb{Z}_p$ for some prime number $p$. Checking the reducibility over $\mathbb{Z}_p$ is much trickier than over $\mathbb{C}$, $\mathbb{R}$ etc. We do, of course, now have brute force as a valid check for roots of $f(x)$ over $\mathbb{Z}_p$, since there are now only a finite number of possibilities for roots. Of course, prime numbers can be arbitrarily large, so checking for roots could take a while. It is however very easy to implement such a check on a computer, so at the very least we can think of this as our last resort for checking for roots.

But what happens if we go through all of this checking to discover that there aren't in fact any roots of $f(x)$ over $\mathbb{Z}_p$? This doesn't imply that the polynomial is irreducible, as it could still factor into quadratic terms. For this we need to change our approach.

Suppose then that we want to factorise f(x) in the following way \begin{align*} f(x)=(x^2+ax+b)(x^2+cx+d) \end{align*} for some integers $a,b,c$ and $d$. A good start is to compare the coefficients when we expand this factorisation to the coefficients of $f(x)$ and solve the resultant set of congruences. The following calculations work, in general, for a polynomial of the form \begin{align*} g(x)=x^4+Ax^2+B^2 \end{align*} for integers $A$ and $B$, so we shall solve the general case and note that our polynomial $f(x)$ is of this form with $A=-4$ and $B=12$.

Factorisation of $x^4+Ax^2+B^2$

Let $g(x)=x^4+Ax^2+B^2$ with $A,B\in\mathbb{Z}$. Comparing the coefficients of $g(x)$ and those of the expansion $(x^2+ax+b)(x^2+cx+d)$ yield the following set of congruences; \begin{align} a+c & \equiv 0 \mod p\\ ac+b+d & \equiv A \mod p\\ ad+bc & \equiv 0 \mod p\\ bd & \equiv B^2 \mod p. \end{align} From our first equation we deduce that $c\equiv-a\mod p$. Multiplying the third equation by $d$ and substituting the fourth into the resultant equation yields \begin{align} a(d^2-B^2)\equiv 0\mod p. \end{align} Now, since $p$ is prime, we have two possible cases, $d^\equiv B^2\mod p$ or $a\equiv 0 \mod p$. (It is possible for both cases to be fulfilled simultaneously, but we need only concentrate on having one of them satisfied).

Case 1: $d^2\equiv B^2\mod p$

In this case we have $d\equiv\pm B\mod p$ and so $b\equiv d\mod p$. Plugging this into $ac+b+d\equiv A\mod p$ from before we get \begin{align} a^2&\equiv 2d-A\mod p\\

  &\equiv \pm 2B-A\mod p.

\end{align} This means, that if $\pm 2B-A$ is a quadratic residue $\mod p$, then $g(x)$ has the factorisation \begin{align} g(x)=(x^2+ax+d)(x^2-ax+d) \end{align} where $d\equiv\pm B\mod p$ and $a^2\equiv 2d-A\mod p$.

Example

Let $p=7$. In our polynomial with $A=-4$ and $B=12$ we see that $-2B-A\equiv 1\mod 7$, and $1$ is a quadratic residue $\mod 7$, so $f(x)$ can be factored as \begin{align} f(x)=(x^2+x+2)(x^2+6x+2)\mod 7. \end{align}

If $\pm 2B-A$ is not a residue $\mod p$, then we must be in case 2.

Case 2: $a\equiv 0\mod p$

In this case we also have $c\equiv 0\mod p$, and so we are now considering a factorisation of the form $(x^2+b)(x^2+d)$ where $b$ and $d$ satisfy \begin{align} b+d&\equiv A\mod p\\ bd&\equiv B^2\mod p. \end{align}

Example

Let $p=11$. In our polynomial with $A=-4$ and $B=12$ we see that $2B-A\equiv 6\mod 11$ and $-2B-A\equiv 2\mod 11$, neither of which are quadratic residues $\mod 11$. So now we look at the set of congruences \begin{align} b+d&\equiv 7\mod p\\ bd&\equiv 1\mod p \end{align} and note that $b=3$ and $d=4$ is a solution. Thus, we have that $f(x)$ has the following factorisation \begin{align} f(x)=(x^2+3)(x^2+4)\mod 11. \end{align}

I would like to say that these congruences will always have solutions when $\pm 2B-A$ is not a quadratic residue $\mod p$, but this assignment is due tomorrow and I really want to go to bed. So instead of proving this, we shall look at a computer implementation of this result and see that there is empirical evidence to support this proposition being true.

We can note, however, that from the above congruences, we can deduce that \begin{align} Ad & \equiv B^2+d^2\\ \Rightarrow -(2B-A)d & \equiv (B+d)^2. \end{align} Since $2B-A$ is not a quadratic residue $\mod p$, $-(2B-A)$ is a quadratic residue if and only if $p\equiv 3\mod 4$. If we do in fact have $p\equiv 3\mod 4$ then we can deduce that both $b$ and $d$ are quadratic residues $\mod p$, which means we half the number of elements we need to test. In the case where $p\equiv 1\mod p$ we just test the non-residues instead. (Here of course we are assuming $p$ is an odd prime).

Factorisation using a computer

The above calculations can be easily implemented as a code in MATLAB. Below is a short code I wrote to do this.

   function [a,b,c,d]=quartic_factors(A,B,p)
   
   % ------------------------------------------------------------------------
   % | This function factorises a quartic polynomial of the form            |
   % | x^4+Ax^2+B^2 over the finite field Z_p, into quadratic polynomials   |
   % | of the form x^2+ax+b and x^2+cx+d. The output is a vector with       |
   % | entries corresponding to the coefficients of these quadratic         |
   % | [a,b,c,d].                                                           |
   % ------------------------------------------------------------------------
   
   x=zeros(round((p-1)/2),2); % creates a vector of the quadratic residues 
   for i=1:(p-1)/2            % of Z_p
       x(i,1)=i;   x(i,2)=mod(i^2,p);
   end
   q1=x(x(:,2)==mod(2*B-A,p),1);   % determines if +/-2B-A are quadratic
   q2=x(x(:,2)==mod(-2*B-A,p),1);  % residues in Z_p
   if q1>-1  % if q1 is a residue, our factorisation will be based on it
       a=q1;   b=mod(B,p); c=mod(-a,p);    d=b;
   elseif q2>-1 % if q1 isn't a residue, we use q2
       a=q2;   b=mod(-B,p);    c=mod(-a,p);    d=b;
   else % if q1 & q2 are both nonresidues in Z_p we try a different approach
       a=0; c=0;
       if mod(p,4)==3 % in this case we know b & d are quadratic residues,
           y=x(:,2);  % so we need only to check the residues in Z_p
       else
           y=1:p-1;        % otherwise we must check through the nonresidues
           for i=1:(p-1)/2
               y(y==x(i,2))=[];
           end
       end
       for i=1:(p-1)/2 % checks each possible combination of (non)residues
           if mod(y(i)*y(y==mod(A-y(i),p)),p)==mod(B^2,p)
               b=y(i); d=y(y==mod(A-y(i),p));
               break
           end
       end
   end

Running this with the following script

   F=zeros(length(primes),5);
   for i=1:length(primes)
       [a,b,c,d]=quartic_factors(-4,12,primes(i));
       F(i,:)=[primes(i), a, b, c, d];
   end
   disp(array2table(F,'VariableNames',{'P' 'a' 'b' 'c' 'd'}))

where 'primes' is just a vector of prime numbers yields the following results for our polynomial $f(x)$

Results from running the above code through MATLAB.
Coefficients $a, b, c$ and $d$ for for factorisations over $\mathbb{Z}_p$. The code created this table for the first $1000$ primes in 10.4 seconds, so if a computer is at hand, brute force is a valid way to factorise these types of polynomials.

For example, we have $f(x)\equiv(x^2+12x+29)(x^2+29x+29)\mod 41$ and $f(x)\equiv(x^2+2444x+7889)(x^2+5457x+7889)\mod 7901$.


Field extensions

Constructing a field such that of $f(x)$ has a root

We know that $f(x)$ is an irreducible polynomial, and so we have that in the ring $\mathbb{Q}[x]$ the ideal $I$ generated by $f(x)$ is a maximal ideal. This means that we can construct a field by considering the quotient $E=\mathbb{Q}[x]/I$. Let $\theta=x+I$, then we see that \begin{align} f(\theta)&=\theta^4-4\theta^2+144\\ &=(x+I)^4-4(x+I)^2+(144+I)\\ &=(x^4-4x^2+144)+I\\ &=f(x)+I\\ &=I\\ &=0. \end{align} Thus we see that $\theta$ is a root of $f(x)$ over $E$. This means that we can factorise $f(x)$ over $E$. For ease of notation we will denote our unknown by $y$ instead of $x$. That is, we will look at the ring $E[y]$. By polynomial long division we get that $f(y)=(y-\theta)(y^3+\theta y^2+(\theta^2-4)y+\theta(\theta^2-4))$. We can factorise this further still, so we have \begin{align} f(y)=(y-\theta)(y+\theta)(y^2+(\theta^2-4)). \end{align} By inspection it is not clear whether or not $(y^2+(\theta^2-4)$ can be factorised further. To find a field for which $f(x)$ can be decomposed as linear terms we will try a different approach.

Constructing fields containing every root of $f(x)$

Recall that $\alpha=\sqrt{7}+\sqrt{5}i$ is a root of $f(x)$. We saw that the minimal polynomial of $\alpha$ had degree $4$, so the field $\mathbb{Q}(\alpha)$ has degree $4$ when considered as a vector space over $\mathbb{Q}$. We can also see this as $\mathbb{Q}(\alpha)=\mathbb{Q}(\sqrt{7},\sqrt{5}i)=(\mathbb{Q}(\sqrt{7}))(\sqrt{5}i)$. So $[\mathbb{Q}(\alpha):\mathbb{Q}]=[(\mathbb{Q}(\sqrt{7}))(\sqrt{5}i):\mathbb{Q}(\sqrt{7})][\mathbb{Q}(\sqrt{7}):\mathbb{Q}]$. Since $\sqrt{7}$ has minimal polynomial $x^2-7$, $[\mathbb{Q}(\sqrt{7}):\mathbb{Q}]=2$ and $\sqrt{5}i$ has minimal polynomial $x^2+5$, $[(\mathbb{Q}(\sqrt{7}))(\sqrt{5}i):\mathbb{Q}(\sqrt{7})]=2$. So $[\mathbb{Q}(\alpha):\mathbb{Q}]=2\dot 2=4$. We also have that the basis of $\mathbb{Q}(\alpha)$ is given by $\{1,\sqrt{7},\sqrt{5}i,\sqrt{35}i\}$. Clearly $\alpha,-\alpha\in\mathbb{Q}(\alpha)$, which makes two of the roots. The other roots are given by $\pm(\sqrt{7}-\sqrt{5}i)$ which are also clear in $span\{1,\sqrt{7},\sqrt{5}i,\sqrt{35}i\}=\mathbb{Q}(\alpha)$.

Constructing fields of size $p^n$

We have seen in the last section that we can factorise $f(x)$ of $\mathbb{Z}_p$ for all primes $p$ into a product of quadratic polynomials. We can use these quadratics to form fields of order $p^2$ as it turns out for $p>3$ these quadratics are irreducible $\mod p$. For example the field $E=\mathbb{Z}_{29}[x]/(x^2+17x+12)$ contains $29^2$ elements. We can see this since $\{1,x\}$ forms a basis for $E$, and so $E=\{a+bx|a,b\in\mathbb{Z}_{29}\}$ and so there are $29$ elements $a$ could be and $29$ elements $b$ could be, so $|E|=29^2=841$.