November 2007 - mathfun@mailman.xmission.com

[math-fun] n-D median?
by Steve Witham 19 Nov '07

19 Nov '07

I said: > o Rotating, translating or scaling the points should do the > same to the result. > o Embedding in a higher-dimensional space shouldn't matter. "Afine equivariant." >More generally, you want a function that finds the middle of the pack, >tending to pay less attention to stragglers. "Outliers". In statistics, trying to be insensitive to outliers or noise is called "robustness," and convex peeling (as well as later non-convex peeling) is one way to do this for "multivariate" data. Gastwirth, J.L. (1966), On Robust Procedures. Journal of the American Statistical Association, 61, 929-948 My first method (the second was nonsense but could be patched but doesn't matter) starts out seeming simple and well-motivated, but when it has to iterate it gets complicated in a way that's ill-motivated anyway. Peelings seem more arbitrary at first, but second-through-nth peels are at least arbitrary in the same way. You could get more plausible by building a model that's a mapping of a normal distribution. Or, you could get simpler by taking my method one step and then taking an average. The nice thing about the 1D median is its grand indifference to details. --Steve

2 1

[math-fun] Adding Math to List of Security Threats
by Henry Baker 17 Nov '07

17 Nov '07

FYI -- The New York Times November 17, 2007 Adding Math to List of Security Threats By JOHN MARKOFF SAN FRANCISCO, Nov. 16 Â One of the worldÂs most prominent cryptographers issued a warning on Friday about a hypothetical incident in which a math error in a widely used computing chip places the security of the global electronic commerce system at risk. Adi Shamir, a professor at the Weizmann Institute of Science in Israel, circulated a research note about the problem to a small group of colleagues. He wrote that the increasing complexity of modern microprocessor chips is almost certain to lead to undetected errors. Historically, the risk has been demonstrated in incidents like the discovery of an obscure division bug in IntelÂs Pentium microprocessor in 1994 and, more recently, in a multiplication bug in MicrosoftÂs Excel spreadsheet program, he wrote. A subtle math error would make it possible for an attacker to break the protection afforded to some electronic messages by a popular technique known as public key cryptography. Using this approach, a message can be scrambled using a publicly known number and then unscrambled with a secret, privately held number. The technology makes it possible for two people who have never met to exchange information securely, and it is the basis for all kinds of electronic transactions. Mr. Shamir wrote that if an intelligence organization discovered a math error in a widely used chip, then security software on a PC with that chip could be Âtrivially broken with a single chosen message.Â Executing the attack would require only knowledge of the math flaw and the ability to send a ÂpoisonedÂ encrypted message to a protected computer, he wrote. It would then be possible to compute the value of the secret key used by the targeted system. With this approach, Âmillions of PCÂs can be attacked simultaneously, without having to manipulate the operating environment of each one of them individually,Â Mr. Shamir wrote. The research note is significant, cryptographers said, in part because of Mr. ShamirÂs role in designing the RSA public key algorithm, software that is widely used to protect e-commerce transactions from hackers. ÂThe remarkable thing about this note is that Adi Shamir is saying that RSA is potentially vulnerable,Â said Jean-Jacques Quisquater, a professor and cryptographic researcher at the UniversitÃ© Catholique de Louvain in Belgium. Mr. Shamir is the S in RSA; he, Ronald Rivest and Leonard Adleman developed it in 1977. Because the exact workings of microprocessor chips are protected by laws governing trade secrets, it is difficult, if not impossible, to verify that they have been correctly designed, Mr. Shamir wrote. ÂEven if we assume that Intel had learned its lesson and meticulously verified the correctness of its multipliers,Â he said, Âthere are many smaller manufacturers of microprocessors who may be less careful with their design.Â The class of problem that Mr. Shamir described has been deeply explored by cryptography experts, said Paul Kocher, who is president of Cryptography Research, a consulting and design firm in San Francisco. However, he added that it illustrated how small flaws could subvert even the strongest security. An Intel spokesman noted that the flaw was a theoretical one and something that required a lot of contingencies. ÂWe appreciate these and we look at everything,Â said George Alfs, an Intel spokesman. In e-mail correspondence after he sent the note, Mr. Shamir said he had no evidence that anyone is using an attack like the one he described.

1 0

[math-fun] wavelet book, comet holmes, random permutation
by Schroeppel, Richard 17 Nov '07

17 Nov '07

