:tocdepth: 2

.. _frobenius_number:

Rethinking Problems 
============================================================================

.. contents:: :local:

.. highlight:: python




In experimental science, sometimes you have to rethink your problem.
 Perhaps a different experiment is needed, perhaps a different model, or
something else. Likewise, in experimental mathematics, sometimes it is
necessary to use a different approach.  We will look at one such
approach today; we will turn questions about numbers into questions
about geometry. Also, I know that some of you are excited to use more
Sage for your computation outside of this class, so we will take a
little time looking at resources.

Reviewing the Problem
---------------------

Our motivational problem is the following: Given positive integers
:math:`a` and :math:`b`, what numbers :math:`n` can be written in the
form :math:`ax+by`, where :math:`x,y\geq 0, \in \mathbb{Z}`?

It has already led to several related questions.  That is exploration!

Is there a number :math:`N` for which all :math:`n\geq N` can be written
:math:`ax+by`, but :math:`N-1` cannot be?  (We called this the
*conductor*.)

If there is such a number, can we find a formula or some other means of
computing it? How *many* numbers can be written :math:`ax+by`, if we
know :math:`a,b`? Remember, you can definitely try to organize your
data.  Did anyone get these results?

.. code:: ipython2

    L = [[(2,3), 1, 2], [(3, 4), 5, 6], [(3,6), oo, 'None'], [(5,7), 23, 24], [(7,11), 59, 60], [(9,11), 79, 80] ]
    
    table(L,header_row=["$(a,b)$",'Frobenius Number', 'Conductor', '# Not Writable'], frame=True)




.. raw:: html

    <div class="notruncate">
    <table border="1" class="table_form">
    <tbody>
    <tr>
    <th><script type="math/tex">(a,b)</script></th>
    <th>Frobenius Number</th>
    <th>Conductor</th>
    <th># Not Writable</th>
    </tr>
    <tr class ="row-a">
    <td><script type="math/tex">\left(2, 3\right)</script></td>
    <td><script type="math/tex">1</script></td>
    <td><script type="math/tex">2</script></td>
    </tr>
    <tr class ="row-b">
    <td><script type="math/tex">\left(3, 4\right)</script></td>
    <td><script type="math/tex">5</script></td>
    <td><script type="math/tex">6</script></td>
    </tr>
    <tr class ="row-a">
    <td><script type="math/tex">\left(3, 6\right)</script></td>
    <td><script type="math/tex">+\infty</script></td>
    <td>None</td>
    </tr>
    <tr class ="row-b">
    <td><script type="math/tex">\left(5, 7\right)</script></td>
    <td><script type="math/tex">23</script></td>
    <td><script type="math/tex">24</script></td>
    </tr>
    <tr class ="row-a">
    <td><script type="math/tex">\left(7, 11\right)</script></td>
    <td><script type="math/tex">59</script></td>
    <td><script type="math/tex">60</script></td>
    </tr>
    <tr class ="row-b">
    <td><script type="math/tex">\left(9, 11\right)</script></td>
    <td><script type="math/tex">79</script></td>
    <td><script type="math/tex">80</script></td>
    </tr>
    </tbody>
    </table>
    </div>




Let us work out by counting the numbers that are not writable. Let’s
start with :math:`a=2`, :math:`b=3` and :math:`a=3`, :math:`b=4`.


A Useful Fact


Recall that we discussed a few facts about integers earlier.



Fact: If :math:`a`, :math:`b>0` are integers then we can write
:math:`a=qb+r` with :math:`0\leq r<b` and :math:`q` integers.



Fact: In this situation, :math:`\gcd(a,b)=\gcd(b,r)`.


Here is another useful fact for our situation.  Many of you already know
this.


Fact: For a given :math:`n\in \mathbb{Z}`, the equation :math:`ax+by=n`
has a solution in integers if and only if :math:`\gcd(a,b) \mid n`.



