July 2019 - mathfun@mailman.xmission.com

Re: [math-fun] Sugar + water paradox:
by Bill Gosper 01 Sep '19

01 Sep '19

On Wed, Mar 20, 2019 at 11:37 AM <Shy respondent> wrote: > [just us] > > I think you may just need to wait longer. > Yes. > If the water isn't stirred (either manually or by boiling) > then the liquid near the sugar pile will be highly saturated > and you'll have to wait for random thermal stirring to transport it away > But for several minutes, at least, the amount of dissolved sugar actually declines. On 2019-03-20 12:17, Allan Wechsler wrote: > The obvious question, for me, is how are you measuring this process? I > imagine that you could extract a cc of solution each minute, then evaporate > them and weigh the amount of sugar in each. But I think you're probably not > doing that, but rather relying on some kind of visual measure. What is the > observed dynamic? Does it dissolve for a while until the concentration hits > a plateau, and then sugar starts to precipitate out? Exactly! There's way more sugar in the bottom after it cools for a while. Huge density gradient from lack of stirring. You should have no trouble observing this. Unless I decontrolled it with a teabag of Stash Double Bergamot. —rwg > > On Wed, Mar 20, 2019 at 1:57 PM Bill Gosper <billgosper(a)gmail.com> wrote: > >> Dump a couple of Tbsp of sugar into a quart or two jar of tepid water. >> Don't stir. >> 𝜇wave a couple minutes, hot but not boiling. Let it sit. Experimental >> claim: >> The total dissolved sugar is not an increasing function of time, even >> though a >> couple of Tbsp is << enough to saturate even cold water. >> —rwg > > > > On Mar 20, 2019, at 10:57 AM, Bill Gosper <billgosper(a)gmail.com> wrote: > > > > Dump a couple of Tbsp of sugar into a quart or two jar of tepid water. > > Don't stir. > > 𝜇wave a couple minutes, hot but not boiling. Let it sit. Experimental > > claim: > > The total dissolved sugar is not an increasing function of time, even > > though a > > couple of Tbsp is << enough to saturate even cold water. > > —rwg > > _______________________________________________ > >

2 2

[math-fun] Homology of YGB Sculpture
by Brad Klee 07 Aug '19

07 Aug '19

Consider a Mobius strip, colored symmetrically: Yellow-Green-Blue-Green. (Actually, there are two shades of blue and accents of orange, purple, and magenta, but these extra colors do not contribute to analysis.) If the Mobius strip were non-self-intersecting, a 4*PI cycle could be written as a word, Y1G1B1g1Y2G2B2g2. Instead require that B2 is bisected by the inner Y edge. The path through B2 is obstructed, and the 4*Pi cycle can not be completed, see for example: https://0x0.st/zpTf.JPG https://0x0.st/zpT9.JPG https://0x0.st/zpTp.JPG https://0x0.st/zpTL.JPG Fix the topology by allowing that Y1 and Y2 connect directly to the left and right parts of B2. PROBLEM: How many homology classes does the YGB sculpture have? ANSWER: Three paths are valid from Y1 to Y2: Y1G1B1g1Y2, Y1B2G2Y2, and Y1g2B2Y2. An entire cycle involves one half path plus the reverse of another. Three choose two equals three. Thus the geometry has three homology classes, two of length 7, one of length 6. Explicitly they are: Y1G1B1g1Y2G2B2, Y1G1B1g1Y2B2g2, and Y1B2G2Y2B2g2. A Mobius strip has only one homology class, so this YGB Surface must be something else entirely. Is it known already? If yes, does it also have a vanity name after a famous mathematician? Cheers, Brad

2 3

[math-fun] Wanted/needed: video of morphing dissection of the plane
by James Propp 05 Aug '19

05 Aug '19

I just realized that, to illustrate Warren Smith's way of proving the Wall of Fire theorem at my August 7 talk, it'd be cool to have a video or GIF showing how the intersection between the 2-skeleton of a moving cubical network and a fixed plane evolves in time. For instance, say the plane is {(x,y,z): x+y+z=0} and the cubical network is the standard one in Z^3 moving at constant speed in the (1,1,1) direction, which one can write as {(x,y,z); x≡t (mod 1) or y≡t (mod 1) or z≡t (mod 1)}. We see a dynamic dissection of the plane in which equilateral triangles grow and turn into hexagons and then turn into shrinking triangles pointing the other way. Can anyone dash off such a video? If I use it in my talk I will of course give credit. Thanks, Jim Propp

