This paper was converted on www.awesomepapers.org from LaTeX by an anonymous user.
Want to know more? Visit the Converter page.

Frobenius templates in certain πŸΓ—πŸ\mathbf{2\times 2} 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 2Γ—22\times 2 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 β„•\mathbb{N} be the set of nonnegative integers, β„€\mathbb{Z} the set of integers, β„€+:=β„•βˆ–{0}\mathbb{Z}^{+}\vcentcolon=\mathbb{N}\setminus\left\{0\right\}, and, for Ξ±1,…,Ξ±nβˆˆβ„•\alpha_{1},\dots,\alpha_{n}\in\mathbb{N}, M​N​(Ξ±1,…,Ξ±n):={βˆ‘i=1nΞ»i​αi:Ξ»1,…,Ξ»nβˆˆβ„•}MN(\alpha_{1},\dots,\alpha_{n})\vcentcolon=\{\sum_{i=1}^{n}\lambda_{i}\alpha_{i}:\lambda_{1},\dots,\lambda_{n}\in\mathbb{N}\}. A list in a set SS is a finite sequence of elements from SS. If nβˆˆβ„€+n\in\mathbb{Z}^{+} and (Ξ±1,…,Ξ±n)(\alpha_{1},\dots,\alpha_{n}) is a list in β„•\mathbb{N}, we will say Ξ±1,…,Ξ±n\alpha_{1},\dots,\alpha_{n} are coprime to mean gcd⁑(Ξ±1,…,Ξ±n)=1\gcd(\alpha_{1},\dots,\alpha_{n})=1. If we assume gcd⁑(Ξ±1,…,Ξ±n)β‰ 1\gcd(\alpha_{1},\dots,\alpha_{n})\neq 1 when Ξ±1=β‹―=Ξ±n=0\alpha_{1}=\dots=\alpha_{n}=0, then a list in β„•\mathbb{N} is coprime if and only if the list contains positive integers and the positive integers in the list are coprime. For an additive group GG, if SβŠ†GS\subseteq G and g∈Gg\in G, then let g+S:={g+s:s∈S}g+S\vcentcolon=\left\{g+s:s\in S\right\}.

Here is a 19th century theorem, due to Sylvester and Frobenius and others, restated to suit our purpose:

Theorem 1.1.

If Ξ±1,…,Ξ±nβˆˆβ„•\alpha_{1},\dots,\alpha_{n}\in\mathbb{N} are coprime, then for some wβˆˆβ„•w\in\mathbb{N}, w+β„•βŠ†M​N​(Ξ±1,…,Ξ±n)w+\mathbb{N}\subseteq MN(\alpha_{1},\dots,\alpha_{n}).

Note that because 0βˆˆβ„•0\in\mathbb{N}, if w+β„•βŠ†M​N​(Ξ±1,…,Ξ±n)w+\mathbb{N}\subseteq MN(\alpha_{1},\dots,\alpha_{n}) then
w∈M​N​(Ξ±1,…,Ξ±n)w\in MN(\alpha_{1},\dots,\alpha_{n}). Note also that because β„•\mathbb{N} is closed under addition, if w+β„•βŠ†M​N​(Ξ±1,…,Ξ±n)w+\mathbb{N}\subseteq MN(\alpha_{1},\dots,\alpha_{n}) and bβˆˆβ„•b\in\mathbb{N}, then w+b+β„•βŠ†w+β„•βŠ†M​N​(Ξ±1,…,Ξ±n)w+b+\mathbb{N}\subseteq w+\mathbb{N}\subseteq MN(\alpha_{1},\dots,\alpha_{n}). Thus, if we define, for Ξ±1,…,Ξ±nβˆˆβ„€+\alpha_{1},\dots,\alpha_{n}\in\mathbb{Z}^{+}, Frob​(Ξ±1,…,Ξ±n):={wβˆˆβ„•:w+β„•βŠ†M​N​(Ξ±1,…,Ξ±n)}\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right)\vcentcolon=\{w\in\mathbb{N}:w+\mathbb{N}\subseteq MN(\alpha_{1},\dots,\alpha_{n})\}, we have that either Frob​(Ξ±1,…,Ξ±n)=βˆ…\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right)=\emptyset or
Frob​(Ξ±1,…,Ξ±n)=χ​(Ξ±1,…,Ξ±n)+β„•\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right)=\chi(\alpha_{1},\dots,\alpha_{n})+\mathbb{N}, where χ​(Ξ±1,…,Ξ±n)\chi(\alpha_{1},\dots,\alpha_{n}) is the least element of Frob​(Ξ±1,…,Ξ±n)\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right).

The classical Frobenius problem [3], sometimes called the β€œcoin problem,” is to evaluate χ​(Ξ±1,…,Ξ±n)\chi(\alpha_{1},\dots,\alpha_{n}) at coprime lists (Ξ±1,…,Ξ±n)(\alpha_{1},\dots,\alpha_{n}) in β„•\mathbb{N}. Frobenius used to discuss this problem in his lectures [1], so this area of number theory happens to be named after him. For n=2n=2, there is a formula: if Ξ±,Ξ²βˆˆβ„•\alpha,\beta\in\mathbb{N} and gcd⁑(Ξ±,Ξ²)=1\gcd(\alpha,\beta)=1, then χ​(Ξ±,Ξ²)=(Ξ±βˆ’1)​(Ξ²βˆ’1)\chi(\alpha,\beta)=(\alpha-1)(\beta-1). For n>2n>2 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 β„€\mathbb{Z}.

All of our rings will contain a multiplicative identity, 1, and most will be commutative. An additive monoid in a ring RR, is a subset of RR that is closed under addition and contains the identity 0; monoids, unlike groups, do not have to contain inverses. A Frobenius template in a ring RR is a triple (A,C,U)(A,C,U) such that:

  1. (i)

    AA is a nonempty subset of RR,

  2. (ii)

    CC and UU are additive monoids in RR, and

  3. (iii)

    for all lists (Ξ±1,…,Ξ±n)(\alpha_{1},\dots,\alpha_{n}) in AA,
    M​N​(Ξ±1,…,Ξ±n)={βˆ‘i=1nΞ»i​αi:Ξ»1,…,Ξ»n∈C}MN(\alpha_{1},\dots,\alpha_{n})=\{\sum_{i=1}^{n}\lambda_{i}\alpha_{i}:\lambda_{1},\dots,\lambda_{n}\in C\} is a subset of UU.

For any valid template, the properties above guarantee that M​N​(Ξ±1,…,Ξ±n)MN(\alpha_{1},\dots,\alpha_{n}) will also be an additive monoid in RR. The Frobenius set of a list Ξ±1,…,Ξ±n∈A\alpha_{1},\dots,\alpha_{n}\in A is Frob​(Ξ±1,…,Ξ±n):={w∈R:w+UβŠ†M​N​(Ξ±1,…,Ξ±n)}\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right)\vcentcolon=\left\{w\in R:w+U\subseteq MN(\alpha_{1},\dots,\alpha_{n})\right\}. Notice that w∈Frob​(Ξ±1,…,Ξ±n)w\in\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right) implies that w∈M​N​(Ξ±1,…,Ξ±n)w\in MN(\alpha_{1},\dots,\alpha_{n}) since 0∈U0\in U, so Frob​(Ξ±1,…,Ξ±n)βŠ†M​N​(Ξ±1,…,Ξ±n)βŠ†U\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right)\subseteq MN(\alpha_{1},\dots,\alpha_{n})\subseteq U. Notice also that the assumption that UU is closed under addition guarantees that if w∈Frob​(Ξ±1,…,Ξ±n)w\in\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right), then w+UβŠ†Frob​(Ξ±1,…,Ξ±n)w+U\subseteq\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right).

For a given template (A,C,U)(A,C,U), the corresponding Frobenius problem is the following pair of tasks:

  1. 1.

    Determine for which lists Ξ±1,…,Ξ±n∈A\alpha_{1},\dots,\alpha_{n}\in A it is true that Frob​(Ξ±1,…,Ξ±n)β‰ βˆ…\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right)\neq\emptyset.

  2. 2.

    For lists Ξ±1,…,Ξ±n\alpha_{1},\dots,\alpha_{n} such that Frob​(Ξ±1,…,Ξ±n)β‰ βˆ…\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right)\neq\emptyset, describe the set Frob​(Ξ±1,…,Ξ±n)\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right).

Note that in all the Frobenius templates that have been studied so far, it has always been the case that Frob​(Ξ±1,…,Ξ±n)\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right), when nonempty, is a finite union of sets of the form w+Uw+U for some w∈Rw\in R.

The classical Frobenius problem revolves around the template (β„•,β„•,β„•)(\mathbb{N},\mathbb{N},\mathbb{N}) in the ring β„€\mathbb{Z}. As discussed earlier, if n=2n=2 and Ξ±1,Ξ±2βˆˆβ„•\alpha_{1},\alpha_{2}\in\mathbb{N}, then Frob​(Ξ±1,Ξ±2)\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right) is nonempty if (and only if) Ξ±1,Ξ±2\alpha_{1},\alpha_{2} are coprime, and Frob​(Ξ±1,Ξ±2)=χ​(Ξ±1,Ξ±2)+β„•=(Ξ±1βˆ’1)​(Ξ±2βˆ’1)+β„•\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right)=\chi(\alpha_{1},\alpha_{2})+\mathbb{N}=(\alpha_{1}-1)(\alpha_{2}-1)+\mathbb{N} in such cases. So the classical Frobenius problem has been completely solved when n=2n=2.

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, U=U​(Ξ±1,…,Ξ±n)U=U(\alpha_{1},\dots,\alpha_{n}) is allowed to vary with the list Ξ±1,…,Ξ±n\alpha_{1},\dots,\alpha_{n}. This is absolutely necessary in order to get interesting and nontrivial results when the ring involved is a subring of β„‚\mathbb{C}, the complex numbers, that is not contained in ℝ\mathbb{R}, the real numbers. The ring of Gaussian integers, ℀​[i]={a+b​i:a,bβˆˆβ„€}\mathbb{Z}[i]=\{a+bi:a,b\in\mathbb{Z}\}, is such a ring, a particularly famous member of the family of rings {℀​[m​i]:mβˆˆβ„€+}\{\mathbb{Z}[\sqrt{m}i]:m\in\mathbb{Z}^{+}\}.

