User sune jakobsen - MathOverflow

Examples of statements that provably can't be proved using a promising looking method

2010-06-12T12:56:50Z

Motivation: In Razborov and Rudichs article "Natural proofs" they define a class of proofs they call "natural proofs" and show that under certain assumptions you can't prove that $P\neq NP$ using a "natural proof". I know that this kind of results is common in complexity theory, but I don't know any good examples from other fields. This is why I ask:

Question: Can you give an example of a statement S that isn't known to be unprovable (it could be an unsolved problem or but it could also be a theorem), a promising-looking class of proofs and a proof that a proof from this class can't prove S.

I'm interested in both famous unsolved problems and in elementary examples, that can be used to explain this kind of thinking to, say, freshmen.

Do sets with positive Lebesgue measure have same cardinality as R?

2009-12-15T10:47:40Z

I have been thinking about which kind of wild non-measurable functions you can define. This led me to the question:

Is it possible to prove in ZFC, that if a (Edit: measurabel) set $A\subset \mathbb{R}$ has positive Lebesgue-measure, it has the same cardinality as $\mathbb{R}$? It is obvious if you assume CH, but can you prove it without CH?

Answer by Sune Jakobsen for Channel capacity of a coin flip

2012-08-26T17:32:05Z

If you channel is that you can decide if the cion shows head or tail and the pass the coin to your friend with that side up, then the channel has capacity of one bit. This corresponds to your first computation.

If you channel is that you throw the coin to you friend on such a way that it is head with 50% probability and tail with 50% probability, then you cannot send any information over the channel. This corresponds to your second computation.

Greatest function satisfying some convexity requirements

2011-11-23T20:34:04Z

Edit: Even though there is an accepted answer, the problem isn't solved. I only accepted the answer, because there was a bounty on the question so I had to accept an incomplete answer.

I was working on a problem in discrete matematics, and reduced it to a more analytical problem. I was hoping that we could use some analytical tecniques to solve it, but I don't know of any.

A special case of the reduced problem is: Consider the 3-simplex

$\Delta^3= \{ (x_1,x_2,x_3,x_4)|0\leq x_1,x_2,x_3,x_4\leq 1, x_1+x_2+x_3+x_4=1\}$
and functions $f:\Delta^3\to [0,1]$. We want to find the greatest such function satisfying

$f(½,0,½,0)=f(0,½,0,½)=½$
If we restrict $f$ to any plane that contains both $(1,0,0,0)$ and $(0,1,0,0)$ we get a convex function
If we restrict $f$ to any plane that contains both $(0,0,1,0)$ and $(0,0,0,1)$ we get a convex function

Here we say that $f$ is greater than $g$ if $f(x)\geq g(x)$ for all $x\in\Delta^3$. It is clear that there exists a greatest function satisfying the above since it is just the supremum of all functions satisfying the above. In particular, I would like to know if $f$ had to be convex on all of $\Delta^3$ and to know the value of $f(1/4,1/4,1/4,1/4)$.

Is there a known theory for solving this kind of problems?

Edit: I would also be interested to know a proof or disproof that the algorithm described in David Speyers community wiki-answer give the function we are looking for in a finite number number of steps (in the limit it does).

How small can a language in NP\P be?

2012-05-18T09:32:53Z

How small can a language in $NP$ but not in $P$ be? Of course, I don't expect a proof that there exists a language in $NP\setminus P$, so instead I'll ask: Can we rule out any of these conjectures?

1) There is a language $NP\setminus P$, where all elements are on the form $0^{2^{2^{\dots ^2}}}$.

2) For any infinite language $A\in P$ there is $B\subset A$ in $NP\setminus P$.

The problem of finding the first digit in Graham's number

2010-04-08T17:53:14Z

Motivation

In this BBC video about infinity they mention Graham's number. In the second part, Graham mentions that "maybe no one will ever know what [the first] digit is". This made me think: Could it be possible to show that (under some assumptions about the speed of our computers) we can never determine the first digit?

In logic you have independence results like "We cannot decide if AC is true in ZF". But we cannot hope for this kind of result in this case, since we can easily program a computer to give us the answer. The problem is, that we don't have enough time to wait for the answer!

In complexity theory you prove things like "no program can solve all problems in this infinite set of problems, fast". But in this case you only have one problem, and it is easy to write a program, that gives you the answer. Just write a program that prints "1" another that prints "2" ... and a program that prints "9". Now you have a program that gives you the answer! The problem is, that you don't know which of the 9 programs that are correct.

Questions

Edit: I have now stated the questions differently. Before I asked about computer programs instead proofs.

Could it be possible to show that any proof of what the first digit in Grahams numbers is, would have length at least $10^{100}$?
Do there exist similar results? That is, do we know a decidable statement P and a proof that any proof or disproof of P must have length $10^{100}$.
Or can we prove, that any proof that a proof or disproof of P must have length at least $n$, must itself have length at least $n$?