8 18

Re: [math-fun] Random nonempty intersection of cube and plane, revisited
by Keith F. Lynch 02 Aug '19

02 Aug '19

"Keith F. Lynch" <kfl(a)KeithLynch.net> wrote: > Someone can collaborate right now by giving me some suggestion on > how to figure out the order of the intersections between the plane > and the cube edges. Without knowing the order, I don't know which > of the pairwise distances to add to get the perimeter (except, of > course, in the case of the triangle). Okay, I think I figured it out. Where n is the order of the intersection polygon, 3 through 6, there are n intersection points between the cube and the plane, hence n! possible sequences of intersection points. Since the polygon is convex, I'm pretty sure that the correct order to visit the n intersection points, returning to my starting point (i.e. a Hamiltonian circuit) will simply be the one with the shortest total distance. Someone please politely tell me if I'm wrong. Since it doesn't matter which intersection point I start on, I only have to try (n-1)! sequences. Make that (n-1)!-1, since there are two correct solutions (the same solution in opposite directions) and they can't both be in the last place. So for the largest possible n, 6, 119 tries. Of course it scales very badly for larger polygons, even worse than exponential in n, but that's not an issue here. For larger convex polygons maybe always go to the nearest neighbor not yet visited? No, that can fail. Maybe that always succeeds for *some* starting point, just not necessarily for all of them. That would scale with n^2. > Areas are even tougher. There's no analog of Heron's formula for > quadrilaterals, pentagons, or hexagons. Certainly there is. Once I know the order of the intersection points, all I have to do is run a line from one intersection point to each of the other intersection points, to divide the polygon into triangles, then Heron each of the triangles and add their areas together. If I get the correct average area, that will give me confidence that I also have the correct average perimeter.

2 2

[math-fun] After Strogatz "Infinite Powers", Encyclopedia Idea.
by Brad Klee 31 Jul '19

31 Jul '19

Recently Jim Propp mentioned "Infinite Powers", which is a nice easy reader with historical detail and relevance via the impact of the infinity principle on the current era. In the last chapter on "The future of Calculus", Strogatz describes the pendulum phase portrait as "Poincaré's picture". How should the reader take this assertion? I briefly checked "Mémoire sur les courbes...", but did not see anything recognizable as a pendulum phase portrait. According to D. Nolte "Tangled tale of phase space", only post Ehrenfest did the concept of "phasenraum" come to acceptance. It's well known from correspondence that Sommerfeld communicated with Ehrenfest on this topic, and /Atombau und spektrallinien/ (1921) contains a couple of early depictions of oscillator phase portraits. This is the earliest reference I've found so far. It is impossible to search even a decade of literature exhaustively. Any suggestions? Too bad there is no "Online Encyclopedia of Manifold Geometry". A nice service would enable searches such as "pendulum phase portrait" and return results including a few things about the history. I tried MPIM-Bonn's MAP: http://www.map.mpim-bonn.mpg.de/ but found nothing helpful at all. --Brad

1 0

[math-fun] Mental Factoring
by rcs＠xmission.com 29 Jul '19

29 Jul '19

Hilarie and I have written a paper about mental factoring. http://www.purplestreak.com/g4g13/mentalfactoring.pdf Comments are welcome. If they are not of interest to the group, (typos, grammos, mathos, pedagos, ...) please direct them to me or Hilarie. Rich

1 0

Re: [math-fun] Random nonempty intersection of cube and plane, revisited
by Keith F. Lynch 29 Jul '19

29 Jul '19

