author: niplav, created: 2024-01-26, modified: 2024-01-31, language: english, status: in progress, importance: 2, confidence: certain

I've decided to learn some real math, not just computer scientist math.

Solutions to “An Infinitely Large Napkin”

Natural explations supersede proofs.

—Evan Chen, “An Infinitely Large Napkin” p. 6, 2023

Chapter 1

Question 1.1.10

Why do we need the fact that $p$ is a prime?

If $p$ 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 $(ℤ/4ℤ)^{\times}$. Then the element $2$ is not invertible: $2 \cdot 1=2, 2 \cdot 2=4 \text{ mod } 4=0, 2 \cdot 3=6 \text{ mod } 4=2$.

So the group operation is not closed, and also $2$ doesn't have an inverse.

Question 1.1.16

What are the identity and the inverses of the product group?

Exercise 1.1.18

This is indeed a group.

  1. The identity element is 0.
  2. The operation $+$ is associative.
  3. Every element has an inverse, it's simply the negation of the element.

Now, is the $+$ operation closed?

$$\frac{a}{2n+1} + \frac{b}{2m+1}=\frac{(2m+1)a+(2n+1)b}{4mn+2n+2m+1}$$

It looks like the denominator must stay odd, but I'm not sure that's necessary.

Assume $(2m+1)a+(2n+1)b=u \cdot k$ and $4mn+2n+2m+1=l \cdot k$. Then $k$ must be greater than or equal to three.

I assume we're excluding denominator zero.

Then we have identity (0), associativity and the inverse (again the negative). The operation looks pretty closed to me as well.

This set is not a group, because with the identity element $1$ the number $3$ doesn't have an inverse.

This set is also not a group because it doesn't have the inverse for, e.g., the number $1$.

Exercise 1.2.6

  1. $x \mapsto gx$ is an injection: Assume there is a $y$ so that no $x$ so that $gx=y$. Then let $g^{-1}y=x'$ (and ignore the suggestive naming). But then $gg^{-1}y=gx'$ and therefore $y=gx'$. So such a $y$ can't exist.
  2. $x \mapsto gx$ is an surjection: Assume $x \not =x'$. Assume also $gx=y=gx'$. Then $gx=gx'$. But then $g^{-1}g=g^{-1}gx'$, so $x=x'$.

A thing that tripped me up was that I then tried to prove that right multiplication isn't a bijection—only to give up in confusion and later find out that it is also a bijection. So much for suggestive questions.

Exercise 1.3.5

Let $g$ be the primite root modulo $p$. Then the isomorphism between $ℤ/(p-1)ℤ \cong (ℤ/pℤ)^{\times}$ is $\phi(x)=g^x \mod p$.

Question 1.4.5

Exercise 1.5.6

I don't quite get this question. I think I need more information about $G$ in order to answer it? Otherwise all I can say about $\langle x \rangle$ is that it contains 2015 elements (or alternatively infinitely many).

Problem 1A

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.


Problem 1B

If we allow Fact 1.4.7 to be given, then this is easy to prove: If $\text{ord } g$ must divide $|G|$ then $g^{|G|}=g^{\frac{|G|}{\text{ord }g} \cdot \text{ord }g}=1_G^{\frac{|G|}{\text{ord }g}}=1_G$.

However, if we can't assume Fact 1.4.7 then we haven't made our job easier.

Assume $\text{ord } g$ does not divide $|G|$. Then it is either the case that (1) $\text{ord } g<|G|$ or (2) $\text{ord } g>|G|$.

  1. Dunno?
  2. In this case, by the pigeonhole principle, there must be some $i, j \in ℕ$ so that $g^i=g^j$, with $i<j<\text{ord } g$. But then $g^j \cdot g^{\text{ ord} g-j}=1$, but then also $g^i \cdot g^{\text{ ord} g-j} \not =1$, even though they are the same operation. This can't be the case, so we exclude $\text{ord } g>|G|$.

Problem 1C

Let the isomorphism $\phi$ be as follows