To see why we must let the element UU of a Frobenius template in such a ring depend on the list Ξ±1,…,Ξ±n∈A\alpha_{1},\dots,\alpha_{n}\in A, here is an example in ℀​[3​i]\mathbb{Z}[\sqrt{3}i]. Suppose C={a+b​3​i:a,bβˆˆβ„•}={r​eiβ€‹ΞΈβˆˆβ„€β€‹[3​i]:0≀r​ and ​0≀θ≀π2}C=\{a+b\sqrt{3}i:a,b\in\mathbb{N}\}=\left\{re^{i\theta}\in\mathbb{Z}[\sqrt{3}i]:0\leq r\text{ and }0\leq\theta\leq\frac{\pi}{2}\right\} and A=Cβˆ–{0}A=C\setminus\{0\}. Then consider Ξ±=2​ei​π3=1+3​i∈A\alpha=2e^{i\frac{\pi}{3}}=1+\sqrt{3}i\in A and Ξ²=1∈A\beta=1\in A. What should UU be for this list? We set U​(Ξ±,Ξ²)={r​eiβ€‹ΞΈβˆˆβ„€β€‹[3​i]:0≀r​ and ​0≀θ≀5​π6}U(\alpha,\beta)=\{re^{i\theta}\in\mathbb{Z}[\sqrt{3}i]:0\leq r\text{ and }0\leq\theta\leq\frac{5\pi}{6}\}, an angular sector in ℀​[3​i]\mathbb{Z}[\sqrt{3}i]. We so choose U​(Ξ±,Ξ²)U(\alpha,\beta) because M​N​(Ξ±,Ξ²)={Ξ»1​(2​ei​π3)+Ξ»2:Ξ»1,Ξ»2∈C}βŠ†U​(Ξ±,Ξ²)MN(\alpha,\beta)=\left\{\lambda_{1}(2e^{i\frac{\pi}{3}})+\lambda_{2}:\lambda_{1},\lambda_{2}\in C\right\}\subseteq U(\alpha,\beta), and no angular sector in ℀​[3​i]\mathbb{Z}[\sqrt{3}i] properly contained in U​(Ξ±,Ξ²)U(\alpha,\beta) contains M​N​(Ξ±,Ξ²)MN(\alpha,\beta). Further, if U^\hat{U} is an additive monoid in ℀​[3​i]\mathbb{Z}[\sqrt{3}i] which properly contains U​(Ξ±,Ξ²)U(\alpha,\beta), then no translate w+U^w+\hat{U}, wβˆˆβ„‚w\in\mathbb{C}, is contained in M​N​(Ξ±,Ξ²)MN(\alpha,\beta). Thus U​(Ξ±,Ξ²)U(\alpha,\beta) is the only possible additive monoid in ℀​[3​i]\mathbb{Z}[\sqrt{3}i] containing M​N​(Ξ±,Ξ²)MN(\alpha,\beta) such that Frob​(Ξ±,Ξ²)={w:w+U​(Ξ±,Ξ²)βŠ†M​N​(Ξ±,Ξ²)}\textnormal{Frob}\left(\alpha,\beta\right)=\{w:w+U(\alpha,\beta)\subseteq MN(\alpha,\beta)\} 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 UU vary with the list Ξ±1,…,Ξ±n∈AβŠ†β„€β€‹[m​i]\alpha_{1},\dots,\alpha_{n}\in A\subseteq\mathbb{Z}[\sqrt{m}i] in the formulation of Frobenius problems in ℀​[m​i]\mathbb{Z}[\sqrt{m}i] 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 ℀​[m]\mathbb{Z}[\sqrt{m}] with mβˆˆβ„€+βˆ–{n2:nβˆˆβ„€+}m\in\mathbb{Z}^{+}\setminus\{n^{2}:n\in\mathbb{Z}^{+}\}. 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 2Γ—22\times 2 (upper) triangular matrices with constant diagonal and entries from a ring QQ, where different choices of QQ 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, RR will be a ring with multiplicative identity 1. A list (Ξ±1,…,Ξ±n)(\alpha_{1},\dots,\alpha_{n}) in RR spans unity in RR if and only if 1=Ξ»1​α1+…+Ξ»n​αn1=\lambda_{1}\alpha_{1}+...+\lambda_{n}\alpha_{n} for some Ξ»1,…,Ξ»n∈R\lambda_{1},\dots,\lambda_{n}\in R.

Proposition 2.1.

Let (A,C,U)(A,C,U) be a Frobenius template in RR such that 1∈U1\in U. If (Ξ±1,…,Ξ±n)(\alpha_{1},\dots,\alpha_{n}) is a list in AA such that Frob​(Ξ±1,…,Ξ±n)β‰ βˆ…\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right)\neq\emptyset, then (Ξ±1,…,Ξ±n)(\alpha_{1},\dots,\alpha_{n}) spans unity in RR.

Proof.

Let w∈Frob​(Ξ±1,…,Ξ±n)w\in\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right), i.e. w∈Rw\in R and w+UβŠ†M​N​(Ξ±1,…,Ξ±n)w+U\subseteq MN(\alpha_{1},\dots,\alpha_{n}). Since 0∈U0\in U and 1∈U1\in U, it follows that w,w+1∈M​N​(Ξ±1,…,Ξ±n)w,w+1\in MN(\alpha_{1},\dots,\alpha_{n}). Therefore, for some Ξ»1,…,Ξ»,Ξ³1,…,Ξ³n∈C\lambda_{1},\dots,\lambda,\gamma_{1},\dots,\gamma_{n}\in C, w=βˆ‘i=1nΞ»i​αiw=\sum_{i=1}^{n}\lambda_{i}\alpha_{i} and w+1=βˆ‘i=1nΞ³i​αiw+1=\sum_{i=1}^{n}\gamma_{i}\alpha_{i}, so 1=βˆ‘i=1n(Ξ³iβˆ’Ξ»i)​αi1=\sum_{i=1}^{n}(\gamma_{i}-\lambda_{i})\alpha_{i}. ∎

As a warm-up, here are some valid Frobenius templates (A,C,U)(A,C,U) with, in most cases, trivial solutions to the corresponding Frobenius problems. In each example, (Ξ±1,…,Ξ±n)(\alpha_{1},\dots,\alpha_{n}) denotes a list in AA. Check that AA is nonempty, CC and UU are additive monoids in RR, and UU always contains M​N​(Ξ±1,…,Ξ±n)MN(\alpha_{1},\dots,\alpha_{n}).

  1. 1.

    In the template (R,{0},{0})(R,\left\{0\right\},\left\{0\right\}), we have M​N​(Ξ±1,…,Ξ±n)={0}MN(\alpha_{1},\dots,\alpha_{n})=\left\{0\right\} and
    Frob​(Ξ±1,…,Ξ±n)={0}\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right)=\left\{0\right\}. This result extends to any template (A,C,U)(A,C,U) with C=U={0}C=U=\left\{0\right\}.

  2. 2.

    Similar to example 1, templates of the form ({0},C,{0})(\left\{0\right\},C,\left\{0\right\}) always have M​N​(0)={0}MN(0)=\left\{0\right\} and Frob​(0)={0}\textnormal{Frob}\left(0\right)=\left\{0\right\}.

  3. 3.

    In the template (R,R,R)(R,R,R), Proposition 2.1 shows that (Ξ±1,…,Ξ±n)(\alpha_{1},\dots,\alpha_{n}) spans unity in RR if Frob​(Ξ±1,…,Ξ±n)β‰ βˆ…\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right)\neq\emptyset. Conversely, if (Ξ±1,…,Ξ±n)(\alpha_{1},\dots,\alpha_{n}) spans unity, then Frob​(Ξ±1,…,Ξ±n)=R\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right)=R.

  4. 4.

    Suppose that II is an ideal of RR and the template is ({1},I,I)(\{1\},I,I). Clearly M​N​(1)=I=UMN(1)=I=U, so UβŠ†Frob​(1)U\subseteq\textnormal{Frob}\left(1\right). Recall that Frob​(Ξ±1,…,Ξ±n)\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right) is a subset of M​N​(Ξ±1,…,Ξ±n)MN(\alpha_{1},\dots,\alpha_{n}); thus Frob​(1)=U\textnormal{Frob}\left(1\right)=U.

  5. 5.

    Again, let II be an ideal of RR, and now consider the template (I,R,I)(I,R,I). When I=RI=R, this is example 3. In contrast, let II be a proper ideal. Then no list (Ξ±1,…,Ξ±n)(\alpha_{1},\dots,\alpha_{n}) spans unity in RR β€” but this is precisely because 1βˆ‰I1\notin I, 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 (2​℀,β„€,2​℀)(2\mathbb{Z},\mathbb{Z},2\mathbb{Z}) in β„€\mathbb{Z}, where 2​℀2\mathbb{Z} is the ideal of even integers, it is straightforward to prove that Frob​(Ξ±1,…,Ξ±n)β‰ βˆ…\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right)\neq\emptyset if and only if the integers |Ξ±12|,…,|Ξ±n2|\absolutevalue{\frac{\alpha_{1}}{2}},\dots,\absolutevalue{\frac{\alpha_{n}}{2}} are coprime. In this case, M​N​(Ξ±1,…,Ξ±n)=2​℀MN(\alpha_{1},\dots,\alpha_{n})=2\mathbb{Z} and Frob​(Ξ±1,…,Ξ±n)=2​Frob′​(Ξ±12,…,Ξ±n2)\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right)=2\text{Frob}^{\prime}\left(\frac{\alpha_{1}}{2},\dots,\frac{\alpha_{n}}{2}\right), where Frobβ€²\text{Frob}^{\prime} denotes Frobenius sets with respect to the classical template (β„•,β„•,β„•)(\mathbb{N},\mathbb{N},\mathbb{N}).

  6. 6.

    If the template is ((0,∞),[0,∞),[0,∞))((0,\infty),[0,\infty),[0,\infty)) in ℝ\mathbb{R}, then M​N​(Ξ±1,…,Ξ±n)=[0,∞)=Frob​(Ξ±1,…,Ξ±n)MN(\alpha_{1},\dots,\alpha_{n})=[0,\infty)=\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right) for every list (Ξ±1,…,Ξ±n)(\alpha_{1},\dots,\alpha_{n}). On the other hand, if we restrict the coefficients to the set of rational numbers β„š\mathbb{Q} with the template ((0,∞),β„šβˆ©[0,∞),[0,∞))((0,\infty),\mathbb{Q}\cap[0,\infty),[0,\infty)) in ℝ\mathbb{R}, then Frob​(Ξ±1,…,Ξ±n)\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right) is always empty, as M​N​(Ξ±1,…,Ξ±n)MN(\alpha_{1},\dots,\alpha_{n}) is countable and any translate of [0,∞)[0,\infty) is uncountable.

  7. 7.

    Suppose that R1R_{1} and R2R_{2} are rings with associated Frobenius templates (A1,C1,U1)(A_{1},C_{1},U_{1}) and (A2,C2,U2)(A_{2},C_{2},U_{2}), respectively. Let A1Γ—A2A_{1}\times A_{2} be the Cartesian product of A1A_{1} and A2A_{2}. The same goes for C1Γ—C2C_{1}\times C_{2} and U1Γ—U2U_{1}\times U_{2}, which are additive monoids (under componentwise addition) in the product ring R1Γ—R2R_{1}\times R_{2}. It is simple to see that (A1Γ—A2,C1Γ—C2,U1Γ—U2)(A_{1}\times A_{2},C_{1}\times C_{2},U_{1}\times U_{2}) is a valid Frobenius template in R1Γ—R2R_{1}\times R_{2}. Let (Ξ²1,…,Ξ²n)(\beta_{1},\dots,\beta_{n}) be a list in A1Γ—A2A_{1}\times A_{2} with each Ξ²i=(Ξ³i,ΞΌi)\beta_{i}=(\gamma_{i},\mu_{i}) for i=1,…,ni=1,\dots,n. If Frob​(Ξ²1,…,Ξ²n)β‰ βˆ…\textnormal{Frob}\left(\beta_{1},\dots,\beta_{n}\right)\neq\emptyset in (A1Γ—A2,C1Γ—C2,U1Γ—U2)(A_{1}\times A_{2},C_{1}\times C_{2},U_{1}\times U_{2}), then
    Frob​(Ξ²1,…,Ξ²n)=Frob1​(Ξ³1,…,Ξ³n)Γ—Frob2​(ΞΌ,…,ΞΌ2)\textnormal{Frob}\left(\beta_{1},\dots,\beta_{n}\right)=\textnormal{Frob}_{1}(\gamma_{1},\dots,\gamma_{n})\times\textnormal{Frob}_{2}(\mu,\dots,\mu_{2}), where Frob1\textnormal{Frob}_{1} and Frob2\textnormal{Frob}_{2} are Frobenius sets in (A1,C1,U1)(A_{1},C_{1},U_{1}) and (A2,C2,U2)(A_{2},C_{2},U_{2}), respectively. For mβˆˆβ„€+m\in\mathbb{Z}^{+}, this result extends to the product ring R1Γ—β‹―Γ—RmR_{1}\times\dots\times R_{m}.

