Frobenius sets for conjugate split primes in the Gaussian integers

Abstract

We solve the Frobenius coin problem in the Gaussian integers when the coin set is comprised of two conjugate primes. We also provide preliminary results toward a general solution for the two-coin problem in the Gaussian integers.

The classical Frobenius coin problem [9] (known variously as the “money-changing problem” [5] or the “Diophantine Frobenius problem” [7] or the “Frobenius number problem for numerical semigroups” [8]) states that for any set of mutually relatively prime coin denominations there is a “sufficient price” beyond which all prices can be assembled by exact change. In [4] we were part of a collaboration which demonstrated the truth of a two-dimensional analog of the Frobenius coin problem for the Gaussian integers, and calculated explicit solutions for two-coin sets drawn from the real axis, the imaginary axis, and the 45-degree line. Although the coin sets considered in that paper each yielded a simple conical solution set which could be specified by the single vertex on its boundary, in general the “sufficient price set” for a 2-coin set may have a very jagged boundary. In this paper we provide what is hoped to be an important step toward a complete solution for the two-coin problem by analyzing the situation where the coins are conjugate primes split from an odd rational prime p. The solution set in this case is a W-shaped region symmetric with respect to the imaginary axis. In the last section of the paper we provide some additional two-coin examples and results in order to raise wider awareness of some of the available lines for further research on this problem.

Let’s review the setup of the problem. Within the Gaussian integers $\mathbb{Z} [i]$ we are given a set of non-zero numbers C={c ₁,c ₂,…,c _n } with each $\operatorname{Re}(c _{j} )\geq0$ and $\operatorname{Im}(c _{j} )\geq0$. We consider two semigroups—the “algebraic” semigroup $\mathit{SG} _{Alg} ( C ) = \{ \lambda_{1} c _{1} + \cdots+\lambda_{n} c _{n} | \lambda_{j} \in\mathbb{Z} [ i ], \operatorname{Re}(\lambda_{j} )\geq 0, \operatorname{Im}(\lambda_{j} )\geq0 \}$ and the “geometric” semigroup $\mathit{SG} _{Geom} ( C ) = \{ z\in \mathbb{Z} [ i ] \backslash\{ 0\} |\min_{j} \operatorname{Arg}( c _{j} ) \leq \operatorname{Arg}(z)\leq\max_{j} \operatorname{Arg}( c _{j} ) + \pi/2 \} \cup\{0\}$. These are both submonoids of the additive semigroup of the non-negative Gaussian integers, and are therefore commutative, cancellative, torsion free and reduced. The algebraic semigroup is finitely generated by the elements of C and iC={ic ₁,ic ₂,…,ic _n } and is therefore affine, while the geometric semigroup generally is not. However, the geometric semigroup is always geometrically convex, while the algebraic semigroup generally is not. In fact one could define SG _Alg (C) to be the minimal affine semigroup containing C∪iC, and SG _Geom (C) to be the minimal geometrically convex semigroup containing C∪iC, so that they can be thought of as the affine and convex semigroup closures of the set C∪iC respectively within the discrete group $\mathbb{Z} [i]$ endowed with the standard Euclidean geometry.

A number $z \in\mathbb{Z} [i]$ is called a sufficient price for the set C if the translate z+SG _Geom (C) is contained in SG _Alg (C). The main result of [4] says that if the numbers in the set C are mutually relatively prime, then there is at least one sufficient price for C. To understand what it means for z to be a sufficient price, let’s look back to the hypothetical context for the classical Frobenius coin problem. In some statements of that problem it is supposed that there is a grocer with no change in the cash register presented with the difficulty that some items cannot be purchased with exact change made from the available coins in that country. A sufficient price would be one that is high enough to guarantee that it or any higher price could be paid with exact change. In our reframing of the problem we envision a country with a fixed set of first quadrant Gaussian integer coins and where purchases can be made using both real and imaginary versions of those coins. A price w is considered more expensive than another price z if the ray from z to w points into the directional span of angles (min _j arg(c _j ),max _j arg(c _j )) for possible coin payments. In this setting a sufficient price z is one that is expensive enough (far enough into the payment span) that it or any more expensive price can actually be paid with an exact-change purchase.

The objective then is to find the set T(C) of all sufficient prices. In the classical Frobenius problem for the rational integers there are two ways to express the set of sufficient prices: you can specify the Frobenius conductor (the least integer which is sufficient), or you can specify the Frobenius number (the greatest integer which is not sufficient). Either way, you have clarified unambiguously the positive ray of integers which are sufficient prices. In [4] we used the Frobenius conductor approach, and specified the sufficient price sets for several instances in the form T(C)=z _C +SG _Geom (C). In this paper, however, the Frobenius number approach provides an easier way to specify the regions which result. We will use the notation $\mathit{SG} _{Geom} ^{0} ( C )= \{ z\in \mathbb{Z} [ i ] \backslash\{ 0\} |\min_{j} \operatorname{Arg} ( c _{j} ) <\operatorname{Arg} ( z ) < \max_{j} \operatorname{Arg}( c _{j} ) +\pi/2 \}$ for the open condition geometric semigroup, and express T(C) as a union of translates of this set. To help familiarize the reader to this convention and to provide some perspective on the extent of significant move forward represented by the current work we restate here the computational results of [4] in the form $T ( C ) = w _{C} + \mathit{SG} _{Geom} ^{0} ( C )$:

FormalPara Proposition

For any two relatively prime positive rational integers c ₁,c ₂

• (a) $T ( c _{1}, c _{2} ) = ( c _{1} c _{2} - c _{1} - c _{2} ) ( 1+i ) + \mathit{SG} _{Geom} ^{0} ( c _{1}, c _{2} )$

