Happy Thanksgiving! Please note that there are no classes November 25th-December 1st.

MIT PRIMES/Art of Problem Solving

CROWDMATH 2022: Factorizations in Additive Structures

G
Topic
First Poster
Last Poster
Solution to Problem 7.3
julmath   0
Jan 4, 2023
The answer is yes. I split the proof in a proposition, a lemma and a theorem.

Proposition: Let $\alpha $ be a positive algebraic number such that $\mathbb{N}_0[\alpha]$ is atomic. Suppose that $\mathbb{N}_0 [\alpha]$ is not finitely generated. Then $\mathbb{N}_0[\alpha]$ has infinitely many Betti elements.
Proof: We have that $\mathcal{A}(\mathbb{N}_0[\alpha])= \{ \alpha^n, n \in \mathbb{N}_0\}$. Let $(p(x),q(x))$ be the minimal pair of $\alpha$. Consider the set $$N=\{n\in \mathbb{N}\; |\; \exists x \in \mathbb{N}_0[\alpha], n \in \mathsf{L}(x) \land \vert \mathsf{Z}(x)\vert \geq 2\}$$We know that $p(1), q(1) \in N$, then $N$ is a nonempty set of positive integers. Let $m$ be its minimal element and let $x \in \mathbb{N}_0[\alpha]$ such that $m \in \mathsf{L}(x)$ and $\vert \mathsf{Z}(x)\vert \geq 2$. Consider $z \in \mathsf{Z}(x)$ such that $\vert z \vert=m$. We have that $z$ is not an isolated vertex in $\triangledown_x$ if and only in there exists $z' \in \mathsf{Z}(x)$, $z'\neq z$, such that $\gcd(z,z')>0$ . It is not hard to see that $z-\gcd(z,z'),z'-\gcd(z,z')\in \mathsf{Z}(y)$ for some $y \in \mathbb{N}_0[\alpha]$. Then $\vert z-\gcd(z,z')\vert \in N$ and $\vert z-\gcd(z,z')\vert<\vert z \vert$. This contradictis the minimality of $m$ in $N$. Hence $z$ is an isolated vertex in $\triangledown_x$. Then $x$ is a Betti element of $\mathbb{N}0[\alpha]$.
Now, for each $l \in \mathbb{N}$, consider $x_l=\alpha^lx$. It is clear that $m \in \mathsf{L}(x_l)$ and $\mathsf{Z}(x_l)\geq 2$, for all $l \in \mathbb{N}$. Following exactly the same reasoning as before, we obtain that there exists an isolated vertex in $\triangledown_{x_l}$. Therefore $x_l$ is a Betti element of $\mathbb{N}_0[\alpha]$ for each $l \in \mathbb{N}$. This concludes our proof.

Lemma: Let $V\subset \mathbb{N}^k$. We say that, for $v=(v_1,...,v_k)\in V$ and $v'=(v_1',...,v_k')\in V$, $v<v'$ if $v_i\leq v_i'$ for all $i=1,...,k$ and $v_j<v_j'$ for some $j=1,...,k$. Then, the set:
$$W=\{ v\in V: \nexists v' \in V , v'<v\}$$has only finitely many elements.

