Polynomials and Commutativity

Standard

In high school, I came to know about the statement of the fundamental theorem of algebra:

Every polynomial of degree n with integer coefficients have exactly n complex roots (with appropriate multiplicity).

In high school, a polynomial = a polynomial in one variable. Then last year I learned 3 different proofs of the following statement of the fundamental theorem of algebra [involving, topology, complex analysis and Galois theory]:

Every non-zero, single-variable, degree n polynomial with complex coefficients has, counted with multiplicity, exactly n complex roots.

A more general statement about the number of roots of a polynomial in one variable is the Factor Theorem:

Let R be a commutative ring with identity and let p(x)\in R[x] be a polynomial with coefficients in R. The element a\in R is a root of p(x) if and only if (x-a) divides p(x).

A corollary of above theorem is that:

A polynomial f of degree n over a field F has at most n roots in F.

(In case you know undergraduate level algebra, recall that R[x] is a Principal Ideal Domain if and only if R is a field.)

The key fact that many times go unnoticed regarding the number of roots of a given polynomial (in one variable) is that the coefficients/solutions belong to a commutative ring (and \mathbb{C} is a field hence a commutative ring). The key step in the proof of all above theorems is the fact that the division algorithm holds only in some special commutative rings (like fields). I would like to illustrate my point with the following fact:

The equation X^2 + X + 1 has only 2 complex roots, namely \omega = \frac{-1+i\sqrt{3}}{2} and \omega^2 = \frac{-1-i\sqrt{3}}{2}. But if we want solutions over 2×2 matrices (non-commutative set) then we have at least  3 solutions (consider 1 as 2×2 identity matrix and 0 as the 2×2 zero matrix.)

\displaystyle{A=\begin{bmatrix} 0 & -1 \\1 & -1 \end{bmatrix}, B=\begin{bmatrix} \omega & 0 \\0 & \omega^2 \end{bmatrix}, C=\begin{bmatrix} \omega^2 & 0 \\0 & \omega \end{bmatrix}}

if we allow complex entries. This phenominona can also be illusttrated using a non-commutative number system, like quaternions. For more details refer to this Math.SE discussion.

Advertisements

Four Examples

Standard

Following are the four examples of sequences (along with their properties) which can be helpful to gain a better understanding of theorems about sequences (real analysis):

  • \langle n\rangle_{n=1}^{\infty} : unbounded, strictly increasing, diverging
  • \langle \frac{1}{n}\rangle_{n=1}^{\infty} : bounded, strictly decreasing, converging
  • \langle \frac{n}{1+n}\rangle_{n=1}^{\infty} : bounded, strictly increasing, converging
  • \langle (-1)^{n+1}\rangle_{n=1}^{\infty} : bounded, not converging (oscillating)

I was really amazed to found that x_n=\frac{n}{n+1} is a strictly increasing sequence, and in general, the function f(x)=\frac{x}{1+x} defined for all positive real numbers is an increasing function bounded by 1:

 

Thre graph of x/(1+x) for x>0. Plotted using SageMath 7.5.1

The graph of x/(1+x) for x>0, plotted using SageMath 7.5.1

 

Also, just a passing remark, since \log(x)< x+1 for all x>0, and as seen in prime number theorem we get an unbounded increasing function \frac{x}{\log(x)} for x>1

dort

The plot of x/log(x) for x>2. The dashed line is y=x for the comparison of growth rate. Plotted using SageMath 7.5.1

 

Magic Cubes

Standard

Last week I attended a talk (by a student) about Magic Squares. I learned a bunch of cool facts about them (like how to devise an algorithm to construct them). Towards the end of the talk, one student from the audience suggested the possibility of Magic Cubes. I got very excited about this idea since it pointed towards the stereotypical mathematical ideology of generalizing the examples in order to see the deeper connections.

I myself don’t know much about Magic Cubes (or even Magic Squares) but would like to quote W. W. Rouse Ball & H. S. M. Coxeter from pp. 217 the book “Mathematical Recreations and Essays” (11th Ed.) :

A Magic Cube of the n^{th} order consists of the consecutive numbers from 1 to n^3, arranged in the form of a cube, so that the sum of the numbers in every row, every column, every file, and in each of the four diagonals (or “diameters “), is the same-namely, \frac{1}{2}(n^3 + 1). This sum occurs in 3n^2 + 4 ways. I do not know of any rule for constructing magic cubes of singly-even order. But such cubes of any odd or doubly-even order can be constructed by a natural extension of the methods already used for squares.

I would like to read about these magic hyper-cubes in future. And if you know something interesting about them, let me know in the comments below.

Counting Cycles

Standard

