How to Prove a Theorem So No One Else Can Claim It

The trouble with sitting down at a computer keyboard to enter a password is that someone may be looking over your shoulder. Because your password could be stolen as you type it, the computer system isn't completely secure.

But if you could somehow provide the computer with information that persuades the computer you know the password without actually giving away the password itself, you would be on your way to solving the security problem.

Furthermore, if no onlooker could reconstruct the password from the information you gave the computer, no one could break into the system—at least by using a purloined password.

The mathematical basis for such a scheme is available, and it depends on something called a "zero-knowledge" proof.

The idea is that a "prover" has found a proof for a theorem and wants to let a "verifier" know that he knows the proof without revealing the proof itself. The verifier can ask a special question that requires the equivalent of a yes-or-no answer. If the prover really knows the proof, he can answer the question correctly every time it is asked.

If the prover doesn't know the proof, he has only a 50 percent of being right each time. After, say, a dozen tries, the chances of fooling the verifier get very small.

Neither the question not the possible answers give away even a hint of the proof itself—hence, the term zero-knowledge proof.

The concept of zero-knowledge proofs was first defined in 1985 by Silvio Micali and Charles Rackoff. A year later, Micali, Oded Goldreich, and Avi Wigderson took a major step forward by showing that such a scheme works for a large class of mathematical theorems.

The three researchers demonstrated the procedure for a mathematical coloring problem, which involves ensuring that no two linked points in certain networks of connected points have the same color.

Manuel Blum then showed how to give an efficient zero-knowledge proof for any mathematical theorem.

One of the more difficult steps, Blum noted, is finding the right question for the verifier to ask. Once this is done, a zero-knowledge scheme can handle any theorem posed within any logic system.

All a verifier finds out is that a theorem is provable and that the prover actually knows the proof. And because the prover has to use at least as many words as the proof itself contains, he gives away an upper limit for the proof's length.

To show how the scheme works, Blum chose an example from graph theory. Any network of points (or nodes) connected by lines (or edges) is called a graph. In Blum's example, the graph consists of a star-shaped pattern of lines linking 11 points.

The prover has found a continuous path among the links that passes only once through through each of the 11 points on the graph and returns to where it started. This special type of path is called a Hamiltonian cycle.

The prover's aim is to persuade a verifier that such a path is known without giving the verifier the slightest idea of how to construct the path.

To do this in Blum's example, the prover privately marks 11 nodes along the circumference of a circle and labels them randomly from 1 to 11. The nodes on the circle are then connected in the same way as the points in the original graph. That is, lines would join nodes 1 and 5, 2 and 6, and so on.

Deciding whether a particular graph—a network of points and connecting lines—has a Hamiltonian cycle is often difficult. This involves finding a continuous path along the links that passes only once through each of the graph's points and then returns to where it started. In this example, such a path exists through the points in the order 1, 5, 6, 2, 8, 4, 10, 11, 9, 3, 7, and then back to 1. For a zero-knowledge proof, the star-shaped graph (above) can be redrawn so that all the points fall on the circumference of an imaginary circle (below) yet the connecting lines still join the same points as in the original graph.

The resulting diagram is covered up by, say, an erasable opaque film like that used on some lottery or contest tickets.

The verifier can ask the prover to uncover the complete graph, which shows that all the points are properly linked, or she can ask to see the Hamiltonian cycle.

In the latter case, the prover erases enough of the film to reveal just the lines that make up the cycle. He can do this only if he knows the right path. However, because the nodes are still covered up, the verifier doesn't know the actual path from point to point. All she can verify is that a Hamiltonian cycle exists. This process can be repeated as many times as the verifier wishes.

Because the prover doesn't know whether the verifier will ask for the graph or the cycle, he has to be ready for either choice and therefore must know the cycle. Failure to produce either the correct graph or the cycle during any turn is equivalent to a wrong answer, and the verifier then knows that either the prover is lying or he doesn't actually have the proof.

