Wedderburn Decomposition of Finite Group Rings Over Algebraically Closed Fields

Dummit and Foote Abstract Algebra, section 18.2:

Let $G$ be a finite group, $F$ a field, and $FG ≅ R = R_1 × ... × R_r$ be the Wedderburn decomposition of the group ring $FG$. Each $R_i$ is a ring of $n_i × n_i$ matrices with entries from a division ring $Δ_i$. We show in this case that in fact $Δ_i ≅ F$.

We have seen already that $Z(R_i)$ is the set of scalar $n_i × n_i$ matrices with entries from $Z(Δ_i)$. Since $F⊆Z(FG)$, this means (after composition with the projection map $π_i : R → R_i$) $F$ embeds into $Z(Δ_i)$ for each $i$. Now, consider the left ideal $I_i$ of $R$ consisting of elements with $0$ in every coordinate but the $i^\text{th}$, where the value may be any $n_i × 1$ column matrix. This left ideal $I_i$ is a left $R$-module, with an action that restricts to turn $I_i$ into a $Δ_i$-module (multiplication with scalar matrices in $R_i$), which in turns restricts to turn $I_i$ into a vector space over $F$. As a left $FG$-module (inherited from isomorphism of $FG$ with $R$), we may decompose $I_i$ into a finite direct sum of cyclic $FG$-modules (of rank $≤n_i$), hence $I_i$ is a finite vector space over $F$ (of dimension $≤n_i|G|$). $I_i$ is also a ring, with a subring $J_i$ (of $1×1$ matrices) isomorphic to $Δ_i$. Since $J_i$ is an $F$-subspace of $I_i$, it too is finite dimensional, with a vector space action agreeing with multiplication from $F⊆J_i$. That is to say, ultimately, that $Δ_i$ is a finite dimensional vector space over $F$ such that $F⊆Z(Δ_i)$.

If $F$ is algebraically closed, then necessarily $F=Δ_i$, since each ring extension $F[α]⊆Δ_i$ of $F$ by an element $α∈Δ_i$ will in fact be a field extension by $F⊆Z(Δ_i)$, hence be of degree one as a vector space over $F$ by algebraic closure, implying $α∈F$.

Basic Group Representations (18.1.4,18-19,21-22,24)

Dummit and Foote Abstract Algebra, section 18.1, exercises 4, 18-19, 22, 24:

In the exercises that follow, $G$ is a finite group, and $F$ a field.

4. Prove that if $G$ is nontrivial, then every irreducible $FG$-module has degree $< |G|$.

18. Prove that if $φ : G → GL_n(ℂ)$ is an irreducible matrix representation and $A$ is an $n×n$ matrix commuting with $φ(g)$ for all $g∈G$, then $A$ is a scalar matrix. Deduce that if $φ$ is a faithful, irreducible, complex representation then the center of $G$ is cyclic and $φ(g)$ is a scalar matrix for all elements $z$ in the center of $G$.

19. Prove that if $G$ is an abelian group then any finite dimensional complex representation of $G$ is equivalent to a representation into diagonal matrices.

21. Let $G$ be a group with noncyclic center acting on a finite-dimensional vector space $V$ over $F$, where $F$ is a field of characteristic $p$ not dividing the order of $G$.
(a) Prove that if $W$ is an irreducible $FG$-submodule of $V$ then there is some nonidentity $g∈G$ such that $W⊆C_V(g)$, where $C_V(g)$ is the set of elements of $V$ fixed by $g$.
(b) Prove that $V$ is generated as an additive group by the sets $C_V(g)$ as $g$ runs over all nonidentity elements of $G$.

22. Let $p$ be a prime, let $P$ be a $p$-group and let $F$ be a field of characteristic $p$. Prove that the only irreducible representation of $P$ over $F$ is the trivial representation.

24. Let $p$ be a prime, let $P$ be a nontrivial $p$-group and let $F$ be a field of characteristic $p$. Prove that the regular representation is indecomposable.

Proof: (4) Let $V$ be an $FG$-module, and let $v∈V$ be nonzero. Then either $\{gv~|~g∈G\}$ are linearly dependent over $F$, in which case they generate a $G$-stable subspace of dimension strictly less than $|G|$, or they are linearly independent, in which case the nonzero element $\sum_{g∈G} gv$ generates a one-dimensional line that is fixed by each $g∈G$. As such, we see that any $FG$-module not containing any proper nonzero $FG$-submodule must be of dimension $< |G|$.

(18) Let $λ$ be an eigenvalue of $A$, i.e. $A-λ$ has nontrivial kernel as a linear transformation $ℂ^n → ℂ^n$. Since $A$ (and $λ$) commute with every element of $φ(G)$, we see the kernel of $A-λ$ is a $G$-submodule. Since the representation is irreducible, this is to say the kernel is all of $ℂ^n$, so that $A-λ = 0$ and $A$ is a scalar matrix. When $φ$ is faithful, this implies the center of $G$ embeds into the group of nonzero scalar matrices, i.e. $ℂ^×$, so that the center of $G$ is cyclic.

