May 2006 - mathfun@mailman.xmission.com

[math-fun] Re: favorite theorem
by James Propp 03 May '06

03 May '06

>I think you're mistaken in dismissing this as a "theorem". >Once when I TA'd in a course "math for elementary school teachers" >taught by Leon >Henkin, he went over a proof of this theorem---I thought it was >pretty revealing, (although I have to say it wasn't very appropriate >for the future elementary school teachers, who didn't understand the >point.) I'm glad to hear that I was hasty in dismissing the theorematic nature of the claim. Such a nice claim should have a proof, even if it's rated M ("for (mathematically) Mature audiences only"). Come to think of it, I was hasty in asserting that the axiom of infinity can't be proved. It seems to me that Cantor's construction of the counting numbers (where 0 is defined as the empty set, 1 is defined as {0}, 2 is defined as {0,1}, 3 is defined as {0,1,2}, etc.) deserves to be called a constructive proof of the existence of an infinite set. It certainly doesn't FEEL like circular reasoning, even if it's unclear how one would formalize it. (Someone who knows more about Bolzano, Dedekind et al. should chime in here.) Jim

1 0

[math-fun] "Stable polyhedron" (?) problem
by dasimov＠earthlink.net 02 May '06

02 May '06

I'm not sure of the correct name of this old problem, but it's been around since at least the mid 1800's. (There's a legend about George Boole's discussing this with a teacher.): Does there exist a convex polyhedron P in 3-space such that, if it has constant positive 3D density, then when its center of gravity is projected orthogonally onto the planes of its faces, at least one such projection lies inside the face. (I.e., there is a face F such that if P is placed on F on a horizontal plane under gravity, it won't fall over.) An old heuristic nonexistence proof is that if P existed, then placing P on an infinite plane under gravity would lead to a perpetual motion machine. (I don't find this argument persuasive even in the realm of physics.) But in any case, does anyone know whether this problem has been settled? Reference(s) ? (And what is it called?) Thanks, Dan

4 3

[math-fun] NYTimes: In Sudoku, Nine Little Numbers Add up to a Big Challenge
by Henry Baker 02 May '06

02 May '06

At 04:12 PM 5/1/2006, dasimov(a)earthlink.net wrote: >Henry Baker wrote: > ><< >Notice that the NYTimes huffs at other newspapers that print Sudoku's, because it >doesn't print any itself. >>> > >(I hadn't noticed the huffing -- can you point to a URL, say?) > >Frankly if they're going to print only one additional mind-puzzle, I'd much rather >it were in the form of a recreational math puzzle that varied daily. > >--Dan See article, below. I notice that NYT now has Sudoku in their online, edition, however. http://www.nytimes.com/ref/crosswords/sudoku/easy.html?8qa (For some reason, this hung my Mozilla Firefox browser.) BTW, I did a Google search on "sudoku" and "direct product", but didn't come up with anything interesting. Since 9=3*3, isn't it possible that at least some Sudoku's are direct product constructions? Aren't at least some Sudoku's the product table of a 9-element group? ----- http://www.nytimes.com/2006/05/01/arts/01conn.html The New York Times May 1, 2006 Connections In Sudoku, Nine Little Numbers Add up to a Big Challenge By EDWARD ROTHSTEIN "When you have eliminated all which is impossible, then whatever remains, however improbable, must be the truth." Â Sherlock Holmes When it comes to sudoku, there is no escape. The grids of these puzzles seem to shut down the mental apparatus, enclosing one's faculties in a tightly constrained universe Â a 9 by 9 array that must be carefully filled up with the numbers 1 to 9, following certain rules. That enclosure is hypnotic. Publisher's Weekly recently counted 23 sudoku books in print with total sales of 5.7 million copies. Newspapers wage circulation wars by running sudoku in their pages. And sudoku Web sites and forums proliferate internationally (for example, see sudoku.jouwpagina.nl). The teams in the first World Sudoku Championship Â held in Lucca, Italy, in March Â came from 22 countries, including the Philippines, India, Venezuela, and Croatia. The winner was a 31-year-old woman, a Czech accountant. The Independent of London recently reported that a 700 percent increase in the sale of pencils has been attributed to the sudoku craze. Last November, British Airways sent a memo to all its cabin crews, forbidding them to work on sudoku puzzles during takeoffs and landings. The international appeal, of course, may have something to do with the fact that no language is needed to solve sudoku puzzles; neither, for that matter, is any mathematics. The puzzler is given an 81-square grid, with about 20 squares filled in (the "givens"). That large grid is itself divided into nine 3 x 3 grids. The challenge is to fill in the blanks so that each nine-cell row, each nine-cell column and each nine-cell mini-grid contains all the numbers from 1 to 9, with no repetitions or omissions. This is not a novel challenge. Magic squares of various kinds were part of many ancient cultures. Benjamin Franklin published a paper about magic squares, and he obsessively fiddled with them during the same years he was helping to form a more perfect union. The 18th-century Swiss mathematician Leonhard Euler studied the properties of Latin Squares in which each row and column would contain a complete list of the elements of a set of numbers or letters. Sudoku-style puzzles Â which add the twist of the mini-grids within a larger array Â were titled Number Place when they began appearing anonymously in 1979 in the periodical Dell Pencil Puzzles and Word Games. Will Shortz, the crossword puzzle editor of The New York Times, deduced the author's identity with sudoku-style argument: anytime the Dell publication contained one of these puzzles Â and never otherwise Â the list of contributors included Howard Garns, an architect from Indianapolis; Mr. Garns died in 1989. The American-born puzzles made their way to Japan in 1984, where the publisher Nikoli ended up calling them sudoku Â meaning single numbers. And in 1997, Wayne Gould, a New Zealander who had served as a judge in Hong Kong, came across them while vacationing in Tokyo. In 2004 he successfully lobbied The Times of London to introduce the puzzles to Britain, beginning the craze in the West. Strangely, in Japan, where Nikoli has trademark control over the name sudoku, the puzzles are still familiarly known by the English title Number Place, while in the English-speaking work, their Japanese pedigree is widely assumed. But what is their lure? A mathematician I spoke with dismissed the puzzles as mere "bookkeeping" Â keeping track of where things go. And there surely is some of that, since one technique for solving them involves tentatively writing miniature numbers in each little square to figure out the various possibilities. The grid for a difficult puzzle can begin to look like the first draft of a major corporation's balance sheet. This is hardly higher mathematics. In fact, numbers are hardly necessary: the same puzzle can be posed using nine colors or nine national flags. Yet mathematicians have been taking more of an interest in sudoku Â not necessarily in solving the puzzles, but in understanding more about their character. In a recent essay in The American Scientist, Brian Hayes described the difficulty of determining the difficulty of these puzzles: it bears little connection with how many numbers are given at the start. And while numbers are really not that important to sudoku itself, they certainly proliferate in discussions about it. In MathWorld, an online mathematical journal (mathworld.wolfram.com) Eric W. Weisstein cited research showing that 6,670,903,752,021,072,936,960 completed grids are possible for sudoku puzzles, though only 5,472,730,538 unique grids remain once equivalent solutions are eliminated. In a September 2005 column by Ed Pegg Jr. on the site of the Mathematical Association of America (maa.org/news/mathgames.html) also pointed out that the graph theorist Gordon Royle had collected more than 10,000 sudoku puzzles, each with 17 givens. That may be the smallest number of givens that will yield unique solutions (any fewer givens will allow multiple answers), though apparently that hypothesis has not yet been proven. The exhaustive Wikipedia article on sudoku goes into even greater detail (en.wikipedia.org/wiki/Sudoku) What many of these studies focus on, though, is how many sudoku possibilities there are. Each puzzle, using only the simplest of elements, combined according to the simplest of rules, pulls a single solution out of a mind-boggling number of possibilities. The puzzle is an act of reduction and elimination. Often, in solving a puzzle, we work toward an answer, accumulating information. Something must be calculated or produced. In a crossword puzzle, the words have to be pulled out of one's experience. Here, though, each square has only nine possibilities and the work mainly involves not finding the possible but eliminating the impossible, filtering away everything that does not fit Â ruling out the number 4 for a particular square, for example, if a 4 appears in the same row or column or mini-grid. Sudoku does not open up into the world; it reduces the world to its boundaries, forcing everything extraneous to be discarded. There is something more technological about it than mathematical: we know what we must produce; the problem is in getting rid of everything that doesn't fit. This must help account for sudoku's tremendous appeal: it seems to distill complication into elemental clarity, even when that task becomes difficult. On the blog onigame.livejournal.com, the puzzle master Wei-Hwa Huang (who came in third at the world competition in March) devised a unusual system, using colored loops, for solving sudoku that is more knotty than seems possible given the puzzle itself. But the solution is still something easily understood once complete. And it is always immensely satisfying, because finally, all impossibilities have been eliminated, leaving behind a neat array of 81 numbers, that however improbably reveal the trivial truth. Connections, a critic's perspective on arts and ideas, appears every other Monday.

1 0

Misattribution Re: [math-fun] Don't hire authoritarian programmers
by dasimov＠earthlink.net 01 May '06

01 May '06

I should've attributed the quote in previous e-mail to Henry (not Bill G.). My apologies.

1 0

Re: [math-fun] Don't hire authoritarian programmers
by dasimov＠earthlink.net 01 May '06

01 May '06

Bill Gosper wrote: << Notice that the NYTimes huffs at other newspapers that print Sudoku's, because it doesn't print any itself. >> (I hadn't noticed the huffing -- can you point to a URL, say?) Frankly if they're going to print only one additional mind-puzzle, I'd much rather it were in the form of a recreational math puzzle that varied daily. --Dan

1 0

[math-fun] Primitive, Hansen addition chains
by David Wilson 01 May '06

01 May '06

I know a lot of work has been done on minimal addition chains (shortest in number of additions). Presumably this is because minimal addition chains are of interest in optimizing certain operations, e.g, computing powers of large matrices or other complicated objects. I was curious if anyone has explored the idea of primitive addition chains, in which every element is necessary, that is, removing any element but the last does not yield an addition chain. It is easy to show that all minimal addition chains are primitive. But not all primitive chains are minimal (I state this without proof, I know it to be true, it requires only exhibiting a non-minimal primitive addition chain for some n). For n >= 4, the complete addition chain for n, (1,2,3,...,n), is not primitive, because the element n-1 may be removed yielding an addition chain. So what would be the smallest n for which some primitive addition chain for n is longer than a minimal chain for n? For small n, what is the length of the longest primitive addition chain for n? I would also like to know what Hansen chains are. The Mathworld description was not particularly enlightening to me, and there was very little information on the Web. An example with explanation might help me.

2 3

[math-fun] a new identity for Zeta(5)
by simon.plouffe＠sympatico.ca 01 May '06

01 May '06

Hello, I have been working on those Zeta(2n+1) identities that involves infinite series with exp(-Pi*n) lately and I think I have found new formulas. They are interesting since they converge fairly rapidly, for example, that one for Zeta(5) : /infinity \ 5 | ----- | 694 Pi 6280 | \ 1 | Zeta(5) - ------- + ---- | ) --------------------| 204813 3251 | / 5 | | ----- n (exp(4 Pi n) - 1)| \ n = 1 / /infinity \ | ----- | 296 | \ 1 | - ---- | ) --------------------| 3251 | / 5 | | ----- n (exp(5 Pi n) - 1)| \ n = 1 / /infinity \ | ----- | 1073 | \ 1 | + ---- | ) ---------------------| 6502 | / 5 | | ----- n (exp(10 Pi n) - 1)| \ n = 1 / /infinity \ | ----- | 37 | \ 1 | - ---- | ) ---------------------| 6502 | / 5 | | ----- n (exp(20 Pi n) - 1)| \ n = 1 / It converges at a rate of 5.45 decimal digits per iteration. lprint(%): Zeta(5)-694/204813*Pi^5+6280/3251*sum(1/n^5/(exp(4*Pi*n)-1),n = 1 .. infinity)-\ 296/3251*sum(1/n^5/(exp(5*Pi*n)-1),n = 1 .. infinity)+1073/6502*sum(1/n^5/(exp( 10*Pi*n)-1),n = 1 .. infinity)-37/6502*sum(1/n^5/(exp(20*Pi*n)-1),n = 1 .. infinity): I have similar identities for Zeta(9) and Zeta(13) but not yet Zeta(3). As you can see there is some general patterns, other formulas can be found here : http://www.lacim.uqam.ca/~plouffe/ Simon Plouffe

