Existence of a real root for polynomials of odd degree

The fundamental theorem of algebra famously states that a polynomial of degree n with real coefficients, say p \in \mathbb{R}[x] , has n complex roots when counting multiplicities. This is equivalent to saying p(x) = \prod_{k=1}^{k=m} (x - \alpha_k)^{h_k} where h_1 + ... + h_m = n and \alpha_i \neq \alpha_j \in \mathbb{C} for all i,j = 1,...,m such that i \neq j . This is due to the ‘equivalence’ of roots and linear factors.

We will probably get round to proving this at some point so if you want to find out how don’t forget to follow us! Or just google how to prove the fundamental theorem of algebra – It is really up to you.

What is rather nice is that by throwing in the condition that n is odd we can guarantee the existence of a real root. The idea is nicely summed up in the Numberphile video:

Presumably if you watched the video you probably have a very good idea of how to prove the result but let us write it out in mathematics.

We have p \in \mathbb{R}[x] with degree n being odd and suppose p(x) = a_0 +a_1x + ... a_nx^n where a_i \in \mathbb{R} and a_n \neq 0 . Polynomials are continuous so we must have p being continuous. Looking at the behaviour of \frac{p(x)}{x^n} = \frac{a_o + ... + a_n x^n}{x^n} = \frac{a_n}{x^n} + ... + a_n as |x| \longrightarrow \infty we have \frac{p(x)}{x^n} \longrightarrow a_n . If we change x to -x , due to n being odd, x^n changes sign. The sign of \frac{p(x)}{x^n} for sufficiently large x always has the same sign as a_n so putting the two facts together means p(x) and p(-x) differ in sign – This is the ‘crossing the x-axis’. We know p is continuous so it is nice and in particular we can use the Intermediate Value Theorem. As 0 is in the image of p when we take |x| sufficiently large there must be an \alpha \in \mathbb{R} such that p(\alpha) = 0 by the intermediate value theorem.



Solving Linear Congruences

Imagine a scenario where you’re lost, lost in a big city full of number theorists, and you wish to ask someone for directions to get home. You approach someone and to your surprise they want you to work for the directions! In particular they want you to produce all the solutions of the linear congruence 4x \equiv 36 \mbox{ (mod } 6 ).

How do you go about getting the directions you so desperately need? Well, to solve a general linear congruence of the form ax \equiv b \mbox{ (mod } n ) it is important to remember the following theorem.

Theorem: ax \equiv b \mbox{ (mod } n ) has a solution iff \gcd(a,n) | b .

Let us write d = \gcd(a,n) and formulate an algorithm to solve our congruence ax \equiv b \mbox{ (mod } n ) – If you ever visit a city of number theorists I strongly recommend memorising this.

(1) – To even wish of having a solution we have to check that d | b .

(2) – Supposing d | b , use the Euclidean Algorithm to find s,t \in \mathbb{Z} such that sa + tn = d.

(3) – By using d | b there exists u \in \mathbb{Z} such that b = du so we have sau + tnu = du = b and rearranging gives sau - b = tnu so asu \equiv b \mbox{ (mod } n ) meaning x_0 = su is a solution to our congruence.

(4) – To get the other solutions we translate x_0 by \frac{nv}{d} where v \in \mathbb{Z} . This will exhaust all possible solutions mod n which are x_0, x_0 + \frac{n}{d},..., x_0 + \frac{(d-1)n}{d} .

You are now in a position to get home if you ever find yourself in such a scenario.

Dirichlet’s approximation

When you are first introduced to the real numbers you are almost forcefully told that they can be approximated by rationals numbers. The voice in your head goes something like ‘we can get as close as we like to an irrational by using rationals’. This is normally expressed in the statement \overline{\mathbb{Q}} = \mathbb{R} which reads \mathbb{Q} is dense in \mathbb{R} where ‘dense’ is a very precise mathematical statement.

It’s quite easy to think we are done here, but what invokes a good approximation? Dirichlet’s approximation is not only good in the sense you can control how close you want your rational approximation to be but it gives a splitting, in terms of behavior, with respect to rational and irrational numbers.

