February 2014 - mathfun@mailman.xmission.com

Re: [math-fun] More 4th grade "math"
by Henry Baker 04 Feb '14

04 Feb '14

In math, definitions like "divisor" are usually adjusted retrospectively to make some important theorem "work" with fewer "special cases", e.g., Euler's product formula for the totient function: http://en.wikipedia.org/wiki/Euler's_totient_function or the sum of positive divisors function http://en.wikipedia.org/wiki/Divisor_function At 11:12 AM 2/4/2014, Eugene Salamin wrote: >According to a friend who volunteers in the Santa Cruz CA Public Schools, the official view is that 1 is a prime, because its only divisors are 1 and itself. However, a teacher did mention that in more advanced mathematics, 1 is not a prime. > > -- Gene >>________________________________ >> From: Bill Gosper <billgosper(a)gmail.com> >>To: math-fun(a)mailman.xmission.com >>Sent: Tuesday, February 4, 2014 10:22 AM >>Subject: [math-fun] More 4th grade "math" >> >>I just failed to Google up any outrage over an infuriating TV quiz show I >>mistakenly watched several years ago. The contestant, (former astronaut >>Rusty Schweikart?) sailed right through to the million dollar question >>without even using his two "lifelines(?)", and then was sent home penniless >>for not listing 1 among the "factors" of 6. I wonder if, had he mentioned >>1, >>they would have screwed him for confusing "factors" with "divisors". >> >>Anyway, ("drill and kill") Saxon Math is apparently using "factor" to mean >>divisor, presumably because it has fewer syllables: >> >>"Write the factors of 10 that are also factors of 15." >> >>Sounds like they are expecting a "factor" of 1. (I should've checked if >>they think 1 is a prime.) >> >>In the same assignment, >> >>"Divide 20/9. Write the quotient as a fraction." >>"Divide and write the quotient as a fraction: 25/6" >> >>It would probably be less harmful if they signaled their intent with >>gestures and whistles, as in canine obedience school. >> >>--rwg

1 0

[math-fun] obfuscated programs, moron detection interlude
by Warren D Smith 04 Feb '14

04 Feb '14

>> http://www.wired.com/wiredscience/2014/02/cryptography-breakthrough/all/ >> >> Cryptography Breakthrough Could Make Software Unhackable >> By Erica Klarreich, Quanta Magazine02.03.149:30 AM --I can write an interpreter WI for interpreting any program written in Warren's Programming Language (WPL). WI works as follows. First, if decrypts the WPL program by public key cryptography with the decryption key 4103943687648904689346189789676897642975685988043769349707438017463179432. Second, it views the result as a BASIC program and runs it. Now. Doesn't the net program (WI+its input) at seem pretty darn obfuscated to you?

3 3

Re: [math-fun] More 4th grade "math"
by Henry Baker 04 Feb '14

04 Feb '14

I think I blew my 800 math SAT on a similar issue, although I don't recall the exact question 50 years later. One of my teachers had good advice: answer the question you think they meant to have asked. Success in the "real world" is correlated with answering the question the way every other "good student" would have answered, and not necessarily correlated with the pedantically "correct" answer. In a similar vein, I've always found it curious that journalists would _poll_ mathematicians about whether some fact is true or not -- e.g., the discussion prior to proving Fermat's Last Theorem. Mathematics, we hope, isn't a matter of opinion or probability, but has an objective truth which is independent of people's hopes, wishes and any other emotions. Of course, any such mathematical statement must be posed in a suitably rigorous form before it can be answered correctly. At 10:22 AM 2/4/2014, Bill Gosper wrote: >I just failed to Google up any outrage over an infuriating TV quiz show I >mistakenly watched several years ago. The contestant, (former astronaut > Rusty Schweikart?) sailed right through to the million dollar question >without even using his two "lifelines(?)", and then was sent home penniless >for not listing 1 among the "factors" of 6. I wonder if, had he mentioned 1, >they would have screwed him for confusing "factors" with "divisors". > >Anyway, ("drill and kill") Saxon Math is apparently using "factor" to mean >divisor, presumably because it has fewer syllables: > >"Write the factors of 10 that are also factors of 15." > >Sounds like they are expecting a "factor" of 1. (I should've checked if > they think 1 is a prime.) > >In the same assignment, > >"Divide 20/9. Write the quotient as a fraction." >"Divide and write the quotient as a fraction: 25/6" > >It would probably be less harmful if they signaled their intent with >gestures and whistles, as in canine obedience school. > >--rwg