2 1

Re: [math-fun] Re: favorite theorem
by dasimov＠earthlink.net 01 May '06

01 May '06

Bill Thurston wrote: << Once when I TA'd in a course "math for elementary school teachers" taught by Leon Henkin, he went over a proof of this theorem---I thought it was pretty revealing, (although I have to say it wasn't very appropriate for the future elementary school teachers, who didn't understand the point.) But for me, after going through the proof and trying to explain it to my students, it made a lot of sense why there is something that needs proof and that can be proven, our early indoctrination to the contrary notwithstanding. In fact, there's a good proof reducing it to on more primitive intuition than counting. It's very close to the standard proof that finite-dimensional vector spaces over a given field are classified by their dimension---which few people think is obvious without proof! I.e., when you count a finite set in two different orders, why do you get the same number? You can transform one order of counting to the other step-by-step using a simple exchange. I kind of like the point of view that proofs as a dialectical construct, as in Lakatos' book "Proofs and their refutations", rather than part of a formal system (which in practice they definitely are not). Many things people accept for a time, or for ever, until they are challenged, when their beliefs can be shaken. Did you ever tabulate a big set of data by hand and find the column sums and the row sums did not reconcile? At times like that, my belief in the commutative law for addition can become shaken --- thinking back through why sums, or counts, should reconcile is a non-obvious task. >> How would you phrase the theorem(s) you're referring to? I can't see how to say the sizes of [two permutations P,Q of a finite set X] are equal other than this: ------------------------------------- Assume X nonempty. A permutation of a nonempty set X is a bijective mapping X -> {1,...,r} for some r in Z+, so we have bijections P: X -> {1,...,k} and Q: X -> {1,...,n}, and hence P Q^(-1) shows {1,...,k} and {1,...,n} are bijective, hence the same size. ------------------------------------- So, you need to know that inverses and compositions of bijections are bijections, as well as the definitions of permutation and "same size". Is that it? --Dan

