:tocdepth: 2

.. _title_goes_here:

New Experiments: Sum of Squares and Plotting III
============================================================================

.. contents:: :local:

.. highlight:: python

What possible *Python* buitin data structure(s) do you think will be
best in storing the numbers that can be written?

.. code:: ipython2

    my_list_database = [0, 1, 2, 4, 5]

What if, in addition to the possible positive integers that can we can
write as the sum of two squares, we also want to know the number of ways
that they can be written. What *Python* builtin data structure(s) do you
think will be suitable in this case?

Let us create a database of some of the numbers that can be written
starting with those that we tried with pens and paper.

.. code:: ipython2

    number_of_ways = [1, 2, 1, 2, 2]

.. code:: ipython2

    possible_database = list(zip(my_list_database, number_of_ways)); possible_database

A more effective way is to use Python’s dictionary data structure. If
that is the case, then we could also have passed the Python variable
``possible_database`` to Python’s ``dict`` function create dictionary
object. That is,

.. code:: ipython2

    dict(possible_database)

Or we could also start everything with a dictionary and type in the data
we want to collect.

.. code:: ipython2

    sum_of_square_database = {0: [(0,0)], 1: [(1,0), (0,1)], 2:[(1,1)]}; sum_of_square_database

We can update the dictionary object assigned to the Python variable
``sum_of_square_database`` as follows:

.. code:: ipython2

    sum_of_square_database[4] = [(0,2), (2, 0)]

.. code:: ipython2

    sum_of_square_database

.. code:: ipython2

    sum_of_square_database[5] = [(1,2), (2, 1)]

.. code:: ipython2

    sum_of_square_database


After a while you will want to think of an effective way of doing this
by using some *Python* programming construct? What could be your
possible effective solution?

.. code:: ipython2

    sum_of_square_database = {}
    for a in range(20):
        for b in range(20):
            m = a^2 + b^2





Hopefully, by now you should have a fair amount of data in
``sum_of_square_database``. Let us now begin exploring the questions we
posed regarding the sum of two squares by querying the database we have
created. Here are the list of questions we posed:

-  Which positive integers can be written as a sum of two squares?
-  Which ones cannot?
-  Which positive integers can be written as a sum of squares of it
   factors?
-  Can there be a formula for expressing :math:`n` as the sum of two
   positive square numbers?
-  Which numbers can be written as a sum of squares of 2 prime numbers?
-  These numbers that can be written as a sum of two squares, are they
   odd or even?
-  Given :math:`a` and :math:`b` are prime, is the sum of their squares,
   :math:`a^{2}+b^{2}` prime?
-  Can the square roots of numbers be written in any other form aside
   from :math:`x^{2} + 0^{2}`?
-  Is there more than one way to get the :math:`n`, and if they is,
   what’s the relationship between the :math:`a`, :math:`b` and
   :math:`n`.

   .. raw:: html

      <hr>

I also possed the following:

-  Are there any special types of numbers that can be written?  (Or that
   cannot?)

   -  Primes
   -  even/odd, modulo 3, modulo 4, modulo 5, etc..
   -  A combination of the above

Let us take a look at a possible way in exploring the first three
questions we possed in class last time.

Exploring Questions 
~~~~~~~~~~~~~~~~~~~~

The goal of this subsection is answer the first three questions that we
possed concerning the sum of squares problems. You will learn what it
means to query the database we have created. Let us begin with the first
question.

Exploration 1 
^^^^^^^^^^^^^^

The question to explore is:

-  *Which positive integers can be written as a sum of two integer
   squares?*

What will be a possible answer to this?

.. code:: ipython2

    sum_of_square_database


That seems to answer the question. However, I think there is more we can
ask here. For example, Is there more to explore about these numbers? Is
there anything common with them or a subset of them? What do you think
we can do?

We may come back to this later.


Exploration 2 
^^^^^^^^^^^^^^

The question to explore is:

-  *Which positive numbers cannot be written as a sum of two integer
   squares?*

What will be a possible answer to this? How would you encode this in
Python in order to query the database ``sum_of_square_database``?


Is there more to explore about these numbers? Is there anything common
with them or a subset of them? What do you think we can do?

We may come back to this later.


Exploration 3 
^^^^^^^^^^^^^^

The question to explore is:

-  *Which positive integers can be written as a sum of two integer
   squares of it factors?*

In other words, among those positive integers :math:`n` can be written
as :math:`n = a^{2} + b^{2}` with :math:`a` and :math:`b` as integers,
which them are factors of :math:`n`. That is, :math:`a` and :math:`b`
both divides :math:`n`.

What will be a possible answer to this? How would you encode this in
Python in order to query the database ``sum_of_square_database``?





