The time is now - Spring classes are filling up!

MIT PRIMES/Art of Problem Solving

CROWDMATH 2023: Arithmetic of Power Monoids

G
Topic
First Poster
Last Poster
Are all numerical monoids finitely generated?
Number_Basher   1
N Nov 22, 2023 by Number_Basher
Are all numerical monoids finitely generated? My intuition agrees with the statement, but I cannot formulate a proof.
1 reply
Number_Basher
Nov 22, 2023
Number_Basher
Nov 22, 2023
minor progress regarding open problem 1b
smileapple   21
N Nov 19, 2023 by jujumumu
Here are a few ideas that could potentially be useful for Open Problem 1b (unimodality of $\alpha_{i,j}$). However, most of them probably still need lots of extra work and are very incomplete.

Part I, notation
For no particular reason, let us call some $S\in M=\mathcal{P}_{\text{fin},0}(\mathbb{N}_0)$ singular if it is noninvertible and not an atom. Because $\mathcal{U}(M)$ is just $\{\{0\}\}$, it follows that $S$ is singular iff we can write it as $S=T_1+T_2$ where the $T_i\in M$ both have at least a nonzero element.

Because $T_1,T_2\in M$, we must have $0\in T_1\cap T_2.$ Hence, if $t\in T_1$, then $t+0\in T_1+T_2=S,$ implying that $T_1\subseteq S.$ Similarly $T_2\subseteq S.$ It follows that $|S|\ge|T_1\cup T_2|.$

Part II, classification of singular sets (small cases)
What I did next was to find possible "structures" of singular $S$ for cases where $|S|$ was small.

So if $|S|=1$, then $S=\{0\}$ because $S\in M$ and thus contains $0$. But $\{0\}$ is invertible, so $S$ is neither an atom nor is singular.

If $|S|=2$, then $S=\{0,a\}.$ However, if $S=T_1+T_2$ such that $x_i$ is a nonzero element of $T_i$, then $\{0,x_1,x_2,x_1+x_2\}\subseteq S,$ so this implies that $x_1=x_2=x_1+x_2$ as $|S|=2,$ so that $x_1=x_2=0.$ But this is impossible, so $S$ can't be singular if $|S|=2.$

Now consider $|S|=3$, so $S=\{0,a,b\}.$ Then we can write $$S=\{0,\cdots\cdots\cdots\}+\{0,\cdots\cdots\cdots\},$$where the $\cdots$ represents some unknown element. Then all the elements $\{0,\cdots\cdots\cdots\}$ must also be in $S$, as established previously. Hence WLOG we let $a$ be in the first component set $T_1$: $$S=\{0,a,\cdots\cdots\cdots\}+\{0,\cdots\cdots\cdots\}.$$Then, let $x\in T_2$: $$S=\{0,a,\cdots\cdots\cdots\}+\{0,x,\cdots\cdots\cdots\}.$$Then, $\{0,a,x,a+x\}\subseteq S,$ so we must have $x=a$ in order to satisfy $|S|=3.$ Thus one singular form would be $$\boxed{\{0,a,2a\}}=\{0,a\}+\{0,a\}.$$
Next, consider $|S|=4$, in which $S=\{0,a,b,c\}.$ We use the same $a$-$x$ setup as before: $$S=\{0,a,\cdots\cdots\cdots\}+\{0,x,\cdots\cdots\cdots\}.$$Here we have two cases.

Case 4a
If $a\neq x$, then WLOG let $x=b$ as $x\in T_2\subseteq S.$ Then $\{0,a,b,a+b\}\subseteq S,$ and clearly $0$, $a$, $b$, and $a+b$ must all be distinct. Thus $a+b=c$ and $S=\{0,a,b,a+b\}$ since $|S|=4.$ Thus another singular form here is $$\boxed{\{0,a,b,a+b\}}=\{0,a\}+\{0,b\}.$$
Case 4b
If $a=x$, then $a$ is in both $T_i$, so clearly $2a\in S.$ Thus, WLOG let's set $b=2a.$ Now we have $$S=\{0,a,\cdots\cdots\cdots\}+\{0,a,\cdots\cdots\cdots\}.$$Since $|S|=4$, we clearly aren't done yet, so let's add some other $y$ to any of the sets, WLOG $T_1.$ Hence $$S=\{0,a,y,\cdots\cdots\cdots\}+\{0,a,\cdots\cdots\cdots\},$$so $\{0,a,2a,y,a+y\}\subseteq S,$ so inspection reveals that $y$ must be $2a$ in order for $|S|$ to be $4.$ In that case our singular set form is $$\{0,a,2a,3a\}=\{0,a,2a\}+\{0,a\}.$$However, this is just a unique case of the one from Case 4a.

To conclude, if $|S|=4$, we have $1$ significant singular form: $$\boxed{\{0,a,b,a+b\}}=\{0,a\}+\{0,b\}.$$
Finally, we tackle the case where $|S|=5,$ which implies that $S=\{0,a,b,c,d\}.$ (This is by far the most complicated case.) Once again, use our $x$-$a$ construction is $$S=\{0,a,\cdots\cdots\cdots\}+\{0,x,\cdots\cdots\cdots\},$$and we also have two big cases.

