Shawn Zhong

Shawn Zhong

钟万祥
  • Tutorials
  • Mathematics
    • Math 240
    • Math 375
    • Math 431
    • Math 514
    • Math 521
    • Math 541
    • Math 632
    • Abstract Algebra
    • Linear Algebra
    • Category Theory
  • Computer Sciences
    • CS/ECE 252
    • CS/ECE 352
    • Learn Haskell
  • AP Notes
    • AP Microecon
    • AP Macroecon
    • AP Statistics
    • AP Chemistry
    • AP Physics E&M
    • AP Physics Mech
    • CLEP Psycho

Shawn Zhong

钟万祥
  • Tutorials
  • Mathematics
    • Math 240
    • Math 375
    • Math 431
    • Math 514
    • Math 521
    • Math 541
    • Math 632
    • Abstract Algebra
    • Linear Algebra
    • Category Theory
  • Computer Sciences
    • CS/ECE 252
    • CS/ECE 352
    • Learn Haskell
  • AP Notes
    • AP Microecon
    • AP Macroecon
    • AP Statistics
    • AP Chemistry
    • AP Physics E&M
    • AP Physics Mech
    • CLEP Psycho

Home / 2018 / April / 7

Math 541 – 4/6

  • Apr 07, 2018
  • Shawn
  • Math 541
  • No comments yet
