October 2007 - mathfun@mailman.xmission.com

[math-fun] well known but no references?
by Anna Johnston 04 Oct '07

04 Oct '07

A last minute talk was given this year at the Finite Fields and their applications conference (http://www.deakin.edu.au/scitech/eit/fq8/) claiming to break several discrete logarithm based public key cryptosystems. Their break consisted of basing the cryptosystems in Z/(p^n)Z where the discrete logarithm was known in Z/pZ. I had thought that this was a well known result, just a simple extension of Hensel lifting (it's a fun number theory exercise to work out the details), but haven't found any references to 'exponential Hensel lifting' in any of the usual places. Google turned up nothing either. Does anyone know of any references to this? Amy Johnston

1 0

[math-fun] Re: Mathpedia/Wikiproof
by Steve Witham 04 Oct '07

04 Oct '07

>From: "Joshua Zucker" <joshua.zucker(a)gmail.com> > >Maybe my experience is too many years out of date, but I find >computer-understandable proofs to make them much less accessible in >general. For instance, in geometry you need to use something closer >to Hilbert's approach, and spend (waste?) lots of time on proving that >this point is between those two, or this ray is between those two, so >you can add or subtract distances or angles. Of course, it's >essential to prove those things to make proofs rigorous, but rigor and >accessibility are quite different things, and I think negatively >correlated. The problem is similar to that of writing good computer programs. But they are like cousins long out of touch. With programming, I think clarity correlates with rigor--but that's in a situation where both are up to the style or preference of the programmer. As with all programming disciplines, a lot depends on whether one has got religion oneself or is being dragged into it. (I could see wikiproof politics going either or both ways.) Math at least has the advantage that proofs tend to be aired by publication. What I mean by rigor is that the programmer worked to be sure they covered all the cases. I think thoroughness correlates with clarity because un-clarity provides places where bugs can hide--it's a bit different with computer validation, but probably clarifying (better organization) is one of the best ways to debug (i.e. satisfy a verifier about) proofs. There is an old study where one group of programmers was told to write a program to be clear, another group, to be fast. The programs written to be clear turned out at least as fast as the "fast" ones. The Qedeq language ( qedeq.org ) looks good in concept with its syntactic sugar and libraries. There could be a form of stretchtext where the justifications of some steps are hidden but clickable (or selectively hideable). My impression is that mathematicians think of a lemma as either a special move like a fancy gymnastic dismount, or a sign that a problem is a really big one. Early in the history of computers subroutines were considered costly and thought of in similar ways. Whereas lately one is encouraged to always break things down. In some languages (e.g. forth) primitives and subroutines are on equal footing and it's considered a sin to write any program longer than a single sentence without breaking it into smaller subroutines (imagine a single dictionary definition going on for a page). Prolog programs that I've seen tend to have very short statements. Long proofs read like the unstructured programs of yore. >Working with automated proof checking sounds painful. "Double-entry bookkeeping? Audit trails? I don't likes the sound o' that!" Just the fact that it seems awkward is an interesting symptom that makes it worth persuing. It's as if we lived in an era where long calculations were carried out by rare experts' hands. Math is very steampunk, including all the funky typography and ancient alphabets. Calculemus, I say. http://www.tiac.net/~sw/2003/08/calculemus.html --Steve

1 0

Re: [math-fun] Mathematical cosmos article by Max Tegmark
by Dan Asimov 01 Oct '07

01 Oct '07

<< So, yes, Max is correct, but only vacuously so. This conclusion also strikes me as correct, but vacuously so. --Dan

1 0

[math-fun] Puzzles that led to new areas of science
by Scott Kim 01 Oct '07

01 Oct '07

I'm writing an article for an upcoming special issue of Discover magazine (in Dec) devoted to puzzles. The article will be about puzzles that led to new developments in math or science. For example, solving the Bridges of Könisburg led Euler to the development of topology. I prefer examples where the puzzle statement and the solution are accessible to a lay audience, and want to include some examples that have very recent implications...for instance even though Könisburg is an old problem, there might be a recent application of Euler circuits that are newsworthy now. Anyone have any thoughts? -- Scott Kim

11 10

[math-fun] Mathpedia/Wikiproof (was Re: Math Fun-ding)
by Henry Baker 01 Oct '07

01 Oct '07

I think that the bulk of the initial part of this work would be done by computer scientists & logicians. Only later, when the bulk of the existing math needs to be shoveled in, would mathematicians be more involved. Re the diversion of effort: one could say the same thing about nearly every tool that has ever been developed -- the effort of creating the tool needs to be traded off against the alternative uses of this effort. Wikipedia presumably doesn't create any "new" knowledge, but makes existing knowledge accessible to a wider audience. Similarly, the discipline of putting every known mathematical proof into computer understandable form would make many of these proofs more accessible to a wider audience. This encyclopedia/database could include multiple proofs of the same theorems, as well as all kinds of human-oriented crutches -- diagrams, animations, movies, pointers to the literature, etc. In many cases, there are smart folks who may not be capable (at least not yet) of developing new theorems (they haven't imbibed enough coffee), but who are perfectly capable of translating math into computer understandable form. "Those who can, do; those who can't, translate proofs." I don't expect that such a project will uncover any significant gaps in existing proofs, but it will require significant clarifications in some cases. The overall goal of this effort would be to have mathematics put its money where its mouth is: mathematics has always claimed a higher/purer form of "truth" than other fields due to the rigor of its proofs. By building this logical structure, mathematics could "prove" this even more concretely. Ancient civilizations built pyramids, acqueducts, coliseums (colisea ?), etc., as monuments to their prowess; why can't we build such a logical structure ? At 11:42 AM 9/29/2007, Andy Latto wrote: >On 9/28/07, Henry Baker <hbaker1(a)pipeline.com> wrote: >> I guess there's also another meaning of "Far Side", as in the "Far Side" cartoons... >> >> I know that Mann is trying to be "open ended", but his topics seem to me to be a bit fuzzier than Hilbert's topics. >> >> I don't know if (D)ARPA is interested, but the time is right for the following project, which could conceivably take 10 or more years: >> >> --- >> Mathpedia/Wikiproof/(still looking for a good name): >> >> Computers are now ubiquitous, and now have enough memory & processing power to enable the following scenario for mathematics publishing: >> >> In order to get a paper published, you have to make all of the proofs mechanically checkable, and submit them to a web-based proof checker prior to being considered by the referees. No proof; no publish. This is arXiv with a prerequisite. > >I wonder why you think this project would be worth the huge diversion >of effort it would involve. > >Number theorists would have to devote effort currently devoted to >advances in number theory to work on formalization of existing work. > >Algebraic geometers would have to devote effort currently devoted to >advances in Algebraic geometry to work on formalization of existing >work. > >And so forth. > >Why is formalization so important that work in every other field of >mathematics should be slowed to make progress in formalization? > >The main advantage I see in formalization is that incorrect proofs are >not mistakenly accepted by the mathematical community. But this seems >to be a solution in seach of a problem; I can count on the fingers of >one hand the cases I know of where a widely accepted result turned out >to be incorrect. > >It's true that under the current system, once an important work is >published, other mathematicians devote effort to verifying its >correctness. But this work would not be eliminated; its main purpose >is not the catching of errors, but the achievement by the verifier of >a deeper understanding of the result and its proof. > >-- > Andy.Latto(a)pobox.com

3 2