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

Under 40

Standard

The age of 40 is considered special in mathematics because it’s an ad-hoc criterion for deciding whether a mathematician is young or old. This idea has been well established by the under-40 rule for Fields Medal, based on Fields‘ desire that:

while it was in recognition of work already done, it was at the same time intended to be an encouragement for further achievement on the part of the recipients and a stimulus to renewed effort on the part of others

Though it must be noted that this criterion doesn’t claim that after 40 mathematicians are not productive (example: Yitang Zhang).  So I wanted to write a bit about the under 40 leading number theorists which I am aware of (in order of decreasing age):

  • Sophie Morel: The area of mathematics in which Morel has already made contributions is called the Langlands program, initiated by Robert Langlands. Langlands brought together two fields, number theory and representation theory. Morel has made significant advances in building that bridge. “It’s an extremely exciting area of mathematics,” Gross says, “and it requires a vast background of knowledge because you have to know both subjects plus algebraic geometry.” [source]
  • Melanie Wood: Profiled at age 17 as “The Girl Who Loved Math” by Discover magazine, Wood has a prodigious list of successes. The main focus of her research is in number theory and algebraic geometry, but it also involves work in probability, additive combinatorics, random groups, and algebraic topology.  [source1, source2]
  • James Maynard:  James is primarily interested in classical number theory, in particular, the distribution of prime numbers. His research focuses on using tools from analytic number theory, particularly sieve methods, to study primes.  He has established the sensational result that the gap between two consecutive primes is no more than 600 infinitely often. [source1, source2]
  • Peter Scholze: Scholze began doing research in the field of arithmetic geometry, which uses geometric tools to understand whole-number solutions to polynomial equations that involve only numbers, variables and exponents. Scholze’s key innovation — a class of fractal structures he calls perfectoid spaces — is only a few years old, but it already has far-reaching ramifications in the field of arithmetic geometry, where number theory and geometry come together. Scholze’s work has a prescient quality, Weinstein said. “He can see the developments before they even begin.” [source]

Ulam Spiral

Standard

Some of you may know what Ulam’s spiral is (I am not describing what it is because the present Wikipedia entry is awesome, though I mentioned it earlier also). When I first read about it, I thought that it is just a coincidence and is a useless observation. But a few days ago while reading an article by Yuri Matiyasevich, I came to know about the importance of this observation. (Though just now I realised that Wikipedia article describes is clearly, so in this post I just want to re-write that idea.)

It’s an open problem in number theory to find a non-linear, non-constant polynomial which can take prime values infinitely many times. There are some conjectures about the conditions to be satisfied by such polynomials but very little progress has been made in this direction. This is a place where Ulam’s spiral raises some hope. In Ulam spiral, the prime numbers tend to create longish chain formations along the diagonals. And the numbers on some diagonals represent the values of some quadratic polynomial with integer coefficients.

ulam_spiral_by_splatbang-d5b0yfj

Ulam spiral consists of the numbers between 1 and 400, in a square spiral. All the prime numbers are highlighted. ( Ulam Spiral by SplatBang)

Surprisingly, this pattern continues for large numbers. A point to be noted is that this pattern is a feature of spirals not necessarily begin with 1. For examples, the values of the polynomial x^2+x+41 form a diagonal pattern on a spiral beginning with 41.

 

Finite Sum & Divisibility

Standard

I wish to discuss a small problem from The USSR Olympiad Problem Book (problem 59) about the finite sum of harmonic series. The problem asks us to prove that

\displaystyle{\sum_{k=2}^{n} \frac{1}{k}}  can never be an  integer for any value of n.

I myself couldn’t think much about how to prove such a statement. So by reading the solution, I realised that how a simple observation about parity leads to this conclusion.

Firstly, observe that among the natural numbers from 2 to n there is exactly one natural number which has the highest power of 2 as its divisor. Now, while summing up the reciprocals of these natural numbers we will get a fraction as the answer. In that fraction, the denominator will be an even number since it’s the least common multiple of all numbers from 2 to n. And the numerator will be an odd number since it’s the sum of (n-2) even numbers with one odd number (corresponding to the reciprocal of the number with the highest power of 2 as the factor). Since under no circumstances an even number can completely divide an odd number, denominator can’t be a factor of the numerator. Hence the fraction can’t be reduced to an integer and the sum can never be an integer.

Repelling Numbers

Standard

An important fact in the theory of prime numbers is the Deuring-Heilbronn phenomenon, which roughly says that:

The zeros of L-functions repel each other.

Interestingly, Andrew Granville in his article for The Princeton Companion to Mathematics remarks that:

This phenomenon is akin to the fact that different algebraic numbers repel one another, part of the basis of the subject of Diophantine approximation.

I am amazed by this repelling relation between two different aspects of arithmetic (a.k.a. number theory). Since I have already discussed the post Colourful Complex Functions, wanted to share this picture of the algebraic numbers in the complex plane, made by David Moore based on earlier work by Stephen J. Brooks:

 

In this picture, the colour of a point indicates the degree of the polynomial of which it’s a root, where red represents the roots of linear polynomials, i.e. rational numbers,  green represents the roots of quadratic polynomials, blue represents the roots of cubic polynomials, yellow represents the roots of quartic polynomials, and so on.  Also, the size of a point decreases exponentially with the complexity of the simplest polynomial with integer coefficient of which it’s a root, where the complexity is the sum of the absolute values of the coefficients of that polynomial.

Moreover,  John Baez comments in his blog post that:

There are many patterns in this picture that call for an explanation! For example, look near the point i. Can you describe some of these patterns, formulate some conjectures about them, and prove some theorems? Maybe you can dream up a stronger version of Roth’s theorem, which says roughly that algebraic numbers tend to ‘repel’ rational numbers of low complexity.

To read more about complex plane plots of families of polynomials, see this write-up by John Baez. I will end this post with the following GIF from Reddit (click on it for details):

Prime Consequences

Standard

Most of us are aware of the following consequence of Fundamental Theorem of Arithmetic:

There are infinitely many prime numbers.

The classic proof by Euclid is easy to follow. But I wanted to share the following two analytic equivalents (infinite series and infinite products) of the above purely arithmetical statement:

  • \displaystyle{\sum_{p}\frac{1}{p}}   diverges.

For proof, refer to this discussion: https://math.stackexchange.com/q/361308/214604

  • \displaystyle{\sum_{n=1}^\infty \frac{1}{n^{s}} = \prod_p\left(1-\frac{1}{p^s}\right)^{-1}}, where s is any complex number with \text{Re}(s)>1.

The outline of proof,   when s is a real number, has been discussed here: http://mathworld.wolfram.com/EulerProduct.html