Theorem: For \alpha \in \mathbb{R} \backslash \mathbb{Q} we can find infinitely \frac{p}{q} \in \mathbb{Q} where \gcd(p,q) = 1 such that | \alpha - \frac{p}{q} | < \frac{1}{q^2}. Moreover, if \alpha \in \mathbb{Q} only finitely many approximations \frac{p}{q} exist.

Proof of theorem: We are fist going to introduce some notation. let x \in \mathbb{R} the integral part of x and the fractional part of x will be denoted and defined as [x] := \max \{z \in \mathbb{Z} : z \leq x \} and \{x\} := x - [x] respectively.

Let \alpha be irrational and Q be a positive integer.  The numbers 0, \{\alpha\}, \{2 \alpha \},..., \{Q\alpha \} gives us Q + 1 points between 0 and 1 that are distributed among the intervals [ \frac{j-1}{Q}, \frac{j}{Q} ) for j = 1,..., Q. Applying the pigeon hole principle means there has to be at least one interval containing at least two numbers \{k\alpha\} and \{l\alpha\} such that \{k\alpha\} \geq \{l\alpha\} with 0 \leq k, l \leq Q and k \neq l.

Computing the difference of \{k\alpha\} and \{l\alpha\} gives us \{k\alpha\} - \{l \alpha\} = k\alpha - [k\alpha] - l\alpha + [l\alpha] = \{(k-l)\alpha\} + [(k-l)\alpha] + [l\alpha] - [k\alpha]  which lies in the interval [0, \frac{1}{Q} ) meaning that [(k-l)\alpha] + [l\alpha] - [k\alpha] = 0 as the LHS is an integer. Setting q = k - l and p = [q \alpha] gives the property \{q \alpha\} < \frac{1}{Q} and so computing the difference between \alpha and \frac{p}{q} gives | \alpha - \frac{p}{q} | = \frac{|q\alpha - p |}{q} = \frac{\{q\alpha\}}{q} < \frac{1}{Qq}< \frac{1}{q^2} . The last inequality follows from q < Q .

To see the split in behaviour we first assume \alpha is irrational and that there are finitely many approximations \frac{p_1}{q_1},..., \frac{p_n}{q_n} . Since \alpha is irrational by the fact $latex  \overline{\mathbb{Q}} = \mathbb{R}$ we can fine Q (a positive integer) such that for all j = 1,...,n we have |\alpha - \frac{p_j}{q_j} | > \frac{1}{Q} which contradicts the established facts above.

In the second case when \alpha is a rational number, say \alpha = \frac{a}{b} with a \in \mathbb{Z} and b\in \mathbb{N} if \frac{a}{b} \neq \frac{p}{q} then by direct computation |\alpha - \frac{p}{q} | = \frac{|aq - bp|}{bq} \geq \frac{1}{bq} so we can only have finitely many such approximations as we require q < b .

Fermat’s Last Theorem (the divisible by 4 case)

Fermat’s last Theorem is infamous, it was unsolved for 358 years and when Andrew Wiles proved the result in 1994 the world received it so well he was offered an opportunity to model for gap jeans.

Although Fermat didn’t give his ‘proof’ of the result due to the width of the margin being too small he did give a proof of the case when n = 4 and hence proved the sub-sequential cases when n is divisible by 4. He did this by considering the more general Diophantine equation X^4 + Y^4 = Z^2 and using the chain that a solution of X^{4n} + Y^{4n} = Z^{4n} gives a solution of X^4 + Y^4 = Z^4 which gives a solution of X^4 + Y^4 = Z^2 it is sufficient to show the last equation has no integer solutions. The symmetry of the equation also means it is sufficient to consider positive integer solutions.

Theorem: The equation X^4 + Y^4 = Z^2 has no positive integer solutions.

Proof of Theorem:  We are going to give Fermat’s original proof which invokes the method of infinite descent. The idea of this method in the most imprecise and general way is to assume the existence of a ‘minimal’ something and show there is a more ‘minimal’ something of the same type hence giving a contradiction to conclude no something exists.