Case 5a
If $a\neq x$, let $x=b$ WLOG. Then, at most four elements of $S$ are known, so we must add some element $y$ to one of the $T_i$. WLOG, add $y$ to $T_1$, so that $$S=\{0,a,y,\cdots\cdots\cdots\}+\{0,x,\cdots\cdots\cdots\}.$$Then $\{0,a,b,a+b,y,b+y\}\subseteq S.$ Then exactly one of $y$ and $b+y$ is in $\{0,a,b,a+b\}$; otherwise, $|S|$ would be $6.$ Inspection reveals that the only possibilities for $y$ are $b$, $a+b$, and $a-b$, so the possible constructions of $S$ are $$\{0,a,b,a+b,2b\},$$$$\{0,a,b,a+b,a+2b\},$$and $$\{0,a,b,a+b,a-b\}.$$However, if we let $a'=a-b$ and $b'=b$, note that $\{0,a,b,a+b,a-b\}=\{0,a'+b',b',a',a'+2b'\}=\{0,a',b',a'+b',a'+2b'\},$ so the latter two cases above are the same. Hence we have two structures here for $|S|=5$: $$S=\boxed{\{0,a,b,a+b,2b\}}=\{0,a,b\}+\{0,b\}$$and $$S=\boxed{\{0,a,b,a+b,a+2b\}}=\{0,a,a+b\}+\{0,b\}.$$
Case 5b
If $a=x$, things get a whole lot more complicated. Specifically, we have $$S=\{0,a,\cdots\cdots\cdots\}+\{0,a,\cdots\cdots\cdots\},$$so $S$ must include $a+a=2a,$ which WLOG we let be equal to $b.$ Then we use the same strategy: add some $y$ to some $T_i$, WLOG $T_1.$ Then there are two more cases based on whether $b=y$.

Case 5bi
If $b\neq y$, then $$S=\{0,a,y,\cdots\cdots\cdots\}+\{0,a,\cdots\cdots\cdots\},$$so $0+y=y\in S.$ Since $a\neq b\neq y$, so WLOG let $y=c.$ If so, $\{0,a,y,2a,a+y\}=\{0,a,2a,c,a+c\}$ so it follows that $a+c=d$ and $2a=b.$ But this is exactly what we found in 5a, so this isn't anything new.

Case 5bii
Here $b=y.$ Thus $$S=\{0,a,2a,\cdots\cdots\cdots\}+\{0,a,\cdots\cdots\cdots\},$$so $\{0,a,2a,3a\}\in S,$ so WLOG let $c=3a.$ If so, we must add a new element $z$ to either set. If we add it to $T_1$, then $$S=\{0,a,2a,z,\cdots\cdots\cdots\}+\{0,a,\cdots\cdots\cdots\},$$so $\{0,a,2a,3a,2a+z,a+z\}\subseteq S$, and it is easy to see by inspection that $z=2a$, so that $d=4a.$ Similarly, if we add $z$ to $T_2$, then $$S=\{0,a,2a,\cdots\cdots\cdots\}+\{0,a,z,\cdots\cdots\cdots\},$$giving $\{0,a,2a,3a,z,a+z,2a+z\}\subseteq S.$ Again, inspection gives $z=2a$, so $d=4a.$ Hence in both cases, $$S=\{0,a,2a,3a,4a\},$$which again is just a special case of 5a. Hence, again we have nothing new.

Thus, the only two distinct general forms for $|S|=5$ are $$S=\boxed{\{0,a,b,a+b,2b\}}=\{0,a,b\}+\{0,b\}$$and $$S=\boxed{\{0,a,b,a+b,a+2b\}}=\{0,a,a+b\}+\{0,b\}.$$
I feel like the process for findings these forms are recursive in some way. Maybe the number of unique forms as $|S|$ increases will follow a linear recursions, such as that of the Fibonacci sequence. But I don't know yet, since I'm still thinking about the $|S|=6,$ which is even more complicated than before.

Part III, computations
Here I was able to use the results from Part II to bash out the first values of $\alpha_{n,k}$ by hand, for positive integers $n\le5.$ The method I used was basically just noting that $\alpha_{n,0}=\alpha_{n,1}=0$ and $\alpha_{n,2}=n$, and brute-forcing everything else when $k\ge3.$ The results I got were
\begin{align*}
(\alpha_{1,0},\alpha_{1,1})&=(0,0),\\
(\alpha_{2,0},\alpha_{2,1},\alpha_{2,2})&=(0,0,2),\\
(\alpha_{3,0},\alpha_{3,1},\alpha_{3,2},\alpha_{3,3})&=(0,0,3,2),\\
(\alpha_{4,0},\alpha_{4,1},\alpha_{4,2},\alpha_{4,3},\alpha_{4,4})&=(0,0,4,4,2),\\
(\alpha_{5,0},\alpha_{5,1},\alpha_{5,2},\alpha_{5,3},\alpha_{5,4},\alpha_{5,5})&=(0,0,5,8,6,1).
\end{align*}which seems to agree with the conjecture of unimodality. If I get to $n=8$ I might be able to get a gauge on the bound for Problem 1.1 found by $2^{\binom{k+1}{2}+(k+1)+2}$, as $$2^{\binom{0+1}{2}+(0+1)+2}=8.$$
Part IV, finite differences???
This is one final whimsical thought that I had. The idea is that if the $\alpha_{n,k}$ are unimodal, then interpreting this as a function of $k$ for a fixed $n$ will give a concave-down graph. If so, then the second difference of the $\alpha_{n,k}$ must be nonpositive, much like $f''\le0$ for concave-down functions. If so, the second finite difference is $$(\alpha_{n,k+1}-\alpha_{n,k})-(\alpha_{n,k}-\alpha_{n,k-1})=\alpha_{n,k+1}-2\alpha_{n,k}+\alpha_{n,k-1}.$$I'm not sure how to continue with this though. I'll keep trying this method, though I'm doubtful of how useful this strategy is.

