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
Mcatenary_degree
Exercise
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
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
No more topics!