As outlined, this scheme sounds somewhat cumbersome. But the opaque film used in the example can be replaced by encryption schemes to hide information. Thus, proof checking can be done electronically when the whole procedure is encoded as strings of binary digits. This makes it possible to use this concept for password protocols and in cryptological games like tossing a coin by telephone or exchanging secret keys.

And in the sometimes turbulent world of mathematics research, it gives a wary mathematician a way to claim credit for being the first to find a particular proof without the necessity of giving away the proof's details. All that someone else can find out, until the proof itself is finally revealed, is that a particular theorem is provable.

Form Plus Function

Nestled beside a national wildlife refuge, the Noyes Museum of Art in Oceanville, N.J., seemed an unlikely place for an exhibit featuring art rooted in mathematical concepts. Nonetheless, in 2006, its galleries (now closed at this location) featured works by four contemporary artists whose art had a strong mathematical element.

The Noyes Museum of Art in Oceanville, N.J. Photo by I. Peterson.

Called "Form + Function: Mathematics and Beyond in Contemporary Art," the exhibit featured artworks by Sol LeWitt (1928-2007), Steven Gwon, Mark Pomilio, and John Sims.

Born in 1928, Sol LeWitt was known for his conceptual art (see "Incomplete Open Cubes," "Puzzling Lines," "LeWitt's Pyramid," "Stairwell Drawing," "Squares and Stripes," "LeWitt's Complex Form," "Thirteen Geometric Shapes," "Garden Pyramid," "Cube Tower," "Floor Structure," and "Wall Pyramids"). 

"In conceptual art the idea or concept is the most important aspect of the work," LeWitt wrote in 1967. "When an artist uses a conceptual form of art, it means that all the planning and decisions are made beforehand and the execution is a perfunctory affair. The idea becomes a machine that makes the art."

LeWitt's series of vast wall drawings exemplified this approach. In effect, the artist conceptualized the work and provided the instructions—an algorithm—for what should appear on a wall. Assistants and volunteers then implemented the instructions.

For the Noyes exhibit, LeWitt contributed three wall drawings. Here are the instructions for these creations, each drawn in thick pencil on white walls.

Wall drawing #142: A twelve-inch grid inside an eight-foot square an increasing number of horizontal not straight lines from the left side.

Wall drawing #143: A twelve-inch grid inside an eight-foot square an increasing number of horizontal straight lines from the left side.

Wall drawing #167: A line from the center of the wall to the midpoint of top side, and a line from the midpoint to the right side.

Catalog cover, "Form + Function" exhibit, Noyes Museum of Art.

The instructions were curiously ambiguous and somewhat puzzling. Given just the instructions, I tried to imagine what each artwork would look like. (Try it yourself.) However, when I compared my imaginings with the actual works drawn on the walls, my images didn't quite match the reality. And it wasn't clear to me whether the instructions had been misinterpreted or were incomplete or whether the artist had provided additional guidance.

Steven Gwon's pieces typically consisted of colored pencil lines, hand drawn on sheets of finely ruled graph paper. The resulting sheets revealed spectral forests of subtly shaded lines, spaced at regular intervals and of precisely defined lengths. Seen from afar, these gently rendered patterns shimmered in the ambient light.

Gwon said that his drawings encapsulated days of the year, as recorded through numbers that measure time and space and through the colors of the spectrum—sunrises or sunsets; minutes, hours or days, months or years. The example on display, called Year, had 36 panels.

Pencil on Paper U by Steven Gwon. Courtesy of Steven Gwon.

Mark Pomilio's art wasn't explicitly tied to a grid. Instead, it explored, through layering and translucency, the geometry of growth and form. Pomilio likened his approach to the generation of a complex form from a single cell (or seed). His forms multiplied, grew, and overlapped to produce subtly complex, translucent landscapes of polygons, lines, and shadows, whether rendered in charcoal or deep, rich colors.

Family Circle VII by Mark Pomilio. Courtesy of Mark Pomilio.

Pomilio used his abstract works as ways to articulate, in a visual sense, profound recent developments in the life sciences, as seen in developmental processes and modeled by simple geometrical expressions.