Besides the Gaussian integers [4, 5], prior work on generalized Frobenius problems has concentrated on templates in the real subring ℀​[m]:={a+b​m:a,bβˆˆβ„€}\mathbb{Z}[\sqrt{m}]\vcentcolon=\{a+b\sqrt{m}:a,b\in\mathbb{Z}\}, where mβˆˆβ„€+m\in\mathbb{Z}^{+} is not a perfect square. Below, we showcase some highlights from this work. If mm is a positive integer with irrational square root, then ℀​[m]\mathbb{Z}[\sqrt{m}] is a subring of ℝ\mathbb{R}. Let ℕ​[m]:={a+b​m:a,bβˆˆβ„•}\mathbb{N}[\sqrt{m}]\vcentcolon=\{a+b\sqrt{m}:a,b\in\mathbb{N}\} and ℀​[m]+:=℀​[m]∩[0,∞)\mathbb{Z}[\sqrt{m}]^{+}\vcentcolon=\mathbb{Z}[\sqrt{m}]\cap[0,\infty), which are both additive monoids in ℀​[m]\mathbb{Z}[\sqrt{m}] that contain 11.

  1. 1.

    In the template (ℕ​[m],ℕ​[m],ℕ​[m])(\mathbb{N}[\sqrt{m}],\mathbb{N}[\sqrt{m}],\mathbb{N}[\sqrt{m}]), the result below is proven in [6]:

    Theorem 2.1.

    If Ξ±1,…,Ξ±nβˆˆβ„•β€‹[m]\alpha_{1},\dots,\alpha_{n}\in\mathbb{N}[\sqrt{m}], Ξ±i=ai+bi​m\alpha_{i}=a_{i}+b_{i}\sqrt{m}, ai,biβˆˆβ„•a_{i},b_{i}\in\mathbb{N}, i=1,…,ni=1,\dots,n, then Frob​(Ξ±1,…,Ξ±n)β‰ βˆ…\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right)\neq\emptyset if and only if (Ξ±1,…,Ξ±n)(\alpha_{1},\dots,\alpha_{n}) spans unity in ℀​[m]\mathbb{Z}[\sqrt{m}] and at least one of a1,…,ana_{1},\dots,a_{n}, b1,…,bnb_{1},\dots,b_{n} is zero.

    The result stated in [6], Theorem 3, is slightly weaker than the formulation above, but needlessly so, since the proof in [6] proves the statement given here.

  2. 2.

    In the template (℀​[m]+,℀​[m]+,℀​[m]+)(\mathbb{Z}[\sqrt{m}]^{+},\mathbb{Z}[\sqrt{m}]^{+},\mathbb{Z}[\sqrt{m}]^{+}), the following is nearly proven in [2]:

    Theorem 2.2.

    If Ξ±1,…,Ξ±nβˆˆβ„€β€‹[m]+\alpha_{1},\dots,\alpha_{n}\in\mathbb{Z}[\sqrt{m}]^{+}, then the following are equivalent:

    1. (i)

      Frob​(Ξ±1,…,Ξ±n)β‰ βˆ…\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right)\neq\emptyset;

    2. (ii)

      Frob​(Ξ±1,…,Ξ±n)=℀​[m]+\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right)=\mathbb{Z}[\sqrt{m}]^{+};

    3. (iii)

      (Ξ±1,…,Ξ±n)(\alpha_{1},\dots,\alpha_{n}) spans unity in ℀​[m]\mathbb{Z}[\sqrt{m}].

    Since Theorem 2 of [2] proves (i​i​i)⟹(i​i)(iii)\implies(ii), 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 (ℕ​[m],ℕ​[m],ℕ​[m])(\mathbb{N}[\sqrt{m}],\mathbb{N}[\sqrt{m}],\mathbb{N}[\sqrt{m}]),
    Frob​(Ξ±1,…,Ξ±n)\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right) is determined in a very special class of cases. Recall that for coprime positive integers c1,…,cnc_{1},\dots,c_{n}, χ​(c1,…,cn)\chi\left(c_{1},\dots,c_{n}\right) is the smallest wβˆˆβ„€+w\in\mathbb{Z}^{+} such that w+β„•βŠ†{βˆ‘i=1nΞ»i​ci:Ξ»1,…,Ξ»nβˆˆβ„•}w+\mathbb{N}\subseteq\left\{\sum_{i=1}^{n}\lambda_{i}c_{i}:\lambda_{1},\dots,\lambda_{n}\in\mathbb{N}\right\}.

    Theorem 2.3.

    For a1,…,ar,b1,…,bsβˆˆβ„•a_{1},\dots,a_{r},b_{1},\dots,b_{s}\in\mathbb{N},
    (a1,…,ar,b1​m,…,bs​m)(a_{1},\dots,a_{r},b_{1}\sqrt{m},\dots,b_{s}\sqrt{m}) is a list in ℕ​[m]\mathbb{N}[\sqrt{m}]. We have

    Frob​(a1,…,ar,b1​m,…,bs​m)β‰ βˆ…β‡”a1,…,ar,b1​m,…,bs​m​ are coprime,\begin{split}&\textnormal{Frob}\left(a_{1},\dots,a_{r},b_{1}\sqrt{m},\dots,b_{s}\sqrt{m}\right)\neq\emptyset\\ &\iff a_{1},\dots,a_{r},b_{1}m,\dots,b_{s}m\text{ are coprime,}\end{split}

    and, in such cases,

    Frob​(a1,…,ar,b1​m,…,bs​m)=χ​(a1,…,ar,b1​m,…,bs​m)+χ​(a1,…,ar,b1,…,bs)​m+ℕ​[m]​.\begin{split}&\textnormal{Frob}\left(a_{1},\dots,a_{r},b_{1}\sqrt{m},\dots,b_{s}\sqrt{m}\right)\\ &=\chi(a_{1},\dots,a_{r},b_{1}m,\dots,b_{s}m)+\chi(a_{1},\dots,a_{r},b_{1},\dots,b_{s})\sqrt{m}+\mathbb{N}[\sqrt{m}]\text{.}\end{split}

    Note that the case s=0s=0 is allowed in this result. Also, if the integers a1,…,ar,b1​m,…,bs​ma_{1},\dots,a_{r},b_{1}m,\dots,b_{s}m are coprime, then so are a1,…,ar,b1,…,bsa_{1},\dots,a_{r},b_{1},\dots,b_{s}, so the second part of Theorem 2.3 uses well-defined expressions.

  3. 3.

    With χ​(a1,…,an)\chi(a_{1},\dots,a_{n}) as above, recall that in the n=2n=2 case of the classical template (β„•,β„•,β„•)(\mathbb{N},\mathbb{N},\mathbb{N}) in β„€\mathbb{Z}, χ​(a1,a2)=(a1βˆ’1)​(a2βˆ’1)\chi(a_{1},a_{2})=(a_{1}-1)(a_{2}-1) for coprime a1,a2a_{1},a_{2}. In a tour de force in [7], Kim proves a similar formula for the template (ℕ​[m],ℕ​[m],ℕ​[m])(\mathbb{N}[\sqrt{m}],\mathbb{N}[\sqrt{m}],\mathbb{N}[\sqrt{m}]) in ℀​[m]\mathbb{Z}[\sqrt{m}]:

    Theorem 2.4.

    Suppose Ξ±=a+b​m,Ξ²=c+d​m\alpha=a+b\sqrt{m},\beta=c+d\sqrt{m}, a,b,c,dβˆˆβ„•a,b,c,d\in\mathbb{N}, a+b,c+d>0a+b,c+d>0, a​b​c​d=0abcd=0 (see Theorem 2.1, above), and suppose that Ξ±,Ξ²\alpha,\beta span unity in ℀​[m]\mathbb{Z}[\sqrt{m}]. Then Frob​(Ξ±,Ξ²)=(Ξ±βˆ’1)​(Ξ²βˆ’1)​(1+m)+ℕ​[m]\textnormal{Frob}\left(\alpha,\beta\right)=(\alpha-1)(\beta-1)(1+\sqrt{m})+\mathbb{N}[\sqrt{m}].

What’s next? We propose these categories of rings where one might discover results of interest of the Frobenius type.

  1. 1.

    Subrings of algebraic extensions of β„š\mathbb{Q}.

    Prior work on the Gaussian integers and the rings ℀​[m]\mathbb{Z}[\sqrt{m}] has put us into the foothills of a mountain range in this area. Besides the extensions of β„š\mathbb{Q} of finite degree, what about the ring of algebraic integers? Or, a better choice to start with, the ring of real algebraic integers?

  2. 2.

    Polynomial rings.

    Somebody we know is working on this, but we haven’t heard from him for a year or so.

  3. 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
    M​N​(Ξ±1,…,Ξ±n)MN(\alpha_{1},\dots,\alpha_{n}) becomes important, since for Ξ±1,…,Ξ±n\alpha_{1},\dots,\alpha_{n} from AA and Ξ»1,…,Ξ»n\lambda_{1},\dots,\lambda_{n} from CC, the linear combinations βˆ‘i=1nΞ»i​αi\sum_{i=1}^{n}\lambda_{i}\alpha_{i} and βˆ‘i=1nΞ±i​λi\sum_{i=1}^{n}\alpha_{i}\lambda_{i} are not necessarily equal.

3 Modifying the classical template

The classical template (β„•,β„•,β„•)(\mathbb{N},\mathbb{N},\mathbb{N}) uses nonnegative integer coefficients. What happens when we modify the available coefficients? Consider the template (β„•,(n+β„•)βˆͺ{0},β„•)(\mathbb{N},(n+\mathbb{N})\cup\left\{0\right\},\mathbb{N}) for some nβˆˆβ„€+n\in\mathbb{Z}^{+}. When n=1n=1, this is the classical template.

Remember that when a1,…,akβˆˆβ„•a_{1},\dots,a_{k}\in\mathbb{N} are coprime, χ​(a1,…,ak)\chi\left(a_{1},\dots,a_{k}\right) is the unique integer such that Frob​(a1​…,ak)=χ​(a1,…,ak)+β„•\textnormal{Frob}\left(a_{1}\dots,a_{k}\right)=\chi\left(a_{1},\dots,a_{k}\right)+\mathbb{N} with respect to the classical template. In the results that follow, χ​(a1,…,ak)\chi\left(a_{1},\dots,a_{k}\right) retains this meaning, whereas Frob and M​NMN reference the modified template (β„•,(n+β„•)βˆͺ{0},β„•)(\mathbb{N},(n+\mathbb{N})\cup\left\{0\right\},\mathbb{N}).

Proposition 3.1.

If a1,…,akβˆˆβ„•a_{1},\dots,a_{k}\in\mathbb{N} are coprime, then

(a1+β‹―+ak)​n+χ​(a1,…,ak)+β„•βŠ†Frob​(a1,…,ak)​.(a_{1}+\dots+a_{k})n+\chi\left(a_{1},\dots,a_{k}\right)+\mathbb{N}\subseteq\textnormal{Frob}\left(a_{1},\dots,a_{k}\right)\text{.}
Proof.

Suppose Ο‰βˆˆβ„•\omega\in\mathbb{N} and Ο‰β‰₯(a1+β‹―+ak)​n+χ​(a1,…,ak)\omega\geq(a_{1}+\dots+a_{k})n+\chi\left(a_{1},\dots,a_{k}\right). We will show Ο‰βˆˆFrob​(a1,…,ak)\omega\in\textnormal{Frob}\left(a_{1},\dots,a_{k}\right), i.e.

Ο‰+β„•βŠ†M​N​(a1,…,ak)={βˆ‘i=1kΞ»i​ai:Ξ»1,…,Ξ»k∈(n+β„•)βˆͺ{0}}​.\omega+\mathbb{N}\subseteq MN(a_{1},\dots,a_{k})=\left\{\sum_{i=1}^{k}\lambda_{i}a_{i}:\lambda_{1},\dots,\lambda_{k}\in(n+\mathbb{N})\cup\left\{0\right\}\right\}\text{.}

