Scratch

In scant moonlight with gray rhinoceros skin
I look at your aging hands, hard

with fleshy nubs like my own withered being
as you tell me you love me for no

particular reason, the lazy midnight breeze
wiggling the curtains like our flown child

slipping between them, darting, at play,
as a long branch, night’s leafiness, shakes

your body rises and falls, bobs

like a slow swell of calm deep ocean, all
I can think about is wanting to pummel you

Brass

I was looking out the window as you spoke

the rouge on your lips turning a ruddy

kept looking beyond where you spoke of
at some other version or vision of this life

where we all do what we say we’ll do
where things work out, but not here, not now,

this version of life where you maintain a gun
with cleaning brushes made of metal parts

well-oiled into which you push the bullets
into the assembled spring clip ready to fire.

Extras

Whenever John Wayne come out of his trailer
thinking to kick some underpaid stunt-man’s ass,
I held my breath, and watched his hands swing back

and forth, each swing just missing the cranium
of some young over-eager talent, ducking
as John’s fists made heedless contact. I worked in legal,

kept the ink in line, avoided
unnecessary confrontation, pushed back
wherever I had too, to keep the lines

lined up, of women, alcohol, drugs that came
with John’s pasty morning under-breath. Here now,
he tries to swallow something of the night before, scratches

his big ass as he lights-up his morning Marlboro, places
a call to services for fresh roasted coffee, stumbles
out shirtless onto Dodge City to check out

the crisp uniform ironed California weather.

Poetry cannot be translated. So too, other than for giving a reader the raw idea of what is being said, any literal translation is especially negligible. The translator must be someone capable of writing decent if not inspired English poetry, whatever that might mean. Therefore, if one does attempt the translation of a poem, it must be ruthless, a culling from the bloody heart of both tongues. In other words, one may only create a poem in the target language that is its own poem with echoes, distortions, and intentions pointing to those places that the original also points out. So, that being said, here are three of my favorite poems from the Spanish, German, and French by Neruda, Rilke and Prevert, respectively.

These translations are very much, in an effort of love and intellect, an attempt to convey the beauty, wordplay and sound-play in the originals — and this explains some of my  perhaps more daring  “choices” — first person tense, ellipses, metaphor shifts, occasional sound emphasis over word sense — choices I prefer to call “intelligently risky”  as they are collectively my attempts to “transmogrify” these lovely poems into some semblance of a worthy English simulacrum.  Caveat emptor!

Árbol

Anoche al apagar la luz
se me durmieron las raíces
y se me quedaron los ojos
hasta que, tarde, con la sombra
se me cayó una rama al sueño
y por el tronco me subió
la fría noche de cristal
como una iguana transparente.
Entonces me quedé dormido.
Cerré los ojos y las hojas.
Pablo Neruda

Tree

Last night, putting the light
out, my deep roots slept
but my eyes strayed, open
tangled in between leaves
of a branch fell over my dream
and I rose up into the trunk
of the cold night, a crystal
transparent iguana.

I slept soundly then.

I closed my eyes and my leaves.

translated by Kurt Lovelace,

Herbsttag

Herr: Es ist Zeit. Der Sommer war sehr groß.
Leg deinen Schatten auf die Sonnenuhren,
und auf den Fluren laß die Winde los.

Befiehl den letzten Früchten voll zu sein;
gieb ihnen noch zwei südlichere Tage,
dränge sie zur Vollendung hin und jage
die letzte Süße in den schweren Wein.

Wer jetzt kein Haus hat, baut sich keines mehr.
Wer jetzt allein ist, wird es lange bleiben,
wird wachen, lesen, lange Briefe schreiben
und wird in den Aleen hin und her
unruhig wandern, wenn die Blätter treiben

Rainer Maria Rilke

Fall Day

God! Its about time! Summer was so fat.
Now shadows drag over the sundials,
and in meadows the wind rips loose!

Oh, let our last fruits fatten into fullness;
give us just two ripe sun-drenched days
plumping all into ripeness till hither and thither
the last sweet drops drain into swarthy wine.

Whoever has no house, you will not build it now.
If you are alone, it will be for a long time,
you will stay awake, reading, writing long letters
as you walk alone, shuffling, here and there,
disturbed, wandering where the leaves tremble.

translated by Kurt Lovelace,

Déjeuner du matin