To begin, we assume that z is the least positive integer for which the equation X^2 + Y^2 = z^2 has a solution with positive integers x, y . Due to the minimality condition of z we can assume that \gcd(x,y) = 1 . This means at least one of x and y is odd and we shall assume x is odd. One can check a^2 \equiv 0 (mod 4 ) or a^2 \equiv 1 (mod 4 ) for any integer a . Using this knowledge z^2 = x^2 + y^2 \equiv 1 or 2 (mod 4 ) and as a square cannot be congruent to 2 mod 4 we must have z being odd. This implies that y is even.

Our solution x,y and z gives a primitive Pythagorean triple (x^2,y^2,z) so using the parametrization in our previous post we can conclude: x^2 = a^2 - b^2, y^2 = 2ab and z = a^2 + b^2 where a and b are coprime integers of opposite parity. If a is even and b is odd then x^2 \equiv a^2 - b^2 \equiv 0 - 1 = -1 ( mod 4 ) which is impossible. Thus, a is odd and b is even with b = 2c for some integer c. Looking back we observe that (\frac{1}{2}y)^2 = ac where \gcd(a,c) = 1 as a and b are coprime. This means that a and c are perfect squares so we can find coprime positive integers u and v such that a = u^2 and b = v^2 . Due to a being odd we must have u being odd.

Using the fact x^2 + b^2 = a^2 we can conclude that (2v^2)^2 + x^2 = (u^2)^2 where the integers 2v^2,x and u^2 have no common factor pairwise. This means (2v^2,x,u^2) is a primitive Pythagorean triple so using the parametrization of such triples we have two coprime positive integers A and B such that 2v^2 = 2AB and u^2 = A^2 + B^2 .

From 2v^2 = 2AB we have v^2 = AB and as \gcd(A,B) = 1 we must have some positive coprime integers X and Y where A = X^2 and B = Y^2 . Looking at the equation u^2 = A^2 + B^2 we must have u^2 = X^4 + Y^4.

Following the method of infinite decent we have constructed a new solution (X,Y,u) from our minimal solution (x,y,z). However, u \leq u^2 \leq a \leq a^2 < a^2 + b^2 = z so we have in fact constructed a ‘more’ minimal solution which impossible by our assumption on z. This means that our hypothesis that a minimal solution exists or any solution existing is false so we conclude X^4 + Y^4 = Z^2 has no positive integer solutions.


Pythagorean Triples

When you talk to the average human about mathematics with a very high probability you can expect a discussion about the Pythagorean theorem. If you’re unaware of this theorem not only am I very shocked but part of me wants to tell you’re in the wrong part of the Internet. Jokes aside this post isn’t about the theorem but is instead about looking for solutions of the Pythagorean equation that are integers. For completeness the so-called Pythagorean equation is X^2 + Y^2 = Z^2 .

We are interested in solutions of this equation in the integers and due to the symmetry of the equation it suffices to consider only non-negative integers. A solution (x,y,z) \in \mathbb{Z}^3 is called a Pythagorean triple and given such a triple, (ax,ay,az ) is also a Pythagorean triple for any a \in \mathbb{Z}.

As we want to understand the integer solutions of the Pythagorean equation X^2 + Y^2 = Z^2 it makes sense to consider triples (x,y,x) where the components are pair-wise coprime and non-negative. This follows from the above observations and we call such solutions primitive.

Pythagoras himself constructed an infinite number of Pythagorean triples by using the identity (2n+1)^2 + (2n^2+2n)^2 = (2n^2+2n+1)^2 . It is worth verifying this identity and finding a triple that isn’t in its form.

In fact this problem is very classical, some may say ancient, as in the third century B.C. Euclid solved the problem of finding all such integer solutions.

Theorem: let a,b \in \mathbb{Z}^+ such that \gcd(a,b) = 1, one is even and the other is odd and a > b, then the triple (x,y,z) \in \mathbb{Z}^3 given by x = a^2 - b^2, y = 2ab and z = a^2 + b^2 is a primitive solution of the Pythagorean equation. Moreover, each primitive solution is of this form.

