MIT PRIMES/Art of Problem Solving
CROWDMATH 2022: Factorizations in Additive Structures
Additive Factorizations
Polymath project forum
Polymath project forum
3
M
G
BBookmark
VNew Topic
kLocked
Additive Factorizations
Polymath project forum
Polymath project forum
3
M
G
BBookmark
VNew Topic
kLocked
No tags match your search
MExercise
resource1
algebra
polynomial
Resource 1
atomicity
catenary_degree
Resource 2
Betti elements
elasticity
factoriality
number theory
prime numbers
Problem 7
Resource 4
set of lengths
algebraic number
almost arithmetic progression
bifurcus monoid
calculus
catenary degree
confusing
crowdmath
CrowdMath Project
hilbert monoid
modular arithmetic
modular congruences
monoids
notation
polyomial
Problem 1
Problem 4
Problem 5
Problem 6
problem-2
Resource 3
sets of lengths
welcome
No tags match your search
MG
Topic
First Poster
Last Poster
Solution to Problem 7.1
Stiffler 2
N
Feb 3, 2023
by Stiffler
Hello!! In a recent post Julmath presented an example that solve part (a) of Problem 7.1. Then I will focus in solve part (b).
Solution of part (b)
Solution of part (b)
Take the polynomial . It is easy to see that it has some positive root . Moreover, it is irreducible and therefore it is the minimal polynomial of . Consider the monoid . We will prove that is atomic by arguing that .
We first assume that . Then there exists such that . Hence is a root of . Since is the minimal polynomial of there exists some polynomial such that . It is easy to see that the constant coefficient of is . However, Gauss lemma ensures that which is a contradiction.
Let us suppose now that for some . Since , we can infer that for every . Then, after dividing both sides of the previous equation by , we obtain that is not an atom, which is a contradiction. Therefore we conclude that is atomic
To see that does not satisfies the ACCP observe that is an ascending chain of principal ideals that does not stabilizes. In fact, since .
Since belongs to the family of polynomials that I presented in my last post, we already know that is a rank- monoid such that . This conclude this part of the prove.
We first assume that . Then there exists such that . Hence is a root of . Since is the minimal polynomial of there exists some polynomial such that . It is easy to see that the constant coefficient of is . However, Gauss lemma ensures that which is a contradiction.
Let us suppose now that for some . Since , we can infer that for every . Then, after dividing both sides of the previous equation by , we obtain that is not an atom, which is a contradiction. Therefore we conclude that is atomic
To see that does not satisfies the ACCP observe that is an ascending chain of principal ideals that does not stabilizes. In fact, since .
Since belongs to the family of polynomials that I presented in my last post, we already know that is a rank- monoid such that . This conclude this part of the prove.
2 replies
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 be a positive algebraic number such that is atomic. Suppose that is not finitely generated. Then has infinitely many Betti elements.
Proof: We have that . Let be the minimal pair of . Consider the set We know that , then is a nonempty set of positive integers. Let be its minimal element and let such that and . Consider such that . We have that is not an isolated vertex in if and only in there exists , , such that . It is not hard to see that for some . Then and . This contradictis the minimality of in . Hence is an isolated vertex in . Then is a Betti element of .
Now, for each , consider . It is clear that and , for all . Following exactly the same reasoning as before, we obtain that there exists an isolated vertex in . Therefore is a Betti element of for each . This concludes our proof.
Lemma: Let . We say that, for and , if for all and for some . Then, the set:
has only finitely many elements.
Proof: Let us proceed by induction on . If , we have that , and by the well-ordering theorem we have that has a minimal element . It follows that . Now, assume the Lemma is valid for . Let . Consider the set:
Fix , and such that . Then for every such that , we have that and . Now, let such that . Then we have that for some and some , , where
Let , such that . It is clear that for , . Applying the lemma in , we obtain that the set
has only finitely many elements.
Since we obtain that also has only finitely many elements. Our proof concludes
Theorem: Let be a positive algebraic number such that is atomic and finitely generated. Then has only finitely many Betti elements.
Proof: Let be the minimal polynomial of , . Suppose that is a Betti element of . Then, there exist such that and are not in the same connected component in . We can say that , , where . It is known that , for some . In this case we will say that produces a Betti element.
Consider the set . For and we say that if and only if for each , or .
It is not hard to see that is an equivalence relation that has finitely many equivalence classes. Let be an equivalence class of . Because of the definition of it is not hard to see that for some and , there exists a map such that for , where is the set of positive coeficients of . Now, note that if we have that for , then
It follows that there exists such that , , . Note that connects and in . Then does not produce a Betti element. Using Lemma 3 on it follows that only finitely many polynomials in produce a Betti element. Since there are only finitely many equivalence classes in , we conclude that must have only finitely many Betti elements.
Proposition: Let be a positive algebraic number such that is atomic. Suppose that is not finitely generated. Then has infinitely many Betti elements.
Proof: We have that . Let be the minimal pair of . Consider the set We know that , then is a nonempty set of positive integers. Let be its minimal element and let such that and . Consider such that . We have that is not an isolated vertex in if and only in there exists , , such that . It is not hard to see that for some . Then and . This contradictis the minimality of in . Hence is an isolated vertex in . Then is a Betti element of .
Now, for each , consider . It is clear that and , for all . Following exactly the same reasoning as before, we obtain that there exists an isolated vertex in . Therefore is a Betti element of for each . This concludes our proof.
Lemma: Let . We say that, for and , if for all and for some . Then, the set:
has only finitely many elements.
Proof: Let us proceed by induction on . If , we have that , and by the well-ordering theorem we have that has a minimal element . It follows that . Now, assume the Lemma is valid for . Let . Consider the set:
Fix , and such that . Then for every such that , we have that and . Now, let such that . Then we have that for some and some , , where
Let , such that . It is clear that for , . Applying the lemma in , we obtain that the set
has only finitely many elements.
Since we obtain that also has only finitely many elements. Our proof concludes
Theorem: Let be a positive algebraic number such that is atomic and finitely generated. Then has only finitely many Betti elements.
Proof: Let be the minimal polynomial of , . Suppose that is a Betti element of . Then, there exist such that and are not in the same connected component in . We can say that , , where . It is known that , for some . In this case we will say that produces a Betti element.
Consider the set . For and we say that if and only if for each , or .
It is not hard to see that is an equivalence relation that has finitely many equivalence classes. Let be an equivalence class of . Because of the definition of it is not hard to see that for some and , there exists a map such that for , where is the set of positive coeficients of . Now, note that if we have that for , then
It follows that there exists such that , , . Note that connects and in . Then does not produce a Betti element. Using Lemma 3 on it follows that only finitely many polynomials in produce a Betti element. Since there are only finitely many equivalence classes in , we conclude that must have only finitely many Betti elements.
0 replies
Till when is This years CrowdMath active ?
Rolo123 1
N
Jan 2, 2023
by felixgotti
I just joined CrowdMath today, Can I still participate or should I start from next year ?
1 reply
Problem 4
julmath 1
N
Jan 2, 2023
by felixgotti
Hello! Here I share an example where I am able to find the catenary degree of .
Suppose that the minimal pair of is , where and is not monic. It is not hard to see that is atomic and . Let , and , . If for some then there exists given by
and . Also . Following this procedure we can create a finite sequence such that and satisfies that for all .
Now, assume that , such that , and for all . Then
where . It is clear that for all , but the coefficient of the monomial of least degree in the right side of (1) is a multiple of . This is a contradiction. Then there exists a unique factorization such that every atom appears in less than times. Also note that is the factorization of minimal length of . We have proved that for every and there exists a n-chain of factorizations that connects and the unique factorization of minimal length of . It follows that . Following the same reasoning as before, we can prove that there is no such that , so . Then .
Suppose that the minimal pair of is , where and is not monic. It is not hard to see that is atomic and . Let , and , . If for some then there exists given by
and . Also . Following this procedure we can create a finite sequence such that and satisfies that for all .
Now, assume that , such that , and for all . Then
where . It is clear that for all , but the coefficient of the monomial of least degree in the right side of (1) is a multiple of . This is a contradiction. Then there exists a unique factorization such that every atom appears in less than times. Also note that is the factorization of minimal length of . We have proved that for every and there exists a n-chain of factorizations that connects and the unique factorization of minimal length of . It follows that . Following the same reasoning as before, we can prove that there is no such that , so . Then .
1 reply
Proposition Problem 4
Stiffler 1
N
Jan 2, 2023
by felixgotti
In the solution of open problem Banghenz found and such that is a non-FGM monoid with . In a recent post Julmath presents an example, again with , where . Here I address a result that I found that contrasts with their examples since it focuses in the case .
Proposition: Let be a positive integer. For every there exists a non-FGM rank-d monoid with and for every .
Proof
Proposition: Let be a positive integer. For every there exists a non-FGM rank-d monoid with and for every .
Proof
Take an irreducible polynomial such that and (for instance take with such that and ). Notice that and . Then has some positive root such that . Since is irreducible it is the minimal polynomial of . Now consider the monoid . From [1, Proposition 3.2] we have that rank . Moreover, we know that is atomic and since [1, Proposition 4.5]. However, is not FGM by virtue of [1, Proposition 5.7].
Let us call a factorization reduced if for every . Take and to be two different reduced factorizations of the same element . Then divides . However, or leading to a contradiction in both cases. Hence which implies that every element has at most one reduced factorization.
Define for every factorization as the greatest such that or if for every . Let us claim that for every and any factorization there exists a reduced and a -chain of factorization connecting and . We know that if , then is reduced and it satisfies our claim. Assume as an induction hypothesis that our claim holds for every such that . Now take such that , for some . Write . Observe that since is a root of . Let be the unique positive integers satisfying and . Consider the chain of factorizations of defined as
for every , where if and in other case. Observe that for each the factorization is obtained after replacing occurrences of the atom in by occurrences of the atom for every . Hence is a -chain of factorizations of since . Moreover, , and by induction hypotesis there exists a reduced and some -chain of factorizations connecting and . Our claim follows after concatenating both chains. Furthermore, for any two factorizations and of the same element the reduced factorization corresponding to each one is the same.
Take any two factorizations of the same element . We have just proved that there exists a reduced factorization and two -chain of factorizations and connecting with and with respectively. Then is a -chain of factorizations connecting and . Hence for every .
Suppose that and are two different factorizations of the same element such that . Then any atom appears at most times in as well as in . Hence any coefficient of the polynomial is smaller than , which contradicts the fact that divides it. We have then that for every , so we conclude that .
[1]. J. Correa-Morris, F. Gotti: On the additive structure of algebraic valuations of cyclic free semirings.
Let us call a factorization reduced if for every . Take and to be two different reduced factorizations of the same element . Then divides . However, or leading to a contradiction in both cases. Hence which implies that every element has at most one reduced factorization.
Define for every factorization as the greatest such that or if for every . Let us claim that for every and any factorization there exists a reduced and a -chain of factorization connecting and . We know that if , then is reduced and it satisfies our claim. Assume as an induction hypothesis that our claim holds for every such that . Now take such that , for some . Write . Observe that since is a root of . Let be the unique positive integers satisfying and . Consider the chain of factorizations of defined as
for every , where if and in other case. Observe that for each the factorization is obtained after replacing occurrences of the atom in by occurrences of the atom for every . Hence is a -chain of factorizations of since . Moreover, , and by induction hypotesis there exists a reduced and some -chain of factorizations connecting and . Our claim follows after concatenating both chains. Furthermore, for any two factorizations and of the same element the reduced factorization corresponding to each one is the same.
Take any two factorizations of the same element . We have just proved that there exists a reduced factorization and two -chain of factorizations and connecting with and with respectively. Then is a -chain of factorizations connecting and . Hence for every .
Suppose that and are two different factorizations of the same element such that . Then any atom appears at most times in as well as in . Hence any coefficient of the polynomial is smaller than , which contradicts the fact that divides it. We have then that for every , so we conclude that .
[1]. J. Correa-Morris, F. Gotti: On the additive structure of algebraic valuations of cyclic free semirings.
1 reply
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 , for rational :
Lemma 1.
- is atomic iff is not the reciprocal of any integer
- If is atomic, the Betti elements of are - If is atomic, the set of lengths of any element is an arithmetic progression with difference
Lemma 2. Let be a positive rational, and let such that is an irreducible n-th root of . Then the polynomial is irreducible in .
Proof: This is seen in the textbook Algebra by S. Lang, in page 297.
Corollary. Let be a positive rational, and let be a positive irreducible n-th root of . Then are linearly independent in .
Proof: The proof follows from Lemma 2; If these powers of were not linearly independent, the polynomial (whose unique positive real root is ) would be reducible in .
Claim. Let be a positive rational that is not the reciprocal of any integer, and let be a positive irreducible n-th root of . Let be the map defined by . Then the following statements hold:
is an isomorphism.
If , then for all . ( is the isomorphism mapping a collection of atoms to the element they form.)
Proof. It's easy to check that 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 corresponds to a unique -tuple of factorizations in , showing both surjectivity and injectivity. Since is generated by , its set of atoms must be a subset of this generating set. Moreover, as , any atom can be written in the form , where , , and . Thus, any factorization in can be written as For some coefficients . This can be rewritten further as
Lemma 1 shows that the set of atoms of is its generating set. Combining this with the previous equation, it's clear to see that the unique -tuple of factorizations in that maps to is . Thus, is an isomorphism.
implies that , and the linear independence shown in Corollary 1 shows that for all .
Corollary 1. Let be a positive rational that is not the reciprocal of any integer, and let be a positive irreducible n-th root of . The set of atoms of is its generating set, .
Proof: Any element that is generated by at least two generating elements can not be an atom, so . On the other hand, by the isomorphism , the factorizations of (where ) are isomorphic to the factorizations of the element in , where is at the -th index. As shown in Lemma 1, is an atom of , thus must be an atom, hence .
Corollary 2.Let be a positive rational that is not the reciprocal of any integer, and let be a positive irreducible n-th root of . The set of Betti elements of is Proof: For a fixed , we identify all Betti elements of the form , where . By the mapping , the factorizations of are isomorphic to the factorizations of the element in , where is at the -th index. [Previous result] shows that the only Betti elements of are . Thus, by isomorphism, the only Betti elements of this form are
Lastly, we prove that all elements of that involve at least two different (linearly independent) powers of can not be Betti elements. Let be such an element, where , and at least two of the 's are nonzero. By the mapping , the factorizations of are isomorphic to the factorizations of in . Let and be two arbitrary factorizations of , and let and be the -tuples of factorizations corresponding to them by . , and so by property in Claim 1, for all . As a result, is a sequence consisting of factorizations of . 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 . Therefore, is not a Betti element, and by isomorphism, is not a Betti element.
Corollary 3. Let be a positive rational that is not the reciprocal of any integer, and let be a positive irreducible n-th root of . For any , is an arithmetic progression with difference .
Proof: Let , where for all . By the mapping , the factorizations of are isomorphic to the factorizations of in . The length of a certain factorization of is equal to . Let . From Lemma 1, the length of the factorization of can take any value in . Moreover, since the terms of the -tuple are independent, . Thus, can take any value in
.
Hence, is an arithmetic progression with difference , and by isomorphism, the same applies to .
Please let me know if anything is unclear!
Lemma 1.
- is atomic iff is not the reciprocal of any integer
- If is atomic, the Betti elements of are - If is atomic, the set of lengths of any element is an arithmetic progression with difference
Lemma 2. Let be a positive rational, and let such that is an irreducible n-th root of . Then the polynomial is irreducible in .
Proof: This is seen in the textbook Algebra by S. Lang, in page 297.
Corollary. Let be a positive rational, and let be a positive irreducible n-th root of . Then are linearly independent in .
Proof: The proof follows from Lemma 2; If these powers of were not linearly independent, the polynomial (whose unique positive real root is ) would be reducible in .
Claim. Let be a positive rational that is not the reciprocal of any integer, and let be a positive irreducible n-th root of . Let be the map defined by . Then the following statements hold:
is an isomorphism.
If , then for all . ( is the isomorphism mapping a collection of atoms to the element they form.)
Proof. It's easy to check that 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 corresponds to a unique -tuple of factorizations in , showing both surjectivity and injectivity. Since is generated by , its set of atoms must be a subset of this generating set. Moreover, as , any atom can be written in the form , where , , and . Thus, any factorization in can be written as For some coefficients . This can be rewritten further as
Lemma 1 shows that the set of atoms of is its generating set. Combining this with the previous equation, it's clear to see that the unique -tuple of factorizations in that maps to is . Thus, is an isomorphism.
implies that , and the linear independence shown in Corollary 1 shows that for all .
Corollary 1. Let be a positive rational that is not the reciprocal of any integer, and let be a positive irreducible n-th root of . The set of atoms of is its generating set, .
Proof: Any element that is generated by at least two generating elements can not be an atom, so . On the other hand, by the isomorphism , the factorizations of (where ) are isomorphic to the factorizations of the element in , where is at the -th index. As shown in Lemma 1, is an atom of , thus must be an atom, hence .
Corollary 2.Let be a positive rational that is not the reciprocal of any integer, and let be a positive irreducible n-th root of . The set of Betti elements of is Proof: For a fixed , we identify all Betti elements of the form , where . By the mapping , the factorizations of are isomorphic to the factorizations of the element in , where is at the -th index. [Previous result] shows that the only Betti elements of are . Thus, by isomorphism, the only Betti elements of this form are
Lastly, we prove that all elements of that involve at least two different (linearly independent) powers of can not be Betti elements. Let be such an element, where , and at least two of the 's are nonzero. By the mapping , the factorizations of are isomorphic to the factorizations of in . Let and be two arbitrary factorizations of , and let and be the -tuples of factorizations corresponding to them by . , and so by property in Claim 1, for all . As a result, is a sequence consisting of factorizations of . 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 . Therefore, is not a Betti element, and by isomorphism, is not a Betti element.
Corollary 3. Let be a positive rational that is not the reciprocal of any integer, and let be a positive irreducible n-th root of . For any , is an arithmetic progression with difference .
Proof: Let , where for all . By the mapping , the factorizations of are isomorphic to the factorizations of in . The length of a certain factorization of is equal to . Let . From Lemma 1, the length of the factorization of can take any value in . Moreover, since the terms of the -tuple are independent, . Thus, can take any value in
.
Hence, is an arithmetic progression with difference , and by isomorphism, the same applies to .
Please let me know if anything is unclear!
0 replies
The last problem of CrowdMath 2022 has been posted!
felixgotti 0
Jan 1, 2023
Hi everyone! Check out the tab of problems. The last problem of CrowdMath 2022 (Problems 7), which has several parts, has just been posted. The problem is aimed to better understand the sets of lengths, catenary degrees, and the sets of Betti elements of the monoids we are studying in our research project. There is no resource corresponding to this last problem, but I have stated the new and needed definitions as part of the problem statement. Feel free of course to post any question you may have. Enjoy this last problem, and Happy New Year!!!
0 replies
Primes in polynomials
FelJac 2
N
Dec 25, 2022
by FelJac
Are there any polynomial of degree higher than one (e.g., n²+1), that contains infinitely many prime numbers?
Do any of you have any idea how we might prove this for a certain polynomial. This is an open problem, and a seemingly very difficult one. All thoughts about partial progres or so, would be very interesting to discuss. (Sorry for bad English).
Do any of you have any idea how we might prove this for a certain polynomial. This is an open problem, and a seemingly very difficult one. All thoughts about partial progres or so, would be very interesting to discuss. (Sorry for bad English).
2 replies
Problem 6 Solution
bangzheng 3
N
Dec 9, 2022
by Stiffler
Fix . Prove (or maybe disprove) that is not -furcus for any .
Solution
Solution
It is indeed not -furcus. Notice that if then it is obviously not -furcus, so we assume .
Let be two (nonempty) closed subset of , we claim that is also closed. To do this, BWOC, there is a real number such that is a limit point of . Then there exist infinite sequences such that as . As , after taking a subsequence we can assume as . Then also as . Because both and are closed we see , so , a contradiction.
BWOC, is -furcus. Take , which is a closed set in . Also notice that is countable. Therefore the set ( times) is also closed and countable. This shows that it cannot be dense in (otherwise because it is closed we see it is equal to , which is not countable). Thus there exist positive reals such that . Now there exists such that . Take . Then from assumption there exists a factorization where , which implies . However, , which has empty intersection with , a contradiction.
Let be two (nonempty) closed subset of , we claim that is also closed. To do this, BWOC, there is a real number such that is a limit point of . Then there exist infinite sequences such that as . As , after taking a subsequence we can assume as . Then also as . Because both and are closed we see , so , a contradiction.
BWOC, is -furcus. Take , which is a closed set in . Also notice that is countable. Therefore the set ( times) is also closed and countable. This shows that it cannot be dense in (otherwise because it is closed we see it is equal to , which is not countable). Thus there exist positive reals such that . Now there exists such that . Take . Then from assumption there exists a factorization where , which implies . However, , which has empty intersection with , a contradiction.
3 replies
Can I join Crowdmath?
Red_Fox_1293 5
N
Oct 6, 2022
by BabaLama
Hello all.
I am currently in eighth grade doing calculus. I have participated in many aops classes in the past, and I feel like I could contribute nicely to crowdmath. However, I see that people under highschool need pre-approval to participate in crowdmath. How do I get that, and can I participate in crowdmath? Any help is welcome.
Thanks,
-Red_Fox_1293
I am currently in eighth grade doing calculus. I have participated in many aops classes in the past, and I feel like I could contribute nicely to crowdmath. However, I see that people under highschool need pre-approval to participate in crowdmath. How do I get that, and can I participate in crowdmath? Any help is welcome.
Thanks,
-Red_Fox_1293
5 replies
Can I join Crowdmath?
Red_Fox_1293 5
N
Oct 6, 2022
by BabaLama
Hello all.
I am currently in eighth grade doing calculus. I have participated in many aops classes in the past, and I feel like I could contribute nicely to crowdmath. However, I see that people under highschool need pre-approval to participate in crowdmath. How do I get that, and can I participate in crowdmath? Any help is welcome.
Thanks,
-Red_Fox_1293
I am currently in eighth grade doing calculus. I have participated in many aops classes in the past, and I feel like I could contribute nicely to crowdmath. However, I see that people under highschool need pre-approval to participate in crowdmath. How do I get that, and can I participate in crowdmath? Any help is welcome.
Thanks,
-Red_Fox_1293
5 replies