• (b) $T ( c _{1}, ic _{2} ) = ( c _{1} c _{2} - c _{1} - c _{2} ) i+ \mathit{SG} _{Geom} ^{0} ( c _{1}, ic _{2} )$

• (c) If c ₁ is odd, $T ( c _{1}, c _{2} (i+1) ) = c _{1} ( c _{2} -1 ) + ( 2c _{1} c _{2} - c _{1} - 2c _{2} ) i+ \mathit{SG} _{Geom} ^{0} ( c _{1}, c _{2} (i+1) )$

• (d) If c ₁ is odd, $T ( ic _{1}, c _{2} (i+1) ) = -c _{1} ( c _{2} -1 ) + ( 2c _{1} c _{2} - c _{1} - 2c _{2} ) i+ \mathit{SG} _{Geom} ^{0} ( ic _{1}, c _{2} (i+1) )$

FormalPara Proof

From the figures in [4] it is geometrically clear that for case (a) the needed adjustment to switch from a closed condition semigroup to an open condition semigroup is w _C =z _C −(1+i) and that for the other three cases w _C =z _C −i. □

Notice that in this proposition all cases concern coins that are either on one of the axes or along the 45 degree line. The formulas (and the proofs there) all are reminiscent of Sylvester’s formula for the two-coin case of the classical Frobenius coin problem. In the current work we consider coin sets with no special angle restrictions, and in moving away from the 8th roots of unity we have largely unmoored the results from any type of lingering dependency on the Sylvester formula.

To understand the setup for our work let’s review the prime structure of the Gaussian integers. (See, for example [6].) The ring $\mathbb{Z} [i]$ is a principal ideal domain, and its primes lie over those of $\mathbb{Z}$ in one of three ways: rational primes of the form p=4n+3 are non-split and non-ramified in $\mathbb{Z} [i]$, rational primes of the form p=4n+1 split into two non-ramified primes each with quadratic norm p, and the rational prime 2 ramifies in $\mathbb{Z} [i]$ as 2=−i(1+i)². The presence of split primes provides the interesting situation that a coin set made up of relatively prime Gaussian coins could have quadratic norms which are not relatively prime. So it was a natural question to investigate how this would affect the conductor set. Typically, the two primes split from a prime of the form p=4n+1 are written as complex conjugates in the first and fourth quadrants, but since our coin sets from [4] must reside in the first quadrant, we chose replace the fourth quadrant prime by its first quadrant associate (that is, we multiplied it by the unit i).

Here is our main result:

FormalPara Theorem

Let a<b be positive rational integers such that p=a ²+b ² is a rational prime with remainder 1 modulo 4, and let u=a+bi, v=b+ai be the first quadrant Gaussian primes split from p. Then the coin set C={u,v} has sufficient price set $T ( C ) = ( w _{1} + \mathit{SG} _{Geom} ^{0} ( C ) ) \cup( w _{2} + \mathit{SG} _{Geom} ^{0} ( C ) )$ where w ₁=ab+(b ²+2ab−2a−2b)i and w ₂=−ab+(b ²+2ab−2a−2b)i.

The following diagram is intended to aid the reader in understanding the geometric aspects of the result and the overall organization of the proof.

In this diagram the algebraic semigroup SG _Alg (C) is spanned by the four vectors shown emanating from the origin. The geometric semigroup SG _Geom (C) includes all lattice points in the angular wedge stretching from v to iu. The white circles are lattice points that will be shown not to be in SG _Alg (C). In particular, the white circle on the imaginary axis represents the highest point on the imaginary axis which is not in SG _Alg (C). The arrows forming a solid W-shape are translates of the vectors v and iu, as are the dashed arrows forming the top sides of two parallelograms. By proving that the lattice points interior to those parallelograms and the solid point at the top of each are all in SG _Alg (C), we will be able to show that every point above the solid W-shape is a sufficient price for C.

Our continued work on the Gaussian version of the Frobenius coin problem represents a significant departure from both the recent work of Beneish et al. [2] on real quadratic extensions of $\mathbb{N}$, and the work on free affine semigroups $\mathbb{N} ^{e}$ going back to Assi [1]. In each of these generalizations the coefficients attached to the elements of the coin set C are taken from the rational integers. Here and in a pending sequel work [3] for non-real quadratic extensions of $\mathbb{N}$ we use the ring multiplication inherited from the complex numbers $\mathbb{C}$ to consider coefficients taken from the algebraic integers of the same number field as the coins. While one could argue that the use of Gaussian coefficients is equivalent to expanding the coin set to C∪iC and using $\mathbb {N}$ coefficients on an $\mathbb{N} ^{2}$ lattice, it is clear from our investigations so far that there is a number-theoretic interplay between the multiplication and addition of $\mathbb{Z} [i]$ that is driving some of the geometric results. In our preliminary work on larger coin sets (not discussed in this paper) we are observing very different results depending on whether any coins share Gaussian prime factors or even conjugate prime factors, even when the full set is relatively prime.

1 Proof

Throughout this section we will assume a,b,p,u,v and C are as specified in the theorem.

Lemma 1

The purely imaginary elements of SG _Alg (C) are exactly the set of Gaussian integers which can be written in the form z=(r ₁2a+r ₂2b+r ₃ p)i for non-negative rational integers r _j .

Proof

First, observe that any Gaussian integer of the prescribed form is purely imaginary and is seen to be an element of SG _Alg (C) through the identities 2ai=iu+v, 2bi=u+iv, pi=uv. Conversely, suppose that z is a purely imaginary element of SG _Alg (C), and let’s write z=(c+di)u+(e+fi)v with c,d,e,f the non-negative real and imaginary parts of the coefficients. Then $\operatorname{Re} ( z ) = ( c-f ) a+ ( e-d ) b=0$, which shows that b|(c−f) and a|(d−e). It also shows that the two fractions $\frac{c-f}{ b}$ and $\frac{d-e}{a}$ have a common value that we will call r. If c≥f then r≥0 and we can write