Il a mis le café
Dans la tasse
Il a mis le lait
Dans la tasse de café
Il a mis le sucre
Dans le café au lait
Avec la petite cuiller
Il a tourné
Il a bu le café au lait
Et il a reposé la tasse
Sans me parler
Il a allumé
Une cigarette
Il a fait des ronds
Avec la fumée
Il a mis les cendres
Dans le cendrier
Sans me parler
Sans me regarder
Il s’est levé
Il a mis
Son chapeau sur sa tête
Il a mis
Son manteau de pluie
Parce qu’il pleuvait
Et il est parti
Sous la pluie
Sans une parole
Sans me regarder
Et moi j’ai pris
Ma tête dans ma main
Et j’ai pleuré.

Jacques Prevert

Breakfast at the Dinner

He pours coffee
into the cup.
He pours milk
into the cup of coffee.
He sprinkles sugar
atop the café au lait,
and with a little spoon
stirs it round.
He finishes his café au lait.
He reposes cup in saucer.
Not one word spoken,
he lights up
a cigarette.
He blows round
smoke rings.
He taps ash
into the ashtray.
Never speaking to me,
never regarding me,
throws on his coat
because rain is splashing down
pouring into puddles
as he leaves me,
turning into the splashing
rain, never speaking
nor regarding me once.
And I, eyes
splashing into the ground
of my hands,
cry.

translation by Kurt Lovelace

I am readying myself for the GRE math subject exam in the late Spring, and therefore reviewing all four years of undergraduate mathematics at this time.

In what follows, I will be summarizing every major area of undergraduate mathematics, as follows:

1. Geometry: Plane, Elliptic, Hyperbolic, and Affine
2. Linear Algebra
3. Vector Analysis
4. Real Analysis
5. Complex Analysis
6. Topology
7. Ordinary Differential Equations
8. Fourier Analysis, Lebesgue Integration and General Transform Theory
9. Probability Theory
10. Abstract Algebra
11. Graph Theory
12. Combinatorics and Algorithmic Complexity
13. Set Theory and Transfinite Arithmetic
14. Basic & Analytic Number Theory
15. Partial Differential Equations
16. Differential Geometry

If you are a student of any subject, then I hope you have already asked yourself at times the question “What does all of this mean? What is it for?” if you are as I am, a mathematics major, then I believe that this question is particularly important. For one can too often get lost in the forest, standing amid the numberless trees, each one a bit different from its neighbors yet all oddly familiar, somehow similar, like wondering through a waking dream.

This is neither an idle nor a superfluous question. Call it “the big picture.” Call it what you will. It is important to know the gist and the connections between different areas of ones subject, and to know each area for what it really is about.

———————————————————————————————————————————-
Linear Algebra

Let’s look at linear algebra. The matrix is the lingua franca tool of linear algebra, and so linear algebra is the study of vector spaces and their transformations using matrices. After a first course, one should know the axioms that define a vector space, the algebra of matrices, how to express the structure of vector spaces using matrices, and especially how, given the basis of a vector space, to represent any transformation of that vector space using a matrix, and how to use and calculate eigenvalues and eigenvectors. Lastly, the key theorem of linear algebra is to know the 8 distinct conditions that each alone can guarantee a matrix is inevitable. And that is it, the heart of an entire semester of undergraduate linear algebra summarized in one paragraph. Again, in a nutshell: basic linear algebra is the study of the transformation of vector spaces into one another and understanding equivalent conditions under which a matrix is invertible.

What is linear algebra used for? Everything, and almost everywhere, is the short answer. Anytime you seek a first approximation to some problem, it is likely that you will be using linear algebra. In graph theory matrices are used to represent a graph’s structure in a precise and concise manner. In abstract algebra, matrices are used in the representation of groups and other algebraic structures. And linear algebra comes up in both ordinary and partial differential equations, differential geometry, knot theory, number theory, and almost everywhere else. Learn it well, know it well if you are going to be doing research in pure or applied mathematics.

If one takes a fourth year, second semester of linear algebra, often considered “part 2″ of linear algebra studies, then one will likely encounter — inner product spaces, direct sums of subspaces, primary decomposition, reduction to triangular and Jordan forms, both rational and classical forms, dual spaces, orthogonal direct sums, bilinear and quadratic forms, and real normality — among the main topics.

Here are some great free full textbooks to download for reference or study:

Linear Algebra by Jim Hefferon. 499 pages. [direct link to whole book.]

Linear Algebra. David Cherney, Tom Denton & Andrew Waldron. 410 pages. [direct link to whole book]

## Euler’s Characteristic Formula V-E+F = 2

How is it that for thousands of years the best minds in mathematics did not see the fundamental relationship that, in any regular polyhedron, the sum of the vertices and faces minus the edges equals two? Although this question is interesting, no attempt will be made to answer it. Yet the question, merely by being asked, serves to highlight the tremendous stature of Leonard Euler.

Euler worked from first principles, digging into a topic by performing calculations to get a feel for the shape and edges of a problem, then developed conjectures and proofs based on such research. And so, Euler must have tabulated the edges, faces and vertices of shapes such as the platonic solids to thereby notice this relationship. Perhaps it took an almost childlike playfulness to discover this relationship. Yet it is all speculation. The only fact is that Euler did discover that $V-E+F=2$ where V, E, and F are, respectively, the vertices, edges and faces of a regular polyhedron

I first learned of Euler’s formula in a senior course on graph theory taught by the Polish graph theorist Dr. Siemion Fajtlowicz. Therefore, let me provide a few definitions before offering a compact proof that $V-E+F=2$ using basic graph theoretical methods.

Definition. A graph consists of a non-empty set of vertices and a set of edges, possibly empty. If an edge E exists, then it will be related to an unordered pair (a,b) of vertices in V. We may write $G=(\{V\},\{E\})$ to denote the graph.

A graph is finite if both the vertex set and edge set are finite. A graph that is not finite is infinite. The size of a graph is the number of vertices. The order of a graph is the number of edges. All graphs discussed in this article are finite.

Immediately note that if we are given one edge, then there exist two vertices — because an edge must connect to something and that something will always be a vertex. Two vertices are incident if they share a common edge and said to be adjacent. An edge with identical ends is called a loop while an edge with distinct ends is called a link. A graph is simple if it has no loops.

The degree $d(v)$ of a vertex in a graph G is equal to the number of edges in G incident with v where each loop counts as two edges. Thus, a vertex with two edges has degree 2 because the degree of the other two vertices would be one each, and so the sum of the degrees of all the vertices would be 4. From this we have immediately the following two theorems.

Theorem 1. The sum of the degree of the vertices of a graph equals twice the number of edges. That is

$\displaystyle \sum\limits_{i/G}{d({{v}_{i}})}=2e$

proof. If a graph has no edges, then e=0 and the theorem is true because the sum of the degree of the vertices of a graph with no edges must, by definition, be zero. If a given vertex has an edge, then there must be a second vertex connected to the first vertex by the given edge and so the sum of the degree of the vertexes will be 2, even if the edge were a loop beginning and returning to a single vertex the degree of that vertex due to the loop would still be 2.

Now, each additional edge added to the graph will increase either the degree of the vertex it is connect to and add one additional vertex or else it will add one degree each to two vertices that already exist. Thus, each time an edge is added, the degree count of the vertices increases by 2. Therefore, the sum of the degree of all the vertices will always be simply twice the number of edges present.

Theorem 1.1 The number of vertices in a graph of odd degree is even.

proof. Let ${{v}_{1}},{{v}_{2}}$ be sets of vertices where the ${{v}_{1}}$ is of odd degree and ${{v}_{2}}$ is of even degree. Then, from Theorem 1, we must have that

$\sum\limits_{i/G}{d({{v}_{1}})}+\sum\limits_{i/G}{d({{v}_{2}})}=\sum\limits_{i/G}{d(v)}$

but we have already established that

$\sum\limits_{i/G}{d({{v}_{i}})}=2e$

and therefore we must have

$\sum\limits_{i/G}{d({{v}_{1}})}+\sum\limits_{i/G}{d({{v}_{2}})}=2e$

$\sum\limits_{i/G}{d({{v}_{1}})}=2e-\sum\limits_{i/G}{d({{v}_{2}})}$

but

$\sum\limits_{i/G}{d({{v}_{2}})}=2{{e}_{2}}$

so

$\sum\limits_{i/G}{d({{v}_{1}})}=2e-2{{e}_{2}}=2(e-{{e}_{2}})=2{{e}_{1}}$

is even. Thus, we have that the sum of the vertices in a graph of odd degree is even. Now, we will need the following definitions to proceed.

