You are here

Inevitable Randomness in Discrete Mathematics

József Beck
Publisher: 
American Mathematical Society
Publication Date: 
2009
Number of Pages: 
250
Format: 
Paperback
Series: 
University Lecture Series 49
Price: 
59.00
ISBN: 
9780821847565
Category: 
Monograph
[Reviewed by
William J. Satzer
, on
11/10/2009
]

The traditional approach of mathematicians and computer scientists to complexity, the general theory of computational complexity, focuses on very general classes such as P and NP. In this book József Beck takes on the big subjects of randomness and complexity, but he has in mind a much different approach. He focuses instead on carefully chosen concrete examples. The overall objective of the book is to identify examples, supported by proofs, of the rather vague complexity law:

  • Discrete systems are either “simple” or they exhibit “advanced pseudorandomness” with or without constraints (even when there is no apparent independence), and
  • Roughly speaking, a priori probabilities often exist, even when there is no intrinsic symmetry.

Much of the book is devoted to the work of giving meaning and substance to this law. The result is unusual, idiosyncratic, and thoroughly intriguing.

The book is divided into three sections. The first is called “Reading the shadows on the wall and formulating a vague conjecture.” Beck begins by collecting data for “advanced pseudorandomness,” largely in number theory: prime numbers and the Riemann hypothesis, normal numbers and apparent randomness in digit sequences, and the 3n + 1 (or Collatz) conjecture, among others.

The Principle of Insufficient Reason is the major topic of one chapter. It states that if you have no grounds whatsoever for believing that any one of n mutually exclusive events is more likely to occur than any other, then you should assign a probability of 1/n to each. (For some arguments – in the realm of prime numbers, for example, a variation is necessary — equiprobability is replaced by probability 1/log n that a given n is a prime.) Massive computational evidence suggests the success of this principle in “proving” that √2 is a normal number, that the sequence (3/2)n is uniformly distributed modulo one, and that the 3n + 1 conjecture is true. While Beck can supply no support for the Principle of Insufficient Reason in number theory, he does so in the context of combinatorics and real game theory. These are the subjects of Parts 2 and 3 of the book.

The first section of the book would be entertaining reading for anyone with a decent background in undergraduate mathematics. The other two sections are aimed more at specialists. The third part, in particular, has new results about graph games. Beck says that his book is self-contained, and mostly it is, though it’s a wild ride. This is more monograph than textbook; it has no exercises. It also has no index and seriously needs one.


Bill Satzer (wjsatzer@mmm.com) is a senior intellectual property scientist at 3M Company, having previously been a lab manager at 3M for composites and electromagnetic materials. His training is in dynamical systems and particularly celestial mechanics; his current interests are broadly in applied mathematics and the teaching of mathematics.

Reading the shadows on the wall and formulating a vague conjecture

  • Complex systems
  • Collecting data: Apparent randomness of digit sequences
  • Collecting data: More randomness in number theory
  • Laplace and the principle of insufficient reason
  • Collecting proofs for the SLG conjecture

More evidence for the SLG conjecture: Exact solutions in real game theory

  • Ramsey theory and games
  • Pratice session (I): More on Ramsey games and strategies
  • Practice session (II): Connectivity games and more strategies
  • What kind of games?
  • Exact solutions of games: Understanding via the equiprobability postulate
  • Equiprobability postulate with constraints (endgame policy)
  • Constraints and threshold clustering
  • Threshold clustering and a few bold conjectures

New evidence: Games and graphs, the surplus, and the square root law

  • Yet another simplification: Sparse hypergraphs and the surplus
  • Is surplus the right concept? (I)
  • Is surplus the right concept? (II)
  • Working with a game-theoretic partition function
  • An attempt to save the variance
  • Proof of theorem 1: Combining the variance with an exponential sum
  • Proof of theoem 2: The upper bound
  • Conclusion (I): More on theorem 1
  • Conclusion (II): Beyond the SLG conjecture
  • Dictionary of phrases and concepts
  • References