Suppose fβˆˆβ„•f\in\mathbb{N}, fβ‰₯Ο‰f\geq\omega. It suffices to show that f∈M​N​(a1,…,ak)f\in MN(a_{1},\dots,a_{k}). Since fβ‰₯Ο‰f\geq\omega, we have that fβˆ’(a1+β‹―+ak)​nβ‰₯χ​(a1,…,ak)f-(a_{1}+\dots+a_{k})n\geq\chi\left(a_{1},\dots,a_{k}\right), so there exist coefficients Ξ³1,…,Ξ³kβˆˆβ„•\gamma_{1},\dots,\gamma_{k}\in\mathbb{N} such that f=(a1+β‹―+ak)​n+βˆ‘i=1kΞ³i​ai=βˆ‘i=1k(Ξ³i+n)​aif=(a_{1}+\dots+a_{k})n+\sum_{i=1}^{k}\gamma_{i}a_{i}=\sum_{i=1}^{k}(\gamma_{i}+n)a_{i}. Taking Ξ»i=Ξ³i+nβ‰₯n\lambda_{i}=\gamma_{i}+n\geq n for i=1,…,ki=1,\dots,k yields the desired result. ∎

While reading the next proof, remember that χ​(a,b)=(aβˆ’1)​(bβˆ’1)\chi\left(a,b\right)=(a-1)(b-1) for coprime a,bβˆˆβ„•a,b\in\mathbb{N}, so χ​(a,b)βˆ’1=a​bβˆ’aβˆ’b\chi\left(a,b\right)-1=ab-a-b.

Proposition 3.2.

Let a,bβˆˆβ„•a,b\in\mathbb{N} and nβˆˆβ„€+n\in\mathbb{Z}^{+}. If a,ba,b are coprime and nβˆ’1n-1 is not divisible by aa or bb, then Frob​(a,b)=(a+b)​n+χ​(a,b)+β„•\textnormal{Frob}\left(a,b\right)=(a+b)n+\chi\left(a,b\right)+\mathbb{N}.

Proof.

By the preceding proposition, it suffices to show that Frob​(a,b)βŠ†(a+b)​n+χ​(a,b)+β„•\textnormal{Frob}\left(a,b\right)\subseteq(a+b)n+\chi\left(a,b\right)+\mathbb{N}. So let tβˆˆβ„•βˆ–((a+b)​n+χ​(a,b)+β„•)t\in\mathbb{N}\setminus\left((a+b)n+\chi\left(a,b\right)+\mathbb{N}\right), and suppose that t∈Frob​(a,b)t\in\textnormal{Frob}\left(a,b\right). We will find a contradiction, which will complete the proof.

Since t∈Frob​(a,b)t\in\textnormal{Frob}\left(a,b\right), we have t+β„•βŠ†M​N​(a,b)t+\mathbb{N}\subseteq MN(a,b), so a​n+b​n+χ​(a,b)βˆ’1β‰₯tan+bn+\chi\left(a,b\right)-1\geq t is an element of M​N​(a,b)MN(a,b), so there exist Ξ»1,Ξ»2∈(n+β„•)βˆͺ{0}\lambda_{1},\lambda_{2}\in(n+\mathbb{N})\cup\left\{0\right\} such that

χ​(a,b)βˆ’1=Ξ»1​a+Ξ»2​bβˆ’a​nβˆ’b​n=(Ξ»1βˆ’n)​a+(Ξ»2βˆ’n)​b​.\chi\left(a,b\right)-1=\lambda_{1}a+\lambda_{2}b-an-bn=(\lambda_{1}-n)a+(\lambda_{2}-n)b\text{.}

Now, if both Ξ»1\lambda_{1} and Ξ»2\lambda_{2} are β‰₯n\geq n, then χ​(a,b)βˆ’1\chi\left(a,b\right)-1 equals a linear combination of aa and bb with nonnegative integer coefficients, which is impossible. We also cannot have Ξ»1=0=Ξ»2\lambda_{1}=0=\lambda_{2} since χ​(a,b)+a​n+b​n>1\chi\left(a,b\right)+an+bn>1. So consider the case that Ξ»1=0\lambda_{1}=0 and Ξ»2β‰₯n\lambda_{2}\geq n. In that case, (Ξ»2βˆ’n)​b=χ​(a,b)βˆ’1+a​n=a​bβˆ’b+a​(nβˆ’1)(\lambda_{2}-n)b=\chi\left(a,b\right)-1+an=ab-b+a(n-1), so (Ξ»2βˆ’nβˆ’a+1)​b=a​(nβˆ’1)(\lambda_{2}-n-a+1)b=a(n-1), so bb divides a​(nβˆ’1)a(n-1). But aa and bb are coprime, so this implies that bb divides nβˆ’1n-1, which we have assumed to be false. Similarly Ξ»1β‰₯n\lambda_{1}\geq n and Ξ»2=0\lambda_{2}=0 would imply that (Ξ»1βˆ’n)​a=χ​(a,b)βˆ’1+b​n=a​bβˆ’a+b​(nβˆ’1)(\lambda_{1}-n)a=\chi\left(a,b\right)-1+bn=ab-a+b(n-1), yielding the contradiction that aa divides nβˆ’1n-1. Thus, all cases yield a contradiction, so our supposition that t∈Frob​(a,b)t\in\textnormal{Frob}\left(a,b\right) must be false. ∎

4 πŸΓ—πŸ\mathbf{2\times 2} triangular matrices with constant diagonal

For a ring QQ with multiplicative identity 11, let RR be the set Q2=QΓ—QQ^{2}=Q\times Q under coordinatewise addition, with multiplication in RR defined by (a,b)β‹…(c,d)=(a​c,a​d+b​c)(a,b)\cdot(c,d)=(ac,ad+bc). RR is a ring with multiplicative identity (1,0)(1,0), isomorphic to the ring of upper triangular 2Γ—22\times 2 matrices over QQ with constant diagonal: (a,b)∼[ab0a](a,b)\sim\begin{bmatrix}a&b\\ 0&a\end{bmatrix}. If QQ is commutative, then RR is commutative.

We will concentrate on the cases when QQ is a subring of the real field ℝ\mathbb{R} containing 11, and the Frobenius template is

(A​(Q),C​(Q),U​(Q))=((Q∩(0,∞))Γ—(Q∩[0,∞)),(Q∩[0,∞))2,(Q∩[0,∞))2).\begin{split}&\left(A(Q),C(Q),U(Q)\right)\\ &=\left(\left(Q\cap(0,\infty)\right)\times\left(Q\cap[0,\infty)\right),\left(Q\cap[0,\infty)\right)^{2},\left(Q\cap[0,\infty)\right)^{2}\right).\end{split}
Proposition 4.1.

Let QQ be a subring of ℝ\mathbb{R} containing 11. For any positive integer nn, let (Ξ±1,…,Ξ±n)(\alpha_{1},\dots,\alpha_{n}) be a list in A​(Q)βˆ–(QΓ—{0})A(Q)\setminus\left(Q\times\left\{0\right\}\right). Then Frob​(Ξ±1,…,Ξ±n)=βˆ…\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right)=\emptyset.

Proof.

Let Ξ±i=(ai,bi)\alpha_{i}=(a_{i},b_{i}), i=1,…,ni=1,\dots,n. Elements of M​N​(Ξ±1,…,Ξ±n)MN(\alpha_{1},\dots,\alpha_{n}) look like

(t,u)=βˆ‘i=1n(ai,bi)β‹…(ci,di)=βˆ‘i=1n(ai​ci,ai​di+bi​ci)=(βˆ‘i=1nai​ci,βˆ‘i=1n(ai​di+bi​ci)),\begin{split}(t,u)&=\sum_{i=1}^{n}(a_{i},b_{i})\cdot(c_{i},d_{i})\\ &=\sum_{i=1}^{n}(a_{i}c_{i},a_{i}d_{i}+b_{i}c_{i})\\ &=\left(\sum_{i=1}^{n}a_{i}c_{i},\sum_{i=1}^{n}\left(a_{i}d_{i}+b_{i}c_{i}\right)\right),\end{split}

where ciβ‰₯0c_{i}\geq 0 and diβ‰₯0d_{i}\geq 0 for all i=1,…,ni=1,\dots,n.

Suppose that Frob​(Ξ±1,…,Ξ±n)\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right) is nonempty, so there is a tuple (t,u)∈Q2(t,u)\in Q^{2} such that (t,u)+(Q∩[0,∞))2βŠ†M​N​(Ξ±1,…,Ξ±n)(t,u)+(Q\cap[0,\infty))^{2}\subseteq MN(\alpha_{1},\dots,\alpha_{n}). Therefore, for all qβ‰₯0q\geq 0, we have (t,u)+(q,0)=(t+q,u)∈M​N​(Ξ±1,…,Ξ±n)(t,u)+(q,0)=(t+q,u)\in MN(\alpha_{1},\dots,\alpha_{n}). So for larger and larger qq, t+q=βˆ‘i=1nai​ci​(q)t+q=\sum_{i=1}^{n}a_{i}c_{i}(q) and u=βˆ‘i=1n(ai​di​(q)+bi​ci​(q))u=\sum_{i=1}^{n}(a_{i}d_{i}(q)+b_{i}c_{i}(q)) for some nonnegative integers ci​(q)c_{i}(q) and di​(q)d_{i}(q) (i=1,…,ni=1,\dots,n) that vary with qq. Clearly βˆ‘i=1nai​ci​(q)=t+qβ†’βˆž\sum_{i=1}^{n}a_{i}c_{i}(q)=t+q\to\infty as qβ†’βˆžq\to\infty. Because each fixed ai,bi>0a_{i},b_{i}>0, and each varying ci​(q),di​(q)β‰₯0c_{i}(q),d_{i}(q)\geq 0, it follows that max1≀i≀n⁑ci​(q)β†’βˆž\max_{1\leq i\leq n}c_{i}(q)\to\infty as qβ†’βˆžq\to\infty, and consequently u=βˆ‘i=1n(ai​di​(q)+bi​ci​(q))β†’βˆžu=\sum_{i=1}^{n}(a_{i}d_{i}(q)+b_{i}c_{i}(q))\to\infty as qβ†’βˆžq\to\infty. But uu is a given constant; it does not vary with qq. Therefore, our supposition must be false, so Frob​(Ξ±1,…,Ξ±n)=βˆ…\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right)=\emptyset. ∎

Moving on, we now know a sufficient condition for Frob​(Ξ±1,…,Ξ±n)=βˆ…\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right)=\emptyset in a large swath of templates. The natural question is whether Frob​(Ξ±1,…,Ξ±n)\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right) is ever nonempty, and the answer is yes.

Proposition 4.2.

Let QQ be a subfield of ℝ\mathbb{R}. For any positive integer nn, let
(Ξ±1,…,Ξ±n)(\alpha_{1},\dots,\alpha_{n}) be a sequence of 22-tuples Ξ±i=(ai,bi)∈A​(Q)\alpha_{i}=(a_{i},b_{i})\in A(Q) (for i=1,…,ni=1,\dots,n) satisfying b1=0b_{1}=0. Then Frob​(Ξ±1,…,Ξ±n)=M​N​(Ξ±1,…,Ξ±n)=U​(Q)\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right)=MN(\alpha_{1},\dots,\alpha_{n})=U(Q).

Proof.

We have

M​N​(Ξ±1,…,Ξ±n)={(βˆ‘i=1nai​ci,βˆ‘i=1nai​di+βˆ‘i=2nbi​ci):ci,di∈Q∩[0,∞)}​.MN(\alpha_{1},\dots,\alpha_{n})=\left\{\left(\sum_{i=1}^{n}a_{i}c_{i},\sum_{i=1}^{n}a_{i}d_{i}+\sum_{i=2}^{n}b_{i}c_{i}\right):c_{i},d_{i}\in Q\cap[0,\infty)\right\}\text{.}