Definition. A cycle is a closed chain of edges. A connected graph that contains no cycles is a tree.

Definition. A spanning tree of a graph G is one that uses every vertex of G but not all of the edges of G.

Every connected graph G contains a spanning tree T as a subgraph of G.

Definition. A planer graph is one that can be drawn in the plane without crossing any edges.

Definition. A face in the plane consists of both unbounded and bounded regions.

The last definition allows us to say that the number of “faces” of a finite line segment in the plane is 1, but that the number of faces of an infinite line is 2, one for each side that the line divides the plane into, and that the number of faces of a circle in the plane is 2, one corresponding to the inside and the other to the outside of the circle one being the unbounded and the other the bounded region.

Now we are ready to prove Euler’s formula as it may be stated in graph theory.

Theorem 2. If G is a connected planer graph with vertices v, edges e, and faces f, then

$\displaystyle v-e+f=2$

proof. Let T be a spanning tree of a graph G. Then the number of faces f=1 and the number of edges e= v – 1 is true for the spanning tree T of G and so we have $v-(v+1)+(1)=2$ and our formula is true. Now, G may be constructed from T by adding edges to T, but each time we do so we are adding a new face to T. Therefore, with the addition of each new edge, e will increase by 1 and f will increase by 1. Therefore, all of these additions cancel out and we have our formula.

Now, a homomorphism exists between polyhedron and graphs in that a connected plane graph can be uniquely associated with a polyhedron by making any face the flat unbounded part of the plane. Therefore, Euler’s formula is true for polyhedron. We can therefore immediately prove:

Theorem 3. Exactly five platonic solids exist.

proof. Let the number of edges and faces be n and the number of edges each vertex is incident to be d. If we multiply nf, we get twice as many edges because each edge belongs to two faces, so nf is the number of faces multiplied by the number of edges on each face. Likewise, with dv each edge is incident to two faces so that we have $dv=2e$ so that we have the equality

$nf=2e=dv$

or

$e=\frac{dv}{2}$ and $f=\frac{dv}{n}$

Now, placing these into Euler’s formula, we get

$v+\frac{dv}{n}-\frac{dv}{2}=2$

or

$(2n+2d-dn)v=4n$

But both v and n are positive integers and for $(2n+2d-dn)v=4n$ to be true, we must have that

$2n+2d-dn>0$

or

$(n-2)(d-2)<4$

and so there are just five possibilities for the values of n and d and each of these corresponds to one of the five platonic solids, so that we have

$n=3,d=3$ is a tetrahedron
$n=3,d=4$ is a hexahedron also known as a cube
$n=4,d=3$ is a octahedron
$n=3,d=5$ is a dodecahedron
$n=5,d=3$ is a icosahedron

QED.

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 water
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.

———————————-

Ghazal to Disquietude

1

Drowned in the honk-squeal above the guard rail, I can almost hear
waves sweep in as the soft susurration in the tip of their lips melts the sand between my curled toes.

Noise is now everywhere I want to be
without it. Cars swoosh past Galveston beach roaring their inept monstrous lungs. I can barely

breathe. Or think. Why do trees and blades of every green thing shudder?
Because we are a hyper-intelligent insidious poison? Cats and dogs cling to us in shock and awe.

Ninety-five percent of a car’s energy goes towards moving simply itself not the passengers.
Or rather that’s 2,500 pounds of wastefulness before the crux of tissue steering the steel.

In Hermann Memorial Park a yellow-blue finch tries to sing and fails
in the roar and wall of sound the cars shed in their wake on the I-10 adjoining the beige greenery.

I nod off under a canker tree. A whale whistles out of its water fountain, breathing.
I roll under such plushness, floating with barnacles and sticky ambergris. So glued are our dream’s illogical logic.

I am a sticky carbuncle tearing through the earth’s thin breathability. It’s afternoon in Houston.
I shower again. I scrunch into a starched shirt. I rope my throat with a dead worm’s shiny excrement.

2

My right ear is dead. When I was three
German measles like dappled freckles grew in me

killing the nerve. Now, left ear still good, I hear pretty well
the unprettiness in my parents voices as they divorce:

the light fades as I listen in, on the mosquito bitten dark
roof above the living room window, then roll on my back

to swallow my insignificance in the drifting milky way above.
Now the frogs have started up. A few ducks quack. A splash

