Generic and Explicit Algebraic Geometric Computations (15.2.21,25,48)

Dummit and Foote Abstract Algebra, section 15.2, exercises 21, 25, 48:

21. Let $V$ be an algebraic set in $\mathbb{A}^n$ and let $f∈k[V]$ be nonzero. Define $V_f = \{v∈V~|~f(v)≠0\}$.
(a) Show that $V_f$ is a Zariski open set in $V$ (called a principal open set in $V$).
(b) Let $J$ be the ideal in $k[x_1,...,x_n,x_{n+1}]$ generated by $\mathcal{I}(V)$ and $x_{n+1}f-1$, and let $W = \mathcal{Z}(J) ⊆ \mathbb{A}^{n+1}$. Show that $J = \mathcal{I}(W)$ and that the map $π : \mathbb{A}^{n+1}→\mathbb{A}^n$ by projection onto the first $n$ coordinates is a Zariski continuous bijection from $W$ to $V_f$.
(c) If $U$ is any open set in $V$ show that $U=V_{f_1}∪...∪V_{f_m}$ for some $f_1,...,f_m∈k[V]$ (so that the principal open sets form a basis for the Zariski topology).

25. Suppose $f(x)=x^3+ax^2+bx+c$ is an irreducible cubic over a field $k$ of characteristic $≠2$, and let $D$ be its discriminant. Let $I=(x+y+z+a,xy+xz+yz-b,xyz+c)⊆k[x,y,z]$.
(a) Show that $I$ is a prime ideal if and only if $D$ is not a square in $k$, and that in this case, $I$ is actually a maximal ideal and $k[x,y,z]/I$ is the splitting field over $k$ for $f(x)$.
(b) If $D=r^2$ is a square over $k$, then show that if $Q_{\pm}=I+((x-y)(x-z)(y-z) \pm r)$ then $I=Q_- ∩ Q_+$ is a primary decomposition for $I$ and both $k[x,y,z]$ modulo $Q_-$ or $Q_+$ is the splitting field over $k$ for $f(x)$.

48. Show that $\mathcal{Z}(x^3-xyz+z^2)$ is the smallest algebraic set in $ℝ^3$ containing the points $S=\{(st,s+t,s^2t)~|~s,t∈ℝ\}$.

Proof: (21)(a) We see that $V_f$ is the complement in $V$ of $\mathcal{Z}(f)$, rendering $V_f$ an open set in the Zariski topology on $V$.
(b) It is clear that $W=\{(a,\dfrac{1}{f(a)})~|~a∈V_f\}$ by construction. Now to show $\mathcal{I}(W)=J$ we must show that if $$g = g_0(x_1,...,x_n) + x_{n+1} g_1(x_1,...,x_n) + ... + x_{n+1}^m g_m(x_1,...,x_n)$$ is zero on all of $W$ then $g≡0 \mod J$. Note that multiplication by a unit biconditionally preserves the property of being non-zero, and since $fx_n≡1 \mod J$, this is equivalent to showing $$gf^m ≡ f^m g_0(x_1,...,x_n) + f^{m-1} g_1(x_1,...,x_n) + ... + g_m(x_1,...,x_n)$$ is zero modulo $J$. Since this latter is a polynomial in variables $x_1,...,x_n$ that is zero on the nonempty open set $V_f⊆V$ hence on all of $V$ (cf. exercise 11), we see it can be written as a $k[x_1,...,x_n]$-linear combination of the generators of $\mathcal{I}(V)$, hence particularly is zero modulo $J$.
(c) If $U=V-\mathcal{Z}(f_1,...,f_m)$ for some $f_1,...,f_m∈k[V]$, then $$U=V-(\mathcal{Z}(f_1)∩...∩\mathcal{Z}(f_m))=$$$$(V-\mathcal{Z}(f_1))∪...∪(V-\mathcal{Z}(f_m))=V_{f_1}∪...∪V_{f_m}$$ as desired.

(25)(a+b) With some preliminary canceling of leading terms, we rewrite $I$ in the following form: $$I=(z+y+x+a,y^2+xy+ay+x^2+ax+b,x^3+ax^2+by+c)$$ At this point, we may observe $k[x,y,z]/I$ is generated as a vector space over $k$ by $1,x,x^2,y,yx,yx^2$, hence is of rank at most $6$. As well, if $φ : k[x,y,z]→K$ is the (surjective) ring homomorphism to the splitting field $K$ of $f(x)$ over $k$ by sending variables to roots of $f(x)$, it is clear $I⊆\text{ker } φ$ so that there is a factored (surjective) morphism $\overline{φ} : k[x,y,z]/I→K$. Since $K$ is a degree $6$ extension of $k$ when $D$ is not a square, it follows that in this case $\overline{φ}$ is an isomorphism so that $I$ is maximal and $k[x,y,z]/I$ is a splitting field.

Suppose $D=r^2$. Notice that one of $Q_{\pm}$, say $Q_+$, is contained in $\text{ker }φ$, and that $I⊆Q_-∩Q_+⊂Q_+$ so that we have a series of factoring surjective morphisms $k[x,y,z]→k[x,y,z]/I→k[x,y,z]/Q_+→K$. As $D$ is square, $K$ is of degree $3$ over $k$, so that necessarily $k[x,y,z]/Q_+$ is of rank $3$, implying $Q_+=\text{ker }φ$ and is thus a maximal ideal with $k[x,y,z]/Q_+≅K$. Since $Q_-$ is the image of $Q_+$ under the automorphism on $k[x,y,z]$ swapping $x$ and $y$, it follows $Q_-$ is also maximal and $k[x,y,z]/Q_-≅K$ as well. As for $I$, it is an easy fact to verify that for $k$-algebras satisfying finite generation as a vector space over $k$, being an integral domain is equivalent to being a field (consider linear dependence over powers of an arbitrary element in order to obtain an inverse), so that $I$ not being maximal ensures $I$ is not prime in this case.

(48) The most routine way to prove this would be to show $(x^3-xyz+z^2)$ is the kernel of the morphism $\overline{φ} : ℝ[x,y,z] → ℝ[s,t]$ given by $\overline{φ}(x)=st$, $\overline{φ}(y)=s+t$, $\overline{φ}(z)=s^2t$ by the method of Proposition 8. But instead, we shall show it more directly without the use of Grobner bases. As can be easily checked, $(x^3-xyz+z^2)⊆\text{ker }\overline{φ}$. Now, suppose $g∈\text{ker }\overline{φ}$ may be written in the form $g=f(x,y)+z·g(x,y)$ for at least one of $f(x,y), g(x,y)$ nonzero. That is to say, $f(xy,x+y)+x^2y·g(xy,x+y)=0$. Taken modulo $(x)$, this means $f(xy,x+y)≡f(0,y)≡f(x,y)≡0 \mod (x)$, implying $x$ is a factor of $f(x,y)$. This implies the existence of a nontrivial solution to the equation $f'(xy,x+y)+y·g(xy,x+y)=0$. Taken modulo $y$ this shows $y$ is a factor of $f'(y,x)$, i.e. again $x$ is a factor of $f'(x,y)$. Continuing in this fashion, we may perform infinite descent on the $x$-factor multiplicity of $f(x,y)$ and $g(x,y)$ which is impossible unless both of them are zero.$~\square$

Primary Ideals and Decompositions (15.2.28,31-32)

Dummit and Foote Abstract Algebra, section 15.2, exercises 28, 31-32:

28. Prove that each of the following rings have infinitely many minimal prime ideals, and that $(0)$ is not the intersection of any finite number of these (so $(0)$ does not have a primary decomposition in these rings):
(a) The infinite direct product ring $ℤ/2ℤ×ℤ/2ℤ×...$
(b) $k[x_1,x_2,...]/(x_1x_2,x_3x_4,...)$
31-32. Let $Q_1$ and $Q_2$ be $P$-primary ideals in a commutative ring with identity $R$. Show that $Q_1∩Q_2$ is also a $P$-primary ideal, and prove that if $P$ is a maximal ideal, then $Q_1Q_2$ and $Q_1+Q_2$ are also $P$-primary ideals.

Proof: 28. (a) Note that since every element of $ℤ/2ℤ×ℤ/2ℤ×...$ is multiplicatively idempotent, it follows that the quotient of $ℤ/2ℤ×ℤ/2ℤ×...$ with any of its prime ideals results in an integral domain with two elements, $1$ and $0$. Therefore, every prime ideal in this ring is a maximal ideal, and in particular is minimal. If we let $I_n$ denote the ideal of elements whose $n^{\text{th}}$ coordinate is zero, then we easily observe an infinite collection of prime/maximal ideals. Now, we shall prove that given any ideal $I$ with the property that it contains an element $x$ which has infinitely many nonzero coordinates, then $P∩I$ also has this property when $P$ is a prime ideal; inductively, this will prove particularly that any finite intersection of prime ideals is nonzero. To wit, write $x=y+z$ for $yz=0$ and each of $y,z$ having infinitely many nonzero coordinates. Then since $yz∈P$ we must have at least one of $y,z∈P$, say $y∈P$. Then since $y=yx$ we also have $y∈I$, hence $y∈P∩I$ as claimed.

(b) For any prime ideal $P⊆R=k[x_1,x_2,...]/(x_1x_2,x_3x_4,...)$, since $\overline{x_1}\overline{x_2}=0$ we must have $\{\overline{x_{2n-1}},\overline{x_{2n}}\}∩P≠ø$ for each $n∈ℕ$. Conversely, if $S⊆ℕ$ is such that exactly one of $2n-1$ or $2n$ is in $S$ for each $n∈ℕ$, and $P_S=(x_i~|~i∈S)⊆k[x_1,x_2,...]$, then $k[x_1,x_2,...]/P_S≅R/\overline{P_S}$ is an integral domain and hence $\overline{P_S}$ is a prime ideal. It follows that the minimal prime ideals of $R$ are exactly $\overline{P_S}$ for such sets $S$, of which there are (uncountably) infinitely many. Now, let $P_{S_1},...,P_{S_n}$ be any finite collection of such ideals. For each $1≤i≤n$ let $α_i∈\{2i-1,2i\}$ be such that $\overline{x_{α_i}}∈P_{S_i}$. Then since provided each $m_1,m_2...$ is monomial, for polynomials $p∈(m_1,m_2,...)$ if and only if each monomial term of $p$ is divisible by some $m_j$, we see $β=x_{α_1}x_{α_2}...x_{α_n}∉(x_1x_2,x_3x_4,...)$ while $β∈P_{S_1}∩...∩P_{S_n}$, so that $\overline{P_{S_1}}∩...∩\overline{P_{S_n}}$ is nonzero.

