MIT PRIMES/Art of Problem Solving
CROWDMATH 2023: Arithmetic of Power Monoids
Arithmetic of Power Monoids
Polymath project forum
Polymath project forum
3
M
G
BBookmark
VNew Topic
kLocked
Arithmetic of Power Monoids
Polymath project forum
Polymath project forum
3
M
G
BBookmark
VNew Topic
kLocked
No tags match your search
MProblem 3
Power Monoid
Exercise 3
Puiseux monoid
Exercise 1
Exercise 2
Exercise 4
atomicity
atoms
Exercise 1.4
exercise 3.1
exercise 3.3
Exercise 5
Exercise 6
Exercise 7
induction
inequalities
Problem 1
almost atomicity
Cancellative
Diophantine equation
Exercise 1.1
Exercise 1.2
Exercise 1.3
exercise 1.5
Exercise 2.1
Exercise 2.2
Exercise 2.3
exercise 2.4
Exercise 2.6
exercise 3.2
Exercise 8
floor function
geometry
nearly atomicity
null - null
number theory
Problem 2
Problem 3
quick question
Ring Theory
strong induction
unimodality
No tags match your search
MG
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, 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 such that exists, there also exists 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 , then
Proof: Clearly, if exists, it must be at least y because for all i. Since , then the set does not have a non-invertible common divisor and for all Clearly, that implies that divides all the elements for all i, and does not have a non-invertible common divisor. That proves that
Lemma 2:
Let and . , and . If and Then if ,
Proof: In this proof, we use the fact that gcd (and consequently mcd in this case) is an associative operation.By induction on that is the cardinality of the set . For the result is elemental and it can be deduced from lemma 1. For , suppose that and . Now by lemma 1, it`s clear that . Similarly . Now we know that
Suppose the proposition holds for and consider such that . Then we have . We also have that . See that is the sum of the sets and by induction hypothesis where . Finally applying the same procedure, we get that . Since is an arbitrary number, the lemma holds for the sum of two sets of any cardinality.
Lemma 3: If and with and . If , then
Proof: The proof is very easy by induction on n.
This lemma proves that if an element B of has a decomposition of the form and the mcd of the elements of B does not exist, then for one of the sets does not exist the mcd of its elements. Indeed if the mcd of the elements of each set 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 does not exist for some . Then there is not exists . 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 , then it does not exist the mcd for the elements of one of the set , then this element is not an atom. Then it is impossible to write B as a sum of atoms in .
Let C be an arbitrary element of , , where . Firstly, suppose that does not exist. Let an arbitrary non-invertible element of with cardinality equals 1. And consider Suppose that exist, then it is equal to by the definition of our monoid. Since , let for some , since for all i, we have that for all i. Then e is a common divisor of the elements of C and, by definition does not have a non-invertible common divisor, then a contradiction. Then does not exist. Now suppose exists and let such that does not exist . Then is an element of such that mcd of its elements does not exist. Indeed by lemma one and the associative property if which not exists as we proved above. If it`s enough to take and then is again an element of such that mcd of its elements does not exist. We have proved that for any element of we can find another non-invertible element B such that B+C is not atomic. That proves that is not nearly atomic.
Therefore, nearly atomicity does not ascend from M to
Part b)
Let M be a Puiseux monoid that is not a -MCD monoid and satisfies the above-mentioned property. Then there exists such that does not exist. Consider the non-invertible element and let be an atomic element of , then exists and we have that for all C, and does not exist. Then by the previous part of the exercise is not atomic for all atomic elements C . Then 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
Let M be an atomic (and therefore nearly atomic) MCD monoid. Then as was shown in the Problem 2, 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 such that exists, there also exists 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 , then
Proof: Clearly, if exists, it must be at least y because for all i. Since , then the set does not have a non-invertible common divisor and for all Clearly, that implies that divides all the elements for all i, and does not have a non-invertible common divisor. That proves that
Lemma 2:
Let and . , and . If and Then if ,
Proof: In this proof, we use the fact that gcd (and consequently mcd in this case) is an associative operation.By induction on that is the cardinality of the set . For the result is elemental and it can be deduced from lemma 1. For , suppose that and . Now by lemma 1, it`s clear that . Similarly . Now we know that
Suppose the proposition holds for and consider such that . Then we have . We also have that . See that is the sum of the sets and by induction hypothesis where . Finally applying the same procedure, we get that . Since is an arbitrary number, the lemma holds for the sum of two sets of any cardinality.
Lemma 3: If and with and . If , then
Proof: The proof is very easy by induction on n.
This lemma proves that if an element B of has a decomposition of the form and the mcd of the elements of B does not exist, then for one of the sets does not exist the mcd of its elements. Indeed if the mcd of the elements of each set 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 does not exist for some . Then there is not exists . 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 , then it does not exist the mcd for the elements of one of the set , then this element is not an atom. Then it is impossible to write B as a sum of atoms in .
Let C be an arbitrary element of , , where . Firstly, suppose that does not exist. Let an arbitrary non-invertible element of with cardinality equals 1. And consider Suppose that exist, then it is equal to by the definition of our monoid. Since , let for some , since for all i, we have that for all i. Then e is a common divisor of the elements of C and, by definition does not have a non-invertible common divisor, then a contradiction. Then does not exist. Now suppose exists and let such that does not exist . Then is an element of such that mcd of its elements does not exist. Indeed by lemma one and the associative property if which not exists as we proved above. If it`s enough to take and then is again an element of such that mcd of its elements does not exist. We have proved that for any element of we can find another non-invertible element B such that B+C is not atomic. That proves that is not nearly atomic.
Therefore, nearly atomicity does not ascend from M to
Part b)
Let M be a Puiseux monoid that is not a -MCD monoid and satisfies the above-mentioned property. Then there exists such that does not exist. Consider the non-invertible element and let be an atomic element of , then exists and we have that for all C, and does not exist. Then by the previous part of the exercise is not atomic for all atomic elements C . Then 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
0 replies
No more topics!