- mathfun@mailman.xmission.com - mailman.xmission.com

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

Re: [math-fun] Wanted/needed: video of morphing dissection of the plane
by Keith F. Lynch 01 Aug '19

01 Aug '19

Fred Lunnon <fred.lunnon(a)gmail.com> wrote: > Do you even know that a pentagonal maximum exists --- the supremum > might occur at some maximal quadrilateral! Huh? There are intersections between the plane and the cube that have 3, 4, 5, and 6 sides. For each number of sides, there's a smallest area and a largest area. And a smallest perimeter and a longest perimeter. Speaking of which, I should also ask what the smallest values should be for 5 and 6 sides. (For 3 and 4 sides, the minimum areas are obviously 0 or infinitesimal. For 3 sides the shortest perimeter is 0 or infinitesimal, and for four sides it's 4, or infinitesimally more.) Again, I'm speaking of planes in all possible orientations and locations, and a cube with a side length of 2. (Why not a unit cube? Because I can visualize larger cubes better! :-) )

2 1

Re: [math-fun] Wanted/needed: video of morphing dissection of the plane
by Keith F. Lynch 01 Aug '19

01 Aug '19

I have a related question, in support of testing my program that finds the average perimeter and area of random intersections of cubes and planes. I know what the maximum perimeter and maximum area are when the intersection is a triangle, a quadrilateral, or a hexagon. (Or at least I think I do.) But I don't know what it is when the intersection is a pentagon. Does anyone know? Thanks.

2 1

[math-fun] A046693(n) - A309407(n) pattern to n=4443
by ed pegg 31 Jul '19

31 Jul '19

A picture of the Sparse ruler pattern, A046693(n) - A309407(n) to n=4443, is at the bottom of https://community.wolfram.com/groups/-/m/t/1749574 It's a fascinating pattern. "Dark Satanic Mills on a cloudy day" -- NJA Sloane The green squares are likely all black with optimal sparse rulers. Many of the black squares are likely white. The pattern is getting so weird that I'm not sure what to predict now. --Ed Pegg Jr

1 0

[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 28 Jul '19

28 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 28 Jul '19

28 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