--WJH
21 replies
smileapple
Apr 22, 2023
jujumumu
Nov 19, 2023
A result regarding problem 2
GPZ   7
N Oct 26, 2023 by felixgotti
Let $M$ be an atomic Puiseux monoid. We will split the proof of the problem into the following two cases.

Case 1: $M$ is a MCD monoid. Suppose, by way of contradiction, that $\mathcal{P}_{\text{fin}}(M)$ is not atomic, then there exists some non-atomic element $A$ of $\mathcal{P}_{\text{fin}}(M)$. This implies that for every factorization of $A$, one of the factors must be a non-atomic element. Consider the set $L:=\{|B|, \text{ where } B \text{ is a non-atomic divisor of } A\}$. $L\subset \mathbb{N}$ so it has a minimum, namely $k$. See that $k>1$ because every element of $M$ is an atomic element. Now consider one element $B_k=\{b_1,b_2,\ldots,b_k\}$ of $L$. See that $|B_k|=k$. Now, if we take $d=\text{mcd}(b_1,b_2,\ldots,b_k)$ we have that $b_n-d$ belongs to $M$ for all $n\in[[1,k]]$, so $B_d:=\{b_1-d,b_2-d,\ldots,b_k-d\}$ is an element of $\mathcal{P}_{\text{fin}}(M)$. Now we have that $B_k=B_d+\{d\}$. Clearly $\{d\}$ is an atomic element of $\mathcal{P}_{\text{fin}}(M)$. Let us prove that $B_d$ is also an atomic element of $\mathcal{P}_{\text{fin}}(M)$. Let $C+D$ be an arbitrary factorization of $B_d$. If $|C|<|B_d|$ and $|D|<|B_d|$, then none of them belongs to $L$ and that implies that $B_d$ is an atomic element. So we will assume WLOG that $|C|=|B_d|$, but this implies that $|D|=1$, so $D=\{0\}$, because 0 is the only common divisor of the set $B_d$. So $B_d$ is an atomic element, implying that $B_k$ is an atomic element, which is a contradiction. Notice that if $M$ is a $k$-MCD atomic cancellative monoid, then we have proved that every element $B$ in $\mathcal{P}_{\text{fin}}(M)$ such that $|B|\le k$ is an atomic element of $\mathcal{P}_{\text{fin}}(M)$.

Case 2: $M$ is not a 2-MCD monoid. In this case, we know that there exists two elements of $M$, namely $a$ and $b$, such that $\text{mcd}(a,b)$ does not exist. Let us prove that the element $\{a,b\}$ is not an atomic element of $\mathcal{P}_{\text{fin}}(M)$. Suppose, by way of contradiction, that $\{a,b\}=\sum\limits_{k=1}^{n}A_n$, where $A_n$ is an atom of $\mathcal{P}_{\text{fin}}(M)$ for all $n\in \mathbb{N}$. We can tell WLOG that $|A_1|=2$ and $|A_n|=1$ for all $n\ge2$. But, since $A_1=\{a,b\}-\sum\limits_{k=2}^{n}A_n=\{a,b\}-\{c\}$, and $\{c\}\neq\text{mcd}(a,b)$, it must exists some non-invertible element $C$ of $\mathcal{P}_{\text{fin}}(M)$ such that $C|_{\mathcal{P}_{\text{fin}}(M)}A_1$ which is a contradiction.

I have not find an atomic Puiseux monoid non 2-MCD, but if this monoid exists, we will be able to find a non-atomic element in $\mathcal{P}_{\text{fin}}(M)$ and we could conclude that in general the property of being atomic does not ascend from $M$ to $\mathcal{P}_{\text{fin}}(M)$.
7 replies
GPZ
Apr 6, 2023
felixgotti
Oct 26, 2023
Resource 0 Questions
DouDragon   2
N Oct 11, 2023 by PiGuy3141592
Hi, I'm just reading over the resources. I don't quite understand what a unit of $M$ is. Can someone explain?
2 replies
DouDragon
Sep 29, 2023
PiGuy3141592
Oct 11, 2023
Casework
CharmaineMa07292010   1
N Sep 13, 2023 by WilsonLiuwz
What I've tried so far:
I've tried to consider a few cases in the set N ( positive integers) and showed that it was true. I then moved on to show that this is true for k integers in each set.

<Describe what you have tried so far here. That way, we can do a better job helping you!>

Where I'm stuck:
I don't know how I can prove that the statement is true for any set S.

<Describe what's confusing you, or what your question is here!>
1 reply
CharmaineMa07292010
Aug 30, 2023
WilsonLiuwz
Sep 13, 2023
Welcome to CrowdMath 2023!
felixgotti   7
N Aug 13, 2023 by felixgotti
Hi everyone!