That is, you can’t even write :math:`ax+by=n` if the greatest common
divisor of :math:`a` and :math:`b` doesn’t divide :math:`n`.  This was
studied by the Greeks, known by Aryabhata in the Indian Middle Ages, and
rediscovered by Bachet de Méziriac about 1600.



Implication For Us: If :math:`a` and :math:`b` have a common divisor
bigger than 1, there cannot be a conductor.


We already saw an example in class. I want you to think about why this
might be.


Rethinking the Problem


I can prove the facts above.  But just proving things are true and using
them isn’t enough.  Why is it true, intuitively?  I believe the right
place to do this is in geometry.

.. raw:: html

   </p>

.. code:: ipython2

    @interact
    def _(a = slider(1, 20, 1, 3), b = slider(1, 20, 1, 4), c = slider(1, 30, 1, 6), viewsize = slider(5, 30, 1, 5)):
        
        # plot the equation of the line `y = - (a/b)*x + c/b`.
        
        p = plot(-(a/b) * x + c/b, (x, -1, viewsize), plot_points = 200)
        
        # integer coordiantes for the lattice 
        
        lattice_pts = [[i,j] for i in [-1..viewsize] for j in [-viewsize..viewsize]]
        
        # plot integer lattice with pointsize set to 2 and rgbcolor set to (0, 0, 0).
        
        plot_lattice_pts = points(lattice_pts, rgbcolor = (0, 0, 0), pointsize = 20)
        
        # Check if gcd(a, b) divides c. 
        
        if mod(c, gcd(a, b)) == 0:
            
            # Get integers x and y in lattice_pts that lies on the line `y = - (a/b)*x + c/b`. 
            # These are integers that satisfy the equation a * x + b * y = c.
            
            line_pts = [coords for coords in lattice_pts if a * coords[0] + b * coords[1] == c]
            
            # Check if line_pts is empty. In other words, there are no integer points x and y in lattice_pts 
            # that lies on the line y = - (a/b)*x + c/b or satisfies the equation a * x + b * y = c. Note that
            # in general, this in effect that not mean that there are no solution since there might exist 
            # integer pairs which are not in lattice_pts. 
            
            if line_pts == []:
                
                # Define an empty Graphics object.
                
                plot_line_pts = Graphics()
                
            else:
                
                # plot the integer points x and y in lattice_pts that lies on the line y = - (a/b)*x + c/b or 
                # satisfies the equation a * x + b * y = c.
                 
                plot_line_pts = points(line_pts, rgbcolor = (0, 0, 1), pointsize = 20)
                
            # Print sentence indicating the set of solution, (integer points) satisfying the equation.
            
            pretty_print(html("Showing solutions to $%s\,x + %s\,y = %s$ in this viewing window" %(str(a), str(b), str(c))))
            
            # Combine the three plot objects together. 
            
            show(p + plot_lattice_pts + plot_line_pts, figsize=[5, 5], xmin = -1, xmax = viewsize, ymin = -1, ymax = viewsize)
            
        # If gcd(a, b) does not divide c.
        
        else:
            
            # Print a sentence stating the gcd(a,b) does not divide c.
            
            pretty_print(html("The gcd of $%s$ and $%s$ is $%s$, which does not divide $%s$," %(str(a), str(b), str(gcd(a,b)), str(c))))
            
            # Print a sentence stating that there are no integer solutions satisfying the equation 
            
            pretty_print(html("so there are no non-negative integer solutions to $%s\,x + %s\,y = %s$" %(str(a), str(b), str(c))))
            
            # Combine plot objects.
            
            show(p + plot_lattice_pts, figsize = [5, 5], xmin = -1, xmax = viewsize, ymin = -1, ymax = viewsize)



.. raw:: html

    Showing solutions to <script type="math/tex">3\,x + 4\,y = 6</script> in this viewing window



.. image:: ./images/output_7_1.png


.. raw:: html

   <p>

