Monthly Archives: May 2009

Some Philosophy of Science

The Bayesian approach to the philosophy of science was developed in the first half of the twentieth century. Karl Popper and Thomas Kuhn are twentieth-century philosophers of science who later proposed alternative approaches.

It will be convenient to start with the Bayesian approach since we already talked about probability and Thomas Bayes in this post. The Bayesian approach (mainly associated with Ramsey and Savage) can be regarded as a verification-based philosophy of science; it is based on different scientists gradually updating, according to new empirical evidence, their (different) prior (subjective) probabilities of scientific explanations and theories, until the cumulative evidence is strong enough to reach a common conclusion.

One difficulty with the Bayesian approach is that in cases of disagreement, there are also disagreements on the interpretation of the evidence.

Bayesian view does not give a way to test a scientific theory but rather to update our beliefs in the theory given new evidence. In practice, scientific theories primarily explain existing observations. For example, the main motivation of Newtonian mechanics and the main support for its validity was the explanation of Kepler’s laws. Kepler’s laws concerning the elliptic orbits of planets around the sun were discovered seventy years before they were explained by Newtonian mechanics.

  

 

              Karl Popper                          Thomas Kuhn

 Popper is famous for basing philosophy of science on the notion of falsification. According to Popper, the mark of a theory as scientific is falsifiability: the possibility to empirically refute the theory – in principle. This is in contrast with other approaches that can be viewed as basing philosophy of science on confirmation or verification. Famously, two principal examples of non-scientific theories according to Popper are the Marxist theory of capital and Freudian psychoanalysis.  

If the Bayesian approach, like approaches based on verification, suggests that the optimal way for a scientific theory to proceed is by making safe conjectures which may lead to small incremental progress, Popper’s approach suggests making bold and risky conjectures. One concern about practical implication of the Popperian approach is the fact that bold conjectures and theories that pass the falsifiability test are of little value if they are absurd or simply false to begin with.

Critics assert that neither Popper’s theory nor earlier approaches based on verification give a proper description of how science is practiced. Also, they have limited normative value regarding how science ought to be practiced. It is especially difficult to use the insights from philosophy of science for scientific theories under development.

Thomas Kuhn is famous for his notions of paradigm shifts and scientific revolutions. According to Kuhn, science is normally carried out inside a certain paradigm that is shared by a community of scientists, and it is furthermore characterized by “paradigm shifts,” which occur when the current paradigm is no longer capable of explaining the new evidence.  Kuhn referred to the process of switching from the common paradigm to a new one as a “scientific revolution.” An important example of a scientific revolution analyzed by Kuhn is the shift from Newtonian mechanics to Einstein’s theory of relativity. Continue reading

A Workshop for Advanced Undergraduate Students, Sept 6-17 2009

סדנא לתלמידי בוגר מצטיינים במתמטיקה

מכון איינשטיין למתמטיקה, האוניברסיטה העברית בירושלים

 

יום א’ י”ז אלול – יום ה’ כ”ח אלול תשס”ט

 

6-17/9/09

 

המכון למתמטיקה של האוניברסיטה העברית מזמין תלמידי מתמטיקה מצטיינים המסיימים שנה ב’ או ג’ של לימודיהם במוסדות להשכלה גבוהה, ומעוניינים להמשיך במחקר מתמטי, לסדנה בת שבועיים שתתקיים בקמפוס ספרא של האוניברסיטה העברית בגבעת רם, ירושלים, בשבועיים שלפני ראש השנה תש”ע.

  Continue reading

Answer to Test Your Intuition (3)

Question: Let X=[0,1]^d be the d-dimensional cube. Turn X into a torus T^d by identifying opposite facets. What is the minumum (d-1)-dimensional volume f(d) of a subset Y of X which intersects every non-trivial cycle in T^d.

Answer: Taking Y to be all points in the solid cube with one coordinate having value 1/2, gives you a set Y that seperates all cycles and has (d-1)-dimensional volume equals d. It is not difficult to prove that f(d) \ge C\sqrt d. Guy Kindler, Ryan O’donnell, Anup Rao and Avi Wigderson proved the existence of Y which seperates all cycles with vol(Y) =O(\sqrt d). A simpler argument was found by Noga Alon and Boaz Klartag.  For an even simpler treatement of this result along with several discrete analogs see this paper by Noga.

How Large can a Spherical Set Without Two Orthogonal Vectors Be?

spherical

The problem

Witsenhausen’s Problem (1974): Let A be a measurable subset of the d-dimensional sphere S^d = \{x\in {\bf R}^{d+1}:\|x\|=1\}. Suppose that A does not contain two orthogonal vectors. How large can the d-dimensional volume of A be?

 

A Conjecture

