September 2008 - mathfun@mailman.xmission.com

Re: [math-fun] ceiling function
by James Propp 24 Sep '08

24 Sep '08

I wrote: >Using the well-orderedness property of the non-negative integers, plus >the usual axioms of R as an ordered field and Z as an ordered ring, one >can show that the the Archimedean property ("For all real x there exists >an integer n with n > x") implies the existence of the ceiling function >("For all real x there exists a smallest integer n with n greater than >or equal to x"). But does one need well-orderedness (or equivalently >the axiom of induction) to prove this? That is, from the assumption that >the ceiling function exists, can one derive the axiom of induction? > >It seems to me that the proposition that the ceiling function exists >has an intermediate character: it cannot be derived from the ordered >field and ordered ring axioms, but neither is it strong enough to >imply induction. Are there a couple of nice non-standard models of >(R,Z,0,1,+,x,>) that make this completely patent? Henry Baker replied: >I think it boils down to what it means (in your system) to be an "integer". > >1. ceil(x) always returns an integer, so "integer" is the range of ceil(). > >2. integers are totally ordered. > >3. between any two integers, there are only a finite number (including zero) >of other integers. But this is basically well-ordering. > >There are a number of interesting models which are less powerful than the >real numbers. There are "real closed fields", which don't support integers >(proof: real closed fields are decidable, whereas full integers get you >undecidability). There are decidable models which include a "successor" >function, and can support addition, and multiplication by a constant, but >not multiplication of two arbitrary numbers. I may be misinterpreting Henry's reply, but his first sentence seems to suggest that my question doesn't have a well-defined answer, but I maintain that the question I'm trying to ask does have a well-defined answer (even if I don't know yet what that answer is!), so I guess I didn't ask my question clearly enough. Let me try to clarify things by asking, and then answering, an anologous but simpler question about the set of natural numbers (i.e. non-negative integers): Question: Do the first two Peano postulates (0 is not the successor of any natural number; if two natural numbers are unequal, then their successors are unequal) imply the third (if S is any set of natural numbers that contains 0 and has the property that whenever it contains s it contains the successor of s, then S contains all natural numbers)? Answer: No. As a counterexample, consider the model consisting of two copies of the (standard) natural numbers: 0 -> 1 -> 2 -> ... 0'-> 1'-> 2'-> ... This satisfies the first two Peano postulates but not the third. We might call this a non-standard model of the first two Peano postulates, since it's not "the one we had in mind". Note that the question "Do the first two Peano postulates imply the third?" is a well-defined question that a priori has a well-defined answer, even before one knows what the answer is. To bring the notion of "meaning" into the story, we might paraphrase the question as: "Does every model that satisfies the first two Peano postulates also satisfy the third?" Each model that satisfies those two postulates gives a different answer to the query "What do you _mean_ by a natural number?" The answer to the question "Is the third Peano postulate true?" depends on what model one uses, i.e., on what the words in the postulates mean; but the answer to the question "Do the first two Peano postulates imply the third?" means "Does there exist a model of the first two Peano postulates in which the third Peano postulate fails?" and is not a question about what the words mean --- though you might poetically describe it as a question about all _possible_ meanings of the first two postulates. So I believe the only issue is, was I sufficiently clear about what postulates I am assuming for Z and R? Assuming I was, then Henry or someone else should be able to tell me whether these postulates imply that every non-empty subset of Z that's bounded below has a least element. Jim

2 1

Re: [math-fun] Thin strip of spring steel model
by Eugene Salamin 23 Sep '08

23 Sep '08

----- Original Message ---- From: Dan Asimov <dasimov(a)earthlink.net> To: math-fun <math-fun(a)mailman.xmission.com> Sent: Tuesday, September 23, 2008 1:46:05 PM Subject: [math-fun] Thin strip of spring steel model I wonder if anyone is familiar with a simplified physics of uniform thin planar elastic strips, and wouldn't mind explaining it. (A.K.A. a leaf spring) In particular, suppose you have a thin strip of fixed length that for each endpoint is fixed to the plane at a fixed location, with a fixed tangent direction there. (There's also probably a spring constant to toss into the mix.) Is there a formula to determine the shape of the resulting curve based on the endpoint data? A differential equation it must satisfy? Or at least a way to calculate explicitly a quantity that is minimized by the shape, such as potential energy ? --Dan ________________________________ The strain energy per unit length is proportional to the square of the curvature. This is the same as for a thin fiber, untwisted and confined to a plane, and a curve that minimizes the energy is known as an "elastica". The intrinsic equation of an elastica is easily found. Let r = position vector along the curve t = unit tangent vector n = unit normal vector k = curvature s = arc length ' = differentiation with respect to s. We have r' = t, t' = k n, and from t.n = 0, n' = - k n. Then we can show that r' = t r'' = k n r'''' = (k'' - k^3) n - 3 k k' t. The total strain energy int(k^2, s = 0..L) = int(x''(s)^2 + y''(s)^2, s = 0..L) is to be minimized subject to the constraint of fixed total arc length. This constraint can be expresses as x'(s)^2 + y'(s)^2 = 1 at each point on the curve. This the variational problem has Lagragrian L = (x''(s)^2 +y''(s)^2) - m(s) (x'(s)^2 + y'(s)^1 - 1), where the Lagrange multiplier m must be a function of s since the constraint holds for each s. >From the calculus of variations, the minimizing curve satisfies (dL/dx(s)) - (dL/dx'(s))' + (dL/dx''(s))'' = 0, and similarly for y. This becomes (m x')' + x'''' = 0, (m y')' + y'''' = 0, Which are the x and y componenets of the single vector equation (m r')' + r'''' = 0, or resolved along t and n, (m' - 3 k k') t + (m k + k'' - k^3) n = 0. The t component gives m' = (3/2) (k^2)' so that m(s) = (3/2) k^2 + A, where A is a constant. Then the n component gives k''(s) + (1/2) k(s)^3 + A k(s) = 0. Multiplying this by k' and integrating gives (k'(s))^2 + (1/4) k(s)^4 + A (k(s))^2 + B = 0. The solution k(s) involves elliptic functions, and introduces one more constant of integration, in the form k(s) = F(A, B, s + C). Integrating k to give t introduces only one more constant, the initial direction of t. Integration to r gives two more constants, the initial point, for a total of six constants of integration. These can be determined, e.g. by imposing initial and final points on the curve, and initial and final tangent directions. Three of the six degrees of freedom are rigid displacements in the plane, one is a scaling, and one is a displacement of the fineite length fiber along an infinite curve. The sixth degree of freedom is the shape of the curve. Gene

1 0

Re: [math-fun] Thin strip of spring steel model
by Dan Asimov 23 Sep '08

23 Sep '08

Technical point: In order to hope for a unique solution, one would also need to specify an additive angle of form 2K*pi at each endpoint, in order to fix the curve's homotopy class (rel endpoints) when lifted to the unit tangent bundle of R^2. --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

[math-fun] Thin strip of spring steel model
by Dan Asimov 23 Sep '08

23 Sep '08

I wonder if anyone is familiar with a simplified physics of uniform thin planar elastic strips, and wouldn't mind explaining it. (A.K.A. a leaf spring) In particular, suppose you have a thin strip of fixed length that for each endpoint is fixed to the plane at a fixed location, with a fixed tangent direction there. (There's also probably a spring constant to toss into the mix.) Is there a formula to determine the shape of the resulting curve based on the endpoint data? A differential equation it must satisfy? Or at least a way to calculate explicitly a quantity that is minimized by the shape, such as potential energy ? --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

