The Big Lock-Down Math-Off, Match 12

The Aperiodical 2020-05-03

Welcome to the 12th match in this year’s Big Math-Off. Take a look at the two interesting bits of maths below, and vote for your favourite.

You can still submit pitches, and anyone can enter: instructions are in the announcement post.

Here are today’s two pitches.

Matthew Scroggs – Interesting Tautologies

Matthew Scroggs is one of the editors of Chalkdust, a magazine for the mathematically curious, and blogs at mscroggs.co.uk. He tweets at @mscroggs.

A few years ago, I made @mathslogicbot, a Twitter bot that tweets logical tautologies.

The statements that @mathslogicbot tweets are made up of variables (a to z) that can be either true or false, and the logical symbols $\lnot$ (not) $\land$ (and), $\lor$ (or), $\rightarrow$ (implies), and $\leftrightarrow$ (if and only if), as well as brackets. A tautology is a statement that is always true, whatever values are assigned to the variables involved.

To get an idea of how to interpret @mathslogicbot’s statements, let’s have a look at a few tautologies:

$( a \rightarrow a )$. This says “$a$ implies $a$”, or in other words “if $a$ is true, then $a$ is true”. Hopefully everyone agrees that this is an always-true statement.

$( a \lor \lnot a )$. This says “$a$ or not $a$”: either $a$ is true, or $a$ is not true.

$(a\leftrightarrow a)$. This says “$a$ if and only if $a$”.

$\lnot ( a \land \lnot a )$. This says “not ($a$ and not $a$)”: $a$ and not $a$ cannot both be true.

$( \lnot a \lor \lnot \lnot a )$. I’ll leave you to think about what this one means.

(Of course, not all statements are tautologies. The statement $(b\land a)$, for example, is not a tautology as is can be true or false depending on the values of $a$ and $b$.)

While looking through @mathslogicbot’s tweets, I noticed that a few of them are interesting, but most are downright rubbish. This got me thinking: could I get rid of the bad tautologies like these, and make a list of just the “interesting” tautologies. To do this, we first need to think of different ways tautologies can be bad.

Looking at tautologies the @mathslogicbot has tweeted, I decided to exclude:

tautologies like $(a\rightarrow\lnot\lnot\lnot\lnot a)$ that contain more than one $\lnot$ in a row.
tautologies like $((a\lor\lnot a)\lor b)$ that contain a shorter tautology. Instead, tautologies like $(\text{True}\lor b)$ should be considered.
tautologies like $((a\land\lnot a)\rightarrow b)$ that contain a shorter contradiction (the opposite of a tautology). Instead, tautologies like $(\text{False}\rightarrow b)$ should be considered.
tautologies like $(\text{True}\lor\lnot\text{True})$ or $((b\land a)\lor\lnot(b\land a)$ that are another tautology (in this case $(a\lor\lnot a)$) with a variable replaced with something else.
tautologies containing substatements like $(a\land a)$, $(a\lor a)$ or $(\text{True}\land a)$ that are equivalent to just writing $a$.
tautologies that contain a $\rightarrow$ that could be replaced with a $\leftrightarrow$, because it’s more interesting if the implication goes both ways.
tautologies containing substatements like $(\lnot a\lor\lnot b)$ or $(\lnot a\land\lnot b)$ that could be replaced with similar terms (in these cases $(a\land b)$ and $(a\lor b)$ respectively) without the $\lnot$s.
tautologies that are repeats of each other with the order changed. For example, only one of $(a\lor\lnot a)$ and $(\lnot a\lor a)$ should be included.

After removing tautologies like these, some of my favourite tautologies are:

$( \text{False} \rightarrow a )$
$( a \rightarrow ( b \rightarrow a ) )$
$( ( \lnot a \rightarrow a ) \leftrightarrow a )$
$( ( ( a \leftrightarrow b ) \land a ) \rightarrow b )$
$( ( ( a \rightarrow b ) \leftrightarrow a ) \rightarrow a )$
$( ( a \lor b ) \lor ( a \leftrightarrow b ) )$
$( \lnot ( ( a \land b ) \leftrightarrow a ) \rightarrow a )$
$( ( \lnot a \rightarrow b ) \leftrightarrow ( \lnot b \rightarrow a ) )$

You can find a list of the first 500 “interesting” tautologies here. Let me know on Twitter which is your favourite. Or let me know which ones you think are rubbish, and we can further refine the list…

Colin Beveridge – Binet’s formula and Haskell

Colin blogs at flyingcoloursmaths.co.uk and tweets at @icecolbeveridge.

As ordained by Stigler’s law (which is attributed to Merton), Binet’s formula was known at least a century before Binet wrote about it

Binet’s formula is a lovely way to generate the $ n $th Fibonacci number, $ F_n $. If $ \phi = \frac{1}{2}\left(\sqrt{5} + 1\right)$, then

$ F_n = \frac{ \phi^n – (-\phi)^{-n} }{\sqrt{5}}$

Where does it come from?

Which, of course, I’ll leave as an exercise

It’s not hard to prove this by induction, but that feels like a bit of a cheat: it doesn’t explain why Binet’s formula works.

Personally, I like to prove it as follows.

Suppose $ F_{n-1} $ and $ F_{n} $ are consecutive Fibonacci numbers for some integer $ n $.
Then, if I want to end up with $ F_{n} $ and $ F_{n+1} $, I can use a matrix: $ \begin{pmatrix} F_{n} \\ F_{n+1} \end{pmatrix}= \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} F_{n-1} \\ F_{n} \end{pmatrix} $
That’s true for any $ n $, and (given that $ F_0 = 0 $ and $ F_1 = 1 $), I can write: $ \begin{pmatrix} F_{n} \\ F_{n+1} \end{pmatrix}= \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^n \begin{pmatrix} 0 \\ 1 \end{pmatrix} $

