Section3.3Positive Integer Lattice Points

Now that we have the geometric viewpoint, here is a more subtle question:

How many such solution pairs \((x,y)\) to \(ax+by=c\) have \(x\) and \(y\) both positive?

This is similar to the conductor question; it turns out that this is related to integer programming, something with industrial applications.

Let's explore this. How many such points are there in the following cases?

  • \(x+y=4\), \(x+y=5\), \(x+y=6\), \(\ldots\)
  • \(2x+y=4\), \(2x+y=5\), \(2x+y=6\), \(\ldots\)
  • \(2x+2y=4\), \(2x+2y=5\), \(2x+2y=6\), \(\ldots\)
  • \(3x+y=4\), \(3x+y=5\), \(3x+y=6\), \(\ldots\)
Can you get any good conjectures?

Note that what we are really asking is how many integer lattice points lie between the intercepts.

Subsection3.3.1Solution Ideas

One way to think about this is the distance between solutions. Let's assume that the equation is \(ax+by=c\), and \(gcd(a,b)=1\). Then, using out technique from last time, from the solution \((x_0,y_0)\) we get a new solution \((x_0+b,y_0-a)\), so the distance between any two solutions is \[\sqrt{[(x_0+b)-x_0]^2+[(y_0-a)+y_0]^2}=\sqrt{a^2+b^2}\, .\] Our strategy is to ask:

  • How many times does that distance fit between the intercepts of the line?
Does that strategy make sense? It doesn't give an exact answer, but should give a good ballpark estimate.

Let's calculate these things. You may want to follow it \(a=3\), \(b=2\), \(c=4\).

  • The intercepts are \(\frac{c}{a}\) and \(\frac{c}{b}\), respectively.
  • Using the Pythagorean Theorem again, we see that the whole length available is \[\sqrt{\Big(\frac{c}{a}\Big)^2+\Big(\frac{c}{b}\Big)^2}=\frac{c}{ab}\sqrt{a^2+b^2}\, .\]
  • The ratio of this total length and the length between solutions is thus \(\frac{c}{ab}\),
That's a nice pat answer.

There are two problems with it, though!

  1. There is no guarantee that \(\frac{c}{ab}\) is an integer! In fact, it usually won't be. For instance, with \(2x+3y=10\), \(\frac{10}{2\cdot 3}\approx 1.67\). So should the number of points be bigger than or less than this?
  2. Secondly, even so it's not clear what the precise connection between \(\frac{c}{ab}\) and the actual number of points is. \(2x+3y=5\) has one, and \(2x+3y=7\) has one, but \(2x+3y=6\) doesn't - even though \(\frac{c}{ab}\) is about one for all three of these. In fact, the number of points is thus not even monotone increasing with respect to \(c\) increasing, which is rather counterintuitive.
We will have to deal with each of these.

Subsection3.3.2Toward the full solution

We can deal with each of these problems. To do so, we introduce a new function:

  • The greatest integer function (also called the floor function) is the function which takes a real number \(x\) and returns the next integer below it (or equal to it).
  • We notate it \(\lfloor x\rfloor\).
  • Examples should suffice to understand it: \[\lfloor 1.5\rfloor=1\; , \lfloor 1\rfloor=1\; ,\lfloor 1.99\rfloor=1\; ,\lfloor 0.99\rfloor=0\; ,\lfloor -.01\rfloor=-1\; .\]
Now let's use this to rectify our problems.

  1. To take care of the integer problem, we will just consider \(n=\left\lfloor \frac{c}{ab}\right\rfloor\), the greatest integer function applied to \(\frac{c}{ab}\).
  2. Secondly, we simply recognize that there isn't a nice formula. On average, we should expect \(n\) lengths between integer points along the line segment in question (and hence as many as \(n+1\) lattice points, since a partition of \(n\) intervals has \(n+1\) endpoints associated to it).

Subsubsection3.3.2.1Positive integer points

Rather than give a general case, we examine individual cases to show what to expect. This applet helps.

Let's focus on the case where \(a\) and \(b\) are relatively prime.

  1. How could the fewest of these appear? That's when both the \(x\)- and \(y\)-intercepts are actually lattice points, because they do not have positive coordinates. So if \(c/a\) and \(c/b\) are both integers, then we get precisely \[n-1=\left\lfloor \frac{c}{ab}\right\rfloor-1\] lattice points. This is the transition between \(2x+3y=5\) to \(2x+3y=6\).
  2. What if just one of the intercepts is a lattice point? Then, beginning at that point, there is definitely room for the full \(n\) lengths to appear - and you're guaranteed to get \(n\) lattice points, because we just said the other intercept isn't a lattice point, so the \(n\)th one must appear before that point. So here the formula is just plain old \[n=\left\lfloor \frac{c}{ab}\right\rfloor\; .\] Compare \(2x+3y=8\) and \(2x+3y=9\) to the others above.
  3. Finally, if neither \(c/a\) nor \(c/b\) is an integer, then you get \(n\) or \(n+1\) lattice points (remember, \(n=\left\lfloor \frac{c}{ab}\right\rfloor\)). There's no nice formula for this otherwise; but notice that with \(2x+3y=11\) you do get \(\left\lfloor \frac{11}{2\cdot 3}\right\rfloor+1=2\) positive lattice points! (And it jumps back down to \(\left\lfloor\frac{12}{2\cdot 3}\right\rfloor-1=1\) at \(c=12\)!
That was all for \(a\) and \(b\) relatively prime.

If \(gcd(a,b)\neq 1\), it is not too hard to show that any such line with respect to lattice points is the same as a line \(a'x+b'y=c'\) for which \(gcd(a',b')=1\). Which line would that be?