/sci/ - Science & Math

>>4366578
I'm extremely rusty on group theory, but I'm pretty sure this isn't correct (which is a shame, because it would be beautiful).

If <span class="math">a,b\in (\mathbb{Z}/2\mathbb{Z})^{10}[/spoiler], <span class="math">a=(a_1,\ldots,a_{10})[/spoiler] and <span class="math">b=(b_1,\ldots,b_{10})[/spoiler], then it is not necessarily the case that <div class="math">f_1^{a_1+b_1}\circ f_2^{a_2+b_2}\circ\cdots\circ f_{10}^{a_{10}+b_{10}} = f_1^{a_1}\circ f_2^{a_2}\circ\cdots\circ f_{10}^{a_{10}}\,\circ\, f_1^{b_1}\circ f_2^{b_2}\circ\cdots\circ f_{10}^{b_{10}}. </div> So we're not dealing with a such a simple group action.

>>4365917
>Countability may not be enough.
Countability of what? Whom are you responding to?

> Perhaps one could argue that all but *finite* number of r_n are within epsilon from 0,
Definitely true...

>...so all but *finite* number of elements of S are within 1994*epsilon from 0.
Not necessarily. See >>4362737

[I've deleted this repeatedly. jsMath doesn't recognize several commands that are part of the amsmath package]

I first came up with a proof by induction as suggested in
>>4362814
But I suspected a clean topological proof is hiding somewhere. We are asked to show that <span class="math">S[/spoiler], a countable set, cannot be dense in any nonempty open interval. Clearly, the condition that <span class="math">r_n\to0[/spoiler] is key. Without it, the statement is not true: If <span class="math">\{r_n\}[/spoiler] is an ordering of the rational numbers <span class="math">\mathbb{Q}[/spoiler], then <span class="math"> S = \mathbb{Q} [/spoiler] is dense in <span class="math">\mathbb{R}[/spoiler]. But what is the quality of the condition <span class="math">r_n\to0[/spoiler] that makes the statement true? The most obvious candidate reason is that this condition ensures that the <span class="math">r_n[/spoiler] can accumulate around at most countably many points.

Claim: if <span class="math">A\subset\mathbb{R}[/spoiler] has at most countably many limit points, then the set <span class="math">A_N=A+A+\cdots+ A[/spoiler] (<span class="math">N[/spoiler] times) also has at most countably many limit points.

Let <span class="math">E=\{r_j\}_{j\in\mathbb{Z}^+}[/spoiler].
If the Claim is true, then the result follows: since <span class="math">S\subset E_N [/spoiler], <span class="math">S[/spoiler] must also have at most countably many limit points. Therefore, <span class="math">S[/spoiler] cannot possibly be dense in any nonempty open interval.

But we can bypass proving the Claim if we also use the fact that <span class="math">E[/spoiler] is precompact. For because of this, <div class="math">\overline{E_N}=\overline{E+\cdots+E}=\overline{E}+\cdots+\overline{E}=(\overline{E})_N, </div> which implies that <span class="math">E_N[/spoiler] can have at most countably many limit points.

I first came up with a proof by induction as suggested in
>>4362814
But I suspected a clean topological proof is hiding somewhere. We are asked to show that <span class="math">S[/spoiler], a countable set, cannot be dense in any nonempty open interval. Clearly, the condition that <span class="math">r_n\to0[/spoiler] is key. Without it, the statement is not true: If <span class="math">\{r_n\}[/spoiler] is an ordering of the rational numbers <span class="math">\mathbb{Q}[/spoiler], then <span class="math"> S = \mathbb{Q} [/spoiler] is dense in <span class="math">\mathbb{R}[/spoiler]. But what is the quality of the condition <span class="math">r_n\to0[/spoiler] that makes the statement true? The most obvious candidate reason is that this condition ensures that the <span class="math">r_n[/spoiler] can accumulate around at most countably many points.

