-
Notifications
You must be signed in to change notification settings - Fork 0
/
napkin_solutions.html
158 lines (157 loc) · 8.9 KB
/
napkin_solutions.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
<html><head><title>niplav</title>
<link href="./favicon.png" rel="shortcut icon" type="image/png"/>
<link href="main.css" rel="stylesheet" type="text/css"/>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type"/>
<!DOCTYPE HTML>
<style type="text/css">
code.has-jax {font: inherit; font-size: 100%; background: inherit; border: inherit;}
</style>
<script async="" src="./mathjax/latest.js?config=TeX-MML-AM_CHTML" type="text/javascript">
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
extensions: ["tex2jax.js"],
jax: ["input/TeX", "output/HTML-CSS"],
tex2jax: {
inlineMath: [ ['$','$'], ["\\(","\\)"] ],
displayMath: [ ['$$','$$'], ["\\[","\\]"] ],
processEscapes: true,
skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
},
"HTML-CSS": { availableFonts: ["TeX"] }
});
</script>
<script>
document.addEventListener('DOMContentLoaded', function () {
// Change the title to the h1 header
var title = document.querySelector('h1')
if(title) {
var title_elem = document.querySelector('title')
title_elem.textContent=title.textContent + " – niplav"
}
});
</script>
</head><body><h2 id="home"><a href="./index.html">home</a></h2>
<p><em>author: niplav, created: 2024-01-26, modified: 2024-10-24, language: english, status: in progress, importance: 2, confidence: certain</em></p>
<blockquote>
<p><strong>I've decided to learn some real math, not just computer scientist
math.</strong></p>
</blockquote><div class="toc"><div class="toc-title">Contents</div><ul><li><a href="#Chapter_1">Chapter 1</a><ul><li><a href="#Question_1110">Question 1.1.10</a><ul></ul></li><li><a href="#Question_1116">Question 1.1.16</a><ul></ul></li><li><a href="#Exercise_1118">Exercise 1.1.18</a><ul></ul></li><li><a href="#Exercise_126">Exercise 1.2.6</a><ul></ul></li><li><a href="#Exercise_135">Exercise 1.3.5</a><ul></ul></li><li><a href="#Question_145">Question 1.4.5</a><ul></ul></li><li><a href="#Exercise_156">Exercise 1.5.6</a><ul></ul></li><li><a href="#Problem_1A">Problem 1A</a><ul></ul></li><li><a href="#Problem_1B">Problem 1B</a><ul></ul></li><li><a href="#Problem_1C">Problem 1C</a><ul></ul></li></ul></li></ul></div>
<h1 id="Solutions_to_An_Infinitely_Large_Napkin"><a class="hanchor" href="#Solutions_to_An_Infinitely_Large_Napkin">Solutions to “An Infinitely Large Napkin”</a></h1>
<blockquote>
<p>Natural explations supersede proofs.</p>
</blockquote>
<p><em>—Evan Chen, “An Infinitely Large Napkin” p. 6, 2023</em></p>
<h2 id="Chapter_1"><a class="hanchor" href="#Chapter_1">Chapter 1</a></h2>
<h3 id="Question_1110"><a class="hanchor" href="#Question_1110">Question 1.1.10</a></h3>
<blockquote>
<p>Why do we need the fact that <code>$p$</code> is a prime?</p>
</blockquote>
<p>If <code>$p$</code> weren't a prime, then the operation is not closed (because there
are elements of the group that divide the group size), and therefore there
are elements that are not invertible. Take <code>$(ℤ/4ℤ)^{\times}$</code>. Then
the element <code>$2$</code> is not invertible:
<code>$2 \cdot 1=2, 2 \cdot 2=4 \text{ mod } 4=0, 2 \cdot 3=6 \text{ mod } 4=2$</code>.</p>
<p>So the group operation is not closed, and also <code>$2$</code> doesn't have
an inverse.</p>
<h3 id="Question_1116"><a class="hanchor" href="#Question_1116">Question 1.1.16</a></h3>
<blockquote>
<p>What are the identity and the inverses of the product group?</p>
</blockquote>
<ul>
<li>Identity: The tuple that contains the identities of each group, <code>$(1_G, 1_H)$</code></li>
<li>Inverses: The tuple that contains the element-wise inverses for <code>$(g_1, h_1)^{-1}=(g_1^{-1}, h_1^{-1})$</code></li>
</ul>
<h3 id="Exercise_1118"><a class="hanchor" href="#Exercise_1118">Exercise 1.1.18</a></h3>
<blockquote>
<ul>
<li>(a) Rational numbers with odd denominators (in simplest form), where
the operation is addition. (This includes integers, written as <code>$n/1$</code>,
and <code>$0 = 0/1)$</code>.</li>
</ul>
</blockquote>
<p>This is indeed a group.</p>
<ol>
<li>The identity element is 0.</li>
<li>The operation <code>$+$</code> is associative.</li>
<li>Every element has an inverse, it's simply the negation of the element.</li>
</ol>
<p>Now, is the <code>$+$</code> operation closed?</p>
<div>
$$\frac{a}{2n+1} + \frac{b}{2m+1}=\frac{(2m+1)a+(2n+1)b}{4mn+2n+2m+1}$$
</div>
<p>It looks like the denominator must stay odd, but I'm not <em>sure</em> that's
necessary.</p>
<p>Assume <code>$(2m+1)a+(2n+1)b=u \cdot k$</code> and <code>$4mn+2n+2m+1=l \cdot k$</code>. Then
<code>$k$</code> must be greater than or equal to three.</p>
<blockquote>
<ul>
<li>(b) The set of rational numbers with denominator at most 2, where the operation is addition.</li>
</ul>
</blockquote>
<p>I assume we're excluding denominator zero.</p>
<p>Then we have identity (0), associativity and the inverse (again the
negative). The operation looks pretty closed to me as well.</p>
<blockquote>
<ul>
<li>(c) The set of rational numbers with denominator at most 2, where the operation is multiplication.</li>
</ul>
</blockquote>
<p>This set is not a group, because with the identity element <code>$1$</code> the
number <code>$3$</code> doesn't have an inverse.</p>
<blockquote>
<ul>
<li>(d) The set of nonnegative integers, where the operation is addition.</li>
</ul>
</blockquote>
<p>This set is also not a group because it doesn't have the inverse for,
e.g., the number <code>$1$</code>.</p>
<h3 id="Exercise_126"><a class="hanchor" href="#Exercise_126">Exercise 1.2.6</a></h3>
<ol>
<li><code>$x \mapsto gx$</code> is an injection: Assume there is a <code>$y$</code> so that no <code>$x$</code> so that <code>$gx=y$</code>. Then let <code>$g^{-1}y=x'$</code> (and ignore the suggestive naming). But then <code>$gg^{-1}y=gx'$</code> and therefore <code>$y=gx'$</code>. So such a <code>$y$</code> can't exist.</li>
<li><code>$x \mapsto gx$</code> is an surjection: Assume <code>$x \not =x'$</code>. Assume also <code>$gx=y=gx'$</code>. Then <code>$gx=gx'$</code>. But then <code>$g^{-1}g=g^{-1}gx'$</code>, so <code>$x=x'$</code>.</li>
</ol>
<p>A thing that tripped me up was that I then tried to prove that right
multiplication <em>isn't</em> a bijection—only to give up in confusion and
later find out that it is <em>also</em> a bijection. So much for suggestive
questions.</p>
<h3 id="Exercise_135"><a class="hanchor" href="#Exercise_135">Exercise 1.3.5</a></h3>
<p>Let <code>$g$</code> be the primite root modulo <code>$p$</code>. Then the isomorphism between
<code>$ℤ/(p-1)ℤ \cong (ℤ/pℤ)^{\times}$</code> is <code>$\phi(x)=g^x \mod p$</code>.</p>
<h3 id="Question_145"><a class="hanchor" href="#Question_145">Question 1.4.5</a></h3>
<ul>
<li>0: Order 1 (it's already the identity element)</li>
<li>1: Order 6, <code>$1+1+1+1+1+1 \mod 6=0$</code></li>
<li>2: Order 3, <code>$2+2+2 \mod 6=0$</code></li>
<li>3: Order 2, <code>$3+3 \mod 6=0$</code></li>
<li>4: Order 3, <code>$4+4+4 \mod 6=0$</code></li>
<li>5: Order 6, <code>$5+5+5+5+5+5 \mod 6=0$</code></li>
</ul>
<h3 id="Exercise_156"><a class="hanchor" href="#Exercise_156">Exercise 1.5.6</a></h3>
<p>I don't quite get this question. I think I need <em>more</em> information about
<code>$G$</code> in order to answer it? Otherwise all I can say about <code>$\langle x \rangle$</code>
is that it contains 2015 elements (or alternatively infinitely many).</p>
<h3 id="Problem_1A"><a class="hanchor" href="#Problem_1A">Problem 1A</a></h3>
<p>The joke here is that a group can only have a proper subgroup isomorphic
to itself if the group is infinitely big. Hence, the person's love for
their partner is infinite.</p>
<p>Sweet.</p>
<h3 id="Problem_1B"><a class="hanchor" href="#Problem_1B">Problem 1B</a></h3>
<p>If we allow <strong>Fact 1.4.7</strong> to be given, then this is easy
to prove: If <code>$\text{ord } g$</code> must divide <code>$|G|$</code> then
<code>$g^{|G|}=g^{\frac{|G|}{\text{ord }g} \cdot \text{ord }g}=1_G^{\frac{|G|}{\text{ord }g}}=1_G$</code>.</p>
<p>However, if we can't assume <strong>Fact 1.4.7</strong> then we haven't made our
job easier.</p>
<p>Assume <code>$\text{ord } g$</code> does not divide <code>$|G|$</code>. Then it is either the
case that (1) <code>$\text{ord } g<|G|$</code> or (2) <code>$\text{ord } g>|G|$</code>.</p>
<ol>
<li>Dunno?</li>
<li>In this case, by the pigeonhole principle, there must be some <code>$i, j \in ℕ$</code> so that <code>$g^i=g^j$</code>, with <code>$i<j<\text{ord } g$</code>. But then <code>$g^j \cdot g^{\text{ ord} g-j}=1$</code>, but then also <code>$g^i \cdot g^{\text{ ord} g-j} \not =1$</code>, even though they are the same operation. This can't be the case, so we exclude <code>$\text{ord } g>|G|$</code>.</li>
</ol>
<h3 id="Problem_1C"><a class="hanchor" href="#Problem_1C">Problem 1C</a></h3>
<p>Let the isomorphism <code>$\phi$</code> be as follows: <code>$\phi(1)=\{1, 2, 3\},
\phi(s)=\{1, 3, 2\}, \phi(r)=\{3, 1, 2\}, \phi(r^2)=\{2, 3, 1\}, \phi(rs)=\{2,
1, 3\}, \phi(r^2s)=\{3, 2, 1\}$</code>.</p>
<p>I could go through the pairs of elements of <code>$D_6$</code> individually, but
that seems not smart.</p>
</body></html>