March 2010 - mathfun@mailman.xmission.com

[math-fun] Euler's constant sum
by Bill Gosper 15 Mar '10

15 Mar '10

I was showing a kid n 2 i k pi ==== -------- \ n > gamma(e r) / ==== k = 1 limit ------------------------ = - %gamma, 0<r<1, n -> oo n because it approximates a contour integral of Gamma(z)/z around 0, modulo the additional crudity of replacing pi sin(--) n pi ------- by --, i pi n ---- n e when he observed that the crudities somehow cancel: n = 1/r = 69 gives 126 digits! --rwg

2 1

Re: [math-fun] What is a "k-vector"?
by Dan Asimov 14 Mar '10

14 Mar '10

A minor point, but Wikipedia uses k-vector for *any linear combination of* the wedge products of k vectors (from a given vector space). --Dan [Victor wrote:] << Good reference, but that points out an ambiguity. The wikipedia article in question uses k-vector for the wedge product of k vectors of any fixed dimension. Fred uses it for a vector in a vector space of dimension k. I think that both terms are in use. [Mike Stay wrote:] << [Fred wrote:] << Can anybody clarify the situation [of what the definition of a k-vector is] or better still, provide some relevant citations? >> How about wikipedia? http://en.wikipedia.org/wiki/Multivector >> >> >> ________________________________________________________________________________________ "Outside of a dog, a book is man's best friend. Inside of a dog, it's too dark to read." --Groucho Marx

1 0

[math-fun] 73 digit factor found with ECM
by rcs＠xmission.com 13 Mar '10

13 Mar '10

(forwarded from the Number Theory List [NMBRTHRY(a)LISTSERV.NODAK.EDU] A new record for ECM factoring, a 73 digit factor. This polished off M1181, since the cofactor is prime. --rich) ---- Thorsten Kleinjung [thorsten.kleinjung(a)epfl.ch] Mon 3/8/2010 7:16 AM This is a tasty factor We are pleased to announce that on the occasion of its 25th anniversary, ECM smashed through the 70-digit barrier by finding the 73-digit prime factor 1808422353177349564546512035512530001279481259854248860454348989451026887 of 2^1181-1 (thereby completing the factorization of 2^1181-1). The previous ECM record, 68 digits, stood only two months. The 40-, 50-, and 60-digit barriers were broken in 1991, 1998, and 2005, respectively. According to Richard Brent's prediction on page 7 of http://wwwmaths.anu.edu.au/~brent/pd/rpb196sp.pdf ECM is a year ahead of schedule. Some details of this computation: We used GMP-ECM with some modifications so we can run stage 1 on a cluster of PlayStation 3 game consoles (PS3) and stage 2 on a cluster of regular processors. Stage 1: We implemented arithmetic functions for PS3s for Mersenne numbers. We used a recently developed 4-way SIMD carry-less Karatsuba multiplier based on radix 2^12 signed digit representation, thereby obtaining a speed-up of approximately a factor of 2 over our previous unoptimized 4-way SIMD PS3 multiplier. Stage 1 for 24 curves in parallel and for B1=3*10^9 took less than 23 hours on one PS3, i.e., less than one hour per curve per PS3. Stage 2: we parallelized some functions, this stage with the default value of B2 of about 10^14 took about 15 minutes on 4 cores (per curve). We ran more than 30000 stage 1 (less than a week on our PS3 cluster) and 8800 stage 2 computations. The output of the lucky job: GMP-ECM 6.2.3 [powered by GMP 4.3.1] [ECM] Resuming ECM residue saved by jwbos(a)node-3-6.ps3 with GMP-ECM 5.0 on Wed Mar 3 14:03:04 2010 Input number is 1761855336087791124260572121569157372619737256927770987290427942110027309694 7426055352862969336263081344598222161658189601456060023050152594640896272783 7512415610132135965435178668094176985071980937279402238467438168204332393198 436347681167033274334629858331628089772185868567968860006604487 (291 digits) Using B1=3000000000-3000000000, B2=103971375307818, polynomial x^1, sigma=4000027779 Step 1 took 0ms Step 2********** Factor found in step 2: 1808422353177349564546512035512530001279481259854248860454348989451026887 Found probable prime factor of 73 digits: 1808422353177349564546512035512530001279481259854248860454348989451026887 Probable prime cofactor 9742499217576350787770770929191499877801596614705458475589688178325583701641 2999374281145264013986049748696515423136622647352488174403160324612550620242 636441380838851457881913863524385273540967010429382172447745964801 has 218 digits Report your potential champion to Richard Brent <champs(a)rpbrent.com> (see http://wwwmaths.anu.edu.au/~brent/ftp/champs.txt) Paul Zimmermann kindly checked the group order: sage: FindGroupOrder(p,4000027779) 2^4 * 3^2 * 13 * 23 * 61 * 379 * 13477 * 272603 * 12331747 * 19481797 * 125550349 * 789142847 * 1923401731 * 10801302048203 Joppe Bos, Thorsten Kleinjung, Arjen Lenstra (EPFL LACAL) Peter Montgomery (Microsoft Research) http://www.youtube.com/watch?v=ecc0nbg9m-8&feature=related

