Math in the Media 1204

Math in the Media

December 2004

IT and the Riemann Hypothesis
Gödel's Theorem on ABC News
Making wavelets in the art world

$*$ IT and the Riemann Hypothesis. "What is the Riemann Hypothesis and why Should I Care?" is the provocative title of a piece by Robin Bloor posted at IT-Director.com on October 5, 2004. The site "provides IT decision makers with a one stop source of all current IT news, information, analysis and advice." (IT = Information Technology). Naturally, there is no attempt at a correct statement of the Riemann Hypothesis ("Without bothering to state the details, it is a proposed formula that calculates the number of primes less than a given number") but the reason why IT decision makers might be concerned is the "worrying predictions that if the Riemann Hypothesis is confirmed mathematically, then most of the encryption schemes we use in commerce and government will suddenly be vulnerable ..." together with news of its possible confirmation by Louis de Branges and perhaps by others. The risk for IT is "if the mathematics surrounding the solution reveals quicker ways to factorize numbers. Actually even then it will only matter if it reveals much quicker ways to factorize numbers." Because public-key cryptography "is based on the product of prime numbers. The fundamental idea is that it is very difficult to find factors for a number that is created by multiplying two prime numbers together. It's easy to multiply the numbers together but very difficult to find out what they were if you're only given the result." But not to worry: "Strange as it may seem (if you never studied Mathematics) there are mathematical relations that can be used to create encryption that can be proved to be unbreakable. The real problem is that we founded the early encryption on a technique that wasn't provably unbreakable." Bloor's piece is available online.

$*$ Gödel's Theorem on ABC News. John Allen Paulos, in his "Who's Counting" column on the ABC News website, posted "Complexity, Randomness and Impossible Tasks" on November 7, 2004. Paulos starts with algorithmic complexity. He invites us to compare the two sequences

(A) 0010010010010010010010010010010010010010010 ... 

(B) 1000101101101100010101100101111010010111010 ...

and asks: "Why is it that the first sequence of 0's and 1's ... is termed orderly or patterned and the second sequence random or patternless?" As a quantitative answer, he proposes Greg Chaitin's definition: The (algorithmic) complexity of a sequence of 0's and 1's is the length of the shortest computer program that will generate the sequence. The program for (A) could be "print 0,0,1, repeat." But for (B) it is quite possible that the only way to generate the sequence is to spell it out: "print 1,0,0,0,1,0,1,1,..." Paulos continues: "We define a sequence to be random if and only if its complexity is (roughly) equal to its length; that is, if the shortest program capable of generating it has (roughly) the same length as the sequence itself." If the only way to generate (B) is to spell it out, (B) is a random sequence. Next Poulos introduces us to the "Berry sentence," which he attributes to Betrrand Russel, 1908. Find the smallest whole number that requires, in order to be specified, more words than there are in this sentence. "The paradoxical nature of the task becomes clear when we realize that the Berry sentence specifies a particular whole number that, by its very definition, the sentence contains too few words to specify." Now the big step: "What yields a paradox about numbers can be modified to yield mathematical statements about sequences that can be neither proved nor disproved." A formal mathematical system can be encoded as a computer program P. As P runs, it generates all the possible theorems which can be proved in that system. "Now we ask whether the system is complete. Is it always the case that for a statement S, the system either proves S or it proves its negation, ~S?" Poulos explains Chaitin's argument, which involves imagining the the following Berry-like task for the program: Generate a sequence of bits that can be proved to be of complexity greater than the number of bits in this program. "The program P cannot generate such a sequence, since any sequence that it generates must, by definition of complexity, be of complexity less than P itself." It follows that "statements of complexity greater than P's can be neither proved nor disproved by P." This is Chaitin's new, quantitative twist on Gödel's Theorem. Since any formal mathematical system has a certain finite complexity, it must allow statements which can be neither proved nor disproved, "a limitation affecting human minds as well as computers."

$*$ Making wavelets in the art world. "Computers confront the art experts" is a piece by Philip Ball posted on November 22, 2004 at Nature's online site news@nature.com. Ball's subheadline reads: "Automated method seems to spot forgeries as well as a connoisseur does."

Siwei Lyu, Dan Rockmore, Hany Farid and the Madonna with Child with Saints at Dartmouth's Hood Museum. The team's wavelet analysis disentangled authorship of the six heads in the painting. Photo by Joseph Mehling, from Dartmouth News, used with permission. Click on image to enlarge.

The forgeries are in paintings, and the method in question, devised by Hany Farid, Dan Blackmore and Siwei Lyu of Darmouth University, uses wavelet analysis to characterize the "hand" of an artist. Ball describes it as follows: "They scan a picture at high resolution and then use the wavelet technique to decompose the picture into sets of vertical, horizontal and diagonal lines. ... From the mathematical distribution of lines, the researchers calculate a set of numbers that characterizes each picture. These numbers can be regarded as coordinates in a multi-dimensional space, like a grid reference. If two images share similarities in their use of line, the points in space defined by their coordinates will lie close together, even if the scenes depicted are totally different." When the Dartmouth team tried their technique on a set of 13 landscapes (genuine and imitation) by Brueghel, "the points corresponding to the eight pictures deemed to be authentic all sat together in a cluster, and the fakes were further away." Then they turned to the Madonna and Child with Saints, attributed to the Italian Renaissance painter Perugino, in the collection of the Hood Museum at Dartmouth. There are four Saints in the picture, so six heads in all. Applying their analysis to the heads, Farid and his collaborators found no fewer than four painters at work. Three of the heads are by three different painters; the three others are by a fourth, "perhaps Perugino himself," as Ball puts it. Article available online.

-Tony Phillips
Stony Brook

$*$ Math in the Media Archive