2 1

[math-fun] Re: favorite theorem
by James Propp 01 May '06

01 May '06

>>Let me say, only half in jest, that my favorite theorem in math is the >>classification theorem for finite sets, i.e., the fact that finite sets >>are classified up to isomorphism by the counting numbers (including zero)! > >And I'll respond, half-seriously: How would you prove that? I wouldn't call it a theorem in the theorem-proof sense. If a proof is defined (epistemo-sociologically) as a text that makes you believe and/or understand a proposition more than you did before you read the proof (leaving aside the question of what "believe" and "understand" mean), then I don't think this theorem *has* a proof! You can undoubtedly set up a formal system in which this claim is proved by induction, but nobody who didn't already accept the claim would be able to understand the formal system, let alone follow the proof. Instead, I am using the word "theorem" to mean any mathematical fact that makes you say "Well, will you look at that!" And this proposition is a real looker. We all encountered it when we were kids and noticed that a set doesn't change its cardinality when its elements are shifted around, and this agreeable invariance probably fuels many kids' enthusiasm for counting (even though their knowledge of this invariance is intuitive and most of them couldn't begin to articulate it as a general proposition). My serious point is that some mathematical facts may simultaneously be so profound and yet so commonplace that we don't recognize them as "theorems" as such. But I think I want to change my mind about my favorite mathematical fact. How about the fact that there are infinitely many counting numbers? The realization that you can keep on counting forever and never run out of numbers (even if you run out of names for them) was such a mind-blowing experience for my young self that I retained absolutely, positively NO memory of the experience. :-) But my mind remained permanently blown, so there was nothing for me to do with my life but become a mathematician... Is it a "theorem"? Well, I doubt that there are any formal bases for mathematics in which the axiom of infinity can be proved. Either you see it, or you don't. And once you've seen it, you can try to doubt it, but it's really hard to do. Jim

10 12

[math-fun] calcul sans peine
by Thane Plambeck 01 May '06

01 May '06

There's an English translation available, but I prefer the French http://www.comelec.enst.fr/~rioul/misc/calcul.html -- Thane Plambeck http://www.plambeck.org/ehome.htm

1 0