[math-fun] nVidia's "CUDA" for math applications?
by Henry Baker 23 Sep '08

23 Sep '08

Does anyone on this group have an opinion about the use of nVidia's new "CUDA" language & architecture for mathematics? (This is not a troll -- I have no relationship with nVidia.) I understand that if you have an nVidia graphics chip in your computer (I think that most of the Apple units now have one), you can utilize the CUDA software to access the parallel capabilities of this chip for general computation. www.nvidia.com/cuda ----- The New York Times September 23, 2008 Nvidia Chip Speeds Up Imaging for Industrial Use By ASHLEE VANCE SANTA CLARA, Calif. Â Figuring out the best way to transform a frozen pizza into a perfectly warmed pie, gooey on top and crispy on the bottom, is as much a computer problem as a work of culinary art. General Mills, maker of the TotinoÂs and JenoÂs brands of pizzas, would prefer not to whip up a thousand combinations of mozzarella cheese, tomato paste, crust and chemicals and blast them with microwave radiation. ItÂs a lot cheaper and easier to model different pizzas using a sophisticated computer and only cook up the best candidates. To speed up the task, General Mills turned to computers containing high-powered graphics chips from Nvidia, a Santa Clara, Calif., company best known for making video games look more realistic on game consoles and personal computers. Energy exploration firms, clothing designers, medical companies and financial services firms have also bought systems running on Nvidia chips. All of these companies share a common problem: they need hardware that can analyze a vast quantity of data and do it much faster than standard computers. Nvidia, which dominates the market for stand-alone graphics processors, has a clear lead over competitors to provide this kind of industrial data crunching, thanks to a risky bet the company made several years ago. Deliberately giving up some of its graphics performance, Nvidia created a new interface, released in 2006, that lets computer programmers easily tap the hundreds of processing engines on a graphics chip to handle other tasks that require a large number of simultaneous calculations. ÂA couple of billion dollars in R.& D. later, scientists and researchers around the world have come out to thank us,Â said Jen-Hsun Huang, NvidiaÂs co-founder and chief executive. If the companyÂs expensive gamble pays off, Nvidia could break out of its graphics niche and become a far more significant player in the computing landscape. ÂOnce you have lots and lots of companies writing programs that run on these types of products, then you have this potential of a snowball effect,Â said Hans Mosesmann, a semiconductor analyst with Raymond James & Associates. However, Intel and Advanced Micro Devices, the dominant players in the market for conventional computer processors, are working on their own high-end chips that will be optimized for complex computer modeling. More immediately, Intel and A.M.D. are also attacking NvidiaÂs core business Â the graphics chips that go into ordinary laptops and desktop PCs. Nvidia is already feeling the pressure. In August, it reported a 5 percent year-on-year drop in second-quarter revenue, to $893 million, and recorded a $196 million charge tied to the replacement of faulty products shipped in notebooks. Last week, Nvidia laid off about 360 workers, or 6.5 percent of its work force. Its shares closed Monday at $11.17, down from nearly $40 last October. NvidiaÂs graphics processor units differ from mainstream Intel and A.M.D. processors in how they handle software. The Nvidia chips break problems up into many parts and then try to solve those problems at the same time. Standard processors, by contrast, crank through one problem at a time as quickly as possible. The Nvidia technique has proved remarkably adept at handling the display of pixels on a screen, where there are a lot of parts changing at the same time Â typically video images. But some companies and research institutions are finding that graphics processors can handle other kinds of work 10 to 150 times faster than standard processors by breaking up large problems into smaller tasks and reassembling the results later. For example, Techniscan Medical Systems of Salt Lake City has turned to NvidiaÂs graphics processors to speed up a three-dimensional breast scanning device that could be used for cancer detection if the machine received regulatory approval. Techniscan must turn tens of gigabytes of raw data generated by transmitting pulses of energy through a breast submerged in water into medical image files that consume just 100 megabytes. This whole process used to take a couple of hours using IntelÂs processors and now takes just 15 minutes with NvidiaÂs hardware. ÂIf we get it down to 15 minutes per scan, then a patient can come in, fill out their paperwork, have the test and get the results in a single visit to the doctor,Â said Jim Hardwick, a software engineer at Techniscan. ÂThis is extremely important.Â The oil and gas industry, which tries to determine the most promising locations to drill wells, has found that NvidiaÂs technology can vastly decrease the time needed to make sense of reams of geologic data. SeismicCity, based in Houston, analyzes data given off by manmade explosions used to ripple waves through the ground and detect changes in density that may point to fruitful places for drilling a new oil well. In the past, the company was limited by the performance of standard microprocessors. It wanted to tweak its algorithm more often to produce more accurate data for its oil company customers. ÂWith the Nvidia chips, we sped up our calculations by 10 times,Â said David Kessler, SeismicCityÂs president. ÂThat doesnÂt happen every day. Now when oil companies drill wells, their success rate should go up.Â Nvidia has shipped close to 100 million processors with the new programmable interface, called Compute Unified Device Architecture, or CUDA. The programming kit has been downloaded more than 150,000 times. Academic institutions have embraced the technology, with the University of Illinois, for example, setting up a teaching center at Urbana-Champaign dedicated to CUDA and NvidiaÂs corresponding Tesla servers. A few companies, including Acceleware of Canada, have centered their business around NvidiaÂs software and hardware, selling customized solutions to General Mills, Eli Lilly, Nokia and other industrial customers. ÂWe think that the number of people interested in this technology is in the tens of millions,Â Mr. Huang said. ÂIt is not just here. It is in China and India and Russia and Brazil. Many billions of dollars is our rough estimate for the size of the market.Â Sangeeth Peruri, an analyst at J.& W. Seligman, said NvidiaÂs new technology could transform the company. ÂWe have to see whether this will ramp or not, but I do think this is pretty amazing technology,Â he said. NvidiaÂs competitors are more dismissive. Executives at A.M.D. and Intel argue that a rather small set of very sophisticated software can take advantage of the CUDA design. ÂThey are severely restricted and limited,Â said Dave Hofer, a director of marketing at Intel. ÂIn the short term, it is not a massive threat.Â Intel plans to release a competing product called Larrabee in 2009 or 2010. A.M.D. is promoting a fledgling programming layer from Apple called OpenCL, or Open Computing Language, which A.M.D. hopes will blunt CUDAÂs momentum should it be ready for widespread use as expected in 2009. Mr. Huang, however, said the competition is underestimating his companyÂs lead. ÂWe will have shipped 300 million units with CUDA by the time those other guys are ready,Â Mr. Huang said. ÂWe probably have a four-year lead on Intel.Â