Several large quilts provided an engaging introduction to John Sims and his visual ruminations on the digits of pi (see "Quilting Pi"). These square patterns mapped the decimal digits of pi to colors, starting from 3 at the center and spiraling outward from that point. Different choices of color led to intriguing variants—the same digits and arrangement in each case, but strikingly different visual effects.

Seeing Pi by John Sims. Courtesy of John Sims.

My favorite, however, was Sims's signature piece, which paired a representation of a tree with a branched, fractal structure (see "Fractal Roots and Artful Math"). It highlighted the connections that Sims saw among mathematics, art, and nature (and presented his own vision of growth and form). In different orientations, this dual image encoded a variety of relationships and concepts.

Mathematical Art Philosophy 101: With Titles (Square Roots of Tree, Mathematical Art Brain, and Tree Root of Fractal) by John Sims. Courtesy of John Sims.

"What is exciting about all this is that these individuals are making work using systems with innumerable applications," curator A. M. Weaver wrote in the catalog accompanying the exhibit.

Each artist, in his own way, alerted viewers to concepts and processes that bring together mathematics, art, and nature. Mathematics itself offers a multifaceted, solid frame on which to hang provocative creations of artistic imagination.

Originally posted November 20, 2006

Fractal Roots and Artful Math

The term "mathematical art" for many people might conjure up images of M.C. Escher's endless staircases, Möbius-strip ants, and mind-boggling tilings. Or it might remind you of the intimate intertwining of mathematics and art during the Renaissance with the development of perspective painting and eye-teasing stagecraft.

A view of the groundbreaking 2002 MathArt/ArtMath show at the Selby Gallery in Sarasota, Fla.

The realm of mathematical art is far wider and more diverse than many people realize, however. A groundbreaking 2002 exhibition at the Ringling College of Art + Design's Selby Gallery (now closed) in Sarasota, Fla., dramatically illustrated the broad range and depth of the burgeoning interaction between mathematics and art.

Titled MathArt/ArtMath, the exhibition was assembled by Kevin Dean, then director of the Selby Gallery, and John Sims, a mathematician and artist who taught at the Ringling School. Sims encouraged the linking of mathematics and art—in his own work, in the classroom, and by calling attention to the endeavors of others devoted to bringing about such interactions.

"My role as an artist is to encode mathematics in what I do," Sims remarked. "The mathematical art that I seek to develop combines mathematical language and analysis with the expressiveness and creativity of the process to make expressive visual theorems."

In constructing his signature piece, Square Roots of a Tree, Sims paired a representation of a tree with a branched fractal structure to highlight the tree-root relationship and interdependency that he sees between mathematics and art. In other orientations, his artwork becomes Tree Root of a Fractal (rotated 180 degrees) and Math Art Brain (rotated 90 degrees).

Square Roots of a Tree. Courtesy of John Sims.

Tree Root of a Fractal, Sims noted, "shows how the latent geometry of nature can inspire and support abstraction." See also "Form Plus Function."

Sims brought the same sort of sensibility to the classroom. Mathematical ideas inspire artistic creations. Conversely, "to see mathematically, one draws from creativity and intuition, as in the case with the art process itself," he said.

One sequence of artworks arose out of a study of the Pythagorean theorem (given a right triangle with sides a, b, and c, a² + b² = c²), particularly the theorem's manifestations in different guises at different times in history and in different cultures.

Holly's Rose: Artwork by Holly Brafflet as part of a course offered by John Sims at the Ringling School of Art and Design. Courtesy of John Sims.

It was a classroom journey, Sims said, that blended "the worlds, vocabularies, and strategies of mathematics and art into an interdisciplinary mixture that celebrates the interconnectedness of analysis and creativity, left brain and right brain, theory and practice, structure and expression, and the liberal arts and studio praxis."

Sims has a strong commitment to bringing art—especially mathematical art—to the public. To that end, he promoted the installation of a maze of pillars draped with murals in a Sarasota neighborhood, where visitors could view artworks created by local and internationally known artists and even find space to paint their own artistic impressions.

