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

The Cap-Set Problem and Frankl-Rodl Theorem (C)

Update: This is a third of three posts (part I, part II) proposing some extensions of the cap set problem and some connections with the Frankl Rodl theorem. Here is a post presenting the problem on Terry Tao’s blog (March 2007). Here is an open discussion post around Roth theorem (March 2009). Here are two “open discussion” posts on the cap set problem (first, and second) from Gowers’s blog (January 2011). These posts include several interesting Fourier theoretic approaches towards improvement of the Roth-Meshulam bound. The second post describes a startling example by Seva Lev.

Suppose that the maximum size of a cap set in \Gamma(n)=\{1,2,3\}^n is n/g(n).  Here is an obvious fact:

The maximum size of a set F in G with the property that every x,y\in G (x \ne y) satisfy x+y \notin G is at most the maximum size of a cap set in G

Proof: Indeed the condition for F is stronger than being a cap set. We require for every x,y \in F x \ne y not only that x+y \notin F but even x+y \notin G.  

Part C.  A more direct relation between Frankl-Rodl’s theorem and the cap set problem and all sorts of fine gradings on subsets of {1,2,…,n}.

In part A we moved from sets avoiding affine lines (cap sets) to sets avoiding “modular lines” and used the Frankl-Rodl theorem to deal with the latter. This may look artificial. Here is a simpler connection between the cap set problem and the Frankl-Rodl theorem.

17. Why weaker forms of the Frankl-Rodl Theorem follow from upper bounds on cap sets.

Consider Continue reading

Ehud Friedgut: Murphy’s Law of Breastfeeding Twins

IMG_0079

This post is authored by Ehud Friedgut. Congratulations to Keren, Ehud and Michal for the birth of Shiri and Hillel!

Murphy’s law of breastfeeding twins, like all of Murphy’s laws, is supported by strong empirical evidence.

The twins’ feeding rhythm depends on your approach. If you decide to try and synchronize them in order to minimize your hassle and maximize your rest periods then twin A’s hunger will be governed by sine(t) and twin B’s by cosine(t).

If you decide to respect their natural rhythm in hope of falling into a fixed predictable pattern then twin A will follow sine(t) and twin B sine(\phi\times t), where \phi, the golden ratio, is the number hardest to approximate by rationals

The Amitsur-Levitzki Theorem for a Non Mathematician.

Yaacov Levitzki

The purpose of this post is to describe the Amitsur-Levitzki theorem: It is meant for people who are not necessarily mathematicians. Yet they need to know two things. The first is what matrices are. Very briefly, matrices are rectangular arrays of numbers. The second is that two n by n square matrices A and B can be multiplied. We denote their product by A x B and the product is again an n by n matrix. Unlike numbers, the product of matrices need not be commutative.  In other words A x B can be different from B x A.  The Wikipedia article about matrices is a good source.

We can multiply more than two matrices. We can write A x B x C for the product of A, B and C. The order of the matrices is important, but the order in which we perform the multiplication is not. This is because multiplication of matrices is associative,  that is

 (A x B ) x C  = A x (B x C).

Here is the Amitsur Levitzki Theorem for 2 x2 matrices:

For every four 2 x 2 matrices A, B, C, and D

A x B x C x D – B x A x C x D – A x B x D x C + B x A x D x C – A x C x B x D + C x A x B x D  +  A x C x D x B – C x A x D x B + A x D x B x C  – D x A x B x C – A x D x C x B  + D x A x C x B +  C  x D x A x B –   C x D x B x A –  D x C x A x B + D x C x B x A  – B x D x A x C  + B x D x C x A   + D x B x A x C  – D x B x C x A  + B x C x A x D  –  B x C x D x A  –  C x B x A x D + C x B x D x A = 0 .

In other words, we take the sum of the products of the matrices for all 24 possible orderings (permutations) with certain plus or minus signs, and lo and behold, we always get 0.

I will say more about it. But first a few remarks. The Amitsur-Levitzki theorem deals with products of 2k matrices of size k \times k. It is very beautiful and important and when it comes to mathematics, it doesn’t get much better than that. It can be a nice theorem to explain to non mathematicians, but in this case I have especially one non-mathematician in mind. Alex Levitzki - Yaacov Levitzkii’s son.  I promised Alex who is a famous HU biologist and chemist to tell him about his father’s theorem so why not share it with others. Yaacov Levitzki was one of the founding members of my department in Jerusalem. As a young man he came to Göttingen with the idea to study chemistry but attending a lecture by Emmy Noether converted him to mathematics.

The Amitsur Levitzki Theorem: For every 2n matrices of size n by n denoted by A_1,A_2,\dots A_{2n}, we have: 

\sum sgn (\sigma) \prod_{i=1}^{2n} A_{\sigma(i)} =0,

where the sum is taken over all (2n)! orderings (permutations) \sigma of \{1,2,\dots, 2n\} and sgn(\sigma) denotes the sign of the ordering  \sigma. Continue reading