Monthly Archives: January 2010

Fundamental Examples

It is not unusual that a single example or a very few shape an entire mathematical discipline. Can you give examples for such examples? 

I’d love to learn about further basic or central examples and I think such examples serve as good invitations to various areas.

I asked this question over mathoverflow and it yielded around 100 examples. They are not equally fundamental and they are not equally suitable to be regarded as “examples,” but overall it is a very good list.  If you see some important example missing please, please add it.  Here are the examples classified to areas. (Of course, sometimes, the same example may fit several areas.)

Logic and foundations:

\aleph_\omega (~1890),  Russell’s paradox (1901), Halting problem (1936), Goedel constructible universe L (1938), McKinsey formula in modal logic (~1941), 3SAT (*1970), The theory of Algebraically closed fields (ACF) (?),



Brachistochrone problem (1696), Ising model (1925), The harmonic oscillator (?), Dirac’s delta function (1927), Feynman path integral (1948),

Real and Complex Analysis:


Continue reading

Michael Schapira: Internet Routing, Distributed Computation, Game Dynamics and Mechanism Design II

This post is authored by Michael Schapira. (It is the second in a series of two posts.)

In thse two post, I outline work on Internet routing and sketch important areas for future work, both on routing itself and, more broadly, on mechanism design, game theory and distributed computation.

A brief reminder from post 1:

The Internet comprises administrative domains known as Autonomous Systems (ASes), which vary in size, from large (multi)national networks to small networks servicing schools or small businesses. The task of establishing routes between ASes, called interdomain routing, is currently handled by the Border Gateway Protocol (BGP)—the core routing protocol of the Internet. BGP is one of the most critical pieces of the Internet’s infrastructure and can be regarded as the glue that holds the Internet together.

We brefly mentioned two main challenges in this area. The first is the quest for network stability, and the second was giving  agents incentives to “behave well”. We will discuss here these challenges in more detail.  

Challenge I: The Quest for Network Stability

Informally, a “stable state’’ is a global routing state that, once reached by BGP, remains unchanged. Formally, a stable state is an assignment of routes R1,…,Rn to the n source nodes (d is assigned the “empty route’’ Rd=Ø) such that for every node i (1) there is a node j such that Ri=(i,j)Rj, where (i,j) Rj is the route that has (i,j) as a first link and then follows Rj to d; and (2) for every node j such that Ri≠(i,j)Rj, and (i,j)Rj is simple, it holds that Ri >i (i,j)Rj.

Continue reading

Randomness in Nature II

In a previous post we presented a MO question by Liza about randomness:

 What is the explanation of the apparent randomness of high-level phenomena in nature?

1. Is it accepted that these phenomena are not really random, meaning that given enough information one could predict it? If so isn’t that the case for all random phenomena?

2. If there is true randomness and the outcome cannot be predicted – what is the origin of that randomness? (is it a result of the randomness in the micro world – quantum phenomena etc…)

Before I give the floor to the commentators, I would like to mention a conference on this topic that took place in Jerusalem a year ago. The title was “The Probable and the Improbable: The Meaning and Role of Probability in Physics” and the conference was in honor of Itamar Pitowsky. Let me also mention that  the Wikipedia article on randomness is also a good resource.

Here are some of the answers offered here to Liza’s question.

Qiaochu Yuan

One way to think about what it means to say that a physical process is “random” is to say that there is no algorithm which predicts its behavior precisely which runs significantly faster than the process itself. Morally I think this should be true of many “high-level” phenomena. Continue reading

Polymath5 – Is 2 logarithmic in 1124?

 Polymath5 – The Erdős discrepancy problem – is on its way.

Update (September 2015): Terry Tao have now solved Erdos discrepancy problem and proved that indeed the discrepancy tends to infinity. See also this blog post on Tao’s blog.

Update: Gowers’s theoretical post marking the official start of Polymath 5 appeared.

Update (February 2014): Boris Konev and Alexei Lisitsa found a sequence of length 1160 of discrepancy 2 and proved that no such sequence of length 1161 exists.
A SAT Attack on the Erdos Discrepancy Conjecture
The abstract reads: “We show that by encoding the problem into Boolean satisfiability and applying the state of the art SAT solvers, one can obtain a sequence of length 1160 with discrepancy 2 and a proof of the Erdos discrepancy conjecture for C=2, claiming that no sequence of length 1161 and discrepancy 2 exists. We also present our partial results for the case of C=3. See also this post. So the title of this post could be revised to: Is 2 logarithmic in 1160? (My conjecture is that 2 represents the square root of log 1160.) Followups:  See also this post Practically P=NP? on GLL, and Jacob Aron’s New Scientist’s article Wikipedia-size maths proof too big for humans to check.  On GLL, Dick and Ken devoted the third Hebrew letter ‘Gimel’ for C.