Claim: if <span class="math">A\subset\mathbb{R}[/spoiler] has at most countably many limit points, then the set <span class="math">A_N=A+A+\cdots+ A[/spoiler] (<span class="math">N[/spoiler] times) also has at most countably many limit points.

Let <span class="math">E=\{r_j\}_{j\in\mathbbm{Z}^+}[/spoiler].
If the Claim is true, then the result follows: since <span class="math">S\subset E_N [/spoiler], <span class="math">S[/spoiler] must also have at most countably many limit points. Therefore, <span class="math">S[/spoiler] cannot possibly be dense in any nonempty open interval.

But we can bypass proving the Claim if we also use the fact that <span class="math">E[/spoiler] is precompact. For because of this, <div class="math">\overline{E_N}=\overline{E+\cdots+E}=\overline{E}+\cdots+\overline{E}=(\overline{E})_N, </div> which implies that <span class="math">E_N[/spoiler] can have at most countably many limit points.

I first came up with a proof by induction as suggested in
>>4362814
But I suspected a clean topological proof is hiding somewhere. We are asked to show that <span class="math">S[/spoiler], a countable set, cannot be dense in any nonempty open interval. Clearly, the condition that <span class="math">r_n\to0[/spoiler] is key. Without it, the statement is not true: If <span class="math">\{r_n\}[/spoiler] is an ordering of the rational numbers <span class="math">\mathbb{Q}[/spoiler], then <span class="math"> S = \mathbb{Q} [/spoiler] is dense in <span class="math">\mathbb{R}[/spoiler]. But what is the quality of the condition <span class="math">r_n\to0[/spoiler] that makes the statement true? The most obvious candidate reason is that this condition ensures that the <span class="math">r_n[/spoiler] can accumulate around at most countably many points.

Claim: if <span class="math">A\subset\mathbb{R}[/spoiler] has at most countably many limit points, then the set <span class="math">A_N=A+A+\cdots+ A[/spoiler] (<span class="math">N[/spoiler] times) also has at most countably many limit points.

If the Claim is true, then the result follows: since <span class="math">S\subset E_N [/spoiler], <span class="math">S[/spoiler] must also have at most countably many limit points. Therefore, <span class="math">S[/spoiler] cannot possibly be dense in any nonempty open interval.

But we can bypass proving the Claim if we also use the fact that <span class="math">E[/spoiler] is precompact. For because of this, <div class="math">\overline{E_N}=\overline{E+\cdots+E}=\overline{E}+\cdots+\overline{E}=(\overline{E})_N, </div> which implies that <span class="math">E_N[/spoiler] can have at most countably many limit points.

I first came up with a proof by induction as suggested in
>>4362814
But I suspected a clean topological proof is hiding somewhere. We are asked to show that <span class="math">S[/spoiler], a countable set, cannot be dense in any nonempty open interval. Clearly, the condition that <span class="math">r_n\to0[/spoiler] is key. Without it, the statement is not true: If <span class="math">\{r_n\}[/spoiler] is an ordering of the rational numbers <span class="math">\mathbb{Q}[/spoiler], then <span class="math">S=\mathbb{Q}[/spoiler] is dense in <span class="math">\mathbb{R}[/spoiler].
But what is the quality of the condition <span class="math">r_n\to0[/spoiler] that makes the statement true? The most obvious candidate reason is that this condition ensures that for any given nonempty open interval, the points <span class="math">r_n[/spoiler] cannot accumulate around all the points of the interval. In fact, the set <span class="math">E=\{r_n\}_{n\in\mathbb{Z}^+}[/spoiler] only has one limit point: 0.

One suspects that a sufficient condition is that <span class="math">\overline{E}[/spoiler] be countable. Indeed it is sufficient, but if we add the fact that <span class="math">E[/spoiler] is bounded, the proof greatly simplifies.

