For people who got scared of math in a school or college when it was taught in a such a way when no curiosity is fostered it is easy to dislike math. But if you still want to give math a try or even curious about mathematics then the How To Bake Pi book by Eugenia Cheng is maybe what you need.
This book is a gentle introduction to a wide audience of the Category Theory which is a part of pure mathematics. It does not require from a reader to be a math expert, but it does require at least a certain interest in math. Each chapter of the book starts with a recipe, usually related to pastries and then proceeds at looking how that recipe could be related to some aspect of mathematics in the first part of the book and to some aspect of Category Theory in the second part of the book.
What I particularly like about this Eugenia’s book is that it talks about sets, rings, groups and categories which are advanced concepts in math, but it is able to explain them in a friendly manner, by providing real world related examples and analogies. For example, she reminded a reader about how it’s possible to use a Pythagoras’s theorem to calculate a vertical and horizontal distances that a ‘real’ taxi cab travels in a city.
What I found most interesting to myself is her layered model of mathematical thinking that consists of three parts: knowledge, understanding and belief. Where understanding is in the middle and binds together knowledge and belief. Put in her own words:
We have knowledge, which is what the outside world sees, belief, which is what we feel inside ourselves, and understanding, which holds them together.
Cheng, Eugenia. How To Bake Pi. Profile Books, 2016: p. 272
What is interesting that Eugenia Cheng has written recently a new book on Category Theory which builds upon the foundations she laid in the How To Bake Pi book. The new book is The Joy Of Abstraction and it can be seen as a textbook for Category Theory presented in a user friendly manner that very much retains the spirit of How To Bake Pi.
If you inclined towards mathematics, but almost didn’t touch it since college years and want to get a math rush again, then following are the books that you may find captivating.
I should mention that these are books on Applied Mathematics which is of useful kind paraphrasing Richard Feynman. The books are ordered from easy to not so.
To start:
1. Applied Mathematics: A Very Short Introduction by Alain Goriely. This book is a gentle intro to applied math and Alain is capable of explaining things lucidly and as simple as required, but not too much.
The Art of Educated Guessing and Opportunistic Problem Solving by Sanjoy Mahajan is more involved and requires some work on readers part, but it’s a delight to read. This book is available in open access here.
3. Next book from the same author is The Art of Insight in Science and Engineering: Mastering Complexity. It is somewhat similar to the former, but different. Again it’s open for public
Hanukkah is a Jewish festival commemorating the recovery of Jerusalem and subsequent rededication of the Second Temple at the beginning of the Maccabean Revolt against the Seleucid Empire in the 2nd century BCE.
During Hanukkah festival it’s a custom to light candles on a special type of candelabrum that has eight plus one places for candles. Eight places to light a candle each day and one for an auxiliary candle (shammash in Hebrew) that is intended to light other candles.
During eight days of the holiday a candle is lit in such a way that on first day you light 1 candle, on second day 2 candles and on it goes until on the eighth day 8 candles are lit.
How many are there?
So then the natural question to ask is how many candles do I need to have to be able to light candles for eight days.
The math says sum them up,
(1 + 2 + 3 + 4 + 5 + 6 + 7 + 8) + 8 = …
And you get the number. Remember that additional 8 candles are there since we need to count the auxiliary candle used each day. Even though this calculation isn’t difficult to make, this may quickly change if you need to sum 1 to 100 candles.
What can you do? Is there a quick way to sum the candles? Indeed there is and if you recall your school math you could remember something about arithmetic progression. It gives you the formula below to count any number of candles or any other objects for that matter:
Sn = (a1 + an) * n / 2,
where Sn – sum of n elements, a1 – first element, an – last element, n – total number of elements.
While this formula is correct one may wonder how do you derive it? What is the intuition? You always can resort to mathematical induction to prove why it works correctly. We leave it for you as an exercise (a free Book Of Proof by Richard Hammack could be helpful). But there is a visual way to understand how this formula was derived.
On the shoulders of giants
It is a folk legend that when one of the greatest mathematicians Carl Friedrich Gauss attended a school a teacher asked pupils to count numbers from 1 to 100 to calm them down. It says that Gauss came up very quickly with the answer 5050.
And the explanation is that he did this trick.
1, … 100 = 101
2, … 99 = 101
3, … 98 = 101
4, … 97 = 101
… …
97, … 4 = 101
98, … 3 = 101
99, … 2 = 101
100, … 1 = 101
He placed numbers form 1 to 100 in such a way that first sequence was ascending from 1 to 100, and the second was descending from 100 to 1. Then if you look at the sum of each pairs it makes 101. There are 100 such pairs, so when you multiply them you get
101 * 100 = 10100
But we counted each pair twice, so there is a need to divide this number by two.
101 * 100 / 2 = 5050
You may think at this point, well Gauss was a genius so he came up with this explanation, but it still feels like I do not get it fully. And I agree. It is still not fully clear how he came up with this trick. So let’s try to look at it more visually.
Visual aids to the rescue
If you look at candles that are lit on each day of Hanukkah from above we’ll see something like on the figure below.
You’ll see that this figure resembles a lot a right triangle. So it’s good to think about this in this way for a moment.
Now, you may recall that to get an area of a rectangular you multiply its two sides
Area = a * b
Well, rectangular is build out of two right triangles isn’t it? So if you look carefully at the figure below you’ll see what Gauss possibly thought.
You have 8 candles on one side of the rectangular. Then you have 9 candles on the other side of the rectangular. The area of this rectangular is
Area = 8 * 9 = 72,
but since we are only interested in half of the rectangular then let’s divide it by two.
72 / 2 = 36.
And don’t forget about adding 8 auxiliary candles.
So we get
36 + 8 = 44
Let there be light
That’s it folks. Let the light of the candles enlighten us in math.
The title of this post can seem strange to you. What mathematics has to do with magic? In my opinion, it depends on what feelings you took from math lessons at school, college or university. There are people who were frightened by math or bored by it. But there were also a lucky few who were able to spot something beautiful about math on their own or thanks to a good teacher. There’s another approach when math lessons cannot do the trick for you. Genrich Altshuller didn’t call it magic, but an encounter with a miracle. In the book How to become a genius. Life strategy of a creative person by Altshuller and Vertkin they mentioned that creative people at an early age encountered a miracle that heavily influenced their trajectory in life. If we take mathematics as an example, showing a kid that mathematics isn’t a boring, but actually interesting field to participate in can be such a decisive encounter with a miracle. And it seems to me the best way to appreciate the beauty of mathematics is by actually doing it.
To organize such an encounter for my daughter, I suggested her to create a YouTube Kids channel about mathematics for kids where she can upload videos on mathematics that kids can understand and relate too. She agreed and with a little help from me she was able to create two videos already. One about square numbers, that as their name suggest, have a shape of a square. Another one about a visual way of depicting the addition of two numbers that third graders are tasked to do at school. Let’s take for example, 111 + 37. It turns out that before kids start using column method addition it’s difficult for them to find the right answer. Using binary trees can visualize the composition of the two numbers and help a kid in summing these numbers together.
One interesting aspect of creating such short video clips is that it encourages a parent and a kid to work together to be ready to present the topic clearly in a way that a kid can understand what the video is about. Also, teaching something is one of the best ways to understand it yourself. One additional thing to mention is that the videos in the channel can cover topics that are not explained at school at all or taught only in upper grades, which provides a kid with an advantage of an early exposure to advanced and interesting mathematical topics.
This way of introducing kids to mathematics has a promise of removing boredom and rut repetition of solving similar exercises and shows kids that math has more to it than how it’s usually taught at school.
Previously, in one of my posts I wrote that I tend to read books as if I proof-read or edit them. There are a number of advantages in doing so. For example, reading books end to end ensures deeper understanding of the content. Attempting to solve each exercise in a book is also a positive thing to do, because even if you do not solve it, you can get a valuable insight just because you tried hard to solve an exercise. When you follow this advice, after a book or two this starts to happen automatically to you and you can’t help, but spot spelling mistakes, wrong diagrams used or mistakes in formulas etc.
To see a real example of the above suggestions let’s look at the All Things Being Equal book by John Mighton founder of the JUMP math teaching method. This book is not a math textbook, but a book about how math can be taught to kids. The main idea is that math can be taught to an average person and it doesn’t take a genius to like math and be productive in it. There are a number of exercises that John Mighton provides in the book to showcase his approach of teaching math at school. I’ve tried each one of them and lo and behold found a number of mistakes in the book. One mistake was spotted by my daughter. And this is exactly what I want to write about next.
Some concrete examples
I’ve got a softcover edition of the book, ISBN 9780735272903. On page 201 of this edition John Mighton provides an example of how a simplified Sudoku version can be accessible and enjoyable to kids. The regular Sudoku puzzle 9 by 9 cells looks as follows. Each row and column in the table below should contain all of the digits from 1 to 9, when no digit can appear more than once.
A simplified version is 4 by 4 cells, which is easier for kids to start to play with. Now, I’ll provide all four puzzles on the page 201 of the book.
Puzzle #1
This puzzle is solvable, so let’s move on to the next
Puzzle #2
This puzzle has a mistake in it. Try to find it yourself or jump to the end of the post for an answer.
Puzzle #3
It’s solvable. Move on.
Puzzle #4
This puzzle has a mistake in it and my daughter, who was in Grade 2 at the time, was able to spot the mistake.
Pay attention, that there cannot be a duplicate value on any row, column in the table.
Closure
When you spot and collect a certain amount of mistakes it’s good to inform an author of the book or a publisher about them. Usually, authors are grateful if you report mistakes to them and it could even result in a friendship or a nice communication with them.
It wasn’t the case with All Things Being Equal where there was no response when I sent the errata to the JUMP Math contact email. So I sent an email directly to the Vintage Canada who is the publisher of this book.
So take care and report mistakes, who knows where it will take you.
I guess you also could have had the same feeling when you learnt algebra at school. Some formulas were clear and understandable, but some were cryptic and it was unclear how would anyone derive them. And then the only way to master it is to memorize it. For example, there is this known formula for a difference of squares:
a2 – b2 = (a – b) * (a + b) = a2 + ab – ba – b2 = a2 – b2 , (1)
Then, there was a little bit more cryptic formula for a difference of cubes, which is not that obvious for a regular student:
a3 – b3 = (a – b) * (a2 + ab + b2) = a3 + a2b + ab2 – ba2 – ab2 – b3 = a3 – b3, (2)
So, I think you get it and the next formula is for a4 – b4 ,
And finally, we get to the most cryptic formula that could be frustrating in a school algebra lesson, the formula for a difference of two positive whole numbers (integers) of power of n
an – bn = (a – b) * (an−1 + an−2b + an-3b2 + … + a2bn-3 + abn−2 + bn−1) , (4)
Now, the last formula seems frightening, and most interestingly one could ask, how did in the world anyone derive it? Also, how do you use it correctly?
Take it slow
Let’s look at it in a slow motion. If we look at how we get from formula (1) to formula (4) we can notice that there is some symmetry in the numbers in the second braces in each of the formula.
Do you see it? When there is a2 on the left side there is a corresponding b2 on the right, when there is a2b on the left, there is a corresponding b2a on the right side, etc. So this is the symmetry I am talking about. The general formula is actually a factorization of a polynomial formula. But we can look at it in a different manner, just to understand how to use it properly. The derivation of the general formula is a little bit more complex and can be found here.
One interesting thing to notice is that the sum of powers of each a, b or there multiplication ab in the second braces is always n – 1.
(a + b) = a1 + b1 , i.e. the powers are 1, 1
(a2 + ab + b2) = a2 + a1b1 + b2 , i.e. the powers are 2, 1 + 1, 2
(a3 + a2b + b2a + b3) = (a3 + a2b1 + a1b2 + b3) , i.e. the powers are 3, 2 + 1, 1 + 2, 3
(an−1+ an−2b + an-3b2 + … + a2bn-3 + abn−2 + bn−1), i.e. the powers are n – 1, n – 2 + 1 = n – 1 , n – 3 + 2 = n – 1, 2 + n – 3 = n – 1, etc.
Now, also let’s pay attention that we can treat 1 as 1 = a0 or 1 = b0, and let’s look again at the expressions above
I hope you can see that there is a systematic pattern which is going on here.
Rules of the game
Rule 1: The number of members in the second braces is always as the power of the initial expression, say two for a2 – b2; three for a3 – b3 etc.
Rule 2: The sum of the powers of each member in the second braces is n – 1, which was already shown in the previous examples.
Pay attention that this can be also proven by mathematical induction. But I leave it as an exercise for you.
How to use this formula and how to zip it
Now that we’ve noticed there is a pattern this pattern show us how to use the formula in a simple way without the need in rote memorization or blindly using someone else derivation.
The only thing is to remember that the first braces always have (a – b) and in the second braces the sum of the powers of each member is n -1. Let’s look at the concrete example of a8 – b8.
Let’s start from the second braces, and write each member without powers in accordance to Rule 1. We know there should be n, i.e. 8 such members.
(ab + ab + ab + ab + ab + ab + ab + ab)
Now, let’s use the Rule 2 and add powers to each member in the second braces, remembering that for a‘s, powers start from n – 1 and decrement by 1 for each consecutive a, and for b‘s powers start from 0 power and increment by 1 for each b until n – 1. Applied to our example,
for a‘s: a7, a6, a5, a4, a3, a2, a1, a0
and b‘s: b0, b1, b2, b3, b4, b5, b6, b7
Now, putting these together in the formula we get,
= (a – b) * (a7 + a6b + a5b2 + a4b3 + a3b4 + a2b5 + ab6 + b7).
Zip it
So, now we ready to zip this formula using the math notation for the sum:
where k increments from 0 to n – 1, i.e. 0, 1 , 2, …, n – 1.
An interesting turn of events
What is nice about this formula is the fact that it’s actually a concise description of an algorithm that checks whether a certain string is a palindrome.
The main idea is to take a sequence of letters (an array of characters in programming speak), and then start comparing
First vs. last letter
Second vs. one before last
etc
For each such case above check whether letters are the same. If there is at least one instance when they are not the same, then it’s not a palindrome.
In Java programming language this algorithm could be implemented as follows (run this code in online Java compiler)
public class Main {
public static void main (String[]args){
String word = "TENET";
System.out.println (isPalindrome(word));
}
static boolean isPalindrome (String word){
char[] charArray = word.toCharArray();
int n = charArray.length;
for (int k = 0; k <= n - 1; k++){
if (charArray[k] != charArray[(n - 1) - k]){
return false;
}
}
return true;
}
}
I think that I already wrote previously that a couple of years ago I bought the Elements of Programming book by Alexander Stepanov and Paul McJones. The issue was that the book content was hard for me to grasp at the time. I can hardly say that I now understand it better, but now I got where the rationale for that book came from and why it was written the way it was. It turns out the Alexander Stepanov as a mathematician was influenced deeply by Abstract Algebra, Group Theory and Number Theory. The elements of these fields of mathematics can be traced in the Elements of Programming clearly. For example, chapter 5 is called Ordered Algebraic Structures and it mentions among other things semigroup, monoid and group, which are elements in Group Theory. Overall, the book is structured somewhat like Euclid’s Elements, since the book starts from definitions, that are later used to build gradually upon in other chapters of the book.
Which brings me to the main topic of this post. By the way, the post is about a different book Alexander Stepanov wrote with Daniel Rose and that book was created by refining the notes for the Four Algorithmic Journeys course that Stepanov taught in 2012 at A9 company (subsidiary of Amazon). The course is available in YouTube and it consists of three parts each having a number of videos and the Epilogue part.
I highly recommend to watch it to anyone who is curious about programming, mathematics and science in general. The course is entertaining and it talks about how programming, or more exactly algorithms that are used in programming, are based on algorithms that were already known thousands of years ago in Egypt, Babylon etc. Alexander Stepanov has a peculiar way of lecturing and I find this way of presentation funny. The slides for the course and the notes that were aggregated in the Three Algorithmic Journeys book draft are freely available at Alexander Stepanov’s site.
So the book which I want to mention is From Mathematics to Generic Programming which was published in 2014 and is a reworked version of the Three Algorithmic Journeys draft. This is how Daniel Rose describes this in the Authors’ Note of the book.
The book you are about to read is based on notes from an “Algorithmic Journeys” course taught by Alex Stepanov at A9.com during 2012. But as Alex and I worked together to transform the material into book form, we realized that there was a stronger story we could tell, one that centered on generic programming and its mathematical foundations. This led to a major reorganization of the topics, and removal of the entire section on set theory and logic, which did not seem to be part of the same story. At the same time, we added and removed details to create a more coherent reading experience and to make the material more accessible to less mathematically advanced readers.
My verdict
As authors mentioned the book is geared towards Generic Programming, but I recommend to read both of them in parallel, since each one complements the other. I think that the Three Algorithmic Journeys is even better than the From Mathematics to Generic Programming (FM2GP). First, it’s free and second, ironically, it’s more generic than the FM2GP book.
It seems like there is hardly a person who didn’t hear the phrase “Thinking outside of the box”. As Wikipedia entry says it’s “a metaphor that means to think differently, unconventionally, or from a new perspective.” While it sounds good in theory, it is unclear what one should do to think unconventionally, differently, creatively etc. Only demanding from someone to think outside of the box, doesn’t provide clear guidance on how to achieve this goal.
The same issue happens in education, when a student is taught any subject that requires thinking beyond what was taught in a lesson or a lecture. There are people who can do better than others in such situations and we tend to label them as creative, smart and sometimes genius. But the psychological research into what makes experts experts, for example done by Anders K. Ericsson et al, shows that this has to do more with the way an expert practiced, and not the innate cognitive abilities.
So what makes us creative and can it be taught and learned? The short answer is yes and the rest of this post will try to justify this answer. The question of creative thinking is relevant in most fields of daily life where problems arise and when there is no obvious way of how to solve them. Here we go into realm of innovation and invention. There are many definitions of these two terms, so let me quote one from Merriam-Webster on the difference between invention and innovation
What is the difference between innovation and invention? The words innovation and invention overlap semantically but are really quite distinct.
Invention can refer to a type of musical composition, a falsehood, a discovery, or any product of the imagination. The sense of invention most likely to be confused with innovation is “a device, contrivance, or process originated after study and experiment,” usually something which has not previously been in existence.
Innovation, for its part, can refer to something new or to a change made to an existing product, idea, or field. One might say that the first telephone was an invention, the first cellular telephone either an invention or an innovation, and the first smartphone an innovation.
Chuck Swoboda, in his The Innovator’s Spirit book also provides detentions for an innovation and an invention that will be discussed in this post and they are
An invention, by definition, is something new—something that’s never been seen before. An innovation, on the other hand, especially a disruptive one, is something new that also creates enormous value by addressing an important problem.
While I do not have any objection to his definition of an innovation, I don’t agree with the definition of an invention. Saying that invention “is something new that’s never been seen before” is too vague a definition to be practical. It takes a quick look into submitted patents to see that there are lots of similar, if not outright identical patents issued for inventions. Which means the definition of invention being something never seen before fails to capture this. Also by the same token invention “being something new” fails too.
But it turns out there is quite precise definition, that exits since 1956, of a technical invention, which was provided by Genrich Altshuller and Rafael Schapiro in a paper About the Psychology of Inventive Creativity (available in Russian) published in Psychology Issues, No. 6, 1956. – p. 37-49. In the paper they mentioned that as a technical system evolves there could arise contradictory requirements between parts of the system. For example, lots of people use mobile phones to browse the internet. To be able to comfortably see the content on the screen of the phone, the screen should be as big as possible, but this requirement clashes (contradicts) with the size of the mobile phone, which should be small enough to be able to hold it comfortably in a hand or carry it in a pocket.
Altshuller and Shapiro defined the invention as a resolution of the contradictory requirements between parts of the system, without having to trade off requirements to achieve the solution. This definition of invention allows to talk precisely about what can be thought as invention and what can’t. Generally speaking, contradictory requirements can be resolved in space, time or structure. For example, returning to the mobile phone example, to resolve the contradiction in structure of the phone, between the size of the screen and the size of the phone there is a functionality that was introduced in mobile phones that allows to screencast the video and audio from a phone to a TV screen using Wi-Fi radio signal. YouTube application on Android phones supports this functionality.
Altshuller wrote a number of books on the subject of creative thinking, particularly books that developed the Theory of Inventive Problem Solving (abbreviated as TRIZ in Russian). In these books the ideas about a contradiction, an invention and an algorithmic approach (ARIZ) to how to invent by solving contradictions in technical problems are elaborated. To name just a few books in chronological order, written by Altshuller
How to learn to invent (“Как научиться изобретать”), 1961
Algorithm of Invention(“АЛГОРИТМ изобретения”), 1969
Creativity as an Exact Science: Theory of Inventive Problem Solving (“ТВОРЧЕСТВО как точная наука: Теория решения изобретательских задач”), 1979
What is important to mention about the books is that they contain systematic, detailed and step by step explanations of how to invent using an algorithm. Lots of examples and exercises for self-study included in them. The books by Altshuller somewhat resemble in their content and in a way of presenting the material books written by George Polya.
Polya being a productive mathematician was also interested in how to convey his ideas in a way that could be easily understood by other people. To this end he wrote a number of books directed to pupils, students, teachers and general audience.
For example, his book How To Solve it first published in 1945 is a step by step instruction set on how to approach mathematical problems in a systematic way, using heuristics that mathematicians accumulated doing math for thousands of years. It very much resembles to me the structure and approach taken in Altshuller’s How to learn to event. Later, Polya wrote two additional books on how mathematicians think and how they arrive to mathematical theories. Each of the books consist of two volumes and they are
What is interesting to mention is that the books written by Polya and Altshuller more than fifty years ago contained very insightful ideas and heuristics to tackle math and inventive problems. But today it’s still difficult to find a widespread adoption of these ideas in education, industry or elsewhere. For example, The Princeton Companion to Applied Mathematics book from 2015 mentions only a rudimentary number of math Tricks and Techniques in the chapter I, Introduction to Applied Mathematics, on pages 39-40, out of 1031 pages.
As well as the general ideas and principles described in this article, applied mathematicians have at their disposal their own bags of tricks and techniques, which they bring into play when experience suggests they might be useful. Some will work only on very specific problems. Others might be nonrigorous but able to give useful insight. George Pólya is quoted as saying, “A trick used three times becomes a standard technique.” Here are a few examples of tricks and techniques that prove useful on many different occasions, along with a very simple example in each case.
– Use symmetry… – Add and subtract a term, or multiply and divide by a term…. – Consider special cases… – Transform the problem… – Proof by contradiction… – Going into the complex plane…
As a summary, if you are curious whether it’s possible to learn how to be more creative, inventive or, in general, approach problems in a systematic way, then check the books by Genrich Altshuller and George Polya. They may provide you with just the tools that you were looking for, but didn’t know where to find.
In this post I want to talk about why providing good and detailed explanations can be a key in deep understanding of things in different fields of life. Particularly, I want to talk about detailed proofs in mathematics that have good step by step explanations of how the proof was constructed. Recently, I’ve started to read the books on math that are piling on my table just as the image above depicts.
I want to point your attention to the second book at the top of the pile, which is Prime Numbers and the Riemann Hypothesis book from 2016 written by Barry Mazur and William Stein. This book talks about Riemann Hypothesis by starting from ‘simple’ math and gradually moving to details about Riemann Hypothesis that require more advanced math background.
So what levels of understanding and well explained proofs have to do with the content of the book. Well, you see in the first part of the book, which authors claim requires some minimal math background a read sees this
Here are two exercises that you might try to do, if this is your first encounter with primes that differ from a power of 2 by 1:
1. Show that if a number of the form M = 2^n – 1 is prime, then the exponent n is also prime. [Hint: This is equivalent to proving that if n is composite, then 2^n -1 is also composite.] For example: 2^2 – 1 = 3, 2^3 -1 = 7 are primes, but 2^4 – 1 = 15 is not. So Mersenne primes are numbers that are
– of the form 2^ prime number – 1, and
– are themselves prime numbers
Some context for the quote
Here comes a little bit of a context about this quote. The quote comes from, part 1, chapter 3: ‘”Named” Prime Numbers’, on page 11. The chapter describes what are Mersenne Primes, which are prime numbers that are one less than a power of two:
M = 2^n – 1
Also, it’s good to know that a prime number is a whole number (positive integer) that can be divided only by itself or 1. For example,
2, 3, 5, 7, 11 … are prime numbers since they can only be divided by themselves and 1.
Now, that we know what prime numbers are, I want to draw your attention to the point in the quote where it says, that the exercises are good for ‘your first encounter with primes that differ from a power of 2 by 1‘. Well, in my opinion these exercises are good only for readers who have at least a BSc in Math or possibly an engineering degree. In a couple of sentences we’ll see why I think so. Since I consider myself as a person who is interested in math and have a BSc degree in Electronics, I think the first part of the book which is indented for a layman person is just for me. Were you able to arrive at the proof for that simple exercises above?
Frankly, I wasn’t able to prove it. So, I went and looked for a proof on the internet. As always, Wikipedia is at the top of the Google search when it comes to math topics. Lo and behold there is a page in the wiki about Mersenne primes, what they are and a number of proofs related to them. One of the proofs was exactly the solution to the exercise in the quote above. Here it comes:
Note: Since, I had no time to learn how to use LaTeX properly in the WordPress, and believe me WordPress doesn’t make blogger’s life easy I write the proofs and picture them.
Does this proof looks like a piece of cake to you? Is it intuitive and easy to grasp? In my opinion, it’s not and also this proof shows why Wikipedia gets a good portion of criticism about its content.
What I find not so obvious about that proof is how the right hand side of the equation came about. Especially, the part that has powers of a * (b – 1) , a* (b – 2), … , a, 1. And then the statement that says ‘By contrapositive, if 2^p -1 is prime then p prime‘. In this particular statement, if you had no courses on mathematical proof, logic or Abstract Algebra, then the words composite and contrapositive can be a little bit mysterious.
I thought to myself, well, the proof looks kind of unclear to me, so I searched better using the internet and also checked the books I own. I was able to find a couple of proofs that were easier to understand and also was able to find a proof in the Book of Proof by Richard Hammack that you can see in the title image for the post. It’s the blue one and it comes third from the top of the pile.
Let’s start with the proof from the Book of Proof, which sounds like a good place to begin with. The proof is a solution to the exercise 25 from Chapter 5 in the book.
If we look carefully at this proof it look almost exactly as the proof in the Wikipedia. It even look less clear. But one important thing to notice is that this proof shows where the ‘1’ comes from on the right hand side of the equation, in comparison to the proof in the wiki. I think so, since 2^(ab-ab) which equals 1, provides more information than a simple number 1. This is because it provides some clues on how the proof was constructed. But for a reader who does not remember math, both of the proofs are not that helpful. Also, we need to take into consideration, that the Book of Proof intended audience is undergraduate students of exact sciences. So the book presupposes some math background.
Some math background
We already mentioned that a prime number is a positive integer that can be only divided by itself or number 1. All other integers, are composite, since any of them can be composed by multiplying prime numbers. This is where composite comes from. As for contrapositive the Merriam-Webster site provides this definition
a proposition or theorem formed by contradicting both the subject and predicate or both the hypothesis and conclusion of a given proposition or theorem and interchanging them
if not-B then not-A ” is the contrapositive of “if A then B ”
For example,
If it was raining then it is wet.
Then contrapositive statement would be
If it is not wet then it wasn’t raining.
Returning back to the original exercise from the Prime Numbers and the Riemann Hypothesis book, now, it becomes a little bit clear, what the hint [Hint: This is equivalent to proving that if n is composite, then 2^n -1 is also composite.] there was for. So the proofs, went to prove that
If n is composite then 2^n – 1 number is composite
and by contrapositive
If 2^n – 1 number is not composite(i.e. prime) then n is not composite (i.e. prime)
Polynomial factorization
Now, that we know what contrapositive proof is that’s turn to the right hand side part of the equation which is
Since this post is becoming to long I need to make it shorter, which defeats the point of providing detailed explanations 😦
But I’ll provide some hints on how the right hand side was derived.
There is a known math formula to compute the following expression a^n – b^n
It turns out that the equation in the proofs that were mentioned in this post has the same structure as the formula to derive a^n – b^n. But the most interesting part is this. If you look at the last equation the Roman numeral I stands for the initial composite number 2^n – 1, and it is composed by multiplying Part II by Part III.
Part I = Part II * Part III
What is interesting about this composite number and that me use A, B and C instead of using I, II and III
A = B * C
is that B and C are factors of A, or alternatively B is a divisor and C is a quotient.
So to summarize the initial number 2^n -1 is composite since it is a product of two other numbers.
ScienceAppliedForGood 