Tag Archives: theory

Examples

The Beauty of Euler’s phi function

Leave a comment

The recent conversation I had about number theory has brought it back into my awareness. In particular, the concept of beauty in numbers. I’m definitely not any kind of graphical designer or fashion expert but I do appreciate what I think of as beautiful, and there are certain areas of mathematics that are just beautiful.

But who am I to say what is beautiful? What really is beautiful? Rather than trying to talk about these things in terms of the abstract concept of beauty, I wanted to try to nail down some of the things I like about it.

In our early years we learn about shapes. Sometime later we learn about things like “regular polygons”. These are polygons where all sides have the same length. We also learn about stars, but the stars we learn to draw most often is the 5 point star that we can draw without lifting the pencil.

A natural question becomes are there other stars we can draw without lifting a pen? A 4 point star? a six point star? a seven point star?

Before we go into the ? function, lets make sure we’re on the same ground. We need to talk about common divisors.

Suppose we have two numbers, lets call them m and n. A common factor of m and n is a number that divides into both of them. For example a common divisor of 4 and 6 is 2 since 4 = 2 * 2 and 6 = 2 * 3. Two numbers are called relatively prime if their only common factor is 1. Remember that 1 is a factor of every number.

Euler’s ? function (called the totient function) of a number n is defined as the count of numbers less than n that are relatively prime to n.

n12345678910111213
?(n)112242646410412

To understand what’s going on in that table above, lets look at a number like 10 and ask what are the numbers relatively prime to 10?

n123456789
Factor 101*102*51*102*52*52*51*102*51_9
Factor n1*11*21*32*21*52*31*72*41*10
GCF121252121

So from this example we see that the numbers relatively prime to 10 are 1, 3, 7, and 9, so ?(10) = 4.

A nice property of Euler’s phi function is that for any n > 3, if ?(n) is 3 or greater, then we can draw a star with that many (n) points without lifting the pencil.

To do this, we first need to talk about modular arithmetic. If we have two numbers, a and b and want to add them modulo some number, written
(a + b) mod n
We take the remainder of (a + b) when this number is divided by n.

For example, if we wanted to calculate (3 + 5) mod 7 we would first compute (3 + 5) to get 8 and then realize that 8 = 7 * 1 + 1. This gives a remainder of 1, so (3 + 5) mod 7 would be congruent to 1.

If we are considering drawing an n pointed star, we can start with a number that is not 1 and is relatively prime to n and continually add that number to itself. What will happen is that because this number is relatively prime to n, it will visit every other number before returning to the number 0.

What is more is that there may be more than one n pointed star that we can draw. The number of stars is (?(n) – 2) / 2. So for 10, it will be (4 – 2) / 2 = 1. This can be seen below.

I wanted to allow users to begin to see more of this beauty, so I wrote a script showcasing it.

Examples

Pascal’s Triangle

Leave a comment

I had a recent conversation with a friend who asked me “what makes number theory interesting?”. I loved the question, mainly because it gave me an opportunity to talk about math in a positive manner. More importantly though, it was an opportunity to talk about one of my favorite courses in mathematics (along with discrete mathematics and set theory). As much as the current day seems to focus on joining Number Theory with Cryptography, when I answered this question I wanted to make sure I didn’t go that route. Numbers are beautiful in their own right, and one of the things about Number Theory that was so interesting was simply the ability to look at all the different questions and patterns and properties of numbers discovered.

To answer this question, I started listing numbers to see if she noticed a pattern, but I did it with a “picture”.

.
..
…
….
…..
……

and I asked two questions

  • How many dots will go on the next line
    and
  • After each line how many dots have been drawn in total?

Lets answer these questions:

Dots# on this line# in total
.11
..23
…36
….410
…..515

There were a lot of directions I could have taken this conversation next, but I decided to stay in the realm of triangles and discuss Pascal’s triangle. This is a triangle that begins with a 1 on the first row and each number on the rows beneath is the sum of the two cells above it, assuming that cells not present have a value of zero.

So the first five rows of this triangle are

1
11
121
1331
14641

This is an interesting and beautiful triangle because of just the number of patterns you can see in it.

  • Obviously there are ones on the outside cells of the triangle.
  • One layer in, we get what are called the Natural or Counting numbers (1, 2, 3, 4, 5, …) .
  • One layer in, we can start to see the list of numbers that I was showing my friend (1, 3, 6, 10, 15, …).