Fact: <span class="math">E=\{r_n\}[/spoiler] is precompact and <span class="math">\overline{E}[/spoiler] is countable.
Let <span class="math">E^N = E\times E\times \cdots \times E[/spoiler], endowed with the product topology. As the product of precompact sets, <span class="math">E^N[/spoiler] is also precompact, with <span class="math">\overline{E^N}=(\overline{E})^N[/spoiler].
Let <span class="math">\sigma\,:\,\mathbb{R}^N\to \mathbb{R}[/spoiler] denote the summation function <span class="math">\sigma((x_1,\cdots,x_N)) = \sum_{j=1}^N x_j[/spoiler]. <div class="math">\overline{S}\subset\overline{\sigma(E^N)}=\sigma\left(\overline{E^N}\right), </div> since the continuous image of a precompact set is precompact (with the closure of the preimage mapping onto the closure of the image). Since <span class="math">\overline{E}^N[/spoiler] is countable, the same must be true of <span class="math">\overline{S}[/spoiler]. Therefore, <span class="math">S[/spoiler] cannot possibly be dense in any nonempty open interval.

>>4357933
>>4358815
Well done. I didn't see the shortcut with the pigeonhole principle, though it's obvious in retrospect. I used the fact that <span class="math">\det(A+nB)=\pm1[/spoiler] for <span class="math">n=0,\ldots,4[/spoiler] to directly (and inelegantly) show that <span class="math">\det(A+5B)=\pm1[/spoiler].

>>4361143
Why must this equality hold in this case? It doesn't hold for <span class="math">2\times2[/spoiler] matrices in general.

>>4361429
Actually, the formula holds for those particular A and B.

This problem was, I think, disappointingly straightforward to solve.

Suppose the sum converges to <span class="math">L[/spoiler].
<div class="math">L =\sum_{n=1}^\infty a_n\leq \sum_{n=1}^\infty ( a_{2n}+a_{2n+1} )= \sum_{\mathrm{even}\; k\geq 2}a_k +\sum_{\mathrm{odd}\; k\geq 3}a_k = \sum_{k=2}^\infty a_k = L - a_1.</div> This can hold only if <span class="math">a_1 = 0[/spoiler], which contradicts the condition that <span class="math">(a_n)[/spoiler] be a positive sequence.

This is just about the easiest Putnam problem I've ever seen. The first thing I would think to try works, and does so quickly.

I think >>4346651 is a prettier proof since it's constructive yet still brief.

>>4346680
The exam consists of 12 questions and is taken over two three-hour sessions, separated by an hour-long lunch break. The first half consists of problems A1-A6; the second, B1-B6. Each half is designed to present problems in increasing order of difficulty: A1 and B1 are supposed to be the easiest problems, followed by A2 and B2, etc. Sometimes the problem writers don't get it right: in a given year, more participants might solve B4 than B2, say. But generally, the rule is pretty sound. This problem was an A1.

>>4345447
Suppose you had succeeded in passing off someone else's proof as your own in this anonymous forum. How would you benefit?

>>4342126
lol

>>4340888
?exp() isn't holomorphic when codomain is the Riemann sphere.

It isn't *bi*holomorphic, but unless I'm totally confused, it is holomorphic. [Here I can take the Riemann surface to just equal the complex plane.]

Did you mean to define <span class="math">U(X)[/spoiler] to be the set of all biholomorphic functions?

>>4340877
The replace <span class="math">f[/spoiler] with <span class="math">f(z)=z[/spoiler]. <span class="math">Gf[/spoiler] clearly doesn't contain exp().

?

>>4340654
>>4340659

How can it be transitive?

Consider <span class="math">f_1(z) = 1[/spoiler]. MTs are functions of the form <span class="math">\phi(z) = (az+b)/(cz+d)[/spoiler].
Thus, <span class="math">Gf= \{z\mapsto (a+b)/(c+d)\,:\,a,b,c,d\in\mathbb{C}\} = [/spoiler] constant functions.
Thus, <span class="math">Gf[/spoiler] cannot equal <span class="math">U(X)[/spoiler].

What am I missing?