Proof of Theorem: Let a,b \in \mathbb{Z}^+ be such as in our hypothesis along with the triple (x,y,z). It is easy to verify that this triple is indeed Pythagorean by simply computing x^2 +y^2 = (a^2 -b^2)^2 +(2ab)^2 = a^4 +2a^2b^2 +b^4 = (a^2 +b^2) = z^2 . Clearly x,y,z are positive integers so we need to show they are pairwise coprime to deduce the triple is primitive. If d = \gcd(x,y,z) then d divides both x + z = 2a^2 and z - x = 2b^2 by the linear property of division. As we assumed that a,b are coprime we must have either d = 1 or d = 2. In the second case, if d=2 , we have a contradiction due to say a being even and b being odd. Bringing this together we have shown (x,y,z) is a primitive Pythagorean triple.

To show each primitive solution is of the form in our hypothesis we let (x,y,z) be a primitive Pythagorean triple. As they are all pairwise coprime and satisfy x^2 + y^2 = z^2 we can conclude that y is even and x,z are odd. I’m leaving this for you to verify and as a hint you might want to look mod 8 .

Using the fact we have a pythagorean triple we deduce the identity (\frac{y}{2})^2 = \frac{1}{4}(x^2-z^2) = \frac{1}{2}(x-z)\frac{1}{2}(x+z). Due to the parity of x and z we observe \frac{1}{2}(z+x) and \frac{1}{2}(z-x) are both integers. We can in fact conclude they are coprime due the coprime conditions of x,y and z . Looking at our identity the factors on the right have no common divisors so they must both be squares. In particular we can find a,b \in \mathbb{Z}^+ such that a^2 = \frac{1}{2}(z+x) and b^2 = \frac{1}{2}(z-x). It follows that \gcd(a,b) =1 due to \gcd(\frac{1}{2}(z+x),\frac{1}{2}(z-x)) =1 .

Its not hard to notice that a^2 - b^2 = x, 2ab = y and a^2 + b^2 = z hence giving us our Pythagorean triple. The last task is to show that a,b are of different parity. We compute a +b \equiv a^2 +b^2 \equiv 1 ( mod 2 ) showing us a +b is odd and by the way parity changes under addition we know a and b have different parity. This means we’ve constructed the parametrization a,b for our triple (x,y,z) as described in the statement of the theorem.

One Topology to rule all normed spaces of a fixed dimension

A normed space is a vector space V over a field \mathbb{F} equipped with a so called ‘norm’ which is a function \lVert . \rVert : V \longrightarrow \mathbb{R} that satisfies a list of axioms. The intuition behind such a function is to give each elements in V a ‘size’. This is a strong piece of information and allows one to vision V as a metric space and hence induce a topology onto V. I am going to assume you’ve seen these concepts before and have knowledge of continuous functions in particular their topological definition and how they act on compact sets.

Looking at the sequence normed space \longrightarrow metric space \longrightarrow topology one can ask the very natural questions: what conditions on V and \lVert . \rVert give the same topology? What normed spaces don’t have the same topology? etc etc etc. The list goes on.

As the name of this post suggests we are going to show that when our underlying vector space V is of a fixed finite dimension (we are going to assume V is over \mathbb{R} or \mathbb{C} ) then there is only one topology that is induced. In some sense this means we know what notion of neighborhoods to expect if we’re in the finite world playing over the most ‘natural’ field. There is only one such notion.

In a more precise fashion what we are going to show is that any two norms on a finite dimensional space V over \mathbb{R} or \mathbb{C} determine the same topology.

For convenience we will let \mathbb{F} be our background field which will either be the real numbers or the complex numbers. Suppose V has dimension n with basis e_1,...,e_n. This means every element in V has a unique representation of the form \sum_{i=1}^{n}\lambda_i e_i where \lambda_i \in \mathbb{F} for all i . To get our result we shall define the ‘special’ Euclidean norm on V as \lVert x\rVert_{E} := (\sum_{i=1}^{n}|\lambda_i|^2)^{\frac{1}{2}}. One can check this is a norm. We also let \lVert.\rVert : V \longrightarrow \mathbb{R} be an arbitrary norm on V.

