Friday, October 14, 2022

A new matrix multiplication record

In Chapter 5, we mentioned Strassen’s algorithm for matrix multiplication. Not many improvements have been made since 1969 when Strassen discovered how to multiply a \pair of 4 by 4 matrices with 49 multiplications - a reduction of 15 multiplications from the  basic definition. A further reduction by one multiplication was announced by two Austrian researchers at Johannes Kepler University Linz in October 2022. 

Monday, September 26, 2022

Does learning about quantifiers help students understand limits?

 A recent thread on the MAA member web site discussed how limits should be taught in Calculus I/II. One comment was that students who take a discrete math course, where quantifiers are discussed, might better understand the definition of a limit.  What follows is a possible example that could be added to our section on quantifiers. Background:  I taught a calculus workshop for mostly middle school teachers several years ago and I recall the most spirited discussion being around the idea that $0.999…  = 1$.

Example: What does it mean that 0.999… = 1?  The ellipsis (…) implies that there are an infinite number of 9’s on the left of the equals sign.  After many years of struggling with what this means, mathematicians have come up with a universally accepted interpretation involving quantifiers.  It is that

$$(\forall \epsilon)_{\mathbb{R}^+} ((\exists N)_{\mathbb{P}})(n\geq N \Rightarrow  |1- 0.\underbrace{99..9}_{n\,9’s}| \lt \epsilon))$$

In calculus, the symbol $\epsilon$ is usually reserved for small positive real numbers. Let’s pick a value for $\epsilon$ and peel the universal quantifier off the statement above.  Let’s try  $\epsilon$ equal to $\frac{1}{2^{10}}=\frac{1}{1024}$.  In addition we note that $0.\underbrace{99..9}_{n\,9’s}=1-\frac{1}{10^n}$.  With our choice of $\epsilon$ we get 

$$ (\exists N)_{\mathbb{P}}(n\geq N \Rightarrow  |1- 0.\underbrace{99..9}_{n\,9’s}| \lt \frac{1}{1024}) $$

$$(\exists N)_{\mathbb{P}}(n\geq N \Rightarrow \frac{1}{10^n} \lt \frac{1}{1024}) $$

This last statement is true - one value of  $N$ that would work is $11$. You just have to convince yourself that any positive value of $\epsilon$, no matter how small, will produce a true statement.  If you see that, you’ve convinced yourself that $0.999…  = 1$!