31-32. Observe: $$\text{rad }(Q_1Q_2)=\text{rad }(Q_1∩Q_2)=(\text{rad }Q_1)∩(\text{rad }Q_2)=P∩P=P$$ $$\text{rad }(Q_1+Q_2)=\text{rad }(\text{rad }Q_1+\text{rad }Q_2)=\text{rad }(P+P)=\text{rad }P=P$$ Therefore it suffices to prove $Q_1∩Q_2$ is a primary ideal, and that when $P$ is maximal, so too are $Q_1Q_2$ and $Q_1+Q_2$.

Suppose $xy∈Q_1∩Q_2$ where $y∉Q_1∩Q_2$, say $y∉Q_1$. Then $x^n∈Q_1⊆P=\text{rad }Q_2$ for some $n$, and therefore $x^{nm}∈Q_1∩Q_2$ for some further $m$.

Now suppose $P$ is maximal. Now $Q_1Q_2$ and $Q_1+Q_2$ are primary by Proposition 19.4.$~\square$

Potential Problems

1. a. (Easy) Find $x$ for $x^4 ≡ 16 \mod 41$.
b. (Medium) Find $x$ for $x^5 ≡ 64 \mod 97$.
c. (Hard) Find $x$ for $x^7 ≡ 1337 \mod 2015$.
Source: Original

2. $x,y,z$ are complex numbers such that $$x+y+z=1$$ $$x^2+y^2+z^2=2$$ $$x^3+y^3+z^3=3$$ Find $x^4+y^4+z^4$.
Source: Dummit and Foote Abstract Algebra, Exercise 14.6.23(a)

3. Find necessary and sufficient conditions for $z∈ℂ$ so that $$\sum_{n=1}^∞ \dfrac{1}{1+z^n}$$ converges.
Source: Walter Rudin Principles of Mathematical Analysis, Exercise 3.6(d)

4. A number with prime factorization $p_1^{α_1}p_2^{α_2}...p_n^{α_n}$ is said to be $B$-powersmooth if $p_i^{α_i} ≤ B$ for all $i$. If $γ(B)$ is the set of all positive $B$-powersmooth numbers, prove $$\sum_{k∈γ(B)} \dfrac{1}{k} ≤ \dfrac{B+1}{2}$$ Source: Original ($B$-powersmoothness, however, is an established term)

5. Let $S$ be a subset of the natural numbers. If $S_n = S∩\{1,2,...,n\}$, then we define the arithmetic density of $S$ to be $\lim_{n→∞} \dfrac{|S_n|}{n}$ where the limit exists. Show that if the infinite sum $\sum_{k∈S} \dfrac{1}{k}$ converges, then the arithmetic density of $S$ is zero.
Source: Original/maintstream

6. Let $B$ be the unit ball of complex numbers (i.e. complex numbers $α$ for which $|α| ≤ 1$), and let $f : B→B$ be a continuous map such that $|α-β| > |f(α)-f(β)|$ for all distinct complex numbers $α,β∈ℂ$. Show there exists a unique complex number $x$ such that $f(x)=x$.
Source: Banach fixed point theorem on $ℂ$ as a metric space

7. Show the function $f(x) = \sum_{k=1}^∞ kx^k$ is well defined and continuous on the interval $(-1,1)$. Source: James Munkres Topology, Exercise 7.46.5

8. A countably infinite number of party-goers will be playing a game. The game will start by every guest donning either a red- or blue-colored hat, and though they will see the colors of every other guest's hat, they will not know their own. Without allowing time for communication, they will then be simultaneously ushered into private rooms and be made to guess the color of their own hats. If all but finitely many guests guess correctly, they win. Is there an a priori strategy the guests can formulate so that they always win?
Source: Mainstream

9. Let $α,β$ be infinite binary sequences (or IBSs), more formally $α,β : ℕ→\{0,1\}$. We define their correlation as $$C(α,β)=\lim_{n→∞} \dfrac{\sum_{i=1}^∞ \text{XNOR}(α(i),β(i))}{n}$$ when the limit exists, where $\text{XNOR}(x,y)=1$ if $x=y$ and $\text{XNOR}(x,y)=0$ otherwise. For example, $C(α,α)=1$, and if $β$ is defined as $β(i)=α(i)$ for all even $i$ and $β(i)=1-α(i)$ otherwise, then $C(α,β)=\dfrac{1}{2}$. We shall say $α$ and $β$ are uncorrelated if $C(α,β)=\dfrac{1}{2}$.

Fixing a pair of IBSs $X=\{x_1,x_2\}$, does there always exist another IBS uncorrelated to them both? What about if $X$ is an arbitrary finite collection of IBSs? Or an arbitrary countable collection?
Source: Original

10. Let $Γ$ be an arbitrary sequence of vectors $$Γ : ℕ→ℝ^m$$ such that $|Γ(n)| ≤ 1$ for all $n∈ℕ$. Does there always exist a sequence of scalars $β : ℕ→\{-1,1\}$ such that $\lim_{n→∞} \dfrac{\sum_{i=1}^n β(i)·Γ(i)}{n} = 0$? What about such that the sequence $|\sum_{i=1}^n β(i)·Γ(i)|$ is bounded?
Source: Original. Note that I don't yet have an answer for the latter question.

11. A $3$-sided die is rolled and its value $A$ is recorded. Then $A$ $5$-sided dice are rolled and their sum $B$ is recorded. Finally, $B$ $7$-sided dice are rolled and their sum $C$ is recorded. Find the standard deviation of $C$ as a random variable.
Source: Euler Project Problem Take on #389

12. If $G$ is a graph whose edges are labeled with integers, let $ε(G)$ denote the sum of all those integers. If $G$ is a connected graph, then let $ε'(G) = \min \{ε(H)\}$, where $H$ ranges over the connected subgraphs of $G$. If $G$ is the graph depicted below, then calculate $ε'(G)$ and demonstrate proof.

Source: Euler Problem Take on #107. Image modified from here.

13. You are blindfolded, then given a deck of $52$ cards in which $3$ of the cards have been flipped up, then inserted into the deck randomly. Without taking the blindfold off, rearrange the deck into two stacks such that both stacks have the same number of up-flipped cards. (You are allowed to flip as many cards as you please.)
Source: Mainstream

14. There are $n$ balls rolling along a line in one direction and $k$ balls rolling along the same line in the opposite direction. The speeds of the balls in the first group and in the second group are equal. Initially the two groups of balls are separated from one another and at some point the balls start colliding. The collisions are assumed to be elastic. How many collisions will there be?
Source: Mainstream

15. There are $30$ students in a class. The teacher has written every student's name on a stick, shuffled them, and handed them out randomly to each student. If a sequence of students is made by the process of selecting a random student $a$, then continuing to the student $b$ whose name is on $a$'s stick, and so forth until a student is repeated in the sequence, what is the probability that the entire class will be in the sequence generated?
Source: Original

16. Simplify $$\sqrt{2+\sqrt{3}}$$ Source: Mainstream