How do we show these norms induce the same topology? We find constants 0 \neq M, m \in \mathbb{R} such that m \lVert x \rVert_{E} \leq \lVert x \rVert \leq M \lVert x\rVert_{E} for all x \in V. The reason why this is sufficient is because in terms of the induced topologies an open ball in one topology will contain an open ball of the other and vice versa. If you’re not convinced take a moment to try to see why(It’s very instructive in getting familiar with the theory).

Let us start by determining M. Let x \in V by using the unique representation in terms of our basis and the axioms of a norm we can estimate the norm like so \lVert x \rVert = \lVert \sum_{i=1}^{n} \lambda_i e_i \rVert \leq \sum_{i=1}^{n} \lVert \lambda_i e_i \rVert = \sum_{i=1}^{n} |\lambda_i| \lVert x\rVert . Using Cauchy-Schwartz we can estimate even further and deduce \lVert x \rVert \leq (\sum_{i=1}^{n}|\lambda_i|^2)^\frac{1}{2} (\sum_{i=1}^{n}| \lVert e_i \rVert^2)^\frac{1}{2} hence we have \lVert x \rVert \leq M \lVert x \rVert_{E} where M = (\sum_{i=1}^{n} \lVert e_i \rVert^2)^\frac{1}{2} > 0 .

That was easy enough, right? If you’ve been doing mathematics long enough you notice the majority of mathematical proofs have an easy direction and a hard direction. That was the easy direction. Determining m is more difficult, it isn’t insanely hard, and relies on the Heine-Borel Theorem and some properties of continuous functions.

Let us first define a function f_{\lVert . \rVert} : \mathbb{F}^n \longrightarrow \mathbb{R} by f(\lambda_1,...,\lambda_n) := \lVert \sum_{i=1}^{n} \lambda_i e_i \rVert . I mentioned continuity and so it’s not surprising that f_{\lVert . \rVert}   is continuous with respect to the standard topology on \mathbb{F}^n.

To show f_{\lVert . \rVert} is continuous we exploit the triangle inequality of the norm \lVert . \rVert . Let \epsilon > 0 and pick \delta = \epsilon and (\alpha_1,...,\alpha_n), (\beta_1,...,\beta_n) \in \mathbb{F}^n be such that (\sum_{i =1}^n |\alpha_i - \beta_i|^2)^{1/2} < \delta and let H := \max_{1 \leq i \leq n} (\lVert e_i \rVert ) . We estimate | \; \lVert \sum_{i=1}^n \alpha_i e_i \rVert - \lVert \sum_{i=1}^n \beta_i e_i \rVert \; | \leq \lVert  \sum_{i=1}^n (\alpha_i - \beta_i) e_i \rVert \leq \sum_{i=1}^n |\alpha_i - \beta_i | \lVert e_i \rVert  \leq H \sum_{i=1}^n |\alpha_i - \beta_i | \leq n^{\frac{1}{2}} H(\sum_{i =1}^n |\alpha_i - \beta_i|^2)^{1/2} \leq  n^{\frac{1}{2}} H\epsilon with the second to last inequality coming from Cauchy-Schwartz. Hence f_{\lVert . \rVert } is continuous.

We also define the set U := \{\lambda_1,...,\lambda_n) \mathbb{F}^n : \sum_{i=1}^{n} |\lambda_i|^2 = 1 \} which is the unit-circle in \mathbb{F}^n . It follows that U is compact with respect to the standard norm on \mathbb{F}^n . To show this we use the the Heine-Borel Theorem which in its statement means it is necessary and sufficient to show that U is closed and bounded as we are working over \mathbb{F}^n .

The fact U is bounded follows straight from the definition so we only need to show that U is closed. This is the part where f_{\lVert .\rVert} comes in as one can check that U = f_{\lVert . \rVert_{E} }^{-1}(\{1\}) where f_{\lVert . \rVert_{E} }^{-1} is the pre-image of f_{\lVert . \rVert_{E} } . As \{1\} is closed in \mathbb{R} and f_{\lVert . \rVert_{E} } is continuous we have that U is closed and hence it is compact by the Heine-Borel Theorem.