It will suffice to show that (0,0)∈Frob​(Ξ±1,…,Ξ±n)(0,0)\in\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right). Let f,gβ‰₯0f,g\geq 0, f,g∈Qf,g\in Q, so that f,g∈(0,0)+U​(Q)f,g\in(0,0)+U(Q). Then use the coefficients c1=fa1c_{1}=\frac{f}{a_{1}}, d1=ga1d_{1}=\frac{g}{a_{1}}, and cj=dj=0c_{j}=d_{j}=0 for j=2,…,nj=2,\dots,n to show that (f,g)∈M​N​(Ξ±1,…,Ξ±n)(f,g)\in MN(\alpha_{1},\dots,\alpha_{n}), so (0,0)∈Frob​(Ξ±1,…,Ξ±n)(0,0)\in\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right). ∎

Proposition 4.1 can be generalized, mutatis mutandis, to QQ being any linearly ordered commutative ring with unity. The same holds for Proposition 4.2, with the additional stipulation that a1a_{1} is a unit. In both cases, the ordering is compatible with addition and multiplication.

In other words, setting QQ as a subfield of ℝ\mathbb{R} yields a boring Frobenius template, since we can shrink elements of ℝ\mathbb{R} using coefficients in ci,di∈Q∩(0,1)c_{i},d_{i}\in Q\cap(0,1). 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 (a,b)(a,b), the notation (a,b)+(a,b)_{+} stands for (a,b)+[0,∞)2(a,b)+[0,\infty)^{2}.

Proposition 4.3.

Let Q=ℝQ=\mathbb{R}, and change C​(ℝ)C(\mathbb{R}) to be C={(0,0)}βˆͺ[1,∞)2C=\left\{(0,0)\right\}\cup[1,\infty)^{2}. Let Ξ±1=(a1,0),Ξ±2=(a2,b2)\alpha_{1}=(a_{1},0),\alpha_{2}=(a_{2},b_{2}) form a list (Ξ±1,Ξ±2)(\alpha_{1},\alpha_{2}) of tuples in AA. If b2=0b_{2}=0, then Frob​(Ξ±1,Ξ±2)=(min⁑(a1,a2),min⁑(a1,a2))+\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right)=(\min(a_{1},a_{2}),\min(a_{1},a_{2}))_{+}. If b2>0b_{2}>0, then

Frob​(Ξ±1,Ξ±2)={(a1,a1)+a1≀a2​ and ​a1≀b2(a1,a1)+βˆͺ(a1​a2b2+a1,b2)+b2<a1≀a2(a1,a2)+βˆͺ(a2,a1​b2a2+a2)+a1>a2​ and ​a2≀b2(a1,a2)+βˆͺ(a2,a1​b2a2+a2)+βˆͺ((a2)2b2+a1,b2)+b2<a2<a1\begin{split}&\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right)=\\ &\begin{cases}(a_{1},a_{1})_{+}&a_{1}\leq a_{2}\text{ and }a_{1}\leq b_{2}\\ \left(a_{1},a_{1}\right)_{+}\cup\left(\frac{a_{1}a_{2}}{b_{2}}+a_{1},b_{2}\right)_{+}&b_{2}<a_{1}\leq a_{2}\\ \left(a_{1},a_{2}\right)_{+}\cup\left(a_{2},\frac{a_{1}b_{2}}{a_{2}}+a_{2}\right)_{+}&a_{1}>a_{2}\text{ and }a_{2}\leq b_{2}\\ \left(a_{1},a_{2}\right)_{+}\cup\left(a_{2},\frac{a_{1}b_{2}}{a_{2}}+a_{2}\right)_{+}\cup\left(\frac{(a_{2})^{2}}{b_{2}}+a_{1},b_{2}\right)_{+}&b_{2}<a_{2}<a_{1}\end{cases}\end{split}

Simple modifications to the proof of Proposition 4.1 will prove that Proposition 4.1 holds in this template. Since Frob​(Ξ±1,Ξ±2)βŠ†Frob​(Ξ±1,…,Ξ±n)\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right)\subseteq\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right), Proposition 4.3 combines with Proposition 4.1 to prove that if Ξ±i=(ai,bi)∈(0,∞)Γ—[0,∞)\alpha_{i}=(a_{i},b_{i})\in(0,\infty)\times[0,\infty) for i=1,…,ni=1,\dots,n and n>1n>1, then Frob​(Ξ±1,…,Ξ±n)\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right) is nonempty if and only if some bi=0b_{i}=0.

Proof.

Case 0: Suppose b2=0b_{2}=0, so elements of M​N​(Ξ±1,Ξ±2)MN(\alpha_{1},\alpha_{2}) look like (a1​c1+a2​c2,a1​d1+a2​d2)(a_{1}c_{1}+a_{2}c_{2},a_{1}d_{1}+a_{2}d_{2}) for c1,c2,d1,d2∈[0,∞)βˆ–(0,1)c_{1},c_{2},d_{1},d_{2}\in[0,\infty)\setminus(0,1). Notice that f∈(0,min(a1,f\in(0,\min(a_{1},
a2))a_{2})) or g∈(0,min⁑(a1,a2))g\in(0,\min(a_{1},a_{2})) implies (f,g)βˆ‰M​N​(Ξ±1,Ξ±2)(f,g)\notin MN(\alpha_{1},\alpha_{2}). Therefore, if (t,u)∈Frob​(Ξ±1,Ξ±2)(t,u)\in\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right), then t,uβ‰₯min⁑(a1,a2)t,u\geq\min(a_{1},a_{2}). The converse is trivial, so this case is done.

The set M​N​(Ξ±1,Ξ±2)MN(\alpha_{1},\alpha_{2}) is

{(a1​c1+a2​c2,a1​d1+a2​d2+b2​c2):c1,c2,d1,d2∈[0,∞)βˆ–(0,1)}​.\left\{\left(a_{1}c_{1}+a_{2}c_{2},a_{1}d_{1}+a_{2}d_{2}+b_{2}c_{2}\right):c_{1},c_{2},d_{1},d_{2}\in[0,\infty)\setminus(0,1)\right\}\text{.}

The trickiness of the remaining cases is that both coordinates share the coefficient c2c_{2}. Similar to the last paragraph, notice that f∈(0,min⁑(a1,a2))f\in(0,\min(a_{1},a_{2})) or g∈(0,min⁑(a1,a2,b2))g\in(0,\min(a_{1},a_{2},b_{2})) implies (f,g)βˆ‰M​N​(Ξ±1,Ξ±2)(f,g)\notin MN(\alpha_{1},\alpha_{2}); therefore, (t,u)∈Frob​(Ξ±1,Ξ±2)(t,u)\in\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right) implies tβ‰₯min⁑(a1,a2)t\geq\min(a_{1},a_{2}) and uβ‰₯min⁑(a1,a2,b2)u\geq\min(a_{1},a_{2},b_{2}).

Case 1: a1≀a2a_{1}\leq a_{2} and a1≀b2a_{1}\leq b_{2}. By remarks above, in this case Frob​(Ξ±1,Ξ±2)βŠ†(a1,a1)βˆͺ[0,∞)2\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right)\subseteq(a_{1},a_{1})\cup[0,\infty)^{2}. On the other hand, if f,gβ‰₯a1f,g\geq a_{1}, then (f,g)=(fa1,ga1)​α1+(0,0)​α2(f,g)=(\frac{f}{a_{1}},\frac{g}{a_{1}})\alpha_{1}+(0,0)\alpha_{2}, so (f,g)∈M​N​(Ξ±1,Ξ±2)(f,g)\in MN(\alpha_{1},\alpha_{2}). Therefore, (a1,a1)+[0,∞)2βŠ†Frob​(Ξ±1,Ξ±2)(a_{1},a_{1})+[0,\infty)^{2}\subseteq\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right), so Frob​(Ξ±1,Ξ±2)=(a1,a1)+[0,∞)2\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right)=(a_{1},a_{1})+[0,\infty)^{2}.

Case 2: 0<b2<a1≀a20<b_{2}<a_{1}\leq a_{2}. Then Frob​(Ξ±1,Ξ±2)βŠ†(a1,b2)+[0,∞)2\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right)\subseteq(a_{1},b_{2})+[0,\infty)^{2} and, by the proof in Case 1,

(a1,a1)+[0,∞)2=[a1,∞)2βŠ†Frob​(Ξ±1,Ξ±2)​.(a_{1},a_{1})+[0,\infty)^{2}=[a_{1},\infty)^{2}\subseteq\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right)\text{.}

Therefore, to determine Frob​(Ξ±1,Ξ±2)\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right) in this case, it is sufficient to determine which (t,u)∈[a1,∞)Γ—[b2,a1)(t,u)\in[a_{1},\infty)\times[b_{2},a_{1}) are in Frob​(Ξ±1,Ξ±2)\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right).

If (t,u)∈Frob​(Ξ±1,Ξ±2)βŠ†M​N​(Ξ±1,Ξ±2)(t,u)\in\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right)\subseteq MN(\alpha_{1},\alpha_{2}), then for some c1,c2,d1,d2∈{0}βˆͺ[1,∞)c_{1},c_{2},d_{1},d_{2}\in\left\{0\right\}\cup[1,\infty), t=a1​c1+a2​c2t=a_{1}c_{1}+a_{2}c_{2} and u=a1​d1+a2​d2+c2​b2u=a_{1}d_{1}+a_{2}d_{2}+c_{2}b_{2}. Then b2≀u<a1≀a2b_{2}\leq u<a_{1}\leq a_{2} implies that d1=d2=0d_{1}=d_{2}=0 and c2=ub2c_{2}=\frac{u}{b_{2}}. Then we have that t=a1​c1+a2​ub2t=a_{1}c_{1}+a_{2}\frac{u}{b_{2}}. If t<a1+a2​ub2t<a_{1}+a_{2}\frac{u}{b_{2}}, then c1=0c_{1}=0 and t=a2​ub2t=a_{2}\frac{u}{b_{2}}. But this would imply that for any tβ€²t^{\prime} such that t<tβ€²<a1+a2​ub2t<t^{\prime}<a_{1}+a_{2}\frac{u}{b_{2}}, (tβ€²,u)βˆ‰M​N​(Ξ±1,Ξ±2)(t^{\prime},u)\notin MN(\alpha_{1},\alpha_{2}), and this would contradict the assumption that (t,u)∈Frob​(Ξ±1,Ξ±2)(t,u)\in\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right).

Therefore, if (t,u)∈Frob​(Ξ±1,Ξ±2)(t,u)\in\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right) and b2≀u<a1b_{2}\leq u<a_{1}, then tβ‰₯a1+a2​ub2t\geq a_{1}+a_{2}\frac{u}{b_{2}}. But (t,u)∈Frob​(Ξ±1,Ξ±2)(t,u)\in\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right) implies that (t,uβ€²)∈Frob​(Ξ±1,Ξ±2)(t,u^{\prime})\in\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right) for every uβ€²β‰₯uu^{\prime}\geq u. Therefore, tβ‰₯a1+a2​uβ€²b2t\geq a_{1}+a_{2}\frac{u^{\prime}}{b_{2}} for every uβ€²u^{\prime} satisfying u≀uβ€²<a1u\leq u^{\prime}<a_{1}. Therefore, tβ‰₯a1+a1​a2b2t\geq a_{1}+\frac{a_{1}a_{2}}{b_{2}}.

Thus