(The little gray dots in the graph above are called the integer lattice.
 You may treat this as a definition.  There are many lattices, but only
one which is basically all the intersections of :math:`y=m,x=n` for all
integers :math:`m,n`.  So for instance :math:`(-2,3)` is probably
visible; however, note that :math:`(-1,1/2)` is not a little dot,
because it doesn’t have integer values.)

.. raw:: html

   </p>

.. raw:: html

   <p>

Since :math:`ax+by=c` may be thought of as a line (in fact, the line

.. math:: y=-\frac{a}{b}x+\frac{c}{b}

\ with slope :math:`-\frac{a}{b}`), we now have a completely different
interpretation of this very basic number theory question (the “linear
Diophantine equation”).  It is simply asking, “When (for what :math:`a`,
:math:`b`, :math:`c` combinations) does the line hit this lattice?  If
it does, can you tell me all intersections?”   If you play around with
the sliders you will quickly see that things work out just as promised
in the theorems. 

.. raw:: html

   </p>

.. raw:: html

   <p>

Now let’s connect this to some of the conductor questions. Given
positive integers :math:`a` and :math:`b`:

.. raw:: html

   </p>

.. raw:: html

   <ul>

.. raw:: html

   <li>

How many ways are there to write :math:`n` as :math:`ax+by`, given
:math:`n`?

.. raw:: html

   <ul>

.. raw:: html

   <li>

How many lattice points (including the axes) hit this line, given
:math:`n`?

.. raw:: html

   </li>

.. raw:: html

   </ul>

.. raw:: html

   </li>

.. raw:: html

   <li>

How is the problem different if we only allow positive :math:`x` and
:math:`y` not just nonnegative?

.. raw:: html

   <ul>

.. raw:: html

   <li>

How does the problem change if we do not allow the axes to be included?

.. raw:: html

   </li>

.. raw:: html

   </ul>

.. raw:: html

   </li>

.. raw:: html

   </ul>

.. raw:: html

   <div>

By the way, this second question is very closely related to an extremely
applied area, integer programming.

.. raw:: html

   </div>