>>4340470
I don't see any reason you can assume <span class="math">K(x,y)=A(x)B(y)[/spoiler]. Not all functions of two variables separate in this way (<span class="math">\cos(x+y)[/spoiler], for instance).


>>4339176
>Hey, looks like you got yourself a tripcode :)
Yes, and you can probably guess where I got the idea to enclose a short, relevant word between two /'s.

>>4338837
Sorry, I'm getting myself confused with something else (it's late — that's my excuse). You can show that <span class="math">\mathcal{K}[/spoiler] is the limit of finite rank operators. I'll omit the details, but any book that discusses compact operators will include this as its first or second example. All that's required is that <span class="math">||K||_{L^2([0,1]\times[0,1])}<\infty[/spoiler].

>>4338813
<span class="math">\mathcal{K}[/spoiler] maps <span class="math">L^2[/spoiler] bounded sets to precompact sets:

Suppose <span class="math">u_n[/spoiler] is a bounded sequence in <span class="math">L^2(\Omega)[/spoiler], <span class="math">||u_n||_{L^2}\leq C[/spoiler].

Using the Arzelà–Ascoli theorem, you can show that <span class="math">Ku_n[/spoiler] must have an <span class="math">L^2[/spoiler]-convergent subsequence.

>>4338797
>Note that K^2 is compact, self-adjoint and positive
oops. Disregard the "self-adjoint". It isn't needed, and it would only obviously be true if <span class="math">K(x,y)=K(y,x)[/spoiler] for all <span class="math">x,y\in[0,1][/spoiler].

>>4338805
The composition of a bounded operator and a compact operator is compact.