(a1,a1)+[0,∞)2\displaystyle(a_{1},a_{1})+[0,\infty)^{2} βŠ†Frob​(Ξ±1,Ξ±2)\displaystyle\subseteq\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right)
βŠ†((a1,a1)+[0,∞)2)βˆͺ([a1​a2b2+a1,∞)Γ—[b2,a1))\displaystyle\subseteq\left((a_{1},a_{1})+[0,\infty)^{2}\right)\cup\left(\bigg{[}\frac{a_{1}a_{2}}{b_{2}}+a_{1},\infty\bigg{)}\times[b_{2},a_{1})\right)
βŠ†((a1,a1)+[0,∞)2)βˆͺ((a1​a2b2+a1,b2)+[0,∞)2)​,\displaystyle\subseteq\left((a_{1},a_{1})+[0,\infty)^{2}\right)\cup\left(\left(\frac{a_{1}a_{2}}{b_{2}}+a_{1},b_{2}\right)+[0,\infty)^{2}\right)\text{,}

so the proof in this case will be over if we show that (a1​a2b2+a1,b2)\left(\frac{a_{1}a_{2}}{b_{2}}+a_{1},b_{2}\right) is in Frob​(Ξ±1,Ξ±2)\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right). Suppose that fβ‰₯a1​a2b2+a1f\geq\frac{a_{1}a_{2}}{b_{2}}+a_{1} and gβ‰₯b2g\geq b_{2}. We will see that (f,g)∈M​N​(Ξ±1,Ξ±2)(f,g)\in MN(\alpha_{1},\alpha_{2}). We may as well assume that g<a1g<a_{1}. Then (f,g)=(1a1​(fβˆ’g​a2b2),0)​α1+(gb2,0)​α2(f,g)=\left(\frac{1}{a_{1}}\left(f-\frac{ga_{2}}{b_{2}}\right),0\right)\alpha_{1}+\left(\frac{g}{b_{2}},0\right)\alpha_{2}, so (f,g)∈M​N​(Ξ±1,Ξ±2)(f,g)\in MN(\alpha_{1},\alpha_{2}) because gb2β‰₯1\frac{g}{b_{2}}\geq 1 and 1a1​(fβˆ’g​a2b2)β‰₯1a1​(a1​a2b2+a1βˆ’a1​a2b2)=1\frac{1}{a_{1}}\left(f-\frac{ga_{2}}{b_{2}}\right)\geq\frac{1}{a_{1}}\left(\frac{a_{1}a_{2}}{b_{2}}+a_{1}-\frac{a_{1}a_{2}}{b_{2}}\right)=1.

Case 3: a2<a1a_{2}<a_{1} and a2≀b2a_{2}\leq b_{2}. By arguments on display above, (a1,a1)+[0,∞)2βŠ†Frob​(Ξ±1,Ξ±2)βŠ†(a2,a2)+[0,∞)2(a_{1},a_{1})+[0,\infty)^{2}\subseteq\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right)\subseteq(a_{2},a_{2})+[0,\infty)^{2}. But it is also easy to see that (a1,a2)∈Frob​(Ξ±1,Ξ±2)(a_{1},a_{2})\in\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right) (⟹(a1,a2)+[0,∞)2∈Frob​(Ξ±1,Ξ±2)\implies(a_{1},a_{2})+[0,\infty)^{2}\in\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right)): if fβ‰₯a1f\geq a_{1} and gβ‰₯a2g\geq a_{2}, then (f,g)=(fa1,0)​α1+(0,ga2)​α2∈M​N​(Ξ±1,Ξ±2)(f,g)=\left(\frac{f}{a_{1}},0\right)\alpha_{1}+\left(0,\frac{g}{a_{2}}\right)\alpha_{2}\in MN(\alpha_{1},\alpha_{2}).

It remains to determine Frob​(Ξ±1,Ξ±2)∩([a2,a1)Γ—[a2,∞))\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right)\cap\left([a_{2},a_{1})\times[a_{2},\infty)\right). Suppose that (t,u)∈Frob​(Ξ±1,Ξ±2)(t,u)\in\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right) and a2≀t<a1a_{2}\leq t<a_{1}. Let c1,c2,d1,d2∈{0}βˆͺ[1,∞)c_{1},c_{2},d_{1},d_{2}\in\left\{0\right\}\cup[1,\infty) satisfy t=a1​c1+a2​c2t=a_{1}c_{1}+a_{2}c_{2}, u=a1​d1+a2​d2+c2​b2u=a_{1}d_{1}+a_{2}d_{2}+c_{2}b_{2}. Then a2≀t<a1a_{2}\leq t<a_{1} implies that c1=0c_{1}=0 and c2=ta2c_{2}=\frac{t}{a_{2}}. If u<a2+t​b2a2u<a_{2}+\frac{tb_{2}}{a_{2}} then d1=d2=0d_{1}=d_{2}=0 and u=t​b2a2u=\frac{tb_{2}}{a_{2}}. But then if u<uβ€²<a2+t​b2a2u<u^{\prime}<a_{2}+\frac{tb_{2}}{a_{2}}, (t,uβ€²)βˆ‰M​N​(Ξ±1,Ξ±2)(t,u^{\prime})\notin MN(\alpha_{1},\alpha_{2}), contradicting the assumption that (t,u)∈Frob​(Ξ±1,Ξ±2)(t,u)\in\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right).

Therefore, uβ‰₯a2+t​b2a2u\geq a_{2}+\frac{tb_{2}}{a_{2}}. But (t,u)∈Frob​(Ξ±1,Ξ±2)(t,u)\in\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right) implies that (tβ€²,u)∈Frob​(Ξ±1,Ξ±2)(t^{\prime},u)\in\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right) for all tβ€²t^{\prime} such that t<tβ€²<a1t<t^{\prime}<a_{1}. Therefore, uβ‰₯a2+t′​b2a2u\geq a_{2}+\frac{t^{\prime}b_{2}}{a_{2}} for all such tβ€²t^{\prime}. Therefore, uβ‰₯a2+a1​b2a2u\geq a_{2}+\frac{a_{1}b_{2}}{a_{2}}.

To finish the proof in this case, it will suffice to show that [a2,a1)Γ—[a2+a1​b2a2,∞)βŠ†Frob​(Ξ±1,Ξ±2)[a_{2},a_{1})\times[a_{2}+\frac{a_{1}b_{2}}{a_{2}},\infty)\subseteq\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right), and for that it will suffice to show that if a2≀f<a1a_{2}\leq f<a_{1} and a2+a1​b2a2≀ga_{2}+\frac{a_{1}b_{2}}{a_{2}}\leq g then (f,g)∈M​N​(Ξ±1,Ξ±2)(f,g)\in MN(\alpha_{1},\alpha_{2}). For such (f,g)(f,g), (f,g)=(fa2,1a2​(gβˆ’f​b2a2))​α2(f,g)=\left(\frac{f}{a_{2}},\frac{1}{a_{2}}\left(g-\frac{fb_{2}}{a_{2}}\right)\right)\alpha_{2}, so (f,g)∈M​N​(Ξ±1,Ξ±2)(f,g)\in MN(\alpha_{1},\alpha_{2}) since fa2β‰₯1\frac{f}{a_{2}}\geq 1 and 1a2​(gβˆ’f​b2a2)β‰₯1a2​(a2+a1​b2a2βˆ’a1​b2a2)=1\frac{1}{a_{2}}\left(g-\frac{fb_{2}}{a_{2}}\right)\geq\frac{1}{a_{2}}\left(a_{2}+\frac{a_{1}b_{2}}{a_{2}}-\frac{a_{1}b_{2}}{a_{2}}\right)=1.

Case 4: 0<b2<a2<a10<b_{2}<a_{2}<a_{1}. Clearly Frob​(Ξ±1,Ξ±2)βŠ†(a2,b2)+[0,∞)2\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right)\subseteq(a_{2},b_{2})+[0,\infty)^{2}. If a1≀fa_{1}\leq f and a2≀ga_{2}\leq g then (f,g)=(fa1,0)​α1+(0,ga2)​α2(f,g)=\left(\frac{f}{a_{1}},0\right)\alpha_{1}+\left(0,\frac{g}{a_{2}}\right)\alpha_{2}, so (f,g)∈M​N​(Ξ±1,Ξ±2)(f,g)\in MN(\alpha_{1},\alpha_{2}); therefore, (a1,a2)+[0,∞)2βŠ†Frob​(Ξ±1,Ξ±2)(a_{1},a_{2})+[0,\infty)^{2}\subseteq\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right).

Next, we shall show that

Frob​(Ξ±1,Ξ±2)∩([a2,a1)Γ—[b2,∞))=[a2,a1)Γ—[a2+a1​b2a2,∞)​,\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right)\cap\left([a_{2},a_{1})\times[b_{2},\infty)\right)=[a_{2},a_{1})\times\bigg{[}a_{2}+\frac{a_{1}b_{2}}{a_{2}},\infty\bigg{)}\text{,}

by an argument that will be familiar to anyone who has read the proofs in cases 2 and 3.

Suppose that (t,u)∈Frob​(Ξ±1,Ξ±2)(t,u)\in\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right) and a2≀t<a1a_{2}\leq t<a_{1}. Then for some c2,d1,d2∈{0}βˆͺ[1,∞)c_{2},d_{1},d_{2}\in\left\{0\right\}\cup[1,\infty), t=c2​a2t=c_{2}a_{2} and u=a1​d1+a2​d2+ta2​b2u=a_{1}d_{1}+a_{2}d_{2}+\frac{t}{a_{2}}b_{2}. If u<a2+t​b2a2u<a_{2}+\frac{tb_{2}}{a_{2}}, then d1=d2=0d_{1}=d_{2}=0 and u=t​b2a2u=\frac{tb_{2}}{a_{2}}. But then for all uβ€²βˆˆ(u,t​b2a2)u^{\prime}\in\left(u,\frac{tb_{2}}{a_{2}}\right), (t,uβ€²)βˆ‰M​N​(Ξ±1,Ξ±2)(t,u^{\prime})\notin MN(\alpha_{1},\alpha_{2}), which contradicts the assumption that (t,u)∈Frob​(Ξ±1,Ξ±2)(t,u)\in\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right).

Therefore, uβ‰₯a2+t​b2a2u\geq a_{2}+\frac{tb_{2}}{a_{2}}. But then the fact that (tβ€²,u)∈Frob​(Ξ±1,Ξ±2)(t^{\prime},u)\in\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right) for all tβ€²t^{\prime} satisfying t<tβ€²<a1t<t^{\prime}<a_{1} implies that uβ‰₯a2+t′​b2a2u\geq a_{2}+\frac{t^{\prime}b_{2}}{a_{2}} for all such tβ€²t^{\prime}. Therefore uβ‰₯a2+a1​b2a2u\geq a_{2}+\frac{a_{1}b_{2}}{a_{2}}, which shows that

Frob​(Ξ±1,Ξ±2)∩([a2,a1)Γ—[b2,∞))βŠ†[a2,a1)Γ—[a2+a1​b2a2,∞)​.\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right)\cap\left([a_{2},a_{1})\times[b_{2},\infty)\right)\subseteq[a_{2},a_{1})\times\bigg{[}a_{2}+\frac{a_{1}b_{2}}{a_{2}},\infty\bigg{)}\text{.}

On the other hand, if a2≀f<a1a_{2}\leq f<a_{1} and gβ‰₯a2+a1​b2a2g\geq a_{2}+\frac{a_{1}b_{2}}{a_{2}}, then (f,g)=(fa2,1a2​(gβˆ’f​b2a2))​α2(f,g)=\left(\frac{f}{a_{2}},\frac{1}{a_{2}}\left(g-\frac{fb_{2}}{a_{2}}\right)\right)\alpha_{2}. From fa2β‰₯0\frac{f}{a_{2}}\geq 0 and

1a2​(gβˆ’f​b2a2)β‰₯1a2​(a2+a1​b2a2βˆ’a1​b2a2)=1,\frac{1}{a_{2}}\left(g-\frac{fb_{2}}{a_{2}}\right)\geq\frac{1}{a_{2}}\left(a_{2}+\frac{a_{1}b_{2}}{a_{2}}-\frac{a_{1}b_{2}}{a_{2}}\right)=1,