3 2

[math-fun] Ben Franklin, mathematics & vegetarianism
by Henry Baker 23 Sep '08

23 Sep '08

I recently heard someone on the radio say that Ben Franklin said he never was able to understand math until he became a vegetarian. I have not been able to find any reference to this statement on the web. Franklin's struggles with math and his vegetarianism are well-known, but I haven't found anything linking the two together. Does anyone else on this list have any info? Thanks.

4 5

[math-fun] Sort of off-topic: road grooved to play the William Tell Overture
by Henry Baker 21 Sep '08

21 Sep '08

FYI -- This is a great hack! http://www.latimes.com/features/la-on-road21-2008sep21,0,3910118.story >From the Los Angeles Times SoCal officials to pave over road grooved to play the William Tell Overture >From the Associated Press September 20, 2008 Officials in northern Los Angeles County are putting an end to the car-tunes that are driving residents crazy. Lancaster city officials said this week that they're paving over a quarter-mile strip of asphalt grooved to play the William Tell Overture when auto tires speed over its surface. The road was completed earlier this month as part of an ad campaign for Honda. It's engineered to play the overture -- also known as the theme to the Lone Ranger -- at perfect pitch for motorists driving Honda Civics at 55 mph. But nearby residents aren't amused. One says the road music sounds like a high-pitch drone. Another says it keeps him and his wife up at night. Lancaster officials plan pave the grooves over Tuesday.

