Congratulations to Professor Amit Patel, who received a prestigious Visiting Professor Grant from the Leverhulme Trust, a large national grant-making organization in the United Kingdom. The grant provides funding to support Professor Patel’s research sabbatical for the upcoming academic year at Queen Mary University.
Professor Patel’s research is in algebraic topology with strong connections to the emerging field of topological data analysis. Motivated by questions stemming from data science, Patel is developing new quantitative methods that can be used, for example, to study topological properties of data. During his sabbatical, he will not only continue working on his research program, but will also launch new collaborative research projects with scientists in the UK by exploring research directions at the interface between algebraic topology, stochastic topology, and the science of data.
Please join us in congratulating the CSU Putnam team for their excellent performance on the 2021 Putnam exam! The CSU team placed 203rd out of 427 institutions, putting us in the top half of all teams nationwide. Special congrats to Naeem Moin, Jillian Eddy, and Evelyn Pidcock for obtaining positive scores and also all easily finishing in the top half (and nearly the top third) of all participants!
Special thanks also to graduate students Chris Liu and Jae Hwang Lee for co-coaching this year!
Putnam practices are on Tuesdays at noon in Weber 201 this semester. Everyone (faculty, grad students, and especially undergraduates) is welcome to attend! Feel free to reach out to me by email if you are interested in being added to the mailing list as well.READ MORE
Many of us could happily fold a paper crane, yet few feel confident solving an equation like x³ – 3 x² – x + 3 = 0, to find a value for x.
Both activities, however, share similar skills: precision, the ability to follow an algorithm, an intuition for shape, and a search for pattern and symmetry.
I’m a mathematician whose hobby is origami, and I love introducing people to mathematical ideas through crafts like paper folding. Any piece of origami will contain mathematical ideas and skills, and can take you on a fascinating, creative journey.
The ‘building blocks’ of origami models
As a geometer (mathematician who studies geometry), my favorite technique is modular origami. That’s where you use several pieces of folded paper as “building blocks” to create a larger, often symmetrical structure.
The building blocks, called units, are typically straightforward to fold; the mathematical skill comes in assembling the larger structure and discovering the patterns within them.
Many modular origami patterns, although they may use different units, have a similar method of combining units into a bigger creation.
So, for a little effort you are rewarded with a vast number of models to explore.
My website Maths Craft Australia contains a range of modular origami patterns, as well as patterns for other crafts such as crochet, knitting and stitching.
They require no mathematical background but will take you in some fascinating mathematical directions.
Building 3D shapes from smaller 2D units
In mathematics, the shapes with the most symmetry are called the Platonic solids. They’re named after the ancient Greek philosopher Plato (although they almost certainly predate him and have been discovered in ancient civilisations around the world).
The Platonic solids are 3D shapes made from regular 2D shapes (also known as regular polygons) where every side and angle is identical: equilateral triangles, squares, pentagons.
While there are infinitely many regular polygons, there are, surprisingly, only five Platonic solids:
- the tetrahedron (four triangles)
- the cube (six squares)
- the octahedron (eight triangles)
- the dodecahedron (12 pentagons) and
- the icosahedron (20 triangles).
To build Platonic solids in origami, the best place to start is to master what’s known as the “sonobe unit“.
Enter the sonobe unit
A sonobe unit (sometimes called the sonobe module) looks a bit like a parallelogram with two flaps folded behind.
I’ve got instructions for how to make a sonobe unit on my website and there are plenty of videos online, like this one:https://www.youtube.com/embed/TKGW2W168H0?color=whiteHow to make a sonobe unit.
Sonobe units are fast and simple to fold, and can be fitted together to create beautiful, intriguing 3D shapes like these:
You will need six sonobe units to make a cube like the yellow-blue-green one pictured above, 12 to make an octahedron (the red-pink-purple one), and 30 to make an icosahedron (the golden one). (Interestingly, it’s not possible to build a tetrahedron and dodecahedron from sonobe units).
I’ve got written instructions for building the cube on my website, and some quick searching online will find you instructions for the larger models.
Into the mathematical rabbit hole
Once you’ve mastered the basic structure of each 3D shape, you may find yourself (as others have done) pondering deeper mathematical questions.
Can you arrange the sonobe units so two units of the same color never touch, if you only have three colors?
Are larger symmetric shapes possible? (Answer: yes!)
Are there relationships between the different 3D shapes? (For example, the icosahedron is basically built of triangles, but can you spot the pentagons lurking within? Or the triangles in the dodecahedron?)
One seemingly innocent question can easily lead to a mathematical rabbit hole.
Questions about coloring will lead you to the mathematics of graphs and networks (and big questions that remained unsolved for many centuries).
Then, for a truly mind-bending journey, you might land on the concept of higher-dimensional symmetric shapes.
Or perhaps your questions will lead you in the opposite direction.
Instead of using origami to explore new ideas in mathematics, some researchers have used mathematical frameworks to explore new ideas in origami.
Solving old problems in new ways
Perhaps the most famous mathematical origami artist is the US-based former NASA physicist Robert Lang, who designs computer programs that generate crease patterns for fantastically complicated models.
His models include segmented tarantulas and ants, stags with twisted antlers and soaring, feathered birds.https://www.youtube.com/embed/DJ4hDppP_SQ?color=white
My final example of the power of origami goes back to the cubic equation I mentioned at the outset:
x³ – 3 x² – x + 3 = 0
Cubic equations relate to some “impossible” mathematical problems, such as trisecting an angle (splitting an arbitrary angle into three equal angles). Or doubling a cube (which is finding a cube with double the volume of a given cube).
Famously, these problems cannot be solved using the classical methods of a straightedge (ruler without the markings) and compass.
In 1980, however, Japanese mathematician Hisashi Abe showed how to solve all these problems using origami.
I am excited to see where mathematics and origami will intersect in future. Grab some paper today, make a few models and start your own journey of mathematical exploration.READ MORE
The notion that some computational problems in math and computer science can be hard should come as no surprise. There is, in fact, an entire class of problems deemed impossible to solve algorithmically. Just below this class lie slightly “easier” problems that are less well-understood—and may be impossible, too.https://9998fe7d14e6f2e0d6669492de6863f1.safeframe.googlesyndication.com/safeframe/1-0-38/html/container.html
David Gamarnik, professor of operations research at the MIT Sloan School of Management and the Institute for Data, Systems, and Society, is focusing his attention on the latter, less-studied category of problems, which are more relevant to the everyday world because they involve randomness—an integral feature of natural systems. He and his colleagues have developed a potent tool for analyzing these problems called the overlap gap property (or OGP). Gamarnik described the new methodology in a recent paper in the Proceedings of the National Academy of Sciences.
P ≠ NP
Fifty years ago, the most famous problem in theoretical computer science was formulated. Labeled “P ≠ NP,” it asks if problems involving vast datasets exist for which an answer can be verified relatively quickly, but whose solution—even if worked out on the fastest available computers—would take an absurdly long time.
The P ≠ NP conjecture is still unproven, yet most computer scientists believe that many familiar problems—including, for instance, the traveling salesman problem—fall into this impossibly hard category. The challenge in the salesman example is to find the shortest route, in terms of distance or time, through N different cities. The task is easily managed when N=4, because there are only six possible routes to consider. But for 30 cities, there are more than 1030 possible routes, and the numbers rise dramatically from there. The biggest difficulty comes in designing an algorithm that quickly solves the problem in all cases, for all integer values of N. Computer scientists are confident, based on algorithmic complexity theory, that no such algorithm exists, thus affirming that P ≠ NP.
There are many other examples of intractable problems like this. Suppose, for instance, you have a giant table of numbers with thousands of rows and thousands of columns. Can you find, among all possible combinations, the precise arrangement of 10 rows and 10 columns such that its 100 entries will have the highest sum attainable? “We call them optimization tasks,” Gamarnik says, “because you’re always trying to find the biggest or best—the biggest sum of numbers, the best route through cities, and so forth.”
Computer scientists have long recognized that you can’t create a fast algorithm that can, in all cases, efficiently solve problems like the saga of the traveling salesman. “Such a thing is likely impossible for reasons that are well-understood,” Gamarnik notes. “But in real life, nature doesn’t generate problems from an adversarial perspective. It’s not trying to thwart you with the most challenging, hand-picked problem conceivable.” In fact, people normally encounter problems under more random, less contrived circumstances, and those are the problems the OGP is intended to address.
Peaks and valleys
To understand what the OGP is all about, it might first be instructive to see how the idea arose. Since the 1970s, physicists have been studying spin glasses—materials with properties of both liquids and solids that have unusual magnetic behaviors. Research into spin glasses has given rise to a general theory of complex systems that’s relevant to problems in physics, math, computer science, materials science, and other fields. (This work earned Giorgio Parisi a 2021 Nobel Prize in Physics.)
One vexing issue physicists have wrestled with is trying to predict the energy states, and particularly the lowest energy configurations, of different spin glass structures. The situation is sometimes depicted by a “landscape” of countless mountain peaks separated by valleys, where the goal is to identify the highest peak. In this case, the highest peak actually represents the lowest energy state (though one could flip the picture around and instead look for the deepest hole). This turns out to be an optimization problem similar in form to the traveling salesman’s dilemma, Gamarnik explains: “You’ve got this huge collection of mountains, and the only way to find the highest appears to be by climbing up each one”—a Sisyphean chore comparable to finding a needle in a haystack.
Physicists have shown that you can simplify this picture, and take a step toward a solution, by slicing the mountains at a certain, predetermined elevation and ignoring everything below that cutoff level. You’d then be left with a collection of peaks protruding above a uniform layer of clouds, with each point on those peaks representing a potential solution to the original problem.
In a 2014 paper, Gamarnik and his coauthors noticed something that had previously been overlooked. In some cases, they realized, the diameter of each peak will be much smaller than the distances between different peaks. Consequently, if one were to pick any two points on this sprawling landscape—any two possible “solutions”—they would either be very close (if they came from the same peak) or very far apart (if drawn from different peaks). In other words, there would be a telltale “gap” in these distances—either small or large, but nothing in between. A system in this state, Gamarnik and colleagues proposed, is characterized by the OGP.
“We discovered that all known problems of a random nature that are algorithmically hard have a version of this property”—namely, that the mountain diameter in the schematic model is much smaller than the space between mountains, Gamarnik asserts. “This provides a more precise measure of algorithmic hardness.”
Unlocking the secrets of algorithmic complexity
The emergence of the OGP can help researchers assess the difficulty of creating fast algorithms to tackle particular problems. And it has already enabled them “to mathematically [and] rigorously rule out a large class of algorithms as potential contenders,” Gamarnik says. “We’ve learned, specifically, that stable algorithms—those whose output won’t change much if the input only changes a little—will fail at solving this type of optimization problem.” This negative result applies not only to conventional computers but also to quantum computers, and specifically, to so-called “quantum approximation optimization algorithms” (QAOAs), which some investigators had hoped could solve these same optimization problems. Now, owing to Gamarnik and his co-authors’ findings, those hopes have been moderated by the recognition that many layers of operations would be required for QAOA-type algorithms to succeed, which could be technically challenging.
“Whether that’s good news or bad news depends on your perspective,” he says. “I think it’s good news in the sense that it helps us unlock the secrets of algorithmic complexity and enhances our knowledge as to what is in the realm of possibility and what is not. It’s bad news in the sense that it tells us that these problems are hard, even if nature produces them, and even if they’re generated in a random way.” The news is not really surprising, he adds. “Many of us expected it all along, but we now we have a more solid basis upon which to make this claim.”
That still leaves researchers light-years away from being able to prove the nonexistence of fast algorithms that could solve these optimization problems in random settings. Having such a proof would provide a definitive answer to the P ≠ NP problem. “If we could show that we can’t have an algorithm that works most of the time,” he says, “that would tell us we certainly can’t have an algorithm that works all the time.”
Predicting how long it will take before the P ≠ NP problem is resolved appears to be an intractable problem in itself. It’s likely there will be many more peaks to climb, and valleys to traverse, before researchers gain a clearer perspective on the situation.READ MORE