(19) By the above exercise, we find that the action of $G$ on any irreducible $G$-stable subspace of $ℂ^n$ is that of scalar multiplication. If we decompose $ℂ^n$ into a direct sum of irreducible $ℂG$-submodules and observe the matrix representation of $G$ with respect to the $ℂ$-basis of this decomposition, we find that they are diagonalized matrices.

(21)(a) This is a consequence fact that for any irreducible representation $φ$ of a group $G$, we find $Z(G/\text{ker }φ)$ is cyclic (cf. exercise 14d). For if $W$ is an irreducible $FG$-submodule, this offers an irreducible representation of $G$ (by the action on $W$). It follows that if $Z(G)$ is not cyclic, then $\text{ker }φ$ is nontrivial, i.e. there exists a nonidentity element of $G$ that fixes all of $W$.

(b) Decompose $V$ into a finite direct sum of irreducible $FG$-submodules by Maschke's theorem. Each of these summands $W_i$ are contained in $C_V(g_i)$ for some nonidentity $g_i∈G$, by part (a). It follows $V$ is generated as an abelian group by the $C_V(g_i)$.

(22) We may assume a representation $φ$ of $P$ over $F$ is faithful by passing to the quotient $P / \text{ker }φ$ if necessary. But if $P$ is a nontrivial $p$-group, it has a nontrivial center, and there is thus an element $x∈P$ of order $p$ commuting with every element in $P$. If $FP$ is acting irreducibly on a vector space $F$ over $V$ via the representation $φ$, then $V$ is finite dimensional, and as finite-dimensional matrices we have $φ(x)^p-1 = (φ(x)-1)^p = 0$, thus $\text{det }φ(x)-1 = 0$. As $x$ commutes with every element of $P$, we have $\text{ker }φ(x)-1$ determines a $P$-stable subspace of $V$, hence is all of $V$, hence $x=1$, a contradiction since $φ$ is faithful.

(24) Lemma: Let $G$ be a group (not necessarily finite), let $F$ be a field, and let $V$ be an $FG$-module. If $N \unlhd G$ is a normal subgroup, then the set of elements $W ⊆ V$ that are fixed by $N$ is an $FG$-submodule, and there is a natural $F(G/N)$-module action on $W$. The $FG$-submodules and $F(G/N)$-submodules of $W$ are the same. Furthermore, if the module $V$ is itself $FG$ affording the regular representation on $G$, then the induced module is isomorphic to the regular representation of $G/N$.

Proof: It is clear $W$ is a subspace, and if $n ∈ N$, $g ∈G$, and $w ∈ W$, then $ng·w = gg^{-1}ng·w = g(g^{-1}ng)·w = g·w$, so that $W$ is $G$-stable. As well, note that the module structure of $FG$ on $V$ is given by the action of $G$ on $V$; since $W$ is an $G$-stable, this restricts to an action of $G$ on $W$; since $N$ fixes each element of $W$, this induces a natural action of $G/N$ on $W$, thereby turning $W$ into a $F(G/N)$-module under this action. We see an $F$-subspace is $G$-stable if and only if it is $G/N$-stable, so the $FG$-submodules and $F(G/N)$-submodules are the same.

Suppose $V$ is the module given by the regular representation, i.e. $V=FG$ and the module action is given by multiplication. For each distinct left coset $xN$ define $α_{xN} = \sum_{g∈xN} g ∈ FG$. It is clear, then, that $α_{xN}∈W$, the $α_{xN}$ are linearly independent over $F$, and that any element of $FG$ fixed by each element of $N$ must retain equivalent coefficients on elements in the same left coset of $N$, hence be an $F$-linear combination of the $α_{xN}$, so the $α_{xN}$ form an $F$-basis for $W$. Define an $F$-linear isomorphism $φ : W→F(G/N)$ given by $φ(α_{xN}) = \overline{x}$. This is in fact an $F(G/N)$-module isomorphism, since $φ(\overline{g}α_{xN}) = φ(α_{gxN}) = \overline{gx} = \overline{g}φ(α_{xN})$.$~\square$

We proceed by induction on the order of $P$. Suppose $FP = V_1 \oplus V_2$ as $FP$-modules. If $P$ is nontrivial, let $x∈Z(P)$ be of order $p$. Then on any $FP$-submodule of $FP$, we have $(x-1)^p = x^p - 1 = 0$ as $FP$-module transformations, hence $x-1$ has nontrivial kernel in each of $V_1, V_2$; this is to say $\langle~x~\rangle$ fixes nontrivial elements in each of $V_1,V_2$, say $W_1,W_2$ respectively. Then if $W$ is the $FP$-submodule of elements of $FP$ fixed by $\langle~x~\rangle$, we in fact have $W = W_1 \oplus W_2$. This nontrivial direct sum expression as $FP$-modules translates to the same as $F(P/\langle~x~\rangle)$-modules. But now $W ≅ F(P/\langle~x~\rangle)$ may be written as a nontrivial direct sum, a contradiction.$~\square$

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$