NTIC <em xmlns:svg="http://www.w3.org/2000/svg" class="emphasis">Positive</em> Integer Lattice Points

Section 3.3 Positive Integer Lattice Points

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

Question 3.3.1.

Assume there exists a solution (hence infinitely many) to $a x + b y = c .$ How many such solution pairs $(x, y)$ have $x$ and $y$ both positive?

🔗

This is similar to the conductor question. It is closely related to integer programming, something with industrial applications.

Positive solutions to $3x+2y=10$ — 🔗
Figure 3.3.2. Positive solutions to $3 x + 2 y = 10$

xxxxxxxxxx
 
@interact
def _(a=slider(1,20,1,1), b=slider(1,20,1,1), c=slider(1,20,1,4)):
    ym = c/b + 1
    xm = c/a + 1
    p = plot(-(a/b)*x+c/b,-1,xm, plot_points = 200)
    lattice_pts = [[i,j] for i in [0..xm] for j in [0..ym]]
    plot_lattice_pts = points(lattice_pts,rgbcolor=(0,0,0), pointsize=2)
    if mod(c,gcd(a,b))==0:
        line_pts = [coords for coords in lattice_pts if (coords[0]>0) and (coords[1]>0) and (a*coords[0]+b*coords[1]==c)]
        if len(line_pts)==0:
            pretty_print(html( 'Solutions to $%sx+%sy=%s$:'%(str(a),str(b),str(c))))
            pretty_print(html( 'No positive lattice points at all!'))
            show(p+plot_lattice_pts, figsize = [5,5], xmin = 0, xmax = xm, ymin = 0, ymax = ym)
        else:
            plot_line_pts = points(line_pts, rgbcolor = (0,0,1), pointsize=20)
            pretty_print(html('Solutions to $%sx+%sy=%s$:'%(str(a),str(b),str(c))))
            pretty_print(html('Number of positive lattice points = ' + str(len(line_pts))))
            show(p+plot_lattice_pts+plot_line_pts, figsize = [5,5], xmin = 0, xmax = xm, ymin = 0, ymax = ym)
    else:
        pretty_print(html('Solutions to $%sx+%sy=%s$:'%(str(a),str(b),str(c))))
        pretty_print(html('No positive lattice points at all!'))
        show(p+plot_lattice_pts, figsize = [5,5], xmin = 0, xmax = xm, ymin = 0, ymax = ym)

🔗

Let's explore this. How many such points are there in the following cases? Draw pictures by hand, or use the interact above.

$x + y = 4,$ $x + y = 5,$ $x + y = 6,$ $\dots$
$2 x + y = 4,$ $2 x + y = 5,$ $2 x + y = 6,$ $\dots$
$2 x + 2 y = 4,$ $2 x + 2 y = 5,$ $2 x + 2 y = 6,$ $\dots$
$3 x + y = 4,$ $3 x + y = 5,$ $3 x + y = 6,$ $\dots$

🔗

Can you get any good conjectures?

🔗

Subsection 3.3.1 Solution ideas

🔗

If you think about the question a little more carefully together with the picture, you may realize that we are really asking about how many integer lattice points lie between the intercepts. So one way to think about an answer would involve the distance between solutions.

🔗

To be concrete, let's assume that the equation is

a x + b y = c,

and

gcd (a, b) = 1 .

Then, using our 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, by the Pythagorean Theorem,

\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{(\frac{c}{a})^{2} + (\frac{c}{b})^{2}} = \frac{c}{a b} \sqrt{a^{2} + b^{2}} .$
The ratio of this total length and the length between solutions is thus $\frac{c}{a b} .$

🔗

That's a nice pat answer. There are two problems with it, though!

There is no guarantee that $\frac{c}{a b}$ is an integer! In fact, it usually won't be. For instance, with $2 x + 3 y = 10,$ $\frac{10}{2 \cdot 3} \approx 1.67 .$ So should the number of points be bigger than or less than this?
Secondly, even so it's not clear what the precise connection between $\frac{c}{a b}$ and the actual number of points is. $2 x + 3 y = 5$ has one, and $2 x + 3 y = 7$ has one, but $2 x + 3 y = 6$ doesn't. Yet $\frac{c}{a b}$ is about equal to 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 situations.

🔗

Subsection 3.3.2 Toward the full solution

🔗

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

🔗

Definition 3.3.3. Greatest integer function.

The greatest integer function (also called the floor function) is the function which takes a real number $x$ and returns the largest integer below it (or equal to it). We notate it $⌊ x ⌋ .$

🔗

Example 3.3.4.

A few examples should suffice to understand it:

⌊ 1.5 ⌋ = 1, ⌊ 1 ⌋ = 1, ⌊ 1.99 ⌋ = 1, ⌊ 0.99 ⌋ = 0, ⌊ - .01 ⌋ = - 1 .

🔗

Now let's use this to rectify our problems.

To take care of the integer problem, we will just consider $n = ⌊ \frac{c}{a b} ⌋,$ the greatest integer function applied to $\frac{c}{a b} .$
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).

🔗

Rather than give a general formula, we examine individual cases to show what to expect. This applet can help supplement trying it by hand.

xxxxxxxxxx
 
@interact
def _(c=[5..12]):
    a = 2
    b = 3
    ym = c/b + 1
    xm = c/a + 1
    p = plot(-(a/b)*x+c/b,-1,xm, plot_points = 200)
    lattice_pts = [[i,j] for i in [0..xm] for j in [0..ym]]
    plot_lattice_pts = points(lattice_pts,rgbcolor=(0,0,0),pointsize=2)
    if mod(c,gcd(a,b))==0:
        line_pts = [coords for coords in lattice_pts if (coords[0]>0) and (coords[1]>0) and (a*coords[0]+b*coords[1]==c)]
        if len(line_pts)==0:
            pretty_print(html('Solutions to $%sx+%sy=%s$:'%(str(a),str(b),str(c))))
            pretty_print(html('No positive lattice points at all!'))
            show(p+plot_lattice_pts, figsize = [5,5], xmin = 0, xmax = xm, ymin = 0, ymax = ym)
        else:
            plot_line_pts = points(line_pts, rgbcolor = (0,0,1),pointsize=20)
            pretty_print(html('Solutions to $%sx+%sy=%s$:'%(str(a),str(b),str(c))))
            pretty_print(html('Number of positive lattice points = ' + str(len(line_pts))))
            show(p+plot_lattice_pts+plot_line_pts, figsize = [5,5], xmin = 0, xmax = xm, ymin = 0, ymax = ym)
    else:
        pretty_print(html('Solutions to $%sx+%sy=%s$:'%(str(a),str(b),str(c))))
        pretty_print(html('No positive lattice points at all!'))
        show(p+plot_lattice_pts, figsize = [5,5], xmin = 0, xmax = xm, ymin = 0, ymax = ym)

🔗

Let's focus on the case where

a, b > 0

are relatively prime, such as in the graphic with

2 x + 3 y = c

for various

c .

Naturally, if

c < 6

in this specific example, then

n = ⌊ \frac{c}{a b} ⌋ = 0,

so one might not expect many points. What about in general?

The easiest case is when just one of the intercepts is a lattice point. 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 the formula is just plain old

$n = ⌊ \frac{c}{a b} ⌋ .$

This will happen (where $n = 1$ ) with $2 x + 3 y = 8$ (or $9$ or $10$ ), for instance.
If neither $c / a$ nor $c / b$ is an integer, then you could get $n$ or $n + 1$ lattice points. There's no nice formula beyond this, and often examples will be like $2 x + 3 y = 7$ with just one lattice point as ‘expected’. When the extra point ‘fits’ is in examples like the case $2 x + 3 y = 11,$ where we have $\frac{11}{2 \cdot 3} - ⌊ \frac{11}{2 \cdot 3} ⌋$ very close to one, and you do get $⌊ \frac{11}{2 \cdot 3} ⌋ + 1 = 2$ positive lattice points here.
Finally, it's also possible for ‘not enough’ lattice points to fit; for example, $2 x + 3 y = 12$ jumps back down to $⌊ \frac{12}{2 \cdot 3} ⌋ - 1 = 1$ points! This situation (not reaching $n$ points) can occur when both the $x$ - and $y$ -intercepts actually are lattice points, because the intercepts by definition do not have positive coordinates. So if $c / a$ and $c / b$ are both integers, then we get precisely

$n - 1 = ⌊ \frac{c}{a b} ⌋ - 1$

lattice points.

🔗

As a side note, the number of points not being a monotone nonincreasing function of

c

should always be expected when

c

transitions to being a multiple of

a b,

such as also from

2 x + 3 y = 5

2 x + 3 y = 6 .

In fact, since the closest solution to the origin of

a x + b y = - 1

must be no more than one half the usual distance

\sqrt{a^{2} + b^{2}}

away (cf. also [E.7.21]), all (positive) solutions of

a x + b y = k a b

will yield (positive) solutions to

a x + b y = k a b - 1,

as will one of the intercepts. See Exercise 3.6.24 to fill in the details.

🔗

The excellent book The Geometry of Numbers [E.4.16, Section 2.2] gives many more details. For instance, 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?