2 1

Re: [math-fun] Window puzzle, sort of
by Dan Asimov 13 Mar '10

13 Mar '10

Bill T. wrote: << It used to be a standard and well-known geometry fact that given a point and a circle, all lines through the point intersect the circle at two distances that have the same geometric mean = the length of a tangent. This is easy to prove using similar triangles, given the fact that all arcs of circles subtend the same angle as seen from any point on the circle outside the arc. Apply this to the bottom of the wall. >> Phrased in this manner, this has to be the Book proof. --Dan P.S. What's this about a Paris fashion show in which at least one designer based their clothing on geometric theories of some American mathematician? More -- but way too little -- at < http://www.nytimes.com/2010/03/06/fashion/06iht-rrick.html >. ________________________________________________________________________________________ "Outside of a dog, a book is man's best friend. Inside of a dog, it's too dark to read." --Groucho Marx

2 1

Re: [math-fun] Window puzzle, sort of
by rcs＠xmission.com 12 Mar '10

12 Mar '10

Yet another mysterious mailing-list holdback. -- Rich --- Date: Thu, 11 Mar 2010 15:08:13 -0700 Subject: RE: [math-fun] Window puzzle, sort of From: "Payton, Paul" <paul.payton(a)lmco.com> To: "'math-fun'" <math-fun(a)mailman.xmission.com> I did this by taking the derivative of two near-identical copies of the atan function, setting the two algebraic quantities equal, and thoroughly enjoying how things cancel and winding up with a clean sqrt of something rather simple. I'm not sure how didactic that is, but it is remarkably straightforward. Only about four lines of symbols... -----Original Message----- From: math-fun-bounces(a)mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Allan Wechsler Sent: Thursday, March 11, 2010 2:02 PM To: Dan Asimov; math-fun Subject: Re: [math-fun] Window puzzle, sort of I did this with a geometric construction, but even though the algebra was easy, I wouldn't have been able to predict the answer in the form that Dan obviously intends. And I agree with him; it sort of calls out for something that qualifies as an explanation, rather than a mere proof. On Thu, Mar 11, 2010 at 4:05 PM, Dan Asimov <dasimov(a)earthlink.net> wrote: [Hide Quoted Text] This is the window puzzle: Given a window -- on the front of a building -- whose lowest point is height A and whose highest point is height B, how far from the building should a ground-level observer be so that the angle subtended by the window is maximum? <<clipped repeat of older messages -- rcs>>

1 0

[math-fun] What is the name of this concept?
by Victor Miller 12 Mar '10

12 Mar '10