might be catfish come to nibble at the stars
tangled in cheap tabloid floating on the pond’s scum.

Pain makes a squelch in my chest like tossed gravel
settling into decay layer at ponds pitch black bottom.

———————————-

Everest

I grasp the impulse that might be driving you
to pity me in some odd way for being flabby and fifty
to your skinny and twenty, but you know, I like most
people stopped aging in my head at twenty-one, the
mental self-image of a nonstop Sid vicious, smiling at
you still trying to figure yourselves out, while we
older folk are done with nothing and wondering
everywhere we still can, asking better questions than
the thin shit we dredged up in our well-spent
grassy laid bare-assed whistling halleluiah youth.
And you listen to nothing we say all day with piercing
eyes as we watch you climbing our mistakes.

———————————-

While sipping coffee, I read what one student wrote:
“The surviving fifty rare whooping cranes
with their seven-foot wingspread that propels them
in their annual migration from northern Canada
to the Gulf of Mexico fly unerringly and
swiftly overhead as they migrate southward
using a kind of built-in radar
in their search for winter quarters
near Aransas Pass.”

Surviving fifty myself, feeling rare and whooping
with my six-foot slouch that propels me nowhere
in my daily migrations from the kitchen to the couch,
I live by the Gulf of Mexico, sleep unerringly and
swiftly, undercover, my dreams migrate southward
using a kind of built-in slinky
in search for vaginal quarters
near my wife’s Aransas Pass.

To be surviving melanoma is rare
with its seven wretched drugs I puke, that propels
me out of the gothic hospital to monthly migrations of chemo;
swimming in the Gulf of Mexico, on my back, I float unerringly and
slowly, overheard, the nurses’ whispers migrate southward
out of memory, which is a kind of built-in shit-breeder
when I am in pain and searching for the way out
near the dark rings of Uranus.

But survival is everything rare as whooping
or her pubic hair spread to propel me
in my daily migrations from her coffer to wherever
it is in the Gulf of Mexico I am off to, I unerringly
admit to caring enough to love her butt
less than I ought too as I migrate southward
using a kind of built-in stupidity
in my blindly succumbing to what is expected of me
clearly perfecting it into a fairly fucked life.

———————————-

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.”

———————————-

Litany

See the purple and green crayon alphabet scrawled on yellow sticky notes stapled to tiny Glen Hills cardboard orange juice containers sucked empty by a strawberry-headed freckled girl named Melissa Alexander Winsum,

See the cardboard, folded and wax coated, that once held the orange juice within it, was wood that came from somewhere green and quiet with squirrels that stretched out on the upholding limbs sucking towards the sun their green certitude of elm or pine or oak,

See how Melissa tied together her carton creation with thick pink fuzzy wool string pulled through holes in the juice containers pricked with a three-fifths whittled down number two Venus pencil she over sharpened while working excited in Miss Thurstin’s after school art class last Tuesday,

See how the wool string grew out of a sheep’s skin, that then kept it warm through a snowy Spring, how that wool sprouted, cell upon cell, a protein made from the very grass the sheep was grazing on, from x-ray sun to chlorophyll to sheep’s cud chewing transformed to the wiry gray mat of wool dyed pink, now holding aloft 26 spent juice containers wobbling in the wind the whole of our English alphabet.

———————————-

Inversion on Monkey Bars

The paths in the park my mother walks me in
crisscross, and cut the grass into Latin squares
or rectangles into which scarf-like flowers bloom
and rooted angels grow, staring up at the sky
with empty alabaster eyes. I chase the wind, turning
stone-edged corners as fast as I can
without falling into the arms of an angel
crouching to take flight. I watch them, their bodies
like sleek athletes, ready to pace the sky
for a brief time, before earth might pull them back
or rain ground them. I climb a boulder’s perch, and jump
spread-armed, trying to stay up in the air
longer and longer each time, to no avail.

But hanging upside down on the monkey bars
I float far above the pitiless earth
as if I spend my days walking the clouds,
and all the angels look up at me, surprised

———————————-

Midnight Recital

Kneeling to untangle my dog’s leg from its leash,
how did I get here, walking a pit bull in the dark
under the sour leaves of drought resistant Texas oaks?
How have these years colluded to put me
with a woman who doesn’t like to be touched
as if my life were still attached
to a former life, lived in felt robes, kneeling,
Why do I sometimes whisper beatitudes in Latin
when grinding roasted coffee beans for breakfast?
Why can’t a fuck be just a fuck like breathing
or the necessary forward movement of starlight
entering my eyes from Polaris when I look up?

