5 insanely great books about mathematics you should read.

I’ve been asked over and over for good books about mathematics for a layperson, someone who hasn’t taken advanced courses in university and is more simply interested in learning about what math is, and some of the more interesting historical figures and results from mathematics. Ironically, when you are a mathematics major at Waterloo, you get the opportunity in 4th year to take a course on the history of mathematics and you get introduced to a few really good books that start to explain the mindset and philosophy behind mathematics and not simply just the theorems and proofs.

Here are the 5 books about I most recommend to those who want to understand the mathematical mind and philosophy. Continue reading

Mathematical tomfoolery: factoring as a geometric problem

RSA encryption… it’s really that easy.

So I’ve always been fascinated by the problem taking a number n = pq and trying to factor it efficiently. While there is a good reason this is worth working on – RSA public key cryptography is dependent on the difficulty of this – I originally just found it fascinating: it seemed that all of the information about the factorization must be somehow contained in n. Simply becausewhen you multiply the factors together no information is lost.

Here’s a way to think about it, let’s say p and q are prime numbers, and let n = pq. Now, if we had any loss of information, then factoring n completely would provide more than one answer. However, that is impossible, however I will leave the exercise of proving that any factorization of n is unique to the reader.

The only information I can see that is lost is the ordering, and that is really insignificant to the original problem – what did I multiply together to produce n.

While playing with this, I keep on finding interesting things to play with. Obviously I haven’t “solved” the problem; otherwise I’d be doing my PhD at UofT. This lack of progress is not surprising considering this is a difficult problem people have been working on for centuries.

I have many many pages of notes, and so, I decided, screw it, I will just share these on my blog and maybe someone will have an idea that pushes me a bit further. Heck, maybe a professor of math will see it and invite me to do my PhD with them around this.

Each idea really deserves it’s own summary post, so I will start with the first approach I’ve played with for the longest.

Solving factoring is solving a simple diophantine equation.

I’m going to distill hundreds of pages of notes into the following, this is the tip of the iceberg when it comes to interesting results from this method. If there is a piece you want me to expound further on, let me know. If I find a particular theorem work going through I will post it in a later post.

The whole idea behind this is the following proposition:

Given, n = pq, p,q \in \mathbb{P}, p,q > 2

It is true that n = (l-k)(l+k) = l^2-k^2, l,k \in \mathbb{N}

where l \neq (n+1)/2, p= (l-k), q=(l+k)

Thus, given an n where we know n = pq: p,q odd, then we can easily see that l = (p+q)/2, and k=l-p, for p<q

Hence p=l-k, q= l+k. So now you just have to solve for l and k. This is a whole lot harder than it sounds. In fact it’s really just one step away from a Heronian triangle; A triangle where all sides are integers. In fact, this leads to an easy proof for finding Heronian triangles, but I will leave that to the reader.

In short, this problem reduces to solving the following diophantine equation.

l^2 = n + k^2

For the more geometrically minded, this means factoring is solving the following diagram for l,k \in \mathbb{N}.

Geometric Representation for Factoring (© 2013 kjro.se)
Geometric Representation for Factoring (© 2013 kjro.se)

No matter how many different methods I have tried to work with this, I just keep ending right back where I started. My knowledge revolves more around computational complexity, combinatorics and optimization so Diophantine equations are interesting, but I’m not as deep into them as I would like to be.  I know there is a decent amount of work on Diophantine equations, if you have a good text to recommend that might gives some more ideas, let me know.

