Original Math Notes
All Seasons
Episode 407: Primacy--Interactive Computations--Explore the Math
Episode 407: Primacy
Discrete Fourier transform of the matrix formed from applying a combinatorial function over the Gaussian integers
Scene 5:
INT. CALSCI - CHARLIE'S OFFICE - DAY

Combinatorial matrix theory

                    AMITA
          I would prefer they stay focused on
          Combinatorial Matrix Theory.
Combinatorial Matrix Theory by Richard A. Brualdi and Herbert J. Ryser

Combinatorial matrix theory is a rich branch of mathematics that combines combinatorics (the enumeration, combination, and permutation of sets of elements and the mathematical relations that characterize their properties), graph theory (the mathematical study of the properties of the formal mathematical structures consisting of vertices and edges called graphs; discussed in the math notes for Episode 401, "Trust Metric"), and linear algebra (the study of linear sets of equations and their transformation properties).

The animation at the top of this page shows the discrete Fourier transform of the n x n matrix with matrix elements given by m_{a,b} = sigma_4(a+ib), where sigma_k(z) is the divisor function of order 4 (i.e., the sum of divisors to the fourth power) generalized to complex numbers (in this case, the Gaussian integers). Since the Fourier transform of a complex number is itself complex, the animation shows only the complex argument (also called the complex modulus), which is simply given by |x+iy| = sqrt(x^2+y^2). As the size n of the matrix increases, more and more beautiful structure is revealed. The structure corresponds to periodicities in the divisor function as well as the relative strengths of periodic components. The application of Fourier transforms to find periodicities in data is an extremely powerful tool that is very commonly used in signal- and image-processing applications.

The book pictured above, by Richard Brualdi and Herbert Ryser, is a classic text on combinatorial matrix theory. This book investigates in detail the theory of matrices with prescribed combinatorial properties, including mathematical objects called permanents and Latin squares (which are important in experimental design). The book ends by applying combinatorial arguments to prove classical algebraic theorems, including the so-called Cayley-Hamilton theorem (which states that an n×n matrix A is annihilated by its characteristic polynomial). The graph shown on the cover is known as the Shrikhande graph.

Regular graphs Petersen graph generalized quadrangle graph Möbius ladder graph antiprism graph 16-cell graph cubical graph prism graph complete graph utility graph octahedral graph cycle graph pentatope graph tetrahedral graph square graph triangle graph

In order to understand the significance of the Shrikhande graph, we must first discuss what it means for a graph to be regular. A regular graph of degree r is a graph all of whose vertices have the same number of edges incident on them. Regular graphs therefore have a high degree of symmetry, and include a number of particularly beautiful examples, such as those illustrated above.

There is a class of graphs known as strongly regular graphs that are even more symmetric than regular graphs. In a strongly regular graph, not only does each vertex have the same number of neighbors (usually denoted k), but every adjacent pair of vertices has the same number (usually denoted lambda) of common neighbors, and every nonadjacent pair of vertices has the same number (usually denoted mu) of common neighbors. A strongly regular graph on nu vertices is therefore said to have parameters (nu, k, lambda, mu). Strongly regular graphs are very special mathematical objects that have connections to other areas of mathematics, including group theory and statistics. One class of strongly regular graphs is the so-called lattice graphs Ln, whose vertices can be thought of as squares on an n×n chessboard, and whose edges can be thought of as pairs of squares that are connected by a possible move by a rook chess piece. It turns out that the lattice graphs are strongly regular, in particular L4, which is strongly regular with parameters (16, 6, 2, 2). Shrikhande established that there exists exactly one other strongly regular graph with those parameters, and that graph, illustrated below in another embedding, now bears his name.

Shrikhande graph
Scene 9:
EXT. DOWNTOWN STREET - CRIME SCENE - DAY

Alternate reality games

                   MEGAN
         Weyburn evidently came here to play
         something called an Alternate
         Reality Game-- Privacy?

They head into the building--

                   AMITA
         Primacy.

                   MEGAN
         You know it?

                   AMITA
         I play it.

An alternate reality game (ARG) projects a fictional story onto the real world. To progress through the story in an alternate reality game, various challenges must be overcome or problems must be solved. The following list summarizes a number of well-known alternate reality games:

In the recent alternate reality game "Why So Serious," which supports the upcoming Batman film The Dark Knight, Batman's nemesis, The Joker, is collecting minions for his nefarious purposes. Toward this end, various puzzles and scavenger hunts are provided to his "clowns" to test their worthiness. The cluses for this game are distributed in actual locations across the United States, and dozens of teams must cooperate in order to locate and solve them.

Scene 12:
EXT. DOWNTOWN ROOFTOP - CRIME SCENE - DAY

Evolutionary algorithms

                    CHARLIE
          I could adapt an evolutionary
          algorithm to search the game
          history for abnormally aggressive
          activity.

          My algorithm would recognize this
          typical activity and ignore it,
          seeking out abnormal actions.
          Think of a pond--

AUDIENCE VISION