1 0

Re: [math-fun] Hilbert curves
by Fred lunnon 20 Sep '08

20 Sep '08

On 9/19/08, Steve Witham <sw(a)tiac.net> wrote: > Found this page: > > http://people.csail.mit.edu/jaffer/Geometry/HSFC > > Pretty much searching for "Butz Hilbert". Very useful page --- wonder why didn't I manage to find it earlier? > Jaffer complains that the existing implementations of Butz's > multi-dimensional Hilbert curve algorithm > 1) are hard to read, > 2) take the number of bits of precision as an argument (instead > of letting it be whatever the arguments require), and > 3) are limited by the precision of the representations they > use for distance-along-curve, for instance to 32 bits, for the > product (number of dimensions x bits of resolution in each). As well as that some are unstable --- increasing the level altering the initial steps. > So, he develops a Scheme algorithm that uses bignums and works "in > terms of higher level constructs: Gray-code, lamination, rotation > and reflection." Unfortunately, unless one speaks "Scheme"(?), it's fairly incomprehensible; and AJ is fares no better than anybody else does (self included, so far!) at giving a coherent description of his algorithm [artificially slowed and complicated by an absence of decent "bitwise" logical operators]. In particular, he fails to define "lamination" --- however, later on he does say "Gray codes find use communicating incrementally changing values between asynchronous agents. De-laminated Gray codes comprise the coordinates of Hilbert space-filling curves." This sounds to be pretty much the same idea that Mike Stay talked about earlier! > This sounds like the right approach to me (although it might need > optimizing/obfuscating again in the end), but I'm still having problem > 1) at the moment. Here's the main routine (mainly to show its length): > ... [There is a link to the entire program for forward and reverse navigation.] > Further rationale: http://people.csail.mit.edu/jaffer/Geometry/RFMDSFF Including a the following thoughtful list of desirable properties for a space-filler: "Space-filling: a continuous function whose range contains the entire n-dimensional unit hypercube. Multidimensional: exist for all ranks greater than one. Self-similar: can be defined by a nonterminating recurrence. Lebesgue measure-preserving: equal length intervals map to equal volumes. Isotropic: the lengths of axis-aligned projections of the space-filling curve should be equal." But alas, still no definition of a "Hilbert curve" ... Jaffer gives a short bibliography, including Rolf Niedermeier, Jochen Alber "On Multi-dimensional Hilbert Indexings" COCOON '98 Springer (1998) who apparently have got some sort of definition, and (remarkably) claim "our analysis shows that there are 1536 structurally different 3D Hilbert curves" at which the imagination boggles (and may be better to remain that way). There are also references to a business-like C-program by Doug Moore at http://web.archive.org/web/20050204100342/http://www.caam.rice.edu/~dougm/t… who includes what Jaffer christens "box" and "comparison" functions, and an experimental comparison of the clustering behaviour. Although the algorithm is undocumented, its general shape is similar enough to my effort to suggest that the time and space costs should be comparable (if/when we get around to C-ifying the Java code). (Curses!). > Also, > He develops a Peano-curve-based method that fills all space instead > of just a >=0 corner. > He measures distance on the curve vs. Euclidean distance for various > curves. Some of these studies mention that the performance of different methods tends to converge for higher dimensions. I wonder if they have taken account of the fact that, for a fixed diameter region, the average level rapidly approaches unity as the dimension increases --- so that the "walk" becomes effectively a Gray coded path around the unit hypercube. A nice project would be to implement the various available algorithms in the same language (probably C), and compare their performance wrt time, space, clustering. Fred Lunnon

