Wikipedia:Reference desk/Archives/Mathematics/2010 July 16

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

July 16

Fixed Point

Studying some old analysis exams, I came across the following problem and it has resisted all efforts by everyone I know (including myself) so I appeal here. Here is the problem verbatim.

"The continuous map $F(x,y)=(f_{1}(x,y),f_{2}(x,y))$ from $\mathbb {R} ^{2}$ to $\mathbb {R} ^{2}$ satisfies

a) $|f_{i}(x_{2},y_{2})-f_{i}(x_{1},y_{1})|<{\frac {1}{2}}(|x_{2}-x_{1}|+|y_{2}-y_{1}|)$ for $i=1,2$

b) F maps the set $\Omega =(0,1)\times (0,1)$ into itself.

Show that F has a unique fixed point in $\mathbb {R} ^{2}$".

Ok, several issues with this question. The only fixed point theorem we are supposed to know is the contraction mapping theorem so I am guessing that the only way to do this problem is to show that F is a strict contraction (with the contraction constant being strictly less than one) on the unit square. Condition a) doesn't give us a contraction because the two metrics being used on the opposite sides of the inequality are different (left is using the 2-norm and the right is using the 1-norm). I have shown that F continuous implies that it maps the closed unit square to itself but I can't get a strict contraction for any of the metrics I can think of. The contraction constant always comes out to one which is useless. In fact I proved that $d_{p}(F(y),F(x))<d_{p}(y,x)$ for any of the p-metrics (include the max-metric). I think that as long as I find one metric (for which R^2 is complete) for which F is a contraction, its good because the actual fixed point doesn't depend on the metric. Any help?-Looking for Wisdom and Insight! (talk) 02:46, 16 July 2010 (UTC)

left is using the 2-norm. Really? There is no square or square root involved. Condition a) is the two inequalities

$|f_{1}(x_{2},y_{2})-f_{1}(x_{1},y_{1})|<{\frac {1}{2}}(|x_{2}-x_{1}|+|y_{2}-y_{1}|)$

$|f_{2}(x_{2},y_{2})-f_{2}(x_{1},y_{1})|<{\frac {1}{2}}(|x_{2}-x_{1}|+|y_{2}-y_{1}|)$

when added together you get

$|f_{1}(x_{2},y_{2})-f_{1}(x_{1},y_{1})|+|f_{2}(x_{2},y_{2})-f_{2}(x_{1},y_{1})|<|x_{2}-x_{1}|+|y_{2}-y_{1}|\,$

or

${\frac {|f_{1}(x_{2},y_{2})-f_{1}(x_{1},y_{1})|+|f_{2}(x_{2},y_{2})-f_{2}(x_{1},y_{1})|}{|x_{2}-x_{1}|+|y_{2}-y_{1}|}}<1$

which looks like a contraction. PS. The notation in the problem is confusing. Indexes 1 and 2 refer sometimes to different points and sometimes to different coordinates of the same point. $f(x,y)=(f_{x}(x,y),f_{y}(x,y))$ is better. Bo Jacoby (talk) 07:41, 16 July 2010 (UTC).

Yes true but this is still $||F(y)-F(x)||_{1}<||y-x||_{1}$ and the constant of contraction is still one (which I already knew). The thing is that it needs to be a number strictly less than one. Contraction constant being one doesn't say anything. There may be a fixed point (like the identity map which has many fixed points) or there may be no fixed points. The constant needs to be less than one for the existence and uniqueness of a fixed point. I already know that any of the standard p-norms (include the infinity norm) give us one. I even tried more exotic things like $d(x,y)={\frac {d_{2}(x,y)}{1+d_{2}(x,y)}}$ and I still get the contraction constant as 1. Is there a metric which would work? How would we go about finding it? Or are we going about this completely the wrong way and the approach is completely different? I was also thinking, this problem of having the contraction constant c=1 happens because of the diagonal y=x so maybe if I could take the diagonal, take a little band around it (width=epsilon) and remove it from the closed unit square. Then I would have a c<1 and then maybe take a limit as epsilon goes to zero or something. Would that work?-Looking for Wisdom and Insight! (talk) 07:58, 16 July 2010 (UTC)