An idyllic pond-- plants, water, insects, birds, frogs, etc.
All look healthy and in balance. A bird eats an insect.

                    CHARLIE (V.O.) (cont'd)
          A pond is a healthy ecosystem where
          predators and prey are in balance--
          however, if an outside predator is
          introduced--

A bird is snatched by something unseen. As more birds
disappear, insects go unchecked and devour the plants.

                    CHARLIE (V.O.) (cont'd)
          The ecosystem changes. An
          evolutionary algorithm highlights
          these abnormal alterations--

In general, the field of evolutionary computation describes the use of iterative stochastic optimization algorithms. Such processes are often inspired by biological mechanisms of evolution, and particular approaches to evolutionary computation go under names such as evolutionary programming, evolution strategies, genetic algorithms, and genetic programming. The term stochastic optimization refers to the minimization (or maximization) of a function in the presence of randomness in the optimization process. The basic idea is to try to mimic a simple picture of natural selection in order to find a good algorithm. Common methods of stochastic optimization include direct search methods (such as the Nelder-Mead method), stochastic approximation, stochastic programming, and miscellaneous methods such as simulated annealing and genetic algorithms. Alert readers will recall that we have already encountered and applied the evolutionary computation method known as differential evolution to the optimal placement of police units in our write-up for Episode 401 "Trust Metric."

There are a many different types of evolutionary computation and genetic algorithms. In particular, the generic algorithm approach, developed by John Holland in 1975, created an electronic organism in the form of a binary string (chromosome), and then used genetic and evolutionary principles of fitness-proportionate selection for reproduction (including random crossover and mutation) to search enormous solution spaces efficiently. So-called genetic programming languages apply the same principles, using an expression tree instead of a bit string as the "chromosome."

Scene 20:
INT. CALSCI - CHARLIE'S OFFICE - DAY

The Higgs boson

                    LARRY
          Well, I have received a rather tantalizing
          offer to join the D Zero team searching
          for the Higgs boson.

                    CHARLIE
          Well all right.  The God Particle.  Which
          would be a continuation of your spiritual
          seeking as well as your quest for a
          Unified Theory?

                    LARRY
          Faith in science is still faith, is
          it not?

                    AMITA
          Now that's very cool, Larry, I think you
          should continue with your search for
          supersymmetric particles.

                    LARRY
          You know, smashing protons at 99.99 %
          of the speed of light-- all to locate
          a single fragment which would move
          us one step closer to unifying all
          physics, explaining how the Old
          One created the universe-- what
          could be more spiritual?
Animation of Higgs emission

There are four fundamental forces in the universe: gravitational, electromagnetic, weak, and nuclear. For more than the last hundred years, physicists have sought to unite the description of these four forces. Einstein himself devoted a substantial part of his life to this goal. Not long after the rise of quantum mechanics, quantum field theory was born. It was applied to microscopic phenomena that involve electrons and photons. The predictions of this theory (quantum electrodynamics) agree with experimentally measured values to astonishing precision. The inclusion of the weak and the nuclear force in quantum field theory resulted in a framework known as the standard model--a beautiful theoretical structure that unites three of the known forces of the world. The creation and developments of the standard model took physicists decades, and resulted in the disbursement of a number of Nobel Prizes along the way.

While many aspects of the standard model have been experimentally confirmed to good precision, one of the main unconfirmed aspects of the theory is the existence (and the properties) of the so-called Higgs boson. This particle is a very important theoretical ingredient of the theory, so finding it in nature is necessary to ensure the full correctness of the standard model. Despite substantial international efforts, the Higgs particle has not been found in accelerator experiments. The D0 experiments currently conducted at the Fermi National Accelerator Laboratory (Fermilab) in Batavia, Illinois, possibly have the capacity to detect indications of the Higgs boson. The LHC (large hadron collider) at CERN, which will begin experiments in mid-2008, will conduct various experiments to find the Higgs particle and measure its properties. Therefore, within the framework of well-established scientific theories, the Higgs particle remains one of the most important--but also the most elusive--components.

Scene 20:
INT. FBI - BULLPEN - CONTINUOUS

Trivial or deep?

                    LARRY
          You know, smashing protons at 99.99 %
          of the speed of light-- all to locate
          a single fragment which would move
          us one step closer to unifying all
          physics, explaining how the Old
          One created the universe-- what
          could be more spiritual?

                    CHARLIE
          Not a trivial activity.

To a mathematician, the word trivial describes a result or theorem that is mathematically obvious (for example, is true by definition). More generally, trivial is used to describe any result that requires little or no effort to derive or prove. The word originates from the Latin trivium, which was the lower division of the seven liberal arts in medieval universities (cf. quadrivium).

Examples of trivial mathematical structures include trivial basis, trivial bundle, trivial group, trivial loop, trivial module, trivial representation, trivial ring, and trivial topology.

According to the Nobel-Prize-winning physicist Richard Feynman, mathematicians designate any theorem as trivial once a proof has been obtained--no matter how difficult the theorem was to prove in the first place. There are therefore exactly two types of true mathematical propositions: trivial ones, and those that have not yet been proven.

The opposite of a trivial theorem is a deep theorem. Qualitatively, a deep theorem is a theorem whose proof is long, complicated, difficult, or appears to involve branches of mathematics that are not obviously related to the theorem itself. The quadratic reciprocity theorem in number theory is sometimes cited as an example of a deep theorem.

References

Brualdi, R. and Ryser, H. J. Combinatorial Matrix Theory. New York: Cambridge University Press, 1991.

CERN. "LCH - The Large Hadron Collider." http://lhc.web.cern.ch/lhc/

Fermi National Accelerator Laboratory. "The D0 Experiment." http://www-d0.fnal.gov/

Feynman, R. P. and Leighton, R. "A Different Set of Tools." In 'Surely You're Joking, Mr. Feynman!': Adventures of a Curious Character. New York: W. W. Norton, pp. 69-72, 1997.

Nobel Foundation. "The Nobel Prize in Physics 2004." http://nobelprize.org/nobel_prizes/physics/laureates/2004/public.html

Shanks, D. "Is the Quadratic Reciprocity Law a Deep Theorem?" §2.25 in Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 64-66, 1993.

Shrikhande, S.-C. S. "The Uniqueness of the L2 Association Scheme." Ann. Math. Stat. 30, 781-798, 1959.

 
Wolfram: Creators of Mathematica, Leaders in Math & Computation
Wolfram|Alpha