During one of my reading projects in 2015, I read about the Enigma cipher machine. While reading about it, I came to know that the number of possible keys of this machine is 7, 156, 755, 732, 750, 624, 000. One can see the counting procedure at pp. 22 of this document. But the counting procedure was not found to be satisfactory by most members of the audience (during my presentation). My failure to convince the audience that the counting procedure was correct, lead to my distrust in the counting arguments in general. Many times, I still, find the counting procedures controversial.

So, in an attempt to regain the trust, I will present two counting procedures for counting the number of cycles of length r when n objects (colours/beads/numbers) are given.

Procedure A: Using multiplication principle
Step 1: Choose r objects from the n choices.
Step 2: Arrange the selected r objects in a cyclic order.

  1. Since the Step 1 and Step 2 are independent of each other but should be performed together, we will multiply the results (i.e. use the multiplication principle). From Step 1 we will get \binom{n}{r} and from Step 2, we will get (r-1)! as per the circular permutation formula. Hence we get:

\displaystyle{\# r-\text{cycles from } n \text{ objects} =\binom{n}{r}\times(r-1)! = \frac{n!}{r (n-r)!}}

Procedure B: Using division principle
Step 1: Permute r of the n objects.
Step 2: Realise the mistake that you counted the permutations r extra times because these circular permutations of objects are equivalent since the circle can be rotated.

Since in Step 2 we want to correct the overcounting mistake of Step 1 performed for different objects simultaneously, we will divide the result of Step 1 by the result of Step 2. From Step 1 we will get ^n P_r and from Step 2 we will get r. Hence we get:

\displaystyle{\# r-\text{cycles from } n \text{ objects} =\frac{^n P_r}{r} = \frac{n!}{r (n-r)!}}

I am still not happy with the Procedure B, so if you have a better way of stating it please let me know.

When the intuition is correct

Standard

Before starting college I read Paul Zeitz’s The Art and Craft of Problem Solving (a must read book along with the books by Arthur Engel and Terence Tao) and after the first example to illustrate Psychological Strategies he writes (pp. 15):

Just because a problem seems impossible does not mean that it is impossible. Never admit defeat after a cursory glance. Begin optimistically; assume that the problem can be solved. Only after several failed attempts should try to prove impossibility. If you cannot do so, then do not admit defeat. Go back to the problem later.

And today I will share a problem posed by August Ferdinand Möbius around 1840:

Problem of the Five Princes:
There was a king in India who had a large kingdom and five sons. In his last will, the king said that after his death the sons should divide the kingdom among themselves in such a way that the region belonging to each son should have a borderline (not just a point) in common with the remaining four regions. How should the kingdom be divided?

The hint is in the title of this blog post. The solution is easy, hence I won’t discuss it here. The reader is invited to write the solution as a comment to this post.

Prime Polynomial Theorem

Standard

I just wanted to point towards a nice theorem, analogous to the Prime Number Theorem, which is not talked about much:

# irreducible monic polynomials with coefficients in \mathbb{F}_q and of degree n \sim \frac{q^n}{n}, for a prime power q.

The proof of this theorem follows from Gauss’ formula:

# monic irreducible polynomialswith coefficients in \mathbb{F}_q and of degree n = \displaystyle{\frac{1}{n}\sum_{d|n}\mu\left(\frac{n}{d}\right)q^d}, by taking d=n.

 

For details, see first section of this: http://alpha.math.uga.edu/~pollack/thesis/thesis-final.pdf

Recursion and Periodicity

Standard

One of the simplest recursive formula that I can think of is the one which generates the Fibonacci sequence, F_{n+1} = F_n +F_{n-1}, n\geq 1 with F_0 = F_1=1. So, I will illustrate a following general concept about recursions using Fibonacci sequence.

A sequence generated by a recursive formula is periodic modulo k, for any positive integer k greater than 1.

I find this fact very interesting because it means that a sequence which is strictly increasing when made bounded using the modulo operation (since it will allow only limited numbers as the output of recursion relation), will lead to a periodic cycle.

Following are the first 25 terms of the Fibonacci sequence:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025.

And here are few examples modulo k, for k=2,3,4,5,6,7,8

table110

As you can see, the sequence repeats as soon as 1,0 appears. And from here actually one can see why there should be a periodicity.

For the sequence to repeat, what we need is a repetition of two consecutive values (i.e. the number of terms involved in the recursive formula) in the sequence of successive pairs. And for mod k, the choices are limited, namely k^2.  Now, all we have to ensure is that “1,0” should repeat. But since consecutive pairs can’ repeat (as per recursive formula) the repetition of “1,0” must occur within the first k^2.

For rigorous proofs and its relation to number theory, see: http://math.stanford.edu/~brianrl/notes/fibonacci.pdf