1 0

Re: [math-fun] More 4th grade "math"
by Bill Gosper 04 Feb '14

04 Feb '14

Kerry>Okay, I'll show my ignorance. What is the difference between factor and divisor? The terms are commonly used interchangeably, even at MathWorld. <Kerry (c7) divisors(15) (d7) [1, 3, 5, 15] (c8) factor(15) (d8) 3 * 5 In[7]:= Divisors[15] Out[7]= {1, 3, 5, 15} In[8]:= FactorInteger[15] Out[8]= {{3, 1}, {5, 1}} Oops! Both Macsyma and Mathematica missed that factor of 1^69! Anyone using "factor" to mean other than prime factor or irreducible factor is *begging* to be misunderstood. Mathworld and Mathematica are both Wolfram products. Eric W, if he needs one, has no excuse. MikeG> I'm sorry to boggle about a non-essential part of this anecdote, but was the "million dollar question" really list the factors of 6? Or was that a small part of a larger, more interesting question? It is really hard to believe a question so simple (but apparently not so straightforward) was really the apex of a struggle for 1 million dollars... < The almost insuperable challenge was to perform mindreading on an inferior species, namely the pinhead producers. NeilB thinks the whole thing was scripted. --rwg

1 0

[math-fun] Cryptography Breakthrough Makes Software Unhackable?
by Henry Baker 04 Feb '14

04 Feb '14