Proof: Let us proceed by induction on $k$. If $k=1$, we have that $V\subset \mathbb{N}$, and by the well-ordering theorem we have that $V$ has a minimal element $m$. It follows that $W=\{m\}$. Now, assume the Lemma is valid for $k=l$. Let $V\subset \mathbb{N}^{l+1}$. Consider the set:
$$ M=\{n \in \mathbb{N}: \exists v \in V, n= \max \{v_i\}\} $$Fix $n_0 \in M$, and $v \in V$ such that $n_0=\max \{v_i\}$. Then for every $v'\in V$ such that $\min\{v'_i\}>n_0$, we have that $v<v'$ and $v'\notin W$. Now, let $v'\in V$ such that $\min \{v_i'\} \leq n_0$. Then we have that for some $j\in [1,l+1]$ and some $s\in [1,n_0]$, $v'\in V_{j,s}$, where
$$V_{j,s}=\{ v \in V: v_j=\min\{v_i\}=s\}$$Let $f:V_{j,s}\rightarrow \mathbb{N}^l$, such that $f(v_1,...,v_{l+1})=(v_1,...v_{j-1},v_{j+1},...,v_{l+1})$. It is clear that for $x,y\in V_{j,s}$, $x<y\Leftrightarrow f(x)<f(y)$. Applying the lemma in $\mathsf{Im} f \subset \mathbb{N}^l$, we obtain that the set
$$W_{j,s}=\{v \in V_{j,s}: \nexists v' \in V_{j,s}, v'<v\}$$has only finitely many elements.
Since $W \subset \displaystyle\cup_{j,s} W_{j,s}$ we obtain that $W$ also has only finitely many elements. Our proof concludes

Theorem: Let $\alpha $ be a positive algebraic number such that $\mathbb{N}_0[\alpha]$ is atomic and finitely generated. Then $\mathbb{N}_0[\alpha]$ has only finitely many Betti elements.
Proof: Let $m_\alpha$ be the minimal polynomial of $\alpha$, $n+1=\vert \mathcal{A}(\mathbb{N}_0[\alpha])\vert$. Suppose that $b$ is a Betti element of $\mathbb{N}_0[\alpha]$. Then, there exist $z,z'\in \mathsf{Z}(b)$ such that $z$ and $z'$ are not in the same connected component in $\bigtriangledown_b$. We can say that $z=a(\alpha)$, $z'=b(\alpha)$, where $a(x), b(x) \in \mathbb{N}[x]$. It is known that $a(x)-b(x)=m_\alpha(x)r(x)$, for some $r\in \mathbb{Z}[x]$. In this case we will say that $m_\alpha(x)r(x)$ produces a Betti element.
Consider the set $P=\{ t(x)\in \mathbb{Z}[x]: m_\alpha(x) \vert t(x), \mathsf{gr}(t)\leq n\}$. For $g(x)=g_nx^n+...+g_0 \in P$ and $h(x)=h_nx^n+...+h_0 \in P$ we say that $gRh$ if and only if for each $i\in [0,n]$, $p_ih_i>0$ or $p_i=h_i=0$.
It is not hard to see that $R$ is an equivalence relation that has finitely many equivalence classes. Let $C$ be an equivalence class of $R$. Because of the definition of $R$ it is not hard to see that for some $k \in \mathbb{N}$ and $i_1,...,i_k \in [0,n]$, there exists a map $f:C\rightarrow \mathbb{N}^k$ such that for $t(x)=t_nx^n+...+t_0 \in C$, $f(t)=(t_{i_1},...,t_{i_k})$ where $\{t_{i_1},...,t_{i_k}\}$ is the set of positive coeficients of $t$. Now, note that if we have that for $t(x),s(x)\in C$, $f(s)<f(t)$ then
$$t^+(x)-s(x)=t^+(x)-s^+(x)+s^-(x)=T(x)\in \mathbb{N}[x] $$It follows that there exists $x\in \mathbb{N}_0[\alpha]$ such that $$z=t^+(\alpha)\in \mathsf{Z}(x)$$, $$z'=t^+(\alpha)-s^+(\alpha)+s^-(\alpha) \in \mathsf{Z}(x)$$, $$z''=t^-(\alpha)\in \mathsf{Z}(x)$$. Note that $z'$ connects $z$ and $z''$ in $\bigtriangledown_x$. Then $t(x)$ does not produce a Betti element. Using Lemma 3 on $\mathsf{Im}f$ it follows that only finitely many polynomials in $C$ produce a Betti element. Since there are only finitely many equivalence classes in $R$, we conclude that $\mathbb{N}_0[\alpha]$ must have only finitely many Betti elements.
0 replies
julmath
Jan 4, 2023
0 replies
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