One ambitious scheme, Time Sculpture, involved installations scattered across the United States—familiar objects (vase, chess set, chair, clock, and so on) that are connected yet dispersed. Sims saw it as another sort of journey—one that maps "orbits from abstract places into diverse geographies, celebrating the search for cycles in both human and natural systems."

Sims's passion for making mathematical art known and accessible to the public led to the original MathArt/ArtMath exhibition at the Selby Gallery. The show represented a significant effort not only to illustrate the diversity of mathematical art and but also to illuminate its common threads.

The exhibition presented a broad spectrum of math-related paintings, prints, sculptures, fabrics, digital prints, electronic music, and videos. Euclidean geometry, Fibonacci numbers, the digits of pi, the notion of algorithms, concepts of infinity, fractals, and other ideas furnished the mathematical underpinnings.

The assembled artworks, carefully arranged to highlight similarities in theme, exemplified the diverse ways in which different artists can approach the same fundamental ideas, yet still reflect their mathematical essence.

One contribution from Sims was a visualization of pi's digits, in a digital video format—with music by composer Frank Rothkamm and the participation of Paul D. Miller, who is better known on the New York City scene and elsewhere as DJ Snoopy (see "Quilting Pi").

Originally posted June 10, 2002

Quilting Pi

When John Sims contemplates a number, he sees color and shape. And an intriguing, enigmatic number such as pi, the ratio of a circle's circumference to its diameter, conjures up vivid patterns that belong on quilts.

Starting with 3.14159265, the decimal digits of pi run on forever, and there's no discernible pattern to ease the task of compiling (or memorizing) these digits. Computer scientists have so far succeeded in computing 50 trillion decimal digits of pi.

Both a mathematician and an artist, Sims taught for many years at the Ringling College of Art + Design in Sarasota, Fla. He's passionately interested in the collision of mathematical ideas and visual culture.

Pi is one of the few mathematical constants that have successfully entered the pop-culture psyche, Sims noted. Pi has appeared as the title of movie, for instance, and as the name of a perfume.

A while ago, Sims created a visualization of pi's digits in a digital video format—with music by Frank Rothkamm and the participation of Paul D. Miller, who was better known on the New York City scene and elsewhere as DJ Spooky. In this visualization, each of the digits from 0 to 9 is represented by its own color on a vast grid of squares.

Seeing Pi by John Sims.

Working in base 2 and using the colors black and white, Sims then created Black White Pi. In base 3, using red, white, and blue, he made American Pi.

From left to right, Seeing Pi, American Pi, and Black White Pi. Courtesy of John Sims.

A second pi-based project involved a collaboration with conceptual artist Sol LeWitt (1928-2007). LeWitt's instructions were to put 1,000 straight lines inside a square. Sims achieved that result by dividing each side of the square into 10 parts (like the axes of a graph), labeling the divisions from 0 to 9, and drawing lines from a division on one side to a division on an adjacent side. The lines followed successive digits of pi from side to side, starting at the top and moving in a clockwise direction until the wall drawing had 1,000 lines.

Sims' former student, Brandon Styza, drew the lines. The result formed the basis for a LeWitt wall drawing in the math lounge at Wesleyan University.

In 2006, before heading for New York City, Sims completed a number of pi works, including several quilts that were constructed by an Amish quilting group in Sarasota. These artworks were on display at Sarasota's mack b gallery.

John Sims working with a group of Amish women to create a pi-based quilt. Courtesy of John Sims.

Sims started out with a drawing of pi's decimal digits on a square grid, with successive digits forming a clockwise spiral from the center.

A square spiral of the digits of pi. Photo by Tobey Albright.

In the gallery, this drawing was displayed with a phonograph that played a recording of Sims reciting the digits of pi in order. A second track presented the digits in German.

With each digit from 0 to 9 mapped to a different color (but not black or white), the central portion of the drawing was then converted into a striking, square quilt of colored patches, with a black border. Sims called the creation Pi sans Salt and Pepper.

Pi sans Salt and Pepper by John Sims. The square quilt is 8 feet wide. Photo by Tobey Albright.

In a variation on this pi-based theme, another quilt designed by Sims featured several, differently color-coded representations of pi. It was called Civil Pi Movement.