$$\begin{aligned} z =& \bigl[ ( c-f ) + ( d-e ) i \bigr] u+e ( iu+v ) +f ( u+iv ) \\=& ( rb+rai ) u+e ( iu+v ) +f ( u+iv ) \\=&r(uv)+e ( iu+v ) +f ( u+iv ) \end{aligned}$$

so that z has the prescribed form with r ₁=e, r ₂=f, r ₃=r. If c<f then r<0 and we can write

$$\begin{aligned} z =&c ( u+iv ) +d ( iu+v ) + \bigl[ ( e-d ) + ( f-c ) i \bigr] v \\=&c ( u+iv ) +d ( iu+v ) + ( -ra-rbi ) v \\=&c ( u+iv ) +d ( iu+v ) -r ( uv ) \end{aligned}$$

so that z has the prescribed from with r ₁=d, r ₂=c, r ₃=−r. □

Corollary 1.1

The highest point on the imaginary axis which is not an element of SG _Alg (C) is i times the (classical) Frobenius number F(2a,2b,p)=a ²+b ²+2ab−2a−2b.

Proof

The claim that this point is i times F(2a,2b,p) follows immediately from the lemma. But we need to demonstrate that the value of this number is as claimed. Notice that the linear combinations r ₁2a+r ₂2b with non-negative rational integers r _j cover all even integers greater than 2∗F(a,b). Since p is odd, we also know that the linear combinations r ₁2a+r ₂2b+p with non-negative rational integers r _j cover all odd integers greater than 2∗F(a,b)+p. Taken together, this already tells us that the full set of linear combinations r ₁2a+r ₂2b+r ₃ p with non-negative rational integers r _j cover all integers of either parity that are greater than 2F(a,b)+p. By Sylvester’s formula [10] we know that 2F(a,b)+p=2(ab−a−b)+p, which is the value we are trying to establish. We need only to show that this number cannot be written in the form r ₁2a+r ₂2b+r ₃ p with non-negative rational integers r _j . Since this number is odd, the number r ₃ would need to be odd. r ₃=1 is impossible, since it would lead to 2F(a,b)=r ₁2a+r ₂2b. So r ₃≥3, but this is also impossible because 3p=p+2(a ²+b ²)>p+2b ²>p+2ab>p+2(ab−a−b). □

For convenience, we will use the letter F for this Frobenius number F(2a,2b,p). Hence, in the diagram we have labeled the open circle on the imaginary axis “Fi”.

Corollary 1.2

Any number z=Fi−riu or z=Fi−rv with r a positive rational integer cannot be an element of SG _Alg (C).

Proof

If either of these points was in SG _Alg (C), then so also would Fi. □

Lemma 2

Any number of the form z=Fi−aiu+rv with r a positive rational integer cannot be an element of SG _Alg (C).

Proof

Suppose instead that some positive value of r led to a value of z which was an element of SG _Alg (C), and let r=r ₀ be the minimal such value. Then we can write Fi−aiu+r ₀ v=(c+di)u+(e+fi)v with c,d,e,f non-negative rational integers. We must have e=0 because the condition e≥r ₀ would mean that Fi=[c+(d+a)i]u+[(e−r ₀)+fi]v∈SG _Alg (C) which violates Corollary 1.2, and the remaining alternative r ₀>e>0 would imply that r=r ₀−1 also leads to a z-value belonging to SG _Alg (C) in contradiction to the minimality of r ₀.

Equating the real and imaginary parts of the two expressions for z yields the equations

$$\begin{aligned} ab+ r _{0} b =&ca-db-fa \end{aligned}$$

(1)

$$\begin{aligned} F- a ^{2} + r _{0} a =&cb+da+fb \end{aligned}$$

(2)

We can rewrite the first of these as

$$( r _{0} +d ) b= ( c-f-b ) a $$

And this shows that a|(r ₀+d) and b|(c−f−b), and that the integers $\frac{r _{0} +d}{a}$ and $\frac{c-f-b}{b}$ are equal (and positive). Let $g= \frac{r _{0} +d}{ a}$, so that we can write r ₀=ag−d and c=bg+f+b. Let’s substitute these two formulas and value of F into Eq. (2).

$$\bigl(a ^{2} + b ^{2} +2ab-2a-2b\bigr)- a ^{2} +(ag-d)a=(bg+f+b)b+da+fb $$

After cancellations and rearrangement we have

$$2ab-2a-2b= \bigl( b ^{2} - a ^{2} \bigr) g+2da+2fb $$

This shows that g is even. Writing g=2g′ and factoring the difference of squares allows us to write

$$2ab-2a-2b= \bigl[ d+ ( b-a ) g ' \bigr] 2a+ \bigl[ f+ ( b-a ) g ' \bigr] 2b $$

Dividing through by 2 then yields

$$ab-a-b= \bigl[ d+ ( b-a ) g ' \bigr] a+ \bigl[ f+ ( b-a ) g ' \bigr] b $$

which expresses frob(a,b) in the form r ₁ a+r ₂ b with positive integers r _j . This is impossible. □

Corollary 2.1

Any number of the form z=Fi−av+riu with r a positive rational integer cannot be an element of SG _Alg (C).

Proof

Suppose Fi−av+riu=(c+di)u+(e+fi)v with c,d,e,f non-negative rational integers. By making the replacements u↔iv and v↔iu we reflect all terms through the imaginary axis to obtain Fi−aiu+rv=(f+ei)u+(d+ci)v in violation of Lemma 2. □

Corollary 1.1, Corollary 1.2, Lemma 2 and Corollary 2.1 together establish that none of the lattice points on the solid W-shaped boundary from our diagram can be elements of SG _Alg (C). And this in turn tells us that no lattice point on or below this W-shape can be in the set T(C) of sufficient prices for C.