I only realised fairly recently what was going on when you diagonalise a matrix as $ \mathbf{PDP}^{-1} $. If you apply this to one of the eigenvectors, $ \mathbf{P}^{-1} $ maps it to one of the axes; $ \mathbf{D} $ stretches it by the appropriate eigenvalue; $\mathbf{P} $ maps it back parallel to the original eigenvector – so applying the diagonalisation to the eigenvector does exactly the same as applying the matrix to it. This is true for the other eigenvector(s), too; and because of all the linear goodness buried in linear algebra, the diagonalisation maps any linear combination of the eigenvectors – which, as long as your matrix has enough eigenvectors, means any vector – the same way as the original matrix does. If you don’t have enough eigenvectors, please consult a linear algebra professional immediately.

I smell an eigensystem – if I diagonalise the matrix, I can use that as a shortcut to unlimited power, bwahaha! (What’s that? Just unlimited powers of the matrix. Fine.) I’ll skip the tedious and arduous calculation required to diagonalise it, and note that: $ \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^n = \frac{1}{\sqrt{5}} \begin{pmatrix} -\phi & \frac{1}{\phi} \\ 1 & 1 \end{pmatrix} \begin{pmatrix} -\frac{1}{\phi} & 0 \\ 0 & \phi \end{pmatrix}^n \begin{pmatrix} -1 & \frac{1}{\phi} \\ 1 & {\phi} \end{pmatrix} $
This simplifies (after a bit of work) to: $\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^n =\frac{1}{\sqrt{5}} \begin{pmatrix} \phi^{-(n-1)} + \phi^{n-1} & -(-\phi)^{-n} + \phi^n \\ \phi^{-n} + \phi^n & -(-\phi)^{-(n+1)} + \phi^{n+1} \end{pmatrix} $
And
$\begin{pmatrix} F_{n} \\ F_{n+1} \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^n \begin{pmatrix} 0 \\ 1 \end{pmatrix}= \frac{1}{\sqrt{5}} \begin{pmatrix} \phi^n – (-\phi)^{-n} \\ \phi^{n+1} – (-\phi)^{-(n+1)} \end{pmatrix} $

… which gives us Binet’s formula $ \blacksquare $

A brief aside

In fact, it’s very close to $ F_n $, but that’s not the interesting thing here.

A thing that makes me go oo: the numerator of Binet’s formula gives integer multiples of $ \sqrt{5} $, and because $ 0 < \phi^{-1} < 1 $, the value of $ \phi^{-n} $ gets small as $ n $ gets large. As a result, $ \frac{\phi^n}{\sqrt{5}} $ is very close to an integer for even moderately large values of $ n $.

Calculating in $ \mathbb{Q}\left(\sqrt{5}\right) $

Which I was – the code is interesting, but not Math-Off-interesting

If you were, for example, trying to implement this in Haskell you might consider working in the field $ \mathbb{Q}\left(\sqrt{5}\right) $. You might, having considered that, run away screaming from the frightening notation – but $ \mathbb{Q}\left(\sqrt{5}\right) $ is less distressing than it looks: it’s just algebraic numbers of the form $ a + b \sqrt{5} $, where $ a $ and $ b $ are rational numbers – and addition, subtraction, multiplication and division (by anything that isn’t zero) are all defined as you would expect. You might like to verify that all of these operations leave you with another element of the field.

Another example of a field extension that works a similar way: the complex numbers can be thought of as $ \mathbb{R}(i) $ – numbers of the form $ a + bi $ where $a $ and $b $ are real.

In particular, $ \phi$ is an element of this field, with $ a = b = \frac{1}{2} $. Also,$ -\phi^{-1} $ is an element of the field, with $ a = \frac{1}{2} $ and $ b = – \frac{1}{2} $.

A little bit of messing with the binomial theorem tells you that calculating $ \phi^n – \left(-\phi^{-n}\right) $ leaves an element of $ \mathbb{Q}(\sqrt{5}) $ that’s purely a multiple of $ \sqrt{5} $ (it’s of the form $ a + b \sqrt{5} $, but with $ a = 0 )$ – so Binet’s formula gives us something that’s definitely rational.

Suppose, for example, we work out $ \phi^{10} $ and get $ \frac{123}{2} + \frac{55}{2}\sqrt{5} $. (It doesn’t take much more work to figure out that $ (-\phi)^{-10} = \frac{123}{2} – \frac{55}{2}\sqrt{5} $ so that Binet gives 55 as the tenth Fibonacci number.)

The oo! thing for me, though, is the other number. 123 is the tenth Lucas number – which are formed the same way as Fibonacci numbers, but with $ L_0 = 2 $ and $ L_1 = 1 $. It’s not necessarily a surprise that the Lucas and Fibonacci sequences are linked like this, but it does strike me as neat.

Links

So, which bit of maths made you say “Aha!” the loudest? Vote:

Note: There is a poll embedded within this post, please visit the site to participate in this post's poll.

The poll closes at 9am BST on Tuesday the 5th, when the next match starts.

If you’ve been inspired to share your own bit of maths, look at the announcement post for how to send it in. The Big Lockdown Math-Off will keep running until we run out of pitches or we’re allowed outside again, whichever comes first.