Exploration 4 
^^^^^^^^^^^^^^

The question to explore is:

-  *Can there be a formula for expressing :math:`n` as the sum of two
   positive square numbers?*

You may want to skip this for now.


Exploration 5 
^^^^^^^^^^^^^^

The question to explore is:

-  *These numbers that can be written as a sum of two squares, are they
   odd or even?*



Exploration 6 
^^^^^^^^^^^^^^

The question to explore is:

-  *Given :math:`a` and :math:`b` are prime, is the sum of their
   squares, :math:`a^{2}+b^{2}` prime?*

*Hint: You may want to use the SageMath function ``is_prime``. Try and
read the documentation so you know how to use it.*



Exploration 7 
^^^^^^^^^^^^^^

The question to explore is:

-  *Can the square roots of numbers be written in any other form aside
   from :math:`x^{2} + 0^{2}`?*

In other words, if :math:`n` is a square, i.e.,
:math:`\exists\, x\in\mathbb{Z}` with :math:`n = x^{2}`, then are there
**positive integers** :math:`a, b` such that :math:`n = a^{2} + b^{2}`?



Exploration 8 
^^^^^^^^^^^^^^

The question to explore is:

-  *Is there more than one way to write a positive integer :math:`n` as
   the sum of two integer squares :math:`a^{2} + b^{2}`, and if they is,
   what’s the relationship between :math:`n`, :math:`a` and :math:`b`?*



Exploration 9 
^^^^^^^^^^^^^^

The question to explore is:

-  *Can prime numbers be written as a sum of two squares and if so, do
   they follow some underlying pattern?*



Congruences 
~~~~~~~~~~~~

I want to introduce an elementary operation that might be useful in our
exploration; namely, modulo arithmetic. You should have seen this
before. It has something to do with divisibilty.

To start, let’s compute.  What is the remainder of :math:`25` when
divided by :math:`6`?  Do it by hand first.

.. code:: ipython2

    mod(25, 6)

From the division algorithm, we know that such a remainder is unique. 
If we divide :math:`x` by :math:`m`, then
:math:`0\leq {\rm mod}(x,m)< m`. But lots and lots of different numbers
can have the same remainder!

.. code:: ipython2

    [mod(num, 6) for num in [1, 7, 13, 19, 25, -5, -11, 6001, -17]]

| In mathematics, what we often do in such a situation where structure
  is shared is to connect things with a *relation*.
| A relation is a very general notion, and basically it exists once you
  define it. Our relation will be called **congruence**, denoted by
  :math:`\equiv` and it is massively important. We essentially use the
  same definitions and notation that Gauss came up with.

**Definition**: We say that :math:`a` is congruent to :math:`b` modulo
:math:`n`, or :math:`a \equiv b \, ({\rm mod} \, n)`, precisely if
:math:`n\mid (a−b)`.

| This is *exactly* the same thing as leaving the same remainder.  It is
  very useful to try to prove that these conditions are the same.
| In our case, saying :math:`25\equiv 1\equiv -5` (mod :math:`6`) is the
  same as saying :math:`25=4\cdot 6 +1` and :math:`1=0\cdot 6 + 1` and
  :math:`-5=-1\cdot 6+1`.
| This idea gives us a *lot* of power.  For instance, calculating
  :math:`2^{1000000000}` (mod 3) instantaneous for me - it’s :math:`1`.

I can check it with *SageMath*:

.. code:: ipython2

    %time mod(2^1000000000,3)

Yet I did it instantaneously in my head. Of course, the reason is not
that I am clever, but that congruence can be turned into arithmetic!
Here are two useful properties:

-  If :math:`a\equiv b` (mod :math:`m`), then :math:`a+c\equiv b+c` (mod
   :math:`m`).
-  If :math:`a\equiv b` (mod :math:`m`), then :math:`ac\equiv bc` (mod
   :math:`m`).

Now I reveal my secret: :math:`2\equiv -1` (mod 3), and
:math:`(-1)^{1000000000}=1`, like all even powers of negative one. 
Ta-dah!

What I’ve done is *first* think of the original number as in the
congruence, and then taken its power. *SageMath* verifies this approach
is much faster, and even for much bigger powers:

.. code:: ipython2

    b = mod(2,3); b

.. code:: ipython2

    print(type(b))

.. code:: ipython2

    %time b^1000000000000000000000000000000

| What was computed above is not a trick; I definitely couldn’t do
  :math:`2000^{1000}`, or even :math:`16^{1000}`, in my head.
| There is another set of properties that congruence has. Congruence is
  *reflexive, symmetric, and transitive*. That is, all the things you
  know are true about equality are also true about congruence (with a
  particular modulus :math:`n` picked, of course).