17. If $f$ is an arbitrary polynomial in $n$ variables, show that the number of distinct polynomials that arise from permuting these variables always divides $n!$. (For example, the permutation swapping $x$ and $y$ in $x+y-z$ doesn't achieve another polynomial, while the permutation sending $x↦y$, $y↦z$, and $z↦x$ results in $z+x-y≠x+y-z$)
Source: Classical result

18. Below is the finite projective plane known as the Fano plane. An automorphism of the Fano plane is a permutation of the vertices preserving all line incidences (for example, $1$ would need to remain on the unique line containing $2$ and $3$, and $5$ on the same line as $4$ and $1$). A simple example of an automorphism would be rotating the whole diagram by $120$ degrees. For any automorphism $σ$, does there always exist a point for which $σ(x)=x$?

Source: Original (no knowledge of projective geometry is expected)

19. There are $7^9$ $3×3$ matrices with values from the modular ring $ℤ/7ℤ$. How many of them are invertible over $ℤ/7ℤ$?
Source: Original

20. Let $A$ be an infinite collection of points on the unit circle. Show there exists a point $x$ on the circle such that for any $ε > 0$, there exists $a∈A$ of distance to $x$ strictly less than $ε$.
Source: Original/compactness of circle

21. Show that there exist no nontrivial integer solutions to the Diophantine equation $$x^2+y^2=3z^2$$ Source: Mainstream

22. Fix $m∈ℤ$, and let $p(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0$ be a polynomial such that $\text{gcd}(a_n,a_{n-1},...,a_0,m) = 1$. Show that if $q(x)$ has the property that at least one of its coefficients is not divisible by $m$, then so too does $p(x)·q(x)$.
Source: Dummit and Foote Abstract Algebra, Exercise 7.2.2 (decontextualized)

23. You have $13$ differently colored beads and a lace of string. There are $5$ pairs of colors that you either consider gaudy or too similar to display next to one another. Prove that you can still make a full bracelet of these colors while avoiding these unfavorable adjacencies.
Source: Original

24. We say $a > 0$ is a universal chord if for every continuous function $f : [0,1]→ℝ$ such that $f(0)=f(1)$, there exists $x∈[0,1-a]$ such that $f(x)=f(x+a)$. Show that the universal chords are exactly $1/n$ for all $n∈ℕ$.
Source: Original

25. Let $p(x)$ be an arbitrary $n^{\text{th}}$ degree polynomial with natural coefficients.
(a) If you are allowed to ask for the value of $p(α)$ for any natural $α$, how many evaluations will you need at maximum in order to determine $p(x)$?
(b) If you are allowed to ask for the value of $p(α)$ for any real $α$, how many evaluations will you need at maximum in order to determine $p(x)$?
Source: Original

26. (a) You have one fairly weighted coin. Determine a game to play with this coin (that will end with probability $1$) whose odds of winning are exactly $1/3$.
(b) If you instead define "game" more strictly to mean "there is no sequence of coin flips (no matter how infinitesimal the likelihood) that will indefinitely prolong the game," prove that there exists no game you can play whose odds of winning are exactly $1/3$.
Source: (a) Old Putnam problem (b) Original take on Putnam problem

27. Prove that the polynomial $$x^6-23x^4+135x^2-225$$ has a root modulo $p$ for every prime $p$, but has no roots in $ℤ$.
Source: Dummit and Foote Abstract Algebra, Exercise 14.3.7.

28. Write the numbers from $1$ to $64$ on a checkerboard, with numbers $8(n-1)+1,...,8(n-1)+8$ occupying the $n^{\text{th}}$ row from left to right. For each coloring of the squares either white or black satisfying the condition that each row and each column contain exactly four white squares and four black squares, show that the sum of the white squares is equal to the sum of the black squares.
Source: Putnam Exam 2001, B-1

29. Let $f(x)$ be a nonconstant polynomial with positive integer coefficients. If $n$ is a positive integer, prove $f(n)$ divides $f(f(n)+1)$ if and only if $n=1$.
Source: Putnam Exam 2007, B-1

30. Suppose $X$ is a random variable taking on non-negative integers, such that $E[X]=1$, $E[X^2]=2$, and $E[X^3]=5$, where $E[Y]$ is the expected value of the variable $Y$. Determine the smallest possible probability of the event $X=0$.
Source: Putnam Exam 2014, A-4

31. There are $7$ different medals in the Arstotzkan army, which may be awarded multiple times to indicate glory. For any two distinct collections of medals, one is decisively more glorious than the other. However, the bureaucratic rules for determining exactly which of the two is more glorious is unreasonably complicated. All you know is that "more glorious" is a transitive relation, and that if one soldier has as many or more medals of every type than another (and has strictly more of \textit{some} type), he is a greater glory to Arstotzka than the other.

Prove that every (potentially infinite) regiment of Arstotzkan soldiers has a least glorious member.
Source: Original, based off Hilbert basis theorem/monomial orderings

32. Find the set of natural numbers that appear at the beginning of a positive integral power of $2$ (written in base $10$). Proof is easy log 10.

33. Something something hexachordal theorem?

34. You start with a thousand dollars, and continue to play the following game for as long as you are not bankrupt: You flip a coin, and win a dollar if it is heads, and lose a dollar if it is tails. (a) If you play with a fair coin, what is the probability you will eventually go bankrupt? (b) If you play with a slightly fixed coin with probability of heads being $0.501$, what is the probability you will eventually go bankrupt?
Source: Original

35. Let $a_n$ be the sequence defined by $a_0 = 1$ and $a_{n+1} = 2^{a_n}$. Prove that, modulo $m$, this sequence stabilizes after at most $m$ terms: $a_{m-1} \equiv a_m \equiv a_{m+1} \equiv ~...~ \text{mod }m$. Note: This sequence must be constructed in the integers, and only then reduced mod $m$; you cannot recursively define $a_{n+1}$ only in terms of the $m$-modular residue of $a_n$, because $a \equiv b~\text{mod }m$ does not necessarily imply $x^a \equiv x^b~\text{mod m}$.

Solution: Prove that if $a, b \geq \phi(m)$ and $a \equiv b ~\text{mod }\phi(m)$, where $\phi$ is Euler's totient function, then $x^a \equiv x^b ~\text{mod }m$ (reduce via Chinese remainder theorem to the case $m=p^r$, and treat $p=2$ as a special case). Then stabilization of $a_n$ after at most $m-1$ terms modulo $\phi(m)$ implies stabilization of $a_n$ after at most $m$ terms modulo $m$.

Source: Putnam B5, 1997

36. Killing hydras.

37. Cuckoo's egg/look-and-say puzzle

38. Prove $22$ is the only number whose look-and-say sequence does not grow indefinitely.

39. Take a chess knight, and restrict his movement pattern to a particular 2 squares (instead of his usual 8). Place him on a toroidal 100x100 grid. After 1 move, he may be in 2 different locations. After 2 moves, he may be in 3 different locations. After a sufficiently long time, what is the maximal number of different locations he may be in? Does it depend on which two 2 squares of movement he is restricted to?
Source: Original

40. If the knight may also choose to sit still for a given turn, how many turns until the knight may potentially be anywhere on the torus? Assume the two nontrivial movements are not opposites of each other.

41. Random points/geodesics on the surface of the sphere.
Source: Original

42. Fifth-arc robot meanderings (Euler project problem 208). Prove that any walk back home must consist of a multiple of five arcs, and return the robot to its original northward-facing position.

43. Josephus suicide problem (solution: even/odd recursive formula). (a) If you are the $1337^\text{th}$ soldier of a group of $2018$, who do you give the knife to? (b) Prove $n+f(n)$ is injective, where $f(n)$ is the survivor in a group of $n$ soldiers. Solve $n$ in $n+f(n)=2018$ (solution: $1355$).
Source: (b) is original.

44. Rotationally distinct colorings of a dodecahedron.

45. Suppose that early in the universe, two planets are a mere hundred million kilometers apart. A rocket launches from one toward the other at a constant speed of 10km/s. Ordinarily, the rocket would reach its destination in three to four months. However, this universe is expanding uniformly, so that the distance between the two planets is increasing at the speed of light (300,000km/s), or even faster. Show that despite this expansion, the rocket will eventually reach the other planet. (Solution: If the speed of the rocket is $1$ compared to the expansion rate of $k$ and initial planetary distance $d$, then if $f(t)$ is the distance traveled from the planet, then we have the differential equation $f' = k \dfrac{f}{d+kt} + 1$. Solve this. Hint: $x \text{log}(x)$)
Source: Ant on a rope problem

46. Show that if $a | b^2 | a^3 | b^4 | a^5 | ...$ ad infinitum, then $a=b$.

47. Let $a,b$ be whole numbers. Show that if $ab+1$ divides $a^2+b^2$, then their quotient is a square number. Hint: Introduce a variable $N$, and rewrite the problem as solving for positive triples satisfying $(ab+1)N = a^2+b^2$. This can be interpreted as a quadratic in $a$. And when polynomials have one solution, they typically have another... what's up with that?

48. "Windmill" problem, IMO 2011 C3

49. (a) If a coin is flipped $2n$ times, let $P(n)$ be the probability that you get exactly $n$ heads and $n$ tails (the most likely distribution). Prove that $P(n) \to 0$ as $n \to \infty$
(b) Let $P_m(n)$ be the probability that the sum of $n$ rolled dice is $m$, and let $\displaystyle P(n) = \max_m P_m(n)$. Prove that $P(n) \to 0$ as $n \to \infty$.
(Proof of (a): Stirling's approximation. Proof of (b) Stirling's approximation + ???, or Central Limit Theorem)

50. Suppose $2n$ coins of different denominations (repetitions allowed) are lined up in a row. Players A and B take turns snatching a coin on either the leftmost or rightmost end of the line. Prove that when playing optimally, Player A will never lose to Player B, no matter the starting coin pattern. (Proof: Player A can always force a final snatch pattern of $ABABA...AB$ or $BABAB...BA$. Force the one that favors him.)

51. Let $e(x)$ be a continuous family of idempotent matrices. Show that the column rank of $e(x)$ is constant at all points $x$. (Serre-Swan stuff. Proof: $1-e(x)$ is another such family whose column spaces are orthogonal and generate the entire space; since the max column rank is an open set, and min column rank a closed set, this implies the theorem)

52. Characterize the one-parameter subgroups of $\text{GL}_n(\mathbb{C})$. Proof

53. The director of a prison offers 300 death row prisoners, who are numbered from 1 to 300, a last chance. A room contains a cupboard with 300 drawers. The director randomly puts one prisoner's number in each closed drawer. The prisoners enter the room, one after another. Each prisoner may open and look into 200 drawers in any order. All drawers are closed again afterwards. If, during this search, each prisoner finds his number in one of the drawers, all prisoners are pardoned. If just one prisoner does not find his number, all prisoners die. Before the first prisoner enters the room, the prisoners may discuss strategy — but may not communicate once the first prisoner enters to look in the drawers.

If all prisoners guess randomly, the chance they survive is less than the chance of correctly guessing a preferred atom from every single atom comprising one thousand Earths (less than one in $10^{53}$). However, if they're smart, the prisoners can formulate a strategy with a survival probability of ~60%; can you find it? Source: 100 prisoners problem

54. (a) Let $f(x)$ be any degree $n-1$ polynomial, and let $g(x) = (x-1)(x-2)...(x-n)$. Show that $f(x)$ may be written as a linear combination of the polynomials $g_m(x) := \frac{g(x)}{x-m}$ for $1 \leq m \leq n$.
(b) Let $M$ be any complex-valued matrix. Show that there exists a nonzero polynomial $f(x)$ with real coefficients such that $f(M) = 0$.

55. (a) A gnat is lost in 3D space, and calls you (situated at the origin) for help. He tells you that from his perspective, the line segments $v$ and $w$ look like equal-length segments of the same straight line. What is the gnat's position? (Equal length is one dimension; parallel is another dimension; lying on the same line is the final dimension). (b) A different gnat is lost and disoriented. The line segment $v$ appears to have length $\alpha$ and points straight "up." The line segment $w$ appears to have length $\beta$ and points $30$ degrees down of left. What is the gnat's position? (3D space + orientation is four variables; each line segment's length + angle constitutes two-dimensional reduction) (c) Another gnat is lost. Three line segments $u,v,w$ float in space, and from the gnat's perspective they constitute a triangle. What is the gnat's position? (Will need to choose third line segment a little specifically)

56. 100 students are taking an oral exam that’s structured a little unusually. The professor asks each student, in turn, the following question: “How many of the 100 students will get a “pass” grade by the time the exam is finished?” Each student must reply with some number, from 0 to 100. The professor then immediately grades the student either “pass” or “fail” and announces the grade out loud – all the remaining students hear it. Then the next student is asked the same question, and so on.

After everyone’s had their turn, an inspector examines all the answers and the grades. If there’s any student who answered correctly (i.e. exactly that number of students passed), but was failed by the professor, all the failing grades are changed to passing, and so all students pass the exam. If there’s no such instance of unfair failing, there are no changes.

Can the students come up with a strategy that will guarantee everyone will pass the exam? Source: Slate Star Codex, Open Thread 145 comments

57. A musical instrument can produce 9 distinct tones. A "beat" is a permutation of these tones in some order. A "transition" is a pair of beats where the first is related to the last by a single adjacent transposition of tones. A "song" is a sequence of transitions, e.g. 1234 - 1324 - 3124. Does there exist a song that includes every transition (forward or backward) exactly once?

58. Solve all $f : \mathbb{Z} \to \mathbb{Z}$ with $2f(a) = f(2b) = f(f(a+b))$ for all $a,b$. (Proof: $a=0$ gives us a way to simplify any $f(f(...))$ expression; applying to $b=0$ gives us a way to reduce any $f(2a)$ expression; applying this to the hypothesis tells us $f(a+b) = f(a) + f(b) - f(0)$, which implies $f$ is affine. Then the characterization $f(n) = 0$ or $f(n) = 2n + C$ follows)

59. Find the covariance matrix of $(x,y)$ distributed uniformly randomly over the unit equilateral Sierpinski triangle. (Answer: 1/18 times the identity. Source: Jane Street advertisement on SSC)

60. In the land of Humilia, a game is played between two players with 101 stones in a pot between them. On each turn, a player may take 1-5 stones from the pot, and nominally, the winner is whoever winds up with the most stones in the end. However, modesty is valued above all in Humilia, and if a player wins by more than three stones in the end, they will be shunned and disqualified from the tournament. Under perfect play, do you choose to be the player who plays first, or second?

61. A 64-player binary tournament bracket is about to start. You plan to free up your schedule in advance to watch some of the matchups (meaning, you can plan to watch the second semifinal, for example, but you cannot decide to watch one game or another based on the results of previous matches and teams seen). What is the minimum number of matches you must plan to see in order to definitely answer any (well-posed) question of the form, "Who won in the match between Team X and Team Y?" Solution: 21

62. You and your friend's new favorite game is "topological nim": You take your favorite compact metric space $X$, and Player 1 chooses a number $r$ less than the diameter of $X$. Starting with Player 1, each removes a closed disk of radius $r$ from the space $X$ on their turn, until one player—the winner—removes what remains of the space on his turn.

For each $n$, who wins topological nim on $S^n$ with the standard metric (easy)? The p-adics (slightly harder)? $\mathbb{RP}^n$ (tough)?

63. Separating axis theorem for polygons, statement that faces are enough. (In 3d, need cross products of edges.)

64. What is the diameter of the intersection of two unit balls in $\mathbb{R}^n$, each positioned on the boundary of the other?

Relative Randomness as Infinite Binary Sequences

Given infinite binary sequences $α,β : ℕ → \{0,1\}$, define $$δ_n = \dfrac{\sum_{i=1}^n {γ_i}}{n}$$ where $γ_i$ is the comparison of $α$ and $β$, i.e. $γ_i=1$ if $α(i)=β(i)$ and $γ_i=0$ otherwise. If $δ_n→z$ for some $z∈[0,1]$, then we write $δ(α,β)=z$. If $z=\dfrac{1}{2}$ in this case, we say $β$ is random relative to $α$ (or obviously vice versa). If $A$ is a set of infinite binary sequences, then we say $β$ is random relative to $A$ if $δ(α,β)=\dfrac{1}{2}$ for all $α∈A$.

Theorem 1 (Existence of Coins): If $X=(x_i)_{i∈ℕ}$ is a countable set of infinite binary sequences, then there exists an infinite binary sequence relatively random to $X$.

Proof: Choose any decreasing real sequence $ε_n→0$. We shall construct an infinite binary sequence $α$ such that for some sequence $N_n$ we have $|δ_i(α,x_j)-\dfrac{1}{2}| < ε_n$ for all $i ≥ N_n$ and $j ≤ n$. Hence as $i→∞$ we shall have $δ_i(α,x_j)→\dfrac{1}{2}$ for arbitrary $j$, implying $δ(α,x_j)=\dfrac{1}{2}$.

We shall attain this by constructing a sequence of finite binary sequences $α_{N_m} : \{1,...,N_m\}→\{0,1\}$ that are pairwise extensions of one another, and such that $|δ_i(α_{N_m}^*,x_j)-\dfrac{1}{2}| < ε_j$ for all free variables subject to $j≤m$ and $N_m+2^{m+1}≥i≥N_j$, and for all $α_{N_m}^* : \{1,...,N_m+2^{m+1}\}→\{0,1\}$ extending $α_{N_m}$. Then the sequence $α$ defined by $α(n) = α_{N_m}(n)$ for any $N_m≥n$ will satisfy the hypothesis above.

This shall be obtained by induction on $m$. (The base case will become superfluous, but is useful for comprehension) For $m=1$, let $β_1(k)=Φ_1(k)$ where $Φ_1(k)≡|\{j~|~j < k, x_1(j)=x_1(k)\}| \mod 2$, and then since we see $δ(β_1,x_1) = \dfrac{1}{2}$, choose $N_1$ large enough so that $$|\dfrac{(\sum_{j=1}^i γ_j)+4}{i+4} - \dfrac{1}{2}| < ε_1$$ $$|\dfrac{\sum_{j=1}^i γ_j}{i+4} - \dfrac{1}{2}| < ε_1$$ for $i ≥ N_1$, where $γ_i$ is the comparison between $β_1$ and $x_1$. Then the restriction $α_{N_1}$ of $β_1$ onto the set $\{1,...,N_1\}$ satisfies the hypothesis for $m=1$.

Now suppose appropriate $α_{N_m}$ has been constructed. Define $β_{m+1}$ by $β_{m+1}(k)=α_{N_m}(k)$ for $k≤N_m$, and otherwise, $β_{m+1}(k)=Φ_{m+1}(k)$ where $$Φ_{m+1}(k)≡|\{j~|~j < k, θ(j)=θ(k)\}| \mod 2$$ $$θ(n)=[x_i(n)]_{1≤i≤m+1}$$ Notice, then, that for any $1≤i≤m+1$ and any $(m+1)×1$ binary vector $v$, the proportion of $k > N_m$ such that $θ(k)=v$ satisfying $x_i(k)=β_{m+1}(k)$ as opposed to $x_i(k)≠β_{m+1}(k)$ approaches $\dfrac{1}{2}$, with at most $1$ extra nonsatisfying $k$ given any of the limit populations observed. Since for each $k > N_m$ there is one such vector $v$ for which $θ(k)=v$, and since there are $2^{m+1}$ vectors overall, for all $1≤i≤m+1$ we observe the proportion of such $k > N_m$ for which $x_i(k)=β_i(k)$ as opposed to $x_i(k)≠β_i(k)$ approaches $\dfrac{1}{2}$, with at most $2^{m+1}$ extra nonsatisfying $k$ given any of the limit populations observed. Therefore, there is sufficiently large $N_{m+1}$ for which $|δ_i(β_{m+1},x_j)-\dfrac{1}{2}| < ε_{m+1}$ for all free variables subject to $j≤m+1$ and $i≥N_j$; all that is missing is the $α_{N_{m+1}}^*$, and the variable index of $ε$. To fix the first, we rechoose $N_{m+1}$ to satisfy $$|\dfrac{(\sum_{j=1}^i γ_j)+2^{m+2}}{i+2^{m+2}} - \dfrac{1}{2}| < ε_{m+1}$$ $$|\dfrac{\sum_{j=1}^i γ_j}{i+2^{m+2}} - \dfrac{1}{2}| < {m+1}$$ for all $i≥m$ where $γ_j$ ranges being relative over $α_{N_1},...,α_{N_{m+1}}$ toward $β_{m+1}$, and then let $α_{m+1}$ be the restriction of $β_{m+1}$ onto $\{1,...,N_{m+1}\}$. Now, observing the upper bound of $2^{m+2}$ on the lag of the previously mentioned proportions of the limit populations in conjunction with the conditions just now qualified to $N_{m+1}$, we may finally conclude $|δ_i(α_{N_{m+1}}^*,x_j)-\dfrac{1}{2}| < ε_j$ for all free variables subject to $j≤m+1$ and $N_{m+1}+2^{m+2}≥i≥N_j$, and for all $α_{N_{m+1}}^* : \{1,...,N_{m+1}+2^{m+2}\}→\{0,1\}$ extending $α_{N_{m+1}}$. This completes the induction, and the proof.$~\square$

With some further complication of the frequency by which we choose $1$ or $0$ given a finite binary pattern vector (i.e. changing $Φ$ so that it isn't merely alternating), the above proof should generalize to show the existence of arbitrarily weighted coins, yielding heads at any given probability in the unit interval.

~~~~~

Given an infinite binary sequence $β$ and $α : ℕ→[0,1]$, define $$δ_n = \dfrac{\sum_{i=1}^n {γ_i}}{n}$$ where $γ_i$ is the comparison of $α$ and $β$, i.e. $γ_i=1-α(i)$ if $β(i)=0$ and $γ_i=α(i)$ otherwise. If $δ_n→z$ for some $z∈[0,1]$, then we write $δ(α,β)=z$. If $z=\dfrac{1}{2}$ in this case, we say $β$ is random relative to $α$. If $A$ is a set of infinite binary sequences, then we say $β$ is random relative to $A$ if $δ(α,β)=\dfrac{1}{2}$ for all $α∈A$.

Theorem 2: If $X$ is a countable set of functions $x_i : ℕ→[0,1]$, then there exists an infinite binary sequence relatively random to $X$.

Proof (sketch): If we define $δ_n'=δ_n-\dfrac{1}{2}=\dfrac{\sum_{i=1}^n {(γ_i-\dfrac{1}{2})}}{n}$ and $δ'=\lim_{n→∞} δ_n'$, then an equivalent reformulation of the problem for the case when $A$ is of finite order $m$ becomes: "Given a sequence $(v_i)$ of vectors of the form $(w_1,...,w_m)$ where $w_i∈[-1,1]$, does there exist a sequence $β=(b_i)$ where $b_i = \pm 1$ such that when $σ_j = \sum^j b_i·v_i$, we observe $\lim_{n→∞} \dfrac{σ_n}{n} = 0$?" As well, having solved this finite case, the countably infinite case will follow in a cumbersome manner as above and will thus be omitted.

Choose a decreasing real sequence $ε_n→0$. For each $n$, let $B_n$ be a partition of $[-1,1]^m$ into finitely many regions (say $\omega_n$) of diameter less than $2ε_n$. We shall inductively construct $β$ so that for sufficiently large indices $n > N_k$, we shall have $σ_n < ε_k·n$. As such, starting with $ε_i$, follow this procedure for as long as it takes for $σ_n$ to be able to incur $\omega_{i+1}$ consecutive "errors" and still be less than $ε_i·n$: At the start, all regions of $B_i$ are "inactive." Given the choice to set $b_j = \pm 1$, if $v_j$ is located in a region of $[-1,1]^m$ that is active, then set $b_j = -1$ and deactivate that region. Otherwise, activate the region and set $b_j=1$. Move on to $v_{j+1},b_{j+1}$. This process is seen to cancel vectors in partial sums with a per-step error factor approaching less than $\dfrac{1}{2}2ε_i=ε_i$ in magnitude.$~\square$

As with the first theorem, with some complication of the region that is to be finitely partitioned, the proof should generalize to show the existence of arbitrarily weighted coins.

~~~~~

Fix an infinite binary sequence $θ$. For infinite binary sequences $α$ and $β$, define $P(α)=δ(α,θ)$ and $P(α~|~β)=δ(γ,θ)$ where $γ(n)=α(b_n)$, if $b_n$ is the $n^\text{th}$ smallest integer to satisfy $β(b_n)=θ(b_n)$.

Theorem 3 (Bayes' Theorem): Suppose $P(α)$ and $P(β)$ exist and are nonzero. Then $$P(α~|~β)·P(β) = P(β~|~α)·P(α)$$ where if one side is undefined, then so is the other.

Proof: Suppose without loss that $P(β~|~α)$ is well defined. Let $γ_α$ denote its helper function, so that $δ_m(γ_α,θ)$ is the fraction of values $a_n ≤ m$ such that $β(a_n)=θ(a_n)$. This latter observation leads us to the identity $$δ_n(γ_α,θ)·(n·δ_n(α,θ))=δ_n(γ_β,θ)·(n·δ_n(β,θ))$$ when $γ_β$ is the associated helper function for $P(α~|~β)$. Therefore we derive $$P(α~|~β)·P(β) = \lim_{n→∞} δ_n(γ_β,θ) · \lim_{n→∞} δ_n(β,θ) = \lim_{n→∞} δ_n(γ_β,θ) · δ_n(β,θ) = $$$$\lim_{n→∞} \dfrac{(n·δ_n(γ_β,θ)) · δ_n(β,θ)}{n} = \lim_{n→∞} \dfrac{(n·δ_n(γ_α,θ)) · δ_n(α,θ)}{n} = $$$$\lim_{n→∞} δ_n(γ_α,θ) · \lim_{n→∞} δ_n(α,θ) = P(β~|~α)·P(α)~~\square$$

Equivalence of Differentiability of Real Functions of Several Variables with Lame MTH254 Definition

(Necessary exercise) Let $f : ℝ^2→ℝ$, fix $α∈ℝ^2$, and define $Δf=f(α+(Δx,Δy))-f(α)$ given $Δx,Δy∈ℝ$. Show that the condition (1) The partial derivatives $f_x=\dfrac{\partial f}{\partial x},f_y=\dfrac{\partial f}{\partial y}$ exist at $α$ and there exists $ε_1,ε_2 : ℝ^2→ℝ$ such that $$Δf=f_x(α)Δx+f_y(α)Δy+ε_1Δx+ε_2Δy$$ $$ε_1,ε_2→0~~~~~~~~~\text{as}~~Δx,Δy→0$$ (implicitly $ε_i=ε_i(Δx,Δy)$) is equivalent to the condition (2) There exists a linear transformation $A : ℝ^2→ℝ$ such that when $h=(Δx,Δy)$, we see $$\lim_{h→0} \dfrac{|Δf-Ah|}{|h|} = 0$$ Proof: We shall use the condition—equivalent to (2)—of there existing a linear transformation $A: ℝ^2→ℝ$ and an error term $r : ℝ^2→ℝ$ such that $$Δf=Ah+r(h)$$ $$\lim_{h→0} \dfrac{|r(h)|}{|h|}→0$$ in the proof that follows. (1)$⇒$(2) Define $A(Δx,Δy)=f_x(α)Δx+f_y(α)Δy$, and $r(Δx,Δy)=ε_1Δx+ε_2Δy$. Then clearly $Δf=Ah+r(h)$, and also $$\dfrac{|r(h)|}{|h|}=|ε_1\dfrac{Δx}{|h|}+ε_2\dfrac{Δy}{|h|}|≤|ε_1|+|ε_2|→0$$ (2)$⇒$(1) Let $α=(x_0,y_0)$. Observing the real functions $x↦(x,y_0)$ and $y↦(x_0,y)$, we see by application of (2) that the appropriate partial derivatives exist, and that such a linear transformation must in fact be $A(Δx,Δy)=f_x(α)Δx+f_y(α)Δy$. Therefore define $$ε_1 = \left\{ \begin{array} \{ r(h)/Δx & Δx≠0 \\ 0 & Δx=0,Δy≠0 \\ 0 & Δx,Δy=0 \end{array} \right.~~~~~ε_2 = \left\{ \begin{array} \{ 0 & Δx≠0 \\ r(h)/Δy & Δx=0,Δy≠0 \\ 0 & Δx,Δy=0 \end{array} \right.$$ then it is clear that $Δf=f_x(α)Δx+f_y(α)Δy+ε_1Δx+ε_2Δy$, and observing $$|\dfrac{r(h)}{Δx}|≤|\dfrac{r(h)}{Δx}·\dfrac{Δx}{|h|}|=\dfrac{|r(h)|}{|h|}→0$$ and similarly $\dfrac{r(h)}{Δy}→0$ we see $ε_1,ε_2→0$ as $Δx,Δy→0$.$~\square$

Degree of Continuous Maps on S^n (9.58.9-10)

James Munkres Topology, chapter 9.58, exercise 9-10:

9. Let $h : S^1→S^1$ be a continuous map. Let $b_0=(1,0)$, and let $γ$ generate $π_1(S^1,b_0)$. For any given point $x∈S^1$, define $γ(x)=\hat{α}(γ)$ where $α$ is a path from $b_0$ to $x$; note that the choice of $α$ is immaterial since $π_1(S^1,b_0)$ is abelian. Since $\hat{α}$ is an isomorphism, $γ(x)$ will generate $π_1(S^1,x)$. As well, we see $h_*$ is a homomorphism between $π_1(S^1,x)$ and $π_1(S^1,h(x))$, so $$h_*(γ(x))=d_x·γ(h(x))$$ for some integer $d_x$, if the fundamental groups are considered additively. This $d_x$ is called the degree of $h$ (relative to $x$), and is independent of choice of $γ$ since choosing the other generator of $π_1(S^1,b_0)$ will change signs accordingly to result in the same $d_x$.

(a) Show that $d_x$ is independent of the choice of $x∈S^1$, so we may denote it more generally by $d$.
(b) Show that if $h, k : S^1→S^1$ are homotopic, then their degrees are the same.
(c) Show that $\text{deg}(h∘k)=(\text{deg }h)·(\text{deg }k)$.
(d) Compute the degrees of the constant map, the identity map, the reflection map $(x,y)↦(x,-y)$, and the map $z↦z^n$ when $S^1$ is considered as a subgroup of $ℂ$.
(e) Show that if $h,k : S^1→S^1$ have the same degree, they are homotopic.

10. Suppose that to every map $h : S^n→S^n$ we have assigned an integer, denoted by $\text{deg }h$ and called the degree of $h$, such that:

1. Homotopic maps have the same degree
2. $\text{deg }(h∘k) = (\text{deg }h)·(\text{deg }k)$
3. The identity map has degree $1$, any constant map degree $0$, and the reflection maps $(x_1,...,x_i,...,x_{n+1})↦(x_1,...,-x_i,...,x_{n+1})$ degree $-1$.

Prove the following:
(a) There is no retraction $r : B^{n+1}→S^n$
(b) If $h : S^n→S^n$ has degree different than $(-1)^{n+1}$, then $h$ has a fixed point.
(c) If $h : S^n→S^n$ has degree different than $(-1)^n$, then $h(x)=-x$ for some $x$.
(d) If $S^n$ has a nonvanishing tangent vector field $v$, then $n$ is odd.

Proof: Notation shall be mildly abused in the explanations that follow, in that $γ$ will refer to an element of $π_1(S^1,b_0)$ when outside brackets, and a loop about $b_0$ whose homotopy class is such $γ$ when inside brackets.

9. (a) We shall show $d_x=d_{b_0}$ for all $x∈S^1$. We have $$h_*(γ)=d_{b_0}·\hat{α}(γ)$$ where $α$ is a path from $b_0$ to $h(b_0)$. Let $β$ be a path from $b_0$ to $x$, and let $δ$ be a path from $b_0$ to $h(x)$, and observe $$h_*(γ(x))=h_*(\hat{β}(γ))=[h∘\overline{β}]*[h∘γ]*[h∘β]=\widehat{h∘β}(h_*(γ))=$$$$\widehat{h∘β}(d_{b_0}·\hat{α}(γ))=d_{b_0}·\widehat{h∘β}∘\hat{α}(γ)=d_{b_0}·\widehat{α*(h∘β)}(γ)=$$$$d_{b_0}·\hat{δ}(γ)=d_{b_0}·γ(h(x))$$ (b) Choose $x∈S^1$. Since $h$ and $k$ are homotopic, let $α$ be a path from $h(x)$ to $k(x)$ such that $k_*=\hat{α}∘h_*$. Then if $d$ is the degree of $h$ and $β$ is a path between $b_0$ and $h(x)$, we have $$k_*(γ(x))=\hat{α}∘h_*(γ(x))=d·\hat{α}(γ(h(x))=$$$$d·\hat{α}∘\hat{β}(γ)=d·\widehat{β*α}(γ)=d·γ(k(x))$$ (c) We simply observe $$(h∘k)_*(γ(x))=h_*∘k_*(γ(x))=(\text{deg }k)·h_*(γ(k(x))=$$$$[(\text{deg }k)·(\text{deg }h)]·γ((h∘k)(x))$$ (d) The constant map induces trivial homomorphisms, so $d=0$ in this case. The identity map induces identity homomorphisms, so $d=1$ in this case. Let $f$ be the reflection map; when $p : ℝ→S^1$ is the standard covering map $x↦(\text{cos }2πx,\text{sin }2πx)$ and $\tilde{γ} : I→ℝ$ is given by $x↦x$, we see $γ=p∘\tilde{γ}$ generates $π_1(S^1,b_0)$. As well, $p(-\tilde{γ}(x))=(\text{cos }(-2πx),\text{sin}(-2πx))=(\text{cos }2πx,-\text{sin}(2πx))=f∘γ(x)$ so $\widetilde{f∘y}=-\tilde{γ}$. Since $-\tilde{γ}$ is a path from $0$ to $-1$ in $ℝ$ we may observe $f_*(γ)=[f∘γ]=-γ$ so that $d=-1$. A similar appeal to covering maps beyond when $n=-1$ shows that generally $z↦z^n$ is degree $n$.

(e) Lemma: If $G : I×I→S^1$ is a homotopy between $h∘γ$ and $k∘γ$, then $h, k$ are homotopic. Proof: Consider $S^1$ as the circle group in $ℂ$. We see $p_1(t)=G(0,t)$ and $p_2(t)=G(1,t)$ are paths from $h(b_0)$ to $k(b_0)$, and let $q(x,t)=(\dfrac{p_1(t)}{p_2(t)})^x$. First we show $J: I×I→S^1$ defined by $J = G·q$ is another homotopy, but such that $J(0,t)=J(1,t)$ for all $t∈I$. As such, it is clear $$J(x,0)=G(x,0)·1^x=h∘γ(x)$$ and $$J(x,1)=G(x,1)·1^x=k∘γ(x)$$ and also $J(0,t)=G(0,t)·1=p_1(t)=p_2(t)·\dfrac{p_1(t)}{p_2(t)}=J(1,t)$.

Thus, since $γ$ is also a quotient map (if $γ$ weren't surjective, then $γ$ would map into $S^1-p≅ℝ$ for some $p∈S^1$ and thus be nulhomotopic), we may factor $J$ through $S^1×I$ via the quotient map $γ×i$ to obtain $K$. For $x∈S^1$, let $γ(v)=x$, and we see $$K(x,0)=K∘(γ×i)(v,0)=J(v,0)=h∘γ(v)=h(x)$$ $$K(x,1)=K∘(γ×i)(v,1)=J(v,1)=k∘γ(v)=k(x)$$ so that $K$ is a homotopy between $h$ and $k$.$~\square$

Let $α$ be a path from $b_0$ to $h(b_0)$, and let $β$ be a path from $h(b_0)$ to $k(b_0)$. Then $$\hat{β}∘h_*(γ)=\hat{β}(d·\hat{α}(γ))=d·\widehat{α*β}(γ)=k_*(γ)$$ so that $\hat{β}∘h_*=k_*$. As such, let $F : I×I→S^1$ be a path homotopy between $\overline{β}*(h∘γ)*β$ and $k∘γ$ (however, by path homotopy equivalence, let this former piecewise function be split such that $(\overline{β}*(h∘γ)*β)(1/3+t/3)=h∘γ(t)$). Also, let $H : I×I→I$ be a homotopy between the functions $f,g : I→I$ given by $f(t)=t$ and $g(t)=1/3+t/3$, specifically a homotopy from $g$ to $f$. Define $K : I×I→S^1$ by $K(x,y)=F(H(x,y),y)$. We claim $K$ is a homotopy between $h∘γ$ and $k∘γ$, so that the statement follows by the proceeding lemma. To wit, observe $$K(x,0)=F(H(x,0),0)=(\overline{β}*(h∘γ)*β)(1/3+x/3)=h∘γ(x)$$ $$K(x,1)=F(H(x,1),1)=k∘γ(x)$$ 10. (a) If $j : S^n→B^{n+1}$ is the inclusion map, then we see if $r$ were a retraction, then since $B^{n+1}$ is convex that $i_{S^n} \simeq r∘j \simeq 0∘j$, and so the identity map is homotopic to the constant map on $S^n$, contradicting (1) and (3).

(b) Suppose $h$ does not have a fixed point; then extend $h$ to $ℝ^{n+1}-0$ via $H(x)=h(\dfrac{x}{||x||})$. Now define a homotopy $G$ from $H$ to the circular antipodal map $λ(x)=-\dfrac{x}{||x||}$ on $ℝ^{n+1}-0$ by $G(x,t)=(1-t)·H(x)+t·λ(x)$. Note that by construction $G(x,t) \not = 0$ for any $x,t$ so the range is indeed within $ℝ^{n+1}-0$. Now when $j : S^n→ℝ^{n+1}-0$ is inclusion and $r : ℝ^{n+1}-0→S^n$ the standard retraction, we see $F : S^n×I→S^n$ given by $F(x,t)=r(G(j(x),t))$ is a homotopy between $H_{|S^n}=h$ and the antipodal map $x↦-x$ on $S^n$, and since this latter is seen to have degree $(-1)^{n+1}$ by (2) and (3), it follows by (1) that $h$ has the same degree.

(c) This is merely part (b) applied to the composite of the antipodal map with $h$.

(d) If a nonvanishing vector $v(x)$ is tangent to a point $x$ of $S^n$, then particularly $t·v(x) ≠ x$ for $t∈ℝ$. Now, when $j : S^n→ℝ^{n+1}-0$ is the inclusion map, consider the straight-line homotopy between $j$ and $v$ on $ℝ^{n+1}-0$. This homotopy is well defined by the nonvanishing and non-orthogonality of the vector field. As well, the straight-line homotopy between $v$ and $-j$ is also defined. Therefore $j$ is homotopic to $-j$ in $ℝ^{n+1}-0$, and since $S^n$ is a retract of this latter, we find the identity map is homotopic to the antipodal map in $S^n$. Since the antipodal map has degree $-1$ when $n$ is even, it follows $n$ must be odd.$~\square$

Contractibility is Not Equivalent to One-Point Homotopy Type (9.58.8)

James Munkres Topology, chapter 9.58, exercise 8:

Find a space $X$ and a point $x_0∈X$ such that the inclusion $\{x_0\}→X$ is a homotopy equivalence, but $\{x_0\}$ is not a deformation retract of $X$.

Proof: Let $X$ be the subset of $ℝ^2$ consisting of those lines $(1/n)×I$ for $n∈ℕ$, as well as $0×I$ and $I×0$, and let $x_0=(0,1)$. Then the map $$F : X×I→X$$ $$F((x,y),t)=\left\{ \begin{array} \{ (x,(1-3)y) & t∈[0,1/3] \\ ((2-3t)x,0) & t∈[1/3,2/3] \\ (0,3t-2) & t∈[2/3,1] \end{array} \right.$$ is a homotopy between the identity on $X$ and the constant map onto $x_0$, so that $X$ is contractible. But suppose $\{x_0\}$ is a deformation retract of $X$ via the map $F : X×I→X$, i.e. a homotopy between the two mentioned above such that $F(x_0×I)=\{x_0\}$. For each $n$ let $x_n=(1/n)×1$; then since each $ρ_n : I→X$ given by $ρ_n(t)=F(x_n,t)$ is a path from $x_n$ to $x_0$, let $t_n∈I$ be such that $π_2(F(x_n,t_n))=0$. Since $I$ is compact, let $t_{n_i}→α$ be a convergent subsequence. Then $(x_{n_i},t_{n_i})→(x_0,α)$ yet $F(x_{n_i},t_{n_i}) \not → x_0$ since every term of this sequence has second coordinate $0$.$~\square$

Contractible Spaces and Homotopy Classes (9.51.3)

James Munkres Topology, chapter 9.51, exercise 3:

A space $X$ is said to be contractible if the identity map $i : X→X$ is nulhomotopic.
(a) Show that $I$ and $ℝ$ are contractible.
(b) Show that contractible spaces are path connected.
(c) Show that if $Y$ is contractible, then for any $X$, the set $[X,Y]$ has a single element.
(d) Show that if $X$ is contractible and $Y$ is path connected, then $[X,Y]$ has a single element.

Proof: (a) Since $I$ and $ℝ$ are both convex, the linear homotopies suffice, for $z : I→\mathcal{C}(ℝ,ℝ)$ (say) given by $(1-t)·f(x)+t·g(x)$ is a path in $\mathcal{C}(ℝ,ℝ)$ in the compact-open topology between arbitrary $f,g∈\mathcal{C}(ℝ,ℝ)$.

(b) Let $X$ be path connected, and let $x,y∈X$. If $G : X×I→X$ is a nulhomotopy to the constant map onto $e$, then $p_1 : I→X$ given by $p_1(t)=G(x,t)$ is a path from $p_1(0)=x$ to $p_1(1)=e$. Similarly there is a path from $y$ to $e$, so that $x$ and $y$ are connected by a path.

(c) First, let $Y$ simply be path connected, let $y,e∈Y$ be arbitrary, and let $p$ be a path from $y$ to $e$. Then $P : Y×I→Y$ given by $P(x,t)=p(t)$ is a homotopy from the constant map onto $y$ to the constant map onto $e$, so that all constant maps into a path connected space are homotopic. Hence, when $Y$ is contractible, it suffices to show that an arbitrary map $f : X→Y$ is homotopic to a constant map; and indeed, if $G$ is a nulhomotopy in $Y$ onto a constant map $x↦e$, then $F : X×I→Y$ given by $F(x,t)=G(f(x),t)$ is continuous such that $F(x,0)=G(f(x),0)=f(x)$ and $F(x,1)=G(f(x),1)=e$.

(d) As we saw, all constant maps $X→Y$ are homotopic, so it suffices to show an arbitrary map $f : X→Y$ is homotopic to a constant map. Let $G$ be a nulhomotopy in $X$ onto a constant map $x↦e$; then $F : X×I→Y$ given by $F(x,t)=f(G(x,t))$ is continuous such that $F(x,0)=f(G(x,0))=f(x)$ and $F(x,1)=f(G(x,1))=f(e)$ is constant.$~\square$

Hierarchy of Conditions on Locally Euclidean Spaces (8.50.Supp 2-6)

James Munkres Topology, chapter 8.50, supplementary exercises 2-6:

Let $X$ be locally $m$-euclidean.

2. Consider the following conditions on $X$:
(i) $X$ is compact Hausdorff (ii) $X$ is an $m$-manifold (iii) $X$ is metrizable (iv) $X$ is normal (v) $X$ is Hausdorff

Show (i) $⇒$ (ii) $⇒$ (iii) $⇒$ (iv) $⇒$ (v).

3. Show $ℝ$ is locally $1$-euclidean and satisfies (ii) but not (i).

4. Show that $ℝ×ℝ$ in the dictionary order topology is locally $1$-euclidean and satisfies (iii) but not (ii).

5. Show that the long line is locally $1$-euclidean and satisfies (iv) but not (iii).

Proof: 2. [(i) $⇒$ (ii)] Since $X$ is locally metrizable, Hausdorff compactness of $X$ implies by the Smirnov metrization theorem that $X$ is metrizable. Since compact metric spaces are second countable, it follows $X$ is an $m$-manifold. [(ii) $⇒$ (iii)] This follows by the Urysohn metrization theorem. [(iii) $⇒$ (iv)] Metric spaces are necessarily normal. [(iv) $⇒$ (v)] Normal spaces are necessarily Hausdorff.

3. $ℝ$ is clearly Hausdorff locally $1$-euclidean with a countable basis, but is not compact.

4. It is clear $ℝ×ℝ$ in the dictionary order topology is locally $1$-euclidean and does not have a countable basis, seeing as $r×(0,1)$ for $r∈ℝ$ is an uncountable collection of disjoint nonempty open sets in $ℝ×ℝ$. However, by paracompactness of $ℝ$, it is seen that $ℝ×ℝ$ is paracompact, so that by the Smirnov metrization theorem the space is metrizable.

5. Every order topology is normal, and by the results of the exercises of chapter 26 we know that the long line is locally $1$-euclidean. However, the long line is limit point compact but not compact, so that it cannot be metrizable.$~\square$

Imbedding Theorem on m-Manifolds (8.50.6-7)

James Munkres Topology, chapter 8.50, exercises 6-7:

6. Prove the following theorem: Let $X$ be a locally compact, second-countable Hausdorff space such that every compact subspace of $X$ has topological dimension at most $m$. Then $X$ can be imbedded as a closed subspace into $ℝ^{2m+1}$.
(a) Given $f : X→ℝ^N$, we say $f(x)→∞$ (as $x→∞$) if for all $n∈ℕ$ there exists a compact subspace $C⊆X$ such that $|f(x)| > n$ whenever $x∈X \setminus C$. When $ρ$ is the bounded metric on $\mathcal{C}(X,ℝ^N)$, show that if $ρ(f,g) < 1$ and $f(x)→∞$, then $g(x)→∞$.
(b) Show that if $f(x)→∞$, then $f$ extends to a continuous mapping of one-point compactifications. Conclude that if $f$ is injective, then $X$ can be imbedded as a closed subspace into $ℝ^N$.
(c) When $C⊆X$ is compact and given $ε > 0$, define $$U_ε(C)=\{f~|~Δ(f|_C) < ε\}$$ Show $U_ε(C)$ is compact.
(d) Show that if $N=2m+1$, then $U_ε(C)$ is dense in $\mathcal{C}(X,ℝ^N)$.
(e) Show there exists a continuous map $F:X→ℝ^N$ such that $F(x)→∞$.
(f) Complete the proof.

7. Show that every $m$-manifold can be imbedded as a closed subspace into $ℝ^{2m+1}$.

Proof: (a) Given $n$, let $C⊆X$ be compact such that $|f(x)| > n+1$ for all $x∈X \setminus C$. Then $|g(x)| > n$ for all $x∈X \setminus C$.

(b) If $f(x)→∞$, then define $F: X^*→(ℝ^N)^*$ by $F(Ω_X)=Ω_{ℝ^N}$ and $F(x)=f(x)$ otherwise. Since $X$ is first-countable, it suffices to show $f(x_n)→f(x)$ whenever $x_n→x$. This is evident by continuity of $f$ when $x≠Ω_X$, and it follows from the definition of $f(x)→∞$ and of one-point compactifications when $x=Ω_X$. And when $f$ is injective, we see $F$ is a homeomorphism whose image is closed in $(ℝ^N)^*$, so that $f$ is a homeomorphism onto a closed subspace of $ℝ^N$.

(c) Note that $X$ is metrizable by the Urysohn metrization theorem, so that for each compact $C⊆X$ we see the image of the restriction of $U_ε(C)$ (technically, it requires specifying it is relative to $C$ rather than $X$, though by the Tietze extension theorem the point is moot) is open in $\mathcal{C}(C,ℝ^N)$ by the result proved in Theorem 50.5, which by nature of the bounded metric $ρ$ implies $U_ε(C)$ is open in $\mathcal{C}(X,ℝ^N)$.

(d) Let $f : X→ℝ^N$ and $δ > 0$ be given. By the result in Theorem 50.5, let $g : C→ℝ^N$ be such that $|f(x)-g(x)| < δ$ for all $x∈C$ and $Δ(g) < ε$. Extend $g-f|_C$ to a continuous map $h : X→[-δ,δ]^N$ by the Tietze extension theorem; then $k = h+f$ is such that $ρ(f,k) < δ$, and since $k|_C=g-f|_C+f|_C=g$, we have $Δ(k) < ε$.

(e) Let $\{U_i\}$ be a countable basis for $X$. First, define a sequence $D_n$ of compact subsets of $X$ such that $∪D_n=X$, such as by letting $D_n$ be the union of those basis elements $U_i$ for $i < n$ with compact closure. Let $C_0=ø$. Given compact $C_n$, by local compactness of $X$ cover $C_n$ by finitely many sets open in $X$ of compact closure, and let $C_{n+1}$ be the union of these closures together with $D_n$; then $C_n ⊆ \text{Int }C_{n+1}$ for each $n$, and $∪C_n=X$.

For all $n$, let $S_n=C_n-\text{Int }C_n$. Let $f_0 : C_n→ℝ$ be void. Given a function $$f_n : C_n→ℝ$$ such that $f_n(x)=n$ for all $x∈S_n$, let $$g_{n+1} : C_{n+1} \setminus \text{Int }C_n → [n,n+1]$$ be such that $g_{n+1}(S_n)=\{n\}$ and $g_{n+1}(S_{n+1})=\{n+1\}$, and define $$f_{n+1} : C_{n+1}→ℝ$$ by $f_{n+1}(x)=f_n(x)$ if $x∈C_n$ and $f_{n+1}(x)=g_{n+1}(x)$ otherwise. Then $f_{n+1}$ is continuous by the pasting lemma, and is $n+1$ on $S_{n+1}$.

Since we see $f_n(x)=f_m(x)$ for all $x∈C_n$ whenever $n≤m$, define $f : X→ℝ$ by $f(x)=f_n(x)$ when $x∈C_n$. Since every compact subset of $X$ must be contained in $C_n$ for some $n$ (lest $\{\text{Int }C_n\}$ be a cover with no finite subcover), and since $X$ is compactly generated, we see $f$ is continuous. Further, $f(x)→∞$ because $f(x) ≥ n$ whenever $x∈X \setminus C_n$. Finally, define $F : X→ℝ^N$ by $π_i(F(x))=f(x)$ for all $i$. It follows that $F$ is continuous and $F(x)→∞$.

(f) By the Baire property and previous arguments, $∩U_{1/n}(C_n)$ is dense in $\mathcal{C}(X,ℝ^N)$. Hence, let $λ : X→ℝ^N$ be such that $λ∈∩U_{1/n}(C_n)$ and $ρ(λ,f) < 1$. It follows that $Δ(λ)=0$ so that $λ$ is injective, hence by (b) $λ$ is an imbedding of $X$ onto a closed subspace of $ℝ^N$.

7. Being regular and locally Euclidean, $m$-manifolds are locally compact, and being Hausdorff and second countable the other qualities necessary to apply the previous theorem follow together with an application of Theorem 50.1.$~\square$

Hausdorffness and Regularity of Compact-Open C(X,Y) (7.46.6)

James Munkres Topology, chapter 7.46, exercise 6:

Let $\mathcal{C}(X,Y)$ be under the compact-open topology. Show $\mathcal{C}(X,Y)$ is Hausdorff if $Y$ is Hausdorff, and regular if $Y$ is regular.

Proof: Hausdorffness is simple, as $\mathcal{C}(X,Y)$ inherits a topology at least as fine as that of a subspace under the product topology of $Y^X$, which is Hausdorff when $Y$ is. So suppose $Y$ is regular, let $f∈\mathcal{C}(X,Y)$, and let $K⊆\mathcal{C}(X,Y)$ be a closed subset not containing $f$. Then there exists compact $C_1,...,C_n⊆X$ and open $U_1,...,U_n⊆Y$ such that $f(C_i)⊆U_i$ and for all $g∈K$ there exists $i_g$ such that $g(C_{i_g})⊈U_{i_g}$. Since $f(C_i)$ is compact for each $i$, by regularity of $Y$ choose neighborhoods $V_i$ of these sets such that $\overline{V_i}⊆U_i$. Then $∩B(C_i,V_i)$ is a hood of $f$, and since $$\overline{B(C_i,V_i)}⊆B(C_i,\overline{V_i})$$ we observe $$\overline{∩B(C_i,V_i)}⊆∩\overline{B(C_i,V_i)}⊆∩B(C_i,U_i)$$ is disjoint from $K$.$~\square$

Compact Convergence of a Power Series (7.46.5)

James Munkres Topology, chapter 7.46, exercise 5:

Consider the sequence of functions $f_n : (-1,1)→ℝ$ defined by $$f_n(x)=\sum_{k=1}^n kx^k$$ (a) Show $(f_n)$ converges in the topology of compact convergence; conclude that the limit function is continuous.
(b) Show $(f_n)$ does not converge uniformly.

Proof: (a) First, note that $f(x)=\sum kx^k$ converges for all $|x| < 1$ by the ratio test. Since each compact subset of $(-1,1)$ is contained in some interval $[-x,x]⊆(-1,1)$, it will suffice to show $f_n$ converges uniformly on $[-x,x]$ for all $x∈(0,1)$. Therefore let $|y| ≤ |x|$ and observe $$|f(y)-f_n(y)| = |\sum^∞_{k=1}ky^k-\sum^n_{k=1}ky^k| = |\sum^∞_{k=n+1} ky^k| ≤$$$$\sum^∞_{k=n+1} k|x|^k →0$$ as $n→∞$.

(b) Suppose some $n$ such that $|f(x)-f_n(x)| < 1/2$ for all $x∈(-1,1)$. Simply choose $x∈(0,1)$ so that $(n+1)x^{n+1} ≥ 1/2$, and observe $$|f(x)-f_n(x)| = |\sum_{k=n+1}^∞ kx^k| ≥ 1/2~~\square$$

Grayscale Functions

Let $X$ be a topological space. For $A⊆X$, let $ι_A(x)=1$ if $x∈A$, and $ι_A(x)=0$ otherwise. Let $\mathcal{U}(X)=\{U~|~U⊆X \text{ is open}\}$. When $(U_n)$ is a sequence in $\mathcal{U}(X)$, we write $U_n→U$ for $U∈\mathcal{U}(X)$ if $$\overline{U}=\overline{\bigcup_{n∈ℕ}(\bigcap_{N≥n} U_N)}$$ (Convergence need not be unique) If $φ : X→\mathcal{U}(X)$ is such that $x∈φ(x)$ when $φ(x)≠ø$, and $φ(x_n)→φ(x)$ whenever $x_n→x$, we say $φ$ is a gradated open assignment on $X$. Given a sequence $σ=(x_i)$ in $X$ and a subset $A⊆X$, let $$λ_σ(A)=\lim_{N→∞} \sum^N \dfrac{ι_A(x_i)}{N}$$ wherever the convergence exists. If $φ$ is a gradated open assignment such that $f = λ_σ ∘ φ : X→[0,1]$ is a well-defined continuous mapping, then the pair $(φ,σ)$ is called a grayscale pair and $f$ the corresponding grayscale function. If every continuous function $f∈\mathcal{C}(X,[0,1])$ is a grayscale function, then $X$ is said to be a grayscale domain.
~~~~~
Every infinite discrete space is grayscale, and a finite discrete space is never grayscale. In fact, if $X=\{x_1,...,x_n\}$ is a finite discrete space, then the function $f : X→[0,1]$ is grayscale if and only if $f(x_i)=0,1$ for some $i$, or there exists some $n×n$ binary matrix $M$ with $1$s on the main diagonal and a non-negative-valued $n×1$ column vector $A$ whose entries sum to $1$ such that $$MA=\begin{bmatrix} f(x_1) \\ f(x_2) \\ \cdots \\ f(x_n) \end{bmatrix}$$ ~~~~~ We prove $[0,1]$ is itself grayscale. If $f : [0,1]→[0,1]$ is continuous, then let $$φ(x) = \left\{ \begin{array} \{ [0,f(x)) & x=0 \\ (1-f(x),1] & x=1 \\ (x(1-f(x)),~f(x)+x(1-f(x)) & x∈(0,1) \end{array} \right.$$ Note that the length of the interval $φ(x)$ is $f(x)$, and $x∈φ(x)$ if $φ(x)≠ø$. To prove gradation, note that when $x_n→x$, we have $x_n(1-f(x_n))→x(1-f(x))$ and $f(x_n)+x_n(1-f(x_n))→f(x)+x(1-x)$. When $μ(n)→0$ denotes the maximum of the difference between the two pairs of an $n^\text{th}$ term and its limit, we see that if $B(y,ε)⊆φ(x)$ for $x∈(0,1)$, we have $y∈φ(x_n)$ for all $n≥N$ when $N$ is such that $μ(n) < ε$ for all $n≥N$. Exclusion of those elements $y∉\overline{φ(x)}$ from the final intersection is similar. The cases for $x=0,1$ are straightforward edge cases.

Let $σ=(x_n)$ be the sequence of rationals in the order $\dfrac{1}{2},\dfrac{1}{3},\dfrac{2}{3},\dfrac{1}{4},\dfrac{2}{4},\dfrac{3}{4},...$ (we shall refer to the subcollection of those with $n$ in the denominator as the $n$-strip elements).

It now remains to show $λ_σ(x)=f(x)$. To observe this, first fix $x$ and let $α=f(x)$. Note that each $n$-strip collection refers to a subset of $[0,1]$ containing $n-1$ elements spaced $1/n$ apart from each other. Therefore, when $g(n)$ denotes the number of $n$-strip elements contained in $φ(x)$, we see $g(n)∈[α(n-1),~α(n-1)-2]$, and when $$G(n)=\sum^N_{i=1} g(i)$$ we see $G(n)∈[\dfrac{1}{2}αn(n-1)-2n,~\dfrac{1}{2}αn(n-1)]$. Since the number of elements up to and including the $n$-strip elements is $β(n)=\dfrac{1}{2}n(n-1)$, we see $G(n)/\sum β(n)∈[α-\dfrac{4}{n-1},α]$. This shows that a subsequence of the limit involved in $λ_σ(x)$ converges to $α=f(x)$, so it suffices to show that the limit inferior and limit superior are the same. To wit, note that the minimum value between the partial sums $G(n)/\sum β(n)$ and $G(n+1)/\sum β(n+1)$ is bounded below by $$G(n)/\sum β(n+1)∈[α\dfrac{n-5}{n+1},α\dfrac{n-1}{n+1}]$$ The case for limit superior is parallel. Thus $λ_σ(x)$ is well defined and equals $f(x)$.

By a similar argument, $(0,1)≅ℝ$ is also grayscale.

Completeness, Total Boundedness, and Compactness of the Hausdorff Metric (7.45.7b-d)

James Munkres Topology, chapter 7.45, exercise 7:

Let $(X,d)$ be a metric space, and let $(\mathcal{H},D)$ be its associated Hausdorff metric. Show completeness, total boundedness, and compactness are equivalent conditions in both spaces.

Proof: Note that there is a natural isometry of $(X,d)$ with a closed subspace of $(\mathcal{H},D)$, so that completeness, total boundedness, and compactness of $\mathcal{H}$ implies the corresponding quality in $X$ (to cover a subset $A$ of a totally bounded space $B$ with finitely many $ε$ balls, cover $B$ with $ε/2$ balls, remove those disjoint from $A$, and place one $ε$ ball centered in $A$ per $ε/2$ ball from $B$). Since completeness and total boundedness imply compactness, it will suffice to prove (a) completeness of $(X,d)$ implies completeness of $(\mathcal{H},D)$, and (b) total boundedness of $(X,d)$ implies total boundedness of $(\mathcal{H},D)$.

(a) Let $(A_n)$ be a Cauchy sequence in $\mathcal{H}$. If necessary, take a subsequence so that $D(A_n,A_{n+1}) < 1/2^n$ for all $n$. Now, let $A$ be the set of all limit points of subsequences of $(a_n)$ of $X$ such that $a_n∈A_n$ for each $n$. Since $D(A_1,A_n) < 1$ for each $n$, it is clear $A$ is bounded, nonempty, and (by diagonalization of limits) closed. We show $A_n → A$. Let $ε > 0$. Since the size of the neighborhood of $A_n$ required to contain $A$ approaches $0$, it suffices to show $A_n ⊈ B_D(A,ε)$ for only finitely many $n$. To wit, let $N$ be such that $\sum_{i=N}^∞ 1/2^i < ε/2$. Then if $a_n∈A_n$ for $n≥N$, set $b_0=a_n$ and given $b_i$, choose $b_{i+1}$ so that $d(b_i,b_{i+1}) < 1/2^n$. Then $(b_i)$ is a Cauchy sequence, and appending cursory points in each of $A_1,...,A_{n-1}$ we can find a point of $A$—namely, $b$ when $b_i→b$—such that $d(a_n,b) < ε$ and now $a_n∈B_D(A,ε)$.

(b) Let $ε > 0$. Cover $X$ by finitely many $ε$ balls centered about the points $a_1,...,a_n$. Let $J=\mathcal{P}(\{a_1,...,a_n\}) \setminus \{ø\}$, and center around each point $j∈J⊆\mathcal{H}$ an $ε$ ball. This is seen to be a finite covering of $\mathcal{H}$ by $ε$ balls, with an arbitrary element $A∈\mathcal{H}$ being within distance $ε$ of the element of $J$ which minimally (with regard to set containment) covers $A$ considered as a subset of $X$.$~\square$

R^ω Under the l^2 Metric is Complete (7.43.7)

James Munkres Topology, chapter 7.43, exercise 7:

Show that the subspace of $ℝ^ω$ of those sequences $(x_n)$ such that $\sum x_n^2$ converges is complete under the $\ell^2$ metric.

Proof: Let $(f_n)$ be a Cauchy sequence under this metric. Since the $\ell^2$ distance between any two points is at least as large as the uniform distance in $ℝ^ω$, and since the metric under the latter is complete is complete, let $f_n→f$ in the uniform topology. It suffices to show $f_n→f$ in the $\ell^2$ metric. Let $ε > 0$; let $N$ be such that $d_{\ell^2}(f_n,f_m) < ε/2$ for $n,m≥N$. We shall proceed by showing $d_{\ell^2}(f,f_N) ≤ ε/2$ so that $d_{\ell^2}(f,f_n) < ε$ for all $n≥N$, and this former will be demonstrated by showing $d_{\ell^2}(f,f_N) > ε/2$ implies a neighborhood about $f$ in the uniform topology that does not intersect any $f_n$ for $n≥N$, a contradiction.

Therefore, assume $d_{\ell^2}(f,f_N) > ε/2$, and let $$\sqrt{(f(1)-f_N(1))^2+...+(f(n)-f_N(n))^2} = ε/2+δ$$ for some $n$ and $δ > 0$. Consider the uniform $δ/\sqrt{n}$ neighborhood $U$ about $f$; for any $g∈U$, it is evident that $d_{\ell^2}(f_N,g) ≥ ε/2$ (otherwise, consider the first $n$ coordinates of $f$, $f_N$, and $g$ in $ℝ^n$ and apply the triangle inequality), so that $g≠f_m$ for any $m≥N$.$~\square$

Uniform Extensions into Complete Metric Spaces (7.43.2)

James Munkres Topology, chapter 7.43, exercise 2:

Let $(X,d_X)$ and $(Y,d_Y)$ be metric spaces, with $Y$ complete. Show that if $A⊆X$ and $f : A→Y$ is uniformly continuous, there exists a uniformly continuous extension of $f$ to $\overline{A}$.

Proof: Let $(x_n)$ be a Cauchy sequence in $X$; we show $(f(x_n))$ is a Cauchy sequence in $Y$. Let $ε > 0$. Then if $δ > 0$ is such that $d_Y(f(a),f(b)) < ε$ for all $a,b∈A$ such that $d_X(a,b) < δ$, and $N$ is such that $d_X(x_n,x_m) < δ$ for all $n,m≥N$, we see $d_Y(f(x_n),f(x_m)) < ε$ for all $n,m≥N$, so that $f(x_n)$ is Cauchy.

For all $x∈\overline{A}$, choose some Cauchy sequence $(x_n)$ in $A$ converging to $x$. Then $f(x_n)→y_x$ since $Y$ is complete. Define $g: \overline{A}→Y$ by $g(x)=y_x$. Since $f$ is continuous, $y_x=f(x)$ for all $x∈A$. Now it suffices to show $g$ is uniformly continuous. Let $ε > 0$; let $δ > 0$ be such that $d_Y(f(a),f(b)) < ε/3$ whenever $a,b∈A$ are such that $d_X(a,b) < δ$. Let $x,y∈\overline{A}$ be such that $d_X(x,y) < δ/3$; let $(x_n)→x$ and $(y_n)→y$ be the chosen sequences as before. Choose $n$ such that $$d_Y(g(x),g(x_n)),d_Y(g(y),g(y_n)) < \text{min }\{ε/3,δ/3\}$$ We see $d_X(g(x_n),g(y_n)) = d_X(f(x_n),f(y_n)) < ε/3$ since $d_X(x_n,y_n) ≤ d_X(x_n,x)+d_X(x,y)+d_X(y,y_n)$. Finally, we observe $$d_Y(g(x),g(y)) ≤ d_Y(g(x),g(x_n)) + d_Y(g(x_n),g(y_n)) + d_Y(g(y_n),g(y)) < ε$$