Can anyone recommend a good introductory book for Wavelets? I have a technical friend who needs to learn about them. He's not a working mathematician, and is looking for a practical approach. Sines & cosines are ok, but triple summations probably not. ------------ Everyone should go look at Comet Holmes. We don't see a comet this bright very often, and it's conveniently located in the evening sky (at least for those of us in the Northern hemisphere.) It's 2nd or 3rd magnitude, in between Cassiopeia & the Pleiades. In binoculars, it's huge. The tail is hidden behind it for now. Google for a finder chart. ------------- I recently came across an old method for generating a random permutation. (Assuming you have a good source of random numbers.) Begin by writing down the identity permutation -- for (i=0;i<n;i++) perm[i] = i; Then pick pairs of locations and swap the contents. x = random(); y = random(); t = perm[x]; perm[x] = perm[y]; perm[y] = t; This isn't an especially good method, but if you do enough swaps, you'll eventually get a random looking result. The surprise is that you need to do a lot more swaps than you'd guess. In the application I encountered, the parameters are N=256 and the number of swaps is 1024, a bit light. The most evident weakness of the method is that it leaves too many cells of the array untouched, giving too many fixed points in the permutation. In the case at hand, I estimate an excess of roughly .1 extra fixed points beyond the expected 1. Depending on the application details, this might be an acceptable deviation from "random". I was inspired to ask a couple of questions. What else might be wrong with these permutations? Is the cycle structure disturbed in some way? Are there too many swaps or short cycles? Is the longest cycle shorter than it should be? Suppose the random number generator is mediocre: How do defects carry over into the generated permutation? Are they repaired by using more swaps? [If the RNG fails to generate some value at all, it's a fixed point of the permutation.] If the swap generator excludes cases when X=Y, but does a replacement swap (so that the total number of executed swaps is always the same), then the result permutation is always even (or odd). This particular defect is undetectable except by examining the entire permutation (minus one element). Even if the swapper doesn't exclude X=Y cases, the expected count is small, so the frequency of even:odd is likely disturbed. How much? Is any of these possible defects harder to remedy than the excess-fixed-points problem? Does getting e-f-p good enough mean you're covered for other kinds of deviations from randomness? Rich

4 5

[math-fun] Re: n-D median?
by Steve Witham 16 Nov '07

16 Nov '07

[revised] Henry Baker <hbaker1(a)pipeline.com> sez: >Consider points more-or-less equally spaced around a circle in 2D. >What should be the "median" ? Well, somewhere close to the center anyway...? With the directions-sum-to-zero median, if you take, say, n > 2 points at equally-spaced angles but random distances from some point, you get that point as the median. E.g. the intersection of a cross. >If I cut the set with hyperplanes, I'd like the hyperplanes to cut >the set in half. Unfortunately, the intersection of [sw: all of] >these hyperplanes is likely to be empty. Yup, can't be that. But maybe: project the points onto every line through the origin, and take the median for each of those lines, then repeat on the result until it converges. Of course this runs into that same counting problem I mentioned before. But I think it avoids the discontinuity problem. (Funny, it also resembles one way to think about a convex hull.) I think my sum of normalized vectors definition is still "median-like". It's the point where there's a "balance of directions." --Steve

1 0

[math-fun] Re: Submarine problem
by Michael Kleber 16 Nov '07

16 Nov '07

In case anyone (other than me) is still interested in the submarine problem, I have a new point of view to share. In particular, I can now construct a sequence of shots for the original n=1,000,000 instance of the problem that destroys all submarines in time 4n. (This is much better than the 12 million or so shots that the n log n algorithm required.) (Oh, and there's an integer sequence that comes up along the way -- so if you're not interested in subs but your initials are NJAS, keep reading anyway. :-) Definition: A "v-sweep" for the n-submarine problem is a sequence of n shots which hit every submarine with velocity v. Note that you can't accomplish this with fewer than n shots, since the n subs with velocity v are parallel -- that is, their paths never intersect, so no single shot can hit two of them. Moreover there are exactly n! v-sweeps (for a given n and v) -- you can hit the n subs in any order. To create a v-sweep, write down any permutation of 1..n and add v*i to the ith element (mod n) -- you're transforming the list of initial positions of the subs you're going to hit into their positions at the times you hit them. Example 1: The permutations are exactly the 0-sweeps: to hit the stationary subs, shoot at every site (in any order). Example 2: The sequence of n 0's is a v-sweep for every v such that gcd(v,n)=1. These are the subs whose trajectories touch every site, so they will pass through 0 once in every n time steps. So one (very limiting) strategy for hitting all the subs is to partition the set of possible velocities V into, say, V1 union V2, and then find a sweep that is a v-sweep for all v in V1 and another sweep that works for all v in V2. If n is a prime, for example, then the two examples above go together to reproduce our old 2p-1 solution. (The "-1" in "2n-1" is because sweeps are translation-invariant -- that is, you can freely add a constant to each term -- so if we're going to shoot one sweep and then another, we can translate one so that the final shot of the first sweep also serves as the initial shot of the second sweep.) Claim: if the sequence (s_i), i=1..n, is a v-sweep, then the sequence ((s_i + w*i) mod n), i=1..n, is a ((v+w) mod n)-sweep. Proof: The map taking the submarine with initial position p and velocity v to the one with initial position p and velocity v+w (mod n) is an automorphism of the original problem. If you think about the subs swimming in a circular ocean, this corresponds to placing the ocean on a lazy susan and spinning it with velocity -w. (Yes, the submarine metaphor seems to be wearing thin.) This is the same logic which allowed the exhaustive search folks to assume WLOG that the first *two* shots are at 0, instead of just the first one shot. Construction: Phase 0: take n shots at 0 Phase 1: take n shots at 0,1,2,...,n-1 Phase 2: take n shots at 0,2,4,6,...,2n-2 (mod n) ... Phase k: take n shots at 0,k,2k,3k,...,k(n-1) (mod n) This will hit all submarines with velocities v such that at least one of v,v+1,v+2,...,v+k is relatively prime to n. So how many phases do you need? Set k to be the length of the longest sequence of consecutive numbers not relatively prime to n. For example: -- For n a prime or prime power, you need two phases (0 and 1), since no two consecutive numbers are both divisible by p. This reproduces the 00...012...n-1 construction that takes 2n-1 shots. -- For n = p^a q^b for odd primes p,q, you can do it with three phases (0,1,2). Certainly if p|i and q|i+1, then neither p nor q can divide i+2. -- For 2^a q^b for odd prime q, you can do it with four phases. The length-3 sequence q-1, q, q+1 is the longest sequence of non-relatively-primes. This does it for n=1,000,000 in 4 million shots (well, 4million-3). -- For n=210=2*3*5*7, for instance, this construction is very bad: you need 10 phases. None of the numbers in the length-9 sequence 2,3,4,5,6,7,8,9,10 is prime to 210. (This means we can solve the n=210 sub problem in 10n-9 = 2091 shots, but the old n log n algorithm does it in 1118.) It seems to me that this "shifts of 00000" strategy doesn't benefit from choosing shifts more complicated than 0,1,2,...k: the Chinese Remainder Theorem says that all that matter are the residue classes of your shifts mod each prime dividing n, since you'll always be able to find a worst-case scenario for each prime individually. I was happy to realize this, because it spared me from having to think about cleverer ways to cover Z/nZ with translates of the set of primitive elements -- but in my relief I didn't think through this as carefully as necessary, so maybe I'm wrong. Integer sequence alert: surely the function "longest gap between numbers relatively prime to n" has a more pleasant name? For n=1,2,3,4,...,20 it has values 0,1,1,1,1,3,1,1,1,3,1,3,1,3,2,1,1,3,1,3, with 1 at every prime power, 3 at 2^a q^b, and the unique 2 at 15. This certainly isn't generally optimal. And it's not an upper bound linear in n, either; pity. But for all that, it's pretty good. --Michael Kleber

1 1

Re: [math-fun] n-D median?
by Dan Asimov 16 Nov '07

16 Nov '07

Steve asks: << Here is a question that's bugged me for a while: Is there a standard or obviously-right way of defining the median for a bag (like a set but with possibly repeated members) of points in 2D or higher space? One way of closing in on it is to ask what properties I want it to have. I can think of a few: o The 1-D case should be the 1-D median. o Rotating, translating or scaling the points should do the same to the result. o Embedding in a higher-dimensional space shouldn't matter. >> The method I've heard about is calld "convex peeling". This means take the convex hull of the data points and remove those lying on the boundary, and repeat. When eventually all remaining data point(s) lie on the most recent convex hull's boundary, take their average and that's the median. --Dan P.S. An interesting phenomenon that occurs at least in 2D: If the data points are a very large random sample from the square, then with high probability the successive convex hull boundaries seem to approach a circular shape (if say they're normalized to have constant diameter).

2 1

[math-fun] n-D median?
by Steve Witham 15 Nov '07

15 Nov '07

Here is a question that's bugged me for a while: Is there a standard or obviously-right way of defining the median for a bag (like a set but with possibly repeated members) of points in 2D or higher space? One way of closing in on it is to ask what properties I want it to have. I can think of a few: o The 1-D case should be the 1-D median. o Rotating, translating or scaling the points should do the same to the result. o Embedding in a higher-dimensional space shouldn't matter. More generally, you want a function that finds the middle of the pack, tending to pay less attention to stragglers. Here's one naive definition, for X, a bag of points in S: Define dir(x) = { 0 if x = 0, x / |x| if x != 0 } (Is there a standard name for dir()? It's like normalizing, only with a special case for zero. "The Sorting Hat") median_like( c, X ) if sum( { dir(x-c) for x in X } ) = 0. median_set( X ) = { c for c in S if median_like( c, X ) } median( X ) = { c if c is the only member of median_set( X ), median( median_set( X ) ) otherwise One nice thing about this recursive definition (given caviats below) is that it gives, e.g.: median( { 0, 1, 2, 3 } ) = 1.5 Here are some of it's naivetes: 1) There are sets of points in n-D space whose median_sets are continuous sets of points--but maybe (n-1) D curves in n-D space. (This happens with discrete(*) points in 1-D, so I assume it can happen with bags of discrete points in higher dimensions.) 2) If so, you need to take the median of a continuous set--which means summing over the highest-dimensional volume you have, in a higher- dimensional space (for instance over the length of a curve in 2D). Maybe this is implied by using special arithmetic where count < length < area < volume ...? 3) The sum of the dir vectors can have discontinuities that cross zero but don't have a zero. For instance, the bag { 0, 0, 1 } has sums ... +3 ... ( +1 ) ... -1 ... ( -2 ) ... -3 ... Should I count zero-crossings like zeroes and say there's a zero- crossing at zero although the value is 1 there? Is 0 the median of { 0, 0, 1 }? 4) Are there situations where the recursion never finishes? If so, must it have a limit at a point? --Steve (*) "individual?" "named?" like discrete but not necessarily distinct? Does the bag { 0, 0 } have two discrete points?

2 1

[math-fun] Pi poem
by Christoph Pacher 12 Nov '07

12 Nov '07

Hi, I pass along a message which was distributed by the latest NA digest (see http://www.netlib.org/na-digest-html/ ). best regards Christoph From: Tim Davis <davis(a)cise.ufl.edu> Date: Wed, 07 Nov 2007 12:56:13 -0500 Subject: One third of a 100-digit challenge (poem) Nick Trefethen defines a ten-digit algorithm as "Ten digits, Five seconds, And just one page", in his essay: http://web.comlab.ox.ac.uk/oucl/work/nick.trefethen/ten_digit_algs.htm , which compares code to poetry. Thus, the following "code" "computes" pi to 33 digits (1/3 of a 100-digit challenge), can be read in about 40 seconds, and fits on half a page. Each line has a number of syllables equal to a digit of pi. The angst comes when the poem itself wonders what to do with the first zero digit ... 3.14159265358979323846264338327950, by T. D. 3 The number, 1 pi. 4 I wonder why 1 I 5 watch the digits fly? 9 Do digits to the infinite tend? 2 Or end 6 at bottom of page ten? 5 Stop I know not when. 3 A circle, 5 pi the number shall 8 encompass all from head to tail. 9 The diameter times pi shall tell 7 not the area, oh swell, 9 but circumference of circles all. 3 pi r square? 2 oh where? 3 Look around, 8 can you find any pie not round? 4 Yet pi r square 6 gives you the area 2 all fine 6 circles you chance to find. 4 e to i pi? 3 (this is fun): 3 minus one. 8 Alas a zed comes up ahead. 3 It cannot 2 be wrought: 7 a poem or stanza taught 9 whose syllables all add up to naught, 5 and so I must stop. 0 [ ]

1 0

Re: [math-fun] octothorpe: M-W's Word of the Day
by Dan Asimov 10 Nov '07

10 Nov '07

Fred asks: << how does one establish the name of a given typographical symbol? E.g. "obelus" refers to a dagger sign ---- but if I didn't already know that, how could I find out? >> Many dictionaries (in the U.S., at least) have a section titled something like Signs and Symbols, where one can look that kind of thing up. (Probably an excellent example would be Merriam-Webster's Third New International Unabridged Dictionary, though many abridged dicts. have rather adequate such lists.) It would be nice if there were such a thing on the web. (A quick check of Wikipedia suggests there is not much on the subject in that resource.) --Dan

3 2

[math-fun] Shortest Ph.D. - apologies
by Guy Haworth 10 Nov '07

10 Nov '07

Google = <"Dan Asmimov" Ph.D. shortest> yields http://www.jstor.org/view/07468342/sp060005/06x0043q/0 Apologies: I did not then notice all the 'Reading University' additions in the URL (interposed by UoR's e-library system - impressive!) but http://www.jstor.org/view/07468342/sp060005/06x0043q/6 does the job - for me ... D Asimov, "Flow Manifolds", UC Berkeley (1972), 28pp. At this rate, we will have written more locating Dan's thesis than Dan did in writing it. Guy

1 0