(Edit Conflict) You are also right about the notation being confusing. Its basically, pick two points $x=(x_{1},y_{1}),y=(x_{2},y_{2})$ in $\mathbb {R} ^{2}$. And F has the two scalar components f1 and f2. I agree this is not the best choice but that's what it said.-Looking for Wisdom and Insight! (talk) 07:58, 16 July 2010 (UTC)

A square with side a is mapped into a square with side a/2? No, sorry. Bo Jacoby (talk) 08:07, 16 July 2010 (UTC).

There's a wee bit of a problem in that if you're talking about the open square there isn't any fixed point - it could all tend to one corner. If you're talking about a closed square then the contraction factor doesn't have to be less than 1, it just needs to always be less than 1 for any pair of points you look at but could have a limit of 1. A map like that sending everything to a diagonal line that then goes towards a corner is

$f_{1}(x,y)=f_{2}(x,y)=(x+y)/(1+x+y)$

The important thing for a closed square is that it is compact. Dmcq (talk) 09:59, 16 July 2010 (UTC)

Stupid me! Just substitute zeroes in all coordinates and obtain the relation 0<0 which is false. No mapping satisfy the required conditions, and so every mapping that does satisfy the condition has a fixed point. Bo Jacoby (talk) 13:30, 16 July 2010 (UTC).

Ah but is it a unique fixed point :) You're quite right, the theorem for the compact case is where the inequality holds whenever the two points are different. Dmcq (talk) 13:39, 16 July 2010 (UTC)

I don't see the need for any separate "compact case". In the original case, f: R² → R² maps Ω to itself and is continuous, therefore it also maps ${\overline {\Omega }}$ to itself. Thus by your argument it has a fixed point in ${\overline {\Omega }}$ and a fortiori in R². Uniqueness is straightforward.—Emil J. 14:05, 16 July 2010 (UTC)

Oh I see what you're talking about, it is a fixed point of the map of the whole plane, I was just thinking of the open square. Um, yes I should have read it better, thanks. Dmcq (talk) 15:51, 16 July 2010 (UTC)

Wait, maybe its just me being stupid but what's the verdict here? How do we know that there is a fixed point and how do we know that its unique? Maybe its irrelevant but can we say anything about where (or what) the fixed point would be? Is it in omega? Is it in omega closure (like the origin)? The only thing I can understand from this is that if I pick two points in omega, then their images will be closer in L1 norm. But we don't even know specifically how close.-Looking for Wisdom and Insight! (talk) 23:25, 16 July 2010 (UTC)

Yep there's always a unique fixed point. I was using the Brouwer fixed point theorem rather than the Banach fixed point theorem on the closure of the unit square. As EmilJ pointed out the closure of an open area will always transform to within the closure of the transformed open area. Plus you can't have two fixed points if the distance after the mapping is always smaller. Dmcq (talk) 00:02, 17 July 2010 (UTC)

The theorem that a distance-reducing map on a compact metric space has a fixed point is much easier than Brouwer (just consider a point x minimizing the continuous function x↦d(x,f(x))). Algebraist 09:11, 17 July 2010 (UTC)

Yes that's better, compact sets map to compact sets, or even invoke the extreme value theorem from analysis but topology is easier here. I was trying to work in the poster's contraction mapping theorem and I didn't manage anyway. Looking at Banach fixed point theorem I see it mentions this bit about a compact set and not needing the contraction to have a definite factor less than 1. I don't see how to fit in the poster's bit about having just done the contraction mapping theorem,it sounds like it should be relevant but just doesn't seem to be, or is the bit about compact sets a part of the contraction mapping theorem? Dmcq (talk) 10:35, 17 July 2010 (UTC)