We’ve done the set-up so now let us get onto proving our actual result. To do this we shall restrict our function f_{\lVert . \rVert } onto the set U and ask ourself what the value m := \inf_{x \in U} (f_{\lVert . \rVert }(x) ) is? As f_{\lVert .\rVert } is continuous and U is compact we can use a property of continuous functions to deduce that there exists an \alpha \in A such that m = f_{\lVert . \rVert }(\alpha) . Suppose \alpha = (\alpha_1,..,\alpha_n) and that m =0 then f(\alpha_1,...,\alpha_n) = \lVert \sum_{i=1}^{n} \alpha_i e_i \rVert = 0 and so \sum_{i=1}^{n} \alpha_i e_i = 0 by properties of the norm and by the linear independence of the basis we must have \alpha_i = 0 for all i \in \{1,...,n\}. This means \alpha = 0 which is a contradiction as 0 \notin U. Bringing this all together m > 0 and by the definition of m we have shown \lVert x \rVert \geq m > 0 when \lVert x \rVert_{E} = 1 .

All x \in V can be written in the form x = \lVert x \rVert_{E}y for some y \in V such that  \lVert y \rVert_{E} = 1 or equivalently where y = \sum_{i=1}^{n}\lambda_i e_i where (\lambda_1,...,\lambda_n) \in U we can say \lVert x \rVert = \lVert x \rVert_{E} \lVert y \rVert  > m\lVert x \rVert_{E} where m \neq 0.

What we’ve shown is that every possible norm on a vector space of a specified dimension over \mathbb{R} or \mathbb{C} induces the same topology,  in other words, as the title suggests there is one topology to rule all normed spaces of a fixed dimension… over \mathbb{R} or \mathbb{C} .

Simple Bounds of Sum Sets

This post is a bit different to what has currently appeared on our blog and fits in the realm of arithmetic combinatorics. We’ll be looking at finite subsets A,B \subseteq \mathbb{Z} of the integers and their designated sum set A + B := \{a + b : a\in A, b\in B\} . Within this set-up we are going investigate the relationship between the relative sizes of the three set A,B and A+B.

What can we say? Well, our first observation is that the size of a finite subset of \mathbb{Z} is invariant under translation which in symbols is represented by |A+\{a\}| = |A| for some a \in \mathbb{Z} . This is rather intuitive and follows from the properties of + . In the most general setting by making no assumptions on the structure of A,B \subseteq \mathbb{Z} one obtains the relationship shown in the theorem bellow.

Theorem: Let A,B \subseteq \mathbb{Z} be finite subsets then we have |A| + |B| - 1 \leq |A+B| \leq |A||B|

Proof of Theorem: Starting with the upper bound we define the function \varphi : A \times B \longrightarrow \mathbb{Z} by \varphi(a,b) = a + b which allows us to think of the sum set as the image of \varphi. In symbols this is A + B = Im\varphi. As A and B are both finite we have Im\varphi is largest when \varphi is injective which gives us the upper bound |A+B| \leq |A||B| .

To show the lower bound we exploit the ordering of the integers by translating both sets A and B. let M = \max(A) and m= \min(B) and depending on the signs of M, m we translate A by \pm M and B by \pm m with the outputs A^* and B^* such that \max(A^*) = 0 = \min(B^*) . By our observation before we have |A| = |A^*| and |B| = |B^*| and it’s important to note we also have |A+B| = |A^* + B^*| . By the design of our translations we have 0 \in A^* \cap B^* which implies A^*\cup B^* \subseteq A^* + B^* and also as A^* consist of non-positive integers and B^* consists of non-negative numbers we have |A^*\cup B^*| =|A^*| + |B^*| - 1 and hence |A| + |B| - 1 \leq |A+B| .

When given an inequality the first thing to ask is when do we get equality and I challenge you to find a pair of finite sets that obtain equality in our theorem! Try to find families of sets with some structure and not sets like A = \{4,6\} and B = \{98,34\} (for the upper bound).