.. code:: ipython2

    @interact
    def _(a = slider(1, 20, 1, 3), b = slider(1, 20, 1, 4), c = slider(1, 40, 1, 4), viewsize = slider(5, 30, 1, 5), positive_only = False):
        
        ym = c/b + 1    # ym is the value of ymax
        xm = c/a + 1    # xm is the value of xmax
        
        # plot the equation of the line `y = - (a/b)*x + c/b`.
        
        p = plot(-(a/b) * x + c/b, -1, xm, plot_points = 200)
        
        # integer coordiantes for the lattice
        
        lattice_pts = [[i,j] for i in [0..xm] for j in [0..ym]]
        
        # plot integer lattice
        
        plot_lattice_pts = points(lattice_pts, rgbcolor = (0, 0, 0), pointsize = 2)
        
        # Check if gcd(a, b) divides c.
        
        if mod(c, gcd(a, b)) == 0:
            
            # If the parameter positive_only is True. That is, find positive x and y such that `a*x + b*y = c` holds.
            
            if positive_only:
                
                # Get positive integers x and y in lattice_pts that lies on the line `y = - (a/b)*x + c/b`. 
                # These are positive integers that satisfy the equation `a * x + b * y = c`.
                
                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 the parameter positive_only is False. That is, find non-negative x and y such that `a*x + b*y = c` holds.
            
            else:
                
                # Get non-negative integers x and y in lattice_pts that lies on the line `y = - (a/b)*x + c/b`. 
                # These are non-negative integers that satisfy the equation a * x + b * y = c.
                
                line_pts = [coords for coords in lattice_pts if (coords[0] >= 0) and (coords[1] >= 0) and (a * coords[0] + b * coords[1] == c)]
                
            # Check if line_pts is empty. In other words, there are no non-negative integer points x and y in lattice_pts 
            # that lies on the line y = - (a/b)*x + c/b or satisfies the equation a * x + b * y = c. Note that in general,
            # this in effect does not mean that there are no solution since there might exist integer pairs which are not 
            # in lattice_pts.
                
            if len(line_pts) == 0:
                
                # Print solutions
                
                pretty_print(html('Solutions to $%s\,x + %s\,y = %s$:' %(str(a), str(b), str(c))))
                
                # If the parameter positive_only is True
                
                if positive_only:
                    
                    # Print no positive solution. 
                    
                    pretty_print(html('No positive lattice points at all!'))
                    
                # If the parameter positive_only is False
                    
                else:
                    
                    # Print sentence 
                    
                    pretty_print(html('No nonnegative lattice points at all!'))
                    
                # Combine the two plot objects together.
                    
                show(p + plot_lattice_pts, figsize = [5,5], xmin = 0, xmax = xm, ymin = 0, ymax = ym)
                
            else:
                
                # plot the integer points x and y in lattice_pts that lies on the line y = - (a/b)*x + c/b or 
                # satisfies the equation a * x + b * y = c.
                
                plot_line_pts = points(line_pts, rgbcolor = (0, 0, 1), pointsize = 20)
                  
                pretty_print(html('Solutions to $%s\,x + %s\,y = %s$:' %(str(a), str(b), str(c))))
                
                # If the parameter positive_only is True 
                
                if positive_only:
                    
                    # Print sentence with positive integer solutions x and y in lattice_pts.
                    
                    pretty_print(html('Number of positive lattice points = ' + str(len(line_pts))))
                    
                # If the parameter positive_only is False
                    
                else:
                    
                    # Print sentence with non-negative integer solutions x and y in lattice_pts.
                    
                    pretty_print(html('Number of nonnegative lattice points = ' + str(len(line_pts))))
                    
                # Combine the three plot objects together.
                    
                show(p + plot_lattice_pts + plot_line_pts, figsize = [5,5], xmin = 0, xmax = xm, ymin = 0, ymax = ym)
                
        # If gcd(a, b) does not divide c.
         
        else:
            
            # Print solutions.
            
            pretty_print(html('Solutions to $%s\,x + %s\,y = %s$:' %(str(a), str(b), str(c))))
            
            # If the parameter positive_only is True
            
            if positive_only:
                
                # Print no positive integer solutions.
                
                pretty_print(html('No positive lattice points at all!'))
                
            else:
                
                 # Print no non-negative integer solutions.
                
                pretty_print(html('No nonnegative lattice points at all!'))
                
            # Combine the two plot objects together.
                
            show(p + plot_lattice_pts, figsize = [5,5], xmin = 0, xmax = xm, ymin = 0, ymax = ym)



.. raw:: html

    Solutions to <script type="math/tex">3\,x + 4\,y = 4</script>:



.. raw:: html

    Number of nonnegative lattice points = 1



.. image:: ./images/output_9_2.png


.. raw:: html

   <p>

Let’s explore this - even in cases where the conductor is not very
interesting.  How many such points are there in the following cases?

.. raw:: html

   </p>

.. raw:: html

   <ul>

.. raw:: html

   <li>

:math:`x+y=4`, \ :math:`x+y=5`, \ :math:`x+y=6`, :math:`\ldots`

.. raw:: html

   </li>

.. raw:: html

   <li>

:math:`2x+y=4`, \ :math:`2x+y=5`, \ :math:`2x+y=6`, :math:`\ldots`

.. raw:: html

   </li>

.. raw:: html

   <li>

:math:`2x+2y=4`, \ :math:`2x+2y=5`, \ :math:`2x+2y=6`, :math:`\ldots`

.. raw:: html

   </li>

.. raw:: html

   <li>

:math:`3x+y=4`, \ :math:`3x+y=5`, \ :math:`3x+y=6`, :math:`\ldots`

.. raw:: html

   </li>

.. raw:: html

   </ul>

.. raw:: html

   <p>

Again, you should be able to start exploring and experimenting.
 Naturally, in this case I don’t only expect you to use my graphic,
which is a big challenge for you to program right now.  Try instead to
write your own program to explore this question.

.. raw:: html

   </p>