Welcome to CrowdMath 2023!

CrowdMath is a collaborative and inclusive research program welcoming participants from all cultural background and region in the planet. With this in mind, we expect all participants to be respectful with their peers and mentors.

Research Project

Our research project this year will be focused on additive combinatorics and power monoids. We will initially consider certain open questions related the set of all finite subsets consisting of nonnegative integers under the Minkowski addition (see https://en.wikipedia.org/wiki/Minkowski_addition). Following our motivating paper (see https://arxiv.org/abs/1701.09152), we call this the power monoid of $\mathbb{N}_0$. Then keeping Minkowski addition in mind, we will study generalized versions of the power monoid of $\mathbb{N}_0$. Although the algebraic (ideal theoretical) and arithemetic properties of power monoids have been systematically investigated only recently, there has been a significant activity in this research area during the last five years. This last statement will be ratified by the CrowdMath resources we will be posting throughout the next few months.

Problems

The section Problems contains the main open problems pertaining the CrowdMath 2023 project. The problems will become systematically available during the coming months as we progress and learn the necessary background and tools needed to understand and work on them. All of the proposed open problems will be thematically linked to the 2023 CrowdMath research project. Most of the problems in the section Problems will have an associated resource, which can be found in the section Resource.

Resources

The content of each resource is directly connected and relevant to the CrowdMath 2023 project. Indeed, each resource contains the notions, definitions, and tools the participants will be learning as the primary sources to understand and make progress on the coming list of open problems. Resources also comes with practice exercises for participants to train. We highly encourage CrowdMath participants to try to solve all the practice exercises, as this will help to deeper understand the new concepts and to get a better insight of the overall project. Participants can discuss the exercises by clicking either the `View Discussions' or `Start New Topic' button.

Intellectual Property

As CrowdMath is a massive collaborative project, sometimes it is not possible to determine the lines between one participant's work and the rest of the group. In such cases, the results created must be attributed to all CrowdMath contributors.
7 replies
felixgotti
Jan 26, 2023
felixgotti
Aug 13, 2023
Exercise 3.2
smileapple   6
N Jun 15, 2023 by felixgotti
& here's a solution to Exercise 3.2. as usual, pls let me know if there are any errors in my reasoning
Problem: Construct a monoid that is almost atomic but not nearly atomic.
-----
-----
Solution: Let $S$ contain the reciprocals of the powers of $2$; that is $$S=\left\{\frac12,\frac14,\frac18,\frac1{16},\cdots\right\}.$$Now let $$M=\left\langle S\cup\left\{\frac13\right\}\right\rangle.$$In other words, if $b\in M$, we can write $$b=\left(\frac{p_1}2+\frac{p_2}4+\frac{p_3}8+\frac{p_4}{16}+\cdots\right)+\frac{r}3.$$-----
Now we determine $\mathcal{A}(M).$ Clearly, if $a\in\mathcal{A}(M),$ it must be in the generating set of $M$; that is, either $a=\frac{1}{2^q}$ or $a=\frac13.$ However, the former case is invalid, as $a=\frac{1}{2^q}=\frac{1}{2^{q+1}}+\frac{1}{2^{q+1}}.$ It is easy to see that the latter case works. Thus $\mathcal{A}(M)=\left\{\frac13\right\}.$
-----
Note that the some of the $\frac{p_i}{2^i}$ on the right hand side must terminate at some point; for instance, we cannot say that $$\frac17=\frac18+\frac1{64}+\frac1{512}+\frac1{4096}+\cdots$$is in $M$; we can only conclude that there exist an infinitude of elements in $M$ that approach $\frac17.$ Under this logic, it follows that there must exist some $q$ such that $p_i=0$ for all $i>q.$ We can thus write $$\frac{p_1}2+\frac{p_2}4+\frac{p_3}8+\frac{p_4}{16}+\cdots+\frac{p_q}{2^q}=\frac{p}{2^q}$$for some $p\in\mathbb{N}.$ Thus, if $b\in M$, then we can write $$b=\frac{p}{2^q}+\frac{r}3.$$It is easy to see that all elements of this form must work as well.
-----
We claim that $M$ is almost atomic. Specifically, for $b=\frac{p}{2^q}+\frac{r}{3},$ let us define $c=\frac{2^q-p}{2^q},$ so that $b+c=1+\frac{r}3=\frac{r+3}3,$ which is truly atomic, reusing the same notation from $\S$3.1.
-----
However, we will also prove that $M$ is not nearly atomic. Suppose by contradiction that there exists some $c=\frac{p_0}{2^{q_0}}+\frac{r_0}3$ such that $b+c$ is truly atomic for all $b\notin\mathcal{U}(M).$ However, setting $b=\frac{1}{2^{q_0+1}},$ we have $$b+c=\frac{2p_0+1}{2^{q_0+1}}+\frac{r_0}3.$$Since $2p_0+1$ is odd and $2^{q_0+1}$ is even, it is clear that $\frac{2p_0+1}{2^{q_0+1}}$ cannot be written in the form $\frac{r_1}3$ for some $r_1\in\mathbb{N}$ and thus $b+c$ is not truly atomic, a contradiction. Thus our $M$ works by construction. $\blacksquare$
6 replies
smileapple
May 13, 2023
felixgotti
Jun 15, 2023
Exercise 3.3
aeemc2   11
N Jun 12, 2023 by smileapple
Here`s a solution to exercise 3.2. Please let me know if there are any errors.
Define $ S = \lbrace  \frac{1}{2^n}: n \in N \rbrace$. Now let $ \mathbb{K}= \langle S \rangle $ The set K is an infinite subset of $ \mathbb{Q}_{\ge 0}$. Then it is countable, and we can construct a bijection f between $ \mathbb{K} $ and $ \mathbb{P}_{>3} $ where $ \mathbb{P}_{>3} $ is the set of prime numbers greater than 3. Define the monoid $M=\langle k, \frac{\frac{1}{3}+k}{f(k)} \rangle $ where $k \in K $. Firstly let's prove that $\mathcal{A}(M)= \lbrace \frac{\frac{1}{3}+k}{f(k)} :k \in K\rbrace$. We can write $ \frac{1}{2^n} = \frac{1}{2^{n+1}}+ \frac{1}{2^ {n+1}} $ Then any number k such that $k \in K$ is not an atom. We can prove that the elements $ \frac{\frac{1}{3}+k}{f(k)}$ are atoms. Suppose that $ \frac{\frac{1}{3}+k}{f(k)} = a+b $ where a and b are elements of M. Then we can write these elements as sum of generators. Let \[ a = k_{a} + \sum_{i=1}^ {n_{a}} \frac {\frac{1}{3}+k_{i}}{f(k_{i})} \]and \[ b = k_{b} + \sum_{j=1}^ {n_{b}} \frac{\frac{1}{3}+k_{j}}{f(k_{j})} \]with all $k_{i}$ and $k_{j}$ different than k. Then we have \[ \frac{\frac{1}{3}+k}{f(k)} = a+b = (k_{a}+k_{b})+ \sum_{i=1}^ {n_{a} + n_{b}} \frac{\frac{1}{3}+k_{i}}{f(k_{i})}\]but in this equality $ v_{f(k)}$ of the left side is -1 and for the right side 0. This contradiction proves the result. M is not atomic. Indeed 1/2 cannon be written as a sum of atoms. Suppose that $ 1/2 =a_1 \frac{\frac{1}{3}+k_1}{f(k_1)}+...+a_n \frac{\frac{1}{3}+k_n}{f(k_n)}$. If $f(k_i)$ does not divide $a_i$ then $v_{f(k_i)}$ of the right side is -1 and for the left side 0, contradiction. Then $f(k_i)|a_i$ for all i=1,2,...,n. Then we have that $1/2= b_1 (\frac{1}{3}+k_1) +...+ b_n (\frac{1}{3}+k_n) = (b_1+...+b_n) \frac{1}{3}+ b_ik_1+...+b_nk_n $ where $b_i= \frac{a_i}{f(k_i)}$. If 3 does not divide $(b_1+...+b_n)$ then $v_{3}$ of the right side is -1 and for the left side 0. Then $3|(b_1+...+b_n)$ but this implies that $ 1/2 = (b_1+...+b_n) \frac{1}{3}+ b_ik_1+...+b_nk_n  \ge 1$, a contradiction. Let`s prove that M is nearly atomic. Firstly we have that $\frac{1}{3}= f(0) \frac{1/3}{f(0)} \in M$. We can write an arbitrary element of M as \[ k+ \sum_{i=1}^{n}a_i \]where $k \in K $ and $a_i$ are atoms of M. Then we have that \[1/3 + k+ \sum_{i=1}^{n}a_i = f(k) \frac{1/3+k}{f(k)} + \sum_{i=1}^{n}a_i \]. Then M is nearly atomic.
11 replies
aeemc2
May 15, 2023
smileapple
Jun 12, 2023
A result regarding problem 3
aeemc2   0
May 18, 2023
Hello everyone. Here I present some ideas related to Problem 3 that could be helpful. Please let me know if there are any mistakes.

Let M be an atomic (and therefore nearly atomic) MCD monoid. Then as was shown in the Problem 2, $\mathcal{P}_{fin}(M)$ is atomic and consequently nearly atomic. Then we have to analyze two cases: M is not an MCD monoid or M is not atomic. I`m working in the first case.

Let M be an atomic monoid that is not a 2-MCD monoid as in exercise 2. Clearly, M is nearly atomic. I`m trying to find a monoid that satisfies these properties and the following: For every set $C=\lbrace c_1,c_2,...,c_n \rbrace$ such that $mcd(c_1,...,c_n)$ exists, there also exists $gcd(c_1,...,c_n)$ and, consequently they are equal. If such a monoid exists, then mcd is an associative operation, and the following reasoning is valid.

Lemma 1: If $mcd(x_1,x_2,...,x_n)=x$, then $mcd (x_1+y,x_2+y,...,x_n+y)=y+x $

Proof: Clearly, if $mcd (x_1+y,x_2+y,...,x_n+y)$ exists, it must be at least y because $y|y+x_i$ for all i. Since $mcd(x_1,x_2,...,x_n)=x$, then the set $N_d=\lbrace x_1-x,...,x_n-x \rbrace$ does not have a non-invertible common divisor and $x|x_i$ for all $i=1,2,...,n.$ Clearly, that implies that $x+y$ divides all the elements $x_i+y$ for all i, and $N_d= \lbrace (x_1+y)-(x+y),...,(x_n+y)-(x+y) \rbrace =  \lbrace x_1-x,...,x_n-x \rbrace$ does not have a non-invertible common divisor. That proves that $x+y=mcd(x_1+y,...,x_n+y)$

Lemma 2:
Let $A_1,A_2 \in  \mathcal{P}_{fin}(M) $ and $B=A_1+A_2$. $A_1= \lbrace a_1^1,...,a_{l_1}^1 \rbrace$, $A_2= \lbrace  a_1^2,...,a_{l_2}^2\rbrace $ and $B=\lbrace b_1,b_2,...,b_m\rbrace$. If $d_1= mcd (a_1^1,...,a_{l_1}^1) $ and $ d_2 = (a_1^2,...,a_{l_2}^2)$ Then if $d= mcd ( b_1,b_2,...,b_m) $, $d=d_1+d_2$

Proof: In this proof, we use the fact that gcd (and consequently mcd in this case) is an associative operation.By induction on $l_1$ that is the cardinality of the set $A_1$. For $l_1 =1$ the result is elemental and it can be deduced from lemma 1. For $l_1=2$, suppose that $A_1=\lbrace a_1^1,a_2^1 \rbrace$ and $A_2= \lbrace  a_1^2,...,a_{l_2}^2\rbrace $. $B=\lbrace a_1^1+a_1^2,...,a_1^1+a_{l_2}^2, a_2^1+a_1^2,...,a_2^1+ a_{l_2}^2 \rbrace$ Now by lemma 1, it`s clear that $mcd(a_1^1+a_1^2+...a_1^1+a_{l_2}^2)=a_1^1+d_2$. Similarly $mcd(a_2^1+a_1^2,...,a_2^1+ a_{l_2}^2 )=a_2^1+d_2$. Now we know that $mcd(a_1^1+a_1^2,...,a_1^1+a_{l_2}^2, a_2^1+a_1^2,...,a_2^1+ a_{l_2}^2)=mcd(a_1^1+d_2,a_2^1+d_2)=d_1+d_2$
Suppose the proposition holds for $l_i=n$ and consider $A_1$ such that $|A_1|=n+1$. Then we have $B=\lbrace a_1^1+a_1^2,...,a_1^1+a_{l_2}^2,..., a_{l_i-1}^1+a_1^2,...,a_{l_i-1}^1+ a_{l_2}^2,a_{l_i}^1+ a_1^2,...,a_{l_i}^1+ a_{l_2}^2 \rbrace $. We also have that $mcd(a_1^1+a_1^2+...a_1^1+a_{l_2}^2,..., a_{l_i-1}^1+a_1^2,...,a_{l_i-1}^1+ a_{l_2}^2,a_{l_i}^1+ a_1^2,...,a_{l_i}^1+ a_{l_2}^2)=mcd(mcd(a_1^1+a_1^2+...a_1^1+a_{l_2}^2,..., a_{l_i-1}^1+a_1^2,...,a_{l_i-1}^1+ a_{l_2}^2),mcd(a_{l_i}^1+ a_1^2,...,a_{l_i}^1+ a_{l_2}^2))$. See that $\lbrace a_1^1+a_1^2+...a_1^1+a_{l_2}^2,..., a_{l_i-1}^1+a_1^2,...,a_{l_i-1}^1+ a_{l_2}^2\rbrace$ is the sum of the sets $\lbrace a_1^1,..., a_{l_i-1}^1 \rbrace + A_2$ and by induction hypothesis $mcd(a_1^1+a_1^2+...a_1^1+a_{l_2}^2,..., a_{l_i-1}^1+a_1^2,...,a_{l_i-1}^1+ a_{l_2}^2)= d_1`+d_2 $where $d_1`=mcd (a_1^1,...,a_{l_i-1}^1)$. Finally applying the same procedure, we get that $mcd(a_1^1+a_1^2+...a_1^1+a_{l_2}^2,..., a_{l_i-1}^1+a_1^2,...,a_{l_i-1}^1+ a_{l_2}^2,a_{l_i}^1+ a_1^2,...,a_{l_i}^1+ a_{l_2}^2) = mcd(d_1`+d_2, a_{l_i}^1+d_2) =mcd ( d_1` ,a_{l_i}^1)+d_2=mcd (a_1^1,...,a_{l_i}^1)+d_2=d_1+d_2$. Since $l_2 $ is an arbitrary number, the lemma holds for the sum of two sets of any cardinality.

Lemma 3: If $B=\lbrace b_1,b_2,...,b_m\rbrace$ and $A_i=\lbrace a_1^i,...,a_{l_i}^i \rbrace$ with $d_i=mcd(a_1^i,...,a_{l_i}^i ) $and $ d = mcd ( b_1,b_2,...,b_m)$. If $B=A_1+A_2+...+A_n$, then $d=d_1+d_2+...+d_n$

Proof: The proof is very easy by induction on n.
This lemma proves that if an element B of $ \mathcal{P}_{fin}(M) $ has a decomposition of the form $B=A_1+A_2+...+A_n$ and the mcd of the elements of B does not exist, then for one of the sets $A_i$ does not exist the mcd of its elements. Indeed if the mcd of the elements of each set $A_i$ exists, then by lemma 3 there exists the mcd of the elements of B.

Suppose that we have a monoid M that is not a 2-MCD monoid. Then $mcd(a,b)$ does not exist for some $a,b \in M$. Then there is not exists $mcd(a,b,2b,3b,...,(n-1)b)$. Then we can construct an element of any cardinality such that there`s not exists the mcd of its elements. Let B be such an element. By lemma 3, if we write B as $B=A_1+A_2+...+A_n$, then it does not exist the mcd for the elements of one of the set $A_i$, then this element is not an atom. Then it is impossible to write B as a sum of atoms in $ \mathcal{P}_{fin}(M) $.


Let C be an arbitrary element of $ \mathcal{P}_{fin}(M) $, $ C = \lbrace c_1,...,c_n\rbrace$, where $ \lbrace n\in \mathbb{N}, n>1 \rbrace$. Firstly, suppose that $mcd(c_1,...,c_n)$ does not exist. Let $B=\lbrace b \rbrace $ an arbitrary non-invertible element of $ \mathcal{P}_{fin}(M)$ with cardinality equals 1. And consider $B+C= \lbrace c_1+b,...,c_n+b \rbrace$ Suppose that $mcd (c_1+b,...,c_n+b)$ exist, then it is equal to $gcd(c_1+b,...,c_n+b)=d$ by the definition of our monoid. Since $b|c_i+b, b|d$, let $d=b+e$ for some $e \in M$, since $d|c_i+b$ for all i, we have that $c_i-e \in M$ for all i. Then e is a common divisor of the elements of C and, by definition $\lbrace c_1-e,...,c_n-e \rbrace$ does not have a non-invertible common divisor, then $e=mcd(c_1,...,c_n)$ a contradiction. Then $mcd (c_1+b,...,c_n+b)$ does not exist. Now suppose $mcd(c_1,...,c_2)$ exists and let $\lbrace a,b \rbrace$ such that does not exist $mcd(a,b)$. Then $C+B=\lbrace c_1+a,...,c_n+a,c_1+b,...,c_n+b \rbrace$ is an element of $ \mathcal{P}_{fin}(M) $ such that mcd of its elements does not exist. Indeed by lemma one and the associative property if $mcd(c_1,...,c_n)=d, mcd (c_1+a,...,c_n+a,c_1+b,...,c_n+b) = mcd (d+a,d+b)$ which not exists as we proved above. If $C=\lbrace c \rbrace$ it`s enough to take $B=\lbrace a,b \rbrace $ and then $C+B$ is again an element of $ \mathcal{P}_{fin}(M) $ such that mcd of its elements does not exist. We have proved that for any element $C$ of $\mathcal{P}_{fin}(M) $ we can find another non-invertible element B such that B+C is not atomic. That proves that $ \mathcal{P}_{fin}(M) $ is not nearly atomic.
Therefore, nearly atomicity does not ascend from M to $ \mathcal{P}_{fin}(M) $

Part b)
Let M be a Puiseux monoid that is not a $2$-MCD monoid and satisfies the above-mentioned property. Then there exists $a,b \in M$ such that $mcd(a,b)$ does not exist. Consider the non-invertible element $\lbrace a,b\rbrace $ and let $C=\lbrace c_1,...,c_n \rbrace$ be an atomic element of $\mathcal{P}_{fin}(M)$, then $mcd (c_1,...,c_n) $ exists and we have that for all C, $B+C=\lbrace a+c_1,...,a+c_n,b+c_1,...,b+c_n \rbrace$ and $mcd(a+c_1,...,a+c_n,b+c_1,...,b+c_n)$ does not exist. Then by the previous part of the exercise $B+C$ is not atomic for all atomic elements C . Then $\mathcal{P}_{fin}(M)$ is not almost atomic, and this concludes the proof.

I`m investigating if there exists a monoid that satisfies the properties mentioned, but if such a monoid exists then we can conclude that nearly and almost atomicity do not ascend from M to $ \mathcal{P}_{fin}(M) $
0 replies
aeemc2
May 18, 2023
0 replies
Exercise 3.3 [but its wrong]
smileapple   3
N May 14, 2023 by smileapple
Hi! here's my thoughts/tentative solution on Exercise 3.3. it feels a little sus somehow, mainly because using the $+_{\ge1}$ function sounds like cheating, so please let me know if there are any logical errors. thanks!
-----
-----
Problem: Construct a monoid that is nearly atomic but not atomic.
-----
-----
Solution: Consider the anomalous addition function $+_{\ge1}:\mathbb{R}\to\mathbb{R}$ defined by $\alpha+_{\ge1}\beta=\alpha+\beta$ if $\alpha+\beta\le1$ and $0$ otherwise. Also, define the parity addition function $+_2:\{0,1\}\to\{0,1\}$ such that we have $0+_20=1+_21=0$ and $0+_21=1+_20=1.$ Let $+_n$ be the operation $$(\alpha,p)+_n(\beta,q)=(\alpha+_{\ge1}\beta,p+_2q).$$Then, we let $M=\langle S\cup\{(0,1)\}\rangle$, where $$S=\left\{\left(\frac12,0\right),\left(\frac14,0\right),\left(\frac18,0\right),\left(\frac1{16},0\right),\cdots\right\}.$$-----
Using an argument similar to the one in $\S$3.2, we find the atoms of $M.$ Clearly, they must be in $S\cup\{(0,1)\},$ but since $$\left(\frac{1}{2^q},0\right)=\left(\frac{1}{2^{q+1}},0\right)+_n\left(\frac{1}{2^{q+1}},0\right),$$it follows that $S\cap\mathcal{A}(M)=\emptyset.$ It thus easily follows that $\mathcal{A}(M)=\{(0,1)\}.$
-----
The above implies that $M$ is not atomic: specifically, elements of the form $(\alpha,p)$ with $\alpha\neq 0$ are not truly atomic, again using the same terms from $\S$3.1.
-----
However, $M$ is nearly atomic: letting $c=(1,0)$ and $\alpha>0$, we have that $$(\alpha,p)+_n(1,0)=(\alpha+_{\ge1}1,p)$$but $\alpha+1\ge1$ implies that the above sum is $(0,p)$, which is truly atomic as $p\in\{0,1\}.$ Otherwise, if $\alpha=0$, then $(\alpha,p)$ is $(0,0)$ or $(0,1)$; since $(0,1)+_n(0,1)=(0,0)$, we must have that $(\alpha,p)$ is invertible. Thus $M$ is nearly atomic but not atomic, so we are done. $\blacksquare$
3 replies
smileapple
May 13, 2023
smileapple
May 14, 2023
A result regarding problem 2
GPZ   7
N Oct 26, 2023 by felixgotti
Let $M$ be an atomic Puiseux monoid. We will split the proof of the problem into the following two cases.

Case 1: $M$ is a MCD monoid. Suppose, by way of contradiction, that $\mathcal{P}_{\text{fin}}(M)$ is not atomic, then there exists some non-atomic element $A$ of $\mathcal{P}_{\text{fin}}(M)$. This implies that for every factorization of $A$, one of the factors must be a non-atomic element. Consider the set $L:=\{|B|, \text{ where } B \text{ is a non-atomic divisor of } A\}$. $L\subset \mathbb{N}$ so it has a minimum, namely $k$. See that $k>1$ because every element of $M$ is an atomic element. Now consider one element $B_k=\{b_1,b_2,\ldots,b_k\}$ of $L$. See that $|B_k|=k$. Now, if we take $d=\text{mcd}(b_1,b_2,\ldots,b_k)$ we have that $b_n-d$ belongs to $M$ for all $n\in[[1,k]]$, so $B_d:=\{b_1-d,b_2-d,\ldots,b_k-d\}$ is an element of $\mathcal{P}_{\text{fin}}(M)$. Now we have that $B_k=B_d+\{d\}$. Clearly $\{d\}$ is an atomic element of $\mathcal{P}_{\text{fin}}(M)$. Let us prove that $B_d$ is also an atomic element of $\mathcal{P}_{\text{fin}}(M)$. Let $C+D$ be an arbitrary factorization of $B_d$. If $|C|<|B_d|$ and $|D|<|B_d|$, then none of them belongs to $L$ and that implies that $B_d$ is an atomic element. So we will assume WLOG that $|C|=|B_d|$, but this implies that $|D|=1$, so $D=\{0\}$, because 0 is the only common divisor of the set $B_d$. So $B_d$ is an atomic element, implying that $B_k$ is an atomic element, which is a contradiction. Notice that if $M$ is a $k$-MCD atomic cancellative monoid, then we have proved that every element $B$ in $\mathcal{P}_{\text{fin}}(M)$ such that $|B|\le k$ is an atomic element of $\mathcal{P}_{\text{fin}}(M)$.

Case 2: $M$ is not a 2-MCD monoid. In this case, we know that there exists two elements of $M$, namely $a$ and $b$, such that $\text{mcd}(a,b)$ does not exist. Let us prove that the element $\{a,b\}$ is not an atomic element of $\mathcal{P}_{\text{fin}}(M)$. Suppose, by way of contradiction, that $\{a,b\}=\sum\limits_{k=1}^{n}A_n$, where $A_n$ is an atom of $\mathcal{P}_{\text{fin}}(M)$ for all $n\in \mathbb{N}$. We can tell WLOG that $|A_1|=2$ and $|A_n|=1$ for all $n\ge2$. But, since $A_1=\{a,b\}-\sum\limits_{k=2}^{n}A_n=\{a,b\}-\{c\}$, and $\{c\}\neq\text{mcd}(a,b)$, it must exists some non-invertible element $C$ of $\mathcal{P}_{\text{fin}}(M)$ such that $C|_{\mathcal{P}_{\text{fin}}(M)}A_1$ which is a contradiction.

I have not find an atomic Puiseux monoid non 2-MCD, but if this monoid exists, we will be able to find a non-atomic element in $\mathcal{P}_{\text{fin}}(M)$ and we could conclude that in general the property of being atomic does not ascend from $M$ to $\mathcal{P}_{\text{fin}}(M)$.
7 replies
GPZ
Apr 6, 2023
felixgotti
Oct 26, 2023
a