I've been doing some computations with directed graphs, and I came across the need for the following. I'm sure that it has a name, and that there are good (i.e. efficient) algorithms for this out there, if I could only guess the name. Let D be a directed graph. If we have a subgraph D' of D (same vertex set, subset of the edges), I'll say that D' ==> D if for every edges from v-->w in D there is a path from v to w in D'. I'd like to find a minimal D' so that D' ==> D (i.e., if we delete any edge from D' it no longer has this property). I suspect, by the general law of perversity, that finding the minimum (i.e. the minimal D' with the least edges) is probably hard in general. So does anyone know what this is called? Victor

2 2

[math-fun] Window puzzle, sort of
by Dan Asimov 11 Mar '10

11 Mar '10

This is the window puzzle: Given a window -- on the front of a building -- whose lowest point is height A and whose highest point is height B, how far from the building should a ground-level observer be so that the angle subtended by the window is maximum? (Let's assume the window is the interval from (0,A) to (0,B) on the y-axis, and the observer is at (x,0) for x > 0.) This is an easy enough calculus problem, and with a bit of thought can also be solved rigorously without calculus. But the answer is a very simple function of A and B, and ideally there would be a solution that sheds light on why this should be. So that's the real puzzle: Find an elegant solution that illuminates why the answer is in the simple form it is. --Dan ________________________________________________________________________________________ "Outside of a dog, a book is man's best friend. Inside of a dog, it's too dark to read." --Groucho Marx

9 13

Re: [math-fun] Window puzzle, sort of
by Dan Asimov 11 Mar '10

11 Mar '10

Allan wrote: << I did this with a geometric construction, but even though the algebra was easy, I wouldn't have been able to predict the answer in the form that Dan obviously intends. And I agree with him; it sort of calls out for something that qualifies as an explanation, rather than a mere proof. [I wrote:] << This is the window puzzle: Given a window -- on the front of a building -- whose lowest point is height A and whose highest point is height B, how far from the building should a ground-level observer be so that the angle subtended by the window is maximum? (Let's assume the window is the interval from (0,A) to (0,B) on the y-axis, and the observer is at (x,0) for x > 0.) This is an easy enough calculus problem, and with a bit of thought can also be solved rigorously without calculus. But the answer is a very simple function of A and B, and ideally there would be a solution that sheds light on why this should be. So that's the real puzzle: Find an elegant solution that illuminates why the answer is in the simple form it is. >> >> I had a vague idea for an enlightening solution: Maybe show the solution has to be of a certain limited form, and then nail it with a particular case. --Dan ________________________________________________________________________________________ "Outside of a dog, a book is man's best friend. Inside of a dog, it's too dark to read." --Groucho Marx

1 0

Re: [math-fun] Fwd: NYTimes.com: Algebra in Wonderland
by Henry Baker 09 Mar '10

09 Mar '10

It's basically the same material from Bayley's New Scientist article: http://www.newscientist.com/article/mg20427391.600-alices-adventures-in-alg… Alice's adventures in algebra: Wonderland solved 16 December 2009 by Melanie Bayley Magazine issue 2739. What would Lewis Carroll's Alice's Adventures in Wonderland be without the Cheshire Cat, the trial, the Duchess's baby or the Mad Hatter's tea party? Look at the original story that the author told Alice Liddell and her two sisters one day during a boat trip near Oxford, though, and you'll find that these famous characters and scenes are missing from the text. As I embarked on my DPhil investigating Victorian literature, I wanted to know what inspired these later additions. The critical literature focused mainly on Freudian interpretations of the book as a wild descent into the dark world of the subconscious. There was no detailed analysis of the added scenes, but from the mass of literary papers, one stood out: in 1984 Helena Pycior of the University of Wisconsin-Milwaukee had linked the trial of the Knave of Hearts with a Victorian book on algebra. Given the author's day job, it was somewhat surprising to find few other reviews of his work from a mathematical perspective. Carroll was a pseudonym: his real name was Charles Dodgson, and he was a mathematician at Christ Church College, Oxford. The 19th century was a turbulent time for mathematics, with many new and controversial concepts, like imaginary numbers, becoming widely accepted in the mathematical community. Putting Alice's Adventures in Wonderland in this context, it becomes clear that Dodgson, a stubbornly conservative mathematician, used some of the missing scenes to satirise these radical new ideas. Even Dodgson's keenest admirers would admit he was a cautious mathematician who produced little original work. He was, however, a conscientious tutor, and, above everything, he valued the ancient Greek textbook Euclid's Elements as the epitome of mathematical thinking. Broadly speaking, it covered the geometry of circles, quadrilaterals, parallel lines and some basic trigonometry. But what's really striking about Elements is its rigorous reasoning: it starts with a few incontrovertible truths, or axioms, and builds up complex arguments through simple, logical steps. Each proposition is stated, proved and finally signed off with QED. For centuries, this approach had been seen as the pinnacle of mathematical and logical reasoning. Yet to Dodgson's dismay, contemporary mathematicians weren't always as rigorous as Euclid. He dismissed their writing as "semi-colloquial" and even "semi-logical". Worse still for Dodgson, this new mathematics departed from the physical reality that had grounded Euclid's works. By now, scholars had started routinely using seemingly nonsensical concepts such as imaginary numbers - the square root of a negative number - which don't represent physical quantities in the same way that whole numbers or fractions do. No Victorian embraced these new concepts wholeheartedly, and all struggled to find a philosophical framework that would accommodate them. But they gave mathematicians a freedom to explore new ideas, and some were prepared to go along with these strange concepts as long as they were manipulated using a consistent framework of operations. To Dodgson, though, the new mathematics was absurd, and while he accepted it might be interesting to an advanced mathematician, he believed it would be impossible to teach to an undergraduate. Outgunned in the specialist press, Dodgson took his mathematics to his fiction. Using a technique familiar from Euclid's proofs, reductio ad absurdum, he picked apart the "semi-logic" of the new abstract mathematics, mocking its weakness by taking these premises to their logical conclusions, with mad results. The outcome is Alice's Adventures in Wonderland. Algebra and hookahs Take the chapter "Advice from a caterpillar", for example. By this point, Alice has fallen down a rabbit hole and eaten a cake that has shrunk her to a height of just 3 inches. Enter the Caterpillar, smoking a hookah pipe, who shows Alice a mushroom that can restore her to her proper size. The snag, of course, is that one side of the mushroom stretches her neck, while another shrinks her torso. She must eat exactly the right balance to regain her proper size and proportions. While some have argued that this scene, with its hookah and "magic mushroom", is about drugs, I believe it's actually about what Dodgson saw as the absurdity of symbolic algebra, which severed the link between algebra, arithmetic and his beloved geometry. Whereas the book's later chapters contain more specific mathematical analogies, this scene is subtle and playful, setting the tone for the madness that will follow. The first clue may be in the pipe itself: the word "hookah" is, after all, of Arabic origin, like "algebra", and it is perhaps striking that Augustus De Morgan, the first British mathematician to lay out a consistent set of rules for symbolic algebra, uses the original Arabic translation in Trigonometry and Double Algebra, which was published in 1849. He calls it "al jebr e al mokabala" or "restoration and reduction" - which almost exactly describes Alice's experience. Restoration was what brought Alice to the mushroom: she was looking for something to eat or drink to "grow to my right size again", and reduction was what actually happened when she ate some: she shrank so rapidly that her chin hit her foot. De Morgan's work explained the departure from universal arithmetic - where algebraic symbols stand for specific numbers rooted in a physical quantity - to that of symbolic algebra, where any "absurd" operations involving negative and impossible solutions are allowed, provided they follow an internal logic. Symbolic algebra is essentially what we use today as a finely honed language for communicating the relations between mathematical objects, but Victorians viewed algebra very differently. Even the early attempts at symbolic algebra retained an indirect relation to physical quantities. De Morgan wanted to lose even this loose association with measurement, and proposed instead that symbolic algebra should be considered as a system of grammar. "Reduce" algebra from a universal arithmetic to a series of logical but purely symbolic operations, he said, and you will eventually be able to "restore" a more profound meaning to the system - though at this point he was unable to say exactly how. When Alice loses her temper The madness of Wonderland, I believe, reflects Dodgson's views on the dangers of this new symbolic algebra. Alice has moved from a rational world to a land where even numbers behave erratically. In the hallway, she tried to remember her multiplication tables, but they had slipped out of the base-10 number system we are used to. In the caterpillar scene, Dodgson's qualms are reflected in the way Alice's height fluctuates between 9 feet and 3 inches. Alice, bound by conventional arithmetic where a quantity such as size should be constant, finds this troubling: "Being so many different sizes in a day is very confusing," she complains. "It isn't," replies the Caterpillar, who lives in this absurd world. Wonderland's madness reflects Carroll's views on the dangers of the new symbolic algebra The Caterpillar's warning, at the end of this scene, is perhaps one of the most telling clues to Dodgson's conservative mathematics. "Keep your temper," he announces. Alice presumes he's telling her not to get angry, but although he has been abrupt he has not been particularly irritable at this point, so it's a somewhat puzzling thing to announce. To intellectuals at the time, though, the word "temper" also retained its original sense of "the proportion in which qualities are mingled", a meaning that lives on today in phrases such as "justice tempered with mercy". So the Caterpillar could well be telling Alice to keep her body in proportion - no matter what her size. This may again reflect Dodgson's love of Euclidean geometry, where absolute magnitude doesn't matter: what's important is the ratio of one length to another when considering the properties of a triangle, for example. To survive in Wonderland, Alice must act like a Euclidean geometer, keeping her ratios constant, even if her size changes. Of course, she doesn't. She swallows a piece of mushroom and her neck grows like a serpent with predictably chaotic results - until she balances her shape with a piece from the other side of the mushroom. It's an important precursor to the next chapter, "Pig and pepper", where Dodgson parodies another type of geometry. By this point, Alice has returned to her proper size and shape, but she shrinks herself down to enter a small house. There she finds the Duchess in her kitchen nursing her baby, while her Cook adds too much pepper to the soup, making everyone sneeze except the Cheshire Cat. But when the Duchess gives the baby to Alice, it somehow turns into a pig. The target of this scene is projective geometry, which examines the properties of figures that stay the same even when the figure is projected onto another surface - imagine shining an image onto a moving screen and then tilting the screen through different angles to give a family of shapes. The field involved various notions that Dodgson would have found ridiculous, not least of which is the "principle of continuity". Jean-Victor Poncelet, the French mathematician who set out the principle, describes it as follows: "Let a figure be conceived to undergo a certain continuous variation, and let some general property concerning it be granted as true, so long as the variation is confined within certain limits; then the same property will belong to all the successive states of the figure." The case of two intersecting circles is perhaps the simplest example to consider. Solve their equations, and you will find that they intersect at two distinct points. According to the principle of continuity, any continuous transformation to these circles - moving their centres away from one another, for example - will preserve the basic property that they intersect at two points. It's just that when their centres are far enough apart the solution will involve an imaginary number that can't be understood physically (see diagram). Of course, when Poncelet talks of "figures", he means geometric figures, but Dodgson playfully subjects Poncelet's "semi-colloquial" argument to strict logical analysis and takes it to its most extreme conclusion. What works for a triangle should also work for a baby; if not, something is wrong with the principle, QED. So Dodgson turns a baby into a pig through the principle of continuity. Importantly, the baby retains most of its original features, as any object going through a continuous transformation must. His limbs are still held out like a starfish, and he has a queer shape, turned-up nose and small eyes. Alice only realises he has changed when his sneezes turn to grunts. The baby's discomfort with the whole process, and the Duchess's unconcealed violence, signpost Dodgson's virulent mistrust of "modern" projective geometry. Everyone in the pig and pepper scene is bad at doing their job. The Duchess is a bad aristocrat and an appallingly bad mother; the Cook is a bad cook who lets the kitchen fill with smoke, over-seasons the soup and eventually throws out her fire irons, pots and plates. Alice, angry now at the strange turn of events, leaves the Duchess's house and wanders into the Mad Hatter's tea party, which explores the work of the Irish mathematician William Rowan Hamilton. Hamilton died in 1865, just after Alice was published, but by this time his discovery of quaternions in 1843 was being hailed as an important milestone in abstract algebra, since they allowed rotations to be calculated algebraically. Just as complex numbers work with two terms, quaternions belong to a number system based on four terms (see "Imaginary mathematics"). Hamilton spent years working with three terms - one for each dimension of space - but could only make them rotate in a plane. When he added the fourth, he got the three-dimensional rotation he was looking for, but he had trouble conceptualising what this extra term meant. Like most Victorians, he assumed this term had to mean something, so in the preface to his Lectures on Quaternions of 1853 he added a footnote: "It seemed (and still seems) to me natural to connect this extra-spatial unit with the conception of time." Where geometry allowed the exploration of space, Hamilton believed, algebra allowed the investigation of "pure time", a rather esoteric concept he had derived from Immanuel Kant that was meant to be a kind of Platonic ideal of time, distinct from the real time we humans experience. Other mathematicians were polite but cautious about this notion, believing pure time was a step too far. The parallels between Hamilton's maths and the Hatter's tea party - or perhaps it should read "t-party" - are uncanny. Alice is now at a table with three strange characters: the Hatter, the March Hare and the Dormouse. The character Time, who has fallen out with the Hatter, is absent, and out of pique he won't let the Hatter move the clocks past six. Reading this scene with Hamilton's maths in mind, the members of the Hatter's tea party represent three terms of a quaternion, in which the all-important fourth term, time, is missing. Without Time, we are told, the characters are stuck at the tea table, constantly moving round to find clean cups and saucers. Their movement around the table is reminiscent of Hamilton's early attempts to calculate motion, which was limited to rotatations in a plane before he added time to the mix. Even when Alice joins the party, she can't stop the Hatter, the Hare and the Dormouse shuffling round the table, because she's not an extra-spatial unit like Time. The Hatter's nonsensical riddle in this scene - "Why is a raven like a writing desk?" - may more specifically target the theory of pure time. In the realm of pure time, Hamilton claimed, cause and effect are no longer linked, and the madness of the Hatter's unanswerable question may reflect this. Alice's ensuing attempt to solve the riddle pokes fun at another aspect of quaternions: their multiplication is non-commutative, meaning that x Ã y is not the same as y Ã x. Alice's answers are equally non-commutative. When the Hare tells her to "say what she means", she replies that she does, "at least I mean what I say - that's the same thing". "Not the same thing a bit!" says the Hatter. "Why, you might just as well say that 'I see what I eat' is the same thing as 'I eat what I see'!" It's an idea that must have grated on a conservative mathematician like Dodgson, since non-commutative algebras contradicted the basic laws of arithmetic and opened up a strange new world of mathematics, even more abstract than that of the symbolic algebraists. When the scene ends, the Hatter and the Hare are trying to put the Dormouse into the teapot. This could be their route to freedom. If they could only lose him, they could exist independently, as a complex number with two terms. Still mad, according to Dodgson, but free from an endless rotation around the table. And there Dodgson's satire of his contemporary mathematicians seems to end. What, then, would remain of Alice's Adventures in Wonderland without these analogies? Nothing but Dodgson's original nursery tale, Alice's Adventures Under Ground, charming but short on characteristic nonsense. Dodgson was most witty when he was poking fun at something, and only then when the subject matter got him truly riled. He wrote two uproariously funny pamphlets, fashioned in the style of mathematical proofs, which ridiculed changes at the University of Oxford. In comparison, other stories he wrote besides the Alice books were dull and moralistic. I would venture that without Dodgson's fierce satire aimed at his colleagues, Alice's Adventures in Wonderland would never have become famous, and Lewis Carroll would not be remembered as the unrivalled master of nonsense fiction. Imaginary mathematics The real numbers, which include fractions and irrational numbers like that can nevertheless be represented as a point on a number line, are only one of many number systems. Complex numbers, for example, consist of two terms - a real component and an "imaginary" component formed of some multiple of the square root of -1, now represented by the symbol i. They are written in the form a + bi. The Victorian mathematician William Rowan Hamilton took this one step further, adding two more terms to make quaternions, which take the form a + bi + cj + dk and have their own strange rules of arithmetic. Melanie Bayley is a DPhil candidate at the University of Oxford. Her work was supported by the UK's Arts and Humanities Research Council At 09:23 AM 3/9/2010, Paul Reiners wrote: >I'm curious what people think of this article: > > http://www.nytimes.com/2010/03/07/opinion/07bayley.html > > OPINION | March 07, 2010 > Op-Ed Contributor: Algebra in Wonderland > By MELANIE BAYLEY > The other-worldly events in "Alice's Adventures in Wonderland" >can be interpreted as satire on 19th-century advances in mathematics.

1 0

Re: [math-fun] Fwd: NYTimes.com: Algebra in Wonderland
by Dan Asimov 09 Mar '10

09 Mar '10

I read that op-ed piece and I think it's a pile of garbage. The author doesn't present one iota of evidence to support her interpretation. (It might be enough to get her a Ph.D. in English, though.) --Dan Paul R. wrote: << I'm curious what people think of this article: http://www.nytimes.com/2010/03/07/opinion/07bayley.html OPINION | March 07, 2010 Op-Ed Contributor: Algebra in Wonderland By MELANIE BAYLEY The other-worldly events in "Alice's Adventures in Wonderland" can be interpreted as satire on 19th-century advances in mathematics. >> ________________________________________________________________________________________ "Outside of a dog, a book is man's best friend. Inside of a dog, it's too dark to read." --Groucho Marx

1 0