FYI -- http://www.wired.com/wiredscience/2014/02/cryptography-breakthrough/all/ Cryptography Breakthrough Could Make Software Unhackable By Erica Klarreich, Quanta Magazine02.03.149:30 AM As a graduate student at the Massachusetts Institute of Technology in 1996, Amit Sahai was fascinated by the strange notion of a Âzero-knowledgeÂ proof, a type of mathematical protocol for convincing someone that something is true without revealing any details of why it is true. As Sahai mulled over this counterintuitive concept, it led him to consider an even more daring notion: What if it were possible to mask the inner workings not just of a proof, but of a computer program, so that people could use the program without being able to figure out how it worked? The idea of ÂobfuscatingÂ a program had been around for decades, but no one had ever developed a rigorous mathematical framework for the concept, let alone created an unassailable obfuscation scheme. Over the years, commercial software companies have engineered various techniques for garbling a computer program so that it will be harder to understand while still performing the same function. But hackers have defeated every attempt. At best, these commercial obfuscators offer a Âspeed bump,Â said Sahai, now a computer science professor at the University of California, Los Angeles. ÂAn attacker might need a few days to unlock the secrets hidden in your software, instead of a few minutes.Â Secure program obfuscation would be useful for many applications, such as protecting software patches, obscuring the workings of the chips that read encrypted DVDs, or encrypting the software controlling military drones. More futuristically, it would allow people to create autonomous virtual agents that they could send out into the computing ÂcloudÂ to act on their behalf. If, for example, you were heading to a remote cabin in the woods for a vacation, you could create and then obfuscate a computer program that would inform your boss about emails you received from an important client, or alert your sister if your bank balance dropped too low. Your passwords and other secrets inside the program would be safe. ÂYou could send that agent into the computing wild, including onto untrusted computers,Â Sahai said. ÂIt could be captured by the enemy, interrogated, and disassembled, but it couldnÂt be forced to reveal your secrets.Â As Sahai pondered program obfuscation, however, he and several colleagues quickly realized that its potential far surpassed any specific applications. If a program obfuscator could be created, it could solve many of the problems that have driven cryptography for the past 40 years Â problems about how to conduct secure interactions with people at, say, the other end of an Internet connection, whom you may not know or trust. ÂA program obfuscator would be a powerful tool for finding plausible constructions for just about any cryptographic task you could conceive of,Â said Yuval Ishai, of the Technion in Haifa, Israel. Precisely because of obfuscationÂs power, many computer scientists, including Sahai and his colleagues, thought it was impossible. ÂWe were convinced it was too powerful to exist,Â he said. Their earliest research findings seemed to confirm this, showing that the most natural form of obfuscation is indeed impossible to achieve for all programs. Then, on July 20, 2013, Sahai and five co-authors posted a paper on the Cryptology ePrint Archive demonstrating a candidate protocol for a kind of obfuscation known as Âindistinguishability obfuscation.Â Two days later, Sahai and one of his co-authors, Brent Waters, of the University of Texas, Austin, posted a second paper that suggested, together with the first paper, that this somewhat arcane form of obfuscation may possess much of the power cryptographers have dreamed of. ÂThis is the first serious positive resultÂ when it comes to trying to find a universal obfuscator, said Boaz Barak, of Microsoft Research in Cambridge, Mass. ÂThe cryptography community is very excited.Â In the six months since the original paper was posted, more papers have appeared on the ePrint archive with ÂobfuscationÂ in the title than in the previous 17 years. However, the new obfuscation scheme is far from ready for commercial applications. The technique turns short, simple programs into giant, unwieldy albatrosses. And the schemeÂs security rests on a new mathematical approach that has not yet been thoroughly vetted by the cryptography community. It has, however, already withstood the first attempts to break it. Researchers are hailing the new work as a watershed moment for cryptography. For many cryptographers, the conversation has shifted from whether obfuscation is possible to how to achieve it. ÂSix or seven years ago, you could have looked at this question and wondered if weÂll ever know the answer,Â said Leonard Schulman, of the California Institute of Technology in Pasadena. ÂThe fact that thereÂs now a plausible construction is huge.Â Too Powerful to Exist When Sahai started thinking about obfuscation 17 years ago, the first task was simply to define it. After all, users can always learn something about a garbled version of a program simply by feeding it inputs and seeing what comes out. The most natural, and also the strongest, definition was the idea of a Âblack boxÂ obfuscator, which would jumble a program so thoroughly that a person with the best available computational resources could figure out nothing at all about it, except for what might be gleaned from inputs and outputs. You could not figure out the value of a password hidden inside the software, unless that password was one of the programÂs outputs, nor could you reassemble parts of the program to compute anything meaningful other than what the program was originally designed to compute. A black box obfuscator, if it existed, would be immensely powerful, providing instant solutions to many cryptography problems that took decades to figure out or in some cases remain unsolved. Take, for example, public key encryption, whose development in the 1970s paved the way for Internet commerce. Prior to its creation, two people who wanted to communicate secretly had to meet in advance to choose an encryption scheme and share a secret key for encoding and decoding messages. Public key encryption allows you to announce a key to the entire world that permits people youÂve never met to send you messages that only you can decrypt. The innovation so revolutionized cryptography that its early developers have been recognized with one award after another. But if you have a black box obfuscator, creating a public key encryption protocol becomes a simple matter of choosing your favorite secret-key encryption scheme, expressing its workings as a computer program, obfuscating the program, and making the obfuscated version widely available. Anyone can then use it to encrypt a message to send to you, but no one can tease the decryption key out of the obfuscated software. Similarly, a black box obfuscator would provide a way to instantly convert any private cryptography scheme to a public one that could be performed over the Internet by strangers. In a sense, obfuscation is the key to all cryptographies. ÂModern cryptography is about the transition from private to public,Â Sahai said. ÂObfuscation gives you a remarkable ability to move between these two worlds that, for decades, we thought of as fundamentally different.Â The power of universal black box obfuscation seemed too good to be true, and it was. In 2001, Sahai, Barak and several co-authors showed that it is impossible. Some programs, the researchers demonstrated, are like people who insist on sharing their most private moments on Twitter or Facebook Â they are so determined to reveal their secrets that no obfuscator can hide them. Still, Sahai couldnÂt stop thinking about the problem. The computer programs the team had devised, which spilled their guts so insistently, were contrived objects unlike any real-world program. Might some weaker notion than black box obfuscation protect the secrets of programs that hadnÂt been specifically constructed to resist obfuscation? And if so, just how powerful would such an idea be? Jigsaw Puzzle Programs Sahai, Barak and their colleagues had put forward one definition of a weaker kind of obfuscation in their 2001 paper, a rather esoteric concept called indistinguishability obfuscation. A program-garbling procedure qualifies as an indistinguishability obfuscator if, whenever two programs that do exactly the same thing pass through the obfuscator, no one is able to tell which garbled program came from which original. ThereÂs no obvious reason why this concept should be particularly useful. After all, even if no one can distinguish the sources of the two garbled programs, it might still be possible to glean important secrets Â a decryption key, or classified instructions Â from looking at the garbled software. ÂItÂs a very weak notion of obfuscation,Â said Craig Gentry, of the IBM Thomas J. Watson Research Center in Yorktown Heights, N.Y. But in 2007, Shafi Goldwasser of MIT and Guy Rothblum of Microsoft Research Silicon Valley in Mountain View, Calif., showed that an indistinguishability obfuscator, if it could be built, would be the best possible obfuscator. The idea is that if some other obfuscator were the best, you could use it to garble the program and then put both the original program and the garbled version through the indistinguishability obfuscator for an additional layer of distortion. Someone looking at the resulting two programs wouldnÂt be able to tell which one came from the original program, meaning that the indistinguishability obfuscator was at least as good at hiding the programÂs secrets as that other, ÂbestÂ obfuscator. Goldwasser and RothblumÂs result meant that indistinguishability obfuscation was the best hope for protecting all of a computer programÂs secrets that are protectable. But no one knew how to build such an obfuscator, or even knew which of a programÂs secrets are protectable. Would an indistinguishability obfuscator, Sahai wondered, protect the secrets people really cared about? For Sahai, the decade leading up to the new finding was marked by dead ends and incremental results. ÂThere was a long period of banging my head against the wall and hoping a dent would form,Â he said. ÂWe were all very pessimistic, but it was such a beautiful problem that I was completely hooked.Â In the fall of 2012, Sahai started collaborating with Gentry and Waters, along with Sanjam Garg and Shai Halevi of the IBM Thomas J. Watson Research Center and Mariana Raykova of SRI International in Menlo Park, Calif., on a problem called functional encryption, which deals with how to give different people particular levels of access to encrypted data. After what Sahai called Âan incredibly intense periodÂ of putting forward ideas, breaking them, and returning to the drawing board, in the spring of 2013 the team came up with a complicated solution to the problem. ÂWhat we had was a mess, with so many moving parts and subscripts of subscripts, but it was the first thing we couldnÂt break,Â Sahai recalled. As the researchers tried to simplify their construction, they discovered that it went much further than anticipated: It presented a way to perform indistinguishability obfuscation on all computer programs. ÂThatÂs a moment IÂll never forget,Â Sahai said. Sahai and Waters proceeded to show that their indistinguishability obfuscator seems to offer much of the all-encompassing cryptographic protection that a black box obfuscator would offer. It can be used, for example, to create public key encryption, digital signatures (which enable a website to convince its visitors that it is legitimate) and a laundry list of other fundamental cryptographic protocols, including two major ones that were previously unsolved, functional encryption and deniable encryption. The teamÂs obfuscator works by transforming a computer program into what Sahai calls a Âmultilinear jigsaw puzzle.Â Each piece of the program gets obfuscated by mixing in random elements that are carefully chosen so that if you run the garbled program in the intended way, the randomness cancels out and the pieces fit together to compute the correct output. But if you try to do anything else with the program, the randomness makes each individual puzzle piece look meaningless. This obfuscation scheme is unbreakable, the team showed, provided that a certain newfangled problem about lattices is as hard to solve as the team thinks it is. Time will tell if this assumption is warranted, but the scheme has already resisted several attempts to crack it, and Sahai, Barak and Garg, together with Yael Tauman Kalai of Microsoft Research New England and Omer Paneth of Boston University, have proved that the most natural types of attacks on the system are guaranteed to fail. And the hard lattice problem, though new, is closely related to a family of hard problems that have stood up to testing and are used in practical encryption schemes. SahaiÂs hope is that not only will this hard problem stand the test of time, but computer scientists will figure out ways to base the obfuscation scheme on more conventional cryptographic assumptions. Cryptographers are already jumping on the indistinguishability obfuscation bandwagon, searching for ways to make the scheme more efficient, bolster its security assumptions, and further elucidate just which secrets it can protect. The proposed obfuscator has already produced a sea change in many cryptographersÂ views of program obfuscation. ÂIt seems that the problem is not impossible,Â said Daniele Micciancio, of the University of California, San Diego. Beyond the immediate task of refining the teamÂs obfuscation protocol lies a deeper question: If the problem of obfuscation has been solved, what remains for cryptographers? ÂWhat is the next major cryptographic frontier that is not solved, at least in principle, by obfuscation?Â Sahai said. ÂThatÂs one of the big questions for our field.Â Original story reprinted with permission from Quanta Magazine, an editorially independent division of SimonsFoundation.org whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.