-  For any :math:`a\in \mathbb{Z}`, :math:`a\equiv a` (mod :math:`n`).
-  If :math:`a\equiv b` mod (:math:`n`), then :math:`b\equiv a` (mod
   :math:`n`).
-  If it happens that both :math:`a\equiv b` and :math:`b\equiv c` (mod
   :math:`n`), then :math:`a\equiv c` (mod :math:`n`) as well.

If we combine all of these facts, it basically means we can divide up
all the integers into “**equivalence classes**”. That is,
:math:`\mathbb{Z}` can be broken up into disjoint pieces which we are
free to consider as units, and which stay different.

We denote such a class by the notation

.. math:: [a]=\{\text{all numbers congruent to }a\text{ modulo }n\}\; .

 

So, for instance, the equivalence class we started with is

.. math:: [1]=\{1, 7, 13, 19, 25, -5, -11, 6001,\ldots\}

\ or perhaps better written as

.. math:: \{1+6n\mid n\in\mathbb{Z}\}=[1]\; .

**Definition**: We call the set of equivalence classes modulo :math:`n`
the *integers modulo n*, and denote them by :math:`\mathbb{Z}_n`.

.. code:: ipython2

    %time mod(2^3000000000,7)

.. code:: ipython2

    %time mod(2,7)^3000000000

I knew this one too.  Figure out why with your group members.

-  Then spend a while making up more examples of this.

   .. raw:: html

      </li>

-  Or, try to figure out how I know that :math:`123456` is divisible by
   :math:`3` but not divisible by :math:`9`, using congruences.

Now let us use the concept of modulo arithmetic in our exploration. In
your groups, try to come up with more questions which uses the modulo
operation and explore together. Try and record your findings.

Before you query the database ``sum_of_square_database`` with the
questions you have possed as a group, take a look at `Exploration
10 <#exploration-10>`__, where I possed a question that makes use of the
modulo operation. Explore this a group and record your findings.
Afterwards, you should explore the questions that you came up with.
Again remember to record your findings.


Exploration 10 
^^^^^^^^^^^^^^^

The question to explore is:

-  *Can even/odd numbers modulo 3, modulo 4, modulo 5, etc., be written
   as a sum of two squares and if so, do they follow some underlying
   pattern?*














Can you think of a way to solve this problem? *Hint: What do you know
about equations of this form :math:`n = a^{2} + b ^{2}`?*

.. code:: ipython2

    var('y')
    n = 5
    P = implicit_plot( x^2 + y^2 == n, (x, -sqrt(n), sqrt(n)), (y, -sqrt(n), sqrt(n)) )
    lattice_pts = [ [i,j] for i in [floor(-sqrt(n))..ceil(sqrt(n))] for j in [floor(-sqrt(n))..ceil(sqrt(n))] ]
    plot_lattice_pts = points(lattice_pts, rgbcolor = (0, 0, 0), pointsize = 10)
    P + plot_lattice_pts



.. image:: ./images/output_87_0.png


This brings up the question of how to do such plotting in the first
place? We will look at this in more detail in the next
`Section <#more-plotting-and-graphics-in-two-dimensions>`__.

More Plotting and Graphics in Two Dimensions 
---------------------------------------------

There is absolutely no way we could cover all the graphics in *SageMath*
(or the program that does it for *SageMath*, matplotlib) in one day, or
even a week. We will look at a bunch of different resources you have
access to, and see lots of different plot types. As we go through these
resources, think of how they will be of in solving our new experiment or
where you could have used them some time back in your academic career. I
definitely do not know everything about the plotting command.
Nevertheless, you may interrupt me with your question so that we can
explore the solution together.

-  We will begin with the `advanced
   2D-plotting <http://localhost:8891/kernelspecs/sagemath/doc/prep/Advanced-2DPlotting.html>`__
   in the built-in live documentation. (This link only works if you are
   already using *SageMath*; the \ `non-live version is
   here <http://www.sagemath.org/doc/prep/Advanced-2DPlotting.html>`__.
-  There are two very important pages with many, MANY examples - the
   documentation for
   `plot <http://www.sagemath.org/doc/reference/plotting/sage/plot/plot.html>`__ and
   that for \ `showing
   graphics <http://www.sagemath.org/doc/reference/plotting/sage/plot/graphics.html#sage.plot.graphics.Graphics.show>`__.
-  The \ `general plotting
   reference <http://www.sagemath.org/doc/reference/plotting/index.html>`__ -
   there are a lot of surprises, like animation, etc.

| Remember, you should feel free to stop listening for a while if you
  can want to try something out!
| Once we’ve seen enough examples, please either start using *SageMath*
  to explore the sums of squares, *or* try to recreate your favorite
  graphic using *SageMath*!