# Monthly Archives: April 2018

Standard

Earlier, YouTube maths channels focused mainly on giving nice expositions of non-trivial math ideas. But recently, two brand new theorems were presented on YouTube instead of being published in a journal.

• Proofs of the fact that $\sqrt{2}$, $\sqrt{3}$, $\sqrt{5}$ and $\sqrt{6}$ are irrational numbers – Burkard Polster (13 April 2018)

This is an extension of the idea discussed in this paper by Steven J. Miller and David Montague.

• A new proof of the Wallis formula for π – Sridhar Ramesh and Grant Sanderson (20 Apr 2018):

This is an extension of Donald Knuth‘s idea documented here by Adrian Petrescu.

It’s nice to see how the publishing in maths is evolving to be accessible to everyone.

# Probability Musing

Standard

Please let me know if you know the solution to the following problem:

What is the probability of me waking up at 10am?

What additional information should be supplied so as to determine the probability? What do you exactly mean by the probability of this event? Which kind of conditional probability will make sense?

Consider the following comment by Timothy Gowers regarding the model for calculating the probability of an event involving a pair of dice:

Rolling a pair of dice (pp. 6), Mathematics: A very short introduction © Timothy Gowers, 2002 [Source]

I find probability very confusing, for example, this old post.

# Sum of squares

Standard

In the past few posts, I have talked about representing integers as a sum of squares:

In this post, I would like to state Lagrange’s four-square theorem following section 6.4 of Niven-Zuckerman-Montgomery’s An introduction to the theory of number.

Firstly, by applying Hensel’s lemma to the result from the earlier post we get (Theorem 5.14):

Proposition: Let $a,b,c$ be arbitrary integers. Then the congruence $ax^2+by^2+cz^2\equiv 0\pmod{p}$ has a non-trivial solution modulo any prime $p$.

The theorem stated in the earlier post establishes that there is no need for any condition modulo primes p not dividing abc. The above proposition, application of Hensel’s lemma, just demonstrates it more explicitly by telling that the equation is solvable everywhere locally (i.e. modulo every prime).

Secondly, we need following result from Geometry of numbers (Theorem 6.21):

Minkowski’s Convex Body Theorem for general lattices: Let $A$ be a non-singular $n\times n$ matrix with real elements, and let $\Lambda = A\mathbb{Z}^n=\{A\mathbf{s}\in \mathbb{R}^n: \mathbf{s}\in \mathbb{Z}^n\}$ be a lattice. If $\mathcal{C}$ is a set in $\mathbb{R}^n$ that is convex, symmetric about origin $\mathbf{0}$, and if $\text{vol}(\mathcal{C})> 2^n |\det(A)|$, then there exists a lattice point $\mathbf{x}\in\Lambda$ such  that $\mathbf{x}\neq 0$ and $\mathbf{x}\in \mathcal{C}$.

Now we are ready to state the theorem (for the proof see Theorem 6.26):

Lagrange’s four-square theorem: Every positive integer $n$ can be expressed as the sum of four squares, $n=x_1^2+x_2^2+x_3^2+x_4^2$, where $x_i$ are non-negative integers.

# Conway’s Prime Producing Machine

Standard

Primes are not randomly arranged (since their position is predetermined) but we can’t find an equation which directly gives us nth prime number. However, we can ask for a function (which surely can’t be a polynomial) which will give only the prime numbers as output. For example, the following one is used for MRDP theorem:

But it’s useless to use this to find bigger primes because the computations are much more difficult than the primality tests.

Conway’s PRIMEGAME takes whole numbers as inputs and outputs $2^k$ if and only if $k$ is prime.

Source: https://cstheory.stackexchange.com/a/14727 [Richard Guy, © 1983 Mathematical Association of America]

PRIMEGAME is based on a Turing-complete esoteric programming language called FRACTRAN, invented by John Conway. A FRACTRAN program is an ordered list of positive fractions together with an initial positive integer input n. The program is run by updating the integer $n$ as follows:

1. for the first fraction $f$ in the list for which $nf$ is an integer, replace $n$ by $nf$;
2. repeat this rule until no fraction in the list produces an integer when multiplied by n, then halt.

PRIMEGAME is an algorithm devised to generate primes using a sequence of 14 rational numbers:

$\displaystyle{\left( \frac{17}{91}, \frac{78}{85}, \frac{19}{51}, \frac{23}{38}, \frac{29}{33}, \frac{77}{29}, \frac{95}{23}, \frac{77}{19}, \frac{1}{17}, \frac{11}{13}, \frac{13}{11}, \frac{15}{2}, \frac{1}{7}, \frac{55}{1} \right)}$

Starting with 2, one finds the first number in the machine that multiplied by 2 gives an integer; then for that integer we find the first number in the machine that generates another integer. Except for the initial 2, each number output have an integer for a binary logarithm is a prime number, which is to say that powers of 2 with composite exponents don’t show up.

If you have some knowledge of computability and unsolvability theory, you can try to understand the working of this Turing machine. There is a nice exposition on OeisWiki  to begin with.

“Hilbert’s 10th Problem” by Martin Davis and Reuben Hersh [© 1973 Scientific American, doi: 10.1038/scientificamerican1173-84] Illustrating the basic idea of machines from unsoilvability theory.

Following is an online program by Prof. Andrew Granville illustrating the working of PRIMEGAME:

Motivation for this post came from Andrew Granville’s Math Mornings at Yale.