2 1

Re: [math-fun] Torus puzzle (spoiler)
by Adam P. Goucher 03 Feb '14

03 Feb '14

> Torus puzzle: > > Find a homeomorphism h: T^2 -> T^2 from the torus T^2 to itself that's > periodic of least period 3, and that has exactly 3 fixed points. > > --Dan Very beautiful. Let T^2 = R/Z x R/Z. Then the homeomorphism corresponding to the matrix: [0 1] [-1 -1] is period-3 and has fixed points (0,0), (1/3,1/3) and (2/3,2/3). This corresponds to the order-3 element of the modular group SL(2,Z), which in turn corresponds to an order-3 rotation in the (2,3,infinity) tiling of the hyperbolic plane (which is how I discovered this homeomorphism). Sincerely, Adam P. Goucher

3 4

[math-fun] S.W.Hawking: "black holes don't exist" ??
by Warren D Smith 03 Feb '14

03 Feb '14

A lot of press hoopla just arose over this paper http://arxiv.org/abs/1401.5761 proposing "gravitational collapse produces apparent horizons but no event horizons behind which information is lost." What the heck is he talking about? Another paper claimed to be relevant (and which looks like it comes a lot closer to saying something comprehensible) is http://arxiv.org/abs/1401.0288 -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 1

Re: [math-fun] physics thought experiment (Dave Dyer)
by Adam P. Goucher 03 Feb '14