Conjecture: The maximum volume is attained by two open caps of diameter \pi/4 around the south pole and the north pole.
For simplicity, let us normalize the volume of S^d to be 1.

 

What is known

What is known The Frankl-Wilson theorem (the version described in the previous post) gives the asymptotic bound Vol(A) \le 2^{(H(1/4)-1)n}=(1.2...)^{-d}, why?
Consider the set C_n=(1/\sqrt{n})\{-1,1\}^n. (And suppose that n=4p where p is a prime, and d+1=n.)  C_n is a subset of S^d.

Let A be a subset of S^d not containing two orthogonal vectors. Now, the intersection of every rotation of A with C_n has at most 4{{n} \choose {0}}+{{n}\choose {1}}+\dots+{{n}\choose{p-1}} elements.

This gives Vol(A) \le (4{{n} \choose {0}}+{{n}\choose {1}}+\dots+{{n}\choose{p-1}})/2^n and implies the asymptotic bound we described.

This is a beautiful application of the Frankl-Wilson theorem which goes back essentially to the original paper.
(If d+1 is not of that form we can suppose that n is the largest integer of the form n=4p smaller than or equal to d+1, and embed C_n in S^d by adding extra n-d coordinates and setting them to zero. Using the density of primes we obtain the required result.)

But we want more!

The proposed example has volume which assymptotically behaves like (1/\sqrt{2})^n.

What standard isoperimetry gives

If we assume that the angle between every two points in A is less than \pi/2, then a standard isoperimetric theorem (due to P. Levi) asserts that the volume of A is maximized by an open cap of radius \pi/4. But this is a stronger assumption.

Other methods?

Frankl-Rodl theorem gives weaker (but still exponentially small) bounds. The linear programming method for codes may lead to exponentially small bounds. [Update: see comment by Frank Vallentin.]

Can the polynomial method help (further)?

I think that the polynomial method (the method we presented to prove Frankl-Wilson’s theorem) is the best avenue for better results. Can it give better results? This is something we should discuss. We should try to replace vectors with plus-minus one entries by more general vectors, perhaps with some weights, and give it a try. So far, no one has succeeded, but I do not know why (and I don’t know if anyone has tried sufficiently hard). The ad-hoc trick from the proof of Frankl-Wilson seems to be one thing that does not generalize so nicely.

Ideas, comments are most welcome!

Extremal Combinatorics VI: The Frankl-Wilson Theorem

flute

Rick Wilson

The Frankl-Wilson theorem is a remarkable theorem with many amazing applications. It has several proofs, all based on linear algebra methods (also referred to as dimension arguments). The original proof is based on a careful study of incidence matrices for families of sets. Another proof by Alon, Babai and Suzuki applies the “polynomial method”. I will describe here one variant of the theorem that we will use in connection with the Borsuk Conjecture (It follows a paper by A. Nilli).  I will post separately about more general versions, the origin of the result, and various applications. One application about the maximum volume of spherical sets not containing a pair of orthogonal vectors is presented in the next post.

Let n=4p and suppose that p is a prime.

Theorem: Let \cal F be a subset of \{-1,1\}^n with the property that no two vectors in \cal F are orthogonal. Then |{\cal F}| \le 4({{n} \choose {0}}+{{n}\choose {1}}+\dots+{{n}\choose{p-1}}).

We will prove a slightly modified version which easily implies the Theorem as we stated it before:

Let \cal G be the set of vectors (x_1,x_2,\dots,x_n) in \{-1,1\}^n such that x_1=1 and the number of ‘1’ coordinates is even.  Let \cal F be a subset of \cal G with the property that no two vectors in \cal F are orthogonal. Then |{\cal F}| \le {{n} \choose {0}}+{{n}\choose {1}}+\dots+{{n}\choose{p-1}}.

Proof:

The ad-hoc trick:

Claim 1: Let x,y\in {\cal G}. If <x,y>=0(mod~p) then <x,y>=0. Continue reading

Recent and Future Excitements

It is very hectic around here and on top of the eight or so regular research seminars at math (and quite a few more at CS) we have many visitors as school terms at the US are over.

A week ago there was a beautiful talk about prejudices in physics in the Friday Rationality series given by an old friend Eliezer Rabinovici who did a great job. He wrote a single formula on the blackboard (of some Lagrangian) and explained various truths about physics that were shattered over the years. (Mainly in connection with string theory.) This Friday Nancy Cartwright is going to talk about causality.

Also Ron Donagi, who was a star math Olympiad boy in our youth and whom I first met 37 39 years ago came to town and the two abstracts of his talks today and tommorow are quite amazing. I am not sure I will be able to tell you more after the talks so have a look now:

Ron’s first lecture (today at 16:00):

Title: The Geometric Langlands Conjecture Continue reading