## Graph Isomorpshism and Coloring

This week, Professor Siemion Fajtlowicz assigned two home work problems:

1. How many graphs with vertices 1 … n are there?

2. Up to isomorphism, how many graphs are there with n vertices?

3. If you invite 6 random people to a party, show that 3 of them will know each other or 3 of them will be mutual strangers — and show that this is guaranteed to always be the case — but only if you invite a minimum of 6 random people to the party. It will not be the case if we only invite 5 random people or 4 random people, et cetera.

____________________________________________________________________________________________________________________________
Question 1 and 2 may appear to be identical questions, but they are not at all identical though they are related.

Question 1 is asking for the number of elements of S. Question 2 is asking for the number of elements of the quotient G\S, a very different and much more difficult question.

Theorem. There are

$\displaystyle {{2}^{\left( \begin{matrix} n \\ 2 \\ \end{matrix} \right)}}$

graphs with vertex set $\displaystyle \{1,2,3,...,n-1,n\}$ .

Proof. The question is easily answered. Given n vertexes, if we start from vertex 1 and connect an edge to each of the remaining vertexes, so that 1 goes to 2, 1 goes to 3, and so on until 1 goes to (n-1) , and 1 goes finally to n. Now, including the null edge or simply 1 itself connected to nothing, which is a legitimate graph, we have that there are n graphs. Repeating this for each additional vertex, and taking into account that the edge may originate at either one of the vertexes making for two graphs — if allowing full duplicates — then we will have that there are exactly,

$\displaystyle ^{1+2+3+...+(n-1)+n}$

possible graphs raised to the power of 2 to account for starting at either vertex, which gives us:

$\displaystyle {{2}^{1+2+3+...+(n-1)+n}}={{2}^{\sum\limits_{i/{{\mathbb{Z}}_{+}}}{i}}}={{2}^{\frac{n(n+1)}{2}}}$

Therfore, the number of graphs with vertices 1 to n are:

$\displaystyle {{2}^{\left( \begin{matrix} n \\ 2 \\ \end{matrix} \right)}}$

and this is simply a more compact way of writing the RHS of the previous result using binomial coefficients. QED

____________________________________________________________________________________________________________________________

Theorem. Up to isomorphism, there are

$\displaystyle \frac{1}{n!}\sum\limits_{n\in \sum\nolimits_{n}{{}}}{{{2}^{o\left( \sigma \right)}}}$

graphs with n vertices.

The answer to the question is much more difficult, because the answer involves some hefty but basic machinery from Group Theory and Combinatorics involving Burnside’s Lemma and Polya’s Enumeration Theorem such that this question may be reworded in those terms, so that it becomes:

How large is the set $\displaystyle \sum\nolimits_{n}{{}}\backslash S$ where $\displaystyle \sum\nolimits_{n}{{}}$ denotes the symmetric group on n letters and $\displaystyle S$ is the set of graphs with vertex set $\displaystyle {1,2,3,...,n-1,n}$ ?

$\displaystyle \frac{1}{n!}\sum\limits_{n\in \sum\nolimits_{n}{{}}}{{{2}^{o\left( \sigma \right)}}}$

where $\displaystyle o\left( \sigma \right)$ denotes the number of $\displaystyle \sigma$ orbits on the set.

____________________________________________________________________________________________________________________________

At any party with 6 guests, either 3 are mutual friends or else 3 are mutual strangers. That is, the symmetric Ramsey Number R(3,3) = 6

If we consider just one person, then the other five must fall into one of the two classes of being either a friend or a stranger. This follows immediately from the pigeonhole principle, namely that, if m pigeons occupy n holes where $\displaystyle n , then at least one hole contains:

$\displaystyle \left\lfloor \frac{m-1}{n} \right\rfloor +1$

pigeons, where $\displaystyle \left\lfloor {} \right\rfloor$ is the greatest integer function. The proof of this follows from the fact that the largest multiple of n that divides into m is the fractional part left over after n divides m-1 or

$\displaystyle \left\lfloor \frac{m-1}{n} \right\rfloor$

and so for n pigeons, we get

$\displaystyle n\left\lfloor \frac{m-1}{n} \right\rfloor$

pigeons that could be put into $\displaystyle \left\lfloor \frac{m-1}{n} \right\rfloor$ holes. But we have m pigeons, and so there must be more than this many pigeons in the holes.

Now, for our problem, we have two classes, friends and strangers. If we choose one person, then that leaves 5 people with whom that person is either a friend or a stranger. And so, by the pigeonhole principle, for five objects going into two classes we must have at least:

$\displaystyle \left\lfloor \frac{5-1}{2} \right\rfloor +1=3$

members in one of the classes. In terms of a graph theoretical viewpoint, we have, starting with one vertex extended out to the other five “people” vertexes, that:

where the red edges represent friends and the blue edges represent strangers. We easily see that, regardless of how we choose one of our 2 colors, 3 of them must be blue or else 3 of them must be red, for if we have five red, then we have met the required condition that at least 3 be red, and likewise if 4 are red, we again fulfill the requirement that at least 3 be red; and so, this whole sequence of argument applies if we swap blur for red. Therefore, we are always guaranteed that there are 3 mutual friends or else that there are 3 mutual strangers in any group of 6 people. QED

In terms of Ramsey Numbers, the statement would be written $\displaystyle R(3,3)=6$ .

This is utterly fascinating, because what this is really telling us it that there is a type of structure built into any random finite set. In this case, for any binary operation or else any question or property that has two values, we have it that any finite set of 6 is sufficient to support there being 3 of one or 3 of the other of that property, and that one of the two sets of 3 always exists inside of the 6 items.

This is a glimpse into a type of “deep structure” embedded within the fabric of finite sets. This is more than merely surprising, as one should not really be expecting to find any such structure whatsoever in a random set.
____________________________________________________________________________________________________________________________

Going somewhat beyond this homework problem, from experimental math studies using Mathematica, I conjecture that:

$\displaystyle R(n,n)=\frac{1}{12}(3{{n}^{4}}-20{{n}^{3}}+63{{n}^{2}}-82n+48)$

holds for n<=20 in a completely trivial and weak algebraic sense that the Ramsey Numbers in this range do indeed appear in this formula.

However, there is no natural or reasonable theoretical connection whatsoever between this formula and Ramsey Numbers other than the search for generating functions and sequence matching studies that I conducted. So, for n = 3 to 20 this formula yields:

$\displaystyle \text{R(3,3) = 6}$
$\displaystyle \text{R(4,4) = 18}$
$\displaystyle \text{R(5,5) = }49$
$\displaystyle \text{R(6,6) = }116$
$\displaystyle \text{R(7,7) = }242$
$\displaystyle \text{R(8,8) = }456$
$\displaystyle \text{R(9,9) = }793$
$\displaystyle \text{R(10,10) = }1,294$
$\displaystyle \text{R(11,11) = }2,006$
$\displaystyle \text{R(12,12) = }2,982$
$\displaystyle \text{R(13,13) = }4,281$
$\displaystyle \text{R(14,14) = }5,968$
$\displaystyle \text{R(15,15) = }8,114$
$\displaystyle \text{R(16,16) = }10,796$
$\displaystyle \text{R(17,17) = }14,097$
$\displaystyle \text{R(18,18) = }18,106$
$\displaystyle \text{R(19,19) = }22,918$
$\displaystyle \text{R(20,20) = }28,634$

which all fall nicely into current best-known intervals for these numbers. But these values are essentially nonsense. However, it is currently believed that $\displaystyle \text{R(5,5) = }43$ rather than 49. But there is no polynomial expression that yields 43 and the other lower already known numbers in the sequence of Ramsey Numbers evident from running long and large searches for such. Therefore, I believe that any meaningful approximate or asymptotic formula must be non-polynomial.

Therefore, my intuition says that there may well exist an exponential, non-polynomial expression for the Ramsey Numbers — perhaps similar to the P(n) function of Rademacher such as

$\displaystyle p(n)=\frac{1}{\pi \sqrt{2}}\sum\limits_{k=1}^{\infty }{\sqrt{k}}{{A}_{k}}(n)\frac{d}{dn}\left( \frac{1}{\sqrt{n-\frac{1}{24}}}\sinh \left[ \frac{\pi }{k}\sqrt{\frac{2}{3}\left( n-\frac{1}{24} \right)} \right] \right)$

where