One other point to make is that for every k,l \in \mathbb{N}, l \neq (n+1)/2 there will be associated non-unique composite number (ie, it will work for other k', l'. Note, for any odd composite number, this representation will exist.

Playing around with this I’ve gotten some other ways of making sieves, but they don’t differ much from the primary techniques. There may be some interesting results this way regardless, possibly around distributions of certain types of numbers.

Next time, I will go through my notes where factoring is seen as solving for roots of an real equation, and how to create a pretty spiffy function that bounces off the x-axis for every integer.


The joys of cardinality – part 1

So, here’s an article I’ve been meaning to write for a while. I love Cantor’s diagonal proof of how there are as many rational numbers (of the form a/b, for example 1/5 or 1/2 or 3/5) and yet there are more real numbers (this is the numbers with an infinite expansion of decimals like pi, e, 3.5252353…) than integers.

However, everytime I try to share this with people I get stuck because it’s very abstract thinking, even though it’s really cool. So, this is my attempt to explain it in a few steps so that everyone can understand how thinking rigourously can teach you very cool things about numbers.

So, let’s start with the idea of cardinality. How can we clearly state that two sets of objects are the same size. I want a method that is indisputable. So let’s imagine we have 2 sets of objects, baskets and balls.

|_| |_| |_|   o o o

Now, above we can see, at a glance, that we have the same number of baskets as balls, but how can we prove it to someone who can’t count. Well, we can put one ball into each basket.
|o| |o| |o|

Yep, each basket is full, and each ball is in a basket. So we must have the same number of baskets as balls. This is great.

Now let’s try another set of baskets and balls.

|_| |_| |_| |_|    o o

Putting them into the baskets, we have

|o||o| |_| |_|

Hmmm… we have more baskets than balls. This means that the two sets aren’t the same size as we have empty baskets. Technically, mathematicians would say this is a injective mapping of balls into baskets. However, we’ll avoid the technical terms for now.

One more set, just so we have all cases covered for finite syts.

|_| |_| |_| o o o o o

Putting balls into baskets, gives us:

|o| |o| |o| o o

Now we have 2 lonely balls rolling around without any baskets. Again, this clearly demonstrates that the two sets aren’t the same size, as we have balls that need baskets, and all of the baskets are full. If we were allowed to put more than one ball into a basket, this would be a surjective mapping of balls onto baskets. Again, you can ignore these technical terms. As the key point here is we now have a clear way to determining when we have 2 sets whether they are equal in size, or whether one is larger than the other.

So let’s try with an infinite set of baskets, and an infinite set of balls.

|_| |_| |_| |_| ....

o o o o ....

Now, obviously, we need to find a clear way to represent which ball would go into each basket without having to draw an infinite number of baskets with balls in them to verify. So, let’s number each basket and number each ball in the obvious fashion.

|_| |_| |_| |_| ...
 1   2   3   4 ...

o o o o ...
1 2 3 4 ...

Now, there is an obvious way we can put every ball into every basket. We put Ball 1 into Basket 1, Ball 2 into Basket 2, and so on. Now, how do we test if every basket is full? Well, we check if the basket has a ball in it. So if you were to challenge me by asking (Does basket 34255 have a ball in it?) I can respond, yes, it has ball 34255 in it, by how we filled the baskets. This is true, because we know ball 34255 exists, and we agreed to this method of filling baskets.

Something interesting happens now, you throw a ball to me and tell me to put it into a basket. Well, all the baskets are full, so this should be, in theory, impossible, right?

I look at the baskets, and go ok. I mark your ball as ball 0 and put it into basket 1, moving ball 1 to basket 2, and so on…

|_| |o| |o| |o| ...
1/1 2/2 3/3 4/4 ... (Basket Number / Ball Number)

0 (Ball Number 0, which to make it clearer we'll 
represent as a ball with a slash on it)

So we do this, take ball 1 out of basket 1, and put into basket 2. ball 2 out of basket 2 and put into basket 3, and so on…

|_| |o| |o| |o| ...
 1  2/1 3/2 4/3 ... (Basket Number / Ball Number)

Put in ball 0 into basket 1

|Ø| |o| |o| |o| ...
1/0 2/1 3/2 4/3 ... (Basket Number / Ball NumbeR)

Now, every single ball is in a basket, even though we added one ball to the previous pile. This is one of the more interesting properties of infinity. Adding a finite number of elements to an infinite set does not change how many objects there are overall from this perspective. You could give me 100 balls, and I would only need to shift the first 100 down all the way down the line and there’ll still be enough baskets.

I’ll let everyone think about that one for a bit, and tomorrow I am going to go into how there are just as many even numbers as numbers in general. Hopefully ending with a framework to show how you can see there are just as many rational numbers (ie. fractions) as integers (whole numbers like 1, 2, 3).

Leading to the really weird realization in the following post that there are actually levels of infinity. 🙂

Please if anything here confused you, please ask questions. I’d love to have the chance to clear it up and develop an even better way to show this neat beauty in mathematics.


Enhanced by Zemanta

Unsolved (math) problems…

Man, I love unsolved problems in any field of science or philosophy. This does not mean I don’t enjoy reading the elegant solutions or re-derivations of solutions to problems solved long ago (I’m looking at my grad studies Galois Theory prof and his re-derivation of everything in that subject using category theory.) However, there’s something energizing to seeing that not every problem has been solved and that science isn’t perfected.

In fact, nothing sends a chill up my spine more than when an experiment in Physics could potentially disprove a well accepted theory. Every time that has happened historically, the world changed (and usually for the better.)

But, I’m not a physicist and while I enjoy playing with the mathematics of quantum computation, I am a math major historically, and a mathematics buff through and through. Thus, I’m putting out this request to anyone who sees it. I want to know any unsolved problems you know of (beyond the obvious clay mathematics prizes) that you are aware are unsolved. Whether they are simple conjectures from combinatorics, to open questions from long long ago. If you have them, I want to hear them. If only so I have more fun things to play with whenever I get time.

Plus, it’d be pretty spiff to have one page (this blog entry) on the web as a central resource for mathies who are interested in these problems.


Enhanced by Zemanta