>>4338788
[cont'd]

Note that <span class="math">\mathcal{K}^2[/spoiler] is compact, self-adjoint and positive with <span class="math">\mathcal{K}^2(f)=f[/spoiler] and <span class="math">\mathcal{K}^2(g)=g[/spoiler]. Since <span class="math">f[/spoiler] and <span class="math">g[/spoiler] are positive, by (c) it follows that 1 must be the spectral radius of <span class="math">\mathcal{K}^2[/spoiler]. By (a), the corresponding eigenspace must have dimension one. Hence, <span class="math">f[/spoiler] and <span class="math">g[/spoiler] must be a multiples of each other: <span class="math">f= \alpha g[/spoiler] for some <span class="math">\alpha>0[/spoiler].

Applying <span class="math">\mathcal{K}[/spoiler] to both sides yields <span class="math">g = \alpha f[/spoiler]. Consequently, <span class="math">\alpha^2=1[/spoiler]. Since <span class="math">\alpha[/spoiler] must be positive, we conclude <span class="math">\alpha=1[/spoiler].

>>4338788
[cont'd]


Note that <span class="math">\mathcal{K}^2[/spoiler] is compact, self-adjoint and positive-definite with <span class="math">\mathcal{K}^2(f)=f[/spoiler] and <span class="math">\mathcal{K}^2(g)=g[/spoiler]. Since <span class="math">f[/spoiler] and <span class="math">g[/spoiler] are positive, by (c) it follows that 1 must be the spectral radius of <span class="math">\mathcal{K}^2[/spoiler]. By (a), the corresponding eigenspace must have dimension one. Hence, <span class="math">f[/spoiler] and <span class="math">g[/spoiler] must be a multiples of each other: <span class="math">f= \alpha g[/spoiler] for some <span class="math">\alpha>0[/spoiler].

Applying <span class="math">\mathcal{K}[/spoiler] to both sides yields <span class="math">g = \alpha f[/spoiler]. Consequently, <span class="math">\alpha^2=1[/spoiler]. Since <span class="math">\alpha[/spoiler] must be positive, we conclude <span class="math">\alpha=1[/spoiler].

[oops. I posted a solution and then deleted it after I realized it was incomplete.]

This solution is pretty straightforward — if you've had a graduate course in functional analysis. I realize there must be a more elementary solution, but since I deal with integral operators so often these days, this is what came to me first:

Let <span class="math">\mathcal{K}:L^2([0,1])\to L^2([0,1])[/spoiler] be the compact, self-adjoint operator <span class="math">\mathcal{K}(u) =\int_0^1 u(y)K(x,y)\,dy[/spoiler] (self-adjointness requires that <span class="math">K[/spoiler] be symmetric). <span class="math">\mathcal{K}[/spoiler] is also a positive operator in the sense that <span class="math">u>0\mathrm{ a.e. }\Rightarrow \mathcal{K}u>0[/spoiler] a.e.

A well-known result from functional analysis (Krein-Rutman):
If <span class="math">\mathcal{A}[/spoiler] is a compact, positive operator on <span class="math">L^2(\Omega)[/spoiler], then
(a) the spectral radius <span class="math">\rho_\mathcal{A}[/spoiler] is a simple eigenvalue of <span class="math">\mathcal{A}[/spoiler] (i.e., the corresponding eigenspace has dimension one),
(b) <span class="math">\rho_\mathcal{A}[/spoiler] has a corresponding eigenfunction that is positive a.e. <span class="math">(\Omega)[/spoiler],
(c) <span class="math">\rho_\mathcal{A}[/spoiler] is the _only_ eigenvalue that corresponds to a positive (a.e.) eigenfunction.

[Here's a link to a proof: http://www.worldscibooks.com/etextbook/5999/5999_chap1.pdf ]

I love this problem. The solution is pretty straightforward — if you've had a graduate course in functional analysis. I realize there must be a more elementary solution, but since I deal with integral operators so often these days, this is what came to me first:

Let <span class="math">\mathcal{K}:L^2([0,1])\to L^2([0,1])[/spoiler] be the compact, self-adjoint, positive-definite operator <span class="math">\mathcal{K}(u) =\int_0^1 u(y)K(x,y)\,dy[/spoiler] (positive-definiteness follows easily from the fact that <span class="math">K[/spoiler] is strictly positive and continuous on its compact domain, and therefore bounded away from 0).

A well-known result from functional analysis:
If <span class="math">\mathcal{A}[/spoiler] is a compact, self-adjoint, positive definite operator on <span class="math">L^2(\Omega)[/spoiler], then
(a) the spectral radius <span class="math">\rho_\mathcal{A}[/spoiler] is a simple eigenvalue of <span class="math">\mathcal{A}[/spoiler] (i.e., the corresponding eigenspace has dimension one),
(b) <span class="math">\rho_\mathcal{A}[/spoiler] has a corresponding eigenfunction that is positive a.e. <span class="math">(\Omega)[/spoiler],
(c) <span class="math">\rho_\mathcal{A}[/spoiler] is the _only_ eigenvalue that corresponds to a positive (a.e.) eigenfunction (this is a consequence of <span class="math">\mathcal{A}[/spoiler] being self-adjoint, and therefore having orthogonal eigenfunctions: two positive functions cannot possibly be orthogonal).


Note that <span class="math">\mathcal{K}^2[/spoiler] is compact with <span class="math">\mathcal{K}^2(f)=f[/spoiler] and <span class="math">\mathcal{K}^2(g)=g[/spoiler]. Since <span class="math">f[/spoiler] and <span class="math">g[/spoiler] are positive, by (c) it follows that 1 must be the spectral radius of <span class="math">\mathcal{K}^2[/spoiler]. By (a), the corresponding eigenspace must have dimension one. Hence, <span class="math">f[/spoiler] and <span class="math">g[/spoiler] must be a multiples of each other: <span class="math">f= \alpha g[/spoiler] for some <span class="math">\alpha>0[/spoiler].

Applying <span class="math">\mathcal{K}[/spoiler] to both sides yields <span class="math">g = \alpha f[/spoiler]. Consequently, <span class="math">\alpha^2=1[/spoiler]. Since <span class="math">\alpha[/spoiler] must be positive, we conclude <span class="math">\alpha=1[/spoiler].