In this pi-based quilt, called Civil Pi Movement, the upper left unit shows the first 36 binary digits of pi (0 = white and 1 = black) and the lower right unit reverses the color scheme. The upper right unit shows the first 36 ternary digits of pi (0 = dark blue, 1 = red, and 2 = white) and the lower left unit uses a different color scheme (0 = green, 1 = red, and 2 = black). The center unit matches the center of Pi sans Salt and Pepper. The square quilt is 8 feet wide. Photo by Tobey Albright.

"The mathematical art that I seek to develop combines mathematical language and analysis with the expressiveness and creativity of the process to make expressive visual theorems," Sims said. "To see mathematically, one draws from creativity and intuition, as in the case with the art process itself."

See also "Fractal Roots and Artful Math" and "Form Plus Function."

Originally posted May 8, 2006

Welcome Ramada

 

Ramada, Welcome Garden, Santa Fe Botanical Garden, Santa Fe Botanical Garden, Santa Fe, New Mexico, 2021.

Photo by I. Peterson

Mountain Spirits

 

Dance of the Mountain Spirits I (detail) by Allan Houser. Santa Fe Botanical Garden, Santa Fe, New Mexico, 2021.

Photo by I. Peterson

Iced Claret Cup

 

Claret cup cactus (Echinocereus triglochidiatus), Santa Fe Botanical Garden, Santa Fe, New Mexico, 2021.

Photo by I. Peterson

Moon Shot

 

Santa Fe, New Mexico, 2021.

Photo by I. Peterson

Patterns and Randomness

When we see patterns—whether in the arrangement of stars in the sky (see "Spying Pi in the Sky") or in the distribution of guests at a dinner party (see "Party Games")—we are constantly tempted to think of these patterns as existing for a purpose and being the effect of a cause. Ramsey's theorem (see "Playing Fields of Logic") suggests otherwise. Patterns can, and indeed must, arise out of pure randomness (or chance).

In mathematics, in science, and in life, we constantly face the delicate, tricky task of separating design from happenstance. We must make decisions about the meaning of apparent coincidences, whether what we have before us is medical data showing an unusual cluster of cancers in a community, a sequence of events that suggests a conspiracy, or a peculiar arrangement of stars in the sky.

Seeing patterns among the stars: Draco and Ursa Minor. Library of Congress.

We detect eight stars in a straight line and think, "That can't be an accident." Is this pattern the result of some cosmic ordering driven by gravity? Is an unknown force involved? Is it a string of deliberately placed beacons for interstellar travel?

In the absence of an obvious explanation, the human tendency has been—and still is—to invoke supernatural forces, extraterrestrial visitors, or other fantastic beings and events to make sense of what we observe.

Humans are model builders, and the human mind is very good at identifying patterns and constructing theories. We are programmed to search for patterns and to invent explanations, and we find it difficult to imagine that patterns emerge from randomness.

As builders, humans can also create edifices on a vast range of scales, from the giant pyramids of ancient times to the intricate microscopic components of a computer's microprocessor. We can manipulate individual atoms to spell out tiny words on a silicon surface, and we can orchestrate the construction of giant skyscrapers and vast malls.

To do so, we design, make plans, create blueprints, organize labor, and marshal resources to create the order that we desire. In nature, however, that order and structure arises from randomness, and we face the puzzle of how the components of life assemble themselves without blueprints as guides.

Previously: Group Thoughts

Group Thoughts

Mathematical research is generally thought to be a solitary pursuit. You might even imagine a mathematician squirreled away in a dingy garret, an isolated wilderness cabin, or a sparsely appointed cubicle, thinking deeply, scrawling inscrutable equations across scraps of paper, to emerge from a self-imposed exile at last with a proof in hand.

A few mathematicians do spend their professional lives in solitary contemplation of a deep mathematical problem. In general, however, mathematical research is a remarkably social process. Colleagues meet constantly to compare notes, discuss problems, look for hints, and work on proofs together.

The abundance of conferences, symposia, workshops, seminars, and other gatherings devoted to mathematical topics attests to a strong desire for interaction.