Original post

After several discussion threads, polymath5 devoted to Erdos’s discrepency problem is on its way on Gowers’s blog. While a theoretical post  with several possible attacks on the problem is planned, there is intensive experimental activity. The picture above shows a sequence of +/- signs length 1124 with discrepency 2: namely on every arithmetic progression of the form d, 2d, 3d, … where all terms are between 1 and 1124 the gap between the number of  ‘+’s and the number of  ‘-‘s is at most two.  The present hopes from these experiments are described in this paragraph:

Continue reading

Translation, Machine Translation, and a Crowded Seminar


I gave in several places a talk entitled “Analytic and Probabilistic Properties of Boolean Functions.” This is a fairly large area so the talks can differ quite a bit. The lecture at the NYU CS theory seminar was described over a Chinese blog entitled (according to the automatic translation) “Notes from Math Library”.  The posting is in Chinese and I used Google translation which gave me this:

Gil Kalai’s Seminar

Hebrew University of Jerusalem last Thursday, and Yale University professor Gil Kalai come Courant Institute speaking seminar. You may have some recollection of the name, because I have a Notes from “Test Your Intuition” in reference to his blog “Combinatorics and More”.

Usually during the same period of the “theory seminar”, where more than 15 people are already rare, but this time Prof. Kalai speaking seminar attracted 38 people to come. Usually there is space left in the room suddenly a full-house, there are several people sitting listening to underground.

Prof. Kalai gave a three guess one of the more accessible and interesting, you can talk about here…

and here is a small expert from the Hebrew translation:

בדרך כלל בתקופה המקבילה של סמינר “תיאוריה”, שבו יותר מ -15 אנשים כבר נדיר, אבל הפעם פרופ ‘קלעי מדבר הסמינר נמשך 38 אנשים לבוא. בדרך כלל יש מקום השמאלי בחדר פתאום הבית מלא, יש כמה אנשים יושבים האזנה תת קרקעית.

פרופ ‘נתן קלעי שלוש משער אחד נגיש יותר ומעניין, אתה יכול לדבר על זה כאן.

Perhaps you can look at the Chinese version and test how good the translations are.  One thing that I liked about the English translation is that it refers to my conjectures as “guesses”. Certainly, this shows that the Google-translation involves deep understanding. (Here is a blog description of a similar lecture at LA.)  One of the “guesses” refers to old conjectures by Itai Benjamini, Oded Schramm and myself about noise stability of monotone Boolean functions in TC0. I will discuss these conjectures in a later post. 

So what are these people listening to the talk  “underground” about? I will explain just after the dividing line.  Continue reading

Rodica Simion: Immigrant Complex

Rodica Simion immigrated to the United States from Romania. She was a Professor of Mathematices at George Washington University untill her untimely death on January 7, 2000. Her poem  “Immigrant complex” appeared in : “Against Infinity”, An Anthology of Contemporary Mathematical Poetry, edited by Ernest Robson and Jet Wimp, 1979, p. 66. Published by Primary Press, Parker Ford, PA, and Jet Wimp, Drexel University.

I have a
not simplicial (it is-in fact-
not a cell-complex
(my cells are
not a CW

(I have no com-
plexion no weight

it is a

my thinking is of
class C-one even

it does not matter:
my speech
approximates it by
linear functions
my talk (being merely
polygonal) wastes
C-n (n  > > 0)
 Continue reading 

Futures Trading as a Game of Luck

A recent interesting article by Ariel Rubinstein entitled “Digital Sodom” (in Hebrew) argues that certain forms of  futures trading (and Internet sites where these forms of trading take place) are essentially gambling activities. 

The issue of “what is gambling” is very intereting. In an earlier post entitled “Chess can be a game of luck” the interesting question regarding “games of luck” and “games of skill” was discussed. It was argued that for a betting game, if, over time, for all players (or even for most players), the expected gains are negative, then we can regard the game as primarily a game of luck. (The claim is that this is a reasonable interpretation of the current law, even if not the only possible interpretation.)

Continue reading