we conclude that (f,g)∈M​N​(Ξ±1,Ξ±2)(f,g)\in MN(\alpha_{1},\alpha_{2}). Thus

Frob​(Ξ±1,Ξ±2)∩([a2,a1)Γ—[b2,∞))=[a2,a1)Γ—[a2+a1​b2a2,∞).\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right)\cap\left([a_{2},a_{1})\times[b_{2},\infty)\right)=[a_{2},a_{1})\times\bigg{[}a_{2}+\frac{a_{1}b_{2}}{a_{2}},\infty\bigg{)}.

To finish Case 4, we will determine Frob​(Ξ±1,Ξ±2)∩([a1,∞)Γ—[b2,a2))\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right)\cap\left([a_{1},\infty)\times[b_{2},a_{2})\right). Suppose that (t,u)∈Frob​(Ξ±1,Ξ±2)(t,u)\in\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right), with tβ‰₯a1t\geq a_{1} and b2≀u<a2b_{2}\leq u<a_{2}. Then for some c1,c2∈{0}βˆͺ[1,∞)c_{1},c_{2}\in\left\{0\right\}\cup[1,\infty), t=a1​c1+a2​c2t=a_{1}c_{1}+a_{2}c_{2} and u=b2​c2u=b_{2}c_{2}. Then t=a1​c1+a2​ub2t=a_{1}c_{1}+\frac{a_{2}u}{b_{2}}. If t<a1+u​a2b2t<a_{1}+\frac{ua_{2}}{b_{2}}, then c1=0c_{1}=0 and t=u​a2b2t=\frac{ua_{2}}{b_{2}}.

Then for all tβ€²t^{\prime} such that t<tβ€²<a1+u​a2b2t<t^{\prime}<a_{1}+\frac{ua_{2}}{b_{2}}, (tβ€²,u)βˆ‰M​N​(Ξ±1,Ξ±2)(t^{\prime},u)\notin MN(\alpha_{1},\alpha_{2}), which contradicts the assumption that (t,u)∈Frob​(Ξ±1,Ξ±2)(t,u)\in\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right). Therefore, tβ‰₯a1+u​a2b2t\geq a_{1}+\frac{ua_{2}}{b_{2}}. But then (t,u)∈Frob​(Ξ±1,Ξ±2)(t,u)\in\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right) implies that (t,uβ€²)∈Frob​(Ξ±1,Ξ±2)(t,u^{\prime})\in\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right) for all uβ€²u^{\prime} satisfying u<uβ€²<a2u<u^{\prime}<a_{2}. Therefore, tβ‰₯a1+u′​a2b2t\geq a_{1}+\frac{u^{\prime}a_{2}}{b_{2}} for each such uβ€²u^{\prime}. Therefore, tβ‰₯a1+a22b2t\geq a_{1}+\frac{a_{2}^{2}}{b_{2}}. Thus Frob​(Ξ±1,Ξ±2)∩([a1,∞)Γ—[b2,a2))βŠ†[a1+a22b2,∞)Γ—[b2,a2)\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right)\cap\left([a_{1},\infty)\times[b_{2},a_{2})\right)\subseteq[a_{1}+\frac{a_{2}^{2}}{b_{2}},\infty)\times[b_{2},a_{2}). On the other hand, suppose that a1+a22b2≀fa_{1}+\frac{a_{2}^{2}}{b_{2}}\leq f and b2≀g<a2b_{2}\leq g<a_{2}. Then (f,g)=(1a1​(fβˆ’g​a2b2),0)​α1+(gb2,0)​α2(f,g)=\left(\frac{1}{a_{1}}\left(f-\frac{ga_{2}}{b_{2}}\right),0\right)\alpha_{1}+\left(\frac{g}{b_{2}},0\right)\alpha_{2}. Thus, since gb2β‰₯1\frac{g}{b_{2}}\geq 1 and 1a1​(fβˆ’g​a2b2)β‰₯1a1​(a1+a22b2βˆ’a22b2)=1\frac{1}{a_{1}}\left(f-\frac{ga_{2}}{b_{2}}\right)\geq\frac{1}{a_{1}}\left(a_{1}+\frac{a_{2}^{2}}{b_{2}}-\frac{a_{2}^{2}}{b_{2}}\right)=1, (f,g)∈M​N​(Ξ±1,Ξ±2)(f,g)\in MN(\alpha_{1},\alpha_{2}). Thus Frob​(Ξ±1,Ξ±2)∩[a1,∞)Γ—[b2,a2)=[a1+a22b2,∞)Γ—[b2,a2)\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right)\cap[a_{1},\infty)\times[b_{2},a_{2})=[a_{1}+\frac{a_{2}^{2}}{b_{2}},\infty)\times[b_{2},a_{2}). This, together with previous results, proves the claim in Case 4. ∎

We now shift focus to Q=β„€Q=\mathbb{Z}. Recall that χ​(a1,…,an)\chi\left(a_{1},\dots,a_{n}\right) is well-defined for coprime positive integers a1,…,ana_{1},\dots,a_{n}, with respect to the classical Frobenius template (β„•,β„•,β„•)(\mathbb{N},\mathbb{N},\mathbb{N}).

Proposition 4.4.

For nβ‰₯2n\geq 2, let (Ξ±1,…,Ξ±n)(\alpha_{1},\dots,\alpha_{n}) be a list of 22-tuples Ξ±i=(ai,bi)βˆˆβ„€+Γ—β„•\alpha_{i}=(a_{i},b_{i})\in\mathbb{Z}^{+}\times\mathbb{N} (for i=1,…,ni=1,\dots,n) satisfying gcd⁑(a1,…,an)=1\gcd(a_{1},\dots,a_{n})=1 and b1=0b_{1}=0. Then

(χ​(a1,…,an),χ​(a1,…,an)+(a1βˆ’1)β€‹βˆ‘i=2nbi)+β„•2βŠ†Frob​(Ξ±1,…,Ξ±n).\left(\chi\left(a_{1},\dots,a_{n}\right),\chi\left(a_{1},\dots,a_{n}\right)+(a_{1}-1)\sum_{i=2}^{n}b_{i}\right)+\mathbb{N}^{2}\subseteq\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right).
Proof.

Let t=χ​(a1,…,an)t=\chi\left(a_{1},\dots,a_{n}\right) and u=χ​(a1,…,an)+(a1βˆ’1)​(βˆ‘j=2nbj)u=\chi\left(a_{1},\dots,a_{n}\right)+(a_{1}-1)(\sum_{j=2}^{n}b_{j}). It’s sufficient to show that (t,u)∈Frob​(Ξ±1,…,Ξ±n)(t,u)\in\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right), i.e.
(t,u)+β„•2βŠ†M​N​(Ξ±1,…,Ξ±n)(t,u)+\mathbb{N}^{2}\subseteq MN(\alpha_{1},\dots,\alpha_{n}). Pick an arbitrary (f,g)∈(t,u)+β„•2(f,g)\in(t,u)+\mathbb{N}^{2}, i.e. choose integers fβ‰₯χ​(a1,…,an)f\geq\chi\left(a_{1},\dots,a_{n}\right) and gβ‰₯χ​(a1,…,an)+βˆ‘j=2nbj​(a1βˆ’1)g\geq\chi\left(a_{1},\dots,a_{n}\right)+\sum_{j=2}^{n}b_{j}(a_{1}-1). To complete the proof, we will show that

(f,g)∈M​N​(Ξ±1,…,Ξ±n)={(βˆ‘i=1nai​ci,βˆ‘i=1nai​di+βˆ‘i=2nbi​ci):ci,diβˆˆβ„•}.(f,g)\in MN(\alpha_{1},\dots,\alpha_{n})=\left\{\left(\sum_{i=1}^{n}a_{i}c_{i},\sum_{i=1}^{n}a_{i}d_{i}+\sum_{i=2}^{n}b_{i}c_{i}\right):c_{i},d_{i}\in\mathbb{N}\right\}.

Since fβ‰₯χ​(a1,…,an)f\geq\chi\left(a_{1},\dots,a_{n}\right), we can write f=βˆ‘i=1nai​cif=\sum_{i=1}^{n}a_{i}c_{i} for some nonnegative integers c1,…,cnc_{1},\dots,c_{n}. For each i∈{2,…,n}i\in\left\{2,\dots,n\right\}, use Euclidean division to write ci=a1​qi+c~ic_{i}=a_{1}q_{i}+\tilde{c}_{i} for some new nonnegative integers qiq_{i} and c~i≀(a1βˆ’1)\tilde{c}_{i}\leq(a_{1}-1), then set c~1=c1+βˆ‘i=2nai​qi\tilde{c}_{1}=c_{1}+\sum_{i=2}^{n}a_{i}q_{i} so that βˆ‘i=1nai​ci=f=βˆ‘i=1nai​c~i\sum_{i=1}^{n}a_{i}c_{i}=f=\sum_{i=1}^{n}a_{i}\tilde{c}_{i}. Can we find nonnegative d1,…,dnd_{1},\dots,d_{n} such that g=βˆ‘i=1nai​di+βˆ‘i=2nbi​c~ig=\sum_{i=1}^{n}a_{i}d_{i}+\sum_{i=2}^{n}b_{i}\tilde{c}_{i}? Well, gβˆ’βˆ‘i=2nbi​c~iβ‰₯gβˆ’βˆ‘i=2nbi​(a1βˆ’1)β‰₯χ​(a1,…,an)g-\sum_{i=2}^{n}b_{i}\tilde{c}_{i}\geq g-\sum_{i=2}^{n}b_{i}(a_{1}-1)\geq\chi\left(a_{1},\dots,a_{n}\right), so yes. Therefore, (f,g)∈M​N​(Ξ±1,…,Ξ±n)(f,g)\in MN(\alpha_{1},\dots,\alpha_{n}). ∎

Corollary 4.4.1.

For nβ‰₯2n\geq 2, let (Ξ±1,…,Ξ±n)(\alpha_{1},\dots,\alpha_{n}) be a list of 22-tuples Ξ±i=(ai,bi)βˆˆβ„€+Γ—β„•\alpha_{i}=(a_{i},b_{i})\in\mathbb{Z}^{+}\times\mathbb{N} (for i=1,…,ni=1,\dots,n) satisfying gcd⁑(a1,…,an)=1\gcd(a_{1},\dots,a_{n})=1. Frob​(Ξ±1,…,Ξ±n)\textnormal{Frob}\left(\alpha_{1},\dots,\alpha_{n}\right) is nonempty if and only if at least one bi=0b_{i}=0.

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 n=2n=2 and Q=β„€Q=\mathbb{Z}.

Proposition 4.5.

Suppose that a1,a2βˆˆβ„€+,bβˆˆβ„•a_{1},a_{2}\in\mathbb{Z}^{+},b\in\mathbb{N}, a1a_{1} and a2a_{2} are coprime, and Ξ±1=(a1,0),Ξ±2=(a2,b)\alpha_{1}=(a_{1},0),\alpha_{2}=(a_{2},b). Then

Frob​(Ξ±1,Ξ±2)=(χ​(a1,a2),χ​(a1,a2)+b​(a1βˆ’1))+β„•2.\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right)=\left(\chi\left(a_{1},a_{2}\right),\chi\left(a_{1},a_{2}\right)+b(a_{1}-1)\right)+\mathbb{N}^{2}.
Proof.