Why is my life so intertwined that it folds me
into fractal compartments that expand, as if
from each decision, outward, new enclosures grip me
as I venture forward, faster than any logic I can conjure?
Should I kill politicians to address society’s wrongs?
Or open a shop and sell cracked imported Chinese
Chia Pets? Or get to the lunar surface to erase
the names of loved ones astronauts left behind?
How can this sticky motion of salt and water
hoisted on these dry branches of bone
discern a purpose, lost among thin pricks of starlight
that amble like ancient animals into the night?

———————————————————

How I Came to Poetry

Tucked into the rear-end of a sagging neighborhood
of immodest upscale homes, I attend
Jeb Stuart High on Peace Valley Lane
in Falls Church, Virginia. My sophomore year
there’s this guy, a senior, named Ferenc Molnár.
“Ferenc, what?”, I said. Classmates whisper
he’d gotten a perfect SAT. “Hmm,”
and I let go of trying to say his name.

That summer at the local library
I find Ferenc
scrawled in pencil on the checkout cards
of books that no one else but he had deigned
to date in years. I skedaddle
to the shelf of the first one
Ferenc courted,
a hard blue bound book from Oxford
abundant with English poets.

It opens to pencil-lined pages and lands
on Shelly. I read. In the library’s stacks,
sand begins to blow and cover my blue jean legs
and rubber flip-flops. The long hair of my face
burns in a blond sun. I see
a chiseled sneer erect on a pedestal
of bone, and ornate letters that tell
what a bad ass the owner was,

and watch the hurled tiny intricate skeletons
of shells from an ancient ocean
rub out all traces of his high-on-himself. I’m left
alone with the wind-thrown sand
sticking to the sky. And nothing
but nothing remains

but Shelly’s words indelibly etched in my brain.

———————————————————

Put Some Relish on Your Plate, Pontius 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

as if posturing a proof were proof enough
by itself, but without the heavy lifting of burdens,
the concrete blunders one must make,
clearing the way
to ubiquitous insight. Now, if only

desire would stop helping the scrunched imp
of all my days, rolled into aphasias of dreaming
that stream down like sunlight
through the wet branches of Spring
it might be enough. Perhaps

and you’ll tell me everything
I’ve ever wanted was within reach
if only I would have put out my hands,
wide palms like bells ringing

but as if to a wedding, a funeral
or just praise
at the hours and minutes granted to us,
I don’t know.
Say again, “What?”

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

———————————————————

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.

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.

Everest

I pity the pitiful grasp the impulse that might be driving you
to pity me in some odd way for being flabby and fifty
to your skinny and twenty, but you know, I like most
people stopped aging in my head at twenty-one, the
mental self-image of a nonstop Sid vicious smiling at
you still trying to figure yourselves out, while we
older folk are done with nothing and wondering
everywhere we still can, asking better questions than
the thin shit we dredged up in our well-spent
grassy laid bare-assed whistling halleluiah youth.
And you listen to nothing we say all day with piercing
eyes, as we watch you climbing our mistakes.

Products and Byproducts

Mother’s lips were always moist and wet
with products from Maybelline, one of which
was centrifugal butt gland oil from a

herbaceous monkey — they did that back then
in the 1950’s — for beauty they would go
to any length of death to look pretty

for their scotched-up husbands, even if to their
own funeral, beaten to death, but covered
everywhere in a perfect shade, wet lips

parted to show the false tint of the entrance
to grief, labial flaps that most of us exited
like Helen’s covered bruises that burnt the topless towers

of ilium — was it for his penis, overextending
itself for pleasure? For Vietnam, for Iraq,
for Afghanistan? How else does madness happen?

Litany

See the purple and green crayon alphabet scrawled on yellow sticky notes stapled to tiny Glen Hills cardboard orange juice containers sucked empty by a strawberry-headed freckled girl named Melissa Alexander Winsum,

See the cardboard, folded and wax coated, that once held the orange juice within it, was wood that came from somewhere green and quiet with squirrels that stretched out on the upholding limbs sucking towards the sun their green certitude of elm or pine or oak,

See how Melissa tied together her carton creation with thick pink fuzzy wool string pulled through holes in the juice containers pricked with a three-fifths whittled down number two Venus pencil she over sharpened while working excited in Miss Thurstin’s after school art class last Tuesday,