03 Feb '14

> Also, Goucher's brownian motion solution is technically wrong in the sense > brownian motion has infinite path length Yes, it does, but you can cover that in finite *proper* time. Admittedly the heat-death of the universe would have occurred in that amount of time, but you would still be alive. > so even if you travel at C and do not mind infinite acceleration, you'll > still never get anywhere. Only from the perspective of a static observer. From your perspective, you'll cover the universe in finite time. Sincerely, Adam P. Goucher

6 9

[math-fun] Torus puzzle
by Dan Asimov 02 Feb '14

02 Feb '14

Torus puzzle: Find a homeomorphism h: T^2 -> T^2 from the torus T^2 to itself that's periodic of least period 3, and that has exactly 3 fixed points. --Dan _________________________________________________________ * Least period 3 means for all x in T^2, h(h(h(x))) = x, but there is some x in T^2 such tha h(h(x)) != x .

1 0

[math-fun] oscillating series
by Warren D Smith 02 Feb '14

02 Feb '14

Cris Moore [WDS editing a bit & changing to Elkies notation]: Define S(x) = x-x^2+x^4-x^8+... As x->1, S(x) becomes Grandi's series 1-1+1-1+..., and it oscillates more and more rapidly around 1/2. These oscillations are periodic in log(1-x): one way to see that is to notice that S(x) = x-S(x^2) = x-x^2+S(x^4) = x-x^2+x^4-S(x^8) = etc or roughly f(x) = 1-f(x^2). So squaring x, which (when x is close to 1) increments log(1-x) by log 2, flips f(x) around 1/2. Hardy knew about these oscillations (see http://en.wikipedia.org/wiki/Summation_of_Grandi%27s_series) But my question is: how do we calculate their amplitude? Numerically, f(x) ranges from 1/2+delta to 1/2-delta, where delta = 0.00274 or so. Does anyone know how to obtain this number? --That Elkies page DA pointed out http://www.math.harvard.edu/~elkies/Misc/sol8.html says the Fourier series is known in closed form, which should solve your problem and then some. Except he does not say what it is. S(x) is ultimately periodic as a function of y=log_4 ( log(1/x) ) with period=1 and amplitude (says Elkies) approx 0.00275. I'd be interested to know what this fourier series is & how to get it. Let T(y)=S(x) Then x=exp(-4^y) and T(y) = exp(-4^y) - T(y + 1/2) and we are interested in y-->+infinity and in what is the fourier series of T(y).

3 2