No, the verdict is that the problem is a joke. Condition a) is a contradiction because for point 1 equal to point 2 condition a) says that 0<0, which is simply not the case. You do not need any fixed point theorems at all. There exist no mapping satisfying condition a). The set of mappings satisfying condition a) is the empty set = { } = Ø. What can be said about the elements of the empty set? The answer is that anything can be said about the elements of the empty set, because the empty set has got no elements. So all the mappings satisfying condition a), ( there are none ), have got unique fix points, Q.E.D. Bo Jacoby (talk) 04:01, 17 July 2010 (UTC).

That's true but I'm reading it as meaning the inequality refers to any two distinct points as I said above. It's not a joke, its just a missing condition. Dmcq (talk) 09:06, 17 July 2010 (UTC)

The original problem may be modified in several ways to make more sense. The sign '<' may be replaced by '≤' to avoid the contradiction 0<0. Then the identity map, having plenty of fixed points, is a possibility. Then the constants 1/2 could be lowered a little to, say, 499/1000. Then the Banach theorem applies and there is a unique fixed point. But the problem as written assumes a contradictory condition. Bo Jacoby (talk) 11:20, 17 July 2010 (UTC).

If a person looks around a house and says "I looked and there was nobody there" we don't go around saying "Ha ha you're trying to trick us, you were there so it couldn't have been empty". Let's just assume a bit of good faith and a straightforward problem and not jump at things like that. Dmcq (talk) 12:58, 17 July 2010 (UTC)

An old analysis exam need no good faith for its interpretation. The purpose is to check that the student can read and think. Bo Jacoby (talk) 18:50, 17 July 2010 (UTC).

Summarizing the above discussion :

• (b) is already sufficient to get a fixed point in the closed square $[0,1]\times [0,1]$, which is an invariant set of the map $f:=(f_{1},f_{2})$: by the Brower fixed point thm. (but not a unique fixed point. The identity map satisfies condition (b). Bo Jacoby (talk) 20:38, 20 July 2010 (UTC).)