See how the wool string grew out of a sheep’s skin, that then kept it warm through a snowy Spring, how that wool sprouted, cell upon cell, a protein made from the very grass the sheep was grazing on, from x-ray sun to chlorophyll to sheep’s cud chewing transformed to the wiry gray mat of wool dyed pink, now holding aloft 26 spent juice containers wobbling in the wind our English alphabet.

Wishing Colors (needs better title)

I was awake, but closed my eyes for a few
seconds, and then opened them and continued
how hard they are to calculate, how slippery
the ideas connecting to them, that we really can’t
put much of a dent in the problem. Then I turned
back to the world around me, how the dishes
need doing. The dog lays its head in my lap
asking to be walked. The bronze curtains
blow about in a chill gust, prefiguring storm.

I lift the mountain that is my body , that excavates
a tunnel
through the room, a zigzag of patterns arriving
at the door shore of my entry, and with dog on leash,
stumble out into the dark certainty of night.

I’m sipping coffee and what one student wrote:
“The surviving fifty rare whooping cranes
with their seven-foot wingspread that propels them
in their annual migration from northern Canada
to the Gulf of Mexico fly unerringly and
swiftly overhead as they migrate southward
using a kind of built-in radar
in their search for winter quarters
near Aransas Pass.”

Surviving fifty myself, feeling rare and whooping
with my six-foot slouch that propels me nowhere
in my daily migrations from the kitchen to the couch,
I live by the Gulf of Mexico, sleep unerringly and
swiftly, undercover, my dreams migrate southward
using a kind of built-in slinky
in search for vaginal quarters
near my wife’s Aransas Pass.

To be surviving melanoma is rare
with its seven wretched drugs I puke, that propels
me out of the gothic hospital to monthly migrations of chemo;
swimming in the Gulf of Mexico, on my back, I float unerringly and
slowly, overheard, the nurses’ whispers migrate southward
out of memory, which is a kind of built-in manure-breeder
when I am in pain and searching for the way out
near the dark rings of Uranus.

But survival is everything rare as whooping
or her pubic hair spread to propel me
in my daily migrations from her coffer to wherever
it is in the Gulf of Mexico I am off to, I unerringly
admit to caring enough to love her butt
less than I ought too as I migrate southward
using a kind of built-in stupidity
in my blindly succumbing to what is expected of me
clearly perfecting it into a fairly fucked life.

A Domestic Plot

I was going to read Dragon Tattoo but switched books.

Back from dropping the children safely ensconced at school,
a speckled man with freckles on his egg shaped head sits
sipping coffee with in both hands, his elbows
crushed into the sunflower and dandelion placemat

on his kitchen table. Behind him, his wife
rinses shiny grease and grits from a plastic plate,
then drips and tips it, sets it into formation
to dry among others in the draining board.

The woman hasn’t spoken and the man says nothing.

In front of him, amid clutter gracing the table, a glass bottle of Heinz ketchup,
three-quarters full, smeared with peanut butter around its svelte neck
catches and throws a shadow of his wife working.

In a moment he will kill her with it.

They’ve not had sex in months
or so the plot thickens, as my wife asks
why I read so many books, and the day still
wide open for questions to which I have no answers.

[4th draft]Last edit after suggestions made by Tony Hoagland. 2nd draft deletions thanks Scott and Anthony for these edit suggestions during class.

Sweet

The ink still wet
on the divorce.

Nothing else matters but the musky
scent stuck in my left ruby-pierced nostril
from the last time I ventured
near her vagina.

Names

At first I couldn’t remember the name
you spat me with, that clung to my face, dripping
that smelled of beer and cigarettes
as I wiped off the brown spittle
with the back of my right hand, my left
still clutching the onion sheaves imprinted
with the thin stalks of penned equations
from my lecture I believe I saw you at
leaning forward in the front row
staring at my Palestinian skin.

Hat

Take this dead hat. Now hold it
up into the sunlight. Notice
the sweet Cuban tobacco that drifts
into your nose, if you wander
too close. Pay particular attention
to the three thin white lines of cloth
encompassing the whole of its felt parts.
Now turn it over. Look into the depths
like venturing at night to the edges
of a smoldering volcano, where only your feet
slipping tells you you are on its clipped edges.

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