Paul Erdős (1913-1996), perhaps more than any other mathematician in modern times, epitomized the strength and breadth of mathematical collaboration. Because he had no permanent home and no particular job, Erdős simply traveled from one mathematical center to another, sometimes seeking new collaborators, sometimes continuing a work in progress. His well-being was the collective responsibility of mathematicians throughout the world.

Paul Erdős (1913-1996). MAA Convergence Portrait Gallery.

"My brain is open," Erdős typically declared on stepping into a mathematician's office, and the work would begin. For him, doing mathematics was as natural as breathing, and he did if for more than 65 years.

Driven by the notion that life represents a cosmic struggle to uncover beautiful truths hidden away by a stubborn, contrary God, Erdős applied himself to his pursuit with frenetic zeal.

"A mathematician is a device for turning coffee into theorems," Erdős wryly remarked.

To Erdős, mathematics and its elements were more real than trees and grass, transcending reality and awaiting discovery. At the same time, though he did not like having possessions, Erdős was not an ascetic. He liked to eat well in good restaurants and stay in fine hotels when he got the chance.

A compassionate, generous, gentle man, he was well informed on almost any topic of conversation and deeply aware of the tragedies of world politics.

Erdős wrote hundreds of research papers on a wide range of mathematical topics. Especially astonishing was the extent to which he also worked with other mathematicians to produce joint papers.

Collaboration on such a scale had never been seen before in mathematics, and it has entered the folklore of the mathematical community. Of course, there's a characteristically mathematical way to describe this webbiness—a quantity called the Erdős number.

Mathematicians assign Erdős the number 0. Anyone who has coauthored a paper with him has the cherished Erdős number 1. As of August 2020, there were 512 such coauthors. Another 12,600 mathematicians have the Erdős number 2, because they wrote a paper not with Erdős himself but with someone who wrote a paper with Erdős.

People belonging to these two categories already encompass a significant proportion of all mathematicians in academia worldwide.

The Erdős number 3 goes to anyone who has collaborated with someone who has collaborated with someone who coauthored a paper with Erdős, and so on. Thus, any person not yet assigned an Erdős number who has written a joint mathematical paper with a person having Erdős number n earns the Erdős number n + 1..

Anyone left out of this assignment process has the Erdős number infinity.

Keeping track of these mathematical links has become a kind of game, punctuated by published, tongue-in-cheek explorations of the properties of Erdős numbers and the extent of mathematical links to the rest of the world.

Theoretical physicist Albert Einstein (1879-1955), for instance, has an Erdős number 2. Andrew Wiles, who in 1994 proved Fermat's Last Theorem, has an Erdős number no greater than 4.

It's possible to draw a collaboration graph in which every point represents a mathematician, and lines join mathematicians who have collaborated with each other on at least one published paper. The resulting tangle is one of the largest, most elaborate graphs available to mathematicians.

Sone scholars have conjectured that this monstrous graph snares nearly every present-day mathematician and has threads into all areas of mathematics, into computer science and physics, and even into the life sciences and social sciences.

This collaboration graph's breadth is astonishing and vividly demonstrates the vital role of collaboration in math and science.

Several decades ago, mathematician Jerrold W. Grossman took on the task of maintaining a comprehensive listing of mathematicians who have earned an Erdős number 1 or 2. "It's fun," Grossman said. "But more seriously, it shows that mathematical research is very webby, with almost everybody talking to people who talk to people."

Indeed, fascinating patterns emerge from the study of Erdős collaboration lists. For example, the average number of authors per research article in the mathematical sciences increased dramatically during Paul Erdős's lifetime.

About 70 years ago, more than 90 percent of all papers were solo works, according to Grossman. In more recent years, barely half of the papers were individual efforts.

In the same period, the fraction of two-author papers rose from less than one-tenth to roughly one-third. In 1940, virtually no papers had three authors. Now, more than 10 percent of all papers have three or more authors.

Erdős himself may have played a role in this relatively recent explosion of collaboration.

Previously: Dartboard Estimates

Next: Patterns and Randomness