Let (t,u)βˆˆβ„•Γ—β„•(t,u)\in\mathbb{N}\times\mathbb{N}. By Proposition 4.4, tβ‰₯χ​(a1,a2)t\geq\chi\left(a_{1},a_{2}\right) and uβ‰₯χ​(a1,a2)+b​(a1βˆ’1)u\geq\chi\left(a_{1},a_{2}\right)+b(a_{1}-1) implies that (t,u)∈Frob​(Ξ±1,Ξ±2)(t,u)\in\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right). For the converse, we will prove the contrapositive. Suppose that t<χ​(a1,a2)t<\chi\left(a_{1},a_{2}\right). Then χ​(a1,a2)βˆ’1β‰₯t\chi\left(a_{1},a_{2}\right)-1\geq t is not in {a1​c1+a2​c2:c1,c2βˆˆβ„•}\left\{a_{1}c_{1}+a_{2}c_{2}:c_{1},c_{2}\in\mathbb{N}\right\}, so (χ​(a1,a2)βˆ’1,u)(\chi\left(a_{1},a_{2}\right)-1,u) is not in {(a1​c1+a2​c2,a1​d1+a2​d2+b​c2):c1,c2,d1,d2βˆˆβ„•}=M​N​(Ξ±1,Ξ±2)\{(a_{1}c_{1}+a_{2}c_{2},a_{1}d_{1}+a_{2}d_{2}+bc_{2}):c_{1},c_{2},d_{1},d_{2}\in\mathbb{N}\}=MN(\alpha_{1},\alpha_{2}), yet (χ​(a1,a2)βˆ’1,u)∈(t,u)+β„•2(\chi\left(a_{1},a_{2}\right)-1,u)\in(t,u)+\mathbb{N}^{2}. Hence (t,u)βˆ‰Frob​(Ξ±1,Ξ±2)(t,u)\notin\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right).

Now assume that u<χ​(a1,a2)+b​(a1βˆ’1)u<\chi\left(a_{1},a_{2}\right)+b(a_{1}-1). Set f=a1​c1+a2​(a1βˆ’1)f=a_{1}c_{1}+a_{2}(a_{1}-1) for some nonnegative c1c_{1} large enough such that fβ‰₯tf\geq t. Consider any alternative expression of ff as f=a1​c~1+a2​c~2f=a_{1}\tilde{c}_{1}+a_{2}\tilde{c}_{2} using nonnegative coefficients c~1,c~2\tilde{c}_{1},\tilde{c}_{2}. Recall that f=a1​c1+a2​(a1βˆ’1)f=a_{1}c_{1}+a_{2}(a_{1}-1), so a1​(c1βˆ’c~1)=a2​(c~2βˆ’(a1βˆ’1))a_{1}(c_{1}-\tilde{c}_{1})=a_{2}(\tilde{c}_{2}-(a_{1}-1)). Then a1|(c~2βˆ’(a1βˆ’1))a_{1}|(\tilde{c}_{2}-(a_{1}-1)) since a1a_{1} and a2a_{2} are coprime, so c~2≑a1βˆ’1(moda1)\tilde{c}_{2}\equiv a_{1}-1\pmod{a_{1}}. And c~2\tilde{c}_{2} is nonnegative, so c~2β‰₯(a1βˆ’1)\tilde{c}_{2}\geq(a_{1}-1), so c~2=(a1βˆ’1)+a1​k\tilde{c}_{2}=(a_{1}-1)+a_{1}k for some nonnegative integer kk. Set g=χ​(a1,a2)+b​(a1βˆ’1)βˆ’1g=\chi\left(a_{1},a_{2}\right)+b(a_{1}-1)-1 so that gβ‰₯ug\geq u; hence (f,g)∈(t,u)+β„•2(f,g)\in(t,u)+\mathbb{N}^{2}. Suppose that (f,g)∈M​N​(Ξ±1,Ξ±2)(f,g)\in MN(\alpha_{1},\alpha_{2}); there are nonnegative coefficients d1d_{1} and d2d_{2} such that g=a1​d1+a2​d2+b​c~2=a1​d1+a2​d2+b​((a1βˆ’1)+a1​k)g=a_{1}d_{1}+a_{2}d_{2}+b\tilde{c}_{2}=a_{1}d_{1}+a_{2}d_{2}+b((a_{1}-1)+a_{1}k). Consequently, gβˆ’b​(a1βˆ’1)=a1​(d1+b​k)+a2​d2g-b(a_{1}-1)=a_{1}(d_{1}+bk)+a_{2}d_{2} for nonnegative integers (d1+b​k)(d_{1}+bk) and d2d_{2}, so gβˆ’b​(a1βˆ’1)∈M​N​(a1,a2)g-b(a_{1}-1)\in MN(a_{1},a_{2}). But this is impossible, because gβˆ’b​(a1βˆ’1)=χ​(a1,a2)βˆ’1βˆ‰M​N​(a1,a2)g-b(a_{1}-1)=\chi\left(a_{1},a_{2}\right)-1\notin MN(a_{1},a_{2}), so our supposition must be false; (f,g)βˆ‰M​N​(Ξ±1,Ξ±2)(f,g)\notin MN(\alpha_{1},\alpha_{2}). Therefore, (t,u)βˆ‰Frob​(Ξ±1,Ξ±2)(t,u)\notin\textnormal{Frob}\left(\alpha_{1},\alpha_{2}\right). ∎

Proposition 4.5 shows that when n=2n=2, the set inclusion in the conclusion of Proposition 4.4 is an equality. However, for lists of length >2>2, 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 Ξ±1=(3,0)\alpha_{1}=(3,0), Ξ±2=(5,2)\alpha_{2}=(5,2), and Ξ±3=(7,4)\alpha_{3}=(7,4). Then it can be shown that (5,16)∈Frob​(Ξ±1,Ξ±2,Ξ±3)+β„•2(5,16)\in\textnormal{Frob}\left(\alpha_{1},\alpha_{2},\alpha_{3}\right)+\mathbb{N}^{2}, but (5,16)βˆ‰{χ​(a1,…,an)+(a1βˆ’1)​(βˆ‘i=2nbi)}+β„•2(5,16)\notin\{\chi\left(a_{1},\dots,a_{n}\right)+(a_{1}-1)\left(\sum_{i=2}^{n}b_{i}\right)\}+\mathbb{N}^{2}. In fact, it can be shown that Frob​(Ξ±1,Ξ±2,Ξ±3)=(5,9)+β„•2\textnormal{Frob}\left(\alpha_{1},\alpha_{2},\alpha_{3}\right)=(5,9)+\mathbb{N}^{2}. Furthermore, for Ξ²1=(3,0)\beta_{1}=(3,0), Ξ²2=(5,1)\beta_{2}=(5,1), and Ξ²3=(7,4)\beta_{3}=(7,4) we have

Frob​(Ξ²1,Ξ²2,Ξ²3)=((5,9)+β„•2)βˆͺ((8,7)+β„•2)​,\textnormal{Frob}\left(\beta_{1},\beta_{2},\beta_{3}\right)=\left((5,9)+\mathbb{N}^{2}\right)\cup\left((8,7)+\mathbb{N}^{2}\right)\text{,}

so the Frobenius set might even be a union of two sets, each of the form (a,b)+β„•2(a,b)+\mathbb{N}^{2}, 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 22, but not for lists of length >2>2.

5 A more general template

Here we broaden our horizons and pass from the templates (A,C,U)(A,C,U) where AA and CC are thought of as subsets of the same overlying ring, to templates (Aβ€²,Cβ€²,Uβ€²)(A^{\prime},C^{\prime},U^{\prime}) where Aβ€²A^{\prime} is a monoid and Cβ€²C^{\prime} is a set of functions acting on Aβ€²A^{\prime}. 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 A=U=β„•Γ—β„•Γ—β„•,A=U=\mathbb{N}\times\mathbb{N}\times\mathbb{N}, and let CC be the set of upper triangular matrices in M3​(β„•)M_{3}(\mathbb{N}). In the ring β„€3\mathbb{Z}^{3} with coordinate addition and multiplication, A=U=β„•3A=U=\mathbb{N}^{3} is a monoid. However, CC is not contained in β„€3,\mathbb{Z}^{3}, so this template is different from those considered previously. Note that CC contains an isomorphic copy of β„•3\mathbb{N}^{3} via the semiring embedding given by

[xyz]↦[x000y000z].\begin{bmatrix}x\\ y\\ z\\ \end{bmatrix}\mapsto\begin{bmatrix}x&0&0\\ 0&y&0\\ 0&0&z\\ \end{bmatrix}.

Consider a general pair of tuples (a,b,c)T(a,b,c)^{T} and (d,e,f)T∈A(d,e,f)^{T}\in A. A general member of

M​N​([abc],[def])MN\left(\begin{bmatrix}a\\ b\\ c\\ \end{bmatrix},\begin{bmatrix}d\\ e\\ f\\ \end{bmatrix}\right)

has the form

[uvw0xy00z]​[abc]+[uβ€²vβ€²wβ€²0xβ€²yβ€²00zβ€²]​[def]​,\begin{bmatrix}u&v&w\\ 0&x&y\\ 0&0&z\\ \end{bmatrix}\begin{bmatrix}a\\ b\\ c\\ \end{bmatrix}+\begin{bmatrix}u^{\prime}&v^{\prime}&w^{\prime}\\ 0&x^{\prime}&y^{\prime}\\ 0&0&z^{\prime}\\ \end{bmatrix}\begin{bmatrix}d\\ e\\ f\\ \end{bmatrix}\text{,}

with all entries coming from β„•\mathbb{N}. As expected, Frob​((a,b,c)T,(d,e,f)T)\textnormal{Frob}\left((a,b,c)^{T},(d,e,f)^{T}\right) is defined to be

{𝐰∈M​N​([abc],[def]):𝐰+β„•3βŠ†M​N​([abc],[def])}​.\left\{\mathbf{w}\in MN\left(\begin{bmatrix}a\\ b\\ c\\ \end{bmatrix},\begin{bmatrix}d\\ e\\ f\\ \end{bmatrix}\right):\mathbf{w}+\mathbb{N}^{3}\subseteq MN\left(\begin{bmatrix}a\\ b\\ c\\ \end{bmatrix},\begin{bmatrix}d\\ e\\ f\\ \end{bmatrix}\right)\right\}\text{.}

Hence, by our understanding of the classical Frobenius problem, we see that

Frob​([abc],[def])=[χ​(a,b,c,d,e,f)χ​(b,c,e,f)χ​(c,f)]+β„•3,\textnormal{Frob}\left(\begin{bmatrix}a\\ b\\ c\\ \end{bmatrix},\begin{bmatrix}d\\ e\\ f\\ \end{bmatrix}\right)=\begin{bmatrix}\chi(a,b,c,d,e,f)\\ \chi(b,c,e,f)\\ \chi(c,f)\\ \end{bmatrix}+\mathbb{N}^{3},

when nonempty, which is true if and only if gcd⁑(c,f)=1\gcd(c,f)=1.

From the case k=2k=2 it is straightforward to see what Frob​(Ξ±1,…,Ξ±k)\textnormal{Frob}\left(\alpha_{1},...,\alpha_{k}\right) is for arbitrary kβˆˆβ„€+k\in\mathbb{Z}^{+} and Ξ±1,…,Ξ±k∈A\alpha_{1},...,\alpha_{k}\in A. It is not difficult to generalize these results to mΓ—1m\times 1 column vectors and mΓ—mm\times m matrices for m>3m>3. 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 CC. For instance, we could require the matrices to be symmetric, or upper triangular with constant diagonal.

These examples point to a generalized Frobenius template (Aβ€²,Cβ€²,Uβ€²)(A^{\prime},C^{\prime},U^{\prime}) in which Aβ€²A^{\prime} (or perhaps Aβ€²βˆͺ{0}A^{\prime}\cup\left\{0\right\}) and Uβ€²U^{\prime} are monoids in a ring RR, and Cβ€²C^{\prime} is a monoid in the ring of endomorphisms of (R,+)(R,+) such that each Ο†βˆˆC\varphi\in C maps AA into U.U.

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 ℀​[m]\mathbb{Z}[\sqrt{m}]. 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 ℀​[m]\mathbb{Z}[\sqrt{m}]. 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.