The time is now - Spring classes are filling up!

MIT PRIMES/Art of Problem Solving

CROWDMATH 2022: Factorizations in Additive Structures

G
Topic
First Poster
Last Poster
Problem 7.2 solution
gourmet_salad   0
Jan 2, 2023
This can be viewed as an extension of existing results in the paper "Factorization invariants of Puiseux monoids generated by geometric sequences" (arxiv: https://arxiv.org/abs/1904.00219). In that paper, three results are shown about $M = \mathbb{N}_0[q]$, for rational $q = a/b$:
Lemma 1.
- $M$ is atomic iff $q$ is not the reciprocal of any integer
- If $M$ is atomic, the Betti elements of $M$ are $$\left\{ \frac{\mathsf{n}(q)^{m+1}}{\mathsf{d}(q)^m}\ \Big|\ m \in \mathbb{N}_0\right\}$$- If $M$ is atomic, the set of lengths of any element is an arithmetic progression with difference $a - b$


Lemma 2. Let $q$ be a positive rational, and let $n \geq 2$ such that $\sqrt[n]{q}$ is an irreducible n-th root of $q$. Then the polynomial $x^n - q$ is irreducible in $\mathbb{Q}$.
Proof: This is seen in the textbook Algebra by S. Lang, in page 297.

Corollary. Let $q$ be a positive rational, and let $\alpha \coloneqq \sqrt[n]{q}$ be a positive irreducible n-th root of $q$. Then $1, \alpha, \alpha^2, \dots, \alpha ^{n-1}$ are linearly independent in $\mathbb{Q}$.
Proof: The proof follows from Lemma 2; If these powers of $\alpha$ were not linearly independent, the polynomial $x^n - q$ (whose unique positive real root is $\alpha$) would be reducible in $\mathbb{Q}$.

Claim. Let $q$ be a positive rational that is not the reciprocal of any integer, and let $\alpha \coloneqq \sqrt[n]{q}$ be a positive irreducible n-th root of $q$. Let $f: \mathsf{Z}(\mathbb{N}_0[q])^n \rightarrow \mathsf{Z}(\mathbb{N}_0[\alpha])$ be the map defined by $f(z_1, z_2, \dots, z_n) = z_1 + \alpha z_2 + \alpha^2z_3 + \dots + \alpha^{n-1}z_n$. Then the following statements hold:
$(i)$ $f$ is an isomorphism.
$(ii)$ If $\pi(f(z_1, z_2, \dots, z_n)) = \pi(f(z_1', z_2', \dots, z_n'))$, then $\pi(z_i) = \pi(z_i')$ for all $i \in [1, n ]$. ($\pi$ is the isomorphism mapping a collection of atoms to the element they form.)
Proof. $(i)$ It's easy to check that $f$ is additive and maps the identity to itself, and thus it is a homomorphism. To show that it is an isomorphism, we will show that every factorization in $\mathsf{Z}(\mathbb{N}_0[\alpha])$ corresponds to a unique $n$-tuple of factorizations in $\mathsf{Z}(\mathbb{N}_0[q])^n$, showing both surjectivity and injectivity. Since $\mathbb{N}_0[\alpha]$ is generated by $\{\alpha^k \mid k \in \mathbb{N}_0\}$, its set of atoms must be a subset of this generating set. Moreover, as $\alpha^n =  q$, any atom $\alpha^{k'}$ can be written in the form $\alpha^rq^k$, where $k' = kn + r$, $k \geq 0$, and $r \in [0, n-1]$. Thus, any factorization in $z \in \mathsf{Z}(\mathbb{N}_0[\alpha])$ can be written as $$z = \sum_{r = 0}^{n-1}\sum_{k=0}^{\infty}c_{r,k}\alpha^rq^k$$For some coefficients $c_{r,k}\in\mathbb{N}_0$. This can be rewritten further as
$$z=\sum_{r = 0}^{n-1}\alpha^r(\sum_{k=0}^{\infty}c_{r,k}q^k)$$Lemma 1 shows that the set of atoms of $\mathbb{N}_0[q]$ is its generating set. Combining this with the previous equation, it's clear to see that the unique $n$-tuple of factorizations in $\mathsf{Z}(\mathbb{N}_0[q])^n$ that maps to $z$ is $(\sum_{k=0}^{\infty}c_{0,k}q^k, \sum_{k=0}^{\infty}c_{1,k}q^k, \dots, \sum_{k=0}^{\infty}c_{n-1,k}q^k)$. Thus, $f$ is an isomorphism.
$(ii)$ $\pi(f(z_1, z_2, \dots, z_n)) = \pi(f(z_1', z_2', \dots, z_n'))$ implies that $\pi(z_1) + \alpha \pi(z_2) + \dots + \alpha^{n-1}\pi(z_n) = \pi(z_1') + \alpha \pi(z_2') + \dots + \alpha^{n-1}\pi(z_n')$, and the linear independence shown in Corollary 1 shows that $\pi(z_i) = \pi(z_i')$ for all $i \in [1, n]$.

Corollary 1. Let $q$ be a positive rational that is not the reciprocal of any integer, and let $\alpha \coloneqq \sqrt[n]{q}$ be a positive irreducible n-th root of $q$. The set of atoms of $\mathbb{N}_0[\alpha]$ is its generating set, $\{\alpha^k \mid k \in \mathbb{N}_0\}$.
Proof: Any element that is generated by at least two generating elements can not be an atom, so $\mathcal{A}(N_0[\alpha]) \subseteq \{\alpha^k \mid k \in \mathbb{N}_0\}$. On the other hand, by the isomorphism $f$, the factorizations of $\alpha^{k'} = \alpha^rq^k$ (where $k' = kn+r$) are isomorphic to the factorizations of the element $(0, 0, \dots, 0, q^k, 0, \dots, 0)$ in $\mathbb{N}_0[q]^n$, where $q^k$ is at the $r$-th index. As shown in Lemma 1, $q^k$ is an atom of $N_0[q]$, thus $\alpha^{k'}$ must be an atom, hence $\mathcal{A}(N_0[\alpha]) = \{\alpha^k \mid k \in \mathbb{N}_0\}$.

Corollary 2.Let $q$ be a positive rational that is not the reciprocal of any integer, and let $\alpha \coloneqq \sqrt[n]{q}$ be a positive irreducible n-th root of $q$. The set of Betti elements of $\mathbb{N}_0[\alpha]$ is $$\left\{ \frac{\mathsf{n}(q)^{m+1}}{\mathsf{d}(q)^m}\alpha^r\ \Big|\ m \in \mathbb{N}_0\ \text{and}\ r \in [ 0, n-1 ]\right\}.$$Proof: For a fixed $r \in [0, n-1]$, we identify all Betti elements of the form $t\alpha^r$, where $t \in \mathbb{Q}_{>0}$. By the mapping $f$, the factorizations of $t\alpha^r$ are isomorphic to the factorizations of the element $(0, 0, \dots, 0, t, 0, \dots, 0)$ in $\mathbb{N}_0[q]^n$, where $t$ is at the $r$-th index. [Previous result] shows that the only Betti elements of $\mathbb{N}_0[q]$ are $\left\{ \frac{\mathsf{n}(q)^{m+1}}{\mathsf{d}(q)^m}\ \Big|\ m \in \mathbb{N}_0 \right\}$. Thus, by isomorphism, the only Betti elements of this form are $$\left\{ \frac{\mathsf{n}(q)^{m+1}}{\mathsf{d}(q)^m}\alpha^r\ \Big|\ m \in \mathbb{N}_0\right\}$$
Lastly, we prove that all elements of $\mathbb{N}_0[\alpha]$ that involve at least two different (linearly independent) powers of $\alpha$ can not be Betti elements. Let $a = t_0 + t_1\alpha + t_2\alpha^2 + \dots + t_{n-1}\alpha^{n-1}$ be such an element, where $t_i \in \mathbb{Q}_{\geq0}$, and at least two of the $t_i$'s are nonzero. By the mapping $f$, the factorizations of $a$ are isomorphic to the factorizations of $(t_0, t_1, \dots, t_{n-1})$ in $\mathbb{N}_0[q]^n$. Let $z$ and $z'$ be two arbitrary factorizations of $a$, and let $(z_0, z_1, \dots, z_{n-1})$ and $(z_0', z_1', \dots, z_{n-1}')$ be the $n$-tuples of factorizations corresponding to them by $f$. $\pi(z) = \pi(z') = a$, and so by property $(ii)$ in Claim 1, $\pi(z_i) = \pi(z_i')$ for all $i$. As a result, $(z_0, z_1, z_2 \dots, z_{n-1}) \rightarrow (z'_0, z_1, z_2 \dots, z_{n-1}) \rightarrow (z'_0, z'_1, z_2 \dots, z_{n-1}) \rightarrow \dots \rightarrow (z'_0, z'_1, z'_2, \dots, z'_{n_1})$ is a sequence consisting of factorizations of $(t_0, t_1, \dots, t_{n-1})$. Moreover, since at least two of these factorizations are non-zero, each two consecutive factorizations have non-zero greatest common divisor, and so this is a path within the factorization graph $\mathcal{G}((t_0, t_1, \dots, t_{n-1}))$. Therefore, $(t_0, t_1, \dots, t_{n-1})$ is not a Betti element, and by isomorphism, $a$ is not a Betti element.

Corollary 3. Let $q$ be a positive rational that is not the reciprocal of any integer, and let $\alpha \coloneqq \sqrt[n]{q}$ be a positive irreducible n-th root of $q$. For any $a \in \mathbb{N}_0[\alpha]$, $\mathsf{L}(a)$ is an arithmetic progression with difference $|\mathsf{n}(q) - \mathsf{d}(q)|$.
Proof: Let $a = t_0 + t_1\alpha + t_2\alpha^2 + \dots + t_{n-1}\alpha^{n-1}$, where $t_i \in \mathbb{Q}_{\geq0}$ for all $i$. By the mapping $f$, the factorizations of $a$ are isomorphic to the factorizations of $T = (t_0, t_1, \dots, t_{n-1})$ in $\mathbb{N}_0[q]^n$. The length of a certain factorization $(z_0, z_1, \dots, z_{n-1})$ of $T$ is equal to $\sum|z_i|$. Let $d = |\mathsf{n}(q) - \mathsf{d}(q)|$. From Lemma 1, the length of the factorization $z_i$ of $t_i$ can take any value in $\{\min\mathsf{L}(t_i) + dk | k \in [0, \frac{\max\mathsf{L}(t_i) - \min\mathsf{L}(t_i)}{d}]\}$. Moreover, since the terms of the $n$-tuple are independent, $\min\mathsf{L}(T) = \sum\min\mathsf{L}(t_i)$. Thus, $|(z_0, z_1, \dots, z_{n-1})|$ can take any value in

$$\{\min\mathsf{L}(T) + dk | k \in [0, \frac{\max\mathsf{L}(T) - \min\mathsf{L}(T)}{d}]\}$$.

Hence, $\mathsf{L}(T)$ is an arithmetic progression with difference $d$, and by isomorphism, the same applies to $\mathsf{L}(a)$.

Please let me know if anything is unclear!
0 replies
gourmet_salad
Jan 2, 2023
0 replies
No more topics!
a