We now turn our attention to the parallelogram P with vertices w ₁=Fi−aiu, w ₁+v, w ₁+iu and w ₁+iu+v. But we actually do not want to include any of the vertices except the uppermost one. For definiteness and in order to make some calculations easier in the next few proofs we will write

$$\begin{aligned} P =& \biggl\{ ab+x+iy | x,y \in\mathbb{Z}, \vert x \vert \leq b-1,\\&\phantom{\{}b ^{2} +2ab-2a-2b+ \frac{a}{b} \vert x \vert <y\leq b ^{2} +2ab-2b- \frac{a}{b} \vert x \vert \biggr\} \end{aligned}$$

We also note here that P is a fundamental region for the translation action of additive group 〈v,iu〉 on the Gaussian integers. So if we can show that P is contained in SG _Alg (C), then so also will the entirety of the open translate $w _{1} + \mathit{SG} _{Geom} ^{0} ( C )$.

Lemma 3

Let x be a rational integer with |x|≤b−1. Then there is a unique pair (K,L) of rational integers satisfying x+ab=Ka+Lb,1≤K≤b,L≥0. For this pair, L≤a.

Proof

x+ab−a>ab−a−b=F(a,b). So we can write x+ab−a=r ₁ a+r ₂ b with non-negative rational integers r _j , and we choose the expression of this form with r ₁ minimal. We must have r ₁<b, because otherwise x+ab−a=(r ₁−b)a+(r ₂+a)b is an expression violating the minimality of r ₁. Then K=r ₁+1,L=r ₂ is a pair satisfying the defining conditions. And it is unique, since any other satisfying pair (K′,L′) would require b|(K′−K) in violation of |K′−K|<b. It remains to show that L≤a, but this follows immediately from the fact that x+ab≤b−1+ab<(a+1)b. □

With x,K,L as in Lemma 3, our plan is to explicitly construct several points on the vertical line $\operatorname{Re} ( z ) =x+ab$ which can be used to demonstrate that the intersection of this line with the parallelogram P is contained in SG _Alg (C). The three points we will use are

$$\begin{aligned} z _{1} =&Ku+Lv \\z _{2} =& \bigl[ ( L+a ) + ( b-K ) i \bigr] v \\z _{3} =& \bigl[ ( K+b ) + ( a-L ) i \bigr] u \end{aligned}$$

It is easily verified that each of these points is in SG _Alg (C) and satisfies $\operatorname{Re} ( z _{j} ) =Ka+Lb=x+ab$.

$$\begin{aligned} \operatorname{Im} ( z _{2} ) =& La+bK+ a ^{2} + b ^{2} -2Kb=\operatorname{Im} ( z _{1} ) +p-2Kb \\\operatorname{Im} ( z _{3} ) =& La+Kb+ a ^{2} + b ^{2} -2La=\operatorname{Im} ( z _{1} ) +p-2La \end{aligned}$$

This shows that $\operatorname{Im} ( z _{2} )$ and $\operatorname{Im} ( z _{3} )$ have the same parity, and that they differ in parity from $\operatorname{Im} ( z _{1} )$.

Lemma 4a

Let x,K,L be as in Lemma 3. Then ab+x+iy∈SG _Alg (C) for all y of the same parity as $\operatorname{Im} ( z _{1} )$ and satisfying $y>b ^{2} +2ab-2a-2b+ \frac{a}{b} \vert x \vert$.

Proof

Observe that

$$\begin{aligned} \operatorname{Im} ( z _{1} ) =&La+Kb= \frac{a}{b} ( Lb+Ka ) +K \biggl( b- \frac{a ^{2}}{b} \biggr) = \frac{a}{b} ( x+ab ) +K \biggl( b- \frac{a ^{2}}{ b} \biggr) \\=& b ^{2} + \frac{a}{b} x+ \biggl( \frac{K}{b} -1 \biggr) \bigl( b ^{2} - a ^{2} \bigr) \leq b ^{2} + \frac{a}{ b} x\leq b ^{2} + \frac{a}{b} | x| \end{aligned}$$

So $y-\operatorname{Im}( z _{1} )$ is an even integer greater than 2ab−2a−2b=2F(a,b), and can therefore be written in the form $y-\operatorname{Im} ( z _{1} ) = r _{1} 2a+ r _{2} 2b$ for non-negative rational integers r _j . But this allows us to write ab+x+iy=z ₁+r ₁(iu+v)+r ₂(u+iv), which is in SG _Alg (C). □

Lemma 4b

Let x,K,L be as in Lemma 3 with the extra condition that K≥a. Then ab+x+iy∈SG _Alg (C) for all y of the opposite parity from $\operatorname{Im} ( z _{1} )$ and satisfying $y>b ^{2} +2ab-2a-2b+ \frac{a}{b} \vert x \vert$.

Proof

Reusing much of what we already proved in Lemma 4a, we have

$$\begin{aligned} \operatorname{Im} ( z _{2} ) =& \operatorname{Im} ( z _{1} ) +p-2Kb= b ^{2} + \frac{a}{b} x+Kb-K \frac{a ^{2}}{b} - b ^{2} + a ^{2} + \bigl( a ^{2} + b ^{2} \bigr) \\&{}-2Kb \\=& b ^{2} + \frac{a}{b} x+K \biggl( \frac{- b ^{2} - a ^{2}}{b} \biggr) +2 a ^{2} \leq b ^{2} + \frac{a}{ b} | x|+K \biggl( \frac{- b ^{2} - a ^{2}}{b} \biggr) +2 a ^{2} \end{aligned}$$

Now using the fact that K≥a, we can continue by writing

$$\begin{aligned} \operatorname{Im} ( z _{2} ) \leq& b ^{2} + \frac{a}{b} \vert x \vert +a \biggl( \frac{- b ^{2} - a ^{2}}{b} \biggr) +2 a ^{2} \\=& b ^{2} + \frac{a}{b} \vert x \vert - \frac{a}{b} \bigl( b ^{2} -2ab+ a ^{2} \bigr) = b ^{2} + \frac{a}{b} \vert x \vert - \frac{a}{b} ( b-a ) ^{2} \leq b ^{2} + \frac{a}{b} \vert x \vert \end{aligned}$$

So $y-\operatorname{Im}( z _{2} )$ is an even integer greater than 2ab−2a−2b=2F(a,b), which means that we can write ab+x+iy=z ₂+r ₁(iu+v)+r ₂(u+iv) for non-negative rational integers r _j . □

Lemma 4c

Let x,K,L be as in Lemma 3 with the extra condition that K<a. Then ab+x+iy∈SG _Alg (C) for all y of the opposite parity from $\operatorname{Im} ( z _{1} )$ and satisfying $y>b ^{2} +2ab-2a-2b+ \frac{a}{b} \vert x \vert$.

Proof

We observed earlier that

$$\begin{aligned} \operatorname{Im} ( z _{2} ) =&\operatorname{Im} ( z _{1} ) +p-2Kb \\\operatorname{Im} ( z _{3} ) =&\operatorname{Im} ( z _{1} ) +p-2La \end{aligned}$$

And used this to show that both of these integers had the parity opposite from $\operatorname{Im} ( z _{1} )$. Each number on the following list also has that same parity:

$$ \begin{aligned} &\operatorname{Im} ( z _{2} ),\ \operatorname{Im} ( z _{2} ) +1 ( 2b ),\ \operatorname{Im} ( z _{2} ) +2 ( 2b ),\dots,\operatorname{Im} ( z _{2} ) + ( K-1 ) ( 2b ) \\&\operatorname{Im} ( z _{3} ),\ \operatorname{Im} ( z _{3} ) +1 ( 2b ),\ \operatorname{Im} ( z _{3} ) +2 ( 2b ),\dots,\operatorname{Im} ( z _{3} ) +(a-K-1) (2b) \end{aligned} $$

(3)

We claim that list of numbers contains no two integers with the same remainder class modulo 2a. If two numbers in the same row differed by a multiple of 2a, then we would have 2a|2jb for some positive integer j less than a, which would lead to the contradiction a|j. And if two numbers in different rows differed by a multiple of 2a, then $2a| \operatorname{Im} ( z _{3} ) -\operatorname{Im} ( z _{2} ) +2jb$ for some integer j satisfying 1−K≤j<a−K−1, which in turn implies 2a|2(K+j)b with 0<K+j<a, again leading to a divisibility contradiction. Since list (3) contains representatives of a distinct classes modulo 2a, we have actually shown that it contains exactly one representative from each class sharing the parity of $\operatorname{Im} ( z _{2} )$.

Next we claim that $\operatorname{Im} ( z _{2} ) + ( K-1 ) ( 2b ) <y+2a$. If this were not true, then we can reuse our computation of $\operatorname{Im} ( z _{2} )$ from Lemma 4b to write the inequality $\operatorname{Im} ( z _{2} ) + ( K-1 ) ( 2b ) \geq y+2a$ as

$$b ^{2} + \frac{a}{b} x+K \biggl( \frac{- b ^{2} - a ^{2}}{b} \biggr) +2 a ^{2} + ( K-1 ) 2b> b ^{2} +2ab-2a-2b+ \frac{a}{b} \vert x \vert +2a $$

After cancellations and rearrangements, this becomes

$$K \biggl( \frac{b ^{2} - a ^{2}}{b} \biggr) +2 a ^{2} > 2ab+ \frac{a}{ b} \bigl( \vert x \vert -x \bigr) \geq2ab $$

But we have stipulated that K≤a−1. So this implies

$$(a-1) \biggl( \frac{b ^{2} - a ^{2}}{b} \biggr) +2 a ^{2} > 2ab+ \frac {a}{b} \bigl( \vert x \vert -x \bigr) \geq2ab $$

Multiplying by b and moving everything to the left side gives us

$$- a ^{3} - b ^{2} + a ^{2} +2 a ^{2} b-a b ^{2} >0 $$

This is a fairly complicated expression, but if we take the partial with respect to b, we get

$$\frac{\partial}{\partial b} \bigl( - a ^{3} - b ^{2} + a ^{2} +2 a ^{2} b-a b ^{2} \bigr) =-2b+2 a ^{2} -2ab=-2b+2a ( a-b ) <0 $$

So if we replace each b by a+1, the inequality will still hold

$$- a ^{3} - ( a+1 ) ^{2} + a ^{2} +2 a ^{2} ( a+1 ) -a ( a+1 ) ^{2} >0 $$

But this simplifies to

$$-3a-1>0 $$

which is clearly false. This contradiction proves the claim.

Next we claim that $\operatorname{Im} ( z _{3} ) +(a-K-1)(2b)<y+2a$. If this were not true then we could write

$$-La+Kb+ a ^{2} + b ^{2} + ( a-K-1 ) ( 2b ) > b ^{2} +2ab-2a-2b+ \frac{a}{b} \vert x \vert +2a $$

This can be rewritten as

$$\begin{aligned} &- \frac{a}{b} ( Ka+Lb ) +K \biggl( b+ \frac{a ^{2}}{b} \biggr) + a ^{2} + b ^{2} + ( a-K-1 ) ( 2b ) \\&\quad> b ^{2} +2ab-2a-2b+ \frac{a}{ b} \vert x \vert +2a \\&- \frac{a}{b} ( x+ab ) +K \biggl( b+ \frac{a ^{2}}{b} \biggr) + a ^{2} + b ^{2} + ( a-K-1 ) ( 2b )\\&\quad > b ^{2} +2ab-2a-2b+ \frac{a}{b} \vert x \vert +2a \end{aligned}$$

After cancellations and rearrangements, this becomes

$$0> \frac{a}{b} \bigl( \vert x \vert +x \bigr) +K \biggl( \frac{b ^{2} - a ^{2}}{b} \biggr) \geq K \biggl( \frac{b ^{2} - a ^{2}}{b} \biggr) $$

which is clearly false. This contradiction proves the claim.

With the previous two claims we have actually proven that every member of the list (3) is less than y+2a, because we have compared the largest member of each row separately to y+2a. In particular, there is some member $M=\operatorname{Im} ( z _{j} ) +s(2b)$ from the list that has the same remainder class modulo 2a as y. Therefore, since M<y+2a we must have M≤y, hence y=M+r(2a) for some non-negative rational integer r. Then we have +x+iy=z _j +s(u+iv)+r(iu+v)∈SG _Alg (C). □

Lemmas 4a, 4b and 4c together tell us that every element of the parallelogram P is contained in SG _Alg (C), which in turn shows that $w _{1} + \mathit{SG} _{Geom} ^{0} ( C )$ is contained in SG _Alg (C). By making the replacements u↔iv and v↔iu to reflect through the imaginary axis, we can convert any SG _Alg (C) expression for a point $z \in w _{1} + \mathit{SG} _{Geom} ^{0} ( C )$ into an SG _Alg (C) expression for the corresponding reflected point $- \overline{z} \in w _{2} + \mathit{SG} _{Geom} ^{0} ( C )$. So the entirety of the union $( w _{1} + \mathit{SG} _{Geom} ^{0} ( C ) ) \cup( w _{2} + \mathit{SG} _{Geom} ^{0} ( C ) )$ is contained in SG _Alg (C). It is clear geometrically that for any point z in this union, the translate z+SG _Geom (C) is also contained in the union, hence also in SG _Alg (C). So every point in the union is an element of T(C), and we have explained previously why no point outside the union can be in T(C). This establishes the theorem.

2 General two-coin problem

In this section we provide pictorial evidence for the remaining complexity of the two-coin problem on the Gaussian integers, together with preliminary results which currently guide our continued investigations. These figures were made with a Java program whose source code can be downloaded at http://dutchk.nfshost.com/GaussianFrobeniusPNG.java Each square pixel represents a Gaussian integer. The red pixels indicate the elements of SG _Alg (C), and are correct and complete through the vertical height shown in the diagram.

Example 1

C={1+2i,2+3i}. The sufficient price set has four “downward indentations” with very different shapes, so that minimal union for T(C) involves a combination of open and closed translates. $T ( C ) = ( 7+10i+ \mathit{SG} _{Geom} ^{0} ( C ) ) \cup( 2+7i+ \mathit{SG} _{Geom} ( C ) ) \cup ( 1+6i+ \mathit{SG} _{Geom} ( C ) ) \cup( 0+6i+ \mathit{SG} _{Geom} ^{0} ( C ) ) \cup( -4+4i+ \mathit{SG} _{Geom} ^{0} ( C ) ) \cup( -11+6i+ \mathit{SG} _{Geom} ( C ) ) \cup ( -12+6i+ \mathit{SG} _{Geom} ( C ) )$.

Example 2

C={1+2i,3+2i}. This involves primes split from the same rational primes as in Example 1, but the sufficient price set now has only two downward indentations and is somewhat simpler to describe. $T ( C ) = ( 4+7i+ \mathit{SG} _{Geom} ( C ) ) \cup ( 3+6i+ \mathit{SG} _{Geom} ( C ) ) \cup( 2+6i+ \mathit{SG} _{Geom} ( C ) ) \cup( -4+5i+ \mathit{SG} _{Geom} ^{0} ( C ) )$.

Example 3

C={4+7i,6+7i}. This involves the product of primes split from 5 and 13 in one coin, and 5 and 17 in the other. The region has six separate downward indentations. T(C) is very difficult to describe as a union of open and closed translates.

In order to describe the sets T(C) for diagrams like these we have found it useful to think of the white (non-representable) points as obstructions to the “line of sight” from other points in one of the directions required by SG _Geom (C). For example, in Example 1 the white point −2+7i not only fails to be in T(C) itself, but is also an obstruction keeping many red points below it like −1+5i from being in T(C). You can describe geometrically the locus of points obstructed by any white point z by basing copies of the vectors −v=−2−3i and −iu=2−i at z and considering the infinite downward wedge-shaped region between them, so that algebraically the set of lattice points obstructed by z is Obs _C z={z−w:w∈SG _Geom (C)}. So −1+5i is obstructed because it is in Obs _C (−2+7i). The white point 6i is also an obstruction; however, you can verify that any point obstructed by 6i is already obstructed by −2+7i. Similarly, any point obstructed by 4+9i is also obstructed by 5+11i. The three white points −10+7i, −2+7i and 5+11i are maximal obstructions, in the sense that they are not obstructed by any other white points. Aside from the maximal obstructions, there are also two lines which are important features in the diagram. It is a consequence of Proposition 1 below that every point on either of the lines $L _{+} =\{1+2i+k ( 2+3i ):k \in\mathbb{Z} \}$ and $L _{-} =\{-3+i+k ( -2+i ):k \in\mathbb{Z} \}$ is white. None of the obstructions on L ₊ or L ₋ is maximal, since each is obstructed by the point corresponding to the next higher value of the parameter k. Proposition 1 says that if we choose each of the two coins to avoid a technical internal divisibility condition then two such lines of obstructions are always present in the diagram, and provides a recipe for each of them. Proposition 2 then says that set of maximal obstructions is finite, and Proposition 3 says that knowledge of the two lines and the finite collection of maximal obstructions is sufficient to determine the entirety of the set T(C).

In these propositions we regard Gaussian points as vectors in $\mathbb {Z} ^{2}$ and use “⋅” to denote the scalar dot product of vectors. The condition “rational-prime-free” means that neither of the coins u or v is a rational integer multiple of another Gaussian point. Among other things, this condition together with the non-unit requirement precludes the possibility that either coin is on an axis.

Proposition 1

Let C={u,v} with u, v first quadrant Gaussian integer non-units which are relatively prime and rational-prime-free, and with $\operatorname{arg}(u) >\operatorname{arg}(v)$. Then any (Gaussian) point on either of the lines L ₊={z:z⋅iv=F(u⋅iv,iu⋅iv,iv⋅iv)} and L ₋={z:z⋅u=F(u⋅u,v⋅u,iv⋅u)} is a non-maximal obstruction. Every line of (Gaussian) points parallel to and above one of these lines must contain a point which is not an obstruction.

Proof

We must first establish that the Frobenius numbers referred to in the definitions of these lines are valid. It is algebraically clear that each of the dot products u⋅iv,iu⋅iv,iv⋅iv,u⋅u,v⋅u,iv⋅u is a rational integer. It is also geometrically clear that each of these dot products is positive, because in each case the angle between the two vectors is less than π/2. To show that u⋅iv,iu⋅iv,iv⋅iv are relatively prime as rational integers, we start by observing that the fact that u and v are relatively prime as Gaussian integers means that we can find an expression 1=(A+Bi)u+(C+Di)v with $A,B,C,D \in\mathbb{Z}$. Multiplying through by i gives us i=(Ai−B)u+(Ci−D)v. From this we obtain

$$\begin{aligned} -\operatorname{Im} ( v ) =&1\cdot iv=A ( u\cdot iv ) +B ( iu\cdot iv ) +D(iv \cdot iv) \\\operatorname{Re} ( v ) =&i\cdot iv=A ( iu\cdot iv ) -B ( u\cdot iv ) +C(iv \cdot iv) \end{aligned}$$

Since v is rational-prime-free, the numbers $\operatorname{Im} ( v )$ and $\operatorname{Re} ( v )$ are relatively prime in the rationals and we can find an expression $1=E\operatorname{Re} ( v ) +F\operatorname{Im}(v)$ with $E,F \in\mathbb{Z}$. And this allows us to write

$$1=(-EB-FA) ( u\cdot iv ) +(EA-FB) ( iu\cdot iv ) +(EC-FD) (iv\cdot iv) $$

which shows that u⋅iv,iu⋅iv,iv⋅iv are relatively prime. It is analogous to show that u⋅u,v⋅u,iv⋅u are relatively prime.

Now suppose that z∈L ₊could be represented as z=(e+fi)u+(g+hi)v with e,f,g,h non-negative integers. Then F(u⋅iv,iu⋅iv,iv⋅iv)=z⋅iv=e(u⋅iv)+f(iu⋅iv)+h(iv⋅iv) would express a classical Frobenius number as a non-negative combination of its coin set, which is impossible. This shows that every point on L ₊ is an obstruction, and our comments above show that none of these is maximal. This establishes the claim about points on L ₊, and the claim about L ₋ is proven similarly.

Now let L be a line parallel to and above L ₊. Then for some integer n>F(u⋅iv,iu⋅iv,iv⋅iv) the line can be written L={z:z⋅iv=n}. We can write n=e(u⋅iv)+f(iu⋅iv)+h(iv⋅iv) for some non-negative integers e,f,h. The point z=(e+fi)u+(hi)v is a non-obstruction on the line L. It is analogous to show that a line parallel to and above L ₋ contains a non-obstruction. □

We comment here that for any Gaussian point z the ordered pair (z⋅iv,z⋅u) uniquely specifies z as the intersection of a particular line parallel to L ₊ and a particular line parallel to L ₋. This allows us to describe elements of z+SG _Geom (C) as those points z′ with z′⋅iv≥z⋅iv and z′⋅u≥z⋅u. We use this condition repeatedly in Proposition 3 below.

Proposition 2

Let C={u,v} with u, v Gaussian integer non-units which are relatively prime and rational-prime-free, and with $\operatorname{arg}(u) > \operatorname{arg}(v)$. Then the set of maximal obstructions is finite.

Proof

Choose w from the non-empty set T(C). We know that w must be above the line L ₊, since otherwise the translate w+SG _Geom (C) would intersect L ₊ in a point which by Proposition 1 would obstruct w and prevent w from being in T(C). Similarly, w must be above the line L ₋.

There are only finitely many lines parallel to and above L ₊ but below w. Similarly, there are only finitely many lines parallel to and above L ₋ but below w. Every maximal obstruction must lie on one of these lines, since points below L ₊ or L ₋ are obstructed, and points above all these lines would be in w+SG _Geom (C). And none of these lines can contain more than one maximal obstruction, since the difference of two points on a line parallel to L ₊ differ by an integer multiple of v so that if both were white one would obstruct the other, and the difference of two points on a line parallel to L ₋ differ by an integer multiple of iu so that again if both were white one would obstruct the other. □

Proposition 3

Let C={u,v} with u, v Gaussian integer non-units which are relatively prime and rational-prime-free, and with $\operatorname{arg}(u) > \operatorname{arg}(v)$. Any point z which is obstructed must satisfy at least one of the three conditions: (1) z is on or below L ₊, (2) z is on or below L ₋, or (3) z is obstructed by a maximal obstruction.

Proof

Suppose that z is an obstructed point that does not satisfy condition 1, 2 or 3. Then z⋅iv>F(u⋅iv,iu⋅iv,iv⋅iv), and z⋅u>F(u⋅u,v⋅u,iv⋅u). Let z ₁ be a white point that obstructs z. Then z ₁⋅iv≥z⋅iv and z ₁⋅u≥z⋅u, and at least one of these inequalities is strict. This shows that z ₁ cannot satisfy condition 1 or condition 2, and we know that z ₁ cannot satisfy condition 3 since z doesn’t. Since z ₁ is itself not maximal, we know that z ₁ must be obstructed. Let z ₂ be a white point that obstructs z ₁. Then once again z ₂ is an obstructed point that does not satisfy condition 1, 2 or 3. We can continue in this way to obtain an infinite sequence z ₀=z,z ₁,z ₂,z ₃,… of points with z _n+1 obstructing z _n for all n. This tells us that for each n the inequalities z _n+1⋅iv≥z _n ⋅iv and z _n+1⋅u≥z _n ⋅u are both true, and at least one of these inequalities is strict.

Choose w∈T(C). There can be no n for which both z _n ⋅iv≥w⋅iv and z _n ⋅u≥w⋅u are true, since then z _n ∈w+SG _Geom (C), which would contradict the fact that z _n is white. So one of the non-decreasing sequences {z _n ⋅iv} _n≥1 or {z _n ⋅u} _n≥1 must eventually be constant, while the other continues to grow without bound. This tells us that for some N all the points z _N ,z _N+1,z _N+2,… are on a line L parallel to and above either L ₊ or L ₋. Proposition 1 tells us that there is a non-obstruction z ^∗ on L.

If L is parallel to L ₊, then the sequence {z _n ⋅iv} _n≥N is constant with value z ^∗⋅iv while the sequence {z _n ⋅u} _n≥N increases with bound to eventually surpass z ^∗⋅u, so that eventually from the sequence of points z _N ,z _N+1,z _N+2,… there is a point z _M which is on L and in the set z ^∗+SG _Geom (C). This means that z _M =z ^∗+kv for some non-negative integer k. But this contradicts the fact that z ^∗ is representable and z _M is not. A similar contradiction results if L is parallel to L ₋. □

So in this situation the set T(C) can be constructed by starting with the upward wedge of points above both L ₊ and L ₋, and removing the downward wedges of points obstructed by each of the maximal obstructions. This is analogous to the standard method for recovering the entirety of the gap set G(S) for a numerical subgroup from the set of fundamental gaps FG(S) and a finite list A of generators by writing $G ( S ) = \{ x- \sum_{a\in A} k _{a} a:x\in\mathit{FG} ( S ),k _{a} \in\mathbb{N} \} \cap \mathbb{N}$. However, in the current situation we are not just trying to find the gaps (obstructions) but also all non-gaps that are disqualified from being sufficient by virtue of being obstructed. So instead of subtracting back via finite sums of generators, we need to subtract back via all possible elements of the geometric semigroup. This leads to the “formula” T(C)={z:z is above both L ₊ and L ₋}∖{x−g:x is a maximal obstruction,g∈SG _Geom (C)} where the backslash designates set difference. Any progress on finding the maximal obstructions would be very useful.

If u or v is not rational-prime-free, a modified version of Proposition 1 is still true. The proof is nearly the same as before.

Proposition 1′

Let C={u,v} with u, v Gaussian integer non-units which are relatively prime and neither purely real or purely imaginary, with $\operatorname{arg}(u) >\operatorname{arg}(v)$. Define $\tilde{u} =u/ \mathrm{gcd} (\operatorname{Re} ( u ),\operatorname{Im} ( u ) )$ and $\tilde{v} =v/ \mathrm{gcd} (\operatorname{Re} ( v ),\operatorname{Im} ( v ) )$. Then any (Gaussian) point on either of the lines $L _{+} =\{z:z\cdot i \tilde{v} =F(u\cdot i \tilde{v},iu\cdot i \tilde{v},iv\cdot i \tilde{v} )\}$ and $L _{-} =\{ z:z\cdot\tilde{u} =F(u\cdot\tilde{u},v\cdot\tilde {u},iv\cdot\tilde{u} )\}$ is a non-maximal obstruction. Every line of (Gaussian) points parallel to and above one of these lines must contain a point which is not an obstruction.

With the same modification to the definitions of L ₊ and L ₋, Proposition 2 is still true although the proof has to be modified to allow that there may be multiple (but only finitely many) maximal obstructions on each of the specified parallel lines. However, the direct analog of Proposition 3 will often fail, as seen in the following example.

Example 4

C={2+3i,3+3i}. In this example, the lines $L _{+} =\{1+k ( 1+i ):k \in\mathbb{Z}\}$ and $L _{-} =\{-2+9i+k ( -3+2i ):k \in\mathbb{Z}\}$ appear as the fully white boundary lines. However, parallel to and above L ₊ are a series of “perforated lines” which each eventually have a stable recurring pattern of red and white points continuing upward forever.

It seems certain that a modification can be made to Proposition 3 which will incorporate this additional feature. If we use the notation L ₊(n) and L ₋(n) to designate the lines parallel to and n units above L ₊ and L ₋ respectively, then here is a conjectural idea of how that modified result might be worded

(Conjectural) Proposition 3′

Let C={u,v} with u, v Gaussian integer non-units which are relatively prime and neither purely real or purely imaginary, with $\operatorname{arg}(u) > \operatorname{arg}(v)$. Any point z which is obstructed must satisfy at least one of the three conditions: (1) z is on or below L ₊(n ₊), (2) z is on or below L ₋(n ₋), or (3) z is obstructed by a maximal obstruction.

The numbers n ₊ and n ₋ in this proposition would need to be found in terms of u and v, and some method for finding the set of maximal obstructions would still need to be found, in order for these results to have any value to us in helping to determine the set T(C). So there are multiple lines of attack on this problem open for further research.