There are several other properties of this triangle and I wanted to allow users to begin to see them, so I wrote a script highlighting some of these patterns.

Blog

How To Take Notes in Math Class

2 Comments

I was recently asked by someone how they should be taking notes in math class. I could immediately relate because I once asked this very same question. In both undergrad and grad, I had to ask myself how to take notes because I often would leave class with a bunch of sentence fragments based on what the professor said, but without anything I could use as a study guide. At best, it would be a garbled thing that I could combine with somebody else’s notes and try to make some legible out of it. Generally though, I would just ignore my notes and go to the text book if it was well written, or the library if the text book was not well written.

So how did I get past this? Well, after taking the Set Theory course, I started seeing mathematics as more of a construction job, like building a house. Mathematics is based on proofs which is nothing more than logical reasoning, and logical reasoning is just a series of statements that are either assumptions, definitions, or conclusions drawn from those assumptions based on known facts. The main purpose of classes is to present these “known facts” to the students and help them become more informed mathematicians. So what is a mathematical fact?

There are two important types of facts we generally learn in mathematics. The first gives us a language we can work from – these are our definitions. These are the most important things in a mathematics class because if it is a class on “group theory”, then one of the first definitions will be of a “group,” and not knowing this definition will cause problems when you are trying to prove that something is or is not a group. Similarly, if your class is on solving quadratic equations, then it is very important to be able to define what a “quadratic equation” is. Definitions in mathematics are important because, unlike in an English class, you cannot always derive the meaning of a mathematical term from its usage. Mathematical definitions are very precise and your notes should include this precision.

As a side note, I will state (if not stress) that examples are not definitions. Examples are meant to bring the definition to life, and to help connect the definition to the student, but if you are asked what is a group and respond that “the set of integers mod 7 under the operation of addition is a group”, you’d be incorrect because you gave an example of a group without telling why this is a group. Similarly, if I were to ask you to define a quadratic equation and you said “x^2 + 2x + 1 = 0 is a quadratic equation”, you’d be giving me an example but not a definition. It is important to understand the distinction between examples and definitions because when we understand the definition we can clearly explain why (ala prove) that the given instance is in fact an example.

Some professors will briefly mention a definition and then focus most of their time on examples in an attempt to make the concepts easier to understand. As a student though, it is important to ask the question “what is the definition of _____” because the exams, or the research that follows, or the applications of this concept in real life are not likely to be that same example. If the professor does not write out the definition of whatever concept you are studying, or you are unclear of this definition you should ask questions, go to an online resource, or a text book for supplementary reference.

The second type of fact presented in mathematical classes is the theorem (aka lemma or corollary). A theorem is a statement that is provable by mathematical reasoning. In a classroom setting, theorems will generally be presented in an orderly fashion such that if Theorem 1 is presented before Theorem 2, then Theorem 1 does not require Theorem 2 in order to be proven.

Because theorems are provable statements, it may be tempting to jump directly into the proof, and particularly to only take notes on the proof. I cannot stress against this enough. Before writing the proof, you should make sure to begin the proof with a clear statement of the theorem. This should be a declarative statement that is thus provable. Do not confuse the questions a professor may ask before proving a theorem with the theorem itself. An example of a theorem from group theory is “Any group that has a prime number of elements of elements in that group is cyclic (or can be generated by a single element). Also, do not confuse the nicknames of theorems with the theorem itself. For instance Lagrange’s Theorem says that “the number of elements of any subgroup of a finite group divides the number of elements in the original group.” Remembering this as Lagrange’s Theorem is fine, but it is much more important to remember the declarative statement proved.

I’m sure there are other things people use to take notes in math classes. Feel free to leave a comment sharing some of this advice.

Examples

The Assignment Problem

Leave a comment

I just finished a script that generates instances of the assignment problem and solves them step by step. You can check it out here.

Assignment Problem Image

Suppose you are the owner of a company and need to delegate tasks to your employees. You’ve generated a table that tells how long (in minutes) you think it would take each person to accomplish each individual task (called Jobs). Your goal is to find an assignment of people to jobs that minimizes the total amount of time it will take to complete all jobs. The requirements are that each job must be completed by only one person, and each person can complete only one job.

We can think of the employees at the job as our supply and the tasks as the demand. In order for this problem to have a feasible solution, we must have enough people (supply) to complete the number of jobs (demand). Because of this, our examples will all include situations where there are exactly the same number of people as jobs.