I think the answer to 3) is no, at least if all proofs are in the same system. Such a proof would prove that it should have length all least n for any n.

(Old Questions:

Could it be possible to show that it would take a computer at least say $10^{100}$ steps to determine the first digit in Grahams number?
Do there exist similar results? That is, do we know a decidable statement P and a proof that P cannot be decided in less that say $10^{100}$ steps.
Or can we prove that we need at least $n$ steps to show that a decidable statement cannot be decided in less than $n$ steps?)

(I'm not sure I tagged correctly. Fell free to retag, or suggest better tags.)

How to get rich in a Hilberts Hotel?

2012-02-12T16:59:55Z

Suppose you can make infinitely many copies of yourself. Each of them starts his/her life in a Hilberts Hotel, where each room is labeled by an element in the free group with two generators, and structured as the Cayley graph of the group. (All the room have the same size, so in particular this hotel is not embedded in $\mathbb{R}^3$!) In the beginning, each clone have 1£. If they all cooperate, they can get richer exponentially fast: If they all give all their money to the neighbor in the direction of $e$, then everyone except the person in $e$ will receive money from three persons, so after n transactions he will have $3^n$£ (and $e$ will receive money from 4 persons, so he will be even richer).

Question: Suppose instead that the rooms were unlabeled. You can decide on a strategy before being copied, and you are allowed to use randomness in this strategy. However, all the copies will be identical, so all of them will think that they are the original "you". Each of the copies can send money and information to each of their four neighbors once each day. Is there a strategy that will make each of them rich exponentially fast?

Comment: If only one of the copies thought he/she was the original you, you could solve the problem: The real you is consider to be $e$. The first day he/she tells his/her neighbors. The next day the neightbors send 2/3 of their money to $e$ and tell their neighbors that "the original you" is in this direction, and so on. With this strategy, each copy become rich exponentialy fast, although it will take some time ("distance to $e$" +3 days) before it starts.

I originally asked the question on my blog, here.

Research Experience for Undergraduates Summer Programs

2010-02-02T18:33:01Z

Some time ago I found this list of REU programs in 2009 (I can't find a similar list for 2010). I think this sounds interesting, and I would like to hear if you know any similar programs. Specifically I would like to know if such programs exists in Europe (or at least if there are programs open for Europeans).

Answer by Sune Jakobsen for Function with range equal to whole reals on every open set

2010-12-12T11:55:43Z

You can even say something much stronger. As Gowers points out, you can reformulate the question as: Does there exist a function that intersect any vertical line, in any open interval? Here you can substitute "vertical line" with "continuous function" and "open interval" with "set with positive measure". The construction is exactly as Gowers point 1. You only have to use that the set of continuous function and the Borel $\sigma$-algebra each have the same cardinality as $\mathbb{R}$.

I wonder if you could substitute "continuous function" with "measureable function" in the above? How many measureable function are there?

Explicit ordering on set with larger cardinality than R

2010-06-02T20:40:23Z

Is it possible to construct (without using Axoim of Choice) a totally ordered set S with cardinality larger than $\mathbb{R}$?

Motivation: A total ordering is often called a “linear ordering”. I have heard the following explanation: “If you have a total ordering on a set S, you can plot the set on the real line such that elements to the right are greater than elements to the left”. Formally this means that there exist a function $\phi:S\rightarrow \mathbb{R}$ such that for all $ a$ ,$b\in S$, x < y $ \Leftrightarrow \phi(x)$ < $\phi(y)$. This is of course correct if the set is finite or countable (and it gives a good intuition on what a total ordering is), but obviously not if $|S|>|\mathbb{R}|$, and using the axiom of choice it is easy to “construct” a total ordering on, say, the power set of $\mathbb{R}$. But I would prefer to have a more concrete counterexample, and this is why I asked myself this question.

Later I realized that is was possible to construct a total ordering on a set $|S|=|\mathbb{R}|$, such that no such function $\phi$ exist, but I still think that the above question is interesting.

Answer by Sune Jakobsen for Most memorable titles

2010-10-31T18:58:50Z

Noone beats Mick gets some (the odds are on his side) by V. Chvatal and B. Reed. It is an article about the satisfiability problem, and the title is of course referring to this song. I havn't read the article, and the only reason I know the it is its title.

Answer by Sune Jakobsen for Generalizing a problem to make it easier

2010-09-26T13:36:59Z

Here is a blog post I wrote about this. I contains three elementary examples of problems from the IMC that you can solve by generalizing.

Answer by Sune Jakobsen for The phenomena of eventual counterexamples

2010-06-12T16:22:49Z

Shapiro inequality: Let $x_1,x_2\dots x_n,x_{n+1},x_{n+2}$ be positive real numbers with $x_{n+1}=x_1$ and $x_{n+2}=x_2$. Now the inequality $\sum_{i=1}^{n} \frac{x_i}{x_{i+1}+x_{i+2}} \geq \frac{n}{2}$ must be true if $n<14$ or if $n\leq 23$ and $n$ is odd. So $n=14$ is the first $n$ where a counterexample can be found. I know that 14 is not that large a number, but remember that for each n we have a problem with a lot of freedom.

Answer by Sune Jakobsen for What is the combinatorial intepretation to this identity?

2010-04-18T10:57:18Z

I don't have an answer, but I have spend a couple of hours on it, so here is some of my thoughts on the problem.

In the following I will identify expressions with sets, so $2^n$ corresponds to the set of 01-sequences of length n, $\binom{n}{k}$ is the set of 01-sequence of length n with exactly k 1s, and products and sums corresponds to taking product sets and unions.

We want to find a bijective function from $\sum_{k=0}^m 2^{2(m-k)} \binom{2k}{k} \binom{2m-k}{m}$ to $\binom{4m+1}{2m}$ (I have multiplied with $4^m$ on both sides). Let me give an example a similar looking equality (you can skip the rest of this paragraph if you want): $\sum_{k=0}^m2^{2(m-k)}\binom{2k}{k}\binom{2m}{2k}=\binom{4m}{2m}$. Take an element in $\binom{4m}{2m}$, and pair the terms, so we have a sequence over {(00),(01),(10),(11)} of length $2m$. We have an even number of 1s in the sequence, so there must be an even number of pairs that contain exactly one 1, and thus and even number of pairs with (00) or (11). Let the number of (00) and (11) in the sequence of pairs be 2k. Now k of these must be (00) and k of them is (11) is the number of 0s and 1s are the same. The 2k terms in the 2m length sequence can be chosen in $\binom{2m}{2k}$ ways, the k (11)s of these 2k terms can chosen in $\binom{2k}{k}$ ways and in the rest of the $2m-2k$ terms we must choose between (10) and (01). This gives a factor $2^{2(m-k)}$, so we have a 1-1 correspondence between $\sum_{k=0}^m2^{2(m-k)}\binom{2k}{k}\binom{2m}{2k}$ and $\binom{4m}{2m}$.

An important part of such a proof is to find out what k represents. In your equality, it turns out that the k=0 part of the sum is about $\sqrt{\frac{1}{2}}$ of the whole sum. Do anyone know where the $\sqrt{\frac{1}{2}}$ could come from? One way to find out what k is, would be to find an injective function from the k=0 term, $2^{2m}\binom{2m}{m}$, to $\binom{4m+1}{2m}$ and see what the image set looks like. But I haven't been able to find such a function, that is, I cannot find a combinatorial proof that $2^{2m}\binom{2m}{m}\leq \binom{4m+1}{2m}$ (nor that $\binom{4m}{2m}<2^{2m}\binom{2m}{m}$). Perhaps you should try to ask this in you question?

Answer by Sune Jakobsen for Most 'unintuitive' application of the Axiom of Choice?

2010-04-10T08:55:58Z

Using AC you can construct a (non-continuous) function that intersects any continuous function on any open interval (or even on any set with positive measure).

Answer by Sune Jakobsen for Estimate rate of real correct/wrong from 4 answers quiz.

2010-04-01T17:00:18Z

As already pointed out, the model seems a bit too simple: In reality the students might be able to exclude one or two of the answers, or they might choose Buzz Lightyear, because they think it is a funny answer. But lets assume that a student either think he knows the answer, or uses a random number generator to decide what to answer (using uniform distribution). We want to find the fraction $a_0$ of students that don't think they know the answer, and the fraction $a_i$ of students, who think the answer is $i$. Now the fraction of students who answer $i$ is $p_i=a_i+\frac{a_0}{4}$. From the test, we are only able to estimate the numbers $p_i$ (unless we ask the students if they guessed) and in general it is not possible to determine say $a_4$ from these numbers. But we know that $p_i$ and $a_i$ are all positive, so we have: $0 \leq a_0 \leq 4\min(p_1,p_2,p_3,p_4)$ and $p_i-\min (p_1,p_2,p_3,p_4)\leq p_i-\frac{a_0}{4}=a_i\leq p_i$ for $ 1\leq i\leq 4$, so (under the assumptions) it is possible to estimate some upper and lower bounds on the number of students who think that Buzz Ligthyear was the first man on the moon: If 10% answered Buzz Lightyear and only 3% said Benjamin Franklin (or perhaps Neil Armstrong!) we could say that between 7% and 10% of all students think that Lightyear was the first man on the moon.

Is every model of ZF countable "seen from the outside"?

2010-01-21T20:56:21Z

I'm not sure if my question make sense, but it would also be interesting to know if it didn't, so I will ask anyway:

There exist a countable model of ZF. This means (if I understand it correctly) that we can find a model of ZF in ZF, such that the set of elements in the model is countable seen from the outer ZF.

My question is: Can every model of ZF be "seen from the outside" in a way that makes it countable?

It seems to me, that if we have a model A of ZF, the model will be a element in a countable model B of ZF. Now, if you look at B from "the outside" A is countable.

Measure between the counting measure and the Lebegue measure

2010-01-13T09:01:19Z

There are subsets of the real line that has infinite counting measure, but Lebegue measure 0, so the Lebegue measure is used for measuring larger sets than the counting measure. My question is: Is there a translation invariant measure m such that for some sets with Lebegue measure 0 the m-measure is infinite and for some sets with infinite counting measure, the m-measure is 0?

I have found one example: m(A)=0 if A is countable, and m(A)=infinite otherwise. So I will require that the measure can take the value 1.

If such a measure exist, can we find a measure between this and the counting measure? and between this and the Lebegue measure? and so on.

What do you call this ring?

2009-12-29T11:59:46Z

I want a ring $R$ of "numbers" such that:

For any sequence of congruences $x\equiv a_1 \pmod{n_1}, x\equiv a_2 \pmod{n_2},\dots$ with $a_i\in \mathbb{Z}$ and $n_i\in \mathbb{N}$ such than any finite set of these congruences has a solution $x\in\mathbb{Z}$, there is a $r\in R$ such that $r\equiv a_1 \pmod{n_1}, r\equiv a_2 \pmod{n_2},\dots$

and

For any $r\in R$ and $n\in\mathbb{N}$ there is a $a, 0\leq a< n $ such that $r\equiv a \pmod{n}$.

I think that $R$ has to be the product set of the p-adic integers over all primes p, but what do you call this ring?

(Perhaps there should be a "terminology" tag? Edit: It already exists but it is called "names")

Unbounded countable subset

2009-11-26T16:31:08Z

(Edit: The first formulation is wrong. See the second answer) Does every totally ordered set contain an unbounded countable subset. In other words: If S is a totally ordered set, can we find a (edit: at most) countable subset A, such that for every $s \in S$, there is a $a \in A, a\geq s$?

Comment by Sune Jakobsen

2012-11-16T20:50:04Z

Is statement B true?

Comment by Sune Jakobsen

2012-08-30T10:42:59Z

Already mentioned twice

Comment by Sune Jakobsen

2012-08-20T22:13:51Z

By planes I mean 2-dimensional planes.

Comment by Sune Jakobsen

2012-06-01T06:32:07Z

But conjecture 1 is a special case of 2. If NP!=P implies conjecture 2, then both conjectures and NP!=P are all equivalent. I doubt that.

Comment by Sune Jakobsen

2012-05-18T14:10:11Z

@David: It might be possible to show that one of the above conjectures are false, without deciding P vs NP.

Comment by Sune Jakobsen

2012-05-18T11:18:11Z

Perhaps I asked the question the wrong way around. I am hoping for an answer that says that we cannot rule out these results from what we know today. E.g. "open conjecture X would imply your conjecture i" (or not i)

Comment by Sune Jakobsen

2012-02-27T08:23:20Z

Well, all the distances might be the same. As I said, the hotel is not embedded in R^3 ;)

Comment by Sune Jakobsen

2012-02-13T16:38:53Z

Now he got it :)