Homework 8 Question 3 • Statement ○ If G is a group with |G|≤11, and ├ d┤ ||G|┤, then G has a subgroup of order d • Proof ○ For |G|=2,3,5,7,11 § |G| is prime, thus cyclic ○ For |G|=4,6,9,10 § |G| is product of two primes, so use the Cauchy s Theorem ○ For |G|=8 § d∈{1,2,4,8} § When d=1,2,8, this is obvious § So assume d=4 § If G contains an element of order 4, then we are done § So, we may assume |g|=2,∀g∈G∖{1}, then G is abelian § Let a,b∈G∖{1}. Let H≔{1,a,b,ab} § H is closed under inverse □ The inverse of every element of G is itself § H is closed under multiplication □ ■8(⋅&1&a&b&ab@1&1&a&b&ab@a&a&1&ab&b@b&b&ab&1&a@ab&ab&b&a&1) Lemma 56 • Statement ○ Let G be a finite abelian group of order mn, where (m,n)=1 ○ If M={x∈G│x^m=1}, N={x∈G│x^n=1}, then ○ M,N≤G and the map α:M×N→G given by (g,h=gh is an isomorphism ○ Moreover, if m,n≠1, then M and N are nontrivial • Proof ○ M,N≤G § It suffices to check M≤G § M≠∅, since 1∈M § If x,y∈M, then (xy^(−1) )^m=x^m (y^m )^(−1)=1. Thus xy^(−1)∈M ○ MN=G § Choose r,s∈Z s.t. mr+ns=1 § Let g∈G, then g=g^(mr+ns)=g^mr g^ns § (g^mr )^n=(g^mn )^r=(g^|G| )^r=1 by Lagrange s Theorem § Similarly, (g^ns )^m=1 § So, g^ns∈M, g^mr∈N, so g∈MN § Therefore MN=G ○ M∩N={1} § Let g∈M∩N, then g^m=1=g^n § Then ├ |g|┤ |m┤ and ├ |g|┤ |n┤ § Since (m,n)=1,|g|=1 § Thus M∩N={1} ○ By Lemma 55, M∩N={1} and MN=G⇒α is an isomorphism ○ M and N are nontrivial § Suppose m≠1 § Let p be a prime divisor of m § Then G contains an element z of order p, by Cauchy s Theorem § z∈M, so M≠{1} § Similarly, if n≠1, N≠{1} Corollary 57 • Statement ○ Let G be a finite abelian group, and p be a prime divisor of |G| ○ Choose m∈Z( 0) s.t. |G|=p^m n and p∤n ○ Then G≅P×T, where P,T≤G, |P|=p^m, and p∤|T| • Intuition ○ If |G|=p_1^(m_1 ) p_2^(m_2 )…p_n^(m_n ) ○ This corollary says G≅P_1×…×P_n, where |P_i |=p_i^(m_i ) ○ This reduces the Fundamental Theorem of Finite Abelian Groups ○ to the case where the group has order given by a prime power • Proof ○ Let P≔{x∈G│x^(p^m )=1}, T≔{x∈G│x^n=1} ○ By Lemma 56, G≅P×T ○ p∤|T| § Suppose, by way of contradiction, that ├ p┤ ||T|┤ § By Cauchy s Theorem, ∃z∈T s.t. |z|=p § Since z∈T, z^n=1, so ├ p┤ |n┤ § This is impossible, thus p∤|T| ○ |P|=p^m § Since |G|=|P|⋅|T|=p^m n, ├ p^m ┤ ||T|┤ § Suppose p^m |P| § Then, ∃ prime q s.t. p≠q and ├ q┤ ||P|┤ § By Cauchy s Theorem, ∃y∈P s.t. |y|=q § This is impossible since y∈P⇒y^(p^m )=1⇒├ q┤ |p^m ┤ § Thus p^m=|P|
Read More >>

Math 521 – 4/6

  • Apr 07, 2018
  • Shawn
  • Math 521
  • No comments yet
Theorem 3.27 (Cauchy Condensation Test) • Statement ○ Suppose a_1≥a_2≥…≥0, then ○ ∑_(n=1)^∞▒a_n converges⟺∑_(k=0)^∞▒〖2^k a_(2^k ) 〗=a_1+2a_2+4a_4+…converges • Proof ○ By Theorem 3.24, we just need to look at boundness of partial sums ○ Let § s_n=a_1+a_2+…+a_n, § t_k=a_1+2a_2+…+2^k a_(2^k ) ○ For n≤2^k § s_n≤a_1+(a_2+a_3 )+…+(a_(2^k )+…+a_(2^(k+1)−1) ) § ≤a_1+2a_2+…+2^k a_(2^k )=t^k ○ For n≥2^k § s_n≥a_1+(a_2+a_3 )+…+(a_(2^(k−1)+1)+…+a_(2^k ) ) § ≥1/2 a_1+a_2+…+2^(k−1) a_(2^k )=1/2 t^k ○ For n=2^k § s_n≤t_k≤2s_n⇒s_(2^k )≤t_k≤2s_(2^k ) § So {s_n } and {t_k } are both bounded or unbounded Theorem 3.28 • Statement ○ ∑_(n=1)^∞▒1/n^p converges if p 1 and diverges if p≤1 • Proof ○ If p≤0 § Theorem 3.23 says if∑_(n=1)^∞▒a_n converges, then lim_(n→∞)⁡〖a_n 〗=0 § In this case lim_(n→∞)⁡〖1/n^p 〗≠0, so series diverges ○ If p 0 § 1/n^p ≥1/(n+1)^p and 1/n^p ≥0 § By Cauchy Condensation Test, § lim_(n→∞)⁡〖1/n^p 〗 converges⟺∑_(n=1)^∞▒〖2^k 1/(2^k )^p 〗 converges § ∑_(n=1)^∞▒〖2^k 1/(2^k )^p 〗=∑_(n=1)^∞▒(2^(1−p) )^k which is a geometric series § By Theorem 3.26, this converges if 2^(1−p) 1⟺p 1 § Otherwise, 2^(1−p) 1, and this diverges Theorem 3.33 (Root Test) • Given ∑_(n=1)^∞▒a_n , put α=(lim⁡sup)_(n→∞)⁡√(n&|a_n | ), then • If α 1, ∑_(n=1)^∞▒a_n converges ○ Theorem 3.17(b) says if x s^∗,then ∃N∈N s.t.s_n x for n≥N ○ So let β∈(α,1) and N∈N s.t. ∀n≥N, √(n&|a_n | ) β i.e. |a_n | β^n ○ 0 β 1, so ∑_(n=1)^∞▒β^n converges ○ Thus, ∑_(n=1)^∞▒a_n converges by comparison test • If α 1, ∑_(n=1)^∞▒a_n diverges ○ By Theorem 3.17, there exists a sequence {n_k } s.t. √(n_k&|a_(n_k ) | )→α ○ So |a_n | 1 for infinitely many n, i.e. a_n↛0 ○ By Theorem 3.23, ∑_(n=1)^∞▒a_n diverges • If α=1, this test gives no information ○ For ∑_(n=1)^∞▒1/n, (lim⁡sup)_(n→∞)⁡√(n&n^(−1) )=lim_(n→∞)⁡√(n&n^(−1) )=1, but the series diverges ○ For ∑_(n=1)^∞▒1/n^2 , (lim⁡sup)_(n→∞)⁡√(n&n^(−2) )=lim_(n→∞)⁡〖1/(√(n&n))^2 〗=1, but the series converges Theorem 3.34 (Ratio Test) • Statement ○ ∑_(n=1)^∞▒a_n converges if (lim⁡sup)_(n→∞)⁡〖|a_(n+1)/a_n | 1〗 ○ ∑_(n=1)^∞▒a_n diverges if |a_(n+1)/a_n |≥1,∀n≥n_0 for some fixed n_0∈N • Proof ○ If (lim⁡sup)_(n→∞)⁡〖|a_(n+1)/a_n | 1〗 ○ We can find β 1, N∈N s.t. |a_(n+1)/a_n | β,∀n≥N ○ In particular § |a_(N+1) | β|a_N | § |a_(N+2) | β|a_(N+1) | β^2 |a_N | § ⋮ § |a_(N+p) | β^p |a_N | ○ So, |a_n | |a_N | β^(−N) β^n, ∀n≥N ○ β 1, so ∑_(n=1)^∞▒β^n converges ○ So ∑_(n=1)^∞▒〖⏟(|a_N | β^(−N) )┬constant β^n 〗 also converges ○ Therefore ∑_(n=1)^∞▒a_n converges by comparison test ○ On the other hand, if |a_(n+1) |≥|a_n |,∀n≥n_0∈N ○ Then a_n↛0, so series divreges by Theorem 3.23 • Note ○ For ∑_(n=1)^∞▒1/n, lim_(n→∞)⁡〖(1/n)/(1/(n+1) )〗=1 ○ For ∑_(n=1)^∞▒1/n^2 , lim_(n→∞)⁡〖(1/n^2)/(1/(n+1)^2 )〗=1 ○ So lim_(n→∞)⁡〖a_n/a_(n+1) 〗=1 is not enough to conclude anything
Read More >>

Search

  • Home Page
  • Tutorials
  • Mathematics
    • Math 240 – Discrete Math
    • Math 375 – Linear Algebra
    • Math 431 – Intro to Probability
    • Math 514 – Numerical Analysis
    • Math 521 – Analysis I
    • Math 541 – Abstract Algebra
    • Math 632 – Stochastic Processes
    • Abstract Algebra @ 万门大学
    • Linear Algebra @ 万门大学
    • Category Theory
  • Computer Sciences
    • CS/ECE 252 – Intro to Computer Engr.
    • CS/ECE 352 – Digital System Fund.
    • Learn Haskell
  • Course Notes
    • AP Macroeconomics
    • AP Microeconomics
    • AP Chemistry
    • AP Statistics
    • AP Physics C: E&M
    • AP Physics C: Mechanics
    • CLEP Psychology
  • 2048 Game
  • HiMCM 2016
  • 登峰杯 MCM

WeChat Account

Categories

  • Notes (418)
    • AP (115)
      • AP Macroeconomics (20)
      • AP Microeconomics (23)
      • AP Physics C E&M (25)
      • AP Physics C Mechanics (28)
      • AP Statistics (19)
    • Computer Sciences (2)
    • Mathematics (300)
      • Abstract Algebra (29)
      • Category Theory (7)
      • Linear Algebra (29)
      • Math 240 (42)
      • Math 375 (71)
      • Math 514 (18)
      • Math 521 (39)
      • Math 541 (39)
      • Math 632 (26)
  • Projects (2)
  • Tutorials (11)

Archives

  • October 2019
  • May 2019
  • April 2019
  • March 2019
  • February 2019
  • December 2018
  • November 2018
  • October 2018
  • September 2018
  • July 2018
  • May 2018
  • April 2018
  • March 2018
  • February 2018
  • January 2018
  • December 2017
  • November 2017
  • October 2017
  • September 2017
  • August 2017
  • July 2017
  • June 2017

WeChat Account

Links

RobeZH's thoughts on Algorithms - Ziyi Zhang
Copyright © 2018.      
TOP