To solve this problem, we must first generate an initial assignment and see how good this assignment is. There are several ways of generating an initial solution, but two that I wanted to focus on are the “NorthWest Corner Rule” and the “Minimum Matrix Method”.

  1. The Northwest Corner Rule considers the matrix and repeatedly assigns the top remaining row to the left-most remaining column. If we think of the cost matrix as a being like a map then “top” becomes similar to “north” and left-most becomes similar to “west”, hence the derivation of the name. In assignment problems, this will result in the main diagonal being selected.
  2. The Minimum Matrix Method is an iterative method that searches the matrix for the minimum cell in the matrix and assigns that person to the associated job and removes them from consideration and repeats itself until all people have been assigned to jobs.

Once we have formulated an initial feasible solution, we need to check it for optimality. To do this, we use the Network Simplex Method, where we build a basis based on this initial solution. When we consider this problem as a network flow problem, a basis for the problem is a spanning tree (one less than twice the number of nodes in the graph that does not have any cycles) of the network. Because the assignment solution only contains one edge for every two nodes in the graph, we need to add a number of edges to the basis that contains no flow (which makes the solution degenerate) to form this spanning tree.

Once a spanning tree is formulated, we can solve for the dual variables by arbitrarily setting one node’s dual value to zero and solving for the remaining dual variables under the requirement that all arcs in the basis (spanning tree) must satisfy the equation uk + vi = cki for each person k and job i.

When we have dual variables, we can check to see if this solution is optimal by checking to see if all the other constraints are violated. This means that for every person k and every job i, we must have uk + vi cki (notice that this is a more relaxed version of what we had when we were solving for the dual variables themselves).

If a constraint is found to be violated, then we need to add the associated edge to the basis and remove an edge on the cycle that is formulated as a result, which generates a new solution.

So check out The Assignment Problem Script and let me know what you think.

Blog, Examples

Understanding Bayes’ Theorem

Leave a comment

An Image of Bayes' Theorem Script
An Image of Bayes’ Theorem Script

I’ve finished a script that helps understand Bayes’ Theorem.

If we have a set of mutually exclusive (aka non-overlapping) sets Bi for i {0, 1, 2, …, n} for some integer n, then the union of these sets forms a sample space. Lets call the sample space S. Suppose that we also have some set (also known as an event) A which is also a subset of S. Bayes’ Theorem considers the probability that one of these mutually exclusive events (one of the Bi‘s) caused the observed event (A).

This probability can be calculated by the formula

Pr(Bj | A) =
Pr(Bj) Pr(A | Bj)
Pr(Bi) Pr(A | Bi)

The theorem helps us determine the the probability of the event Bj given A, or in more plain English, the probability that the event Bj is the cause that gives rise to the observed event A. The numerator is given by the product of of the probability of the causal event (Pr(Bj) times the conditional probability of the observed event given the causal event (Pr(A | Bj)). This numerator could be replaced by its equivalent statement of the set A Bj. Likewise, the denominator the sum (over all the causal events) of the probaility of each causal event times the conditional probability of the observed event given that particular causal event. Each term in this denominator could be replaced b its equivalent staetment A Bi, which when summed give the total probability of A because each pair of the Bj‘s is mutually exclusive. So we are able to replace the probability of A with Pr(Bi) Pr(A | Bi) because of the fundamental law of probability.

An example that would use Bayes’ Theorem is analyzing the results of an election. The set of mutually exclusive events could be membership in a political party (Democrat, Republican, or Independent). The observed event could be the election of an individual. And the conditional distributions could be the percentage of each party that voted for this individual. If we want to calculate how significant each party was to the individual’s election, we’d use Bayes’ Theorem.

The script I’ve written to help understand Bayes’ Theorem works as follows:
– A set of mutually exclusive sets is randomly generated (the number of sets also varies). These sets are called Bi for i (0, …, n}.
– A set A is randomly generated from the union of the Bi‘s.
– A table is displayed showing:
Pr(Bi) for each i on line 1.
Pr(A | Bi) for each i on line 2.

– The user is given the option to select which of the mutually exclusive sets they would like to use to calculate the probability that this set caused the event A.
– Once a set is chosen, the user clicks the “Calculate Conditional” button and Bayes’ Theorem gives the result.
– If the “show work” checkbox was checked, then the steps used in this calculation are also shown.
– All work is done using fractions to give an idea of where the numbers come from.

Other Blogs that have covered this topic:
Better Explained
Bayes’ Theorem-qed