1 0

[math-fun] AGM for Gamma(n/12)
by rwg＠sdf.lonestar.org 19 Sep '08

19 Sep '08

In case anybody besides me missed it, Gamma(1/3) = 2^(11/18)*(sqrt(3)+1)^(1/3)*%pi^(2/3)/(3^(1/4)*agm(sqrt(2)*(sqrt(3)+1),1)^(1/3)) 11/18 1/3 2/3 1 2 (sqrt(3) + 1) %pi gamma(-) = ------------------------------------- 3 1/4 1/3 3 AGM (sqrt(2) (sqrt(3) + 1), 1) follows from Borwein&Borwein, pp 15(a) and 28(d), so Gamma(1/3) is nearly as easy as pi. Similarly, Gamma(1/4) = 2^(3/4)*%pi^(3/4)/sqrt(agm(sqrt(2),1)) 3/4 3/4 1 2 %pi Gamma(-) = --------------------- 4 sqrt(AGM(sqrt(2), 1)) finishes off Gamma(n/12). Interesting that, unlike pi, there are no hypergeometric series for these, although the sum(n/(%e^(2*sqrt(3)*%pi*n)-1),n,1,inf) is a degenerate bibasic series. ((1 = AGM(eta(q^2)^10/(eta(q)^4*eta(q^4)^4),eta(q)^4/eta(q^2)^2)) = AGM((16*eta(q^4)^8+eta(q)^8)^(5/12)/eta(q)^(2/3),eta(q)^(10/3)/(16*eta(q^4)^8+eta(q)^8)^(1/12))/eta(q^4)^(2/3)) = AGM(sqrt(64*eta(q^4)^24+eta(q^2)^24)-8*eta(q^4)^12,eta(q^2)^12)/(eta(q^2)^2*eta(q^4)^2*sqrt(sqrt(64*eta(q^4)^24+eta(q^2)^24)-8*eta(q^4)^12)) 10 2 4 eta (q ) eta (q) 1 = AGM(----------------, --------) 4 4 4 2 2 eta (q) eta (q ) eta (q ) 8 4 8 5/12 10/3 (16 eta (q ) + eta (q)) eta (q) AGM(---------------------------, ---------------------------) 2/3 8 4 8 1/12 eta (q) (16 eta (q ) + eta (q)) = ------------------------------------------------------------- 2/3 4 eta (q ) 24 4 24 2 12 4 12 2 AGM(sqrt(64 eta (q ) + eta (q )) - 8 eta (q ), eta (q )) = --------------------------------------------------------------------. 2 2 2 4 24 4 24 2 12 4 eta (q ) eta (q ) sqrt(sqrt(64 eta (q ) + eta (q )) - 8 eta (q )) --rwg Does anyone besides Salamin remember the meaning of the agm error in Peter Samson's (1960s) PDP-1 music compiler?

6 19

Re: [math-fun] polynomial questions of Dan Asimov
by Dan Asimov 19 Sep '08

19 Sep '08

<< Dan later asks a similar question regarding the difference between the largest and smallest real roots. For that, consider: x^d - N x^(d-1) - N x^(d-2) + N x^(d-3) - N x^(d-4) + ... (first 2 terms after leading term are negative after which terms alternate in sign, last term is + or - N depending on parity of d). This polynomial has roots near -2 and N+1 suggesting the largest spread of real roots is around n+3. I did not try to prove these are best possible, but they may be. >> I see my writing was not clear, since I wasn't looking for the maximum difference between roots of *any one polynomial*. Rather, among *all* monic integer polynomials of degree <= d, with a constraint on the size of the coefficients -- say the absolute values of the coefficients sum to <= N -- Then, among the set R(d: N) of *all* real roots of these polynomials, let the maximum be max(d; N) and the minimum be min(d; N). Then I'm interested here in an estimate (or asymptotics) for MM(d: N) := max(d; N) - min(d; N). --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

2 1