James Propp <jamespropp(a)gmail.com> wrote: > You may remember from a couple of years ago the math-fun discussion > of what one gets when one intersects a cube with a random plane that > intersects it nontrivially (Subject: Random slice of a cube). > Thanks to communal effort, we learned that the expected number > of sides is exactly 4, and that this remains true even if one > preselects the orientation of the plane. > In preparing to give a public talk about this result (see > https://www.cityguideny.com/event/MoMath--National-Museum-of-Mathematics--2…) > I realized that some members of the audience may ask "What about the > expected area of the intersection? What about the expected perimeter?" > The answer to the first question is nice (2/3 times the square of > the side-length; ask me if you want to know why). I don't know the > answer to the second question, but maybe some of you can help me > figure it out (e.g., maybe Keith Lynch can dust off his code and > use it to estimate expected perimeter). I don't know, it's still kind of dusty. I've answered the problem, but only for triangles. The average perimeter if the intersection happens to be a triangle is 3.061, and the average area is 0.5495. (The cube has an edge length of 2.) That's with 10 million random planes. As a sanity check, I tracked the maximum perimeter, expecting to get close to 6 sqrt(2), and the maximum area, expecting to get close to 2 sqrt(3), and in both cases I fell short by less than half a percent, which is good. > By the way, one of the themes of my talk is the collaborative > process by which math is done (in contrast to the myth of the > isolated genius), so the sequence of events that brought these > results to light is going to be integral to my talk. Someone can collaborate right now by giving me some suggestion on how to figure out the order of the intersections between the plane and the cube edges. Without knowing the order, I don't know which of the pairwise distances to add to get the perimeter (except, of course, in the case of the triangle). The obvious idea is to check for intersections, other than at or beyond the intersections with the cube edges, between two of the lines, but finding intersections between lines in three dimensions is iffy. A miss is as good as a mile. Areas are even tougher. There's no analog of Heron's formula for quadrilaterals, pentagons, or hexagons. Will your talk be viewable on the Internet?

2 1

[math-fun] Lexicographic ordering of powers of two ...
by Colin Wright 28 Jul '19

28 Jul '19

Here's a small thing that a friend of mine discovered: https://www.solipsys.co.uk/new/PowersOfTwoInLexOrder.html?sg26mf Surely this has been seen before, but I can't find any kinds of references to it. If anyone can suggest some references I'd be grateful. Thanks.

5 6

[math-fun] 30yo Conjecture Solved in Two Pages
by Henry Baker 28 Jul '19

28 Jul '19

FYI -- Wouldn't this conjecture be relevant to the design of more perfect crypto *hashing algorithms* and crypto *S-boxes* -- e.g., "bent", "hyperbent" functions, etc. ? Isn't one goal of such hashing algorithms to perfect an "avalanche effect", whereby flipping a single bit in the input will cause upwards of half of the output bits to flip? --- https://www.scottaaronson.com/blog/?p=4229 https://cstheory.stackexchange.com/questions/19902/boolean-functions-where-… www.mathcs.emory.edu/~hhuan30/papers/sensitivity_1.pdf https://arxiv.org/pdf/1312.0036.pdf https://www.quantamagazine.org/mathematician-solves-computer-science-conjec… Decades-Old Computer Science Conjecture Solved in Two Pages The "sensitivity" conjecture stumped many top computer scientists, yet the new proof is so simple that one researcher summed it up in a single tweet. Dave Whyte for Quanta Magazine A paper posted online this month has settled a nearly 30-year-old conjecture about the structure of the fundamental building blocks of computer circuits. This "sensitivity" conjecture has stumped many of the most prominent computer scientists over the years, yet the new proof is so simple that one researcher summed it up in a single tweet. "This conjecture has stood as one of the most frustrating and embarrassing open problems in all of combinatorics and theoretical computer science," wrote Scott Aaronson of the University of Texas, Austin, in a blog post. "The list of people who tried to solve it and failed is like a who's who of discrete math and theoretical computer science," he added in an email. The conjecture concerns Boolean functions, rules for transforming a string of input bits (0s and 1s) into a single output bit. One such rule is to output a 1 provided any of the input bits is 1, and a 0 otherwise; another rule is to output a 0 if the string has an even number of 1s, and a 1 otherwise. Every computer circuit is some combination of Boolean functions, making them "the bricks and mortar of whatever you're doing in computer science," said Rocco Servedio of Columbia University. Over the years, computer scientists have developed many ways to measure the complexity of a given Boolean function. Each measure captures a different aspect of how the information in the input string determines the output bit. For instance, the "sensitivity" of a Boolean function tracks, roughly speaking, the likelihood that flipping a single input bit will alter the output bit. And "query complexity" calculates how many input bits you have to ask about before you can be sure of the output. Each measure provides a unique window into the structure of the Boolean function. Yet computer scientists have found that nearly all these measures fit into a unified framework, so that the value of any one of them is a rough gauge for the value of the others. Only one complexity measure didn't seem to fit in: sensitivity. In 1992, Noam Nisan of the Hebrew University of Jerusalem and Mario Szegedy, now of Rutgers University, conjectured that sensitivity does indeed fit into this framework. But no one could prove it. "This, I would say, probably was the outstanding open question in the study of Boolean functions," Servedio said. "People wrote long, complicated papers trying to make the tiniest progress," said Ryan O'Donnell of Carnegie Mellon University. Now Hao Huang, a mathematician at Emory University, has proved the sensitivity conjecture with an ingenious but elementary two-page argument about the combinatorics of points on cubes. "It is just beautiful, like a precious pearl," wrote Claire Mathieu, of the French National Center for Scientific Research, during a Skype interview. Aaronson and O'Donnell both called Huang's paper the "book" proof of the sensitivity conjecture, referring to Paul ErdÅs' notion of a celestial book in which God writes the perfect proof of every theorem. "I find it hard to imagine that even God knows how to prove the Sensitivity Conjecture in any simpler way than this," Aaronson wrote. A Sensitive Matter Imagine, Mathieu said, that you are filling out a series of yes/no questions on a bank loan application. When you're done, the banker will score your results and tell you whether you qualify for a loan. This process is a Boolean function: Your answers are the input bits, and the banker's decision is the output bit. If your application gets denied, you might wonder whether you could have changed the outcome by lying on a single question -- perhaps, by claiming that you earn more than $50,000 when you really don't. If that lie would have flipped the outcome, computer scientists say that the Boolean function is "sensitive" to the value of that particular bit. If, say, there are seven different lies you could have told that would have each separately flipped the outcome, then for your loan profile, the sensitivity of the Boolean function is seven. Computer scientists define the overall sensitivity of the Boolean function as the biggest sensitivity value when looking at all the different possible loan profiles. In some sense, this measure calculates how many of the questions are truly important in the most borderline cases -- the applications that could most easily have swung the other way if they'd been ever so slightly different. Sensitivity is usually one of the easiest complexity measures to compute, but it's far from the only illuminating measure. For instance, instead of handing you a paper application, the banker could have interviewed you, starting with a single question and then using your answer to determine what question to ask next. The largest number of questions the banker would ever need to ask before reaching a decision is the Boolean function's query complexity. This measure arises in a host of settings -- for instance, a doctor might want to send a patient for as few tests as possible before reaching a diagnosis, or a machine learning expert might want an algorithm to examine as few features of an object as possible before classifying it. "In a lot of situations -- diagnostic situations or learning situations -- you're really happy if the underlying rule ... has low query complexity," O'Donnell said. Other measures involve looking for the simplest way to write the Boolean function as a mathematical expression, or calculating how many answers the banker would have to show a boss to prove they had made the right loan decision. There's even a quantum physics version of query complexity in which the banker can ask a "superposition" of several questions at the same time. Figuring out how this measure relates to other complexity measures has helped researchers understand the limitations of quantum algorithms. With the single exception of sensitivity, computer scientists proved that all these measures are closely linked. Specifically, they have a polynomial relationship to each other -- for example, one measure might be roughly the square or cube or square root of another. Only sensitivity stubbornly refused to fit into this neat characterization. Many researchers suspected that it did indeed belong, but they couldn't prove that there were no strange Boolean functions out there whose sensitivity had an exponential rather than polynomial relationship to the other measures, which in this setting would mean that the sensitivity measure is vastly smaller than the other measures. "This question was a thorn in people's sides for 30 years," Aaronson said. Cornering the Solution Huang heard about the sensitivity conjecture in late 2012, over lunch with the mathematician Michael Saks at the Institute for Advanced Study, where Huang was a postdoctoral fellow. He was immediately taken with the conjecture's simplicity and elegance. "Starting from that moment, I became really obsessed with thinking about it," he said. Huang added the sensitivity conjecture to a "secret list" of problems he was interested in, and whenever he learned about a new mathematical tool, he considered whether it might help. "Every time after I'd publish a new paper, I would always go back to this problem," he said. "Of course, I would give up after a certain amount of time and work on some more realistic problem." Huang knew, as did the broader research community, that the sensitivity conjecture could be settled if mathematicians could prove an easily stated conjecture about collections of points on cubes of different dimensions. There's a natural way to go from a string of n 0s and 1s to a point on an n-dimensional cube: Simply use the n bits as the coordinates of the point. For instance, the four two-bit strings -- 00, 01, 10 and 11 -- correspond to the four corners of a square in the two-dimensional plane: (0,0), (0,1), (1,0) and (1,1). Likewise, the eight three-bit strings correspond to the eight corners of a three-dimensional cube, and so on in higher dimensions. A Boolean function, in turn, can be thought of as a rule for coloring these corners with two different colors (say, red for 0 and blue for 1). In 1992, Craig Gotsman, now of the New Jersey Institute of Technology, and Nati Linial of Hebrew University figured out that proving the sensitivity conjecture can be reduced to answering a simple question about cubes of different dimensions: If you choose any collection of more than half the corners of a cube and color them red, is there always some red point that is connected to many other red points? (Here, by "connected," we mean that the two points share one of the outer edges of the cube, as opposed to being across a diagonal.) If your collection contains exactly half the corners of the cube, it's possible that none of them will be connected. For example, among the eight corners of the three-dimensional cube, the four points (0,0,0), (1,1,0), (1,0,1) and (0,1,1) all sit across diagonals from one another. But as soon as more than half the points in a cube of any dimension are colored red, some connections between red points must pop up. The question is: How are these connections distributed? Will there be at least one highly connected point? In 2013, Huang started thinking that the best route to understanding this question might be through the standard method of representing a network with a matrix that tracks which points are connected and then examining a set of numbers called the matrix's eigenvalues. For five years he kept revisiting this idea, without success. "But at least thinking about it [helped] me quickly fall asleep many nights," he commented on Aaronson's blog post. Then in 2018, it occurred to Huang to use a 200-year-old piece of mathematics called the Cauchy interlace theorem, which relates a matrix's eigenvalues to those of a submatrix, making it potentially the perfect tool to study the relationship between a cube and a subset of its corners. Huang decided to request a grant from the National Science Foundation to explore this idea further. Then last month, as he sat in a Madrid hotel writing his grant proposal, he suddenly realized that he could push this approach all the way to fruition simply by switching the signs of some of the numbers in his matrix. In this way, he was able to prove that in any collection of more than half the points in an n-dimensional cube, there will be some point that is connected to at least $latex \sqrt{n}$ of the other points -- and the sensitivity conjecture instantly followed from this result. When Huang's paper landed in Mathieu's inbox, her first reaction was "uh-oh," she said. "When a problem has been around 30 years and everybody has heard about it, probably the proof is either very long and tedious and complicated, or it's very deep." She opened the paper expecting to understand nothing. But the proof was simple enough for Mathieu and many other researchers to digest in one sitting. "I expect that this fall it will be taught -- in a single lecture -- in every master's-level combinatorics course," she messaged over Skype. Huang's result is even stronger than necessary to prove the sensitivity conjecture, and this power should yield new insights about complexity measures. "It adds to our toolkit for maybe trying to answer other questions in the analysis of Boolean functions," Servedio said. Most importantly, though, Huang's result lays to rest nagging worries about whether sensitivity might be some strange outlier in the world of complexity measures, Servedio said. "I think a lot of people slept easier that night, after hearing about this." Erica Klarreich Contributing Correspondent

2 1

[math-fun] MOVES conference
by James Propp 28 Jul '19

28 Jul '19

I see I’ve fallen down on the job as a friend of the Museum of Mathematics and as a friend of math-fun by failing to let you all know about a biennial conference on recreational math held at the museum. It’s called the conference on the Mathematics of Various Entertaining Subjects (MOVES for short), and it’s held in odd-numbered years, nicely complementing the Gatherings for Gardner held in even-numbered years and the Bridges gatherings held annually. In case you haven’t heard of Gathering for Gardner and/or Bridges, here are links for all three: https://momath.org/moves-conference/ https://www.gathering4gardner.org/the-gathering/ http://bridgesmathart.org/ Sorry not to have given more notice about MOVES. It’s certainly too late to submit a paper, and probably too late to register to attend. Jim Propp

1 0