• Condition (a) as it is, is empty, so it was possibly not properly stated. One may modify it requiring (a'): the strict inequality holds only for pairs $(x_{2},y_{2})\neq (x_{1},y_{1})$. Summing the two inequalities one gets $d(f(z_{1}),f(z_{2}))<d(z_{1},z_{2})$ for all $z_{1}\neq z_{2}$ in the square, where $d(\cdot ,\cdot )$ is the L1 distance (sum of absolute values of the coordinates).

• In the assumptions (a') and (b) the conclusion follows by minimizing $d(x,f(x))$ on the compact square, or, if you want to use the contraction principle, taking a limit point of a sequence $z_{k}$ of fixed points of the contractions $f_{k}:=(1-1/k)f$. (Unicity is obvious).

--pma 18:16, 19 July 2010 (UTC)

Linear independence over complex numbers of modular forms of different weights

Hello, I am trying to show that n nonzero modular forms of n distinct integer weights are linearly independent over the complex numbers. I thought induction might work and the base case is easy as it is just the case n = 1. But, I can also prove it for n = 2 directly:

Assume $f_{1}(z),f_{2}(z)$ are nonzero modular forms of distinct integer weights $k_{1},k_{2}$. Assume also that there exist $a_{1},a_{2}\in \mathbb {C}$, not both zero such that $a_{1}f_{1}+a_{2}f_{2}=0$. WLOG, assume $a_{1}\neq 0$. Then, I can solve for $f_{1}(z)=-{\frac {a_{2}}{a_{1}}}f_{2}(z)$. Since these are both modular forms, they are invariant under the stroke operator for any $\gamma ={\begin{bmatrix}a&b\\c&d\end{bmatrix}}\in SL_{2}(\mathbb {Z} )$ for their respective weights. Thus,

$(cz+d)^{-k_{1}}f_{1}(\gamma z)=-{\frac {a_{2}}{a_{1}}}(cz+d)^{-k_{2}}f_{2}(\gamma z)$

which gives

$f_{1}(\gamma z)=-{\frac {a_{2}}{a_{1}}}(cz+d)^{k_{1}-k_{2}}f_{2}(\gamma z)$

which gives

$-{\frac {a_{2}}{a_{1}}}f_{2}(\gamma z)=-{\frac {a_{2}}{a_{1}}}(cz+d)^{k_{1}-k_{2}}f_{2}(\gamma z)$

so that

$(cz+d)^{k_{1}-k_{2}}=1$.

Now, since $\gamma \in SL_{2}(\mathbb {Z} )$ can be anything and this exact equation must hold for all such matrices, the only conclusion is $k_{1}=k_{2}$, a contradiction. Thus, they are linearly independent.

I tried extending this same argument to the general case of n but I am not sure where to go. Any suggestions? Thanks StatisticsMan (talk) 13:26, 16 July 2010 (UTC)

Just to be clear, when I tried it with n, hoping to use the induction hypothesis that n-1 are linearly independent, I got

$\sum _{i=2}^{n}a_{i}f_{i}(\gamma z)=\sum _{i=2}^{n}a_{i}(cz+d)^{k_{1}-k_{i}}f_{i}(\gamma z)$

and this does not seem to have any great way to cancel. I put everything on one side to get

$\sum _{i=2}^{n}a_{i}f_{i}(\gamma z)[1-(cz+d)^{k_{1}-k_{i}}]=0$

which is almost a linear combination of n-1 of them, well it is, but it's in complex variables instead of complex numbers. StatisticsMan (talk) 13:57, 16 July 2010 (UTC)

Millennium Prize Problems

Would you get the prize money for disproving one of the conjectures or proving it independent? --138.110.206.101 (talk) 16:12, 16 July 2010 (UTC)

The rules say

In the case of the P versus NP problem and the Navier-Stokes problem, the SAB will consider the award of the Millennium Prize for deciding the question in either direction. In the case of the other problems if a counterexample is proposed, the SAB will consider this counterexample after publication and the same two-year waiting period as for a proposed solution will apply. If, in the opinion of the SAB, the counterexample effectively resolves the problem then the SAB may recommend the award of the Prize. If the counterexample shows that the original problem survives after reformulation or elimination of some special case, then the SAB may recommend that a small prize be awarded to the author. The money for this prize will not be taken from the Millennium Prize Problem fund, but from other CMI funds.

Independence proofs aren't mentioned as far as I can see. Algebraist 16:16, 16 July 2010 (UTC)

For good reason, I'd say. It's always important to keep in mind that independence is not a truth value. All you can hope to show — well, at least all anyone heretofore has shown — is that a proposition is independent of some specific formal theory.

Granted, the same objection could be applied to a proof, period; I'm not sure what would happen if, say, someone proved that P!=NP, but had to assume the existence of a supercompact cardinal. Well I can tell you one thing that would happen, which is it would make me very happy. But would they award the prize? In my opinion they ought to, but I don't know whether they have a settled decision on the point. --Trovatore (talk) 20:57, 18 July 2010 (UTC)

If they can prove it by assuming the existence of such a cardinal and prove that it is false if there is no such cardinal (ie. they've proven it is independent of any axiomatic system that doesn't precisely determine whether or not supercompact cardinals exist) then I'd say they have solved the problem and should get the money. If they've only proven the first half, then I'd say they haven't solved it. They've just solved a special case of the problem. If I were in charge, I would give them a smaller prize, as per the rules for counterexamples due to technicalities. If you give them the full prize, then what do you do when someone else comes along as solves the whole problem? The money would already be gone. --Tango (talk) 21:27, 18 July 2010 (UTC)

You're going to require a sharp estimate of the exact large-cardinal strength needed? It seems a bit arbitrary to apply that criterion only at consistency strengths higher than ZFC. For example the axiom of replacement can be thought of as a large-cardinal axiom in a way. If someone proved P!=NP in a way that used replacement, but didn't show that replacement was necessary, would you withhold the prize? --Trovatore (talk) 21:44, 18 July 2010 (UTC)

I read your scenario as suggesting someone proved LC=>(P!=NP) for some large cardinal LC, but didn't rule out the possibility that P!=NP is provable in, say, Peano arithmetic (it has already been proven independent of some fragments of PA). Of course it would be different (and astounding) if P vs NP was proved independent of ZFC. Note that there is a theorem that if P vs NP is provably independent of PA, then in "practical" terms P is equal to NP. Specifically, SAT can be solved in running time O(n^f(n)) where f(n) is an unbounded but ultra-slow-growing function, like the inverse of the Ackermann function, i.e. effectively constant for all problems that can fit in a computer. This is mentioned on p. 15 of [1] which is a good paper on the possible independence of P vs NP. 67.122.211.208 (talk) 02:36, 19 July 2010 (UTC)

Yes, you read my scenario correctly. Since I am of the Cabal mindset that large-cardinal axioms may be used freely, I would consider that scenario to settle the question.

Now, as to the theorem you mention, I would like to get this straight because we should really be accurate about it in the articles. If I remember correctly, at least one of our articles mentions it in the form you state, namely that if P!=NP is not provable in PA, then your conclusion holds. But someone claimed on a talk page that you actually need to assume that P!=NP is not provable in PA by means of the sort of proof that has up to now been used (possibly Aronson's "natural proofs"). And Aronson himself states the conclusion if P!=NP is not provable in the theory he calls "PA+Π₁", that is, PA plus all true Π⁰₁ sentences.

Note that the latter theory is quite a bit stronger than PA as regards the natural numbers. For example the statement "the theory 'ZFC+there exists a supercompact cardinal' is consistent" is a true Π⁰₁ statement, and therefore provable in PA+Π₁. So independence from PA+Π₁ would be, in my subjective estimation, not really all that far from independence from "ZFC+there exists a supercompact cardinal". --Trovatore (talk) 03:32, 19 July 2010 (UTC)

Sorry-- I've added the word "provably" above, but I think that means any sort of proof, not just a "natural" proof. That is explained in Aaronson's article, pp. 14-15. 67.122.211.208 (talk) 04:53, 19 July 2010 (UTC)

It means "any sort of proof" if you're assuming independence from the stronger theory PA+Π₁. I haven't been over Aronson's paper with a fine-tooth comb, but I see nothing that would enable the conclusion merely if P!=NP is independent from PA.

Now, he does observe at the top of page 15 that, if you can prove P!=NP is independent of PA, then you can prove that SAT can be computed in n^{log n} time, or much less (your inverse Ackermann etc). But it doesn't follow that you can prove this in PA! Not unless your independence proof is also formalizable in PA. --Trovatore (talk) 05:12, 19 July 2010 (UTC)

Sorry, I got confused — that's not what he observes at the top of page 15. If that were true it would pretty much prove your point, but it isn't. What he shows is that if PA doesn't prove that SAT can't can be computed in n^{log n} time, well then it can cannot be.

But that doesn't exclude the following situation: Suppose ZFC (just for example) proves that P!=NP is independent of PA, but true, and that SAT cannot be computed in n^{log n} time. As far as I can see, nothing that Aronson writes excludes that possibility. If you see something that does, or otherwise know a reason that that can't be true, please let me know. --Trovatore (talk) 05:36, 19 July 2010 (UTC)

I should say: I'm not sure the above is quite right, when talking about time. Aronson actually talks about "circuits" rather than time. I haven't read his paper closely enough to know what a "circuit" is. So please don't take my analysis as necessarily a precisely correct representation of what Aronson means. --Trovatore (talk) 07:34, 19 July 2010 (UTC)

See circuit complexity. Basically, circuits are a nonuniform computation model where the size of the circuit roughly corresponds to time on a Turing machine; for example, SAT is computable by circuits of size n^{O(log n)} iff it is computable by an algorithm running in time n^{O(log n)} with access to an extra "advice string" A_n, which has to be the same for all inputs of length n (and itself has length n^{O(log n)}, but that's implicit in that the algorithm would not have the time to read it otherwise).—Emil J. 11:40, 19 July 2010 (UTC)

Separately from P vs NP as above, I wonder what the current state of the Millenium Prize problem fund is, since one of the problems has been solved but the solver declined the prize. 67.122.211.208 (talk) 07:20, 19 July 2010 (UTC)