Frobenius templates in certain matrix ringsβ
Abstract
The classical Frobenius problem is to find the largest integer that cannot be written as a linear combination of a given set of positive, coprime integers using nonnegative integer coefficients. Prior work has generalized the classical Frobenius problem from integers to Frobenius problems in other rings. This paper explores Frobenius problems in various rings of (upper) triangular matrices with constant diagonal.
Timothy Eller
Georgia Southern University, [email protected]
Jakub Kraus
University of Michigan, [email protected]
Yuki Takahashi
Grinnell College, [email protected]
Zhichun (Joy) Zhang
Swarthmore College, [email protected]
Key words and phrases: Frobenius template, Frobenius problem, coin problem, monoid, ring.
AMS Subject Classification: 11D07, 11B05.
1 Introduction
Let be the set of nonnegative integers, the set of integers, , and, for , . A list in a set is a finite sequence of elements from . If and is a list in , we will say are coprime to mean . If we assume when , then a list in is coprime if and only if the list contains positive integers and the positive integers in the list are coprime. For an additive group , if and , then let .
Here is a 19th century theorem, due to Sylvester and Frobenius and others, restated to suit our purpose:
Theorem 1.1.
If are coprime, then for some , .
Note that because , if then
.
Note also that because is closed under addition, if and , then .
Thus, if we define, for , ,
we have that either or
, where is the least element of .
The classical Frobenius problem [3], sometimes called the βcoin problem,β is to evaluate at coprime lists in . Frobenius used to discuss this problem in his lectures [1], so this area of number theory happens to be named after him. For , there is a formula: if and , then . For there are no known general formulas, although there are formulas for special cases and there are algorithms; see [8]. The classical Frobenius problem inspired the results in [4], which in turn inspired Nicole Looper [6] to generalize the classical Frobenius problem by introducing the notion of a Frobenius template (defined below), allowing one to pose similar problems in rings other than .
All of our rings will contain a multiplicative identity, 1, and most will be commutative. An additive monoid in a ring , is a subset of that is closed under addition and contains the identity ; monoids, unlike groups, do not have to contain inverses. A Frobenius template in a ring is a triple such that:
-
(i)
is a nonempty subset of ,
-
(ii)
and are additive monoids in , and
-
(iii)
for all lists in ,
is a subset of .
For any valid template, the properties above guarantee that will also be an additive monoid in . The Frobenius set of a list is . Notice that implies that since , so . Notice also that the assumption that is closed under addition guarantees that if , then .
For a given template , the corresponding Frobenius problem is the following pair of tasks:
-
1.
Determine for which lists it is true that .
-
2.
For lists such that , describe the set .
Note that in all the Frobenius templates that have been studied so far, it has always been the case that , when nonempty, is a finite union of sets of the form for some .
The classical Frobenius problem revolves around the template in the ring . As discussed earlier, if and , then is nonempty if (and only if) are coprime, and in such cases. So the classical Frobenius problem has been completely solved when .
Our definition above of a Frobenius template is slightly less general than Looperβs definition in [6]. The difference is that in Looperβs templates, is allowed to vary with the list . This is absolutely necessary in order to get interesting and nontrivial results when the ring involved is a subring of , the complex numbers, that is not contained in , the real numbers. The ring of Gaussian integers, , is such a ring, a particularly famous member of the family of rings .
To see why we must let the element of a Frobenius template in such a ring depend on the list , here is an example in . Suppose and . Then consider and . What should be for this list? We set , an angular sector in . We so choose because , and no angular sector in properly contained in contains . Further, if is an additive monoid in which properly contains , then no translate , , is contained in . Thus is the only possible additive monoid in containing such that might possibly be nonempty.
We leave to the reader the verification of the claims in the previous paragraph. We hope that the main point is clear: letting vary with the list in the formulation of Frobenius problems in is necessitated by the nature of multiplication in the complex numbers. For an appreciation of Frobenius problems in such settings, see [4] and [5].
We do not take on similar difficulties here. In the next section we give some more or less obvious results in various Frobenius templates, then review previous results concerning templates in the rings with . In the third section, we classify the Frobenius set in a pleasing modification of the classical Frobenius template. In the fourth section, we solve Frobenius problems in rings of (upper) triangular matrices with constant diagonal and entries from a ring , where different choices of allow different templates. In the last section, we further generalize the idea of a Frobenius template and explore an example of this generalization.
2 Some fundamentals and known results
Throughout this section, will be a ring with multiplicative identity 1. A list in spans unity in if and only if for some .
Proposition 2.1.
Let be a Frobenius template in such that . If is a list in such that , then spans unity in .
Proof.
Let , i.e. and . Since and , it follows that . Therefore, for some , and , so . β
As a warm-up, here are some valid Frobenius templates with, in most cases, trivial solutions to the corresponding Frobenius problems. In each example, denotes a list in . Check that is nonempty, and are additive monoids in , and always contains .
-
1.
In the template , we have and
. This result extends to any template with . -
2.
Similar to example 1, templates of the form always have and .
-
3.
In the template , Proposition 2.1 shows that spans unity in if . Conversely, if spans unity, then .
-
4.
Suppose that is an ideal of and the template is . Clearly , so . Recall that is a subset of ; thus .
-
5.
Again, let be an ideal of , and now consider the template . When , this is example 3. In contrast, let be a proper ideal. Then no list spans unity in β but this is precisely because , so no facile conclusion based on Proposition 2.1 presents itself. Frobenius problems for this class of templates could be interesting. For instance, if the template is in , where is the ideal of even integers, it is straightforward to prove that if and only if the integers are coprime. In this case, and , where denotes Frobenius sets with respect to the classical template .
-
6.
If the template is in , then for every list . On the other hand, if we restrict the coefficients to the set of rational numbers with the template in , then is always empty, as is countable and any translate of is uncountable.
-
7.
Suppose that and are rings with associated Frobenius templates and , respectively. Let be the Cartesian product of and . The same goes for and , which are additive monoids (under componentwise addition) in the product ring . It is simple to see that is a valid Frobenius template in . Let be a list in with each for . If in , then
, where and are Frobenius sets in and , respectively. For , this result extends to the product ring .
Besides the Gaussian integers [4, 5], prior work on generalized Frobenius problems has concentrated on templates in the real subring , where is not a perfect square. Below, we showcase some highlights from this work. If is a positive integer with irrational square root, then is a subring of . Let and , which are both additive monoids in that contain .
-
1.
In the template , the result below is proven in [6]:
Theorem 2.1.
If , , , , then if and only if spans unity in and at least one of , is zero.
-
2.
In the template , the following is nearly proven in [2]:
Theorem 2.2.
If , then the following are equivalent:
-
(i)
;
-
(ii)
;
-
(iii)
spans unity in .
Since Theorem 2 of [2] proves , we simply appeal to Proposition 2.1 to prove the statement above, which is somewhat stronger than Theorem 2 in [2].
Also in [2], with reference to the template ,
is determined in a very special class of cases. Recall that for coprime positive integers , is the smallest such that .Theorem 2.3.
For ,
is a list in . We haveand, in such cases,
Note that the case is allowed in this result. Also, if the integers are coprime, then so are , so the second part of Theorem 2.3 uses well-defined expressions.
-
(i)
-
3.
With as above, recall that in the case of the classical template in , for coprime . In a tour de force in [7], Kim proves a similar formula for the template in :
Theorem 2.4.
Suppose , , , (see Theorem 2.1, above), and suppose that span unity in . Then .
Whatβs next? We propose these categories of rings where one might discover results of interest of the Frobenius type.
-
1.
Subrings of algebraic extensions of .
Prior work on the Gaussian integers and the rings has put us into the foothills of a mountain range in this area. Besides the extensions of of finite degree, what about the ring of algebraic integers? Or, a better choice to start with, the ring of real algebraic integers?
-
2.
Polynomial rings.
Somebody we know is working on this, but we havenβt heard from him for a year or so.
-
3.
Rings of square matrices.
Did we say our rings have to be commutative? No, we did not. Keep in mind that in noncommutative rings, the precise definition of
becomes important, since for from and from , the linear combinations and are not necessarily equal.
3 Modifying the classical template
The classical template uses nonnegative integer coefficients. What happens when we modify the available coefficients? Consider the template for some . When , this is the classical template.
Remember that when are coprime, is the unique integer such that with respect to the classical template. In the results that follow, retains this meaning, whereas Frob and reference the modified template .
Proposition 3.1.
If are coprime, then
Proof.
Suppose and . We will show , i.e.
Suppose , . It suffices to show that . Since , we have that , so there exist coefficients such that . Taking for yields the desired result. β
While reading the next proof, remember that for coprime , so .
Proposition 3.2.
Let and . If are coprime and is not divisible by or , then .
Proof.
By the preceding proposition, it suffices to show that . So let , and suppose that . We will find a contradiction, which will complete the proof.
Since , we have , so is an element of , so there exist such that
Now, if both and are , then equals a linear combination of and with nonnegative integer coefficients, which is impossible. We also cannot have since . So consider the case that and . In that case, , so , so divides . But and are coprime, so this implies that divides , which we have assumed to be false. Similarly and would imply that , yielding the contradiction that divides . Thus, all cases yield a contradiction, so our supposition that must be false. β
4 triangular matrices with constant diagonal
For a ring with multiplicative identity , let be the set under coordinatewise addition, with multiplication in defined by . is a ring with multiplicative identity , isomorphic to the ring of upper triangular matrices over with constant diagonal: . If is commutative, then is commutative.
We will concentrate on the cases when is a subring of the real field containing , and the Frobenius template is
Proposition 4.1.
Let be a subring of containing . For any positive integer , let be a list in . Then .
Proof.
Let , . Elements of look like
where and for all .
Suppose that is nonempty, so there is a tuple such that . Therefore, for all , we have . So for larger and larger , and for some nonnegative integers and () that vary with . Clearly as . Because each fixed , and each varying , it follows that as , and consequently as . But is a given constant; it does not vary with . Therefore, our supposition must be false, so . β
Moving on, we now know a sufficient condition for in a large swath of templates. The natural question is whether is ever nonempty, and the answer is yes.
Proposition 4.2.
Let be a subfield of . For any positive integer , let
be a sequence of -tuples (for ) satisfying . Then .
Proof.
We have
It will suffice to show that . Let , , so that . Then use the coefficients , , and for to show that , so . β
Proposition 4.1 can be generalized, mutatis mutandis, to being any linearly ordered commutative ring with unity. The same holds for Proposition 4.2, with the additional stipulation that is a unit. In both cases, the ordering is compatible with addition and multiplication.
In other words, setting as a subfield of yields a boring Frobenius template, since we can shrink elements of using coefficients in . If we prohibit such shrinking, the template becomes much more interesting. Notice that this modification is similar to Section 3βs modification of the classical template.
To make the following result fit on the page, we will temporarily adopt the convention that for a tuple , the notation stands for .
Proposition 4.3.
Let , and change to be . Let form a list of tuples in . If , then . If , then
Simple modifications to the proof of Proposition 4.1 will prove that Proposition 4.1 holds in this template. Since , Proposition 4.3 combines with Proposition 4.1 to prove that if for and , then is nonempty if and only if some .
Proof.
Case 0: Suppose , so elements of look like for . Notice that
or implies . Therefore, if , then . The converse is trivial, so this case is done.
The set is
The trickiness of the remaining cases is that both coordinates share the coefficient . Similar to the last paragraph, notice that or implies ; therefore, implies and .
Case 1: and . By remarks above, in this case . On the other hand, if , then , so . Therefore, , so .
Case 2: . Then and, by the proof in Case 1,
Therefore, to determine in this case, it is sufficient to determine which are in .
If , then for some , and . Then implies that and . Then we have that . If , then and . But this would imply that for any such that , , and this would contradict the assumption that .
Therefore, if and , then . But implies that for every . Therefore, for every satisfying . Therefore, .
Thus
so the proof in this case will be over if we show that is in . Suppose that and . We will see that . We may as well assume that . Then , so because and .
Case 3: and . By arguments on display above, . But it is also easy to see that (): if and , then .
It remains to determine . Suppose that and . Let satisfy , . Then implies that and . If then and . But then if , , contradicting the assumption that .
Therefore, . But implies that for all such that . Therefore, for all such . Therefore, .
To finish the proof in this case, it will suffice to show that , and for that it will suffice to show that if and then . For such , , so since and .
Case 4: . Clearly . If and then , so ; therefore, .
Next, we shall show that
by an argument that will be familiar to anyone who has read the proofs in cases 2 and 3.
Suppose that and . Then for some , and . If , then and . But then for all , , which contradicts the assumption that .
Therefore, . But then the fact that for all satisfying implies that for all such . Therefore , which shows that
On the other hand, if and , then . From and
we conclude that . Thus
To finish Case 4, we will determine . Suppose that , with and . Then for some , and . Then . If , then and .
Then for all such that , , which contradicts the assumption that . Therefore, . But then implies that for all satisfying . Therefore, for each such . Therefore, . Thus . On the other hand, suppose that and . Then . Thus, since and , . Thus . This, together with previous results, proves the claim in Case 4. β
We now shift focus to . Recall that is well-defined for coprime positive integers , with respect to the classical Frobenius template .
Proposition 4.4.
For , let be a list of -tuples (for ) satisfying and . Then
Proof.
Let and . Itβs sufficient to show that , i.e.
. Pick an arbitrary , i.e. choose integers and . To complete the proof, we will show that
Since , we can write for some nonnegative integers . For each , use Euclidean division to write for some new nonnegative integers and , then set so that . Can we find nonnegative such that ? Well, , so yes. Therefore, . β
Corollary 4.4.1.
For , let be a list of -tuples (for ) satisfying . is nonempty if and only if at least one .
Proof.
Combine propositions 4.1 and 4.4. β
We have seen results like this before, such as Theorem 2.1 of Section 2 and the paragraph preceding the proof of Proposition 4.3. Combining this corollary with the next result completely solves the Frobenius problem in the case and .
Proposition 4.5.
Suppose that , and are coprime, and . Then
Proof.
Let . By Proposition 4.4, and implies that . For the converse, we will prove the contrapositive. Suppose that . Then is not in , so is not in , yet . Hence .
Now assume that . Set for some nonnegative large enough such that . Consider any alternative expression of as using nonnegative coefficients . Recall that , so . Then since and are coprime, so . And is nonnegative, so , so for some nonnegative integer . Set so that ; hence . Suppose that ; there are nonnegative coefficients and such that . Consequently, for nonnegative integers and , so . But this is impossible, because , so our supposition must be false; . Therefore, . β
Proposition 4.5 shows that when , the set inclusion in the conclusion of Proposition 4.4 is an equality. However, for lists of length , there are counterexamples to the reverse set inclusion of Proposition 4.4, so Proposition 4.5 does not generalize to longer lists of tuples. The following is a counterexample: Let , , and . Then it can be shown that , but . In fact, it can be shown that . Furthermore, for , , and we have
so the Frobenius set might even be a union of two sets, each of the form , neither contained in the other. This situation resembles that of the classical template, in the sense that the Frobenius problem is completely solved for lists of length , but not for lists of length .
5 A more general template
Here we broaden our horizons and pass from the templates where and are thought of as subsets of the same overlying ring, to templates where is a monoid and is a set of functions acting on . The first kind of template, i.e. the only kind hitherto discussed in this paper, can be considered a special case of the second; furthermore, templates of the second kind cannot in general be interpreted as examples of the first kind. The different entries in the new kind of template have the same roles as the corresponding entries in the original kind of template.
For the sake of presentation, we will showcase a certain example of this new kind of template and leave the precise definitions to the reader. Let and let be the set of upper triangular matrices in . In the ring with coordinate addition and multiplication, is a monoid. However, is not contained in so this template is different from those considered previously. Note that contains an isomorphic copy of via the semiring embedding given by
Consider a general pair of tuples and . A general member of
has the form
with all entries coming from . As expected, is defined to be
Hence, by our understanding of the classical Frobenius problem, we see that
when nonempty, which is true if and only if .
From the case it is straightforward to see what is for arbitrary and . It is not difficult to generalize these results to column vectors and matrices for . Therefore these cases are no longer interesting, except for the connection between them and the classical Frobenius problem. We can get more challenging problems by restricting the matrices in . For instance, we could require the matrices to be symmetric, or upper triangular with constant diagonal.
These examples point to a generalized Frobenius template in which (or perhaps ) and are monoids in a ring , and is a monoid in the ring of endomorphisms of such that each maps into
References
- [1] Jorge LuisΒ RamΓrez AlfonsΓn. The diophantine Frobenius problem. Oxford University Press, 2005.
- [2] Lea Beneish, Brent Holmes, Peter Johnson, and Tim Lai. Two kinds of Frobenius problems in . International Journal of Mathematics and Computer Science, 7:93β100, 1982.
- [3] Alfred Brauer. On a problem of partitions. American Journal of Mathematics, 64:299β312, 1942.
- [4] Ken Dutch, Peter Johnson, Christopher Maier, and Jordan Paschke. Frobenius problems in the Gaussian integers. Geombinatorics, 20:93β109, January, 2011.
- [5] Ken Dutch and Christopher Maier. Frobenius sets for conjugate split primes in the Gaussian integers. Semigroup Forum, 88:113β128, 2014.
- [6] Peter Johnson and Nicole Looper. Frobenius problems in integral domains. Geombinatorics, 22:71β86, October, 2012.
- [7] Doyon Kim. Two-variable Frobenius problems in . International Journal of Mathematics and Computer Science, 10(2):251β266, 2015.
- [8] Janet Trimm. On Frobenius numbers in three variables. PhD thesis, Auburn University, 2006.