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

MIT PRIMES/Art of Problem Solving

CROWDMATH 2023: Arithmetic of Power Monoids

G
Topic
First Poster
Last Poster
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
No more topics!
a