$\displaystyle {{A}_{k}}(n)=\sum\limits_{0\le m

But then I may be dreaming here because there need be no sequential connection between one of these numbers and the other — if each is a unique value in it’s own problem space.

What I find frustrating with papers on Ramsey Numbers that I have read is their lack of a more probing approach. We know that calculating Ramsey Numbers is NP-hard. One paper even suggested that this is Hyper-NP hard — but did not specify in what manner they meant this to be true. Most likely they were referring to the absurdly rapid exponential growth of the possible solution space. But where are the more basic insights into the nature of these numbers? Most of what we have now is not much beyond Paul Erdős work in the 1930’s!

In a recent paper on Ramsey Numbers, the physicist Kunjun Song, said: “Roughly speaking, Ramsey theory is the precise mathematical formulation of the statement: Complete disorder is impossible. or Every large enough structure will inevitably contain some regular substructures. The Ramsey number measures how large on earth does the structure need to be so that the speci ed (sic.) substructures are guaranteed to emerge.”

I think that we have yet to ask ourselves the deeper questions to get further along here. I am now researching the different ways in which the same questions may be asked, such as via Shannon limits of graphs and quantum algorithms to see what pure mathematical insight might be gleamed from these approaches. I am looking for good questions that, if properly phrased, should provide a road-map for further fruitful research.

## Introduction to Graph Theory

This was the first week of my senior-level class with Professor Siemion Fajtlowicz, MATH 4315 – Graph Theory, and it was a blast!

The central question put to the class is when are two graphs isomorphic. There is nothing easy nor trivial about this question. It can be challenging to even distinguish that two simple graph representations are of different graphs, let alone of the same graph.

Also, we have been assigned the task of showing how one is to interpret the historically notable problem, first presented to and solved by Leonhard Euler in 1735, of the Seven Bridges of Königsberg in a graph theoretic manner. Euler resolved this question in the negative, but there is a lot more to it than that, as we will see in this article.

Along with this problem, we have also been assigned the Knight’s Tour problem which we are also to interpret in a graph theoretic fashion.

## Divisiblity and the GCD

The work here is actual assigned homework from Dr. Mary Flagg’s Number Theory, Math 4383 – Section 19842, going on now at the University of Houston this Spring 2012 semester. This is from homework assignment 2. The problems are taken from Elementary Number Theory, Seventh Edition, by David. M. Burton.

However, I will be going beyond much of this homework by adding additional material as it strikes me as being relevant to the topic at hand.

Basic Divisibility Theory of the Integers

2.2 – 5. For $\displaystyle n\ge 1$ , prove that $\displaystyle n(n+1)(2n+1)/6$ is an integer.

Proof. By the division algorithm, if $\displaystyle 6|n(n+1)(2n+1)$ , we may write

$\displaystyle n(n+1)(2n+1)=6q+r$ where $\displaystyle 0\le r\le 6$ . Therefore, since r may only assume integer values, we have that $\displaystyle n(n+1)(2n+1)$ may only assume any one of the following six forms, corresponding to each value of the remainder $\displaystyle r=0,1,2,3,4,5$ so that n must be in one of the following forms:

$\displaystyle n=6q$ , $\displaystyle n=6q+1$ , $\displaystyle n=6q+2$ , $\displaystyle n=6q+3$ , $\displaystyle n=6q+4$, $\displaystyle n=6q+5$

Therefore, we need only substitute each of these in our expression $\displaystyle n(n+1)(2n+1)/6$ and simplify to see what results. So, proceeding on a case by case basis, we have, for the first case:

$\displaystyle n(n+1)(2n+1)/6$ for $\displaystyle n=6q$ we get

$\displaystyle \frac{6q(6q+1)(2(6q)+1)}{6}=\frac{432{{q}^{3}}+108{{q}^{2}}+6q}{6}$

$\displaystyle =72{{q}^{3}}+18{{q}^{2}}+q$

which is an integer, as there are no fractions left on the RHS. Now, in the second case:

$\displaystyle n(n+1)(2n+1)/6$ for $\displaystyle n=6q+1$ we get

$\displaystyle \frac{(6q+1)((6q+1)+1)(2(6q+1)+1)}{6}=\frac{432{{q}^{3}}+324{{q}^{2}}+78q+6}{6}$

$\displaystyle =72{{q}^{3}}+54{{q}^{2}}+13q+1$

which is also clearly an integer. And, in the third case:

$\displaystyle n(n+1)(2n+1)/6$ for $\displaystyle n=6q+2$ we get

$\displaystyle \frac{(6q+2)((6q+2)+1)(2(6q+2)+1)}{6}=\frac{432{{q}^{3}}+540{{q}^{2}}+222q+30}{6}$

$\displaystyle =72{{q}^{3}}+90{{q}^{2}}+37q+5$

which is also clearly an integer. And, in the fourth case:

$\displaystyle n(n+1)(2n+1)/6$ for $\displaystyle n=6q+3$ we get

$\displaystyle \frac{(6q+3)((6q+3)+1)(2(6q+3)+1)}{6}=\frac{432{{q}^{3}}+756{{q}^{2}}+438q+84}{6}$

$\displaystyle =72{{q}^{3}}+126{{q}^{2}}+73q+14$

which is also clearly an integer. And, in the fifth case:

$\displaystyle n(n+1)(2n+1)/6$ for $\displaystyle n=6q+4$ we get

$\displaystyle \frac{(6q+4)((6q+4)+1)(2(6q+4)+1)}{6}=\frac{432{{q}^{3}}+972{{q}^{2}}+726q+180}{6}$

$\displaystyle =72{{q}^{3}}+162{{q}^{2}}+121q+30$

which is also clearly an integer. And, in the sixth case:

$\displaystyle n(n+1)(2n+1)/6$ for $\displaystyle n=6q+5$ we get

$\displaystyle \frac{(6q+5)((6q+5)+1)(2(6q+5)+1)}{6}=\frac{432{{q}^{3}}+1188{{q}^{2}}+1086q+330}{6}$

$\displaystyle =72{{q}^{3}}+198{{q}^{2}}+181q+55$

and this too is an integer. Therefore, for all values of $\displaystyle n\ge 1$ , we have established that

$\displaystyle \frac{n(n+1)(2n+1)}{6}$

is an integer for all $\displaystyle n\ge 1$ . QED

Note. Of course, this expression is also the sum of the squares of the first n integers, or

$\displaystyle {{1}^{2}}+{{2}^{2}}+{{3}^{2}}+...+{{n}^{2}}=\frac{n(n+1)(2n+1)}{6}$

for all $\displaystyle n\ge 1$ and so, because the square of an integer is an integer, so would be a sum of squares of integers, and so this may be developed out into another proof, as a corollary, by obtaining and proving the summation formula itself it would follow that it is an integer.

2.2 – 11. If n is an odd integer, show that $\displaystyle {{n}^{4}}+4{{n}^{2}}+11$ is of the form 16k.

Proof. Assume that n has the form $\displaystyle n=2k+1$ so that n is odd. Then, by direct substitution and upon simplification, we have

$\displaystyle {{(2n+1)}^{4}}+4{{(2k+1)}^{2}}+11$

$\displaystyle =(16{{k}^{4}}+16{{k}^{3}}+16{{k}^{2}}+8k+1)+(8k+4)+11$

$\displaystyle =16{{k}^{4}}+16{{k}^{3}}+16{{k}^{2}}+(8+8)k+(1+4+11)$

$\displaystyle =16{{k}^{4}}+16{{k}^{3}}+16{{k}^{2}}+16k+16$

$\displaystyle =16({{k}^{4}}+{{k}^{3}}+{{k}^{2}}+k+1)=16K$

where

$\displaystyle K={{k}^{4}}+{{k}^{3}}+{{k}^{2}}+k+1$ .

Therefore, $\displaystyle {{n}^{4}}+4{{n}^{2}}+11$ is of the form 16K for all odd positive integers. QED

2.3 – 3. Prove or disprove: if $\displaystyle a|(b+c)$ , then either $\displaystyle a|b$ or $\displaystyle a|c$ .

Proof. By counterexample, we have

$\displaystyle 18|7+11$ but $\displaystyle 18|7$ false and $\displaystyle 18|11$ is false.

So, without loss of generality, we may say that,

if $\displaystyle b and $\displaystyle c but $\displaystyle b+c=a$ , then it is true that:

$\displaystyle a|(b+c)$ or more fully, that $\displaystyle \frac{b+c}{a}=\frac{a}{a}=1$ and we see that $\displaystyle a|b$ and $\displaystyle a|c$ are both false. QED.

2.3 – 4. For $\displaystyle n\ge 1$ , use mathematical induction to establish the following divisibility statement that

$\displaystyle 15|{{2}^{4n}}-1$ .

Proof. Using the PMI, we have for $\displaystyle n=1$ ,

$\displaystyle \frac{{{2}^{4(1)}}-1}{15}=\frac{{{2}^{4}}-1}{15}=\frac{16-1}{15}=\frac{15}{15}=1$

or

$\displaystyle ({{2}^{4}}-1)=1\cdot 15+0$

and therefore it is true that

$\displaystyle 15|{{2}^{4n}}-1$

when n=1. Assume that for some positive integer k that

$\displaystyle 15|{{2}^{4k}}-1$

is true and note that this also means that:

$\displaystyle 3\cdot 5|{{2}^{4k}}-1$

or that

$\displaystyle {{2}^{4k}}-1=15q$

or

$\displaystyle {{2}^{4k}}-1=3\cdot 5\cdot q$

for some multiple q of 15. But the LHS factors into:

$\displaystyle {{2}^{4k}}-1=({{2}^{k}}+1)({{2}^{2k}}+1)({{2}^{k}}-1)$

which implies that:

$\displaystyle 3\cdot 5|({{2}^{k}}+1)({{2}^{2k}}+1)({{2}^{k}}-1)$

or

$\displaystyle ({{2}^{k}}+1)({{2}^{2k}}+1)({{2}^{k}}-1)=3\cdot 5\cdot q$

and now this implies that, either:

$\displaystyle 3|{{2}^{k}}+1$

or else

$\displaystyle 3|{{2}^{2k}}+1$

or else

$\displaystyle 3|{{2}^{k}}-1$

and likewise for 5, that either:

$\displaystyle 5|{{2}^{k}}+1$

or else

$\displaystyle 5|{{2}^{2k}}+1$

or else

$\displaystyle 5|{{2}^{k}}-1$

one of which must be true and for each of the integers 3 and 5. Now, for (k+1) we have that:

$\displaystyle \frac{{{2}^{4(k+1)}}-1}{15}=\frac{{{2}^{4k+4}}-1}{15}=q+r$

or

$\displaystyle {{2}^{4k+4}}-1=15q$

or

$\displaystyle {{2}^{4k+4}}-1=3\cdot 5\cdot q$

where q is the quotient and r must equal 0 if 15 is to divide exactly into $\displaystyle {{2}^{4k+4}}-1$ . Now, by factoring, we have that:

$\displaystyle {{2}^{4k+4}}-1=({{2}^{k+1}}+1)({{2}^{2k+2}}+1)({{2}^{k+1}}-1)$

so that we have also:

$\displaystyle ({{2}^{k+1}}+1)({{2}^{2k+2}}+1)({{2}^{k+1}}-1)=15q$

or

$\displaystyle ({{2}^{k+1}}+1)({{2}^{2k+2}}+1)({{2}^{k+1}}-1)=3\cdot 5\cdot q$

but each of these factors is simply the same as the assumed case n=k when n=k+1. And it is already true, by assumption, that

$\displaystyle 3\cdot 5|({{2}^{k}}+1)({{2}^{2k}}+1)({{2}^{k}}-1)$

or

$\displaystyle 3\cdot 5|{{2}^{4k}}-1$

Therefore, by the PMI, we have that,

$\displaystyle 15|{{2}^{4n}}-1$

for all

$\displaystyle n\ge 1$ , $\displaystyle n\in {{\mathbb{Z}}^{+}}$. QED

2.3 – 13 Given two integers a and b, prove the following: there exists integers x and y for which $\displaystyle c=ax+by$ if and only if $\displaystyle \gcd (a,b)|c.$

Proof. This is almost the converse of theorem 2.4 on page 23, namely that, if a and b are both integers not equal to zero, then a and b are relatively prime if and only if there exist integers x and y such that $\displaystyle 1=ax+by$ . From this we have that, if $\displaystyle \gcd (a,b)=1$ , then:

$\displaystyle 1=ax+by$ but from corollary 1 to the theorem 2.4, both on page 23, we have that if $\displaystyle \gcd (a,b)=d$ then $\displaystyle gdc(a/d,b/d)=1$ and this implies that:

$\displaystyle 1=\left( \frac{a}{d} \right)x+\left( \frac{b}{d} \right)y$

but multiplying both sides of this by d and setting d=c yields:

$\displaystyle c=ax+by$

but this means that $\displaystyle \gcd (a,b)=c$ but c|a and c|b and therefore $\displaystyle \gcd (a,b)|c$ because $\displaystyle \frac{\gcd (a,b)}{c}=\frac{c}{c}=1$ . QED

2.3 – 13(b) If there exist integers x and y for which $\displaystyle ax+by=\gcd (a,b)$, then $\displaystyle \gcd (x,y)=1$ .

Proof. This is theorem 2.4 where the terms are inverted. We have, by theorem 2.4, that a and b are relatively prime if and only if there exists integers x and you such that $\displaystyle 1=ax+by$ . Now, suppose that $\displaystyle 1=ax+by$ for some choice of x and y, such that $\displaystyle =\gcd (a,b)$. Because $\displaystyle |a$ and $\displaystyle |b$ , by theorm 2.2 we get that $\displaystyle |(ax+by)$or $\displaystyle =0$ but this last condition forces d to be 1. Therefore, $\displaystyle \gcd (x,y)=1$ must be true. QED

2.3 – 20(e). Confirm the following properties of the greatest common divisor. If $\displaystyle \gcd (a,b)=1$ and $\displaystyle |ac$ and $\displaystyle |bc$ , then $\displaystyle |c$ .

Proof. We are given that a and b are relatively prime, which means that:

$\displaystyle 1=ax+by$ for some linear combination of a and b their exist such integers x and y that this is true. Now, if $\displaystyle |ac$ and $\displaystyle |bc$ means that $\displaystyle ac=qd+r$ and $\displaystyle bc={{q}^{'}}d+{{r}^{'}}$ for some q, q’, r, r’. Therefore, we must have that d divides either a or c, given that $\displaystyle d|ac$ , and likewise, d must divide either b or c, given that $\displaystyle d|bc$ .

Assume, in the first case, that d divides a but not c. And assume that, in the second case, that d divides b but not c also. Then we would have $\displaystyle a={{q}_{1}}d+{{r}_{1}}$and $\displaystyle b={{q}_{1}}^{'}d+{{r}^{'}}_{1}$ or subtracting these from the other set, that:

$\displaystyle ac-a=q-{{q}_{1}}d+(r-{{r}_{1}})$

or

$\displaystyle a(c-1)=(q-{{q}_{1}})d+(r-{{r}_{1}})$

and

$\displaystyle c-b={{q}^{'}}-{{q}_{1}}^{'}d+({{r}^{'}}-{{r}_{1}}^{'})$

or

$\displaystyle (c-1)=({{q}^{'}}-{{q}_{1}}^{'})d+({{r}^{'}}-{{r}_{1}}^{'})$

but a and b are relatively prime implies, if d dives both a and b, then:

$\displaystyle 1=\left( \frac{a}{d} \right)x+\left( \frac{b}{d} \right)y$

or

$\displaystyle d=ax+by$

but since it is also true that $\displaystyle d|ac$ and that $\displaystyle d|bc$ each implies that $\displaystyle \gcd (d,a)=1$ and that the $\displaystyle \gcd (d,b)=1$ respectably, which is a contradiction. Therefore, d must divide c if $\displaystyle d|ac$ and $\displaystyle d|bc$ . QED

2.3 – 21.
(a) Prove that if $\displaystyle d|n$ , then $\displaystyle {{2}^{d}}-1|{{2}^{n}}-1$ .

Proof. First off, if $\displaystyle d|n$ , then there exists a q and r such that:

$\displaystyle n=qd+r$ where $\displaystyle 0\le r\le d$ and so, we are being asked to prove that:

$\displaystyle ({{2}^{n}}-1)=q({{2}^{d}}-1)+r$ where $\displaystyle 0\le r\le ({{2}^{d}}-1)$

Now, from first principles, because $\displaystyle d|n$ , we must have that:

$\displaystyle d

or else there could be no division by d into n in integer terms, and so therefore, we also have:

$\displaystyle {{a}^{d}}<{{a}^{n}}$ for some positive integer $\displaystyle a\ge 1$ because $\displaystyle d . Note that this implies that $\displaystyle 1<\frac{{{a}^{n}}}{{{a}^{d}}}={{a}^{n-d}}$ . Now, subtracting one from both sides yields:

$\displaystyle {{a}^{d}}-1<{{a}^{n}}-1$

And, because $\displaystyle d implies that $\displaystyle {{a}^{d}}<{{a}^{n}}$ , and this implies that $\displaystyle {{a}^{d}}-1<{{a}^{n}}-1$ , upon division of the RHS by the LHS, yields:

$\displaystyle 1b>0$ , then $\displaystyle a+b\le ab$ , and so, if the $\displaystyle \gcd (a,b)=1$ , then

$\displaystyle a=k\cdot b+0$ for some $\displaystyle k>0$ . Now, without loss of generally, taking $\displaystyle a=k\cdot b$ and

substituting, we have:

$\displaystyle \gcd (a+b,ab)=\gcd (kb,(kb)b)=\gcd (kb,k{{b}^{2}})$

but this implies that

$\displaystyle kb=kb\cdot b+0$

or

$\displaystyle kb=k{{b}^{2}}+0$

or dividing both sides by b

$\displaystyle k=kb+0$

which implies that

$\displaystyle \gcd (k,b)=1$ and likewise argument if we go substituting $\displaystyle a=k\cdot b$ but this is just $\displaystyle \gcd (k,b)=\gcd (kb,k{{b}^{2}})=\gcd (kb,(kb)b)=\gcd (a+b,ab)=1$ and therefore, if $\displaystyle \gcd (a,b)=1$ , then $\displaystyle \gcd (a+b,ab)=1$ . QED

2.4 – 9. Prove that the greatest common divisor of two positive numbers a and b divides their least common multiple, especially that $\displaystyle \frac{lcm(a,b)}{\gcd (a,b)}$ .

Proof. By merging the definitions of the gcd and lcm of two integers, a and b, we have that the gcd of a and b is the positive integer d satisfying the following:

(a) $\displaystyle d|a$ and $\displaystyle d|b$
(b) if $\displaystyle c|a$ and $\displaystyle c|a$ , then $\displaystyle c\le d$

and the lcm of two positive integers a and b is the positive integer m satisfying:

(a) $\displaystyle a|m$ and $\displaystyle b|m$
(b) If $\displaystyle a|c$ and $\displaystyle b|c$ , with $\displaystyle c>0$ , then $\displaystyle m\le c$

but $\displaystyle d|a$ and $\displaystyle a|m$ , therefore $\displaystyle d|m$ and $\displaystyle m\le c\le d$ because $\displaystyle c\le d$ and $\displaystyle m\le c$ . Again, we have that $\displaystyle d|b$ and $\displaystyle b|m$ , therefore $\displaystyle d|m$ and $\displaystyle m\le c\le d$ because $\displaystyle c\le d$ and $\displaystyle m\le c$ . Therefore, we see that the gcd does indeed divide the lcm, and we have established that

$\displaystyle \gcd (a,b)|lcm(a,b)$ .

QED

Saturday 28 January 2012
© Kurt Lovelace all right reserved

## Jan 2012 Aletheia Reading at Avant Garden

Here is a recap of sorts for those of you unable to attend the reading of the University of Houston’s Honors College Aletheia Literary and Arts Journal’s new Spring 2012 Chapbook due to the severe thunderstorms and flooding during the day. One artist and three poets were present.

The venue for the reading was the second floor of the marvelous Avant Garden. As you can see from the photo above, the place exuded a very beat-like 1950’s atmosphere and even had a trio downstairs on stage performing melancholy soundscapes on cello, piano, and guitar across from the open bar.

Be sure to join the Aletheia Journal every 3rd Wednesday of the month for new readings at the Avant Garden.

First happening at the reading was a presentation and warm welcome for the amazing artist, Lindsey Slavin, whose work is prominently featured in the current issue. Then followed introductions of the readers, prior to each getting on stage. The readers, in order of reading, were Chris Oidtmann, Justin Carter, and Kurt Lovelace.

Below are listed their poems in the order in which they were read. Also, the full text of the poems that Chris Oidtmann and Kurt Lovelace read are included here in their entirety. Some of Justin Carter’s pieces are pending publication elsewhere, so he was not able to make them available here, but the titles of what he read are nonetheless included.

Ghost
I Help You Create An eHarmony Account
Poem For A Blind Friend
Walmart Sestina
I Hope The Motion-Detecting Cameras Did Not See Our Faces
After Hoagland’s Color of the Sky
We Discovered We Were Chewable
Rita Repulsa
Lord Zedd

[back to the top]

Chris Oditmann

Mother Is Resting, Light the Match

‘76 Nova in the garage
papers piled on the kitchen table,
cups and saucers cracked
and stacked on the counter,
another log for the waning fire

basement flooded with gasoline,
pungent fumes creeping upstairs
saturating the carpets and drapes,

dogs tied to trees, pacing in circles
panting under relentless sunlight
that melts thin windows.

The smell of Weller and Pall Malls
burns his nose as he lies on her floor
watching the pious people on TV
proselytizing while Hank Williams
bleeds from the radio next to her bed

He looks at her,
then to the mirror
and repeats

“Forgive her father, for she has sinned”
Because unto her a monster was born
With flailing limbs, a balding crown
a demon in swaddling clothes.

He played his role today
and waits for the brimstone to fall
on the drapes and the carpets
and his own body, prone and naked
while he watches her stare
at machines gasping a last I LOVE YOU.

[back to the top]

Sundae

I remember your black shoes with the silver buckle
Leaping across rocks and along jettys
Sending up splashes of salty water shining
In the moonlight like sparks from a bottle rocket

That same night you left your wallet by the bed,
And pulsed against the wall until it broke
Into a milky way of beige and fluorescent beige.
Sidney can’t sing any more. He’s dead.

Isn’t that how this began?
Drops of still gin fizz, so sloe
They fell into our laps and covered
The little boy’s overalls with mud?
Fuck the rabbit hole. He hit the concrete.

Great forces won’t come to our aid.
They know better than to hide under our
Pillows while we sleep so they can swap stories
And return to their rightful owners in Bakersfield
Where you gagged my mouth so we could kick,
Kick, and kick again until the headboard fell.

He was with us in that abandoned apartment
Looking for something to make it home.
One eye pressed against a crack in the door
Surveying the vacant parking lot for
Whatever left him behind by mistake.

[back to the top]

Sedona

You asked me if I wanted you
and I did, so said I did,
me which you
I wanted, so I told you.

The you who looked at me
with stained glass eyes
under stained glass stars,
into strained black eyes
weighted down by glasses
broken under the rose colored
weight of a thousand petals
pressed into books we read
when we chose thorns over petals
and pricked our feet on thorn
after thorn after thorn, but drew
no blood because we were covered
with roses that shielded our feet
from shards of glass and kept
the pains from breaking our stride.

When we left the Cathedral Rock
you asked me if I loved you
and I did
so I asked if you loved me.

You said you loved
the water in my eyes
and the boat in my mind
that carried us across a sea
where took to the shore
and saw reflections of ourselves
walking over sandy rocks
Because you said I was your rock
when you need to be strong
and I was the white sand
when you need to be weak
so weeks won’t become months
of seclusion hidden in jars
in the cupboard next to jam
and pickles, and peaches.

We agreed that the boat
would carry us across the ocean
until some lighthouse lamp
hits the panes of a church window
and reflects off the water,
the glory of stained glass

[back to the top]


One Night Stand

A man in the corner catches my eye
He rejected me last month.
Coiffed admirers dangle from his every word.
Scenester bastards in skinny jeans.
Everyone who’s anyone is here tonight.
A festering pile of tweaked-out skanks.
It’s great when old friends get together again.
Heard Sam gave Ryan herpes.
Laser lights illuminate naked, nubile torsos.
I see you’re still snorting your inheritance.
Bodies pressed together in warm embraces
Your friend was much cuter.
Tongues intertwined for the very first time.
The acrid taste of liquor and cigarettes.
I wonder if he’s “the one”.
What the fuck is your name?
Fumbling hands unlock the apartment door
I went home with your neighbor last month
Hands gently caress soft cheeks
This apartment smells like cat piss.
Tender fingers trace down a shoulder and up a spine
If he has backne I’m leaving.
Two bodies fall gently onto clean linen sheets
Did I wear underwear tonight?
Tangled limbs move in unison to a single heartbeat.
Get your knee off my shin.
An arcane glimpse of the universe.  We’re decoding the secret.
Your moans sound like the loose timing belt on my car
He falls asleep, head resting gently on my chest
I like him better when he’s quiet
His slow breathing matches mine
God, he looks so peaceful.
I can feel his breath in the hair on my chest
That sort of tickles.
My eyes are getting heavy, but I can’t look away yet
I wonder if he goes home with a lot of guys
What does he thinks of me?
Am I special, or does this happen all the time?
Did he see me spill that drink earlier?
He’s talking in his sleep.
I hope I didn’t seem too drunk.
Damn, he has great skin.
Maybe I shouldn’t have tried to be witty.
Didn’t he say he liked Siouxsie?
I should have gotten a manicure.
I haven’t been this comfortable in a while.
Was my cologne too strong?
I like a guy with strong hands
Maybe we can get breakfast tomorrow morning.
Those eyes were pretty amazing
Where would I take him?
The clearest blue I’ve ever seen.
I’ll let him choose.



[back to the top]

Horses

I.
Before dawn she woke me
drove us to the race track
in the El Camino, 1976
with the windows down.
We parked behind the concession stand
so I could meet you
shortly after your first heart attack.

Asphalt pebbles shattered
under the weight of the well worn boots
that held you up.
You realized your mortality
and banished it to the ticket booth.
Place another wager.
Pray for a superfecta.

We sat and watched the horses run trials
with a stopwatch in my hand
held inside your hand.

II.
Again, I rode to meet you at the track
on a motorbike with blue trim,
bought with court-ordered money
you never sent

My leather jacket reeked of pot
your denim smelled of Maker’s Mark and cigarettes.
We sat together on the ground
pretending we had no senses

You hugged me in that parking lot.
I turned my head
towards an abandoned truck
run down, full of scrap metal
hoping you didn’t crush the joint in my breast pocket.

III.
My sister called at 7am
while I shaved for work
two weeks ago you died at last

I stared at my calloused hands, and thought of a child
leaving home in a starched white shirt
and black cotton trousers
running around a red dirt track
whipping red welts into pink skin
until a checkered flag signaled the end of the race.

[back to the top]

This Kiss is Unfinished

I don’t even smoke, but I will tonight.
sitting in the black vinyl passenger seat
as I laugh and wish I wasn’t there
listening to a Cocteau Twins tape he plays
because I said I liked it after he said hello
and I said hey and he bought me a drink
and offered me a smoke, and his eyes
slowly traced from the tip of my new heels,
up my stocking covered thighs.

When we get to his place I wonder why
men are so fucking clumsy with straps
and garters, why they always bite my lip
and softly pant in my ear “you like it, don’t you”
because this sort of thing should remain unspoken,
like the clock on his wall that moves in silence.

His hands moves across my breast and
I wonder why a blowjob is called a blowjob
because no one actually blows on anything.
We just move in and out of each other’s
lives and that’s the new handshake we learn
in charm school after they teach us how to hide
our text messages, and email accounts, and lists
of partners we’ve been with because the number
is too high and private and won’t get us laid
by a man we might want to marry one day.

When he sleeps, I look through his cabinets,
and his desk drawers, and his address book
next to his prescription for Dexedrine
and imagine the man back in Georgia
who makes my body crackle and hum
and accept the substitute sleeping next to me
and reach for the man I’m with
while the one I want
bounces through the sky like a positive charge
looking for my negative to make us whole again.

[back to the top]

The Sacking of Troy

I remember the moment
We abandoned solitude.
The moment we raised a flag
And Staked a claim
on the words we and us

Releasing two pasts
Beginning one future.

We were blessed by clergy
And paraded through a sea
of spectators and well wishers

But now we stand in the distance
watching the Troy we built
laying in smoldering ruins

Destroyed by six years
Spent casually tossing
Little Apples of discord
Like golden hand grenades
Back and forth, back and forth

They eventually have to explode.

[back to the top]

Justin Carter

Some of Justin Carter’s pieces are pending publication elsewhere, so he was not able to make them available here, but the titles of what he read are nonetheless included above.

[back to the top]

Kurt Lovelace

The last reader of the evening, Kurt Lovelace, read the following poems in the order that they appear here. Kurt addressed the audience, and his comments appear below in the green text.

"Hello, everyone, I am glad that you were all able to come out tonight. I'd like to make a few comments before I begin reading. Having just returned to school last year after a nearly 30 year career as a software engineer, I feel like a time traveler, being back where I was 30 years ago. I took Kevin Prufer's workshop along with Chris and Justin last semester, and so, it is a real privilege to be up here reading with my two classmates."

 

I'll begin with a few older poems written when I was in my early twenties, and I begin with these simply because they may be of interest in themselves and because they have never been heard by anyone before -- so it's a starting point in introducing you to my work, which now spans over 35 years. Then I will move on to my current work. The first of the three older pieces is called 'Taradiddle Smile' followed by 'Good Morning Captain Kangaroo' and concluded by 'Hunger' -- written at a time when I was perhaps too fond of John Ashbery, but they contain some fun and hopefully entertaining language in them."

Taradiddle Smile (#8 from Sewn Nets)

Dislocate that chagrin with a taradiddle smile
texturing into laughter. Realize that these tweed gearings
are success’s necessary dress, de rigueur
in the legato of getting ahead. You are commodity enough for your greed
rat-tailing through some echelon of employment, up-stepping
like a slinky down-steps. Your profit is
pragmatic redundancy, plus the intangibles of involvement:
no why for a house pregnant with family. Asking would
flabbergast you into a gypsy barreling over Niagara
for the gloat, thrill of it, a runaway reaction
like Caligula, claiming it made as much sense as
hiccups or Halloween, feeling your life like Sampson’s haircut, unfair,
yet you in fools-gold accord with its TV shine.

[back to the top]

Good Morning Captain Kangaroo

my eyes open
every day with the front page of the news
breakfasting with the voices of legislators

and in the inkdots turned into the semblance
of photos, their hard noses flash there in the cameras
where they laugh they smile they grin

their papers their briefcases their limousines
tuned and humning my taxes
but I say, we all say

it is necessary:
eggs in their cartons, bombs in their submarines
and we go on

flipping to the editorials that explain
everything.

[back to the top]

Hunger

Money,
a small quantity of it
floats in my pocket.

I pass a poor man on the street,
his mouth
open,
his belt about his waist
pulled tight.

His hand reaches out to me
shriveled. I pause.
Reaching into my pocket,
pulling out a dollar,
and leaning my mouth toward the man’s left ear
whisper, I wish you were a

woman.

[back to the top]

"Now, moving on to the present, all the pieces that follow were written in the last 12 months with the exception of Sculpting, a poem chosen for Aletheia that was, however, written sometime ago."

Put Some Relish on Your Plate, Pontus Pilate

I started out believing in everything:
the open field, plow in hand, horse
waiting to be worked, words
hedged in the furrow, irises open
to the moment of opening.

Perhaps I can ask you about it someday
and you’ll tell me everything I’ve ever wanted
was within reach, if only I would have put
out my hand, wide palms like bells ringing.

Say again, what?

Put your fears in a little box, and smoke it,
not this warm interrogatory weather we’ve been having
that no one really wants to talk about, that peels
shirts from bodies with an utter unconcern that’s neither
here nor there.

[back to the top]

Sculpting

The cost of involvement is you get involved and there she is
and your her painting garden her kitchen things on her desk at the office and
she’s looking how it’s all arranged
your colors the smell of your herbs
aren’t put away are your pencils
sharpened

then she sees
carrots need planting, the rhubarb
must go, suddenly
you need new dishes.

Then you start drunk serious writing poems about the cost of involvement
how her lips are not cherries but
red angry commandments painted in a delightful rouge
to elicit your obeisance

so softly
her requests patter
and when her such and such of such words fall
yawns lifts up its arms at her
smiling

she sculpts you

and one night reads your poems and thinks that they are very
pretty.

But you are drunk and serious
you keep the gun in the drawer.

[back to the top]

Time

My wife, who hasn’t touched me in months, asks
would I perhaps take the trash out today
before the blue-green shimmer of the peacocks
flight to roost high in the safe night trees?

I stick my right pinky into cold vodka
and stir. Smoky Kahlua swirls. Sticky,
I lift out, then suck my honeyed finger.
“A moment,” I tell her, “in a moment.”

[back to the top]

At Marfreley’s Bar in Houston, Texas

In a dim lit mural behind the bar,
two swans amble in front of a plantation:
its white house lies against the river, lonely

for the cover of more trees that the artist
left out, as the rushing river
empties into the dark dandelion breeze

of rewritten histories. And I had wanted to see
a single woman out, tonight, sitting
alone, like me at the bar, looking

at their life, the plantation, the swans swallowing
small sips of whatever they find in front
of themselves, any parts of a life that might

make sense, tell me I have done the right things.

[back to the top]

Blossoms in the Salt-Sand Waves

“Geswind, geswind, wir hilft dem Kind?”

1

Minding the green chain on our cockatoo,
my mother has coffee and oranges, spends
Sunday sitting in her sunny chair. Ripe fruit falls
from our plum bushes and banana trees, yet our boughs
hang heavy in the clearest blue. My father says:
“We’re here to track the rockets.” I am seven. Soon,
one man is going to walk upon the moon.
The beaches go on and on the water even more.
What about the man already in the moon?

As the Shipley brothers, and Buddy, and I
yank coral piled by the Shipley’s rusting Chevy
that hunkers, helpless in Bahamian sea-spray:
scorpions skedaddle, stick sticky, skitter or scatter
if we let them, but we leave them twitching.

Hammocked, I wake naked to the naked sun:
nose itching in salt-spray, head stuck out
the A-frame’s attic window. Sand-tufted plum ﬁelds
sway by seaweed bedraggled beaches, splashed
and resplashed and splashing in ambergris
waves that glint and pop with turquoise and white
bubbling froth the crabs scurry-up in, till waves pull back
leaving their wet-shaved arms on the shore
shiny, and smooth and new, invites us to play.

2

I eat hyacinths, their wet, red lips
ﬂopped or folded open, sticky witch’s doors:
my tongue feels the ridges of her ﬂoor,
unswept, gritty with the bones of children, before
I swallow them, then pocket three gleaming cat’s
eyes. I’ve won the dare of Buddy Bogus
the 3rd. His mother holds me by my hair

hanging, just off the ground, above the dirt road
that her paneled wagon had banged against
from Freeport, with ﬁve of us screaming. But when
I said “shit”, she slammed the car into its own dust,
stopping. She shook when she said: “We do not swear!”
That’s when she’d yanked me out the door,
ﬁsted my crew-cut, then lifted my brain
an astronaut, at T-minus zero, not counting,
pushed back by gravity: around me the hushed jungle
peed in it’s pants. But I sat on her hat
all the way home, naming the stars
just coming-on: Ursa Major, Andromeda,
Hydra, Cygnus, Draco, Vulpecula
poking through, their thin pinpricks of light
slow-moving against one fast satellite of ours.

3

My parents go to the Missile Base to dance
leaving me asleep. I wake up and run
breathless outside crying on sprinkled grass.
Back in, I pull out the TV’s boney on-switch:
a soda jerk on The Twilight Zone tips-up
his white hat: a third eye looks out.
Something scratches on the screen door.
I pull my hair under my mother’s milk sheets
and squeeze my eyes tight, and whisper:
“Make it go, make it go, make it go!” Asleep,
I fall into the same sticky hole, night
after night, I grab its edges but keep slipping
over into it only to slip over into it again.

Papaya grow with phosphorescent slugs
a breadcrumb’s throw behind the Blue Lagoon
Apartments where then we live, and two older boys
make me dance naked till I scream, pounding
through palm trees towards home, unable
to speak for a week. But once, I stole the night

pulling it tight like an enormous sheet
of black with dotted lights, and naked, swam
back into the sea from where I came;
and later sit on the shore with the storied moon,
wiggling my toes, squishy, in the midnight tides
pulling back drowned voices; I think I almost know
the sound of drowning.

4

Just in from Germany, my English played-out,
Dad tutors me, three months at the kitchen table.
I spell everything exactly as it sounds:
“Witch witch wood u bee?” At Saint Mary’s Star
Of the Sea, the nuns thought me dyslexic,
till someone told them I was bilingual
and could recite the Lords Prayer in Latin:
Pater noster, qui es in caelis, sanctiﬁcetur
nomen tuum.
It made the nuns ﬂutter, holding
white habits as if they might take ﬂight, be
the sea foam that ﬂoats inland on the wind
as at noon, they air their prayers, the angelus:
Et verbum caro factum est. Et habitavit in nobis.
(and the word, made ﬂesh, dwelt among us.)
And I kissed Eve, that morning’s milk break,
under stiff pines, the sea gulls shreeing, we ran
back, caught. Sister Anne ruled my knuckles raw,
beating their boney nubs on top her desk.

5

Dad floats a bright brochure at me: green eyes
burn in a panther’s face, peering out from a jungle
that fans its Stygian felt. “Let’s go,” he says,
and opens our white battled Ford. For half an hour
we bump the pebbled roads towards Freeport
to see a Brazilian emerald dealer in his shop
tucked away, in an alley of hallways going up
and down, around corners, and then two doors
both locked with slapping bolts, opened. He unrolls
black velvet in a curtained room, one bright light
shines down to show how black the velvet is. He
lays seven stones out, their rough edges “Uncut,”
he says, “from Santa Muerto,” and rolls them burning
in the blood between the tips of his ﬁngers.

(Stanza 6,7,8 left out at reading…)

9

What was it then? What is it now? Let’s ask,
what measurements for us? If we stretch out our arms
the edge of ocean along the sinking sun
seems a dimming thing, encompassed
by the milk of the visiting moon. We bounce
off of the porch and walk toward the beach.

A stick bug extends its manifold hand,
and boysenberries ripen under pricking cactus;
in-between driftwood, ashore, a hermit crab
discards its shell, and in the shallows a leopard ray
wiggles underneath the sand, its spotted wings.

## Elementary Binomial Proofs and Catalan Numbers

The work here is actual assigned homework from Dr. Mary Flagg’s Number Theory, Math 4383 – Section 19842, going on now at the University of Houston this Spring 2012 semester. This is from homework assignment 1. The problems are taken from Elementary Number Theory, Seventh Edition, by David. M. Burton.

However, I will be going beyond much of this homework by adding additional material as it strikes me as being relevant to the topic at hand.

The theorems of importance in Chapter One are the following: Well-Ordering Principle, Archimedean property, the Principle of Mathematical Induction (PMI), and the Binomial Theorem. All of these were introduced to me last semester by Professor Garret Etgen in his Analysis course, and again, by Professor Siemion Fajtlowicz in his abstract algebra course, and here they are yet again in Dr. Mary Flagg’s number theory — that is how utterly important and basic these concepts are that they deserve repeated introduction. For analysis, the well-ordering and Archimedean property are appealed to time and again when working with proofs.

Well-Ordering Principle Every nonempty set S of nonnegative integers contains a least element.

[proof pending, time permitting]

This principle is the key to proving the Archimedean property, which in turn is the key needed to prove the principle of mathematical induction. Therefore, these three are all conjoined concepts.

Theorem 1.1 Archimedean Property. If a and b are any positive integers, then there exists a positive integer n such that $\displaystyle na\ge b$.

[proof pending, time permitting]

Essentially, this is saying that if we have n of something, then there is always n+1 of them, a successor, if you will. Intuitively, this allows us to define infinity without ever really having to deal with it philosophically: that which is finite stops while that which is infinite continues beyond any one of its members, especially, there is no “last” one in an infinite set. Yet we never have to actually talk about “infinity” to mean infinite.

Theorem 1.2 First Principle of Mathematical Induction (PMI) Let S be a set of positive integers with the following properties:

(a) The integer 1 belongs to S.
(b) Whenever the integer k is in S, the next integer k+1 must also be in S.

Then S is the set of all positive integers.

[proof pending, time permitting]

As a technique with which to prove theorems, Mathematical induction was first demonstrated by Francesco Maurolyeus (1494-1575). It was heavily relied upon by Blaise Pascal (1623-1662) when he undertook his research into the binomial coefficients.

But there are actually three version of the PMI: the Principle of Mathematical Induction (PMI), the General Principle of Mathematical Induction (GPMI), and the Strong or Complete Principle of Mathematical Induction (SPMI). And there is also Transfinite Induction, just to be somewhat thorough. Most texts suffice with the PMI and SPMI. Are these divisions of the PMI necessary? Yes, for each serves its purpose when working with particular types of induction problems.

Perhaps many people, upon first seeing induction used, are shown rather trivial problems, and so feel that this is a trivial technique. Nothing could be further from the truth. But one must be shown non-trivial problems to appreciate why one would never consider leaving induction out of one’s mathematical toolkit. A small hint of its power glimmers in problem 1.2 #5(a) below, where the PMI is combined with other ideas in an effort to prove a statement. And it is in conjunction with other techniques that the utility and power of the PMI will be felt when going about proofs.

The Binomial Theorem

$\displaystyle {{(a+b)}^{n}}=\left( \begin{matrix}n \\o \\\end{matrix} \right){{a}^{n}}+\left( \begin{matrix}n \\1 \\\end{matrix} \right){{a}^{n-1}}b+\left( \begin{matrix}n \\2 \\\end{matrix} \right){{a}^{n-2}}{{b}^{2}}+...+\left( \begin{matrix}n \\n \\\end{matrix} \right){{b}^{n}}$

This is one of the main concepts of chapter 1, without a doubt. Taking Pascal’s Triangle, and going down the center, these coefficients are very important, and accordingly given the name Centeral Binomial Coefficients, because they appear everywhere in mathematics, but especially in combinatorics and number theory.

$\displaystyle {2n \choose n} = \frac{(2n)!}{(n!)^2}\text{ for all }n \geq 0$

where the first few values of this coefficient are:

$\displaystyle 1, 2, 6, 20, 70, 252, 924, 3432, 12870, 48620, ...$

Worked Problems

1.1 #2. If $\displaystyle r\ne 1$, show that for any positive integer n,

$\displaystyle a+ar+a{{r}^{2}}+a{{r}^{3}}+a{{r}^{4}}+...+a{{r}^{n-1}}+a{{r}^{n}}=\frac{a\left( {{r}^{n+1}}-1 \right)}{r-1}$

Proof. Using the PMI, Step 1. Let $\displaystyle n=1\in \mathbb{S}$. Then we have:

$\displaystyle a+ar=\frac{a\left( {{r}^{1+1}}-1 \right)}{r-1}=\frac{a\left( {{r}^{2}}-1 \right)}{r-1}=\frac{a\left( r+1 \right)\left( r-1 \right)}{r-1}=a\left( r+1 \right)=a+ar$

so that the formula is true for $\displaystyle 1\in \mathbb{S}$.

Step 2. Now, assume that the formula holds for $\displaystyle k\in \mathbb{S}$ so that:

$\displaystyle a+ar+a{{r}^{2}}+a{{r}^{3}}+a{{r}^{4}}+...+a{{r}^{k-1}}+a{{r}^{k}}=\frac{a\left( {{r}^{k+1}}-1 \right)}{r-1}$

Step 3. Then, for k+1 we have:

$\displaystyle a+ar+a{{r}^{2}}+a{{r}^{3}}+a{{r}^{4}}+...+a{{r}^{k-1}}+a{{r}^{k}}+a{{r}^{k+1}}=\frac{a\left( {{r}^{(k+1)+1}}-1 \right)}{r-1}$

and simplifying yields:

$\displaystyle a+ar+a{{r}^{2}}+a{{r}^{3}}+a{{r}^{4}}+...+a{{r}^{k-1}}+a{{r}^{k}}+a{{r}^{k+1}}=\frac{a\left( {{r}^{k+2}}-1 \right)}{r-1}$

but the LHS may be further simplified as:

$\displaystyle (a+ar+a{{r}^{2}}+a{{r}^{3}}+a{{r}^{4}}+...+a{{r}^{k-1}}+a{{r}^{k}})+a{{r}^{k+1}}$

$\displaystyle =\frac{a\left( {{r}^{k+1}}-1 \right)}{r-1}+\frac{a{{r}^{k+1}}(r-1)}{r-1}$

$\displaystyle =\frac{a\left( {{r}^{k+1}}-1 \right)+a{{r}^{k+1}}(r-1)}{r-1}=\frac{a{{r}^{k+1}}-a+a{{r}^{k+2}}-a{{r}^{k+1}}}{r-1}$

$\displaystyle =\frac{a(-1+{{r}^{k+2}})}{r-1}=\frac{-a+a{{r}^{k+2}}}{r-1}=\frac{a{{r}^{k+2}}-a}{r-1}$

$\displaystyle =\frac{a({{r}^{k+2}}-1)}{r-1}$

but this is the original RHS when we let n=k+2 . Therefore, by the PMI, we have that for all $\displaystyle n\in {{\mathbb{Z}}^{+}}$,

$\displaystyle a+ar+a{{r}^{2}}+a{{r}^{3}}+a{{r}^{4}}+...+a{{r}^{n-1}}+a{{r}^{n}}=\frac{a\left( {{r}^{n+1}}-1 \right)}{r-1}$

holds true. QED

1.1 #9. Establish the Bernoulli inequality: if $\displaystyle 1+a>0$, then

$\displaystyle {{\left( 1+a \right)}^{n}}\ge 1+na$

Proof. Using the PMI, we proceed as follows.

Step 1. Let n=1. Then we have:

$\displaystyle {{\left( 1+a \right)}^{1}}\ge 1+(1)a\Rightarrow {{(1+a)}^{{}}}\ge 1+a$

therefore it is true for n=1. Next,

Step 2. Assume it to be true for k.

$\displaystyle {{\left( 1+a \right)}^{k}}\ge 1+ka$

Step 3. For k+1, we have:

$\displaystyle {{\left( 1+a \right)}^{k+1}}\ge 1+(k+1)a$

or, since $\displaystyle 1+a>0$, we have that

$\displaystyle (1+a){{\left( 1+a \right)}^{k}}\ge (1+a)(1+ka)$

or

$\displaystyle {{\left( 1+a \right)}^{k+1}}\ge 1+a+ka+k{{a}^{2}}$

or

$\displaystyle {{\left( 1+a \right)}^{k+1}}\ge 1+(1+k)a+k{{a}^{2}}$

but

$\displaystyle 1+(1+k)a+k{{a}^{2}}\ge 1+(k+1)a$

because $\displaystyle k{{a}^{2}}>0$, we therefore also that

$\displaystyle {{\left( 1+a \right)}^{k+1}}\ge 1+(k+1)a$

but this is simply n=k+1. Therefore, by the PMI, we have that, when $\displaystyle 1+a>0$:

$\displaystyle {{\left( 1+a \right)}^{n}}\ge 1+na$

holds true for all $\displaystyle n\in {{\mathbb{Z}}^{+}}$. QED

Another interesting way to see this, without using induction, is to simply expand the LHS via the Binomial Theorem, and we get:

$\displaystyle {{(1+a)}^{n}}=\left( \begin{matrix}n \\n \\\end{matrix} \right)+\left( \begin{matrix}n \\n-1 \\\end{matrix} \right)a+\left( \begin{matrix}n \\n-2 \\\end{matrix} \right){{a}^{2}}+...+\left( \begin{matrix}n \ \\\end{matrix} \right){{a}^{n}}$

and from this it follows that:

$\displaystyle {{(1+a)}^{n}}=1+na+\frac{n(n-1){{a}^{2}}}{2}+...+{{a}^{n}}\ge 1+na$

and so the expanded LHS is certainly larger than the sum of its first two terms. Therefore,

$\displaystyle {{(1+a)}^{n}}\ge 1+na$

follows immediately. QED

1.2 #3(d). Derive the following identity:

$\displaystyle \left( \begin{matrix}n \\n \\\end{matrix}\right)+\left( \begin{matrix}n \\n-1 \\\end{matrix} \right)2+\left( \begin{matrix}n \\n-2 \\\end{matrix} \right){{2}^{2}}+...+\left( \begin{matrix}n \ \\\end{matrix} \right){{2}^{n}}={{3}^{n}}$

Proof. We may derive this directly from the binomial theorem:

$\displaystyle {{(a+b)}^{n}}=\left( \begin{matrix}n \\o \\\end{matrix} \right){{a}^{n}}+\left( \begin{matrix}n \\1 \\\end{matrix} \right){{a}^{n-1}}b+\left( \begin{matrix}n \\2 \\\end{matrix} \right){{a}^{n-2}}{{b}^{2}}+...+\left( \begin{matrix}n \\n \\\end{matrix} \right){{b}^{n}}$

by setting a=2, b=1 and reversing the order of terms, we get:

$\displaystyle {{(2+1)}^{n}}=\left( \begin{matrix}n \\n \\\end{matrix}\right)+\left( \begin{matrix}n \\n-1 \\\end{matrix} \right)2+\left( \begin{matrix}n \\n-2 \\\end{matrix} \right){{2}^{2}}+...+\left( \begin{matrix}n \ \\\end{matrix} \right){{2}^{n}}$

and combing terms and rearranging, the result immediately follows:

$\displaystyle {{3}^{n}}=\left( \begin{matrix}n \\n \\\end{matrix}\right)+\left( \begin{matrix}n \\n-1 \\\end{matrix} \right)2+\left( \begin{matrix}n \\n-2 \\\end{matrix} \right){{2}^{2}}+...+\left( \begin{matrix}n \ \\\end{matrix} \right){{2}^{n}}$

QED

1.2 #5(a) For $\displaystyle n\ge 2$ , prove that:

$\displaystyle \left(\begin{matrix}2 \\2 \\\end{matrix}\right)+\left(\begin{matrix}3 \\2 \\\end{matrix}\right)+\left( \begin{matrix}4 \\2 \\\end{matrix}\right)+...+\left(\begin{matrix}n \\2 \\\end{matrix}\right)=\left(\begin{matrix}n+1 \\3 \\\end{matrix} \right)$

Proof. Using the PMI, we proceed as follows.

Let $\displaystyle n=2\in \mathbb{S}$ (because n cannot be less than 2, by definition). Then we have:

$\displaystyle \left(\begin{matrix}2 \\2 \\\end{matrix}\right)=\left(\begin{matrix}2+1 \\3 \\\end{matrix} \right)$

or

$\displaystyle \left( \begin{matrix}2 \\2 \\\end{matrix}\right)=\left(\begin{matrix}3 \\3 \\\end{matrix} \right)$

which, when expended, gives:

$\displaystyle \frac{2!}{2!(2-2)!}=\frac{3!}{3!(3-3)!}$

which simplifies to:

$\displaystyle \frac{1*2}{1*2(0!)}=\frac{1*2*3}{1*2*3(0!)}$

which reduces to:

$\displaystyle 1=1$

and so the statement is true when n=1.

Now, assume that the statement is true for $\displaystyle k\in \mathbb{S}$

$\displaystyle \left(\begin{matrix}2 \\2 \\\end{matrix}\right)+\left(\begin{matrix}3 \\2 \\\end{matrix}\right)+\left(\begin{matrix}4 \\2 \\\end{matrix}\right)+...+\left(\begin{matrix}k \\2 \\\end{matrix}\right)=\left(\begin{matrix}k+1 \\3 \\\end{matrix} \right)$

Next, for k+1 we have:

$\displaystyle \left(\begin{matrix}2 \\2 \\\end{matrix}\right)+\left(\begin{matrix}3 \\2 \\\end{matrix}\right)+\left(\begin{matrix}4 \\2 \\\end{matrix}\right)+...+\left(\begin{matrix}(k+1) \\2 \\\end{matrix}\right)=\left(\begin{matrix}(k+1)+1 \\3 \\\end{matrix} \right)$

or more expansively:

$\displaystyle \left(\begin{matrix}2 \\2 \\\end{matrix}\right)+\left(\begin{matrix}3 \\2 \\\end{matrix}\right)+\left(\begin{matrix}4 \\2 \\\end{matrix}\right)+...+\left(\begin{matrix}k-1 \\2 \\\end{matrix}\right)+\left(\begin{matrix}k \\2 \\\end{matrix}\right)+\left(\begin{matrix}k+1 \\2 \\\end{matrix}\right)=\left(\begin{matrix}k+2 \\3 \\\end{matrix} \right)$

but, per our assumption that this formula holds for k, the first k terms on the LHS simply add up to:

$\displaystyle \left(\begin{matrix}2 \\2 \\\end{matrix}\right)+\left(\begin{matrix}3 \\2 \\\end{matrix}\right)+\left(\begin{matrix}4 \\2 \\\end{matrix}\right)+...+\left(\begin{matrix}k \\2 \\\end{matrix}\right)=\left(\begin{matrix}k+1 \\3 \\\end{matrix} \right)$

and so, substituting, we have:

$\displaystyle \left(\begin{matrix}k+1 \\3 \\\end{matrix}\right)+\left(\begin{matrix}k+1 \\2 \\\end{matrix}\right)=\left(\begin{matrix}k+2 \\3 \\\end{matrix} \right)$

or, rearranged:

$\displaystyle \left(\begin{matrix}k+1 \\2 \\\end{matrix}\right)+\left(\begin{matrix}k+1 \\3 \\\end{matrix}\right)=\left(\begin{matrix}k+2 \\3 \\\end{matrix} \right)$

But, using Pascal’s Rule that:

$\displaystyle \left(\begin{matrix}a \\b \\\end{matrix}\right)+\left(\begin{matrix}a \\b-1 \\\end{matrix}\right)=\left(\begin{matrix}a+1 \\b \\\end{matrix} \right)$

and letting b=3, a=k+1, we have:

$\displaystyle \left(\begin{matrix}k+1 \\2 \\\end{matrix}\right)+\left(\begin{matrix}k+1 \\3 \\\end{matrix}\right)=\left(\begin{matrix}k+2 \\3 \\\end{matrix} \right)$

but this is the identity we just worked out. Also, this is simply our original identity when k=n-1 or n=k+1.

Therefore, by the PMI, we have that

$\displaystyle \left(\begin{matrix}2 \\2 \\\end{matrix}\right)+\left(\begin{matrix}3 \\2 \\\end{matrix}\right)+\left(\begin{matrix}4 \\2 \\\end{matrix}\right)+...+\left(\begin{matrix}n \\2 \\\end{matrix}\right)=\left(\begin{matrix}n+1 \\3 \\\end{matrix}\right)$

is true of all values of $\displaystyle n\in {{\mathbb{Z}}^{+}}$ . QED

1.3 #7. For $\displaystyle n\ge 1$ , verify that:

$\displaystyle {{1}^{2}}+{{3}^{2}}+{{5}^{2}}+...+{{(2n-1)}^{2}}=\left(\begin{matrix}2n+1 \\3 \\\end{matrix} \right)$

Proof. Using the PMI, we proceed as follows.

Let $\displaystyle n=1\in \mathbb{S}$ . Then we have:

$\displaystyle {{1}^{2}}=\left(\begin{matrix}2(1)+1 \\3 \\\end{matrix} \right)$

or

$\displaystyle {{1}^{2}}=\left(\begin{matrix}3 \\3 \\\end{matrix} \right)$

which expands to:

$\displaystyle 1=\frac{3!}{3!(3-3)!}=\frac{3!}{3!0!}=\frac{3!}{3!}=1$

and so it is true for $\displaystyle n=1\in \mathbb{S}$ .

Assume it true for k so that:

$\displaystyle {{1}^{2}}+{{3}^{2}}+{{5}^{2}}+...+{{(2k-1)}^{2}}=\left(\begin{matrix}2k+1 \\3 \\\end{matrix} \right)$

is true. Now, for k+1 we have

$\displaystyle {{1}^{2}}+{{3}^{2}}+{{5}^{2}}+...+{{(2(k+1)-1)}^{2}}=\left(\begin{matrix}2(k+1)+1 \\3 \\\end{matrix} \right)$

or

$\displaystyle {{1}^{2}}+{{3}^{2}}+{{5}^{2}}+...+{{(2k+2-1)}^{2}}=\left(\begin{matrix}(2k+2+1) \\3 \\\end{matrix} \right)$

or

$\displaystyle {{1}^{2}}+{{3}^{2}}+{{5}^{2}}+...+{{(2k+1)}^{2}}=\left(\begin{matrix}2k+3 \\3 \\\end{matrix} \right)$

but this is simply the same as for k, when we set n=k+1. Therefor, we have that

$\displaystyle {{1}^{2}}+{{3}^{2}}+{{5}^{2}}+...+{{(2n-1)}^{2}}=\left(\begin{matrix}2n+1 \\3 \\\end{matrix}\right)$

is true for all $\displaystyle n\in {{\mathbb{Z}}^{+}}$ . QED

1.2 #10. The Catalan numbers, defined by

$\displaystyle {{C}_{n}}=\frac{1}{n+1}\left( \begin{matrix} 2n\\n\\\end{matrix}\right)=\frac{(2n)!}{n!(n+1)!}$

for $\displaystyle n=1,2,3,...$ so that they form the sequence:

$\displaystyle 1, 1, 2, 5, 14, 42, 132, 429,1 430, 4862, 16796...$ et cetera

For $\displaystyle n\ge 1$, prove that $\displaystyle {{C}_{n}}$, the $\displaystyle {{n}^{th}}$ Catalan number, can be given inductively by

$\displaystyle {{C}_{n}}=\frac{2(2n-1)}{n+1}{{C}_{n-1}}$

Proof. Using the PMI, we proceed as follows:

Step 1. Let n=1. And we have

$\displaystyle {{C}_{1}}=\frac{2(2(1)-1)}{1+1}{{C}_{1-1}}$

therefore, it is true for and

$\displaystyle {{C}_{1}}=\frac{2}{2}{{C}_{0}}={{C}_{0}}$

But $\displaystyle {{C}_{0}}=1$ by definition, and so $\displaystyle {{C}_{1}}=1$

Step 2. Assume the formula is true for k such that:

$\displaystyle {{C}_{k}}=\frac{2(2k-1)}{k+1}{{C}_{k-1}}$

is true.

Step 3. Now, for k+1 we have:

$\displaystyle {{C}_{k+1}}=\frac{2(2(k+1)-1)}{(k+1)+1}{{C}_{(k+1)-1}}$

or

$\displaystyle {{C}_{k+1}}=\frac{2(2k+2-1)}{k+2}{{C}_{k}}$

$\displaystyle {{C}_{k+1}}=\frac{2(2k+1)}{k+2}{{C}_{k}}$

but this is just our first formula when n=k+1. Therefore, for any

$\displaystyle {{C}_{n}}=\frac{2(2n-1)}{n+1}{{C}_{n-1}}$

holds true for any $\displaystyle n\in {{\mathbb{Z}}^{+}}$. QED

Now, we may also establish this result, namely that:

$\displaystyle {{C}_{n}}=\frac{2(2n-1)}{n+1}{{C}_{n-1}}$

directly, because it is a recurrence relation, using a little algebra, like this:

$\displaystyle {{C}_{n}}=\frac{4n-2}{n+1}{{C}_{n-1}}$

$\displaystyle =\frac{(4n-2)(4n-6)}{(n+1)n}{{C}_{n-2}}$

$\displaystyle =\frac{(4n-2)(4n-6)(4n-10)}{(n+1)n(n-1)}{{C}_{n-3}}$
. . . . .
. . . . .

$\displaystyle =\frac{(4n-2)(4n-6)(4n-10)...6\cdot 2}{(n+1)n(n-1)\cdot ...\cdot 3\cdot 2}{{C}_{0}}$

$\displaystyle =\frac{(2n-1)(2n-3)(2n-5)...3\cdot 1}{(n+1)!}\cdot {{2}^{n}}$

$\displaystyle =\frac{{{2}^{n}}(2n)!}{{{2}^{n}}n!(n+1)!}$

$\displaystyle =\frac{(2n)!}{(n+1)!n!}$

$\displaystyle =\frac{1}{n+1}\left(\begin{matrix}2n \\n \\\end{matrix} \right)$

and the result is again established. QED

One question immediately arises from this proof. Notice that from:

$\displaystyle {{C}_{n}}=\frac{2(2n-1)}{n+1}{{C}_{n-1}}$

we have immediately that:

$\displaystyle \frac{{{C}_{n}}}{{{C}_{n-1}}}=\frac{2(2n-1)}{n+1}$

and so it is natural to ask what the value of this ratio might be in the limit, especially, what does:

$\displaystyle \underset{n\to \infty }{\mathop{\lim }}\,\frac{{{C}_{n}}}{{{C}_{n-1}}}=\underset{n\to \infty }{\mathop{\lim }}\,\frac{2(2n-1)}{n+1}$

equal in the limit? Calculating this directly, we have:

$\displaystyle \underset{n\to \infty }{\mathop{\lim }}\,\frac{2(2n-1)}{n+1} \\=\underset{n\to \infty }{\mathop{\lim }}\,\frac{4n-2}{n+1} \\ =\underset{n\to \infty }{\mathop{\lim }}\,\frac{4n}{n+1}-\underset{n\to \infty }{\mathop{\lim }}\,\frac{2}{n+1} \\ =\underset{n\to \infty }{\mathop{\lim }}\,\frac{\frac{4n}{n}}{\frac{n}{n}+\frac{1}{n}}-\underset{n\to \infty }{\mathop{\lim }}\,\frac{\frac{2}{n}}{\frac{n}{n}+\frac{1}{n}} \\=\underset{n\to \infty }{\mathop{\lim }}\,\frac{4}{1+\frac{1}{n}}-\underset{n\to \infty }{\mathop{\lim }}\,\frac{2}{n+1} \\ =\underset{n\to \infty }{\mathop{4\lim }}\,\frac{1}{1+\frac{1}{n}}-2\underset{n\to \infty }{\mathop{\lim }}\,\frac{1}{n+1}$

But this limit further reduces to:

$\displaystyle 4\frac{1}{1+\underset{n\to \infty }{\mathop{\lim }}\,\frac{1}{n}}-2\frac{1}{\underset{n\to \infty }{\mathop{\lim }}\,\left( n+1 \right)}$

and because we have that:

$\displaystyle \underset{n\to \infty }{\mathop{\lim }}\,\frac{1}{n}=0$ and $\displaystyle \underset{n\to \infty }{\mathop{\lim }}\,\left( n+1 \right)=\infty$

therefore:

$\displaystyle 4\frac{1}{1+\underset{n\to \infty }{\mathop{\lim }}\,\frac{1}{n}}-2\frac{1}{\underset{n\to \infty }{\mathop{\lim }}\,\left( n+1 \right)}$

= 4(1) – 2(0) = 4

and so we have, finally, that:

$\displaystyle \underset{n\to \infty }{\mathop{\lim }}\,\frac{2(2n-1)}{n+1}=4$

and therefore, we have established that:

Lemma. The ratio of the nth Catalan number to the (n-1)th Catalan number equals 4 as n approaches infinity.

$\displaystyle \underset{n\to \infty }{\mathop{\lim }}\,\frac{{{C}_{n}}}{{{C}_{n-1}}}=4$

This also means that, for sufficiently large values of n:

$\displaystyle {{C}_{n}}\approx 4{{C}_{n-1}}$

Now, the properties for the Catalan numbers just go on and on, but here is a beautiful identity between the integer sequence of Catalan numbers and functions. This also provides the merest glimpse into the powerful techniques of analytic number theory.

There is an extension of the factorial function, called the gamma function, defined as:

$\displaystyle \Gamma (z)=\int\limits_{0}^{\infty }{{{t}^{z-1}}{{e}^{-t}}dt}$

where z is a complex variable whose real part is positive. Now, integration by parts will yield:

$\displaystyle \Gamma (z)=(z-1)\Gamma (z-1)$

and when z is an integer, we get

$\displaystyle \Gamma (n)=(n-1)!$

But the Gamma function gives values for non-integral n, so that we have, by Euler’s reflection formula that:

$\displaystyle \Gamma (1/2)=\sqrt{\pi }$

Now, treating $\displaystyle \Gamma (z)=(z-1)\Gamma (z-1)$ as a recurrence relation, we can substitute and get:

$\displaystyle \Gamma (n+\frac{1}{2})=(n-\frac{1}{2})\Gamma (n-\frac{1}{2})$

$\displaystyle =(n-\frac{1}{2})(n-\frac{3}{2})\Gamma (n-\frac{3}{2})$

$\displaystyle =(n-\frac{1}{2})(n-\frac{3}{2})...(n-\frac{2n-1}{2})\Gamma (\frac{1}{2})$

$\displaystyle =\frac{1\cdot 3\cdot 5...(2n-1)}{{{2}^{n}}}\sqrt{\pi }$

$\displaystyle =\frac{(2n)!}{{{4}^{n}}n!}\sqrt{\pi }$

this give us:

$\displaystyle \frac{\Gamma (n+\frac{1}{2})}{\Gamma (n+2)}=\frac{(2n)!}{{{4}^{n}}n!(n+1)!}\sqrt{\pi }=\frac{{{C}_{n}}}{{{4}^{n}}}\sqrt{\pi }$

and so, rearranging terms, we have established that:

The nth Catalan number may be expressed in terms of the Gamma function as:

$\displaystyle {{C}_{n}}=\frac{{{4}^{n}}\Gamma (n+\frac{1}{2})}{\sqrt{\pi }\Gamma (n+2)}$

Wednesday 25 January 2012

## Human Pitch Perception Follows a GCD Formula

Given two integers n and m, their Greatest Common Divisor or GCD is defined as the largest number that divides into both n and m. So, given 6 and 35, for example, we have that the GCD(6,35) = (2·3,5·7) = 1, and likewise, the GCD of 121 and 44, or GCD(121,44) = GCD(11·11,4·11)= 11 because 11 is the largest number that divides into both 121 and 44.

But there is a very unexpected application of the GCD going on every second inside our own heads, as Manfred Schroder* goes on to say:

“An interesting and most surprising application of the GCD occurs in human perception of pitch: the brain, upon being presented with a set of harmonically related frequencies, will perceive the GCD of these frequencies as the pitch. Thus, the subjective pitch of the two-tone chord (320 Hz and 560 Hz) is (320,560) = 80Hz, and not the difference frequency (240 Hz).

Upon a frequency shift of +5Hz applied to both frequencies, the GCD drops to 5 Hz; and for an irrational frequency shift, the GCD even drops to 0 Hz. But that is not what the ear perceives as the pitch. Rather it tries to find a close match in the range of pitches above 50 Hz. For the frequencies 325 Hz and 565 Hz such a match is given by 81 Hz, which is the GCD of 324 Hz and 567 Hz – close to the two given frequencies.

Note that the concept that pitch is given by the difference frequency or “beat” frequency has been beaten: if both frequencies are shifted by the same amount, their difference remains unchanged. Yet psycho-acoustic experiments clearly show that the perceived pitch is increased, from 80 Hz to about 81 Hz in our example, just as the amplified GCD model predicts.

What this tells us is that the human brain switches on something like a GCD spectral matching computer program when listening to tone complexes. Fascinating? Indeed. Unbelievable? Well, the brain has been caught doing much trickier things than that.”

[ Technical Notes ]

The GCD appears in the solution to many, seemingly unrelated, problems. For example, take n jugs with capacities of L1, L2, . . . , Ln liters. What amounts k of water (or wine) can be dispensed by these n/1 jugs?

Answer: k must be a multiple of the GCD. Now, to better understand the GCD and its counterpart, the LCM, we will need more math.

Fundamental theorem of arithmetic. Each natural number n > 1 is either a prime or can be uniquely factored into primes

$n=p_{1}^{{{e}_{1}}}p_{2}^{{{e}_{2}}}p_{3}^{{{e}_{3}}}...p_{k}^{{{e}_{k}}}...p_{r}^{{{e}_{r}}}=\prod\limits_{i}{p_{i}^{{{e}_{i}}}}$

where the order of the prime factors makes no difference.

Proof. There are only two cases to consider. Either n is prime or n is composite. If n is prime, then the theorem is obviously true, by definition. Therefore, the only case we need to consider is when n is composite.

If n is composite, then there exists an integer p where p divides into n so that and 1 < p < n must be true because n is, by definition, greater than 1, and so if p divides into n, then p must be smaller than n, hence 1 < p < n as just stated. [this proof is still being written, and will be completed by the Jan 25 weekend]

It is extremely relevant to note that because there is no corresponding theorem for the additive decomposition of natural numbers into primes, this lack explains why additive number theory, when dealing with things like partitions, is so difficult.

Now, two integers n and m have a least common multiple (LCM) [n,m], and we need this every time we want to add two fractions, because we then need to find the LCM to combine two fractions with denominators n and m into a single fraction, and that is where the expression least common denominator comes from.

So, the LCM of 6 and 9 is LCM[6,9] = 18 so that:

$\frac{1}{6}+\frac{2}{9}=\frac{3}{18}+\frac{4}{18}=\frac{7}{18}$

So that we have, in general:

Definition. The Lowest Common Multiple or LCM of two integers n and m is defined as:

${}[n,m]=\prod\limits_{i}{p_{i}^{\max ({{e}_{i}},{{f}_{i}})}}$

and likewise, given two integers, we have:

Definition. the Greatest Common Divisor or GDC is defined as:

${}(n,m)=\prod\limits_{i}{p_{i}^{\min ({{e}_{i}},{{f}_{i}})}}$

and there are interesting properties between the GDC and LCM, such as that, for any two numbers n and m, the product of the GCD and the LCM equals the
product of n and m.

$(n,m)[n,m]=nm$

because whenever the GCD picks the exponent e of i for p of i, the LCM picks the exponent f of i, and vice versa and so:

$(n,m)[n,m]=\prod\limits_{i}{p_{i}^{{{e}_{i}}+{{f}_{i}}}=nm}$

and this works for three or more integers as well

$(n,m,k)[n,m,k]=nmk$

$(n,m,k,j)[n,m,k,j]=nmkj$

$(n,m,k,j,l)[n,m,k,j,l]=nmkjl$

Also, the direct result of the Min and Max functions in the definition of the GCD and LCD yields a “distributive law”

$(k[n,m])=[(k,n),(k,m)]$

$[k(n,m)]=([k,n],[k,m])$

And a beautiful “self-duel” relationship

$([k,n],[k,m],[n,m])=[(k,n),(k,m),(n,m)]$

Tuesday 17 January 2012