Comment by Sune Jakobsen

2012-02-12T18:38:03Z

The book is available online, and the relevant theorem is on page 283 in the book (page 293 in the pdf-file).

Comment by Sune Jakobsen

2012-01-24T13:09:57Z

@David: Thanks for thinking about the problem. Did you receive my email yesterday?

Comment by Sune Jakobsen

2011-11-24T20:01:29Z

@fedja how do you get continuity at the boundary?

Comment by Sune Jakobsen

2011-11-24T07:53:41Z

I know that the value at the center is at most 2/3 and fedjas comment proves that it is at least 7/12.

Comment by Sune Jakobsen

2011-11-23T22:48:25Z

Remember that the function is to [0,1]. It is not allowed to take values above 1. I think I once checked that the above function (which can also be written as $\max(x_1,x_3)+\max(x_2,x_4)$) is the greatest convex function that satisfy $f(½,0,½,0)=f(0,½,0,½)=½$. However, it could be that some greater function is convex only when restricted to the relevant planes.

Comment by Sune Jakobsen

2011-11-23T22:13:49Z

$x_1+x_2+x_3+x_4=1$ so the function you mention is constantly 1/2. We can do better than that, $max(x_1+x_2,x_3+x_4,x_1+x_4,x_2+x_3)$, but I don't know if we can do even better.

Comment by Sune Jakobsen

2011-11-01T20:23:48Z

No, there could be some 0<p_i<1